LLVM  15.0.0git
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 (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 
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  Available.clear(); // -misched-cutoff.
76  LLVM_DEBUG(HazardRec->dumpState(););
77 }
78 
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 
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 }
llvm::SystemZPostRASchedStrategy::leaveMBB
void leaveMBB() override
Tell the strategy that current MBB is done.
Definition: SystemZMachineScheduler.cpp:120
llvm::SystemZHazardRecognizer::EmitInstruction
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
Definition: SystemZHazardRecognizer.cpp:271
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:326
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:126
llvm::sys::path::rbegin
reverse_iterator rbegin(StringRef path, Style style=Style::native)
Get reverse begin iterator over path.
Definition: Path.cpp:297
llvm::SystemZPostRASchedStrategy::enterMBB
void enterMBB(MachineBasicBlock *NextMBB) override
Tell the strategy that MBB is about to be processed.
Definition: SystemZMachineScheduler.cpp:79
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:116
llvm::SystemZHazardRecognizer::getSchedClass
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
Definition: SystemZHazardRecognizer.h:121
llvm::SystemZInstrInfo
Definition: SystemZInstrInfo.h:174
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::SystemZHazardRecognizer
SystemZHazardRecognizer maintains the state for one MBB during scheduling.
Definition: SystemZHazardRecognizer.h:45
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::TargetSchedModel::init
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
Definition: TargetSchedule.cpp:62
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:338
MachineLoopInfo.h
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:418
llvm::SUnit::isUnbuffered
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:288
llvm::SUnit::isScheduleHigh
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
llvm::SystemZPostRASchedStrategy::SystemZPostRASchedStrategy
SystemZPostRASchedStrategy(const MachineSchedContext *C)
Definition: SystemZMachineScheduler.cpp:129
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::SUnit::NodeNum
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
llvm::MCSchedClassDesc
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:109
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::SystemZInstrInfo::getBranchInfo
SystemZII::Branch getBranchInfo(const MachineInstr &MI) const
Definition: SystemZInstrInfo.cpp:1539
llvm::SystemZII::Branch::getMBBTarget
MachineBasicBlock * getMBBTarget()
Definition: SystemZInstrInfo.h:131
llvm::SystemZPostRASchedStrategy::releaseTopNode
void releaseTopNode(SUnit *SU) override
SU has had all predecessor dependencies resolved.
Definition: SystemZMachineScheduler.cpp:251
c
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int c
Definition: README.txt:418
llvm::SystemZHazardRecognizer::copyState
void copyState(SystemZHazardRecognizer *Incoming)
Copy counters from end of single predecessor.
Definition: SystemZHazardRecognizer.cpp:451
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
llvm::SystemZHazardRecognizer::emitInstruction
void emitInstruction(MachineInstr *MI, bool TakenBranch=false)
Wrap a non-scheduled instruction in an SU and emit it.
Definition: SystemZHazardRecognizer.cpp:410
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::MachineSchedContext
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
Definition: MachineScheduler.h:125
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SystemZPostRASchedStrategy::pickNode
SUnit * pickNode(bool &IsTopNode) override
Pick the next node to schedule, or return NULL.
Definition: SystemZMachineScheduler.cpp:158
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:359
llvm::ScheduleDAGMI
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
Definition: MachineScheduler.h:271
llvm::SystemZHazardRecognizer::getLastEmittedMI
MachineBasicBlock::iterator getLastEmittedMI()
Definition: SystemZHazardRecognizer.h:153
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:238
llvm::SystemZHazardRecognizer::groupingCost
int groupingCost(SUnit *SU) const
Return the cost of decoder grouping for SU.
Definition: SystemZHazardRecognizer.cpp:340
llvm::SystemZHazardRecognizer::resourcesCost
int resourcesCost(SUnit *SU)
Return the cost of SU in regards to processor resources usage.
Definition: SystemZHazardRecognizer.cpp:387
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy
virtual ~SystemZPostRASchedStrategy()
Definition: SystemZMachineScheduler.cpp:138
llvm::Pass::dump
void dump() const
Definition: Pass.cpp:135
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:60
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
getSingleSchedPred
static MachineBasicBlock * getSingleSchedPred(MachineBasicBlock *MBB, const MachineLoop *Loop)
Definition: SystemZMachineScheduler.cpp:40
llvm::SystemZII::Branch::isIndirect
bool isIndirect()
Definition: SystemZInstrInfo.h:129
operator<
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::SystemZHazardRecognizer::dumpSU
void dumpSU(SUnit *SU, raw_ostream &OS) const
Definition: SystemZHazardRecognizer.cpp:167
llvm::SystemZPostRASchedStrategy::schedNode
void schedNode(SUnit *SU, bool IsTopNode) override
ScheduleDAGMI has scheduled an instruction - tell HazardRec about it.
Definition: SystemZMachineScheduler.cpp:241
llvm::SystemZPostRASchedStrategy::initialize
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
Definition: SystemZMachineScheduler.cpp:74
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:278
llvm::SystemZPostRASchedStrategy::initPolicy
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Called for a region before scheduling.
Definition: SystemZMachineScheduler.cpp:146
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::MachineInstrBundleIterator< MachineInstr >
SystemZMachineScheduler.h
llvm::SystemZHazardRecognizer::dumpState
void dumpState() const
Definition: SystemZHazardRecognizer.cpp:248