21 #define DEBUG_TYPE "machine-scheduler" 43 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 51 auto BB = Begin->getParent();
53 << BB->getName() <<
":\n";
55 MaxInstNum =
std::max(MaxInstNum, 1u);
56 for (;
I != End && MaxInstNum; ++
I, --MaxInstNum) {
57 if (!
I->isDebugInstr() && LIS)
64 if (!
I->isDebugInstr() && LIS)
68 if (End != BB->end()) {
80 const auto BB = Begin->getParent();
81 const auto &
MRI = BB->getParent()->getRegInfo();
87 const auto BottomMI = End == BB->end() ? std::prev(End) : End;
97 OS <<
"Region to schedule ";
101 R->MaxPressure.print(OS, &
ST);
109 OS <<
"\nAfter scheduling ";
136 auto BB = R.Begin->getParent();
137 Sch.BaseClass::startBlock(
BB);
138 Sch.BaseClass::enterRegion(
BB, R.Begin, R.End, R.NumRegionInstrs);
147 Sch.BaseClass::exitRegion();
148 Sch.BaseClass::finishBlock();
162 std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
172 , SaveMaxRP(R.MaxPressure) {
174 auto BB = R.Begin->getParent();
175 Sch.BaseClass::startBlock(
BB);
176 Sch.BaseClass::enterRegion(
BB, R.Begin, R.End, R.NumRegionInstrs);
180 Sch.BaseClass::exitRegion();
181 Sch.BaseClass::finishBlock();
190 Sch.BaseClass::schedule();
212 bool shouldTrackPressure()
const override {
return false; }
213 bool shouldTrackLaneMasks()
const override {
return false; }
215 SUnit *pickNode(
bool &IsTopNode)
override {
return nullptr; }
216 void schedNode(
SUnit *SU,
bool IsTopNode)
override {}
217 void releaseTopNode(
SUnit *SU)
override {}
218 void releaseBottomNode(
SUnit *SU)
override {}
239 auto const BBEnd = Begin->getParent()->end();
240 auto const BottomMI = End == BBEnd ? std::prev(End) : End;
244 auto AfterBottomMI = std::next(BottomMI);
245 if (AfterBottomMI == BBEnd ||
252 for (
auto I = BottomMI;
I != Begin; --
I)
258 (
dbgs() <<
"Tracked region ",
266 Range &&Schedule)
const {
267 auto const BBEnd = R.Begin->getParent()->end();
269 if (R.End != BBEnd) {
278 for (
auto I = Schedule.end(),
B = Schedule.begin();
I !=
B;) {
287 unsigned NumRegionInstrs) {
291 new (
Alloc.Allocate())
301 dbgs() <<
"Max RP: ";
302 Regions.back()->MaxPressure.print(
321 std::vector<MachineInstr*>
323 std::vector<MachineInstr*> Res;
324 Res.reserve(Schedule.
size() * 2);
330 for (
auto SU : Schedule) {
331 Res.push_back(SU->getInstr());
332 const auto &
D =
std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &
P) {
333 return P.second == SU->getInstr();
336 Res.push_back(
D->first);
344 R.BestSchedule.reset(
349 assert(R.BestSchedule.get() &&
"No schedule specified");
350 scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
351 R.BestSchedule.reset();
356 template <
typename Range>
364 auto BB = R.Begin->getParent();
366 for (
const auto &
I : Schedule) {
371 if (!
MI->isDebugInstr())
374 if (!
MI->isDebugInstr()) {
376 for (
auto &
Op :
MI->operands())
377 if (
Op.isReg() &&
Op.isDef())
378 Op.setIsUndef(
false);
387 Top = std::next(
MI->getIterator());
393 if (!std::is_same<decltype(*Schedule.begin()),
MachineInstr*>::value) {
401 R.MaxPressure = MaxRP;
407 assert((SchedMaxRP == RegionMaxRP && (MaxRP.
empty() || SchedMaxRP == MaxRP))
408 || (
dbgs() <<
"Max RP mismatch!!!\n" 409 "RP for schedule (calculated): ",
410 SchedMaxRP.print(
dbgs(), &
ST),
411 dbgs() <<
"RP for schedule (reported): ",
413 dbgs() <<
"RP after scheduling: ",
414 RegionMaxRP.print(
dbgs(), &
ST),
438 const auto Occ =
Regions.front()->MaxPressure.getOccupancy(
ST);
439 LLVM_DEBUG(
dbgs() <<
"Trying to improve occupancy, target = " << TargetOcc
440 <<
", current = " << Occ <<
'\n');
442 auto NewOcc = TargetOcc;
444 if (R->MaxPressure.getOccupancy(
ST) >= NewOcc)
456 NewOcc =
std::min(NewOcc, MaxRP.getOccupancy(
ST));
463 <<
", prev occupancy = " << Occ <<
'\n');
466 MFI->increaseOccupancy(
MF, NewOcc);
473 bool TryMaximizeOccupancy) {
476 auto TgtOcc =
MFI->getMinAllowedOccupancy();
479 auto Occ =
Regions.front()->MaxPressure.getOccupancy(
ST);
481 if (TryMaximizeOccupancy && Occ < TgtOcc)
486 const int NumPasses = Occ < TgtOcc ? 2 : 1;
490 "target occupancy = " 493 unsigned FinalOccupancy =
std::min(Occ,
MFI->getOccupancy());
495 for (
int I = 0;
I < NumPasses; ++
I) {
506 if (
RP.getOccupancy(
ST) < TgtOcc) {
507 LLVM_DEBUG(
dbgs() <<
"Didn't fit into target occupancy O" << TgtOcc);
508 if (R->BestSchedule.get() &&
509 R->BestSchedule->MaxPressure.getOccupancy(
ST) >= TgtOcc) {
515 assert(R->MaxPressure.getOccupancy(
ST) >= TgtOcc);
518 FinalOccupancy =
std::min(FinalOccupancy,
RP.getOccupancy(
ST));
521 MFI->limitOccupancy(FinalOccupancy);
530 const auto TgtOcc =
MFI->getOccupancy();
533 auto MaxPressure =
Regions.front()->MaxPressure;
535 if (!force && R->MaxPressure.less(
ST, MaxPressure, TgtOcc))
543 dbgs() <<
"\nWarning: Pressure becomes worse after minreg!";
547 if (!force && MaxPressure.less(
ST,
RP, TgtOcc))
561 bool TryMaximizeOccupancy) {
564 auto TgtOcc =
MFI->getMinAllowedOccupancy();
567 auto Occ =
Regions.front()->MaxPressure.getOccupancy(
ST);
569 if (TryMaximizeOccupancy && Occ < TgtOcc)
574 "target occupancy = " 577 unsigned FinalOccupancy =
std::min(Occ,
MFI->getOccupancy());
585 if (
RP.getOccupancy(
ST) < TgtOcc) {
586 LLVM_DEBUG(
dbgs() <<
"Didn't fit into target occupancy O" << TgtOcc);
587 if (R->BestSchedule.get() &&
588 R->BestSchedule->MaxPressure.getOccupancy(
ST) >= TgtOcc) {
595 FinalOccupancy =
std::min(FinalOccupancy,
RP.getOccupancy(
ST));
598 MFI->limitOccupancy(FinalOccupancy);
unsigned tryMaximizeOccupancy(unsigned TargetOcc=std::numeric_limits< unsigned >::max())
void enterRegion(MachineBasicBlock *BB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned RegionInstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
GCNRegPressure getRegionPressure(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End) const
AMDGPU specific subclass of TargetSubtarget.
This class represents lattice values for constants.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is a minimal scheduler strategy.
void sortRegionsByPressure(unsigned TargetOcc)
decltype(MaxPressure) moveMaxPressure()
SpecificBumpPtrAllocator< Region > Alloc
GCNRegPressure MaxPressure
std::vector< Region * > Regions
void setTargetOccupancy(unsigned Occ)
std::vector< MachineInstr * > detachSchedule(ScheduleRef Schedule) const
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
std::unique_ptr< MachineSchedStrategy > SchedImpl
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
MachineFunction & MF
Machine function.
void printRegions(raw_ostream &OS) const
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
MachineBasicBlock::iterator Begin
void finalizeSchedule() override
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
MachineSchedContext * Context
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
void scheduleLegacyMaxOccupancy(bool TryMaximizeOccupancy=true)
void scheduleBest(Region &R)
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
static LLVM_DUMP_METHOD void printLivenessInfo(raw_ostream &OS, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, const LiveIntervals *LIS)
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
GCNRPTracker::LiveRegSet getLiveRegsBefore(const MachineInstr &MI, const LiveIntervals &LIS)
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
static MachineInstr * getMachineInstr(MachineInstr *MI)
List of registers defined and used by a machine instruction.
void printSchedRP(raw_ostream &OS, const GCNRegPressure &Before, const GCNRegPressure &After) const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
void reset(const MachineInstr &MI, const LiveRegSet *LiveRegs=nullptr)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
void setBestSchedule(Region &R, ScheduleRef Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
unsigned const MachineRegisterInfo * MRI
const MachineInstr * getLastTrackedMI() const
std::vector< const SUnit * > makeGCNILPScheduler(ArrayRef< const SUnit * > BotRoots, const ScheduleDAG &DAG)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
size_t size() const
size - Get the array size.
~OverrideLegacyStrategy()
std::vector< const SUnit * > makeMinRegSchedule(ArrayRef< const SUnit * > TopRoots, const ScheduleDAG &DAG)
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
This file defines the class GCNIterativeScheduler, which uses an iterative approach to find a best sc...
void sort(IteratorTy Start, IteratorTy End)
const MachineFrameInfo & MFI
GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI, const LiveIntervals &LIS)
void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)
Use liveness information to find out which uses/defs are partially undefined/dead and adjust the Regi...
GCNRegPressure getSchedulePressure(const Region &R, Range &&Schedule) const
ArrayRef< SUnit * > getBottomRoots() const
Align max(MaybeAlign Lhs, Align Rhs)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
OverrideLegacyStrategy(Region &R, MachineSchedStrategy &OverrideStrategy, GCNIterativeScheduler &_Sch)
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
GCNUpwardRPTracker UPTracker
const MachineBasicBlock::iterator End
static LLVM_DUMP_METHOD void printRegion(raw_ostream &OS, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, const LiveIntervals *LIS, unsigned MaxInstNum=std::numeric_limits< unsigned >::max())
ArrayRef< const SUnit * > getTopRoots() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
GCNRegPressure getRegPressure(const MachineRegisterInfo &MRI, Range &&LiveRegs)
Representation of each machine instruction.
This class keeps track of the SPI_SP_INPUT_ADDR config register, which tells the hardware which inter...
BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
const TargetRegisterInfo * TRI
Target processor register info.
void printSchedResult(raw_ostream &OS, const Region *R, const GCNRegPressure &RP) const
const StrategyKind Strategy
GCNIterativeScheduler(MachineSchedContext *C, StrategyKind S)
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
void scheduleRegion(Region &R, Range &&Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void print(raw_ostream &OS, const GCNSubtarget *ST=nullptr) const
void scheduleMinReg(bool force=false)
This class implements an extremely fast bulk output stream that can only output to a stream.
MachineInstr * FirstDbgValue
MachineBasicBlock * BB
The block in which to insert instructions.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
void scheduleILP(bool TryMaximizeOccupancy=true)
MachineRegisterInfo & MRI
Virtual/real register map.
std::vector< SUnit > SUnits
The scheduling units.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void recede(const MachineInstr &MI)
RegPressureTracker RPTracker
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
Scheduling unit. This is a node in the scheduling DAG.