[Hexagon] Improve scheduling heuristic for large basic blocks

This patch changes the isLatencyBound heuristic to look at the
path length based upon the number of packets needed to schedule
a basic block. For small basic blocks, the heuristic uses a small
threshold for isLatencyBound. For large basic blocks, the
heuristic uses a large threshold.

The goal is to increase the priority of an instruction in a small
basic block that has a large height or depth relative to the code
size. For large functions, the height and depth are ignored
because it increases the live range of a register and causes more
spills. That is, for large functions, it is more important to
schedule instructions when available, and attempt to keep the defs
and uses closer together.

Patch by Brendon Cahoon.

llvm-svn: 327987

1 files changed, 28 insertions, 0 deletions

diff --git a/llvm/lib/Target/Hexagon/HexagonMachineScheduler.h b/llvm/lib/Target/Hexagon/HexagonMachineScheduler.h
index e26e9ab0f2f..3248c6ae021 100644
--- a/llvm/lib/Target/Hexagon/HexagonMachineScheduler.h
+++ b/llvm/lib/Target/Hexagon/HexagonMachineScheduler.h
@@ -98,6 +98,7 @@ public:
   void schedule() override;
 
   RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
+  int getBBSize() { return BB->size(); }
 };
 
 //===----------------------------------------------------------------------===//
@@ -143,6 +144,7 @@ class ConvergingVLIWScheduler : public MachineSchedStrategy {
 
     unsigned CurrCycle = 0;
     unsigned IssueCount = 0;
+    unsigned CriticalPathLength = 0;
 
     /// MinReadyCycle - Cycle of the soonest available instruction.
     unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
@@ -166,6 +168,25 @@ class ConvergingVLIWScheduler : public MachineSchedStrategy {
       SchedModel = smodel;
       CurrCycle = 0;
       IssueCount = 0;
+      // Initialize the critical path length limit, which used by the scheduling
+      // cost model to determine the value for scheduling an instruction. We use
+      // a slightly different heuristic for small and large functions. For small
+      // functions, it's important to use the height/depth of the instruction.
+      // For large functions, prioritizing by height or depth increases spills.
+      CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth();
+      if (DAG->getBBSize() < 50)
+        // We divide by two as a cheap and simple heuristic to reduce the
+        // critcal path length, which increases the priority of using the graph
+        // height/depth in the scheduler's cost computation.
+        CriticalPathLength >>= 1;
+      else {
+        // For large basic blocks, we prefer a larger critical path length to
+        // decrease the priority of using the graph height/depth.
+        unsigned MaxPath = 0;
+        for (auto &SU : DAG->SUnits)
+          MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
+        CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
+      }
     }
 
     bool isTop() const {
@@ -185,6 +206,13 @@ class ConvergingVLIWScheduler : public MachineSchedStrategy {
     void removeReady(SUnit *SU);
 
     SUnit *pickOnlyChoice();
+ 
+    bool isLatencyBound(SUnit *SU) {
+      if (CurrCycle >= CriticalPathLength)
+        return true;
+      unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
+      return CriticalPathLength - CurrCycle <= PathLength;
+    }
   };
 
   VLIWMachineScheduler *DAG = nullptr;