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