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