diff options
| -rw-r--r-- | include/llvm/CodeGen/ScheduleDAG.h | 16 | ||||
| -rw-r--r-- | lib/CodeGen/DFAPacketizer.cpp | 4 | ||||
| -rw-r--r-- | lib/CodeGen/MachineScheduler.cpp | 26 | ||||
| -rw-r--r-- | lib/CodeGen/PostRASchedulerList.cpp | 50 | ||||
| -rw-r--r-- | lib/CodeGen/ScheduleDAG.cpp | 22 | ||||
| -rw-r--r-- | lib/CodeGen/ScheduleDAGInstrs.cpp | 49 | ||||
| -rw-r--r-- | lib/CodeGen/ScheduleDAGInstrs.h | 56 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp | 20 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h | 9 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 7 |
10 files changed, 156 insertions, 103 deletions
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 5c317d2f91..c2dee41bd9 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -486,15 +486,11 @@ namespace llvm { class ScheduleDAG { public: - MachineBasicBlock *BB; // The block in which to insert instructions - MachineBasicBlock::iterator InsertPos;// The position to insert instructions const TargetMachine &TM; // Target processor const TargetInstrInfo *TII; // Target instruction information const TargetRegisterInfo *TRI; // Target processor register info MachineFunction &MF; // Machine function MachineRegisterInfo &MRI; // Virtual/real register map - std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s - // represent noop instructions. std::vector<SUnit> SUnits; // The scheduling units. SUnit EntrySU; // Special node for the region entry. SUnit ExitSU; // Special node for the region exit. @@ -509,6 +505,9 @@ namespace llvm { virtual ~ScheduleDAG(); + /// clearDAG - clear the DAG state (between regions). + void clearDAG(); + /// getInstrDesc - Return the MCInstrDesc of this SUnit. /// Return NULL for SDNodes without a machine opcode. const MCInstrDesc *getInstrDesc(const SUnit *SU) const { @@ -542,10 +541,6 @@ namespace llvm { #endif protected: - /// Run - perform scheduling. - /// - void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos); - /// ComputeLatency - Compute node latency. /// virtual void ComputeLatency(SUnit *SU) = 0; @@ -556,11 +551,6 @@ namespace llvm { virtual void ComputeOperandLatency(SUnit *, SUnit *, SDep&) const { } - /// Schedule - Order nodes according to selected style, filling - /// in the Sequence member. - /// - virtual void Schedule() = 0; - /// ForceUnitLatencies - Return true if all scheduling edges should be given /// a latency value of one. The default is to return false; schedulers may /// override this as needed. diff --git a/lib/CodeGen/DFAPacketizer.cpp b/lib/CodeGen/DFAPacketizer.cpp index f0cf290825..f2179eeef5 100644 --- a/lib/CodeGen/DFAPacketizer.cpp +++ b/lib/CodeGen/DFAPacketizer.cpp @@ -185,7 +185,9 @@ void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, MachineBasicBlock::iterator BeginItr, MachineBasicBlock::iterator EndItr) { DefaultVLIWScheduler *Scheduler = (DefaultVLIWScheduler *)SchedulerImpl; - Scheduler->Run(MBB, BeginItr, EndItr, MBB->size()); + Scheduler->enterRegion(MBB, BeginItr, EndItr, MBB->size()); + Scheduler->Schedule(); + Scheduler->exitRegion(); // Remember scheduling units. SUnits = Scheduler->SUnits; diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index 5d7dee8e1e..96af4091e2 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -281,15 +281,17 @@ bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) break; } - if (I == RegionEnd) { - // Skip empty scheduling regions. - RegionEnd = llvm::prior(RegionEnd); - --RemainingCount; - continue; - } - // Skip regions with one instruction. - if (I == llvm::prior(RegionEnd)) { + // Notify the scheduler of the region, even if we may skip scheduling + // it. Perhaps it still needs to be bundled. + Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount); + + // Skip empty scheduling regions (0 or 1 schedulable instructions). + if (I == RegionEnd || I == llvm::prior(RegionEnd)) { RegionEnd = llvm::prior(RegionEnd); + if (I != RegionEnd) + --RemainingCount; + // Close the current region. Bundle the terminator if needed. + Scheduler->exitRegion(); continue; } DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() @@ -300,8 +302,12 @@ bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { // Inform ScheduleDAGInstrs of the region being scheduled. It calls back // to our Schedule() method. - Scheduler->Run(MBB, I, RegionEnd, MBB->size()); - RegionEnd = Scheduler->Begin; + Scheduler->Schedule(); + Scheduler->exitRegion(); + + // Scheduling has invalidated the current iterator 'I'. Ask the + // scheduler for the top of it's scheduled region. + RegionEnd = Scheduler->begin(); } assert(RemainingCount == 0 && "Instruction count mismatch!"); Scheduler->FinishBlock(); diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index 488dab7217..c5310fce10 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -127,6 +127,9 @@ namespace { /// LiveRegs - true if the register is live. BitVector LiveRegs; + /// The schedule. Null SUnit*'s represent noop instructions. + std::vector<SUnit*> Sequence; + public: SchedulePostRATDList( MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, @@ -141,6 +144,15 @@ namespace { /// 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(); @@ -206,6 +218,25 @@ 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(); +} + /// dumpSchedule - dump the scheduled Sequence. void SchedulePostRATDList::dumpSchedule() const { for (unsigned i = 0, e = Sequence.size(); i != e; i++) { @@ -282,7 +313,9 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { // 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.Run(MBB, I, Current, CurrentCount); + Scheduler.enterRegion(MBB, I, Current, CurrentCount); + Scheduler.Schedule(); + Scheduler.exitRegion(); Scheduler.EmitSchedule(); Current = MI; CurrentCount = Count - 1; @@ -296,7 +329,9 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 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. @@ -340,10 +375,7 @@ 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(); + ScheduleDAG::clearDAG(); BuildSchedGraph(AA); NumFixedAnti += Broken; @@ -357,12 +389,6 @@ void SchedulePostRATDList::Schedule() { AvailableQueue.initNodes(SUnits); ListScheduleTopDown(); AvailableQueue.releaseState(); - - DEBUG({ - dbgs() << "*** Final schedule ***\n"; - dumpSchedule(); - dbgs() << '\n'; - }); } /// Observe - Update liveness information to account for the current diff --git a/lib/CodeGen/ScheduleDAG.cpp b/lib/CodeGen/ScheduleDAG.cpp index 7fae783f8d..8fd64265fd 100644 --- a/lib/CodeGen/ScheduleDAG.cpp +++ b/lib/CodeGen/ScheduleDAG.cpp @@ -46,25 +46,17 @@ ScheduleDAG::ScheduleDAG(MachineFunction &mf) ScheduleDAG::~ScheduleDAG() {} -/// getInstrDesc helper to handle SDNodes. -const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const { - if (!Node || !Node->isMachineOpcode()) return NULL; - return &TII->get(Node->getMachineOpcode()); -} - -/// Run - perform scheduling. -/// -void ScheduleDAG::Run(MachineBasicBlock *bb, - MachineBasicBlock::iterator insertPos) { - BB = bb; - InsertPos = insertPos; - +/// Clear the DAG state (e.g. between scheduling regions). +void ScheduleDAG::clearDAG() { SUnits.clear(); - Sequence.clear(); EntrySU = SUnit(); ExitSU = SUnit(); +} - Schedule(); +/// getInstrDesc helper to handle SDNodes. +const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const { + if (!Node || !Node->isMachineOpcode()) return NULL; + return &TII->get(Node->getMachineOpcode()); } /// addPred - This adds the specified edge as a pred of the current node if diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index 8cab9fbbe5..9671b9c146 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -46,22 +46,6 @@ ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, "Virtual registers must be removed prior to PostRA scheduling"); } -/// Run - perform scheduling. -/// -void ScheduleDAGInstrs::Run(MachineBasicBlock *bb, - MachineBasicBlock::iterator begin, - MachineBasicBlock::iterator end, - unsigned endcount) { - BB = bb; - Begin = begin; - InsertPosIndex = endcount; - - // Check to see if the scheduler cares about latencies. - UnitLatencies = ForceUnitLatencies(); - - ScheduleDAG::Run(bb, end); -} - /// getUnderlyingObjectFromInt - This is the function that does the work of /// looking through basic ptrtoint+arithmetic+inttoptr sequences. static const Value *getUnderlyingObjectFromInt(const Value *V) { @@ -148,6 +132,10 @@ void ScheduleDAGInstrs::StartBlock(MachineBasicBlock *BB) { LoopRegs.VisitLoop(ML); } +void ScheduleDAGInstrs::FinishBlock() { + // Nothing to do. +} + /// Initialize the map with the number of registers. void ScheduleDAGInstrs::Reg2SUnitsMap::setRegLimit(unsigned Limit) { PhysRegSet.setUniverse(Limit); @@ -162,6 +150,31 @@ void ScheduleDAGInstrs::Reg2SUnitsMap::clear() { PhysRegSet.clear(); } +/// Initialize the DAG and common scheduler state for the current scheduling +/// region. This does not actually create the DAG, only clears it. The +/// scheduling driver may call BuildSchedGraph multiple times per scheduling +/// region. +void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, + MachineBasicBlock::iterator begin, + MachineBasicBlock::iterator end, + unsigned endcount) { + BB = bb; + Begin = begin; + InsertPos = end; + InsertPosIndex = endcount; + + // Check to see if the scheduler cares about latencies. + UnitLatencies = ForceUnitLatencies(); + + ScheduleDAG::clearDAG(); +} + +/// Close the current scheduling region. Don't clear any state in case the +/// driver wants to refer to the previous scheduling region. +void ScheduleDAGInstrs::exitRegion() { + // Nothing to do. +} + /// AddSchedBarrierDeps - Add dependencies from instructions in the current /// list of instructions being scheduled to scheduling barrier by adding /// the exit SU to the register defs and use list. This is because we want to @@ -715,10 +728,6 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { MISUnitMap.clear(); } -void ScheduleDAGInstrs::FinishBlock() { - // Nothing to do. -} - void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) { // Compute the latency for the node. if (!InstrItins || InstrItins->isEmpty()) { diff --git a/lib/CodeGen/ScheduleDAGInstrs.h b/lib/CodeGen/ScheduleDAGInstrs.h index a27a8c4891..7830f83fff 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.h +++ b/lib/CodeGen/ScheduleDAGInstrs.h @@ -101,6 +101,7 @@ namespace llvm { /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of /// MachineInstrs. class LLVM_LIBRARY_VISIBILITY ScheduleDAGInstrs : public ScheduleDAG { + protected: const MachineLoopInfo &MLI; const MachineDominatorTree &MDT; const MachineFrameInfo *MFI; @@ -112,6 +113,23 @@ namespace llvm { /// Live Intervals provides reaching defs in preRA scheduling. LiveIntervals *LIS; + /// State specific to the current scheduling region. + /// + + // The block in which to insert instructions + MachineBasicBlock *BB; + + // The beginning of the range to + // be scheduled. The range extends + // to InsertPos. + MachineBasicBlock::iterator Begin; + + // The position to insert instructions + MachineBasicBlock::iterator InsertPos; + + // The index in BB of InsertPos. + unsigned InsertPosIndex; + /// After calling BuildSchedGraph, each machine instruction in the current /// scheduling region is mapped to an SUnit. DenseMap<MachineInstr*, SUnit*> MISUnitMap; @@ -209,11 +227,6 @@ namespace llvm { MachineInstr *FirstDbgValue; public: - MachineBasicBlock::iterator Begin; // The beginning of the range to - // be scheduled. The range extends - // to InsertPos. - unsigned InsertPosIndex; // The index in BB of InsertPos. - explicit ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo &mli, const MachineDominatorTree &mdt, @@ -222,6 +235,12 @@ namespace llvm { virtual ~ScheduleDAGInstrs() {} + /// begin - Return an iterator to the top of the current scheduling region. + MachineBasicBlock::iterator begin() const { return Begin; } + + /// end - Return an iterator to the bottom of the current scheduling region. + MachineBasicBlock::iterator end() const { return InsertPos; } + /// NewSUnit - Creates a new SUnit and return a ptr to it. /// SUnit *NewSUnit(MachineInstr *MI) { @@ -235,13 +254,22 @@ namespace llvm { return &SUnits.back(); } + /// StartBlock - Prepare to perform scheduling in the given block. + /// + virtual void StartBlock(MachineBasicBlock *BB); - /// Run - perform scheduling. + /// FinishBlock - Clean up after scheduling in the given block. /// - void Run(MachineBasicBlock *bb, - MachineBasicBlock::iterator begin, - MachineBasicBlock::iterator end, - unsigned endindex); + virtual void FinishBlock(); + + /// 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(); /// BuildSchedGraph - Build SUnits from the MachineBasicBlock that we are /// input. @@ -266,19 +294,11 @@ namespace llvm { virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use, SDep& dep) const; - /// 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; /// Return a label for a DAG node that points to an instruction. diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp index 9c870d5e8c..2d17e9dcdf 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp @@ -46,15 +46,21 @@ static cl::opt<int> HighLatencyCycles( "instructions take for targets with no itinerary")); ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) - : ScheduleDAG(mf), + : ScheduleDAG(mf), BB(0), DAG(0), InstrItins(mf.getTarget().getInstrItineraryData()) {} /// Run - perform scheduling. /// -void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, - MachineBasicBlock::iterator insertPos) { +void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) { + BB = bb; DAG = dag; - ScheduleDAG::Run(bb, insertPos); + + // Clear the scheduler's SUnit DAG. + ScheduleDAG::clearDAG(); + Sequence.clear(); + + // Invoke the target's selection of scheduler. + Schedule(); } /// NewSUnit - Creates a new SUnit and return a ptr to it. @@ -752,7 +758,8 @@ EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, /// InsertPos and MachineBasicBlock that contains this insertion /// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does /// not necessarily refer to returned BB. The emitter may split blocks. -MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { +MachineBasicBlock *ScheduleDAGSDNodes:: +EmitSchedule(MachineBasicBlock::iterator &InsertPos) { InstrEmitter Emitter(BB, InsertPos); DenseMap<SDValue, unsigned> VRBaseMap; DenseMap<SUnit*, unsigned> CopyVRBaseMap; @@ -860,9 +867,8 @@ MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { } } - BB = Emitter.getBlock(); InsertPos = Emitter.getInsertPos(); - return BB; + return Emitter.getBlock(); } /// Return the basic block label. diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h index 69f1b7b657..5605bd506b 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h @@ -35,17 +35,20 @@ namespace llvm { /// class ScheduleDAGSDNodes : public ScheduleDAG { public: + MachineBasicBlock *BB; SelectionDAG *DAG; // DAG of the current basic block const InstrItineraryData *InstrItins; + /// The schedule. Null SUnit*'s represent noop instructions. + std::vector<SUnit*> Sequence; + explicit ScheduleDAGSDNodes(MachineFunction &mf); virtual ~ScheduleDAGSDNodes() {} /// Run - perform scheduling. /// - void Run(SelectionDAG *dag, MachineBasicBlock *bb, - MachineBasicBlock::iterator insertPos); + void Run(SelectionDAG *dag, MachineBasicBlock *bb); /// isPassiveNode - Return true if the node is a non-scheduled leaf. /// @@ -104,8 +107,6 @@ namespace llvm { virtual void ComputeOperandLatency(SDNode *Def, SDNode *Use, unsigned OpIdx, SDep& dep) const; - virtual MachineBasicBlock *EmitSchedule(); - /// Schedule - Order nodes according to selected style, filling /// in the Sequence member. /// diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 1414810f3c..8aabc02443 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -673,7 +673,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { { NamedRegionTimer T("Instruction Scheduling", GroupName, TimePassesIsEnabled); - Scheduler->Run(CurDAG, FuncInfo->MBB, FuncInfo->InsertPt); + Scheduler->Run(CurDAG, FuncInfo->MBB); } if (ViewSUnitDAGs) Scheduler->viewGraph(); @@ -684,8 +684,9 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { { NamedRegionTimer T("Instruction Creation", GroupName, TimePassesIsEnabled); - LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(); - FuncInfo->InsertPt = Scheduler->InsertPos; + // FuncInfo->InsertPt is passed by reference and set to the end of the + // scheduled instructions. + LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt); } // If the block was split, make sure we update any references that are used to |