Index: llvm/include/llvm/Analysis/IVUsers.h
===================================================================
--- llvm/include/llvm/Analysis/IVUsers.h
+++ llvm/include/llvm/Analysis/IVUsers.h
@@ -159,7 +159,7 @@
   void dump() const;
 
 protected:
-  bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests);
+  bool AddUsersImpl(Instruction *I);
 };
 
 Pass *createIVUsersPass();
Index: llvm/lib/Analysis/IVUsers.cpp
===================================================================
--- llvm/lib/Analysis/IVUsers.cpp
+++ llvm/lib/Analysis/IVUsers.cpp
@@ -90,33 +90,6 @@
   return false;
 }
 
-/// Return true if all loop headers that dominate this block have a preheader.
-static bool isPreheaderLoopNest(BasicBlock *BB, const DominatorTree *DT,
-                                const LoopInfo *LI,
-                                SmallPtrSetImpl<Loop*> &PreheaderLoopNests) {
-  Loop *NearestLoop = nullptr;
-  for (DomTreeNode *Rung = DT->getNode(BB);
-       Rung; Rung = Rung->getIDom()) {
-    BasicBlock *DomBB = Rung->getBlock();
-    Loop *DomLoop = LI->getLoopFor(DomBB);
-    if (DomLoop && DomLoop->getHeader() == DomBB) {
-      // If we have already checked this loop nest, stop checking.
-      if (PreheaderLoopNests.count(DomLoop))
-        break;
-      // If the domtree walk reaches a loop with no preheader, return false.
-      if (!DomLoop->getLoopPreheader())
-        return false;
-      // If we have not already checked this loop nest, remember the loop
-      // header nearest to BB. The nearest loop may not contain BB.
-      if (!NearestLoop)
-        NearestLoop = DomLoop;
-    }
-  }
-  if (NearestLoop)
-    PreheaderLoopNests.insert(NearestLoop);
-  return true;
-}
-
 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
 /// and now we need to decide whether the user should use the preinc or post-inc
 /// value.  If this user should use the post-inc version of the IV, return true.
@@ -164,8 +137,7 @@
 /// AddUsersImpl - Inspect the specified instruction.  If it is a
 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
 /// return true.  Otherwise, return false.
-bool IVUsers::AddUsersImpl(Instruction *I,
-                           SmallPtrSetImpl<Loop*> &PreheaderLoopNests) {
+bool IVUsers::AddUsersImpl(Instruction *I) {
   const DataLayout &DL = I->getModule()->getDataLayout();
 
   // Add this IV user to the Processed set before returning false to ensure that
@@ -212,18 +184,6 @@
     if (isa<PHINode>(User) && Processed.count(User))
       continue;
 
-    // Only consider IVUsers that are dominated by simplified loop
-    // headers. Otherwise, SCEVExpander will crash.
-    BasicBlock *UseBB = User->getParent();
-    // A phi's use is live out of its predecessor block.
-    if (PHINode *PHI = dyn_cast<PHINode>(User)) {
-      unsigned OperandNo = U.getOperandNo();
-      unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
-      UseBB = PHI->getIncomingBlock(ValNo);
-    }
-    if (!isPreheaderLoopNest(UseBB, DT, LI, PreheaderLoopNests))
-      return false;
-
     // Descend recursively, but not into PHI nodes outside the current loop.
     // It's important to see the entire expression outside the loop to get
     // choices that depend on addressing mode use right, although we won't
@@ -232,14 +192,12 @@
     // but do want to record a second reference in the same instruction.
     bool AddUserToIVUsers = false;
     if (LI->getLoopFor(User->getParent()) != L) {
-      if (isa<PHINode>(User) || Processed.count(User) ||
-          !AddUsersImpl(User, PreheaderLoopNests)) {
+      if (isa<PHINode>(User) || Processed.count(User) || !AddUsersImpl(User)) {
         LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
                           << "   OF SCEV: " << *ISE << '\n');
         AddUserToIVUsers = true;
       }
-    } else if (Processed.count(User) ||
-               !AddUsersImpl(User, PreheaderLoopNests)) {
+    } else if (Processed.count(User) || !AddUsersImpl(User)) {
       LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
                         << "   OF SCEV: " << *ISE << '\n');
       AddUserToIVUsers = true;
@@ -289,12 +247,7 @@
 }
 
 bool IVUsers::AddUsersIfInteresting(Instruction *I) {
-  // SCEVExpander can only handle users that are dominated by loops with
-  // preheaders. Keep track of all loops that are only dominated by preheader
-  // loops so we don't traverse the domtree for each user.
-  SmallPtrSet<Loop*,16> PreheaderLoopNests;
-
-  return AddUsersImpl(I, PreheaderLoopNests);
+  return AddUsersImpl(I);
 }
 
 IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -5706,23 +5706,6 @@
     }
   }
 
-#ifndef NDEBUG
-  // All dominating loops must have preheaders, or SCEVExpander may not be able
-  // to materialize an AddRecExpr whose Start is an outer AddRecExpr.
-  //
-  // IVUsers analysis should only create users that are dominated by simple loop
-  // headers. Since this loop should dominate all of its users, its user list
-  // should be empty if this loop itself is not within a simple loop nest.
-  for (DomTreeNode *Rung = DT.getNode(L->getLoopPreheader());
-       Rung; Rung = Rung->getIDom()) {
-    BasicBlock *BB = Rung->getBlock();
-    const Loop *DomLoop = LI.getLoopFor(BB);
-    if (DomLoop && DomLoop->getHeader() == BB) {
-      assert(DomLoop->getLoopPreheader() && "LSR needs a simplified loop nest");
-    }
-  }
-#endif // DEBUG
-
   LLVM_DEBUG(dbgs() << "\nLSR on loop ";
              L->getHeader()->printAsOperand(dbgs(), /*PrintType=*/false);
              dbgs() << ":\n");
Index: llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
===================================================================
--- llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
+++ llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
@@ -2631,6 +2631,12 @@
       }
     }
     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
+      // There must be a preheader we can expand into.
+      if (!AR->getLoop()->getLoopPreheader()) {
+        IsUnsafe = true;
+        return false;
+      }
+
       const SCEV *Step = AR->getStepRecurrence(SE);
       if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
         IsUnsafe = true;