35#include "llvm/Config/llvm-config.h"
44#define DEBUG_TYPE "post-RA-sched"
48STATISTIC(NumFixedAnti,
"Number of fixed anti-dependencies");
55 cl::desc(
"Enable scheduling after register allocation"),
59 cl::desc(
"Break post-RA scheduling anti-dependencies: "
60 "\"critical\", \"all\", or \"none\""),
66 cl::desc(
"Debug control MBBs that are scheduled"),
70 cl::desc(
"Debug control MBBs that are scheduled"),
97 MachineFunctionProperties::Property::NoVRegs);
102 char PostRAScheduler::ID = 0;
113 std::vector<SUnit*> PendingQueue;
128 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
134 unsigned EndIndex = 0;
137 SchedulePostRATDList(
143 ~SchedulePostRATDList()
override;
151 void setEndIndex(
unsigned EndIdx) { EndIndex = EndIdx; }
157 unsigned regioninstrs)
override;
179 void postProcessDAG();
181 void ReleaseSucc(
SUnit *SU,
SDep *SuccEdge);
182 void ReleaseSuccessors(
SUnit *SU);
183 void ScheduleNodeTopDown(
SUnit *SU,
unsigned CurCycle);
184 void ListScheduleTopDown();
186 void dumpSchedule()
const;
187 void emitNoop(
unsigned CurCycle);
194 "Post RA top-down list latency scheduler",
false,
false)
196SchedulePostRATDList::SchedulePostRATDList(
204 MF.getSubtarget().getInstrItineraryData();
206 MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
208 MF.getSubtarget().getPostRAMutations(Mutations);
210 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
211 MRI.tracksLiveness()) &&
212 "Live-ins must be accurate for anti-dependency breaking");
213 AntiDepBreak = ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL)
215 : ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL)
220SchedulePostRATDList::~SchedulePostRATDList() {
229 unsigned regioninstrs) {
235void SchedulePostRATDList::exitRegion() {
237 dbgs() <<
"*** Final schedule ***\n";
244#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
247 for (
const SUnit *SU : Sequence) {
251 dbgs() <<
"**** NOOP ****\n";
262 return ST.enablePostRAScheduler() &&
263 OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
276 TII = Subtarget.getInstrInfo();
277 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
278 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
280 Subtarget.getAntiDepBreakMode();
283 ? TargetSubtargetInfo::ANTIDEP_ALL
285 ? TargetSubtargetInfo::ANTIDEP_CRITICAL
286 : TargetSubtargetInfo::ANTIDEP_NONE);
289 Subtarget.getCriticalPathRCs(CriticalPathRCs);
294 SchedulePostRATDList
Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode,
298 for (
auto &
MBB : Fn) {
302 static int bbcnt = 0;
305 dbgs() <<
"*** DEBUG scheduling " << Fn.getName() <<
":"
316 unsigned Count =
MBB.
size(), CurrentCount = Count;
324 Scheduler.enterRegion(&
MBB,
I, Current, CurrentCount - Count);
330 CurrentCount = Count;
335 Count -=
MI.getBundleSize();
337 assert(Count == 0 &&
"Instruction count mismatch!");
339 "Instruction count mismatch!");
366 AntiDepBreak->StartBlock(BB);
371void SchedulePostRATDList::schedule() {
377 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd,
378 EndIndex, DbgValues);
390 NumFixedAnti += Broken;
399 AvailableQueue.initNodes(SUnits);
400 ListScheduleTopDown();
401 AvailableQueue.releaseState();
407void SchedulePostRATDList::Observe(
MachineInstr &
MI,
unsigned Count) {
409 AntiDepBreak->Observe(
MI, Count, EndIndex);
414void SchedulePostRATDList::finishBlock() {
416 AntiDepBreak->FinishBlock();
423void SchedulePostRATDList::postProcessDAG() {
424 for (
auto &M : Mutations)
434void SchedulePostRATDList::ReleaseSucc(
SUnit *SU,
SDep *SuccEdge) {
443 dbgs() <<
"*** Scheduling failed! ***\n";
445 dbgs() <<
" has been released too many times!\n";
465 PendingQueue.push_back(SuccSU);
469void SchedulePostRATDList::ReleaseSuccessors(
SUnit *SU) {
472 ReleaseSucc(SU, &*
I);
479void SchedulePostRATDList::ScheduleNodeTopDown(
SUnit *SU,
unsigned CurCycle) {
485 "Node scheduled above its depth!");
488 ReleaseSuccessors(SU);
490 AvailableQueue.scheduledNode(SU);
494void SchedulePostRATDList::emitNoop(
unsigned CurCycle) {
495 LLVM_DEBUG(
dbgs() <<
"*** Emitting noop in cycle " << CurCycle <<
'\n');
496 HazardRec->EmitNoop();
503void SchedulePostRATDList::ListScheduleTopDown() {
504 unsigned CurCycle = 0;
513 ReleaseSuccessors(&EntrySU);
519 AvailableQueue.push(&
SUnit);
526 bool CycleHasInsts =
false;
530 std::vector<SUnit*> NotReady;
532 while (!AvailableQueue.empty() || !PendingQueue.empty()) {
535 unsigned MinDepth = ~0
u;
536 for (
unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
537 if (PendingQueue[i]->getDepth() <= CurCycle) {
538 AvailableQueue.push(PendingQueue[i]);
539 PendingQueue[i]->isAvailable =
true;
540 PendingQueue[i] = PendingQueue.back();
541 PendingQueue.pop_back();
543 }
else if (PendingQueue[i]->getDepth() < MinDepth)
544 MinDepth = PendingQueue[i]->getDepth();
548 AvailableQueue.dump(
this));
550 SUnit *FoundSUnit =
nullptr, *NotPreferredSUnit =
nullptr;
551 bool HasNoopHazards =
false;
552 while (!AvailableQueue.empty()) {
553 SUnit *CurSUnit = AvailableQueue.pop();
556 HazardRec->getHazardType(CurSUnit, 0);
558 if (HazardRec->ShouldPreferAnother(CurSUnit)) {
559 if (!NotPreferredSUnit) {
564 NotPreferredSUnit = CurSUnit;
568 FoundSUnit = CurSUnit;
576 NotReady.push_back(CurSUnit);
582 if (NotPreferredSUnit) {
585 dbgs() <<
"*** Will schedule a non-preferred instruction...\n");
586 FoundSUnit = NotPreferredSUnit;
588 AvailableQueue.push(NotPreferredSUnit);
591 NotPreferredSUnit =
nullptr;
595 if (!NotReady.empty()) {
596 AvailableQueue.push_all(NotReady);
603 unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);
604 for (
unsigned i = 0; i != NumPreNoops; ++i)
608 ScheduleNodeTopDown(FoundSUnit, CurCycle);
609 HazardRec->EmitInstruction(FoundSUnit);
610 CycleHasInsts =
true;
611 if (HazardRec->atIssueLimit()) {
612 LLVM_DEBUG(
dbgs() <<
"*** Max instructions per cycle " << CurCycle
614 HazardRec->AdvanceCycle();
616 CycleHasInsts =
false;
621 HazardRec->AdvanceCycle();
622 }
else if (!HasNoopHazards) {
626 HazardRec->AdvanceCycle();
636 CycleHasInsts =
false;
641 unsigned ScheduledNodes = VerifyScheduledDAG(
false);
644 "The number of nodes scheduled doesn't match the expected number!");
649void SchedulePostRATDList::EmitSchedule() {
650 RegionBegin = RegionEnd;
654 BB->
splice(RegionEnd, BB, FirstDbgValue);
657 for (
unsigned i = 0, e =
Sequence.size(); i != e; i++) {
658 if (
SUnit *SU = Sequence[i])
667 RegionBegin = std::prev(RegionEnd);
671 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
672 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
673 std::pair<MachineInstr *, MachineInstr *>
P = *std::prev(DI);
679 FirstDbgValue =
nullptr;
unsigned const MachineRegisterInfo * MRI
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
const HexagonInstrInfo * TII
Machine Instruction Scheduler
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static cl::opt< int > DebugDiv("postra-sched-debugdiv", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)
static cl::opt< bool > EnablePostRAScheduler("post-RA-scheduler", cl::desc("Enable scheduling after register allocation"), cl::init(false), cl::Hidden)
static cl::opt< std::string > EnableAntiDepBreaking("break-anti-dependencies", cl::desc("Break post-RA scheduling anti-dependencies: " "\"critical\", \"all\", or \"none\""), cl::init("none"), cl::Hidden)
static bool enablePostRAScheduler(const TargetSubtargetInfo &ST, CodeGenOptLevel OptLevel)
static cl::opt< int > DebugMod("postra-sched-debugmod", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Target-Independent Code Generator Pass Configuration Options pass.
Class recording the (high level) value of a variable.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
virtual ~AntiDepBreaker()
void insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const override
Insert a noop into the instruction stream at the specified point.
bool isSchedulingBoundary(const MachineInstr &MI, const MachineBasicBlock *MBB, const MachineFunction &MF) const override
Test if the given instruction should be considered a scheduling boundary.
Itinerary data supplied by a subtarget to be used by a target.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Analysis pass which computes a MachineDominatorTree.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
bool isWeak() const
Tests if this a weak dependence.
Scheduling unit. This is a node in the scheduling DAG.
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
bool isScheduled
True once scheduled.
bool isAvailable
True once available.
SmallVector< SDep, 4 > Succs
All sunit successors.
SmallVectorImpl< SDep >::iterator succ_iterator
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node's depth value, sets it to be the new depth value.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
A ScheduleDAG for scheduling lists of MachineInstr.
virtual void finishBlock()
Cleans up after scheduling in the given block.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
virtual void schedule()=0
Orders nodes according to selected style.
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
void clearDAG()
Clears the DAG state (between regions).
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
Target-Independent Code Generator Pass Configuration Options.
CodeGenOptLevel getOptLevel() const
TargetSubtargetInfo - Generic base class for all target subtargets.
enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL } AntiDepBreakMode
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
AntiDepBreaker * createAggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
char & PostRASchedulerID
PostRAScheduler - This pass performs post register allocation scheduling.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
CodeGenOptLevel
Code generation optimization level.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
AntiDepBreaker * createCriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.