loads from a null address and optimizations

Hi,

Currently, llvm treats the loads from a null address as unreachable code, i.e.:
load i32* null
is transformed by some optimization pass into
unreachable

This presents problems in JIT compilers like mono which implement null pointer checks by trapping SIGSEGV signals. It also
looks incorrect since it changes program behavior, which might be undefined in general, but it is quite well defined on unix.
Is there a way to prevent llvm from doing this besides marking all loads as volatile ?

thanks

Zoltan

Zoltan Varga wrote:

                Hi,

  Currently, llvm treats the loads from a null address as unreachable code, i.e.:
     load i32* null
is transformed by some optimization pass into
    unreachable

This presents problems in JIT compilers like mono which implement null pointer checks by trapping SIGSEGV signals. It also
looks incorrect since it changes program behavior, which might be undefined in general, but it is quite well defined on unix.
Is there a way to prevent llvm from doing this besides marking all loads as volatile ?

The other way is to use a custom (ie., non-zero) address space for your pointers. I'm not sure what the backend will do with these, but the optimizers know not to treat load/store from null as special in alternate address spaces. You may have to teach the backend to ignore your addrspace though.

Nick

Hi Zoltan,

We've come across this before where people meant to induce a trap by dereferencing a null. It doesn't work for LLVM (as you found out). Essentially, it's a valid transformation to turn this into unreachable. The better solution is to use something like __builtin_trap.

-bw

Hi,

I don’t intentionally want to induce a tramp, the load null is created by an llvm optimization
pass from code like:
v = null;

v.Call ();

Zoltan

Zoltan Varga wrote:

Hi,

  I don't intentionally want to induce a tramp, the load null is created by an llvm optimization
pass from code like:
   v = null;
   .....
   v.Call ();

This is more of a workaround than a solution, but have you tried emitting null as inttoptr(0) instead of a ConstantPointerNull? That should disable optimizations relying on C-like undefined behavior semantics, at least as long as there isn't some pass which recognizes that pattern and turns it back into null.

John.

It’s essentially the sane thing. :slight_smile: I don’t quite understand the code. Is ‘v’ ever assigned a value before ‘v.Call()’?

Two options remain, from what I can see. Either mark v as volatile, or compile without optimizations. The second is more drastic.

If you really want it to perform a call on null. Then you could place a function in another module that only returns null, then do the call:

// module A
typedef void (*func)();

func Foo() { return 0; }

// module B

Foo().Call();

And then make sure you don’t perform LTO.

-bw

How about this:

1. A custom pass run at the beginning that inserts a null check before
every load/store:

if ( ptr == null )
  trap;

Then if any pointers get optimized to null, the if condition becomes a
constant true,and the trap call should become unconditional.

2. A custom pass at the end that takes out every remaining null check
that your first pass inserted. It should first check whether the
condition is in fact a constant true (since that reduction might not
have been run after ptr became a constant null) and turn it into an
unconditional trap.

On second thought...

You'd like the program to behave correctly (whatever you mean by that)
whether any optimization passes are run or not. So have your
front-end emit the null-pointer checks with the explicit trap call,
and then you'll only need the pass at the end to take them out; but
leaving them in will still have your program behaving correctly,
although running a bit slower.

The problem he's facing here isn't necessarily one of correctness. He's dealing with undefined behavior (at least in C code). There are no guarantees that the compiler will retain a certain semantic interpretation of an undefined construct between different versions of the compiler, let alone different optimization levels.

From what I understand, he wants a particular behavior from the OS (a signal). The compiler shouldn't have to worry about OS semantics in the face of undefined language constructs. That being said, if he wants to implement a couple of passes to change his code, then sure. :slight_smile:

-bw

This is something that LLVM isn't currently good at, but that we're actively interested in improving. Here is some related stuff:
http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt

I don't know of anyone working on this, or planning to work on it in the short term though.

-Chris

The problem he's facing here isn't necessarily one of correctness.
He's dealing with undefined behavior (at least in C code). There are
no guarantees that the compiler will retain a certain semantic
interpretation of an undefined construct between different versions of
the compiler, let alone different optimization levels.
  
Should LLVM IR inherit all that is undefined behavior in C?
That makes it harder to support other languages, or new languages that
want different semantics
for things that the C standard defines as undefined.

BTW even for C gcc has -fno-delete-null-pointer-checks, and the Linux
kernel started using that recently
by default after all the exploits that mapped NULL to valid memory, and
took advantage of
gcc optimizing away the NULL checks.

The problem he's facing here isn't necessarily one of correctness.
He's dealing with undefined behavior (at least in C code). There are
no guarantees that the compiler will retain a certain semantic
interpretation of an undefined construct between different versions of
the compiler, let alone different optimization levels.

From what I understand, he wants a particular behavior from the OS (a
signal). The compiler shouldn't have to worry about OS semantics in
the face of undefined language constructs. That being said, if he
wants to implement a couple of passes to change his code, then
sure. :slight_smile:
    
This is something that LLVM isn't currently good at, but that we're
actively interested in improving. Here is some related stuff:
http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt
  
Looks interesting, but it also looks like a lot of work to implement.
Could instructions have a flag that says whether their semantics is
C-like (i.e. undefined behavior when you load from null etc.), or
something else? (throw exception, etc.).
Optimizations that assume the behavior is undefined should be updated to
check that flag, and perform the optimization only if the flag is set to
C-like.

What do you think?

I don't know of anyone working on this, or planning to work on it in
the short term though.
  
Although this is something I'd be interested in having, I lack the time
to implement it.

Best regards,
--Edwin

The problem he's facing here isn't necessarily one of correctness.
He's dealing with undefined behavior (at least in C code). There are
no guarantees that the compiler will retain a certain semantic
interpretation of an undefined construct between different versions of
the compiler, let alone different optimization levels.

Should LLVM IR inherit all that is undefined behavior in C?

For better or worse, it already inherits some of them. No, I don't think the idea is to make LLVM dependent on C's way of doing things. But one must assume some base-level of what to do with a particular construct.

Apparently, at this time at least, it's considered good to turn a dereference of null into unreachable. But like chris mentioned, it's something that we should improve.

That makes it harder to support other languages, or new languages that
want different semantics
for things that the C standard defines as undefined.

Yup.

BTW even for C gcc has -fno-delete-null-pointer-checks, and the Linux
kernel started using that recently
by default after all the exploits that mapped NULL to valid memory, and
took advantage of
gcc optimizing away the NULL checks.

What's the affect of this flag? I've never seen it before. :slight_smile: If we're doing something that violates the semantics of this flag, then it's something we need to fix, of course.

-bw

Interesting. What advantage do we get from the restriction that
terminators (including invokes) can only appear at the end of a basic
block? We'd lose that advantage, but in one sense that advantage is
already lost since loads, stores, calls, and whatnot *can* throw the
path of execution out of the middle of a basic block, we just have no
standard way to control or determine where it goes.

It would be unfortunate in a way if "this instruction can trap and go
there" is taken to mean "if this instruction has no effect other than
a possible trap, the instruction and the trapping behavior *must* be
preserved".

What exactly would the semantics be if the instruction *might* trap?
I somehow can't imagine it being useful.

-Eli

I'm not sure I understand the question. Instructions that are
guaranteed to trap can be optimized into unconditional traps. So
we're talking about instructions that *might* trap in any case.

I was saying that if the only possible effect of an instruction is a
trap, do we really want optimizers to preserve it in every case?

Right... the question is, is there any language that actually has such
semantics?

-Eli

Hi Eli,

What exactly would the semantics be if the instruction *might* trap?
I somehow can't imagine it being useful.

-Eli

I'm not sure I understand the question. Instructions that are
guaranteed to trap can be optimized into unconditional traps. So
we're talking about instructions that *might* trap in any case.

I was saying that if the only possible effect of an instruction is a
trap, do we really want optimizers to preserve it in every case?

Right... the question is, is there any language that actually has such
semantics?

before every operation, the Ada front-end generates code that checks
for out-of-bound array accesses, null pointer dereference, integer
overflow etc (whatever is appropriate for the operation) and throws
an exception if the error occurs. It would be nice if the compiler
could turn these explicit checks into more efficient implicit checks.
For example, on a platform on which load/store to a null pointer will
send a signal to the program, the explicit null checks could be
removed since the Ada runtime knows how to magically convert the signal
into an exception thrown at the right place. That said, the compiler
mustn't move around the load/store in a way that it wouldn't have done
if the explicit checks were present.

Ciao,

Duncan.

The problem he's facing here isn't necessarily one of correctness.
He's dealing with undefined behavior (at least in C code). There are
no guarantees that the compiler will retain a certain semantic
interpretation of an undefined construct between different versions of
the compiler, let alone different optimization levels.

Should LLVM IR inherit all that is undefined behavior in C?

For better or worse, it already inherits some of them. No, I don't
think the idea is to make LLVM dependent on C's way of doing things.
But one must assume some base-level of what to do with a particular
construct.

Apparently, at this time at least, it's considered good to turn a
dereference of null into unreachable. But like chris mentioned, it's
something that we should improve.

Ok.

That makes it harder to support other languages, or new languages that
want different semantics
for things that the C standard defines as undefined.

Yup.

BTW even for C gcc has -fno-delete-null-pointer-checks, and the Linux
kernel started using that recently
by default after all the exploits that mapped NULL to valid memory, and
took advantage of
gcc optimizing away the NULL checks.

What's the affect of this flag? I've never seen it before. :slight_smile: If
we're doing something that violates the semantics of this flag, then
it's something we need to fix, of course.

At -O2 and higher gcc deletes if (p == NULL) checks after p has been
dereferenced, assuming that a deref of null halts the program.
-fno-delete-null-pointer-checks disables that optimization.
I haven't seen LLVM do this optimization currently, but maybe I just
haven't seen it yet.

From the gcc manpage:

   `-fdelete-null-pointer-checks'
     Use global dataflow analysis to identify and eliminate useless
     checks for null pointers. The compiler assumes that dereferencing
     a null pointer would have halted the program. If a pointer is
     checked after it has already been dereferenced, it cannot be null.

     In some environments, this assumption is not true, and programs can
     safely dereference null pointers. Use
     `-fno-delete-null-pointer-checks' to disable this optimization for
     programs which depend on that behavior.

     Enabled at levels `-O2', `-O3', `-Os'.

Best regards,
--Edwin

Eli Friedman wrote:

Hi Andrew,

We faced this problem in gcc, and unfortunately Java and Ada have different
properties when it comes to trapping instructions: Java must throw a
NullPointerException at the appropriate place, but AIUI Ada may or may not.

in the case of Ada, throwing an exception at the appropriate place is
always fine. The language standard does allow the compiler to perform
some optimizations which may result in the exception being thrown
somewhere else, but of course the compiler isn't obliged to perform
these optimizations. In summary: it is always right to throw the
exception at the obvious place, but it is not necessarily wrong if it is
thrown somewhere else.

Ciao,

Duncan.