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