Reassociating expressions involving GEPs

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

addind.c (271 Bytes)

addind-opt.ll (1.7 KB)

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

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

GEP overflow is undefined, but this sentence means that *accesses* to an array must be within its bounds. It is fine to GEP outside the array as long as you readjust the pointer back before access.

-Chris

Thanks, that was my hope. Maybe this should be spelled out in the langref, especially since it's inconsistent with C, where merely doing pointer arithmetic that yields an out-of-bounds pointer (except for "one element past the end") yields undefined behaviour.

Perhaps something like: (apologies for the inline patch):

Index: LangRef.html

These two sentences contain a contradiction. GEPing outside of an array
may lead to overflow, because in general one doesn't know where an
array will be placed within the address space. If GEP overflow is
undefined, then it's not fine to GEP outside the array, in general.

Dan

looks good to me, applied, thanks!
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090309/074908.html

-Chris