Index: include/llvm/Transforms/Utils/SimplifyIndVar.h =================================================================== --- include/llvm/Transforms/Utils/SimplifyIndVar.h +++ include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -57,13 +57,14 @@ /// 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 Index: lib/Transforms/Scalar/IndVarSimplify.cpp =================================================================== --- lib/Transforms/Scalar/IndVarSimplify.cpp +++ lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1395,7 +1395,7 @@ // 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); Index: lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- lib/Transforms/Utils/LoopUnroll.cpp +++ lib/Transforms/Utils/LoopUnroll.cpp @@ -499,7 +499,7 @@ // 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. Index: lib/Transforms/Utils/SimplifyIndVar.cpp =================================================================== --- lib/Transforms/Utils/SimplifyIndVar.cpp +++ lib/Transforms/Utils/SimplifyIndVar.cpp @@ -47,15 +47,16 @@ 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,25 @@ (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 (!DT || !DT->dominates(IVOperand, UseInst)) + return false; + DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n'); UseInst->replaceAllUsesWith(IVOperand); @@ -568,22 +588,23 @@ /// 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; } Index: test/Transforms/IndVarSimplify/pr25051.ll =================================================================== --- /dev/null +++ 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 +}