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