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