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