llvm dev - Sep 2017 - Equality saturation: Status & how-to-upstream discussion

There's the explicit sinking code in the main worklist processing loop
around TryToSinkInstruction. I don't believe that can move code into a loop
since it can only move into a successor block with no predecessors. So I
don't believe that's what happened in the addressspace cast case.

Then there's accidental sinking that occurs when InstCombine looks at two
or more instructions with some in another basic block and combines them to
two or more instructions. In that case all of the combined instructions
will be created in the block that contains the instruction that started the
combine since that's going to be the insert location for the IRBuilder. I
think that's what happened in the addressspace cast case. I don't know
how
to fix this without qualifying every transform that produces mutliple
instructions with a check that all the original instructions started in the
same basic block.

~Craig

On Tue, Sep 12, 2017 at 11:15 AM, Davide Italiano via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
>
> On Sep 12, 2017 1:34 AM, "David Chisnall via llvm-dev" <
> llvm-dev at lists.llvm.org> wrote:
>
> The sinking in instcombine is not always a win.  We hit a case recently
> where instcombine made a hot loop in a benchmark significantly slower by
> moving an address-space cast instruction into a loop as part of its gep of
> addrspacecast to addrspacecast of gep transformation.  On our architecture,
> this translates to an extra instruction in a hot loop for the address-space
> cast *and* means that we then can’t use the complex addressing modes for
> the loads and stores because we have an address space cast in between the
> GEP and the memory op.  We end up increasing the number of instruction in
> the loop by around 20%, with a corresponding decrease in performance.
>
> My somewhat long-winded point is that I’m not convinced that InstCombine
> is doing sufficient reasoning when it moves instructions between basic
> blocks to determine that the moves actually make sense.
>
>
> My somewhat long-winded point is instead that IC shouldn't even bother
> trying to sink. I understand it may eventually expose other optimizations
> but it doesn't seem to be worth the complexity added. As you say, the
> heuristic is pretty simple (fold instructions to blocks with a single
> predecessor, IIRC, but don't quote me on that). There are cases where
it
> regresses, and I'm not surprised as sinking is not done after a proper
> analysis (as, e.g. the one GVNSink or LICM are doing). You could probably
> catch some cases teaching IC about profile metadata when taking sink
> decisions, but that sounds like adding even more madness.
>
> --
> Davide
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170912/b1b44f2c/attachment.html>

Hello all,

I've been working on a prototype implementation of equality saturation on a
personal branch:

https://github.com/bollu/llvm/tree/1ab19bdb5eba00d1d508535758d700c1d60a3815

For those who have read the paper, I now create A-PEG nodes. I need to
create PEG nodes from these.

There are four more "steps" before this is a minimal, conservatively
correct implementation:

- Fill in the BasicBlock nodes with information from llvm::BasicBlock.
- Implement the PEG -> CFG back-conversion (what the paper calls reversion).
- Figure out how to handle things like switch and more complex terminators
which are not directly handled by the original paper (as far as I have
seen. Please correct me if am wrong).

This brings me to the question, how is this going to be upstreamed? Will I
have to write an RFC that details what changes are proposed by this?

I'm new to adding a large "chunk" of changes, so any help is very
appreciated!

Thanks,
~Siddharth
-- 
Sending this from my phone, please excuse any typos!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170918/61bda79b/attachment.html>

I'm sorry, there are a couple of inaccuracies in the above e-mail:

1. This will be a minimal working example, not a conservatively correct
implementation.
2. I also need to perform the following steps:

- Convert stub "condition" nodes to actual nodes with information.
- Perform equality saturation till fixpoint / timeout.
- Use some kind of profitability heuristic to pick final optimisations.

Once this is done, I can have it bail out on code it does not understand.
Then, this is a "minimal working example" on which stuff can be built.

Thanks, and sorry for the rushed e-mail
~Siddharth

On Mon, 18 Sep 2017 at 02:35 (IIIT) Siddharth Bhat <
siddharth.bhat at research.iiit.ac.in> wrote:
> Hello all,
>
> I've been working on a prototype implementation of equality saturation
on
> a personal branch:
>
> https://github.com/bollu/llvm/tree/1ab19bdb5eba00d1d508535758d700c1d60a3815
>
> For those who have read the paper, I now create A-PEG nodes. I need to
> create PEG nodes from these.
>
> There are four more "steps" before this is a minimal,
conservatively
> correct implementation:
>
> - Fill in the BasicBlock nodes with information from llvm::BasicBlock.
> - Implement the PEG -> CFG back-conversion (what the paper calls
> reversion).
> - Figure out how to handle things like switch and more complex
> terminators which are not directly handled by the original paper (as far as
> I have seen. Please correct me if am wrong).
>
> This brings me to the question, how is this going to be upstreamed? Will I
> have to write an RFC that details what changes are proposed by this?
>
> I'm new to adding a large "chunk" of changes, so any help is
very
> appreciated!
>
> Thanks,
> ~Siddharth
> --
> Sending this from my phone, please excuse any typos!
>
-- 
Sending this from my phone, please excuse any typos!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170918/98fdf790/attachment.html>

> This brings me to the question, how is this going to be upstreamed? Will
> I have to write an RFC that details what changes are proposed by this?
Before you get to the stage of proposing changes, you should help us 
understand what the costs (compile time) and benefits (size/speed of 
generated code) are. LNT or SPEC CPU or LLVM itself are all good targets.

John

> I've been working on a prototype implementation of equality saturation
> on a personal branch:
>
> https://github.com/bollu/llvm/tree/1ab19bdb5eba00d1d508535758d700c1d60a3815
Usually when you fork a github repo, a "compare" button will appear
that
makes it easy for people to see the diffs with respect to the upstream 
version. But I'm not seeing that here -- did you do something 
non-standard when you forked LLVM?

John