diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -190,10 +190,14 @@ return MadeChanges; } +static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB, + DomTreeUpdater &DTU, + BasicBlock *&NewUnreachableBB); + // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, // and return true if the function was modified. static bool runSCCP(Function &F, const DataLayout &DL, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) { LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); SCCPSolver Solver( DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; }, @@ -221,13 +225,12 @@ // as we cannot modify the CFG of the function. SmallPtrSet InsertedValues; + SmallVector BlocksToErase; for (BasicBlock &BB : F) { if (!Solver.isBlockExecutable(&BB)) { LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); - ++NumDeadBlocks; - NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB).first; - + BlocksToErase.push_back(&BB); MadeChanges = true; continue; } @@ -236,17 +239,32 @@ NumInstRemoved, NumInstReplaced); } + // Remove unreachable blocks and non-feasible edges. + for (BasicBlock *DeadBB : BlocksToErase) + NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(), + /*PreserveLCSSA=*/false, &DTU); + + BasicBlock *NewUnreachableBB = nullptr; + for (BasicBlock &BB : F) + MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU, NewUnreachableBB); + + for (BasicBlock *DeadBB : BlocksToErase) + if (!DeadBB->hasAddressTaken()) + DTU.deleteBB(DeadBB); + return MadeChanges; } PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) { const DataLayout &DL = F.getParent()->getDataLayout(); auto &TLI = AM.getResult(F); - if (!runSCCP(F, DL, &TLI)) + auto *DT = AM.getCachedResult(F); + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); + if (!runSCCP(F, DL, &TLI, DTU)) return PreservedAnalyses::all(); auto PA = PreservedAnalyses(); - PA.preserveSet(); + PA.preserve(); return PA; } @@ -269,7 +287,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addPreserved(); - AU.setPreservesCFG(); + AU.addPreserved(); } // runOnFunction - Run the Sparse Conditional Constant Propagation @@ -280,7 +298,10 @@ const DataLayout &DL = F.getParent()->getDataLayout(); const TargetLibraryInfo *TLI = &getAnalysis().getTLI(F); - return runSCCP(F, DL, TLI); + auto *DTWP = getAnalysisIfAvailable(); + DomTreeUpdater DTU(DTWP ? &DTWP->getDomTree() : nullptr, + DomTreeUpdater::UpdateStrategy::Lazy); + return runSCCP(F, DL, TLI, DTU); } }; diff --git a/llvm/test/Transforms/GVN/gvn-loop-load-pre-order.ll b/llvm/test/Transforms/GVN/gvn-loop-load-pre-order.ll --- a/llvm/test/Transforms/GVN/gvn-loop-load-pre-order.ll +++ b/llvm/test/Transforms/GVN/gvn-loop-load-pre-order.ll @@ -30,9 +30,7 @@ ; CHECK-SCCP: while.cond.loopexit.loopexit: ; CHECK-SCCP-NEXT: ret void ; CHECK-SCCP: while.body3: -; CHECK-SCCP-NEXT: br i1 true, label [[IF_END:%.*]], label [[IF_THEN:%.*]] -; CHECK-SCCP: if.then: -; CHECK-SCCP-NEXT: br label [[IF_END]] +; CHECK-SCCP-NEXT: br label [[IF_END:%.*]] ; CHECK-SCCP: if.end: ; CHECK-SCCP-NEXT: br i1 [[COND:%.*]], label [[WHILE_COND_LOOPEXIT_LOOPEXIT:%.*]], label [[WHILE_BODY3]] ; diff --git a/llvm/test/Transforms/SCCP/2004-12-10-UndefBranchBug.ll b/llvm/test/Transforms/SCCP/2004-12-10-UndefBranchBug.ll --- a/llvm/test/Transforms/SCCP/2004-12-10-UndefBranchBug.ll +++ b/llvm/test/Transforms/SCCP/2004-12-10-UndefBranchBug.ll @@ -6,9 +6,7 @@ define i32 @foo() { ; CHECK-LABEL: @foo( -; CHECK-NEXT: br i1 undef, label [[T:%.*]], label [[T]] -; CHECK: T: -; CHECK-NEXT: ret i32 undef +; CHECK-NEXT: unreachable ; br i1 undef, label %T, label %T T: diff --git a/llvm/test/Transforms/SCCP/2008-01-27-UndefCorrelate.ll b/llvm/test/Transforms/SCCP/2008-01-27-UndefCorrelate.ll --- a/llvm/test/Transforms/SCCP/2008-01-27-UndefCorrelate.ll +++ b/llvm/test/Transforms/SCCP/2008-01-27-UndefCorrelate.ll @@ -7,19 +7,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[BB:%.*]] ; CHECK: bb: -; CHECK-NEXT: br i1 undef, label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]] -; CHECK: cond_true: -; CHECK-NEXT: br i1 undef, label [[BB_BACKEDGE:%.*]], label [[BB12:%.*]] -; CHECK: bb.backedge: -; CHECK-NEXT: br label [[BB]] -; CHECK: cond_false: -; CHECK-NEXT: br i1 undef, label [[BB_BACKEDGE]], label [[BB12]] -; CHECK: bb12: -; CHECK-NEXT: br i1 undef, label [[COND_NEXT18:%.*]], label [[COND_TRUE17:%.*]] -; CHECK: cond_true17: ; CHECK-NEXT: unreachable -; CHECK: cond_next18: -; CHECK-NEXT: ret i32 0 ; entry: br label %bb diff --git a/llvm/test/Transforms/SCCP/preserve-analysis.ll b/llvm/test/Transforms/SCCP/preserve-analysis.ll --- a/llvm/test/Transforms/SCCP/preserve-analysis.ll +++ b/llvm/test/Transforms/SCCP/preserve-analysis.ll @@ -1,13 +1,13 @@ ; RUN: opt < %s -debug-pass-manager -passes='loop-vectorize,sccp,loop-vectorize' 2>&1 -S | FileCheck --check-prefix=NEW-PM %s -; Check CFG-only analysis are preserved by SCCP by running it between 2 +; Check that DT is preserved by SCCP by running it between 2 ; loop-vectorize runs. ; NEW-PM-DAG: Running analysis: LoopAnalysis on test ; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on test ; NEW-PM: Running pass: SCCPPass on test ; NEW-PM: Running analysis: TargetLibraryAnalysis on test -; NEW-PM-NOT: Running analysis: LoopAnalysis on test +; NEW-PM: Running analysis: LoopAnalysis on test ; NEW-PM-NOT: Running analysis: DominatorTreeAnalysis on test ; NEW-PM-NOT: Running analysis: AssumptionAnalysis on test ; NEW-PM-NOT: Running analysis: TargetLibraryAnalysis on test diff --git a/llvm/test/Transforms/SCCP/sccptest.ll b/llvm/test/Transforms/SCCP/sccptest.ll --- a/llvm/test/Transforms/SCCP/sccptest.ll +++ b/llvm/test/Transforms/SCCP/sccptest.ll @@ -35,20 +35,17 @@ ; CHECK-NEXT: BB1: ; CHECK-NEXT: br label [[BB2:%.*]] ; CHECK: BB2: -; CHECK-NEXT: [[K2:%.*]] = phi i32 [ [[K4:%.*]], [[BB7:%.*]] ], [ 0, [[BB1:%.*]] ] +; CHECK-NEXT: [[K2:%.*]] = phi i32 [ [[K3:%.*]], [[BB7:%.*]] ], [ 0, [[BB1:%.*]] ] ; CHECK-NEXT: [[KCOND:%.*]] = icmp slt i32 [[K2]], 100 ; CHECK-NEXT: br i1 [[KCOND]], label [[BB3:%.*]], label [[BB4:%.*]] ; CHECK: BB3: -; CHECK-NEXT: br i1 true, label [[BB5:%.*]], label [[BB6:%.*]] +; CHECK-NEXT: br label [[BB5:%.*]] ; CHECK: BB4: ; CHECK-NEXT: ret i32 1 ; CHECK: BB5: -; CHECK-NEXT: [[K3:%.*]] = add i32 [[K2]], 1 -; CHECK-NEXT: br label [[BB7]] -; CHECK: BB6: +; CHECK-NEXT: [[K3]] = add i32 [[K2]], 1 ; CHECK-NEXT: br label [[BB7]] ; CHECK: BB7: -; CHECK-NEXT: [[K4]] = phi i32 [ [[K3]], [[BB5]] ], [ undef, [[BB6]] ] ; CHECK-NEXT: br label [[BB2]] ; BB1: diff --git a/llvm/test/Transforms/SCCP/strictfp-phis-fcmp.ll b/llvm/test/Transforms/SCCP/strictfp-phis-fcmp.ll --- a/llvm/test/Transforms/SCCP/strictfp-phis-fcmp.ll +++ b/llvm/test/Transforms/SCCP/strictfp-phis-fcmp.ll @@ -223,8 +223,6 @@ ; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_TRUE:%.*]], label [[END:%.*]] ; CHECK: if.true: ; CHECK-NEXT: br label [[END]] -; CHECK: dead: -; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[C:%.*]] = call i1 @llvm.experimental.constrained.fcmp.f32(float 1.000000e+00, float 1.000000e+00, metadata !"une", metadata !"fpexcept.ignore") #[[ATTR0]] ; CHECK-NEXT: ret i1 [[C]] @@ -251,8 +249,6 @@ ; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_TRUE:%.*]], label [[END:%.*]] ; CHECK: if.true: ; CHECK-NEXT: br label [[END]] -; CHECK: dead: -; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[C:%.*]] = call i1 @llvm.experimental.constrained.fcmp.f32(float 1.000000e+00, float 1.000000e+00, metadata !"une", metadata !"fpexcept.maytrap") #[[ATTR0]] ; CHECK-NEXT: ret i1 [[C]] @@ -280,8 +276,6 @@ ; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_TRUE:%.*]], label [[END:%.*]] ; CHECK: if.true: ; CHECK-NEXT: br label [[END]] -; CHECK: dead: -; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[C:%.*]] = call i1 @llvm.experimental.constrained.fcmp.f32(float 1.000000e+00, float 1.000000e+00, metadata !"une", metadata !"fpexcept.strict") #[[ATTR0]] ; CHECK-NEXT: ret i1 [[C]] diff --git a/llvm/test/Transforms/SCCP/strictfp-phis-fcmps.ll b/llvm/test/Transforms/SCCP/strictfp-phis-fcmps.ll --- a/llvm/test/Transforms/SCCP/strictfp-phis-fcmps.ll +++ b/llvm/test/Transforms/SCCP/strictfp-phis-fcmps.ll @@ -223,8 +223,6 @@ ; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_TRUE:%.*]], label [[END:%.*]] ; CHECK: if.true: ; CHECK-NEXT: br label [[END]] -; CHECK: dead: -; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[C:%.*]] = call i1 @llvm.experimental.constrained.fcmps.f32(float 1.000000e+00, float 1.000000e+00, metadata !"une", metadata !"fpexcept.ignore") #[[ATTR0]] ; CHECK-NEXT: ret i1 [[C]] @@ -251,8 +249,6 @@ ; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_TRUE:%.*]], label [[END:%.*]] ; CHECK: if.true: ; CHECK-NEXT: br label [[END]] -; CHECK: dead: -; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[C:%.*]] = call i1 @llvm.experimental.constrained.fcmps.f32(float 1.000000e+00, float 1.000000e+00, metadata !"une", metadata !"fpexcept.maytrap") #[[ATTR0]] ; CHECK-NEXT: ret i1 [[C]] @@ -280,8 +276,6 @@ ; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_TRUE:%.*]], label [[END:%.*]] ; CHECK: if.true: ; CHECK-NEXT: br label [[END]] -; CHECK: dead: -; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: [[C:%.*]] = call i1 @llvm.experimental.constrained.fcmps.f32(float 1.000000e+00, float 1.000000e+00, metadata !"une", metadata !"fpexcept.strict") #[[ATTR0]] ; CHECK-NEXT: ret i1 [[C]] diff --git a/llvm/test/Transforms/SCCP/widening.ll b/llvm/test/Transforms/SCCP/widening.ll --- a/llvm/test/Transforms/SCCP/widening.ll +++ b/llvm/test/Transforms/SCCP/widening.ll @@ -195,11 +195,11 @@ ; SCCP: bb3: ; SCCP-NEXT: br label [[EXIT]] ; SCCP: exit: -; SCCP-NEXT: [[P:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 3, [[BB1]] ], [ 2, [[BB2]] ], [ 5, [[BB3]] ], [ [[A:%.*]], [[EXIT]] ] -; SCCP-NEXT: [[A]] = add i32 [[P]], 1 +; SCCP-NEXT: [[P:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 3, [[BB1]] ], [ 2, [[BB2]] ], [ 5, [[BB3]] ] +; SCCP-NEXT: [[A:%.*]] = add i32 [[P]], 1 ; SCCP-NEXT: call void @use(i1 true) ; SCCP-NEXT: call void @use(i1 false) -; SCCP-NEXT: br i1 false, label [[EXIT]], label [[EXIT_1:%.*]] +; SCCP-NEXT: br label [[EXIT_1:%.*]] ; SCCP: exit.1: ; SCCP-NEXT: ret void ; @@ -451,10 +451,10 @@ ; SCCP-NEXT: [[TMP7:%.*]] = sub i64 3, [[TMP6]] ; SCCP-NEXT: [[TMP8:%.*]] = shl i64 [[TMP7]], 1 ; SCCP-NEXT: [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32 -; SCCP-NEXT: [[TMP0:%.*]] = zext i32 [[TMP9]] to i64 +; SCCP-NEXT: [[TMP10:%.*]] = zext i32 [[TMP9]] to i64 ; SCCP-NEXT: br label [[BB11:%.*]] ; SCCP: bb11: -; SCCP-NEXT: [[TMP12:%.*]] = phi i64 [ [[TMP0]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ] +; SCCP-NEXT: [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ] ; SCCP-NEXT: br label [[BB13:%.*]] ; SCCP: bb13: ; SCCP-NEXT: [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6 @@ -489,10 +489,10 @@ ; IPSCCP-NEXT: [[TMP7:%.*]] = sub i64 3, [[TMP6]] ; IPSCCP-NEXT: [[TMP8:%.*]] = shl i64 [[TMP7]], 1 ; IPSCCP-NEXT: [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32 -; IPSCCP-NEXT: [[TMP0:%.*]] = zext i32 [[TMP9]] to i64 +; IPSCCP-NEXT: [[TMP10:%.*]] = zext i32 [[TMP9]] to i64 ; IPSCCP-NEXT: br label [[BB11:%.*]] ; IPSCCP: bb11: -; IPSCCP-NEXT: [[TMP12:%.*]] = phi i64 [ [[TMP0]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ] +; IPSCCP-NEXT: [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ] ; IPSCCP-NEXT: br label [[BB13:%.*]] ; IPSCCP: bb13: ; IPSCCP-NEXT: [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6