[LLVMdev] proposed new rule for getelementptr

[Mark Shannon]

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.

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.

Intermediate representations are often full of weird-looking, but 
correct, pointer arithmetic.

> 
> 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.

> 
> 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" :(

> 
> 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.
So all this breakage is for a few optimisation passes, that I don't even 
use?
> 
> 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,
> 
Please don't do this!

My suggestion is this:

Add a "strict-GEP", which does what you suggest. This would allow 
front-ends to tell the back-end about what things cannot be aliased,
and not cause any breakages for code that uses the "old" GEP.

Cheers,
Mark.