X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPostRASchedulerList.cpp;h=d57bc7362de95d217dcbb21ce43b30edf0d248c3;hb=b21d9aebba7e45ddcbce61dd501000049cefb335;hp=c73e87733cb4212421bb9e7a90084c51212baebc;hpb=5b1b4489cf3a0f56f8be0673fc5cc380a32d277b;p=oota-llvm.git diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index c73e87733cb..d57bc7362de 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -22,8 +22,6 @@ #include "AntiDepBreaker.h" #include "AggressiveAntiDepBreaker.h" #include "CriticalAntiDepBreaker.h" -#include "RegisterClassInfo.h" -#include "ScheduleDAGInstrs.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/LatencyPriorityQueue.h" #include "llvm/CodeGen/SchedulerRegistry.h" @@ -32,6 +30,8 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" #include "llvm/CodeGen/ScheduleHazardRecognizer.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Target/TargetLowering.h" @@ -45,7 +45,6 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/Statistic.h" -#include using namespace llvm; STATISTIC(NumNoops, "Number of noops inserted"); @@ -79,19 +78,17 @@ AntiDepBreaker::~AntiDepBreaker() { } namespace { class PostRAScheduler : public MachineFunctionPass { - AliasAnalysis *AA; const TargetInstrInfo *TII; RegisterClassInfo RegClassInfo; - CodeGenOpt::Level OptLevel; public: static char ID; - PostRAScheduler(CodeGenOpt::Level ol) : - MachineFunctionPass(ID), OptLevel(ol) {} + PostRAScheduler() : MachineFunctionPass(ID) {} void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); AU.addRequired(); @@ -99,10 +96,6 @@ namespace { MachineFunctionPass::getAnalysisUsage(AU); } - const char *getPassName() const { - return "Post RA top-down list latency scheduler"; - } - bool runOnMachineFunction(MachineFunction &Fn); }; char PostRAScheduler::ID = 0; @@ -130,36 +123,49 @@ namespace { /// AA - AliasAnalysis for making memory reference queries. AliasAnalysis *AA; - /// KillIndices - The index of the most recent kill (proceding bottom-up), - /// or ~0u if the register is not live. - std::vector KillIndices; + /// LiveRegs - true if the register is live. + BitVector LiveRegs; + + /// The schedule. Null SUnit*'s represent noop instructions. + std::vector Sequence; public: SchedulePostRATDList( MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, AliasAnalysis *AA, const RegisterClassInfo&, TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, - SmallVectorImpl &CriticalPathRCs); + SmallVectorImpl &CriticalPathRCs); ~SchedulePostRATDList(); - /// StartBlock - Initialize register live-range state for scheduling in + /// startBlock - Initialize register live-range state for scheduling in /// this block. /// - void StartBlock(MachineBasicBlock *BB); + void startBlock(MachineBasicBlock *BB); + + /// Initialize the scheduler state for the next scheduling region. + virtual void enterRegion(MachineBasicBlock *bb, + MachineBasicBlock::iterator begin, + MachineBasicBlock::iterator end, + unsigned endcount); + + /// Notify that the scheduler has finished scheduling the current region. + virtual void exitRegion(); /// Schedule - Schedule the instruction range using list scheduling. /// - void Schedule(); + void schedule(); + + void EmitSchedule(); /// Observe - Update liveness information to account for the current /// instruction, which will not be scheduled. /// void Observe(MachineInstr *MI, unsigned Count); - /// FinishBlock - Clean up register live-range state. + /// finishBlock - Clean up register live-range state. /// - void FinishBlock(); + void finishBlock(); /// FixupKills - Fix register kill flags that have been made /// invalid due to scheduling @@ -177,21 +183,32 @@ namespace { // adjustments may be made to the instruction if necessary. Return // true if the operand has been deleted, false if not. bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO); + + void dumpSchedule() const; }; } +char &llvm::PostRASchedulerID = PostRAScheduler::ID; + +INITIALIZE_PASS(PostRAScheduler, "post-RA-sched", + "Post RA top-down list latency scheduler", false, false) + SchedulePostRATDList::SchedulePostRATDList( MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, AliasAnalysis *AA, const RegisterClassInfo &RCI, TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, - SmallVectorImpl &CriticalPathRCs) - : ScheduleDAGInstrs(MF, MLI, MDT), Topo(SUnits), AA(AA), - KillIndices(TRI->getNumRegs()) + SmallVectorImpl &CriticalPathRCs) + : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), Topo(SUnits), AA(AA), + LiveRegs(TRI->getNumRegs()) { const TargetMachine &TM = MF.getTarget(); const InstrItineraryData *InstrItins = TM.getInstrItineraryData(); HazardRec = TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this); + + assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE || + MRI.tracksLiveness()) && + "Live-ins must be accurate for anti-dependency breaking"); AntiDepBreak = ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : @@ -204,16 +221,50 @@ SchedulePostRATDList::~SchedulePostRATDList() { delete AntiDepBreak; } +/// Initialize state associated with the next scheduling region. +void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb, + MachineBasicBlock::iterator begin, + MachineBasicBlock::iterator end, + unsigned endcount) { + ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); + Sequence.clear(); +} + +/// Print the schedule before exiting the region. +void SchedulePostRATDList::exitRegion() { + DEBUG({ + dbgs() << "*** Final schedule ***\n"; + dumpSchedule(); + dbgs() << '\n'; + }); + ScheduleDAGInstrs::exitRegion(); +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +/// dumpSchedule - dump the scheduled Sequence. +void SchedulePostRATDList::dumpSchedule() const { + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + if (SUnit *SU = Sequence[i]) + SU->dump(this); + else + dbgs() << "**** NOOP ****\n"; + } +} +#endif + bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { TII = Fn.getTarget().getInstrInfo(); MachineLoopInfo &MLI = getAnalysis(); MachineDominatorTree &MDT = getAnalysis(); AliasAnalysis *AA = &getAnalysis(); + TargetPassConfig *PassConfig = &getAnalysis(); + RegClassInfo.runOnMachineFunction(Fn); // Check for explicit enable/disable of post-ra scheduling. - TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = TargetSubtargetInfo::ANTIDEP_NONE; - SmallVector CriticalPathRCs; + TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = + TargetSubtargetInfo::ANTIDEP_NONE; + SmallVector CriticalPathRCs; if (EnablePostRAScheduler.getPosition() > 0) { if (!EnablePostRAScheduler) return false; @@ -221,7 +272,8 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { // Check that post-RA scheduling is enabled for this target. // This may upgrade the AntiDepMode. const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget(); - if (!ST.enablePostRAScheduler(OptLevel, AntiDepMode, CriticalPathRCs)) + if (!ST.enablePostRAScheduler(PassConfig->getOptLevel(), AntiDepMode, + CriticalPathRCs)) return false; } @@ -248,13 +300,13 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { static int bbcnt = 0; if (bbcnt++ % DebugDiv != DebugMod) continue; - dbgs() << "*** DEBUG scheduling " << Fn.getFunction()->getNameStr() << - ":BB#" << MBB->getNumber() << " ***\n"; + dbgs() << "*** DEBUG scheduling " << Fn.getName() + << ":BB#" << MBB->getNumber() << " ***\n"; } #endif // Initialize register live-range state for scheduling in this block. - Scheduler.StartBlock(MBB); + Scheduler.startBlock(MBB); // Schedule each sequence of instructions not interrupted by a label // or anything else that effectively needs to shut down scheduling. @@ -262,8 +314,13 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { unsigned Count = MBB->size(), CurrentCount = Count; for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { MachineInstr *MI = llvm::prior(I); - if (TII->isSchedulingBoundary(MI, MBB, Fn)) { - Scheduler.Run(MBB, I, Current, CurrentCount); + // Calls are not scheduling boundaries before register allocation, but + // post-ra we don't gain anything by scheduling across calls since we + // don't need to worry about register pressure. + if (MI->isCall() || TII->isSchedulingBoundary(MI, MBB, Fn)) { + Scheduler.enterRegion(MBB, I, Current, CurrentCount); + Scheduler.schedule(); + Scheduler.exitRegion(); Scheduler.EmitSchedule(); Current = MI; CurrentCount = Count - 1; @@ -271,15 +328,19 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { } I = MI; --Count; + if (MI->isBundle()) + Count -= MI->getBundleSize(); } assert(Count == 0 && "Instruction count mismatch!"); assert((MBB->begin() == Current || CurrentCount != 0) && "Instruction count mismatch!"); - Scheduler.Run(MBB, MBB->begin(), Current, CurrentCount); + Scheduler.enterRegion(MBB, MBB->begin(), Current, CurrentCount); + Scheduler.schedule(); + Scheduler.exitRegion(); Scheduler.EmitSchedule(); // Clean up register live-range state. - Scheduler.FinishBlock(); + Scheduler.finishBlock(); // Update register kills Scheduler.FixupKills(MBB); @@ -291,9 +352,9 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { /// StartBlock - Initialize register live-range state for scheduling in /// this block. /// -void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) { +void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { // Call the superclass. - ScheduleDAGInstrs::StartBlock(BB); + ScheduleDAGInstrs::startBlock(BB); // Reset the hazard recognizer and anti-dep breaker. HazardRec->Reset(); @@ -303,14 +364,14 @@ void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) { /// Schedule - Schedule the instruction range using list scheduling. /// -void SchedulePostRATDList::Schedule() { +void SchedulePostRATDList::schedule() { // Build the scheduling graph. - BuildSchedGraph(AA); + buildSchedGraph(AA); if (AntiDepBreak != NULL) { unsigned Broken = - AntiDepBreak->BreakAntiDependencies(SUnits, Begin, InsertPos, - InsertPosIndex, DbgValues); + AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd, + EndIndex, DbgValues); if (Broken != 0) { // We made changes. Update the dependency graph. @@ -319,11 +380,8 @@ void SchedulePostRATDList::Schedule() { // the def's anti-dependence *and* output-dependence edges due to // that register, and add new anti-dependence and output-dependence // edges based on the next live range of the register. - SUnits.clear(); - Sequence.clear(); - EntrySU = SUnit(); - ExitSU = SUnit(); - BuildSchedGraph(AA); + ScheduleDAG::clearDAG(); + buildSchedGraph(AA); NumFixedAnti += Broken; } @@ -343,38 +401,35 @@ void SchedulePostRATDList::Schedule() { /// void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { if (AntiDepBreak != NULL) - AntiDepBreak->Observe(MI, Count, InsertPosIndex); + AntiDepBreak->Observe(MI, Count, EndIndex); } /// FinishBlock - Clean up register live-range state. /// -void SchedulePostRATDList::FinishBlock() { +void SchedulePostRATDList::finishBlock() { if (AntiDepBreak != NULL) AntiDepBreak->FinishBlock(); // Call the superclass. - ScheduleDAGInstrs::FinishBlock(); + ScheduleDAGInstrs::finishBlock(); } /// StartBlockForKills - Initialize register live-range state for updating kills /// void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { - // Initialize the indices to indicate that no registers are live. - for (unsigned i = 0; i < TRI->getNumRegs(); ++i) - KillIndices[i] = ~0u; + // Start with no live registers. + LiveRegs.reset(); // Determine the live-out physregs for this block. - if (!BB->empty() && BB->back().getDesc().isReturn()) { + if (!BB->empty() && BB->back().isReturn()) { // In a return block, examine the function live-out regs. for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), E = MRI.liveout_end(); I != E; ++I) { unsigned Reg = *I; - KillIndices[Reg] = BB->size(); + LiveRegs.set(Reg); // Repeat, for all subregs. - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - KillIndices[*Subreg] = BB->size(); - } + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + LiveRegs.set(*SubRegs); } } else { @@ -384,12 +439,10 @@ void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), E = (*SI)->livein_end(); I != E; ++I) { unsigned Reg = *I; - KillIndices[Reg] = BB->size(); + LiveRegs.set(Reg); // Repeat, for all subregs. - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - KillIndices[*Subreg] = BB->size(); - } + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + LiveRegs.set(*SubRegs); } } } @@ -404,7 +457,7 @@ bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, } // If MO itself is live, clear the kill flag... - if (KillIndices[MO.getReg()] != ~0u) { + if (LiveRegs.test(MO.getReg())) { MO.setIsKill(false); return false; } @@ -414,10 +467,9 @@ bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, MO.setIsKill(false); bool AllDead = true; const unsigned SuperReg = MO.getReg(); - for (const unsigned *Subreg = TRI->getSubRegisters(SuperReg); - *Subreg; ++Subreg) { - if (KillIndices[*Subreg] != ~0u) { - MI->addOperand(MachineOperand::CreateReg(*Subreg, + for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { + if (LiveRegs.test(*SubRegs)) { + MI->addOperand(MachineOperand::CreateReg(*SubRegs, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/, @@ -437,8 +489,7 @@ bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); - std::set killedRegs; - BitVector ReservedRegs = TRI->getReservedRegs(MF); + BitVector killedRegs(TRI->getNumRegs()); StartBlockForKills(MBB); @@ -455,6 +506,8 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { // are completely defined. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); + if (MO.isRegMask()) + LiveRegs.clearBitsNotInMask(MO.getRegMask()); if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); if (Reg == 0) continue; @@ -462,32 +515,29 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { // Ignore two-addr defs. if (MI->isRegTiedToUseOperand(i)) continue; - KillIndices[Reg] = ~0u; + LiveRegs.reset(Reg); // Repeat for all subregs. - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - KillIndices[*Subreg] = ~0u; - } + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + LiveRegs.reset(*SubRegs); } // Examine all used registers and set/clear kill flag. When a // register is used multiple times we only set the kill flag on // the first use. - killedRegs.clear(); + killedRegs.reset(); for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (!MO.isReg() || !MO.isUse()) continue; unsigned Reg = MO.getReg(); - if ((Reg == 0) || ReservedRegs.test(Reg)) continue; + if ((Reg == 0) || MRI.isReserved(Reg)) continue; bool kill = false; - if (killedRegs.find(Reg) == killedRegs.end()) { + if (!killedRegs.test(Reg)) { kill = true; // A register is not killed if any subregs are live... - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - if (KillIndices[*Subreg] != ~0u) { + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + if (LiveRegs.test(*SubRegs)) { kill = false; break; } @@ -496,7 +546,7 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { // If subreg is not live, then register is killed if it became // live in this instruction if (kill) - kill = (KillIndices[Reg] == ~0u); + kill = !LiveRegs.test(Reg); } if (MO.isKill() != kill) { @@ -506,7 +556,7 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { DEBUG(MI->dump()); } - killedRegs.insert(Reg); + killedRegs.set(Reg); } // Mark any used register (that is not using undef) and subregs as @@ -515,14 +565,12 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { MachineOperand &MO = MI->getOperand(i); if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; unsigned Reg = MO.getReg(); - if ((Reg == 0) || ReservedRegs.test(Reg)) continue; + if ((Reg == 0) || MRI.isReserved(Reg)) continue; - KillIndices[Reg] = Count; + LiveRegs.set(Reg); - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - KillIndices[*Subreg] = Count; - } + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + LiveRegs.set(*SubRegs); } } } @@ -585,7 +633,7 @@ void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { ReleaseSuccessors(SU); SU->isScheduled = true; - AvailableQueue.ScheduledNode(SU); + AvailableQueue.scheduledNode(SU); } /// ListScheduleTopDown - The main loop of list scheduling for top-down @@ -699,14 +747,46 @@ void SchedulePostRATDList::ListScheduleTopDown() { } #ifndef NDEBUG - VerifySchedule(/*isBottomUp=*/false); -#endif + unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false); + unsigned Noops = 0; + for (unsigned i = 0, e = Sequence.size(); i != e; ++i) + if (!Sequence[i]) + ++Noops; + assert(Sequence.size() - Noops == ScheduledNodes && + "The number of nodes scheduled doesn't match the expected number!"); +#endif // NDEBUG } -//===----------------------------------------------------------------------===// -// Public Constructor Functions -//===----------------------------------------------------------------------===// +// EmitSchedule - Emit the machine code in scheduled order. +void SchedulePostRATDList::EmitSchedule() { + RegionBegin = RegionEnd; + + // If first instruction was a DBG_VALUE then put it back. + if (FirstDbgValue) + BB->splice(RegionEnd, BB, FirstDbgValue); + + // Then re-insert them according to the given schedule. + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + if (SUnit *SU = Sequence[i]) + BB->splice(RegionEnd, BB, SU->getInstr()); + else + // Null SUnit* is a noop. + TII->insertNoop(*BB, RegionEnd); + + // Update the Begin iterator, as the first instruction in the block + // may have been scheduled later. + if (i == 0) + RegionBegin = prior(RegionEnd); + } -FunctionPass *llvm::createPostRAScheduler(CodeGenOpt::Level OptLevel) { - return new PostRAScheduler(OptLevel); + // Reinsert any remaining debug_values. + for (std::vector >::iterator + DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { + std::pair P = *prior(DI); + MachineInstr *DbgValue = P.first; + MachineBasicBlock::iterator OrigPrivMI = P.second; + BB->splice(++OrigPrivMI, BB, DbgValue); + } + DbgValues.clear(); + FirstDbgValue = NULL; }