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