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