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/LiveInterval.h"
16 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/RegisterClassInfo.h"
19 #include "llvm/CodeGen/RegisterPressure.h"
20 #include "llvm/Target/TargetMachine.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
26 /// Increase register pressure for each set impacted by this register class.
27 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
28 std::vector<unsigned> &MaxSetPressure,
29 const TargetRegisterClass *RC,
30 const TargetRegisterInfo *TRI) {
31 unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
32 for (const int *PSet = TRI->getRegClassPressureSets(RC);
33 *PSet != -1; ++PSet) {
34 CurrSetPressure[*PSet] += Weight;
35 if (&CurrSetPressure != &MaxSetPressure
36 && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) {
37 MaxSetPressure[*PSet] = CurrSetPressure[*PSet];
42 /// Decrease register pressure for each set impacted by this register class.
43 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
44 const TargetRegisterClass *RC,
45 const TargetRegisterInfo *TRI) {
46 unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
47 for (const int *PSet = TRI->getRegClassPressureSets(RC);
48 *PSet != -1; ++PSet) {
49 assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow");
50 CurrSetPressure[*PSet] -= Weight;
54 /// Directly increase pressure only within this RegisterPressure result.
55 void RegisterPressure::increase(const TargetRegisterClass *RC,
56 const TargetRegisterInfo *TRI) {
57 increaseSetPressure(MaxSetPressure, MaxSetPressure, RC, TRI);
60 /// Directly decrease pressure only within this RegisterPressure result.
61 void RegisterPressure::decrease(const TargetRegisterClass *RC,
62 const TargetRegisterInfo *TRI) {
63 decreaseSetPressure(MaxSetPressure, RC, TRI);
66 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
67 void RegisterPressure::dump(const TargetRegisterInfo *TRI) {
68 dbgs() << "Live In: ";
69 for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i)
70 dbgs() << PrintReg(LiveInRegs[i], TRI) << " ";
72 dbgs() << "Live Out: ";
73 for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i)
74 dbgs() << PrintReg(LiveOutRegs[i], TRI) << " ";
76 for (unsigned i = 0, e = MaxSetPressure.size(); i < e; ++i) {
77 if (MaxSetPressure[i] != 0)
78 dbgs() << TRI->getRegPressureSetName(i) << "=" << MaxSetPressure[i]
84 /// Increase the current pressure as impacted by these physical registers and
85 /// bump the high water mark if needed.
86 void RegPressureTracker::increasePhysRegPressure(ArrayRef<unsigned> Regs) {
87 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
88 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
89 TRI->getMinimalPhysRegClass(Regs[I]), TRI);
92 /// Simply decrease the current pressure as impacted by these physcial
94 void RegPressureTracker::decreasePhysRegPressure(ArrayRef<unsigned> Regs) {
95 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
96 decreaseSetPressure(CurrSetPressure, TRI->getMinimalPhysRegClass(Regs[I]),
100 /// Increase the current pressure as impacted by these virtual registers and
101 /// bump the high water mark if needed.
102 void RegPressureTracker::increaseVirtRegPressure(ArrayRef<unsigned> Regs) {
103 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
104 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
105 MRI->getRegClass(Regs[I]), TRI);
108 /// Simply decrease the current pressure as impacted by these virtual registers.
109 void RegPressureTracker::decreaseVirtRegPressure(ArrayRef<unsigned> Regs) {
110 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
111 decreaseSetPressure(CurrSetPressure, MRI->getRegClass(Regs[I]), TRI);
114 /// Clear the result so it can be used for another round of pressure tracking.
115 void IntervalPressure::reset() {
116 TopIdx = BottomIdx = SlotIndex();
117 MaxSetPressure.clear();
122 /// Clear the result so it can be used for another round of pressure tracking.
123 void RegionPressure::reset() {
124 TopPos = BottomPos = MachineBasicBlock::const_iterator();
125 MaxSetPressure.clear();
130 /// If the current top is not less than or equal to the next index, open it.
131 /// We happen to need the SlotIndex for the next top for pressure update.
132 void IntervalPressure::openTop(SlotIndex NextTop) {
133 if (TopIdx <= NextTop)
135 TopIdx = SlotIndex();
139 /// If the current top is the previous instruction (before receding), open it.
140 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
141 if (TopPos != PrevTop)
143 TopPos = MachineBasicBlock::const_iterator();
147 /// If the current bottom is not greater than the previous index, open it.
148 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
149 if (BottomIdx > PrevBottom)
151 BottomIdx = SlotIndex();
155 /// If the current bottom is the previous instr (before advancing), open it.
156 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
157 if (BottomPos != PrevBottom)
159 BottomPos = MachineBasicBlock::const_iterator();
163 /// Setup the RegPressureTracker.
165 /// TODO: Add support for pressure without LiveIntervals.
166 void RegPressureTracker::init(const MachineFunction *mf,
167 const RegisterClassInfo *rci,
168 const LiveIntervals *lis,
169 const MachineBasicBlock *mbb,
170 MachineBasicBlock::const_iterator pos)
173 TRI = MF->getTarget().getRegisterInfo();
175 MRI = &MF->getRegInfo();
178 if (RequireIntervals) {
179 assert(lis && "IntervalPressure requires LiveIntervals");
184 while (CurrPos != MBB->end() && CurrPos->isDebugValue())
187 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
189 if (RequireIntervals)
190 static_cast<IntervalPressure&>(P).reset();
192 static_cast<RegionPressure&>(P).reset();
193 P.MaxSetPressure = CurrSetPressure;
195 LivePhysRegs.clear();
196 LivePhysRegs.setUniverse(TRI->getNumRegs());
197 LiveVirtRegs.clear();
198 LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
201 /// Does this pressure result have a valid top position and live ins.
202 bool RegPressureTracker::isTopClosed() const {
203 if (RequireIntervals)
204 return static_cast<IntervalPressure&>(P).TopIdx.isValid();
205 return (static_cast<RegionPressure&>(P).TopPos ==
206 MachineBasicBlock::const_iterator());
209 /// Does this pressure result have a valid bottom position and live outs.
210 bool RegPressureTracker::isBottomClosed() const {
211 if (RequireIntervals)
212 return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
213 return (static_cast<RegionPressure&>(P).BottomPos ==
214 MachineBasicBlock::const_iterator());
217 /// Set the boundary for the top of the region and summarize live ins.
218 void RegPressureTracker::closeTop() {
219 if (RequireIntervals)
220 static_cast<IntervalPressure&>(P).TopIdx =
221 LIS->getInstructionIndex(CurrPos).getRegSlot();
223 static_cast<RegionPressure&>(P).TopPos = CurrPos;
225 assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
226 P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
227 P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
228 for (SparseSet<unsigned>::const_iterator I =
229 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
230 P.LiveInRegs.push_back(*I);
231 std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
232 P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
236 /// Set the boundary for the bottom of the region and summarize live outs.
237 void RegPressureTracker::closeBottom() {
238 if (RequireIntervals)
239 if (CurrPos == MBB->end())
240 static_cast<IntervalPressure&>(P).BottomIdx = LIS->getMBBEndIdx(MBB);
242 static_cast<IntervalPressure&>(P).BottomIdx =
243 LIS->getInstructionIndex(CurrPos).getRegSlot();
245 static_cast<RegionPressure&>(P).BottomPos = CurrPos;
247 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
248 P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
249 P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
250 for (SparseSet<unsigned>::const_iterator I =
251 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
252 P.LiveOutRegs.push_back(*I);
253 std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
254 P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
255 P.LiveOutRegs.end());
258 /// Finalize the region boundaries and record live ins and live outs.
259 void RegPressureTracker::closeRegion() {
260 if (!isTopClosed() && !isBottomClosed()) {
261 assert(LivePhysRegs.empty() && LiveVirtRegs.empty() &&
262 "no region boundary");
265 if (!isBottomClosed())
267 else if (!isTopClosed())
269 // If both top and bottom are closed, do nothing.
272 /// Return true if Reg aliases a register in Regs SparseSet.
273 static bool hasRegAlias(unsigned Reg, SparseSet<unsigned> &Regs,
274 const TargetRegisterInfo *TRI) {
275 assert(!TargetRegisterInfo::isVirtualRegister(Reg) && "only for physregs");
276 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
282 /// Return true if Reg aliases a register in unsorted Regs SmallVector.
283 /// This is only valid for physical registers.
284 static SmallVectorImpl<unsigned>::iterator
285 findRegAlias(unsigned Reg, SmallVectorImpl<unsigned> &Regs,
286 const TargetRegisterInfo *TRI) {
287 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
288 SmallVectorImpl<unsigned>::iterator I =
289 std::find(Regs.begin(), Regs.end(), *AI);
296 /// Return true if Reg can be inserted into Regs SmallVector. For virtual
297 /// register, do a linear search. For physical registers check for aliases.
298 static SmallVectorImpl<unsigned>::iterator
299 findReg(unsigned Reg, bool isVReg, SmallVectorImpl<unsigned> &Regs,
300 const TargetRegisterInfo *TRI) {
302 return std::find(Regs.begin(), Regs.end(), Reg);
303 return findRegAlias(Reg, Regs, TRI);
306 /// Collect this instruction's unique uses and defs into SmallVectors for
307 /// processing defs and uses in order.
308 template<bool isVReg>
309 struct RegisterOperands {
310 SmallVector<unsigned, 8> Uses;
311 SmallVector<unsigned, 8> Defs;
312 SmallVector<unsigned, 8> DeadDefs;
314 /// Push this operand's register onto the correct vector.
315 void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
317 if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end())
318 Uses.push_back(MO.getReg());
322 if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end())
323 DeadDefs.push_back(MO.getReg());
326 if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
327 Defs.push_back(MO.getReg());
332 typedef RegisterOperands<false> PhysRegOperands;
333 typedef RegisterOperands<true> VirtRegOperands;
335 /// Collect physical and virtual register operands.
336 static void collectOperands(const MachineInstr *MI,
337 PhysRegOperands &PhysRegOpers,
338 VirtRegOperands &VirtRegOpers,
339 const TargetRegisterInfo *TRI,
340 const RegisterClassInfo *RCI) {
341 for(ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) {
342 const MachineOperand &MO = *OperI;
343 if (!MO.isReg() || !MO.getReg())
346 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
347 VirtRegOpers.collect(MO, TRI);
348 else if (RCI->isAllocatable(MO.getReg()))
349 PhysRegOpers.collect(MO, TRI);
351 // Remove redundant physreg dead defs.
352 for (unsigned i = PhysRegOpers.DeadDefs.size(); i > 0; --i) {
353 unsigned Reg = PhysRegOpers.DeadDefs[i-1];
354 if (findRegAlias(Reg, PhysRegOpers.Defs, TRI) != PhysRegOpers.Defs.end())
355 PhysRegOpers.DeadDefs.erase(&PhysRegOpers.DeadDefs[i-1]);
359 /// Force liveness of registers.
360 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
361 for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
362 if (TargetRegisterInfo::isVirtualRegister(Regs[i])) {
363 if (LiveVirtRegs.insert(Regs[i]).second)
364 increaseVirtRegPressure(Regs[i]);
367 if (!hasRegAlias(Regs[i], LivePhysRegs, TRI)) {
368 LivePhysRegs.insert(Regs[i]);
369 increasePhysRegPressure(Regs[i]);
375 /// Add PhysReg to the live in set and increase max pressure.
376 void RegPressureTracker::discoverPhysLiveIn(unsigned Reg) {
377 assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
378 if (findRegAlias(Reg, P.LiveInRegs, TRI) != P.LiveInRegs.end())
381 // At live in discovery, unconditionally increase the high water mark.
382 P.LiveInRegs.push_back(Reg);
383 P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
386 /// Add PhysReg to the live out set and increase max pressure.
387 void RegPressureTracker::discoverPhysLiveOut(unsigned Reg) {
388 assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
389 if (findRegAlias(Reg, P.LiveOutRegs, TRI) != P.LiveOutRegs.end())
392 // At live out discovery, unconditionally increase the high water mark.
393 P.LiveOutRegs.push_back(Reg);
394 P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
397 /// Add VirtReg to the live in set and increase max pressure.
398 void RegPressureTracker::discoverVirtLiveIn(unsigned Reg) {
399 assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
400 if (std::find(P.LiveInRegs.begin(), P.LiveInRegs.end(), Reg) !=
404 // At live in discovery, unconditionally increase the high water mark.
405 P.LiveInRegs.push_back(Reg);
406 P.increase(MRI->getRegClass(Reg), TRI);
409 /// Add VirtReg to the live out set and increase max pressure.
410 void RegPressureTracker::discoverVirtLiveOut(unsigned Reg) {
411 assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
412 if (std::find(P.LiveOutRegs.begin(), P.LiveOutRegs.end(), Reg) !=
416 // At live out discovery, unconditionally increase the high water mark.
417 P.LiveOutRegs.push_back(Reg);
418 P.increase(MRI->getRegClass(Reg), TRI);
421 /// Recede across the previous instruction.
422 bool RegPressureTracker::recede() {
423 // Check for the top of the analyzable region.
424 if (CurrPos == MBB->begin()) {
428 if (!isBottomClosed())
431 // Open the top of the region using block iterators.
432 if (!RequireIntervals && isTopClosed())
433 static_cast<RegionPressure&>(P).openTop(CurrPos);
435 // Find the previous instruction.
438 while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
440 if (CurrPos->isDebugValue()) {
445 if (RequireIntervals)
446 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
448 // Open the top of the region using slot indexes.
449 if (RequireIntervals && isTopClosed())
450 static_cast<IntervalPressure&>(P).openTop(SlotIdx);
452 PhysRegOperands PhysRegOpers;
453 VirtRegOperands VirtRegOpers;
454 collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
456 // Boost pressure for all dead defs together.
457 increasePhysRegPressure(PhysRegOpers.DeadDefs);
458 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
459 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
460 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
462 // Kill liveness at live defs.
463 // TODO: consider earlyclobbers?
464 for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
465 unsigned Reg = PhysRegOpers.Defs[i];
466 if (LivePhysRegs.erase(Reg))
467 decreasePhysRegPressure(Reg);
469 discoverPhysLiveOut(Reg);
471 for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
472 unsigned Reg = VirtRegOpers.Defs[i];
473 if (LiveVirtRegs.erase(Reg))
474 decreaseVirtRegPressure(Reg);
476 discoverVirtLiveOut(Reg);
479 // Generate liveness for uses.
480 for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
481 unsigned Reg = PhysRegOpers.Uses[i];
482 if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
483 increasePhysRegPressure(Reg);
484 LivePhysRegs.insert(Reg);
487 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
488 unsigned Reg = VirtRegOpers.Uses[i];
489 if (!LiveVirtRegs.count(Reg)) {
490 // Adjust liveouts if LiveIntervals are available.
491 if (RequireIntervals) {
492 const LiveInterval *LI = &LIS->getInterval(Reg);
493 if (!LI->killedAt(SlotIdx))
494 discoverVirtLiveOut(Reg);
496 increaseVirtRegPressure(Reg);
497 LiveVirtRegs.insert(Reg);
503 /// Advance across the current instruction.
504 bool RegPressureTracker::advance() {
505 // Check for the bottom of the analyzable region.
506 if (CurrPos == MBB->end()) {
514 if (RequireIntervals)
515 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
517 // Open the bottom of the region using slot indexes.
518 if (isBottomClosed()) {
519 if (RequireIntervals)
520 static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
522 static_cast<RegionPressure&>(P).openBottom(CurrPos);
525 PhysRegOperands PhysRegOpers;
526 VirtRegOperands VirtRegOpers;
527 collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
529 // Kill liveness at last uses.
530 for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
531 unsigned Reg = PhysRegOpers.Uses[i];
532 if (!hasRegAlias(Reg, LivePhysRegs, TRI))
533 discoverPhysLiveIn(Reg);
535 // Allocatable physregs are always single-use before regalloc.
536 decreasePhysRegPressure(Reg);
537 LivePhysRegs.erase(Reg);
540 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
541 unsigned Reg = VirtRegOpers.Uses[i];
542 if (RequireIntervals) {
543 const LiveInterval *LI = &LIS->getInterval(Reg);
544 if (LI->killedAt(SlotIdx)) {
545 if (LiveVirtRegs.erase(Reg))
546 decreaseVirtRegPressure(Reg);
548 discoverVirtLiveIn(Reg);
551 else if (!LiveVirtRegs.count(Reg)) {
552 discoverVirtLiveIn(Reg);
553 increaseVirtRegPressure(Reg);
557 // Generate liveness for defs.
558 for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
559 unsigned Reg = PhysRegOpers.Defs[i];
560 if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
561 increasePhysRegPressure(Reg);
562 LivePhysRegs.insert(Reg);
565 for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
566 unsigned Reg = VirtRegOpers.Defs[i];
567 if (LiveVirtRegs.insert(Reg).second)
568 increaseVirtRegPressure(Reg);
571 // Boost pressure for all dead defs together.
572 increasePhysRegPressure(PhysRegOpers.DeadDefs);
573 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
574 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
575 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
577 // Find the next instruction.
580 while (CurrPos != MBB->end() && CurrPos->isDebugValue());
584 /// Find the max change in excess pressure across all sets.
585 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
586 ArrayRef<unsigned> NewPressureVec,
587 RegPressureDelta &Delta,
588 const TargetRegisterInfo *TRI) {
590 unsigned PSetID = ~0U;
591 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
592 unsigned POld = OldPressureVec[i];
593 unsigned PNew = NewPressureVec[i];
594 int PDiff = (int)PNew - (int)POld;
595 if (!PDiff) // No change in this set in the common case.
597 // Only consider change beyond the limit.
598 unsigned Limit = TRI->getRegPressureSetLimit(i);
601 PDiff = 0; // Under the limit
603 PDiff = PNew - Limit; // Just exceeded limit.
605 else if (Limit > PNew)
606 PDiff = Limit - POld; // Just obeyed limit.
608 if (std::abs(PDiff) > std::abs(ExcessUnits)) {
613 Delta.Excess.PSetID = PSetID;
614 Delta.Excess.UnitIncrease = ExcessUnits;
617 /// Find the max change in max pressure that either surpasses a critical PSet
618 /// limit or exceeds the current MaxPressureLimit.
620 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
621 /// silly. It's done now to demonstrate the concept but will go away with a
622 /// RegPressureTracker API change to work with pressure differences.
623 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
624 ArrayRef<unsigned> NewMaxPressureVec,
625 ArrayRef<PressureElement> CriticalPSets,
626 ArrayRef<unsigned> MaxPressureLimit,
627 RegPressureDelta &Delta) {
628 Delta.CriticalMax = PressureElement();
629 Delta.CurrentMax = PressureElement();
631 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
632 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
633 unsigned POld = OldMaxPressureVec[i];
634 unsigned PNew = NewMaxPressureVec[i];
635 if (PNew == POld) // No change in this set in the common case.
638 while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
641 if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
642 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
643 if (PDiff > Delta.CriticalMax.UnitIncrease) {
644 Delta.CriticalMax.PSetID = i;
645 Delta.CriticalMax.UnitIncrease = PDiff;
649 // Find the greatest increase above MaxPressureLimit.
650 // (Ignores negative MDiff).
651 int MDiff = (int)PNew - (int)MaxPressureLimit[i];
652 if (MDiff > Delta.CurrentMax.UnitIncrease) {
653 Delta.CurrentMax.PSetID = i;
654 Delta.CurrentMax.UnitIncrease = PNew;
659 /// Record the upward impact of a single instruction on current register
660 /// pressure. Unlike the advance/recede pressure tracking interface, this does
661 /// not discover live in/outs.
663 /// This is intended for speculative queries. It leaves pressure inconsistent
664 /// with the current position, so must be restored by the caller.
665 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
666 // Account for register pressure similar to RegPressureTracker::recede().
667 PhysRegOperands PhysRegOpers;
668 VirtRegOperands VirtRegOpers;
669 collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
671 // Boost max pressure for all dead defs together.
672 // Since CurrSetPressure and MaxSetPressure
673 increasePhysRegPressure(PhysRegOpers.DeadDefs);
674 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
675 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
676 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
678 // Kill liveness at live defs.
679 decreasePhysRegPressure(PhysRegOpers.Defs);
680 decreaseVirtRegPressure(VirtRegOpers.Defs);
682 // Generate liveness for uses.
683 for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
684 unsigned Reg = PhysRegOpers.Uses[i];
685 if (!hasRegAlias(Reg, LivePhysRegs, TRI))
686 increasePhysRegPressure(Reg);
688 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
689 unsigned Reg = VirtRegOpers.Uses[i];
690 if (!LiveVirtRegs.count(Reg))
691 increaseVirtRegPressure(Reg);
695 /// Consider the pressure increase caused by traversing this instruction
696 /// bottom-up. Find the pressure set with the most change beyond its pressure
697 /// limit based on the tracker's current pressure, and return the change in
698 /// number of register units of that pressure set introduced by this
701 /// This assumes that the current LiveOut set is sufficient.
703 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
704 /// result per-SUnit with enough information to adjust for the current
705 /// scheduling position. But this works as a proof of concept.
706 void RegPressureTracker::
707 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
708 ArrayRef<PressureElement> CriticalPSets,
709 ArrayRef<unsigned> MaxPressureLimit) {
710 // Snapshot Pressure.
711 // FIXME: The snapshot heap space should persist. But I'm planning to
712 // summarize the pressure effect so we don't need to snapshot at all.
713 std::vector<unsigned> SavedPressure = CurrSetPressure;
714 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
716 bumpUpwardPressure(MI);
718 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
719 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
720 MaxPressureLimit, Delta);
721 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
722 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
724 // Restore the tracker's state.
725 P.MaxSetPressure.swap(SavedMaxPressure);
726 CurrSetPressure.swap(SavedPressure);
729 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
730 static bool findUseBetween(unsigned Reg,
731 SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
732 const MachineRegisterInfo *MRI,
733 const LiveIntervals *LIS) {
734 for (MachineRegisterInfo::use_nodbg_iterator
735 UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
736 UI != UE; UI.skipInstruction()) {
737 const MachineInstr* MI = &*UI;
738 SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
739 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
745 /// Record the downward impact of a single instruction on current register
746 /// pressure. Unlike the advance/recede pressure tracking interface, this does
747 /// not discover live in/outs.
749 /// This is intended for speculative queries. It leaves pressure inconsistent
750 /// with the current position, so must be restored by the caller.
751 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
752 // Account for register pressure similar to RegPressureTracker::recede().
753 PhysRegOperands PhysRegOpers;
754 VirtRegOperands VirtRegOpers;
755 collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
757 // Kill liveness at last uses. Assume allocatable physregs are single-use
758 // rather than checking LiveIntervals.
759 decreasePhysRegPressure(PhysRegOpers.Uses);
760 if (RequireIntervals) {
761 SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
762 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
763 unsigned Reg = VirtRegOpers.Uses[i];
764 const LiveInterval *LI = &LIS->getInterval(Reg);
765 // FIXME: allow the caller to pass in the list of vreg uses that remain to
766 // be bottom-scheduled to avoid searching uses at each query.
767 SlotIndex CurrIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
768 if (LI->killedAt(SlotIdx)
769 && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
770 decreaseVirtRegPressure(Reg);
775 // Generate liveness for defs.
776 increasePhysRegPressure(PhysRegOpers.Defs);
777 increaseVirtRegPressure(VirtRegOpers.Defs);
779 // Boost pressure for all dead defs together.
780 increasePhysRegPressure(PhysRegOpers.DeadDefs);
781 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
782 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
783 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
786 /// Consider the pressure increase caused by traversing this instruction
787 /// top-down. Find the register class with the most change in its pressure limit
788 /// based on the tracker's current pressure, and return the number of excess
789 /// register units of that pressure set introduced by this instruction.
791 /// This assumes that the current LiveIn set is sufficient.
792 void RegPressureTracker::
793 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
794 ArrayRef<PressureElement> CriticalPSets,
795 ArrayRef<unsigned> MaxPressureLimit) {
796 // Snapshot Pressure.
797 std::vector<unsigned> SavedPressure = CurrSetPressure;
798 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
800 bumpDownwardPressure(MI);
802 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
803 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
804 MaxPressureLimit, Delta);
805 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
806 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
808 // Restore the tracker's state.
809 P.MaxSetPressure.swap(SavedMaxPressure);
810 CurrSetPressure.swap(SavedPressure);
813 /// Get the pressure of each PSet after traversing this instruction bottom-up.
814 void RegPressureTracker::
815 getUpwardPressure(const MachineInstr *MI,
816 std::vector<unsigned> &PressureResult,
817 std::vector<unsigned> &MaxPressureResult) {
818 // Snapshot pressure.
819 PressureResult = CurrSetPressure;
820 MaxPressureResult = P.MaxSetPressure;
822 bumpUpwardPressure(MI);
824 // Current pressure becomes the result. Restore current pressure.
825 P.MaxSetPressure.swap(MaxPressureResult);
826 CurrSetPressure.swap(PressureResult);
829 /// Get the pressure of each PSet after traversing this instruction top-down.
830 void RegPressureTracker::
831 getDownwardPressure(const MachineInstr *MI,
832 std::vector<unsigned> &PressureResult,
833 std::vector<unsigned> &MaxPressureResult) {
834 // Snapshot pressure.
835 PressureResult = CurrSetPressure;
836 MaxPressureResult = P.MaxSetPressure;
838 bumpDownwardPressure(MI);
840 // Current pressure becomes the result. Restore current pressure.
841 P.MaxSetPressure.swap(MaxPressureResult);
842 CurrSetPressure.swap(PressureResult);