[LLVMdev] Reassociating expressions involving GEPs

[Stefanus Du Toit]

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."

--
Stefanus Du Toit <stefanus.dutoit at rapidmind.com>
   RapidMind Inc.
   phone: +1 519 885 5455 x116 -- fax: +1 519 885 1463