1 //-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- C++ -*---==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // -------------------------- Post RA scheduling ---------------------------- //
11 // SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
12 // the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
13 // implementation that looks to optimize decoder grouping and balance the
14 // usage of processor resources.
15 //===----------------------------------------------------------------------===//
16 
17 #include "SystemZMachineScheduler.h"
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "machine-scheduler"
22 
23 #ifndef NDEBUG
24 // Print the set of SUs
25 void SystemZPostRASchedStrategy::SUSet::
26 dump(SystemZHazardRecognizer &HazardRec) const {
27   dbgs() << "{";
28   for (auto &SU : *this) {
29     HazardRec.dumpSU(SU, dbgs());
30     if (SU != *rbegin())
31       dbgs() << ",  ";
32   }
33   dbgs() << "}\n";
34 }
35 #endif
36 
37 SystemZPostRASchedStrategy::
38 SystemZPostRASchedStrategy(const MachineSchedContext *C)
39   : DAG(nullptr), HazardRec(C) {}
40 
41 void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {
42   DAG = dag;
43   HazardRec.setDAG(dag);
44   HazardRec.Reset();
45 }
46 
47 // Pick the next node to schedule.
48 SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
49   // Only scheduling top-down.
50   IsTopNode = true;
51 
52   if (Available.empty())
53     return nullptr;
54 
55   // If only one choice, return it.
56   if (Available.size() == 1) {
57     DEBUG (dbgs() << "+++ Only one: ";
58            HazardRec.dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
59     return *Available.begin();
60   }
61 
62   // All nodes that are possible to schedule are stored by in the
63   // Available set.
64   DEBUG(dbgs() << "+++ Available: "; Available.dump(HazardRec););
65 
66   Candidate Best;
67   for (auto *SU : Available) {
68 
69     // SU is the next candidate to be compared against current Best.
70     Candidate c(SU, HazardRec);
71 
72     // Remeber which SU is the best candidate.
73     if (Best.SU == nullptr || c < Best) {
74       Best = c;
75       DEBUG(dbgs() << "+++ Best sofar: ";
76             HazardRec.dumpSU(Best.SU, dbgs());
77             if (Best.GroupingCost != 0)
78               dbgs() << "\tGrouping cost:" << Best.GroupingCost;
79             if (Best.ResourcesCost != 0)
80               dbgs() << " Resource cost:" << Best.ResourcesCost;
81             dbgs() << " Height:" << Best.SU->getHeight();
82             dbgs() << "\n";);
83     }
84 
85     // Once we know we have seen all SUs that affect grouping or use unbuffered
86     // resources, we can stop iterating if Best looks good.
87     if (!SU->isScheduleHigh && Best.noCost())
88       break;
89   }
90 
91   assert (Best.SU != nullptr);
92   return Best.SU;
93 }
94 
95 SystemZPostRASchedStrategy::Candidate::
96 Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
97   SU = SU_;
98 
99   // Check the grouping cost. For a node that must begin / end a
100   // group, it is positive if it would do so prematurely, or negative
101   // if it would fit naturally into the schedule.
102   GroupingCost = HazardRec.groupingCost(SU);
103 
104     // Check the resources cost for this SU.
105   ResourcesCost = HazardRec.resourcesCost(SU);
106 }
107 
108 bool SystemZPostRASchedStrategy::Candidate::
109 operator<(const Candidate &other) {
110 
111   // Check decoder grouping.
112   if (GroupingCost < other.GroupingCost)
113     return true;
114   if (GroupingCost > other.GroupingCost)
115     return false;
116 
117   // Compare the use of resources.
118   if (ResourcesCost < other.ResourcesCost)
119     return true;
120   if (ResourcesCost > other.ResourcesCost)
121     return false;
122 
123   // Higher SU is otherwise generally better.
124   if (SU->getHeight() > other.SU->getHeight())
125     return true;
126   if (SU->getHeight() < other.SU->getHeight())
127     return false;
128 
129   // If all same, fall back to original order.
130   if (SU->NodeNum < other.SU->NodeNum)
131     return true;
132 
133   return false;
134 }
135 
136 void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
137   DEBUG(dbgs() << "+++ Scheduling SU(" << SU->NodeNum << ")\n";);
138 
139   // Remove SU from Available set and update HazardRec.
140   Available.erase(SU);
141   HazardRec.EmitInstruction(SU);
142 }
143 
144 void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
145   // Set isScheduleHigh flag on all SUs that we want to consider first in
146   // pickNode().
147   const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
148   bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
149   SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
150 
151   // Put all released SUs in the Available set.
152   Available.insert(SU);
153 }
154