[LLVMdev] proposed new rule for getelementptr

[Vikram S. Adve]

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