Page MenuHomePhabricator

[IPSCCP] Fix a bug that the "returned" attribute is not cleared when function is optimized to return undef
ClosedPublic

Authored by congzhe on Jul 20 2020, 10:00 PM.

Details

Summary

In IPSCCP when a function is optimized to return undef, it should clear the returned attribute for all its input arguments
and its corresponding call sites.

The bug is exposed when the value of an input argument of the function is assigned to a physical register and
because of the argument having a returned attribute, the value of this physical register will continue to be used
as the function return value right after the call instruction returns, even if the value that this register holds may
be clobbered during the function call. This potentially results in incorrect values being used afterwards.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
congzhe created this object with edit policy "Administrators".Jul 20 2020, 10:00 PM
nikic added a subscriber: nikic.Jul 21 2020, 2:39 AM

Could you review this patch please? Thank you! @nikic @davide @efriedma

Florian, can you take a look?

Florian, can you take a look?

On Tue, Jul 28, 2020 at 10:35 PM Florian Hahn via llvm-commits <llvm-commits@lists.llvm.org> wrote:

On Jul 28, 2020, at 20:32, Congzhe Cao via Phabricator <reviews@reviews.llvm.org> wrote:

congzhe added a comment.

Could you review this patch please? Thank you! @nikic @davide @efriedma

As I mentioned already, I have some comments in phabricator, but cannot submit them because "You do not have permission to edit this object.”

FWIW it is not common to lock down reviews to require Admin permissions.


llvm-commits mailing list
llvm-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

congzhe changed the edit policy from "Administrators" to "All Users".Jul 28 2020, 12:40 PM
fhahn added a subscriber: fhahn.Jul 28 2020, 12:41 PM

Thanks for the patch! Some comments inline.

llvm/lib/Transforms/Scalar/SCCP.cpp
2121

A single function can have multiple returns to 'zap' and we would repeatedly checked the same function unnecessarily.

It might be better to remove the returned argument once for each function we found returns to zap. This could either be done by checking if findReturnsToZap found returns to zap or by collecting a set of functions for which zapped returns and then remove the Returned attribute for their arguments.

llvm/test/Transforms/SCCP/ipsccp-clear-returned.ll
12

Using a regular expression here looks a bit odd. Maybe ; CHECK: call {{.*}} @func_return_undef or maybe even better spell out the full call? Also it might be good to return the result value ret i32 %call and check if it gets replaced with 1.

Florian, can you take a look?

On Tue, Jul 28, 2020 at 10:35 PM Florian Hahn via llvm-commits <llvm-commits@lists.llvm.org> wrote:

On Jul 28, 2020, at 20:32, Congzhe Cao via Phabricator <reviews@reviews.llvm.org> wrote:

congzhe added a comment.

Could you review this patch please? Thank you! @nikic @davide @efriedma

As I mentioned already, I have some comments in phabricator, but cannot submit them because "You do not have permission to edit this object.”

FWIW it is not common to lock down reviews to require Admin permissions.


llvm-commits mailing list
llvm-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

My apologies, I've updated permissions.

I'm not sure I understand the motivation. My problem is that if we replace the return values with undef, it should mean there is no use of the returned value of the function live anymore. What am I missing? Maybe provide the motivating example as a test case?

llvm/lib/Transforms/Scalar/SCCP.cpp
2121

call sites can have the attribute too.

I'm not sure I understand the motivation. My problem is that if we replace the return values with undef, it should mean there is no use of the returned value of the function live anymore. What am I missing? Maybe provide the motivating example as a test case?

We use "returned" in codegen even if the value has no uses; see https://reviews.llvm.org/D64986 .

I'm not sure I understand the motivation. My problem is that if we replace the return values with undef, it should mean there is no use of the returned value of the function live anymore. What am I missing? Maybe provide the motivating example as a test case?

We use "returned" in codegen even if the value has no uses; see https://reviews.llvm.org/D64986 .

Argh, ... I'm certain this is a bad idea and we are just hiding the problem one level deeper here. I still believe violation of the attributes means the value is poison, not immediate UB. With that semantic the codegen trick is not valid in general but the IPSCCP transformation is. As I argued before, IPSCCP is only one reason things can become undef. FWIW, I am actually expecting a patch + RFC on the attribute semantic is poison not UB stuff "soonish". If you feel this is the right way for now, I will not stop you. If you want me to come up with other examples where the codegen logic will break, let me know.

The current definition of "returned" in LangRef is unclear, yes.

In terms of what we actually want, the "must be equal or else instant UB" variation seems more useful than the "must be equal or poison" variation. With "must be equal or poison", basically the only legal optimization is replacing the result with the argument. The only reason I can think of we wouldn't want the instant UB is if it interacts badly with some significant number of optimizations. I'm not coming up with anything it could interact badly with off the top of my head, though, and any transform that did have an issue would also interact badly with noundef.

The current definition of "returned" in LangRef is unclear, yes.

In terms of what we actually want, the "must be equal or else instant UB" variation seems more useful than the "must be equal or poison" variation. With "must be equal or poison", basically the only legal optimization is replacing the result with the argument.

I always thought that was the purpose. Could you elaborate what else we want to do?

The only reason I can think of we wouldn't want the instant UB is if it interacts badly with some significant number of optimizations. I'm not coming up with anything it could interact badly with off the top of my head, though, and any transform that did have an issue would also interact badly with noundef.

I agree that it would interact badly with noundef but I was always thinking that would be less of an issue, maybe I'm wrong though.

When it comes to optimizations, I think this shows how problematic the UB semantic is. The codegen interpretation is the problem not IPSCCP (IMHO). Even if you disagree, I doubt this will fix it. Without running it I would suspect https://godbolt.org/z/rG48nz to have at least one returned argument in a ret undef function. @congzhe could you try this?

The current definition of "returned" in LangRef is unclear, yes.

In terms of what we actually want, the "must be equal or else instant UB" variation seems more useful than the "must be equal or poison" variation. With "must be equal or poison", basically the only legal optimization is replacing the result with the argument.

I always thought that was the purpose. Could you elaborate what else we want to do?

Would poison limit the way we can use other information for the returned value, e.g. range information?

For example, consider the (arguably a bit contrived) code below. We know that %limit is [0, 2), not poison, and that it is UB for @foo to return anything other than %limit. It should be legal to replace %res with %r.f. https://alive2.llvm.org/ce/z/NrdV6x

But can we do the same transform if @foo returns poison instead of immediate UB on an invalid return value? In case it returned poison, %r.f would be any i4, while in the original function it would be in the range [0, 2).

declare i4 @foo(i4 returned %arg)

define i4 @src(i4 %x) {
  %x.f = freeze i4 %x
  %limit = and i4 %x.f, 1
  %r = call i4 @foo(i4 %limit)
  %r.f = freeze i4 %r
  %res = and i4 %r.f, 1
  ret i4 %res
}
congzhe added a comment.EditedJul 29 2020, 1:43 PM

The current definition of "returned" in LangRef is unclear, yes.

In terms of what we actually want, the "must be equal or else instant UB" variation seems more useful than the "must be equal or poison" variation. With "must be equal or poison", basically the only legal optimization is replacing the result with the argument.

I always thought that was the purpose. Could you elaborate what else we want to do?

The only reason I can think of we wouldn't want the instant UB is if it interacts badly with some significant number of optimizations. I'm not coming up with anything it could interact badly with off the top of my head, though, and any transform that did have an issue would also interact badly with noundef.

I agree that it would interact badly with noundef but I was always thinking that would be less of an issue, maybe I'm wrong though.

When it comes to optimizations, I think this shows how problematic the UB semantic is. The codegen interpretation is the problem not IPSCCP (IMHO). Even if you disagree, I doubt this will fix it. Without running it I would suspect https://godbolt.org/z/rG48nz to have at least one returned argument in a ret undef function. @congzhe could you try this?

Thanks for the comment, for the IR provided in https://godbolt.org/z/rG48nz, with this patch the output after "opt -ipsccp" is

define i32 @main() {
  %call = call i32 @func_return_undef_outer(i32 1)
  ret i32 0
}

define internal i32 @func_return_undef_inner(i32 %arg) {
  ret i32 undef
}

define internal i32 @func_return_undef_outer(i32 %arg) {
  %call = call i32 @func_return_undef_inner(i32 1)
  ret i32 undef
}

The current definition of "returned" in LangRef is unclear, yes.

In terms of what we actually want, the "must be equal or else instant UB" variation seems more useful than the "must be equal or poison" variation. With "must be equal or poison", basically the only legal optimization is replacing the result with the argument.

I always thought that was the purpose. Could you elaborate what else we want to do?

Would poison limit the way we can use other information for the returned value, e.g. range information?

For example, consider the (arguably a bit contrived) code below. We know that %limit is [0, 2), not poison, and that it is UB for @foo to return anything other than %limit. It should be legal to replace %res with %r.f. https://alive2.llvm.org/ce/z/NrdV6x

But can we do the same transform if @foo returns poison instead of immediate UB on an invalid return value? In case it returned poison, %r.f would be any i4, while in the original function it would be in the range [0, 2).

declare i4 @foo(i4 returned %arg)

define i4 @src(i4 %x) {
  %x.f = freeze i4 %x
  %limit = and i4 %x.f, 1
  %r = call i4 @foo(i4 %limit)
  %r.f = freeze i4 %r
  %res = and i4 %r.f, 1
  ret i4 %res
}

Right. And if you wanted to say, this has to be returned or it is UB, you simply add noundef as an attribute to the return value. The poison proposal doesn't limit us in any way due to noundef.

Thanks for the comment, for the IR provided in https://godbolt.org/z/rG48nz, with this patch the output after "opt -ipsccp" is

Yes, thanks for checking.

I guess if we fix up every pass that modifies returned instructions we can do this. The Attributor is probably broken too.
That said, I still believe there is is bandaging the underlying problem. I don't have a really good example handy right now though.

congzhe added a comment.EditedJul 30 2020, 1:00 PM

I'm not sure I understand the motivation. My problem is that if we replace the return values with undef, it should mean there is no use of the returned value of the function live anymore. What am I missing? Maybe provide the motivating example as a test case?

We use "returned" in codegen even if the value has no uses; see https://reviews.llvm.org/D64986 .

Yes that might be a concern (IMHO). Even if the value has no uses, there might be other values aliasing with it, causing “uses” of the return value.

Just adding more background information about the bug. It is exposed in the following piece of pseudocode (a simplified version of the whole testing code, which is a bit complicated):

function_x()

function_y()

int* a, b  // a and b are detected to be alias 

int main {
      a = function_y();
      function_x(b);
}

In IPSCCP LLVM determines to zap function_y() to return undef, and since the first argument of function_y() has the returned attribute, during register allocation the regmask for function_y indicates w0 is preserved.

In AArch64 assembly after bl function_y instruction, it keeps using w0 as the return value of function_y() (i.e., a). w0 will continue to be passed to function_x() as the value of b . However, inside function_y() it does not mov the return value to w0 and w0 is just clobbered and therefore contains dirty values. Hence what gets passed to function_x() is incorrect, making the rest of program execute incorrectly.

Clearing the returned attribute in this patch fixes this issue. With the patch w0 now contains the correct value during the call of function_y().

Hope it helps -

FWIW, I don't try to block this. The call site attribute comment is not addressed but other than that this patch "makes sense" assuming we keep the current semantics.

FWIW, I don't try to block this. The call site attribute comment is not addressed but other than that this patch "makes sense" assuming we keep the current semantics.

Thanks for the comment, I will address those comments asap.

Regarding the semantics of the "returned" attribute: I am very interested in your above-mentioned discussions on the semantics of the "returned" attribute, to be honest however, I did not quite follow and understand them. Would you please clarify them a little bit more, like what do you think should be the correct and incorrect semantics of "returned" ? Thank you!

Regarding the semantics of the "returned" attribute: I am very interested in your above-mentioned discussions on the semantics of the "returned" attribute, to be honest however, I did not quite follow and understand them. Would you please clarify them a little bit more, like what do you think should be the correct and incorrect semantics of "returned" ? Thank you!

The question is if "violating" returned is UB or something else. I generally think attribute violations should not result in UB (in most cases). My proposal is that you get the argument or poison, though, for now we stick to the former and modify the IPO passes that replace the return values.

congzhe updated this revision to Diff 282245.Jul 31 2020, 9:22 AM

comments addressed:

  1. keep a set of zapped functions to avoid removing the attribute for a function more than one times, since a single function can have multiple returns to zap.
  1. also remove the returned attribte for call sites that correspond to the zapped functions
  1. updated the test file to reflect the changes
congzhe updated this revision to Diff 282339.Jul 31 2020, 3:43 PM
congzhe added inline comments.Aug 5 2020, 8:53 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
2121

Thanks, added code that removes returned attribute for call sites

2121

Thanks, now keep a set of functions whose returns are zapped, and work on functions in the set afterwards

llvm/test/Transforms/SCCP/ipsccp-clear-returned.ll
12

Thank you, updated accordingly.

jdoerfert added inline comments.Aug 5 2020, 8:36 PM
llvm/lib/Transforms/Scalar/SCCP.cpp
33

Funnily, if this branch would hit we have a problem. I mean, there is a use that could have an annotation like returned but we did make it UB now. Not that I think this branch should ever be taken anyway. I'd propose an assertion, @fhahn @efriedma WDYT ?

36

Style: No braces, Arg and I would not use auto but that is probably OK.

congzhe added inline comments.Aug 6 2020, 6:07 PM
llvm/lib/Transforms/Scalar/SCCP.cpp
33

Thank you, I guess I could replace the branch with something along the following line?
assert(CB && "Use of zapped functions should be valid direct calls!");

jdoerfert added inline comments.Aug 6 2020, 7:21 PM
llvm/lib/Transforms/Scalar/SCCP.cpp
33

I think that would be better, yes.

congzhe updated this revision to Diff 283815.Aug 6 2020, 11:09 PM

Comments addressed:

replaced the if branch with assert(); replaced auto with Use in the for loop

congzhe added inline comments.Aug 6 2020, 11:10 PM
llvm/lib/Transforms/Scalar/SCCP.cpp
33

Thanks, updated accordingly.

36

Updated accordingly

jdoerfert accepted this revision.Aug 7 2020, 8:25 AM

This diff is only against the last version, squash the commits locally before merging them into master. LGTM, apologies for the long time this took.

This revision is now accepted and ready to land.Aug 7 2020, 8:25 AM
congzhe added inline comments.Aug 7 2020, 8:56 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
33

Adding this assertion fails one test case: llvm/test/Transforms/SCCP/indirectbr.ll

This is because functions in FuncZappedReturn are functions that are zapped, but they may not necessarily have returned attribute for its arguments. Therefore CB can actually be null and hence fails assertion.

I can either revert back to the previous version (without assert), or I can add some code to make sure FuncZappedReturn contains functions that are zapped AND have returned attribute for its arguments.

PS. the specific test case that fails is the following:

; CHECK-LABEL: define internal i32 @indbrtest5(
; CHECK: ret i32 undef
define internal i32 @indbrtest5(i1 %c) {
entry:
  br i1 %c, label %bb1, label %bb2

bb1:
  br label %branch.block


bb2:
  br label %branch.block

branch.block:
  %addr = phi i8* [blockaddress(@indbrtest5, %target1), %bb1], [blockaddress(@indbrtest5, %target2), %bb2]
  indirectbr i8* %addr, [label %target1, label %target2]

target1:
  br label %target2

target2:
  ret i32 10
}


define i32 @indbrtest5_callee(i1 %c) {
; CHECK-LABEL: define i32 @indbrtest5_callee(
; CHECK-NEXT:    %r = call i32 @indbrtest5(i1 %c)
; CHECK-NEXT:    ret i32 10
  %r = call i32 @indbrtest5(i1 %c)
  ret i32 %r
}
fhahn added inline comments.Aug 7 2020, 9:02 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
20

Probably better to use SetVector, so the iteration order in the later loop is deterministic.

21

I don't think you need the check, insert should only add the function if it is not already present.

fhahn added a comment.Aug 7 2020, 9:16 AM

Looks like the line numbers in my previous comment got messed up. I let them at an earlier version that actually contained the code. It would be good if you could update the patch with a squashed version of all changes.

The assertion doesn't work alone. I would still prefer not to skip over non-call sites blindly. @fhahn in addition to blockaddr users, do we expect anything else? We can skip those just fine.

congzhe updated this revision to Diff 284526.Aug 10 2020, 4:46 PM
congzhe edited the summary of this revision. (Show Details)

Updated and squashed all commits into a single one

The assertion doesn't work alone. I would still prefer not to skip over non-call sites blindly. @fhahn in addition to blockaddr users, do we expect anything else? We can skip those just fine.

Thank you, now skipped over blockaddr users.

Looks like the line numbers in my previous comment got messed up. I let them at an earlier version that actually contained the code. It would be good if you could update the patch with a squashed version of all changes.

Thanks for the comment, now squashed all commits into a single one.

llvm/lib/Transforms/Scalar/SCCP.cpp
21

Thank you, now used SmallSetVector and removed the check.

The assertion doesn't work alone. I would still prefer not to skip over non-call sites blindly. @fhahn in addition to blockaddr users, do we expect anything else? We can skip those just fine.

Thank you, now skipped over blockaddr users.

Looks like the line numbers in my previous comment got messed up. I let them at an earlier version that actually contained the code. It would be good if you could update the patch with a squashed version of all changes.

Thanks for the comment, now squashed all commits into a single one.

@jdoerfert @fhahn I updated this patch according to your previous comments, I'd very much appreciate it if you could confirm so it can get merged. Thank you very much.

jdoerfert accepted this revision.Aug 17 2020, 9:52 AM

LGTM, please clang-format the code

fhahn added inline comments.Aug 17 2020, 10:02 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
37

Is this include needed?

2133

I think you can just use cast<> here, which has a similar assertion.

congzhe updated this revision to Diff 286083.Aug 17 2020, 10:43 AM
congzhe added inline comments.Aug 17 2020, 10:46 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
37

This header file is included since we need the CallBase class when we remove the returned attribute in call sites.

2133

Thanks. Now used cast<> instead of dyn_cast<> and removed the assert().

@fhahn could you let me know if you have further comments on this revision? Thanks!

fhahn accepted this revision.Aug 27 2020, 4:37 AM

LGTM, thanks. Just a minor comment about the comments. Also, could you add the blockaddress case to llvm/test/Transforms/SCCP/ipsccp-clear-returned.ll?

llvm/lib/Transforms/Scalar/SCCP.cpp
20

nit: period at end of sentence. (here and at the other comments)

20

Is this needed?

congzhe added inline comments.Aug 27 2020, 9:22 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
20

This header file is included since we need the CallBase class when we remove the returned attribute in call sites.

fhahn added inline comments.Aug 27 2020, 9:40 AM
llvm/lib/Transforms/Scalar/SCCP.cpp
20

CallBase is defined here https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/IR/InstrTypes.h#L1100, which is already included?

congzhe updated this revision to Diff 288662.Aug 28 2020, 11:52 AM
congzhe updated this revision to Diff 288665.EditedAug 28 2020, 11:56 AM

@fhahn Thanks for the comments.

Now removed the include of AbstractCallBase. Also fixed the lack of periods in comments. Clang-format-ed the code.

Added a test case for the blockaddr case.

llvm/lib/Transforms/Scalar/SCCP.cpp
20

Thanks, now removed the include of AbstractCallBase

fhahn added a comment.Aug 28 2020, 2:46 PM

Thanks! Please let us know if you need someone to commit the change on your behalf. If that's the case, please let us also know then name & email to use as commit author.

congzhe updated this revision to Diff 289231.Sep 1 2020, 11:23 AM

rebased and clang format-ed the code, ready to merge

fhahn added a comment.Sep 1 2020, 11:53 AM

rebased and clang format-ed the code, ready to merge

great, thanks! As mentioned earlier, please let us know here if you need someone to commit this change on your behalf, with the name/email you'd like the author field set to.

rebased and clang format-ed the code, ready to merge

great, thanks! As mentioned earlier, please let us know here if you need someone to commit this change on your behalf, with the name/email you'd like the author field set to.

Thanks a lot! I asked Danilo to commit the patch for me and I already let him know the info, I think I'm all set.
Thanks again!

congzhe updated this revision to Diff 289447.Sep 2 2020, 7:56 AM