[LLVMdev] proposed new rule for getelementptr

[Dan Gohman]

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