Go to the documentation of this file.
20 #define DEBUG_TYPE "machine-scheduler"
42 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
50 auto BB = Begin->getParent();
52 <<
BB->getName() <<
":\n";
54 MaxInstNum =
std::max(MaxInstNum, 1u);
55 for (;
I != End && MaxInstNum; ++
I, --MaxInstNum) {
56 if (!
I->isDebugInstr() && LIS)
63 if (!
I->isDebugInstr() && LIS)
67 if (End !=
BB->end()) {
79 const auto BB = Begin->getParent();
80 const auto &
MRI =
BB->getParent()->getRegInfo();
86 const auto BottomMI = End ==
BB->end() ? std::prev(End) : End;
96 OS <<
"Region to schedule ";
100 R->MaxPressure.print(OS, &
ST);
108 OS <<
"\nAfter scheduling ";
135 auto BB = R.Begin->getParent();
136 Sch.BaseClass::startBlock(
BB);
137 Sch.BaseClass::enterRegion(
BB, R.Begin, R.End, R.NumRegionInstrs);
146 Sch.BaseClass::exitRegion();
147 Sch.BaseClass::finishBlock();
161 std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
171 , SaveMaxRP(R.MaxPressure) {
173 auto BB = R.Begin->getParent();
174 Sch.BaseClass::startBlock(
BB);
175 Sch.BaseClass::enterRegion(
BB, R.Begin, R.End, R.NumRegionInstrs);
179 Sch.BaseClass::exitRegion();
180 Sch.BaseClass::finishBlock();
189 Sch.BaseClass::schedule();
211 bool shouldTrackPressure()
const override {
return false; }
212 bool shouldTrackLaneMasks()
const override {
return false; }
214 SUnit *pickNode(
bool &IsTopNode)
override {
return nullptr; }
215 void schedNode(
SUnit *SU,
bool IsTopNode)
override {}
216 void releaseTopNode(
SUnit *SU)
override {}
217 void releaseBottomNode(
SUnit *SU)
override {}
238 auto const BBEnd = Begin->getParent()->end();
239 auto const BottomMI = End == BBEnd ? std::prev(End) : End;
243 auto AfterBottomMI = std::next(BottomMI);
244 if (AfterBottomMI == BBEnd ||
251 for (
auto I = BottomMI;
I != Begin; --
I)
257 (
dbgs() <<
"Tracked region ",
265 Range &&Schedule)
const {
266 auto const BBEnd = R.Begin->getParent()->end();
268 if (R.End != BBEnd) {
277 for (
auto I = Schedule.end(),
B = Schedule.begin();
I !=
B;) {
286 unsigned NumRegionInstrs) {
290 new (
Alloc.Allocate())
291 Region { Begin, End, NumRegionInstrs,
292 getRegionPressure(Begin, End), nullptr });
300 dbgs() <<
"Max RP: ";
301 Regions.back()->MaxPressure.print(
302 dbgs(), &MF.getSubtarget<GCNSubtarget>());
320 std::vector<MachineInstr*>
322 std::vector<MachineInstr*> Res;
323 Res.reserve(Schedule.
size() * 2);
329 for (
auto SU : Schedule) {
330 Res.push_back(SU->getInstr());
331 const auto &
D =
std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &
P) {
332 return P.second == SU->getInstr();
335 Res.push_back(
D->first);
343 R.BestSchedule.reset(
348 assert(R.BestSchedule.get() &&
"No schedule specified");
349 scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
350 R.BestSchedule.reset();
355 template <
typename Range>
363 auto BB = R.Begin->getParent();
365 for (
const auto &
I : Schedule) {
370 if (!
MI->isDebugInstr())
373 if (!
MI->isDebugInstr()) {
375 for (
auto &
Op :
MI->operands())
376 if (
Op.isReg() &&
Op.isDef())
377 Op.setIsUndef(
false);
386 Top = std::next(
MI->getIterator());
392 if (!std::is_same<decltype(*Schedule.begin()),
MachineInstr*>::value) {
400 R.MaxPressure = MaxRP;
406 assert((SchedMaxRP == RegionMaxRP && (MaxRP.
empty() || SchedMaxRP == MaxRP))
407 || (
dbgs() <<
"Max RP mismatch!!!\n"
408 "RP for schedule (calculated): ",
409 SchedMaxRP.print(
dbgs(), &
ST),
410 dbgs() <<
"RP for schedule (reported): ",
412 dbgs() <<
"RP after scheduling: ",
413 RegionMaxRP.print(
dbgs(), &
ST),
437 const auto Occ =
Regions.front()->MaxPressure.getOccupancy(
ST);
438 LLVM_DEBUG(
dbgs() <<
"Trying to improve occupancy, target = " << TargetOcc
439 <<
", current = " << Occ <<
'\n');
441 auto NewOcc = TargetOcc;
443 if (R->MaxPressure.getOccupancy(
ST) >= NewOcc)
455 NewOcc =
std::min(NewOcc, MaxRP.getOccupancy(
ST));
462 <<
", prev occupancy = " << Occ <<
'\n');
465 MFI->increaseOccupancy(
MF, NewOcc);
472 bool TryMaximizeOccupancy) {
475 auto TgtOcc =
MFI->getMinAllowedOccupancy();
478 auto Occ =
Regions.front()->MaxPressure.getOccupancy(
ST);
480 if (TryMaximizeOccupancy && Occ < TgtOcc)
485 const int NumPasses = Occ < TgtOcc ? 2 : 1;
489 "target occupancy = "
492 unsigned FinalOccupancy =
std::min(Occ,
MFI->getOccupancy());
494 for (
int I = 0;
I < NumPasses; ++
I) {
505 if (
RP.getOccupancy(
ST) < TgtOcc) {
506 LLVM_DEBUG(
dbgs() <<
"Didn't fit into target occupancy O" << TgtOcc);
507 if (R->BestSchedule.get() &&
508 R->BestSchedule->MaxPressure.getOccupancy(
ST) >= TgtOcc) {
514 assert(R->MaxPressure.getOccupancy(
ST) >= TgtOcc);
517 FinalOccupancy =
std::min(FinalOccupancy,
RP.getOccupancy(
ST));
520 MFI->limitOccupancy(FinalOccupancy);
529 const auto TgtOcc =
MFI->getOccupancy();
532 auto MaxPressure =
Regions.front()->MaxPressure;
534 if (!
force && R->MaxPressure.less(
ST, MaxPressure, TgtOcc))
542 dbgs() <<
"\nWarning: Pressure becomes worse after minreg!";
543 printSchedRP(dbgs(), R->MaxPressure, RP);
546 if (!
force && MaxPressure.less(
ST,
RP, TgtOcc))
560 bool TryMaximizeOccupancy) {
563 auto TgtOcc =
MFI->getMinAllowedOccupancy();
566 auto Occ =
Regions.front()->MaxPressure.getOccupancy(
ST);
568 if (TryMaximizeOccupancy && Occ < TgtOcc)
573 "target occupancy = "
576 unsigned FinalOccupancy =
std::min(Occ,
MFI->getOccupancy());
584 if (
RP.getOccupancy(
ST) < TgtOcc) {
585 LLVM_DEBUG(
dbgs() <<
"Didn't fit into target occupancy O" << TgtOcc);
586 if (R->BestSchedule.get() &&
587 R->BestSchedule->MaxPressure.getOccupancy(
ST) >= TgtOcc) {
594 FinalOccupancy =
std::min(FinalOccupancy,
RP.getOccupancy(
ST));
597 MFI->limitOccupancy(FinalOccupancy);
MachineInstr * FirstDbgValue
MachineRegisterInfo & MRI
Virtual/real register map.
void reset(const MachineInstr &MI, const LiveRegSet *LiveRegs=nullptr)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is an optimization pass for GlobalISel generic memory operations.
unsigned tryMaximizeOccupancy(unsigned TargetOcc=std::numeric_limits< unsigned >::max())
GCNRPTracker::LiveRegSet getLiveRegsBefore(const MachineInstr &MI, const LiveIntervals &LIS)
GCNRegPressure getRegPressure(const MachineRegisterInfo &MRI, Range &&LiveRegs)
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
List of registers defined and used by a machine instruction.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
@ SCHEDULE_LEGACYMAXOCCUPANCY
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
GCNRegPressure getRegionPressure(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End) const
ArrayRef< const SUnit * > getTopRoots() const
const MachineBasicBlock::iterator End
std::vector< Region * > Regions
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI, const LiveIntervals &LIS)
static MachineInstr * getMachineInstr(MachineInstr *MI)
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
void printRegions(raw_ostream &OS) const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void recede(const MachineInstr &MI)
decltype(MaxPressure) moveMaxPressure()
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
void finalizeSchedule() override
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
const MachineInstr * getLastTrackedMI() const
This is a minimal scheduler strategy.
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
(vector float) vec_cmpeq(*A, *B) C
~OverrideLegacyStrategy()
void printSchedResult(raw_ostream &OS, const Region *R, const GCNRegPressure &RP) const
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
GCNRegPressure getSchedulePressure(const Region &R, Range &&Schedule) const
MachineSchedContext * Context
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
std::vector< const SUnit * > makeMinRegSchedule(ArrayRef< const SUnit * > TopRoots, const ScheduleDAG &DAG)
GCNUpwardRPTracker UPTracker
This class implements an extremely fast bulk output stream that can only output to a stream.
void scheduleRegion(Region &R, Range &&Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
void setTargetOccupancy(unsigned Occ)
therefore end up llgh r3 lr r0 br r14 but truncating the load would lh r3 br r14 Functions ret i64 and ought to be implemented ngr r0 br r14 but two address optimizations reverse the order of the AND and force
RegPressureTracker RPTracker
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...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void scheduleBest(Region &R)
Representation of each machine instruction.
BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
void sortRegionsByPressure(unsigned TargetOcc)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
static LLVM_DUMP_METHOD void printLivenessInfo(raw_ostream &OS, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, const LiveIntervals *LIS)
const MachineFrameInfo & MFI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
std::unique_ptr< MachineSchedStrategy > SchedImpl
SpecificBumpPtrAllocator< Region > Alloc
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
const StrategyKind Strategy
const TargetRegisterInfo * TRI
Target processor register info.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
void scheduleLegacyMaxOccupancy(bool TryMaximizeOccupancy=true)
MachineFunction & MF
Machine function.
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())
GCNRegPressure MaxPressure
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
std::vector< const SUnit * > makeGCNILPScheduler(ArrayRef< const SUnit * > BotRoots, const ScheduleDAG &DAG)
void setBestSchedule(Region &R, ScheduleRef Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
unsigned const MachineRegisterInfo * MRI
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
MachineBasicBlock::iterator Begin
OverrideLegacyStrategy(Region &R, MachineSchedStrategy &OverrideStrategy, GCNIterativeScheduler &_Sch)
std::vector< SUnit > SUnits
The scheduling units.
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
ArrayRef< SUnit * > getBottomRoots() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
void sort(IteratorTy Start, IteratorTy End)
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
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...
std::vector< MachineInstr * > detachSchedule(ScheduleRef Schedule) const
MachineBasicBlock * BB
The block in which to insert instructions.
void enterRegion(MachineBasicBlock *BB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned RegionInstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
void scheduleILP(bool TryMaximizeOccupancy=true)
This class keeps track of the SPI_SP_INPUT_ADDR config register, which tells the hardware which inter...
size_t size() const
size - Get the array size.
GCNIterativeScheduler(MachineSchedContext *C, StrategyKind S)
Scheduling unit. This is a node in the scheduling DAG.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
void print(raw_ostream &OS, const GCNSubtarget *ST=nullptr) const
void scheduleMinReg(bool force=false)
void printSchedRP(raw_ostream &OS, const GCNRegPressure &Before, const GCNRegPressure &After) const
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.