[SLP] Restructure RescheduleHandling [NFC]

[reames]

Summary

This change clarifies, but does not actually change the handling for, how we handle a scheduling window extension.

Context:

• During normal pre-scheduling (i.e. what we do while walking the tree forming vector nodes), we only compute dependencies for instructions which are transitive users of a node in the vector tree.
• Our scheduling dependencies change based on the end of the current scheduling window. When we change the boundary, we must ensure new dependencies are computed before the next schedule.
• Because of the first point, it's normal to have nodes reached in the transitive users of a new node which don't yet have valid dependencies. As such, we can always leave nodes in the invalid dependency state so long as they haven't yet been scheduled.
• When dependencies are invalid, the node was not considered "ready" for scheduling. As such, initialFillReadyList is a nop when no instruction has valid dependencies.

Let me explain the old code, because it was a tad non-obvious.

The case with a bundle is fairly straight forward. We cleared dependencies and schedule. Then initialFillReadyList is nop. Then we schedule all the transitive users of the bundle. And we've basically done a normal pre-schedule with a side effect of having to recompute dependencies and schedule for the entire DAG.

The case without a bundle is trickier, and the comments were misleading. The key point is that initialFillReadyList does nothing when all nodes are the invalid dependency state. As such, we hit the bottom, the readylist is empty, and we immediately exit having left both scheduling and dependencies cleared to their uncomputed states.

End result, we can do the same thing much more obviously by just resetting the info, and only attempting rescheduling if we have a bundle.

[reames]

Closing for now to focus attention on more important patches.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

bool isPartOfBundle() const {
       return NextInBundle != nullptr || FirstInBundle != this;
     }
 
     /// Returns true if it is ready for scheduling, i.e. it has no more
     /// unscheduled depending instructions/bundles.
     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;
     }
 
     /// Modifies the number of unscheduled dependencies, also updating it for
     /// the whole bundle.
     int incrementUnscheduledDeps(int Incr) {
       UnscheduledDeps += Incr;
       return FirstInBundle->UnscheduledDepsInBundle += Incr;
BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP,
   LLVM_DEBUG(dbgs() << "SLP:  bundle: " << *S.OpValue << "\n");
 
   auto TryScheduleBundleImpl = [this, OldScheduleEnd, SLP](ScheduleData *Bundle) {
     // The scheduling region got new instructions at the lower end (or it is a
     // new region for the first bundle). This makes it necessary to
     // 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);
+
+      // 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) {
-      LLVM_DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle
-                        << " in block " << BB->getName() << "\n");
-      calculateDependencies(Bundle, /*InsertInReadyList=*/true, SLP);
-    }
+    if (!Bundle)
+      return;
+
 
-    // 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);
     }
   };
 
   // Make sure that the scheduling region contains all
   // instructions of the bundle.