llvm dev - Jul 2009 - [LLVMdev] proposed new rule for getelementptr

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:32 PM, Dan Gohman wrote:
>>>
>>> - 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.
FWIW, this will be addressed when we finally get around to adding  
explicit support for trappability to load/store.

-Chris

On Jul 22, 2009, at 5:23 PM, Chris Lattner wrote:
>
> On Jul 22, 2009, at 1:32 PM, Dan Gohman wrote:
>
>>>>
>>>> - 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.
>
> FWIW, this will be addressed when we finally get around to adding
> explicit support for trappability to load/store.
This won't free the optimizer to treat null as an invalid pointer  
though.
Some LLVM hacker thought it would be a good idea to use address
spaces 256 and 257 on x86 in a way that can require dereferences
of address 0 to be valid.

Dan

On Wed, Jul 22, 2009 at 1:32 PM, Dan Gohman<gohman at apple.com>
wrote:
> 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.
Hmm, yeah, I was considering that too.  We quickly run into the issue
of "what sort of integer overflow", though.

-Eli