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

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