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)
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 
859  const MachineInstr &MI = *CurrPos;
860  RegisterOperands RegOpers;
861  RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
862  if (TrackLaneMasks) {
863  SlotIndex SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
864  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
865  } else if (RequireIntervals) {
866  RegOpers.detectDeadDefs(MI, *LIS);
867  }
868 
869  recede(RegOpers, LiveUses);
870 }
871 
872 /// Advance across the current instruction.
874  assert(!TrackUntiedDefs && "unsupported mode");
875  assert(CurrPos != MBB->end());
876  if (!isTopClosed())
877  closeTop();
878 
879  SlotIndex SlotIdx;
880  if (RequireIntervals)
881  SlotIdx = getCurrSlot();
882 
883  // Open the bottom of the region using slot indexes.
884  if (isBottomClosed()) {
885  if (RequireIntervals)
886  static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
887  else
888  static_cast<RegionPressure&>(P).openBottom(CurrPos);
889  }
890 
891  for (const RegisterMaskPair &Use : RegOpers.Uses) {
892  unsigned Reg = Use.RegUnit;
893  LaneBitmask LiveMask = LiveRegs.contains(Reg);
894  LaneBitmask LiveIn = Use.LaneMask & ~LiveMask;
895  if (LiveIn.any()) {
896  discoverLiveIn(RegisterMaskPair(Reg, LiveIn));
897  increaseRegPressure(Reg, LiveMask, LiveMask | LiveIn);
898  LiveRegs.insert(RegisterMaskPair(Reg, LiveIn));
899  }
900  // Kill liveness at last uses.
901  if (RequireIntervals) {
902  LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
903  if (LastUseMask.any()) {
904  LiveRegs.erase(RegisterMaskPair(Reg, LastUseMask));
905  decreaseRegPressure(Reg, LiveMask, LiveMask & ~LastUseMask);
906  }
907  }
908  }
909 
910  // Generate liveness for defs.
911  for (const RegisterMaskPair &Def : RegOpers.Defs) {
912  LaneBitmask PreviousMask = LiveRegs.insert(Def);
913  LaneBitmask NewMask = PreviousMask | Def.LaneMask;
914  increaseRegPressure(Def.RegUnit, PreviousMask, NewMask);
915  }
916 
917  // Boost pressure for all dead defs together.
918  bumpDeadDefs(RegOpers.DeadDefs);
919 
920  // Find the next instruction.
921  CurrPos = skipDebugInstructionsForward(std::next(CurrPos), MBB->end());
922 }
923 
925  const MachineInstr &MI = *CurrPos;
926  RegisterOperands RegOpers;
927  RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
928  if (TrackLaneMasks) {
929  SlotIndex SlotIdx = getCurrSlot();
930  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
931  }
932  advance(RegOpers);
933 }
934 
935 /// Find the max change in excess pressure across all sets.
937  ArrayRef<unsigned> NewPressureVec,
938  RegPressureDelta &Delta,
939  const RegisterClassInfo *RCI,
940  ArrayRef<unsigned> LiveThruPressureVec) {
941  Delta.Excess = PressureChange();
942  for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
943  unsigned POld = OldPressureVec[i];
944  unsigned PNew = NewPressureVec[i];
945  int PDiff = (int)PNew - (int)POld;
946  if (!PDiff) // No change in this set in the common case.
947  continue;
948  // Only consider change beyond the limit.
949  unsigned Limit = RCI->getRegPressureSetLimit(i);
950  if (!LiveThruPressureVec.empty())
951  Limit += LiveThruPressureVec[i];
952 
953  if (Limit > POld) {
954  if (Limit > PNew)
955  PDiff = 0; // Under the limit
956  else
957  PDiff = PNew - Limit; // Just exceeded limit.
958  } else if (Limit > PNew)
959  PDiff = Limit - POld; // Just obeyed limit.
960 
961  if (PDiff) {
962  Delta.Excess = PressureChange(i);
963  Delta.Excess.setUnitInc(PDiff);
964  break;
965  }
966  }
967 }
968 
969 /// Find the max change in max pressure that either surpasses a critical PSet
970 /// limit or exceeds the current MaxPressureLimit.
971 ///
972 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
973 /// silly. It's done now to demonstrate the concept but will go away with a
974 /// RegPressureTracker API change to work with pressure differences.
975 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
976  ArrayRef<unsigned> NewMaxPressureVec,
977  ArrayRef<PressureChange> CriticalPSets,
978  ArrayRef<unsigned> MaxPressureLimit,
979  RegPressureDelta &Delta) {
980  Delta.CriticalMax = PressureChange();
981  Delta.CurrentMax = PressureChange();
982 
983  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
984  for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
985  unsigned POld = OldMaxPressureVec[i];
986  unsigned PNew = NewMaxPressureVec[i];
987  if (PNew == POld) // No change in this set in the common case.
988  continue;
989 
990  if (!Delta.CriticalMax.isValid()) {
991  while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
992  ++CritIdx;
993 
994  if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
995  int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
996  if (PDiff > 0) {
997  Delta.CriticalMax = PressureChange(i);
998  Delta.CriticalMax.setUnitInc(PDiff);
999  }
1000  }
1001  }
1002  // Find the first increase above MaxPressureLimit.
1003  // (Ignores negative MDiff).
1004  if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
1005  Delta.CurrentMax = PressureChange(i);
1006  Delta.CurrentMax.setUnitInc(PNew - POld);
1007  if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
1008  break;
1009  }
1010  }
1011 }
1012 
1013 /// Record the upward impact of a single instruction on current register
1014 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1015 /// not discover live in/outs.
1016 ///
1017 /// This is intended for speculative queries. It leaves pressure inconsistent
1018 /// with the current position, so must be restored by the caller.
1020  assert(!MI->isDebugInstr() && "Expect a nondebug instruction.");
1021 
1022  SlotIndex SlotIdx;
1023  if (RequireIntervals)
1024  SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1025 
1026  // Account for register pressure similar to RegPressureTracker::recede().
1027  RegisterOperands RegOpers;
1028  RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, /*IgnoreDead=*/true);
1029  assert(RegOpers.DeadDefs.size() == 0);
1030  if (TrackLaneMasks)
1031  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1032  else if (RequireIntervals)
1033  RegOpers.detectDeadDefs(*MI, *LIS);
1034 
1035  // Boost max pressure for all dead defs together.
1036  // Since CurrSetPressure and MaxSetPressure
1037  bumpDeadDefs(RegOpers.DeadDefs);
1038 
1039  // Kill liveness at live defs.
1040  for (const RegisterMaskPair &P : RegOpers.Defs) {
1041  unsigned Reg = P.RegUnit;
1042  LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1043  LaneBitmask UseLanes = getRegLanes(RegOpers.Uses, Reg);
1044  LaneBitmask DefLanes = P.LaneMask;
1045  LaneBitmask LiveAfter = (LiveLanes & ~DefLanes) | UseLanes;
1046  decreaseRegPressure(Reg, LiveLanes, LiveAfter);
1047  }
1048  // Generate liveness for uses.
1049  for (const RegisterMaskPair &P : RegOpers.Uses) {
1050  unsigned Reg = P.RegUnit;
1051  LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1052  LaneBitmask LiveAfter = LiveLanes | P.LaneMask;
1053  increaseRegPressure(Reg, LiveLanes, LiveAfter);
1054  }
1055 }
1056 
1057 /// Consider the pressure increase caused by traversing this instruction
1058 /// bottom-up. Find the pressure set with the most change beyond its pressure
1059 /// limit based on the tracker's current pressure, and return the change in
1060 /// number of register units of that pressure set introduced by this
1061 /// instruction.
1062 ///
1063 /// This assumes that the current LiveOut set is sufficient.
1064 ///
1065 /// This is expensive for an on-the-fly query because it calls
1066 /// bumpUpwardPressure to recompute the pressure sets based on current
1067 /// liveness. This mainly exists to verify correctness, e.g. with
1068 /// -verify-misched. getUpwardPressureDelta is the fast version of this query
1069 /// that uses the per-SUnit cache of the PressureDiff.
1072  RegPressureDelta &Delta,
1073  ArrayRef<PressureChange> CriticalPSets,
1074  ArrayRef<unsigned> MaxPressureLimit) {
1075  // Snapshot Pressure.
1076  // FIXME: The snapshot heap space should persist. But I'm planning to
1077  // summarize the pressure effect so we don't need to snapshot at all.
1078  std::vector<unsigned> SavedPressure = CurrSetPressure;
1079  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1080 
1081  bumpUpwardPressure(MI);
1082 
1083  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1084  LiveThruPressure);
1085  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1086  MaxPressureLimit, Delta);
1087  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1088  Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1089 
1090  // Restore the tracker's state.
1091  P.MaxSetPressure.swap(SavedMaxPressure);
1092  CurrSetPressure.swap(SavedPressure);
1093 
1094 #ifndef NDEBUG
1095  if (!PDiff)
1096  return;
1097 
1098  // Check if the alternate algorithm yields the same result.
1099  RegPressureDelta Delta2;
1100  getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
1101  if (Delta != Delta2) {
1102  dbgs() << "PDiff: ";
1103  PDiff->dump(*TRI);
1104  dbgs() << "DELTA: " << *MI;
1105  if (Delta.Excess.isValid())
1106  dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
1107  << " " << Delta.Excess.getUnitInc() << "\n";
1108  if (Delta.CriticalMax.isValid())
1109  dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
1110  << " " << Delta.CriticalMax.getUnitInc() << "\n";
1111  if (Delta.CurrentMax.isValid())
1112  dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
1113  << " " << Delta.CurrentMax.getUnitInc() << "\n";
1114  if (Delta2.Excess.isValid())
1115  dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
1116  << " " << Delta2.Excess.getUnitInc() << "\n";
1117  if (Delta2.CriticalMax.isValid())
1118  dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
1119  << " " << Delta2.CriticalMax.getUnitInc() << "\n";
1120  if (Delta2.CurrentMax.isValid())
1121  dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
1122  << " " << Delta2.CurrentMax.getUnitInc() << "\n";
1123  llvm_unreachable("RegP Delta Mismatch");
1124  }
1125 #endif
1126 }
1127 
1128 /// This is the fast version of querying register pressure that does not
1129 /// directly depend on current liveness.
1130 ///
1131 /// @param Delta captures information needed for heuristics.
1132 ///
1133 /// @param CriticalPSets Are the pressure sets that are known to exceed some
1134 /// limit within the region, not necessarily at the current position.
1135 ///
1136 /// @param MaxPressureLimit Is the max pressure within the region, not
1137 /// necessarily at the current position.
1140  RegPressureDelta &Delta,
1141  ArrayRef<PressureChange> CriticalPSets,
1142  ArrayRef<unsigned> MaxPressureLimit) const {
1143  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1145  PDiffI = PDiff.begin(), PDiffE = PDiff.end();
1146  PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
1147 
1148  unsigned PSetID = PDiffI->getPSet();
1149  unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
1150  if (!LiveThruPressure.empty())
1151  Limit += LiveThruPressure[PSetID];
1152 
1153  unsigned POld = CurrSetPressure[PSetID];
1154  unsigned MOld = P.MaxSetPressure[PSetID];
1155  unsigned MNew = MOld;
1156  // Ignore DeadDefs here because they aren't captured by PressureChange.
1157  unsigned PNew = POld + PDiffI->getUnitInc();
1158  assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
1159  && "PSet overflow/underflow");
1160  if (PNew > MOld)
1161  MNew = PNew;
1162  // Check if current pressure has exceeded the limit.
1163  if (!Delta.Excess.isValid()) {
1164  unsigned ExcessInc = 0;
1165  if (PNew > Limit)
1166  ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
1167  else if (POld > Limit)
1168  ExcessInc = Limit - POld;
1169  if (ExcessInc) {
1170  Delta.Excess = PressureChange(PSetID);
1171  Delta.Excess.setUnitInc(ExcessInc);
1172  }
1173  }
1174  // Check if max pressure has exceeded a critical pressure set max.
1175  if (MNew == MOld)
1176  continue;
1177  if (!Delta.CriticalMax.isValid()) {
1178  while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
1179  ++CritIdx;
1180 
1181  if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
1182  int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
1183  if (CritInc > 0 && CritInc <= std::numeric_limits<int16_t>::max()) {
1184  Delta.CriticalMax = PressureChange(PSetID);
1185  Delta.CriticalMax.setUnitInc(CritInc);
1186  }
1187  }
1188  }
1189  // Check if max pressure has exceeded the current max.
1190  if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
1191  Delta.CurrentMax = PressureChange(PSetID);
1192  Delta.CurrentMax.setUnitInc(MNew - MOld);
1193  }
1194  }
1195 }
1196 
1197 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
1198 /// The query starts with a lane bitmask which gets lanes/bits removed for every
1199 /// use we find.
1200 static LaneBitmask findUseBetween(unsigned Reg, LaneBitmask LastUseMask,
1201  SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1202  const MachineRegisterInfo &MRI,
1203  const LiveIntervals *LIS) {
1205  for (const MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1206  if (MO.isUndef())
1207  continue;
1208  const MachineInstr *MI = MO.getParent();
1209  SlotIndex InstSlot = LIS->getInstructionIndex(*MI).getRegSlot();
1210  if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) {
1211  unsigned SubRegIdx = MO.getSubReg();
1212  LaneBitmask UseMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
1213  LastUseMask &= ~UseMask;
1214  if (LastUseMask.none())
1215  return LaneBitmask::getNone();
1216  }
1217  }
1218  return LastUseMask;
1219 }
1220 
1222  SlotIndex Pos) const {
1223  assert(RequireIntervals);
1224  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1226  [](const LiveRange &LR, SlotIndex Pos) {
1227  return LR.liveAt(Pos);
1228  });
1229 }
1230 
1232  SlotIndex Pos) const {
1233  assert(RequireIntervals);
1234  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit,
1236  [](const LiveRange &LR, SlotIndex Pos) {
1237  const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1238  return S != nullptr && S->end == Pos.getRegSlot();
1239  });
1240 }
1241 
1243  SlotIndex Pos) const {
1244  assert(RequireIntervals);
1245  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1247  [](const LiveRange &LR, SlotIndex Pos) {
1248  const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1249  return S != nullptr && S->start < Pos.getRegSlot(true) &&
1250  S->end != Pos.getDeadSlot();
1251  });
1252 }
1253 
1254 /// Record the downward impact of a single instruction on current register
1255 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1256 /// not discover live in/outs.
1257 ///
1258 /// This is intended for speculative queries. It leaves pressure inconsistent
1259 /// with the current position, so must be restored by the caller.
1261  assert(!MI->isDebugInstr() && "Expect a nondebug instruction.");
1262 
1263  SlotIndex SlotIdx;
1264  if (RequireIntervals)
1265  SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1266 
1267  // Account for register pressure similar to RegPressureTracker::recede().
1268  RegisterOperands RegOpers;
1269  RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, false);
1270  if (TrackLaneMasks)
1271  RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1272 
1273  if (RequireIntervals) {
1274  for (const RegisterMaskPair &Use : RegOpers.Uses) {
1275  unsigned Reg = Use.RegUnit;
1276  LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
1277  if (LastUseMask.none())
1278  continue;
1279  // The LastUseMask is queried from the liveness information of instruction
1280  // which may be further down the schedule. Some lanes may actually not be
1281  // last uses for the current position.
1282  // FIXME: allow the caller to pass in the list of vreg uses that remain
1283  // to be bottom-scheduled to avoid searching uses at each query.
1284  SlotIndex CurrIdx = getCurrSlot();
1285  LastUseMask
1286  = findUseBetween(Reg, LastUseMask, CurrIdx, SlotIdx, *MRI, LIS);
1287  if (LastUseMask.none())
1288  continue;
1289 
1290  LaneBitmask LiveMask = LiveRegs.contains(Reg);
1291  LaneBitmask NewMask = LiveMask & ~LastUseMask;
1292  decreaseRegPressure(Reg, LiveMask, NewMask);
1293  }
1294  }
1295 
1296  // Generate liveness for defs.
1297  for (const RegisterMaskPair &Def : RegOpers.Defs) {
1298  unsigned Reg = Def.RegUnit;
1299  LaneBitmask LiveMask = LiveRegs.contains(Reg);
1300  LaneBitmask NewMask = LiveMask | Def.LaneMask;
1301  increaseRegPressure(Reg, LiveMask, NewMask);
1302  }
1303 
1304  // Boost pressure for all dead defs together.
1305  bumpDeadDefs(RegOpers.DeadDefs);
1306 }
1307 
1308 /// Consider the pressure increase caused by traversing this instruction
1309 /// top-down. Find the register class with the most change in its pressure limit
1310 /// based on the tracker's current pressure, and return the number of excess
1311 /// register units of that pressure set introduced by this instruction.
1312 ///
1313 /// This assumes that the current LiveIn set is sufficient.
1314 ///
1315 /// This is expensive for an on-the-fly query because it calls
1316 /// bumpDownwardPressure to recompute the pressure sets based on current
1317 /// liveness. We don't yet have a fast version of downward pressure tracking
1318 /// analogous to getUpwardPressureDelta.
1321  ArrayRef<PressureChange> CriticalPSets,
1322  ArrayRef<unsigned> MaxPressureLimit) {
1323  // Snapshot Pressure.
1324  std::vector<unsigned> SavedPressure = CurrSetPressure;
1325  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1326 
1327  bumpDownwardPressure(MI);
1328 
1329  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1330  LiveThruPressure);
1331  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1332  MaxPressureLimit, Delta);
1333  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1334  Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1335 
1336  // Restore the tracker's state.
1337  P.MaxSetPressure.swap(SavedMaxPressure);
1338  CurrSetPressure.swap(SavedPressure);
1339 }
1340 
1341 /// Get the pressure of each PSet after traversing this instruction bottom-up.
1344  std::vector<unsigned> &PressureResult,
1345  std::vector<unsigned> &MaxPressureResult) {
1346  // Snapshot pressure.
1347  PressureResult = CurrSetPressure;
1348  MaxPressureResult = P.MaxSetPressure;
1349 
1350  bumpUpwardPressure(MI);
1351 
1352  // Current pressure becomes the result. Restore current pressure.
1353  P.MaxSetPressure.swap(MaxPressureResult);
1354  CurrSetPressure.swap(PressureResult);
1355 }
1356 
1357 /// Get the pressure of each PSet after traversing this instruction top-down.
1360  std::vector<unsigned> &PressureResult,
1361  std::vector<unsigned> &MaxPressureResult) {
1362  // Snapshot pressure.
1363  PressureResult = CurrSetPressure;
1364  MaxPressureResult = P.MaxSetPressure;
1365 
1366  bumpDownwardPressure(MI);
1367 
1368  // Current pressure becomes the result. Restore current pressure.
1369  P.MaxSetPressure.swap(MaxPressureResult);
1370  CurrSetPressure.swap(PressureResult);
1371 }
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:464
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:808
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:437
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.