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