[LLVMdev] Reassociating expressions involving GEPs

[Stefanus Du Toit]

Hello,

We've run across the following missed optimization: in the attached  
loop (addind.c/addind-opt.ll) there's a lookup into an array (V) using  
an indirect index (coming from another array, WI[k]) offset by a loop- 
invariant base (l). The full addressing expression can be reassociated  
so that we add the offset l to V's base first, and then add the  
indirect part. This makes the addition of the offset loop-invariant.

This is pretty much what you would get from reassociation on algebraic  
expressions, except that it's involving a GEP. Basically, we'd  
transform this:

   ; Note: %call and %tmp7 are loop-invariant
   %tmp4 = load i32* %arrayidx
   %add = add i32 %tmp4, %call
   %arrayidx8 = getelementptr float* %tmp7, i32 %add

into this:

   %tmp4 = load i32* %arrayidx
   %base = getelementptr float* %tmp7, %call
   %arrayidx8 = getelementptr float* %base, i32 %tmp4

The computation of %base then becomes loop-invariant and can be lifted  
out.

What's the best way to add this optimization to LLVM? Should the  
reassociate pass be made aware of GEPs somehow? Note that the  
transformation also involves turning an add into a GEP, so I'm not  
sure reassociate is the right place.

Suggestions appreciated! Thanks,

Stefanus

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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: addind.c
Type: application/octet-stream
Size: 271 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090130/48849bae/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: addind-opt.ll
Type: application/octet-stream
Size: 1740 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090130/48849bae/attachment-0001.obj>