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) const {
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 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
186 if (RequireIntervals)
187 static_cast<IntervalPressure&>(P).reset();
189 static_cast<RegionPressure&>(P).reset();
190 P.MaxSetPressure = CurrSetPressure;
192 LivePhysRegs.clear();
193 LivePhysRegs.setUniverse(TRI->getNumRegs());
194 LiveVirtRegs.clear();
195 LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
198 /// Does this pressure result have a valid top position and live ins.
199 bool RegPressureTracker::isTopClosed() const {
200 if (RequireIntervals)
201 return static_cast<IntervalPressure&>(P).TopIdx.isValid();
202 return (static_cast<RegionPressure&>(P).TopPos ==
203 MachineBasicBlock::const_iterator());
206 /// Does this pressure result have a valid bottom position and live outs.
207 bool RegPressureTracker::isBottomClosed() const {
208 if (RequireIntervals)
209 return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
210 return (static_cast<RegionPressure&>(P).BottomPos ==
211 MachineBasicBlock::const_iterator());
215 SlotIndex RegPressureTracker::getCurrSlot() const {
216 MachineBasicBlock::const_iterator IdxPos = CurrPos;
217 while (IdxPos != MBB->end() && IdxPos->isDebugValue())
219 if (IdxPos == MBB->end())
220 return LIS->getMBBEndIdx(MBB);
221 return LIS->getInstructionIndex(IdxPos).getRegSlot();
224 /// Set the boundary for the top of the region and summarize live ins.
225 void RegPressureTracker::closeTop() {
226 if (RequireIntervals)
227 static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
229 static_cast<RegionPressure&>(P).TopPos = CurrPos;
231 assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
232 P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
233 P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
234 for (SparseSet<unsigned>::const_iterator I =
235 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
236 P.LiveInRegs.push_back(*I);
237 std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
238 P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
242 /// Set the boundary for the bottom of the region and summarize live outs.
243 void RegPressureTracker::closeBottom() {
244 if (RequireIntervals)
245 static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
247 static_cast<RegionPressure&>(P).BottomPos = CurrPos;
249 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
250 P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
251 P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
252 for (SparseSet<unsigned>::const_iterator I =
253 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
254 P.LiveOutRegs.push_back(*I);
255 std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
256 P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
257 P.LiveOutRegs.end());
260 /// Finalize the region boundaries and record live ins and live outs.
261 void RegPressureTracker::closeRegion() {
262 if (!isTopClosed() && !isBottomClosed()) {
263 assert(LivePhysRegs.empty() && LiveVirtRegs.empty() &&
264 "no region boundary");
267 if (!isBottomClosed())
269 else if (!isTopClosed())
271 // If both top and bottom are closed, do nothing.
274 /// Return true if Reg aliases a register in Regs SparseSet.
275 static bool hasRegAlias(unsigned Reg, SparseSet<unsigned> &Regs,
276 const TargetRegisterInfo *TRI) {
277 assert(!TargetRegisterInfo::isVirtualRegister(Reg) && "only for physregs");
278 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
284 /// Return true if Reg aliases a register in unsorted Regs SmallVector.
285 /// This is only valid for physical registers.
286 static SmallVectorImpl<unsigned>::iterator
287 findRegAlias(unsigned Reg, SmallVectorImpl<unsigned> &Regs,
288 const TargetRegisterInfo *TRI) {
289 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
290 SmallVectorImpl<unsigned>::iterator I =
291 std::find(Regs.begin(), Regs.end(), *AI);
298 /// Return true if Reg can be inserted into Regs SmallVector. For virtual
299 /// register, do a linear search. For physical registers check for aliases.
300 static SmallVectorImpl<unsigned>::iterator
301 findReg(unsigned Reg, bool isVReg, SmallVectorImpl<unsigned> &Regs,
302 const TargetRegisterInfo *TRI) {
304 return std::find(Regs.begin(), Regs.end(), Reg);
305 return findRegAlias(Reg, Regs, TRI);
308 /// Collect this instruction's unique uses and defs into SmallVectors for
309 /// processing defs and uses in order.
310 template<bool isVReg>
311 struct RegisterOperands {
312 SmallVector<unsigned, 8> Uses;
313 SmallVector<unsigned, 8> Defs;
314 SmallVector<unsigned, 8> DeadDefs;
316 /// Push this operand's register onto the correct vector.
317 void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
319 if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end())
320 Uses.push_back(MO.getReg());
324 if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end())
325 DeadDefs.push_back(MO.getReg());
327 else if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
328 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 MachineRegisterInfo *MRI) {
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 (MRI->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, MRI);
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 = getCurrSlot();
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, MRI);
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, MRI);
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 for (unsigned i = 0, e = PhysRegOpers.Defs.size(); i < e; ++i) {
680 unsigned Reg = PhysRegOpers.Defs[i];
681 if (!findReg(Reg, false, PhysRegOpers.Uses, TRI))
682 decreasePhysRegPressure(PhysRegOpers.Defs);
684 for (unsigned i = 0, e = VirtRegOpers.Defs.size(); i < e; ++i) {
685 unsigned Reg = VirtRegOpers.Defs[i];
686 if (!findReg(Reg, true, VirtRegOpers.Uses, TRI))
687 decreaseVirtRegPressure(VirtRegOpers.Defs);
689 // Generate liveness for uses.
690 for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
691 unsigned Reg = PhysRegOpers.Uses[i];
692 if (!hasRegAlias(Reg, LivePhysRegs, TRI))
693 increasePhysRegPressure(Reg);
695 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
696 unsigned Reg = VirtRegOpers.Uses[i];
697 if (!LiveVirtRegs.count(Reg))
698 increaseVirtRegPressure(Reg);
702 /// Consider the pressure increase caused by traversing this instruction
703 /// bottom-up. Find the pressure set with the most change beyond its pressure
704 /// limit based on the tracker's current pressure, and return the change in
705 /// number of register units of that pressure set introduced by this
708 /// This assumes that the current LiveOut set is sufficient.
710 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
711 /// result per-SUnit with enough information to adjust for the current
712 /// scheduling position. But this works as a proof of concept.
713 void RegPressureTracker::
714 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
715 ArrayRef<PressureElement> CriticalPSets,
716 ArrayRef<unsigned> MaxPressureLimit) {
717 // Snapshot Pressure.
718 // FIXME: The snapshot heap space should persist. But I'm planning to
719 // summarize the pressure effect so we don't need to snapshot at all.
720 std::vector<unsigned> SavedPressure = CurrSetPressure;
721 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
723 bumpUpwardPressure(MI);
725 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
726 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
727 MaxPressureLimit, Delta);
728 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
729 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
731 // Restore the tracker's state.
732 P.MaxSetPressure.swap(SavedMaxPressure);
733 CurrSetPressure.swap(SavedPressure);
736 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
737 static bool findUseBetween(unsigned Reg,
738 SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
739 const MachineRegisterInfo *MRI,
740 const LiveIntervals *LIS) {
741 for (MachineRegisterInfo::use_nodbg_iterator
742 UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
743 UI != UE; UI.skipInstruction()) {
744 const MachineInstr* MI = &*UI;
745 SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
746 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
752 /// Record the downward impact of a single instruction on current register
753 /// pressure. Unlike the advance/recede pressure tracking interface, this does
754 /// not discover live in/outs.
756 /// This is intended for speculative queries. It leaves pressure inconsistent
757 /// with the current position, so must be restored by the caller.
758 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
759 // Account for register pressure similar to RegPressureTracker::recede().
760 PhysRegOperands PhysRegOpers;
761 VirtRegOperands VirtRegOpers;
762 collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, MRI);
764 // Kill liveness at last uses. Assume allocatable physregs are single-use
765 // rather than checking LiveIntervals.
766 decreasePhysRegPressure(PhysRegOpers.Uses);
767 if (RequireIntervals) {
768 SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
769 for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
770 unsigned Reg = VirtRegOpers.Uses[i];
771 const LiveInterval *LI = &LIS->getInterval(Reg);
772 // FIXME: allow the caller to pass in the list of vreg uses that remain to
773 // be bottom-scheduled to avoid searching uses at each query.
774 SlotIndex CurrIdx = getCurrSlot();
775 if (LI->killedAt(SlotIdx)
776 && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
777 decreaseVirtRegPressure(Reg);
782 // Generate liveness for defs.
783 increasePhysRegPressure(PhysRegOpers.Defs);
784 increaseVirtRegPressure(VirtRegOpers.Defs);
786 // Boost pressure for all dead defs together.
787 increasePhysRegPressure(PhysRegOpers.DeadDefs);
788 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
789 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
790 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
793 /// Consider the pressure increase caused by traversing this instruction
794 /// top-down. Find the register class with the most change in its pressure limit
795 /// based on the tracker's current pressure, and return the number of excess
796 /// register units of that pressure set introduced by this instruction.
798 /// This assumes that the current LiveIn set is sufficient.
799 void RegPressureTracker::
800 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
801 ArrayRef<PressureElement> CriticalPSets,
802 ArrayRef<unsigned> MaxPressureLimit) {
803 // Snapshot Pressure.
804 std::vector<unsigned> SavedPressure = CurrSetPressure;
805 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
807 bumpDownwardPressure(MI);
809 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
810 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
811 MaxPressureLimit, Delta);
812 assert(Delta.CriticalMax.UnitIncrease >= 0 &&
813 Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
815 // Restore the tracker's state.
816 P.MaxSetPressure.swap(SavedMaxPressure);
817 CurrSetPressure.swap(SavedPressure);
820 /// Get the pressure of each PSet after traversing this instruction bottom-up.
821 void RegPressureTracker::
822 getUpwardPressure(const MachineInstr *MI,
823 std::vector<unsigned> &PressureResult,
824 std::vector<unsigned> &MaxPressureResult) {
825 // Snapshot pressure.
826 PressureResult = CurrSetPressure;
827 MaxPressureResult = P.MaxSetPressure;
829 bumpUpwardPressure(MI);
831 // Current pressure becomes the result. Restore current pressure.
832 P.MaxSetPressure.swap(MaxPressureResult);
833 CurrSetPressure.swap(PressureResult);
836 /// Get the pressure of each PSet after traversing this instruction top-down.
837 void RegPressureTracker::
838 getDownwardPressure(const MachineInstr *MI,
839 std::vector<unsigned> &PressureResult,
840 std::vector<unsigned> &MaxPressureResult) {
841 // Snapshot pressure.
842 PressureResult = CurrSetPressure;
843 MaxPressureResult = P.MaxSetPressure;
845 bumpDownwardPressure(MI);
847 // Current pressure becomes the result. Restore current pressure.
848 P.MaxSetPressure.swap(MaxPressureResult);
849 CurrSetPressure.swap(PressureResult);