[LLVMdev] proposed new rule for getelementptr

[Dan Gohman]

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