https://github.com/llvmbot created https://github.com/llvm/llvm-project/pull/117869
Backport 3c9022c965b85951f30af140da591f819acef8a0 39601a6e5484de183bf525b7d0624e7890ccd8ab Requested by: @nikic >From 30e75e7bdac13b4139a687adbf42c289c31f3305 Mon Sep 17 00:00:00 2001 From: AdityaK <hiradi...@msn.com> Date: Tue, 10 Sep 2024 22:39:02 -0700 Subject: [PATCH 1/2] Bail out jump threading on indirect branches (#103688) The bug was introduced by https://github.com/llvm/llvm-project/pull/68473 Fixes: #102351 (cherry picked from commit 3c9022c965b85951f30af140da591f819acef8a0) --- llvm/lib/Transforms/Utils/Local.cpp | 11 +- .../switch-branch-fold-indirectbr-102351.ll | 104 ++++++++++++++++++ 2 files changed, 113 insertions(+), 2 deletions(-) create mode 100644 llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp index 7192efe3f16b9d..4eb8dc1d2d6158 100644 --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -1028,7 +1028,14 @@ CanRedirectPredsOfEmptyBBToSucc(BasicBlock *BB, BasicBlock *Succ, if (!BB->hasNPredecessorsOrMore(2)) return false; - // Get single common predecessors of both BB and Succ + if (any_of(BBPreds, [](const BasicBlock *Pred) { + return isa<PHINode>(Pred->begin()) && + isa<IndirectBrInst>(Pred->getTerminator()); + })) + return false; + + // Get the single common predecessor of both BB and Succ. Return false + // when there are more than one common predecessors. for (BasicBlock *SuccPred : SuccPreds) { if (BBPreds.count(SuccPred)) { if (CommonPred) @@ -1133,7 +1140,7 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, bool BBKillable = CanPropagatePredecessorsForPHIs(BB, Succ, BBPreds); - // Even if we can not fold bB into Succ, we may be able to redirect the + // Even if we can not fold BB into Succ, we may be able to redirect the // predecessors of BB to Succ. bool BBPhisMergeable = BBKillable || diff --git a/llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll b/llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll new file mode 100644 index 00000000000000..03aee68fa4248c --- /dev/null +++ b/llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll @@ -0,0 +1,104 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 +; RUN: opt < %s -passes=simplifycfg -S | FileCheck %s + +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define dso_local noundef i32 @main() { +; CHECK-LABEL: define dso_local noundef i32 @main() { +; CHECK-NEXT: [[BB:.*]]: +; CHECK-NEXT: [[ALLOCA:%.*]] = alloca [2 x ptr], align 16 +; CHECK-NEXT: store ptr blockaddress(@main, %[[BB4:.*]]), ptr [[ALLOCA]], align 16, !tbaa [[TBAA0:![0-9]+]] +; CHECK-NEXT: [[GETELEMENTPTR:%.*]] = getelementptr inbounds [2 x ptr], ptr [[ALLOCA]], i64 0, i64 1 +; CHECK-NEXT: store ptr blockaddress(@main, %[[BB10:.*]]), ptr [[GETELEMENTPTR]], align 8, !tbaa [[TBAA0]] +; CHECK-NEXT: br label %[[BB1:.*]] +; CHECK: [[BB1]]: +; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ 0, %[[BB]] ], [ [[PHI8:%.*]], %[[BB7:.*]] ] +; CHECK-NEXT: [[PHI2:%.*]] = phi i32 [ 0, %[[BB]] ], [ [[PHI9:%.*]], %[[BB7]] ] +; CHECK-NEXT: switch i32 [[PHI]], label %[[BB7]] [ +; CHECK-NEXT: i32 0, label %[[BB12:.*]] +; CHECK-NEXT: i32 1, label %[[BB4]] +; CHECK-NEXT: i32 2, label %[[BB6:.*]] +; CHECK-NEXT: ] +; CHECK: [[BB4]]: +; CHECK-NEXT: [[PHI5:%.*]] = phi i32 [ [[PHI13:%.*]], %[[BB12]] ], [ [[PHI2]], %[[BB1]] ] +; CHECK-NEXT: br label %[[BB7]] +; CHECK: [[BB6]]: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @foo(i32 noundef [[PHI2]]) +; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[PHI2]], 1 +; CHECK-NEXT: br label %[[BB12]] +; CHECK: [[BB7]]: +; CHECK-NEXT: [[PHI8]] = phi i32 [ [[PHI]], %[[BB1]] ], [ 2, %[[BB4]] ] +; CHECK-NEXT: [[PHI9]] = phi i32 [ [[PHI2]], %[[BB1]] ], [ [[PHI5]], %[[BB4]] ] +; CHECK-NEXT: br label %[[BB1]], !llvm.loop [[LOOP4:![0-9]+]] +; CHECK: [[BB10]]: +; CHECK-NEXT: [[CALL11:%.*]] = call i32 @foo(i32 noundef [[PHI13]]) +; CHECK-NEXT: ret i32 0 +; CHECK: [[BB12]]: +; CHECK-NEXT: [[PHI13]] = phi i32 [ [[ADD]], %[[BB6]] ], [ [[PHI2]], %[[BB1]] ] +; CHECK-NEXT: [[SEXT:%.*]] = sext i32 [[PHI13]] to i64 +; CHECK-NEXT: [[GETELEMENTPTR14:%.*]] = getelementptr inbounds [2 x ptr], ptr [[ALLOCA]], i64 0, i64 [[SEXT]] +; CHECK-NEXT: [[LOAD:%.*]] = load ptr, ptr [[GETELEMENTPTR14]], align 8, !tbaa [[TBAA0]] +; CHECK-NEXT: indirectbr ptr [[LOAD]], [label %[[BB4]], label %bb10] +; +bb: + %alloca = alloca [2 x ptr], align 16 + store ptr blockaddress(@main, %bb4), ptr %alloca, align 16, !tbaa !0 + %getelementptr = getelementptr inbounds [2 x ptr], ptr %alloca, i64 0, i64 1 + store ptr blockaddress(@main, %bb10), ptr %getelementptr, align 8, !tbaa !0 + br label %bb1 + +bb1: ; preds = %bb7, %bb + %phi = phi i32 [ 0, %bb ], [ %phi8, %bb7 ] + %phi2 = phi i32 [ 0, %bb ], [ %phi9, %bb7 ] + switch i32 %phi, label %bb7 [ + i32 0, label %bb3 + i32 1, label %bb4 + i32 2, label %bb6 + ] + +bb3: ; preds = %bb1 + br label %bb12 + +bb4: ; preds = %bb12, %bb1 + %phi5 = phi i32 [ %phi13, %bb12 ], [ %phi2, %bb1 ] + br label %bb7 + +bb6: ; preds = %bb1 + %call = call i32 @foo(i32 noundef %phi2) + %add = add nsw i32 %phi2, 1 + br label %bb12 + +bb7: ; preds = %bb4, %bb1 + %phi8 = phi i32 [ %phi, %bb1 ], [ 2, %bb4 ] + %phi9 = phi i32 [ %phi2, %bb1 ], [ %phi5, %bb4 ] + br label %bb1, !llvm.loop !4 + +bb10: ; preds = %bb12 + %call11 = call i32 @foo(i32 noundef %phi13) + ret i32 0 + +bb12: ; preds = %bb6, %bb3 + %phi13 = phi i32 [ %add, %bb6 ], [ %phi2, %bb3 ] + %sext = sext i32 %phi13 to i64 + %getelementptr14 = getelementptr inbounds [2 x ptr], ptr %alloca, i64 0, i64 %sext + %load = load ptr, ptr %getelementptr14, align 8, !tbaa !0 + indirectbr ptr %load, [label %bb4, label %bb10] +} + +declare i32 @foo(i32) + +!0 = !{!1, !1, i64 0} +!1 = !{!"any pointer", !2, i64 0} +!2 = !{!"omnipotent char", !3, i64 0} +!3 = !{!"Simple C++ TBAA"} +!4 = !{!5, !5, i64 0} +!5 = !{!"int", !2, i64 0} +;. +; CHECK: [[TBAA0]] = !{[[META1:![0-9]+]], [[META1]], i64 0} +; CHECK: [[META1]] = !{!"any pointer", [[META2:![0-9]+]], i64 0} +; CHECK: [[META2]] = !{!"omnipotent char", [[META3:![0-9]+]], i64 0} +; CHECK: [[META3]] = !{!"Simple C++ TBAA"} +; CHECK: [[LOOP4]] = !{[[META5:![0-9]+]], [[META5]], i64 0} +; CHECK: [[META5]] = !{!"int", [[META2]], i64 0} +;. >From a87c6224086f35162c6001fbc87818b286d6af41 Mon Sep 17 00:00:00 2001 From: AdityaK <hiradi...@msn.com> Date: Tue, 26 Nov 2024 14:57:28 -0800 Subject: [PATCH 2/2] Bail out jump threading on indirect branches only (#117778) Remove check for PHI in pred as pointed out in #103688 Reduced the testcase to remove redundant phi in pred Fixes: #102351 (cherry picked from commit 39601a6e5484de183bf525b7d0624e7890ccd8ab) --- llvm/lib/Transforms/Utils/Local.cpp | 3 +- .../switch-branch-fold-indirectbr-102351.ll | 141 ++++++++---------- 2 files changed, 60 insertions(+), 84 deletions(-) diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp index 4eb8dc1d2d6158..f68cbf62b9825f 100644 --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -1029,8 +1029,7 @@ CanRedirectPredsOfEmptyBBToSucc(BasicBlock *BB, BasicBlock *Succ, return false; if (any_of(BBPreds, [](const BasicBlock *Pred) { - return isa<PHINode>(Pred->begin()) && - isa<IndirectBrInst>(Pred->getTerminator()); + return isa<IndirectBrInst>(Pred->getTerminator()); })) return false; diff --git a/llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll b/llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll index 03aee68fa4248c..d3713be8358db4 100644 --- a/llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll +++ b/llvm/test/Transforms/SimplifyCFG/switch-branch-fold-indirectbr-102351.ll @@ -1,104 +1,81 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --prefix-filecheck-ir-name pref --version 5 ; RUN: opt < %s -passes=simplifycfg -S | FileCheck %s -target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128" -target triple = "x86_64-unknown-linux-gnu" - -define dso_local noundef i32 @main() { -; CHECK-LABEL: define dso_local noundef i32 @main() { +define i32 @foo.1(i32 %arg, ptr %arg1) { +; CHECK-LABEL: define i32 @foo.1( +; CHECK-SAME: i32 [[ARG:%.*]], ptr [[ARG1:%.*]]) { ; CHECK-NEXT: [[BB:.*]]: ; CHECK-NEXT: [[ALLOCA:%.*]] = alloca [2 x ptr], align 16 -; CHECK-NEXT: store ptr blockaddress(@main, %[[BB4:.*]]), ptr [[ALLOCA]], align 16, !tbaa [[TBAA0:![0-9]+]] +; CHECK-NEXT: store ptr blockaddress(@foo.1, %[[BB8:.*]]), ptr [[ALLOCA]], align 16 ; CHECK-NEXT: [[GETELEMENTPTR:%.*]] = getelementptr inbounds [2 x ptr], ptr [[ALLOCA]], i64 0, i64 1 -; CHECK-NEXT: store ptr blockaddress(@main, %[[BB10:.*]]), ptr [[GETELEMENTPTR]], align 8, !tbaa [[TBAA0]] -; CHECK-NEXT: br label %[[BB1:.*]] -; CHECK: [[BB1]]: -; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ 0, %[[BB]] ], [ [[PHI8:%.*]], %[[BB7:.*]] ] -; CHECK-NEXT: [[PHI2:%.*]] = phi i32 [ 0, %[[BB]] ], [ [[PHI9:%.*]], %[[BB7]] ] -; CHECK-NEXT: switch i32 [[PHI]], label %[[BB7]] [ -; CHECK-NEXT: i32 0, label %[[BB12:.*]] -; CHECK-NEXT: i32 1, label %[[BB4]] -; CHECK-NEXT: i32 2, label %[[BB6:.*]] +; CHECK-NEXT: store ptr blockaddress(@foo.1, %[[BB16:.*]]), ptr [[GETELEMENTPTR]], align 8 +; CHECK-NEXT: br label %[[PREFBB2:.*]] +; CHECK: [[PREFBB2]]: +; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ 0, %[[BB]] ], [ [[PHI14:%.*]], %[[BB13:.*]] ] +; CHECK-NEXT: [[PHI3:%.*]] = phi i32 [ 0, %[[BB]] ], [ [[PHI15:%.*]], %[[BB13]] ] +; CHECK-NEXT: switch i32 [[PHI]], label %[[BB13]] [ +; CHECK-NEXT: i32 0, label %[[PREFBB18:.*]] +; CHECK-NEXT: i32 1, label %[[BB8]] +; CHECK-NEXT: i32 2, label %[[PREFBB11:.*]] ; CHECK-NEXT: ] -; CHECK: [[BB4]]: -; CHECK-NEXT: [[PHI5:%.*]] = phi i32 [ [[PHI13:%.*]], %[[BB12]] ], [ [[PHI2]], %[[BB1]] ] -; CHECK-NEXT: br label %[[BB7]] -; CHECK: [[BB6]]: -; CHECK-NEXT: [[CALL:%.*]] = call i32 @foo(i32 noundef [[PHI2]]) -; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[PHI2]], 1 -; CHECK-NEXT: br label %[[BB12]] -; CHECK: [[BB7]]: -; CHECK-NEXT: [[PHI8]] = phi i32 [ [[PHI]], %[[BB1]] ], [ 2, %[[BB4]] ] -; CHECK-NEXT: [[PHI9]] = phi i32 [ [[PHI2]], %[[BB1]] ], [ [[PHI5]], %[[BB4]] ] -; CHECK-NEXT: br label %[[BB1]], !llvm.loop [[LOOP4:![0-9]+]] -; CHECK: [[BB10]]: -; CHECK-NEXT: [[CALL11:%.*]] = call i32 @foo(i32 noundef [[PHI13]]) +; CHECK: [[BB8]]: +; CHECK-NEXT: [[PHI10:%.*]] = phi i32 [ [[ARG]], %[[PREFBB18]] ], [ [[PHI3]], %[[PREFBB2]] ] +; CHECK-NEXT: br label %[[BB13]] +; CHECK: [[PREFBB11]]: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @wombat(i32 noundef [[PHI3]]) +; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[PHI3]], 1 +; CHECK-NEXT: br label %[[PREFBB18]] +; CHECK: [[BB13]]: +; CHECK-NEXT: [[PHI14]] = phi i32 [ [[PHI]], %[[PREFBB2]] ], [ 2, %[[BB8]] ] +; CHECK-NEXT: [[PHI15]] = phi i32 [ [[PHI3]], %[[PREFBB2]] ], [ [[PHI10]], %[[BB8]] ] +; CHECK-NEXT: br label %[[PREFBB2]] +; CHECK: [[BB16]]: +; CHECK-NEXT: [[CALL17:%.*]] = call i32 @wombat(i32 noundef [[ARG]]) ; CHECK-NEXT: ret i32 0 -; CHECK: [[BB12]]: -; CHECK-NEXT: [[PHI13]] = phi i32 [ [[ADD]], %[[BB6]] ], [ [[PHI2]], %[[BB1]] ] -; CHECK-NEXT: [[SEXT:%.*]] = sext i32 [[PHI13]] to i64 -; CHECK-NEXT: [[GETELEMENTPTR14:%.*]] = getelementptr inbounds [2 x ptr], ptr [[ALLOCA]], i64 0, i64 [[SEXT]] -; CHECK-NEXT: [[LOAD:%.*]] = load ptr, ptr [[GETELEMENTPTR14]], align 8, !tbaa [[TBAA0]] -; CHECK-NEXT: indirectbr ptr [[LOAD]], [label %[[BB4]], label %bb10] +; CHECK: [[PREFBB18]]: +; CHECK-NEXT: [[LOAD:%.*]] = load ptr, ptr [[ARG1]], align 8 +; CHECK-NEXT: indirectbr ptr [[LOAD]], [label %[[BB8]], label %bb16] ; bb: %alloca = alloca [2 x ptr], align 16 - store ptr blockaddress(@main, %bb4), ptr %alloca, align 16, !tbaa !0 + store ptr blockaddress(@foo.1, %bb8), ptr %alloca, align 16 %getelementptr = getelementptr inbounds [2 x ptr], ptr %alloca, i64 0, i64 1 - store ptr blockaddress(@main, %bb10), ptr %getelementptr, align 8, !tbaa !0 - br label %bb1 + store ptr blockaddress(@foo.1, %bb16), ptr %getelementptr, align 8 + br label %bb2 -bb1: ; preds = %bb7, %bb - %phi = phi i32 [ 0, %bb ], [ %phi8, %bb7 ] - %phi2 = phi i32 [ 0, %bb ], [ %phi9, %bb7 ] - switch i32 %phi, label %bb7 [ - i32 0, label %bb3 - i32 1, label %bb4 - i32 2, label %bb6 +bb2: ; preds = %bb13, %bb + %phi = phi i32 [ 0, %bb ], [ %phi14, %bb13 ] + %phi3 = phi i32 [ 0, %bb ], [ %phi15, %bb13 ] + switch i32 %phi, label %bb13 [ + i32 0, label %bb5 + i32 1, label %bb8 + i32 2, label %bb11 ] -bb3: ; preds = %bb1 - br label %bb12 +bb5: ; preds = %bb2 + br label %bb18 -bb4: ; preds = %bb12, %bb1 - %phi5 = phi i32 [ %phi13, %bb12 ], [ %phi2, %bb1 ] - br label %bb7 +bb8: ; preds = %bb18, %bb2 + %phi10 = phi i32 [ %arg, %bb18 ], [ %phi3, %bb2 ] + br label %bb13 -bb6: ; preds = %bb1 - %call = call i32 @foo(i32 noundef %phi2) - %add = add nsw i32 %phi2, 1 - br label %bb12 +bb11: ; preds = %bb2 + %call = call i32 @wombat(i32 noundef %phi3) + %add = add nsw i32 %phi3, 1 + br label %bb18 -bb7: ; preds = %bb4, %bb1 - %phi8 = phi i32 [ %phi, %bb1 ], [ 2, %bb4 ] - %phi9 = phi i32 [ %phi2, %bb1 ], [ %phi5, %bb4 ] - br label %bb1, !llvm.loop !4 +bb13: ; preds = %bb8, %bb2 + %phi14 = phi i32 [ %phi, %bb2 ], [ 2, %bb8 ] + %phi15 = phi i32 [ %phi3, %bb2 ], [ %phi10, %bb8 ] + br label %bb2 -bb10: ; preds = %bb12 - %call11 = call i32 @foo(i32 noundef %phi13) +bb16: ; preds = %bb18 + %call17 = call i32 @wombat(i32 noundef %arg) ret i32 0 -bb12: ; preds = %bb6, %bb3 - %phi13 = phi i32 [ %add, %bb6 ], [ %phi2, %bb3 ] - %sext = sext i32 %phi13 to i64 - %getelementptr14 = getelementptr inbounds [2 x ptr], ptr %alloca, i64 0, i64 %sext - %load = load ptr, ptr %getelementptr14, align 8, !tbaa !0 - indirectbr ptr %load, [label %bb4, label %bb10] +bb18: ; preds = %bb11, %bb5 + %load = load ptr, ptr %arg1, align 8 + indirectbr ptr %load, [label %bb8, label %bb16] } -declare i32 @foo(i32) - -!0 = !{!1, !1, i64 0} -!1 = !{!"any pointer", !2, i64 0} -!2 = !{!"omnipotent char", !3, i64 0} -!3 = !{!"Simple C++ TBAA"} -!4 = !{!5, !5, i64 0} -!5 = !{!"int", !2, i64 0} -;. -; CHECK: [[TBAA0]] = !{[[META1:![0-9]+]], [[META1]], i64 0} -; CHECK: [[META1]] = !{!"any pointer", [[META2:![0-9]+]], i64 0} -; CHECK: [[META2]] = !{!"omnipotent char", [[META3:![0-9]+]], i64 0} -; CHECK: [[META3]] = !{!"Simple C++ TBAA"} -; CHECK: [[LOOP4]] = !{[[META5:![0-9]+]], [[META5]], i64 0} -; CHECK: [[META5]] = !{!"int", [[META2]], i64 0} -;. +declare i32 @wombat(i32) _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
