X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterPressure.cpp;h=97f22e1049f68c1612170a48d4a4b3cbad6b0d5a;hb=aae0fa998af0f65221d7b98630162be6d88f05dc;hp=912ed0dd7b149a5bb42c6366d24e674cafef49bb;hpb=0556bd35e564c89149aa02ea8d76f539c87ee875;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterPressure.cpp b/lib/CodeGen/RegisterPressure.cpp index 912ed0dd7b1..97f22e1049f 100644 --- a/lib/CodeGen/RegisterPressure.cpp +++ b/lib/CodeGen/RegisterPressure.cpp @@ -12,23 +12,22 @@ // //===----------------------------------------------------------------------===// -#include "RegisterClassInfo.h" -#include "RegisterPressure.h" +#include "llvm/CodeGen/RegisterPressure.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetMachine.h" using namespace llvm; -/// Increase register pressure for each set impacted by this register class. +/// Increase pressure for each pressure set provided by TargetRegisterInfo. static void increaseSetPressure(std::vector &CurrSetPressure, std::vector &MaxSetPressure, - const TargetRegisterClass *RC, - const TargetRegisterInfo *TRI) { - unsigned Weight = TRI->getRegClassWeight(RC).RegWeight; - for (const int *PSet = TRI->getRegClassPressureSets(RC); - *PSet != -1; ++PSet) { + const int *PSet, unsigned Weight) { + for (; *PSet != -1; ++PSet) { CurrSetPressure[*PSet] += Weight; if (&CurrSetPressure != &MaxSetPressure && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) { @@ -37,58 +36,106 @@ static void increaseSetPressure(std::vector &CurrSetPressure, } } -/// Decrease register pressure for each set impacted by this register class. +/// Decrease pressure for each pressure set provided by TargetRegisterInfo. static void decreaseSetPressure(std::vector &CurrSetPressure, - const TargetRegisterClass *RC, - const TargetRegisterInfo *TRI) { - unsigned Weight = TRI->getRegClassWeight(RC).RegWeight; - for (const int *PSet = TRI->getRegClassPressureSets(RC); - *PSet != -1; ++PSet) { + const int *PSet, unsigned Weight) { + for (; *PSet != -1; ++PSet) { assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow"); CurrSetPressure[*PSet] -= Weight; } } /// Directly increase pressure only within this RegisterPressure result. -void RegisterPressure::increase(const TargetRegisterClass *RC, - const TargetRegisterInfo *TRI) { - increaseSetPressure(MaxSetPressure, MaxSetPressure, RC, TRI); +void RegisterPressure::increase(unsigned Reg, const TargetRegisterInfo *TRI, + const MachineRegisterInfo *MRI) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + const TargetRegisterClass *RC = MRI->getRegClass(Reg); + increaseSetPressure(MaxSetPressure, MaxSetPressure, + TRI->getRegClassPressureSets(RC), + TRI->getRegClassWeight(RC).RegWeight); + } + else { + increaseSetPressure(MaxSetPressure, MaxSetPressure, + TRI->getRegUnitPressureSets(Reg), + TRI->getRegUnitWeight(Reg)); + } } /// Directly decrease pressure only within this RegisterPressure result. -void RegisterPressure::decrease(const TargetRegisterClass *RC, - const TargetRegisterInfo *TRI) { - decreaseSetPressure(MaxSetPressure, RC, TRI); -} - -/// Increase the current pressure as impacted by these physical registers and -/// bump the high water mark if needed. -void RegPressureTracker::increasePhysRegPressure(ArrayRef Regs) { - for (unsigned I = 0, E = Regs.size(); I != E; ++I) - increaseSetPressure(CurrSetPressure, P.MaxSetPressure, - TRI->getMinimalPhysRegClass(Regs[I]), TRI); +void RegisterPressure::decrease(unsigned Reg, const TargetRegisterInfo *TRI, + const MachineRegisterInfo *MRI) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + const TargetRegisterClass *RC = MRI->getRegClass(Reg); + decreaseSetPressure(MaxSetPressure, TRI->getRegClassPressureSets(RC), + TRI->getRegClassWeight(RC).RegWeight); + } + else { + decreaseSetPressure(MaxSetPressure, TRI->getRegUnitPressureSets(Reg), + TRI->getRegUnitWeight(Reg)); + } } -/// Simply decrease the current pressure as impacted by these physcial -/// registers. -void RegPressureTracker::decreasePhysRegPressure(ArrayRef Regs) { - for (unsigned I = 0, E = Regs.size(); I != E; ++I) - decreaseSetPressure(CurrSetPressure, TRI->getMinimalPhysRegClass(Regs[I]), - TRI); +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +static void dumpSetPressure(const std::vector &SetPressure, + const TargetRegisterInfo *TRI) { + for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) { + if (SetPressure[i] != 0) + dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n'; + } } -/// Increase the current pressure as impacted by these virtual registers and -/// bump the high water mark if needed. -void RegPressureTracker::increaseVirtRegPressure(ArrayRef Regs) { - for (unsigned I = 0, E = Regs.size(); I != E; ++I) - increaseSetPressure(CurrSetPressure, P.MaxSetPressure, - MRI->getRegClass(Regs[I]), TRI); +void RegisterPressure::dump(const TargetRegisterInfo *TRI) const { + dbgs() << "Max Pressure: "; + dumpSetPressure(MaxSetPressure, TRI); + dbgs() << "Live In: "; + for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i) + dbgs() << PrintReg(LiveInRegs[i], TRI) << " "; + dbgs() << '\n'; + dbgs() << "Live Out: "; + for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i) + dbgs() << PrintReg(LiveOutRegs[i], TRI) << " "; + dbgs() << '\n'; +} + +void RegPressureTracker::dump() const { + dbgs() << "Curr Pressure: "; + dumpSetPressure(CurrSetPressure, TRI); + P.dump(TRI); +} +#endif + +/// Increase the current pressure as impacted by these registers and bump +/// the high water mark if needed. +void RegPressureTracker::increaseRegPressure(ArrayRef Regs) { + for (unsigned I = 0, E = Regs.size(); I != E; ++I) { + if (TargetRegisterInfo::isVirtualRegister(Regs[I])) { + const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]); + increaseSetPressure(CurrSetPressure, P.MaxSetPressure, + TRI->getRegClassPressureSets(RC), + TRI->getRegClassWeight(RC).RegWeight); + } + else { + increaseSetPressure(CurrSetPressure, P.MaxSetPressure, + TRI->getRegUnitPressureSets(Regs[I]), + TRI->getRegUnitWeight(Regs[I])); + } + } } -/// Simply decrease the current pressure as impacted by these virtual registers. -void RegPressureTracker::decreaseVirtRegPressure(ArrayRef Regs) { - for (unsigned I = 0, E = Regs.size(); I != E; ++I) - decreaseSetPressure(CurrSetPressure, MRI->getRegClass(Regs[I]), TRI); +/// Simply decrease the current pressure as impacted by these registers. +void RegPressureTracker::decreaseRegPressure(ArrayRef Regs) { + for (unsigned I = 0, E = Regs.size(); I != E; ++I) { + if (TargetRegisterInfo::isVirtualRegister(Regs[I])) { + const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]); + decreaseSetPressure(CurrSetPressure, + TRI->getRegClassPressureSets(RC), + TRI->getRegClassWeight(RC).RegWeight); + } + else { + decreaseSetPressure(CurrSetPressure, TRI->getRegUnitPressureSets(Regs[I]), + TRI->getRegUnitWeight(Regs[I])); + } + } } /// Clear the result so it can be used for another round of pressure tracking. @@ -140,6 +187,12 @@ void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) { LiveInRegs.clear(); } +const LiveInterval *RegPressureTracker::getInterval(unsigned Reg) const { + if (TargetRegisterInfo::isVirtualRegister(Reg)) + return &LIS->getInterval(Reg); + return LIS->getCachedRegUnit(Reg); +} + /// Setup the RegPressureTracker. /// /// TODO: Add support for pressure without LiveIntervals. @@ -161,9 +214,6 @@ void RegPressureTracker::init(const MachineFunction *mf, } CurrPos = pos; - while (CurrPos != MBB->end() && CurrPos->isDebugValue()) - ++CurrPos; - CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0); if (RequireIntervals) @@ -172,10 +222,10 @@ void RegPressureTracker::init(const MachineFunction *mf, static_cast(P).reset(); P.MaxSetPressure = CurrSetPressure; - LivePhysRegs.clear(); - LivePhysRegs.setUniverse(TRI->getNumRegs()); - LiveVirtRegs.clear(); - LiveVirtRegs.setUniverse(MRI->getNumVirtRegs()); + LiveRegs.PhysRegs.clear(); + LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs()); + LiveRegs.VirtRegs.clear(); + LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs()); } /// Does this pressure result have a valid top position and live ins. @@ -194,19 +244,28 @@ bool RegPressureTracker::isBottomClosed() const { MachineBasicBlock::const_iterator()); } + +SlotIndex RegPressureTracker::getCurrSlot() const { + MachineBasicBlock::const_iterator IdxPos = CurrPos; + while (IdxPos != MBB->end() && IdxPos->isDebugValue()) + ++IdxPos; + if (IdxPos == MBB->end()) + return LIS->getMBBEndIdx(MBB); + return LIS->getInstructionIndex(IdxPos).getRegSlot(); +} + /// Set the boundary for the top of the region and summarize live ins. void RegPressureTracker::closeTop() { if (RequireIntervals) - static_cast(P).TopIdx = - LIS->getInstructionIndex(CurrPos).getRegSlot(); + static_cast(P).TopIdx = getCurrSlot(); else static_cast(P).TopPos = CurrPos; assert(P.LiveInRegs.empty() && "inconsistent max pressure result"); - P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size()); - P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end()); + P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); + P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); for (SparseSet::const_iterator I = - LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I) + LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) P.LiveInRegs.push_back(*I); std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end()); P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()), @@ -216,19 +275,15 @@ void RegPressureTracker::closeTop() { /// Set the boundary for the bottom of the region and summarize live outs. void RegPressureTracker::closeBottom() { if (RequireIntervals) - if (CurrPos == MBB->end()) - static_cast(P).BottomIdx = LIS->getMBBEndIdx(MBB); - else - static_cast(P).BottomIdx = - LIS->getInstructionIndex(CurrPos).getRegSlot(); + static_cast(P).BottomIdx = getCurrSlot(); else static_cast(P).BottomPos = CurrPos; assert(P.LiveOutRegs.empty() && "inconsistent max pressure result"); - P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size()); - P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end()); + P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); + P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); for (SparseSet::const_iterator I = - LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I) + LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) P.LiveOutRegs.push_back(*I); std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end()); P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()), @@ -238,7 +293,7 @@ void RegPressureTracker::closeBottom() { /// Finalize the region boundaries and record live ins and live outs. void RegPressureTracker::closeRegion() { if (!isTopClosed() && !isBottomClosed()) { - assert(LivePhysRegs.empty() && LiveVirtRegs.empty() && + assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() && "no region boundary"); return; } @@ -249,154 +304,97 @@ void RegPressureTracker::closeRegion() { // If both top and bottom are closed, do nothing. } -/// Return true if Reg aliases a register in Regs SparseSet. -static bool hasRegAlias(unsigned Reg, SparseSet &Regs, - const TargetRegisterInfo *TRI) { - assert(!TargetRegisterInfo::isVirtualRegister(Reg) && "only for physregs"); - for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) { - if (Regs.count(*Alias)) - return true; - } - return false; -} - -/// Return true if Reg aliases a register in unsorted Regs SmallVector. -/// This is only valid for physical registers. -static SmallVectorImpl::iterator -findRegAlias(unsigned Reg, SmallVectorImpl &Regs, - const TargetRegisterInfo *TRI) { - for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) { - SmallVectorImpl::iterator I = - std::find(Regs.begin(), Regs.end(), *Alias); - if (I != Regs.end()) - return I; - } - return Regs.end(); -} - -/// Return true if Reg can be inserted into Regs SmallVector. For virtual -/// register, do a linear search. For physical registers check for aliases. -static SmallVectorImpl::iterator -findReg(unsigned Reg, bool isVReg, SmallVectorImpl &Regs, - const TargetRegisterInfo *TRI) { - if(isVReg) - return std::find(Regs.begin(), Regs.end(), Reg); - return findRegAlias(Reg, Regs, TRI); +/// \brief Convenient wrapper for checking membership in RegisterOperands. +static bool containsReg(ArrayRef Regs, unsigned Reg) { + return std::find(Regs.begin(), Regs.end(), Reg) != Regs.end(); } /// Collect this instruction's unique uses and defs into SmallVectors for /// processing defs and uses in order. -template -struct RegisterOperands { +class RegisterOperands { + const TargetRegisterInfo *TRI; + const MachineRegisterInfo *MRI; + +public: SmallVector Uses; SmallVector Defs; SmallVector DeadDefs; + RegisterOperands(const TargetRegisterInfo *tri, + const MachineRegisterInfo *mri): TRI(tri), MRI(mri) {} + /// Push this operand's register onto the correct vector. - void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) { - if (MO.readsReg()) { - if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end()) - Uses.push_back(MO.getReg()); - } + void collect(const MachineOperand &MO) { + if (!MO.isReg() || !MO.getReg()) + return; + if (MO.readsReg()) + pushRegUnits(MO.getReg(), Uses); if (MO.isDef()) { - if (MO.isDead()) { - if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end()) - DeadDefs.push_back(MO.getReg()); - } - else { - if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end()) - Defs.push_back(MO.getReg()); + if (MO.isDead()) + pushRegUnits(MO.getReg(), DeadDefs); + else + pushRegUnits(MO.getReg(), Defs); + } + } + +protected: + void pushRegUnits(unsigned Reg, SmallVectorImpl &Regs) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + if (containsReg(Regs, Reg)) + return; + Regs.push_back(Reg); + } + else if (MRI->isAllocatable(Reg)) { + for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { + if (containsReg(Regs, *Units)) + continue; + Regs.push_back(*Units); } } } }; -typedef RegisterOperands PhysRegOperands; -typedef RegisterOperands VirtRegOperands; /// Collect physical and virtual register operands. static void collectOperands(const MachineInstr *MI, - PhysRegOperands &PhysRegOpers, - VirtRegOperands &VirtRegOpers, - const TargetRegisterInfo *TRI, - const RegisterClassInfo *RCI) { - for(ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) { - const MachineOperand &MO = *OperI; - if (!MO.isReg() || !MO.getReg()) - continue; + RegisterOperands &RegOpers) { + for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) + RegOpers.collect(*OperI); - if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) - VirtRegOpers.collect(MO, TRI); - else if (RCI->isAllocatable(MO.getReg())) - PhysRegOpers.collect(MO, TRI); - } // Remove redundant physreg dead defs. - for (unsigned i = PhysRegOpers.DeadDefs.size(); i > 0; --i) { - unsigned Reg = PhysRegOpers.DeadDefs[i-1]; - if (findRegAlias(Reg, PhysRegOpers.Defs, TRI) != PhysRegOpers.Defs.end()) - PhysRegOpers.DeadDefs.erase(&PhysRegOpers.DeadDefs[i-1]); - } + SmallVectorImpl::iterator I = + std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(), + std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs)); + RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end()); } /// 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]); - } - } + if (LiveRegs.insert(Regs[i])) + increaseRegPressure(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"); - if (findRegAlias(Reg, P.LiveInRegs, TRI) == P.LiveInRegs.end()) +/// Add Reg to the live in set and increase max pressure. +void RegPressureTracker::discoverLiveIn(unsigned Reg) { + assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); + if (containsReg(P.LiveInRegs, Reg)) return; // At live in discovery, unconditionally increase the high water mark. P.LiveInRegs.push_back(Reg); - P.increase(TRI->getMinimalPhysRegClass(Reg), TRI); + P.increase(Reg, TRI, MRI); } -/// Add PhysReg to the live out set and increase max pressure. -void RegPressureTracker::discoverPhysLiveOut(unsigned Reg) { - assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice"); - if (findRegAlias(Reg, P.LiveOutRegs, TRI) == P.LiveOutRegs.end()) +/// Add Reg to the live out set and increase max pressure. +void RegPressureTracker::discoverLiveOut(unsigned Reg) { + assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); + if (containsReg(P.LiveOutRegs, Reg)) return; // At live out discovery, unconditionally increase the high water mark. P.LiveOutRegs.push_back(Reg); - P.increase(TRI->getMinimalPhysRegClass(Reg), TRI); -} - -/// Add VirtReg to the live in set and increase max pressure. -void RegPressureTracker::discoverVirtLiveIn(unsigned Reg) { - assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice"); - if (std::find(P.LiveInRegs.begin(), P.LiveInRegs.end(), Reg) != - P.LiveInRegs.end()) - return; - - // At live in discovery, unconditionally increase the high water mark. - P.LiveInRegs.push_back(Reg); - P.increase(MRI->getRegClass(Reg), TRI); -} - -/// Add VirtReg to the live out set and increase max pressure. -void RegPressureTracker::discoverVirtLiveOut(unsigned Reg) { - assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice"); - if (std::find(P.LiveOutRegs.begin(), P.LiveOutRegs.end(), Reg) != - P.LiveOutRegs.end()) - return; - - // At live out discovery, unconditionally increase the high water mark. - P.LiveOutRegs.push_back(Reg); - P.increase(MRI->getRegClass(Reg), TRI); + P.increase(Reg, TRI, MRI); } /// Recede across the previous instruction. @@ -430,52 +428,35 @@ bool RegPressureTracker::recede() { if (RequireIntervals && isTopClosed()) static_cast(P).openTop(SlotIdx); - PhysRegOperands PhysRegOpers; - VirtRegOperands VirtRegOpers; - collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI); + RegisterOperands RegOpers(TRI, MRI); + collectOperands(CurrPos, RegOpers); // Boost pressure for all dead defs together. - increasePhysRegPressure(PhysRegOpers.DeadDefs); - increaseVirtRegPressure(VirtRegOpers.DeadDefs); - decreasePhysRegPressure(PhysRegOpers.DeadDefs); - decreaseVirtRegPressure(VirtRegOpers.DeadDefs); + increaseRegPressure(RegOpers.DeadDefs); + decreaseRegPressure(RegOpers.DeadDefs); // Kill liveness at live defs. // TODO: consider earlyclobbers? - for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) { - unsigned Reg = PhysRegOpers.Defs[i]; - if (LivePhysRegs.erase(Reg)) - decreasePhysRegPressure(Reg); - else - discoverPhysLiveOut(Reg); - } - for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) { - unsigned Reg = VirtRegOpers.Defs[i]; - if (LiveVirtRegs.erase(Reg)) - decreaseVirtRegPressure(Reg); + for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { + unsigned Reg = RegOpers.Defs[i]; + if (LiveRegs.erase(Reg)) + decreaseRegPressure(Reg); else - discoverVirtLiveOut(Reg); + discoverLiveOut(Reg); } // 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) { - unsigned Reg = VirtRegOpers.Uses[i]; - if (!LiveVirtRegs.count(Reg)) { + for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { + unsigned Reg = RegOpers.Uses[i]; + if (!LiveRegs.contains(Reg)) { // Adjust liveouts if LiveIntervals are available. if (RequireIntervals) { - const LiveInterval *LI = &LIS->getInterval(Reg); - if (!LI->killedAt(SlotIdx)) - discoverVirtLiveOut(Reg); + const LiveInterval *LI = getInterval(Reg); + if (LI && !LI->killedAt(SlotIdx)) + discoverLiveOut(Reg); } - increaseVirtRegPressure(Reg); - LiveVirtRegs.insert(Reg); + increaseRegPressure(Reg); + LiveRegs.insert(Reg); } } return true; @@ -493,7 +474,7 @@ bool RegPressureTracker::advance() { SlotIndex SlotIdx; if (RequireIntervals) - SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); + SlotIdx = getCurrSlot(); // Open the bottom of the region using slot indexes. if (isBottomClosed()) { @@ -503,57 +484,43 @@ bool RegPressureTracker::advance() { static_cast(P).openBottom(CurrPos); } - PhysRegOperands PhysRegOpers; - VirtRegOperands VirtRegOpers; - collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI); - - // Kill liveness at last uses. - for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) { - unsigned Reg = PhysRegOpers.Uses[i]; - if (!hasRegAlias(Reg, LivePhysRegs, TRI)) - discoverPhysLiveIn(Reg); - else { - // Allocatable physregs are always single-use before regalloc. - decreasePhysRegPressure(Reg); - LivePhysRegs.erase(Reg); - } - } - for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) { - unsigned Reg = VirtRegOpers.Uses[i]; + RegisterOperands RegOpers(TRI, MRI); + collectOperands(CurrPos, RegOpers); + + for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { + unsigned Reg = RegOpers.Uses[i]; + // Discover live-ins. + bool isLive = LiveRegs.contains(Reg); + if (!isLive) + discoverLiveIn(Reg); + // Kill liveness at last uses. + bool lastUse = false; if (RequireIntervals) { - const LiveInterval *LI = &LIS->getInterval(Reg); - if (LI->killedAt(SlotIdx)) { - if (LiveVirtRegs.erase(Reg)) - decreaseVirtRegPressure(Reg); - else - discoverVirtLiveIn(Reg); - } + const LiveInterval *LI = getInterval(Reg); + lastUse = LI && LI->killedAt(SlotIdx); } - else if (!LiveVirtRegs.count(Reg)) { - discoverVirtLiveIn(Reg); - increaseVirtRegPressure(Reg); + else { + // Allocatable physregs are always single-use before register rewriting. + lastUse = !TargetRegisterInfo::isVirtualRegister(Reg); } + if (lastUse && isLive) { + LiveRegs.erase(Reg); + decreaseRegPressure(Reg); + } + else if (!lastUse && !isLive) + increaseRegPressure(Reg); } // Generate liveness for defs. - for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) { - unsigned Reg = PhysRegOpers.Defs[i]; - if (!hasRegAlias(Reg, LivePhysRegs, TRI)) { - increasePhysRegPressure(Reg); - LivePhysRegs.insert(Reg); - } - } - for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) { - unsigned Reg = VirtRegOpers.Defs[i]; - if (LiveVirtRegs.insert(Reg).second) - increaseVirtRegPressure(Reg); + for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { + unsigned Reg = RegOpers.Defs[i]; + if (LiveRegs.insert(Reg)) + increaseRegPressure(Reg); } // Boost pressure for all dead defs together. - increasePhysRegPressure(PhysRegOpers.DeadDefs); - increaseVirtRegPressure(VirtRegOpers.DeadDefs); - decreasePhysRegPressure(PhysRegOpers.DeadDefs); - decreaseVirtRegPressure(VirtRegOpers.DeadDefs); + increaseRegPressure(RegOpers.DeadDefs); + decreaseRegPressure(RegOpers.DeadDefs); // Find the next instruction. do @@ -562,12 +529,13 @@ bool RegPressureTracker::advance() { return true; } -// Find the max change in excess pressure across all sets. -static int computeMaxPressureDelta(ArrayRef OldPressureVec, - ArrayRef NewPressureVec, - unsigned &PSetID, - const TargetRegisterInfo *TRI) { +/// Find the max change in excess pressure across all sets. +static void computeExcessPressureDelta(ArrayRef OldPressureVec, + ArrayRef NewPressureVec, + RegPressureDelta &Delta, + const TargetRegisterInfo *TRI) { int ExcessUnits = 0; + unsigned PSetID = ~0U; for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) { unsigned POld = OldPressureVec[i]; unsigned PNew = NewPressureVec[i]; @@ -590,7 +558,82 @@ static int computeMaxPressureDelta(ArrayRef OldPressureVec, PSetID = i; } } - return ExcessUnits; + Delta.Excess.PSetID = PSetID; + Delta.Excess.UnitIncrease = ExcessUnits; +} + +/// Find the max change in max pressure that either surpasses a critical PSet +/// limit or exceeds the current MaxPressureLimit. +/// +/// FIXME: comparing each element of the old and new MaxPressure vectors here is +/// silly. It's done now to demonstrate the concept but will go away with a +/// RegPressureTracker API change to work with pressure differences. +static void computeMaxPressureDelta(ArrayRef OldMaxPressureVec, + ArrayRef NewMaxPressureVec, + ArrayRef CriticalPSets, + ArrayRef MaxPressureLimit, + RegPressureDelta &Delta) { + Delta.CriticalMax = PressureElement(); + Delta.CurrentMax = PressureElement(); + + unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); + for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) { + unsigned POld = OldMaxPressureVec[i]; + unsigned PNew = NewMaxPressureVec[i]; + if (PNew == POld) // No change in this set in the common case. + continue; + + while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i) + ++CritIdx; + + if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) { + int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease; + if (PDiff > Delta.CriticalMax.UnitIncrease) { + Delta.CriticalMax.PSetID = i; + Delta.CriticalMax.UnitIncrease = PDiff; + } + } + + // Find the greatest increase above MaxPressureLimit. + // (Ignores negative MDiff). + int MDiff = (int)PNew - (int)MaxPressureLimit[i]; + if (MDiff > Delta.CurrentMax.UnitIncrease) { + Delta.CurrentMax.PSetID = i; + Delta.CurrentMax.UnitIncrease = PNew; + } + } +} + +/// Record the upward impact of a single instruction on current register +/// pressure. Unlike the advance/recede pressure tracking interface, this does +/// not discover live in/outs. +/// +/// This is intended for speculative queries. It leaves pressure inconsistent +/// with the current position, so must be restored by the caller. +void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) { + assert(!MI->isDebugValue() && "Expect a nondebug instruction."); + + // Account for register pressure similar to RegPressureTracker::recede(). + RegisterOperands RegOpers(TRI, MRI); + collectOperands(MI, RegOpers); + + // Boost max pressure for all dead defs together. + // Since CurrSetPressure and MaxSetPressure + increaseRegPressure(RegOpers.DeadDefs); + decreaseRegPressure(RegOpers.DeadDefs); + + // Kill liveness at live defs. + for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { + unsigned Reg = RegOpers.Defs[i]; + if (!containsReg(RegOpers.Uses, Reg)) + decreaseRegPressure(Reg); + } + // Generate liveness for uses. + for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { + unsigned Reg = RegOpers.Uses[i]; + if (!LiveRegs.contains(Reg)) + increaseRegPressure(Reg); + } } /// Consider the pressure increase caused by traversing this instruction @@ -605,51 +648,22 @@ static int computeMaxPressureDelta(ArrayRef OldPressureVec, /// result per-SUnit with enough information to adjust for the current /// scheduling position. But this works as a proof of concept. void RegPressureTracker:: -getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta) { - // Account for register pressure similar to RegPressureTracker::recede(). - PhysRegOperands PhysRegOpers; - VirtRegOperands VirtRegOpers; - collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI); - +getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, + ArrayRef CriticalPSets, + ArrayRef MaxPressureLimit) { // Snapshot Pressure. + // FIXME: The snapshot heap space should persist. But I'm planning to + // summarize the pressure effect so we don't need to snapshot at all. std::vector SavedPressure = CurrSetPressure; std::vector SavedMaxPressure = P.MaxSetPressure; - // Boost max pressure for all dead defs together. - // Since CurrSetPressure and MaxSetPressure - increasePhysRegPressure(PhysRegOpers.DeadDefs); - increaseVirtRegPressure(VirtRegOpers.DeadDefs); - decreasePhysRegPressure(PhysRegOpers.DeadDefs); - decreaseVirtRegPressure(VirtRegOpers.DeadDefs); - - // Kill liveness at live defs. - decreasePhysRegPressure(PhysRegOpers.Defs); - decreaseVirtRegPressure(VirtRegOpers.Defs); + bumpUpwardPressure(MI); - // 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) - && (findRegAlias(Reg, PhysRegOpers.Defs, TRI) - == PhysRegOpers.Defs.end())) { - increasePhysRegPressure(Reg); - } - } - for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) { - unsigned Reg = VirtRegOpers.Uses[i]; - if (!LiveVirtRegs.count(Reg) - && (std::find(VirtRegOpers.Defs.begin(), VirtRegOpers.Defs.end(), Reg) - != VirtRegOpers.Defs.end())) { - increaseVirtRegPressure(Reg); - } - } - Delta.ExcessUnits = - computeMaxPressureDelta(SavedPressure, CurrSetPressure, - Delta.ExcessSetID, TRI); - Delta.MaxUnitIncrease = - computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, - Delta.MaxSetID, TRI); - assert(Delta.MaxUnitIncrease >= 0 && "cannot increase max pressure"); + computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI); + computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, + MaxPressureLimit, Delta); + assert(Delta.CriticalMax.UnitIncrease >= 0 && + Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure"); // Restore the tracker's state. P.MaxSetPressure.swap(SavedMaxPressure); @@ -665,6 +679,8 @@ static bool findUseBetween(unsigned Reg, UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end(); UI != UE; UI.skipInstruction()) { const MachineInstr* MI = &*UI; + if (MI->isDebugValue()) + continue; SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot(); if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) return true; @@ -672,59 +688,106 @@ static bool findUseBetween(unsigned Reg, return false; } -/// Consider the pressure increase caused by traversing this instruction -/// top-down. Find the register class with the most change in its pressure limit -/// based on the tracker's current pressure, and return the number of excess -/// register units of that pressure set introduced by this instruction. +/// Record the downward impact of a single instruction on current register +/// pressure. Unlike the advance/recede pressure tracking interface, this does +/// not discover live in/outs. /// -/// This assumes that the current LiveIn set is sufficient. -void RegPressureTracker:: -getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta) { - // Account for register pressure similar to RegPressureTracker::recede(). - PhysRegOperands PhysRegOpers; - VirtRegOperands VirtRegOpers; - collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI); +/// This is intended for speculative queries. It leaves pressure inconsistent +/// with the current position, so must be restored by the caller. +void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) { + assert(!MI->isDebugValue() && "Expect a nondebug instruction."); - // Snapshot Pressure. - std::vector SavedPressure = CurrSetPressure; - std::vector SavedMaxPressure = P.MaxSetPressure; + // Account for register pressure similar to RegPressureTracker::recede(). + RegisterOperands RegOpers(TRI, MRI); + collectOperands(MI, RegOpers); // Kill liveness at last uses. Assume allocatable physregs are single-use // rather than checking LiveIntervals. - decreasePhysRegPressure(PhysRegOpers.Uses); - if (RequireIntervals) { - SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot(); - for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) { - unsigned Reg = VirtRegOpers.Uses[i]; - const LiveInterval *LI = &LIS->getInterval(Reg); - // FIXME: allow the caller to pass in the list of vreg uses that remain to - // be bottom-scheduled to avoid searching uses at each query. - SlotIndex CurrIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); - if (LI->killedAt(SlotIdx) + SlotIndex SlotIdx; + if (RequireIntervals) + SlotIdx = LIS->getInstructionIndex(MI).getRegSlot(); + + for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { + unsigned Reg = RegOpers.Uses[i]; + if (RequireIntervals) { + // FIXME: allow the caller to pass in the list of vreg uses that remain + // to be bottom-scheduled to avoid searching uses at each query. + SlotIndex CurrIdx = getCurrSlot(); + const LiveInterval *LI = getInterval(Reg); + if (LI && LI->killedAt(SlotIdx) && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) { - decreaseVirtRegPressure(Reg); + decreaseRegPressure(Reg); } } + else if (!TargetRegisterInfo::isVirtualRegister(Reg)) { + // Allocatable physregs are always single-use before register rewriting. + decreaseRegPressure(Reg); + } } // Generate liveness for defs. - increasePhysRegPressure(PhysRegOpers.Defs); - increaseVirtRegPressure(VirtRegOpers.Defs); + increaseRegPressure(RegOpers.Defs); // Boost pressure for all dead defs together. - increasePhysRegPressure(PhysRegOpers.DeadDefs); - increaseVirtRegPressure(VirtRegOpers.DeadDefs); - decreasePhysRegPressure(PhysRegOpers.DeadDefs); - decreaseVirtRegPressure(VirtRegOpers.DeadDefs); - - Delta.ExcessUnits = - computeMaxPressureDelta(SavedPressure, CurrSetPressure, - Delta.ExcessSetID, TRI); - Delta.MaxUnitIncrease = - computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, - Delta.MaxSetID, TRI); + increaseRegPressure(RegOpers.DeadDefs); + decreaseRegPressure(RegOpers.DeadDefs); +} + +/// Consider the pressure increase caused by traversing this instruction +/// top-down. Find the register class with the most change in its pressure limit +/// based on the tracker's current pressure, and return the number of excess +/// register units of that pressure set introduced by this instruction. +/// +/// This assumes that the current LiveIn set is sufficient. +void RegPressureTracker:: +getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, + ArrayRef CriticalPSets, + ArrayRef MaxPressureLimit) { + // Snapshot Pressure. + std::vector SavedPressure = CurrSetPressure; + std::vector SavedMaxPressure = P.MaxSetPressure; + + bumpDownwardPressure(MI); + + computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI); + computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, + MaxPressureLimit, Delta); + assert(Delta.CriticalMax.UnitIncrease >= 0 && + Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure"); // Restore the tracker's state. P.MaxSetPressure.swap(SavedMaxPressure); CurrSetPressure.swap(SavedPressure); } + +/// Get the pressure of each PSet after traversing this instruction bottom-up. +void RegPressureTracker:: +getUpwardPressure(const MachineInstr *MI, + std::vector &PressureResult, + std::vector &MaxPressureResult) { + // Snapshot pressure. + PressureResult = CurrSetPressure; + MaxPressureResult = P.MaxSetPressure; + + bumpUpwardPressure(MI); + + // Current pressure becomes the result. Restore current pressure. + P.MaxSetPressure.swap(MaxPressureResult); + CurrSetPressure.swap(PressureResult); +} + +/// Get the pressure of each PSet after traversing this instruction top-down. +void RegPressureTracker:: +getDownwardPressure(const MachineInstr *MI, + std::vector &PressureResult, + std::vector &MaxPressureResult) { + // Snapshot pressure. + PressureResult = CurrSetPressure; + MaxPressureResult = P.MaxSetPressure; + + bumpDownwardPressure(MI); + + // Current pressure becomes the result. Restore current pressure. + P.MaxSetPressure.swap(MaxPressureResult); + CurrSetPressure.swap(PressureResult); +}