[LLVMdev] proposed new rule for getelementptr

[Dan Gohman]

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