X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPostRASchedulerList.cpp;h=c73e87733cb4212421bb9e7a90084c51212baebc;hb=5c75af6eb72bd74bc35f46e5037dd5646e04f3b6;hp=d5edb36b44b64d6d8c9f05b85b159d66cd2c280c;hpb=4de099d8ca651e00fa5fac22bace4f4dba2d0292;p=oota-llvm.git diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index d5edb36b44b..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. /// @@ -175,13 +167,12 @@ namespace { void FixupKills(MachineBasicBlock *MBB); private: - void ReleaseSucc(SUnit *SU, SDep *SuccEdge, bool IgnoreAntiDep); - void ReleaseSuccessors(SUnit *SU, bool IgnoreAntiDep); - void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle, bool IgnoreAntiDep); - void ListScheduleTopDown( - AntiDepBreaker::CandidateMap *AntiDepCandidates); + void ReleaseSucc(SUnit *SU, SDep *SuccEdge); + void ReleaseSuccessors(SUnit *SU); + 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. @@ -189,65 +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(); - if (!ST.enablePostRAScheduler(OptLevel, AntiDepMode)) + // 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"); - - 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) : - ((AntiDepMode == TargetSubtarget::ANTIDEP_CRITICAL) ? - (AntiDepBreaker *)new CriticalAntiDepBreaker(Fn) : NULL)); + DEBUG(dbgs() << "PostRAScheduler\n"); - 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,59 +308,33 @@ void SchedulePostRATDList::Schedule() { BuildSchedGraph(AA); if (AntiDepBreak != NULL) { - AntiDepBreaker::CandidateMap AntiDepCandidates; - const bool NeedCandidates = AntiDepBreak->NeedCandidates(); - - for (unsigned i = 0, Trials = AntiDepBreak->GetMaxTrials(); - i < Trials; ++i) { - DEBUG(errs() << "\n********** Break Anti-Deps, Trial " << - i << " **********\n"); - - // If candidates are required, then schedule forward ignoring - // anti-dependencies to collect the candidate operands for - // anti-dependence breaking. The candidates will be the def - // operands for the anti-dependencies that if broken would allow - // an improved schedule - if (NeedCandidates) { - DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) - SUnits[su].dumpAll(this)); - - AntiDepCandidates.clear(); - AvailableQueue.initNodes(SUnits); - ListScheduleTopDown(&AntiDepCandidates); - AvailableQueue.releaseState(); - } - - unsigned Broken = - AntiDepBreak->BreakAntiDependencies(SUnits, AntiDepCandidates, - Begin, InsertPos, InsertPosIndex); + unsigned Broken = + AntiDepBreak->BreakAntiDependencies(SUnits, Begin, InsertPos, + InsertPosIndex, DbgValues); + if (Broken != 0) { // We made changes. Update the dependency graph. // Theoretically we could update the graph in place: // When a live range is changed to use a different register, remove // 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. - if ((Broken != 0) || NeedCandidates) { - SUnits.clear(); - Sequence.clear(); - EntrySU = SUnit(); - ExitSU = SUnit(); - BuildSchedGraph(AA); - } + SUnits.clear(); + Sequence.clear(); + EntrySU = SUnit(); + ExitSU = SUnit(); + BuildSchedGraph(AA); NumFixedAnti += Broken; - if (Broken == 0) - break; } } - 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)); AvailableQueue.initNodes(SUnits); - ListScheduleTopDown(NULL); + ListScheduleTopDown(); AvailableQueue.releaseState(); } @@ -399,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()) { @@ -440,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); @@ -473,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 @@ -497,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) { @@ -534,20 +498,17 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { if (kill) kill = (KillIndices[Reg] == ~0u); } - + if (MO.isKill() != kill) { - bool removed = ToggleKillFlag(MI, MO); - if (removed) { - DEBUG(errs() << "Fixed in "); - } else { - DEBUG(errs() << "Fixed " << 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) { @@ -557,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; @@ -572,26 +533,30 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to /// the PendingQueue if the count reaches zero. Also update its cycle bound. -void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge, - bool IgnoreAntiDep) { +void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { SUnit *SuccSU = SuccEdge->getSUnit(); #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(IgnoreAntiDep) + - SuccEdge->getLatency(), IgnoreAntiDep); - + // 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) @@ -599,72 +564,48 @@ void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge, } /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. -void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU, bool IgnoreAntiDep) { +void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) { - if (IgnoreAntiDep && (I->getKind() == SDep::Anti)) continue; - ReleaseSucc(SU, &*I, IgnoreAntiDep); + ReleaseSucc(SU, &*I); } } /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending /// count of its successors. If a successor pending count is zero, add it to /// the Available queue. -void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle, - bool IgnoreAntiDep) { - DEBUG(errs() << "*** Scheduling [" << CurCycle << "]: "); +void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { + DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); DEBUG(SU->dump(this)); - + Sequence.push_back(SU); - assert(CurCycle >= SU->getDepth(IgnoreAntiDep) && + assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); - SU->setDepthToAtLeast(CurCycle, IgnoreAntiDep); + SU->setDepthToAtLeast(CurCycle); - ReleaseSuccessors(SU, IgnoreAntiDep); + ReleaseSuccessors(SU); SU->isScheduled = true; AvailableQueue.ScheduledNode(SU); } /// ListScheduleTopDown - The main loop of list scheduling for top-down /// schedulers. -void SchedulePostRATDList::ListScheduleTopDown( - AntiDepBreaker::CandidateMap *AntiDepCandidates) { +void SchedulePostRATDList::ListScheduleTopDown() { unsigned CurCycle = 0; - const bool IgnoreAntiDep = (AntiDepCandidates != NULL); - + // 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 // blocks are a single region). HazardRec->Reset(); - // If ignoring anti-dependencies, the Schedule DAG still has Anti - // dep edges, but we ignore them for scheduling purposes - AvailableQueue.setIgnoreAntiDep(IgnoreAntiDep); - // Release any successors of the special Entry node. - ReleaseSuccessors(&EntrySU, IgnoreAntiDep); + ReleaseSuccessors(&EntrySU); - // Add all leaves to Available queue. If ignoring antideps we also - // adjust the predecessor count for each node to not include antidep - // edges. + // Add all leaves to Available queue. for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { // It is available if it has no predecessors. bool available = SUnits[i].Preds.empty(); - // If we are ignoring anti-dependencies then a node that has only - // anti-dep predecessors is available. - if (!available && IgnoreAntiDep) { - available = true; - for (SUnit::const_pred_iterator I = SUnits[i].Preds.begin(), - E = SUnits[i].Preds.end(); I != E; ++I) { - if (I->getKind() != SDep::Anti) { - available = false; - } else { - SUnits[i].NumPredsLeft -= 1; - } - } - } - if (available) { AvailableQueue.push(&SUnits[i]); SUnits[i].isAvailable = true; @@ -684,23 +625,17 @@ void SchedulePostRATDList::ListScheduleTopDown( // so, add them to the available queue. unsigned MinDepth = ~0u; for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { - if (PendingQueue[i]->getDepth(IgnoreAntiDep) <= CurCycle) { + if (PendingQueue[i]->getDepth() <= CurCycle) { AvailableQueue.push(PendingQueue[i]); PendingQueue[i]->isAvailable = true; PendingQueue[i] = PendingQueue.back(); PendingQueue.pop_back(); --i; --e; - } else if (PendingQueue[i]->getDepth(IgnoreAntiDep) < MinDepth) - MinDepth = PendingQueue[i]->getDepth(IgnoreAntiDep); + } else if (PendingQueue[i]->getDepth() < MinDepth) + MinDepth = PendingQueue[i]->getDepth(); } - DEBUG(errs() << "\n*** Examining Available\n"; - LatencyPriorityQueue q = AvailableQueue; - while (!q.empty()) { - SUnit *su = q.pop(); - errs() << "Height " << su->getHeight(IgnoreAntiDep) << ": "; - su->dump(this); - }); + DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this)); SUnit *FoundSUnit = 0; bool HasNoopHazards = false; @@ -708,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; @@ -728,54 +663,31 @@ void SchedulePostRATDList::ListScheduleTopDown( // If we found a node to schedule... if (FoundSUnit) { - // If we are ignoring anti-dependencies and the SUnit we are - // scheduling has an antidep predecessor that has not been - // scheduled, then we will need to break that antidep if we want - // to get this schedule when not ignoring anti-dependencies. - if (IgnoreAntiDep) { - AntiDepBreaker::AntiDepRegVector AntiDepRegs; - for (SUnit::const_pred_iterator I = FoundSUnit->Preds.begin(), - E = FoundSUnit->Preds.end(); I != E; ++I) { - if ((I->getKind() == SDep::Anti) && !I->getSUnit()->isScheduled) - AntiDepRegs.push_back(I->getReg()); - } - - if (AntiDepRegs.size() > 0) { - DEBUG(errs() << "*** AntiDep Candidate: "); - DEBUG(FoundSUnit->dump(this)); - AntiDepCandidates->insert( - AntiDepBreaker::CandidateMap::value_type(FoundSUnit, AntiDepRegs)); - } - } - // ... schedule the node... - ScheduleNodeTopDown(FoundSUnit, CurCycle, IgnoreAntiDep); + 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;