SCEVExpander fixes. Affects LSR and indvars.

LSR has gradually been improved to more aggressively reuse existing code, particularly existing phi cycles. This exposed problems with the SCEVExpander's sloppy treatment of its insertion point. I applied some rigor to the insertion point problem that will hopefully avoid an endless bug cycle in this area. Changes:

- Always used properlyDominates to check safe code hoisting.

- The insertion point provided to SCEV is now considered a lower bound. This is usually a block terminator or the use itself. Under no cirumstance may SCEVExpander insert below this point.

- LSR is reponsible for finding a "canonical" insertion point across expansion of different expressions.

- Robust logic to determine whether IV increments are in "expanded" form and/or can be safely hoisted above some insertion point.

Fixes PR11783: SCEVExpander assert.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148535 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 114 insertions, 115 deletions

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index e2f75aa0ea..0f7475673a 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -38,8 +38,11 @@ Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
     if (U->getType() == Ty)
       if (CastInst *CI = dyn_cast<CastInst>(U))
         if (CI->getOpcode() == Op) {
-          // If the cast isn't where we want it, fix it.
-          if (BasicBlock::iterator(CI) != IP) {
+          // If the cast isn't where we want it, fix it. All new or reused
+          // instructions must strictly dominate the Builder's InsertPt to
+          // ensure that the expression's expansion dominates its uses.
+          if (BasicBlock::iterator(CI) != IP
+              || IP == Builder.GetInsertPoint()) {
             // Create a new cast, and leave the old cast in place in case
             // it is being used as an insert point. Clear its operand
             // so that it doesn't hold anything live.
@@ -867,61 +870,108 @@ bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
   return isNormalAddRecExprPHI(PN, IncV, L);
 }
 
-/// Determine if this cyclic phi is in a form that would have been generated by
-/// LSR. We don't care if the phi was actually expanded in this pass, as long
-/// as it is in a low-cost form, for example, no implied multiplication. This
-/// should match any patterns generated by getAddRecExprPHILiterally and
-/// expandAddtoGEP.
-bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
-                                           const Loop *L) {
-  if (ChainedPhis.count(PN))
-    return true;
+/// getIVIncOperand returns an induction variable increment's induction
+/// variable operand.
+///
+/// If allowScale is set, any type of GEP is allowed as long as the nonIV
+/// operands dominate InsertPos.
+///
+/// If allowScale is not set, ensure that a GEP increment conforms to one of the
+/// simple patterns generated by getAddRecExprPHILiterally and
+/// expandAddtoGEP. If the pattern isn't recognized, return NULL.
+Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
+                                           Instruction *InsertPos,
+                                           bool allowScale) {
+  if (IncV == InsertPos)
+    return NULL;
 
   switch (IncV->getOpcode()) {
+  default:
+    return NULL;
   // Check for a simple Add/Sub or GEP of a loop invariant step.
   case Instruction::Add:
-  case Instruction::Sub:
-    return IncV->getOperand(0) == PN
-      && L->isLoopInvariant(IncV->getOperand(1));
+  case Instruction::Sub: {
+    Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
+    if (!OInst || SE.DT->properlyDominates(OInst, InsertPos))
+      return dyn_cast<Instruction>(IncV->getOperand(0));
+    return NULL;
+  }
   case Instruction::BitCast:
-    IncV = dyn_cast<GetElementPtrInst>(IncV->getOperand(0));
-    if (!IncV)
-      return false;
-    // fall-thru to GEP handling
-  case Instruction::GetElementPtr: {
-    // This must be a pointer addition of constants (pretty) or some number of
-    // address-size elements (ugly).
+    return dyn_cast<Instruction>(IncV->getOperand(0));
+  case Instruction::GetElementPtr:
     for (Instruction::op_iterator I = IncV->op_begin()+1, E = IncV->op_end();
          I != E; ++I) {
       if (isa<Constant>(*I))
         continue;
-      // ugly geps have 2 operands.
-      // i1* is used by the expander to represent an address-size element.
+      if (Instruction *OInst = dyn_cast<Instruction>(*I)) {
+        if (!SE.DT->properlyDominates(OInst, InsertPos))
+          return NULL;
+      }
+      if (allowScale) {
+        // allow any kind of GEP as long as it can be hoisted.
+        continue;
+      }
+      // This must be a pointer addition of constants (pretty), which is already
+      // handled, or some number of address-size elements (ugly). Ugly geps
+      // have 2 operands. i1* is used by the expander to represent an
+      // address-size element.
       if (IncV->getNumOperands() != 2)
-        return false;
+        return NULL;
       unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
       if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
           && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
-        return false;
-      // Ensure the operands dominate the insertion point. I don't know of a
-      // case when this would not be true, so this is somewhat untested.
-      if (L == IVIncInsertLoop) {
-        for (User::op_iterator OI = IncV->op_begin()+1,
-               OE = IncV->op_end(); OI != OE; ++OI)
-          if (Instruction *OInst = dyn_cast<Instruction>(OI))
-            if (!SE.DT->dominates(OInst, IVIncInsertPos))
-              return false;
-      }
+        return NULL;
       break;
     }
-    IncV = dyn_cast<Instruction>(IncV->getOperand(0));
-    if (IncV && IncV->getOpcode() == Instruction::BitCast)
-      IncV = dyn_cast<Instruction>(IncV->getOperand(0));
-    return IncV == PN;
+    return dyn_cast<Instruction>(IncV->getOperand(0));
   }
-  default:
+}
+
+/// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
+/// it available to other uses in this loop. Recursively hoist any operands,
+/// until we reach a value that dominates InsertPos.
+bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
+  if (SE.DT->properlyDominates(IncV, InsertPos))
+      return true;
+
+  // InsertPos must itself dominate IncV so that IncV's new position satisfies
+  // its existing users.
+  if (!SE.DT->dominates(InsertPos->getParent(), IncV->getParent()))
     return false;
+
+  // Check that the chain of IV operands leading back to Phi can be hoisted.
+  SmallVector<Instruction*, 4> IVIncs;
+  for(;;) {
+    Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
+    if (!Oper)
+      return false;
+    // IncV is safe to hoist.
+    IVIncs.push_back(IncV);
+    IncV = Oper;
+    if (SE.DT->properlyDominates(IncV, InsertPos))
+      break;
+  }
+  for (SmallVectorImpl<Instruction*>::reverse_iterator I = IVIncs.rbegin(),
+         E = IVIncs.rend(); I != E; ++I) {
+    (*I)->moveBefore(InsertPos);
+  }
+  return true;
+}
+
+/// Determine if this cyclic phi is in a form that would have been generated by
+/// LSR. We don't care if the phi was actually expanded in this pass, as long
+/// as it is in a low-cost form, for example, no implied multiplication. This
+/// should match any patterns generated by getAddRecExprPHILiterally and
+/// expandAddtoGEP.
+bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
+                                           const Loop *L) {
+  for(Instruction *IVOper = IncV;
+      (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
+                                /*allowScale=*/false));) {
+    if (IVOper == PN)
+      return true;
   }
+  return false;
 }
 
 /// expandIVInc - Expand an IV increment at Builder's current InsertPos.
@@ -981,26 +1031,28 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
       if (LSRMode) {
         if (!isExpandedAddRecExprPHI(PN, IncV, L))
           continue;
+        if (L == IVIncInsertLoop && !hoistIVInc(IncV, IVIncInsertPos))
+          continue;
       }
       else {
         if (!isNormalAddRecExprPHI(PN, IncV, L))
           continue;
+        if (L == IVIncInsertLoop)
+          do {
+            if (SE.DT->dominates(IncV, IVIncInsertPos))
+              break;
+            // Make sure the increment is where we want it. But don't move it
+            // down past a potential existing post-inc user.
+            IncV->moveBefore(IVIncInsertPos);
+            IVIncInsertPos = IncV;
+            IncV = cast<Instruction>(IncV->getOperand(0));
+          } while (IncV != PN);
       }
       // Ok, the add recurrence looks usable.
       // Remember this PHI, even in post-inc mode.
       InsertedValues.insert(PN);
       // Remember the increment.
       rememberInstruction(IncV);
-      if (L == IVIncInsertLoop)
-        do {
-          if (SE.DT->dominates(IncV, IVIncInsertPos))
-            break;
-          // Make sure the increment is where we want it. But don't move it
-          // down past a potential existing post-inc user.
-          IncV->moveBefore(IVIncInsertPos);
-          IVIncInsertPos = IncV;
-          IncV = cast<Instruction>(IncV->getOperand(0));
-        } while (IncV != PN);
       return PN;
     }
   }
@@ -1404,10 +1456,7 @@ Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
 }
 
 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,
-                                   Instruction *I) {
-  BasicBlock::iterator IP = I;
-  while (isInsertedInstruction(IP) || isa<DbgInfoIntrinsic>(IP))
-    ++IP;
+                                   Instruction *IP) {
   Builder.SetInsertPoint(IP->getParent(), IP);
   return expandCodeFor(SH, Ty);
 }
@@ -1445,8 +1494,11 @@ Value *SCEVExpander::expand(const SCEV *S) {
       // there) so that it is guaranteed to dominate any user inside the loop.
       if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
         InsertPt = L->getHeader()->getFirstInsertionPt();
-      while (isInsertedInstruction(InsertPt) || isa<DbgInfoIntrinsic>(InsertPt))
+      while (InsertPt != Builder.GetInsertPoint()
+             && (isInsertedInstruction(InsertPt)
+                 || isa<DbgInfoIntrinsic>(InsertPt))) {
         InsertPt = llvm::next(BasicBlock::iterator(InsertPt));
+      }
       break;
     }
 
@@ -1481,23 +1533,9 @@ void SCEVExpander::rememberInstruction(Value *I) {
     InsertedPostIncValues.insert(I);
   else
     InsertedValues.insert(I);
-
-  // If we just claimed an existing instruction and that instruction had
-  // been the insert point, adjust the insert point forward so that
-  // subsequently inserted code will be dominated.
-  if (Builder.GetInsertPoint() == I) {
-    BasicBlock::iterator It = cast<Instruction>(I);
-    do { ++It; } while (isInsertedInstruction(It) ||
-                        isa<DbgInfoIntrinsic>(It));
-    Builder.SetInsertPoint(Builder.GetInsertBlock(), It);
-  }
 }
 
 void SCEVExpander::restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I) {
-  // If we acquired more instructions since the old insert point was saved,
-  // advance past them.
-  while (isInsertedInstruction(I) || isa<DbgInfoIntrinsic>(I)) ++I;
-
   Builder.SetInsertPoint(BB, I);
 }
 
@@ -1525,49 +1563,6 @@ SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
   return V;
 }
 
-/// hoistStep - Attempt to hoist an IV increment above a potential use.
-///
-/// To successfully hoist, two criteria must be met:
-/// - IncV operands dominate InsertPos and
-/// - InsertPos dominates IncV
-///
-/// Meeting the second condition means that we don't need to check all of IncV's
-/// existing uses (it's moving up in the domtree).
-///
-/// This does not yet recursively hoist the operands, although that would
-/// not be difficult.
-///
-/// This does not require a SCEVExpander instance and could be replaced by a
-/// general code-insertion helper.
-bool SCEVExpander::hoistStep(Instruction *IncV, Instruction *InsertPos,
-                             const DominatorTree *DT) {
-  // Phi nodes are strangely positional but don't follow normal rules for
-  // instruction dominance. Handle them immediately.
-  if (isa<PHINode>(InsertPos))
-    return isa<PHINode>(IncV);
-  else if (isa<PHINode>(IncV))
-    return false;
-
-  if (DT->dominates(IncV, InsertPos))
-    return true;
-
-  if (!DT->dominates(InsertPos->getParent(), IncV->getParent()))
-    return false;
-
-  if (IncV->mayHaveSideEffects())
-    return false;
-
-  // Attempt to hoist IncV
-  for (User::op_iterator OI = IncV->op_begin(), OE = IncV->op_end();
-       OI != OE; ++OI) {
-    Instruction *OInst = dyn_cast<Instruction>(OI);
-    if (OInst && (OInst == InsertPos || !DT->dominates(OInst, InsertPos)))
-      return false;
-  }
-  IncV->moveBefore(InsertPos);
-  return true;
-}
-
 /// Sort values by integer width for replaceCongruentIVs.
 static bool width_descending(Value *lhs, Value *rhs) {
   // Put pointers at the back and make sure pointer < pointer = false.
@@ -1632,10 +1627,13 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
         cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
 
       // If this phi has the same width but is more canonical, replace the
-      // original with it.
+      // original with it. As part of the "more canonical" determination,
+      // respect a prior decision to use an IV chain.
       if (OrigPhiRef->getType() == Phi->getType()
-          && !isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)
-          && isExpandedAddRecExprPHI(Phi, IsomorphicInc, L)) {
+          && !(ChainedPhis.count(Phi)
+               || isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L))
+          && (ChainedPhis.count(Phi)
+              || isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
         std::swap(OrigPhiRef, Phi);
         std::swap(OrigInc, IsomorphicInc);
       }
@@ -1649,7 +1647,8 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
                                                    IsomorphicInc->getType());
       if (OrigInc != IsomorphicInc
           && TruncExpr == SE.getSCEV(IsomorphicInc)
-          && hoistStep(OrigInc, IsomorphicInc, DT)) {
+          && ((isa<PHINode>(OrigInc) && isa<PHINode>(IsomorphicInc))
+              || hoistIVInc(OrigInc, IsomorphicInc))) {
         DEBUG_WITH_TYPE(DebugType, dbgs()
                         << "INDVARS: Eliminated congruent iv.inc: "
                         << *IsomorphicInc << '\n');