1//===- RegisterPressure.cpp - Dynamic Register Pressure -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the RegisterPressure class which can be used to track
10// MachineInstr level register pressure.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/RegisterPressure.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/CodeGen/LiveInterval.h"
19#include "llvm/CodeGen/LiveIntervals.h"
20#include "llvm/CodeGen/MachineBasicBlock.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/CodeGen/MachineInstrBundle.h"
24#include "llvm/CodeGen/MachineOperand.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/CodeGen/RegisterClassInfo.h"
27#include "llvm/CodeGen/SlotIndexes.h"
28#include "llvm/CodeGen/TargetRegisterInfo.h"
29#include "llvm/CodeGen/TargetSubtargetInfo.h"
30#include "llvm/Config/llvm-config.h"
31#include "llvm/MC/LaneBitmask.h"
32#include "llvm/Support/Compiler.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/ErrorHandling.h"
35#include "llvm/Support/raw_ostream.h"
36#include <algorithm>
37#include <cassert>
38#include <cstdint>
39#include <cstdlib>
40#include <cstring>
41#include <iterator>
42#include <limits>
43#include <utility>
44#include <vector>
45
46using namespace llvm;
47
48/// Increase pressure for each pressure set provided by TargetRegisterInfo.
49static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
50 const MachineRegisterInfo &MRI, unsigned Reg,
51 LaneBitmask PrevMask, LaneBitmask NewMask) {
52 assert((PrevMask & ~NewMask).none() && "Must not remove bits");
53 if (PrevMask.any() || NewMask.none())
54 return;
55
56 PSetIterator PSetI = MRI.getPressureSets(RegUnit: Reg);
57 unsigned Weight = PSetI.getWeight();
58 for (; PSetI.isValid(); ++PSetI)
59 CurrSetPressure[*PSetI] += Weight;
60}
61
62/// Decrease pressure for each pressure set provided by TargetRegisterInfo.
63static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
64 const MachineRegisterInfo &MRI, Register Reg,
65 LaneBitmask PrevMask, LaneBitmask NewMask) {
66 assert((NewMask & ~PrevMask).none() && "Must not add bits");
67 if (NewMask.any() || PrevMask.none())
68 return;
69
70 PSetIterator PSetI = MRI.getPressureSets(RegUnit: Reg);
71 unsigned Weight = PSetI.getWeight();
72 for (; PSetI.isValid(); ++PSetI) {
73 assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow");
74 CurrSetPressure[*PSetI] -= Weight;
75 }
76}
77
78#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
79LLVM_DUMP_METHOD
80void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
81 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] << ' ';
85 }
86 }
87 dbgs() << "\n";
88}
89
90LLVM_DUMP_METHOD
91void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
92 dbgs() << "Max Pressure: ";
93 dumpRegSetPressure(MaxSetPressure, TRI);
94 dbgs() << "Live In: ";
95 for (const VRegMaskOrUnit &P : LiveInRegs) {
96 dbgs() << printVRegOrUnit(P.RegUnit, TRI);
97 if (!P.LaneMask.all())
98 dbgs() << ':' << PrintLaneMask(P.LaneMask);
99 dbgs() << ' ';
100 }
101 dbgs() << '\n';
102 dbgs() << "Live Out: ";
103 for (const VRegMaskOrUnit &P : LiveOutRegs) {
104 dbgs() << printVRegOrUnit(P.RegUnit, TRI);
105 if (!P.LaneMask.all())
106 dbgs() << ':' << PrintLaneMask(P.LaneMask);
107 dbgs() << ' ';
108 }
109 dbgs() << '\n';
110}
111
112LLVM_DUMP_METHOD
113void RegPressureTracker::dump() const {
114 if (!isTopClosed() || !isBottomClosed()) {
115 dbgs() << "Curr Pressure: ";
116 dumpRegSetPressure(CurrSetPressure, TRI);
117 }
118 P.dump(TRI);
119}
120
121LLVM_DUMP_METHOD
122void PressureDiff::dump(const TargetRegisterInfo &TRI) const {
123 const char *sep = "";
124 for (const PressureChange &Change : *this) {
125 if (!Change.isValid())
126 break;
127 dbgs() << sep << TRI.getRegPressureSetName(Change.getPSet())
128 << " " << Change.getUnitInc();
129 sep = " ";
130 }
131 dbgs() << '\n';
132}
133
134LLVM_DUMP_METHOD
135void PressureChange::dump() const {
136 dbgs() << "[" << getPSetOrMax() << ", " << getUnitInc() << "]\n";
137}
138
139void RegPressureDelta::dump() const {
140 dbgs() << "[Excess=";
141 Excess.dump();
142 dbgs() << ", CriticalMax=";
143 CriticalMax.dump();
144 dbgs() << ", CurrentMax=";
145 CurrentMax.dump();
146 dbgs() << "]\n";
147}
148
149#endif
150
151void RegPressureTracker::increaseRegPressure(Register RegUnit,
152 LaneBitmask PreviousMask,
153 LaneBitmask NewMask) {
154 if (PreviousMask.any() || NewMask.none())
155 return;
156
157 PSetIterator PSetI = MRI->getPressureSets(RegUnit);
158 unsigned Weight = PSetI.getWeight();
159 for (; PSetI.isValid(); ++PSetI) {
160 CurrSetPressure[*PSetI] += Weight;
161 P.MaxSetPressure[*PSetI] =
162 std::max(a: P.MaxSetPressure[*PSetI], b: CurrSetPressure[*PSetI]);
163 }
164}
165
166void RegPressureTracker::decreaseRegPressure(Register RegUnit,
167 LaneBitmask PreviousMask,
168 LaneBitmask NewMask) {
169 decreaseSetPressure(CurrSetPressure, MRI: *MRI, Reg: RegUnit, PrevMask: PreviousMask, NewMask);
170}
171
172/// Clear the result so it can be used for another round of pressure tracking.
173void IntervalPressure::reset() {
174 TopIdx = BottomIdx = SlotIndex();
175 MaxSetPressure.clear();
176 LiveInRegs.clear();
177 LiveOutRegs.clear();
178}
179
180/// Clear the result so it can be used for another round of pressure tracking.
181void RegionPressure::reset() {
182 TopPos = BottomPos = MachineBasicBlock::const_iterator();
183 MaxSetPressure.clear();
184 LiveInRegs.clear();
185 LiveOutRegs.clear();
186}
187
188/// If the current top is not less than or equal to the next index, open it.
189/// We happen to need the SlotIndex for the next top for pressure update.
190void IntervalPressure::openTop(SlotIndex NextTop) {
191 if (TopIdx <= NextTop)
192 return;
193 TopIdx = SlotIndex();
194 LiveInRegs.clear();
195}
196
197/// If the current top is the previous instruction (before receding), open it.
198void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
199 if (TopPos != PrevTop)
200 return;
201 TopPos = MachineBasicBlock::const_iterator();
202 LiveInRegs.clear();
203}
204
205/// If the current bottom is not greater than the previous index, open it.
206void IntervalPressure::openBottom(SlotIndex PrevBottom) {
207 if (BottomIdx > PrevBottom)
208 return;
209 BottomIdx = SlotIndex();
210 LiveInRegs.clear();
211}
212
213/// If the current bottom is the previous instr (before advancing), open it.
214void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
215 if (BottomPos != PrevBottom)
216 return;
217 BottomPos = MachineBasicBlock::const_iterator();
218 LiveInRegs.clear();
219}
220
221void LiveRegSet::init(const MachineRegisterInfo &MRI) {
222 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
223 unsigned NumRegUnits = TRI.getNumRegs();
224 unsigned NumVirtRegs = MRI.getNumVirtRegs();
225 Regs.setUniverse(NumRegUnits + NumVirtRegs);
226 this->NumRegUnits = NumRegUnits;
227}
228
229void LiveRegSet::clear() {
230 Regs.clear();
231}
232
233static const LiveRange *getLiveRange(const LiveIntervals &LIS, unsigned Reg) {
234 if (Register::isVirtualRegister(Reg))
235 return &LIS.getInterval(Reg);
236 return LIS.getCachedRegUnit(Unit: Reg);
237}
238
239void RegPressureTracker::reset() {
240 MBB = nullptr;
241 LIS = nullptr;
242
243 CurrSetPressure.clear();
244 LiveThruPressure.clear();
245 P.MaxSetPressure.clear();
246
247 if (RequireIntervals)
248 static_cast<IntervalPressure&>(P).reset();
249 else
250 static_cast<RegionPressure&>(P).reset();
251
252 LiveRegs.clear();
253 UntiedDefs.clear();
254}
255
256/// Setup the RegPressureTracker.
257///
258/// TODO: Add support for pressure without LiveIntervals.
259void RegPressureTracker::init(const MachineFunction *mf,
260 const RegisterClassInfo *rci,
261 const LiveIntervals *lis,
262 const MachineBasicBlock *mbb,
263 MachineBasicBlock::const_iterator pos,
264 bool TrackLaneMasks, bool TrackUntiedDefs) {
265 reset();
266
267 MF = mf;
268 TRI = MF->getSubtarget().getRegisterInfo();
269 RCI = rci;
270 MRI = &MF->getRegInfo();
271 MBB = mbb;
272 this->TrackUntiedDefs = TrackUntiedDefs;
273 this->TrackLaneMasks = TrackLaneMasks;
274
275 if (RequireIntervals) {
276 assert(lis && "IntervalPressure requires LiveIntervals");
277 LIS = lis;
278 }
279
280 CurrPos = pos;
281 CurrSetPressure.assign(n: TRI->getNumRegPressureSets(), val: 0);
282
283 P.MaxSetPressure = CurrSetPressure;
284
285 LiveRegs.init(MRI: *MRI);
286 if (TrackUntiedDefs)
287 UntiedDefs.setUniverse(MRI->getNumVirtRegs());
288}
289
290/// Does this pressure result have a valid top position and live ins.
291bool RegPressureTracker::isTopClosed() const {
292 if (RequireIntervals)
293 return static_cast<IntervalPressure&>(P).TopIdx.isValid();
294 return (static_cast<RegionPressure&>(P).TopPos ==
295 MachineBasicBlock::const_iterator());
296}
297
298/// Does this pressure result have a valid bottom position and live outs.
299bool RegPressureTracker::isBottomClosed() const {
300 if (RequireIntervals)
301 return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
302 return (static_cast<RegionPressure&>(P).BottomPos ==
303 MachineBasicBlock::const_iterator());
304}
305
306SlotIndex RegPressureTracker::getCurrSlot() const {
307 MachineBasicBlock::const_iterator IdxPos =
308 skipDebugInstructionsForward(It: CurrPos, End: MBB->end());
309 if (IdxPos == MBB->end())
310 return LIS->getMBBEndIdx(mbb: MBB);
311 return LIS->getInstructionIndex(Instr: *IdxPos).getRegSlot();
312}
313
314/// Set the boundary for the top of the region and summarize live ins.
315void RegPressureTracker::closeTop() {
316 if (RequireIntervals)
317 static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
318 else
319 static_cast<RegionPressure&>(P).TopPos = CurrPos;
320
321 assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
322 P.LiveInRegs.reserve(N: LiveRegs.size());
323 LiveRegs.appendTo(To&: P.LiveInRegs);
324}
325
326/// Set the boundary for the bottom of the region and summarize live outs.
327void RegPressureTracker::closeBottom() {
328 if (RequireIntervals)
329 static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
330 else
331 static_cast<RegionPressure&>(P).BottomPos = CurrPos;
332
333 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
334 P.LiveOutRegs.reserve(N: LiveRegs.size());
335 LiveRegs.appendTo(To&: P.LiveOutRegs);
336}
337
338/// Finalize the region boundaries and record live ins and live outs.
339void RegPressureTracker::closeRegion() {
340 if (!isTopClosed() && !isBottomClosed()) {
341 assert(LiveRegs.size() == 0 && "no region boundary");
342 return;
343 }
344 if (!isBottomClosed())
345 closeBottom();
346 else if (!isTopClosed())
347 closeTop();
348 // If both top and bottom are closed, do nothing.
349}
350
351/// The register tracker is unaware of global liveness so ignores normal
352/// live-thru ranges. However, two-address or coalesced chains can also lead
353/// to live ranges with no holes. Count these to inform heuristics that we
354/// can never drop below this pressure.
355void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
356 LiveThruPressure.assign(n: TRI->getNumRegPressureSets(), val: 0);
357 assert(isBottomClosed() && "need bottom-up tracking to intialize.");
358 for (const VRegMaskOrUnit &Pair : P.LiveOutRegs) {
359 Register RegUnit = Pair.RegUnit;
360 if (RegUnit.isVirtual() && !RPTracker.hasUntiedDef(VirtReg: RegUnit))
361 increaseSetPressure(CurrSetPressure&: LiveThruPressure, MRI: *MRI, Reg: RegUnit,
362 PrevMask: LaneBitmask::getNone(), NewMask: Pair.LaneMask);
363 }
364}
365
366static LaneBitmask getRegLanes(ArrayRef<VRegMaskOrUnit> RegUnits,
367 Register RegUnit) {
368 auto I = llvm::find_if(Range&: RegUnits, P: [RegUnit](const VRegMaskOrUnit Other) {
369 return Other.RegUnit == RegUnit;
370 });
371 if (I == RegUnits.end())
372 return LaneBitmask::getNone();
373 return I->LaneMask;
374}
375
376static void addRegLanes(SmallVectorImpl<VRegMaskOrUnit> &RegUnits,
377 VRegMaskOrUnit Pair) {
378 Register RegUnit = Pair.RegUnit;
379 assert(Pair.LaneMask.any());
380 auto I = llvm::find_if(Range&: RegUnits, P: [RegUnit](const VRegMaskOrUnit Other) {
381 return Other.RegUnit == RegUnit;
382 });
383 if (I == RegUnits.end()) {
384 RegUnits.push_back(Elt: Pair);
385 } else {
386 I->LaneMask |= Pair.LaneMask;
387 }
388}
389
390static void setRegZero(SmallVectorImpl<VRegMaskOrUnit> &RegUnits,
391 Register RegUnit) {
392 auto I = llvm::find_if(Range&: RegUnits, P: [RegUnit](const VRegMaskOrUnit Other) {
393 return Other.RegUnit == RegUnit;
394 });
395 if (I == RegUnits.end()) {
396 RegUnits.emplace_back(Args&: RegUnit, Args: LaneBitmask::getNone());
397 } else {
398 I->LaneMask = LaneBitmask::getNone();
399 }
400}
401
402static void removeRegLanes(SmallVectorImpl<VRegMaskOrUnit> &RegUnits,
403 VRegMaskOrUnit Pair) {
404 Register RegUnit = Pair.RegUnit;
405 assert(Pair.LaneMask.any());
406 auto I = llvm::find_if(Range&: RegUnits, P: [RegUnit](const VRegMaskOrUnit Other) {
407 return Other.RegUnit == RegUnit;
408 });
409 if (I != RegUnits.end()) {
410 I->LaneMask &= ~Pair.LaneMask;
411 if (I->LaneMask.none())
412 RegUnits.erase(CI: I);
413 }
414}
415
416static LaneBitmask
417getLanesWithProperty(const LiveIntervals &LIS, const MachineRegisterInfo &MRI,
418 bool TrackLaneMasks, Register RegUnit, SlotIndex Pos,
419 LaneBitmask SafeDefault,
420 bool (*Property)(const LiveRange &LR, SlotIndex Pos)) {
421 if (RegUnit.isVirtual()) {
422 const LiveInterval &LI = LIS.getInterval(Reg: RegUnit);
423 LaneBitmask Result;
424 if (TrackLaneMasks && LI.hasSubRanges()) {
425 for (const LiveInterval::SubRange &SR : LI.subranges()) {
426 if (Property(SR, Pos))
427 Result |= SR.LaneMask;
428 }
429 } else if (Property(LI, Pos)) {
430 Result = TrackLaneMasks ? MRI.getMaxLaneMaskForVReg(Reg: RegUnit)
431 : LaneBitmask::getAll();
432 }
433
434 return Result;
435 } else {
436 const LiveRange *LR = LIS.getCachedRegUnit(Unit: RegUnit);
437 // Be prepared for missing liveranges: We usually do not compute liveranges
438 // for physical registers on targets with many registers (GPUs).
439 if (LR == nullptr)
440 return SafeDefault;
441 return Property(*LR, Pos) ? LaneBitmask::getAll() : LaneBitmask::getNone();
442 }
443}
444
445static LaneBitmask getLiveLanesAt(const LiveIntervals &LIS,
446 const MachineRegisterInfo &MRI,
447 bool TrackLaneMasks, Register RegUnit,
448 SlotIndex Pos) {
449 return getLanesWithProperty(LIS, MRI, TrackLaneMasks, RegUnit, Pos,
450 SafeDefault: LaneBitmask::getAll(),
451 Property: [](const LiveRange &LR, SlotIndex Pos) {
452 return LR.liveAt(index: Pos);
453 });
454}
455
456namespace {
457
458/// Collect this instruction's unique uses and defs into SmallVectors for
459/// processing defs and uses in order.
460///
461/// FIXME: always ignore tied opers
462class RegisterOperandsCollector {
463 friend class llvm::RegisterOperands;
464
465 RegisterOperands &RegOpers;
466 const TargetRegisterInfo &TRI;
467 const MachineRegisterInfo &MRI;
468 bool IgnoreDead;
469
470 RegisterOperandsCollector(RegisterOperands &RegOpers,
471 const TargetRegisterInfo &TRI,
472 const MachineRegisterInfo &MRI, bool IgnoreDead)
473 : RegOpers(RegOpers), TRI(TRI), MRI(MRI), IgnoreDead(IgnoreDead) {}
474
475 void collectInstr(const MachineInstr &MI) const {
476 for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
477 collectOperand(MO: *OperI);
478
479 // Remove redundant physreg dead defs.
480 for (const VRegMaskOrUnit &P : RegOpers.Defs)
481 removeRegLanes(RegUnits&: RegOpers.DeadDefs, Pair: P);
482 }
483
484 void collectInstrLanes(const MachineInstr &MI) const {
485 for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
486 collectOperandLanes(MO: *OperI);
487
488 // Remove redundant physreg dead defs.
489 for (const VRegMaskOrUnit &P : RegOpers.Defs)
490 removeRegLanes(RegUnits&: RegOpers.DeadDefs, Pair: P);
491 }
492
493 /// Push this operand's register onto the correct vectors.
494 void collectOperand(const MachineOperand &MO) const {
495 if (!MO.isReg() || !MO.getReg())
496 return;
497 Register Reg = MO.getReg();
498 if (MO.isUse()) {
499 if (!MO.isUndef() && !MO.isInternalRead())
500 pushReg(Reg, RegUnits&: RegOpers.Uses);
501 } else {
502 assert(MO.isDef());
503 // Subregister definitions may imply a register read.
504 if (MO.readsReg())
505 pushReg(Reg, RegUnits&: RegOpers.Uses);
506
507 if (MO.isDead()) {
508 if (!IgnoreDead)
509 pushReg(Reg, RegUnits&: RegOpers.DeadDefs);
510 } else
511 pushReg(Reg, RegUnits&: RegOpers.Defs);
512 }
513 }
514
515 void pushReg(Register Reg, SmallVectorImpl<VRegMaskOrUnit> &RegUnits) const {
516 if (Reg.isVirtual()) {
517 addRegLanes(RegUnits, Pair: VRegMaskOrUnit(Reg, LaneBitmask::getAll()));
518 } else if (MRI.isAllocatable(PhysReg: Reg)) {
519 for (MCRegUnit Unit : TRI.regunits(Reg: Reg.asMCReg()))
520 addRegLanes(RegUnits, Pair: VRegMaskOrUnit(Unit, LaneBitmask::getAll()));
521 }
522 }
523
524 void collectOperandLanes(const MachineOperand &MO) const {
525 if (!MO.isReg() || !MO.getReg())
526 return;
527 Register Reg = MO.getReg();
528 unsigned SubRegIdx = MO.getSubReg();
529 if (MO.isUse()) {
530 if (!MO.isUndef() && !MO.isInternalRead())
531 pushRegLanes(Reg, SubRegIdx, RegUnits&: RegOpers.Uses);
532 } else {
533 assert(MO.isDef());
534 // Treat read-undef subreg defs as definitions of the whole register.
535 if (MO.isUndef())
536 SubRegIdx = 0;
537
538 if (MO.isDead()) {
539 if (!IgnoreDead)
540 pushRegLanes(Reg, SubRegIdx, RegUnits&: RegOpers.DeadDefs);
541 } else
542 pushRegLanes(Reg, SubRegIdx, RegUnits&: RegOpers.Defs);
543 }
544 }
545
546 void pushRegLanes(Register Reg, unsigned SubRegIdx,
547 SmallVectorImpl<VRegMaskOrUnit> &RegUnits) const {
548 if (Reg.isVirtual()) {
549 LaneBitmask LaneMask = SubRegIdx != 0
550 ? TRI.getSubRegIndexLaneMask(SubIdx: SubRegIdx)
551 : MRI.getMaxLaneMaskForVReg(Reg);
552 addRegLanes(RegUnits, Pair: VRegMaskOrUnit(Reg, LaneMask));
553 } else if (MRI.isAllocatable(PhysReg: Reg)) {
554 for (MCRegUnit Unit : TRI.regunits(Reg: Reg.asMCReg()))
555 addRegLanes(RegUnits, Pair: VRegMaskOrUnit(Unit, LaneBitmask::getAll()));
556 }
557 }
558};
559
560} // end anonymous namespace
561
562void RegisterOperands::collect(const MachineInstr &MI,
563 const TargetRegisterInfo &TRI,
564 const MachineRegisterInfo &MRI,
565 bool TrackLaneMasks, bool IgnoreDead) {
566 RegisterOperandsCollector Collector(*this, TRI, MRI, IgnoreDead);
567 if (TrackLaneMasks)
568 Collector.collectInstrLanes(MI);
569 else
570 Collector.collectInstr(MI);
571}
572
573void RegisterOperands::detectDeadDefs(const MachineInstr &MI,
574 const LiveIntervals &LIS) {
575 SlotIndex SlotIdx = LIS.getInstructionIndex(Instr: MI);
576 for (auto *RI = Defs.begin(); RI != Defs.end(); /*empty*/) {
577 Register Reg = RI->RegUnit;
578 const LiveRange *LR = getLiveRange(LIS, Reg);
579 if (LR != nullptr) {
580 LiveQueryResult LRQ = LR->Query(Idx: SlotIdx);
581 if (LRQ.isDeadDef()) {
582 // LiveIntervals knows this is a dead even though it's MachineOperand is
583 // not flagged as such.
584 DeadDefs.push_back(Elt: *RI);
585 RI = Defs.erase(CI: RI);
586 continue;
587 }
588 }
589 ++RI;
590 }
591}
592
593void RegisterOperands::adjustLaneLiveness(const LiveIntervals &LIS,
594 const MachineRegisterInfo &MRI,
595 SlotIndex Pos,
596 MachineInstr *AddFlagsMI) {
597 for (auto *I = Defs.begin(); I != Defs.end();) {
598 LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, TrackLaneMasks: true, RegUnit: I->RegUnit,
599 Pos: Pos.getDeadSlot());
600 // If the def is all that is live after the instruction, then in case
601 // of a subregister def we need a read-undef flag.
602 Register RegUnit = I->RegUnit;
603 if (RegUnit.isVirtual() && AddFlagsMI != nullptr &&
604 (LiveAfter & ~I->LaneMask).none())
605 AddFlagsMI->setRegisterDefReadUndef(Reg: RegUnit);
606
607 LaneBitmask ActualDef = I->LaneMask & LiveAfter;
608 if (ActualDef.none()) {
609 I = Defs.erase(CI: I);
610 } else {
611 I->LaneMask = ActualDef;
612 ++I;
613 }
614 }
615
616 // For uses just copy the information from LIS.
617 for (auto &[RegUnit, LaneMask] : Uses)
618 LaneMask = getLiveLanesAt(LIS, MRI, TrackLaneMasks: true, RegUnit, Pos: Pos.getBaseIndex());
619
620 if (AddFlagsMI != nullptr) {
621 for (const VRegMaskOrUnit &P : DeadDefs) {
622 Register RegUnit = P.RegUnit;
623 if (!RegUnit.isVirtual())
624 continue;
625 LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, TrackLaneMasks: true, RegUnit,
626 Pos: Pos.getDeadSlot());
627 if (LiveAfter.none())
628 AddFlagsMI->setRegisterDefReadUndef(Reg: RegUnit);
629 }
630 }
631}
632
633/// Initialize an array of N PressureDiffs.
634void PressureDiffs::init(unsigned N) {
635 Size = N;
636 if (N <= Max) {
637 memset(s: PDiffArray, c: 0, n: N * sizeof(PressureDiff));
638 return;
639 }
640 Max = Size;
641 free(ptr: PDiffArray);
642 PDiffArray = static_cast<PressureDiff*>(safe_calloc(Count: N, Sz: sizeof(PressureDiff)));
643}
644
645void PressureDiffs::addInstruction(unsigned Idx,
646 const RegisterOperands &RegOpers,
647 const MachineRegisterInfo &MRI) {
648 PressureDiff &PDiff = (*this)[Idx];
649 assert(!PDiff.begin()->isValid() && "stale PDiff");
650 for (const VRegMaskOrUnit &P : RegOpers.Defs)
651 PDiff.addPressureChange(RegUnit: P.RegUnit, IsDec: true, MRI: &MRI);
652
653 for (const VRegMaskOrUnit &P : RegOpers.Uses)
654 PDiff.addPressureChange(RegUnit: P.RegUnit, IsDec: false, MRI: &MRI);
655}
656
657/// Add a change in pressure to the pressure diff of a given instruction.
658void PressureDiff::addPressureChange(Register RegUnit, bool IsDec,
659 const MachineRegisterInfo *MRI) {
660 PSetIterator PSetI = MRI->getPressureSets(RegUnit);
661 int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight();
662 for (; PSetI.isValid(); ++PSetI) {
663 // Find an existing entry in the pressure diff for this PSet.
664 PressureDiff::iterator I = nonconst_begin(), E = nonconst_end();
665 for (; I != E && I->isValid(); ++I) {
666 if (I->getPSet() >= *PSetI)
667 break;
668 }
669 // If all pressure sets are more constrained, skip the remaining PSets.
670 if (I == E)
671 break;
672 // Insert this PressureChange.
673 if (!I->isValid() || I->getPSet() != *PSetI) {
674 PressureChange PTmp = PressureChange(*PSetI);
675 for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J)
676 std::swap(a&: *J, b&: PTmp);
677 }
678 // Update the units for this pressure set.
679 unsigned NewUnitInc = I->getUnitInc() + Weight;
680 if (NewUnitInc != 0) {
681 I->setUnitInc(NewUnitInc);
682 } else {
683 // Remove entry
684 PressureDiff::iterator J;
685 for (J = std::next(x: I); J != E && J->isValid(); ++J, ++I)
686 *I = *J;
687 *I = PressureChange();
688 }
689 }
690}
691
692/// Force liveness of registers.
693void RegPressureTracker::addLiveRegs(ArrayRef<VRegMaskOrUnit> Regs) {
694 for (const VRegMaskOrUnit &P : Regs) {
695 LaneBitmask PrevMask = LiveRegs.insert(Pair: P);
696 LaneBitmask NewMask = PrevMask | P.LaneMask;
697 increaseRegPressure(RegUnit: P.RegUnit, PreviousMask: PrevMask, NewMask);
698 }
699}
700
701void RegPressureTracker::discoverLiveInOrOut(
702 VRegMaskOrUnit Pair, SmallVectorImpl<VRegMaskOrUnit> &LiveInOrOut) {
703 assert(Pair.LaneMask.any());
704
705 Register RegUnit = Pair.RegUnit;
706 auto I = llvm::find_if(Range&: LiveInOrOut, P: [RegUnit](const VRegMaskOrUnit &Other) {
707 return Other.RegUnit == RegUnit;
708 });
709 LaneBitmask PrevMask;
710 LaneBitmask NewMask;
711 if (I == LiveInOrOut.end()) {
712 PrevMask = LaneBitmask::getNone();
713 NewMask = Pair.LaneMask;
714 LiveInOrOut.push_back(Elt: Pair);
715 } else {
716 PrevMask = I->LaneMask;
717 NewMask = PrevMask | Pair.LaneMask;
718 I->LaneMask = NewMask;
719 }
720 increaseSetPressure(CurrSetPressure&: P.MaxSetPressure, MRI: *MRI, Reg: RegUnit, PrevMask, NewMask);
721}
722
723void RegPressureTracker::discoverLiveIn(VRegMaskOrUnit Pair) {
724 discoverLiveInOrOut(Pair, LiveInOrOut&: P.LiveInRegs);
725}
726
727void RegPressureTracker::discoverLiveOut(VRegMaskOrUnit Pair) {
728 discoverLiveInOrOut(Pair, LiveInOrOut&: P.LiveOutRegs);
729}
730
731void RegPressureTracker::bumpDeadDefs(ArrayRef<VRegMaskOrUnit> DeadDefs) {
732 for (const VRegMaskOrUnit &P : DeadDefs) {
733 Register Reg = P.RegUnit;
734 LaneBitmask LiveMask = LiveRegs.contains(Reg);
735 LaneBitmask BumpedMask = LiveMask | P.LaneMask;
736 increaseRegPressure(RegUnit: Reg, PreviousMask: LiveMask, NewMask: BumpedMask);
737 }
738 for (const VRegMaskOrUnit &P : DeadDefs) {
739 Register Reg = P.RegUnit;
740 LaneBitmask LiveMask = LiveRegs.contains(Reg);
741 LaneBitmask BumpedMask = LiveMask | P.LaneMask;
742 decreaseRegPressure(RegUnit: Reg, PreviousMask: BumpedMask, NewMask: LiveMask);
743 }
744}
745
746/// Recede across the previous instruction. If LiveUses is provided, record any
747/// RegUnits that are made live by the current instruction's uses. This includes
748/// registers that are both defined and used by the instruction. If a pressure
749/// difference pointer is provided record the changes is pressure caused by this
750/// instruction independent of liveness.
751void RegPressureTracker::recede(const RegisterOperands &RegOpers,
752 SmallVectorImpl<VRegMaskOrUnit> *LiveUses) {
753 assert(!CurrPos->isDebugOrPseudoInstr());
754
755 // Boost pressure for all dead defs together.
756 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
757
758 // Kill liveness at live defs.
759 // TODO: consider earlyclobbers?
760 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
761 Register Reg = Def.RegUnit;
762
763 LaneBitmask PreviousMask = LiveRegs.erase(Pair: Def);
764 LaneBitmask NewMask = PreviousMask & ~Def.LaneMask;
765
766 LaneBitmask LiveOut = Def.LaneMask & ~PreviousMask;
767 if (LiveOut.any()) {
768 discoverLiveOut(Pair: VRegMaskOrUnit(Reg, LiveOut));
769 // Retroactively model effects on pressure of the live out lanes.
770 increaseSetPressure(CurrSetPressure, MRI: *MRI, Reg, PrevMask: LaneBitmask::getNone(),
771 NewMask: LiveOut);
772 PreviousMask = LiveOut;
773 }
774
775 if (NewMask.none()) {
776 // Add a 0 entry to LiveUses as a marker that the complete vreg has become
777 // dead.
778 if (TrackLaneMasks && LiveUses != nullptr)
779 setRegZero(RegUnits&: *LiveUses, RegUnit: Reg);
780 }
781
782 decreaseRegPressure(RegUnit: Reg, PreviousMask, NewMask);
783 }
784
785 SlotIndex SlotIdx;
786 if (RequireIntervals)
787 SlotIdx = LIS->getInstructionIndex(Instr: *CurrPos).getRegSlot();
788
789 // Generate liveness for uses.
790 for (const VRegMaskOrUnit &Use : RegOpers.Uses) {
791 Register Reg = Use.RegUnit;
792 assert(Use.LaneMask.any());
793 LaneBitmask PreviousMask = LiveRegs.insert(Pair: Use);
794 LaneBitmask NewMask = PreviousMask | Use.LaneMask;
795 if (NewMask == PreviousMask)
796 continue;
797
798 // Did the register just become live?
799 if (PreviousMask.none()) {
800 if (LiveUses != nullptr) {
801 if (!TrackLaneMasks) {
802 addRegLanes(RegUnits&: *LiveUses, Pair: VRegMaskOrUnit(Reg, NewMask));
803 } else {
804 auto I = llvm::find_if(Range&: *LiveUses, P: [Reg](const VRegMaskOrUnit Other) {
805 return Other.RegUnit == Reg;
806 });
807 bool IsRedef = I != LiveUses->end();
808 if (IsRedef) {
809 // ignore re-defs here...
810 assert(I->LaneMask.none());
811 removeRegLanes(RegUnits&: *LiveUses, Pair: VRegMaskOrUnit(Reg, NewMask));
812 } else {
813 addRegLanes(RegUnits&: *LiveUses, Pair: VRegMaskOrUnit(Reg, NewMask));
814 }
815 }
816 }
817
818 // Discover live outs if this may be the first occurance of this register.
819 if (RequireIntervals) {
820 LaneBitmask LiveOut = getLiveThroughAt(RegUnit: Reg, Pos: SlotIdx);
821 if (LiveOut.any())
822 discoverLiveOut(Pair: VRegMaskOrUnit(Reg, LiveOut));
823 }
824 }
825
826 increaseRegPressure(RegUnit: Reg, PreviousMask, NewMask);
827 }
828 if (TrackUntiedDefs) {
829 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
830 Register RegUnit = Def.RegUnit;
831 if (RegUnit.isVirtual() &&
832 (LiveRegs.contains(Reg: RegUnit) & Def.LaneMask).none())
833 UntiedDefs.insert(Val: RegUnit);
834 }
835 }
836}
837
838void RegPressureTracker::recedeSkipDebugValues() {
839 assert(CurrPos != MBB->begin());
840 if (!isBottomClosed())
841 closeBottom();
842
843 // Open the top of the region using block iterators.
844 if (!RequireIntervals && isTopClosed())
845 static_cast<RegionPressure&>(P).openTop(PrevTop: CurrPos);
846
847 // Find the previous instruction.
848 CurrPos = prev_nodbg(It: CurrPos, Begin: MBB->begin());
849
850 SlotIndex SlotIdx;
851 if (RequireIntervals && !CurrPos->isDebugOrPseudoInstr())
852 SlotIdx = LIS->getInstructionIndex(Instr: *CurrPos).getRegSlot();
853
854 // Open the top of the region using slot indexes.
855 if (RequireIntervals && isTopClosed())
856 static_cast<IntervalPressure&>(P).openTop(NextTop: SlotIdx);
857}
858
859void RegPressureTracker::recede(SmallVectorImpl<VRegMaskOrUnit> *LiveUses) {
860 recedeSkipDebugValues();
861 if (CurrPos->isDebugInstr() || CurrPos->isPseudoProbe()) {
862 // It's possible to only have debug_value and pseudo probe instructions and
863 // hit the start of the block.
864 assert(CurrPos == MBB->begin());
865 return;
866 }
867
868 const MachineInstr &MI = *CurrPos;
869 RegisterOperands RegOpers;
870 RegOpers.collect(MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, /*IgnoreDead=*/false);
871 if (TrackLaneMasks) {
872 SlotIndex SlotIdx = LIS->getInstructionIndex(Instr: *CurrPos).getRegSlot();
873 RegOpers.adjustLaneLiveness(LIS: *LIS, MRI: *MRI, Pos: SlotIdx);
874 } else if (RequireIntervals) {
875 RegOpers.detectDeadDefs(MI, LIS: *LIS);
876 }
877
878 recede(RegOpers, LiveUses);
879}
880
881/// Advance across the current instruction.
882void RegPressureTracker::advance(const RegisterOperands &RegOpers) {
883 assert(!TrackUntiedDefs && "unsupported mode");
884 assert(CurrPos != MBB->end());
885 if (!isTopClosed())
886 closeTop();
887
888 SlotIndex SlotIdx;
889 if (RequireIntervals)
890 SlotIdx = getCurrSlot();
891
892 // Open the bottom of the region using slot indexes.
893 if (isBottomClosed()) {
894 if (RequireIntervals)
895 static_cast<IntervalPressure&>(P).openBottom(PrevBottom: SlotIdx);
896 else
897 static_cast<RegionPressure&>(P).openBottom(PrevBottom: CurrPos);
898 }
899
900 for (const VRegMaskOrUnit &Use : RegOpers.Uses) {
901 Register Reg = Use.RegUnit;
902 LaneBitmask LiveMask = LiveRegs.contains(Reg);
903 LaneBitmask LiveIn = Use.LaneMask & ~LiveMask;
904 if (LiveIn.any()) {
905 discoverLiveIn(Pair: VRegMaskOrUnit(Reg, LiveIn));
906 increaseRegPressure(RegUnit: Reg, PreviousMask: LiveMask, NewMask: LiveMask | LiveIn);
907 LiveRegs.insert(Pair: VRegMaskOrUnit(Reg, LiveIn));
908 }
909 // Kill liveness at last uses.
910 if (RequireIntervals) {
911 LaneBitmask LastUseMask = getLastUsedLanes(RegUnit: Reg, Pos: SlotIdx);
912 if (LastUseMask.any()) {
913 LiveRegs.erase(Pair: VRegMaskOrUnit(Reg, LastUseMask));
914 decreaseRegPressure(RegUnit: Reg, PreviousMask: LiveMask, NewMask: LiveMask & ~LastUseMask);
915 }
916 }
917 }
918
919 // Generate liveness for defs.
920 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
921 LaneBitmask PreviousMask = LiveRegs.insert(Pair: Def);
922 LaneBitmask NewMask = PreviousMask | Def.LaneMask;
923 increaseRegPressure(RegUnit: Def.RegUnit, PreviousMask, NewMask);
924 }
925
926 // Boost pressure for all dead defs together.
927 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
928
929 // Find the next instruction.
930 CurrPos = next_nodbg(It: CurrPos, End: MBB->end());
931}
932
933void RegPressureTracker::advance() {
934 const MachineInstr &MI = *CurrPos;
935 RegisterOperands RegOpers;
936 RegOpers.collect(MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, IgnoreDead: false);
937 if (TrackLaneMasks) {
938 SlotIndex SlotIdx = getCurrSlot();
939 RegOpers.adjustLaneLiveness(LIS: *LIS, MRI: *MRI, Pos: SlotIdx);
940 }
941 advance(RegOpers);
942}
943
944/// Find the max change in excess pressure across all sets.
945static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
946 ArrayRef<unsigned> NewPressureVec,
947 RegPressureDelta &Delta,
948 const RegisterClassInfo *RCI,
949 ArrayRef<unsigned> LiveThruPressureVec) {
950 Delta.Excess = PressureChange();
951 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
952 unsigned POld = OldPressureVec[i];
953 unsigned PNew = NewPressureVec[i];
954 int PDiff = (int)PNew - (int)POld;
955 if (!PDiff) // No change in this set in the common case.
956 continue;
957 // Only consider change beyond the limit.
958 unsigned Limit = RCI->getRegPressureSetLimit(Idx: i);
959 if (!LiveThruPressureVec.empty())
960 Limit += LiveThruPressureVec[i];
961
962 if (Limit > POld) {
963 if (Limit > PNew)
964 PDiff = 0; // Under the limit
965 else
966 PDiff = PNew - Limit; // Just exceeded limit.
967 } else if (Limit > PNew)
968 PDiff = Limit - POld; // Just obeyed limit.
969
970 if (PDiff) {
971 Delta.Excess = PressureChange(i);
972 Delta.Excess.setUnitInc(PDiff);
973 break;
974 }
975 }
976}
977
978/// Find the max change in max pressure that either surpasses a critical PSet
979/// limit or exceeds the current MaxPressureLimit.
980///
981/// FIXME: comparing each element of the old and new MaxPressure vectors here is
982/// silly. It's done now to demonstrate the concept but will go away with a
983/// RegPressureTracker API change to work with pressure differences.
984static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
985 ArrayRef<unsigned> NewMaxPressureVec,
986 ArrayRef<PressureChange> CriticalPSets,
987 ArrayRef<unsigned> MaxPressureLimit,
988 RegPressureDelta &Delta) {
989 Delta.CriticalMax = PressureChange();
990 Delta.CurrentMax = PressureChange();
991
992 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
993 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
994 unsigned POld = OldMaxPressureVec[i];
995 unsigned PNew = NewMaxPressureVec[i];
996 if (PNew == POld) // No change in this set in the common case.
997 continue;
998
999 if (!Delta.CriticalMax.isValid()) {
1000 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
1001 ++CritIdx;
1002
1003 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
1004 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
1005 if (PDiff > 0) {
1006 Delta.CriticalMax = PressureChange(i);
1007 Delta.CriticalMax.setUnitInc(PDiff);
1008 }
1009 }
1010 }
1011 // Find the first increase above MaxPressureLimit.
1012 // (Ignores negative MDiff).
1013 if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
1014 Delta.CurrentMax = PressureChange(i);
1015 Delta.CurrentMax.setUnitInc(PNew - POld);
1016 if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
1017 break;
1018 }
1019 }
1020}
1021
1022/// Record the upward impact of a single instruction on current register
1023/// pressure. Unlike the advance/recede pressure tracking interface, this does
1024/// not discover live in/outs.
1025///
1026/// This is intended for speculative queries. It leaves pressure inconsistent
1027/// with the current position, so must be restored by the caller.
1028void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
1029 assert(!MI->isDebugOrPseudoInstr() && "Expect a nondebug instruction.");
1030
1031 SlotIndex SlotIdx;
1032 if (RequireIntervals)
1033 SlotIdx = LIS->getInstructionIndex(Instr: *MI).getRegSlot();
1034
1035 // Account for register pressure similar to RegPressureTracker::recede().
1036 RegisterOperands RegOpers;
1037 RegOpers.collect(MI: *MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, /*IgnoreDead=*/true);
1038 assert(RegOpers.DeadDefs.empty());
1039 if (TrackLaneMasks)
1040 RegOpers.adjustLaneLiveness(LIS: *LIS, MRI: *MRI, Pos: SlotIdx);
1041 else if (RequireIntervals)
1042 RegOpers.detectDeadDefs(MI: *MI, LIS: *LIS);
1043
1044 // Boost max pressure for all dead defs together.
1045 // Since CurrSetPressure and MaxSetPressure
1046 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
1047
1048 // Kill liveness at live defs.
1049 for (const VRegMaskOrUnit &P : RegOpers.Defs) {
1050 Register Reg = P.RegUnit;
1051 LaneBitmask LiveAfter = LiveRegs.contains(Reg);
1052 LaneBitmask UseLanes = getRegLanes(RegUnits: RegOpers.Uses, RegUnit: Reg);
1053 LaneBitmask DefLanes = P.LaneMask;
1054 LaneBitmask LiveBefore = (LiveAfter & ~DefLanes) | UseLanes;
1055
1056 // There may be parts of the register that were dead before the
1057 // instruction, but became live afterwards.
1058 decreaseRegPressure(RegUnit: Reg, PreviousMask: LiveAfter, NewMask: LiveAfter & LiveBefore);
1059 }
1060 // Generate liveness for uses. Also handle any uses which overlap with defs.
1061 for (const VRegMaskOrUnit &P : RegOpers.Uses) {
1062 Register Reg = P.RegUnit;
1063 LaneBitmask LiveAfter = LiveRegs.contains(Reg);
1064 LaneBitmask LiveBefore = LiveAfter | P.LaneMask;
1065 increaseRegPressure(RegUnit: Reg, PreviousMask: LiveAfter, NewMask: LiveBefore);
1066 }
1067}
1068
1069/// Consider the pressure increase caused by traversing this instruction
1070/// bottom-up. Find the pressure set with the most change beyond its pressure
1071/// limit based on the tracker's current pressure, and return the change in
1072/// number of register units of that pressure set introduced by this
1073/// instruction.
1074///
1075/// This assumes that the current LiveOut set is sufficient.
1076///
1077/// This is expensive for an on-the-fly query because it calls
1078/// bumpUpwardPressure to recompute the pressure sets based on current
1079/// liveness. This mainly exists to verify correctness, e.g. with
1080/// -verify-misched. getUpwardPressureDelta is the fast version of this query
1081/// that uses the per-SUnit cache of the PressureDiff.
1082void RegPressureTracker::
1083getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
1084 RegPressureDelta &Delta,
1085 ArrayRef<PressureChange> CriticalPSets,
1086 ArrayRef<unsigned> MaxPressureLimit) {
1087 // Snapshot Pressure.
1088 // FIXME: The snapshot heap space should persist. But I'm planning to
1089 // summarize the pressure effect so we don't need to snapshot at all.
1090 std::vector<unsigned> SavedPressure = CurrSetPressure;
1091 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1092
1093 bumpUpwardPressure(MI);
1094
1095 computeExcessPressureDelta(OldPressureVec: SavedPressure, NewPressureVec: CurrSetPressure, Delta, RCI,
1096 LiveThruPressureVec: LiveThruPressure);
1097 computeMaxPressureDelta(OldMaxPressureVec: SavedMaxPressure, NewMaxPressureVec: P.MaxSetPressure, CriticalPSets,
1098 MaxPressureLimit, Delta);
1099 assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1100 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1101
1102 // Restore the tracker's state.
1103 P.MaxSetPressure.swap(x&: SavedMaxPressure);
1104 CurrSetPressure.swap(x&: SavedPressure);
1105
1106#ifndef NDEBUG
1107 if (!PDiff)
1108 return;
1109
1110 // Check if the alternate algorithm yields the same result.
1111 RegPressureDelta Delta2;
1112 getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
1113 if (Delta != Delta2) {
1114 dbgs() << "PDiff: ";
1115 PDiff->dump(*TRI);
1116 dbgs() << "DELTA: " << *MI;
1117 if (Delta.Excess.isValid())
1118 dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
1119 << " " << Delta.Excess.getUnitInc() << "\n";
1120 if (Delta.CriticalMax.isValid())
1121 dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
1122 << " " << Delta.CriticalMax.getUnitInc() << "\n";
1123 if (Delta.CurrentMax.isValid())
1124 dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
1125 << " " << Delta.CurrentMax.getUnitInc() << "\n";
1126 if (Delta2.Excess.isValid())
1127 dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
1128 << " " << Delta2.Excess.getUnitInc() << "\n";
1129 if (Delta2.CriticalMax.isValid())
1130 dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
1131 << " " << Delta2.CriticalMax.getUnitInc() << "\n";
1132 if (Delta2.CurrentMax.isValid())
1133 dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
1134 << " " << Delta2.CurrentMax.getUnitInc() << "\n";
1135 llvm_unreachable("RegP Delta Mismatch");
1136 }
1137#endif
1138}
1139
1140/// This is the fast version of querying register pressure that does not
1141/// directly depend on current liveness.
1142///
1143/// @param Delta captures information needed for heuristics.
1144///
1145/// @param CriticalPSets Are the pressure sets that are known to exceed some
1146/// limit within the region, not necessarily at the current position.
1147///
1148/// @param MaxPressureLimit Is the max pressure within the region, not
1149/// necessarily at the current position.
1150void RegPressureTracker::
1151getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
1152 RegPressureDelta &Delta,
1153 ArrayRef<PressureChange> CriticalPSets,
1154 ArrayRef<unsigned> MaxPressureLimit) const {
1155 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1156 for (PressureDiff::const_iterator
1157 PDiffI = PDiff.begin(), PDiffE = PDiff.end();
1158 PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
1159
1160 unsigned PSetID = PDiffI->getPSet();
1161 unsigned Limit = RCI->getRegPressureSetLimit(Idx: PSetID);
1162 if (!LiveThruPressure.empty())
1163 Limit += LiveThruPressure[PSetID];
1164
1165 unsigned POld = CurrSetPressure[PSetID];
1166 unsigned MOld = P.MaxSetPressure[PSetID];
1167 unsigned MNew = MOld;
1168 // Ignore DeadDefs here because they aren't captured by PressureChange.
1169 unsigned PNew = POld + PDiffI->getUnitInc();
1170 assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
1171 && "PSet overflow/underflow");
1172 if (PNew > MOld)
1173 MNew = PNew;
1174 // Check if current pressure has exceeded the limit.
1175 if (!Delta.Excess.isValid()) {
1176 unsigned ExcessInc = 0;
1177 if (PNew > Limit)
1178 ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
1179 else if (POld > Limit)
1180 ExcessInc = Limit - POld;
1181 if (ExcessInc) {
1182 Delta.Excess = PressureChange(PSetID);
1183 Delta.Excess.setUnitInc(ExcessInc);
1184 }
1185 }
1186 // Check if max pressure has exceeded a critical pressure set max.
1187 if (MNew == MOld)
1188 continue;
1189 if (!Delta.CriticalMax.isValid()) {
1190 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
1191 ++CritIdx;
1192
1193 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
1194 int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
1195 if (CritInc > 0 && CritInc <= std::numeric_limits<int16_t>::max()) {
1196 Delta.CriticalMax = PressureChange(PSetID);
1197 Delta.CriticalMax.setUnitInc(CritInc);
1198 }
1199 }
1200 }
1201 // Check if max pressure has exceeded the current max.
1202 if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
1203 Delta.CurrentMax = PressureChange(PSetID);
1204 Delta.CurrentMax.setUnitInc(MNew - MOld);
1205 }
1206 }
1207}
1208
1209/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
1210/// The query starts with a lane bitmask which gets lanes/bits removed for every
1211/// use we find.
1212static LaneBitmask findUseBetween(unsigned Reg, LaneBitmask LastUseMask,
1213 SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1214 const MachineRegisterInfo &MRI,
1215 const LiveIntervals *LIS) {
1216 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
1217 for (const MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1218 if (MO.isUndef())
1219 continue;
1220 const MachineInstr *MI = MO.getParent();
1221 SlotIndex InstSlot = LIS->getInstructionIndex(Instr: *MI).getRegSlot();
1222 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) {
1223 unsigned SubRegIdx = MO.getSubReg();
1224 LaneBitmask UseMask = TRI.getSubRegIndexLaneMask(SubIdx: SubRegIdx);
1225 LastUseMask &= ~UseMask;
1226 if (LastUseMask.none())
1227 return LaneBitmask::getNone();
1228 }
1229 }
1230 return LastUseMask;
1231}
1232
1233LaneBitmask RegPressureTracker::getLiveLanesAt(Register RegUnit,
1234 SlotIndex Pos) const {
1235 assert(RequireIntervals);
1236 return getLanesWithProperty(LIS: *LIS, MRI: *MRI, TrackLaneMasks, RegUnit, Pos,
1237 SafeDefault: LaneBitmask::getAll(),
1238 Property: [](const LiveRange &LR, SlotIndex Pos) {
1239 return LR.liveAt(index: Pos);
1240 });
1241}
1242
1243LaneBitmask RegPressureTracker::getLastUsedLanes(Register RegUnit,
1244 SlotIndex Pos) const {
1245 assert(RequireIntervals);
1246 return getLanesWithProperty(LIS: *LIS, MRI: *MRI, TrackLaneMasks, RegUnit,
1247 Pos: Pos.getBaseIndex(), SafeDefault: LaneBitmask::getNone(),
1248 Property: [](const LiveRange &LR, SlotIndex Pos) {
1249 const LiveRange::Segment *S = LR.getSegmentContaining(Idx: Pos);
1250 return S != nullptr && S->end == Pos.getRegSlot();
1251 });
1252}
1253
1254LaneBitmask RegPressureTracker::getLiveThroughAt(Register RegUnit,
1255 SlotIndex Pos) const {
1256 assert(RequireIntervals);
1257 return getLanesWithProperty(LIS: *LIS, MRI: *MRI, TrackLaneMasks, RegUnit, Pos,
1258 SafeDefault: LaneBitmask::getNone(),
1259 Property: [](const LiveRange &LR, SlotIndex Pos) {
1260 const LiveRange::Segment *S = LR.getSegmentContaining(Idx: Pos);
1261 return S != nullptr && S->start < Pos.getRegSlot(EC: true) &&
1262 S->end != Pos.getDeadSlot();
1263 });
1264}
1265
1266/// Record the downward impact of a single instruction on current register
1267/// pressure. Unlike the advance/recede pressure tracking interface, this does
1268/// not discover live in/outs.
1269///
1270/// This is intended for speculative queries. It leaves pressure inconsistent
1271/// with the current position, so must be restored by the caller.
1272void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
1273 assert(!MI->isDebugOrPseudoInstr() && "Expect a nondebug instruction.");
1274
1275 SlotIndex SlotIdx;
1276 if (RequireIntervals)
1277 SlotIdx = LIS->getInstructionIndex(Instr: *MI).getRegSlot();
1278
1279 // Account for register pressure similar to RegPressureTracker::advance().
1280 RegisterOperands RegOpers;
1281 RegOpers.collect(MI: *MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, /*IgnoreDead=*/false);
1282 if (TrackLaneMasks)
1283 RegOpers.adjustLaneLiveness(LIS: *LIS, MRI: *MRI, Pos: SlotIdx);
1284
1285 if (RequireIntervals) {
1286 for (const VRegMaskOrUnit &Use : RegOpers.Uses) {
1287 Register Reg = Use.RegUnit;
1288 LaneBitmask LastUseMask = getLastUsedLanes(RegUnit: Reg, Pos: SlotIdx);
1289 if (LastUseMask.none())
1290 continue;
1291 // The LastUseMask is queried from the liveness information of instruction
1292 // which may be further down the schedule. Some lanes may actually not be
1293 // last uses for the current position.
1294 // FIXME: allow the caller to pass in the list of vreg uses that remain
1295 // to be bottom-scheduled to avoid searching uses at each query.
1296 SlotIndex CurrIdx = getCurrSlot();
1297 LastUseMask
1298 = findUseBetween(Reg, LastUseMask, PriorUseIdx: CurrIdx, NextUseIdx: SlotIdx, MRI: *MRI, LIS);
1299 if (LastUseMask.none())
1300 continue;
1301
1302 LaneBitmask LiveMask = LiveRegs.contains(Reg);
1303 LaneBitmask NewMask = LiveMask & ~LastUseMask;
1304 decreaseRegPressure(RegUnit: Reg, PreviousMask: LiveMask, NewMask);
1305 }
1306 }
1307
1308 // Generate liveness for defs.
1309 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
1310 Register Reg = Def.RegUnit;
1311 LaneBitmask LiveMask = LiveRegs.contains(Reg);
1312 LaneBitmask NewMask = LiveMask | Def.LaneMask;
1313 increaseRegPressure(RegUnit: Reg, PreviousMask: LiveMask, NewMask);
1314 }
1315
1316 // Boost pressure for all dead defs together.
1317 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
1318}
1319
1320/// Consider the pressure increase caused by traversing this instruction
1321/// top-down. Find the register class with the most change in its pressure limit
1322/// based on the tracker's current pressure, and return the number of excess
1323/// register units of that pressure set introduced by this instruction.
1324///
1325/// This assumes that the current LiveIn set is sufficient.
1326///
1327/// This is expensive for an on-the-fly query because it calls
1328/// bumpDownwardPressure to recompute the pressure sets based on current
1329/// liveness. We don't yet have a fast version of downward pressure tracking
1330/// analogous to getUpwardPressureDelta.
1331void RegPressureTracker::
1332getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
1333 ArrayRef<PressureChange> CriticalPSets,
1334 ArrayRef<unsigned> MaxPressureLimit) {
1335 // Snapshot Pressure.
1336 std::vector<unsigned> SavedPressure = CurrSetPressure;
1337 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1338
1339 bumpDownwardPressure(MI);
1340
1341 computeExcessPressureDelta(OldPressureVec: SavedPressure, NewPressureVec: CurrSetPressure, Delta, RCI,
1342 LiveThruPressureVec: LiveThruPressure);
1343 computeMaxPressureDelta(OldMaxPressureVec: SavedMaxPressure, NewMaxPressureVec: P.MaxSetPressure, CriticalPSets,
1344 MaxPressureLimit, Delta);
1345 assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1346 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1347
1348 // Restore the tracker's state.
1349 P.MaxSetPressure.swap(x&: SavedMaxPressure);
1350 CurrSetPressure.swap(x&: SavedPressure);
1351}
1352
1353/// Get the pressure of each PSet after traversing this instruction bottom-up.
1354void RegPressureTracker::
1355getUpwardPressure(const MachineInstr *MI,
1356 std::vector<unsigned> &PressureResult,
1357 std::vector<unsigned> &MaxPressureResult) {
1358 // Snapshot pressure.
1359 PressureResult = CurrSetPressure;
1360 MaxPressureResult = P.MaxSetPressure;
1361
1362 bumpUpwardPressure(MI);
1363
1364 // Current pressure becomes the result. Restore current pressure.
1365 P.MaxSetPressure.swap(x&: MaxPressureResult);
1366 CurrSetPressure.swap(x&: PressureResult);
1367}
1368
1369/// Get the pressure of each PSet after traversing this instruction top-down.
1370void RegPressureTracker::
1371getDownwardPressure(const MachineInstr *MI,
1372 std::vector<unsigned> &PressureResult,
1373 std::vector<unsigned> &MaxPressureResult) {
1374 // Snapshot pressure.
1375 PressureResult = CurrSetPressure;
1376 MaxPressureResult = P.MaxSetPressure;
1377
1378 bumpDownwardPressure(MI);
1379
1380 // Current pressure becomes the result. Restore current pressure.
1381 P.MaxSetPressure.swap(x&: MaxPressureResult);
1382 CurrSetPressure.swap(x&: PressureResult);
1383}
1384

source code of llvm/lib/CodeGen/RegisterPressure.cpp