X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterPressure.cpp;h=f33dc3e10492d4a29b579785efe997844e876da8;hb=92da4c5cb5e293890b919511ea60a97b8e4e8679;hp=b30f76d05da645d26e28844e24084b638fd5a18c;hpb=73a0d8ecf838a9b333c9865d2a4b72c5768fb49f;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterPressure.cpp b/lib/CodeGen/RegisterPressure.cpp index b30f76d05da..f33dc3e1049 100644 --- a/lib/CodeGen/RegisterPressure.cpp +++ b/lib/CodeGen/RegisterPressure.cpp @@ -12,83 +12,101 @@ // //===----------------------------------------------------------------------===// -#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/Target/TargetMachine.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.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) { - CurrSetPressure[*PSet] += Weight; - if (&CurrSetPressure != &MaxSetPressure - && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) { - MaxSetPressure[*PSet] = CurrSetPressure[*PSet]; - } - } + PSetIterator PSetI) { + unsigned Weight = PSetI.getWeight(); + for (; PSetI.isValid(); ++PSetI) + CurrSetPressure[*PSetI] += Weight; } -/// 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) { - assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow"); - CurrSetPressure[*PSet] -= Weight; + PSetIterator PSetI) { + unsigned Weight = PSetI.getWeight(); + for (; PSetI.isValid(); ++PSetI) { + assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"); + CurrSetPressure[*PSetI] -= Weight; } } -/// Directly increase pressure only within this RegisterPressure result. -void RegisterPressure::increase(const TargetRegisterClass *RC, - const TargetRegisterInfo *TRI) { - increaseSetPressure(MaxSetPressure, MaxSetPressure, RC, TRI); -} - -/// 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); -} - -/// 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); +LLVM_DUMP_METHOD +void llvm::dumpRegSetPressure(ArrayRef SetPressure, + const TargetRegisterInfo *TRI) { + bool Empty = true; + for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) { + if (SetPressure[i] != 0) { + dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n'; + Empty = false; + } + } + if (Empty) + dbgs() << "\n"; +} + +LLVM_DUMP_METHOD +void RegisterPressure::dump(const TargetRegisterInfo *TRI) const { + dbgs() << "Max Pressure: "; + dumpRegSetPressure(MaxSetPressure, TRI); + dbgs() << "Live In: "; + for (unsigned Reg : LiveInRegs) + dbgs() << PrintVRegOrUnit(Reg, TRI) << " "; + dbgs() << '\n'; + dbgs() << "Live Out: "; + for (unsigned Reg : LiveOutRegs) + dbgs() << PrintVRegOrUnit(Reg, TRI) << " "; + dbgs() << '\n'; +} + +LLVM_DUMP_METHOD +void RegPressureTracker::dump() const { + if (!isTopClosed() || !isBottomClosed()) { + dbgs() << "Curr Pressure: "; + dumpRegSetPressure(CurrSetPressure, TRI); + } + P.dump(TRI); } -/// 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 PressureDiff::dump(const TargetRegisterInfo &TRI) const { + const char *sep = ""; + for (const PressureChange &Change : *this) { + if (!Change.isValid()) + break; + dbgs() << sep << TRI.getRegPressureSetName(Change.getPSet()) + << " " << Change.getUnitInc(); + sep = " "; + } + dbgs() << '\n'; +} + +/// Increase the current pressure as impacted by these registers and bump +/// the high water mark if needed. +void RegPressureTracker::increaseRegPressure(ArrayRef RegUnits) { + for (unsigned RegUnit : RegUnits) { + PSetIterator PSetI = MRI->getPressureSets(RegUnit); + unsigned Weight = PSetI.getWeight(); + for (; PSetI.isValid(); ++PSetI) { + CurrSetPressure[*PSetI] += Weight; + P.MaxSetPressure[*PSetI] = + std::max(P.MaxSetPressure[*PSetI], CurrSetPressure[*PSetI]); + } + } } -/// 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 RegUnits) { + for (unsigned RegUnit : RegUnits) + decreaseSetPressure(CurrSetPressure, MRI->getPressureSets(RegUnit)); } /// Clear the result so it can be used for another round of pressure tracking. @@ -140,6 +158,41 @@ void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) { LiveInRegs.clear(); } +void LiveRegSet::init(const MachineRegisterInfo &MRI) { + const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); + unsigned NumRegUnits = TRI.getNumRegs(); + unsigned NumVirtRegs = MRI.getNumVirtRegs(); + Regs.setUniverse(NumRegUnits + NumVirtRegs); + this->NumRegUnits = NumRegUnits; +} + +void LiveRegSet::clear() { + Regs.clear(); +} + +static const LiveRange *getLiveRange(const LiveIntervals &LIS, unsigned Reg) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) + return &LIS.getInterval(Reg); + return LIS.getCachedRegUnit(Reg); +} + +void RegPressureTracker::reset() { + MBB = nullptr; + LIS = nullptr; + + CurrSetPressure.clear(); + LiveThruPressure.clear(); + P.MaxSetPressure.clear(); + + if (RequireIntervals) + static_cast(P).reset(); + else + static_cast(P).reset(); + + LiveRegs.clear(); + UntiedDefs.clear(); +} + /// Setup the RegPressureTracker. /// /// TODO: Add support for pressure without LiveIntervals. @@ -147,13 +200,17 @@ void RegPressureTracker::init(const MachineFunction *mf, const RegisterClassInfo *rci, const LiveIntervals *lis, const MachineBasicBlock *mbb, - MachineBasicBlock::const_iterator pos) + MachineBasicBlock::const_iterator pos, + bool ShouldTrackUntiedDefs) { + reset(); + MF = mf; - TRI = MF->getTarget().getRegisterInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); RCI = rci; MRI = &MF->getRegInfo(); MBB = mbb; + TrackUntiedDefs = ShouldTrackUntiedDefs; if (RequireIntervals) { assert(lis && "IntervalPressure requires LiveIntervals"); @@ -161,21 +218,13 @@ void RegPressureTracker::init(const MachineFunction *mf, } CurrPos = pos; - while (CurrPos != MBB->end() && CurrPos->isDebugValue()) - ++CurrPos; - CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0); - if (RequireIntervals) - static_cast(P).reset(); - else - static_cast(P).reset(); P.MaxSetPressure = CurrSetPressure; - LivePhysRegs.clear(); - LivePhysRegs.setUniverse(TRI->getNumRegs()); - LiveVirtRegs.clear(); - LiveVirtRegs.setUniverse(MRI->getNumVirtRegs()); + LiveRegs.init(*MRI); + if (TrackUntiedDefs) + UntiedDefs.setUniverse(MRI->getNumVirtRegs()); } /// Does this pressure result have a valid top position and live ins. @@ -194,52 +243,44 @@ 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()); - for (SparseSet::const_iterator I = - LiveVirtRegs.begin(), E = LiveVirtRegs.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()), - P.LiveInRegs.end()); + P.LiveInRegs.reserve(LiveRegs.size()); + LiveRegs.appendTo(P.LiveInRegs); } /// 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()); - for (SparseSet::const_iterator I = - LiveVirtRegs.begin(), E = LiveVirtRegs.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()), - P.LiveOutRegs.end()); + P.LiveOutRegs.reserve(LiveRegs.size()); + LiveRegs.appendTo(P.LiveOutRegs); } /// Finalize the region boundaries and record live ins and live outs. void RegPressureTracker::closeRegion() { if (!isTopClosed() && !isBottomClosed()) { - assert(LivePhysRegs.empty() && LiveVirtRegs.empty() && - "no region boundary"); + assert(LiveRegs.size() == 0 && "no region boundary"); return; } if (!isBottomClosed()) @@ -249,163 +290,264 @@ 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; +/// The register tracker is unaware of global liveness so ignores normal +/// live-thru ranges. However, two-address or coalesced chains can also lead +/// to live ranges with no holes. Count these to inform heuristics that we +/// can never drop below this pressure. +void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) { + LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0); + assert(isBottomClosed() && "need bottom-up tracking to intialize."); + for (unsigned Reg : P.LiveOutRegs) { + if (TargetRegisterInfo::isVirtualRegister(Reg) + && !RPTracker.hasUntiedDef(Reg)) { + increaseSetPressure(LiveThruPressure, MRI->getPressureSets(Reg)); + } } - 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(); +/// \brief Convenient wrapper for checking membership in RegisterOperands. +/// (std::count() doesn't have an early exit). +static bool containsReg(ArrayRef RegUnits, unsigned RegUnit) { + return std::find(RegUnits.begin(), RegUnits.end(), RegUnit) != RegUnits.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); -} +namespace { /// Collect this instruction's unique uses and defs into SmallVectors for /// processing defs and uses in order. -template -struct RegisterOperands { - SmallVector Uses; - SmallVector Defs; - SmallVector DeadDefs; - - /// 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()); - } +/// +/// FIXME: always ignore tied opers +class RegisterOperandsCollector { + RegisterOperands &RegOpers; + const TargetRegisterInfo &TRI; + const MachineRegisterInfo &MRI; + bool IgnoreDead; + + RegisterOperandsCollector(RegisterOperands &RegOpers, + const TargetRegisterInfo &TRI, + const MachineRegisterInfo &MRI, + bool IgnoreDead) + : RegOpers(RegOpers), TRI(TRI), MRI(MRI), IgnoreDead(IgnoreDead) {} + + void collectInstr(const MachineInstr &MI) const { + for (ConstMIBundleOperands OperI(&MI); OperI.isValid(); ++OperI) + collectOperand(*OperI); + + // Remove redundant physreg dead defs. + 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()); + } + + /// Push this operand's register onto the correct vectors. + void collectOperand(const MachineOperand &MO) const { + if (!MO.isReg() || !MO.getReg()) + return; + unsigned Reg = MO.getReg(); + if (MO.readsReg()) + pushRegUnits(Reg, RegOpers.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 (!IgnoreDead) + pushRegUnits(Reg, RegOpers.DeadDefs); + } else + pushRegUnits(Reg, RegOpers.Defs); + } + } + + void pushRegUnits(unsigned Reg, SmallVectorImpl &RegUnits) const { + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + if (containsReg(RegUnits, Reg)) + return; + RegUnits.push_back(Reg); + } else if (MRI.isAllocatable(Reg)) { + for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) { + if (containsReg(RegUnits, *Units)) + continue; + RegUnits.push_back(*Units); } } } + + friend class llvm::RegisterOperands; }; -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; - if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) - VirtRegOpers.collect(MO, TRI); - else if (RCI->isAllocatable(MO.getReg())) - PhysRegOpers.collect(MO, TRI); +} // namespace + +void RegisterOperands::collect(const MachineInstr &MI, + const TargetRegisterInfo &TRI, + const MachineRegisterInfo &MRI, + bool IgnoreDead) { + RegisterOperandsCollector Collector(*this, TRI, MRI, IgnoreDead); + Collector.collectInstr(MI); +} + +void RegisterOperands::detectDeadDefs(const MachineInstr &MI, + const LiveIntervals &LIS) { + SlotIndex SlotIdx = LIS.getInstructionIndex(&MI); + for (SmallVectorImpl::iterator RI = Defs.begin(); + RI != Defs.end(); /*empty*/) { + unsigned Reg = *RI; + const LiveRange *LR = getLiveRange(LIS, Reg); + if (LR != nullptr) { + LiveQueryResult LRQ = LR->Query(SlotIdx); + if (LRQ.isDeadDef()) { + // LiveIntervals knows this is a dead even though it's MachineOperand is + // not flagged as such. + DeadDefs.push_back(Reg); + RI = Defs.erase(RI); + continue; + } + } + ++RI; + } +} + +/// Initialize an array of N PressureDiffs. +void PressureDiffs::init(unsigned N) { + Size = N; + if (N <= Max) { + memset(PDiffArray, 0, N * sizeof(PressureDiff)); + return; } - // 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]); + Max = Size; + free(PDiffArray); + PDiffArray = reinterpret_cast(calloc(N, sizeof(PressureDiff))); +} + +void PressureDiffs::addInstruction(unsigned Idx, + const RegisterOperands &RegOpers, + const MachineRegisterInfo &MRI) { + PressureDiff &PDiff = (*this)[Idx]; + assert(!PDiff.begin()->isValid() && "stale PDiff"); + for (unsigned Reg : RegOpers.Defs) + PDiff.addPressureChange(Reg, true, &MRI); + + for (unsigned Reg : RegOpers.Uses) + PDiff.addPressureChange(Reg, false, &MRI); +} + +/// Add a change in pressure to the pressure diff of a given instruction. +void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec, + const MachineRegisterInfo *MRI) { + PSetIterator PSetI = MRI->getPressureSets(RegUnit); + int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight(); + for (; PSetI.isValid(); ++PSetI) { + // Find an existing entry in the pressure diff for this PSet. + PressureDiff::iterator I = nonconst_begin(), E = nonconst_end(); + for (; I != E && I->isValid(); ++I) { + if (I->getPSet() >= *PSetI) + break; + } + // If all pressure sets are more constrained, skip the remaining PSets. + if (I == E) + break; + // Insert this PressureChange. + if (!I->isValid() || I->getPSet() != *PSetI) { + PressureChange PTmp = PressureChange(*PSetI); + for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J) + std::swap(*J, PTmp); + } + // Update the units for this pressure set. + unsigned NewUnitInc = I->getUnitInc() + Weight; + if (NewUnitInc != 0) { + I->setUnitInc(NewUnitInc); + } else { + // Remove entry + PressureDiff::iterator J; + for (J = std::next(I); J != E && J->isValid(); ++J, ++I) + *I = *J; + if (J != E) + *I = *J; + } } } /// 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]); - } - } + for (unsigned Reg : Regs) { + if (LiveRegs.insert(Reg)) + increaseRegPressure(Reg); } } -/// 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); + increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); } -/// 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); + increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); } -/// 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; +/// Recede across the previous instruction. If LiveUses is provided, record any +/// RegUnits that are made live by the current instruction's uses. This includes +/// registers that are both defined and used by the instruction. If a pressure +/// difference pointer is provided record the changes is pressure caused by this +/// instruction independent of liveness. +void RegPressureTracker::recede(const RegisterOperands &RegOpers, + SmallVectorImpl *LiveUses) { + assert(!CurrPos->isDebugValue()); - // At live in discovery, unconditionally increase the high water mark. - P.LiveInRegs.push_back(Reg); - P.increase(MRI->getRegClass(Reg), TRI); -} + // Boost pressure for all dead defs together. + increaseRegPressure(RegOpers.DeadDefs); + decreaseRegPressure(RegOpers.DeadDefs); -/// 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; + // Kill liveness at live defs. + // TODO: consider earlyclobbers? + for (unsigned Reg : RegOpers.Defs) { + if (LiveRegs.erase(Reg)) + decreaseRegPressure(Reg); + else + discoverLiveOut(Reg); + } - // At live out discovery, unconditionally increase the high water mark. - P.LiveOutRegs.push_back(Reg); - P.increase(MRI->getRegClass(Reg), TRI); -} + SlotIndex SlotIdx; + if (RequireIntervals) + SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); -/// Recede across the previous instruction. -bool RegPressureTracker::recede() { - // Check for the top of the analyzable region. - if (CurrPos == MBB->begin()) { - closeRegion(); - return false; + // Generate liveness for uses. + for (unsigned Reg : RegOpers.Uses) { + if (!LiveRegs.contains(Reg)) { + // Adjust liveouts if LiveIntervals are available. + if (RequireIntervals) { + const LiveRange *LR = getLiveRange(*LIS, Reg); + if (LR) { + LiveQueryResult LRQ = LR->Query(SlotIdx); + if (!LRQ.isKill() && !LRQ.valueDefined()) + discoverLiveOut(Reg); + } + } + increaseRegPressure(Reg); + LiveRegs.insert(Reg); + if (LiveUses && !containsReg(*LiveUses, Reg)) + LiveUses->push_back(Reg); + } + } + if (TrackUntiedDefs) { + for (unsigned Reg : RegOpers.Defs) { + if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg)) + UntiedDefs.insert(Reg); + } } +} + +void RegPressureTracker::recedeSkipDebugValues() { + assert(CurrPos != MBB->begin()); if (!isBottomClosed()) closeBottom(); @@ -418,10 +560,6 @@ bool RegPressureTracker::recede() { --CurrPos; while (CurrPos != MBB->begin() && CurrPos->isDebugValue()); - if (CurrPos->isDebugValue()) { - closeRegion(); - return false; - } SlotIndex SlotIdx; if (RequireIntervals) SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); @@ -429,71 +567,31 @@ bool RegPressureTracker::recede() { // Open the top of the region using slot indexes. if (RequireIntervals && isTopClosed()) static_cast(P).openTop(SlotIdx); +} - PhysRegOperands PhysRegOpers; - VirtRegOperands VirtRegOpers; - collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI); - - // Boost pressure for all dead defs together. - increasePhysRegPressure(PhysRegOpers.DeadDefs); - increaseVirtRegPressure(VirtRegOpers.DeadDefs); - decreasePhysRegPressure(PhysRegOpers.DeadDefs); - decreaseVirtRegPressure(VirtRegOpers.DeadDefs); +void RegPressureTracker::recede(SmallVectorImpl *LiveUses) { + recedeSkipDebugValues(); - // 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); - else - discoverVirtLiveOut(Reg); - } + const MachineInstr &MI = *CurrPos; + RegisterOperands RegOpers; + RegOpers.collect(MI, *TRI, *MRI); + if (RequireIntervals) + RegOpers.detectDeadDefs(MI, *LIS); - // 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)) { - // Adjust liveouts if LiveIntervals are available. - if (RequireIntervals) { - const LiveInterval *LI = &LIS->getInterval(Reg); - if (!LI->killedAt(SlotIdx)) - discoverVirtLiveOut(Reg); - } - increaseVirtRegPressure(Reg); - LiveVirtRegs.insert(Reg); - } - } - return true; + recede(RegOpers, LiveUses); } /// Advance across the current instruction. -bool RegPressureTracker::advance() { - // Check for the bottom of the analyzable region. - if (CurrPos == MBB->end()) { - closeRegion(); - return false; - } +void RegPressureTracker::advance() { + assert(!TrackUntiedDefs && "unsupported mode"); + + assert(CurrPos != MBB->end()); if (!isTopClosed()) closeTop(); SlotIndex SlotIdx; if (RequireIntervals) - SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); + SlotIdx = getCurrSlot(); // Open the bottom of the region using slot indexes. if (isBottomClosed()) { @@ -503,72 +601,53 @@ 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; + RegOpers.collect(*CurrPos, *TRI, *MRI); + + for (unsigned Reg : RegOpers.Uses) { + // 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); - } - } - else if (!LiveVirtRegs.count(Reg)) { - discoverVirtLiveIn(Reg); - increaseVirtRegPressure(Reg); + const LiveRange *LR = getLiveRange(*LIS, Reg); + lastUse = LR && LR->Query(SlotIdx).isKill(); + } 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 Reg : RegOpers.Defs) { + 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 ++CurrPos; while (CurrPos != MBB->end() && CurrPos->isDebugValue()); - return true; } /// 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; + const RegisterClassInfo *RCI, + ArrayRef LiveThruPressureVec) { + Delta.Excess = PressureChange(); for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) { unsigned POld = OldPressureVec[i]; unsigned PNew = NewPressureVec[i]; @@ -576,23 +655,24 @@ static void computeExcessPressureDelta(ArrayRef OldPressureVec, if (!PDiff) // No change in this set in the common case. continue; // Only consider change beyond the limit. - unsigned Limit = TRI->getRegPressureSetLimit(i); + unsigned Limit = RCI->getRegPressureSetLimit(i); + if (!LiveThruPressureVec.empty()) + Limit += LiveThruPressureVec[i]; + if (Limit > POld) { if (Limit > PNew) PDiff = 0; // Under the limit else PDiff = PNew - Limit; // Just exceeded limit. - } - else if (Limit > PNew) + } else if (Limit > PNew) PDiff = Limit - POld; // Just obeyed limit. - if (std::abs(PDiff) > std::abs(ExcessUnits)) { - ExcessUnits = PDiff; - PSetID = i; + if (PDiff) { + Delta.Excess = PressureChange(i); + Delta.Excess.setUnitInc(PDiff); + break; } } - Delta.Excess.PSetID = PSetID; - Delta.Excess.UnitIncrease = ExcessUnits; } /// Find the max change in max pressure that either surpasses a critical PSet @@ -603,11 +683,11 @@ static void computeExcessPressureDelta(ArrayRef OldPressureVec, /// RegPressureTracker API change to work with pressure differences. static void computeMaxPressureDelta(ArrayRef OldMaxPressureVec, ArrayRef NewMaxPressureVec, - ArrayRef CriticalPSets, + ArrayRef CriticalPSets, ArrayRef MaxPressureLimit, RegPressureDelta &Delta) { - Delta.CriticalMax = PressureElement(); - Delta.CurrentMax = PressureElement(); + Delta.CriticalMax = PressureChange(); + Delta.CurrentMax = PressureChange(); unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) { @@ -616,27 +696,57 @@ static void computeMaxPressureDelta(ArrayRef OldMaxPressureVec, if (PNew == POld) // No change in this set in the common case. continue; - while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i) - ++CritIdx; + if (!Delta.CriticalMax.isValid()) { + while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < 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; + if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) { + int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc(); + if (PDiff > 0) { + Delta.CriticalMax = PressureChange(i); + Delta.CriticalMax.setUnitInc(PDiff); + } } } - - // Find the greatest increase above MaxPressureLimit. + // Find the first 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; + if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) { + Delta.CurrentMax = PressureChange(i); + Delta.CurrentMax.setUnitInc(PNew - POld); + if (CritIdx == CritEnd || Delta.CriticalMax.isValid()) + break; } } } +/// 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; + RegOpers.collect(*MI, *TRI, *MRI, /*IgnoreDead=*/true); + assert(RegOpers.DeadDefs.size() == 0); + if (RequireIntervals) + RegOpers.detectDeadDefs(*MI, *LIS); + + // Kill liveness at live defs. + for (unsigned Reg : RegOpers.Defs) { + if (!containsReg(RegOpers.Uses, Reg)) + decreaseRegPressure(Reg); + } + // Generate liveness for uses. + for (unsigned Reg : RegOpers.Uses) { + if (!LiveRegs.contains(Reg)) + increaseRegPressure(Reg); + } +} + /// 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 return the change in @@ -645,133 +755,255 @@ static void computeMaxPressureDelta(ArrayRef OldMaxPressureVec, /// /// This assumes that the current LiveOut set is sufficient. /// -/// FIXME: This is expensive for an on-the-fly query. We need to cache the -/// result per-SUnit with enough information to adjust for the current -/// scheduling position. But this works as a proof of concept. +/// This is expensive for an on-the-fly query because it calls +/// bumpUpwardPressure to recompute the pressure sets based on current +/// liveness. This mainly exists to verify correctness, e.g. with +/// -verify-misched. getUpwardPressureDelta is the fast version of this query +/// that uses the per-SUnit cache of the PressureDiff. void RegPressureTracker:: -getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, - ArrayRef CriticalPSets, +getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, + RegPressureDelta &Delta, + ArrayRef CriticalPSets, ArrayRef MaxPressureLimit) { - // Account for register pressure similar to RegPressureTracker::recede(). - PhysRegOperands PhysRegOpers; - VirtRegOperands VirtRegOpers; - collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI); - // 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); - } - } - computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI); + computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, + LiveThruPressure); computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, MaxPressureLimit, Delta); - assert(Delta.CriticalMax.UnitIncrease >= 0 && - Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure"); + assert(Delta.CriticalMax.getUnitInc() >= 0 && + Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure"); // Restore the tracker's state. P.MaxSetPressure.swap(SavedMaxPressure); CurrSetPressure.swap(SavedPressure); + +#ifndef NDEBUG + if (!PDiff) + return; + + // Check if the alternate algorithm yields the same result. + RegPressureDelta Delta2; + getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit); + if (Delta != Delta2) { + dbgs() << "PDiff: "; + PDiff->dump(*TRI); + dbgs() << "DELTA: " << *MI; + if (Delta.Excess.isValid()) + dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet()) + << " " << Delta.Excess.getUnitInc() << "\n"; + if (Delta.CriticalMax.isValid()) + dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet()) + << " " << Delta.CriticalMax.getUnitInc() << "\n"; + if (Delta.CurrentMax.isValid()) + dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet()) + << " " << Delta.CurrentMax.getUnitInc() << "\n"; + if (Delta2.Excess.isValid()) + dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet()) + << " " << Delta2.Excess.getUnitInc() << "\n"; + if (Delta2.CriticalMax.isValid()) + dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet()) + << " " << Delta2.CriticalMax.getUnitInc() << "\n"; + if (Delta2.CurrentMax.isValid()) + dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet()) + << " " << Delta2.CurrentMax.getUnitInc() << "\n"; + llvm_unreachable("RegP Delta Mismatch"); + } +#endif +} + +/// This is the fast version of querying register pressure that does not +/// directly depend on current liveness. +/// +/// @param Delta captures information needed for heuristics. +/// +/// @param CriticalPSets Are the pressure sets that are known to exceed some +/// limit within the region, not necessarily at the current position. +/// +/// @param MaxPressureLimit Is the max pressure within the region, not +/// necessarily at the current position. +void RegPressureTracker:: +getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff, + RegPressureDelta &Delta, + ArrayRef CriticalPSets, + ArrayRef MaxPressureLimit) const { + unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); + for (PressureDiff::const_iterator + PDiffI = PDiff.begin(), PDiffE = PDiff.end(); + PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) { + + unsigned PSetID = PDiffI->getPSet(); + unsigned Limit = RCI->getRegPressureSetLimit(PSetID); + if (!LiveThruPressure.empty()) + Limit += LiveThruPressure[PSetID]; + + unsigned POld = CurrSetPressure[PSetID]; + unsigned MOld = P.MaxSetPressure[PSetID]; + unsigned MNew = MOld; + // Ignore DeadDefs here because they aren't captured by PressureChange. + unsigned PNew = POld + PDiffI->getUnitInc(); + assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld) + && "PSet overflow/underflow"); + if (PNew > MOld) + MNew = PNew; + // Check if current pressure has exceeded the limit. + if (!Delta.Excess.isValid()) { + unsigned ExcessInc = 0; + if (PNew > Limit) + ExcessInc = POld > Limit ? PNew - POld : PNew - Limit; + else if (POld > Limit) + ExcessInc = Limit - POld; + if (ExcessInc) { + Delta.Excess = PressureChange(PSetID); + Delta.Excess.setUnitInc(ExcessInc); + } + } + // Check if max pressure has exceeded a critical pressure set max. + if (MNew == MOld) + continue; + if (!Delta.CriticalMax.isValid()) { + while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID) + ++CritIdx; + + if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) { + int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc(); + if (CritInc > 0 && CritInc <= INT16_MAX) { + Delta.CriticalMax = PressureChange(PSetID); + Delta.CriticalMax.setUnitInc(CritInc); + } + } + } + // Check if max pressure has exceeded the current max. + if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) { + Delta.CurrentMax = PressureChange(PSetID); + Delta.CurrentMax.setUnitInc(MNew - MOld); + } + } } /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx). -static bool findUseBetween(unsigned Reg, - SlotIndex PriorUseIdx, SlotIndex NextUseIdx, - const MachineRegisterInfo *MRI, +static bool findUseBetween(unsigned Reg, SlotIndex PriorUseIdx, + SlotIndex NextUseIdx, const MachineRegisterInfo &MRI, const LiveIntervals *LIS) { - for (MachineRegisterInfo::use_nodbg_iterator - UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end(); - UI != UE; UI.skipInstruction()) { - const MachineInstr* MI = &*UI; - SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot(); - if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) - return true; + for (const MachineInstr &MI : MRI.use_nodbg_instructions(Reg)) { + SlotIndex InstSlot = LIS->getInstructionIndex(&MI).getRegSlot(); + if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) + return true; } return false; } +/// 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 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."); + + // Account for register pressure similar to RegPressureTracker::recede(). + RegisterOperands RegOpers; + RegOpers.collect(*MI, *TRI, *MRI); + + // Kill liveness at last uses. Assume allocatable physregs are single-use + // rather than checking LiveIntervals. + SlotIndex SlotIdx; + if (RequireIntervals) + SlotIdx = LIS->getInstructionIndex(MI).getRegSlot(); + + for (unsigned Reg : RegOpers.Uses) { + 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 LiveRange *LR = getLiveRange(*LIS, Reg); + if (LR) { + LiveQueryResult LRQ = LR->Query(SlotIdx); + if (LRQ.isKill() && !findUseBetween(Reg, CurrIdx, SlotIdx, *MRI, LIS)) + decreaseRegPressure(Reg); + } + } else if (!TargetRegisterInfo::isVirtualRegister(Reg)) { + // Allocatable physregs are always single-use before register rewriting. + decreaseRegPressure(Reg); + } + } + + // Generate liveness for defs. + increaseRegPressure(RegOpers.Defs); + + // Boost pressure for all dead defs together. + 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. +/// +/// This is expensive for an on-the-fly query because it calls +/// bumpDownwardPressure to recompute the pressure sets based on current +/// liveness. We don't yet have a fast version of downward pressure tracking +/// analogous to getUpwardPressureDelta. void RegPressureTracker:: getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, - ArrayRef CriticalPSets, + ArrayRef CriticalPSets, ArrayRef MaxPressureLimit) { - // Account for register pressure similar to RegPressureTracker::recede(). - PhysRegOperands PhysRegOpers; - VirtRegOperands VirtRegOpers; - collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI); - // Snapshot Pressure. std::vector SavedPressure = CurrSetPressure; std::vector SavedMaxPressure = P.MaxSetPressure; - // 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) - && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) { - decreaseVirtRegPressure(Reg); - } - } - } + bumpDownwardPressure(MI); - // Generate liveness for defs. - increasePhysRegPressure(PhysRegOpers.Defs); - increaseVirtRegPressure(VirtRegOpers.Defs); - - // Boost pressure for all dead defs together. - increasePhysRegPressure(PhysRegOpers.DeadDefs); - increaseVirtRegPressure(VirtRegOpers.DeadDefs); - decreasePhysRegPressure(PhysRegOpers.DeadDefs); - decreaseVirtRegPressure(VirtRegOpers.DeadDefs); - - computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI); + computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, + LiveThruPressure); computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, MaxPressureLimit, Delta); - assert(Delta.CriticalMax.UnitIncrease >= 0 && - Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure"); + assert(Delta.CriticalMax.getUnitInc() >= 0 && + Delta.CurrentMax.getUnitInc() >= 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); +}