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 = getLiveLanesAt(LIS, MRI, /*TrackLaneMasks=*/true,
597 VRegOrUnit: I->VRegOrUnit, Pos: Pos.getDeadSlot());
598 I = adjustDef(Def&: *I, LiveAfterDef: LiveAfter);
599 }
600 adjustUses(LIS, MRI, Pos: Pos.getBaseIndex());
601}
602
603void RegisterOperands::adjustLaneLiveness(LiveIntervals &LIS,
604 const MachineRegisterInfo &MRI,
605 MachineInstr &MI) {
606 SlotIndex Pos = LIS.getInstructionIndex(Instr: MI);
607 for (auto *I = Defs.begin(); I != Defs.end(); /*empty*/) {
608 LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, /*TrackLaneMasks=*/true,
609 VRegOrUnit: I->VRegOrUnit, Pos: Pos.getDeadSlot());
610 // If the def is all that is live after the instruction, then in case
611 // of a subregister def we need a read-undef flag.
612 VirtRegOrUnit VRegOrUnit = I->VRegOrUnit;
613 if (VRegOrUnit.isVirtualReg() && (LiveAfter & ~I->LaneMask).none())
614 MI.setRegisterDefReadUndef(Reg: VRegOrUnit.asVirtualReg());
615 I = adjustDef(Def&: *I, LiveAfterDef: LiveAfter);
616 }
617
618 adjustUses(LIS, MRI, Pos);
619
620 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
621 for (const VRegMaskOrUnit &P : DeadDefs) {
622 VirtRegOrUnit VRegOrUnit = P.VRegOrUnit;
623 if (!VRegOrUnit.isVirtualReg())
624 continue;
625 Register VReg = VRegOrUnit.asVirtualReg();
626 LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, /*TrackLaneMasks=*/true,
627 VRegOrUnit, Pos: Pos.getDeadSlot());
628 if (!LiveAfter.none())
629 continue;
630 // The register's read value doesn't matter if none of its lanes are live
631 // after the def.
632 MI.setRegisterDefReadUndef(Reg: VReg);
633
634 // The register's last definition should be marked dead.
635 const LiveInterval &LI = LIS.getInterval(Reg: VReg);
636 if (LI.segments.back().end == Pos.getDeadSlot())
637 MI.addRegisterDead(Reg: VReg, RegInfo: TRI, /*AddIfNotFound=*/false);
638 }
639}
640
641void RegisterOperands::restoreLivenessFlags(MachineInstr &MI,
642 const TargetRegisterInfo &TRI,
643 const MachineRegisterInfo &MRI,
644 LiveIntervals &LIS,
645 bool TrackLaneMasks,
646 ArrayRef<Register> OnlyRegs) {
647 assert(!MI.isDebugInstr() && "No flags to restore on debug instructions");
648 // Clear potentially-stale read-undef flags. They are re-added below for the
649 // lanes that are still dead.
650 bool HasClearedDef = false;
651 for (MachineOperand &MO : MI.all_defs()) {
652 if (!OnlyRegs.empty() && (!MO.getReg().isVirtual() || MO.getSubReg() == 0 ||
653 !llvm::is_contained(Range&: OnlyRegs, Element: MO.getReg())))
654 continue;
655 MO.setIsUndef(false);
656 HasClearedDef = true;
657 }
658 if (!HasClearedDef)
659 return;
660 RegisterOperands RegOpers;
661 RegOpers.collect(MI, TRI, MRI, TrackLaneMasks, /*IgnoreDead=*/false);
662 if (TrackLaneMasks) {
663 // Adjust liveness and add missing dead+read-undef flags.
664 RegOpers.adjustLaneLiveness(LIS, MRI, MI);
665 } else {
666 // Adjust for missing dead-def flags.
667 RegOpers.detectDeadDefs(MI, LIS, MRI);
668 }
669}
670
671VRegMaskOrUnit *RegisterOperands::adjustDef(VRegMaskOrUnit &Def,
672 LaneBitmask LiveAfterDef) {
673 LaneBitmask ActualDef = Def.LaneMask & LiveAfterDef;
674 if (ActualDef.none()) {
675 DeadDefs.push_back(Elt: Def);
676 return Defs.erase(CI: &Def);
677 }
678
679 Def.LaneMask = ActualDef;
680 return &Def + 1;
681}
682
683void RegisterOperands::adjustUses(LiveIntervals &LIS,
684 const MachineRegisterInfo &MRI,
685 SlotIndex Pos) {
686 for (auto &[VRegOrUnit, LaneMask] : Uses) {
687 LaneMask =
688 getLiveLanesAt(LIS, MRI, /*TrackLaneMasks=*/true, VRegOrUnit, Pos);
689 }
690}
691
692/// Initialize an array of N PressureDiffs.
693void PressureDiffs::init(unsigned N) {
694 Size = N;
695 if (N <= Max) {
696 memset(s: PDiffArray, c: 0, n: N * sizeof(PressureDiff));
697 return;
698 }
699 Max = Size;
700 free(ptr: PDiffArray);
701 PDiffArray = static_cast<PressureDiff*>(safe_calloc(Count: N, Sz: sizeof(PressureDiff)));
702}
703
704void PressureDiffs::addInstruction(unsigned Idx,
705 const RegisterOperands &RegOpers,
706 const MachineRegisterInfo &MRI) {
707 PressureDiff &PDiff = (*this)[Idx];
708 assert(!PDiff.begin()->isValid() && "stale PDiff");
709 for (const VRegMaskOrUnit &P : RegOpers.Defs)
710 PDiff.addPressureChange(VRegOrUnit: P.VRegOrUnit, IsDec: true, MRI: &MRI);
711
712 for (const VRegMaskOrUnit &P : RegOpers.Uses)
713 PDiff.addPressureChange(VRegOrUnit: P.VRegOrUnit, IsDec: false, MRI: &MRI);
714}
715
716/// Add a change in pressure to the pressure diff of a given instruction.
717void PressureDiff::addPressureChange(VirtRegOrUnit VRegOrUnit, bool IsDec,
718 const MachineRegisterInfo *MRI) {
719 PSetIterator PSetI = MRI->getPressureSets(VRegOrUnit);
720 int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight();
721 for (; PSetI.isValid(); ++PSetI) {
722 // Find an existing entry in the pressure diff for this PSet.
723 PressureDiff::iterator I = nonconst_begin(), E = nonconst_end();
724 for (; I != E && I->isValid(); ++I) {
725 if (I->getPSet() >= *PSetI)
726 break;
727 }
728 // If all pressure sets are more constrained, skip the remaining PSets.
729 if (I == E)
730 break;
731 // Insert this PressureChange.
732 if (!I->isValid() || I->getPSet() != *PSetI) {
733 PressureChange PTmp = PressureChange(*PSetI);
734 for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J)
735 std::swap(a&: *J, b&: PTmp);
736 }
737 // Update the units for this pressure set.
738 unsigned NewUnitInc = I->getUnitInc() + Weight;
739 if (NewUnitInc != 0) {
740 I->setUnitInc(NewUnitInc);
741 } else {
742 // Remove entry
743 PressureDiff::iterator J;
744 for (J = std::next(x: I); J != E && J->isValid(); ++J, ++I)
745 *I = *J;
746 *I = PressureChange();
747 }
748 }
749}
750
751/// Force liveness of registers.
752void RegPressureTracker::addLiveRegs(ArrayRef<VRegMaskOrUnit> Regs) {
753 for (const VRegMaskOrUnit &P : Regs) {
754 LaneBitmask PrevMask = LiveRegs.insert(Pair: P);
755 LaneBitmask NewMask = PrevMask | P.LaneMask;
756 increaseRegPressure(VRegOrUnit: P.VRegOrUnit, PreviousMask: PrevMask, NewMask);
757 }
758}
759
760void RegPressureTracker::discoverLiveInOrOut(
761 VRegMaskOrUnit Pair, SmallVectorImpl<VRegMaskOrUnit> &LiveInOrOut) {
762 assert(Pair.LaneMask.any());
763
764 VirtRegOrUnit VRegOrUnit = Pair.VRegOrUnit;
765 auto I = find_if(Range&: LiveInOrOut, P: [VRegOrUnit](const VRegMaskOrUnit &Other) {
766 return Other.VRegOrUnit == VRegOrUnit;
767 });
768 LaneBitmask PrevMask;
769 LaneBitmask NewMask;
770 if (I == LiveInOrOut.end()) {
771 PrevMask = LaneBitmask::getNone();
772 NewMask = Pair.LaneMask;
773 LiveInOrOut.push_back(Elt: Pair);
774 } else {
775 PrevMask = I->LaneMask;
776 NewMask = PrevMask | Pair.LaneMask;
777 I->LaneMask = NewMask;
778 }
779 increaseSetPressure(CurrSetPressure&: P.MaxSetPressure, MRI: *MRI, VRegOrUnit, PrevMask, NewMask);
780}
781
782void RegPressureTracker::discoverLiveIn(VRegMaskOrUnit Pair) {
783 discoverLiveInOrOut(Pair, LiveInOrOut&: P.LiveInRegs);
784}
785
786void RegPressureTracker::discoverLiveOut(VRegMaskOrUnit Pair) {
787 discoverLiveInOrOut(Pair, LiveInOrOut&: P.LiveOutRegs);
788}
789
790void RegPressureTracker::bumpDeadDefs(ArrayRef<VRegMaskOrUnit> DeadDefs) {
791 for (const VRegMaskOrUnit &P : DeadDefs) {
792 LaneBitmask LiveMask = LiveRegs.contains(VRegOrUnit: P.VRegOrUnit);
793 LaneBitmask BumpedMask = LiveMask | P.LaneMask;
794 increaseRegPressure(VRegOrUnit: P.VRegOrUnit, PreviousMask: LiveMask, NewMask: BumpedMask);
795 }
796 for (const VRegMaskOrUnit &P : DeadDefs) {
797 LaneBitmask LiveMask = LiveRegs.contains(VRegOrUnit: P.VRegOrUnit);
798 LaneBitmask BumpedMask = LiveMask | P.LaneMask;
799 decreaseRegPressure(VRegOrUnit: P.VRegOrUnit, PreviousMask: BumpedMask, NewMask: LiveMask);
800 }
801}
802
803/// Recede across the previous instruction. If LiveUses is provided, record any
804/// RegUnits that are made live by the current instruction's uses. This includes
805/// registers that are both defined and used by the instruction. If a pressure
806/// difference pointer is provided record the changes is pressure caused by this
807/// instruction independent of liveness.
808void RegPressureTracker::recede(const RegisterOperands &RegOpers,
809 SmallVectorImpl<VRegMaskOrUnit> *LiveUses) {
810 assert(!CurrPos->isDebugOrPseudoInstr());
811
812 // Boost pressure for all dead defs together.
813 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
814
815 // Kill liveness at live defs.
816 // TODO: consider earlyclobbers?
817 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
818 VirtRegOrUnit VRegOrUnit = Def.VRegOrUnit;
819
820 LaneBitmask PreviousMask = LiveRegs.erase(Pair: Def);
821 LaneBitmask NewMask = PreviousMask & ~Def.LaneMask;
822
823 LaneBitmask LiveOut = Def.LaneMask & ~PreviousMask;
824 if (LiveOut.any()) {
825 discoverLiveOut(Pair: VRegMaskOrUnit(VRegOrUnit, LiveOut));
826 // Retroactively model effects on pressure of the live out lanes.
827 increaseSetPressure(CurrSetPressure, MRI: *MRI, VRegOrUnit,
828 PrevMask: LaneBitmask::getNone(), NewMask: LiveOut);
829 PreviousMask = LiveOut;
830 }
831
832 if (NewMask.none()) {
833 // Add a 0 entry to LiveUses as a marker that the complete vreg has become
834 // dead.
835 if (TrackLaneMasks && LiveUses != nullptr)
836 setRegZero(RegUnits&: *LiveUses, VRegOrUnit);
837 }
838
839 decreaseRegPressure(VRegOrUnit, PreviousMask, NewMask);
840 }
841
842 SlotIndex SlotIdx;
843 if (RequireIntervals)
844 SlotIdx = LIS->getInstructionIndex(Instr: *CurrPos).getRegSlot();
845
846 // Generate liveness for uses.
847 for (const VRegMaskOrUnit &Use : RegOpers.Uses) {
848 VirtRegOrUnit VRegOrUnit = Use.VRegOrUnit;
849 assert(Use.LaneMask.any());
850 LaneBitmask PreviousMask = LiveRegs.insert(Pair: Use);
851 LaneBitmask NewMask = PreviousMask | Use.LaneMask;
852 if (NewMask == PreviousMask)
853 continue;
854
855 // Did the register just become live?
856 if (PreviousMask.none()) {
857 if (LiveUses != nullptr) {
858 if (!TrackLaneMasks) {
859 addRegLanes(RegUnits&: *LiveUses, Pair: VRegMaskOrUnit(VRegOrUnit, NewMask));
860 } else {
861 auto I = find_if(Range&: *LiveUses, P: [VRegOrUnit](const VRegMaskOrUnit Other) {
862 return Other.VRegOrUnit == VRegOrUnit;
863 });
864 bool IsRedef = I != LiveUses->end();
865 if (IsRedef) {
866 // ignore re-defs here...
867 assert(I->LaneMask.none());
868 removeRegLanes(RegUnits&: *LiveUses, Pair: VRegMaskOrUnit(VRegOrUnit, NewMask));
869 } else {
870 addRegLanes(RegUnits&: *LiveUses, Pair: VRegMaskOrUnit(VRegOrUnit, NewMask));
871 }
872 }
873 }
874
875 // Discover live outs if this may be the first occurance of this register.
876 if (RequireIntervals) {
877 LaneBitmask LiveOut = getLiveThroughAt(VRegOrUnit, Pos: SlotIdx);
878 if (LiveOut.any())
879 discoverLiveOut(Pair: VRegMaskOrUnit(VRegOrUnit, LiveOut));
880 }
881 }
882
883 increaseRegPressure(VRegOrUnit, PreviousMask, NewMask);
884 }
885 if (TrackUntiedDefs) {
886 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
887 VirtRegOrUnit VRegOrUnit = Def.VRegOrUnit;
888 if (VRegOrUnit.isVirtualReg() &&
889 (LiveRegs.contains(VRegOrUnit) & Def.LaneMask).none())
890 UntiedDefs.insert(Val: VRegOrUnit.asVirtualReg());
891 }
892 }
893}
894
895void RegPressureTracker::recedeSkipDebugValues() {
896 assert(CurrPos != MBB->begin());
897 if (!isBottomClosed())
898 closeBottom();
899
900 // Open the top of the region using block iterators.
901 if (!RequireIntervals && isTopClosed())
902 static_cast<RegionPressure&>(P).openTop(PrevTop: CurrPos);
903
904 // Find the previous instruction.
905 CurrPos = prev_nodbg(It: CurrPos, Begin: MBB->begin());
906
907 SlotIndex SlotIdx;
908 if (RequireIntervals && !CurrPos->isDebugOrPseudoInstr())
909 SlotIdx = LIS->getInstructionIndex(Instr: *CurrPos).getRegSlot();
910
911 // Open the top of the region using slot indexes.
912 if (RequireIntervals && isTopClosed())
913 static_cast<IntervalPressure&>(P).openTop(NextTop: SlotIdx);
914}
915
916void RegPressureTracker::recede(SmallVectorImpl<VRegMaskOrUnit> *LiveUses) {
917 recedeSkipDebugValues();
918 if (CurrPos->isDebugOrPseudoInstr()) {
919 // It's possible to only have debug_value and pseudo probe instructions and
920 // hit the start of the block.
921 assert(CurrPos == MBB->begin());
922 return;
923 }
924
925 const MachineInstr &MI = *CurrPos;
926 RegisterOperands RegOpers;
927 RegOpers.collect(MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, /*IgnoreDead=*/false);
928 if (TrackLaneMasks) {
929 SlotIndex SlotIdx = LIS->getInstructionIndex(Instr: *CurrPos).getRegSlot();
930 RegOpers.adjustLaneLiveness(LIS&: *LIS, MRI: *MRI, Pos: SlotIdx);
931 } else if (RequireIntervals) {
932 RegOpers.detectDeadDefs(MI, LIS&: *LIS, MRI: *MRI);
933 }
934
935 recede(RegOpers, LiveUses);
936}
937
938/// Advance across the current instruction.
939void RegPressureTracker::advance(const RegisterOperands &RegOpers) {
940 assert(!TrackUntiedDefs && "unsupported mode");
941 assert(CurrPos != MBB->end());
942 if (!isTopClosed())
943 closeTop();
944
945 SlotIndex SlotIdx;
946 if (RequireIntervals)
947 SlotIdx = getCurrSlot();
948
949 // Open the bottom of the region using slot indexes.
950 if (isBottomClosed()) {
951 if (RequireIntervals)
952 static_cast<IntervalPressure&>(P).openBottom(PrevBottom: SlotIdx);
953 else
954 static_cast<RegionPressure&>(P).openBottom(PrevBottom: CurrPos);
955 }
956
957 for (const VRegMaskOrUnit &Use : RegOpers.Uses) {
958 VirtRegOrUnit VRegOrUnit = Use.VRegOrUnit;
959 LaneBitmask LiveMask = LiveRegs.contains(VRegOrUnit);
960 LaneBitmask LiveIn = Use.LaneMask & ~LiveMask;
961 if (LiveIn.any()) {
962 discoverLiveIn(Pair: VRegMaskOrUnit(VRegOrUnit, LiveIn));
963 increaseRegPressure(VRegOrUnit, PreviousMask: LiveMask, NewMask: LiveMask | LiveIn);
964 LiveRegs.insert(Pair: VRegMaskOrUnit(VRegOrUnit, LiveIn));
965 }
966 // Kill liveness at last uses.
967 if (RequireIntervals) {
968 LaneBitmask LastUseMask = getLastUsedLanes(VRegOrUnit, Pos: SlotIdx);
969 if (LastUseMask.any()) {
970 LiveRegs.erase(Pair: VRegMaskOrUnit(VRegOrUnit, LastUseMask));
971 decreaseRegPressure(VRegOrUnit, PreviousMask: LiveMask, NewMask: LiveMask & ~LastUseMask);
972 }
973 }
974 }
975
976 // Generate liveness for defs.
977 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
978 LaneBitmask PreviousMask = LiveRegs.insert(Pair: Def);
979 LaneBitmask NewMask = PreviousMask | Def.LaneMask;
980 increaseRegPressure(VRegOrUnit: Def.VRegOrUnit, PreviousMask, NewMask);
981 }
982
983 // Boost pressure for all dead defs together.
984 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
985
986 // Find the next instruction.
987 CurrPos = next_nodbg(It: CurrPos, End: MBB->end());
988}
989
990void RegPressureTracker::advance() {
991 const MachineInstr &MI = *CurrPos;
992 RegisterOperands RegOpers;
993 RegOpers.collect(MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, IgnoreDead: false);
994 if (TrackLaneMasks) {
995 SlotIndex SlotIdx = getCurrSlot();
996 RegOpers.adjustLaneLiveness(LIS&: *LIS, MRI: *MRI, Pos: SlotIdx);
997 }
998 advance(RegOpers);
999}
1000
1001/// Find the max change in excess pressure across all sets.
1002static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
1003 ArrayRef<unsigned> NewPressureVec,
1004 RegPressureDelta &Delta,
1005 const RegisterClassInfo *RCI,
1006 ArrayRef<unsigned> LiveThruPressureVec) {
1007 Delta.Excess = PressureChange();
1008 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
1009 unsigned POld = OldPressureVec[i];
1010 unsigned PNew = NewPressureVec[i];
1011 int PDiff = (int)PNew - (int)POld;
1012 if (!PDiff) // No change in this set in the common case.
1013 continue;
1014 // Only consider change beyond the limit.
1015 unsigned Limit = RCI->getRegPressureSetLimit(Idx: i);
1016 if (!LiveThruPressureVec.empty())
1017 Limit += LiveThruPressureVec[i];
1018
1019 if (Limit > POld) {
1020 if (Limit > PNew)
1021 PDiff = 0; // Under the limit
1022 else
1023 PDiff = PNew - Limit; // Just exceeded limit.
1024 } else if (Limit > PNew)
1025 PDiff = Limit - POld; // Just obeyed limit.
1026
1027 if (PDiff) {
1028 Delta.Excess = PressureChange(i);
1029 Delta.Excess.setUnitInc(PDiff);
1030 break;
1031 }
1032 }
1033}
1034
1035/// Find the max change in max pressure that either surpasses a critical PSet
1036/// limit or exceeds the current MaxPressureLimit.
1037///
1038/// FIXME: comparing each element of the old and new MaxPressure vectors here is
1039/// silly. It's done now to demonstrate the concept but will go away with a
1040/// RegPressureTracker API change to work with pressure differences.
1041static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
1042 ArrayRef<unsigned> NewMaxPressureVec,
1043 ArrayRef<PressureChange> CriticalPSets,
1044 ArrayRef<unsigned> MaxPressureLimit,
1045 RegPressureDelta &Delta) {
1046 Delta.CriticalMax = PressureChange();
1047 Delta.CurrentMax = PressureChange();
1048
1049 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1050 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
1051 unsigned POld = OldMaxPressureVec[i];
1052 unsigned PNew = NewMaxPressureVec[i];
1053 if (PNew == POld) // No change in this set in the common case.
1054 continue;
1055
1056 if (!Delta.CriticalMax.isValid()) {
1057 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
1058 ++CritIdx;
1059
1060 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
1061 int PDiff = (int)PNew - CriticalPSets[CritIdx].getUnitInc();
1062 if (PDiff > 0) {
1063 Delta.CriticalMax = PressureChange(i);
1064 Delta.CriticalMax.setUnitInc(PDiff);
1065 }
1066 }
1067 }
1068 // Find the first increase above MaxPressureLimit.
1069 // (Ignores negative MDiff).
1070 if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
1071 Delta.CurrentMax = PressureChange(i);
1072 Delta.CurrentMax.setUnitInc(PNew - POld);
1073 if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
1074 break;
1075 }
1076 }
1077}
1078
1079/// Record the upward impact of a single instruction on current register
1080/// pressure. Unlike the advance/recede pressure tracking interface, this does
1081/// not discover live in/outs.
1082///
1083/// This is intended for speculative queries. It leaves pressure inconsistent
1084/// with the current position, so must be restored by the caller.
1085void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
1086 assert(!MI->isDebugOrPseudoInstr() && "Expect a nondebug instruction.");
1087
1088 SlotIndex SlotIdx;
1089 if (RequireIntervals)
1090 SlotIdx = LIS->getInstructionIndex(Instr: *MI).getRegSlot();
1091
1092 // Account for register pressure similar to RegPressureTracker::recede().
1093 RegisterOperands RegOpers;
1094 RegOpers.collect(MI: *MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, /*IgnoreDead=*/true);
1095 assert(RegOpers.DeadDefs.empty());
1096 if (TrackLaneMasks)
1097 RegOpers.adjustLaneLiveness(LIS&: *LIS, MRI: *MRI, Pos: SlotIdx);
1098 else if (RequireIntervals)
1099 RegOpers.detectDeadDefs(MI: *MI, LIS&: *LIS, MRI: *MRI);
1100
1101 // Boost max pressure for all dead defs together.
1102 // Since CurrSetPressure and MaxSetPressure
1103 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
1104
1105 // Kill liveness at live defs.
1106 for (const VRegMaskOrUnit &P : RegOpers.Defs) {
1107 LaneBitmask LiveAfter = LiveRegs.contains(VRegOrUnit: P.VRegOrUnit);
1108 LaneBitmask UseLanes = getRegLanes(RegUnits: RegOpers.Uses, VRegOrUnit: P.VRegOrUnit);
1109 LaneBitmask DefLanes = P.LaneMask;
1110 LaneBitmask LiveBefore = (LiveAfter & ~DefLanes) | UseLanes;
1111
1112 // There may be parts of the register that were dead before the
1113 // instruction, but became live afterwards.
1114 decreaseRegPressure(VRegOrUnit: P.VRegOrUnit, PreviousMask: LiveAfter, NewMask: LiveAfter & LiveBefore);
1115 }
1116 // Generate liveness for uses. Also handle any uses which overlap with defs.
1117 for (const VRegMaskOrUnit &P : RegOpers.Uses) {
1118 LaneBitmask LiveAfter = LiveRegs.contains(VRegOrUnit: P.VRegOrUnit);
1119 LaneBitmask LiveBefore = LiveAfter | P.LaneMask;
1120 increaseRegPressure(VRegOrUnit: P.VRegOrUnit, PreviousMask: LiveAfter, NewMask: LiveBefore);
1121 }
1122}
1123
1124/// Consider the pressure increase caused by traversing this instruction
1125/// bottom-up. Find the pressure set with the most change beyond its pressure
1126/// limit based on the tracker's current pressure, and return the change in
1127/// number of register units of that pressure set introduced by this
1128/// instruction.
1129///
1130/// This assumes that the current LiveOut set is sufficient.
1131///
1132/// This is expensive for an on-the-fly query because it calls
1133/// bumpUpwardPressure to recompute the pressure sets based on current
1134/// liveness. This mainly exists to verify correctness, e.g. with
1135/// -verify-misched. getUpwardPressureDelta is the fast version of this query
1136/// that uses the per-SUnit cache of the PressureDiff.
1137void RegPressureTracker::
1138getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
1139 RegPressureDelta &Delta,
1140 ArrayRef<PressureChange> CriticalPSets,
1141 ArrayRef<unsigned> MaxPressureLimit) {
1142 // Snapshot Pressure.
1143 // FIXME: The snapshot heap space should persist. But I'm planning to
1144 // summarize the pressure effect so we don't need to snapshot at all.
1145 std::vector<unsigned> SavedPressure = CurrSetPressure;
1146 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1147
1148 bumpUpwardPressure(MI);
1149
1150 computeExcessPressureDelta(OldPressureVec: SavedPressure, NewPressureVec: CurrSetPressure, Delta, RCI,
1151 LiveThruPressureVec: LiveThruPressure);
1152 computeMaxPressureDelta(OldMaxPressureVec: SavedMaxPressure, NewMaxPressureVec: P.MaxSetPressure, CriticalPSets,
1153 MaxPressureLimit, Delta);
1154 assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1155 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1156
1157 // Restore the tracker's state.
1158 P.MaxSetPressure.swap(x&: SavedMaxPressure);
1159 CurrSetPressure.swap(x&: SavedPressure);
1160
1161#ifndef NDEBUG
1162 if (!PDiff)
1163 return;
1164
1165 // Check if the alternate algorithm yields the same result.
1166 RegPressureDelta Delta2;
1167 getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
1168 if (Delta != Delta2) {
1169 dbgs() << "PDiff: ";
1170 PDiff->dump(*TRI);
1171 dbgs() << "DELTA: " << *MI;
1172 if (Delta.Excess.isValid())
1173 dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
1174 << " " << Delta.Excess.getUnitInc() << "\n";
1175 if (Delta.CriticalMax.isValid())
1176 dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
1177 << " " << Delta.CriticalMax.getUnitInc() << "\n";
1178 if (Delta.CurrentMax.isValid())
1179 dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
1180 << " " << Delta.CurrentMax.getUnitInc() << "\n";
1181 if (Delta2.Excess.isValid())
1182 dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
1183 << " " << Delta2.Excess.getUnitInc() << "\n";
1184 if (Delta2.CriticalMax.isValid())
1185 dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
1186 << " " << Delta2.CriticalMax.getUnitInc() << "\n";
1187 if (Delta2.CurrentMax.isValid())
1188 dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
1189 << " " << Delta2.CurrentMax.getUnitInc() << "\n";
1190 llvm_unreachable("RegP Delta Mismatch");
1191 }
1192#endif
1193}
1194
1195/// This is the fast version of querying register pressure that does not
1196/// directly depend on current liveness.
1197///
1198/// @param Delta captures information needed for heuristics.
1199///
1200/// @param CriticalPSets Are the pressure sets that are known to exceed some
1201/// limit within the region, not necessarily at the current position.
1202///
1203/// @param MaxPressureLimit Is the max pressure within the region, not
1204/// necessarily at the current position.
1205void RegPressureTracker::
1206getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
1207 RegPressureDelta &Delta,
1208 ArrayRef<PressureChange> CriticalPSets,
1209 ArrayRef<unsigned> MaxPressureLimit) const {
1210 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1211 for (PressureDiff::const_iterator
1212 PDiffI = PDiff.begin(), PDiffE = PDiff.end();
1213 PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
1214
1215 unsigned PSetID = PDiffI->getPSet();
1216 unsigned Limit = RCI->getRegPressureSetLimit(Idx: PSetID);
1217 if (!LiveThruPressure.empty())
1218 Limit += LiveThruPressure[PSetID];
1219
1220 unsigned POld = CurrSetPressure[PSetID];
1221 unsigned MOld = P.MaxSetPressure[PSetID];
1222 unsigned MNew = MOld;
1223 // Ignore DeadDefs here because they aren't captured by PressureChange.
1224 unsigned PNew = POld + PDiffI->getUnitInc();
1225 assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
1226 && "PSet overflow/underflow");
1227 if (PNew > MOld)
1228 MNew = PNew;
1229 // Check if current pressure has exceeded the limit.
1230 if (!Delta.Excess.isValid()) {
1231 unsigned ExcessInc = 0;
1232 if (PNew > Limit)
1233 ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
1234 else if (POld > Limit)
1235 ExcessInc = Limit - POld;
1236 if (ExcessInc) {
1237 Delta.Excess = PressureChange(PSetID);
1238 Delta.Excess.setUnitInc(ExcessInc);
1239 }
1240 }
1241 // Check if max pressure has exceeded a critical pressure set max.
1242 if (MNew == MOld)
1243 continue;
1244 if (!Delta.CriticalMax.isValid()) {
1245 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
1246 ++CritIdx;
1247
1248 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
1249 int CritInc = (int)MNew - CriticalPSets[CritIdx].getUnitInc();
1250 if (CritInc > 0 && CritInc <= std::numeric_limits<int16_t>::max()) {
1251 Delta.CriticalMax = PressureChange(PSetID);
1252 Delta.CriticalMax.setUnitInc(CritInc);
1253 }
1254 }
1255 }
1256 // Check if max pressure has exceeded the current max.
1257 if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
1258 Delta.CurrentMax = PressureChange(PSetID);
1259 Delta.CurrentMax.setUnitInc(MNew - MOld);
1260 }
1261 }
1262}
1263
1264/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
1265/// The query starts with a lane bitmask which gets lanes/bits removed for every
1266/// use we find.
1267static LaneBitmask findUseBetween(VirtRegOrUnit VRegOrUnit,
1268 LaneBitmask LastUseMask,
1269 SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1270 const MachineRegisterInfo &MRI,
1271 const LiveIntervals *LIS) {
1272 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
1273 // FIXME: The static_cast is a bug.
1274 Register Reg =
1275 VRegOrUnit.isVirtualReg()
1276 ? VRegOrUnit.asVirtualReg()
1277 : Register(static_cast<unsigned>(VRegOrUnit.asMCRegUnit()));
1278 for (const MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1279 if (MO.isUndef())
1280 continue;
1281 const MachineInstr *MI = MO.getParent();
1282 SlotIndex InstSlot = LIS->getInstructionIndex(Instr: *MI).getRegSlot();
1283 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) {
1284 unsigned SubRegIdx = MO.getSubReg();
1285 LaneBitmask UseMask = TRI.getSubRegIndexLaneMask(SubIdx: SubRegIdx);
1286 LastUseMask &= ~UseMask;
1287 if (LastUseMask.none())
1288 return LaneBitmask::getNone();
1289 }
1290 }
1291 return LastUseMask;
1292}
1293
1294LaneBitmask RegPressureTracker::getLiveLanesAt(VirtRegOrUnit VRegOrUnit,
1295 SlotIndex Pos) const {
1296 assert(RequireIntervals);
1297 return getLanesWithProperty(
1298 LIS&: *LIS, MRI: *MRI, TrackLaneMasks, VRegOrUnit, Pos, SafeDefault: LaneBitmask::getAll(),
1299 Property: [](const LiveRange &LR, SlotIndex Pos) { return LR.liveAt(index: Pos); });
1300}
1301
1302LaneBitmask RegPressureTracker::getLastUsedLanes(VirtRegOrUnit VRegOrUnit,
1303 SlotIndex Pos) const {
1304 assert(RequireIntervals);
1305 return getLanesWithProperty(
1306 LIS&: *LIS, MRI: *MRI, TrackLaneMasks, VRegOrUnit, Pos: Pos.getBaseIndex(),
1307 SafeDefault: LaneBitmask::getNone(), Property: [](const LiveRange &LR, SlotIndex Pos) {
1308 const LiveRange::Segment *S = LR.getSegmentContaining(Idx: Pos);
1309 return S != nullptr && S->end == Pos.getRegSlot();
1310 });
1311}
1312
1313LaneBitmask RegPressureTracker::getLiveThroughAt(VirtRegOrUnit VRegOrUnit,
1314 SlotIndex Pos) const {
1315 assert(RequireIntervals);
1316 return getLanesWithProperty(
1317 LIS&: *LIS, MRI: *MRI, TrackLaneMasks, VRegOrUnit, Pos, SafeDefault: LaneBitmask::getNone(),
1318 Property: [](const LiveRange &LR, SlotIndex Pos) {
1319 const LiveRange::Segment *S = LR.getSegmentContaining(Idx: Pos);
1320 return S != nullptr && S->start < Pos.getRegSlot(EC: true) &&
1321 S->end != Pos.getDeadSlot();
1322 });
1323}
1324
1325/// Record the downward impact of a single instruction on current register
1326/// pressure. Unlike the advance/recede pressure tracking interface, this does
1327/// not discover live in/outs.
1328///
1329/// This is intended for speculative queries. It leaves pressure inconsistent
1330/// with the current position, so must be restored by the caller.
1331void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
1332 assert(!MI->isDebugOrPseudoInstr() && "Expect a nondebug instruction.");
1333
1334 SlotIndex SlotIdx;
1335 if (RequireIntervals)
1336 SlotIdx = LIS->getInstructionIndex(Instr: *MI).getRegSlot();
1337
1338 // Account for register pressure similar to RegPressureTracker::advance().
1339 RegisterOperands RegOpers;
1340 RegOpers.collect(MI: *MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks, /*IgnoreDead=*/false);
1341 if (TrackLaneMasks)
1342 RegOpers.adjustLaneLiveness(LIS&: *LIS, MRI: *MRI, Pos: SlotIdx);
1343
1344 if (RequireIntervals) {
1345 for (const VRegMaskOrUnit &Use : RegOpers.Uses) {
1346 VirtRegOrUnit VRegOrUnit = Use.VRegOrUnit;
1347 LaneBitmask LastUseMask = getLastUsedLanes(VRegOrUnit, Pos: SlotIdx);
1348 if (LastUseMask.none())
1349 continue;
1350 // The LastUseMask is queried from the liveness information of instruction
1351 // which may be further down the schedule. Some lanes may actually not be
1352 // last uses for the current position.
1353 // FIXME: allow the caller to pass in the list of vreg uses that remain
1354 // to be bottom-scheduled to avoid searching uses at each query.
1355 SlotIndex CurrIdx = getCurrSlot();
1356 LastUseMask =
1357 findUseBetween(VRegOrUnit, LastUseMask, PriorUseIdx: CurrIdx, NextUseIdx: SlotIdx, MRI: *MRI, LIS);
1358 if (LastUseMask.none())
1359 continue;
1360
1361 LaneBitmask LiveMask = LiveRegs.contains(VRegOrUnit);
1362 LaneBitmask NewMask = LiveMask & ~LastUseMask;
1363 decreaseRegPressure(VRegOrUnit, PreviousMask: LiveMask, NewMask);
1364 }
1365 }
1366
1367 // Generate liveness for defs.
1368 for (const VRegMaskOrUnit &Def : RegOpers.Defs) {
1369 LaneBitmask LiveMask = LiveRegs.contains(VRegOrUnit: Def.VRegOrUnit);
1370 LaneBitmask NewMask = LiveMask | Def.LaneMask;
1371 increaseRegPressure(VRegOrUnit: Def.VRegOrUnit, PreviousMask: LiveMask, NewMask);
1372 }
1373
1374 // Boost pressure for all dead defs together.
1375 bumpDeadDefs(DeadDefs: RegOpers.DeadDefs);
1376}
1377
1378/// Consider the pressure increase caused by traversing this instruction
1379/// top-down. Find the register class with the most change in its pressure limit
1380/// based on the tracker's current pressure, and return the number of excess
1381/// register units of that pressure set introduced by this instruction.
1382///
1383/// This assumes that the current LiveIn set is sufficient.
1384///
1385/// This is expensive for an on-the-fly query because it calls
1386/// bumpDownwardPressure to recompute the pressure sets based on current
1387/// liveness. We don't yet have a fast version of downward pressure tracking
1388/// analogous to getUpwardPressureDelta.
1389void RegPressureTracker::
1390getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
1391 ArrayRef<PressureChange> CriticalPSets,
1392 ArrayRef<unsigned> MaxPressureLimit) {
1393 // Snapshot Pressure.
1394 std::vector<unsigned> SavedPressure = CurrSetPressure;
1395 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1396
1397 bumpDownwardPressure(MI);
1398
1399 computeExcessPressureDelta(OldPressureVec: SavedPressure, NewPressureVec: CurrSetPressure, Delta, RCI,
1400 LiveThruPressureVec: LiveThruPressure);
1401 computeMaxPressureDelta(OldMaxPressureVec: SavedMaxPressure, NewMaxPressureVec: P.MaxSetPressure, CriticalPSets,
1402 MaxPressureLimit, Delta);
1403 assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1404 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1405
1406 // Restore the tracker's state.
1407 P.MaxSetPressure.swap(x&: SavedMaxPressure);
1408 CurrSetPressure.swap(x&: SavedPressure);
1409}
1410
1411/// Get the pressure of each PSet after traversing this instruction bottom-up.
1412void RegPressureTracker::
1413getUpwardPressure(const MachineInstr *MI,
1414 std::vector<unsigned> &PressureResult,
1415 std::vector<unsigned> &MaxPressureResult) {
1416 // Snapshot pressure.
1417 PressureResult = CurrSetPressure;
1418 MaxPressureResult = P.MaxSetPressure;
1419
1420 bumpUpwardPressure(MI);
1421
1422 // Current pressure becomes the result. Restore current pressure.
1423 P.MaxSetPressure.swap(x&: MaxPressureResult);
1424 CurrSetPressure.swap(x&: PressureResult);
1425}
1426
1427/// Get the pressure of each PSet after traversing this instruction top-down.
1428void RegPressureTracker::
1429getDownwardPressure(const MachineInstr *MI,
1430 std::vector<unsigned> &PressureResult,
1431 std::vector<unsigned> &MaxPressureResult) {
1432 // Snapshot pressure.
1433 PressureResult = CurrSetPressure;
1434 MaxPressureResult = P.MaxSetPressure;
1435
1436 bumpDownwardPressure(MI);
1437
1438 // Current pressure becomes the result. Restore current pressure.
1439 P.MaxSetPressure.swap(x&: MaxPressureResult);
1440 CurrSetPressure.swap(x&: PressureResult);
1441}
1442