GEP with a null pointer base

This is the part that confuses me, why would such code be eliminated.
If it is illegal then this should be a compilation failure,
If it is legal then either you prefer to let it compile as is,
or you prefer to allow “undefined behavior optimization” to take effect,
In which case it is not the load instruction that should be deleted but
rather then entire block containing the load (under the assumption
that “undefined behavior” is unreachable) and InstCombine isn’t the
place to do that.

Confused,
Peter Lawrence.

This is illegal code, and if we only cared about the C spec, we could at least warn about it if not reject it outright.

That said, the purpose of clang is to build real code, and real code contains some amount of invalid constructs in important code bases. We care about building a pragmatic compiler that gets the job done, so we sometimes “make things work” even though we don’t have to. There are numerous patterns in old-style “offsetof” macros that do similar things. Instead of fighting to make all the world’s code be theoretically ideal, it is better to just eat it and “do what they meant”.

-Chris

So far, so good. The problem is that while LLVM seems to consider
the above IR to be valid, we officially do not allow dereferencing
a pointer constructed in this way (if I’m reading the rules
correctly). Consequently, if this GEP ever gets close enough to a
load using the pointer, InstCombine will eliminate the GEP and the
load.

This is the part that confuses me, why would such code be eliminated.
If it is illegal then this should be a compilation failure,

This is illegal code, and if we only cared about the C spec, we could at least warn about it if not reject it outright.

That said, the purpose of clang is to build real code, and real code contains some amount of invalid constructs in important code bases. We care about building a pragmatic compiler that gets the job done, so we sometimes “make things work” even though we don’t have to. There are numerous patterns in old-style “offsetof” macros that do similar things. Instead of fighting to make all the world’s code be theoretically ideal, it is better to just eat it and “do what they meant”.

Chris,
The issue the original poster brought up is that instead of a compiler
that as you say “makes things work” and “gets the job done” we have a compiler
that intentionally deletes “undefined behavior”, on the assumption that since it
is the users responsibility to avoid UB this code must be unreachable and
is therefore safe to delete.

It seems like there are three things the compiler could do with undefined behavior

  1. let the code go through (perhaps with a warning)
  2. replace the code with a trap
  3. optimize the code as unreachable (no warning because we’re assuming this is the users intention)

It looks like 3 is the llvm default, but IMHO is the least desirable choice,
real world examples showing the benefit are practically non-existent,
and it can mask a real source code bug.

In spite of option 3 being (IMHO) the least desirable choice, considerable
resources are being devoted to implementing it, and it does not seem
to be being done according to good software engineering practice.

This optimization seems to fit the “compiler design pattern” of a separate
analysis and transform pass where “poison” is an attribute that gets forward
propagated through expressions and assignments until it reaches some
instruction that turns “poison” into “undefined behavior”, after which the
block containing the UB can be deleted.

Putting this analysis and transform into a separate pass means that the
LangRef and IR can be cleaned up, there is no reason to have “poison”
and “freeze” in the IR, nor have any other passes have to deal with them.

Some folks are saying damn the torpedoes full speed ahead on option 3
in its least software-engineering-friendly form, others are saying wait-a-minute
lets slow down take a deep breath and consider the big picture first.

Thoughts ?
Comments ?
Questions ?

Peter Lawrence.

Hi Peter,

I think you have a somewhat fundamental misunderstanding of how UB works (or rather, why it is so crappy and doesn’t really work :-). The compiler can and does do all three of those, and it doesn’t have to have consistent algorithms for how it picks. I highly recommend you read some blog posts I wrote about it years ago, starting with:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

John Regehr also has written a lot on the topic, including the recent post:
https://blog.regehr.org/archives/1520

What you should take from this is that while UB is an inseperable part of C programming, that this is a depressing and faintly terrifying thing. The tooling built around the C family of languages helps make the situation “less bad”, but it is still pretty bad. The only solution is to move to new programming languages that don’t inherit the problem of C. I’m a fan of Swift, but there are others.

In the case of this particular thread, we aren’t trying to fix UB, we’re trying to switch one very specific syntactic idiom from UB to defined.

-Chris

In this particular case, I believe llvm is really emitting a store of undef to a nullptr. I think this later gets turned into a trap. Here’s the relevant code from instcombine.

// load(gep null, …) → unreachable
// load null/undef → unreachable
// TODO: Consider a target hook for valid address spaces for this xforms.
if (canSimplifyNullLoadOrGEP(LI, Op)) {
// Insert a new store to null instruction before the load to indicate
// that this code is not reachable. We do this instead of inserting
// an unreachable instruction directly because we cannot modify the
// CFG.
new StoreInst(UndefValue::get(LI.getType()),
Constant::getNullValue(Op->getType()), &LI);
return replaceInstUsesWith(LI, UndefValue::get(LI.getType()));
}

Right. It is turning undefined behavior (load of null) into the canonical pattern that SimplifyCFG picks up. This is because InstCombine can’t change the CFG.

-Chris

Chris,
          nice segue to Swift ! :-), but...

The question is what should LLVM do with UB in general, saying that
we are going to change one specific idiom from undefined to defined glosses
over the real question: why should we ever optimize / delete any UB at all ?

This “depressing and faintly terrifying thing” as you call it, should be viewed not as
an opportunity for optimization, but rather as the source of bugs that need to be
warned about at the very least.

The current action is to delete UB (without warning), is that really right ?
Who can possibly benefit from this optimization ?
And how can that ever outweigh the harm in not reporting an error ?
Why are we expending any effort at all to optimize something that just
about everyone agrees should always be avoided ?

These last questions are all rhetorical so no need to answer them, the problem
as I see it now is that everyone CC'ed on this email probably by now would agree
privately that optimizing away undefined behavior is wrong, but no one wants
to be the first to say so publicly. We’re stuck in a log-jam. We need someone like
you to take that first step so the rest can go along.

Please help in un-jamming the current log-jam.

Peter Lawrence.

Chris,
           nice segue to Swift ! :-), but...

The question is what should LLVM do with UB in general, saying that
we are going to change one specific idiom from undefined to defined glosses
over the real question: why should we ever optimize / delete any UB at all ?

This “depressing and faintly terrifying thing” as you call it, should be viewed not as
an opportunity for optimization, but rather as the source of bugs that need to be
warned about at the very least.

The current action is to delete UB (without warning), is that really right ?
Who can possibly benefit from this optimization ?
And how can that ever outweigh the harm in not reporting an error ?
Why are we expending any effort at all to optimize something that just
about everyone agrees should always be avoided ?

These last questions are all rhetorical so no need to answer them, the problem
as I see it now is that everyone CC'ed on this email probably by now would agree
privately that optimizing away undefined behavior is wrong, but no one wants
to be the first to say so publicly.

I'm certain this hypothesis is false.

  -Hal

It's definitely false.
I think it's quite right to optimize way undefined behavior.

I'm in the camp of "if you want better programming languages, take full
advantage of what you can in the current ones, and if people don't like it,
awesome, let them use a language that has more guarantees".

(Though i'm usually in the camp of using flags and defaults to achieve
this, since i'm somewhat pragmatic)

If you don't take advantage at all, or only of some things, in the name of
pragmatics, now every compiler does something different, and users can't
even know what to expect.

In practice, taking advantage is also the only way this stuff gets fixed.
It becomes enough of a pain that either later revisions of the same
programming language, or a new programming language, fix it.

I'm emphatically not a fan of "well, the language designers suck at giving
users what they want and need, so we should fix it for them in the
compiler". Down this path, madness lies.

Instead, i'd rather make these folks do their job :wink:

As several others have pointed out, we are not in a log-jam and your hypothesis about how people feel is false.

However, I also want to point out that using rhetorical questions (or more broadly, rhetorical devices and techniques) is probably not the best approach for any of these discussions. And down this path comes a form of dialog that has been a problem in prior discussions, so I strongly urge you to phrase your emails differently.

If you want to persuade people on this list about how LLVM should work, I would suggest that you to avoid rhetoric and instead focus on actually making changes to LLVM (it is open source) and showing the empirical results of the experiment.

No one has addressed this yet, which may be why you are still under the impression that it’s under discussion. You seem to have some misconceptions about UB. There are two major reasons for UB in a language such as C:

1. The safe version may be prohibitively expensive on some architectures. For example, division by zero will give a trap on some architectures or an unspecified value on others. If the C specification stated that it gave an unspecified value, then on architectures that trap every division would have to be wrapped in a branch that tested if the divisor was zero and branched over the divide instruction if so. This would lead to very inefficient code on these architectures, so the C standard says that anything is allowed to happen.

2. Some properties are effectively impossible to verify statically[1]. For example, it is undefined behaviour in C to use a pointer to a deallocated object[2]. If C required well-defined behaviour here then it would effectively be mandating some form of garbage collector: you’d need to either find all pointers to an object and null them on free, or you’d need to mark the object, check the mark on every load, and not reuse the memory until later. This would be unacceptable overhead for a C implementation. A lot of other things are in this category.

Many things are a mixture of these. Most optimisations that rely on undefined behaviour are not saying ‘aha, we’ve spotted that the program invokes undefined behaviour, we can replace the whole thing with a trap instruction!’, they’re saying ‘this program does either X or Y, X would be undefined behaviour and so we can assume that it does Y’. Not being able to do the latter would mean that they’d need to insert run-time checks each time, which would negate the optimisation and *in well-written code would never be hit*.

The cases where the compiler can statically prove that undefined behaviour is present are comparatively rare.

David

[1] Note: Some of these are possible with whole-program analysis, so if you’re happy without shared libraries and with week-long compile times then it’s possible.

[2] The wording of this actually means that it’s impossible to implement malloc() in ISO C, because as soon as the pointer has been passed to free then it becomes invalid and using it to put the object on a free list invokes undefined behaviour.

David,
          Here is the definition accepted by Hal of what we’re doing

1. Sometimes there are abstraction penalties in C++ code
2. That can be optimized away after template instantiation, function inlining, etc
3. When they for example exhibit this pattern
  if (A) {
    stuff;
  } else {
    other stuff including “undefined behavior”;
  }
4. Where the compiler assumes “undefined behavior” doesn’t actually happen because
   In the C language standard it is the users responsibility to avoid it
5. Therefore in this example the compiler can a) delete the else-clause
    b) delete the if-cond, c) assume A is true and propagate that information

We are actively deleting undefined behavior, and the question is why
given that doing so potentially masks a real source code bug.
At the very least deleting undefined behavior should not be the default.

Peter Lawrence.

You are asserting this (again), but others have clearly stated that they disagree. David gave detailed and clear reasons why. Continuing to re-state positions is not productive.

-Chandler

I don't believe it is the default today: optimizations aren't turned on
unless you opt-in.

Chandler,
The only thing David made clear that wasn’t already clear
is that he believes UB to be “comparatively rare”, which is in agreement
with what Hal already said which is that he does not expect deleting
UB will be of benefit to for example SPEC benchmarks.

Given that it is “comparatively rare”, why all the effort to delete it ?
And why make deleting it the default rather than warning about it ?

Peter

Chandler,
The only thing David made clear that wasn’t already clear
is that he believes UB to be “comparatively rare”, which is in agreement
with what Hal already said which is that he does not expect deleting
UB will be of benefit to for example SPEC benchmarks.

Given that it is “comparatively rare”, why all the effort to delete it ?

And why make deleting it the default rather than warning about it ?

There seems to be some confusion/misunderstanding here. My best understanding is that when David said this:

“The cases where the compiler can statically prove that undefined behaviour is present are comparatively rare.”

What he was referring to/describing was a contrast with the optimizations described prior to that.

It’s something like this:

UB-based optimizations don’t prove UB is present - they optimize on the assumption that it is not present due to some unproven (by the compiler, but assumed to be known by the developer) invariants in the program.

Think about a simple case like array bounds - the compiler emits an unconditional load to the memory because it assumes the developer correctly validated the bounds or otherwise constructed so that out of bounds indexes never reach that piece of code. This is quite common - that UB is assumed to not happen, and the compiler optimizes on this fact.

What is less common, is for the compiler to be able to (in reasonable time) prove that UB /does/ happen (in many cases this would require complex interprocedural analysis - the array is defined in one function, maybe with a complex dynamic bound, then passed to another function and indexed using a non-trivial dynamic expression… statically proving that to be true or false is complex/expensive and so basically not done by any compiler - so any cases that are caught by the compiler are relatively trivial (“oh, you declared a const null pointer value, then dereferenced it within the same function”, etc) & so don’t happen very often (because they’re also fairly obvious to developers too))

Does that help explain the difference/distinction being drawn here?

  • Dave

Chandler,
The only thing David made clear that wasn’t already clear
is that he believes UB to be “comparatively rare”, which is in agreement
with what Hal already said which is that he does not expect deleting
UB will be of benefit to for example SPEC benchmarks.

Given that it is “comparatively rare”, why all the effort to delete it ?

And why make deleting it the default rather than warning about it ?

There seems to be some confusion/misunderstanding here. My best understanding is that when David said this:

“The cases where the compiler can statically prove that undefined behaviour is present are comparatively rare.”

What he was referring to/describing was a contrast with the optimizations described prior to that.

It’s something like this:

UB-based optimizations don’t prove UB is present - they optimize on the assumption that it is not present due to some unproven (by the compiler, but assumed to be known by the developer) invariants in the program.

Think about a simple case like array bounds - the compiler emits an unconditional load to the memory because it assumes the developer correctly validated the bounds or otherwise constructed so that out of bounds indexes never reach that piece of code. This is quite common - that UB is assumed to not happen, and the compiler optimizes on this fact.

What is less common, is for the compiler to be able to (in reasonable time) prove that UB /does/ happen (in many cases this would require complex interprocedural analysis - the array is defined in one function, maybe with a complex dynamic bound, then passed to another function and indexed using a non-trivial dynamic expression… statically proving that to be true or false is complex/expensive and so basically not done by any compiler - so any cases that are caught by the compiler are relatively trivial (“oh, you declared a const null pointer value, then dereferenced it within the same function”, etc) & so don’t happen very often (because they’re also fairly obvious to developers too))

Does that help explain the difference/distinction being drawn here?

Dave,
perhaps you missed these parts of the discussion

Here is the definition, acknowledged by Hal, of what we’re doing

  1. Sometimes there are abstraction penalties in C++ code
  2. That can be optimized away after template instantiation, function inlining, etc
  3. When they for example exhibit this pattern
    if (A) {
    stuff;
    } else {
    other stuff including “undefined behavior”;
    }
  4. Where the compiler assumes “undefined behavior” doesn’t actually happen because
    In the C language standard it is the users responsibility to avoid it
  5. Therefore in this example the compiler can a) delete the else-clause
    b) delete the if-cond, c) assume A is true and propagate that information

And, here’s the optimization that according to Sean we’re using to delete UB

[ … ]

In other words, if we can prove “when program statement A executes then
program statement B is guaranteed to execute and have undefined behavior”
then we can assume that program statement A is never executed.

In particular, deleting program statement A is a correct transformation.
Deleting program statement B itself is a special case of this (when A = B).

And yes, this does include everything up to and including main,
intraprocedurally and interprocedurally.

[ … ]

– Sean Silva

This is entirely a separate issue from what Dan Gohman did to optimize sign extension
of i32 induction variables out of loops for LP64 target machines, where the optimization
is justified based on “the assumption that UB does not happen”, and no actual UB
exists either statically or dynamically.

But when it comes to actual provable UB the plan is to delete it.
On that there is no confusion, and there is no mis-understanding.

Peter Lawrence.

Sorry, the way I phrased this in terms of program statements may have made this unclear, but this is precisely the particular case A=B that I mentioned. In this case, A=B=“the induction variable increment” and we use that to deduce that the statement will not execute and overflow, which is what justifies the widening.

Notice that I mentioned that deleting code is only a particular case. In the general case we deduce that dynamically something simply does not happen, which is what we do in order to prove that induction variable widening is safe (overflow cannot happen).

There is nothing special about induction variable widening with respect to UB. It is justified by applying the same principles as all other UB-related transformations.

Briefly, there is only one axiom in the compiler writer’s toolbox w.r.t. UB and that is “the input program does not execute UB”. Everything else is derived from that by pure logical reasoning. Does that make sense? Can you see how all the descriptions I gave above are derivable from that axiom?

The common application of this is that we can assume any program property P whatsoever (not just liveness, but variable ranges, etc.) if we can prove that the program would execute UB should that property P fail to hold.

– Sean Silva

Chandler,
               The only thing David made clear that wasn’t already clear
is that he believes UB to be “comparatively rare”, which is in agreement
with what Hal already said which is that he does not expect deleting
UB will be of benefit to for example SPEC benchmarks.

Given that it is “comparatively rare”, why all the effort to delete it ?

And why make deleting it the default rather than warning about it ?

There seems to be some confusion/misunderstanding here. My best
understanding is that when David said this:

"The cases where the compiler can statically prove that undefined
behaviour is present are comparatively rare."

What he was referring to/describing was a contrast with the optimizations
described prior to that.

It's something like this:

UB-based optimizations don't prove UB is present - they optimize on the
assumption that it is not present due to some unproven (by the compiler,
but assumed to be known by the developer) invariants in the program.

Think about a simple case like array bounds - the compiler emits an
unconditional load to the memory because it assumes the developer correctly
validated the bounds or otherwise constructed so that out of bounds indexes
never reach that piece of code. This is quite common - that UB is assumed
to not happen, and the compiler optimizes on this fact.

What is less common, is for the compiler to be able to (in reasonable
time) prove that UB /does/ happen (in many cases this would require complex
interprocedural analysis - the array is defined in one function, maybe with
a complex dynamic bound, then passed to another function and indexed using
a non-trivial dynamic expression... statically proving that to be true or
false is complex/expensive and so basically not done by any compiler - so
any cases that are caught by the compiler are relatively trivial ("oh, you
declared a const null pointer value, then dereferenced it within the same
function", etc) & so don't happen very often (because they're also fairly
obvious to developers too))

Does that help explain the difference/distinction being drawn here?

Dave,
          perhaps you missed these parts of the discussion

Here is the definition, acknowledged by Hal, of what we’re doing

1. Sometimes there are abstraction penalties in C++ code
2. That can be optimized away after template instantiation, function
inlining, etc
3. When they for example exhibit this pattern
if (A) {
stuff;
} else {
other stuff including “undefined behavior”;
}
4. Where the compiler assumes “undefined behavior” doesn’t actually happen
because
  In the C language standard it is the users responsibility to avoid it
5. Therefore in this example the compiler can a) delete the else-clause
   b) delete the if-cond, c) assume A is true and propagate that
information

And, here’s the optimization that according to Sean we’re using to delete
UB

[ … ]

In other words, if we can prove "when program statement A executes then
program statement B is guaranteed to execute and have undefined behavior"
then we can assume that program statement A is never executed.

In particular, deleting program statement A is a correct transformation.
Deleting program statement B itself is a special case of this (when A = B).

And yes, this does include everything up to and including `main`,
intraprocedurally and interprocedurally.

[ … ]

-- Sean Silva

This is entirely a separate issue from what Dan Gohman did to optimize
sign extension
of i32 induction variables out of loops for LP64 target machines, where
the optimization
is justified based on “the assumption that UB does not happen”, and no
actual UB
exists either statically or dynamically.

Sorry, the way I phrased this in terms of program statements may have made
this unclear, but this is precisely the particular case A=B that I
mentioned. In this case, A=B="the induction variable increment"

This should have said A=B="the induction variable increments and
overflows". Describing it in terms of general program properties instead of
"program statements" is more mathematically precise in this case (talking
about coarse-granularity things like statements is restrictive for the
induction variable widening case where you want to talk about a statement
and something dynamically happening in that statement rather than just its
liveness).

-- Sean Silva

Sean,

Dan Gohman’s “transform” changes a loop induction variable, but does not change the CFG,

Hal’s “transform” deletes blocks out of the CFG, fundamentally altering it.

These are two totally different transforms.

And even the analysis is different,

The first is based on an assumption of non-UB (actually there is no analysis to perform)

the second Is based on a proof of existence of UB (here typically some non-trivial analysis is required)

These have, practically speaking, nothing in common.

Peter Lawrence.