From 7f8ab785af09e4d6e4db07157a5b5aa449b5c3ae Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Thu, 10 May 2012 21:06:10 +0000 Subject: misched: Introducing Top and Bottom register pressure trackers during scheduling. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156571 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineScheduler.cpp | 81 +++++++++++++++++++++++++++++++++++----- lib/CodeGen/RegisterPressure.cpp | 34 +++++++++-------- lib/CodeGen/RegisterPressure.h | 36 +++++++++++------- 3 files changed, 112 insertions(+), 39 deletions(-) (limited to 'lib') diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index 4314e48f9f..7e871a737b 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -322,15 +322,21 @@ class ScheduleDAGMI : public ScheduleDAGInstrs { RegisterClassInfo *RegClassInfo; MachineSchedStrategy *SchedImpl; + MachineBasicBlock::iterator LiveRegionEnd; + // Register pressure in this region computed by buildSchedGraph. IntervalPressure RegPressure; RegPressureTracker RPTracker; /// The top of the unscheduled zone. MachineBasicBlock::iterator CurrentTop; + IntervalPressure TopPressure; + RegPressureTracker TopRPTracker; /// The bottom of the unscheduled zone. MachineBasicBlock::iterator CurrentBottom; + IntervalPressure BotPressure; + RegPressureTracker BotRPTracker; /// The number of instructions scheduled so far. Used to cut off the /// scheduler at the point determined by misched-cutoff. @@ -339,8 +345,8 @@ public: ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), - RPTracker(RegPressure), CurrentTop(), CurrentBottom(), - NumInstrsScheduled(0) {} + RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), + CurrentBottom(), BotRPTracker(BotPressure), NumInstrsScheduled(0) {} ~ScheduleDAGMI() { delete SchedImpl; @@ -349,6 +355,15 @@ public: MachineBasicBlock::iterator top() const { return CurrentTop; } MachineBasicBlock::iterator bottom() const { return CurrentBottom; } + /// Get current register pressure for the top scheduled instructions. + const IntervalPressure &getTopPressure() const { return TopPressure; } + + /// Get current register pressure for the bottom scheduled instructions. + const IntervalPressure &getBotPressure() const { return BotPressure; } + + /// Get register pressure for the entire scheduling region before scheduling. + const IntervalPressure &getRegPressure() const { return RegPressure; } + /// Implement the ScheduleDAGInstrs interface for handling the next scheduling /// region. This covers all instructions in a block, while schedule() may only /// cover a subset. @@ -362,6 +377,8 @@ public: void schedule(); protected: + void initRegPressure(); + void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); bool checkSchedLimit(); @@ -436,6 +453,9 @@ void ScheduleDAGMI::moveInstruction(MachineInstr *MI, // Fix RegionBegin if another instruction moves above the first instruction. if (RegionBegin == InsertPos) RegionBegin = MI; + // Fix TopRPTracker if we move something above CurrentTop. + if (CurrentTop == InsertPos) + TopRPTracker.setPos(MI); } bool ScheduleDAGMI::checkSchedLimit() { @@ -459,23 +479,55 @@ void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb, unsigned endcount) { ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); - // Setup the register pressure tracker to begin tracking at the end of this - // region. - RPTracker.init(&MF, RegClassInfo, LIS, BB, end); + + // For convenience remember the end of the liveness region. + LiveRegionEnd = + (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd); +} + +// Setup the register pressure trackers for the top scheduled top and bottom +// scheduled regions. +void ScheduleDAGMI::initRegPressure() { + TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin); + BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); + + // Close the RPTracker to finalize live ins. + RPTracker.closeRegion(); + + // Initialize the live ins and live outs. + TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); + BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); + + // Close one end of the tracker so we can call + // getMaxUpward/DownwardPressureDelta before advancing across any + // instructions. This converts currently live regs into live ins/outs. + TopRPTracker.closeTop(); + BotRPTracker.closeBottom(); + + // Account for liveness generated by the region boundary. + if (LiveRegionEnd != RegionEnd) + BotRPTracker.recede(); + + assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom"); } /// schedule - Called back from MachineScheduler::runOnMachineFunction /// after setting up the current scheduling region. [RegionBegin, RegionEnd) /// only includes instructions that have DAG nodes, not scheduling boundaries. void ScheduleDAGMI::schedule() { - while(RPTracker.getPos() != RegionEnd) { - bool Moved = RPTracker.recede(); - assert(Moved && "Regpressure tracker cannot find RegionEnd"); (void)Moved; - } + // Initialize the register pressure tracker used by buildSchedGraph. + RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); + + // Account for liveness generate by the region boundary. + if (LiveRegionEnd != RegionEnd) + RPTracker.recede(); - // Build the DAG. + // Build the DAG, and compute current register pressure. buildSchedGraph(AA, &RPTracker); + // Initialize top/bottom trackers after computing region pressure. + initRegPressure(); + DEBUG(dbgs() << "********** MI Scheduling **********\n"); DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) SUnits[su].dumpAll(this)); @@ -517,6 +569,11 @@ void ScheduleDAGMI::schedule() { CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); else moveInstruction(MI, CurrentTop); + + // Update top scheduled pressure. + TopRPTracker.advance(); + assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); + // Release dependent instructions for scheduling. releaseSuccessors(SU); } @@ -532,6 +589,10 @@ void ScheduleDAGMI::schedule() { moveInstruction(MI, CurrentBottom); CurrentBottom = MI; } + // Update bottom scheduled pressure. + BotRPTracker.recede(); + assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); + // Release dependent instructions for scheduling. releasePredecessors(SU); } diff --git a/lib/CodeGen/RegisterPressure.cpp b/lib/CodeGen/RegisterPressure.cpp index 657d066405..7b86899b17 100644 --- a/lib/CodeGen/RegisterPressure.cpp +++ b/lib/CodeGen/RegisterPressure.cpp @@ -337,6 +337,22 @@ static void collectOperands(const MachineInstr *MI, } } +/// Force liveness of registers. +void RegPressureTracker::addLiveRegs(ArrayRef Regs) { + for (unsigned i = 0, e = Regs.size(); i != e; ++i) { + if (TargetRegisterInfo::isVirtualRegister(Regs[i])) { + if (LiveVirtRegs.insert(Regs[i]).second) + increaseVirtRegPressure(Regs[i]); + } + else { + if (!hasRegAlias(Regs[i], LivePhysRegs, TRI)) { + LivePhysRegs.insert(Regs[i]); + increasePhysRegPressure(Regs[i]); + } + } + } +} + /// Add PhysReg to the live in set and increase max pressure. void RegPressureTracker::discoverPhysLiveIn(unsigned Reg) { assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice"); @@ -607,28 +623,14 @@ getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta) { decreaseVirtRegPressure(VirtRegOpers.DeadDefs); // Kill liveness at live defs. - // TODO: consider earlyclobbers? - for (unsigned i = 0; i < PhysRegOpers.Defs.size(); ++i) { - unsigned Reg = PhysRegOpers.Defs[i]; - if (LivePhysRegs.erase(Reg)) - decreasePhysRegPressure(Reg); - else - discoverPhysLiveOut(Reg); - } - for (unsigned i = 0; i < VirtRegOpers.Defs.size(); ++i) { - unsigned Reg = VirtRegOpers.Defs[i]; - if (LiveVirtRegs.erase(Reg)) - decreaseVirtRegPressure(Reg); - else - discoverVirtLiveOut(Reg); - } + decreasePhysRegPressure(PhysRegOpers.Defs); + decreaseVirtRegPressure(VirtRegOpers.Defs); // Generate liveness for uses. for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) { unsigned Reg = PhysRegOpers.Uses[i]; if (!hasRegAlias(Reg, LivePhysRegs, TRI)) { increasePhysRegPressure(Reg); - LivePhysRegs.insert(Reg); } } for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) { diff --git a/lib/CodeGen/RegisterPressure.h b/lib/CodeGen/RegisterPressure.h index 93bb85a435..e4a27176b4 100644 --- a/lib/CodeGen/RegisterPressure.h +++ b/lib/CodeGen/RegisterPressure.h @@ -159,9 +159,19 @@ public: const LiveIntervals *lis, const MachineBasicBlock *mbb, MachineBasicBlock::const_iterator pos); - // Get the MI position corresponding to this register pressure. + /// Force liveness of registers. Particularly useful to initialize the + /// livein/out state of the tracker before the first call to advance/recede. + void addLiveRegs(ArrayRef Regs); + + /// Get the MI position corresponding to this register pressure. MachineBasicBlock::const_iterator getPos() const { return CurrPos; } + // Reset the MI position corresponding to the register pressure. This allows + // schedulers to move instructions above the RegPressureTracker's + // CurrPos. Since the pressure is computed before CurrPos, the iterator + // position changes while pressure does not. + void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } + /// Recede across the previous instruction. bool recede(); @@ -176,6 +186,18 @@ public: /// or if closeRegion() was explicitly invoked. RegisterPressure &getPressure() { return P; } + void discoverPhysLiveIn(unsigned Reg); + void discoverPhysLiveOut(unsigned Reg); + + void discoverVirtLiveIn(unsigned Reg); + void discoverVirtLiveOut(unsigned Reg); + + bool isTopClosed() const; + bool isBottomClosed() const; + + void closeTop(); + void closeBottom(); + /// Consider the pressure increase caused by traversing this instruction /// bottom-up. Find the pressure set with the most change beyond its pressure /// limit based on the tracker's current pressure, and record the number of @@ -201,23 +223,11 @@ public: } protected: - bool isTopClosed() const; - bool isBottomClosed() const; - - void closeTop(); - void closeBottom(); - void increasePhysRegPressure(ArrayRef Regs); void decreasePhysRegPressure(ArrayRef Regs); void increaseVirtRegPressure(ArrayRef Regs); void decreaseVirtRegPressure(ArrayRef Regs); - - void discoverPhysLiveIn(unsigned Reg); - void discoverPhysLiveOut(unsigned Reg); - - void discoverVirtLiveIn(unsigned Reg); - void discoverVirtLiveOut(unsigned Reg); }; } // end namespace llvm -- cgit v1.2.3