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

[congzhe]

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.

[congzhe]

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

[davide]

Florian, can you take a look?

[lebedev.ri]

In D84220#2179754, @davide wrote:

Florian, can you take a look?

On Tue, Jul 28, 2020 at 10:35 PM Florian Hahn via llvm-commits <[e-mail]> wrote:

On Jul 28, 2020, at 20:32, Congzhe Cao via Phabricator <[e-mail]> 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
[e-mail]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

[fhahn]

Thanks for the patch! Some comments inline.

llvm/lib/Transforms/Scalar/SCCP.cpp

21

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.

[congzhe]

In D84220#2179764, @lebedev.ri wrote:

In D84220#2179754, @davide wrote:

Florian, can you take a look?

On Tue, Jul 28, 2020 at 10:35 PM Florian Hahn via llvm-commits <[e-mail]> wrote:

On Jul 28, 2020, at 20:32, Congzhe Cao via Phabricator <[e-mail]> 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
[e-mail]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

My apologies, I've updated permissions.

[jdoerfert]

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

21

call sites can have the attribute too.

[efriedma]

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 .

[jdoerfert]

In D84220#2179859, @efriedma wrote:

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.

[efriedma]

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.

[jdoerfert]

In D84220#2180340, @efriedma wrote:

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?

[fhahn]

In D84220#2180375, @jdoerfert wrote:

In D84220#2180340, @efriedma wrote:

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]

In D84220#2180375, @jdoerfert wrote:

In D84220#2180340, @efriedma wrote:

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
}

[jdoerfert]

In D84220#2182687, @fhahn wrote:

In D84220#2180375, @jdoerfert wrote:

In D84220#2180340, @efriedma wrote:

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]

In D84220#2179859, @efriedma wrote:

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 -

[jdoerfert]

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.

[congzhe]

In D84220#2185774, @jdoerfert wrote:

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!

[jdoerfert]

In D84220#2185949, @congzhe wrote:

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]

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.

2. also remove the returned attribte for call sites that correspond to the zapped functions

3. updated the test file to reflect the changes

[congzhe]

llvm/lib/Transforms/Scalar/SCCP.cpp

21

Thanks, added code that removes returned attribute for call sites

21

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]

llvm/lib/Transforms/Scalar/SCCP.cpp

2056

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 ?

2059

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

[congzhe]

llvm/lib/Transforms/Scalar/SCCP.cpp

2056

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]

llvm/lib/Transforms/Scalar/SCCP.cpp

2056

I think that would be better, yes.

[congzhe]

Comments addressed:

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

[congzhe]

llvm/lib/Transforms/Scalar/SCCP.cpp

2056

Thanks, updated accordingly.

2059

Updated accordingly

[jdoerfert]

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.

[congzhe]

llvm/lib/Transforms/Scalar/SCCP.cpp

2056

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]

llvm/lib/Transforms/Scalar/SCCP.cpp

2039

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

2044

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

[fhahn]

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.

[jdoerfert]

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 and squashed all commits into a single one

[congzhe]

In D84220#2203480, @jdoerfert wrote:

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.

In D84220#2203014, @fhahn wrote:

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

2044

Thank you, now used SmallSetVector and removed the check.

[congzhe]

In D84220#2208460, @congzhe wrote:

In D84220#2203480, @jdoerfert wrote:

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.

In D84220#2203014, @fhahn wrote:

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]

LGTM, please clang-format the code

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

20

Is this include needed?

33

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

[congzhe]

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.

33

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

[congzhe]

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

[fhahn]

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

36

Is this needed?

2043

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

[congzhe]

llvm/lib/Transforms/Scalar/SCCP.cpp

36

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

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

36

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

[congzhe]

@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

36

Thanks, now removed the include of AbstractCallBase

[fhahn]

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]

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

[fhahn]

In D84220#2250221, @congzhe wrote:

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.

[congzhe]

In D84220#2250298, @fhahn wrote:

In D84220#2250221, @congzhe wrote:

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!

llvm/lib/Transforms/Scalar/SCCP.cpp

 //   * Assumes values are constant unless proven otherwise
 //   * Assumes BasicBlocks are dead unless proven otherwise
 //   * Proves values to be constant, and replaces them with constants
 //   * Proves conditional branches to be unconditional
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/ValueLatticeUtils.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/AbstractCallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/InstrTypes.h"
for (auto F : Solver.getMRVFunctionsTracked()) {
     assert(F->getReturnType()->isStructTy() &&
            "The return type should be a struct");
     StructType *STy = cast<StructType>(F->getReturnType());
     if (Solver.isStructLatticeConstant(F, STy))
       findReturnsToZap(*F, ReturnsToZap, Solver);
   }
 
   // Zap all returns which we've identified as zap to change.
+  SmallPtrSet<Function*, 8> FuncZappedReturn;
   for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
     Function *F = ReturnsToZap[i]->getParent()->getParent();
     ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
+    // Record all functions that are zapped
+    if (FuncZappedReturn.find(F) == FuncZappedReturn.end())
+      FuncZappedReturn.insert(F);
+  }
+
+  // Remove the returned attribute for zapped functions and the
+  // corresponding call sites
+  for (Function *F : FuncZappedReturn) {
+    for (Argument &A : F->args())
+      F->removeParamAttr(A.getArgNo(), Attribute::Returned);
+    for (Use &U : F->uses()) {
+      CallBase *CB = dyn_cast<CallBase>(U.getUser());
+      if (!CB)
+        continue;
+      for (auto &arg : CB->args()) {
+        CB->removeParamAttr(CB->getArgOperandNo(&arg), Attribute::Returned);
+      }
+    }
   }
-
   // If we inferred constant or undef values for globals variables, we can
   // delete the global and any stores that remain to it.
   for (auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
     GlobalVariable *GV = I.first;
     if (isOverdefined(I.second))
       continue;
     LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
                       << "' is constant!\n");

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

+; if IPSCCP determines a function returns undef,
+; then the "returned" attribute of input arguments
+; should be cleared.
+
+; RUN: opt < %s -ipsccp -S | FileCheck %s
+define i32 @main() {
+; CHECK-LABEL: @main
+entry:
+; CHECK-NEXT: entry:
+  %call = call i32 @func_return_undef(i32 returned 1)
+; CHECK: call i32 @func_return_undef(i32 1)
+; CHECK-NOT: returned
+  ret i32 %call
+; CHECK: ret i32 1
+}
+
+define internal i32 @func_return_undef(i32 returned %arg) {
+; CHECK: {{define.*@func_return_undef}}
+; CHECK-NOT: returned
+entry:
+; CHECK-NEXT: entry:
+; CHECK-NEXT: {{ret.*undef}}
+ret i32 %arg
+}