Hello,
I'm working on refining the definition of getelementptr (GEP) to
clarify its semantics and to allow front-ends to provide additional
information to optimization passes.
To help support this, I'd like to propose the following rule:
Any memory access must be done though a pointer value associated
with with address range of the memory access, otherwise the behavior
is undefined.
"associated with" is defined as follows:
- A pointer value formed from a getelementptr instruction is
associated with the addresses associated with the first operand of
the getelementptr.
- An addresses of a global variable is associated with the address
range of the variable's storage.
- The result value of an allocation instruction is associated with
the address range of the allocated storage.
- A null pointer is associated with no addresses.
- A pointer value formed by a ptrtoint is associated with all address
ranges of all pointer values that contribute (directly or
indirectly) to the computation of the pointer's value.
- An integer value other than zero may be associated with address
ranges allocated through mechanisms other than those provided by
LLVM; such ranges shall not overlap with any ranges of address
allocated by mechanisms provided by LLVM.
For example, in an instruction like this:
%p = getelementptr [4 x i8]* @A, i32 0, i32 %huge
if %huge is beyond the size of @A, %p could potentially point into
some object other than @A. This rule says that it's not valid to use
%p to access that other object. %p would only be usable for memory
accesses when it points within @A.
C and C-like front-ends already obey this rule, since in C pointer
arithmetic results must remain within an allocated object (or one
past the end), which is more strict.
Front-ends that do crazy things to pointers may need to use
ptrtoint+arithmetic+inttoptr instead of getelementptr. If the
target-independent properties of getelementptr are needed, the
"getelementptr null" trick may be useful.
With this rule, BasicAliasAnalysis and similar analyses that depend
on being able to track a pointer value up to its base value will be
able to safely climb through getelementptr definitions without
needing any further guarantees.
That means that this rule will eliminate the most severe need for
having getelementptr overflow produce undefined results. This will
make it practical to have an undefined-on-overflow flag for
getelementptr that can be meaningfully set to either true or false.
A non-overflowing option for getelementptr would be useful to allow
SCEVExpander and other passes to convert code like this:
%a = mul %x, 4
%b = add %y, %a
%c = getelementptr [4 x i8]* @Object, 0, %b
into this:
%c = getelementptr [4 x i8]* @Object, %x, %y
which wouldn't otherwise be safe because (getelementptr @Object, %x)
by itself might overflow. (From a low-level perspective this isn't
much of an optimization, but from a high-level perspective it's
easier for non-SCEV-based passes to analyze.)
Comments and suggestions are welcome,
Dan
On Wednesday 22 July 2009 13:30, Dan Gohman wrote:> - A pointer value formed by a ptrtoint is associated with all address > ranges of all pointer values that contribute (directly or > indirectly) to the computation of the pointer's value.Do you mean inttoptr here? And that "all pointer values that contribute (directly or indirectly) to the computation of the pointer's value" could equally mean "all pointer values that contribute (directly or indirectly) to the computation of the integer's value?"> - An integer value other than zero may be associated with address > ranges allocated through mechanisms other than those provided by > LLVM; such ranges shall not overlap with any ranges of address > allocated by mechanisms provided by LLVM.What's the intent here? Are you basically saying that memory regions accessed through random integer arithmetic can't overlap memory regions allocated by alloca, malloc, etc.? If so, my sense is that's too demanding. In general one does not know the aliasing properties of addresses computed entirely by integer arithmetic. It could be some misguided user trying to "help" the compiler by explicitly linearizing addressing or it could be an embedded developer computing a memory-mapped I/O address. There's just no way to know.> Front-ends that do crazy things to pointers may need to use > ptrtoint+arithmetic+inttoptr instead of getelementptr. If the > target-independent properties of getelementptr are needed, the > "getelementptr null" trick may be useful.To clarify, the ptrtoint+arithmetic+inttoptr would still be legal? -Dave
On Wed, Jul 22, 2009 at 11:30 AM, Dan Gohman<gohman at apple.com> wrote:> - The result value of an allocation instruction is associated with > the address range of the allocated storage.Might want to clarify this to include calloc/realloc.> - A null pointer is associated with no addresses.A null pointer in address space 0.> - A pointer value formed by a ptrtoint is associated with all address > ranges of all pointer values that contribute (directly or > indirectly) to the computation of the pointer's value.I assume you mean inttoptr?> A non-overflowing option for getelementptr would be useful to allow > SCEVExpander and other passes to convert code like this: > %a = mul %x, 4 > %b = add %y, %a > %c = getelementptr [4 x i8]* @Object, 0, %b > > into this: > %c = getelementptr [4 x i8]* @Object, %x, %ySo a "defined-overflow" gep would act like wrapping integer arithmetic in the width of the pointer? Then what exactly is the definition of an "undefined-overflow" gep? Here's a first shot at a definition: "Considering a GEP as a series of calculations, one for each index, if the result that would be obtained by performing exact arithmetic (treating the index as a signed integer) is outside the bounds of the address range of the base pointer, the result is undefined." -Eli
On Jul 22, 2009, at 12:33 PM, David Greene wrote:> On Wednesday 22 July 2009 13:30, Dan Gohman wrote: > > >> - A pointer value formed by a ptrtoint is associated with all >> address >> >> ranges of all pointer values that contribute (directly or >> >> indirectly) to the computation of the pointer's value. >> > > Do you mean inttoptr here? And that "all pointer values that > contribute > (directly or indirectly) to the computation of the pointer's value" > could > equally mean "all pointer values that contribute (directly or > indirectly) to > the computation of the integer's value?"Yes, I meant inttoptr instead of ptrtoint here.> > >> - An integer value other than zero may be associated with address >> >> ranges allocated through mechanisms other than those provided by >> >> LLVM; such ranges shall not overlap with any ranges of address >> >> allocated by mechanisms provided by LLVM. >> > > What's the intent here? Are you basically saying that memory > regions accessed > through random integer arithmetic can't overlap memory regions > allocated by > alloca, malloc, etc.? If so, my sense is that's too demanding. In > general > one does not know the aliasing properties of addresses computed > entirely by > integer arithmetic. It could be some misguided user trying to > "help" the > compiler by explicitly linearizing addressing or it could be an > embedded > developer computing a memory-mapped I/O address. There's just no > way to > know.The intent is to cover code like this: %p = alloca i32 %q = inttoptr i64 0123456789 to i32* Here, %p and %q are assumed to be non-aliasing. This kind of thing is used by some JITs; they allocate objects via custom mechanisms and then tell LLVM IR about the address of the objects via magic integer constants like this. The optimizer is already making this assumption today, though implicitly. If the user hand-linearizes addressing using casts to integers, it will still be supported -- that's what the broad language for inttoptr above is intended to cover.> > >> Front-ends that do crazy things to pointers may need to use >> >> ptrtoint+arithmetic+inttoptr instead of getelementptr. If the >> >> target-independent properties of getelementptr are needed, the >> >> "getelementptr null" trick may be useful. >> > > To clarify, the ptrtoint+arithmetic+inttoptr would still be legal?Yes, subject to constraints in the bullet point quoted at the top of this email, which effectively just spelling out rules that are already assumed today. Dan
On Wed, Jul 22, 2009 at 12:33 PM, David Greene<dag at cray.com> wrote:>> - An integer value other than zero may be associated with address >> ranges allocated through mechanisms other than those provided by >> LLVM; such ranges shall not overlap with any ranges of address >> allocated by mechanisms provided by LLVM. > > What's the intent here? Are you basically saying that memory regions accessed > through random integer arithmetic can't overlap memory regions allocated by > alloca, malloc, etc.?Yes, I think that's the intent.> If so, my sense is that's too demanding. In general > one does not know the aliasing properties of addresses computed entirely by > integer arithmetic. It could be some misguided user trying to "help" the > compiler by explicitly linearizing addressing or it could be an embedded > developer computing a memory-mapped I/O address. There's just no way to > know.If a memory-mapped I/O address aliases the stack, there's something seriously messed up going on... of course, we wouldn't assume anything about whether 1000 and 2000 alias.>> Front-ends that do crazy things to pointers may need to use >> ptrtoint+arithmetic+inttoptr instead of getelementptr. If the >> target-independent properties of getelementptr are needed, the >> "getelementptr null" trick may be useful. > > To clarify, the ptrtoint+arithmetic+inttoptr would still be legal?Yes, I think that is the intent. -Eli
On 2009-07-22 21:30, Dan Gohman wrote:> Hello, > > I'm working on refining the definition of getelementptr (GEP) to > clarify its semantics and to allow front-ends to provide additional > information to optimization passes. > > To help support this, I'd like to propose the following rule: > > Any memory access must be done though a pointer value associated > with with address range of the memory access, otherwise the behavior > is undefined. >If I compute an out-of-bounds GEPs and use it in ICMP is that undefined behaviour, or wrapping behaviour? Instcombine currently does this transform ((gep Ptr, OFFSET) cmp Ptr) ---> (OFFSET cmp 0), which is perfectly fine when GEP is assumed to have undefined behavior on overflow, but is wrong if GEP is allowed to overflow with well defined behavior (it wraps). Also will can the behavior of GEP be changed depending on llvm-gcc's -fno-strict-aliasing/-fwrapv/-fno-strict-pointer-overflow flags?> Front-ends that do crazy things to pointers may need to use > ptrtoint+arithmetic+inttoptr instead of getelementptr. If the > target-independent properties of getelementptr are needed, the > "getelementptr null" trick may be useful.Will various optimizations make sure they don't introduce undefined operations in programs with otherwise well defined semantics? I think instcombine may turn them into GEPs, thus transforming a program with well defined semantics according to above rules into undefined semantics. Of course if the optimizer can see that the access is always well defined it should do this transform. Best regards, --Edwin
On Jul 22, 2009, at 12:56 PM, Eli Friedman wrote:> On Wed, Jul 22, 2009 at 11:30 AM, Dan Gohman<gohman at apple.com> wrote: > >> - The result value of an allocation instruction is associated with >> >> the address range of the allocated storage. >> > > Might want to clarify this to include calloc/realloc.These sort of fall under the category of allocations done outside of LLVM IR, but it'd be better to address this case explicitly. I'll make a note of that.> > >> - A null pointer is associated with no addresses. >> > > A null pointer in address space 0.I'm not fond of weird address-space semantics, but for consistency with what the optimizer is currently doing, you're right.> > >> - A pointer value formed by a ptrtoint is associated with all >> address >> >> ranges of all pointer values that contribute (directly or >> >> indirectly) to the computation of the pointer's value. >> > > I assume you mean inttoptr?Yes.> > >> A non-overflowing option for getelementptr would be useful to allow >> >> SCEVExpander and other passes to convert code like this: >> >> %a = mul %x, 4 >> >> %b = add %y, %a >> >> %c = getelementptr [4 x i8]* @Object, 0, %b >> >> >> >> into this: >> >> %c = getelementptr [4 x i8]* @Object, %x, %y >> > > So a "defined-overflow" gep would act like wrapping integer arithmetic > in the width of the pointer? Then what exactly is the definition of > an "undefined-overflow" gep? Here's a first shot at a definition: > "Considering a GEP as a series of calculations, one for each index, if > the result that would be obtained by performing exact arithmetic > (treating the index as a signed integer) is outside the bounds of the > address range of the base pointer, the result is undefined."Yes, something like this. I had been thinking of defining gep overflow in terms of integer overflow, and then just saying that since LLVM IR doesn't usually know what the address is, the only way to be safe is to stay within the object, but your suggestion might be simpler. Also, for completeness, the conversion of indices to pointer-sized integers shouldn't change their value, the multiplication of the indices by array element sizes shouldn't overflow, and computing an address one-past-the-end is ok. Dan
On Jul 22, 2009, at 1:28 PM, Török Edwin wrote:> On 2009-07-22 21:30, Dan Gohman wrote: > >> Hello, >> >> >> >> I'm working on refining the definition of getelementptr (GEP) to >> >> clarify its semantics and to allow front-ends to provide additional >> >> information to optimization passes. >> >> >> >> To help support this, I'd like to propose the following rule: >> >> >> >> Any memory access must be done though a pointer value associated >> >> with with address range of the memory access, otherwise the behavior >> >> is undefined. >> >> >> > > If I compute an out-of-bounds GEPs and use it in ICMP is that > undefined > behaviour, or wrapping behaviour?This will be addressed when the wrapping option for GEP is available. A wrapping GEP will provide wrapping behavior, and a non-wrapping GEP will have an undefined result on overflow. So it's up to the front-end to decide which one it wants.> > Instcombine currently does this transform ((gep Ptr, OFFSET) cmp Ptr) > ---> (OFFSET cmp 0), which is perfectly > fine when GEP is assumed to have undefined behavior on overflow, but > is > wrong if GEP is allowed to overflow > with well defined behavior (it wraps). > > Also will can the behavior of GEP be changed depending on llvm-gcc's > -fno-strict-aliasing/-fwrapv/-fno-strict-pointer-overflow flags?Yes. To implement -fwrapv, the front-end can omit any of the no-overflow flags, and choose the wrapping form of GEP, as appropriate. I'm not familiar with -fno-strict-pointer-overflow. Do you mean -fno-strict-overflow? I guess for LLVM that would be equivalent to -fwrapv. -fno-strict-aliasing is not impacted.> > >> Front-ends that do crazy things to pointers may need to use >> >> ptrtoint+arithmetic+inttoptr instead of getelementptr. If the >> >> target-independent properties of getelementptr are needed, the >> >> "getelementptr null" trick may be useful. >> > > Will various optimizations make sure they don't introduce undefined > operations in programs with otherwise well defined semantics? > I think instcombine may turn them into GEPs, thus transforming a > program > with well defined semantics according to above rules into > undefined semantics. Of course if the optimizer can see that the > access > is always well defined it should do this transform.Yes. One of the goals of this effort is to legitimize some of what the optimizer is already doing, and another is to make some of the things it's doing dependent on explicit permission in the form of no-overflow flags. Dan
On 2009-07-22 21:30, Dan Gohman wrote:> Hello, > > I'm working on refining the definition of getelementptr (GEP) to > clarify its semantics and to allow front-ends to provide additional > information to optimization passes. > > To help support this, I'd like to propose the following rule: > > Any memory access must be done though a pointer value associated > with with address range of the memory access, otherwise the behavior > is undefined. > > "associated with" is defined as follows: > > - A pointer value formed from a getelementptr instruction is > associated with the addresses associated with the first operand of > the getelementptr. > - An addresses of a global variable is associated with the address > range of the variable's storage. > - The result value of an allocation instruction is associated with > the address range of the allocated storage. > - A null pointer is associated with no addresses. > - A pointer value formed by a ptrtoint is associated with all address > ranges of all pointer values that contribute (directly or > indirectly) to the computation of the pointer's value. > - An integer value other than zero may be associated with address > ranges allocated through mechanisms other than those provided by > LLVM; such ranges shall not overlap with any ranges of address > allocated by mechanisms provided by LLVM. >What happens when you allocate more room for a variable than its type says it needs, and then access the variable beyond the limit of what its type would allow (but is otherwise valid, because you did allocate enough bytes)? I assume that the intention is to treat these as well defined accesses (pointer is within address range), is that right? I'm thinking of flexible array members in structs, and things like: struct foo { ... char var[1]; }; struct foo *x = malloc(sizeof(*x) + len); x->var[len-1]; Best regards, --Edwin
On Jul 22, 2009, at 2:27 PM, Török Edwin wrote:> On 2009-07-22 21:30, Dan Gohman wrote: > >> Hello, >> >> >> >> I'm working on refining the definition of getelementptr (GEP) to >> >> clarify its semantics and to allow front-ends to provide additional >> >> information to optimization passes. >> >> >> >> To help support this, I'd like to propose the following rule: >> >> >> >> Any memory access must be done though a pointer value associated >> >> with with address range of the memory access, otherwise the behavior >> >> is undefined. >> >> >> >> "associated with" is defined as follows: >> >> >> >> - A pointer value formed from a getelementptr instruction is >> >> associated with the addresses associated with the first operand of >> >> the getelementptr. >> >> - An addresses of a global variable is associated with the address >> >> range of the variable's storage. >> >> - The result value of an allocation instruction is associated with >> >> the address range of the allocated storage. >> >> - A null pointer is associated with no addresses. >> >> - A pointer value formed by a ptrtoint is associated with all >> address >> >> ranges of all pointer values that contribute (directly or >> >> indirectly) to the computation of the pointer's value. >> >> - An integer value other than zero may be associated with address >> >> ranges allocated through mechanisms other than those provided by >> >> LLVM; such ranges shall not overlap with any ranges of address >> >> allocated by mechanisms provided by LLVM. >> >> >> > > > What happens when you allocate more room for a variable than its type > says it needs, > and then access the variable beyond the limit of what its type would > allow (but is otherwise valid, because you did allocate enough bytes)? > > I assume that the intention is to treat these as well defined accesses > (pointer is within address range), is that right? > > I'm thinking of flexible array members in structs, and things like: > struct foo > { > ... > char var[1]; > }; > > struct foo *x = malloc(sizeof(*x) + len); > x->var[len-1];Yep, this is fine. The types in a getelementptr are just used to guide offset computation; they don't say anything about how the underlying memory was allocated. Dan
Hi Dan, What you are proposing is a major change in the semantics of llvm. You are taking certain uses of an instruction that have well defined behaviour and undefining them. Have you made any estimate of how many peoples' code this may or may not break? I think this is a *very* bad idea. Let me make some more detailed comments: Dan Gohman wrote:> Hello, > > I'm working on refining the definition of getelementptr (GEP) to > clarify its semantics and to allow front-ends to provide additional > information to optimization passes. > > To help support this, I'd like to propose the following rule: > > Any memory access must be done though a pointer value associated > with with address range of the memory access, otherwise the behavior > is undefined. > > "associated with" is defined as follows: > > - A pointer value formed from a getelementptr instruction is > associated with the addresses associated with the first operand of > the getelementptr. > - An addresses of a global variable is associated with the address > range of the variable's storage. > - The result value of an allocation instruction is associated with > the address range of the allocated storage. > - A null pointer is associated with no addresses. > - A pointer value formed by a ptrtoint is associated with all address > ranges of all pointer values that contribute (directly or > indirectly) to the computation of the pointer's value. > - An integer value other than zero may be associated with address > ranges allocated through mechanisms other than those provided by > LLVM; such ranges shall not overlap with any ranges of address > allocated by mechanisms provided by LLVM.I notice no mention of bitcasts on pointers here. Intermediate representations are often full of weird-looking, but correct, pointer arithmetic.> > For example, in an instruction like this: > > %p = getelementptr [4 x i8]* @A, i32 0, i32 %huge > > if %huge is beyond the size of @A, %p could potentially point into > some object other than @A. This rule says that it's not valid to use > %p to access that other object. %p would only be usable for memory > accesses when it points within @A. > > C and C-like front-ends already obey this rule, since in C pointer > arithmetic results must remain within an allocated object (or one > past the end), which is more strict.Lots of C code passes pointers around which might point to the middle of an array, say for searching. That means that negative indices could still remain within an allocated object.> > Front-ends that do crazy things to pointers may need to use > ptrtoint+arithmetic+inttoptr instead of getelementptr. If the > target-independent properties of getelementptr are needed, the > "getelementptr null" trick may be useful.Who says pointer arithmetic is crazy? I create llvm code from an IR that has 2 types of pointers, heap-pointers and non-heap pointers, and is safe for GC, but prevents alias analysis. So, I don't use any alias analysis stuff when doing optimisation, no big deal. Suddenly, my correct and working code will become "undefined" :(> > With this rule, BasicAliasAnalysis and similar analyses that depend > on being able to track a pointer value up to its base value will be > able to safely climb through getelementptr definitions without > needing any further guarantees.So all this breakage is for a few optimisation passes, that I don't even use?> > That means that this rule will eliminate the most severe need for > having getelementptr overflow produce undefined results. This will > make it practical to have an undefined-on-overflow flag for > getelementptr that can be meaningfully set to either true or false. > > A non-overflowing option for getelementptr would be useful to allow > SCEVExpander and other passes to convert code like this: > %a = mul %x, 4 > %b = add %y, %a > %c = getelementptr [4 x i8]* @Object, 0, %b > > into this: > %c = getelementptr [4 x i8]* @Object, %x, %y > > which wouldn't otherwise be safe because (getelementptr @Object, %x) > by itself might overflow. (From a low-level perspective this isn't > much of an optimization, but from a high-level perspective it's > easier for non-SCEV-based passes to analyze.) > > Comments and suggestions are welcome, >Please don't do this! My suggestion is this: Add a "strict-GEP", which does what you suggest. This would allow front-ends to tell the back-end about what things cannot be aliased, and not cause any breakages for code that uses the "old" GEP. Cheers, Mark.
On Thu, Jul 23, 2009 at 1:59 AM, Mark Shannon<marks at dcs.gla.ac.uk> wrote:> What you are proposing is a major change in the semantics of llvm.The thing is, it isn't really a big change; it's essentially what we already implement.> I notice no mention of bitcasts on pointers here. > > Intermediate representations are often full of weird-looking, but > correct, pointer arithmetic.A bitcast of a pointer is still the same pointer for the purposes of this section.> Lots of C code passes pointers around which might point to the middle of > an array, say for searching. That means that negative indices could > still remain within an allocated object.Umm, right... GEP should be explicitly documented to take signed indices. Anyway, this isn't actually saying anything about the given example, because that's still the same object (the array).>> With this rule, BasicAliasAnalysis and similar analyses that depend >> on being able to track a pointer value up to its base value will be >> able to safely climb through getelementptr definitions without >> needing any further guarantees. > So all this breakage is for a few optimisation passes, that I don't even > use?If your code is such that BasicAA isn't correct, it's already well into undefined territory; you're basically redefining your own IR semantics.> Add a "strict-GEP", which does what you suggest. This would allow > front-ends to tell the back-end about what things cannot be aliased, > and not cause any breakages for code that uses the "old" GEP.This isn't actually proposing any immediate code changes except adding a new flag to GEP for strict overflow semantics. -Eli
On Jul 23, 2009, at 1:59 AM, Mark Shannon wrote:> Hi Dan, > > What you are proposing is a major change in the semantics of llvm. > > You are taking certain uses of an instruction that have well defined > behaviour and undefining them. > > Have you made any estimate of how many peoples' code this may or may > not > break? > > I think this is a *very* bad idea.Hi Mark, I estimate this will break very little. I apologize for being unclear; In practical terms, this proposal isn't a big change. It's a conceptual framework for describing assumptions that the optimizer is already making in many cases. It will help us resolve some cases where the optimizer's assumptions are contradictory. And, it sets the stage for a new flavor of getelementptr which will be more permissive than the current getelementptr.> > Let me make some more detailed comments: > > Dan Gohman wrote: >> Hello, >> >> I'm working on refining the definition of getelementptr (GEP) to >> clarify its semantics and to allow front-ends to provide additional >> information to optimization passes. >> >> To help support this, I'd like to propose the following rule: >> >> Any memory access must be done though a pointer value associated >> with with address range of the memory access, otherwise the behavior >> is undefined. >> >> "associated with" is defined as follows: >> >> - A pointer value formed from a getelementptr instruction is >> associated with the addresses associated with the first operand of >> the getelementptr. >> - An addresses of a global variable is associated with the address >> range of the variable's storage. >> - The result value of an allocation instruction is associated with >> the address range of the allocated storage. >> - A null pointer is associated with no addresses. >> - A pointer value formed by a ptrtoint is associated with all >> address >> ranges of all pointer values that contribute (directly or >> indirectly) to the computation of the pointer's value. >> - An integer value other than zero may be associated with address >> ranges allocated through mechanisms other than those provided by >> LLVM; such ranges shall not overlap with any ranges of address >> allocated by mechanisms provided by LLVM. > I notice no mention of bitcasts on pointers here.This was an oversight. Bitcasts are simple: - The result value of a bitcast is associated with all addresses associated with the operand of the bitcast.>> For example, in an instruction like this: >> >> %p = getelementptr [4 x i8]* @A, i32 0, i32 %huge >> >> if %huge is beyond the size of @A, %p could potentially point into >> some object other than @A. This rule says that it's not valid to use >> %p to access that other object. %p would only be usable for memory >> accesses when it points within @A. >> >> C and C-like front-ends already obey this rule, since in C pointer >> arithmetic results must remain within an allocated object (or one >> past the end), which is more strict. > Lots of C code passes pointers around which might point to the > middle of > an array, say for searching. That means that negative indices could > still remain within an allocated object.This proposal supports negative GEP indices. In fact, negative GEP indices are one of the corner cases that the optimizer today handles incorrectly, though only in obscure ways that usually don't break real code. This proposal will actually let LLVM support them in a more robust manner.> >> >> Front-ends that do crazy things to pointers may need to use >> ptrtoint+arithmetic+inttoptr instead of getelementptr. If the >> target-independent properties of getelementptr are needed, the >> "getelementptr null" trick may be useful. > > Who says pointer arithmetic is crazy? > I create llvm code from an IR that has 2 types of pointers, > heap-pointers and non-heap pointers, and is safe for GC, but prevents > alias analysis. > So, I don't use any alias analysis stuff when doing optimisation, no > big > deal. > Suddenly, my correct and working code will become "undefined" :(I don't see anything problematic in your description here. Alias analysis may not be especially profitable in these circumstances, but I wouldn't guess that it would be unsafe. Dan
On Thu, Jul 23, 2009 at 1:59 AM, Mark Shannon<marks at dcs.gla.ac.uk> wrote:> Hi Dan, > > What you are proposing is a major change in the semantics of llvm. > > You are taking certain uses of an instruction that have well defined > behaviour and undefining them.As far as I can tell, this only affects uses of GEP that were undefined under the "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." rule. (Removed by Dan in http://llvm.org/viewvc/llvm-project?view=rev&revision=76495) What are the cases that the new behavior makes undefined that the old behavior didn't? I think this is just a loosening of the rules.
On Jul 22, 2009, at 1:30 PM, Dan Gohman wrote:> Hello, > > I'm working on refining the definition of getelementptr (GEP) to > clarify its semantics and to allow front-ends to provide additional > information to optimization passes.It would be quite valuable to have cleaner semantics for GEPs, both for LLVM in general and for the memory safety work we have been doing in the SAFECode project. For example, Andrew's optimization to convert integer address arithmetic to equivalent GEPs was recently disabled because GEPs don't have well-defined overflow semantics but Andrew's optimization is very important for SAFECode. At the same time, I don't understand how you plan to handle a couple of cases (plus some comments):> > To help support this, I'd like to propose the following rule: > > Any memory access must be done though a pointer value associated > with with address range of the memory access, otherwise the behavior > is undefined. > > "associated with" is defined as follows: > > - A pointer value formed from a getelementptr instruction is > associated with the addresses associated with the first operand of > the getelementptr.[I think this correctly handles an illegal, though commonly used, special case: when a pointer walks off the end of an object but walks back before being dereferenced. This should work.]> - An addresses of a global variable is associated with the address > range of the variable's storage. > - The result value of an allocation instruction is associated with > the address range of the allocated storage. > - A null pointer is associated with no addresses.Null in C is always implemented as 0, and address 0 is a perfectly valid address in kernel code. What happens there?> - A pointer value formed by a ptrtoint is associated with all address > ranges of all pointer values that contribute (directly or > indirectly) to the computation of the pointer's value.This seems technically well defined (after rephrasing in terms of inttoptr, as you said), but can be very expensive for a pointer analysis to track. I'm not sure any of our current analyses actually track this in any sense, except DSA which only does this as an option that hasn't been used for a while and has likely bit-rotted. This means the "ptrtoint+arithmetic+inttoptr" case, though legal, should lead to very poor aliasing results. I guess you could argue that current LLVM passes don't do any better?> - An integer value other than zero may be associated with address > ranges allocated through mechanisms other than those provided by > LLVM; such ranges shall not overlap with any ranges of address > allocated by mechanisms provided by LLVM. > > For example, in an instruction like this: > > %p = getelementptr [4 x i8]* @A, i32 0, i32 %huge > > if %huge is beyond the size of @A, %p could potentially point into > some object other than @A. This rule says that it's not valid to use > %p to access that other object. %p would only be usable for memory > accesses when it points within @A. > > C and C-like front-ends already obey this rule, since in C pointer > arithmetic results must remain within an allocated object (or one > past the end), which is more strict. > > Front-ends that do crazy things to pointers may need to use > ptrtoint+arithmetic+inttoptr instead of getelementptr. If the > target-independent properties of getelementptr are needed, the > "getelementptr null" trick may be useful. > > With this rule, BasicAliasAnalysis and similar analyses that depend > on being able to track a pointer value up to its base value will be > able to safely climb through getelementptr definitions without > needing any further guarantees. > > That means that this rule will eliminate the most severe need for > having getelementptr overflow produce undefined results. This will > make it practical to have an undefined-on-overflow flag for > getelementptr that can be meaningfully set to either true or false. > > A non-overflowing option for getelementptr would be useful to allow > SCEVExpander and other passes to convert code like this: > %a = mul %x, 4 > %b = add %y, %a > %c = getelementptr [4 x i8]* @Object, 0, %b > > into this: > %c = getelementptr [4 x i8]* @Object, %x, %y > > which wouldn't otherwise be safe because (getelementptr @Object, %x) > by itself might overflow. (From a low-level perspective this isn't > much of an optimization, but from a high-level perspective it's > easier for non-SCEV-based passes to analyze.) > > Comments and suggestions are welcome, > > Dan > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev--Vikram Associate Professor, Computer Science University of Illinois at Urbana-Champaign http://llvm.org/~vadve
On Mon, Jul 27, 2009 at 9:21 PM, Vikram S. Adve<vadve at illinois.edu> wrote:>> - An addresses of a global variable is associated with the address >> range of the variable's storage. >> - The result value of an allocation instruction is associated with >> the address range of the allocated storage. >> - A null pointer is associated with no addresses. > > Null in C is always implemented as 0, and address 0 is a perfectly > valid address in kernel code. What happens there?It doesn't work; this documentation change is just clarifying that. There are various ugly ways to deal with this at the moment, like inline asm, but I'm not sure what the right thing to do here is...>> - A pointer value formed by a ptrtoint is associated with all address >> ranges of all pointer values that contribute (directly or >> indirectly) to the computation of the pointer's value. > > This seems technically well defined (after rephrasing in terms of > inttoptr, as you said), but can be very expensive for a pointer > analysis to track. I'm not sure any of our current analyses actually > track this in any sense, except DSA which only does this as an option > that hasn't been used for a while and has likely bit-rotted. This > means the "ptrtoint+arithmetic+inttoptr" case, though legal, should > lead to very poor aliasing results. I guess you could argue that > current LLVM passes don't do any better?On one end, this is only slightly more general than what BasicAA already assumes, which is roughly "if a pointer doesn't escape, it doesn't alias any other pointer." And on the other end, we don't want to break legal C code like http://llvm.org/bugs/show_bug.cgi?id=2831#c11 . I don't think there's really much choice involved in this definition. -Eli
On Jul 27, 2009, at 9:21 PM, Vikram S. Adve wrote:> On Jul 22, 2009, at 1:30 PM, Dan Gohman wrote: > > >> Hello, >> >> >> >> I'm working on refining the definition of getelementptr (GEP) to >> >> clarify its semantics and to allow front-ends to provide additional >> >> information to optimization passes. >> > > It would be quite valuable to have cleaner semantics for GEPs, both > for LLVM in general and for the memory safety work we have been doing > in the SAFECode project. For example, Andrew's optimization to > convert integer address arithmetic to equivalent GEPs was recently > disabled because GEPs don't have well-defined overflow semantics but > Andrew's optimization is very important for SAFECode.Ok. With this new rule, getelementptr semantics will hopefully be quite well specified. It won't be possible to translate arbitrary adds into getelementptrs, but you can do this kind of thing if you can prove that one operand of an add is an address and that the other is a well-behaved offset.> > At the same time, I don't understand how you plan to handle a couple > of cases (plus some comments): > > > >> >> >> To help support this, I'd like to propose the following rule: >> >> >> >> Any memory access must be done though a pointer value associated >> >> with with address range of the memory access, otherwise the behavior >> >> is undefined. >> >> >> >> "associated with" is defined as follows: >> >> >> >> - A pointer value formed from a getelementptr instruction is >> >> associated with the addresses associated with the first operand of >> >> the getelementptr. >> > > [I think this correctly handles an illegal, though commonly used, > special case: when a pointer walks off the end of an object but walks > back before being dereferenced. This should work.]Yes, while it's not permitted in C, it's useful in LLVM IR. This special case is specifically intended to be supported. Some LLVM optimizations rely on it.> > > >> - An addresses of a global variable is associated with the address >> >> range of the variable's storage. >> >> - The result value of an allocation instruction is associated with >> >> the address range of the allocated storage. >> >> - A null pointer is associated with no addresses. >> > > Null in C is always implemented as 0, and address 0 is a perfectly > valid address in kernel code. What happens there?Handling address 0 as a special case here is just documenting existing practice within LLVM. For example, instcombine followed by simplifycfg turns "store i32 0, i32* null" into "unreachable". I'm going to leave this rule in place for now to cover this, however there's certainly room for improvement in this area.> > > >> - A pointer value formed by a ptrtoint is associated with all address >> >> ranges of all pointer values that contribute (directly or >> >> indirectly) to the computation of the pointer's value. >> > > This seems technically well defined (after rephrasing in terms of > inttoptr, as you said), but can be very expensive for a pointer > analysis to track. I'm not sure any of our current analyses actually > track this in any sense, except DSA which only does this as an option > that hasn't been used for a while and has likely bit-rotted. This > means the "ptrtoint+arithmetic+inttoptr" case, though legal, should > lead to very poor aliasing results. I guess you could argue that > current LLVM passes don't do any better?Yes; this is existing practice in LLVM. inttoptr provides essential functionality, but optimizers don't attempt expensive heroics to understand what it's doing. I don't know how to constrain inttoptr in a way that would meaningfully aid pointer analysis without either making it over-complicated or breaking some extant idiom. I'm open to suggestions though. Dan