X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterPressure.cpp;h=ba0a9158b46c192bfa56ae2d1a630cc7b709199d;hb=324bf0ddcc8acfaba6c07415335a978ba3f0a57f;hp=1be203f36dd18b04a79e881002ee17bdbb607abd;hpb=663bd9922776e5f7bc17dfc574efe3fe05ceb12c;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterPressure.cpp b/lib/CodeGen/RegisterPressure.cpp index 1be203f36dd..ba0a9158b46 100644 --- a/lib/CodeGen/RegisterPressure.cpp +++ b/lib/CodeGen/RegisterPressure.cpp @@ -19,7 +19,6 @@ #include "llvm/CodeGen/RegisterClassInfo.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetMachine.h" using namespace llvm; @@ -41,7 +40,7 @@ static void decreaseSetPressure(std::vector &CurrSetPressure, } } -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void llvm::dumpRegSetPressure(ArrayRef SetPressure, const TargetRegisterInfo *TRI) { bool Empty = true; @@ -55,19 +54,21 @@ void llvm::dumpRegSetPressure(ArrayRef SetPressure, dbgs() << "\n"; } +LLVM_DUMP_METHOD void RegisterPressure::dump(const TargetRegisterInfo *TRI) const { dbgs() << "Max Pressure: "; dumpRegSetPressure(MaxSetPressure, TRI); dbgs() << "Live In: "; for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i) - dbgs() << PrintReg(LiveInRegs[i], TRI) << " "; + dbgs() << PrintVRegOrUnit(LiveInRegs[i], TRI) << " "; dbgs() << '\n'; dbgs() << "Live Out: "; for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i) - dbgs() << PrintReg(LiveOutRegs[i], TRI) << " "; + dbgs() << PrintVRegOrUnit(LiveOutRegs[i], TRI) << " "; dbgs() << '\n'; } +LLVM_DUMP_METHOD void RegPressureTracker::dump() const { if (!isTopClosed() || !isBottomClosed()) { dbgs() << "Curr Pressure: "; @@ -75,7 +76,16 @@ void RegPressureTracker::dump() const { } P.dump(TRI); } -#endif + +void PressureDiff::dump(const TargetRegisterInfo &TRI) const { + for (const PressureChange &Change : *this) { + if (!Change.isValid()) + break; + dbgs() << " " << TRI.getRegPressureSetName(Change.getPSet()) + << " " << Change.getUnitInc(); + } + dbgs() << '\n'; +} /// Increase the current pressure as impacted by these registers and bump /// the high water mark if needed. @@ -147,12 +157,41 @@ void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) { LiveInRegs.clear(); } -const LiveInterval *RegPressureTracker::getInterval(unsigned Reg) const { +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(); +} + +const LiveRange *RegPressureTracker::getLiveRange(unsigned Reg) const { 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. @@ -163,8 +202,10 @@ void RegPressureTracker::init(const MachineFunction *mf, MachineBasicBlock::const_iterator pos, bool ShouldTrackUntiedDefs) { + reset(); + MF = mf; - TRI = MF->getTarget().getRegisterInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); RCI = rci; MRI = &MF->getRegInfo(); MBB = mbb; @@ -177,19 +218,10 @@ void RegPressureTracker::init(const MachineFunction *mf, CurrPos = pos; CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0); - LiveThruPressure.clear(); - if (RequireIntervals) - static_cast(P).reset(); - else - static_cast(P).reset(); P.MaxSetPressure = CurrSetPressure; - LiveRegs.PhysRegs.clear(); - LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs()); - LiveRegs.VirtRegs.clear(); - LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs()); - UntiedDefs.clear(); + LiveRegs.init(*MRI); if (TrackUntiedDefs) UntiedDefs.setUniverse(MRI->getNumVirtRegs()); } @@ -228,14 +260,8 @@ void RegPressureTracker::closeTop() { static_cast(P).TopPos = CurrPos; assert(P.LiveInRegs.empty() && "inconsistent max pressure result"); - P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); - P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); - for (SparseSet::const_iterator 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()), - 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. @@ -246,21 +272,14 @@ void RegPressureTracker::closeBottom() { static_cast(P).BottomPos = CurrPos; assert(P.LiveOutRegs.empty() && "inconsistent max pressure result"); - P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); - P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); - for (SparseSet::const_iterator 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()), - 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(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() && - "no region boundary"); + assert(LiveRegs.size() == 0 && "no region boundary"); return; } if (!isBottomClosed()) @@ -292,6 +311,7 @@ static bool containsReg(ArrayRef RegUnits, unsigned RegUnit) { return std::find(RegUnits.begin(), RegUnits.end(), RegUnit) != RegUnits.end(); } +namespace { /// Collect this instruction's unique uses and defs into SmallVectors for /// processing defs and uses in order. /// @@ -342,6 +362,7 @@ protected: } } }; +} // namespace /// Collect physical and virtual register operands. static void collectOperands(const MachineInstr *MI, @@ -375,7 +396,7 @@ void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec, 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 = begin(), E = end(); + PressureDiff::iterator I = nonconst_begin(), E = nonconst_end(); for (; I != E && I->isValid(); ++I) { if (I->getPSet() >= *PSetI) break; @@ -387,10 +408,20 @@ void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec, if (!I->isValid() || I->getPSet() != *PSetI) { PressureChange PTmp = PressureChange(*PSetI); for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J) - std::swap(*J,PTmp); + std::swap(*J, PTmp); } // Update the units for this pressure set. - I->setUnitInc(I->getUnitInc() + Weight); + 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; + } } } @@ -486,10 +517,26 @@ bool RegPressureTracker::recede(SmallVectorImpl *LiveUses, // TODO: consider earlyclobbers? for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { unsigned Reg = RegOpers.Defs[i]; - if (LiveRegs.erase(Reg)) - decreaseRegPressure(Reg); - else - discoverLiveOut(Reg); + bool DeadDef = false; + if (RequireIntervals) { + const LiveRange *LR = getLiveRange(Reg); + if (LR) { + LiveQueryResult LRQ = LR->Query(SlotIdx); + DeadDef = LRQ.isDeadDef(); + } + } + if (DeadDef) { + // LiveIntervals knows this is a dead even though it's MachineOperand is + // not flagged as such. Since this register will not be recorded as + // live-out, increase its PDiff value to avoid underflowing pressure. + if (PDiff) + PDiff->addPressureChange(Reg, false, MRI); + } else { + if (LiveRegs.erase(Reg)) + decreaseRegPressure(Reg); + else + discoverLiveOut(Reg); + } } // Generate liveness for uses. @@ -498,10 +545,10 @@ bool RegPressureTracker::recede(SmallVectorImpl *LiveUses, if (!LiveRegs.contains(Reg)) { // Adjust liveouts if LiveIntervals are available. if (RequireIntervals) { - const LiveInterval *LI = getInterval(Reg); - // Check if this LR is killed and not redefined here. - if (LI && !LI->isKilledAtInstr(SlotIdx) - && !LI->isDefinedByInstr(SlotIdx)) { + const LiveRange *LR = getLiveRange(Reg); + if (LR) { + LiveQueryResult LRQ = LR->Query(SlotIdx); + if (!LRQ.isKill() && !LRQ.valueDefined()) discoverLiveOut(Reg); } } @@ -557,8 +604,8 @@ bool RegPressureTracker::advance() { // Kill liveness at last uses. bool lastUse = false; if (RequireIntervals) { - const LiveInterval *LI = getInterval(Reg); - lastUse = LI && LI->isKilledAtInstr(SlotIdx); + const LiveRange *LR = getLiveRange(Reg); + lastUse = LR && LR->Query(SlotIdx).isKill(); } else { // Allocatable physregs are always single-use before register rewriting. @@ -690,8 +737,19 @@ void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) { // 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); + bool DeadDef = false; + if (RequireIntervals) { + const LiveRange *LR = getLiveRange(Reg); + if (LR) { + SlotIndex SlotIdx = LIS->getInstructionIndex(MI); + LiveQueryResult LRQ = LR->Query(SlotIdx); + DeadDef = LRQ.isDeadDef(); + } + } + if (!DeadDef) { + if (!containsReg(RegOpers.Uses, Reg)) + decreaseRegPressure(Reg); + } } // Generate liveness for uses. for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { @@ -709,9 +767,11 @@ void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) { /// /// 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, PressureDiff *PDiff, RegPressureDelta &Delta, @@ -744,6 +804,8 @@ getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, 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()) @@ -768,10 +830,8 @@ getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, #endif } -/// This is a prototype of the fast version of querying register pressure that -/// does not directly depend on current liveness. It's still slow because we -/// recompute pressure change on-the-fly. This implementation only exists to -/// prove correctness. +/// This is the fast version of querying register pressure that does not +/// directly depend on current liveness. /// /// @param Delta captures information needed for heuristics. /// @@ -839,19 +899,13 @@ getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff, } /// 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; - if (MI->isDebugValue()) - continue; - 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; } @@ -881,10 +935,11 @@ void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) { // 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->isKilledAtInstr(SlotIdx) - && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) { - decreaseRegPressure(Reg); + const LiveRange *LR = getLiveRange(Reg); + if (LR) { + LiveQueryResult LRQ = LR->Query(SlotIdx); + if (LRQ.isKill() && !findUseBetween(Reg, CurrIdx, SlotIdx, *MRI, LIS)) + decreaseRegPressure(Reg); } } else if (!TargetRegisterInfo::isVirtualRegister(Reg)) { @@ -907,6 +962,11 @@ void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) { /// 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,