From d15cdb7b13fb7b274aeba4951e3eadec4072bce9 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Tue, 6 Oct 2015 21:44:49 +0000 Subject: [PATCH] [IndVars] Don't break dominance in `eliminateIdentitySCEV` Summary: After r249211, `getSCEV(X) == getSCEV(Y)` does not guarantee that X and Y are related in the dominator tree, even if X is an operand to Y (I've included a toy example in comments, and a real example as a test case). This commit changes `SimplifyIndVar` to require a `DominatorTree`. I don't think this is a problem because `ScalarEvolution` requires it anyway. Fixes PR25051. Depends on D13459. Reviewers: atrick, hfinkel Subscribers: joker.eph, llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D13460 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@249471 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/SimplifyIndVar.h | 9 +++--- lib/Transforms/Scalar/IndVarSimplify.cpp | 2 +- lib/Transforms/Utils/LoopUnroll.cpp | 2 +- lib/Transforms/Utils/SimplifyIndVar.cpp | 42 ++++++++++++++++++------ test/Transforms/IndVarSimplify/pr25051.ll | 44 ++++++++++++++++++++++++++ 5 files changed, 84 insertions(+), 15 deletions(-) create mode 100644 test/Transforms/IndVarSimplify/pr25051.ll diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index dcb1d67cbf7..8a6eba74ecc 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -57,13 +57,14 @@ public: /// simplifyUsersOfIV - Simplify instructions that use this induction variable /// by using ScalarEvolution to analyze the IV's recurrence. -bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM, - SmallVectorImpl &Dead, IVVisitor *V = nullptr); +bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, + LPPassManager *LPM, SmallVectorImpl &Dead, + IVVisitor *V = nullptr); /// SimplifyLoopIVs - Simplify users of induction variables within this /// loop. This does not actually change or add IVs. -bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM, - SmallVectorImpl &Dead); +bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, + LPPassManager *LPM, SmallVectorImpl &Dead); } // namespace llvm diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 2f295fedf05..0062ce5517d 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1395,7 +1395,7 @@ void IndVarSimplify::SimplifyAndExtend(Loop *L, // Information about sign/zero extensions of CurrIV. IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT); - Changed |= simplifyUsersOfIV(CurrIV, SE, &LPM, DeadInsts, &Visitor); + Changed |= simplifyUsersOfIV(CurrIV, SE, DT, &LPM, DeadInsts, &Visitor); if (Visitor.WI.WidestNativeType) { WideIVs.push_back(Visitor.WI); diff --git a/lib/Transforms/Utils/LoopUnroll.cpp b/lib/Transforms/Utils/LoopUnroll.cpp index 95d31d86644..b7e248860c5 100644 --- a/lib/Transforms/Utils/LoopUnroll.cpp +++ b/lib/Transforms/Utils/LoopUnroll.cpp @@ -499,7 +499,7 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, // Simplify any new induction variables in the partially unrolled loop. if (SE && !CompletelyUnroll) { SmallVector DeadInsts; - simplifyLoopIVs(L, SE, LPM, DeadInsts); + simplifyLoopIVs(L, SE, DT, LPM, DeadInsts); // Aggressively clean up dead instructions that simplifyLoopIVs already // identified. Any remaining should be cleaned up below. diff --git a/lib/Transforms/Utils/SimplifyIndVar.cpp b/lib/Transforms/Utils/SimplifyIndVar.cpp index b85dd5d5f9d..c7ec1bc263d 100644 --- a/lib/Transforms/Utils/SimplifyIndVar.cpp +++ b/lib/Transforms/Utils/SimplifyIndVar.cpp @@ -47,15 +47,16 @@ namespace { Loop *L; LoopInfo *LI; ScalarEvolution *SE; + DominatorTree *DT; SmallVectorImpl &DeadInsts; bool Changed; public: - SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LoopInfo *LI, - SmallVectorImpl &Dead) - : L(Loop), LI(LI), SE(SE), DeadInsts(Dead), Changed(false) { + SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT, + LoopInfo *LI,SmallVectorImpl &Dead) + : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) { assert(LI && "IV simplification requires LoopInfo"); } @@ -310,6 +311,28 @@ bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst, (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand))) return false; + // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the + // dominator tree, even if X is an operand to Y. For instance, in + // + // %iv = phi i32 {0,+,1} + // br %cond, label %left, label %merge + // + // left: + // %X = add i32 %iv, 0 + // br label %merge + // + // merge: + // %M = phi (%X, %iv) + // + // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and + // %M.replaceAllUsesWith(%X) would be incorrect. + + if (isa(UseInst)) + // If UseInst is not a PHI node then we know that IVOperand dominates + // UseInst directly from the legality of SSA. + if (!DT || !DT->dominates(IVOperand, UseInst)) + return false; + DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n'); UseInst->replaceAllUsesWith(IVOperand); @@ -568,22 +591,23 @@ void IVVisitor::anchor() { } /// Simplify instructions that use this induction variable /// by using ScalarEvolution to analyze the IV's recurrence. -bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM, - SmallVectorImpl &Dead, IVVisitor *V) +bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, + LPPassManager *LPM, SmallVectorImpl &Dead, IVVisitor *V) { LoopInfo *LI = &LPM->getAnalysis().getLoopInfo(); - SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LI, Dead); + + SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, Dead); SIV.simplifyUsers(CurrIV, V); return SIV.hasChanged(); } /// Simplify users of induction variables within this /// loop. This does not actually change or add IVs. -bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM, - SmallVectorImpl &Dead) { +bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, + LPPassManager *LPM, SmallVectorImpl &Dead) { bool Changed = false; for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { - Changed |= simplifyUsersOfIV(cast(I), SE, LPM, Dead); + Changed |= simplifyUsersOfIV(cast(I), SE, DT, LPM, Dead); } return Changed; } diff --git a/test/Transforms/IndVarSimplify/pr25051.ll b/test/Transforms/IndVarSimplify/pr25051.ll new file mode 100644 index 00000000000..a02d539a66d --- /dev/null +++ b/test/Transforms/IndVarSimplify/pr25051.ll @@ -0,0 +1,44 @@ +; RUN: opt -S -indvars < %s | FileCheck %s + +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-apple-macosx10.11.0" + +define i32 @somefunc(double* %arr) { +; CHECK-LABEL: @somefunc( +entry: + br label %for.cond.1.preheader + +for.cond.1.preheader: ; preds = %for.inc.9, %entry + %index3.013 = phi i32 [ 0, %entry ], [ %index3.1.lcssa, %for.inc.9 ] + %index.012 = phi i32 [ 0, %entry ], [ %inc10, %for.inc.9 ] + %cmp2.9 = icmp sgt i32 %index.012, 0 + br i1 %cmp2.9, label %for.body.3.lr.ph, label %for.inc.9 + +for.body.3.lr.ph: ; preds = %for.cond.1.preheader + %idxprom5 = sext i32 %index.012 to i64 + br label %for.body.3 + +for.body.3: ; preds = %for.body.3, %for.body.3.lr.ph + %index3.111 = phi i32 [ %index3.013, %for.body.3.lr.ph ], [ %inc, %for.body.3 ] + %index2.010 = phi i32 [ 0, %for.body.3.lr.ph ], [ %inc8, %for.body.3 ] + %inc = add nsw i32 %index3.111, 1 + %idxprom = sext i32 %index3.111 to i64 + %arrayidx = getelementptr inbounds double, double* %arr, i64 %idxprom + %idxprom4 = sext i32 %index2.010 to i64 + %inc8 = add nsw i32 %index2.010, 1 + %cmp2 = icmp slt i32 %inc8, %index.012 + br i1 %cmp2, label %for.body.3, label %for.inc.9.loopexit + +for.inc.9.loopexit: ; preds = %for.body.3 + %inc.lcssa = phi i32 [ %inc, %for.body.3 ] + br label %for.inc.9 + +for.inc.9: ; preds = %for.inc.9.loopexit, %for.cond.1.preheader + %index3.1.lcssa = phi i32 [ %index3.013, %for.cond.1.preheader ], [ %inc.lcssa, %for.inc.9.loopexit ] + %inc10 = add nsw i32 %index.012, 1 + %cmp = icmp slt i32 %inc10, 10 + br i1 %cmp, label %for.cond.1.preheader, label %for.end.11 + +for.end.11: ; preds = %for.inc.9 + ret i32 1 +} -- 2.11.0