1//-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- C++ -*---==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// -------------------------- Post RA scheduling ---------------------------- //
10// SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
11// the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
12// implementation that looks to optimize decoder grouping and balance the
13// usage of processor resources. Scheduler states are saved for the end
14// region of each MBB, so that a successor block can learn from it.
15//===----------------------------------------------------------------------===//
16
17#include "SystemZMachineScheduler.h"
18#include "llvm/CodeGen/MachineLoopInfo.h"
19
20using namespace llvm;
21
22#define DEBUG_TYPE "machine-scheduler"
23
24#ifndef NDEBUG
25// Print the set of SUs
26void SystemZPostRASchedStrategy::SUSet::
27dump(SystemZHazardRecognizer &HazardRec) const {
28  dbgs() << "{";
29  for (auto &SU : *this) {
30    HazardRec.dumpSU(SU, dbgs());
31    if (SU != *rbegin())
32      dbgs() << ",  ";
33  }
34  dbgs() << "}\n";
35}
36#endif
37
38// Try to find a single predecessor that would be interesting for the
39// scheduler in the top-most region of MBB.
40static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB,
41                                             const MachineLoop *Loop) {
42  MachineBasicBlock *PredMBB = nullptr;
43  if (MBB->pred_size() == 1)
44    PredMBB = *MBB->pred_begin();
45
46  // The loop header has two predecessors, return the latch, but not for a
47  // single block loop.
48  if (MBB->pred_size() == 2 && Loop != nullptr && Loop->getHeader() == MBB) {
49    for (MachineBasicBlock *Pred : MBB->predecessors())
50      if (Loop->contains(Pred))
51        PredMBB = (Pred == MBB ? nullptr : Pred);
52  }
53
54  assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB))
55          && "Loop MBB should not consider predecessor outside of loop.");
56
57  return PredMBB;
58}
59
60void SystemZPostRASchedStrategy::
61advanceTo(MachineBasicBlock::iterator NextBegin) {
62  MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI();
63  MachineBasicBlock::iterator I =
64    ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB) ?
65     std::next(LastEmittedMI) : MBB->begin());
66
67  for (; I != NextBegin; ++I) {
68    if (I->isPosition() || I->isDebugInstr())
69      continue;
70    HazardRec->emitInstruction(&*I);
71  }
72}
73
74void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {
75  Available.clear();  // -misched-cutoff.
76  LLVM_DEBUG(HazardRec->dumpState(););
77}
78
79void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) {
80  assert ((SchedStates.find(NextMBB) == SchedStates.end()) &&
81          "Entering MBB twice?");
82  LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB));
83
84  MBB = NextMBB;
85
86  /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to
87  /// point to it.
88  HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel);
89  LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB);
90             if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)";
91             dbgs() << ":\n";);
92
93  // Try to take over the state from a single predecessor, if it has been
94  // scheduled. If this is not possible, we are done.
95  MachineBasicBlock *SinglePredMBB =
96    getSingleSchedPred(MBB, MLI->getLoopFor(MBB));
97  if (SinglePredMBB == nullptr ||
98      SchedStates.find(SinglePredMBB) == SchedStates.end())
99    return;
100
101  LLVM_DEBUG(dbgs() << "** Continued scheduling from "
102                    << printMBBReference(*SinglePredMBB) << "\n";);
103
104  HazardRec->copyState(SchedStates[SinglePredMBB]);
105  LLVM_DEBUG(HazardRec->dumpState(););
106
107  // Emit incoming terminator(s). Be optimistic and assume that branch
108  // prediction will generally do "the right thing".
109  for (MachineInstr &MI : SinglePredMBB->terminators()) {
110    LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; MI.dump(););
111    bool TakenBranch = (MI.isBranch() &&
112                        (TII->getBranchInfo(MI).isIndirect() ||
113                         TII->getBranchInfo(MI).getMBBTarget() == MBB));
114    HazardRec->emitInstruction(&MI, TakenBranch);
115    if (TakenBranch)
116      break;
117  }
118}
119
120void SystemZPostRASchedStrategy::leaveMBB() {
121  LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
122
123  // Advance to first terminator. The successor block will handle terminators
124  // dependent on CFG layout (T/NT branch etc).
125  advanceTo(MBB->getFirstTerminator());
126}
127
128SystemZPostRASchedStrategy::
129SystemZPostRASchedStrategy(const MachineSchedContext *C)
130  : MLI(C->MLI),
131    TII(static_cast<const SystemZInstrInfo *>
132        (C->MF->getSubtarget().getInstrInfo())),
133    MBB(nullptr), HazardRec(nullptr) {
134  const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
135  SchedModel.init(ST);
136}
137
138SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {
139  // Delete hazard recognizers kept around for each MBB.
140  for (auto I : SchedStates) {
141    SystemZHazardRecognizer *hazrec = I.second;
142    delete hazrec;
143  }
144}
145
146void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
147                                            MachineBasicBlock::iterator End,
148                                            unsigned NumRegionInstrs) {
149  // Don't emit the terminators.
150  if (Begin->isTerminator())
151    return;
152
153  // Emit any instructions before start of region.
154  advanceTo(Begin);
155}
156
157// Pick the next node to schedule.
158SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
159  // Only scheduling top-down.
160  IsTopNode = true;
161
162  if (Available.empty())
163    return nullptr;
164
165  // If only one choice, return it.
166  if (Available.size() == 1) {
167    LLVM_DEBUG(dbgs() << "** Only one: ";
168               HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
169    return *Available.begin();
170  }
171
172  // All nodes that are possible to schedule are stored in the Available set.
173  LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
174
175  Candidate Best;
176  for (auto *SU : Available) {
177
178    // SU is the next candidate to be compared against current Best.
179    Candidate c(SU, *HazardRec);
180
181    // Remeber which SU is the best candidate.
182    if (Best.SU == nullptr || c < Best) {
183      Best = c;
184      LLVM_DEBUG(dbgs() << "** Best so far: ";);
185    } else
186      LLVM_DEBUG(dbgs() << "** Tried      : ";);
187    LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
188               dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
189
190    // Once we know we have seen all SUs that affect grouping or use unbuffered
191    // resources, we can stop iterating if Best looks good.
192    if (!SU->isScheduleHigh && Best.noCost())
193      break;
194  }
195
196  assert (Best.SU != nullptr);
197  return Best.SU;
198}
199
200SystemZPostRASchedStrategy::Candidate::
201Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
202  SU = SU_;
203
204  // Check the grouping cost. For a node that must begin / end a
205  // group, it is positive if it would do so prematurely, or negative
206  // if it would fit naturally into the schedule.
207  GroupingCost = HazardRec.groupingCost(SU);
208
209  // Check the resources cost for this SU.
210  ResourcesCost = HazardRec.resourcesCost(SU);
211}
212
213bool SystemZPostRASchedStrategy::Candidate::
214operator<(const Candidate &other) {
215
216  // Check decoder grouping.
217  if (GroupingCost < other.GroupingCost)
218    return true;
219  if (GroupingCost > other.GroupingCost)
220    return false;
221
222  // Compare the use of resources.
223  if (ResourcesCost < other.ResourcesCost)
224    return true;
225  if (ResourcesCost > other.ResourcesCost)
226    return false;
227
228  // Higher SU is otherwise generally better.
229  if (SU->getHeight() > other.SU->getHeight())
230    return true;
231  if (SU->getHeight() < other.SU->getHeight())
232    return false;
233
234  // If all same, fall back to original order.
235  if (SU->NodeNum < other.SU->NodeNum)
236    return true;
237
238  return false;
239}
240
241void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
242  LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";
243             if (Available.size() == 1) dbgs() << "(only one) ";
244             Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);
245
246  // Remove SU from Available set and update HazardRec.
247  Available.erase(SU);
248  HazardRec->EmitInstruction(SU);
249}
250
251void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
252  // Set isScheduleHigh flag on all SUs that we want to consider first in
253  // pickNode().
254  const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
255  bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
256  SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
257
258  // Put all released SUs in the Available set.
259  Available.insert(SU);
260}
261