[IndVarSimplify] Simplify code using preheader assumption

As noted in the nice block comment, the previous code didn't actually handle multi-entry loops correctly, it just assumed SCEV didn't analyze such loops.  Given SCEV has comments to the contrary, that seems a bit suspect.  More importantly, the pass actually requires loopsimplify form which ensures a loop-preheader is available.  Remove the excessive generaility and shorten the code greatly.

Note that we do successfully analyze many multi-entry loops, but we do so by converting them to single entry loops.  See the added test case.

llvm-svn: 316976

1 files changed, 6 insertions, 44 deletions

diff --git a/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp b/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
index c39e7861c50..bceb02a3c21 100644
--- a/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
@@ -182,7 +182,8 @@ bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
   ICmpInst::Predicate InvariantPredicate;
   const SCEV *InvariantLHS, *InvariantRHS;
 
-  if (!isa<PHINode>(IVOperand))
+  auto *PN = dyn_cast<PHINode>(IVOperand);
+  if (!PN)
     return false;
   if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,
                                     InvariantLHS, InvariantRHS))
@@ -202,49 +203,10 @@ bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
     NewRHS =
       ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx));
 
-  auto *PN = cast<PHINode>(IVOperand);
-  for (unsigned i = 0, e = PN->getNumIncomingValues();
-       i != e && (!NewLHS || !NewRHS);
-       ++i) {
-
-    // If this is a value incoming from the backedge, then it cannot be a loop
-    // invariant value (since we know that IVOperand is an induction variable).
-    if (L->contains(PN->getIncomingBlock(i)))
-      continue;
-
-    // NB! This following assert does not fundamentally have to be true, but
-    // it is true today given how SCEV analyzes induction variables.
-    // Specifically, today SCEV will *not* recognize %iv as an induction
-    // variable in the following case:
-    //
-    // define void @f(i32 %k) {
-    // entry:
-    //   br i1 undef, label %r, label %l
-    //
-    // l:
-    //   %k.inc.l = add i32 %k, 1
-    //   br label %loop
-    //
-    // r:
-    //   %k.inc.r = add i32 %k, 1
-    //   br label %loop
-    //
-    // loop:
-    //   %iv = phi i32 [ %k.inc.l, %l ], [ %k.inc.r, %r ], [ %iv.inc, %loop ]
-    //   %iv.inc = add i32 %iv, 1
-    //   br label %loop
-    // }
-    //
-    // but if it starts to, at some point, then the assertion below will have
-    // to be changed to a runtime check.
-
-    Value *Incoming = PN->getIncomingValue(i);
-
-#ifndef NDEBUG
-    if (auto *I = dyn_cast<Instruction>(Incoming))
-      assert(DT->dominates(I, ICmp) && "Should be a unique loop dominating value!");
-#endif
-
+  // TODO: Support multiple entry loops?  (We currently bail out of these in
+  // the IndVarSimplify pass)
+  if (auto *BB = L->getLoopPredecessor()) {
+    Value *Incoming = PN->getIncomingValue(PN->getBasicBlockIndex(BB));
     const SCEV *IncomingS = SE->getSCEV(Incoming);
 
     if (!NewLHS && IncomingS == InvariantLHS)