llvm dev - Mar 2015 - [LLVMdev] Question about shouldMergeGEPs in InstructionCombining

On Fri, Mar 13, 2015 at 10:16 AM Mark Heffernan <meheff at google.com>
wrote:
> On Thu, Mar 12, 2015 at 2:34 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
>
>> It is not clear to me at all that preventing the merging is the right
>> solution. There are a large number of analysis, including alias
analysis,
>> and optimizations that use GetUnderlyingObject, and related routines to
>> search back through GEPs. They only do this up to some small finite
depth
>> (six, IIRC). So reducing the GEP depth is likely the right solution for
>> InstCombine (which has the job of canonicalizing the IR).
>>
>> We should, however, pull these apart somewhere, and probably in some
way
>> that is address-mode aware. I'd recommend trying to split non-free
(via the
>> addressing-mode) loop-invariant parts of GEPs out of loops in
CodeGenPrep.
>>
>
> Thanks, Hal.  I'll have a look at CGP to see how this might be done. 
It's
> a little more complicated than just pulling the GEP apart, there needs to
> be a loop-invariant-aware reassociation to undo the damage done by the
> initial merge.
>
So, this is in fact, just using the ranks reassociation would normally use,
to do splitting :)

That is, even outside of geps, you end up with chains of operations where,
if you moved the operands around, you would expose loop-invariant
calculation.

Reassociation builds a rank map ordered by RPO traversal of the CFG, and
uses it to place operations at the same rank into the same expression.
This guarantees deeper loops have higher ranks.
For your purposes, if you have it calculated already, you could just use
loop depth instead of RPO ordering, since you only care about invariantness
(the downside to not using RPO here is that you may increase register
pressure. The upside is it's easier to reason about the ranks for your
purposes).

Anyway, reassociate tries to place operations with the lowest ranks into
leaf computations, since those are "the most loop invariant".

You want to do exactly the same thing, with likely the same algorithm,
splitting geps as necessary into "leaf geps" to place low-ranking
operations in the same gep.

The only heuristic part is "what is the lowest rank you want to split
for".
If you have stuff at rank 0 and stuff not at rank 0, you always want to
split out the rank 0 stuff.
rank 1 and rank 2, well, if you are using loop depth, it can only  be
invariant in a loop of rank 2, etc.
You don't need to split if rank == highest rank in functions, since you are
guaranteed it is not invariant in any loop in that case
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150313/42191b03/attachment.html>

Hi Daniel,

Thanks! I wonder if there's a way to reuse some code in Reassociation.
Looks like most of the logic we want to implement is in Reassociate.cpp
already. But the entire pass seems too expensive to run with CGP or after
each instcombine.

Jingyue

On Fri, Mar 13, 2015 at 10:43 AM Daniel Berlin <dberlin at dberlin.org>
wrote:
> On Fri, Mar 13, 2015 at 10:16 AM Mark Heffernan <meheff at
google.com> wrote:
>
>> On Thu, Mar 12, 2015 at 2:34 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
>>
>>> It is not clear to me at all that preventing the merging is the
right
>>> solution. There are a large number of analysis, including alias
analysis,
>>> and optimizations that use GetUnderlyingObject, and related
routines to
>>> search back through GEPs. They only do this up to some small finite
depth
>>> (six, IIRC). So reducing the GEP depth is likely the right solution
for
>>> InstCombine (which has the job of canonicalizing the IR).
>>>
>>> We should, however, pull these apart somewhere, and probably in
some way
>>> that is address-mode aware. I'd recommend trying to split
non-free (via the
>>> addressing-mode) loop-invariant parts of GEPs out of loops in
CodeGenPrep.
>>>
>>
>> Thanks, Hal.  I'll have a look at CGP to see how this might be
done.
>> It's a little more complicated than just pulling the GEP apart,
there needs
>> to be a loop-invariant-aware reassociation to undo the damage done by
the
>> initial merge.
>>
>
> So, this is in fact, just using the ranks reassociation would normally
> use, to do splitting :)
>
> That is, even outside of geps, you end up with chains of operations where,
> if you moved the operands around, you would expose loop-invariant
> calculation.
>
> Reassociation builds a rank map ordered by RPO traversal of the CFG, and
> uses it to place operations at the same rank into the same expression.
> This guarantees deeper loops have higher ranks.
> For your purposes, if you have it calculated already, you could just use
> loop depth instead of RPO ordering, since you only care about invariantness
> (the downside to not using RPO here is that you may increase register
> pressure. The upside is it's easier to reason about the ranks for your
> purposes).
>
> Anyway, reassociate tries to place operations with the lowest ranks into
> leaf computations, since those are "the most loop invariant".
>
> You want to do exactly the same thing, with likely the same algorithm,
> splitting geps as necessary into "leaf geps" to place low-ranking
> operations in the same gep.
>
> The only heuristic part is "what is the lowest rank you want to split
for".
> If you have stuff at rank 0 and stuff not at rank 0, you always want to
> split out the rank 0 stuff.
> rank 1 and rank 2, well, if you are using loop depth, it can only  be
> invariant in a loop of rank 2, etc.
> You don't need to split if rank == highest rank in functions, since you
> are guaranteed it is not invariant in any loop in that case
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150313/a9129452/attachment.html>

Honestly, i'm not sure it's worth it.
If you want stuff,  the only thing you want is probably rewriteExprTree.
The ranking code is about 10 lines if you are just using loop depth, and so
is the sorting code.
You have to do splitting before you hand it to rewriteexprtree anyway.

Otherwise, reassociate probably has too much high level logic/optimization
for what you want, and it's not entirely cleanly factored


On Fri, Mar 13, 2015 at 11:32 AM Jingyue Wu <jingyue at google.com> wrote:
> Hi Daniel,
>
> Thanks! I wonder if there's a way to reuse some code in Reassociation.
> Looks like most of the logic we want to implement is in Reassociate.cpp
> already. But the entire pass seems too expensive to run with CGP or after
> each instcombine.
>
> Jingyue
> On Fri, Mar 13, 2015 at 10:43 AM Daniel Berlin <dberlin at
dberlin.org>
> wrote:
>
>> On Fri, Mar 13, 2015 at 10:16 AM Mark Heffernan <meheff at
google.com>
>> wrote:
>>
>>> On Thu, Mar 12, 2015 at 2:34 PM, Hal Finkel <hfinkel at
anl.gov> wrote:
>>>
>>>> It is not clear to me at all that preventing the merging is the
right
>>>> solution. There are a large number of analysis, including alias
analysis,
>>>> and optimizations that use GetUnderlyingObject, and related
routines to
>>>> search back through GEPs. They only do this up to some small
finite depth
>>>> (six, IIRC). So reducing the GEP depth is likely the right
solution for
>>>> InstCombine (which has the job of canonicalizing the IR).
>>>>
>>>> We should, however, pull these apart somewhere, and probably in
some
>>>> way that is address-mode aware. I'd recommend trying to
split non-free (via
>>>> the addressing-mode) loop-invariant parts of GEPs out of loops
in
>>>> CodeGenPrep.
>>>>
>>>
>>> Thanks, Hal.  I'll have a look at CGP to see how this might be
done.
>>> It's a little more complicated than just pulling the GEP apart,
there needs
>>> to be a loop-invariant-aware reassociation to undo the damage done
by the
>>> initial merge.
>>>
>>
>> So, this is in fact, just using the ranks reassociation would normally
>> use, to do splitting :)
>>
>> That is, even outside of geps, you end up with chains of operations
>> where, if you moved the operands around, you would expose
loop-invariant
>> calculation.
>>
>> Reassociation builds a rank map ordered by RPO traversal of the CFG,
and
>> uses it to place operations at the same rank into the same expression.
>> This guarantees deeper loops have higher ranks.
>> For your purposes, if you have it calculated already, you could just
use
>> loop depth instead of RPO ordering, since you only care about
invariantness
>> (the downside to not using RPO here is that you may increase register
>> pressure. The upside is it's easier to reason about the ranks for
your
>> purposes).
>>
>> Anyway, reassociate tries to place operations with the lowest ranks
into
>> leaf computations, since those are "the most loop invariant".
>>
>> You want to do exactly the same thing, with likely the same algorithm,
>> splitting geps as necessary into "leaf geps" to place
low-ranking
>> operations in the same gep.
>>
>> The only heuristic part is "what is the lowest rank you want to
split
>> for".
>> If you have stuff at rank 0 and stuff not at rank 0, you always want to
>> split out the rank 0 stuff.
>> rank 1 and rank 2, well, if you are using loop depth, it can only  be
>> invariant in a loop of rank 2, etc.
>> You don't need to split if rank == highest rank in functions, since
you
>> are guaranteed it is not invariant in any loop in that case
>>
> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150313/6df49976/attachment.html>

----- Original Message -----
> From: "Jingyue Wu" <jingyue at google.com>
> To: "Daniel Berlin" <dberlin at dberlin.org>, "Mark
Heffernan" <meheff at google.com>, "Hal Finkel" <hfinkel
at anl.gov>
> Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Friday, March 13, 2015 1:31:59 PM
> Subject: Re: [LLVMdev] Question about shouldMergeGEPs in
InstructionCombining
> 
> 
> Hi Daniel,
> 
> Thanks! I wonder if there's a way to reuse some code in
> Reassociation. Looks like most of the logic we want to implement is
> in Reassociate.cpp already. But the entire pass seems too expensive
> to run with CGP or after each instcombine.
> 
I don't think that the algorithm itself is too expensive for CGP (and we
already do dominance-aware GEP splitting in CGP), we don't do any of this at
-O0 anyway, but we need something that specifically handles GEPs. For most
operations (adds, etc.) reassociating in a way likely to enable LICM is, I
believe, already our canonical IR form, and so we do that as part of the normal
optimization pipeline. For GEPs, it is anti-canonical, and so GEPs are the
special case that needs handling in CGP where we perform these kinds of
anti-canonical transformations.

 -Hal
> 
> Jingyue
> 
> On Fri, Mar 13, 2015 at 10:43 AM Daniel Berlin < dberlin at dberlin.org
> > wrote:
> 
> 
> 
> 
> On Fri, Mar 13, 2015 at 10:16 AM Mark Heffernan < meheff at google.com
>
> wrote:
> 
> 
> 
> 
> 
> On Thu, Mar 12, 2015 at 2:34 PM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> It is not clear to me at all that preventing the merging is the right
> solution. There are a large number of analysis, including alias
> analysis, and optimizations that use GetUnderlyingObject, and
> related routines to search back through GEPs. They only do this up
> to some small finite depth (six, IIRC). So reducing the GEP depth is
> likely the right solution for InstCombine (which has the job of
> canonicalizing the IR).
> 
> We should, however, pull these apart somewhere, and probably in some
> way that is address-mode aware. I'd recommend trying to split
> non-free (via the addressing-mode) loop-invariant parts of GEPs out
> of loops in CodeGenPrep.
> 
> 
> 
> 
> 
> 
> Thanks, Hal. I'll have a look at CGP to see how this might be done.
> It's a little more complicated than just pulling the GEP apart,
> there needs to be a loop-invariant-aware reassociation to undo the
> damage done by the initial merge.
> 
> 
> 
> 
> So, this is in fact, just using the ranks reassociation would
> normally use, to do splitting :)
> 
> 
> That is, even outside of geps, you end up with chains of operations
> where, if you moved the operands around, you would expose
> loop-invariant calculation.
> 
> 
> 
> Reassociation builds a rank map ordered by RPO traversal of the CFG,
> and uses it to place operations at the same rank into the same
> expression. This guarantees deeper loops have higher ranks.
> For your purposes, if you have it calculated already, you could just
> use loop depth instead of RPO ordering, since you only care about
> invariantness (the downside to not using RPO here is that you may
> increase register pressure. The upside is it's easier to reason
> about the ranks for your purposes).
> 
> 
> Anyway, reassociate tries to place operations with the lowest ranks
> into leaf computations, since those are "the most loop
invariant".
> 
> 
> You want to do exactly the same thing, with likely the same
> algorithm, splitting geps as necessary into "leaf geps" to place
> low-ranking operations in the same gep.
> 
> 
> The only heuristic part is "what is the lowest rank you want to split
> for".
> If you have stuff at rank 0 and stuff not at rank 0, you always want
> to split out the rank 0 stuff.
> rank 1 and rank 2, well, if you are using loop depth, it can only be
> invariant in a loop of rank 2, etc.
> You don't need to split if rank == highest rank in functions, since
> you are guaranteed it is not invariant in any loop in that case
> ______________________________ _________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/ mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory