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