The semantics of nonnull attribute

Project Infrastructure LLVM Dev List Archives
1

Hello all,

LangRef says it is undefined behavior to pass null to a nonnull argument (call f(nonnull null);), but the semantics is too strong for a few existing optimizations.
To support these, we can relax the semantics so f(nonnull null) is equivalent to f(poison), but (A) it again blocks another set of optimizations, and (B) this makes the semantics of nonnull deviate from other attributes like dereferenceable.
I found that there was a similar discussion about this issue in the past as well, but seems it is not settled yet.
What should the semantics of nonnull be?
I listed a few optimizations that are relevant with this issue.

  1. Propagating nonnull attribute to callee’s arg (https://godbolt.org/z/-cVsVP )

g(i8* ptr) {
f(nonnull ptr);
}

=>
g(i8* nonnull ptr) {
f(nonnull ptr);
}

This is correct if f(nonnull null) is UB. If ptr == null, f(nonnull null) should have raised UB, so ptr shouldn’t be null.

However, this transformation is incorrect if f(nonnull null) is equivalent to f(poison).
If f was an empty function, f(nonnull null) never raises UB regardless of ptr. So we can’t guarantee ptr != null at other uses of ptr.

  1. InstCombine (https://godbolt.org/z/HDQ7rD ):

%ptr_inb = gep inbounds %any_ptr, 1
f(%ptr_inb)
=>
%ptr_inb = … (identical)
f(nonnull %ptr_inb)

This optimization is incorrect if f(nonnull null) is UB. The reason is as follows.
If gep inbounds %any_ptr, 1 yields poison, the source is f(poison) whereas the optimized one is f(nonnull poison).
f(nonnull poison) should be UB because f(nonnull null) is UB. So, the transformation introduced UB.
This optimization is correct if both f(nonnull null) and f(nonnull poison) are equivalent to f(poison).

  1. https://reviews.llvm.org/D69477

f(nonnull ptr);
use(ptr);
=>
llvm.assume(ptr != null);
use(ptr);
f(nonnull ptr);

If f(nonnull null) is f(poison), this is incorrect. If ptr was null, the added llvm.assume(ptr != null) raises UB whereas the source may not raise UB at all. (e.g. assume that f() was an empty function)
If f(nonnull null) is UB, this is correct.

  1. Dead argument elimination (from https://reviews.llvm.org/D70749 )

f(nonnull ptr); // f’s argument is dead
=>
f(nonnull undef);

This is incorrect if f(nonnull null) is UB. To make this correct, nonnull should be dropped. This becomes harder to fix if nonnull was attached at the signature of a function (not at the callee site).
It is correct if f(nonnull null) is f(poison).

Actually the D70749’s thread had an end-to-end miscompilation example due to the interaction between this DAE and the optimization 3 (insertion of llvm.assume).

Thanks,
Juneyoung Lee

2

Hi Juneyoung,

thank you for starting this discussion again, the last one [0] did not
really end in a solution but the issue remains and will only become
worse, e.g., enable the Attributor and you might see all of the problems
below exposed in a single pass [1-4].

As I argued in [0], UB is problematic and I am strongly in favor of
poison. In some sense I see UB as a very "strong" guarantee and poison
as a fairly "week" one. We will have a hard time deriving the strong one
and it might cause us to break things along the way, I mean your
examples show that we already miscompile codes.

I agree that poison is on its own not "strong enough" for certain
optimization, as you pointed out below, but we could reasonably augment
it with another attribute, let's call it `used`, that basically bridges
the gap:

  void @foo(nonnull);
  void @bar(nonnull used);

  foo(NULL) // <- argument is poison inside of @foo
  bar(NULL) // <- UB at the call site of @bar

A value is `used` if it would inevitably cause UB if it was poison at
this program point. I hope this makes some sense if not I can explain in
more detail.

Btw. I think this also integrates well with other attribute problems we
had in the past, e.g., memcpy(NULL, NULL, 0), since the pointers in this
example were "not used" (in some naive implementation of memcpy at
least).

Maybe I have overlooked a problem with this solution so let me know what
you think.

Cheers,
  Johannes

[0] ⚙ D70749 [InstCombine] do not insert nonnull assumption for undef
[1] 1. below: Compiler Explorer
[2] 2. below: Compiler Explorer
[3] 3. below: Compiler Explorer (doesn't work yet, will though)
[4] 4. below: Compiler Explorer
              Compiler Explorer
              ...

Hello all,

LangRef says it is undefined behavior to pass null to a nonnull argument
(`call f(nonnull null);`), but the semantics is too strong for a few
existing optimizations.
To support these, we can relax the semantics so `f(nonnull null)` is
equivalent to `f(poison)`, but (A) it again blocks another set of
optimizations, and (B) this makes the semantics of nonnull deviate from
other attributes like dereferenceable.
I found that there was a similar discussion about this issue in the past as
well, but seems it is not settled yet.
What should the semantics of nonnull be?
I listed a few optimizations that are relevant with this issue.

1. Propagating nonnull attribute to callee's arg (
Compiler Explorer )

g(i8* ptr) {
f(nonnull ptr);
}
=>
g(i8* nonnull ptr) {
f(nonnull ptr);
}

This is correct if f(nonnull null) is UB. If ptr == null, f(nonnull null)
should have raised UB, so ptr shouldn't be null.
However, this transformation is incorrect if f(nonnull null) is equivalent
to f(poison).
If f was an empty function, f(nonnull null) never raises UB regardless of
ptr. So we can't guarantee ptr != null at other uses of ptr.

For the given code snipped it is not even invalid to propagate nonnull
in the poison case but your point is not wrong, if we have f(poison) we
cannot derive anything from it if the argument might be unused.

3

Hello all,

LangRef says it is undefined behavior to pass null to a nonnull argument (`call f(nonnull null);`), but the semantics is too strong for a few existing optimizations.
To support these, we can relax the semantics so `f(nonnull null)` is equivalent to `f(poison)`, but (A) it again blocks another set of optimizations, and (B) this makes the semantics of nonnull deviate from other attributes like dereferenceable.
I found that there was a similar discussion about this issue in the past as well, but seems it is not settled yet.
What should the semantics of nonnull be?

I had been operating under the idea that it was UB. However, it probably should be poison. Do we care if the pointer is nonnull if it's never used? It's not clear to me that we do. It's not as though we somehow optimize the parameter passing itself based on the nonnull property.

-Hal

4

Not sure the semantics of "used" you propose is sufficient. AFAIU the proposal, "used" could only be used in cases where the function will always trigger UB if poison is passed as argument.
The semantics of attributes is usually the other way around, since function calls need to have UB as strong as the worst behavior of the function. If a function may for some reason trigger UB with a given set of arguments, then the function call has to trigger UB as well.

Imagine something like:
Call f(null, 1)

int f(nonnull %ptr, int c) {
  if (c)
    deref %ptr
}

You can't use the "used" attribute, since UB is only conditional. So we would say the return value of f(null, 1) is poison. But if you inline the function you get UB. Inlining has to continue to be correct without exceptions.
Maybe I misunderstood the semantics of used, but if not I hope the example above is sufficient to show it isn't sufficient.

Thanks,
Nuno

5

Hi Nuno,

(Disclaimer: This is before my first coffee)

[ Moved from the end of Nuno's email]

Maybe I misunderstood the semantics of used, but if not I hope the
example above is sufficient to show it isn't sufficient.

I think we somehow talk past each other :(. It seems we actually agree
on the semantics of "used" but the meaning/use of attributes seems to be
the problem. I tried to explain where I am coming from below.

Not sure the semantics of "used" you propose is sufficient. AFAIU the
proposal, "used" could only be used in cases where the function will
always trigger UB if poison is passed as argument. The semantics of
attributes is usually the other way around, since function calls need
to have UB as strong as the worst behavior of the function. If a
function may for some reason trigger UB with a given set of arguments,
then the function call has to trigger UB as well.

"Used", as other attributes are "best effort". We can drop them any
time, so having "insufficient information" is not a correctness problem
but an optimization problem. I mean, even if the function always causes
UB if a `null` argument is given we do not need to know/annotate/exploit
that. In fact, we can, and do, throw away that information, e.g., by
removing the instruction known to cause UB which effectively defines
some semantic for the UB program (which is then "w/o UB"). Long story
short, I don't think "as strong as the worst behavior" is plausible (nor
possible TBH).

Imagine something like:
Call f(null, 1)

int f(nonnull %ptr, int c) {
  if (c)
    deref %ptr
}

You can't use the "used" attribute, since UB is only conditional.

Agreed, for the callee (f) you cannot annotate "used". You can place
"used" on the call site though*. And you can place it on the callee (f)
if it was internal or you copy it to make it internal. So the
optimization potential is still there, even if it is a little trickier.

* FWIW, one-level of selective context sensitive propagaton is planned
  for the Attributor.

we would say the return value of f(null, 1) is poison. But if you
inline the function you get UB. Inlining has to continue to be correct
without exceptions.

The attributes will just never represent the possible UB exhaustively.
I mean, inlining is still correct and the UB that it will expose,
together with SCCP, was there all along. With one-level of context
sensitivity we could have even known, without we just didn't know but
that is fine too.

...

[ moved to the front ]

I hope this makes some sense.

Cheers,
  Johannes

P.S.
  I think I'll write "used" deduction later so we can take a look at how
  this would look like.

6

Hello all,

LangRef says it is undefined behavior to pass null to a nonnull argument
(`call f(nonnull null);`), but the semantics is too strong for a few
existing optimizations.
To support these, we can relax the semantics so `f(nonnull null)` is
equivalent to `f(poison)`, but (A) it again blocks another set of
optimizations, and (B) this makes the semantics of nonnull deviate from
other attributes like dereferenceable.

I forgot to explicit say that in my first email but whatever we decide
for `nonnull` needs to be applied to basically all other attributes as
well. `nonnul` is no way special (IMHO).

Cheers,
  Johannes

7

I forgot to explicit say that in my first email but whatever we decide for `nonnull` needs to be applied to basically all other attributes as well. `nonnul` is no way special (IMHO).

I think that not all attributes are the same. For example, "dereferenceable(n)" is quite strong. It allows e.g.:
f(dereferenceable(4) %p) {
  loop() {
    %v = load %p
    use(%v)
  }
}
=>
f(dereferenceable(4) %p) {
  %v = load %p
  loop() {
    use(%v)
  }
}

For this transformation to be correct, the function call must trigger UB if the pointer passed as argument is not dereferenceable. Otherwise, upon inlining, it would become UB.
Other attributes are not as severe. Ideally we would have a consistent solution so we don't need to remember which are the nice attributes.

Nuno

8

Hi Johannes,

Not sure the semantics of "used" you propose is sufficient. AFAIU the
proposal, "used" could only be used in cases where the function will
always trigger UB if poison is passed as argument. The semantics of
attributes is usually the other way around, since function calls need
to have UB as strong as the worst behavior of the function. If a
function may for some reason trigger UB with a given set of arguments,
then the function call has to trigger UB as well.

"Used", as other attributes are "best effort". We can drop them any time, so having "insufficient information" is not a correctness problem but an optimization problem. I mean, even if the function always causes UB if a `null` argument is given we do not need to know/annotate/exploit that. In fact, we can, and do, throw away that information, e.g., by removing the instruction known to cause UB which effectively defines some semantic for the UB program (which is then "w/o UB"). Long story short, I don't think "as strong as the worst behavior" is plausible (nor possible TBH).

I agree with the motivation, but not with the exact semantics. The reason is that it seems that removing "used" wouldn't be possible. This is because a function with "used" gives poison, and without gives UB. It should the other way around, such that optimizers can freely remove "used".
To make it clear, what I understood was:
- %v = call @fn(nonnull null) -- %v == poison
- %v = call @fn(nonnull used null) -- UB

Even if the function is just a load of the pointer argument.

Nuno

Imagine something like:
Call f(null, 1)

int f(nonnull %ptr, int c) {
  if (c)
    deref %ptr
}

You can't use the "used" attribute, since UB is only conditional.

Agreed, for the callee (f) you cannot annotate "used". You can place "used" on the call site though*. And you can place it on the callee (f) if it was internal or you copy it to make it internal. So the optimization potential is still there, even if it is a little trickier.

* FWIW, one-level of selective context sensitive propagaton is planned
  for the Attributor.

we would say the return value of f(null, 1) is poison. But if you
inline the function you get UB. Inlining has to continue to be correct
without exceptions.

The attributes will just never represent the possible UB exhaustively.
I mean, inlining is still correct and the UB that it will expose, together with SCCP, was there all along. With one-level of context sensitivity we could have even known, without we just didn't know but that is fine too.

...

[ moved to the front ]

I hope this makes some sense.

Cheers,
  Johannes

P.S.
  I think I'll write "used" deduction later so we can take a look at how
  this would look like.

9

I think we are actually in agreement. "Used" should be removable, it would potentially define UB but that is valid and happening anyway everywhere.
Maybe my initial mail might have been confusing but I tried to show that with this snippet:

  void @foo(nonnull);
  void @bar(nonnull used);

> foo(NULL) // <- argument is poison inside of @foo
> bar(NULL) // <- UB at the call site of @bar

If we remove `used`, thus go from @bar to @foo, we get a poison argument instead of UB, which is fine.

WDYT?

Even if the function is just a load of the pointer argument.

The Attributor does infer `nonnull` and `dereferenceable` in this case already so `used` would follow the same logic (+ look for uses in branches etc)

FWIW, frontends that want `nonnull`, `align`, `dereferenceable`, etc. to keep the UB behavior can just add `used` as well.

10

I think calling the attribute "used" is confusing. I'd suggest the following:

"not_poison": If an argument is marked not_poison, and the argument is poison at runtime, the call is instant UB. Whether an argument is poison is checked after the rules for other attributes like "nonnull" and "align" are applied.

This makes it clear that the IR semantics don't depend on the implementation of the called function. And it's the logical extension of the way we define the relationship between UB and poison for instructions.

-Eli

11

I like “not_poison” a lot.

That one can make UB out of poison and other attributes make poison when violated.

12

I think calling the attribute “used” is confusing. I’d suggest the following:

“not_poison”: If an argument is marked not_poison, and the argument is poison at runtime, the call is instant UB. Whether an argument is poison is checked after the rules for other attributes like “nonnull” and “align” are applied.

This makes it clear that the IR semantics don’t depend on the implementation of the called function. And it’s the logical extension of the way we define the relationship between UB and poison for instructions.

Would I be right in assuming that frontends could annotate all arguments (at call-site) with the non_poison attribute to start with? And then it would get dropped during optimization if necessary to add inferred attributes.

Nikita

13

I'm really not sure I agree there's a problem with the current semantics at all.

The root of your argument appears to be that passing poison to a function argument is "harmless" if that argument is unused in the callee. This seems reasonable to me, but it brings with it a restriction on any IPO pass which is non-obvious. It essentially requires that the IPA argument inference framework prove both that a property holds, and that if that property didn't hold UB would be triggered. (I think this is similar in spirit to the "used" discussion downthread.) In general, it is much easier to prove the former property than the later.

I would simply state that per the current semantics, any IPO/IPA transform which doesn't do so is buggy. That's not pretty, but it's valid and I believe matches (most of?) the current implementation.

Conversely, the power for the frontend to annotate such facts on the function boundary is one of the key advantages higher level semantics give over inference. I would be very reluctant to give that up.

To be clear, I'm completely open to proposals to change the current semantics for ease of implementation on the IPO/IPA side. I just think it's important to distinguish between "current semantics are wrong" and "current semantics are inconvenient".

Philip

14

FWIW, frontends that want nonnull, align, dereferenceable, etc. to keep the
UB behavior can just add used as well.

If the frontend wants to keep UB, the behavior now, add not_poison with the attribute.

It would never get dropped on purpose though, at least I don’t see why. Inferring information works the same regardless, what that information means once attached. It could be poison or UB, it could also change over time, e.g when we infer not_poison.

15

I think we are actually in agreement. "Used" should be removable, it would potentially define UB but that is valid and happening anyway everywhere.
Maybe my initial mail might have been confusing but I tried to show that with this snippet:

  void @foo(nonnull);
  void @bar(nonnull used);

> foo(NULL) // <- argument is poison inside of @foo
> bar(NULL) // <- UB at the call site of @bar

If we remove `used`, thus go from @bar to @foo, we get a poison argument instead of UB, which is fine.

Ah, now I understand the idea. Sorry, I was thinking about the return value of the function rather that the value of the argument.
The guarantee that a callee gets is that a nonnull argument is either non-null or poison. Should be sufficient to fold comparisons with null.
The disadvantage is that the caller cannot infer that a pointer passed as nonnull argument is indeed non-null. Unless you use this non_poison attribute.

I don't think I have enough data/experience to have at any idea which of these 3 semantics is better (outright UB vs UB only if non_poison vs arg is poison in callee).
If frontends add non_poison everywhere, then it's that same have any outright UB semantics. Deducing it might not be very easy either.

Nuno

16

I'm really not sure I agree there's a problem with the current semantics at
all.

The root of your argument appears to be that passing poison to a function
argument is "harmless" if that argument is unused in the callee. This seems
reasonable to me, but it brings with it a restriction on any IPO pass which
is non-obvious. It essentially requires that the IPA argument inference
framework prove both that a property holds, and that if that property didn't
hold UB would be triggered. (I think this is similar in spirit to the
"used" discussion downthread.) In general, it is much easier to prove the
former property than the later.

I would simply state that per the current semantics, any IPO/IPA transform
which doesn't do so is buggy. That's not pretty, but it's valid and I
believe matches (most of?) the current implementation.

There is a good example (below) that shows how we misinterpret this
already and I anticipate more as we improve our attribute deduction
capabilities.

Conversely, the power for the frontend to annotate such facts on the
function boundary is one of the key advantages higher level semantics give
over inference. I would be very reluctant to give that up.

You would not loose anything. As we discussed in the other part of the
thread:
  `attr` + `not_poison` (aka. `used`) => current UB semantics
All we get is a two step process which frontends can avoid by always
using the attributes together.

To be clear, I'm completely open to proposals to change the current
semantics for ease of implementation on the IPO/IPA side. I just think it's
important to distinguish between "current semantics are wrong" and "current
semantics are inconvenient".

Juneyoung lists nice examples of transformations that are "buggy"
according to the current semantics. I think one of the strongest
arguments for a change is his case 2. You can also write it as:

void @bar();
void @foo(nonnull %a, %offset) {
  %g = gep inbounds %a, %offset
  call void @bar(%g) ; <- You cannot mark %g at the call
                                 ; site as nonnull according to the
                                 ; current lang-ref rules as a
                                 ; violation of `inbounds` results
                                 ; in a poison value and not UB.
                                 ; Now, `call void @bar(nonnull %g)`
                                 ; would introduce UB where there was
                                 ; none. We still do that though,
                                 ; e.g., in instcombine. The helper
                                 ; `isKnownNonZero` will return true
                                 ; as well, which actually means,
                                 ; non-zero or poison.
}

Cheers,
  Johannes

17

Hello all,

I think not_poison (Johannes’s used keyword) makes sense. We can simulate the original UB semantics by simply attaching it, as explained.
For the attributes other than nonnull, we may need more discussion; align attribute seems to be okay with defining it as poison, dereferenceable may need UB even without nonnull (because it needs to be non-poison as shown Nuno’s hoisting example).

The reason why I think not_poison is good even if it may cause divergence of attribute semantics is that it brings a few more opportunities to optimizations.

(1) We can do optimizations that require certain operands to be never poison.

This is important for, say, hoisting of division:

void f(int x, int y) {
int x0 = x > 0 ? x : 1; // x0 is never zero or poison(undef)
loop() { f(y / x0); }
}
=>

void f(int x, int y) { ; x shouldn’t be undef/poison

int x0 = x > 0 ? x : 1;
int tmp = y / x0; // this may raise UB
loop() { f(tmp); }
}

This optimization is incorrect if x is undef or poison. If x has non_poison, this becomes valid.

I guess in many cases Rust/Swift functions can be lowered into IR functions with not_poison flags attached (though I’m not an Rust/Swift expert, so just a guess)
For C, people may want to allow idioms like below, so further investigation is needed:

int x, y;
if (cond) x = 1; else y = 1;
f(cond, x, y);

(2) Hoisting of function call becomes easier and semantically clearer

https://godbolt.org/z/ThYt29

f() call is hoisted out of the loop thanks to speculatable attribute, but this is problematic if nonnull was defined to raise UB.

We should have syntactically prohibited having nonnull and speculatable in a single function declaration, but this may block optimization opportunities.
By adding not_poison and making nonnull to have poison semantics, this problem is resolved.

Thanks,
Juneyoung Lee

18

Correction of a few typos:

dereferenceable may need UB even without nonnull
may need to be UB even without non_poison

int x0 = x > 0 ? x : 1; // x0 is never zero or poison(undef)
// x0 should be never zero or poison(undef)

19

For reference, the hoisting example was:

f(dereferenceable(4) %p) {
  loop() {
    %v = load %p
    use(%v)
  }
}
=>
f(dereferenceable(4) %p) {
  %v = load %p
  loop() {
    use(%v)
  }
}

Would it be correct to resolve this by saying that dereferenceable(N)
*implies* not_poison? This would be helpful as a clarification of how
it all fits together.

Cheers,
Nicolai

20

I think not_poison (Johannes's used keyword) makes sense. We can simulate
the original UB semantics by simply attaching it, as explained.

Agreed.

For the attributes other than nonnull, we may need more discussion; align
attribute seems to be okay with defining it as poison, dereferenceable may
need UB even without nonnull (because it needs to be non-poison as shown
Nuno's hoisting example).

I would strongly prefer not to diverge things here.

The reason why I think not_poison is good even if it may cause divergence
of attribute semantics is that it brings a few more opportunities to
optimizations.

I am unsure if there are opportunities where you need "poison" for
`nonnull` and "UB" for the rest. With `non_poison` we get, poison for
all or UB for all. We can think of other combinations but we should
determine if we actually need them.

(1) We can do optimizations that require certain operands to be never
poison.

This is important for, say, hoisting of division:

void f(int x, int y) {
int x0 = x > 0 ? x : 1; // x0 is never zero *or poison(undef)*
loop() { f(y / x0); }
}
=>
void f(int x, int y) { ; x shouldn't be undef/poison
int x0 = x > 0 ? x : 1;
int tmp = y / x0; // this may raise UB
loop() { f(tmp); }
}

This optimization is incorrect if x is undef or poison. If x has
non_poison, this becomes valid.

I don't understand this. Why should the transformed code raise UB when
the original did not? I assume the loop is executed for sure, if the
loop is not executed for sure, the situation is different but then I
don't think the hoisting is "sound". (Btw. `nonnull` should also be
applicable to integers.)

Three cases for a loop that is always entered:
1) x = undef,
    if each use of x allows a different value I pick 1 in the comparison
    and 0 otherwise, this is UB in either case.
    if each use (in the same instruction) has to be the same `x0 = max(x, 1)`
    which should be save.
2) x = poison,
    you should be able to propagate `x0 = poison` which is UB in either
    case.
3) x is a "proper value",
    `x0 = max(x, 1)` which should be save.

Let me know what I am missing here.

I guess in many cases Rust/Swift functions can be lowered into IR functions
with not_poison flags attached (though I'm not an Rust/Swift expert, so
just a guess)
For C, people may want to allow idioms like below, so further investigation
is needed:

int x, y;
if (cond) x = 1; else y = 1;
f(cond, x, y);

I'm unsure what semantics you want here. Either x or y is uninitialized,
right? From the C perspective that is totally fine so far (AFAIK).

(2) Hoisting of function call becomes easier and semantically clearer

Compiler Explorer
f() call is hoisted out of the loop thanks to `speculatable` attribute, but
this is problematic if nonnull was defined to raise UB.
We should have syntactically prohibited having nonnull and speculatable in
a single function declaration, but this may block optimization
opportunities.
By adding not_poison and making nonnull to have poison semantics, this
problem is resolved.

I don't see why nonnull (either with UB or poison semantics) is
necessary incompatible with speculateable (which has UB semantics) but I
agree that the transformation we do here become actually valid only with
poison for nonnull.

Cheers,
  Johannes