Index: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
===================================================================
--- llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
+++ llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
@@ -2362,6 +2362,8 @@
     bool isReady() const {
       assert(isSchedulingEntity() &&
              "can't consider non-scheduling entity for ready list");
+      assert(hasValidDependencies() &&
+             "can't schedule without dependencies");
       return UnscheduledDepsInBundle == 0 && !IsScheduled;
     }
 
@@ -7346,28 +7348,30 @@
     // recalculate all dependencies.
     // It is seldom that this needs to be done a second time after adding the
     // initial bundle to the region.
-    bool ReSchedule = false;
     if (ScheduleEnd != OldScheduleEnd) {
       for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode())
         doForAllOpcodes(I, [](ScheduleData *SD) { SD->clearDependencies(); });
-      ReSchedule = true;
-    }
-    if (ReSchedule) {
+
       resetSchedule();
-      initialFillReadyList(ReadyInsts);
-    }
-    if (Bundle) {
-      LLVM_DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle
-                        << " in block " << BB->getName() << "\n");
-      calculateDependencies(Bundle, /*InsertInReadyList=*/true, SLP);
+
+      // NOTE: At this point, we've cleared dependencies and schedule information
+      // we can not restart scheduling without computing dependencies again.  During
+      // prescheduling, we only build dependencies for things which are transitive
+      // users of a proposed node in the tree.  This means we leave large sections
+      // of the overall window without valid dependencies until final scheduling.
     }
+    if (!Bundle)
+      return;
+
+    LLVM_DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle
+               << " in block " << BB->getName() << "\n");
+    calculateDependencies(Bundle, /*InsertInReadyList=*/true, SLP);
 
-    // Now try to schedule the new bundle or (if no bundle) just calculate
-    // dependencies. As soon as the bundle is "ready" it means that there are no
-    // cyclic dependencies and we can schedule it. Note that's important that we
-    // don't "schedule" the bundle yet (see cancelScheduling).
-    while (((!Bundle && ReSchedule) || (Bundle && !Bundle->isReady())) &&
-           !ReadyInsts.empty()) {
+    // Now try to schedule the new bundle. As soon as the bundle is "ready" it
+    // means that there are no cyclic dependencies and we can schedule it. Note
+    // that it's important that we don't "schedule" the bundle yet (see
+    // cancelScheduling).
+    while (!Bundle->isReady() && !ReadyInsts.empty()) {
       ScheduleData *Picked = ReadyInsts.pop_back_val();
       if (Picked->isSchedulingEntity() && Picked->isReady())
         schedule(Picked, ReadyInsts);