From 9e64bbb322417c09f27afdf08e3946287c9df5aa Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Tue, 10 Feb 2009 23:27:53 +0000 Subject: [PATCH] Factor out more code for computing register live-range informationfor scheduling, and generalize is so that preserves state across scheduling regions. This fixes incorrect live-range information around terminators and labels, which are effective region boundaries. In place of looking for terminators to anchor inter-block dependencies, introduce special entry and exit scheduling units for this purpose. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64254 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/ScheduleDAG.h | 15 + lib/CodeGen/PostRASchedulerList.cpp | 483 +++++++++++------- lib/CodeGen/ScheduleDAG.cpp | 5 +- lib/CodeGen/ScheduleDAGInstrs.cpp | 160 ++---- lib/CodeGen/ScheduleDAGInstrs.h | 91 +++- lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp | 35 +- lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp | 28 +- .../SelectionDAG/ScheduleDAGRRList.cpp | 64 ++- 8 files changed, 524 insertions(+), 357 deletions(-) diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index c62c3af232f..786a5f40738 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -282,6 +282,16 @@ namespace llvm { isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), CopyDstRC(NULL), CopySrcRC(NULL) {} + /// SUnit - Construct a placeholder SUnit. + SUnit() + : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), NodeQueueId(0), + Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), + isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), + isPending(false), isAvailable(false), isScheduled(false), + isScheduleHigh(false), isCloned(false), + isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), + CopyDstRC(NULL), CopySrcRC(NULL) {} + /// setNode - Assign the representative SDNode for this SUnit. /// This may be used during pre-regalloc scheduling. void setNode(SDNode *N) { @@ -430,6 +440,8 @@ namespace llvm { std::vector Sequence; // The schedule. Null SUnit*'s // represent noop instructions. std::vector SUnits; // The scheduling units. + SUnit EntrySU; // Special node for the region entry. + SUnit ExitSU; // Special node for the region exit. explicit ScheduleDAG(MachineFunction &mf); @@ -446,6 +458,9 @@ namespace llvm { MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End); + /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock + /// according to the order specified in Sequence. + /// virtual MachineBasicBlock *EmitSchedule() = 0; void dumpSchedule() const; diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index 94b6be19fba..617b4ac1ec2 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -94,6 +94,25 @@ namespace { /// HazardRec - The hazard recognizer to use. ScheduleHazardRecognizer *HazardRec; + /// Classes - For live regs that are only used in one register class in a + /// live range, the register class. If the register is not live, the + /// corresponding value is null. If the register is live but used in + /// multiple register classes, the corresponding value is -1 casted to a + /// pointer. + const TargetRegisterClass * + Classes[TargetRegisterInfo::FirstVirtualRegister]; + + /// RegRegs - Map registers to all their references within a live range. + std::multimap RegRefs; + + /// The index of the most recent kill (proceding bottom-up), or ~0u if + /// the register is not live. + unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; + + /// The index of the most recent complete def (proceding bottom up), or ~0u + /// if the register is live. + unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; + public: SchedulePostRATDList(MachineFunction &MF, const MachineLoopInfo &MLI, @@ -107,10 +126,29 @@ namespace { delete HazardRec; } + /// StartBlock - Initialize register live-range state for scheduling in + /// this block. + /// + void StartBlock(MachineBasicBlock *BB); + + /// 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. + /// + void Observe(MachineInstr *MI); + + /// FinishBlock - Clean up register live-range state. + /// + void FinishBlock(); + private: + void PrescanInstruction(MachineInstr *MI); + void ScanInstruction(MachineInstr *MI, unsigned Count); void ReleaseSucc(SUnit *SU, SDep *SuccEdge); + void ReleaseSuccessors(SUnit *SU); void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); void ListScheduleTopDown(); bool BreakAntiDependencies(); @@ -173,6 +211,19 @@ 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; + + return false; +} + bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { DOUT << "PostRAScheduler\n"; @@ -187,26 +238,111 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { // Loop over all of the basic blocks for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe; ++MBB) { + // Initialize register live-range state for scheduling in this block. + Scheduler.StartBlock(MBB); + // Schedule each sequence of instructions not interrupted by a label // or anything else that effectively needs to shut down scheduling. - MachineBasicBlock::iterator Current = MBB->end(), Top = MBB->begin(); - for (MachineBasicBlock::iterator I = Current; I != Top; ) { - MachineInstr *MI = --I; - if (MI->getDesc().isTerminator() || MI->isLabel()) { - Scheduler.Run(0, MBB, next(I), Current); - Scheduler.EmitSchedule(); - Current = I; + MachineBasicBlock::iterator Current = MBB->end(); + for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { + MachineInstr *MI = prior(I); + if (isSchedulingBoundary(MI, Fn)) { + if (I != Current) { + Scheduler.Run(0, MBB, I, Current); + Scheduler.EmitSchedule(); + } + Scheduler.Observe(MI); + Current = MI; } + I = MI; } - - Scheduler.Run(0, MBB, Top, Current); + Scheduler.Run(0, MBB, MBB->begin(), Current); Scheduler.EmitSchedule(); + + // Clean up register live-range state. + Scheduler.FinishBlock(); } return true; } -/// Schedule - Schedule the DAG using list scheduling. +/// StartBlock - Initialize register live-range state for scheduling in +/// this block. +/// +void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) { + // Call the superclass. + ScheduleDAGInstrs::StartBlock(BB); + + // Clear out the register class data. + std::fill(Classes, array_endof(Classes), + static_cast(0)); + + // Initialize the indices to indicate that no registers are live. + std::fill(KillIndices, array_endof(KillIndices), ~0u); + std::fill(DefIndices, array_endof(DefIndices), BB->size()); + + // Determine the live-out physregs for this block. + if (!BB->empty() && BB->back().getDesc().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; + Classes[Reg] = reinterpret_cast(-1); + KillIndices[Reg] = BB->size(); + DefIndices[Reg] = ~0u; + // Repeat, for all aliases. + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + unsigned AliasReg = *Alias; + Classes[AliasReg] = reinterpret_cast(-1); + KillIndices[AliasReg] = BB->size(); + DefIndices[AliasReg] = ~0u; + } + } + else + // In a non-return block, examine the live-in regs of all successors. + for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), + SE = BB->succ_end(); SI != SE; ++SI) + for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), + E = (*SI)->livein_end(); I != E; ++I) { + unsigned Reg = *I; + Classes[Reg] = reinterpret_cast(-1); + KillIndices[Reg] = BB->size(); + DefIndices[Reg] = ~0u; + // Repeat, for all aliases. + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + unsigned AliasReg = *Alias; + Classes[AliasReg] = reinterpret_cast(-1); + KillIndices[AliasReg] = BB->size(); + DefIndices[AliasReg] = ~0u; + } + } + + // Consider callee-saved registers as live-out, since we're running after + // prologue/epilogue insertion so there's no way to add additional + // saved registers. + // + // TODO: If the callee saves and restores these, then we can potentially + // use them between the save and the restore. To do that, we could scan + // the exit blocks to see which of these registers are defined. + // Alternatively, callee-saved registers that aren't saved and restored + // could be marked live-in in every block. + for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { + unsigned Reg = *I; + Classes[Reg] = reinterpret_cast(-1); + KillIndices[Reg] = BB->size(); + DefIndices[Reg] = ~0u; + // Repeat, for all aliases. + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + unsigned AliasReg = *Alias; + Classes[AliasReg] = reinterpret_cast(-1); + KillIndices[AliasReg] = BB->size(); + DefIndices[AliasReg] = ~0u; + } + } +} + +/// Schedule - Schedule the instruction range using list scheduling. +/// void SchedulePostRATDList::Schedule() { DOUT << "********** List Scheduling **********\n"; @@ -222,6 +358,8 @@ void SchedulePostRATDList::Schedule() { // that register, and add new anti-dependence and output-dependence // edges based on the next live range of the register. SUnits.clear(); + EntrySU = SUnit(); + ExitSU = SUnit(); BuildSchedGraph(); } } @@ -233,6 +371,23 @@ void SchedulePostRATDList::Schedule() { AvailableQueue.releaseState(); } +/// Observe - Update liveness information to account for the current +/// instruction, which will not be scheduled. +/// +void SchedulePostRATDList::Observe(MachineInstr *MI) { + PrescanInstruction(MI); + ScanInstruction(MI, 0); +} + +/// FinishBlock - Clean up register live-range state. +/// +void SchedulePostRATDList::FinishBlock() { + RegRefs.clear(); + + // Call the superclass. + ScheduleDAGInstrs::FinishBlock(); +} + /// getInstrOperandRegClass - Return register class of the operand of an /// instruction of the specified TargetInstrDesc. static const TargetRegisterClass* @@ -267,6 +422,111 @@ static SDep *CriticalPathStep(SUnit *SU) { return Next; } +void SchedulePostRATDList::PrescanInstruction(MachineInstr *MI) { + // Scan the register operands for this instruction and update + // Classes and RegRefs. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + const TargetRegisterClass *NewRC = + getInstrOperandRegClass(TRI, MI->getDesc(), i); + + // For now, only allow the register to be changed if its register + // class is consistent across all uses. + if (!Classes[Reg] && NewRC) + Classes[Reg] = NewRC; + else if (!NewRC || Classes[Reg] != NewRC) + Classes[Reg] = reinterpret_cast(-1); + + // Now check for aliases. + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + // If an alias of the reg is used during the live range, give up. + // Note that this allows us to skip checking if AntiDepReg + // overlaps with any of the aliases, among other things. + unsigned AliasReg = *Alias; + if (Classes[AliasReg]) { + Classes[AliasReg] = reinterpret_cast(-1); + Classes[Reg] = reinterpret_cast(-1); + } + } + + // If we're still willing to consider this register, note the reference. + if (Classes[Reg] != reinterpret_cast(-1)) + RegRefs.insert(std::make_pair(Reg, &MO)); + } +} + +void SchedulePostRATDList::ScanInstruction(MachineInstr *MI, + unsigned Count) { + // Update liveness. + // Proceding upwards, registers that are defed but not used in this + // instruction are now dead. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + if (!MO.isDef()) continue; + // Ignore two-addr defs. + if (MI->isRegReDefinedByTwoAddr(i)) continue; + + DefIndices[Reg] = Count; + KillIndices[Reg] = ~0u; + Classes[Reg] = 0; + RegRefs.erase(Reg); + // Repeat, for all subregs. + for (const unsigned *Subreg = TRI->getSubRegisters(Reg); + *Subreg; ++Subreg) { + unsigned SubregReg = *Subreg; + DefIndices[SubregReg] = Count; + KillIndices[SubregReg] = ~0u; + Classes[SubregReg] = 0; + RegRefs.erase(SubregReg); + } + // Conservatively mark super-registers as unusable. + for (const unsigned *Super = TRI->getSuperRegisters(Reg); + *Super; ++Super) { + unsigned SuperReg = *Super; + Classes[SuperReg] = reinterpret_cast(-1); + } + } + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + if (!MO.isUse()) continue; + + const TargetRegisterClass *NewRC = + getInstrOperandRegClass(TRI, MI->getDesc(), i); + + // For now, only allow the register to be changed if its register + // class is consistent across all uses. + if (!Classes[Reg] && NewRC) + Classes[Reg] = NewRC; + else if (!NewRC || Classes[Reg] != NewRC) + Classes[Reg] = reinterpret_cast(-1); + + RegRefs.insert(std::make_pair(Reg, &MO)); + + // It wasn't previously live but now it is, this is a kill. + if (KillIndices[Reg] == ~0u) { + KillIndices[Reg] = Count; + DefIndices[Reg] = ~0u; + } + // Repeat, for all aliases. + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + unsigned AliasReg = *Alias; + if (KillIndices[AliasReg] == ~0u) { + KillIndices[AliasReg] = Count; + DefIndices[AliasReg] = ~0u; + } + } + } +} + /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path /// of the ScheduleDAG and break them by renaming registers. /// @@ -291,84 +551,6 @@ bool SchedulePostRATDList::BreakAntiDependencies() { SUnit *CriticalPathSU = Max; MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); - // For live regs that are only used in one register class in a live range, - // the register class. If the register is not live, the corresponding value - // is null. If the register is live but used in multiple register classes, - // the corresponding value is -1 casted to a pointer. - const TargetRegisterClass * - Classes[TargetRegisterInfo::FirstVirtualRegister] = {}; - - // Map registers to all their references within a live range. - std::multimap RegRefs; - - // The index of the most recent kill (proceding bottom-up), or ~0u if - // the register is not live. - unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; - std::fill(KillIndices, array_endof(KillIndices), ~0u); - // The index of the most recent complete def (proceding bottom up), or ~0u if - // the register is live. - unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; - std::fill(DefIndices, array_endof(DefIndices), BB->size()); - - // Determine the live-out physregs for this block. - if (BB->back().getDesc().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; - Classes[Reg] = reinterpret_cast(-1); - KillIndices[Reg] = BB->size(); - DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - Classes[AliasReg] = reinterpret_cast(-1); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; - } - } - else - // In a non-return block, examine the live-in regs of all successors. - for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), - SE = BB->succ_end(); SI != SE; ++SI) - for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), - E = (*SI)->livein_end(); I != E; ++I) { - unsigned Reg = *I; - Classes[Reg] = reinterpret_cast(-1); - KillIndices[Reg] = BB->size(); - DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - Classes[AliasReg] = reinterpret_cast(-1); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; - } - } - - // Consider callee-saved registers as live-out, since we're running after - // prologue/epilogue insertion so there's no way to add additional - // saved registers. - // - // TODO: If the callee saves and restores these, then we can potentially - // use them between the save and the restore. To do that, we could scan - // the exit blocks to see which of these registers are defined. - // Alternatively, callee-saved registers that aren't saved and restored - // could be marked live-in in every block. - for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { - unsigned Reg = *I; - Classes[Reg] = reinterpret_cast(-1); - KillIndices[Reg] = BB->size(); - DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - Classes[AliasReg] = reinterpret_cast(-1); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; - } - } - // Consider this pattern: // A = ... // ... = A @@ -481,43 +663,19 @@ bool SchedulePostRATDList::BreakAntiDependencies() { } } - // Scan the register operands for this instruction and update - // Classes and RegRefs. + PrescanInstruction(MI); + + // If this instruction has a use of AntiDepReg, breaking it + // is invalid. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); if (Reg == 0) continue; - const TargetRegisterClass *NewRC = - getInstrOperandRegClass(TRI, MI->getDesc(), i); - - // If this instruction has a use of AntiDepReg, breaking it - // is invalid. - if (MO.isUse() && AntiDepReg == Reg) + if (MO.isUse() && AntiDepReg == Reg) { AntiDepReg = 0; - - // For now, only allow the register to be changed if its register - // class is consistent across all uses. - if (!Classes[Reg] && NewRC) - Classes[Reg] = NewRC; - else if (!NewRC || Classes[Reg] != NewRC) - Classes[Reg] = reinterpret_cast(-1); - - // Now check for aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - // If an alias of the reg is used during the live range, give up. - // Note that this allows us to skip checking if AntiDepReg - // overlaps with any of the aliases, among other things. - unsigned AliasReg = *Alias; - if (Classes[AliasReg]) { - Classes[AliasReg] = reinterpret_cast(-1); - Classes[Reg] = reinterpret_cast(-1); - } + break; } - - // If we're still willing to consider this register, note the reference. - if (Classes[Reg] != reinterpret_cast(-1)) - RegRefs.insert(std::make_pair(Reg, &MO)); } // Determine AntiDepReg's register class, if it is live and is @@ -584,71 +742,7 @@ bool SchedulePostRATDList::BreakAntiDependencies() { } } - // Update liveness. - // Proceding upwards, registers that are defed but not used in this - // instruction are now dead. - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - if (!MO.isDef()) continue; - // Ignore two-addr defs. - if (MI->isRegReDefinedByTwoAddr(i)) continue; - - DefIndices[Reg] = Count; - KillIndices[Reg] = ~0u; - Classes[Reg] = 0; - RegRefs.erase(Reg); - // Repeat, for all subregs. - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) { - unsigned SubregReg = *Subreg; - DefIndices[SubregReg] = Count; - KillIndices[SubregReg] = ~0u; - Classes[SubregReg] = 0; - RegRefs.erase(SubregReg); - } - // Conservatively mark super-registers as unusable. - for (const unsigned *Super = TRI->getSuperRegisters(Reg); - *Super; ++Super) { - unsigned SuperReg = *Super; - Classes[SuperReg] = reinterpret_cast(-1); - } - } - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - if (!MO.isUse()) continue; - - const TargetRegisterClass *NewRC = - getInstrOperandRegClass(TRI, MI->getDesc(), i); - - // For now, only allow the register to be changed if its register - // class is consistent across all uses. - if (!Classes[Reg] && NewRC) - Classes[Reg] = NewRC; - else if (!NewRC || Classes[Reg] != NewRC) - Classes[Reg] = reinterpret_cast(-1); - - RegRefs.insert(std::make_pair(Reg, &MO)); - - // It wasn't previously live but now it is, this is a kill. - if (KillIndices[Reg] == ~0u) { - KillIndices[Reg] = Count; - DefIndices[Reg] = ~0u; - } - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - if (KillIndices[AliasReg] == ~0u) { - KillIndices[AliasReg] = Count; - DefIndices[AliasReg] = ~0u; - } - } - } + ScanInstruction(MI, Count); } assert(Count == ~0u && "Count mismatch!"); @@ -679,9 +773,17 @@ void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { // their latencies. SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); - if (SuccSU->NumPredsLeft == 0) { + // 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) PendingQueue.push_back(SuccSU); - } +} + +/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. +void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { + for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) + ReleaseSucc(SU, &*I); } /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending @@ -695,11 +797,7 @@ void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); SU->setDepthToAtLeast(CurCycle); - // Top down: release successors. - for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) - ReleaseSucc(SU, &*I); - + ReleaseSuccessors(SU); SU->isScheduled = true; AvailableQueue.ScheduledNode(SU); } @@ -709,6 +807,9 @@ void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { void SchedulePostRATDList::ListScheduleTopDown() { unsigned CurCycle = 0; + // Release any successors of the special Entry node. + ReleaseSuccessors(&EntrySU); + // All leaves to Available queue. for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { // It is available if it has no predecessors. @@ -717,7 +818,7 @@ void SchedulePostRATDList::ListScheduleTopDown() { SUnits[i].isAvailable = true; } } - + // While Available queue is not empty, grab the node with the highest // priority. If it is not ready put it back. Schedule the node. std::vector NotReady; diff --git a/lib/CodeGen/ScheduleDAG.cpp b/lib/CodeGen/ScheduleDAG.cpp index 718f591902f..f9b94083548 100644 --- a/lib/CodeGen/ScheduleDAG.cpp +++ b/lib/CodeGen/ScheduleDAG.cpp @@ -28,7 +28,8 @@ ScheduleDAG::ScheduleDAG(MachineFunction &mf) TRI(TM.getRegisterInfo()), TLI(TM.getTargetLowering()), MF(mf), MRI(mf.getRegInfo()), - ConstPool(MF.getConstantPool()) { + ConstPool(MF.getConstantPool()), + EntrySU(), ExitSU() { } ScheduleDAG::~ScheduleDAG() {} @@ -58,6 +59,8 @@ void ScheduleDAG::Run(SelectionDAG *dag, MachineBasicBlock *bb, BB = bb; Begin = begin; End = end; + EntrySU = SUnit(); + ExitSU = SUnit(); Schedule(); diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index eee398ea16f..dac29f1161d 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -15,86 +15,22 @@ #define DEBUG_TYPE "sched-instrs" #include "ScheduleDAGInstrs.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtarget.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/SmallSet.h" -#include using namespace llvm; -namespace { - class VISIBILITY_HIDDEN LoopDependencies { - const MachineLoopInfo &MLI; - const MachineDominatorTree &MDT; - - public: - typedef std::map > - LoopDeps; - LoopDeps Deps; - - LoopDependencies(const MachineLoopInfo &mli, - const MachineDominatorTree &mdt) : - MLI(mli), MDT(mdt) {} - - void VisitLoop(const MachineLoop *Loop) { - Deps.clear(); - MachineBasicBlock *Header = Loop->getHeader(); - SmallSet LoopLiveIns; - for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(), - LE = Header->livein_end(); LI != LE; ++LI) - LoopLiveIns.insert(*LI); - - const MachineDomTreeNode *Node = MDT.getNode(Header); - const MachineBasicBlock *MBB = Node->getBlock(); - assert(Loop->contains(MBB) && - "Loop does not contain header!"); - VisitRegion(Node, MBB, Loop, LoopLiveIns); - } - - private: - void VisitRegion(const MachineDomTreeNode *Node, - const MachineBasicBlock *MBB, - const MachineLoop *Loop, - const SmallSet &LoopLiveIns) { - unsigned Count = 0; - for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I, ++Count) { - const MachineInstr *MI = I; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isUse()) - continue; - unsigned MOReg = MO.getReg(); - if (LoopLiveIns.count(MOReg)) - Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count))); - } - } - - const std::vector &Children = Node->getChildren(); - for (std::vector::const_iterator I = - Children.begin(), E = Children.end(); I != E; ++I) { - const MachineDomTreeNode *ChildNode = *I; - MachineBasicBlock *ChildBlock = ChildNode->getBlock(); - if (Loop->contains(ChildBlock)) - VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns); - } - } - }; -} - ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo &mli, const MachineDominatorTree &mdt) - : ScheduleDAG(mf), MLI(mli), MDT(mdt) {} + : ScheduleDAG(mf), MLI(mli), MDT(mdt), LoopRegs(MLI, MDT) {} /// getOpcode - If this is an Instruction or a ConstantExpr, return the /// opcode value. Otherwise return UserOp1. @@ -172,7 +108,20 @@ static const Value *getUnderlyingObjectForInstr(const MachineInstr *MI) { return V; } +void ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { + if (MachineLoop *ML = MLI.getLoopFor(BB)) + if (BB == ML->getLoopLatch()) { + MachineBasicBlock *Header = ML->getHeader(); + for (MachineBasicBlock::livein_iterator I = Header->livein_begin(), + E = Header->livein_end(); I != E; ++I) + LoopLiveInRegs.insert(*I); + LoopRegs.VisitLoop(ML); + } +} + void ScheduleDAGInstrs::BuildSchedGraph() { + // We'll be allocating one SUnit for each instruction, plus one for + // the region exit node. SUnits.reserve(BB->size()); // We build scheduling units by walking a block's instruction list from bottom @@ -189,30 +138,6 @@ void ScheduleDAGInstrs::BuildSchedGraph() { std::map MemDefs; std::map > MemUses; - // If we have an SUnit which is representing a terminator instruction, we - // can use it as a place-holder successor for inter-block dependencies. - SUnit *Terminator = 0; - - // Terminators can perform control transfers, we we need to make sure that - // all the work of the block is done before the terminator. Labels can - // mark points of interest for various types of meta-data (eg. EH data), - // and we need to make sure nothing is scheduled around them. - SUnit *SchedulingBarrier = 0; - - LoopDependencies LoopRegs(MLI, MDT); - - // Track which regs are live into a loop, to help guide back-edge-aware - // scheduling. - SmallSet LoopLiveInRegs; - if (MachineLoop *ML = MLI.getLoopFor(BB)) - if (BB == ML->getLoopLatch()) { - MachineBasicBlock *Header = ML->getHeader(); - for (MachineBasicBlock::livein_iterator I = Header->livein_begin(), - E = Header->livein_end(); I != E; ++I) - LoopLiveInRegs.insert(*I); - LoopRegs.VisitLoop(ML); - } - // Check to see if the scheduler cares about latencies. bool UnitLatencies = ForceUnitLatencies(); @@ -220,10 +145,14 @@ void ScheduleDAGInstrs::BuildSchedGraph() { unsigned SpecialAddressLatency = TM.getSubtarget().getSpecialAddressLatency(); + // Walk the list of instructions, from bottom moving up. for (MachineBasicBlock::iterator MII = End, MIE = Begin; MII != MIE; --MII) { MachineInstr *MI = prior(MII); const TargetInstrDesc &TID = MI->getDesc(); + assert(!TID.isTerminator() && !MI->isLabel() && + "Cannot schedule terminators or labels!"); + // Create the SUnit for this MI. SUnit *SU = NewSUnit(MI); // Assign the Latency field of SU using target-provided information. @@ -298,8 +227,7 @@ void ScheduleDAGInstrs::BuildSchedGraph() { // If a def is going to wrap back around to the top of the loop, // backschedule it. - // TODO: Blocks in loops without terminators can benefit too. - if (!UnitLatencies && Terminator && DefList.empty()) { + if (!UnitLatencies && DefList.empty()) { LoopDependencies::LoopDeps::iterator I = LoopRegs.Deps.find(Reg); if (I != LoopRegs.Deps.end()) { const MachineOperand *UseMO = I->second.first; @@ -323,10 +251,10 @@ void ScheduleDAGInstrs::BuildSchedGraph() { // scheduling region. Latency -= std::min(Latency, Count); // Add the artifical edge. - Terminator->addPred(SDep(SU, SDep::Order, Latency, - /*Reg=*/0, /*isNormalMemory=*/false, - /*isMustAlias=*/false, - /*isArtificial=*/true)); + ExitSU.addPred(SDep(SU, SDep::Order, Latency, + /*Reg=*/0, /*isNormalMemory=*/false, + /*isMustAlias=*/false, + /*isArtificial=*/true)); } else if (SpecialAddressLatency > 0 && UseTID.OpInfo[UseMOIdx].isLookupPtrRegClass()) { // The entire loop body is within the current scheduling region @@ -355,7 +283,7 @@ void ScheduleDAGInstrs::BuildSchedGraph() { // after stack slots are lowered to actual addresses. // TODO: Use an AliasAnalysis and do real alias-analysis queries, and // produce more precise dependence information. - if (TID.isCall() || TID.isTerminator() || TID.hasUnmodeledSideEffects()) { + if (TID.isCall() || TID.hasUnmodeledSideEffects()) { new_chain: // This is the conservative case. Add dependencies on all memory // references. @@ -379,7 +307,7 @@ void ScheduleDAGInstrs::BuildSchedGraph() { // See if it is known to just have a single memory reference. MachineInstr *ChainMI = Chain->getInstr(); const TargetInstrDesc &ChainTID = ChainMI->getDesc(); - if (!ChainTID.isCall() && !ChainTID.isTerminator() && + if (!ChainTID.isCall() && !ChainTID.hasUnmodeledSideEffects() && ChainMI->hasOneMemOperand() && !ChainMI->memoperands_begin()->isVolatile() && @@ -452,28 +380,6 @@ void ScheduleDAGInstrs::BuildSchedGraph() { PendingLoads.push_back(SU); } } - - // Add chain edges from terminators and labels to ensure that no - // instructions are scheduled past them. - if (SchedulingBarrier && SU->Succs.empty()) - SchedulingBarrier->addPred(SDep(SU, SDep::Order, SU->Latency)); - // If we encounter a mid-block label, we need to go back and add - // dependencies on SUnits we've already processed to prevent the - // label from moving downward. - if (MI->isLabel()) - for (SUnit *I = SU; I != &SUnits[0]; --I) { - SUnit *SuccSU = SU-1; - SuccSU->addPred(SDep(SU, SDep::Order, SU->Latency)); - MachineInstr *SuccMI = SuccSU->getInstr(); - if (SuccMI->getDesc().isTerminator() || SuccMI->isLabel()) - break; - } - // If this instruction obstructs all scheduling, remember it. - if (TID.isTerminator() || MI->isLabel()) - SchedulingBarrier = SU; - // If this instruction is a terminator, remember it. - if (TID.isTerminator()) - Terminator = SU; } for (int i = 0, e = TRI->getNumRegs(); i != e; ++i) { @@ -483,6 +389,10 @@ void ScheduleDAGInstrs::BuildSchedGraph() { PendingLoads.clear(); } +void ScheduleDAGInstrs::FinishBlock() { + // Nothing to do. +} + void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); @@ -505,7 +415,12 @@ void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { std::string s; raw_string_ostream oss(s); - SU->getInstr()->print(oss); + if (SU == &EntrySU) + oss << ""; + else if (SU == &ExitSU) + oss << ""; + else + SU->getInstr()->print(oss); return oss.str(); } @@ -531,5 +446,10 @@ MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() { BB->insert(End, SU->getInstr()); } + // Update the Begin iterator, as the first instruction in the block + // may have been scheduled later. + if (!Sequence.empty()) + Begin = Sequence[0]->getInstr(); + return BB; } diff --git a/lib/CodeGen/ScheduleDAGInstrs.h b/lib/CodeGen/ScheduleDAGInstrs.h index 3a10b5e4de9..713534ba767 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.h +++ b/lib/CodeGen/ScheduleDAGInstrs.h @@ -15,14 +15,86 @@ #ifndef SCHEDULEDAGINSTRS_H #define SCHEDULEDAGINSTRS_H +#include "llvm/ADT/SmallSet.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/Support/Compiler.h" #include "llvm/Target/TargetRegisterInfo.h" +#include namespace llvm { class MachineLoopInfo; class MachineDominatorTree; - class ScheduleDAGInstrs : public ScheduleDAG { + /// LoopDependencies - This class analyzes loop-oriented register + /// dependencies, which are used to guide scheduling decisions. + /// For example, loop induction variable increments should be + /// scheduled as soon as possible after the variable's last use. + /// + class VISIBILITY_HIDDEN LoopDependencies { + const MachineLoopInfo &MLI; + const MachineDominatorTree &MDT; + + public: + typedef std::map > + LoopDeps; + LoopDeps Deps; + + LoopDependencies(const MachineLoopInfo &mli, + const MachineDominatorTree &mdt) : + MLI(mli), MDT(mdt) {} + + /// VisitLoop - Clear out any previous state and analyze the given loop. + /// + void VisitLoop(const MachineLoop *Loop) { + Deps.clear(); + MachineBasicBlock *Header = Loop->getHeader(); + SmallSet LoopLiveIns; + for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(), + LE = Header->livein_end(); LI != LE; ++LI) + LoopLiveIns.insert(*LI); + + const MachineDomTreeNode *Node = MDT.getNode(Header); + const MachineBasicBlock *MBB = Node->getBlock(); + assert(Loop->contains(MBB) && + "Loop does not contain header!"); + VisitRegion(Node, MBB, Loop, LoopLiveIns); + } + + private: + void VisitRegion(const MachineDomTreeNode *Node, + const MachineBasicBlock *MBB, + const MachineLoop *Loop, + const SmallSet &LoopLiveIns) { + unsigned Count = 0; + for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I, ++Count) { + const MachineInstr *MI = I; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isUse()) + continue; + unsigned MOReg = MO.getReg(); + if (LoopLiveIns.count(MOReg)) + Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count))); + } + } + + const std::vector &Children = Node->getChildren(); + for (std::vector::const_iterator I = + Children.begin(), E = Children.end(); I != E; ++I) { + const MachineDomTreeNode *ChildNode = *I; + MachineBasicBlock *ChildBlock = ChildNode->getBlock(); + if (Loop->contains(ChildBlock)) + VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns); + } + } + }; + + /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of + /// MachineInstrs. + class VISIBILITY_HIDDEN ScheduleDAGInstrs : public ScheduleDAG { const MachineLoopInfo &MLI; const MachineDominatorTree &MDT; @@ -38,6 +110,15 @@ namespace llvm { /// to minimize construction/destruction. std::vector PendingLoads; + /// LoopRegs - Track which registers are used for loop-carried dependencies. + /// + LoopDependencies LoopRegs; + + /// LoopLiveInRegs - Track which regs are live into a loop, to help guide + /// back-edge-aware scheduling. + /// + SmallSet LoopLiveInRegs; + public: explicit ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo &mli, @@ -68,11 +149,19 @@ namespace llvm { virtual MachineBasicBlock *EmitSchedule(); + /// StartBlock - Prepare to perform scheduling in the given block. + /// + virtual void StartBlock(MachineBasicBlock *BB); + /// Schedule - Order nodes according to selected style, filling /// in the Sequence member. /// virtual void Schedule() = 0; + /// FinishBlock - Clean up after scheduling in the given block. + /// + virtual void FinishBlock(); + virtual void dumpNode(const SUnit *SU) const; virtual std::string getGraphNodeLabel(const SUnit *SU) const; diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp index e43b992407b..1cd893e587d 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp @@ -90,6 +90,7 @@ public: private: void ReleasePred(SUnit *SU, SDep *PredEdge); + void ReleasePredecessors(SUnit *SU, unsigned CurCycle); void ScheduleNodeBottomUp(SUnit*, unsigned); SUnit *CopyAndMoveSuccessors(SUnit*); void InsertCopiesAndMoveSuccs(SUnit*, unsigned, @@ -142,23 +143,15 @@ void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) { } #endif - if (PredSU->NumSuccsLeft == 0) { + // If all the node's successors are scheduled, this node is ready + // to be scheduled. Ignore the special EntrySU node. + if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { PredSU->isAvailable = true; AvailableQueue.push(PredSU); } } -/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending -/// count of its predecessors. If a predecessor pending count is zero, add it to -/// the Available queue. -void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { - DOUT << "*** Scheduling [" << CurCycle << "]: "; - DEBUG(SU->dump(this)); - - assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); - SU->setHeightToAtLeast(CurCycle); - Sequence.push_back(SU); - +void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { // Bottom up: release predecessors for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) { @@ -175,6 +168,20 @@ void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { } } } +} + +/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending +/// count of its predecessors. If a predecessor pending count is zero, add it to +/// the Available queue. +void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { + DOUT << "*** Scheduling [" << CurCycle << "]: "; + DEBUG(SU->dump(this)); + + assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); + SU->setHeightToAtLeast(CurCycle); + Sequence.push_back(SU); + + ReleasePredecessors(SU, CurCycle); // Release all the implicit physical register defs that are live. for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); @@ -480,6 +487,10 @@ bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, /// schedulers. void ScheduleDAGFast::ListScheduleBottomUp() { unsigned CurCycle = 0; + + // Release any predecessors of the special Exit node. + ReleasePredecessors(&ExitSU, CurCycle); + // Add root to Available queue. if (!SUnits.empty()) { SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index b0b9e4ce08c..c78ecb8aa4d 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -78,6 +78,7 @@ public: private: void ReleaseSucc(SUnit *SU, const SDep &D); + void ReleaseSuccessors(SUnit *SU); void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); void ListScheduleTopDown(); }; @@ -118,8 +119,20 @@ void ScheduleDAGList::ReleaseSucc(SUnit *SU, const SDep &D) { SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); - if (SuccSU->NumPredsLeft == 0) { + // 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) PendingQueue.push_back(SuccSU); +} + +void ScheduleDAGList::ReleaseSuccessors(SUnit *SU) { + // Top down: release successors. + for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) { + assert(!I->isAssignedRegDep() && + "The list-td scheduler doesn't yet support physreg dependencies!"); + + ReleaseSucc(SU, *I); } } @@ -134,15 +147,7 @@ void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); SU->setDepthToAtLeast(CurCycle); - // Top down: release successors. - for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) { - assert(!I->isAssignedRegDep() && - "The list-td scheduler doesn't yet support physreg dependencies!"); - - ReleaseSucc(SU, *I); - } - + ReleaseSuccessors(SU); SU->isScheduled = true; AvailableQueue->ScheduledNode(SU); } @@ -152,6 +157,9 @@ void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { void ScheduleDAGList::ListScheduleTopDown() { unsigned CurCycle = 0; + // Release any successors of the special Entry node. + ReleaseSuccessors(&EntrySU); + // All leaves to Available queue. for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { // It is available if it has no predecessors. diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index 16102f342f4..94006b5d8c8 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -114,7 +114,9 @@ public: private: void ReleasePred(SUnit *SU, const SDep *PredEdge); + void ReleasePredecessors(SUnit *SU, unsigned CurCycle); void ReleaseSucc(SUnit *SU, const SDep *SuccEdge); + void ReleaseSuccessors(SUnit *SU); void CapturePred(SDep *PredEdge); void ScheduleNodeBottomUp(SUnit*, unsigned); void ScheduleNodeTopDown(SUnit*, unsigned); @@ -204,23 +206,15 @@ void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) { } #endif - if (PredSU->NumSuccsLeft == 0) { + // If all the node's successors are scheduled, this node is ready + // to be scheduled. Ignore the special EntrySU node. + if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { PredSU->isAvailable = true; AvailableQueue->push(PredSU); } } -/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending -/// count of its predecessors. If a predecessor pending count is zero, add it to -/// the Available queue. -void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { - DOUT << "*** Scheduling [" << CurCycle << "]: "; - DEBUG(SU->dump(this)); - - assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); - SU->setHeightToAtLeast(CurCycle); - Sequence.push_back(SU); - +void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { // Bottom up: release predecessors for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) { @@ -237,6 +231,20 @@ void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { } } } +} + +/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending +/// count of its predecessors. If a predecessor pending count is zero, add it to +/// the Available queue. +void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { + DOUT << "*** Scheduling [" << CurCycle << "]: "; + DEBUG(SU->dump(this)); + + assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); + SU->setHeightToAtLeast(CurCycle); + Sequence.push_back(SU); + + ReleasePredecessors(SU, CurCycle); // Release all the implicit physical register defs that are live. for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); @@ -627,6 +635,10 @@ bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, /// schedulers. void ScheduleDAGRRList::ListScheduleBottomUp() { unsigned CurCycle = 0; + + // Release any predecessors of the special Exit node. + ReleasePredecessors(&ExitSU, CurCycle); + // Add root to Available queue. if (!SUnits.empty()) { SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; @@ -789,12 +801,25 @@ void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) { } #endif - if (SuccSU->NumPredsLeft == 0) { + // 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) { SuccSU->isAvailable = true; AvailableQueue->push(SuccSU); } } +void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) { + // Top down: release successors + for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) { + assert(!I->isAssignedRegDep() && + "The list-tdrr scheduler doesn't yet support physreg dependencies!"); + + 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. @@ -806,15 +831,7 @@ void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { SU->setDepthToAtLeast(CurCycle); Sequence.push_back(SU); - // Top down: release successors - for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) { - assert(!I->isAssignedRegDep() && - "The list-tdrr scheduler doesn't yet support physreg dependencies!"); - - ReleaseSucc(SU, &*I); - } - + ReleaseSuccessors(SU); SU->isScheduled = true; AvailableQueue->ScheduledNode(SU); } @@ -824,6 +841,9 @@ void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { void ScheduleDAGRRList::ListScheduleTopDown() { unsigned CurCycle = 0; + // Release any successors of the special Entry node. + ReleaseSuccessors(&EntrySU); + // All leaves to Available queue. for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { // It is available if it has no predecessors. -- 2.34.1