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