LLVM  6.0.0svn
RegisterPressure.cpp
Go to the documentation of this file.
1 //===- RegisterPressure.cpp - Dynamic Register Pressure -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the RegisterPressure class which can be used to track
11 // MachineInstr level register pressure.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.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 
126 void PressureDiff::dump(const TargetRegisterInfo &TRI) const {
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 
210  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
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 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 = reinterpret_cast<PressureDiff*>(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  if (J != E)
684  *I = *J;
685  }
686  }
687 }
688 
689 /// Force liveness of registers.
691  for (const RegisterMaskPair &P : Regs) {
692  LaneBitmask PrevMask = LiveRegs.insert(P);
693  LaneBitmask NewMask = PrevMask | P.LaneMask;
694  increaseRegPressure(P.RegUnit, PrevMask, NewMask);
695  }
696 }
697 
699  SmallVectorImpl<RegisterMaskPair> &LiveInOrOut) {
700  assert(Pair.LaneMask.any());
701 
702  unsigned RegUnit = Pair.RegUnit;
703  auto I = llvm::find_if(LiveInOrOut, [RegUnit](const RegisterMaskPair &Other) {
704  return Other.RegUnit == RegUnit;
705  });
706  LaneBitmask PrevMask;
707  LaneBitmask NewMask;
708  if (I == LiveInOrOut.end()) {
709  PrevMask = LaneBitmask::getNone();
710  NewMask = Pair.LaneMask;
711  LiveInOrOut.push_back(Pair);
712  } else {
713  PrevMask = I->LaneMask;
714  NewMask = PrevMask | Pair.LaneMask;
715  I->LaneMask = NewMask;
716  }
717  increaseSetPressure(P.MaxSetPressure, *MRI, RegUnit, PrevMask, NewMask);
718 }
719 
721  discoverLiveInOrOut(Pair, P.LiveInRegs);
722 }
723 
725  discoverLiveInOrOut(Pair, P.LiveOutRegs);
726 }
727 
729  for (const RegisterMaskPair &P : DeadDefs) {
730  unsigned Reg = P.RegUnit;
731  LaneBitmask LiveMask = LiveRegs.contains(Reg);
732  LaneBitmask BumpedMask = LiveMask | P.LaneMask;
733  increaseRegPressure(Reg, LiveMask, BumpedMask);
734  }
735  for (const RegisterMaskPair &P : DeadDefs) {
736  unsigned Reg = P.RegUnit;
737  LaneBitmask LiveMask = LiveRegs.contains(Reg);
738  LaneBitmask BumpedMask = LiveMask | P.LaneMask;
739  decreaseRegPressure(Reg, BumpedMask, LiveMask);
740  }
741 }
742 
743 /// Recede across the previous instruction. If LiveUses is provided, record any
744 /// RegUnits that are made live by the current instruction's uses. This includes
745 /// registers that are both defined and used by the instruction. If a pressure
746 /// difference pointer is provided record the changes is pressure caused by this
747 /// instruction independent of liveness.
750  assert(!CurrPos->isDebugValue());
751 
752  // Boost pressure for all dead defs together.
753  bumpDeadDefs(RegOpers.DeadDefs);
754 
755  // Kill liveness at live defs.
756  // TODO: consider earlyclobbers?
757  for (const RegisterMaskPair &Def : RegOpers.Defs) {
758  unsigned Reg = Def.RegUnit;
759 
760  LaneBitmask PreviousMask = LiveRegs.erase(Def);
761  LaneBitmask NewMask = PreviousMask & ~Def.LaneMask;
762 
763  LaneBitmask LiveOut = Def.LaneMask & ~PreviousMask;
764  if (LiveOut.any()) {
765  discoverLiveOut(RegisterMaskPair(Reg, LiveOut));
766  // Retroactively model effects on pressure of the live out lanes.
767  increaseSetPressure(CurrSetPressure, *MRI, Reg, LaneBitmask::getNone(),
768  LiveOut);
769  PreviousMask = LiveOut;
770  }
771 
772  if (NewMask.none()) {
773  // Add a 0 entry to LiveUses as a marker that the complete vreg has become
774  // dead.
775  if (TrackLaneMasks && LiveUses != nullptr)
776  setRegZero(*LiveUses, Reg);
777  }
778 
779  decreaseRegPressure(Reg, PreviousMask, NewMask);
780  }
781 
782  SlotIndex SlotIdx;
783  if (RequireIntervals)
784  SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
785 
786  // Generate liveness for uses.
787  for (const RegisterMaskPair &Use : RegOpers.Uses) {
788  unsigned Reg = Use.RegUnit;
789  assert(Use.LaneMask.any());
790  LaneBitmask PreviousMask = LiveRegs.insert(Use);
791  LaneBitmask NewMask = PreviousMask | Use.LaneMask;
792  if (NewMask == PreviousMask)
793  continue;
794 
795  // Did the register just become live?
796  if (PreviousMask.none()) {
797  if (LiveUses != nullptr) {
798  if (!TrackLaneMasks) {
799  addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
800  } else {
801  auto I =
802  llvm::find_if(*LiveUses, [Reg](const RegisterMaskPair Other) {
803  return Other.RegUnit == Reg;
804  });
805  bool IsRedef = I != LiveUses->end();
806  if (IsRedef) {
807  // ignore re-defs here...
808  assert(I->LaneMask.none());
809  removeRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
810  } else {
811  addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
812  }
813  }
814  }
815 
816  // Discover live outs if this may be the first occurance of this register.
817  if (RequireIntervals) {
818  LaneBitmask LiveOut = getLiveThroughAt(Reg, SlotIdx);
819  if (LiveOut.any())
820  discoverLiveOut(RegisterMaskPair(Reg, LiveOut));
821  }
822  }
823 
824  increaseRegPressure(Reg, PreviousMask, NewMask);
825  }
826  if (TrackUntiedDefs) {
827  for (const RegisterMaskPair &Def : RegOpers.Defs) {
828  unsigned RegUnit = Def.RegUnit;
830  (LiveRegs.contains(RegUnit) & Def.LaneMask).none())
831  UntiedDefs.insert(RegUnit);
832  }
833  }
834 }
835 
837  assert(CurrPos != MBB->begin());
838  if (!isBottomClosed())
839  closeBottom();
840 
841  // Open the top of the region using block iterators.
842  if (!RequireIntervals && isTopClosed())
843  static_cast<RegionPressure&>(P).openTop(CurrPos);
844 
845  // Find the previous instruction.
846  CurrPos = skipDebugInstructionsBackward(std::prev(CurrPos), MBB->begin());
847 
848  SlotIndex SlotIdx;
849  if (RequireIntervals)
850  SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
851 
852  // Open the top of the region using slot indexes.
853  if (RequireIntervals && isTopClosed())
854  static_cast<IntervalPressure&>(P).openTop(SlotIdx);
855 }
856 
858  recedeSkipDebugValues();
859 
860  const MachineInstr &MI = *CurrPos;
861  RegisterOperands RegOpers;
862  RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
863  if (TrackLaneMasks) {
864  SlotIndex SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
865  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
866  } else if (RequireIntervals) {
867  RegOpers.detectDeadDefs(MI, *LIS);
868  }
869 
870  recede(RegOpers, LiveUses);
871 }
872 
873 /// Advance across the current instruction.
875  assert(!TrackUntiedDefs && "unsupported mode");
876  assert(CurrPos != MBB->end());
877  if (!isTopClosed())
878  closeTop();
879 
880  SlotIndex SlotIdx;
881  if (RequireIntervals)
882  SlotIdx = getCurrSlot();
883 
884  // Open the bottom of the region using slot indexes.
885  if (isBottomClosed()) {
886  if (RequireIntervals)
887  static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
888  else
889  static_cast<RegionPressure&>(P).openBottom(CurrPos);
890  }
891 
892  for (const RegisterMaskPair &Use : RegOpers.Uses) {
893  unsigned Reg = Use.RegUnit;
894  LaneBitmask LiveMask = LiveRegs.contains(Reg);
895  LaneBitmask LiveIn = Use.LaneMask & ~LiveMask;
896  if (LiveIn.any()) {
897  discoverLiveIn(RegisterMaskPair(Reg, LiveIn));
898  increaseRegPressure(Reg, LiveMask, LiveMask | LiveIn);
899  LiveRegs.insert(RegisterMaskPair(Reg, LiveIn));
900  }
901  // Kill liveness at last uses.
902  if (RequireIntervals) {
903  LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
904  if (LastUseMask.any()) {
905  LiveRegs.erase(RegisterMaskPair(Reg, LastUseMask));
906  decreaseRegPressure(Reg, LiveMask, LiveMask & ~LastUseMask);
907  }
908  }
909  }
910 
911  // Generate liveness for defs.
912  for (const RegisterMaskPair &Def : RegOpers.Defs) {
913  LaneBitmask PreviousMask = LiveRegs.insert(Def);
914  LaneBitmask NewMask = PreviousMask | Def.LaneMask;
915  increaseRegPressure(Def.RegUnit, PreviousMask, NewMask);
916  }
917 
918  // Boost pressure for all dead defs together.
919  bumpDeadDefs(RegOpers.DeadDefs);
920 
921  // Find the next instruction.
922  CurrPos = skipDebugInstructionsForward(std::next(CurrPos), MBB->end());
923 }
924 
926  const MachineInstr &MI = *CurrPos;
927  RegisterOperands RegOpers;
928  RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
929  if (TrackLaneMasks) {
930  SlotIndex SlotIdx = getCurrSlot();
931  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
932  }
933  advance(RegOpers);
934 }
935 
936 /// Find the max change in excess pressure across all sets.
938  ArrayRef<unsigned> NewPressureVec,
939  RegPressureDelta &Delta,
940  const RegisterClassInfo *RCI,
941  ArrayRef<unsigned> LiveThruPressureVec) {
942  Delta.Excess = PressureChange();
943  for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
944  unsigned POld = OldPressureVec[i];
945  unsigned PNew = NewPressureVec[i];
946  int PDiff = (int)PNew - (int)POld;
947  if (!PDiff) // No change in this set in the common case.
948  continue;
949  // Only consider change beyond the limit.
950  unsigned Limit = RCI->getRegPressureSetLimit(i);
951  if (!LiveThruPressureVec.empty())
952  Limit += LiveThruPressureVec[i];
953 
954  if (Limit > POld) {
955  if (Limit > PNew)
956  PDiff = 0; // Under the limit
957  else
958  PDiff = PNew - Limit; // Just exceeded limit.
959  } else if (Limit > PNew)
960  PDiff = Limit - POld; // Just obeyed limit.
961 
962  if (PDiff) {
963  Delta.Excess = PressureChange(i);
964  Delta.Excess.setUnitInc(PDiff);
965  break;
966  }
967  }
968 }
969 
970 /// Find the max change in max pressure that either surpasses a critical PSet
971 /// limit or exceeds the current MaxPressureLimit.
972 ///
973 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
974 /// silly. It's done now to demonstrate the concept but will go away with a
975 /// RegPressureTracker API change to work with pressure differences.
976 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
977  ArrayRef<unsigned> NewMaxPressureVec,
978  ArrayRef<PressureChange> CriticalPSets,
979  ArrayRef<unsigned> MaxPressureLimit,
980  RegPressureDelta &Delta) {
981  Delta.CriticalMax = PressureChange();
982  Delta.CurrentMax = PressureChange();
983 
984  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
985  for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
986  unsigned POld = OldMaxPressureVec[i];
987  unsigned PNew = NewMaxPressureVec[i];
988  if (PNew == POld) // No change in this set in the common case.
989  continue;
990 
991  if (!Delta.CriticalMax.isValid()) {
992  while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
993  ++CritIdx;
994 
995  if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
996  int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
997  if (PDiff > 0) {
998  Delta.CriticalMax = PressureChange(i);
999  Delta.CriticalMax.setUnitInc(PDiff);
1000  }
1001  }
1002  }
1003  // Find the first increase above MaxPressureLimit.
1004  // (Ignores negative MDiff).
1005  if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
1006  Delta.CurrentMax = PressureChange(i);
1007  Delta.CurrentMax.setUnitInc(PNew - POld);
1008  if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
1009  break;
1010  }
1011  }
1012 }
1013 
1014 /// Record the upward impact of a single instruction on current register
1015 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1016 /// not discover live in/outs.
1017 ///
1018 /// This is intended for speculative queries. It leaves pressure inconsistent
1019 /// with the current position, so must be restored by the caller.
1021  assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
1022 
1023  SlotIndex SlotIdx;
1024  if (RequireIntervals)
1025  SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1026 
1027  // Account for register pressure similar to RegPressureTracker::recede().
1028  RegisterOperands RegOpers;
1029  RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, /*IgnoreDead=*/true);
1030  assert(RegOpers.DeadDefs.size() == 0);
1031  if (TrackLaneMasks)
1032  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1033  else if (RequireIntervals)
1034  RegOpers.detectDeadDefs(*MI, *LIS);
1035 
1036  // Boost max pressure for all dead defs together.
1037  // Since CurrSetPressure and MaxSetPressure
1038  bumpDeadDefs(RegOpers.DeadDefs);
1039 
1040  // Kill liveness at live defs.
1041  for (const RegisterMaskPair &P : RegOpers.Defs) {
1042  unsigned Reg = P.RegUnit;
1043  LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1044  LaneBitmask UseLanes = getRegLanes(RegOpers.Uses, Reg);
1045  LaneBitmask DefLanes = P.LaneMask;
1046  LaneBitmask LiveAfter = (LiveLanes & ~DefLanes) | UseLanes;
1047  decreaseRegPressure(Reg, LiveLanes, LiveAfter);
1048  }
1049  // Generate liveness for uses.
1050  for (const RegisterMaskPair &P : RegOpers.Uses) {
1051  unsigned Reg = P.RegUnit;
1052  LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1053  LaneBitmask LiveAfter = LiveLanes | P.LaneMask;
1054  increaseRegPressure(Reg, LiveLanes, LiveAfter);
1055  }
1056 }
1057 
1058 /// Consider the pressure increase caused by traversing this instruction
1059 /// bottom-up. Find the pressure set with the most change beyond its pressure
1060 /// limit based on the tracker's current pressure, and return the change in
1061 /// number of register units of that pressure set introduced by this
1062 /// instruction.
1063 ///
1064 /// This assumes that the current LiveOut set is sufficient.
1065 ///
1066 /// This is expensive for an on-the-fly query because it calls
1067 /// bumpUpwardPressure to recompute the pressure sets based on current
1068 /// liveness. This mainly exists to verify correctness, e.g. with
1069 /// -verify-misched. getUpwardPressureDelta is the fast version of this query
1070 /// that uses the per-SUnit cache of the PressureDiff.
1073  RegPressureDelta &Delta,
1074  ArrayRef<PressureChange> CriticalPSets,
1075  ArrayRef<unsigned> MaxPressureLimit) {
1076  // Snapshot Pressure.
1077  // FIXME: The snapshot heap space should persist. But I'm planning to
1078  // summarize the pressure effect so we don't need to snapshot at all.
1079  std::vector<unsigned> SavedPressure = CurrSetPressure;
1080  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1081 
1082  bumpUpwardPressure(MI);
1083 
1084  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1085  LiveThruPressure);
1086  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1087  MaxPressureLimit, Delta);
1088  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1089  Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1090 
1091  // Restore the tracker's state.
1092  P.MaxSetPressure.swap(SavedMaxPressure);
1093  CurrSetPressure.swap(SavedPressure);
1094 
1095 #ifndef NDEBUG
1096  if (!PDiff)
1097  return;
1098 
1099  // Check if the alternate algorithm yields the same result.
1100  RegPressureDelta Delta2;
1101  getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
1102  if (Delta != Delta2) {
1103  dbgs() << "PDiff: ";
1104  PDiff->dump(*TRI);
1105  dbgs() << "DELTA: " << *MI;
1106  if (Delta.Excess.isValid())
1107  dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
1108  << " " << Delta.Excess.getUnitInc() << "\n";
1109  if (Delta.CriticalMax.isValid())
1110  dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
1111  << " " << Delta.CriticalMax.getUnitInc() << "\n";
1112  if (Delta.CurrentMax.isValid())
1113  dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
1114  << " " << Delta.CurrentMax.getUnitInc() << "\n";
1115  if (Delta2.Excess.isValid())
1116  dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
1117  << " " << Delta2.Excess.getUnitInc() << "\n";
1118  if (Delta2.CriticalMax.isValid())
1119  dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
1120  << " " << Delta2.CriticalMax.getUnitInc() << "\n";
1121  if (Delta2.CurrentMax.isValid())
1122  dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
1123  << " " << Delta2.CurrentMax.getUnitInc() << "\n";
1124  llvm_unreachable("RegP Delta Mismatch");
1125  }
1126 #endif
1127 }
1128 
1129 /// This is the fast version of querying register pressure that does not
1130 /// directly depend on current liveness.
1131 ///
1132 /// @param Delta captures information needed for heuristics.
1133 ///
1134 /// @param CriticalPSets Are the pressure sets that are known to exceed some
1135 /// limit within the region, not necessarily at the current position.
1136 ///
1137 /// @param MaxPressureLimit Is the max pressure within the region, not
1138 /// necessarily at the current position.
1141  RegPressureDelta &Delta,
1142  ArrayRef<PressureChange> CriticalPSets,
1143  ArrayRef<unsigned> MaxPressureLimit) const {
1144  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1146  PDiffI = PDiff.begin(), PDiffE = PDiff.end();
1147  PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
1148 
1149  unsigned PSetID = PDiffI->getPSet();
1150  unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
1151  if (!LiveThruPressure.empty())
1152  Limit += LiveThruPressure[PSetID];
1153 
1154  unsigned POld = CurrSetPressure[PSetID];
1155  unsigned MOld = P.MaxSetPressure[PSetID];
1156  unsigned MNew = MOld;
1157  // Ignore DeadDefs here because they aren't captured by PressureChange.
1158  unsigned PNew = POld + PDiffI->getUnitInc();
1159  assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
1160  && "PSet overflow/underflow");
1161  if (PNew > MOld)
1162  MNew = PNew;
1163  // Check if current pressure has exceeded the limit.
1164  if (!Delta.Excess.isValid()) {
1165  unsigned ExcessInc = 0;
1166  if (PNew > Limit)
1167  ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
1168  else if (POld > Limit)
1169  ExcessInc = Limit - POld;
1170  if (ExcessInc) {
1171  Delta.Excess = PressureChange(PSetID);
1172  Delta.Excess.setUnitInc(ExcessInc);
1173  }
1174  }
1175  // Check if max pressure has exceeded a critical pressure set max.
1176  if (MNew == MOld)
1177  continue;
1178  if (!Delta.CriticalMax.isValid()) {
1179  while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
1180  ++CritIdx;
1181 
1182  if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
1183  int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
1184  if (CritInc > 0 && CritInc <= std::numeric_limits<int16_t>::max()) {
1185  Delta.CriticalMax = PressureChange(PSetID);
1186  Delta.CriticalMax.setUnitInc(CritInc);
1187  }
1188  }
1189  }
1190  // Check if max pressure has exceeded the current max.
1191  if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
1192  Delta.CurrentMax = PressureChange(PSetID);
1193  Delta.CurrentMax.setUnitInc(MNew - MOld);
1194  }
1195  }
1196 }
1197 
1198 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
1199 /// The query starts with a lane bitmask which gets lanes/bits removed for every
1200 /// use we find.
1201 static LaneBitmask findUseBetween(unsigned Reg, LaneBitmask LastUseMask,
1202  SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1203  const MachineRegisterInfo &MRI,
1204  const LiveIntervals *LIS) {
1205  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
1206  for (const MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1207  if (MO.isUndef())
1208  continue;
1209  const MachineInstr *MI = MO.getParent();
1210  SlotIndex InstSlot = LIS->getInstructionIndex(*MI).getRegSlot();
1211  if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) {
1212  unsigned SubRegIdx = MO.getSubReg();
1213  LaneBitmask UseMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
1214  LastUseMask &= ~UseMask;
1215  if (LastUseMask.none())
1216  return LaneBitmask::getNone();
1217  }
1218  }
1219  return LastUseMask;
1220 }
1221 
1223  SlotIndex Pos) const {
1224  assert(RequireIntervals);
1225  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1227  [](const LiveRange &LR, SlotIndex Pos) {
1228  return LR.liveAt(Pos);
1229  });
1230 }
1231 
1233  SlotIndex Pos) const {
1234  assert(RequireIntervals);
1235  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit,
1237  [](const LiveRange &LR, SlotIndex Pos) {
1238  const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1239  return S != nullptr && S->end == Pos.getRegSlot();
1240  });
1241 }
1242 
1244  SlotIndex Pos) const {
1245  assert(RequireIntervals);
1246  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1248  [](const LiveRange &LR, SlotIndex Pos) {
1249  const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1250  return S != nullptr && S->start < Pos.getRegSlot(true) &&
1251  S->end != Pos.getDeadSlot();
1252  });
1253 }
1254 
1255 /// Record the downward impact of a single instruction on current register
1256 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1257 /// not discover live in/outs.
1258 ///
1259 /// This is intended for speculative queries. It leaves pressure inconsistent
1260 /// with the current position, so must be restored by the caller.
1262  assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
1263 
1264  SlotIndex SlotIdx;
1265  if (RequireIntervals)
1266  SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1267 
1268  // Account for register pressure similar to RegPressureTracker::recede().
1269  RegisterOperands RegOpers;
1270  RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, false);
1271  if (TrackLaneMasks)
1272  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1273 
1274  if (RequireIntervals) {
1275  for (const RegisterMaskPair &Use : RegOpers.Uses) {
1276  unsigned Reg = Use.RegUnit;
1277  LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
1278  if (LastUseMask.none())
1279  continue;
1280  // The LastUseMask is queried from the liveness information of instruction
1281  // which may be further down the schedule. Some lanes may actually not be
1282  // last uses for the current position.
1283  // FIXME: allow the caller to pass in the list of vreg uses that remain
1284  // to be bottom-scheduled to avoid searching uses at each query.
1285  SlotIndex CurrIdx = getCurrSlot();
1286  LastUseMask
1287  = findUseBetween(Reg, LastUseMask, CurrIdx, SlotIdx, *MRI, LIS);
1288  if (LastUseMask.none())
1289  continue;
1290 
1291  LaneBitmask LiveMask = LiveRegs.contains(Reg);
1292  LaneBitmask NewMask = LiveMask & ~LastUseMask;
1293  decreaseRegPressure(Reg, LiveMask, NewMask);
1294  }
1295  }
1296 
1297  // Generate liveness for defs.
1298  for (const RegisterMaskPair &Def : RegOpers.Defs) {
1299  unsigned Reg = Def.RegUnit;
1300  LaneBitmask LiveMask = LiveRegs.contains(Reg);
1301  LaneBitmask NewMask = LiveMask | Def.LaneMask;
1302  increaseRegPressure(Reg, LiveMask, NewMask);
1303  }
1304 
1305  // Boost pressure for all dead defs together.
1306  bumpDeadDefs(RegOpers.DeadDefs);
1307 }
1308 
1309 /// Consider the pressure increase caused by traversing this instruction
1310 /// top-down. Find the register class with the most change in its pressure limit
1311 /// based on the tracker's current pressure, and return the number of excess
1312 /// register units of that pressure set introduced by this instruction.
1313 ///
1314 /// This assumes that the current LiveIn set is sufficient.
1315 ///
1316 /// This is expensive for an on-the-fly query because it calls
1317 /// bumpDownwardPressure to recompute the pressure sets based on current
1318 /// liveness. We don't yet have a fast version of downward pressure tracking
1319 /// analogous to getUpwardPressureDelta.
1322  ArrayRef<PressureChange> CriticalPSets,
1323  ArrayRef<unsigned> MaxPressureLimit) {
1324  // Snapshot Pressure.
1325  std::vector<unsigned> SavedPressure = CurrSetPressure;
1326  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1327 
1328  bumpDownwardPressure(MI);
1329 
1330  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1331  LiveThruPressure);
1332  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1333  MaxPressureLimit, Delta);
1334  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1335  Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1336 
1337  // Restore the tracker's state.
1338  P.MaxSetPressure.swap(SavedMaxPressure);
1339  CurrSetPressure.swap(SavedPressure);
1340 }
1341 
1342 /// Get the pressure of each PSet after traversing this instruction bottom-up.
1345  std::vector<unsigned> &PressureResult,
1346  std::vector<unsigned> &MaxPressureResult) {
1347  // Snapshot pressure.
1348  PressureResult = CurrSetPressure;
1349  MaxPressureResult = P.MaxSetPressure;
1350 
1351  bumpUpwardPressure(MI);
1352 
1353  // Current pressure becomes the result. Restore current pressure.
1354  P.MaxSetPressure.swap(MaxPressureResult);
1355  CurrSetPressure.swap(PressureResult);
1356 }
1357 
1358 /// Get the pressure of each PSet after traversing this instruction top-down.
1361  std::vector<unsigned> &PressureResult,
1362  std::vector<unsigned> &MaxPressureResult) {
1363  // Snapshot pressure.
1364  PressureResult = CurrSetPressure;
1365  MaxPressureResult = P.MaxSetPressure;
1366 
1367  bumpDownwardPressure(MI);
1368 
1369  // Current pressure becomes the result. Restore current pressure.
1370  P.MaxSetPressure.swap(MaxPressureResult);
1371  CurrSetPressure.swap(PressureResult);
1372 }
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:242
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...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:449
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.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void decreaseRegPressure(unsigned RegUnit, LaneBitmask PreviousMask, LaneBitmask NewMask)
static LaneBitmask getAll()
Definition: LaneBitmask.h:84
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
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 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:117
A live range for subregisters.
Definition: LiveInterval.h:645
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:94
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:157
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:260
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:56
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:42
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:723
Result of a LiveRange query.
Definition: LiveInterval.h:90
Reg
All possible values of the reg field in the ModR/M byte.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:751
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:736
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:255
const RegList & Regs
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:529
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...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:389
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:149
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...
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:52
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.
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:449
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
bool hasUntiedDef(unsigned VirtReg) const
#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.
bool isDebugValue() const
Definition: MachineInstr.h:816
MachineOperand class - Representation of each machine instruction operand.
static LaneBitmask getNone()
Definition: LaneBitmask.h:83
iterator end() const
Definition: ArrayRef.h:138
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:923
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:59
void dump(const TargetRegisterInfo &TRI) const
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
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:53
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.
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:396
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
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
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
LaneBitmask getLiveLanesAt(unsigned RegUnit, SlotIndex Pos) const
unsigned getWeight() const
unsigned getPSet() const
auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:795
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
Printable PrintVRegOrUnit(unsigned VRegOrUnit, const TargetRegisterInfo *TRI)
Create Printable object to print virtual registers and physical registers on a raw_ostream.
Register Usage Information Collector
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144
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.