RegisterPressure.cpp revision afc2657cc33988a178d3b21645dba54484600c5f 
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 "RegisterClassInfo.h"
16#include "llvm/CodeGen/LiveInterval.h"
17#include "llvm/CodeGen/LiveIntervalAnalysis.h"
18#include "llvm/CodeGen/MachineRegisterInfo.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
66void RegisterPressure::dump(const TargetRegisterInfo *TRI) {
67  dbgs() << "Live In: ";
68  for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i)
69    dbgs() << PrintReg(LiveInRegs[i], TRI) << " ";
70  dbgs() << '\n';
71  dbgs() << "Live Out: ";
72  for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i)
73    dbgs() << PrintReg(LiveOutRegs[i], TRI) << " ";
74  dbgs() << '\n';
75  for (unsigned i = 0, e = MaxSetPressure.size(); i < e; ++i) {
76    if (MaxSetPressure[i] != 0)
77      dbgs() << TRI->getRegPressureSetName(i) << "=" << MaxSetPressure[i]
78             << '\n';
79  }
80}
81
82/// Increase the current pressure as impacted by these physical registers and
83/// bump the high water mark if needed.
84void RegPressureTracker::increasePhysRegPressure(ArrayRef<unsigned> Regs) {
85  for (unsigned I = 0, E = Regs.size(); I != E; ++I)
86    increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
87                        TRI->getMinimalPhysRegClass(Regs[I]), TRI);
88}
89
90/// Simply decrease the current pressure as impacted by these physcial
91/// registers.
92void RegPressureTracker::decreasePhysRegPressure(ArrayRef<unsigned> Regs) {
93  for (unsigned I = 0, E = Regs.size(); I != E; ++I)
94    decreaseSetPressure(CurrSetPressure, TRI->getMinimalPhysRegClass(Regs[I]),
95                        TRI);
96}
97
98/// Increase the current pressure as impacted by these virtual registers and
99/// bump the high water mark if needed.
100void RegPressureTracker::increaseVirtRegPressure(ArrayRef<unsigned> Regs) {
101  for (unsigned I = 0, E = Regs.size(); I != E; ++I)
102    increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
103                        MRI->getRegClass(Regs[I]), TRI);
104}
105
106/// Simply decrease the current pressure as impacted by these virtual registers.
107void RegPressureTracker::decreaseVirtRegPressure(ArrayRef<unsigned> Regs) {
108  for (unsigned I = 0, E = Regs.size(); I != E; ++I)
109    decreaseSetPressure(CurrSetPressure, MRI->getRegClass(Regs[I]), TRI);
110}
111
112/// Clear the result so it can be used for another round of pressure tracking.
113void IntervalPressure::reset() {
114  TopIdx = BottomIdx = SlotIndex();
115  MaxSetPressure.clear();
116  LiveInRegs.clear();
117  LiveOutRegs.clear();
118}
119
120/// Clear the result so it can be used for another round of pressure tracking.
121void RegionPressure::reset() {
122  TopPos = BottomPos = MachineBasicBlock::const_iterator();
123  MaxSetPressure.clear();
124  LiveInRegs.clear();
125  LiveOutRegs.clear();
126}
127
128/// If the current top is not less than or equal to the next index, open it.
129/// We happen to need the SlotIndex for the next top for pressure update.
130void IntervalPressure::openTop(SlotIndex NextTop) {
131  if (TopIdx <= NextTop)
132    return;
133  TopIdx = SlotIndex();
134  LiveInRegs.clear();
135}
136
137/// If the current top is the previous instruction (before receding), open it.
138void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
139  if (TopPos != PrevTop)
140    return;
141  TopPos = MachineBasicBlock::const_iterator();
142  LiveInRegs.clear();
143}
144
145/// If the current bottom is not greater than the previous index, open it.
146void IntervalPressure::openBottom(SlotIndex PrevBottom) {
147  if (BottomIdx > PrevBottom)
148    return;
149  BottomIdx = SlotIndex();
150  LiveInRegs.clear();
151}
152
153/// If the current bottom is the previous instr (before advancing), open it.
154void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
155  if (BottomPos != PrevBottom)
156    return;
157  BottomPos = MachineBasicBlock::const_iterator();
158  LiveInRegs.clear();
159}
160
161/// Setup the RegPressureTracker.
162///
163/// TODO: Add support for pressure without LiveIntervals.
164void RegPressureTracker::init(const MachineFunction *mf,
165                              const RegisterClassInfo *rci,
166                              const LiveIntervals *lis,
167                              const MachineBasicBlock *mbb,
168                              MachineBasicBlock::const_iterator pos)
169{
170  MF = mf;
171  TRI = MF->getTarget().getRegisterInfo();
172  RCI = rci;
173  MRI = &MF->getRegInfo();
174  MBB = mbb;
175
176  if (RequireIntervals) {
177    assert(lis && "IntervalPressure requires LiveIntervals");
178    LIS = lis;
179  }
180
181  CurrPos = pos;
182  while (CurrPos != MBB->end() && CurrPos->isDebugValue())
183    ++CurrPos;
184
185  CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
186
187  if (RequireIntervals)
188    static_cast<IntervalPressure&>(P).reset();
189  else
190    static_cast<RegionPressure&>(P).reset();
191  P.MaxSetPressure = CurrSetPressure;
192
193  LivePhysRegs.clear();
194  LivePhysRegs.setUniverse(TRI->getNumRegs());
195  LiveVirtRegs.clear();
196  LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
197}
198
199/// Does this pressure result have a valid top position and live ins.
200bool RegPressureTracker::isTopClosed() const {
201  if (RequireIntervals)
202    return static_cast<IntervalPressure&>(P).TopIdx.isValid();
203  return (static_cast<RegionPressure&>(P).TopPos ==
204          MachineBasicBlock::const_iterator());
205}
206
207/// Does this pressure result have a valid bottom position and live outs.
208bool RegPressureTracker::isBottomClosed() const {
209  if (RequireIntervals)
210    return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
211  return (static_cast<RegionPressure&>(P).BottomPos ==
212          MachineBasicBlock::const_iterator());
213}
214
215/// Set the boundary for the top of the region and summarize live ins.
216void RegPressureTracker::closeTop() {
217  if (RequireIntervals)
218    static_cast<IntervalPressure&>(P).TopIdx =
219      LIS->getInstructionIndex(CurrPos).getRegSlot();
220  else
221    static_cast<RegionPressure&>(P).TopPos = CurrPos;
222
223  assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
224  P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
225  P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
226  for (SparseSet<unsigned>::const_iterator I =
227         LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
228    P.LiveInRegs.push_back(*I);
229  std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
230  P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
231                     P.LiveInRegs.end());
232}
233
234/// Set the boundary for the bottom of the region and summarize live outs.
235void RegPressureTracker::closeBottom() {
236  if (RequireIntervals)
237    if (CurrPos == MBB->end())
238      static_cast<IntervalPressure&>(P).BottomIdx = LIS->getMBBEndIdx(MBB);
239    else
240      static_cast<IntervalPressure&>(P).BottomIdx =
241        LIS->getInstructionIndex(CurrPos).getRegSlot();
242  else
243    static_cast<RegionPressure&>(P).BottomPos = CurrPos;
244
245  assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
246  P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
247  P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
248  for (SparseSet<unsigned>::const_iterator I =
249         LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
250    P.LiveOutRegs.push_back(*I);
251  std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
252  P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
253                      P.LiveOutRegs.end());
254}
255
256/// Finalize the region boundaries and record live ins and live outs.
257void RegPressureTracker::closeRegion() {
258  if (!isTopClosed() && !isBottomClosed()) {
259    assert(LivePhysRegs.empty() && LiveVirtRegs.empty() &&
260           "no region boundary");
261    return;
262  }
263  if (!isBottomClosed())
264    closeBottom();
265  else if (!isTopClosed())
266    closeTop();
267  // If both top and bottom are closed, do nothing.
268}
269
270/// Return true if Reg aliases a register in Regs SparseSet.
271static bool hasRegAlias(unsigned Reg, SparseSet<unsigned> &Regs,
272                        const TargetRegisterInfo *TRI) {
273  assert(!TargetRegisterInfo::isVirtualRegister(Reg) && "only for physregs");
274  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
275    if (Regs.count(*AI))
276      return true;
277  return false;
278}
279
280/// Return true if Reg aliases a register in unsorted Regs SmallVector.
281/// This is only valid for physical registers.
282static SmallVectorImpl<unsigned>::iterator
283findRegAlias(unsigned Reg, SmallVectorImpl<unsigned> &Regs,
284             const TargetRegisterInfo *TRI) {
285  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
286    SmallVectorImpl<unsigned>::iterator I =
287      std::find(Regs.begin(), Regs.end(), *AI);
288    if (I != Regs.end())
289      return I;
290  }
291  return Regs.end();
292}
293
294/// Return true if Reg can be inserted into Regs SmallVector. For virtual
295/// register, do a linear search. For physical registers check for aliases.
296static SmallVectorImpl<unsigned>::iterator
297findReg(unsigned Reg, bool isVReg, SmallVectorImpl<unsigned> &Regs,
298        const TargetRegisterInfo *TRI) {
299  if(isVReg)
300    return std::find(Regs.begin(), Regs.end(), Reg);
301  return findRegAlias(Reg, Regs, TRI);
302}
303
304/// Collect this instruction's unique uses and defs into SmallVectors for
305/// processing defs and uses in order.
306template<bool isVReg>
307struct RegisterOperands {
308  SmallVector<unsigned, 8> Uses;
309  SmallVector<unsigned, 8> Defs;
310  SmallVector<unsigned, 8> DeadDefs;
311
312  /// Push this operand's register onto the correct vector.
313  void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
314    if (MO.readsReg()) {
315      if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end())
316      Uses.push_back(MO.getReg());
317    }
318    if (MO.isDef()) {
319      if (MO.isDead()) {
320        if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end())
321          DeadDefs.push_back(MO.getReg());
322      }
323      else {
324        if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
325          Defs.push_back(MO.getReg());
326      }
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 RegisterClassInfo *RCI) {
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 (RCI->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, RCI);
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, RCI);
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/// Consider the pressure increase caused by traversing this instruction
658/// bottom-up. Find the pressure set with the most change beyond its pressure
659/// limit based on the tracker's current pressure, and return the change in
660/// number of register units of that pressure set introduced by this
661/// instruction.
662///
663/// This assumes that the current LiveOut set is sufficient.
664///
665/// FIXME: This is expensive for an on-the-fly query. We need to cache the
666/// result per-SUnit with enough information to adjust for the current
667/// scheduling position. But this works as a proof of concept.
668void RegPressureTracker::
669getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
670                          ArrayRef<PressureElement> CriticalPSets,
671                          ArrayRef<unsigned> MaxPressureLimit) {
672  // Account for register pressure similar to RegPressureTracker::recede().
673  PhysRegOperands PhysRegOpers;
674  VirtRegOperands VirtRegOpers;
675  collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
676
677  // Snapshot Pressure.
678  // FIXME: The snapshot heap space should persist. But I'm planning to
679  // summarize the pressure effect so we don't need to snapshot at all.
680  std::vector<unsigned> SavedPressure = CurrSetPressure;
681  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
682
683  // Boost max pressure for all dead defs together.
684  // Since CurrSetPressure and MaxSetPressure
685  increasePhysRegPressure(PhysRegOpers.DeadDefs);
686  increaseVirtRegPressure(VirtRegOpers.DeadDefs);
687  decreasePhysRegPressure(PhysRegOpers.DeadDefs);
688  decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
689
690  // Kill liveness at live defs.
691  decreasePhysRegPressure(PhysRegOpers.Defs);
692  decreaseVirtRegPressure(VirtRegOpers.Defs);
693
694  // Generate liveness for uses.
695  for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
696    unsigned Reg = PhysRegOpers.Uses[i];
697    if (!hasRegAlias(Reg, LivePhysRegs, TRI)
698        && (findRegAlias(Reg, PhysRegOpers.Defs, TRI)
699            == PhysRegOpers.Defs.end())) {
700      increasePhysRegPressure(Reg);
701    }
702  }
703  for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
704    unsigned Reg = VirtRegOpers.Uses[i];
705    if (!LiveVirtRegs.count(Reg)
706        && (std::find(VirtRegOpers.Defs.begin(), VirtRegOpers.Defs.end(), Reg)
707            != VirtRegOpers.Defs.end())) {
708      increaseVirtRegPressure(Reg);
709    }
710  }
711  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
712  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
713                          MaxPressureLimit, Delta);
714  assert(Delta.CriticalMax.UnitIncrease >= 0 &&
715         Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
716
717  // Restore the tracker's state.
718  P.MaxSetPressure.swap(SavedMaxPressure);
719  CurrSetPressure.swap(SavedPressure);
720}
721
722/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
723static bool findUseBetween(unsigned Reg,
724                           SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
725                           const MachineRegisterInfo *MRI,
726                           const LiveIntervals *LIS) {
727  for (MachineRegisterInfo::use_nodbg_iterator
728         UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
729         UI != UE; UI.skipInstruction()) {
730      const MachineInstr* MI = &*UI;
731      SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
732      if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
733        return true;
734  }
735  return false;
736}
737
738/// Consider the pressure increase caused by traversing this instruction
739/// top-down. Find the register class with the most change in its pressure limit
740/// based on the tracker's current pressure, and return the number of excess
741/// register units of that pressure set introduced by this instruction.
742///
743/// This assumes that the current LiveIn set is sufficient.
744void RegPressureTracker::
745getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
746                            ArrayRef<PressureElement> CriticalPSets,
747                            ArrayRef<unsigned> MaxPressureLimit) {
748  // Account for register pressure similar to RegPressureTracker::recede().
749  PhysRegOperands PhysRegOpers;
750  VirtRegOperands VirtRegOpers;
751  collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
752
753  // Snapshot Pressure.
754  std::vector<unsigned> SavedPressure = CurrSetPressure;
755  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
756
757  // Kill liveness at last uses. Assume allocatable physregs are single-use
758  // rather than checking LiveIntervals.
759  decreasePhysRegPressure(PhysRegOpers.Uses);
760  if (RequireIntervals) {
761    SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
762    for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
763      unsigned Reg = VirtRegOpers.Uses[i];
764      const LiveInterval *LI = &LIS->getInterval(Reg);
765      // FIXME: allow the caller to pass in the list of vreg uses that remain to
766      // be bottom-scheduled to avoid searching uses at each query.
767      SlotIndex CurrIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
768      if (LI->killedAt(SlotIdx)
769          && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
770        decreaseVirtRegPressure(Reg);
771      }
772    }
773  }
774
775  // Generate liveness for defs.
776  increasePhysRegPressure(PhysRegOpers.Defs);
777  increaseVirtRegPressure(VirtRegOpers.Defs);
778
779  // Boost pressure for all dead defs together.
780  increasePhysRegPressure(PhysRegOpers.DeadDefs);
781  increaseVirtRegPressure(VirtRegOpers.DeadDefs);
782  decreasePhysRegPressure(PhysRegOpers.DeadDefs);
783  decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
784
785  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
786  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
787                          MaxPressureLimit, Delta);
788  assert(Delta.CriticalMax.UnitIncrease >= 0 &&
789         Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
790
791  // Restore the tracker's state.
792  P.MaxSetPressure.swap(SavedMaxPressure);
793  CurrSetPressure.swap(SavedPressure);
794}
795