diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1573,6 +1573,8 @@
   /// We know that there is no SCEV for the specified value.  Analyze the
   /// expression.
   const SCEV *createSCEV(Value *V);
+  const SCEV *createSCEVIter(Value *V);
+  void getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
 
   /// Provide the special handling we need to analyze PHI SCEVs.
   const SCEV *createNodeForPHI(PHINode *PN);
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -4324,18 +4324,9 @@
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
-  const SCEV *S = getExistingSCEV(V);
-  if (S == nullptr) {
-    S = createSCEV(V);
-    // During PHI resolution, it is possible to create two SCEVs for the same
-    // V, so it is needed to double check whether V->S is inserted into
-    // ValueExprMap before insert S->{V, 0} into ExprValueMap.
-    std::pair<ValueExprMapType::iterator, bool> Pair =
-        ValueExprMap.insert({SCEVCallbackVH(V, this), S});
-    if (Pair.second)
-      ExprValueMap[S].insert(V);
-  }
-  return S;
+  if (const SCEV *S = getExistingSCEV(V))
+    return S;
+  return createSCEVIter(V);
 }
 
 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
@@ -5495,10 +5486,13 @@
     return nullptr;
 
   const SCEV *Accum = nullptr;
-  if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
+  if (BO->LHS == PN && L->isLoopInvariant(BO->RHS)) {
     Accum = getSCEV(BO->RHS);
-  else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
+    assert(Accum);
+  } else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS)) {
     Accum = getSCEV(BO->LHS);
+    assert(Accum);
+  }
 
   if (!Accum)
     return nullptr;
@@ -5509,7 +5503,7 @@
   if (BO->IsNSW)
     Flags = setFlags(Flags, SCEV::FlagNSW);
 
-  const SCEV *StartVal = getSCEV(StartValueV);
+  const SCEV *StartVal = getExistingSCEV(StartValueV);
   const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
   insertValueToMap(PN, PHISCEV);
 
@@ -5526,10 +5520,10 @@
   return PHISCEV;
 }
 
-const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
-  const Loop *L = LI.getLoopFor(PN->getParent());
+static std::pair<Value *, Value *> classifyPhiValues(PHINode *PN,
+                                                     const Loop *L) {
   if (!L || L->getHeader() != PN->getParent())
-    return nullptr;
+    return {nullptr, nullptr};
 
   // The loop may have multiple entrances or multiple exits; we can analyze
   // this phi as an addrec if it has a unique entry value and a unique
@@ -5551,6 +5545,13 @@
       break;
     }
   }
+  return {StartValueV, BEValueV};
+}
+
+const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
+  const Loop *L = LI.getLoopFor(PN->getParent());
+  Value *BEValueV, *StartValueV;
+  std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L);
   if (!BEValueV || !StartValueV)
     return nullptr;
 
@@ -5799,11 +5800,12 @@
   return false;
 }
 
-const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
+static BranchInst *getSelectPhiBr(PHINode *PN, const Loop *L, DominatorTree &DT,
+                                  LoopInfo &LI) {
   auto IsReachable =
       [&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); };
+
   if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {
-    const Loop *L = LI.getLoopFor(PN->getParent());
 
     // We don't want to break LCSSA, even in a SCEV expression tree.
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
@@ -5825,15 +5827,19 @@
     BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();
     assert(IDom && "At least the entry block should dominate PN");
 
-    auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
-    Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
-
-    if (BI && BI->isConditional() &&
-        BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&
-        IsAvailableOnEntry(L, DT, getSCEV(LHS), PN->getParent()) &&
-        IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent()))
-      return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
+    return dyn_cast<BranchInst>(IDom->getTerminator());
   }
+  return nullptr;
+}
+
+const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
+  const Loop *L = LI.getLoopFor(PN->getParent());
+  BranchInst *BI = getSelectPhiBr(PN, L, DT, LI);
+  Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+  if (BI && BI->isConditional() && BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&
+      IsAvailableOnEntry(L, DT, getSCEV(LHS), PN->getParent()) &&
+      IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent()))
+    return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
 
   return nullptr;
 }
@@ -5916,6 +5922,7 @@
     // a > b ? b+x : a+x  ->  min(a, b)+x
     if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {
       bool Signed = ICI->isSigned();
+      // TODO: Use getExistingSCEV!
       const SCEV *LA = getSCEV(TrueVal);
       const SCEV *RA = getSCEV(FalseVal);
       const SCEV *LS = getSCEV(LHS);
@@ -7079,6 +7086,185 @@
   return isFinite(L) || (isMustProgress(L) && loopHasNoSideEffects(L));
 }
 
+const SCEV *ScalarEvolution::createSCEVIter(Value *V) {
+  SmallVector<std::pair<Value *, bool>> Stack;
+  SmallVector<Value *> Worklist;
+  SmallPtrSet<Value *, 8> Visited;
+
+  Stack.emplace_back(V, true);
+  Stack.emplace_back(V, false);
+  while (!Stack.empty()) {
+    std::pair<Value *, bool> E = Stack.pop_back_val();
+    if (E.second) {
+      auto *S = getExistingSCEV(E.first);
+      if (!S) {
+        S = createSCEV(E.first);
+        // During PHI resolution, it is possible to create two SCEVs for the
+        // same V, so it is needed to double check whether V->S is inserted into
+        // ValueExprMap before insert S->{V, 0} into ExprValueMap.
+        std::pair<ValueExprMapType::iterator, bool> Pair =
+            ValueExprMap.insert({SCEVCallbackVH(E.first, this), S});
+        if (Pair.second)
+          ExprValueMap[S].insert(E.first);
+      }
+    } else {
+      if (!Visited.insert(E.first).second || getExistingSCEV(E.first))
+        continue;
+      SmallVector<Value *> Ops;
+      getOperandsToCreate(E.first, Ops);
+      Stack.emplace_back(E.first, true);
+      for (Value *Op : Ops) {
+        Stack.emplace_back(Op, false);
+      }
+    }
+  }
+
+  return getExistingSCEV(V);
+}
+void ScalarEvolution::getOperandsToCreate(Value *V,
+                                          SmallVectorImpl<Value *> &Ops) {
+  if (!isSCEVable(V->getType()))
+    return;
+
+  if (Instruction *I = dyn_cast<Instruction>(V)) {
+    // Don't attempt to analyze instructions in blocks that aren't
+    // reachable. Such instructions don't matter, and they aren't required
+    // to obey basic rules for definitions dominating uses which this
+    // analysis depends on.
+    if (!DT.isReachableFromEntry(I->getParent()))
+      return;
+  } else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+    return;
+  else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
+    if (!GA->isInterposable())
+      Ops.push_back(GA->getAliasee());
+    return;
+  } else if (!isa<ConstantExpr>(V))
+    return;
+
+  Operator *U = cast<Operator>(V);
+  if (auto BO = MatchBinaryOp(U, DT)) {
+    Ops.push_back(BO->LHS);
+    Ops.push_back(BO->RHS);
+    return;
+  }
+
+  switch (U->getOpcode()) {
+  case Instruction::Trunc:
+  case Instruction::ZExt:
+  case Instruction::SExt:
+  case Instruction::PtrToInt:
+    Ops.push_back(U->getOperand(0));
+    return;
+
+  case Instruction::BitCast:
+    if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) {
+      Ops.push_back(U->getOperand(0));
+      return;
+    }
+    break;
+
+  case Instruction::SDiv:
+  case Instruction::SRem:
+    Ops.push_back(U->getOperand(0));
+    Ops.push_back(U->getOperand(1));
+    return;
+
+  case Instruction::GetElementPtr:
+    if (cast<GEPOperator>(U)->getSourceElementType()->isSized()) {
+      for (Value *Index : U->operands())
+        Ops.push_back(Index);
+    }
+    return;
+
+  case Instruction::IntToPtr:
+    return;
+
+  case Instruction::PHI: {
+    auto *PN = cast<PHINode>(U);
+    const Loop *L = LI.getLoopFor(PN->getParent());
+    Value *BEValueV, *StartValueV;
+    std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L);
+
+    auto GetFoo = [&]() -> Value * {
+      if (!BEValueV || !StartValueV)
+        return nullptr;
+      auto BO = MatchBinaryOp(BEValueV, DT);
+      if (!BO)
+        return nullptr;
+
+      if (BO->Opcode != Instruction::Add)
+        return nullptr;
+
+      if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
+        return BO->RHS;
+      else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
+        return BO->LHS;
+      return nullptr;
+    };
+
+    if (auto *Acc = GetFoo()) {
+      Ops.push_back(StartValueV);
+      Ops.push_back(Acc);
+      return;
+    }
+    BranchInst *BI = getSelectPhiBr(PN, L, DT, LI);
+    Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+    if (BI && BI->isConditional() &&
+        BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS)) {
+      Ops.push_back(LHS);
+      Ops.push_back(RHS);
+      return;
+    }
+    return;
+  }
+
+  case Instruction::Select:
+    // U can also be a select constant expr, which let fall through.  Since
+    // createNodeForSelect only works for a condition that is an `ICmpInst`, and
+    // constant expressions cannot have instructions as operands, we'd have
+    // returned getUnknown for a select constant expressions anyway.
+    if (isa<Instruction>(U)) {
+      for (Value *Inc : cast<Instruction>(U)->operands())
+        Ops.push_back(Inc);
+      return;
+    }
+    break;
+
+  case Instruction::Call:
+  case Instruction::Invoke:
+    if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
+      Ops.push_back(RV);
+      return;
+    }
+
+    if (auto *II = dyn_cast<IntrinsicInst>(U)) {
+      switch (II->getIntrinsicID()) {
+      case Intrinsic::abs:
+        Ops.push_back(II->getArgOperand(0));
+        return;
+      case Intrinsic::umax:
+      case Intrinsic::umin:
+      case Intrinsic::smax:
+      case Intrinsic::smin:
+      case Intrinsic::usub_sat:
+      case Intrinsic::uadd_sat:
+        Ops.push_back(II->getArgOperand(0));
+        Ops.push_back(II->getArgOperand(1));
+        return;
+      case Intrinsic::start_loop_iterations:
+        Ops.push_back(II->getArgOperand(0));
+        return;
+      default:
+        break;
+      }
+    }
+    break;
+  }
+
+  return;
+}
+
 const SCEV *ScalarEvolution::createSCEV(Value *V) {
   if (!isSCEVable(V->getType()))
     return getUnknown(V);
diff --git a/llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll b/llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll
--- a/llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll
+++ b/llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll
@@ -325,7 +325,7 @@
 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 ; CHECK-NEXT:    --> %iv.shl U: [4,65) S: [4,65) Exits: 16 LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %shiftamt = and i64 %iv, 1
 ; CHECK-NEXT:    --> (zext i1 {false,+,true}<%loop> to i64) U: [0,2) S: [0,2) Exits: 0 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, %shiftamt