X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPostRASchedulerList.cpp;h=c73e87733cb4212421bb9e7a90084c51212baebc;hb=340d596509129de8c3fa9dbe4184a2b148b78757;hp=6995e9db1c1351c8d4588e08839af4e4dbd5ca28;hpb=15d75d9f11f877bf3716257013b563e67341b0ed;p=oota-llvm.git diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index 6995e9db1c1..c73e87733cb 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -22,8 +22,7 @@ #include "AntiDepBreaker.h" #include "AggressiveAntiDepBreaker.h" #include "CriticalAntiDepBreaker.h" -#include "ExactHazardRecognizer.h" -#include "SimpleHazardRecognizer.h" +#include "RegisterClassInfo.h" #include "ScheduleDAGInstrs.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/LatencyPriorityQueue.h" @@ -39,14 +38,13 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetSubtarget.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/Statistic.h" -#include #include using namespace llvm; @@ -55,7 +53,7 @@ STATISTIC(NumStalls, "Number of pipeline stalls"); STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies"); // Post-RA scheduling is enabled with -// TargetSubtarget.enablePostRAScheduler(). This flag can be used to +// TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to // override the target. static cl::opt EnablePostRAScheduler("post-RA-scheduler", @@ -66,10 +64,6 @@ EnableAntiDepBreaking("break-anti-dependencies", cl::desc("Break post-RA scheduling anti-dependencies: " "\"critical\", \"all\", or \"none\""), cl::init("none"), cl::Hidden); -static cl::opt -EnablePostRAHazardAvoidance("avoid-hazards", - cl::desc("Enable exact hazard avoidance"), - cl::init(true), cl::Hidden); // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod static cl::opt @@ -86,12 +80,14 @@ 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) {} + MachineFunctionPass(ID), OptLevel(ol) {} void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); @@ -115,7 +111,7 @@ namespace { /// AvailableQueue - The priority queue to use for the available SUnits. /// LatencyPriorityQueue AvailableQueue; - + /// PendingQueue - This contains all of the instructions whose operands have /// been issued, but their results are not ready yet (due to the latency of /// the operation). Once the operands becomes available, the instruction is @@ -136,20 +132,16 @@ namespace { /// KillIndices - The index of the most recent kill (proceding bottom-up), /// or ~0u if the register is not live. - unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; + std::vector KillIndices; public: - SchedulePostRATDList(MachineFunction &MF, - const MachineLoopInfo &MLI, - const MachineDominatorTree &MDT, - ScheduleHazardRecognizer *HR, - AntiDepBreaker *ADB, - AliasAnalysis *aa) - : ScheduleDAGInstrs(MF, MLI, MDT), Topo(SUnits), - HazardRec(HR), AntiDepBreak(ADB), AA(aa) {} - - ~SchedulePostRATDList() { - } + SchedulePostRATDList( + MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, + AliasAnalysis *AA, const RegisterClassInfo&, + TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, + SmallVectorImpl &CriticalPathRCs); + + ~SchedulePostRATDList(); /// StartBlock - Initialize register live-range state for scheduling in /// this block. @@ -159,7 +151,7 @@ namespace { /// Schedule - Schedule the instruction range using list scheduling. /// void Schedule(); - + /// Observe - Update liveness information to account for the current /// instruction, which will not be scheduled. /// @@ -180,7 +172,7 @@ namespace { void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); void ListScheduleTopDown(); void StartBlockForKills(MachineBasicBlock *BB); - + // ToggleKillFlag - Toggle a register operand kill flag. Other // adjustments may be made to the instruction if necessary. Return // true if the operand has been deleted, false if not. @@ -188,66 +180,64 @@ namespace { }; } -/// isSchedulingBoundary - Test if the given instruction should be -/// considered a scheduling boundary. This primarily includes labels -/// and terminators. -/// -static bool isSchedulingBoundary(const MachineInstr *MI, - const MachineFunction &MF) { - // Terminators and labels can't be scheduled around. - if (MI->getDesc().isTerminator() || MI->isLabel()) - return true; - - // Don't attempt to schedule around any instruction that modifies - // a stack-oriented pointer, as it's unlikely to be profitable. This - // saves compile time, because it doesn't require every single - // stack slot reference to depend on the instruction that does the - // modification. - const TargetLowering &TLI = *MF.getTarget().getTargetLowering(); - if (MI->modifiesRegister(TLI.getStackPointerRegisterToSaveRestore())) - return true; +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()) +{ + const TargetMachine &TM = MF.getTarget(); + const InstrItineraryData *InstrItins = TM.getInstrItineraryData(); + HazardRec = + TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this); + AntiDepBreak = + ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? + (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : + ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ? + (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : NULL)); +} - return false; +SchedulePostRATDList::~SchedulePostRATDList() { + delete HazardRec; + delete AntiDepBreak; } bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { - AA = &getAnalysis(); + TII = Fn.getTarget().getInstrInfo(); + MachineLoopInfo &MLI = getAnalysis(); + MachineDominatorTree &MDT = getAnalysis(); + AliasAnalysis *AA = &getAnalysis(); + RegClassInfo.runOnMachineFunction(Fn); // Check for explicit enable/disable of post-ra scheduling. - TargetSubtarget::AntiDepBreakMode AntiDepMode = TargetSubtarget::ANTIDEP_NONE; + TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = TargetSubtargetInfo::ANTIDEP_NONE; SmallVector CriticalPathRCs; if (EnablePostRAScheduler.getPosition() > 0) { if (!EnablePostRAScheduler) return false; } else { // Check that post-RA scheduling is enabled for this target. - const TargetSubtarget &ST = Fn.getTarget().getSubtarget(); + // This may upgrade the AntiDepMode. + const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget(); if (!ST.enablePostRAScheduler(OptLevel, AntiDepMode, CriticalPathRCs)) return false; } // Check for antidep breaking override... if (EnableAntiDepBreaking.getPosition() > 0) { - AntiDepMode = (EnableAntiDepBreaking == "all") ? TargetSubtarget::ANTIDEP_ALL : - (EnableAntiDepBreaking == "critical") ? TargetSubtarget::ANTIDEP_CRITICAL : - TargetSubtarget::ANTIDEP_NONE; + AntiDepMode = (EnableAntiDepBreaking == "all") + ? TargetSubtargetInfo::ANTIDEP_ALL + : ((EnableAntiDepBreaking == "critical") + ? TargetSubtargetInfo::ANTIDEP_CRITICAL + : TargetSubtargetInfo::ANTIDEP_NONE); } - DEBUG(errs() << "PostRAScheduler\n"); + DEBUG(dbgs() << "PostRAScheduler\n"); - const MachineLoopInfo &MLI = getAnalysis(); - const MachineDominatorTree &MDT = getAnalysis(); - const InstrItineraryData &InstrItins = Fn.getTarget().getInstrItineraryData(); - ScheduleHazardRecognizer *HR = EnablePostRAHazardAvoidance ? - (ScheduleHazardRecognizer *)new ExactHazardRecognizer(InstrItins) : - (ScheduleHazardRecognizer *)new SimpleHazardRecognizer(); - AntiDepBreaker *ADB = - ((AntiDepMode == TargetSubtarget::ANTIDEP_ALL) ? - (AntiDepBreaker *)new AggressiveAntiDepBreaker(Fn, CriticalPathRCs) : - ((AntiDepMode == TargetSubtarget::ANTIDEP_CRITICAL) ? - (AntiDepBreaker *)new CriticalAntiDepBreaker(Fn) : NULL)); - - SchedulePostRATDList Scheduler(Fn, MLI, MDT, HR, ADB, AA); + SchedulePostRATDList Scheduler(Fn, MLI, MDT, AA, RegClassInfo, AntiDepMode, + CriticalPathRCs); // Loop over all of the basic blocks for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); @@ -258,7 +248,7 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { static int bbcnt = 0; if (bbcnt++ % DebugDiv != DebugMod) continue; - errs() << "*** DEBUG scheduling " << Fn.getFunction()->getNameStr() << + dbgs() << "*** DEBUG scheduling " << Fn.getFunction()->getNameStr() << ":BB#" << MBB->getNumber() << " ***\n"; } #endif @@ -271,10 +261,10 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { MachineBasicBlock::iterator Current = MBB->end(); unsigned Count = MBB->size(), CurrentCount = Count; for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { - MachineInstr *MI = prior(I); - if (isSchedulingBoundary(MI, Fn)) { + MachineInstr *MI = llvm::prior(I); + if (TII->isSchedulingBoundary(MI, MBB, Fn)) { Scheduler.Run(MBB, I, Current, CurrentCount); - Scheduler.EmitSchedule(0); + Scheduler.EmitSchedule(); Current = MI; CurrentCount = Count - 1; Scheduler.Observe(MI, CurrentCount); @@ -286,7 +276,7 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { assert((MBB->begin() == Current || CurrentCount != 0) && "Instruction count mismatch!"); Scheduler.Run(MBB, MBB->begin(), Current, CurrentCount); - Scheduler.EmitSchedule(0); + Scheduler.EmitSchedule(); // Clean up register live-range state. Scheduler.FinishBlock(); @@ -295,12 +285,9 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { Scheduler.FixupKills(MBB); } - delete HR; - delete ADB; - return true; } - + /// StartBlock - Initialize register live-range state for scheduling in /// this block. /// @@ -321,10 +308,10 @@ void SchedulePostRATDList::Schedule() { BuildSchedGraph(AA); if (AntiDepBreak != NULL) { - unsigned Broken = + unsigned Broken = AntiDepBreak->BreakAntiDependencies(SUnits, Begin, InsertPos, - InsertPosIndex); - + InsertPosIndex, DbgValues); + if (Broken != 0) { // We made changes. Update the dependency graph. // Theoretically we could update the graph in place: @@ -337,12 +324,12 @@ void SchedulePostRATDList::Schedule() { EntrySU = SUnit(); ExitSU = SUnit(); BuildSchedGraph(AA); - + NumFixedAnti += Broken; } } - DEBUG(errs() << "********** List Scheduling **********\n"); + DEBUG(dbgs() << "********** List Scheduling **********\n"); DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) SUnits[su].dumpAll(this)); @@ -373,7 +360,8 @@ void SchedulePostRATDList::FinishBlock() { /// void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { // Initialize the indices to indicate that no registers are live. - std::fill(KillIndices, array_endof(KillIndices), ~0u); + for (unsigned i = 0; i < TRI->getNumRegs(); ++i) + KillIndices[i] = ~0u; // Determine the live-out physregs for this block. if (!BB->empty() && BB->back().getDesc().isReturn()) { @@ -414,7 +402,7 @@ bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, MO.setIsKill(true); return false; } - + // If MO itself is live, clear the kill flag... if (KillIndices[MO.getReg()] != ~0u) { MO.setIsKill(false); @@ -447,18 +435,20 @@ bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, /// incorrect by instruction reordering. /// void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { - DEBUG(errs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); + DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); std::set killedRegs; BitVector ReservedRegs = TRI->getReservedRegs(MF); StartBlockForKills(MBB); - + // Examine block from end to start... unsigned Count = MBB->size(); for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); I != E; --Count) { MachineInstr *MI = --I; + if (MI->isDebugValue()) + continue; // Update liveness. Registers that are defed but not used in this // instruction are now dead. Mark register and all subregs as they @@ -471,9 +461,9 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { if (!MO.isDef()) continue; // Ignore two-addr defs. if (MI->isRegTiedToUseOperand(i)) continue; - + KillIndices[Reg] = ~0u; - + // Repeat for all subregs. for (const unsigned *Subreg = TRI->getSubRegisters(Reg); *Subreg; ++Subreg) { @@ -508,17 +498,17 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { if (kill) kill = (KillIndices[Reg] == ~0u); } - + if (MO.isKill() != kill) { - DEBUG(errs() << "Fixing " << MO << " in "); + DEBUG(dbgs() << "Fixing " << MO << " in "); // Warning: ToggleKillFlag may invalidate MO. ToggleKillFlag(MI, MO); DEBUG(MI->dump()); } - + killedRegs.insert(Reg); } - + // Mark any used register (that is not using undef) and subregs as // now live... for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { @@ -528,7 +518,7 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { if ((Reg == 0) || ReservedRegs.test(Reg)) continue; KillIndices[Reg] = Count; - + for (const unsigned *Subreg = TRI->getSubRegisters(Reg); *Subreg; ++Subreg) { KillIndices[*Subreg] = Count; @@ -548,19 +538,25 @@ void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { #ifndef NDEBUG if (SuccSU->NumPredsLeft == 0) { - errs() << "*** Scheduling failed! ***\n"; + dbgs() << "*** Scheduling failed! ***\n"; SuccSU->dump(this); - errs() << " has been released too many times!\n"; + dbgs() << " has been released too many times!\n"; llvm_unreachable(0); } #endif --SuccSU->NumPredsLeft; - // Compute how many cycles it will be before this actually becomes - // available. This is the max of the start time of all predecessors plus - // their latencies. - SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); - + // Standard scheduler algorithms will recompute the depth of the successor + // here as such: + // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); + // + // However, we lazily compute node depth instead. Note that + // ScheduleNodeTopDown has already updated the depth of this node which causes + // all descendents to be marked dirty. Setting the successor depth explicitly + // here would cause depth to be recomputed for all its ancestors. If the + // successor is not yet ready (because of a transitively redundant edge) then + // this causes depth computation to be quadratic in the size of the DAG. + // If all the node's predecessors are scheduled, this node is ready // to be scheduled. Ignore the special ExitSU node. if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) @@ -579,11 +575,11 @@ void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { /// count of its successors. If a successor pending count is zero, add it to /// the Available queue. void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { - DEBUG(errs() << "*** Scheduling [" << CurCycle << "]: "); + DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); DEBUG(SU->dump(this)); - + Sequence.push_back(SU); - assert(CurCycle >= SU->getDepth() && + assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); SU->setDepthToAtLeast(CurCycle); @@ -596,7 +592,7 @@ void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { /// schedulers. void SchedulePostRATDList::ListScheduleTopDown() { unsigned CurCycle = 0; - + // We're scheduling top-down but we're visiting the regions in // bottom-up order, so we don't know the hazards at the start of a // region. So assume no hazards (this should usually be ok as most @@ -639,13 +635,7 @@ void SchedulePostRATDList::ListScheduleTopDown() { MinDepth = PendingQueue[i]->getDepth(); } - DEBUG(errs() << "\n*** Examining Available\n"; - LatencyPriorityQueue q = AvailableQueue; - while (!q.empty()) { - SUnit *su = q.pop(); - errs() << "Height " << su->getHeight() << ": "; - su->dump(this); - }); + DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this)); SUnit *FoundSUnit = 0; bool HasNoopHazards = false; @@ -653,7 +643,7 @@ void SchedulePostRATDList::ListScheduleTopDown() { SUnit *CurSUnit = AvailableQueue.pop(); ScheduleHazardRecognizer::HazardType HT = - HazardRec->getHazardType(CurSUnit); + HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); if (HT == ScheduleHazardRecognizer::NoHazard) { FoundSUnit = CurSUnit; break; @@ -677,30 +667,27 @@ void SchedulePostRATDList::ListScheduleTopDown() { ScheduleNodeTopDown(FoundSUnit, CurCycle); HazardRec->EmitInstruction(FoundSUnit); CycleHasInsts = true; - - // If we are using the target-specific hazards, then don't - // advance the cycle time just because we schedule a node. If - // the target allows it we can schedule multiple nodes in the - // same cycle. - if (!EnablePostRAHazardAvoidance) { - if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! - ++CurCycle; + if (HazardRec->atIssueLimit()) { + DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n'); + HazardRec->AdvanceCycle(); + ++CurCycle; + CycleHasInsts = false; } } else { if (CycleHasInsts) { - DEBUG(errs() << "*** Finished cycle " << CurCycle << '\n'); + DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n'); HazardRec->AdvanceCycle(); } else if (!HasNoopHazards) { // Otherwise, we have a pipeline stall, but no other problem, // just advance the current cycle and try again. - DEBUG(errs() << "*** Stall in cycle " << CurCycle << '\n'); + DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n'); HazardRec->AdvanceCycle(); ++NumStalls; } else { // Otherwise, we have no instructions to issue and we have instructions // that will fault if we don't do this right. This is the case for // processors without pipeline interlocks and other cases. - DEBUG(errs() << "*** Emitting noop in cycle " << CurCycle << '\n'); + DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n'); HazardRec->EmitNoop(); Sequence.push_back(0); // NULL here means noop ++NumNoops;