Page MenuHomePhabricator

Allow nonnull/align attribute to accept poison
ClosedPublic

Authored by aqjune on Oct 31 2020, 6:56 AM.

Details

Summary

Currently LLVM is relying on ValueTracking's isKnownNonZero to attach nonnull, which can return true when the value is poison.
To make the semantics of nonnull consistent with the behavior of isKnownNonZero, this makes the semantics of nonnull to accept poison, and return poison if the input pointer isn't null.
This makes many transformations like below legal:

%p = gep inbounds %x, 1 ; % p is non-null pointer or poison
call void @f(%p)        ; instcombine converts this to call void @f(nonnull %p)

This semantics makes propagation of nonnull to caller illegal.
The reason is that, passing poison to nonnull does not immediately raise UB anymore, so such program is still well defined, if the callee does not use the argument.
Having noundef attribute there re-allows this.

define void @f(i8* %p) {       ; functionattr cannot mark %p nonnull here anymore
  call void @g(i8* nonnull %p) ; .. because @g never raises UB if it never uses %p.
  ret void
}

Another attribute that needs to be updated is align. This patch updates the semantics of align to accept poison as well.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a project: Restricted Project. · View Herald TranscriptOct 31 2020, 6:56 AM
aqjune requested review of this revision.Oct 31 2020, 6:56 AM

I tried to update Attributor as well, but the infrastructure was quite big; I'll update Attributor as well if someone points where to fix.

aqjune updated this revision to Diff 302096.Oct 31 2020, 8:32 AM

make LangRef explicitly describe non-ub

To share my understanding about how nonnull is used in optimizations:

  1. It is mainly used to fold away null pointer checks.
define void @f(i8* nonnull %p) {
  if (icmp eq %p, null) ret void         ; this check can be folded to true
  ...
}

Note that the new nonnull-or-poison semantics is fine in the above case because if %p is poison we can fold icmp eq %p, null into false.

A similar but slightly different case:

...
call void @f(i8* nonnull %p)
if (icmp eq %p, null) ret void

In this case, the nonnull-or-poison semantics cannot make the comparison after call folded, because f may not use the poison argument at all, making the program well-defined.
But, if f has noundef attribute as well, this is fine because passing null to f is now UB:

...
call void @f(i8* noundef nonnull %p)
if (icmp eq %p, null) ret void            ; %p is always non-null pointer!
  1. It is combined with dereferenceable_or_null to infer dereferenceable.

This is still fine with the new nonnull-or-poison because passing poison to dereferenceable_or_null is still UB, guaranteeing that the pointer is never poison.

jdoerfert requested changes to this revision.Oct 31 2020, 3:35 PM

I think we have two choices here:

  1. Don't raise UB when "value attributes" are passed a "wrong value", e.g., null for a nonnull attribute, but make the value poison. Use nonull + noundef to make it UB.
  2. Make all "value attributes" accept poison without raising UB.

I was in the past pushing for 1), I don't have the link handy but we can probably find it. I think the last time I brought this up was the noundef discussion actually.
One of my examples was the gep one shown in the commit message,
I vaguely remember one where the user "broke the contract" but in a way they would assume to be harmless, e.g., they did not cause any side-effect, maybe something like:

void foo(bool valid, X& x) {
  if (!valid) return;
  ...
}

obj_ptr = null;
foo(obj_ptr != null, *obj_ptr);

I remember @efriedma was not a fan of 1) at the time, unsure if that is still the case with noundef in place.

If we don't do 1), we should talk about 2) before we make nonnull special. I fail to see the reason it is different from any other (or at least most) "value attributes".

This revision now requires changes to proceed.Oct 31 2020, 3:35 PM
aqjune added a comment.Nov 1 2020, 2:37 AM

I think we have two choices here:

  1. Don't raise UB when "value attributes" are passed a "wrong value", e.g., null for a nonnull attribute, but make the value poison. Use nonull + noundef to make it UB.
  2. Make all "value attributes" accept poison without raising UB.

If we don't do 1), we should talk about 2) before we make nonnull special.

It seems these two choices are entangled.
If f(nonnull poison) is okay (in other words, not UB), then f(nonnull null) shouldn't be UB as well.
The reason is that poison can be folded into null in any time.
For example, when inbounds is stripped from v = gep inbounds ..., v can be transformed from poison to null pointer.

I fail to see the reason it is different from any other (or at least most) "value attributes".

I had a thought about this, and here's what I think:
Each value attribute has a primary transformation to target.
For example, nonnull is for null comparison folding, and dereferenceable is for reordering of load instructions by guaranteeing that dereferencing the pointer never raises UB (unless the pointer is freed).

I think nonnull is different from dereferenceable in that allowing it to be poison doesn't break the intended optimization.
This folding is still okay even if the pointer is poison.
By allowing poison, further optimizations can be done as well because gep inbounds ptr, 1 can be marked as nonnull.
However, allowing dereferenceable to be poison will block such optimizations, which doesn't seem quite desirable IMO.

This causes the properties of attributes slightly heterogeneous, but I think it is fine if the goal is to support more optimizations.

uenoku added a subscriber: uenoku.Nov 1 2020, 10:12 AM

I think we have two choices here:

  1. Don't raise UB when "value attributes" are passed a "wrong value", e.g., null for a nonnull attribute, but make the value poison. Use nonull + noundef to make it UB.
  2. Make all "value attributes" accept poison without raising UB.

If we don't do 1), we should talk about 2) before we make nonnull special.

It seems these two choices are entangled.
If f(nonnull poison) is okay (in other words, not UB), then f(nonnull null) shouldn't be UB as well.
The reason is that poison can be folded into null in any time.
For example, when inbounds is stripped from v = gep inbounds ..., v can be transformed from poison to null pointer.

Agreed. So let's go with 1) and we change all the "value attribute" semantics to produce poison on violation.
We have noundef for the UB case, that was the reason I wanted it ;)

I fail to see the reason it is different from any other (or at least most) "value attributes".

I had a thought about this, and here's what I think:
Each value attribute has a primary transformation to target.
For example, nonnull is for null comparison folding, and dereferenceable is for reordering of load instructions by guaranteeing that dereferencing the pointer never raises UB (unless the pointer is freed).

I think nonnull is different from dereferenceable in that allowing it to be poison doesn't break the intended optimization.
This folding is still okay even if the pointer is poison.
By allowing poison, further optimizations can be done as well because gep inbounds ptr, 1 can be marked as nonnull.
However, allowing dereferenceable to be poison will block such optimizations, which doesn't seem quite desirable IMO.

This causes the properties of attributes slightly heterogeneous, but I think it is fine if the goal is to support more optimizations.

I don't think we should argue this way, at least it should be the last resort. An attribute describes a property, doesn't matter if it is
nonnull, align, or dereferenceable, it's a property of the value. Now, due to the way things are it is possible to violate
that property and then we need to define what is happening. If we do this on a case-by-case basis and with specific transformations
in mind, we will make the IR more complex, the attributes confusing, and in the end non-composeable.

What is the reason not to go with 1) above, so to remove the UB behavior and produce poison. We write an RFC and do the change.
FWIW, that is what AAUndefinedBehavior in the Attributor already does, only with noundef it will deduce UB for nonnull null.

Agreed. So let's go with 1) and we change all the "value attribute" semantics to produce poison on violation.
We have noundef for the UB case, that was the reason I wanted it ;)

Thank you, glad to hear that moving towards the change!

I don't think we should argue this way, at least it should be the last resort. An attribute describes a property, doesn't matter if it is
nonnull, align, or dereferenceable, it's a property of the value. Now, due to the way things are it is possible to violate
that property and then we need to define what is happening. If we do this on a case-by-case basis and with specific transformations
in mind, we will make the IR more complex, the attributes confusing, and in the end non-composeable.

I think the discussion finally falls into which attribute is a value attribute and which is not.
Value attributes should have the same semantics as you said.
Sometimes value attribute and non-value attribute can interact with each other (e.g., byval implies nonnull unless null is a valid pointer), but such complexity should be only at there.

FWIW, that is what AAUndefinedBehavior in the Attributor already does, only with noundef it will deduce UB for nonnull null.

Aha, thanks for the info.

Agreed. So let's go with 1) and we change all the "value attribute" semantics to produce poison on violation.
We have noundef for the UB case, that was the reason I wanted it ;)

Thank you, glad to hear that moving towards the change!

Wasn't that my position for more than a year now ;)

I don't think we should argue this way, at least it should be the last resort. An attribute describes a property, doesn't matter if it is
nonnull, align, or dereferenceable, it's a property of the value. Now, due to the way things are it is possible to violate
that property and then we need to define what is happening. If we do this on a case-by-case basis and with specific transformations
in mind, we will make the IR more complex, the attributes confusing, and in the end non-composeable.

I think the discussion finally falls into which attribute is a value attribute and which is not.
Value attributes should have the same semantics as you said.
Sometimes value attribute and non-value attribute can interact with each other (e.g., byval implies nonnull unless null is a valid pointer), but such complexity should be only at there.

Fair. Though, I think we want to produce poison for one set of attributes for which the name "value attribute" was not well chosen.
So far, the things I think should produce poison not UB are:

(pure) value attributes:

  • nonnull
  • align
  • [used_bits] (not existing yet)

(context) value attributes:

  • dereferenceable
  • dereferenceable_or_null
  • [object_size] (as proposed on the list)

WDYT?

FWIW, that is what AAUndefinedBehavior in the Attributor already does, only with noundef it will deduce UB for nonnull null.

Aha, thanks for the info.

aqjune added a comment.Nov 2 2020, 1:02 PM

Fair. Though, I think we want to produce poison for one set of attributes for which the name "value attribute" was not well chosen.
So far, the things I think should produce poison not UB are:

(pure) value attributes:

  • nonnull
  • align
  • [used_bits] (not existing yet)

(context) value attributes:

  • dereferenceable
  • dereferenceable_or_null
  • [object_size] (as proposed on the list)

WDYT?

In case of dereferenceable, my opinion is still slightly different: it represents the property of the memory at the point.
If a memory block is freed, a same pointer value won't be dereferenceable after the deallocation.

Other than the conceptual reason, my practical concern about dereferenceable is that dereferenceable is hard to use unless it is with noundef.
Since loading poison is UB, the attribute can't still give a guarantee that loading the pointer is well defined.
Furthermore, noundef is hard to infer from the context. For example,

store i32 0, i32* %p
call void @f(i32* %p) ; can we infer %p's noundef & dereferenceable(4) from store?

store i32 0, i32* %p does not guarantee that %p is noundef because it can be partially undef but still dereferenceable (D87994 is a relevant LangRef patch).

The example above was propagating the attribute from caller to callee, but the inverse direction (callee -> caller) is the same: If @f contains a store, it guarantees that the pointer is dereferenceable but not noundef.

In order to regain optimization power, we need a way to attach noundef more aggressively.
D81678 will attach noundef to arguments, and additionally I think it is valid for clang to attach !noundef when lowering non-char typed lvalues to load.

Fair. Though, I think we want to produce poison for one set of attributes for which the name "value attribute" was not well chosen.
So far, the things I think should produce poison not UB are:

(pure) value attributes:

  • nonnull
  • align
  • [used_bits] (not existing yet)

(context) value attributes:

  • dereferenceable
  • dereferenceable_or_null
  • [object_size] (as proposed on the list)

WDYT?

In case of dereferenceable, my opinion is still slightly different: it represents the property of the memory at the point.
If a memory block is freed, a same pointer value won't be dereferenceable after the deallocation.

That is why it is not listed in the "pure" category ;). It is not only a property of the value, but it still should be split wrt UB behavior. See below for my reasoning based on your example.

Partially related:
It is, nowadays, unclear to me if your interpretation of dereferenceable is what we want though. It is/was my interpretation as well FWIW.
@reames suggested that dereferenceability is not about it pointing to an allocated object but to a memory location that can be loaded without causing observable behavior, i.a., a trap.
Unsure if we want a new attribute for that but certainly there are reasons that you want that information which is a "value property" and not tied to the "allocation status".

Other than the conceptual reason, my practical concern about dereferenceable is that dereferenceable is hard to use unless it is with noundef.

Regardless of my argument below, nobody said you cannot use dereferenceable with noundef "all the time".
I mean, if you argue a current use of dereferenceable would actually require the "UB if violated" behavior, then simply also add noundef as well.

Since loading poison is UB, the attribute can't still give a guarantee that loading the pointer is well defined.

Can you clarify "loading poison is UB". I'm unsure I follow/agree.

FWIW, loading a dereferenceable pointer might result in poison but it's even not clear to me that out-of-bounds accesses are UB as of now (in IR).
Maybe I just forgot where it says I cannot do load i32, i32* (bitcast i8* [alloca i8] to i32*). I certainly would get 3 poison bytes if not UB.

Furthermore, noundef is hard to infer from the context. For example,

store i32 0, i32* %p
call void @f(i32* %p) ; can we infer %p's noundef & dereferenceable(4) from store?

store i32 0, i32* %p does not guarantee that %p is noundef because it can be partially undef but still dereferenceable (D87994 is a relevant LangRef patch).

The example above was propagating the attribute from caller to callee, but the inverse direction (callee -> caller) is the same: If @f contains a store, it guarantees that the pointer is dereferenceable but not noundef.

OK, I'm unsure I get the point though. We can derive dereferenceable in either case, agreed? What is currently better?

(@hideto @stefan1 @okura, I think the Attributor might derive noundef here but should not, wdyt?)

In order to regain optimization power, we need a way to attach noundef more aggressively.

This is correct but orthogonal. Having noundef "backed-in" to other attributes is not helping us to derive noundef it just prevents us to derive other attributes.

D81678 will attach noundef to arguments, and additionally I think it is valid for clang to attach !noundef when lowering non-char typed lvalues to load.

Great.

aqjune added a comment.Nov 3 2020, 1:19 AM

In order to regain optimization power, we need a way to attach noundef more aggressively.

This is correct but orthogonal. Having noundef "backed-in" to other attributes is not helping us to derive noundef it just prevents us to derive other attributes.

I think dereferenceable(current UB semantics) != dereferenceable(new poison semantics) + noundef. In the past I thought they were equal, but here is the reason...

The reason is that the current dereferenceable accepts partially undefined pointers, IIUC. At least, LangRef does not prohibit it.
noundef allows accepting well-defined pointers only, so there is a slight difference.

Note that this also happens to nonnull: nonnull (current UB sem.) != nonnull(new poison sem.) + noundef.
However, the situation is slightly different, because the change allows more analysis.
gep inbounds p, 1 is now nonnull, which is certainly a benefit.

In order to regain equivalence, nopoison should be introduced. nopoison allows the value to be (partially) undef but not poison.
dereferenceable(current UB semantics) == dereferenceable(new poison semantics) + nopoison holds.

This is really due to the complexity of undef.... :(

Can you clarify "loading poison is UB". I'm unsure I follow/agree.

FWIW, loading a dereferenceable pointer might result in poison but it's even not clear to me that out-of-bounds accesses are UB as of now (in IR).
Maybe I just forgot where it says I cannot do load i32, i32* (bitcast i8* [alloca i8] to i32*). I certainly would get 3 poison bytes if not UB.

I meant 'loading a poison pointer', sorry. load i8* poison raises UB.

aqjune added a comment.Nov 3 2020, 1:21 AM

OK, I'm unsure I get the point though. We can derive dereferenceable in either case, agreed? What is currently better?

The current dereferenceable definition gives a guarantee that the pointer is not poison. :)
It is good because it guarantees that loads and stores to the pointer don't trap.

aqjune added a comment.Nov 3 2020, 7:03 PM

BTW, there are !nonnull metadata and llvm.assume with nonnull operand bundle as well - the semantics of those should be updated too.
Maybe we can just follow the semantics of nonnull attribute here.

(reviving an old discussion) to summarize the issue:
The issue was whether it is okay to make dereferenceable %p non-UB if %p was not dereferenceable.

In order to make the attribute useful, noundef %p should be accompanied.
The problem is that we cannot infer noundef %p from store or load in general; noundef can be inferred in limited cases only.

aqjune added a comment.Dec 2 2020, 4:28 AM

@jdoerfert Kindly ping, what do you think?

I think making align and nonnull to follow poison semantics is still a great thing.
The update of nonnull makes its semantics and existing optimizations about nonnull consistent.
I did not deeply investigate align yet, but I have a good feeling that that moving towards poison semantics will explain more optimizations about align that involve gep inbounds with aligned offsets.

jdoerfert accepted this revision.Dec 2 2020, 8:41 AM

Some nits. I think the direction is right. Update the commit message though. And please wait for an OK by @efriedma .

llvm/docs/LangRef.rst
1231

Mention the combination with noundef please.

llvm/lib/Analysis/ValueTracking.cpp
2091–2092

/* AllowUndefOrPoison */ false

llvm/lib/Transforms/IPO/FunctionAttrs.cpp
645

see above.

llvm/test/Analysis/ValueTracking/known-nonnull-at.ll
5

maybe rename to make it clear at the call site

This revision is now accepted and ready to land.Dec 2 2020, 8:41 AM
aqjune updated this revision to Diff 309157.Dec 2 2020, 10:40 PM

Address comments

aqjune marked 4 inline comments as done.Dec 2 2020, 10:42 PM
aqjune edited the summary of this revision. (Show Details)Dec 2 2020, 10:46 PM
aqjune edited the summary of this revision. (Show Details)
aqjune updated this revision to Diff 309159.Dec 2 2020, 10:50 PM

minor fix to a test

aqjune added a comment.Dec 8 2020, 2:43 AM

@efriedma gentle ping

Slightly related to this patch: should llvm.assume's nonnull/align operand bundles be updated to follow this semantics as well?
I'll follow any semantics that would be convenient for Attributor's implementation or anything related to this.
I can make a LangRef update patch as well.

Should we have clarification about the semantics of align/nonnull bundle for the assume intrinsic?
When a function call is inlined, the attributes of the parameters may remain as assume's bundles:

call f(nonnull %p)
->
llvm.assume [ "nonnull"(%p) ]

Here are two possible semantics:

  1. When "nonnull"(%p) is at the operand bundle, there also should be "noundef"(%p), otherwise it is a no-op.
; A correct transformation
call f(nonnull noundef %p)
->
llvm.assume [ "nonnull"(%p), "noundef"(%p) ] ; since noundef and nonnull are both in the bundle, it is UB if %p is null
  1. "nonnull"(%p) diverges from nonnull, and immediately raises UB if %p is null. This means that the lowering should be done only when noundef existed.
; A correct transformation
call f(nonnull noundef %p)
->
llvm.assume [ "nonnull"(%p) ] ; this is UB if %p is null

The former makes attribute -> op bundle conversion simpler, whereas the latter makes reasoning from op bundle simpler (well, maybe both are simple enough). :)
I think either option is fine.

Should we have clarification about the semantics of align/nonnull bundle for the assume intrinsic?

Probably true, good catch. Why not make it the same as the attribute? So,

; A correct transformation
call f(nonnull %p, nonnull noundef %q)
->
llvm.assume [ "nonnull"(%p), "nonnull"(%q), "noundef"(%q)]
; where a `null` value for %p can be assumed to be a poison value and
; a `null` value for %q can be assumed to cause UB because `noundef` of
; poison is UB.

Should we have clarification about the semantics of align/nonnull bundle for the assume intrinsic?

Probably true, good catch. Why not make it the same as the attribute? So,

; A correct transformation
call f(nonnull %p, nonnull noundef %q)
->
llvm.assume [ "nonnull"(%p), "nonnull"(%q), "noundef"(%q)]
; where a `null` value for %p can be assumed to be a poison value and
; a `null` value for %q can be assumed to cause UB because `noundef` of
; poison is UB.

+1, I'll make a separate patch for this.

I like where this is going. Most of LLVM's alias analysis produce information that only holds if the value is not poison. Since these attributes are derived from said analysis, then it makes sense then they have the same "X is poison or foo(X) holds" semantics.
I agree that certain attributes are different, like dereferenceable. It is useless if the value might be poison as well. Though we may go with the same semantics and then require the noundef attribute to make it useful. Seems like a good way to go as well.

For the partial undef memory access example that Juneyoung gave.. Well, maybe we need to make it UB to dereference a non-deterministic value. Doesn't seem like it's a very useful thing to do, and this non-determinism comes from some previous undefined behavior, so it seems fine to just make dereference of partial undef UB. Simplifies things.

I'll make this patch include the updates in the align attribute first because it helps making fewer patches.
The next patch (operand bundle) will include changes in nonnull/align operand bundles as well.

For the partial undef memory access example that Juneyoung gave.. Well, maybe we need to make it UB to dereference a non-deterministic value. Doesn't seem like it's a very useful thing to do, and this non-determinism comes from some previous undefined behavior, so it seems fine to just make dereference of partial undef UB. Simplifies things.

There was a discussion for this: https://groups.google.com/g/llvm-dev/c/2Qk4fOHUoAE/m/OxZa3bIhAgAJ
This partially undef thing is a bit painful.. :/

For the partial undef memory access example that Juneyoung gave.. Well, maybe we need to make it UB to dereference a non-deterministic value. Doesn't seem like it's a very useful thing to do, and this non-determinism comes from some previous undefined behavior, so it seems fine to just make dereference of partial undef UB. Simplifies things.

There was a discussion for this: https://groups.google.com/g/llvm-dev/c/2Qk4fOHUoAE/m/OxZa3bIhAgAJ
This partially undef thing is a bit painful.. :/

If we allow partial undef pointers to be dereferenced, then it's nearly impossible to derive noundef for pointers. So we will have to rely on frontends to annotate. So the question is whether there's any benefit of allowing such accesses and whether that breaks any frontend if not. Can't think of any reason to allow them and that thread doesn't really provide any either AFAICT.

aqjune updated this revision to Diff 311540.Dec 14 2020, 3:39 AM

update langref align

I tried to fix Attributor to propagate nonnull/align only when there is noundef, but couldn't: https://godbolt.org/z/Yzsc14
Where should I start?

If we allow partial undef pointers to be dereferenced, then it's nearly impossible to derive noundef for pointers. So we will have to rely on frontends to annotate. So the question is whether there's any benefit of allowing such accesses and whether that breaks any frontend if not. Can't think of any reason to allow them and that thread doesn't really provide any either AFAICT.

I agree that any frontend won't emit undef when compiling a valid program, but I think the point is that the semantics requires a transformation that hoists a memory instruction to prove that the pointer isn't partially undef, which isn't done by LLVM now.

void f(i64 %offset) {
  p = alloca [16 x i8]
  assume(0 <= offset < 16)
  init(p)
  for (..) {
    v = load p[offset] // if offset is partially undef, this load cannot be hoisted out of the loop
    use(v)
  }
}
aqjune retitled this revision from Allow nonnull attribute to accept poison to Allow nonnull/align attribute to accept poison.Dec 14 2020, 4:03 AM
aqjune edited the summary of this revision. (Show Details)

ping @efriedma

@jdoerfert Would it be okay if I land this after a week? D91480 also uses the semantics described in this patch as well.

jdoerfert accepted this revision.Jan 12 2021, 7:52 AM

For the attributor, add the tests that don't work with FIXMEs into the attributor test folder please, potentially just into the respective test files, e.g. nonnull.ll

I proposed some wording changes, but no semantic change.

llvm/docs/LangRef.rst
1163–1169

poison is not aligned, and can well be null. Let's state the intent and not "include" poison as valid input. It is not and that is why it triggers the output to be poison.

1228–1233
aqjune updated this revision to Diff 316308.Jan 12 2021, 7:13 PM

Address comments, leave tests with FIXME

aqjune marked 2 inline comments as done.Jan 12 2021, 7:13 PM
This revision was landed with ongoing or failed builds.Jan 19 2021, 6:54 PM
This revision was automatically updated to reflect the committed changes.

Should we have clarification about the semantics of align/nonnull bundle for the assume intrinsic?

Probably true, good catch. Why not make it the same as the attribute? So,

; A correct transformation
call f(nonnull %p, nonnull noundef %q)
->
llvm.assume [ "nonnull"(%p), "nonnull"(%q), "noundef"(%q)]
; where a `null` value for %p can be assumed to be a poison value and
; a `null` value for %q can be assumed to cause UB because `noundef` of
; poison is UB.

+1, I'll make a separate patch for this.

I'll start working on this soon.

MaskRay added a subscriber: MaskRay.EditedFeb 23 2021, 11:50 PM

I got a bit confused by the summary until I realized that I should read it this way:) Perhaps you can still edit the summary like the following:

This propagates the nonnull attribute to the caller in the following case:

%p = gep inbounds %x, 1 ; % p is non-null pointer or poison
call void @f(%p)        ; instcombine converts this to call void @f(nonnull %p)

<del>Instead, </del>This patch makes it illegal to propagate the nonnull attribute to the caller, e.g.

define void @f(i8* %p) {       ; functionattr cannot mark %p nonnull here anymore
  call void @g(i8* nonnull %p) ; .. because @g never raises UB if it never uses %p.
  ret void
}

To re-allow nonnull propagation to the caller, the caller should have the noundef attribute.

aqjune edited the summary of this revision. (Show Details)Feb 24 2021, 12:18 AM

I got a bit confused by the summary until I realized that I should read it this way:) Perhaps you can still edit the summary like the following:

This propagates the nonnull attribute to the caller in the following case:

%p = gep inbounds %x, 1 ; % p is non-null pointer or poison
call void @f(%p)        ; instcombine converts this to call void @f(nonnull %p)

<del>Instead, </del>This patch makes it illegal to propagate the nonnull attribute to the caller, e.g.

define void @f(i8* %p) {       ; functionattr cannot mark %p nonnull here anymore
  call void @g(i8* nonnull %p) ; .. because @g never raises UB if it never uses %p.
  ret void
}

To re-allow nonnull propagation to the caller, the caller should have the noundef attribute.

Edited the summary, thanks :)

aqjune added a comment.EditedMar 1 2021, 5:50 AM

Should we have clarification about the semantics of align/nonnull bundle for the assume intrinsic?

Probably true, good catch. Why not make it the same as the attribute? So,

; A correct transformation
call f(nonnull %p, nonnull noundef %q)
->
llvm.assume [ "nonnull"(%p), "nonnull"(%q), "noundef"(%q)]
; where a `null` value for %p can be assumed to be a poison value and
; a `null` value for %q can be assumed to cause UB because `noundef` of
; poison is UB.

+1, I'll make a separate patch for this.

While writing a LangRef patch for the semantic changes in nonnull & align attributes in assume operand bundle, I found one interesting case. :)

Creating assume from these two calls yields the same result:

call void @hi1(i8* nonnull %val, i8* noundef %val)
call void @hi2(i8* nonnull noundef %val)

They both generate:

call void @llvm.assume(true)["nonnull"(i8* %val), "noundef"(i8* %val)]

A question is whether this assume is UB if, say, %val is inttoptr(1).
Creating this assume from call void @hi2(%val) is okay because call void @hi2(%val) is already UB.
But, creating the assume from call void @hi1(%val, %val) isn't okay! %val is non-null and noundef, so the call is fine.

To distinguish these two, what about this?
(1) simply use UB semantics for nonnull attribute in assume operand bundle
(2) lower nonnull attribute in the call-site into nonnull bundle only if it is accompanied with noundef.
Then, we don't need to change anything about nonnull from LangRef: the current text is defining it as UB (https://llvm.org/docs/LangRef.html#assume-operand-bundles ).

While writing a LangRef patch for the semantic changes in nonnull & align attributes in assume operand bundle, I found one interesting case. :)

Creating assume from these two calls yields the same result:

call void @hi1(i8* nonnull %val, i8* noundef %val)
call void @hi2(i8* nonnull noundef %val)

They both generate:

call void @llvm.assume(true)["nonnull"(i8* %val), "noundef"(i8* %val)]

A question is whether this assume is UB if, say, %val is inttoptr(1).
Creating this assume from call void @hi2(%val) is okay because call void @hi2(%val) is already UB.
But, creating the assume from call void @hi1(%val, %val) isn't okay! %val is non-null and noundef, so the call is fine.

To distinguish these two, what about this?
(1) simply use UB semantics for nonnull attribute in assume operand bundle
(2) lower nonnull attribute in the call-site into nonnull bundle only if it is accompanied with noundef.
Then, we don't need to change anything about nonnull from LangRef: the current text is defining it as UB (https://llvm.org/docs/LangRef.html#assume-operand-bundles ).

I thought at first (2) is the way to go but then I asked myself if @hi1(%val, %val) is really not already UB. The question is, does val become poison for this use or is val poison in the scope of the use. I feel the latter is what we actually want. If we assume this is the only call of hi1 and we then do interprocedural transformations to replace the use of the first argument with the second or vice versa, would that be illegal because of the attribute mismatch or allowed? If it is the latter, the call must have been UB.

While writing a LangRef patch for the semantic changes in nonnull & align attributes in assume operand bundle, I found one interesting case. :)

Creating assume from these two calls yields the same result:

call void @hi1(i8* nonnull %val, i8* noundef %val)
call void @hi2(i8* nonnull noundef %val)

They both generate:

call void @llvm.assume(true)["nonnull"(i8* %val), "noundef"(i8* %val)]

A question is whether this assume is UB if, say, %val is inttoptr(1).
Creating this assume from call void @hi2(%val) is okay because call void @hi2(%val) is already UB.
But, creating the assume from call void @hi1(%val, %val) isn't okay! %val is non-null and noundef, so the call is fine.

To distinguish these two, what about this?
(1) simply use UB semantics for nonnull attribute in assume operand bundle
(2) lower nonnull attribute in the call-site into nonnull bundle only if it is accompanied with noundef.
Then, we don't need to change anything about nonnull from LangRef: the current text is defining it as UB (https://llvm.org/docs/LangRef.html#assume-operand-bundles ).

I thought at first (2) is the way to go but then I asked myself if @hi1(%val, %val) is really not already UB. The question is, does val become poison for this use or is val poison in the scope of the use. I feel the latter is what we actually want. If we assume this is the only call of hi1 and we then do interprocedural transformations to replace the use of the first argument with the second or vice versa, would that be illegal because of the attribute mismatch or allowed? If it is the latter, the call must have been UB.

Hmm, I think the issue happens with a call without noundef as well:

call void @hi1(nonnull %val, %val) ; let's assume that this is the only call

define void @hi(i8* %x, i8* %y) {
  use(%x, %y) ; this cannot be use(%x, %x)!
}

To do this replacement, nonnull at the call site should be dropped first.

Besides this, I think expanding the scope of being poison to the same variables makes optimizations like CSE hard. For example:

call void @hi1(<attr> %val, <attr2> %val2)

If CSE concludes that %val is %val2, it can remove %val2 and optimize it into:

call void @hi1(<attr> %val, <attr2> %val)

.. and this can unexpectedly introduce UB due to the synergy between <attr> and <attr2>. I guess fixing optimizations to consider attributes might be a bit costly.. :/

While writing a LangRef patch for the semantic changes in nonnull & align attributes in assume operand bundle, I found one interesting case. :)

Creating assume from these two calls yields the same result:

call void @hi1(i8* nonnull %val, i8* noundef %val)
call void @hi2(i8* nonnull noundef %val)

They both generate:

call void @llvm.assume(true)["nonnull"(i8* %val), "noundef"(i8* %val)]

A question is whether this assume is UB if, say, %val is inttoptr(1).
Creating this assume from call void @hi2(%val) is okay because call void @hi2(%val) is already UB.
But, creating the assume from call void @hi1(%val, %val) isn't okay! %val is non-null and noundef, so the call is fine.

To distinguish these two, what about this?
(1) simply use UB semantics for nonnull attribute in assume operand bundle
(2) lower nonnull attribute in the call-site into nonnull bundle only if it is accompanied with noundef.
Then, we don't need to change anything about nonnull from LangRef: the current text is defining it as UB (https://llvm.org/docs/LangRef.html#assume-operand-bundles ).

I thought at first (2) is the way to go but then I asked myself if @hi1(%val, %val) is really not already UB. The question is, does val become poison for this use or is val poison in the scope of the use. I feel the latter is what we actually want. If we assume this is the only call of hi1 and we then do interprocedural transformations to replace the use of the first argument with the second or vice versa, would that be illegal because of the attribute mismatch or allowed? If it is the latter, the call must have been UB.

Hmm, I think the issue happens with a call without noundef as well:

call void @hi1(nonnull %val, %val) ; let's assume that this is the only call

define void @hi(i8* %x, i8* %y) {
  use(%x, %y) ; this cannot be use(%x, %x)!
}

To do this replacement, nonnull at the call site should be dropped first.

Besides this, I think expanding the scope of being poison to the same variables makes optimizations like CSE hard. For example:

call void @hi1(<attr> %val, <attr2> %val2)

If CSE concludes that %val is %val2, it can remove %val2 and optimize it into:

call void @hi1(<attr> %val, <attr2> %val)

.. and this can unexpectedly introduce UB due to the synergy between <attr> and <attr2>. I guess fixing optimizations to consider attributes might be a bit costly.. :/

That is/was already the case, right? So, is the current behavior OK or not, potentially in light of making nonnull produce poison not UB.
I think it is/was OK, and, TBH I think it has to be. If we look at it scoped based it all makes sense (I think/hope).
On a practical note, you might not see all the call sites so "dropping first" doesn't work if you know that x == y from a local assume (in the hi example above).

If the attribute holds for the value in the scope, CSE is free to change val to val2 because the attributes did already conflict even if you used val and val2.
Do you see a problem when the attribute is scope based?

We might need range based assumptions (ref. section D and 3 in [0]) to encode this information properly when we go from calls to llvm.assume but that is doable.

[0] https://lists.llvm.org/pipermail/llvm-dev/2019-December/137632.html]

aqjune added a comment.Mar 1 2021, 6:13 PM

While writing a LangRef patch for the semantic changes in nonnull & align attributes in assume operand bundle, I found one interesting case. :)

Creating assume from these two calls yields the same result:

call void @hi1(i8* nonnull %val, i8* noundef %val)
call void @hi2(i8* nonnull noundef %val)

They both generate:

call void @llvm.assume(true)["nonnull"(i8* %val), "noundef"(i8* %val)]

A question is whether this assume is UB if, say, %val is inttoptr(1).
Creating this assume from call void @hi2(%val) is okay because call void @hi2(%val) is already UB.
But, creating the assume from call void @hi1(%val, %val) isn't okay! %val is non-null and noundef, so the call is fine.

To distinguish these two, what about this?
(1) simply use UB semantics for nonnull attribute in assume operand bundle
(2) lower nonnull attribute in the call-site into nonnull bundle only if it is accompanied with noundef.
Then, we don't need to change anything about nonnull from LangRef: the current text is defining it as UB (https://llvm.org/docs/LangRef.html#assume-operand-bundles ).

I thought at first (2) is the way to go but then I asked myself if @hi1(%val, %val) is really not already UB. The question is, does val become poison for this use or is val poison in the scope of the use. I feel the latter is what we actually want. If we assume this is the only call of hi1 and we then do interprocedural transformations to replace the use of the first argument with the second or vice versa, would that be illegal because of the attribute mismatch or allowed? If it is the latter, the call must have been UB.

Hmm, I think the issue happens with a call without noundef as well:

call void @hi1(nonnull %val, %val) ; let's assume that this is the only call

define void @hi(i8* %x, i8* %y) {
  use(%x, %y) ; this cannot be use(%x, %x)!
}

To do this replacement, nonnull at the call site should be dropped first.

Besides this, I think expanding the scope of being poison to the same variables makes optimizations like CSE hard. For example:

call void @hi1(<attr> %val, <attr2> %val2)

If CSE concludes that %val is %val2, it can remove %val2 and optimize it into:

call void @hi1(<attr> %val, <attr2> %val)

.. and this can unexpectedly introduce UB due to the synergy between <attr> and <attr2>. I guess fixing optimizations to consider attributes might be a bit costly.. :/

That is/was already the case, right? So, is the current behavior OK or not, potentially in light of making nonnull produce poison not UB.
I think it is/was OK, and, TBH I think it has to be. If we look at it scoped based it all makes sense (I think/hope).
On a practical note, you might not see all the call sites so "dropping first" doesn't work if you know that x == y from a local assume (in the hi example above).

I don't understand this sentence, I thought we could see all the call sites and assume that it was the only call of hi1.

If we assume this is the only call of `hi1` and we then do interprocedural transformations to replace the use of the first argument with the second or vice versa, would that be illegal because of the attribute mismatch or allowed?

If the attribute holds for the value in the scope, CSE is free to change val to val2 because the attributes did already conflict even if you used val and val2.
Do you see a problem when the attribute is scope based?

Before diving into further discussion, let's clarify my understanding about the semantics that you want:

  • Calling f(nonnull null, noundef null) is equivalent to f(nonnull noundef null, nonnull noundef null) because an attribute applies to all 'equivalent' values in the arguments. Is my understanding correct?
  • Similarly, calling f(nonnull null, null) is equivalent to f(poison, poison)?
  • What about f(nonnull poison, null)? Since poison can be folded into any value, we can make it f(nonnull null, null), which is again f(poison, poison).
aqjune added a comment.Mar 1 2021, 6:31 PM

Besides this, merging two assumes might require something. A notion of scope should be carefully defined in this case.

call void @llvm.assume(true) ["attr1"(p)]
call void @llvm.assume(true) ["attr2"(p)]
  =>
call void @llvm.assume(true) ["attr1"(p), "attr2"(p)] ; synergy between attributes may introduce UB

TBH, making things simple and introducing no special rule seems to be the best practice for avoiding possible miscompilations or glitches in spec I think.
I see that a similar thing is happening in relaxed concurrency and it is really hard to write at least medium-scale program correctly without relying on commonly-used patterns. :(

If the attribute holds for the value in the scope, CSE is free to change val to val2 because the attributes did already conflict even if you used val and val2.
Do you see a problem when the attribute is scope based?

Before diving into further discussion, let's clarify my understanding about the semantics that you want:

  • Calling f(nonnull null, noundef null) is equivalent to f(nonnull noundef null, nonnull noundef null) because an attribute applies to all 'equivalent' values in the arguments. Is my understanding correct?
  • Similarly, calling f(nonnull null, null) is equivalent to f(poison, poison)?
  • What about f(nonnull poison, null)? Since poison can be folded into any value, we can make it f(nonnull null, null), which is again f(poison, poison).

You need to start with the same value for this to make sense (to me), so these are what I want:

  • f(nonnull %p, noundef %p) is equivalent to f(nonnull noundef %p, nonnull noundef %p)
  • %p = %q; f(nonnull %p, noundef %q) is equivalent to f(nonnull noundef %p, nonnull noundef %q)
  • %p = null; f(nonnull %p, %p) is equivalent to f(poison, poison)

I don't understand how the values were set up in the last example.

[...]

I don't understand this sentence, I thought we could see all the call sites and assume that it was the only call of hi1.

My bad, I forgot we are still assuming this and therefore I interpreted your suggested to scrub the call site in a general setting (which doesn't work).

jdoerfert added a comment.EditedMar 1 2021, 6:58 PM

Besides this, merging two assumes might require something. A notion of scope should be carefully defined in this case.

assumes need scopes for this to make sense. the current ones have "point-scope" and you could not simply merge them, right.

call void @llvm.assume(true) ["attr1"(p)]
call void @llvm.assume(true) ["attr2"(p)]

=>

call void @llvm.assume(true) ["attr1"(p), "attr2"(p)] ; synergy between attributes may introduce UB

TBH, making things simple and introducing no special rule seems to be the best practice for avoiding possible miscompilations or glitches in spec I think.
I see that a similar thing is happening in relaxed concurrency and it is really hard to write at least medium-scale program correctly without relying on commonly-used patterns. :(

I think I missed your "simple" no-special rule suggestion. Could you repeat that or link it?

aqjune added a comment.Mar 1 2021, 7:52 PM
call void @llvm.assume(true) ["attr1"(p)]
call void @llvm.assume(true) ["attr2"(p)]
  =>
call void @llvm.assume(true) ["attr1"(p), "attr2"(p)] ; synergy between attributes may introduce UB

TBH, making things simple and introducing no special rule seems to be the best practice for avoiding possible miscompilations or glitches in spec I think.
I see that a similar thing is happening in relaxed concurrency and it is really hard to write at least medium-scale program correctly without relying on commonly-used patterns. :(

I think I missed your "simple" no-special rule suggestion. Could you repeat that or link it?

My suggestion is to keep the LangRef text of assume bundle as it is, and add nonnull/align to a bundle when creating assume only if it was paired with noundef.

call void @f(nonnull %p)         ; => llvm.assume(true) []
call void @f(nonnull noundef %p) ; => llvm.assume(true) ["nonnull"(%p)]

Well, it is still doing something (the lowering needs to check the existence of noundef), but I think the principle is already applied to the nonnull/align attributes; they can raise UB only if it is paired with noundef, as LangRef says.
I'm sorry if it sounded a bit aggressive :(

call void @llvm.assume(true) ["attr1"(p)]
call void @llvm.assume(true) ["attr2"(p)]
  =>
call void @llvm.assume(true) ["attr1"(p), "attr2"(p)] ; synergy between attributes may introduce UB

TBH, making things simple and introducing no special rule seems to be the best practice for avoiding possible miscompilations or glitches in spec I think.
I see that a similar thing is happening in relaxed concurrency and it is really hard to write at least medium-scale program correctly without relying on commonly-used patterns. :(

I think I missed your "simple" no-special rule suggestion. Could you repeat that or link it?

My suggestion is to keep the LangRef text of assume bundle as it is, and add nonnull/align to a bundle when creating assume only if it was paired with noundef.

call void @f(nonnull %p)         ; => llvm.assume(true) []
call void @f(nonnull noundef %p) ; => llvm.assume(true) ["nonnull"(%p)]

Well, it is still doing something (the lowering needs to check the existence of noundef), but I think the principle is already applied to the nonnull/align attributes; they can raise UB only if it is paired with noundef, as LangRef says.

I still like this, it seems like a natural next step, let's do that first.
We can revisit the scope discussion and I think will have to because of the GVN example, among other things.

I'm sorry if it sounded a bit aggressive :(

No worries.

aqjune added a comment.Mar 2 2021, 4:59 PM

Thank you! :)
I'll implement the corresponding semantics in Alive2 and see whether there is regression.

aqjune added a comment.Mar 4 2021, 1:57 AM

There was no regression in intraprocedural optimizations (and interprocedural optimizations that Alive2 could support)
But I think I need to look into Attributor's implementation as well; maybe I can have a look tomorrow

aqjune added a comment.Mar 8 2021, 6:22 PM

A fix in AssumeBundleBuilder to make it comply LangRef: D98228

BTW, I found that "align" can take two operands: "align"(i8* ptr, i64 a, i64 b) What is the meaning of the second index (b)?

Tyker added a subscriber: Tyker.EditedMar 9 2021, 1:41 AM

A fix in AssumeBundleBuilder to make it comply LangRef: D98228

BTW, I found that "align" can take two operands: "align"(i8* ptr, i64 a, i64 b) What is the meaning of the second index (b)?

the meaning of the second index is the offset of the alignment. so with "align"(i8* ptr, i64 16, i64 12), ptr is aligned on 4 but ptr + 4 is aligned on 16.
I introduced this to support __builtin_assume_aligned which has similar semantics.

A fix in AssumeBundleBuilder to make it comply LangRef: D98228

BTW, I found that "align" can take two operands: "align"(i8* ptr, i64 a, i64 b) What is the meaning of the second index (b)?

the meaning of the second index is the offset of the alignment. so with "align"(i8* ptr, i64 16, i64 12), ptr is aligned on 4 but ptr + 4 is aligned on 16.
I introduced this to support __builtin_assume_aligned which has similar semantics.

Hi, thanks for the info.

But I think an example in Transforms/AlignmentFromAssumptions/simple.ll conflicts with your definition. It has:

28 define i32 @foo2a(i32* nocapture %a) nounwind uwtable readonly {
29 entry:
30   tail call void @llvm.assume(i1 true) ["align"(i32* %a, i32 32, i32 28)]
31   %arrayidx = getelementptr inbounds i32, i32* %a, i64 -1
32   %0 = load i32, i32* %arrayidx, align 4
33   ret i32 %0
34 
35 ; CHECK-LABEL: @foo2a
36 ; CHECK: load i32, i32* {{[^,]+}}, align 32
37 ; CHECK: ret i32
38 }

"align"(i32* %a, i32 32, i32 28) means %a + 4 is 32-bytes aligned, IIUC. Then, %a - 4 cannot be 32-bytes aligned, is it?

From https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html , the definition you've explained seems to be correct because it is saying

void *x = __builtin_assume_aligned (arg, 32, 8);
means that the compiler can assume for x, set to arg, that (char *) x - 8 is 32-byte aligned.

Should we specify this in LangRef as well to make its definition explicit?

Tyker added a comment.Mar 15 2021, 8:20 AM

A fix in AssumeBundleBuilder to make it comply LangRef: D98228

BTW, I found that "align" can take two operands: "align"(i8* ptr, i64 a, i64 b) What is the meaning of the second index (b)?

the meaning of the second index is the offset of the alignment. so with "align"(i8* ptr, i64 16, i64 12), ptr is aligned on 4 but ptr + 4 is aligned on 16.
I introduced this to support __builtin_assume_aligned which has similar semantics.

Hi, thanks for the info.

But I think an example in Transforms/AlignmentFromAssumptions/simple.ll conflicts with your definition. It has:

28 define i32 @foo2a(i32* nocapture %a) nounwind uwtable readonly {
29 entry:
30   tail call void @llvm.assume(i1 true) ["align"(i32* %a, i32 32, i32 28)]
31   %arrayidx = getelementptr inbounds i32, i32* %a, i64 -1
32   %0 = load i32, i32* %arrayidx, align 4
33   ret i32 %0
34 
35 ; CHECK-LABEL: @foo2a
36 ; CHECK: load i32, i32* {{[^,]+}}, align 32
37 ; CHECK: ret i32
38 }

"align"(i32* %a, i32 32, i32 28) means %a + 4 is 32-bytes aligned, IIUC. Then, %a - 4 cannot be 32-bytes aligned, is it?

Yes, this looks like a bug.

From https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html , the definition you've explained seems to be correct because it is saying

void *x = __builtin_assume_aligned (arg, 32, 8);
means that the compiler can assume for x, set to arg, that (char *) x - 8 is 32-byte aligned.

Should we specify this in LangRef as well to make its definition explicit?

Yes