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                                PSetIterator PSetI) {
28  unsigned Weight = PSetI.getWeight();
29  for (; PSetI.isValid(); ++PSetI)
30    CurrSetPressure[*PSetI] += Weight;
31}
32
33/// Decrease pressure for each pressure set provided by TargetRegisterInfo.
34static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
35                                PSetIterator PSetI) {
36  unsigned Weight = PSetI.getWeight();
37  for (; PSetI.isValid(); ++PSetI) {
38    assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow");
39    CurrSetPressure[*PSetI] -= Weight;
40  }
41}
42
43LLVM_DUMP_METHOD
44void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
45                              const TargetRegisterInfo *TRI) {
46  bool Empty = true;
47  for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
48    if (SetPressure[i] != 0) {
49      dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
50      Empty = false;
51    }
52  }
53  if (Empty)
54    dbgs() << "\n";
55}
56
57LLVM_DUMP_METHOD
58void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
59  dbgs() << "Max Pressure: ";
60  dumpRegSetPressure(MaxSetPressure, TRI);
61  dbgs() << "Live In: ";
62  for (unsigned Reg : LiveInRegs)
63    dbgs() << PrintVRegOrUnit(Reg, TRI) << " ";
64  dbgs() << '\n';
65  dbgs() << "Live Out: ";
66  for (unsigned Reg : LiveOutRegs)
67    dbgs() << PrintVRegOrUnit(Reg, TRI) << " ";
68  dbgs() << '\n';
69}
70
71LLVM_DUMP_METHOD
72void RegPressureTracker::dump() const {
73  if (!isTopClosed() || !isBottomClosed()) {
74    dbgs() << "Curr Pressure: ";
75    dumpRegSetPressure(CurrSetPressure, TRI);
76  }
77  P.dump(TRI);
78}
79
80void PressureDiff::dump(const TargetRegisterInfo &TRI) const {
81  const char *sep = "";
82  for (const PressureChange &Change : *this) {
83    if (!Change.isValid())
84      break;
85    dbgs() << sep << TRI.getRegPressureSetName(Change.getPSet())
86           << " " << Change.getUnitInc();
87    sep = "    ";
88  }
89  dbgs() << '\n';
90}
91
92/// Increase the current pressure as impacted by these registers and bump
93/// the high water mark if needed.
94void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> RegUnits) {
95  for (unsigned RegUnit : RegUnits) {
96    PSetIterator PSetI = MRI->getPressureSets(RegUnit);
97    unsigned Weight = PSetI.getWeight();
98    for (; PSetI.isValid(); ++PSetI) {
99      CurrSetPressure[*PSetI] += Weight;
100      if (CurrSetPressure[*PSetI] > P.MaxSetPressure[*PSetI]) {
101        P.MaxSetPressure[*PSetI] = CurrSetPressure[*PSetI];
102      }
103    }
104  }
105}
106
107/// Simply decrease the current pressure as impacted by these registers.
108void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> RegUnits) {
109  for (unsigned RegUnit : RegUnits)
110    decreaseSetPressure(CurrSetPressure, MRI->getPressureSets(RegUnit));
111}
112
113/// Clear the result so it can be used for another round of pressure tracking.
114void IntervalPressure::reset() {
115  TopIdx = BottomIdx = SlotIndex();
116  MaxSetPressure.clear();
117  LiveInRegs.clear();
118  LiveOutRegs.clear();
119}
120
121/// Clear the result so it can be used for another round of pressure tracking.
122void RegionPressure::reset() {
123  TopPos = BottomPos = MachineBasicBlock::const_iterator();
124  MaxSetPressure.clear();
125  LiveInRegs.clear();
126  LiveOutRegs.clear();
127}
128
129/// If the current top is not less than or equal to the next index, open it.
130/// We happen to need the SlotIndex for the next top for pressure update.
131void IntervalPressure::openTop(SlotIndex NextTop) {
132  if (TopIdx <= NextTop)
133    return;
134  TopIdx = SlotIndex();
135  LiveInRegs.clear();
136}
137
138/// If the current top is the previous instruction (before receding), open it.
139void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
140  if (TopPos != PrevTop)
141    return;
142  TopPos = MachineBasicBlock::const_iterator();
143  LiveInRegs.clear();
144}
145
146/// If the current bottom is not greater than the previous index, open it.
147void IntervalPressure::openBottom(SlotIndex PrevBottom) {
148  if (BottomIdx > PrevBottom)
149    return;
150  BottomIdx = SlotIndex();
151  LiveInRegs.clear();
152}
153
154/// If the current bottom is the previous instr (before advancing), open it.
155void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
156  if (BottomPos != PrevBottom)
157    return;
158  BottomPos = MachineBasicBlock::const_iterator();
159  LiveInRegs.clear();
160}
161
162void LiveRegSet::init(const MachineRegisterInfo &MRI) {
163  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
164  unsigned NumRegUnits = TRI.getNumRegs();
165  unsigned NumVirtRegs = MRI.getNumVirtRegs();
166  Regs.setUniverse(NumRegUnits + NumVirtRegs);
167  this->NumRegUnits = NumRegUnits;
168}
169
170void LiveRegSet::clear() {
171  Regs.clear();
172}
173
174static const LiveRange *getLiveRange(const LiveIntervals &LIS, unsigned Reg) {
175  if (TargetRegisterInfo::isVirtualRegister(Reg))
176    return &LIS.getInterval(Reg);
177  return LIS.getCachedRegUnit(Reg);
178}
179
180void RegPressureTracker::reset() {
181  MBB = nullptr;
182  LIS = nullptr;
183
184  CurrSetPressure.clear();
185  LiveThruPressure.clear();
186  P.MaxSetPressure.clear();
187
188  if (RequireIntervals)
189    static_cast<IntervalPressure&>(P).reset();
190  else
191    static_cast<RegionPressure&>(P).reset();
192
193  LiveRegs.clear();
194  UntiedDefs.clear();
195}
196
197/// Setup the RegPressureTracker.
198///
199/// TODO: Add support for pressure without LiveIntervals.
200void RegPressureTracker::init(const MachineFunction *mf,
201                              const RegisterClassInfo *rci,
202                              const LiveIntervals *lis,
203                              const MachineBasicBlock *mbb,
204                              MachineBasicBlock::const_iterator pos,
205                              bool ShouldTrackUntiedDefs)
206{
207  reset();
208
209  MF = mf;
210  TRI = MF->getSubtarget().getRegisterInfo();
211  RCI = rci;
212  MRI = &MF->getRegInfo();
213  MBB = mbb;
214  TrackUntiedDefs = ShouldTrackUntiedDefs;
215
216  if (RequireIntervals) {
217    assert(lis && "IntervalPressure requires LiveIntervals");
218    LIS = lis;
219  }
220
221  CurrPos = pos;
222  CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
223
224  P.MaxSetPressure = CurrSetPressure;
225
226  LiveRegs.init(*MRI);
227  if (TrackUntiedDefs)
228    UntiedDefs.setUniverse(MRI->getNumVirtRegs());
229}
230
231/// Does this pressure result have a valid top position and live ins.
232bool RegPressureTracker::isTopClosed() const {
233  if (RequireIntervals)
234    return static_cast<IntervalPressure&>(P).TopIdx.isValid();
235  return (static_cast<RegionPressure&>(P).TopPos ==
236          MachineBasicBlock::const_iterator());
237}
238
239/// Does this pressure result have a valid bottom position and live outs.
240bool RegPressureTracker::isBottomClosed() const {
241  if (RequireIntervals)
242    return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
243  return (static_cast<RegionPressure&>(P).BottomPos ==
244          MachineBasicBlock::const_iterator());
245}
246
247
248SlotIndex RegPressureTracker::getCurrSlot() const {
249  MachineBasicBlock::const_iterator IdxPos = CurrPos;
250  while (IdxPos != MBB->end() && IdxPos->isDebugValue())
251    ++IdxPos;
252  if (IdxPos == MBB->end())
253    return LIS->getMBBEndIdx(MBB);
254  return LIS->getInstructionIndex(IdxPos).getRegSlot();
255}
256
257/// Set the boundary for the top of the region and summarize live ins.
258void RegPressureTracker::closeTop() {
259  if (RequireIntervals)
260    static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
261  else
262    static_cast<RegionPressure&>(P).TopPos = CurrPos;
263
264  assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
265  P.LiveInRegs.reserve(LiveRegs.size());
266  LiveRegs.appendTo(P.LiveInRegs);
267}
268
269/// Set the boundary for the bottom of the region and summarize live outs.
270void RegPressureTracker::closeBottom() {
271  if (RequireIntervals)
272    static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
273  else
274    static_cast<RegionPressure&>(P).BottomPos = CurrPos;
275
276  assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
277  P.LiveOutRegs.reserve(LiveRegs.size());
278  LiveRegs.appendTo(P.LiveOutRegs);
279}
280
281/// Finalize the region boundaries and record live ins and live outs.
282void RegPressureTracker::closeRegion() {
283  if (!isTopClosed() && !isBottomClosed()) {
284    assert(LiveRegs.size() == 0 && "no region boundary");
285    return;
286  }
287  if (!isBottomClosed())
288    closeBottom();
289  else if (!isTopClosed())
290    closeTop();
291  // If both top and bottom are closed, do nothing.
292}
293
294/// The register tracker is unaware of global liveness so ignores normal
295/// live-thru ranges. However, two-address or coalesced chains can also lead
296/// to live ranges with no holes. Count these to inform heuristics that we
297/// can never drop below this pressure.
298void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
299  LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
300  assert(isBottomClosed() && "need bottom-up tracking to intialize.");
301  for (unsigned Reg : P.LiveOutRegs) {
302    if (TargetRegisterInfo::isVirtualRegister(Reg)
303        && !RPTracker.hasUntiedDef(Reg)) {
304      increaseSetPressure(LiveThruPressure, MRI->getPressureSets(Reg));
305    }
306  }
307}
308
309/// \brief Convenient wrapper for checking membership in RegisterOperands.
310/// (std::count() doesn't have an early exit).
311static bool containsReg(ArrayRef<unsigned> RegUnits, unsigned RegUnit) {
312  return std::find(RegUnits.begin(), RegUnits.end(), RegUnit) != RegUnits.end();
313}
314
315namespace {
316
317/// List of register defined and used by a machine instruction.
318class RegisterOperands {
319public:
320  SmallVector<unsigned, 8> Uses;
321  SmallVector<unsigned, 8> Defs;
322  SmallVector<unsigned, 8> DeadDefs;
323
324  void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI,
325               const MachineRegisterInfo &MRI, bool IgnoreDead = false);
326
327  /// Use liveness information to find dead defs not marked with a dead flag
328  /// and move them to the DeadDefs vector.
329  void detectDeadDefs(const MachineInstr &MI, const LiveIntervals &LIS);
330};
331
332/// Collect this instruction's unique uses and defs into SmallVectors for
333/// processing defs and uses in order.
334///
335/// FIXME: always ignore tied opers
336class RegisterOperandsCollector {
337  RegisterOperands &RegOpers;
338  const TargetRegisterInfo &TRI;
339  const MachineRegisterInfo &MRI;
340  bool IgnoreDead;
341
342  RegisterOperandsCollector(RegisterOperands &RegOpers,
343                            const TargetRegisterInfo &TRI,
344                            const MachineRegisterInfo &MRI,
345                            bool IgnoreDead)
346    : RegOpers(RegOpers), TRI(TRI), MRI(MRI), IgnoreDead(IgnoreDead) {}
347
348  void collectInstr(const MachineInstr &MI) const {
349    for (ConstMIBundleOperands OperI(&MI); OperI.isValid(); ++OperI)
350      collectOperand(*OperI);
351
352    // Remove redundant physreg dead defs.
353    SmallVectorImpl<unsigned>::iterator I =
354      std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(),
355                     std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs));
356    RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end());
357  }
358
359  /// Push this operand's register onto the correct vectors.
360  void collectOperand(const MachineOperand &MO) const {
361    if (!MO.isReg() || !MO.getReg())
362      return;
363    unsigned Reg = MO.getReg();
364    if (MO.readsReg())
365      pushRegUnits(Reg, RegOpers.Uses);
366    if (MO.isDef()) {
367      if (MO.isDead()) {
368        if (!IgnoreDead)
369          pushRegUnits(Reg, RegOpers.DeadDefs);
370      } else
371        pushRegUnits(Reg, RegOpers.Defs);
372    }
373  }
374
375  void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &RegUnits) const {
376    if (TargetRegisterInfo::isVirtualRegister(Reg)) {
377      if (containsReg(RegUnits, Reg))
378        return;
379      RegUnits.push_back(Reg);
380    } else if (MRI.isAllocatable(Reg)) {
381      for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) {
382        if (containsReg(RegUnits, *Units))
383          continue;
384        RegUnits.push_back(*Units);
385      }
386    }
387  }
388
389  friend class RegisterOperands;
390};
391
392void RegisterOperands::collect(const MachineInstr &MI,
393                               const TargetRegisterInfo &TRI,
394                               const MachineRegisterInfo &MRI,
395                               bool IgnoreDead) {
396  RegisterOperandsCollector Collector(*this, TRI, MRI, IgnoreDead);
397  Collector.collectInstr(MI);
398}
399
400void RegisterOperands::detectDeadDefs(const MachineInstr &MI,
401                                      const LiveIntervals &LIS) {
402  SlotIndex SlotIdx = LIS.getInstructionIndex(&MI);
403  for (SmallVectorImpl<unsigned>::iterator RI = Defs.begin();
404       RI != Defs.end(); /*empty*/) {
405    unsigned Reg = *RI;
406    const LiveRange *LR = getLiveRange(LIS, Reg);
407    if (LR != nullptr) {
408      LiveQueryResult LRQ = LR->Query(SlotIdx);
409      if (LRQ.isDeadDef()) {
410        // LiveIntervals knows this is a dead even though it's MachineOperand is
411        // not flagged as such.
412        DeadDefs.push_back(Reg);
413        RI = Defs.erase(RI);
414        continue;
415      }
416    }
417    ++RI;
418  }
419}
420
421} // namespace
422
423/// Initialize an array of N PressureDiffs.
424void PressureDiffs::init(unsigned N) {
425  Size = N;
426  if (N <= Max) {
427    memset(PDiffArray, 0, N * sizeof(PressureDiff));
428    return;
429  }
430  Max = Size;
431  free(PDiffArray);
432  PDiffArray = reinterpret_cast<PressureDiff*>(calloc(N, sizeof(PressureDiff)));
433}
434
435/// Add a change in pressure to the pressure diff of a given instruction.
436void PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec,
437                                     const MachineRegisterInfo *MRI) {
438  PSetIterator PSetI = MRI->getPressureSets(RegUnit);
439  int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight();
440  for (; PSetI.isValid(); ++PSetI) {
441    // Find an existing entry in the pressure diff for this PSet.
442    PressureDiff::iterator I = nonconst_begin(), E = nonconst_end();
443    for (; I != E && I->isValid(); ++I) {
444      if (I->getPSet() >= *PSetI)
445        break;
446    }
447    // If all pressure sets are more constrained, skip the remaining PSets.
448    if (I == E)
449      break;
450    // Insert this PressureChange.
451    if (!I->isValid() || I->getPSet() != *PSetI) {
452      PressureChange PTmp = PressureChange(*PSetI);
453      for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J)
454        std::swap(*J, PTmp);
455    }
456    // Update the units for this pressure set.
457    unsigned NewUnitInc = I->getUnitInc() + Weight;
458    if (NewUnitInc != 0) {
459      I->setUnitInc(NewUnitInc);
460    } else {
461      // Remove entry
462      PressureDiff::iterator J;
463      for (J = std::next(I); J != E && J->isValid(); ++J, ++I)
464        *I = *J;
465      if (J != E)
466        *I = *J;
467    }
468  }
469}
470
471/// Record the pressure difference induced by the given operand list.
472static void collectPDiff(PressureDiff &PDiff, RegisterOperands &RegOpers,
473                         const MachineRegisterInfo *MRI) {
474  assert(!PDiff.begin()->isValid() && "stale PDiff");
475
476  for (unsigned Reg : RegOpers.Defs)
477    PDiff.addPressureChange(Reg, true, MRI);
478
479  for (unsigned Reg : RegOpers.Uses)
480    PDiff.addPressureChange(Reg, false, MRI);
481}
482
483/// Force liveness of registers.
484void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
485  for (unsigned Reg : Regs) {
486    if (LiveRegs.insert(Reg))
487      increaseRegPressure(Reg);
488  }
489}
490
491/// Add Reg to the live in set and increase max pressure.
492void RegPressureTracker::discoverLiveIn(unsigned Reg) {
493  assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
494  if (containsReg(P.LiveInRegs, Reg))
495    return;
496
497  // At live in discovery, unconditionally increase the high water mark.
498  P.LiveInRegs.push_back(Reg);
499  increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg));
500}
501
502/// Add Reg to the live out set and increase max pressure.
503void RegPressureTracker::discoverLiveOut(unsigned Reg) {
504  assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
505  if (containsReg(P.LiveOutRegs, Reg))
506    return;
507
508  // At live out discovery, unconditionally increase the high water mark.
509  P.LiveOutRegs.push_back(Reg);
510  increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg));
511}
512
513/// Recede across the previous instruction. If LiveUses is provided, record any
514/// RegUnits that are made live by the current instruction's uses. This includes
515/// registers that are both defined and used by the instruction.  If a pressure
516/// difference pointer is provided record the changes is pressure caused by this
517/// instruction independent of liveness.
518void RegPressureTracker::recede(SmallVectorImpl<unsigned> *LiveUses,
519                                PressureDiff *PDiff) {
520  assert(CurrPos != MBB->begin());
521  if (!isBottomClosed())
522    closeBottom();
523
524  // Open the top of the region using block iterators.
525  if (!RequireIntervals && isTopClosed())
526    static_cast<RegionPressure&>(P).openTop(CurrPos);
527
528  // Find the previous instruction.
529  do
530    --CurrPos;
531  while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
532  assert(!CurrPos->isDebugValue());
533
534  SlotIndex SlotIdx;
535  if (RequireIntervals)
536    SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
537
538  // Open the top of the region using slot indexes.
539  if (RequireIntervals && isTopClosed())
540    static_cast<IntervalPressure&>(P).openTop(SlotIdx);
541
542  const MachineInstr &MI = *CurrPos;
543  RegisterOperands RegOpers;
544  RegOpers.collect(MI, *TRI, *MRI);
545  if (RequireIntervals)
546    RegOpers.detectDeadDefs(MI, *LIS);
547
548  if (PDiff)
549    collectPDiff(*PDiff, RegOpers, MRI);
550
551  // Boost pressure for all dead defs together.
552  increaseRegPressure(RegOpers.DeadDefs);
553  decreaseRegPressure(RegOpers.DeadDefs);
554
555  // Kill liveness at live defs.
556  // TODO: consider earlyclobbers?
557  for (unsigned Reg : RegOpers.Defs) {
558    if (LiveRegs.erase(Reg))
559      decreaseRegPressure(Reg);
560    else
561      discoverLiveOut(Reg);
562  }
563
564  // Generate liveness for uses.
565  for (unsigned Reg : RegOpers.Uses) {
566    if (!LiveRegs.contains(Reg)) {
567      // Adjust liveouts if LiveIntervals are available.
568      if (RequireIntervals) {
569        const LiveRange *LR = getLiveRange(*LIS, Reg);
570        if (LR) {
571          LiveQueryResult LRQ = LR->Query(SlotIdx);
572          if (!LRQ.isKill() && !LRQ.valueDefined())
573            discoverLiveOut(Reg);
574        }
575      }
576      increaseRegPressure(Reg);
577      LiveRegs.insert(Reg);
578      if (LiveUses && !containsReg(*LiveUses, Reg))
579        LiveUses->push_back(Reg);
580    }
581  }
582  if (TrackUntiedDefs) {
583    for (unsigned Reg : RegOpers.Defs) {
584      if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg))
585        UntiedDefs.insert(Reg);
586    }
587  }
588}
589
590/// Advance across the current instruction.
591void RegPressureTracker::advance() {
592  assert(!TrackUntiedDefs && "unsupported mode");
593
594  assert(CurrPos != MBB->end());
595  if (!isTopClosed())
596    closeTop();
597
598  SlotIndex SlotIdx;
599  if (RequireIntervals)
600    SlotIdx = getCurrSlot();
601
602  // Open the bottom of the region using slot indexes.
603  if (isBottomClosed()) {
604    if (RequireIntervals)
605      static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
606    else
607      static_cast<RegionPressure&>(P).openBottom(CurrPos);
608  }
609
610  RegisterOperands RegOpers;
611  RegOpers.collect(*CurrPos, *TRI, *MRI);
612
613  for (unsigned Reg : RegOpers.Uses) {
614    // Discover live-ins.
615    bool isLive = LiveRegs.contains(Reg);
616    if (!isLive)
617      discoverLiveIn(Reg);
618    // Kill liveness at last uses.
619    bool lastUse = false;
620    if (RequireIntervals) {
621      const LiveRange *LR = getLiveRange(*LIS, Reg);
622      lastUse = LR && LR->Query(SlotIdx).isKill();
623    } else {
624      // Allocatable physregs are always single-use before register rewriting.
625      lastUse = !TargetRegisterInfo::isVirtualRegister(Reg);
626    }
627    if (lastUse && isLive) {
628      LiveRegs.erase(Reg);
629      decreaseRegPressure(Reg);
630    } else if (!lastUse && !isLive)
631      increaseRegPressure(Reg);
632  }
633
634  // Generate liveness for defs.
635  for (unsigned Reg : RegOpers.Defs) {
636    if (LiveRegs.insert(Reg))
637      increaseRegPressure(Reg);
638  }
639
640  // Boost pressure for all dead defs together.
641  increaseRegPressure(RegOpers.DeadDefs);
642  decreaseRegPressure(RegOpers.DeadDefs);
643
644  // Find the next instruction.
645  do
646    ++CurrPos;
647  while (CurrPos != MBB->end() && CurrPos->isDebugValue());
648}
649
650/// Find the max change in excess pressure across all sets.
651static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
652                                       ArrayRef<unsigned> NewPressureVec,
653                                       RegPressureDelta &Delta,
654                                       const RegisterClassInfo *RCI,
655                                       ArrayRef<unsigned> LiveThruPressureVec) {
656  Delta.Excess = PressureChange();
657  for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
658    unsigned POld = OldPressureVec[i];
659    unsigned PNew = NewPressureVec[i];
660    int PDiff = (int)PNew - (int)POld;
661    if (!PDiff) // No change in this set in the common case.
662      continue;
663    // Only consider change beyond the limit.
664    unsigned Limit = RCI->getRegPressureSetLimit(i);
665    if (!LiveThruPressureVec.empty())
666      Limit += LiveThruPressureVec[i];
667
668    if (Limit > POld) {
669      if (Limit > PNew)
670        PDiff = 0;            // Under the limit
671      else
672        PDiff = PNew - Limit; // Just exceeded limit.
673    } else if (Limit > PNew)
674      PDiff = Limit - POld;   // Just obeyed limit.
675
676    if (PDiff) {
677      Delta.Excess = PressureChange(i);
678      Delta.Excess.setUnitInc(PDiff);
679      break;
680    }
681  }
682}
683
684/// Find the max change in max pressure that either surpasses a critical PSet
685/// limit or exceeds the current MaxPressureLimit.
686///
687/// FIXME: comparing each element of the old and new MaxPressure vectors here is
688/// silly. It's done now to demonstrate the concept but will go away with a
689/// RegPressureTracker API change to work with pressure differences.
690static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
691                                    ArrayRef<unsigned> NewMaxPressureVec,
692                                    ArrayRef<PressureChange> CriticalPSets,
693                                    ArrayRef<unsigned> MaxPressureLimit,
694                                    RegPressureDelta &Delta) {
695  Delta.CriticalMax = PressureChange();
696  Delta.CurrentMax = PressureChange();
697
698  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
699  for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
700    unsigned POld = OldMaxPressureVec[i];
701    unsigned PNew = NewMaxPressureVec[i];
702    if (PNew == POld) // No change in this set in the common case.
703      continue;
704
705    if (!Delta.CriticalMax.isValid()) {
706      while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
707        ++CritIdx;
708
709      if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
710        int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
711        if (PDiff > 0) {
712          Delta.CriticalMax = PressureChange(i);
713          Delta.CriticalMax.setUnitInc(PDiff);
714        }
715      }
716    }
717    // Find the first increase above MaxPressureLimit.
718    // (Ignores negative MDiff).
719    if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
720      Delta.CurrentMax = PressureChange(i);
721      Delta.CurrentMax.setUnitInc(PNew - POld);
722      if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
723        break;
724    }
725  }
726}
727
728/// Record the upward impact of a single instruction on current register
729/// pressure. Unlike the advance/recede pressure tracking interface, this does
730/// not discover live in/outs.
731///
732/// This is intended for speculative queries. It leaves pressure inconsistent
733/// with the current position, so must be restored by the caller.
734void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
735  assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
736
737  // Account for register pressure similar to RegPressureTracker::recede().
738  RegisterOperands RegOpers;
739  RegOpers.collect(*MI, *TRI, *MRI, /*IgnoreDead=*/true);
740  assert(RegOpers.DeadDefs.size() == 0);
741  if (RequireIntervals)
742    RegOpers.detectDeadDefs(*MI, *LIS);
743
744  // Kill liveness at live defs.
745  for (unsigned Reg : RegOpers.Defs) {
746    if (!containsReg(RegOpers.Uses, Reg))
747      decreaseRegPressure(Reg);
748  }
749  // Generate liveness for uses.
750  for (unsigned Reg : RegOpers.Uses) {
751    if (!LiveRegs.contains(Reg))
752      increaseRegPressure(Reg);
753  }
754}
755
756/// Consider the pressure increase caused by traversing this instruction
757/// bottom-up. Find the pressure set with the most change beyond its pressure
758/// limit based on the tracker's current pressure, and return the change in
759/// number of register units of that pressure set introduced by this
760/// instruction.
761///
762/// This assumes that the current LiveOut set is sufficient.
763///
764/// This is expensive for an on-the-fly query because it calls
765/// bumpUpwardPressure to recompute the pressure sets based on current
766/// liveness. This mainly exists to verify correctness, e.g. with
767/// -verify-misched. getUpwardPressureDelta is the fast version of this query
768/// that uses the per-SUnit cache of the PressureDiff.
769void RegPressureTracker::
770getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
771                          RegPressureDelta &Delta,
772                          ArrayRef<PressureChange> CriticalPSets,
773                          ArrayRef<unsigned> MaxPressureLimit) {
774  // Snapshot Pressure.
775  // FIXME: The snapshot heap space should persist. But I'm planning to
776  // summarize the pressure effect so we don't need to snapshot at all.
777  std::vector<unsigned> SavedPressure = CurrSetPressure;
778  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
779
780  bumpUpwardPressure(MI);
781
782  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
783                             LiveThruPressure);
784  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
785                          MaxPressureLimit, Delta);
786  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
787         Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
788
789  // Restore the tracker's state.
790  P.MaxSetPressure.swap(SavedMaxPressure);
791  CurrSetPressure.swap(SavedPressure);
792
793#ifndef NDEBUG
794  if (!PDiff)
795    return;
796
797  // Check if the alternate algorithm yields the same result.
798  RegPressureDelta Delta2;
799  getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
800  if (Delta != Delta2) {
801    dbgs() << "PDiff: ";
802    PDiff->dump(*TRI);
803    dbgs() << "DELTA: " << *MI;
804    if (Delta.Excess.isValid())
805      dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
806             << " " << Delta.Excess.getUnitInc() << "\n";
807    if (Delta.CriticalMax.isValid())
808      dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
809             << " " << Delta.CriticalMax.getUnitInc() << "\n";
810    if (Delta.CurrentMax.isValid())
811      dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
812             << " " << Delta.CurrentMax.getUnitInc() << "\n";
813    if (Delta2.Excess.isValid())
814      dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
815             << " " << Delta2.Excess.getUnitInc() << "\n";
816    if (Delta2.CriticalMax.isValid())
817      dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
818             << " " << Delta2.CriticalMax.getUnitInc() << "\n";
819    if (Delta2.CurrentMax.isValid())
820      dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
821             << " " << Delta2.CurrentMax.getUnitInc() << "\n";
822    llvm_unreachable("RegP Delta Mismatch");
823  }
824#endif
825}
826
827/// This is the fast version of querying register pressure that does not
828/// directly depend on current liveness.
829///
830/// @param Delta captures information needed for heuristics.
831///
832/// @param CriticalPSets Are the pressure sets that are known to exceed some
833/// limit within the region, not necessarily at the current position.
834///
835/// @param MaxPressureLimit Is the max pressure within the region, not
836/// necessarily at the current position.
837void RegPressureTracker::
838getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
839                       RegPressureDelta &Delta,
840                       ArrayRef<PressureChange> CriticalPSets,
841                       ArrayRef<unsigned> MaxPressureLimit) const {
842  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
843  for (PressureDiff::const_iterator
844         PDiffI = PDiff.begin(), PDiffE = PDiff.end();
845       PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
846
847    unsigned PSetID = PDiffI->getPSet();
848    unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
849    if (!LiveThruPressure.empty())
850      Limit += LiveThruPressure[PSetID];
851
852    unsigned POld = CurrSetPressure[PSetID];
853    unsigned MOld = P.MaxSetPressure[PSetID];
854    unsigned MNew = MOld;
855    // Ignore DeadDefs here because they aren't captured by PressureChange.
856    unsigned PNew = POld + PDiffI->getUnitInc();
857    assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
858           && "PSet overflow/underflow");
859    if (PNew > MOld)
860      MNew = PNew;
861    // Check if current pressure has exceeded the limit.
862    if (!Delta.Excess.isValid()) {
863      unsigned ExcessInc = 0;
864      if (PNew > Limit)
865        ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
866      else if (POld > Limit)
867        ExcessInc = Limit - POld;
868      if (ExcessInc) {
869        Delta.Excess = PressureChange(PSetID);
870        Delta.Excess.setUnitInc(ExcessInc);
871      }
872    }
873    // Check if max pressure has exceeded a critical pressure set max.
874    if (MNew == MOld)
875      continue;
876    if (!Delta.CriticalMax.isValid()) {
877      while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
878        ++CritIdx;
879
880      if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
881        int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
882        if (CritInc > 0 && CritInc <= INT16_MAX) {
883          Delta.CriticalMax = PressureChange(PSetID);
884          Delta.CriticalMax.setUnitInc(CritInc);
885        }
886      }
887    }
888    // Check if max pressure has exceeded the current max.
889    if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
890      Delta.CurrentMax = PressureChange(PSetID);
891      Delta.CurrentMax.setUnitInc(MNew - MOld);
892    }
893  }
894}
895
896/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
897static bool findUseBetween(unsigned Reg, SlotIndex PriorUseIdx,
898                           SlotIndex NextUseIdx, const MachineRegisterInfo &MRI,
899                           const LiveIntervals *LIS) {
900  for (const MachineInstr &MI : MRI.use_nodbg_instructions(Reg)) {
901    SlotIndex InstSlot = LIS->getInstructionIndex(&MI).getRegSlot();
902    if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
903      return true;
904  }
905  return false;
906}
907
908/// Record the downward impact of a single instruction on current register
909/// pressure. Unlike the advance/recede pressure tracking interface, this does
910/// not discover live in/outs.
911///
912/// This is intended for speculative queries. It leaves pressure inconsistent
913/// with the current position, so must be restored by the caller.
914void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
915  assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
916
917  // Account for register pressure similar to RegPressureTracker::recede().
918  RegisterOperands RegOpers;
919  RegOpers.collect(*MI, *TRI, *MRI);
920
921  // Kill liveness at last uses. Assume allocatable physregs are single-use
922  // rather than checking LiveIntervals.
923  SlotIndex SlotIdx;
924  if (RequireIntervals)
925    SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
926
927  for (unsigned Reg : RegOpers.Uses) {
928    if (RequireIntervals) {
929      // FIXME: allow the caller to pass in the list of vreg uses that remain
930      // to be bottom-scheduled to avoid searching uses at each query.
931      SlotIndex CurrIdx = getCurrSlot();
932      const LiveRange *LR = getLiveRange(*LIS, Reg);
933      if (LR) {
934        LiveQueryResult LRQ = LR->Query(SlotIdx);
935        if (LRQ.isKill() && !findUseBetween(Reg, CurrIdx, SlotIdx, *MRI, LIS))
936          decreaseRegPressure(Reg);
937      }
938    } else if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
939      // Allocatable physregs are always single-use before register rewriting.
940      decreaseRegPressure(Reg);
941    }
942  }
943
944  // Generate liveness for defs.
945  increaseRegPressure(RegOpers.Defs);
946
947  // Boost pressure for all dead defs together.
948  increaseRegPressure(RegOpers.DeadDefs);
949  decreaseRegPressure(RegOpers.DeadDefs);
950}
951
952/// Consider the pressure increase caused by traversing this instruction
953/// top-down. Find the register class with the most change in its pressure limit
954/// based on the tracker's current pressure, and return the number of excess
955/// register units of that pressure set introduced by this instruction.
956///
957/// This assumes that the current LiveIn set is sufficient.
958///
959/// This is expensive for an on-the-fly query because it calls
960/// bumpDownwardPressure to recompute the pressure sets based on current
961/// liveness. We don't yet have a fast version of downward pressure tracking
962/// analogous to getUpwardPressureDelta.
963void RegPressureTracker::
964getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
965                            ArrayRef<PressureChange> CriticalPSets,
966                            ArrayRef<unsigned> MaxPressureLimit) {
967  // Snapshot Pressure.
968  std::vector<unsigned> SavedPressure = CurrSetPressure;
969  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
970
971  bumpDownwardPressure(MI);
972
973  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
974                             LiveThruPressure);
975  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
976                          MaxPressureLimit, Delta);
977  assert(Delta.CriticalMax.getUnitInc() >= 0 &&
978         Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
979
980  // Restore the tracker's state.
981  P.MaxSetPressure.swap(SavedMaxPressure);
982  CurrSetPressure.swap(SavedPressure);
983}
984
985/// Get the pressure of each PSet after traversing this instruction bottom-up.
986void RegPressureTracker::
987getUpwardPressure(const MachineInstr *MI,
988                  std::vector<unsigned> &PressureResult,
989                  std::vector<unsigned> &MaxPressureResult) {
990  // Snapshot pressure.
991  PressureResult = CurrSetPressure;
992  MaxPressureResult = P.MaxSetPressure;
993
994  bumpUpwardPressure(MI);
995
996  // Current pressure becomes the result. Restore current pressure.
997  P.MaxSetPressure.swap(MaxPressureResult);
998  CurrSetPressure.swap(PressureResult);
999}
1000
1001/// Get the pressure of each PSet after traversing this instruction top-down.
1002void RegPressureTracker::
1003getDownwardPressure(const MachineInstr *MI,
1004                    std::vector<unsigned> &PressureResult,
1005                    std::vector<unsigned> &MaxPressureResult) {
1006  // Snapshot pressure.
1007  PressureResult = CurrSetPressure;
1008  MaxPressureResult = P.MaxSetPressure;
1009
1010  bumpDownwardPressure(MI);
1011
1012  // Current pressure becomes the result. Restore current pressure.
1013  P.MaxSetPressure.swap(MaxPressureResult);
1014  CurrSetPressure.swap(PressureResult);
1015}
1016