LLVM  10.0.0svn
SystemZMachineScheduler.cpp
Go to the documentation of this file.
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 
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "machine-scheduler"
22 
23 #ifndef NDEBUG
24 // Print the set of SUs
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 // Try to find a single predecessor that would be interesting for the
38 // scheduler in the top-most region of MBB.
40  const MachineLoop *Loop) {
41  MachineBasicBlock *PredMBB = nullptr;
42  if (MBB->pred_size() == 1)
43  PredMBB = *MBB->pred_begin();
44 
45  // The loop header has two predecessors, return the latch, but not for a
46  // single block loop.
47  if (MBB->pred_size() == 2 && Loop != nullptr && Loop->getHeader() == MBB) {
48  for (auto I = MBB->pred_begin(); I != MBB->pred_end(); ++I)
49  if (Loop->contains(*I))
50  PredMBB = (*I == MBB ? nullptr : *I);
51  }
52 
53  assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB))
54  && "Loop MBB should not consider predecessor outside of loop.");
55 
56  return PredMBB;
57 }
58 
59 void SystemZPostRASchedStrategy::
60 advanceTo(MachineBasicBlock::iterator NextBegin) {
61  MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI();
63  ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB) ?
64  std::next(LastEmittedMI) : MBB->begin());
65 
66  for (; I != NextBegin; ++I) {
67  if (I->isPosition() || I->isDebugInstr())
68  continue;
69  HazardRec->emitInstruction(&*I);
70  }
71 }
72 
74  LLVM_DEBUG(HazardRec->dumpState(););
75 }
76 
78  assert ((SchedStates.find(NextMBB) == SchedStates.end()) &&
79  "Entering MBB twice?");
80  LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB));
81 
82  MBB = NextMBB;
83 
84  /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to
85  /// point to it.
86  HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel);
87  LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB);
88  if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)";
89  dbgs() << ":\n";);
90 
91  // Try to take over the state from a single predecessor, if it has been
92  // scheduled. If this is not possible, we are done.
93  MachineBasicBlock *SinglePredMBB =
94  getSingleSchedPred(MBB, MLI->getLoopFor(MBB));
95  if (SinglePredMBB == nullptr ||
96  SchedStates.find(SinglePredMBB) == SchedStates.end())
97  return;
98 
99  LLVM_DEBUG(dbgs() << "** Continued scheduling from "
100  << printMBBReference(*SinglePredMBB) << "\n";);
101 
102  HazardRec->copyState(SchedStates[SinglePredMBB]);
103  LLVM_DEBUG(HazardRec->dumpState(););
104 
105  // Emit incoming terminator(s). Be optimistic and assume that branch
106  // prediction will generally do "the right thing".
107  for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator();
108  I != SinglePredMBB->end(); I++) {
109  LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump(););
110  bool TakenBranch = (I->isBranch() &&
111  (TII->getBranchInfo(*I).Target->isReg() || // Relative branch
112  TII->getBranchInfo(*I).Target->getMBB() == MBB));
113  HazardRec->emitInstruction(&*I, TakenBranch);
114  if (TakenBranch)
115  break;
116  }
117 }
118 
120  LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
121 
122  // Advance to first terminator. The successor block will handle terminators
123  // dependent on CFG layout (T/NT branch etc).
124  advanceTo(MBB->getFirstTerminator());
125 }
126 
129  : MLI(C->MLI),
130  TII(static_cast<const SystemZInstrInfo *>
131  (C->MF->getSubtarget().getInstrInfo())),
132  MBB(nullptr), HazardRec(nullptr) {
133  const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
134  SchedModel.init(ST);
135 }
136 
138  // Delete hazard recognizers kept around for each MBB.
139  for (auto I : SchedStates) {
140  SystemZHazardRecognizer *hazrec = I.second;
141  delete hazrec;
142  }
143 }
144 
147  unsigned NumRegionInstrs) {
148  // Don't emit the terminators.
149  if (Begin->isTerminator())
150  return;
151 
152  // Emit any instructions before start of region.
153  advanceTo(Begin);
154 }
155 
156 // Pick the next node to schedule.
158  // Only scheduling top-down.
159  IsTopNode = true;
160 
161  if (Available.empty())
162  return nullptr;
163 
164  // If only one choice, return it.
165  if (Available.size() == 1) {
166  LLVM_DEBUG(dbgs() << "** Only one: ";
167  HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
168  return *Available.begin();
169  }
170 
171  // All nodes that are possible to schedule are stored in the Available set.
172  LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
173 
174  Candidate Best;
175  for (auto *SU : Available) {
176 
177  // SU is the next candidate to be compared against current Best.
178  Candidate c(SU, *HazardRec);
179 
180  // Remeber which SU is the best candidate.
181  if (Best.SU == nullptr || c < Best) {
182  Best = c;
183  LLVM_DEBUG(dbgs() << "** Best so far: ";);
184  } else
185  LLVM_DEBUG(dbgs() << "** Tried : ";);
186  LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
187  dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
188 
189  // Once we know we have seen all SUs that affect grouping or use unbuffered
190  // resources, we can stop iterating if Best looks good.
191  if (!SU->isScheduleHigh && Best.noCost())
192  break;
193  }
194 
195  assert (Best.SU != nullptr);
196  return Best.SU;
197 }
198 
199 SystemZPostRASchedStrategy::Candidate::
200 Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
201  SU = SU_;
202 
203  // Check the grouping cost. For a node that must begin / end a
204  // group, it is positive if it would do so prematurely, or negative
205  // if it would fit naturally into the schedule.
206  GroupingCost = HazardRec.groupingCost(SU);
207 
208  // Check the resources cost for this SU.
209  ResourcesCost = HazardRec.resourcesCost(SU);
210 }
211 
213 operator<(const Candidate &other) {
214 
215  // Check decoder grouping.
216  if (GroupingCost < other.GroupingCost)
217  return true;
218  if (GroupingCost > other.GroupingCost)
219  return false;
220 
221  // Compare the use of resources.
222  if (ResourcesCost < other.ResourcesCost)
223  return true;
224  if (ResourcesCost > other.ResourcesCost)
225  return false;
226 
227  // Higher SU is otherwise generally better.
228  if (SU->getHeight() > other.SU->getHeight())
229  return true;
230  if (SU->getHeight() < other.SU->getHeight())
231  return false;
232 
233  // If all same, fall back to original order.
234  if (SU->NodeNum < other.SU->NodeNum)
235  return true;
236 
237  return false;
238 }
239 
240 void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
241  LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";
242  if (Available.size() == 1) dbgs() << "(only one) ";
243  Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);
244 
245  // Remove SU from Available set and update HazardRec.
246  Available.erase(SU);
247  HazardRec->EmitInstruction(SU);
248 }
249 
251  // Set isScheduleHigh flag on all SUs that we want to consider first in
252  // pickNode().
253  const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
254  bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
255  SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
256 
257  // Put all released SUs in the Available set.
258  Available.insert(SU);
259 }
uint64_t CallInst * C
void releaseTopNode(SUnit *SU) override
SU has had all predecessor dependencies resolved.
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SUnit * pickNode(bool &IsTopNode) override
Pick the next node to schedule, or return NULL.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:322
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
reverse_iterator rbegin(StringRef path, Style style=Style::native)
Get reverse begin iterator over path.
Definition: Path.cpp:295
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Called for a region before scheduling.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
int groupingCost(SUnit *SU) const
Return the cost of decoder grouping for SU.
BlockT * getHeader() const
Definition: LoopInfo.h:105
SystemZHazardRecognizer maintains the state for one MBB during scheduling.
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
const MachineOperand * Target
void schedNode(SUnit *SU, bool IsTopNode) override
ScheduleDAGMI has scheduled an instruction - tell HazardRec about it.
bool isValid() const
Definition: MCSchedule.h:127
void copyState(SystemZHazardRecognizer *Incoming)
Copy counters from end of single predecessor.
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:288
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Summarize the scheduling resources required for an instruction of a particular scheduling class...
Definition: MCSchedule.h:110
int resourcesCost(SUnit *SU)
Return the cost of SU in regards to processor resources usage.
void leaveMBB() override
Tell the strategy that current MBB is done.
void enterMBB(MachineBasicBlock *NextMBB) override
Tell the strategy that MBB is about to be processed.
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
void emitInstruction(MachineInstr *MI, bool TakenBranch=false)
Wrap a non-scheduled instruction in an SU and emit it.
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
CHAIN = SC CHAIN, Imm128 - System call.
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
TargetSubtargetInfo - Generic base class for all target subtargets.
SystemZPostRASchedStrategy(const MachineSchedContext *C)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
#define I(x, y, z)
Definition: MD5.cpp:58
bool isReg() const
isReg - Tests if this is a MO_Register operand.
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
MachineBasicBlock::iterator getLastEmittedMI()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
aarch64 promote const
SystemZII::Branch getBranchInfo(const MachineInstr &MI) const
static MachineBasicBlock * getSingleSchedPred(MachineBasicBlock *MBB, const MachineLoop *Loop)
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
void dumpSU(SUnit *SU, raw_ostream &OS) const
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242