proposed new rule for getelementptr

What you are proposing is a major change in the semantics of llvm.

The thing is, it isn't really a big change; it's essentially what we
already implement.

I notice no mention of bitcasts on pointers here.

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

A bitcast of a pointer is still the same pointer for the purposes of
this section.

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.

Umm, right... GEP should be explicitly documented to take signed
indices. Anyway, this isn't actually saying anything about the given
example, because that's still the same object (the array).

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?

If your code is such that BasicAA isn't correct, it's already well
into undefined territory; you're basically redefining your own IR
semantics.

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.

This isn't actually proposing any immediate code changes except adding
a new flag to GEP for strict overflow semantics.

-Eli

Hmm, yeah, I was considering that too. We quickly run into the issue
of "what sort of integer overflow", though.

-Eli

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

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

As far as I can tell, this only affects uses of GEP that were
undefined under the "Note that it is undefined to access an array out
of bounds: array and pointer indexes must always be within the defined
bounds of the array type." rule. (Removed by Dan in
http://llvm.org/viewvc/llvm-project?view=rev&revision=76495) What are
the cases that the new behavior makes undefined that the old behavior
didn't? I think this is just a loosening of the rules.

Hi Dan,
Thanks for reply, it seems that

Dan Gohman 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;

No apology needed

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

I'm curious what these assumptions are, but its not important.

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.

This makes a big difference :slight_smile:

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.

It doesn't appear to have broken mine. My compiler could potentially use negative indices in GEPs.

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

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.

Any tests I can do to find out if its safe?

One last question.
If I were to turn off all optimisations, would that ensure that the final machine code semantics with the new GEP would be unchanged from the present GEP?
In other words, will any of this affect to the code-generator?

Cheers,
Mark.

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

I'm curious what these assumptions are, but its not important.

My first email aimed to make them explicit. Here's another example:

    @g = global i32

    %a = alloca i32
    %b = malloc i32
    %c = inttoptr 777770 to i32*

    %aa = getelementptr i32* %a, i64 %i
    %bb = getelementptr i32* %b, i64 %j
    %cc = getelementptr i32* %c, i64 %k
    %gg = getelementptr i32* @g, i64 %l

    store i32 0, i32* %aa
    store i32 1, i32* %bb
    store i32 2, i32* %cc
    store i32 3, i32* %gg

Here, %i, %j, %k, and %l are totally arbitrary values that the optimizer
knows nothing about. The optimizer will assume that all four stores are
to different memory locations. In theory, some truly crazy code could
figure out what values to use for %i, %j, %k, and/or %l to cause the
getelementptrs to overindex recklessly through the address space and
break this assumption. This the kind of thing that the optimizer
assumes doesn't happen.

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.

Any tests I can do to find out if its safe?

I don't know of any. You can run GVN and LICM and so on to see if
they break anything, but of course that wouldn't prove that there
aren't any problems.

One last question.
If I were to turn off all optimisations, would that ensure that the
final machine code semantics with the new GEP would be unchanged from
the present GEP?
In other words, will any of this affect to the code-generator?

It probably will at some point, to use alias-analysis info for
scheduling and other things. After all, CodeGen is just a highly
specialized optimizer ;-).

Dan

Hi Daniel,

In my case ExecutionEngine::create() loads 40 modules, then each time I try to resolve a symbol that I know is in a DLL that I supply, it looks through all 40 modules first. This is on Windows, so I get the following modules loaded:

ntdll.dll, kernel32.dll, USER32.dll, GDI32.dll, SHELL32.dll, ADVAPI32.dll, RPCRT4.dll,
Secur32.dll, msvcrt.dll, SHLWAPI.dll, ole32.dll, OLEAUT32.dll, WS2_32.dll, WS2HELP.dll,
PSAPI.DLL, VERSION.dll, MSACM32.dll, WINMM.dll, WININET.dll, Normaliz.dll, urlmon.dll,
iertutil.dll, IPHLPAPI.DLL, IMM32.dll, HID.DLL, SETUPAPI.dll, OPENGL32.dll, GLU32.dll,
DDRAW.dll, DCIMAN32.dll, dbghelp.dll, LPK.DLL, USP10.dll, comctl32.dll, comctl32.dll,
rsaenh.dll, uxtheme.dll, MSCTF.dll, USERENV.dll, as well as the exe.

It wouldn't be so bad if it looked through the modules in reverse order, so mine were searched
first.

So, as an alternative can the order be changed, or, can it be set up so that the user must explicitly enumerate and add modules.

Rob.

I probably shouldn't have weighed in on this thread, since I have
limited knowledge on the JIT.

If the current behavior is to enumerate all those modules, however,
adding a flag to the constructor doesn't seem so bad -- especially now
that we have the builder. I'll defer to Evan though.

- Daniel

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

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

It doesn't work; this documentation change is just clarifying that.
There are various ugly ways to deal with this at the moment, like
inline asm, but I'm not sure what the right thing to do here is...

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

On one end, this is only slightly more general than what BasicAA
already assumes, which is roughly "if a pointer doesn't escape, it
doesn't alias any other pointer." And on the other end, we don't want
to break legal C code like
http://llvm.org/bugs/show_bug.cgi?id=2831#c11 . I don't think there's
really much choice involved in this definition.

-Eli

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