Page MenuHomePhabricator

[Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions.
AcceptedPublic

Authored by baziotis on Dec 28 2019, 8:00 AM.

Details

Summary

Query AAValueSimplify on pointers in memory accessing instructions to take advantage of the constant propagation (or any other value simplification) of such values.

Diff Detail

Event Timeline

baziotis created this revision.Dec 28 2019, 8:00 AM
Herald added a project: Restricted Project. · View Herald Transcript
uenoku added a comment.EditedDec 28 2019, 8:27 AM

There's one test case that is worrying: IPConstantProp/PR26044.ll. With this patch, a from undef becomes load from null and I don't see the reason.

I think this is no problem. It is because of on-demand creation. It is the first time to create AAValueSimplify to a pointer operand. The deduction is like this:

  1. The assumption which claims "for.cond1 is dead" is rejected because AAIsDead doesn't know there is UB.
  2. %e.2 is simplified to null because %e.2 can be null or undef.
  3. %e.2 is replaced with null in manifest

So once AAIsDead can get to interact with AAUB, the problem will be solved.
Please add FIXME now.

There's one test case that is worrying: IPConstantProp/PR26044.ll. With this patch, a from undef becomes load from null and I don't see the reason.

I think this is no problem. It is because of on-demand creation. It is the first time to create AAValueSimplify to a pointer operand. The deduction is like this:

  1. The assumption which claims "for.cond1 is dead" is rejected because AAIsDead doesn't know there is UB.
  2. %e.2 is simplified to null because %e.2 can be null or undef.
  3. %e.2 is replaced with null in manifest

    So once AAIsDead can get to interact with AAUB, the problem will be solved. Please add FIXME now.

Hmm, actually by looking again the code, I think that null is the correct value.
From looking at the IR, without thinking what Attributor does, it seems that the only valid value is null (because it comes from entry while the others are
unreachable).
Now, the more interesting part is actually looking what the Attributor does. If I followed the code correctly, previously we didn't query AAValueSimplify.
What happens if we do (and correct me if I'm wrong, it seems useful to me to know how it works) is that %e.2 is a floating value,
which calls genericValueTraversal(), which for the phi node, calls VisitValueCB with the 3 incoming values: null, undef and undef.
This in turn calls checkAndUpdate() which ignores UndefValue and finalizes on null (but if we had other different values, this:

if (AccumulatedSimplifiedValue.hasValue())
  return AccumulatedSimplifiedValue == QueryingValueSimplified;

in checkAndUpdate() would return false because of conflicting values, effectively indicating pessimistic fixpoint).

Now, other than that, I guess that with this:

So once AAIsDead can get to interact with AAUB, the problem will be solved.

you meant that when AAIsDead will interact with AAUB, the former will ignore the 2 phis in genericValueTraversal() since it will consider them dead.

Now, the more interesting part is actually looking what the Attributor does. If I followed the code correctly, previously we didn't query AAValueSimplify.
What happens if we do (and correct me if I'm wrong, it seems useful to me to know how it works) is that %e.2 is a floating value,
which calls genericValueTraversal(), which for the phi node, calls VisitValueCB with the 3 incoming values: null, undef and undef.
This in turn calls checkAndUpdate() which ignores UndefValue and finalizes on null (but if we had other different values, this:

if (AccumulatedSimplifiedValue.hasValue())
  return AccumulatedSimplifiedValue == QueryingValueSimplified;

in checkAndUpdate() would return false because of conflicting values, effectively indicating pessimistic fixpoint).

Now, other than that, I guess that with this:

So once AAIsDead can get to interact with AAUB, the problem will be solved.

you meant that when AAIsDead will interact with AAUB, the former will ignore the 2 phis in genericValueTraversal() since it will consider them dead.

Yes, exactly. Btw, my understating is that load inst from undef pointer causes UB even if "null-pointer-is-valid"="true" (https://llvm.org/docs/LangRef.html#pointeraliasing).
Then, I think @fn_no_null_opt can be optimized aggressively, is this correct? If so, please add FIXME.

Now, the more interesting part is actually looking what the Attributor does. If I followed the code correctly, previously we didn't query AAValueSimplify.
What happens if we do (and correct me if I'm wrong, it seems useful to me to know how it works) is that %e.2 is a floating value,
which calls genericValueTraversal(), which for the phi node, calls VisitValueCB with the 3 incoming values: null, undef and undef.
This in turn calls checkAndUpdate() which ignores UndefValue and finalizes on null (but if we had other different values, this:

if (AccumulatedSimplifiedValue.hasValue())
  return AccumulatedSimplifiedValue == QueryingValueSimplified;

in checkAndUpdate() would return false because of conflicting values, effectively indicating pessimistic fixpoint).

Now, other than that, I guess that with this:

So once AAIsDead can get to interact with AAUB, the problem will be solved.

you meant that when AAIsDead will interact with AAUB, the former will ignore the 2 phis in genericValueTraversal() since it will consider them dead.

Yes, exactly.

Great :)

Btw, my understating is that load inst from undef pointer causes UB even if "null-pointer-is-valid"="true" (https://llvm.org/docs/LangRef.html#pointeraliasing).
Then, I think @fn_no_null_opt can be optimized aggressively, is this correct? If so, please add FIXME.

Oh btw, I missed the code haha:

Hmm, actually by looking again the code, I think that null is the correct value.

It so isn't the correct value :P I thought the code was: phi = [entry, null], [for.cond1, undef], [for.cond1, undef] but it is: phi = [entry, undef], [for.cond1, null], [for.cond1, null]. That's why you mentioned the FIXME above. I'll add it.
And yes, what you mentioned is totally UB and the code is written in such a way as to handle it. But it doesn't, I'll add a FIXME for that as well.
It seems there's some problem in general with the propagation of values. For example, in undefined_behavior.ll test, if you check load_null_propagated() the null is propagated, but AAUB doesn't pick it up.

baziotis updated this revision to Diff 235485.EditedDec 28 2019, 11:01 AM
  • Added FIXMEs.

Edit: Ignore that, I upload the previous diff by mistake.

baziotis edited the summary of this revision. (Show Details)Dec 28 2019, 11:02 AM
baziotis updated this revision to Diff 235487.Dec 28 2019, 11:06 AM

Actually added FIXMEs.

jdoerfert added inline comments.Dec 28 2019, 2:32 PM
llvm/lib/Transforms/IPO/Attributor.cpp
2187

Where is stopOnUndefOrAssumed defined?

llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
9

This test is actually really broken. The function can never be executed w/o causing UB. We need to fix these tests to have some behavior.

baziotis marked 2 inline comments as done.Dec 28 2019, 2:53 PM
baziotis added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2187

Sorry, I should have mentioned in the summary that this diff is based on: https://reviews.llvm.org/D71799
That is already accepted and will be committed so I thought it would be good to not wait for it to actually be commited.

llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
9

Did I break anything? As far as I could understand, this was true before as well.
Or just a general comment? I personally think that now we have AAUB, it's ok to have "always UB" functions on tests that are supposed to test UB (like in the undefined_behavior.ll) but here it may be irrelevant to always have UB.

baziotis edited the summary of this revision. (Show Details)Dec 28 2019, 2:54 PM

(Don't wait for me to review/accept these even if I leave random comments once in a while.)

llvm/lib/Transforms/IPO/Attributor.cpp
2187

No worries, I just missed that part of D71799.

llvm/test/Transforms/Attributor/ArgumentPromotion/2008-07-02-array-indexing.ll
11–12

We should also repair this test. pass a valid pointer into callee, e.g., an argument.

llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
9

The test was broken, the new AAUB just exposed it (more and more). Since this is supposed to test AAValueSimplify, we should remove the UB. Can you replace the undef in the branch with some argument value (which you need to add), and the undef in the phi with %p. Then let the jump go to some exit block that returns. At least that way we have defined behavior until the Attributor gets smart enough to realize the endless loop has no atomic side effect and can be removed as UB as well ;)

(Don't wait for me to review/accept these even if I leave random comments once in a while.)

Ok, I'll wait for Hideto and Stefan, thanks for the comments though.

baziotis marked 2 inline comments as done.Dec 29 2019, 9:56 AM
baziotis added inline comments.
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-07-02-array-indexing.ll
11–12

Ok,yes. Btw, the nonnull and dereferenceable attributes for %A are wrong right? I guess these are the kind of checks for violations you have proposed that AAUB could do.

llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
9

If I understood correctly, the code will look like this:

entry:
  br label %if.end

for.cond1:
  br i1 %C, label %if.end, label %if.end

if.end:
  %e.2 = phi i32* [ %P, %entry ], [ null, %for.cond1 ], [ null, %for.cond1 ]
  %0 = load i32, i32* %e.2, align 4
  ...
  br label %exit
exit:
  ret void
}

where %C is an argument. If we do that, there's no endless loop and the %for.cond1 branch is unreachable (not because AAUB, but because there's no way to reach it).

uenoku added inline comments.Dec 30 2019, 8:01 AM
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-07-02-array-indexing.ll
11–12

Btw, the nonnull and dereferenceable attributes for %A are wrong right?

I think to mark nonnull and dereferenceable attributes for %A itself is not wrong.
(but anyway %A will be deleted with D68765 or additional patches)
I mean passing null to this function is UB too. So AAUB can prove

%X = call i32 @callee(i1 false, i32* null)

is UB.

baziotis marked an inline comment as done.Dec 30 2019, 8:49 AM
baziotis added inline comments.
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-07-02-array-indexing.ll
11–12

So, generally for attributes, I'm not sure when is the caller responsible for it to hold or the "marker" (or both).
What I mean is that the way I see it, in this example, there are 2 cases (in the general case, replace "parameter" with "value that can be attributed"):

  1. If the caller is responsible, then I can mark any attributes in the parameter (e.g. nonnull) and whoever calls this function is responsible for the attributes to hold (e.g. not pass a null). Otherwise, it is UB.
  2. If the marker is responsible, then whoever marks a parameter (e.g. nonnull) is responsible to validate that anyone who

calls this function does not pass a null parameter.

The 1) makes more sense since 2) is practically impossible if the function is external. But 2) isn't really what the Attributor does?
(e.g. the Attributor tries to be sure that an argument is dereferenceable to mark it as such).

uenoku added inline comments.Dec 30 2019, 9:19 AM
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-07-02-array-indexing.ll
11–12

If the caller is responsible, then I can mark any attributes in the parameter (e.g. nonnull) and whoever calls this function is responsible for the attributes to hold (e.g. not pass a null). Otherwise, it is UB.
If the marker is responsible, then whoever marks a parameter (e.g. nonnull) is responsible to validate that anyone who calls this function does not pass a null parameter.
The 1) makes more sense since 2) is practically impossible if the function is external. But 2) isn't really what the Attributor does?

Yes, almost all the attributes are using only 2) but some (ex. nonnull, align, dereferenceable) are doing deduction in both ways. In this case, %A is known as nonnull because %A is loaded at an entry point.

If the function is an external function, Attributor gives up 2). (please look at checkForAllCallsites implementation)

baziotis marked an inline comment as done.Dec 30 2019, 10:10 AM
baziotis added inline comments.
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-07-02-array-indexing.ll
11–12

Aha, got it, thanks!

baziotis updated this revision to Diff 235806.Jan 1 2020, 5:08 PM
  • Updated tests

Note that I removed the second test in IPConstantProp/PR26044.ll since as far as I could tell, it is based on having null in a load.
Since this test tests value simplification and not UB (which is the reason why the first test was changed as well), probably this would not
be very useful.

baziotis marked an inline comment as done.Jan 1 2020, 5:12 PM
baziotis added inline comments.
llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
9

Then let the jump go to some exit block that returns

I had forgotten about this. Sorry, just yesterday I learned about the terminology of loops. So I didn't get that "exit block" is a characteristic term that makes clear that you were referring to the "else" jump on the conditional branch and not the jump on the latch.
It should be ok now.

jdoerfert added inline comments.Jan 2 2020, 9:51 AM
llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
88

Please do not delete the tests but "repair" them if possible. Replace undef above with argument values such that we could still propagate the load null, which is valid in @fn_no_null_opt, into @fn0.

baziotis marked an inline comment as done.Jan 2 2020, 3:30 PM
baziotis added inline comments.
llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll
88

Ah right. Let me make the "null-pointer-is-valid"="true" more obvious because I keep forgetting it.

baziotis updated this revision to Diff 235960.Jan 2 2020, 3:42 PM
  • Repaired test case.

Anything else needed for that?

jdoerfert accepted this revision.Tue, Feb 11, 2:38 PM

LGTM, two things before we commit though:

  1. update the commit message
  2. add a test that checks the functionality. the test changes in this patch "repair" existing tests to not expose unwanted UB but we want to have at least one test that exhibits UB and which gets exploited due to this patch.
This revision is now accepted and ready to land.Tue, Feb 11, 2:38 PM
baziotis updated this revision to Diff 244209.Wed, Feb 12, 9:35 AM
baziotis retitled this revision from [Attributor] AAUndefinedBehavior: AAValueSimplify in memory accessing instructions. to [Attributor] AAUndefinedBehavior: Use AAValueSimplify.
baziotis edited the summary of this revision. (Show Details)
  • Update commit message and test cases

in ArgumentPromotion/2008-07-02-array-indexing.ll, there was a weird align value that was only in the CHECK directives so it didn't seem it was coming from somewhere. I had to change it to make it pass. Please verify that it is not needed.

baziotis added a comment.EditedWed, Feb 12, 9:36 AM
  1. add a test that checks the functionality. the test changes in this patch "repair" existing tests to not expose unwanted UB but we want to have at least one test that exhibits UB and which gets exploited due to this patch.

Something more complicated than load_null_propagated() and / or cond_br_on_undef* functions (in undefined_behavior.ll testcase) ?

  • Update commit message and test cases

    in ArgumentPromotion/2008-07-02-array-indexing.ll, there was a weird align value that was only in the CHECK directives so it didn't seem it was coming from somewhere. I had to change it to make it pass. Please verify that it is not needed.

The align was "derived" from a null pointer, which has every alignment. Since you made the UB go away by using an argument instead of loading from null, the alignment is no longer deduced. All as expected :)

  1. add a test that checks the functionality. the test changes in this patch "repair" existing tests to not expose unwanted UB but we want to have at least one test that exhibits UB and which gets exploited due to this patch.

Something more complicated than load_null_propagated() and / or cond_br_on_undef* functions (in undefined_behavior.ll testcase) ?

Nothing complicated. Along those lines but as far as I can tell this patch does not include changes to these tests, correct?

  • Update commit message and test cases

    in ArgumentPromotion/2008-07-02-array-indexing.ll, there was a weird align value that was only in the CHECK directives so it didn't seem it was coming from somewhere. I had to change it to make it pass. Please verify that it is not needed.

The align was "derived" from a null pointer, which has every alignment. Since you made the UB go away by using an argument instead of loading from null, the alignment is no longer deduced. All as expected :)

Ok and so it put a random value, got it :)

  1. add a test that checks the functionality. the test changes in this patch "repair" existing tests to not expose unwanted UB but we want to have at least one test that exhibits UB and which gets exploited due to this patch.

Something more complicated than load_null_propagated() and / or cond_br_on_undef* functions (in undefined_behavior.ll testcase) ?

Nothing complicated. Along those lines but as far as I can tell this patch does not include changes to these tests, correct?

Correct. TBH, it's been some time since I saw this that for example even I forgot that load_null_propagated() was not introduced in this patch (although it still puzzles me how it worked before this patch).
I'll add more tests.

baziotis updated this revision to Diff 244306.Wed, Feb 12, 4:56 PM
baziotis retitled this revision from [Attributor] AAUndefinedBehavior: Use AAValueSimplify to [Attributor] AAUndefinedBehavior: Use AAValueSimplify in memory accessing instructions..
baziotis edited the summary of this revision. (Show Details)
  • Added tests
  • Added tests

All the tests have FIXMEs, right? Can you explain why they don't work yet? We also need tests that didn't work before but now, maybe just copies of the one you repaired but without the "repair" part.

  • Added tests

All the tests have FIXMEs, right? Can you explain why they don't work yet?

Yes. For most tests the reason is that AAValueSimplify doesn't give a known value. In other words, in stopOnUndefOrAssumed(), we don't get past the first if (if (!ValueSimplifyAA.isKnown())).

Seeing that again though, returning from this if effectively means that the instruction remains assumed UB.
The whole procedure ends with the instruction still assumed UB. So, doesn't that fixpoint to known UB actually ?

But then, check this:

define internal i32* @ret_null(i32* %A) {
  ret i32* %A
}

define void @load_null_propagated(i32* %A) {
  %ptr = call i32* @ret_null(i32* %A)
  %a = load i32, i32* %ptr
  ret void
}

The output is (same with AAUB disabled):

define void @load_null_propagated(i32* nocapture nofree readonly %A) #0 {
  %a = load i32, i32* undef
  ret void
}

First of all, even if what I said above is correct, AAValueSimplify still gives us no value for the pointer which keeps an actually non-UB instruction to assumed till the end.
But then second, isn't that output wrong in general ?

We also need tests that didn't work before but now, maybe just copies of the one you repaired but without the "repair" part.

Hmm, yes, that should be feasible to do in 2008-07-02-array-indexing.ll and PR26044.ll. Guessing what else this patch could "repair" / improve and making new tests is more challenging.

  • Added tests

All the tests have FIXMEs, right? Can you explain why they don't work yet?

Yes. For most tests the reason is that AAValueSimplify doesn't give a known value. In other words, in stopOnUndefOrAssumed(), we don't get past the first if (if (!ValueSimplifyAA.isKnown())).

Seeing that again though, returning from this if effectively means that the instruction remains assumed UB.
The whole procedure ends with the instruction still assumed UB. So, doesn't that fixpoint to known UB actually ?

But then, check this:

define internal i32* @ret_null(i32* %A) {
  ret i32* %A
}

define void @load_null_propagated(i32* %A) {
  %ptr = call i32* @ret_null(i32* %A)
  %a = load i32, i32* %ptr
  ret void
}

The output is (same with AAUB disabled):

define void @load_null_propagated(i32* nocapture nofree readonly %A) #0 {
  %a = load i32, i32* undef
  ret void
}

First of all, even if what I said above is correct, AAValueSimplify still gives us no value for the pointer which keeps an actually non-UB instruction to assumed till the end.
But then second, isn't that output wrong in general ?

I think this is a bad artifact of our current "code deletion" at the end of the Attributor run. Make the load live and it will not happen, I mean, the load in the example above can be removed either way.

define internal i32* @ret_null(i32* %A) {
   ret i32* %A
 }
 
 define void @load_null_propagated(i32* %A) {
   %ptr = call i32* @ret_null(i32* %A)
   %a = load i32, i32* %ptr
   ret void
 }

I wanted to confirm and I noticed that in-tree we actually do not replace with undef, did you rebase your patch recently?

We also need tests that didn't work before but now, maybe just copies of the one you repaired but without the "repair" part.

Hmm, yes, that should be feasible to do in 2008-07-02-array-indexing.ll and PR26044.ll. Guessing what else this patch could "repair" / improve and making new tests is more challenging.

Assuming this patch has some effect, we need to have a test for it. Then we merge and make bigger changes.

baziotis added a comment.EditedFri, Feb 14, 9:17 AM
  • Added tests

All the tests have FIXMEs, right? Can you explain why they don't work yet?

Yes. For most tests the reason is that AAValueSimplify doesn't give a known value. In other words, in stopOnUndefOrAssumed(), we don't get past the first if (if (!ValueSimplifyAA.isKnown())).

Seeing that again though, returning from this if effectively means that the instruction remains assumed UB.
The whole procedure ends with the instruction still assumed UB. So, doesn't that fixpoint to known UB actually ?

But then, check this:

define internal i32* @ret_null(i32* %A) {
  ret i32* %A
}

define void @load_null_propagated(i32* %A) {
  %ptr = call i32* @ret_null(i32* %A)
  %a = load i32, i32* %ptr
  ret void
}

The output is (same with AAUB disabled):

define void @load_null_propagated(i32* nocapture nofree readonly %A) #0 {
  %a = load i32, i32* undef
  ret void
}

First of all, even if what I said above is correct, AAValueSimplify still gives us no value for the pointer which keeps an actually non-UB instruction to assumed till the end.
But then second, isn't that output wrong in general ?

I think this is a bad artifact of our current "code deletion" at the end of the Attributor run. Make the load live and it will not happen, I mean, the load in the example above can be removed either way.

You mean because it's unused anyway? Indeed if we return %a for example, it's not replaced with undef.

define internal i32* @ret_null(i32* %A) {
   ret i32* %A
 }
 
 define void @load_null_propagated(i32* %A) {
   %ptr = call i32* @ret_null(i32* %A)
   %a = load i32, i32* %ptr
   ret void
 }

I wanted to confirm and I noticed that in-tree we actually do not replace with undef, did you rebase your patch recently?

Not too long ago, about 3-4 days ago but now that I rebased again, it seems it acts differently. I'll update the diff.

Edit: And btw sorry for not following the Attributor closely. Time is limited right now,
I hope I'll have more time in the future.

We also need tests that didn't work before but now, maybe just copies of the one you repaired but without the "repair" part.

Hmm, yes, that should be feasible to do in 2008-07-02-array-indexing.ll and PR26044.ll. Guessing what else this patch could "repair" / improve and making new tests is more challenging.

Assuming this patch has some effect, we need to have a test for it. Then we merge and make bigger changes.

Yes, I think new tests test the new things. I'll update the repaired as well and then we see if it needs anything more.

baziotis updated this revision to Diff 244694.Fri, Feb 14, 9:42 AM
  • Rebased

Now tests are a lot better!

(I will follow with copies of repaired tests)

xbolva00 added a subscriber: xbolva00.EditedFri, Feb 14, 12:44 PM

I have a similar case how to exploit UB to simplify code:

int process(char *p) __attribute__((nonnull));


void doit(bool b, char *d) {
    char *p = 0;
    if (b)
        p = d;
    process(p);
}

https://godbolt.org/z/eYcApm

In this case, it is invalid to call process with null pointer since args are nonnull, so we can remove branch and call process(d) directly.

I have a similar case how to exploit UB to simplify code:

int process(char *p) __attribute__((nonnull));


void doit(bool b, char *d) {
    char *p = 0;
    if (b)
        p = d;
    process(p);
}

https://godbolt.org/z/eYcApm

In this case, it is invalid to call process with null pointer since args are nonnull, so we can remove branch and call process(d) directly.

Thanks for the proposal! At first glance, deleting the branch is not straightforward and may not make a lot of sense. Reaching the call, you have a phi node basically saying:

  • If you got into the branch, the value is d.
  • If not, the value is p (which with constant propagation, let's say null).

Deleting the branch first of all seems to require somehow going "backwards", tracking where this (or these) value came from. Second, I can't find a reasoning on how to generalize this (except since we have UB, do whatever)
because the previous code is not invalid, only the call.

That said, personally I think it's a very good idea to check if null arguments are passed to nonnull parameters and consider that UB. Then, we can make the call unreachable.

That said, personally I think it's a very good idea to check if null arguments are passed to nonnull parameters and consider that UB. Then, we can make the call unreachable.

Yeah.

One last nit with one of the tests, then I'll commit this.

I have a similar case how to exploit UB to simplify code:

int process(char *p) __attribute__((nonnull));


void doit(bool b, char *d) {
    char *p = 0;
    if (b)
        p = d;
    process(p);
}

https://godbolt.org/z/eYcApm

In this case, it is invalid to call process with null pointer since args are nonnull, so we can remove branch and call process(d) directly.

Nit: In the godbold example you don't even need the __attribute__((nonnull)) for this, the access is sufficient ;)

Thanks for the proposal! At first glance, deleting the branch is not straightforward and may not make a lot of sense. Reaching the call, you have a phi node basically saying:

  • If you got into the branch, the value is d.
  • If not, the value is p (which with constant propagation, let's say null).

This is where AAIsDead needs to talk to AAUnreachable at some point but we have simpler cases to tackle first.

Deleting the branch first of all seems to require somehow going "backwards", tracking where this (or these) value came from. Second, I can't find a reasoning on how to generalize this (except since we have UB, do whatever)
because the previous code is not invalid, only the call.

I was always hoping for backwards propagation of UB. Let's start with propagating unreachable backwards. There is already a TODO in the code btw:
// TODO: look for (assumed) UB to backwards propagate "deadness".

A good first step would be to check the MustBeExecutedContext either backwards from known UB, e.g. hitting an unreachable, or forward after a control dependence change (e.g, after a conditional branch).
The backwards propagation is not cleaned up and integrated yet (for MustBeExecutedContext, it's somewhere in a review though).
One could maybe work on that or go with the forward approach. This should be done in AAIsDeadFunction.

That said, personally I think it's a very good idea to check if null arguments are passed to nonnull parameters and consider that UB. Then, we can make the call unreachable.

I generally agree but we have to be a bit careful. People don't like "obviously harmless" UB to be exploited, e.g., passing null to a nonnull argument that is unused should not cause an unreachable

llvm/test/Transforms/Attributor/undefined_behavior.ll
91

You have to return the value or sth. As it is, the call has no side-effects and is deleted either way.

One last nit with one of the tests, then I'll commit this.

Ok thanks, I'll address it. Looking at the repaired tests, I can't see something that this patch exposed
that is not tested in undefined_behavior.ll test.

I have a similar case how to exploit UB to simplify code:

int process(char *p) __attribute__((nonnull));


void doit(bool b, char *d) {
    char *p = 0;
    if (b)
        p = d;
    process(p);
}

https://godbolt.org/z/eYcApm

In this case, it is invalid to call process with null pointer since args are nonnull, so we can remove branch and call process(d) directly.

Nit: In the godbold example you don't even need the __attribute__((nonnull)) for this, the access is sufficient ;)

May I add: You don't need it because of the Attributor (which puts the nonnull since there is an access).

Thanks for the proposal! At first glance, deleting the branch is not straightforward and may not make a lot of sense. Reaching the call, you have a phi node basically saying:

  • If you got into the branch, the value is d.
  • If not, the value is p (which with constant propagation, let's say null).

This is where AAIsDead needs to talk to AAUnreachable at some point but we have simpler cases to tackle first.

Deleting the branch first of all seems to require somehow going "backwards", tracking where this (or these) value came from. Second, I can't find a reasoning on how to generalize this (except since we have UB, do whatever)
because the previous code is not invalid, only the call.

I was always hoping for backwards propagation of UB. Let's start with propagating unreachable backwards. There is already a TODO in the code btw:
// TODO: look for (assumed) UB to backwards propagate "deadness".

A good first step would be to check the MustBeExecutedContext either backwards from known UB, e.g. hitting an unreachable, or forward after a control dependence change (e.g, after a conditional branch).
The backwards propagation is not cleaned up and integrated yet (for MustBeExecutedContext, it's somewhere in a review though).
One could maybe work on that or go with the forward approach. This should be done in AAIsDeadFunction.

It seems that what you're describing is similar to: https://reviews.llvm.org/D71974 when checking for known UB.

That said, personally I think it's a very good idea to check if null arguments are passed to nonnull parameters and consider that UB. Then, we can make the call unreachable.

I generally agree but we have to be a bit careful. People don't like "obviously harmless" UB to be exploited, e.g., passing null to a nonnull argument that is unused should not cause an unreachable

Right, I hadn't thought of that.

baziotis updated this revision to Diff 244791.Fri, Feb 14, 4:36 PM

Fixed test which actually exposed a FIXME. Again for the same reason, it doesn't seem to get a known value from AAValueSimplify.
Should I go ahead and change to unreachable the assumed instructions as well? Meaning in manifest(), after the updates have finished.

Fixed test which actually exposed a FIXME. Again for the same reason, it doesn't seem to get a known value from AAValueSimplify.
Should I go ahead and change to unreachable the assumed instructions as well? Meaning in manifest(), after the updates have finished.

Yes, I think something like that makes sense. Let's do that in a follow up though. This looks good now and I'll commit it once I get the chance.

Fixed test which actually exposed a FIXME. Again for the same reason, it doesn't seem to get a known value from AAValueSimplify.
Should I go ahead and change to unreachable the assumed instructions as well? Meaning in manifest(), after the updates have finished.

Yes, I think something like that makes sense. Let's do that in a follow up though. This looks good now and I'll commit it once I get the chance.

Yes, ok, thanks!