1 //===-- RegisterPressure.cpp - Dynamic Register Pressure ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the RegisterPressure class which can be used to track
11 // MachineInstr level register pressure.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/CodeGen/RegisterPressure.h"
16 #include "llvm/CodeGen/LiveInterval.h"
17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/CodeGen/RegisterClassInfo.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include "llvm/Target/TargetMachine.h"
26 /// Increase pressure for each pressure set provided by TargetRegisterInfo.
27 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
28 std::vector<unsigned> &MaxSetPressure,
29 const int *PSet, unsigned Weight) {
30 for (; *PSet != -1; ++PSet) {
31 CurrSetPressure[*PSet] += Weight;
32 if (&CurrSetPressure != &MaxSetPressure
33 && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) {
34 MaxSetPressure[*PSet] = CurrSetPressure[*PSet];
39 /// Decrease pressure for each pressure set provided by TargetRegisterInfo.
40 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
41 const int *PSet, unsigned Weight) {
42 for (; *PSet != -1; ++PSet) {
43 assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow");
44 CurrSetPressure[*PSet] -= Weight;
48 /// Directly increase pressure only within this RegisterPressure result.
49 void RegisterPressure::increase(unsigned Reg, const TargetRegisterInfo *TRI,
50 const MachineRegisterInfo *MRI) {
51 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
52 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
53 increaseSetPressure(MaxSetPressure, MaxSetPressure,
54 TRI->getRegClassPressureSets(RC),
55 TRI->getRegClassWeight(RC).RegWeight);
58 increaseSetPressure(MaxSetPressure, MaxSetPressure,
59 TRI->getRegUnitPressureSets(Reg),
60 TRI->getRegUnitWeight(Reg));
64 /// Directly decrease pressure only within this RegisterPressure result.
65 void RegisterPressure::decrease(unsigned Reg, const TargetRegisterInfo *TRI,
66 const MachineRegisterInfo *MRI) {
67 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
68 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
69 decreaseSetPressure(MaxSetPressure, TRI->getRegClassPressureSets(RC),
70 TRI->getRegClassWeight(RC).RegWeight);
73 decreaseSetPressure(MaxSetPressure, TRI->getRegUnitPressureSets(Reg),
74 TRI->getRegUnitWeight(Reg));
78 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
79 void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
80 const TargetRegisterInfo *TRI) {
82 for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
83 if (SetPressure[i] != 0) {
84 dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
92 void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
93 dbgs() << "Max Pressure: ";
94 dumpRegSetPressure(MaxSetPressure, TRI);
95 dbgs() << "Live In: ";
96 for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i)
97 dbgs() << PrintReg(LiveInRegs[i], TRI) << " ";
99 dbgs() << "Live Out: ";
100 for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i)
101 dbgs() << PrintReg(LiveOutRegs[i], TRI) << " ";
105 void RegPressureTracker::dump() const {
106 if (!isTopClosed() || !isBottomClosed()) {
107 dbgs() << "Curr Pressure: ";
108 dumpRegSetPressure(CurrSetPressure, TRI);
114 /// Increase the current pressure as impacted by these registers and bump
115 /// the high water mark if needed.
116 void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> Regs) {
117 for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
118 if (TargetRegisterInfo::isVirtualRegister(Regs[I])) {
119 const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
120 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
121 TRI->getRegClassPressureSets(RC),
122 TRI->getRegClassWeight(RC).RegWeight);
125 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
126 TRI->getRegUnitPressureSets(Regs[I]),
127 TRI->getRegUnitWeight(Regs[I]));
132 /// Simply decrease the current pressure as impacted by these registers.
133 void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> Regs) {
134 for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
135 if (TargetRegisterInfo::isVirtualRegister(Regs[I])) {
136 const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
137 decreaseSetPressure(CurrSetPressure,
138 TRI->getRegClassPressureSets(RC),
139 TRI->getRegClassWeight(RC).RegWeight);
142 decreaseSetPressure(CurrSetPressure, TRI->getRegUnitPressureSets(Regs[I]),
143 TRI->getRegUnitWeight(Regs[I]));
148 /// Clear the result so it can be used for another round of pressure tracking.
149 void IntervalPressure::reset() {
150 TopIdx = BottomIdx = SlotIndex();
151 MaxSetPressure.clear();
156 /// Clear the result so it can be used for another round of pressure tracking.
157 void RegionPressure::reset() {
158 TopPos = BottomPos = MachineBasicBlock::const_iterator();
159 MaxSetPressure.clear();
164 /// If the current top is not less than or equal to the next index, open it.
165 /// We happen to need the SlotIndex for the next top for pressure update.
166 void IntervalPressure::openTop(SlotIndex NextTop) {
167 if (TopIdx <= NextTop)
169 TopIdx = SlotIndex();
173 /// If the current top is the previous instruction (before receding), open it.
174 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
175 if (TopPos != PrevTop)
177 TopPos = MachineBasicBlock::const_iterator();
181 /// If the current bottom is not greater than the previous index, open it.
182 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
183 if (BottomIdx > PrevBottom)
185 BottomIdx = SlotIndex();
189 /// If the current bottom is the previous instr (before advancing), open it.
190 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
191 if (BottomPos != PrevBottom)
193 BottomPos = MachineBasicBlock::const_iterator();
197 const LiveInterval *RegPressureTracker::getInterval(unsigned Reg) const {
198 if (TargetRegisterInfo::isVirtualRegister(Reg))
199 return &LIS->getInterval(Reg);
200 return LIS->getCachedRegUnit(Reg);
203 /// Setup the RegPressureTracker.
205 /// TODO: Add support for pressure without LiveIntervals.
206 void RegPressureTracker::init(const MachineFunction *mf,
207 const RegisterClassInfo *rci,
208 const LiveIntervals *lis,
209 const MachineBasicBlock *mbb,
210 MachineBasicBlock::const_iterator pos,
211 bool ShouldTrackUntiedDefs)
214 TRI = MF->getTarget().getRegisterInfo();
216 MRI = &MF->getRegInfo();
218 TrackUntiedDefs = ShouldTrackUntiedDefs;
220 if (RequireIntervals) {
221 assert(lis && "IntervalPressure requires LiveIntervals");
226 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
227 LiveThruPressure.clear();
229 if (RequireIntervals)
230 static_cast<IntervalPressure&>(P).reset();
232 static_cast<RegionPressure&>(P).reset();
233 P.MaxSetPressure = CurrSetPressure;
235 LiveRegs.PhysRegs.clear();
236 LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs());
237 LiveRegs.VirtRegs.clear();
238 LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs());
241 UntiedDefs.setUniverse(MRI->getNumVirtRegs());
244 /// Does this pressure result have a valid top position and live ins.
245 bool RegPressureTracker::isTopClosed() const {
246 if (RequireIntervals)
247 return static_cast<IntervalPressure&>(P).TopIdx.isValid();
248 return (static_cast<RegionPressure&>(P).TopPos ==
249 MachineBasicBlock::const_iterator());
252 /// Does this pressure result have a valid bottom position and live outs.
253 bool RegPressureTracker::isBottomClosed() const {
254 if (RequireIntervals)
255 return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
256 return (static_cast<RegionPressure&>(P).BottomPos ==
257 MachineBasicBlock::const_iterator());
261 SlotIndex RegPressureTracker::getCurrSlot() const {
262 MachineBasicBlock::const_iterator IdxPos = CurrPos;
263 while (IdxPos != MBB->end() && IdxPos->isDebugValue())
265 if (IdxPos == MBB->end())
266 return LIS->getMBBEndIdx(MBB);
267 return LIS->getInstructionIndex(IdxPos).getRegSlot();
270 /// Set the boundary for the top of the region and summarize live ins.
271 void RegPressureTracker::closeTop() {
272 if (RequireIntervals)
273 static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
275 static_cast<RegionPressure&>(P).TopPos = CurrPos;
277 assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
278 P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
279 P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
280 for (SparseSet<unsigned>::const_iterator I =
281 LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
282 P.LiveInRegs.push_back(*I);
283 std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
284 P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
288 /// Set the boundary for the bottom of the region and summarize live outs.
289 void RegPressureTracker::closeBottom() {
290 if (RequireIntervals)
291 static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
293 static_cast<RegionPressure&>(P).BottomPos = CurrPos;
295 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
296 P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
297 P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
298 for (SparseSet<unsigned>::const_iterator I =
299 LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
300 P.LiveOutRegs.push_back(*I);
301 std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
302 P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
303 P.LiveOutRegs.end());
306 /// Finalize the region boundaries and record live ins and live outs.
307 void RegPressureTracker::closeRegion() {
308 if (!isTopClosed() && !isBottomClosed()) {
309 assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() &&
310 "no region boundary");
313 if (!isBottomClosed())
315 else if (!isTopClosed())
317 // If both top and bottom are closed, do nothing.
320 /// The register tracker is unaware of global liveness so ignores normal
321 /// live-thru ranges. However, two-address or coalesced chains can also lead
322 /// to live ranges with no holes. Count these to inform heuristics that we
323 /// can never drop below this pressure.
324 void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
325 LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
326 assert(isBottomClosed() && "need bottom-up tracking to intialize.");
327 for (unsigned i = 0, e = P.LiveOutRegs.size(); i < e; ++i) {
328 unsigned Reg = P.LiveOutRegs[i];
329 if (TargetRegisterInfo::isVirtualRegister(Reg)
330 && !RPTracker.hasUntiedDef(Reg)) {
331 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
332 increaseSetPressure(LiveThruPressure, LiveThruPressure,
333 TRI->getRegClassPressureSets(RC),
334 TRI->getRegClassWeight(RC).RegWeight);
339 /// \brief Convenient wrapper for checking membership in RegisterOperands.
340 static bool containsReg(ArrayRef<unsigned> Regs, unsigned Reg) {
341 return std::find(Regs.begin(), Regs.end(), Reg) != Regs.end();
344 /// Collect this instruction's unique uses and defs into SmallVectors for
345 /// processing defs and uses in order.
346 class RegisterOperands {
347 const TargetRegisterInfo *TRI;
348 const MachineRegisterInfo *MRI;
351 SmallVector<unsigned, 8> Uses;
352 SmallVector<unsigned, 8> Defs;
353 SmallVector<unsigned, 8> DeadDefs;
355 RegisterOperands(const TargetRegisterInfo *tri,
356 const MachineRegisterInfo *mri): TRI(tri), MRI(mri) {}
358 /// Push this operand's register onto the correct vector.
359 void collect(const MachineOperand &MO) {
360 if (!MO.isReg() || !MO.getReg())
363 pushRegUnits(MO.getReg(), Uses);
366 pushRegUnits(MO.getReg(), DeadDefs);
368 pushRegUnits(MO.getReg(), Defs);
373 void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &Regs) {
374 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
375 if (containsReg(Regs, Reg))
379 else if (MRI->isAllocatable(Reg)) {
380 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
381 if (containsReg(Regs, *Units))
383 Regs.push_back(*Units);
389 /// Collect physical and virtual register operands.
390 static void collectOperands(const MachineInstr *MI,
391 RegisterOperands &RegOpers) {
392 for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
393 RegOpers.collect(*OperI);
395 // Remove redundant physreg dead defs.
396 SmallVectorImpl<unsigned>::iterator I =
397 std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(),
398 std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs));
399 RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end());
402 /// Force liveness of registers.
403 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
404 for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
405 if (LiveRegs.insert(Regs[i]))
406 increaseRegPressure(Regs[i]);
410 /// Add Reg to the live in set and increase max pressure.
411 void RegPressureTracker::discoverLiveIn(unsigned Reg) {
412 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
413 if (containsReg(P.LiveInRegs, Reg))
416 // At live in discovery, unconditionally increase the high water mark.
417 P.LiveInRegs.push_back(Reg);
418 P.increase(Reg, TRI, MRI);
421 /// Add Reg to the live out set and increase max pressure.
422 void RegPressureTracker::discoverLiveOut(unsigned Reg) {
423 assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
424 if (containsReg(P.LiveOutRegs, Reg))
427 // At live out discovery, unconditionally increase the high water mark.
428 P.LiveOutRegs.push_back(Reg);
429 P.increase(Reg, TRI, MRI);
432 /// Recede across the previous instruction.
433 bool RegPressureTracker::recede() {
434 // Check for the top of the analyzable region.
435 if (CurrPos == MBB->begin()) {
439 if (!isBottomClosed())
442 // Open the top of the region using block iterators.
443 if (!RequireIntervals && isTopClosed())
444 static_cast<RegionPressure&>(P).openTop(CurrPos);
446 // Find the previous instruction.
449 while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
451 if (CurrPos->isDebugValue()) {
456 if (RequireIntervals)
457 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
459 // Open the top of the region using slot indexes.
460 if (RequireIntervals && isTopClosed())
461 static_cast<IntervalPressure&>(P).openTop(SlotIdx);
463 RegisterOperands RegOpers(TRI, MRI);
464 collectOperands(CurrPos, RegOpers);
466 // Boost pressure for all dead defs together.
467 increaseRegPressure(RegOpers.DeadDefs);
468 decreaseRegPressure(RegOpers.DeadDefs);
470 // Kill liveness at live defs.
471 // TODO: consider earlyclobbers?
472 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
473 unsigned Reg = RegOpers.Defs[i];
474 if (LiveRegs.erase(Reg))
475 decreaseRegPressure(Reg);
477 discoverLiveOut(Reg);
480 // Generate liveness for uses.
481 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
482 unsigned Reg = RegOpers.Uses[i];
483 if (!LiveRegs.contains(Reg)) {
484 // Adjust liveouts if LiveIntervals are available.
485 if (RequireIntervals) {
486 const LiveInterval *LI = getInterval(Reg);
487 if (LI && !LI->killedAt(SlotIdx))
488 discoverLiveOut(Reg);
490 increaseRegPressure(Reg);
491 LiveRegs.insert(Reg);
494 if (TrackUntiedDefs) {
495 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
496 unsigned Reg = RegOpers.Defs[i];
497 if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg))
498 UntiedDefs.insert(Reg);
504 /// Advance across the current instruction.
505 bool RegPressureTracker::advance() {
506 assert(!TrackUntiedDefs && "unsupported mode");
508 // Check for the bottom of the analyzable region.
509 if (CurrPos == MBB->end()) {
517 if (RequireIntervals)
518 SlotIdx = getCurrSlot();
520 // Open the bottom of the region using slot indexes.
521 if (isBottomClosed()) {
522 if (RequireIntervals)
523 static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
525 static_cast<RegionPressure&>(P).openBottom(CurrPos);
528 RegisterOperands RegOpers(TRI, MRI);
529 collectOperands(CurrPos, RegOpers);
531 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
532 unsigned Reg = RegOpers.Uses[i];
533 // Discover live-ins.
534 bool isLive = LiveRegs.contains(Reg);
537 // Kill liveness at last uses.
538 bool lastUse = false;
539 if (RequireIntervals) {
540 const LiveInterval *LI = getInterval(Reg);
541 lastUse = LI && LI->killedAt(SlotIdx);
544 // Allocatable physregs are always single-use before register rewriting.
545 lastUse = !TargetRegisterInfo::isVirtualRegister(Reg);
547 if (lastUse && isLive) {
549 decreaseRegPressure(Reg);
551 else if (!lastUse && !isLive)
552 increaseRegPressure(Reg);
555 // Generate liveness for defs.
556 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
557 unsigned Reg = RegOpers.Defs[i];
558 if (LiveRegs.insert(Reg))
559 increaseRegPressure(Reg);
562 // Boost pressure for all dead defs together.
563 increaseRegPressure(RegOpers.DeadDefs);
564 decreaseRegPressure(RegOpers.DeadDefs);
566 // Find the next instruction.
569 while (CurrPos != MBB->end() && CurrPos->isDebugValue());
573 /// Find the max change in excess pressure across all sets.
574 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
575 ArrayRef<unsigned> NewPressureVec,
576 RegPressureDelta &Delta,
577 const RegisterClassInfo *RCI,
578 ArrayRef<unsigned> LiveThruPressureVec) {
580 unsigned PSetID = ~0U;
581 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
582 unsigned POld = OldPressureVec[i];
583 unsigned PNew = NewPressureVec[i];
584 int PDiff = (int)PNew - (int)POld;
585 if (!PDiff) // No change in this set in the common case.
587 // Only consider change beyond the limit.
588 unsigned Limit = RCI->getRegPressureSetLimit(i);
589 if (!LiveThruPressureVec.empty())
590 Limit += LiveThruPressureVec[i];
594 PDiff = 0; // Under the limit
596 PDiff = PNew - Limit; // Just exceeded limit.
598 else if (Limit > PNew)
599 PDiff = Limit - POld; // Just obeyed limit.
607 Delta.Excess.PSetID = PSetID;
608 Delta.Excess.UnitIncrease = ExcessUnits;
611 /// Find the max change in max pressure that either surpasses a critical PSet
612 /// limit or exceeds the current MaxPressureLimit.
614 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
615 /// silly. It's done now to demonstrate the concept but will go away with a
616 /// RegPressureTracker API change to work with pressure differences.
617 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
618 ArrayRef<unsigned> NewMaxPressureVec,
619 ArrayRef<PressureElement> CriticalPSets,
620 ArrayRef<unsigned> MaxPressureLimit,
621 RegPressureDelta &Delta) {
622 Delta.CriticalMax = PressureElement();
623 Delta.CurrentMax = PressureElement();
625 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
626 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
627 unsigned POld = OldMaxPressureVec[i];
628 unsigned PNew = NewMaxPressureVec[i];
629 if (PNew == POld) // No change in this set in the common case.
632 if (!Delta.CriticalMax.isValid()) {
633 while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
636 if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
637 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
639 Delta.CriticalMax.PSetID = i;
640 Delta.CriticalMax.UnitIncrease = PDiff;
644 // Find the first increase above MaxPressureLimit.
645 // (Ignores negative MDiff).
646 if (!Delta.CurrentMax.isValid()) {
647 int MDiff = (int)PNew - (int)MaxPressureLimit[i];
649 Delta.CurrentMax.PSetID = i;
650 Delta.CurrentMax.UnitIncrease = MDiff;
651 if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
658 /// Record the upward impact of a single instruction on current register
659 /// pressure. Unlike the advance/recede pressure tracking interface, this does
660 /// not discover live in/outs.
662 /// This is intended for speculative queries. It leaves pressure inconsistent
663 /// with the current position, so must be restored by the caller.
664 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
665 assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
667 // Account for register pressure similar to RegPressureTracker::recede().
668 RegisterOperands RegOpers(TRI, MRI);
669 collectOperands(MI, RegOpers);
671 // Boost max pressure for all dead defs together.
672 // Since CurrSetPressure and MaxSetPressure
673 increaseRegPressure(RegOpers.DeadDefs);
674 decreaseRegPressure(RegOpers.DeadDefs);
676 // Kill liveness at live defs.
677 for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
678 unsigned Reg = RegOpers.Defs[i];
679 if (!containsReg(RegOpers.Uses, Reg))
680 decreaseRegPressure(Reg);
682 // Generate liveness for uses.
683 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
684 unsigned Reg = RegOpers.Uses[i];
685 if (!LiveRegs.contains(Reg))
686 increaseRegPressure(Reg);
690 /// Consider the pressure increase caused by traversing this instruction
691 /// bottom-up. Find the pressure set with the most change beyond its pressure
692 /// limit based on the tracker's current pressure, and return the change in
693 /// number of register units of that pressure set introduced by this
696 /// This assumes that the current LiveOut set is sufficient.
698 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
699 /// result per-SUnit with enough information to adjust for the current
700 /// scheduling position. But this works as a proof of concept.
701 void RegPressureTracker::
702 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
703 ArrayRef<PressureElement> CriticalPSets,
704 ArrayRef<unsigned> MaxPressureLimit) {
705 // Snapshot Pressure.
706 // FIXME: The snapshot heap space should persist. But I'm planning to
707 // summarize the pressure effect so we don't need to snapshot at all.
708 std::vector<unsigned> SavedPressure = CurrSetPressure;
709 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
711 bumpUpwardPressure(MI);
713 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
715 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
716 MaxPressureLimit, Delta);
717 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
718 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
720 // Restore the tracker's state.
721 P.MaxSetPressure.swap(SavedMaxPressure);
722 CurrSetPressure.swap(SavedPressure);
725 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
726 static bool findUseBetween(unsigned Reg,
727 SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
728 const MachineRegisterInfo *MRI,
729 const LiveIntervals *LIS) {
730 for (MachineRegisterInfo::use_nodbg_iterator
731 UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
732 UI != UE; UI.skipInstruction()) {
733 const MachineInstr* MI = &*UI;
734 if (MI->isDebugValue())
736 SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
737 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
743 /// Record the downward impact of a single instruction on current register
744 /// pressure. Unlike the advance/recede pressure tracking interface, this does
745 /// not discover live in/outs.
747 /// This is intended for speculative queries. It leaves pressure inconsistent
748 /// with the current position, so must be restored by the caller.
749 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
750 assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
752 // Account for register pressure similar to RegPressureTracker::recede().
753 RegisterOperands RegOpers(TRI, MRI);
754 collectOperands(MI, RegOpers);
756 // Kill liveness at last uses. Assume allocatable physregs are single-use
757 // rather than checking LiveIntervals.
759 if (RequireIntervals)
760 SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
762 for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
763 unsigned Reg = RegOpers.Uses[i];
764 if (RequireIntervals) {
765 // FIXME: allow the caller to pass in the list of vreg uses that remain
766 // to be bottom-scheduled to avoid searching uses at each query.
767 SlotIndex CurrIdx = getCurrSlot();
768 const LiveInterval *LI = getInterval(Reg);
769 if (LI && LI->killedAt(SlotIdx)
770 && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
771 decreaseRegPressure(Reg);
774 else if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
775 // Allocatable physregs are always single-use before register rewriting.
776 decreaseRegPressure(Reg);
780 // Generate liveness for defs.
781 increaseRegPressure(RegOpers.Defs);
783 // Boost pressure for all dead defs together.
784 increaseRegPressure(RegOpers.DeadDefs);
785 decreaseRegPressure(RegOpers.DeadDefs);
788 /// Consider the pressure increase caused by traversing this instruction
789 /// top-down. Find the register class with the most change in its pressure limit
790 /// based on the tracker's current pressure, and return the number of excess
791 /// register units of that pressure set introduced by this instruction.
793 /// This assumes that the current LiveIn set is sufficient.
794 void RegPressureTracker::
795 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
796 ArrayRef<PressureElement> CriticalPSets,
797 ArrayRef<unsigned> MaxPressureLimit) {
798 // Snapshot Pressure.
799 std::vector<unsigned> SavedPressure = CurrSetPressure;
800 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
802 bumpDownwardPressure(MI);
804 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
806 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
807 MaxPressureLimit, Delta);
808 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
809 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
811 // Restore the tracker's state.
812 P.MaxSetPressure.swap(SavedMaxPressure);
813 CurrSetPressure.swap(SavedPressure);
816 /// Get the pressure of each PSet after traversing this instruction bottom-up.
817 void RegPressureTracker::
818 getUpwardPressure(const MachineInstr *MI,
819 std::vector<unsigned> &PressureResult,
820 std::vector<unsigned> &MaxPressureResult) {
821 // Snapshot pressure.
822 PressureResult = CurrSetPressure;
823 MaxPressureResult = P.MaxSetPressure;
825 bumpUpwardPressure(MI);
827 // Current pressure becomes the result. Restore current pressure.
828 P.MaxSetPressure.swap(MaxPressureResult);
829 CurrSetPressure.swap(PressureResult);
832 /// Get the pressure of each PSet after traversing this instruction top-down.
833 void RegPressureTracker::
834 getDownwardPressure(const MachineInstr *MI,
835 std::vector<unsigned> &PressureResult,
836 std::vector<unsigned> &MaxPressureResult) {
837 // Snapshot pressure.
838 PressureResult = CurrSetPressure;
839 MaxPressureResult = P.MaxSetPressure;
841 bumpDownwardPressure(MI);
843 // Current pressure becomes the result. Restore current pressure.
844 P.MaxSetPressure.swap(MaxPressureResult);
845 CurrSetPressure.swap(PressureResult);