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
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
On Feb 25, 2009, at 12:12 PM, Stefanus Du Toit wrote:>> 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."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
On 9-Mar-09, at 12:14 AM, Chris Lattner wrote:> 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.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 ==================================================================--- LangRef.html (revision 66420) +++ LangRef.html (working copy) @@ -3637,11 +3637,13 @@ } </pre> -<p>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. -The one exception for this rule is zero length arrays. These arrays are -defined to be accessible as variable length arrays, which requires access -beyond the zero'th element.</p> +<p>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 when accessed with an instruction that dereferences the +pointer (e.g. a load or store instruction). The one exception for +this rule is zero length arrays. These arrays are defined to be +accessible as variable length arrays, which requires access beyond the +zero'th element.</p> <p>The getelementptr instruction is often confusing. For some more insight into how it works, see <a href="GetElementPtr.html">the getelementptr -- Stefanus Du Toit <stefanus.dutoit at rapidmind.com> RapidMind Inc. phone: +1 519 885 5455 x116 -- fax: +1 519 885 1463
On Mar 8, 2009, at 9:14 PM, Chris Lattner wrote:> On Feb 25, 2009, at 12:12 PM, Stefanus Du Toit wrote: >>> 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." > > 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.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