[LLVMdev] Reassociating expressions involving GEPs

[Dan Gohman]

On Feb 25, 2009, at 12:12 PM, Stefanus Du Toit wrote:

> On 30-Jan-09, at 6:14 PM, Eli Friedman wrote:
>> On Fri, Jan 30, 2009 at 3:03 PM, Stefanus Du Toit
>> <stefanus.dutoit at rapidmind.com> wrote:
>>> The computation of %base then becomes loop-invariant and can be
>>> lifted out.
>>>
>>> What's the best way to add this optimization to LLVM?
>>
>> Probably the best place is LICM itself... only loop transformations
>> are aware whether something is loop-invariant.
>
> After considering this some more it does seem like Reassociate is a
> good place for this to go. While it's not explicitly aware of loops,
> it uses a ranking based on an RPO traversal of the CFG to give higher
> ranks to values the deeper they are in loop nests.
>
> LICM will then be enabled to lift things out based on the  
> reassociation.
>
>> Although, I'm not completely sure the transformation is safe, at  
>> least
>> the way you're stating it; unlike add, GEP has undefined overflow, so
>> this isn't right in cases like %call == %tmp4 == INT_MIN.
>
> Hmm, you raise a good point. There's a similar issue even without
> overflow, e.g. (gep p, (add -1, t)). The lang ref isn't exactly clear
> on this, but one interpretation says that if p points to the start of
> an array allocation, (gep p, -1) has undefined behaviour. Perhaps
> someone (Chris?) can clarify whether that's what's meant, or whether
> only loads and stores out of bounds are considered undefined. The
> sentences in question are:
>
> "Note that it is undefined to access an array out of bounds: array and
> pointer indexes must always be within the defined bounds of the array
> type."

LangRef.html doesn't apparently spell this out, but the common
understanding is that overflow in a GEP is always undefined. I
interpret it to mean that (gep p, -1) is undefined when p is
the beginning of an allocation. This is more conservative than
common targets require, but it's consistent with C.

For that reason, it's tempting suggest that this transformation
be done in CodeGen, as all pointer arithmetic is in lowered
form. However, the part of CodeGen that does reassociation
doesn't currently know anything about loops, so it would
require some non-trivial infrastructure work.

Dan