RegisterPressure.cpp revision 360784 
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
14#include "llvm/CodeGen/RegisterPressure.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/CodeGen/LiveInterval.h"
19#include "llvm/CodeGen/LiveIntervals.h"
20#include "llvm/CodeGen/MachineBasicBlock.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/CodeGen/MachineInstrBundle.h"
24#include "llvm/CodeGen/MachineOperand.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/CodeGen/RegisterClassInfo.h"
27#include "llvm/CodeGen/SlotIndexes.h"
28#include "llvm/CodeGen/TargetRegisterInfo.h"
29#include "llvm/CodeGen/TargetSubtargetInfo.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"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Support/raw_ostream.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
47using namespace llvm;
48
49/// Increase pressure for each pressure set provided by TargetRegisterInfo.
50static 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.
64static 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)
80LLVM_DUMP_METHOD
81void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
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
94LLVM_DUMP_METHOD
95void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
96  dbgs() << "Max Pressure: ";
97  dumpRegSetPressure(MaxSetPressure, TRI);
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
116LLVM_DUMP_METHOD
117void RegPressureTracker::dump() const {
118  if (!isTopClosed() || !isBottomClosed()) {
119    dbgs() << "Curr Pressure: ";
120    dumpRegSetPressure(CurrSetPressure, TRI);
121  }
122  P.dump(TRI);
123}
124
125LLVM_DUMP_METHOD
126void PressureDiff::dump(const TargetRegisterInfo &TRI) const {
127  const char *sep = "";
128  for (const PressureChange &Change : *this) {
129    if (!Change.isValid())
130      break;
131    dbgs() << sep << TRI.getRegPressureSetName(Change.getPSet())
132           << " " << Change.getUnitInc();
133    sep = "    ";
134  }
135  dbgs() << '\n';
136}
137
138LLVM_DUMP_METHOD
139void PressureChange::dump() const {
140  dbgs() << "[" << getPSetOrMax() << ", " << getUnitInc() << "]\n";
141}
142
143void RegPressureDelta::dump() const {
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
155void RegPressureTracker::increaseRegPressure(unsigned RegUnit,
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
170void RegPressureTracker::decreaseRegPressure(unsigned RegUnit,
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.
177void IntervalPressure::reset() {
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.
185void RegionPressure::reset() {
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.
194void IntervalPressure::openTop(SlotIndex NextTop) {
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.
202void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
203  if (TopPos != PrevTop)
204    return;
205  TopPos = MachineBasicBlock::const_iterator();
206  LiveInRegs.clear();
207}
208
209/// If the current bottom is not greater than the previous index, open it.
210void IntervalPressure::openBottom(SlotIndex PrevBottom) {
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.
218void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
219  if (BottomPos != PrevBottom)
220    return;
221  BottomPos = MachineBasicBlock::const_iterator();
222  LiveInRegs.clear();
223}
224
225void LiveRegSet::init(const MachineRegisterInfo &MRI) {
226  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
227  unsigned NumRegUnits = TRI.getNumRegs();
228  unsigned NumVirtRegs = MRI.getNumVirtRegs();
229  Regs.setUniverse(NumRegUnits + NumVirtRegs);
230  this->NumRegUnits = NumRegUnits;
231}
232
233void LiveRegSet::clear() {
234  Regs.clear();
235}
236
237static const LiveRange *getLiveRange(const LiveIntervals &LIS, unsigned Reg) {
238  if (Register::isVirtualRegister(Reg))
239    return &LIS.getInterval(Reg);
240  return LIS.getCachedRegUnit(Reg);
241}
242
243void RegPressureTracker::reset() {
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.
263void RegPressureTracker::init(const MachineFunction *mf,
264                              const RegisterClassInfo *rci,
265                              const LiveIntervals *lis,
266                              const MachineBasicBlock *mbb,
267                              MachineBasicBlock::const_iterator pos,
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.
295bool RegPressureTracker::isTopClosed() const {
296  if (RequireIntervals)
297    return static_cast<IntervalPressure&>(P).TopIdx.isValid();
298  return (static_cast<RegionPressure&>(P).TopPos ==
299          MachineBasicBlock::const_iterator());
300}
301
302/// Does this pressure result have a valid bottom position and live outs.
303bool RegPressureTracker::isBottomClosed() const {
304  if (RequireIntervals)
305    return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
306  return (static_cast<RegionPressure&>(P).BottomPos ==
307          MachineBasicBlock::const_iterator());
308}
309
310SlotIndex RegPressureTracker::getCurrSlot() const {
311  MachineBasicBlock::const_iterator IdxPos =
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.
319void RegPressureTracker::closeTop() {
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.
331void RegPressureTracker::closeBottom() {
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.
343void RegPressureTracker::closeRegion() {
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.
359void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
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,
367                          LaneBitmask::getNone(), Pair.LaneMask);
368  }
369}
370
371static LaneBitmask getRegLanes(ArrayRef<RegisterMaskPair> RegUnits,
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
381static void addRegLanes(SmallVectorImpl<RegisterMaskPair> &RegUnits,
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
395static void setRegZero(SmallVectorImpl<RegisterMaskPair> &RegUnits,
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
407static void removeRegLanes(SmallVectorImpl<RegisterMaskPair> &RegUnits,
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
421static LaneBitmask getLanesWithProperty(const LiveIntervals &LIS,
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)
435                              : LaneBitmask::getAll();
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
449static LaneBitmask getLiveLanesAt(const LiveIntervals &LIS,
450                                  const MachineRegisterInfo &MRI,
451                                  bool TrackLaneMasks, unsigned RegUnit,
452                                  SlotIndex Pos) {
453  return getLanesWithProperty(LIS, MRI, TrackLaneMasks, RegUnit, Pos,
454                              LaneBitmask::getAll(),
455                              [](const LiveRange &LR, SlotIndex Pos) {
456                                return LR.liveAt(Pos);
457                              });
458}
459
460
461namespace {
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
467class 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)) {
523      addRegLanes(RegUnits, RegisterMaskPair(Reg, LaneBitmask::getAll()));
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
568void RegisterOperands::collect(const MachineInstr &MI,
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
579void RegisterOperands::detectDeadDefs(const MachineInstr &MI,
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
599void RegisterOperands::adjustLaneLiveness(const LiveIntervals &LIS,
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.
646void 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
657void PressureDiffs::addInstruction(unsigned Idx,
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.
670void 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
696      PressureDiff::iterator J;
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.
705void RegPressureTracker::addLiveRegs(ArrayRef<RegisterMaskPair> Regs) {
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
713void RegPressureTracker::discoverLiveInOrOut(RegisterMaskPair Pair,
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
735void RegPressureTracker::discoverLiveIn(RegisterMaskPair Pair) {
736  discoverLiveInOrOut(Pair, P.LiveInRegs);
737}
738
739void RegPressureTracker::discoverLiveOut(RegisterMaskPair Pair) {
740  discoverLiveInOrOut(Pair, P.LiveOutRegs);
741}
742
743void RegPressureTracker::bumpDeadDefs(ArrayRef<RegisterMaskPair> DeadDefs) {
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.
763void RegPressureTracker::recede(const RegisterOperands &RegOpers,
764                                SmallVectorImpl<RegisterMaskPair> *LiveUses) {
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
851void RegPressureTracker::recedeSkipDebugValues() {
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
872void RegPressureTracker::recede(SmallVectorImpl<RegisterMaskPair> *LiveUses) {
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.
895void RegPressureTracker::advance(const RegisterOperands &RegOpers) {
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
946void RegPressureTracker::advance() {
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.
958static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
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.
997static 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.
1041void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
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.
1092void RegPressureTracker::
1093getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
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.
1160void RegPressureTracker::
1161getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
1162                       RegPressureDelta &Delta,
1163                       ArrayRef<PressureChange> CriticalPSets,
1164                       ArrayRef<unsigned> MaxPressureLimit) const {
1165  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1166  for (PressureDiff::const_iterator
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.
1222static LaneBitmask findUseBetween(unsigned Reg, LaneBitmask LastUseMask,
1223                                  SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1224                                  const MachineRegisterInfo &MRI,
1225                                  const LiveIntervals *LIS) {
1226  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
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
1243LaneBitmask RegPressureTracker::getLiveLanesAt(unsigned RegUnit,
1244                                               SlotIndex Pos) const {
1245  assert(RequireIntervals);
1246  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1247                              LaneBitmask::getAll(),
1248      [](const LiveRange &LR, SlotIndex Pos) {
1249        return LR.liveAt(Pos);
1250      });
1251}
1252
1253LaneBitmask RegPressureTracker::getLastUsedLanes(unsigned RegUnit,
1254                                                 SlotIndex Pos) const {
1255  assert(RequireIntervals);
1256  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit,
1257                              Pos.getBaseIndex(), LaneBitmask::getNone(),
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
1264LaneBitmask RegPressureTracker::getLiveThroughAt(unsigned RegUnit,
1265                                                 SlotIndex Pos) const {
1266  assert(RequireIntervals);
1267  return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1268                              LaneBitmask::getNone(),
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.
1282void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
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.
1341void RegPressureTracker::
1342getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
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.
1364void RegPressureTracker::
1365getUpwardPressure(const MachineInstr *MI,
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.
1380void RegPressureTracker::
1381getDownwardPressure(const MachineInstr *MI,
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}
1394