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 
19 
20 using namespace llvm;
21 
22 #define DEBUG_TYPE "machine-scheduler"
23 
24 #ifndef NDEBUG
25 // Print the set of SUs
27 dump(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.
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 (auto I = MBB->pred_begin(); I != MBB->pred_end(); ++I)
50  if (Loop->contains(*I))
51  PredMBB = (*I == MBB ? nullptr : *I);
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 
60 void SystemZPostRASchedStrategy::
61 advanceTo(MachineBasicBlock::iterator NextBegin) {
62  MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI();
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 
75  LLVM_DEBUG(HazardRec->dumpState(););
76 }
77 
79  assert ((SchedStates.find(NextMBB) == SchedStates.end()) &&
80  "Entering MBB twice?");
81  LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB));
82 
83  MBB = NextMBB;
84 
85  /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to
86  /// point to it.
87  HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel);
88  LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB);
89  if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)";
90  dbgs() << ":\n";);
91 
92  // Try to take over the state from a single predecessor, if it has been
93  // scheduled. If this is not possible, we are done.
94  MachineBasicBlock *SinglePredMBB =
95  getSingleSchedPred(MBB, MLI->getLoopFor(MBB));
96  if (SinglePredMBB == nullptr ||
97  SchedStates.find(SinglePredMBB) == SchedStates.end())
98  return;
99 
100  LLVM_DEBUG(dbgs() << "** Continued scheduling from "
101  << printMBBReference(*SinglePredMBB) << "\n";);
102 
103  HazardRec->copyState(SchedStates[SinglePredMBB]);
104  LLVM_DEBUG(HazardRec->dumpState(););
105 
106  // Emit incoming terminator(s). Be optimistic and assume that branch
107  // prediction will generally do "the right thing".
108  for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator();
109  I != SinglePredMBB->end(); I++) {
110  LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump(););
111  bool TakenBranch = (I->isBranch() &&
112  (TII->getBranchInfo(*I).isIndirect() ||
113  TII->getBranchInfo(*I).getMBBTarget() == MBB));
114  HazardRec->emitInstruction(&*I, TakenBranch);
115  if (TakenBranch)
116  break;
117  }
118 }
119 
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 
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 
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 
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.
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 
200 SystemZPostRASchedStrategy::Candidate::
201 Candidate(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 
214 operator<(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 
241 void 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 
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 }
uint64_t CallInst * C
void releaseTopNode(SUnit *SU) override
SU has had all predecessor dependencies resolved.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
MachineBasicBlock * getMBBTarget()
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...
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
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
MachineBasicBlock::iterator getLastEmittedMI()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
#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