diff --git a/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp b/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
--- a/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
@@ -675,6 +675,12 @@
   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);
diff --git a/llvm/test/Transforms/PhaseOrdering/pr64289-tce.ll b/llvm/test/Transforms/PhaseOrdering/pr64289-tce.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/PhaseOrdering/pr64289-tce.ll
@@ -0,0 +1,27 @@
+; 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
+}
diff --git a/llvm/test/Transforms/TailCallElim/tre-byval-parameter-2.ll b/llvm/test/Transforms/TailCallElim/tre-byval-parameter-2.ll
--- a/llvm/test/Transforms/TailCallElim/tre-byval-parameter-2.ll
+++ b/llvm/test/Transforms/TailCallElim/tre-byval-parameter-2.ll
@@ -25,7 +25,7 @@
 ; 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
diff --git a/llvm/test/Transforms/TailCallElim/tre-byval-parameter.ll b/llvm/test/Transforms/TailCallElim/tre-byval-parameter.ll
--- a/llvm/test/Transforms/TailCallElim/tre-byval-parameter.ll
+++ b/llvm/test/Transforms/TailCallElim/tre-byval-parameter.ll
@@ -25,7 +25,7 @@
 ; 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