[IndVars] Don't break dominance in `eliminateIdentitySCEV`

[sanjoy]

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.

[mehdi_amini]

lib/Transforms/Utils/SimplifyIndVar.cpp

328 ↗

(On Diff #36591)

Not sure if it is related, but about live-out value for loops, if the exit value is the same you could RAUW uses that are outside of the loop. Does it mean that we will pessimize this case? Is it handled somewhere else?

[sanjoy]

lib/Transforms/Utils/SimplifyIndVar.cpp

328 ↗

(On Diff #36591)

I'm not a 100% sure I understand what you mean, but RewriteLoopExitValues runs /after/ the induction variables have been simplified.

If you're concerned about breaking LCSSA, then see D13461. :)

[sanjoy]

I decided to check this in and switch to a post-commit review for the following reasons:

• The fix itself is fairly simple and low-risk
• People were blocked on getting this fix in
• I didn't want to mess up the history with revert / un-revert commits

llvm/trunk/include/llvm/Transforms/Utils/SimplifyIndVar.h

void setSplitOverflowIntrinsics() {
     assert(DT && "Splitting overflow intrinsics requires a DomTree.");
   }
 
   virtual void visitCast(CastInst *Cast) = 0;
 };
 
 /// 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<WeakVH> &Dead, IVVisitor *V = nullptr);
+bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
+                       LPPassManager *LPM, SmallVectorImpl<WeakVH> &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<WeakVH> &Dead);
+bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
+                     LPPassManager *LPM, SmallVectorImpl<WeakVH> &Dead);
 
 } // namespace llvm
 
 #endif

llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp

while (!LoopPhis.empty()) {
     // evaluation of sign/zero extend evaluation until needed, and avoid running
     // other SCEV based analysis prior to SimplifyAndExtend.
     do {
       PHINode *CurrIV = LoopPhis.pop_back_val();
 
       // 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);
       }
     } while(!LoopPhis.empty());
 
     for (; !WideIVs.empty(); WideIVs.pop_back()) {
       WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts);

llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp

if (DominatorTreeWrapperPass *DTWP =
             PP->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
       DT = &DTWP->getDomTree();
       DT->recalculate(*L->getHeader()->getParent());
     }
 
     // Simplify any new induction variables in the partially unrolled loop.
     if (SE && !CompletelyUnroll) {
       SmallVector<WeakVH, 16> 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.
       while (!DeadInsts.empty())
         if (Instruction *Inst =
             dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
           RecursivelyDeleteTriviallyDeadInstructions(Inst);
     }

llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp

namespace {
   /// This is a utility for simplifying induction variables
   /// based on ScalarEvolution. It is the primary instrument of the
   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
   /// other loop passes that preserve SCEV.
   class SimplifyIndvar {
     Loop             *L;
     LoopInfo         *LI;
     ScalarEvolution  *SE;
+    DominatorTree    *DT;
 
     SmallVectorImpl<WeakVH> &DeadInsts;
 
     bool Changed;
 
   public:
-    SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LoopInfo *LI,
-                   SmallVectorImpl<WeakVH> &Dead)
-        : L(Loop), LI(LI), SE(SE), DeadInsts(Dead), Changed(false) {
+    SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
+                   LoopInfo *LI,SmallVectorImpl<WeakVH> &Dead)
+        : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) {
       assert(LI && "IV simplification requires LoopInfo");
     }
 
     bool hasChanged() const { return Changed; }
 
     /// Iteratively perform simplification on a worklist of users of the
     /// specified induction variable. This is the top-level driver that applies
     /// all simplifications to users of an IV.

 /// Eliminate any operation that SCEV can prove is an identity function.
 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
                                            Instruction *IVOperand) {
   if (!SE->isSCEVable(UseInst->getType()) ||
       (UseInst->getType() != IVOperand->getType()) ||
       (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<PHINode>(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);
   ++NumElimIdentity;
   Changed = true;
   DeadInsts.emplace_back(UseInst);
   return true;
 }

 }
 
 namespace llvm {
 
 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<WeakVH> &Dead, IVVisitor *V)
+bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
+                       LPPassManager *LPM, SmallVectorImpl<WeakVH> &Dead, IVVisitor *V)
 {
   LoopInfo *LI = &LPM->getAnalysis<LoopInfoWrapperPass>().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<WeakVH> &Dead) {
+bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
+                     LPPassManager *LPM, SmallVectorImpl<WeakVH> &Dead) {
   bool Changed = false;
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
-    Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, LPM, Dead);
+    Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LPM, Dead);
   }
   return Changed;
 }
 
 } // namespace llvm

llvm/trunk/test/Transforms/IndVarSimplify/pr25051.ll

+; 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
+}