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(const TargetRegisterClass *RC,
50 const TargetRegisterInfo *TRI) {
51 increaseSetPressure(MaxSetPressure, MaxSetPressure,
52 TRI->getRegClassPressureSets(RC),
53 TRI->getRegClassWeight(RC).RegWeight);
56 /// Directly increase pressure only within this RegisterPressure result.
57 void RegisterPressure::increase(unsigned RU, const TargetRegisterInfo *TRI) {
58 increaseSetPressure(MaxSetPressure, MaxSetPressure,
59 TRI->getRegUnitPressureSets(RU),
60 TRI->getRegUnitWeight(RU));
63 /// Directly decrease pressure only within this RegisterPressure result.
64 void RegisterPressure::decrease(const TargetRegisterClass *RC,
65 const TargetRegisterInfo *TRI) {
66 decreaseSetPressure(MaxSetPressure, TRI->getRegClassPressureSets(RC),
67 TRI->getRegClassWeight(RC).RegWeight);
70 /// Directly decrease pressure only within this RegisterPressure result.
71 void RegisterPressure::decrease(unsigned RU, const TargetRegisterInfo *TRI) {
72 decreaseSetPressure(MaxSetPressure, TRI->getRegUnitPressureSets(RU),
73 TRI->getRegUnitWeight(RU));
76 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
77 static void dumpSetPressure(const std::vector<unsigned> &SetPressure,
78 const TargetRegisterInfo *TRI) {
79 for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
80 if (SetPressure[i] != 0)
81 dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
85 void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
86 dbgs() << "Max Pressure: ";
87 dumpSetPressure(MaxSetPressure, TRI);
88 dbgs() << "Live In: ";
89 for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i)
90 dbgs() << PrintReg(LiveInRegs[i], TRI) << " ";
92 dbgs() << "Live Out: ";
93 for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i)
94 dbgs() << PrintReg(LiveOutRegs[i], TRI) << " ";
98 void RegPressureTracker::dump(const TargetRegisterInfo *TRI) const {
99 dbgs() << "Curr Pressure: ";
100 dumpSetPressure(CurrSetPressure, TRI);
105 /// Increase the current pressure as impacted by these register units and bump
106 /// the high water mark if needed.
107 void RegPressureTracker::increasePhysRegPressure(ArrayRef<unsigned> Regs) {
108 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
109 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
110 TRI->getRegUnitPressureSets(Regs[I]),
111 TRI->getRegUnitWeight(Regs[I]));
114 /// Simply decrease the current pressure as impacted by these physcial
116 void RegPressureTracker::decreasePhysRegPressure(ArrayRef<unsigned> Regs) {
117 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
118 decreaseSetPressure(CurrSetPressure, TRI->getRegUnitPressureSets(Regs[I]),
119 TRI->getRegUnitWeight(Regs[I]));
122 /// Increase the current pressure as impacted by these virtual registers and
123 /// bump the high water mark if needed.
124 void RegPressureTracker::increaseVirtRegPressure(ArrayRef<unsigned> Regs) {
125 for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
126 const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
127 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
128 TRI->getRegClassPressureSets(RC),
129 TRI->getRegClassWeight(RC).RegWeight);
133 /// Simply decrease the current pressure as impacted by these virtual registers.
134 void RegPressureTracker::decreaseVirtRegPressure(ArrayRef<unsigned> Regs) {
135 for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
136 const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
137 decreaseSetPressure(CurrSetPressure,
138 TRI->getRegClassPressureSets(RC),
139 TRI->getRegClassWeight(RC).RegWeight);
143 /// Clear the result so it can be used for another round of pressure tracking.
144 void IntervalPressure::reset() {
145 TopIdx = BottomIdx = SlotIndex();
146 MaxSetPressure.clear();
151 /// Clear the result so it can be used for another round of pressure tracking.
152 void RegionPressure::reset() {
153 TopPos = BottomPos = MachineBasicBlock::const_iterator();
154 MaxSetPressure.clear();
159 /// If the current top is not less than or equal to the next index, open it.
160 /// We happen to need the SlotIndex for the next top for pressure update.
161 void IntervalPressure::openTop(SlotIndex NextTop) {
162 if (TopIdx <= NextTop)
164 TopIdx = SlotIndex();
168 /// If the current top is the previous instruction (before receding), open it.
169 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
170 if (TopPos != PrevTop)
172 TopPos = MachineBasicBlock::const_iterator();
176 /// If the current bottom is not greater than the previous index, open it.
177 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
178 if (BottomIdx > PrevBottom)
180 BottomIdx = SlotIndex();
184 /// If the current bottom is the previous instr (before advancing), open it.
185 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
186 if (BottomPos != PrevBottom)
188 BottomPos = MachineBasicBlock::const_iterator();
192 /// Setup the RegPressureTracker.
194 /// TODO: Add support for pressure without LiveIntervals.
195 void RegPressureTracker::init(const MachineFunction *mf,
196 const RegisterClassInfo *rci,
197 const LiveIntervals *lis,
198 const MachineBasicBlock *mbb,
199 MachineBasicBlock::const_iterator pos)
202 TRI = MF->getTarget().getRegisterInfo();
204 MRI = &MF->getRegInfo();
207 if (RequireIntervals) {
208 assert(lis && "IntervalPressure requires LiveIntervals");
213 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
215 if (RequireIntervals)
216 static_cast<IntervalPressure&>(P).reset();
218 static_cast<RegionPressure&>(P).reset();
219 P.MaxSetPressure = CurrSetPressure;
221 LivePhysRegs.clear();
222 LivePhysRegs.setUniverse(TRI->getNumRegs());
223 LiveVirtRegs.clear();
224 LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
227 /// Does this pressure result have a valid top position and live ins.
228 bool RegPressureTracker::isTopClosed() const {
229 if (RequireIntervals)
230 return static_cast<IntervalPressure&>(P).TopIdx.isValid();
231 return (static_cast<RegionPressure&>(P).TopPos ==
232 MachineBasicBlock::const_iterator());
235 /// Does this pressure result have a valid bottom position and live outs.
236 bool RegPressureTracker::isBottomClosed() const {
237 if (RequireIntervals)
238 return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
239 return (static_cast<RegionPressure&>(P).BottomPos ==
240 MachineBasicBlock::const_iterator());
244 SlotIndex RegPressureTracker::getCurrSlot() const {
245 MachineBasicBlock::const_iterator IdxPos = CurrPos;
246 while (IdxPos != MBB->end() && IdxPos->isDebugValue())
248 if (IdxPos == MBB->end())
249 return LIS->getMBBEndIdx(MBB);
250 return LIS->getInstructionIndex(IdxPos).getRegSlot();
253 /// Set the boundary for the top of the region and summarize live ins.
254 void RegPressureTracker::closeTop() {
255 if (RequireIntervals)
256 static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
258 static_cast<RegionPressure&>(P).TopPos = CurrPos;
260 assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
261 P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
262 P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
263 for (SparseSet<unsigned>::const_iterator I =
264 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
265 P.LiveInRegs.push_back(*I);
266 std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
267 P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
271 /// Set the boundary for the bottom of the region and summarize live outs.
272 void RegPressureTracker::closeBottom() {
273 if (RequireIntervals)
274 static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
276 static_cast<RegionPressure&>(P).BottomPos = CurrPos;
278 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
279 P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
280 P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
281 for (SparseSet<unsigned>::const_iterator I =
282 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
283 P.LiveOutRegs.push_back(*I);
284 std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
285 P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
286 P.LiveOutRegs.end());
289 /// Finalize the region boundaries and record live ins and live outs.
290 void RegPressureTracker::closeRegion() {
291 if (!isTopClosed() && !isBottomClosed()) {
292 assert(LivePhysRegs.empty() && LiveVirtRegs.empty() &&
293 "no region boundary");
296 if (!isBottomClosed())
298 else if (!isTopClosed())
300 // If both top and bottom are closed, do nothing.
303 /// \brief Convenient wrapper for checking membership in RegisterOperands.
304 static bool containsReg(ArrayRef<unsigned> Regs, unsigned Reg) {
305 return std::find(Regs.begin(), Regs.end(), Reg) != Regs.end();
308 /// Collect this instruction's unique uses and defs into SmallVectors for
309 /// processing defs and uses in order.
310 template<bool isVReg>
311 class RegisterOperands {
313 SmallVector<unsigned, 8> Uses;
314 SmallVector<unsigned, 8> Defs;
315 SmallVector<unsigned, 8> DeadDefs;
317 /// Push this operand's register onto the correct vector.
318 void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
320 pushRegUnits(MO.getReg(), Uses, TRI);
323 pushRegUnits(MO.getReg(), DeadDefs, TRI);
325 pushRegUnits(MO.getReg(), Defs, TRI);
330 void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &Regs,
331 const TargetRegisterInfo *TRI) {
333 if (containsReg(Regs, Reg))
338 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
339 if (containsReg(Regs, *Units))
341 Regs.push_back(*Units);
346 typedef RegisterOperands<false> PhysRegOperands;
347 typedef RegisterOperands<true> VirtRegOperands;
349 /// Collect physical and virtual register operands.
350 static void collectOperands(const MachineInstr *MI,
351 PhysRegOperands &PhysRegOpers,
352 VirtRegOperands &VirtRegOpers,
353 const TargetRegisterInfo *TRI,
354 const MachineRegisterInfo *MRI) {
355 for(ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) {
356 const MachineOperand &MO = *OperI;
357 if (!MO.isReg() || !MO.getReg())
360 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
361 VirtRegOpers.collect(MO, TRI);
362 else if (MRI->isAllocatable(MO.getReg()))
363 PhysRegOpers.collect(MO, TRI);
365 // Remove redundant physreg dead defs.
366 for (unsigned i = PhysRegOpers.DeadDefs.size(); i > 0; --i) {
367 unsigned Reg = PhysRegOpers.DeadDefs[i-1];
368 if (containsReg(PhysRegOpers.Defs, Reg))
369 PhysRegOpers.DeadDefs.erase(&PhysRegOpers.DeadDefs[i-1]);
373 /// Force liveness of registers.
374 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
375 for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
376 if (TargetRegisterInfo::isVirtualRegister(Regs[i])) {
377 if (LiveVirtRegs.insert(Regs[i]).second)
378 increaseVirtRegPressure(Regs[i]);
381 if (LivePhysRegs.insert(Regs[i]).second)
382 increasePhysRegPressure(Regs[i]);
387 /// Add PhysReg to the live in set and increase max pressure.
388 void RegPressureTracker::discoverPhysLiveIn(unsigned Reg) {
389 assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
390 if (containsReg(P.LiveInRegs, Reg))
393 // At live in discovery, unconditionally increase the high water mark.
394 P.LiveInRegs.push_back(Reg);
395 P.increase(Reg, TRI);
398 /// Add PhysReg to the live out set and increase max pressure.
399 void RegPressureTracker::discoverPhysLiveOut(unsigned Reg) {
400 assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
401 if (containsReg(P.LiveOutRegs, Reg))
404 // At live out discovery, unconditionally increase the high water mark.
405 P.LiveOutRegs.push_back(Reg);
406 P.increase(Reg, TRI);
409 /// Add VirtReg to the live in set and increase max pressure.
410 void RegPressureTracker::discoverVirtLiveIn(unsigned Reg) {
411 assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
412 if (containsReg(P.LiveInRegs, Reg))
415 // At live in discovery, unconditionally increase the high water mark.
416 P.LiveInRegs.push_back(Reg);
417 P.increase(MRI->getRegClass(Reg), TRI);
420 /// Add VirtReg to the live out set and increase max pressure.
421 void RegPressureTracker::discoverVirtLiveOut(unsigned Reg) {
422 assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
423 if (containsReg(P.LiveOutRegs, Reg))
426 // At live out discovery, unconditionally increase the high water mark.
427 P.LiveOutRegs.push_back(Reg);
428 P.increase(MRI->getRegClass(Reg), TRI);
431 /// Recede across the previous instruction.
432 bool RegPressureTracker::recede() {
433 // Check for the top of the analyzable region.
434 if (CurrPos == MBB->begin()) {
438 if (!isBottomClosed())
441 // Open the top of the region using block iterators.
442 if (!RequireIntervals && isTopClosed())
443 static_cast<RegionPressure&>(P).openTop(CurrPos);
445 // Find the previous instruction.
448 while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
450 if (CurrPos->isDebugValue()) {
455 if (RequireIntervals)
456 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
458 // Open the top of the region using slot indexes.
459 if (RequireIntervals && isTopClosed())
460 static_cast<IntervalPressure&>(P).openTop(SlotIdx);
462 PhysRegOperands PhysRegOpers;
463 VirtRegOperands VirtRegOpers;
464 collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, MRI);
466 // Boost pressure for all dead defs together.
467 increasePhysRegPressure(PhysRegOpers.DeadDefs);
468 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
469 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
470 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
472 // Kill liveness at live defs.
473 // TODO: consider earlyclobbers?
474 for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
475 unsigned Reg = PhysRegOpers.Defs[i];
476 if (LivePhysRegs.erase(Reg))
477 decreasePhysRegPressure(Reg);
479 discoverPhysLiveOut(Reg);
481 for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
482 unsigned Reg = VirtRegOpers.Defs[i];
483 if (LiveVirtRegs.erase(Reg))
484 decreaseVirtRegPressure(Reg);
486 discoverVirtLiveOut(Reg);
489 // Generate liveness for uses.
490 for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
491 unsigned Reg = PhysRegOpers.Uses[i];
492 if (LivePhysRegs.insert(Reg).second)
493 increasePhysRegPressure(Reg);
495 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
496 unsigned Reg = VirtRegOpers.Uses[i];
497 if (!LiveVirtRegs.count(Reg)) {
498 // Adjust liveouts if LiveIntervals are available.
499 if (RequireIntervals) {
500 const LiveInterval *LI = &LIS->getInterval(Reg);
501 if (!LI->killedAt(SlotIdx))
502 discoverVirtLiveOut(Reg);
504 increaseVirtRegPressure(Reg);
505 LiveVirtRegs.insert(Reg);
511 /// Advance across the current instruction.
512 bool RegPressureTracker::advance() {
513 // Check for the bottom of the analyzable region.
514 if (CurrPos == MBB->end()) {
522 if (RequireIntervals)
523 SlotIdx = getCurrSlot();
525 // Open the bottom of the region using slot indexes.
526 if (isBottomClosed()) {
527 if (RequireIntervals)
528 static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
530 static_cast<RegionPressure&>(P).openBottom(CurrPos);
533 PhysRegOperands PhysRegOpers;
534 VirtRegOperands VirtRegOpers;
535 collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, MRI);
537 // Kill liveness at last uses.
538 for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
539 unsigned Reg = PhysRegOpers.Uses[i];
540 // Allocatable physregs are always single-use before register rewriting.
541 if (LivePhysRegs.erase(Reg))
542 decreasePhysRegPressure(Reg);
544 discoverPhysLiveIn(Reg);
546 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
547 unsigned Reg = VirtRegOpers.Uses[i];
548 if (RequireIntervals) {
549 const LiveInterval *LI = &LIS->getInterval(Reg);
550 if (LI->killedAt(SlotIdx)) {
551 if (LiveVirtRegs.erase(Reg))
552 decreaseVirtRegPressure(Reg);
554 discoverVirtLiveIn(Reg);
557 else if (!LiveVirtRegs.count(Reg)) {
558 discoverVirtLiveIn(Reg);
559 increaseVirtRegPressure(Reg);
563 // Generate liveness for defs.
564 for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
565 unsigned Reg = PhysRegOpers.Defs[i];
566 if (LivePhysRegs.insert(Reg).second)
567 increasePhysRegPressure(Reg);
569 for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
570 unsigned Reg = VirtRegOpers.Defs[i];
571 if (LiveVirtRegs.insert(Reg).second)
572 increaseVirtRegPressure(Reg);
575 // Boost pressure for all dead defs together.
576 increasePhysRegPressure(PhysRegOpers.DeadDefs);
577 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
578 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
579 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
581 // Find the next instruction.
584 while (CurrPos != MBB->end() && CurrPos->isDebugValue());
588 /// Find the max change in excess pressure across all sets.
589 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
590 ArrayRef<unsigned> NewPressureVec,
591 RegPressureDelta &Delta,
592 const TargetRegisterInfo *TRI) {
594 unsigned PSetID = ~0U;
595 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
596 unsigned POld = OldPressureVec[i];
597 unsigned PNew = NewPressureVec[i];
598 int PDiff = (int)PNew - (int)POld;
599 if (!PDiff) // No change in this set in the common case.
601 // Only consider change beyond the limit.
602 unsigned Limit = TRI->getRegPressureSetLimit(i);
605 PDiff = 0; // Under the limit
607 PDiff = PNew - Limit; // Just exceeded limit.
609 else if (Limit > PNew)
610 PDiff = Limit - POld; // Just obeyed limit.
612 if (std::abs(PDiff) > std::abs(ExcessUnits)) {
617 Delta.Excess.PSetID = PSetID;
618 Delta.Excess.UnitIncrease = ExcessUnits;
621 /// Find the max change in max pressure that either surpasses a critical PSet
622 /// limit or exceeds the current MaxPressureLimit.
624 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
625 /// silly. It's done now to demonstrate the concept but will go away with a
626 /// RegPressureTracker API change to work with pressure differences.
627 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
628 ArrayRef<unsigned> NewMaxPressureVec,
629 ArrayRef<PressureElement> CriticalPSets,
630 ArrayRef<unsigned> MaxPressureLimit,
631 RegPressureDelta &Delta) {
632 Delta.CriticalMax = PressureElement();
633 Delta.CurrentMax = PressureElement();
635 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
636 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
637 unsigned POld = OldMaxPressureVec[i];
638 unsigned PNew = NewMaxPressureVec[i];
639 if (PNew == POld) // No change in this set in the common case.
642 while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
645 if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
646 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
647 if (PDiff > Delta.CriticalMax.UnitIncrease) {
648 Delta.CriticalMax.PSetID = i;
649 Delta.CriticalMax.UnitIncrease = PDiff;
653 // Find the greatest increase above MaxPressureLimit.
654 // (Ignores negative MDiff).
655 int MDiff = (int)PNew - (int)MaxPressureLimit[i];
656 if (MDiff > Delta.CurrentMax.UnitIncrease) {
657 Delta.CurrentMax.PSetID = i;
658 Delta.CurrentMax.UnitIncrease = PNew;
663 /// Record the upward impact of a single instruction on current register
664 /// pressure. Unlike the advance/recede pressure tracking interface, this does
665 /// not discover live in/outs.
667 /// This is intended for speculative queries. It leaves pressure inconsistent
668 /// with the current position, so must be restored by the caller.
669 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
670 // Account for register pressure similar to RegPressureTracker::recede().
671 PhysRegOperands PhysRegOpers;
672 VirtRegOperands VirtRegOpers;
673 collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, MRI);
675 // Boost max pressure for all dead defs together.
676 // Since CurrSetPressure and MaxSetPressure
677 increasePhysRegPressure(PhysRegOpers.DeadDefs);
678 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
679 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
680 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
682 // Kill liveness at live defs.
683 for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
684 unsigned Reg = PhysRegOpers.Defs[i];
685 if (!containsReg(PhysRegOpers.Uses, Reg))
686 decreasePhysRegPressure(Reg);
688 for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
689 unsigned Reg = VirtRegOpers.Defs[i];
690 if (!containsReg(VirtRegOpers.Uses, Reg))
691 decreaseVirtRegPressure(Reg);
693 // Generate liveness for uses.
694 for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
695 unsigned Reg = PhysRegOpers.Uses[i];
696 if (!LivePhysRegs.count(Reg))
697 increasePhysRegPressure(Reg);
699 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
700 unsigned Reg = VirtRegOpers.Uses[i];
701 if (!LiveVirtRegs.count(Reg))
702 increaseVirtRegPressure(Reg);
706 /// Consider the pressure increase caused by traversing this instruction
707 /// bottom-up. Find the pressure set with the most change beyond its pressure
708 /// limit based on the tracker's current pressure, and return the change in
709 /// number of register units of that pressure set introduced by this
712 /// This assumes that the current LiveOut set is sufficient.
714 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
715 /// result per-SUnit with enough information to adjust for the current
716 /// scheduling position. But this works as a proof of concept.
717 void RegPressureTracker::
718 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
719 ArrayRef<PressureElement> CriticalPSets,
720 ArrayRef<unsigned> MaxPressureLimit) {
721 // Snapshot Pressure.
722 // FIXME: The snapshot heap space should persist. But I'm planning to
723 // summarize the pressure effect so we don't need to snapshot at all.
724 std::vector<unsigned> SavedPressure = CurrSetPressure;
725 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
727 bumpUpwardPressure(MI);
729 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
730 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
731 MaxPressureLimit, Delta);
732 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
733 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
735 // Restore the tracker's state.
736 P.MaxSetPressure.swap(SavedMaxPressure);
737 CurrSetPressure.swap(SavedPressure);
740 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
741 static bool findUseBetween(unsigned Reg,
742 SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
743 const MachineRegisterInfo *MRI,
744 const LiveIntervals *LIS) {
745 for (MachineRegisterInfo::use_nodbg_iterator
746 UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
747 UI != UE; UI.skipInstruction()) {
748 const MachineInstr* MI = &*UI;
749 SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
750 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
756 /// Record the downward impact of a single instruction on current register
757 /// pressure. Unlike the advance/recede pressure tracking interface, this does
758 /// not discover live in/outs.
760 /// This is intended for speculative queries. It leaves pressure inconsistent
761 /// with the current position, so must be restored by the caller.
762 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
763 // Account for register pressure similar to RegPressureTracker::recede().
764 PhysRegOperands PhysRegOpers;
765 VirtRegOperands VirtRegOpers;
766 collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, MRI);
768 // Kill liveness at last uses. Assume allocatable physregs are single-use
769 // rather than checking LiveIntervals.
770 decreasePhysRegPressure(PhysRegOpers.Uses);
771 if (RequireIntervals) {
772 SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
773 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
774 unsigned Reg = VirtRegOpers.Uses[i];
775 const LiveInterval *LI = &LIS->getInterval(Reg);
776 // FIXME: allow the caller to pass in the list of vreg uses that remain to
777 // be bottom-scheduled to avoid searching uses at each query.
778 SlotIndex CurrIdx = getCurrSlot();
779 if (LI->killedAt(SlotIdx)
780 && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
781 decreaseVirtRegPressure(Reg);
786 // Generate liveness for defs.
787 increasePhysRegPressure(PhysRegOpers.Defs);
788 increaseVirtRegPressure(VirtRegOpers.Defs);
790 // Boost pressure for all dead defs together.
791 increasePhysRegPressure(PhysRegOpers.DeadDefs);
792 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
793 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
794 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
797 /// Consider the pressure increase caused by traversing this instruction
798 /// top-down. Find the register class with the most change in its pressure limit
799 /// based on the tracker's current pressure, and return the number of excess
800 /// register units of that pressure set introduced by this instruction.
802 /// This assumes that the current LiveIn set is sufficient.
803 void RegPressureTracker::
804 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
805 ArrayRef<PressureElement> CriticalPSets,
806 ArrayRef<unsigned> MaxPressureLimit) {
807 // Snapshot Pressure.
808 std::vector<unsigned> SavedPressure = CurrSetPressure;
809 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
811 bumpDownwardPressure(MI);
813 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
814 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
815 MaxPressureLimit, Delta);
816 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
817 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
819 // Restore the tracker's state.
820 P.MaxSetPressure.swap(SavedMaxPressure);
821 CurrSetPressure.swap(SavedPressure);
824 /// Get the pressure of each PSet after traversing this instruction bottom-up.
825 void RegPressureTracker::
826 getUpwardPressure(const MachineInstr *MI,
827 std::vector<unsigned> &PressureResult,
828 std::vector<unsigned> &MaxPressureResult) {
829 // Snapshot pressure.
830 PressureResult = CurrSetPressure;
831 MaxPressureResult = P.MaxSetPressure;
833 bumpUpwardPressure(MI);
835 // Current pressure becomes the result. Restore current pressure.
836 P.MaxSetPressure.swap(MaxPressureResult);
837 CurrSetPressure.swap(PressureResult);
840 /// Get the pressure of each PSet after traversing this instruction top-down.
841 void RegPressureTracker::
842 getDownwardPressure(const MachineInstr *MI,
843 std::vector<unsigned> &PressureResult,
844 std::vector<unsigned> &MaxPressureResult) {
845 // Snapshot pressure.
846 PressureResult = CurrSetPressure;
847 MaxPressureResult = P.MaxSetPressure;
849 bumpDownwardPressure(MI);
851 // Current pressure becomes the result. Restore current pressure.
852 P.MaxSetPressure.swap(MaxPressureResult);
853 CurrSetPressure.swap(PressureResult);