[MachineScheduler][NFC] Refactor MachineScheduler

[courbet]

Summary

Refactor MachineScheduler to get rid of duplicate code. NFC.

[courbet]

Rebase.

[courbet]

Fix previous rebase.

include/llvm/CodeGen/MachineScheduler.h

public:
 
   const SUnit *getNextClusterPred() const { return NextClusterPred; }
 
   const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
 
   void viewGraph(const Twine &Name, const Twine &Title) override;
   void viewGraph() override;
 
+  // Dumps additional debug information for the given SUnit Only called within
+  // DEBUG().
+  virtual void dumpDebugInfoForSU(const SUnit &SU) const {}
+
 protected:
   // Top-Level entry points for the schedule() driver...
 
+  // Build the scheduling DAG.
+  virtual void buildDAG() { buildSchedGraph(AA); };
+
+  /// Move an instruction and update state.
+  virtual void scheduleMI(SUnit *SU, bool IsTopNode);
+
   /// Apply each ScheduleDAGMutation step in order. This allows different
   /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
   void postprocessDAG();
 
   /// Release ExitSU predecessors and setup scheduler queues.
   void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
 
   /// Update scheduler DAG and queues after scheduling an instruction.
public:
   const std::vector<PressureChange> &getRegionCriticalPSets() const {
     return RegionCriticalPSets;
   }
 
   PressureDiff &getPressureDiff(const SUnit *SU) {
     return SUPressureDiffs[SU->NodeNum];
   }
 
+  const PressureDiff &getPressureDiff(const SUnit *SU) const {
+    return SUPressureDiffs[SU->NodeNum];
+  }
+
   /// Compute a DFSResult after DAG building is complete, and before any
   /// queue comparisons.
   void computeDFSResult();
 
   /// Return a non-null DFS result if the scheduling strategy initialized it.
   const SchedDFSResult *getDFSResult() const { return DFSResult; }
 
   BitVector &getScheduledTrees() { return ScheduledTrees; }
 
   /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
   /// region. This covers all instructions in a block, while schedule() may only
   /// cover a subset.
   void enterRegion(MachineBasicBlock *bb,
                    MachineBasicBlock::iterator begin,
                    MachineBasicBlock::iterator end,
                    unsigned regioninstrs) override;
 
-  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
-  /// reorderable instructions.
-  void schedule() override;
-
   /// Compute the cyclic critical path through the DAG.
   unsigned computeCyclicCriticalPath();
 
 protected:
   // Top-Level entry points for the schedule() driver...
 
   /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
   /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
   /// region, TopTracker and BottomTracker will be initialized to the top and
   /// bottom of the DAG region without covereing any unscheduled instruction.
-  void buildDAGWithRegPressure();
+  void buildDAG() override;
 
   /// Release ExitSU predecessors and setup scheduler queues. Re-position
   /// the Top RP tracker in case the region beginning has changed.
   void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
 
   /// Move an instruction and update register pressure.
-  void scheduleMI(SUnit *SU, bool IsTopNode);
+  void scheduleMI(SUnit *SU, bool IsTopNode) override;
 
   // Lesser helpers...
 
   void initRegPressure();
 
   void updatePressureDiffs(ArrayRef<RegisterMaskPair> LiveUses);
 
   void updateScheduledPressure(const SUnit *SU,
                                const std::vector<unsigned> &NewMaxPressure);
 
   void collectVRegUses(SUnit &SU);
+
+  void dumpDebugInfoForSU(const SUnit &SU) const override;
 };
 
 //===----------------------------------------------------------------------===//
 ///
 /// Helpers for implementing custom MachineSchedStrategy classes. These take
 /// care of the book-keeping associated with list scheduling heuristics.
 ///
 //===----------------------------------------------------------------------===//

lib/CodeGen/MachineScheduler.cpp

if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
     CurrentTop = CurrentBottom;
     return false;
   }
   ++NumInstrsScheduled;
 #endif
   return true;
 }
 
+void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) {
+  MachineInstr *MI = SU->getInstr();
+  if (IsTopNode) {
+    assert(SU->isTopReady() && "node still has unscheduled dependencies");
+    if (&*CurrentTop == MI)
+      CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
+    else
+      moveInstruction(MI, CurrentTop);
+  } else {
+    assert(SU->isBottomReady() && "node still has unscheduled dependencies");
+    MachineBasicBlock::iterator priorII =
+      priorNonDebug(CurrentBottom, CurrentTop);
+    if (&*priorII == MI)
+      CurrentBottom = priorII;
+    else {
+      if (&*CurrentTop == MI)
+        CurrentTop = nextIfDebug(++CurrentTop, priorII);
+      moveInstruction(MI, CurrentBottom);
+      CurrentBottom = MI;
+    }
+  }
+}
+
 /// Per-region scheduling driver, called back from
-/// MachineScheduler::runOnMachineFunction. This is a simplified driver that
-/// does not consider liveness or register pressure. It is useful for PostRA
-/// scheduling and potentially other custom schedulers.
+/// MachineScheduler::runOnMachineFunction
+/// This is a skeletal driver, with all the functionality pushed into helpers,
+/// so that it can be easily extended by experimental schedulers. Generally,
+/// implementing MachineSchedStrategy should be sufficient to implement a new
+/// scheduling algorithm. However, if a scheduler further subclasses
+/// ScheduleDAGMI then it will want to override this virtual method in order
+/// to update any specialized state.
 void ScheduleDAGMI::schedule() {
   DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");
   DEBUG(SchedImpl->dumpPolicy());
 
   // Build the DAG.
-  buildSchedGraph(AA);
+  buildDAG();
 
   Topo.InitDAGTopologicalSorting();
 
   postprocessDAG();
 
   SmallVector<SUnit*, 8> TopRoots, BotRoots;
   findRootsAndBiasEdges(TopRoots, BotRoots);
 
   // Initialize the strategy before modifying the DAG.
   // This may initialize a DFSResult to be used for queue priority.
   SchedImpl->initialize(this);
 
   DEBUG(
     if (EntrySU.getInstr() != nullptr)
       EntrySU.dumpAll(this);
-    for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
-      SUnits[su].dumpAll(this);
+    for (const SUnit &SU : SUnits) {
+      SU.dumpAll(this);
+      dumpDebugInfoForSU(SU);
+    }
+    dbgs() << '\n';
     if (ExitSU.getInstr() != nullptr)
       ExitSU.dumpAll(this);
   );
   if (ViewMISchedDAGs) viewGraph();
 
   // Initialize ready queues now that the DAG and priority data are finalized.
   initQueues(TopRoots, BotRoots);
 
   bool IsTopNode = false;
   while (true) {
     DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n");
     SUnit *SU = SchedImpl->pickNode(IsTopNode);
     if (!SU) break;
 
     assert(!SU->isScheduled && "Node already scheduled");
     if (!checkSchedLimit())
       break;
 
-    MachineInstr *MI = SU->getInstr();
-    if (IsTopNode) {
-      assert(SU->isTopReady() && "node still has unscheduled dependencies");
-      if (&*CurrentTop == MI)
-        CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
-      else
-        moveInstruction(MI, CurrentTop);
-    } else {
-      assert(SU->isBottomReady() && "node still has unscheduled dependencies");
-      MachineBasicBlock::iterator priorII =
-        priorNonDebug(CurrentBottom, CurrentTop);
-      if (&*priorII == MI)
-        CurrentBottom = priorII;
-      else {
-        if (&*CurrentTop == MI)
-          CurrentTop = nextIfDebug(++CurrentTop, priorII);
-        moveInstruction(MI, CurrentBottom);
-        CurrentBottom = MI;
-      }
-    }
+    scheduleMI(SU, IsTopNode);
+
     // Notify the scheduling strategy before updating the DAG.
     // This sets the scheduled node's ReadyCycle to CurrCycle. When updateQueues
     // runs, it can then use the accurate ReadyCycle time to determine whether
     // newly released nodes can move to the readyQ.
     SchedImpl->schedNode(SU, IsTopNode);
 
     updateQueues(SU, IsTopNode);
   }
if (ShouldTrackLaneMasks) {
             );
           }
         }
       }
     }
   }
 }
 
-/// schedule - Called back from MachineScheduler::runOnMachineFunction
-/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
-/// only includes instructions that have DAG nodes, not scheduling boundaries.
-///
-/// This is a skeletal driver, with all the functionality pushed into helpers,
-/// so that it can be easily extended by experimental schedulers. Generally,
-/// implementing MachineSchedStrategy should be sufficient to implement a new
-/// scheduling algorithm. However, if a scheduler further subclasses
-/// ScheduleDAGMILive then it will want to override this virtual method in order
-/// to update any specialized state.
-void ScheduleDAGMILive::schedule() {
-  DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");
-  DEBUG(SchedImpl->dumpPolicy());
-  buildDAGWithRegPressure();
-
-  Topo.InitDAGTopologicalSorting();
-
-  postprocessDAG();
-
-  SmallVector<SUnit*, 8> TopRoots, BotRoots;
-  findRootsAndBiasEdges(TopRoots, BotRoots);
-
-  // Initialize the strategy before modifying the DAG.
-  // This may initialize a DFSResult to be used for queue priority.
-  SchedImpl->initialize(this);
-
-  DEBUG(
-    if (EntrySU.getInstr() != nullptr)
-      EntrySU.dumpAll(this);
-    for (const SUnit &SU : SUnits) {
-      SU.dumpAll(this);
-      if (ShouldTrackPressure) {
-        dbgs() << "  Pressure Diff      : ";
-        getPressureDiff(&SU).dump(*TRI);
-      }
-      dbgs() << "  Single Issue       : ";
-      if (SchedModel.mustBeginGroup(SU.getInstr()) &&
-         SchedModel.mustEndGroup(SU.getInstr()))
-        dbgs() << "true;";
-      else
-        dbgs() << "false;";
-      dbgs() << '\n';
-    }
-    if (ExitSU.getInstr() != nullptr)
-      ExitSU.dumpAll(this);
-  );
-  if (ViewMISchedDAGs) viewGraph();
-
-  // Initialize ready queues now that the DAG and priority data are finalized.
-  initQueues(TopRoots, BotRoots);
-
-  bool IsTopNode = false;
-  while (true) {
-    DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n");
-    SUnit *SU = SchedImpl->pickNode(IsTopNode);
-    if (!SU) break;
-
-    assert(!SU->isScheduled && "Node already scheduled");
-    if (!checkSchedLimit())
-      break;
-
-    scheduleMI(SU, IsTopNode);
-
-    if (DFSResult) {
-      unsigned SubtreeID = DFSResult->getSubtreeID(SU);
-      if (!ScheduledTrees.test(SubtreeID)) {
-        ScheduledTrees.set(SubtreeID);
-        DFSResult->scheduleTree(SubtreeID);
-        SchedImpl->scheduleTree(SubtreeID);
-      }
-    }
-
-    // Notify the scheduling strategy after updating the DAG.
-    SchedImpl->schedNode(SU, IsTopNode);
-
-    updateQueues(SU, IsTopNode);
-  }
-  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
-
-  placeDebugValues();
-
-  DEBUG({
-      unsigned BBNum = begin()->getParent()->getNumber();
-      dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
-      dumpSchedule();
-      dbgs() << '\n';
-    });
-}
-
 /// Build the DAG and setup three register pressure trackers.
-void ScheduleDAGMILive::buildDAGWithRegPressure() {
+void ScheduleDAGMILive::buildDAG() {
   if (!ShouldTrackPressure) {
     RPTracker.reset();
     RegionCriticalPSets.clear();
     buildSchedGraph(AA);
     return;
   }
 
   // Initialize the register pressure tracker used by buildSchedGraph.
   RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
                  ShouldTrackLaneMasks, /*TrackUntiedDefs=*/true);
 
   // Account for liveness generate by the region boundary.
   if (LiveRegionEnd != RegionEnd)
     RPTracker.recede();
 
   // Build the DAG, and compute current register pressure.
   buildSchedGraph(AA, &RPTracker, &SUPressureDiffs, LIS, ShouldTrackLaneMasks);
 
   // Initialize top/bottom trackers after computing region pressure.
   initRegPressure();
 }
 
+void ScheduleDAGMILive::dumpDebugInfoForSU(const SUnit &SU) const {
+  DEBUG(
+    if (ShouldTrackPressure) {
+      dbgs() << "  Pressure Diff      : ";
+      getPressureDiff(&SU).dump(*TRI);
+    }
+    dbgs() << "  Single Issue       : ";
+    if (SchedModel.mustBeginGroup(SU.getInstr()) &&
+        SchedModel.mustEndGroup(SU.getInstr()))
+      dbgs() << "true;";
+    else
+      dbgs() << "false;";
+  );
+}
+
 void ScheduleDAGMILive::computeDFSResult() {
   if (!DFSResult)
     DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize);
   DFSResult->clear();
   ScheduledTrees.clear();
   DFSResult->resize(SUnits.size());
   DFSResult->compute(SUnits);
   ScheduledTrees.resize(DFSResult->getNumSubtrees());
if (ShouldTrackPressure) {
         dbgs() << "Bottom Pressure:\n";
         dumpRegSetPressure(BotRPTracker.getRegSetPressureAtPos(), TRI);
       );
 
       updateScheduledPressure(SU, BotRPTracker.getPressure().MaxSetPressure);
       updatePressureDiffs(LiveUses);
     }
   }
+
+  if (DFSResult) {
+    unsigned SubtreeID = DFSResult->getSubtreeID(SU);
+    if (!ScheduledTrees.test(SubtreeID)) {
+      ScheduledTrees.set(SubtreeID);
+      DFSResult->scheduleTree(SubtreeID);
+      SchedImpl->scheduleTree(SubtreeID);
+    }
+  }
 }
 
 //===----------------------------------------------------------------------===//
 // BaseMemOpClusterMutation - DAG post-processing to cluster loads or stores.
 //===----------------------------------------------------------------------===//
 
 namespace {
 

lib/Target/AMDGPU/SIMachineScheduler.cpp

 }
 
 void SIScheduleDAGMI::schedule()
 {
   SmallVector<SUnit*, 8> TopRoots, BotRoots;
   SIScheduleBlockResult Best, Temp;
   DEBUG(dbgs() << "Preparing Scheduling\n");
 
-  buildDAGWithRegPressure();
+  buildDAG();
   DEBUG(
     for(SUnit& SU : SUnits)
        SU.dumpAll(this)
   );
 
   topologicalSort();
   findRootsAndBiasEdges(TopRoots, BotRoots);
   // We reuse several ScheduleDAGMI and ScheduleDAGMILive

lib/Target/Hexagon/HexagonMachineScheduler.cpp

 void VLIWMachineScheduler::schedule() {
   DEBUG(dbgs()
         << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber()
         << " " << BB->getName()
         << " in_func " << BB->getParent()->getFunction()->getName()
         << " at loop depth "  << MLI->getLoopDepth(BB)
         << " \n");
 
-  buildDAGWithRegPressure();
+  buildDAG();
 
   SmallVector<SUnit*, 8> TopRoots, BotRoots;
   findRootsAndBiasEdges(TopRoots, BotRoots);
 
   // Initialize the strategy before modifying the DAG.
   SchedImpl->initialize(this);
 
   DEBUG(unsigned maxH = 0;

test/CodeGen/AMDGPU/schedule-regpressure.mir

 # RUN: llc -march=amdgcn -misched=converge -run-pass machine-scheduler %s -o - -debug-only=misched 2>&1 | FileCheck %s
 # REQUIRES: asserts
 
 # Check there is no SReg_32 pressure created by DS_* instructions because of M0 use
 
-# CHECK: ScheduleDAGMILive::schedule starting
+# CHECK: ScheduleDAGMI::schedule starting
 # CHECK: SU({{.*}} = DS_READ_B32 {{.*}} %M0<imp-use>, %EXEC<imp-use>
 # CHECK: Pressure Diff : {{$}}
 # CHECK: SU({{.*}} DS_WRITE_B32
 
 ---
 name:            mo_pset
 alignment:       0
 exposesReturnsTwice: false

test/CodeGen/ARM/misched-int-basic-thumb2.mir

 # CHECK_A9:    Latency    : 3
 # CHECK_SWIFT: Latency    : 5
 # CHECK_R52:   Latency    : 4
 #
 # CHECK:       SU(18):   %vreg19<def,tied4>, %vreg20<def,tied5> = t2UMLAL %vreg12, %vreg12, %vreg19<tied0>, %vreg20<tied1>, pred:14, pred:%noreg; rGPR:%vreg19,%vreg20,%vreg12,%vreg12,%vreg20
 # CHECK_A9:    Latency    : 3
 # CHECK_SWIFT: Latency    : 7
 # CHECK_R52:   Latency    : 4
-# CHECK:  ** ScheduleDAGMILive::schedule picking next node
+# CHECK:  ** ScheduleDAGMI::schedule picking next node
 ...
 ---
 name:            foo
 alignment:       1
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false

test/CodeGen/ARM/misched-int-basic.mir

 # CHECK_A9:    Latency    : 3
 # CHECK_SWIFT: Latency    : 5
 # CHECK_R52:   Latency    : 4
 #
 # CHECK:       SU(11):   %vreg13<def,tied4>, %vreg14<def,tied5> = UMLAL %vreg6, %vreg6, %vreg13<tied0>, %vreg14<tied1>, pred:14, pred:%noreg, opt:%noreg; GPR:%vreg13 GPRnopc:%vreg14,%vreg6,%vreg6
 # CHECK_SWIFT: Latency    : 7
 # CHECK_A9:    Latency    : 3
 # CHECK_R52:   Latency    : 4
-# CHECK:  ** ScheduleDAGMILive::schedule picking next node
+# CHECK:  ** ScheduleDAGMI::schedule picking next node
 ...
 ---
 name:            foo
 alignment:       2
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false

test/CodeGen/ARM/single-issue-r52.mir

define <8 x i8> @foo(i8* %A) {
     %tmp2 = extractvalue %struct.__neon_int8x8x4_t %tmp1, 0
     %tmp3 = extractvalue %struct.__neon_int8x8x4_t %tmp1, 1
     %tmp4 = add <8 x i8> %tmp2, %tmp3
     ret <8 x i8> %tmp4
   }
   declare %struct.__neon_int8x8x4_t @llvm.arm.neon.vld4.v8i8.p0i8(i8*, i32)
 
 # CHECK: ********** MI Scheduling **********
-# CHECK: ScheduleDAGMILive::schedule starting
+# CHECK: ScheduleDAGMI::schedule starting
 # CHECK: SU(1):   %vreg1<def> = VLD4d8Pseudo %vreg0, 8, pred:14, pred:%noreg; mem:LD32[%A](align=8) QQPR:%vreg1 GPR:%vreg0
 # CHECK: Latency            : 8
 # CHECK: Single Issue       : true;
 # CHECK: SU(2):   %vreg4<def> = VADDv8i8 %vreg1:dsub_0, %vreg1:dsub_1, pred:14, pred:%noreg; DPR:%vreg4 QQPR:%vreg1
 # CHECK: Latency            : 5
 # CHECK: Single Issue       : false;
 # CHECK: SU(3):   %vreg5<def>, %vreg6<def> = VMOVRRD %vreg4, pred:14, pred:%noreg; GPR:%vreg5,%vreg6 DPR:%vreg4
 # CHECK: Latency            : 4