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