Add "blocked" heuristic to the Hexagon MI scheduler.

  Improve AQ instruction selection in the Hexagon MI scheduler.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163523 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 155 insertions, 141 deletions

diff --git a/lib/Target/Hexagon/HexagonMachineScheduler.h b/lib/Target/Hexagon/HexagonMachineScheduler.h
index 7d8cc3d..f3643d6 100644
--- a/lib/Target/Hexagon/HexagonMachineScheduler.h
+++ b/lib/Target/Hexagon/HexagonMachineScheduler.h
@@ -40,11 +40,10 @@ using namespace llvm;
 namespace llvm {
 class VLIWMachineScheduler;
 
-/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive the selected
-/// scheduling algorithm.
+/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive
+/// the selected scheduling algorithm.
 ///
-/// If this works well and targets wish to reuse VLIWMachineScheduler, we may expose it
-/// in ScheduleDAGInstrs.h
+/// TODO: Move this to ScheduleDAGInstrs.h
 class MachineSchedStrategy {
 public:
   virtual ~MachineSchedStrategy() {}
@@ -57,7 +56,8 @@ public:
   /// be scheduled at the bottom.
   virtual SUnit *pickNode(bool &IsTopNode) = 0;
 
-  /// Notify MachineSchedStrategy that VLIWMachineScheduler has scheduled a node.
+  /// Notify MachineSchedStrategy that VLIWMachineScheduler has
+  /// scheduled a node.
   virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
 
   /// When all predecessor dependencies have been resolved, free this node for
@@ -69,7 +69,8 @@ public:
 };
 
 //===----------------------------------------------------------------------===//
-// ConvergingVLIWScheduler - Implementation of the standard MachineSchedStrategy.
+// ConvergingVLIWScheduler - Implementation of the standard
+// MachineSchedStrategy.
 //===----------------------------------------------------------------------===//
 
 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
@@ -123,123 +124,6 @@ public:
   }
 };
 
-/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance
-/// the schedule.
-class ConvergingVLIWScheduler : public MachineSchedStrategy {
-
-  /// Store the state used by ConvergingVLIWScheduler heuristics, required for the
-  /// lifetime of one invocation of pickNode().
-  struct SchedCandidate {
-    // The best SUnit candidate.
-    SUnit *SU;
-
-    // Register pressure values for the best candidate.
-    RegPressureDelta RPDelta;
-
-    // Best scheduling cost.
-    int SCost;
-
-    SchedCandidate(): SU(NULL), SCost(0) {}
-  };
-  /// Represent the type of SchedCandidate found within a single queue.
-  enum CandResult {
-    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
-    BestCost};
-
-  /// Each Scheduling boundary is associated with ready queues. It tracks the
-  /// current cycle in whichever direction at has moved, and maintains the state
-  /// of "hazards" and other interlocks at the current cycle.
-  struct SchedBoundary {
-    VLIWMachineScheduler *DAG;
-
-    ReadyQueue Available;
-    ReadyQueue Pending;
-    bool CheckPending;
-
-    ScheduleHazardRecognizer *HazardRec;
-
-    unsigned CurrCycle;
-    unsigned IssueCount;
-
-    /// MinReadyCycle - Cycle of the soonest available instruction.
-    unsigned MinReadyCycle;
-
-    // Remember the greatest min operand latency.
-    unsigned MaxMinLatency;
-
-    /// Pending queues extend the ready queues with the same ID and the
-    /// PendingFlag set.
-    SchedBoundary(unsigned ID, const Twine &Name):
-      DAG(0), Available(ID, Name+".A"),
-      Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
-      CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0),
-      MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
-
-    ~SchedBoundary() { delete HazardRec; }
-
-    bool isTop() const {
-      return Available.getID() == ConvergingVLIWScheduler::TopQID;
-    }
-
-    bool checkHazard(SUnit *SU);
-
-    void releaseNode(SUnit *SU, unsigned ReadyCycle);
-
-    void bumpCycle();
-
-    void bumpNode(SUnit *SU);
-
-    void releasePending();
-
-    void removeReady(SUnit *SU);
-
-    SUnit *pickOnlyChoice();
-  };
-
-  VLIWMachineScheduler *DAG;
-  const TargetRegisterInfo *TRI;
-
-  // State of the top and bottom scheduled instruction boundaries.
-  SchedBoundary Top;
-  SchedBoundary Bot;
-
-public:
-  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
-  enum {
-    TopQID = 1,
-    BotQID = 2,
-    LogMaxQID = 2
-  };
-
-  ConvergingVLIWScheduler():
-    DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
-
-  virtual void initialize(VLIWMachineScheduler *dag);
-
-  virtual SUnit *pickNode(bool &IsTopNode);
-
-  virtual void schedNode(SUnit *SU, bool IsTopNode);
-
-  virtual void releaseTopNode(SUnit *SU);
-
-  virtual void releaseBottomNode(SUnit *SU);
-
-protected:
-  SUnit *pickNodeBidrectional(bool &IsTopNode);
-
-  int SchedulingCost(ReadyQueue &Q,
-                     SUnit *SU, SchedCandidate &Candidate,
-                     RegPressureDelta &Delta, bool verbose);
-
-  CandResult pickNodeFromQueue(ReadyQueue &Q,
-                               const RegPressureTracker &RPTracker,
-                               SchedCandidate &Candidate);
-#ifndef NDEBUG
-  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
-                      PressureElement P = PressureElement());
-#endif
-};
-
 class VLIWResourceModel {
   /// ResourcesModel - Represents VLIW state.
   /// Not limited to VLIW targets per say, but assumes
@@ -261,7 +145,21 @@ public:
     const TargetMachine &TM = C->MF->getTarget();
     ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
 
-    // This hard requirement could be relaxed, but for now do not let it proceed.
+    // This hard requirement could be relaxed,
+    // but for now do not let it proceed.
+    assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
+
+    Packet.resize(InstrItins->SchedModel->IssueWidth);
+    Packet.clear();
+    ResourcesModel->clearResources();
+  }
+
+  VLIWResourceModel(const TargetMachine &TM) :
+    InstrItins(TM.getInstrItineraryData()), TotalPackets(0) {
+    ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
+
+    // This hard requirement could be relaxed,
+    // but for now do not let it proceed.
     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
 
     Packet.resize(InstrItins->SchedModel->IssueWidth);
@@ -281,8 +179,13 @@ public:
     ResourcesModel->clearResources();
   }
 
+  void reset() {
+    Packet.clear();
+    ResourcesModel->clearResources();
+  }
+
   bool isResourceAvailable(SUnit *SU);
-  void reserveResources(SUnit *SU);
+  bool reserveResources(SUnit *SU);
   unsigned getTotalPackets() const { return TotalPackets; }
 };
 
@@ -293,10 +196,6 @@ class VLIWMachineScheduler : public ScheduleDAGInstrs {
   RegisterClassInfo *RegClassInfo;
   MachineSchedStrategy *SchedImpl;
 
-  /// state separatly for top/bottom sectioins.
-  VLIWResourceModel *TopResourceModel;
-  VLIWResourceModel *BotResourceModel;
-
   MachineBasicBlock::iterator LiveRegionEnd;
 
   /// Register pressure in this region computed by buildSchedGraph.
@@ -334,10 +233,6 @@ public:
     AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S),
     RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
     CurrentBottom(), BotRPTracker(BotPressure), MLI(C->MLI) {
-
-    TopResourceModel = new VLIWResourceModel(C, InstrItins);
-    BotResourceModel = new VLIWResourceModel(C, InstrItins);
-
 #ifndef NDEBUG
     NumInstrsScheduled = 0;
 #endif
@@ -346,8 +241,6 @@ public:
 
   virtual ~VLIWMachineScheduler() {
     delete SchedImpl;
-    delete TopResourceModel;
-    delete BotResourceModel;
   }
 
   MachineBasicBlock::iterator top() const { return CurrentTop; }
@@ -382,9 +275,6 @@ public:
     return RegionCriticalPSets;
   }
 
-  VLIWResourceModel *getTopResourceModel() { return TopResourceModel; }
-  VLIWResourceModel *getBotResourceModel() { return BotResourceModel; }
-
   /// getIssueWidth - Return the max instructions per scheduling group.
   unsigned getIssueWidth() const {
     return (InstrItins && InstrItins->SchedModel)
@@ -393,9 +283,10 @@ public:
 
   /// getNumMicroOps - Return the number of issue slots required for this MI.
   unsigned getNumMicroOps(MachineInstr *MI) const {
-    if (!InstrItins) return 1;
-    int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass());
-    return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI);
+    return 1;
+    //if (!InstrItins) return 1;
+    //int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass());
+    //return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI);
   }
 
 private:
@@ -417,6 +308,129 @@ private:
 
   void placeDebugValues();
 };
+
+/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
+/// to balance the schedule.
+class ConvergingVLIWScheduler : public MachineSchedStrategy {
+
+  /// Store the state used by ConvergingVLIWScheduler heuristics, required
+  ///  for the lifetime of one invocation of pickNode().
+  struct SchedCandidate {
+    // The best SUnit candidate.
+    SUnit *SU;
+
+    // Register pressure values for the best candidate.
+    RegPressureDelta RPDelta;
+
+    // Best scheduling cost.
+    int SCost;
+
+    SchedCandidate(): SU(NULL), SCost(0) {}
+  };
+  /// Represent the type of SchedCandidate found within a single queue.
+  enum CandResult {
+    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
+    BestCost};
+
+  /// Each Scheduling boundary is associated with ready queues. It tracks the
+  /// current cycle in whichever direction at has moved, and maintains the state
+  /// of "hazards" and other interlocks at the current cycle.
+  struct SchedBoundary {
+    VLIWMachineScheduler *DAG;
+
+    ReadyQueue Available;
+    ReadyQueue Pending;
+    bool CheckPending;
+
+    ScheduleHazardRecognizer *HazardRec;
+    VLIWResourceModel *ResourceModel;
+
+    unsigned CurrCycle;
+    unsigned IssueCount;
+
+    /// MinReadyCycle - Cycle of the soonest available instruction.
+    unsigned MinReadyCycle;
+
+    // Remember the greatest min operand latency.
+    unsigned MaxMinLatency;
+
+    /// Pending queues extend the ready queues with the same ID and the
+    /// PendingFlag set.
+    SchedBoundary(unsigned ID, const Twine &Name):
+      DAG(0), Available(ID, Name+".A"),
+      Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
+      CheckPending(false), HazardRec(0), ResourceModel(0),
+      CurrCycle(0), IssueCount(0),
+      MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
+
+    ~SchedBoundary() {
+      delete ResourceModel;
+      delete HazardRec;
+    }
+
+    bool isTop() const {
+      return Available.getID() == ConvergingVLIWScheduler::TopQID;
+    }
+
+    bool checkHazard(SUnit *SU);
+
+    void releaseNode(SUnit *SU, unsigned ReadyCycle);
+
+    void bumpCycle();
+
+    void bumpNode(SUnit *SU);
+
+    void releasePending();
+
+    void removeReady(SUnit *SU);
+
+    SUnit *pickOnlyChoice();
+  };
+
+  VLIWMachineScheduler *DAG;
+  const TargetRegisterInfo *TRI;
+
+  // State of the top and bottom scheduled instruction boundaries.
+  SchedBoundary Top;
+  SchedBoundary Bot;
+
+public:
+  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
+  enum {
+    TopQID = 1,
+    BotQID = 2,
+    LogMaxQID = 2
+  };
+
+  ConvergingVLIWScheduler():
+    DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
+
+  virtual void initialize(VLIWMachineScheduler *dag);
+
+  virtual SUnit *pickNode(bool &IsTopNode);
+
+  virtual void schedNode(SUnit *SU, bool IsTopNode);
+
+  virtual void releaseTopNode(SUnit *SU);
+
+  virtual void releaseBottomNode(SUnit *SU);
+
+protected:
+  SUnit *pickNodeBidrectional(bool &IsTopNode);
+
+  int SchedulingCost(ReadyQueue &Q,
+                     SUnit *SU, SchedCandidate &Candidate,
+                     RegPressureDelta &Delta, bool verbose);
+
+  CandResult pickNodeFromQueue(ReadyQueue &Q,
+                               const RegPressureTracker &RPTracker,
+                               SchedCandidate &Candidate);
+#ifndef NDEBUG
+  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
+                      PressureElement P = PressureElement());
+#endif
+};
+
 } // namespace