LLVM  14.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 (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  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 (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator();
110  I != SinglePredMBB->end(); I++) {
111  LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump(););
112  bool TakenBranch = (I->isBranch() &&
113  (TII->getBranchInfo(*I).isIndirect() ||
114  TII->getBranchInfo(*I).getMBBTarget() == MBB));
115  HazardRec->emitInstruction(&*I, TakenBranch);
116  if (TakenBranch)
117  break;
118  }
119 }
120 
122  LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
123 
124  // Advance to first terminator. The successor block will handle terminators
125  // dependent on CFG layout (T/NT branch etc).
126  advanceTo(MBB->getFirstTerminator());
127 }
128 
131  : MLI(C->MLI),
132  TII(static_cast<const SystemZInstrInfo *>
133  (C->MF->getSubtarget().getInstrInfo())),
134  MBB(nullptr), HazardRec(nullptr) {
135  const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
136  SchedModel.init(ST);
137 }
138 
140  // Delete hazard recognizers kept around for each MBB.
141  for (auto I : SchedStates) {
142  SystemZHazardRecognizer *hazrec = I.second;
143  delete hazrec;
144  }
145 }
146 
149  unsigned NumRegionInstrs) {
150  // Don't emit the terminators.
151  if (Begin->isTerminator())
152  return;
153 
154  // Emit any instructions before start of region.
155  advanceTo(Begin);
156 }
157 
158 // Pick the next node to schedule.
160  // Only scheduling top-down.
161  IsTopNode = true;
162 
163  if (Available.empty())
164  return nullptr;
165 
166  // If only one choice, return it.
167  if (Available.size() == 1) {
168  LLVM_DEBUG(dbgs() << "** Only one: ";
169  HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
170  return *Available.begin();
171  }
172 
173  // All nodes that are possible to schedule are stored in the Available set.
174  LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
175 
176  Candidate Best;
177  for (auto *SU : Available) {
178 
179  // SU is the next candidate to be compared against current Best.
180  Candidate c(SU, *HazardRec);
181 
182  // Remeber which SU is the best candidate.
183  if (Best.SU == nullptr || c < Best) {
184  Best = c;
185  LLVM_DEBUG(dbgs() << "** Best so far: ";);
186  } else
187  LLVM_DEBUG(dbgs() << "** Tried : ";);
188  LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
189  dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
190 
191  // Once we know we have seen all SUs that affect grouping or use unbuffered
192  // resources, we can stop iterating if Best looks good.
193  if (!SU->isScheduleHigh && Best.noCost())
194  break;
195  }
196 
197  assert (Best.SU != nullptr);
198  return Best.SU;
199 }
200 
201 SystemZPostRASchedStrategy::Candidate::
202 Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
203  SU = SU_;
204 
205  // Check the grouping cost. For a node that must begin / end a
206  // group, it is positive if it would do so prematurely, or negative
207  // if it would fit naturally into the schedule.
208  GroupingCost = HazardRec.groupingCost(SU);
209 
210  // Check the resources cost for this SU.
211  ResourcesCost = HazardRec.resourcesCost(SU);
212 }
213 
215 operator<(const Candidate &other) {
216 
217  // Check decoder grouping.
218  if (GroupingCost < other.GroupingCost)
219  return true;
220  if (GroupingCost > other.GroupingCost)
221  return false;
222 
223  // Compare the use of resources.
224  if (ResourcesCost < other.ResourcesCost)
225  return true;
226  if (ResourcesCost > other.ResourcesCost)
227  return false;
228 
229  // Higher SU is otherwise generally better.
230  if (SU->getHeight() > other.SU->getHeight())
231  return true;
232  if (SU->getHeight() < other.SU->getHeight())
233  return false;
234 
235  // If all same, fall back to original order.
236  if (SU->NodeNum < other.SU->NodeNum)
237  return true;
238 
239  return false;
240 }
241 
242 void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
243  LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";
244  if (Available.size() == 1) dbgs() << "(only one) ";
245  Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);
246 
247  // Remove SU from Available set and update HazardRec.
248  Available.erase(SU);
249  HazardRec->EmitInstruction(SU);
250 }
251 
253  // Set isScheduleHigh flag on all SUs that we want to consider first in
254  // pickNode().
255  const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
256  bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
257  SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
258 
259  // Put all released SUs in the Available set.
260  Available.insert(SU);
261 }
llvm::SystemZPostRASchedStrategy::leaveMBB
void leaveMBB() override
Tell the strategy that current MBB is done.
Definition: SystemZMachineScheduler.cpp:121
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:316
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:127
llvm::sys::path::rbegin
reverse_iterator rbegin(StringRef path, Style style=Style::native)
Get reverse begin iterator over path.
Definition: Path.cpp:295
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:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
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:876
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:63
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:328
MachineLoopInfo.h
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:410
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:130
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:110
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::SystemZInstrInfo::getBranchInfo
SystemZII::Branch getBranchInfo(const MachineInstr &MI) const
Definition: SystemZInstrInfo.cpp:1522
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:252
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:95
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
llvm::MachineBasicBlock::pred_end
pred_iterator pred_end()
Definition: MachineBasicBlock.h:318
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
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:120
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SystemZPostRASchedStrategy::pickNode
SUnit * pickNode(bool &IsTopNode) override
Pick the next node to schedule, or return NULL.
Definition: SystemZMachineScheduler.cpp:159
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ScheduleDAGMI
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
Definition: MachineScheduler.h:266
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:242
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:139
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
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:242
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:268
llvm::SystemZPostRASchedStrategy::initPolicy
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Called for a region before scheduling.
Definition: SystemZMachineScheduler.cpp:147
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