[TailCallElim] Remove the readonly attribute of byval.

[DianQK]

Summary

When eliminating a tail call, we modify the values of the arguments.
Therefore, if the byval parameter has a readonly attribute, we have to remove it. It is safe because,
from the perspective of a caller, the byval parameter is always treated as "readonly," even if the readonly attribute is removed.

Fixes https://github.com/llvm/llvm-project/issues/64289.

[nikic]

LGTM, but maybe wait a day before committing in case somebody disagrees with this approach.

I would also recommend to add a PhaseOrdering test for https://github.com/llvm/llvm-project/issues/64289. This miscompile here is due to an interaction of multiple passes, so I think it's worthwhile to check the full optimization pipeline.

[DianQK]

In D156793#4550462, @nikic wrote:

LGTM, but maybe wait a day before committing in case somebody disagrees with this approach.

Do you think we need to add someone else to review it?
TailRecursionElimination.cpp has had very few non-NFC changes recently.

[DianQK]

Add a PhaseOrdering test for https://github.com/llvm/llvm-project/issues/64289.

[avl]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

683

probably, instead of removing readonly attribute we could stop generating it? Otherwise it will be presented or not depending of whether tail recursion elimination is happened.

byval(<ty>)

    This indicates that the pointer parameter should really be passed by value to the function. The attribute implies that a hidden copy of the pointee is made between the caller and the callee, so the callee is unable to modify the value in the caller.

The hidden copy protects original value from modifications done by callee. Having readonly attribute for hidden copy, probably, redundant.

[DianQK]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

683

Do you mean don't add readonly at PostOrderFunctionAttrsPass?
I don't think so. First rustc/clang can also add the readonly attribute.
I think readonly + byval makes sense. There are more internal invariant representations than only byval.

[avl]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

683

if readonly is important then we probably should not do tail recursion elimination for readonly + byval as we will write into the readonly data. if it is not important then it should be safe to not set this flag?

[efriedma]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

683

Marking a byval pointer readonly isn't very useful; MemorySSA can easily analyze a byval argument without the marking in almost all cases.

I would tend towards saying we shouldn't add readonly markings to byval values, if only to reduce the chance of this sort of confusion. But that doesn't really impact this patch: unless we actually make "readonly byval" illegal, TCE needs to handle it anyway.

[DianQK]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

683

if readonly is important then we probably should not do tail recursion elimination for readonly + byval as we will write into the readonly data. if it is not important then it should be safe to not set this flag?

It is possible to perform a transformation in a way that prevents another, larger optimization.
readonly must make sense. At least until tail recursion elimination, other passes can use readonly.
But I think tail recursion elimination has a better opportunity for optimization than readonly.
In the test case, with tail recursion elimination eventually converted to a ret instruction.

Marking a byval pointer readonly isn't very useful; MemorySSA can easily analyze a byval argument without the marking in almost all cases.

I would tend towards saying we shouldn't add readonly markings to byval values, if only to reduce the chance of this sort of confusion. But that doesn't really impact this patch: unless we actually make "readonly byval" illegal, TCE needs to handle it anyway.

Using readonly we can avoid reusing MemorySSA analysis. This should reduce compilation time. And that covers all cases.
readonly + byval is indeed confusing. But I think this discussion we can clarify the meaning.

• readonly = Indicates invariance to *internal* and external.
• byval = Indicates invariance to external.

683

Marking a byval pointer readonly isn't very useful; MemorySSA can easily analyze a byval argument without the marking in almost all cases.

I would tend towards saying we shouldn't add readonly markings to byval values, if only to reduce the chance of this sort of confusion. But that doesn't really impact this patch: unless we actually make "readonly byval" illegal, TCE needs to handle it anyway.

[DianQK]

In my mind, this is a worse case of mis-compilation.

With the current discussion, we have three methods to address it:

1. Remove the readonly attribute, which is safe with byval.
2. Do not add the readonly attribute to byval.
3. Prevent the tail recursion elimination.

First, all three methods can solve this problem.
But I prefer the first one, and I think there is less opportunity to prevent other optimizations.

[DianQK]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

683

But that doesn't really impact this patch: unless we actually make "readonly byval" illegal, TCE needs to handle it anyway.

So I think I'd go ahead and submit this patch to fix the miscompilation. If anyone has other ideas they can submit a new patch.

[nikic]

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

683

Yes, please go ahead. If we like, we can forbid byval + readonly in a followup, but it's allowed right now, so we should handle it.

llvm/test/Transforms/PhaseOrdering/pr64289-tce.ll

4

These two RUN lines do the same thing, drop one of them.

[DianQK]

Rebase and remove the duplicate test.

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

bool TailRecursionEliminator::eliminateCall(CallInst *CI) {
   }
 
   // Ok, now that we know we have a pseudo-entry block WITH all of the
   // required PHI nodes, add entries into the PHI node for the actual
   // parameters passed into the tail-recursive call.
   for (unsigned I = 0, E = CI->arg_size(); I != E; ++I) {
     if (CI->isByValArgument(I)) {
       copyLocalTempOfByValueOperandIntoArguments(CI, I);
+      // When eliminating a tail call, we modify the values of the arguments.
+      // Therefore, if the byval parameter has a readonly attribute, we have to
+      // remove it. It is safe because, from the perspective of a caller, the
+      // byval parameter is always treated as "readonly," even if the readonly
+      // attribute is removed.
+      F.removeParamAttr(I, Attribute::ReadOnly);
       ArgumentPHIs[I]->addIncoming(F.getArg(I), BB);
     } else
       ArgumentPHIs[I]->addIncoming(CI->getArgOperand(I), BB);
   }
 
   if (AccRecInstr) {
     insertAccumulator(AccRecInstr);
 

llvm/test/Transforms/PhaseOrdering/pr64289-tce.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -O3 < %s | FileCheck %s
+
+; A miscompilation found on https://github.com/llvm/llvm-project/issues/64289.
+; 1. PostOrderFunctionAttrsPass added readonly to the parameter.
+; 2. TailCallElimPass modified the parameter but kept readonly.
+; 3. LICMPass incorrectly hoisted the load instruction.
+
+define void @pr64289(ptr noalias byval(i64) %x) {
+; CHECK-LABEL: @pr64289(
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    ret void
+;
+start:
+  %new_x = alloca i64, align 8
+  %x_val = load i64, ptr %x, align 8
+  %is_zero = icmp eq i64 %x_val, 0
+  br i1 %is_zero, label %end, label %recurse
+
+recurse:
+  store i64 0, ptr %new_x, align 8
+  call void @pr64289(ptr %new_x)
+  br label %end
+
+end:
+  ret void
+}

llvm/test/Transforms/TailCallElim/tre-byval-parameter-2.ll

 %struct.A = type { [10 x i64] }
 
 @global = dso_local local_unnamed_addr global %struct.A zeroinitializer, align 8
 @.str = private unnamed_addr constant [11 x i8] c"%lld %lld\0A\00", align 1
 
 ; Function Attrs: noinline nounwind uwtable
 define dso_local void @_Z7dostuff1AS_i(ptr nocapture byval(%struct.A) align 8 %a, ptr nocapture readonly byval(%struct.A) align 8 %b, i32 %i) local_unnamed_addr #0 {
 ; CHECK-LABEL: define {{[^@]+}}@_Z7dostuff1AS_i
-; CHECK-SAME: (ptr nocapture byval([[STRUCT_A:%.*]]) align 8 [[A:%.*]], ptr nocapture readonly byval([[STRUCT_A]]) align 8 [[B:%.*]], i32 [[I:%.*]]) local_unnamed_addr #[[ATTR0:[0-9]+]] {
+; CHECK-SAME: (ptr nocapture byval([[STRUCT_A:%.*]]) align 8 [[A:%.*]], ptr nocapture byval([[STRUCT_A]]) align 8 [[B:%.*]], i32 [[I:%.*]]) local_unnamed_addr #[[ATTR0:[0-9]+]] {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AGG_TMP52:%.*]] = alloca [[STRUCT_A]], align 8
 ; CHECK-NEXT:    [[AGG_TMP1:%.*]] = alloca [[STRUCT_A]], align 8
 ; CHECK-NEXT:    [[AGG_TMP:%.*]] = alloca [[STRUCT_A]], align 8
 ; CHECK-NEXT:    [[AGG_TMP5:%.*]] = alloca [[STRUCT_A]], align 8
 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
 ; CHECK:       tailrecurse:
 ; CHECK-NEXT:    [[I_TR:%.*]] = phi i32 [ [[I]], [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[IF_END:%.*]] ]

llvm/test/Transforms/TailCallElim/tre-byval-parameter.ll

 ; new iteration started.
 
 %struct.S = type { i32, i32, float, %struct.B }
 %struct.B = type { i32, float }
 
 ; Function Attrs: uwtable
 define dso_local i32 @_Z3fooi1S(i32 %count, ptr nocapture readonly byval(%struct.S) align 8 %p1) local_unnamed_addr #0 {
 ; CHECK-LABEL: define {{[^@]+}}@_Z3fooi1S
-; CHECK-SAME: (i32 [[COUNT:%.*]], ptr nocapture readonly byval([[STRUCT_S:%.*]]) align 8 [[P1:%.*]]) local_unnamed_addr #[[ATTR0:[0-9]+]] {
+; CHECK-SAME: (i32 [[COUNT:%.*]], ptr nocapture byval([[STRUCT_S:%.*]]) align 8 [[P1:%.*]]) local_unnamed_addr #[[ATTR0:[0-9]+]] {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AGG_TMP_I1:%.*]] = alloca [[STRUCT_S]], align 8
 ; CHECK-NEXT:    [[AGG_TMP_I:%.*]] = alloca [[STRUCT_S]], align 8
 ; CHECK-NEXT:    [[AGG_TMP14:%.*]] = alloca [[STRUCT_S]], align 8
 ; CHECK-NEXT:    [[AGG_TMP:%.*]] = alloca [[STRUCT_S]], align 8
 ; CHECK-NEXT:    [[AGG_TMP1:%.*]] = alloca [[STRUCT_S]], align 8
 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
 ; CHECK:       tailrecurse: