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