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#ifndef NDEBUG
67void RegisterPressure::dump(const TargetRegisterInfo *TRI) {
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 {
326        if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
327          Defs.push_back(MO.getReg());
328      }
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 RegisterClassInfo *RCI) {
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 (RCI->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, RCI);
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 = LIS->getInstructionIndex(CurrPos).getRegSlot();
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, RCI);
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, RCI);
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  decreasePhysRegPressure(PhysRegOpers.Defs);
680  decreaseVirtRegPressure(VirtRegOpers.Defs);
681
682  // Generate liveness for uses.
683  for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
684    unsigned Reg = PhysRegOpers.Uses[i];
685    if (!hasRegAlias(Reg, LivePhysRegs, TRI))
686      increasePhysRegPressure(Reg);
687  }
688  for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
689    unsigned Reg = VirtRegOpers.Uses[i];
690    if (!LiveVirtRegs.count(Reg))
691      increaseVirtRegPressure(Reg);
692  }
693}
694
695/// Consider the pressure increase caused by traversing this instruction
696/// bottom-up. Find the pressure set with the most change beyond its pressure
697/// limit based on the tracker's current pressure, and return the change in
698/// number of register units of that pressure set introduced by this
699/// instruction.
700///
701/// This assumes that the current LiveOut set is sufficient.
702///
703/// FIXME: This is expensive for an on-the-fly query. We need to cache the
704/// result per-SUnit with enough information to adjust for the current
705/// scheduling position. But this works as a proof of concept.
706void RegPressureTracker::
707getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
708                          ArrayRef<PressureElement> CriticalPSets,
709                          ArrayRef<unsigned> MaxPressureLimit) {
710  // Snapshot Pressure.
711  // FIXME: The snapshot heap space should persist. But I'm planning to
712  // summarize the pressure effect so we don't need to snapshot at all.
713  std::vector<unsigned> SavedPressure = CurrSetPressure;
714  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
715
716  bumpUpwardPressure(MI);
717
718  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
719  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
720                          MaxPressureLimit, Delta);
721  assert(Delta.CriticalMax.UnitIncrease >= 0 &&
722         Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
723
724  // Restore the tracker's state.
725  P.MaxSetPressure.swap(SavedMaxPressure);
726  CurrSetPressure.swap(SavedPressure);
727}
728
729/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
730static bool findUseBetween(unsigned Reg,
731                           SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
732                           const MachineRegisterInfo *MRI,
733                           const LiveIntervals *LIS) {
734  for (MachineRegisterInfo::use_nodbg_iterator
735         UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
736         UI != UE; UI.skipInstruction()) {
737      const MachineInstr* MI = &*UI;
738      SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
739      if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
740        return true;
741  }
742  return false;
743}
744
745/// Record the downward impact of a single instruction on current register
746/// pressure. Unlike the advance/recede pressure tracking interface, this does
747/// not discover live in/outs.
748///
749/// This is intended for speculative queries. It leaves pressure inconsistent
750/// with the current position, so must be restored by the caller.
751void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
752  // Account for register pressure similar to RegPressureTracker::recede().
753  PhysRegOperands PhysRegOpers;
754  VirtRegOperands VirtRegOpers;
755  collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
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
786/// Consider the pressure increase caused by traversing this instruction
787/// top-down. Find the register class with the most change in its pressure limit
788/// based on the tracker's current pressure, and return the number of excess
789/// register units of that pressure set introduced by this instruction.
790///
791/// This assumes that the current LiveIn set is sufficient.
792void RegPressureTracker::
793getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
794                            ArrayRef<PressureElement> CriticalPSets,
795                            ArrayRef<unsigned> MaxPressureLimit) {
796  // Snapshot Pressure.
797  std::vector<unsigned> SavedPressure = CurrSetPressure;
798  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
799
800  bumpDownwardPressure(MI);
801
802  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
803  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
804                          MaxPressureLimit, Delta);
805  assert(Delta.CriticalMax.UnitIncrease >= 0 &&
806         Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
807
808  // Restore the tracker's state.
809  P.MaxSetPressure.swap(SavedMaxPressure);
810  CurrSetPressure.swap(SavedPressure);
811}
812
813/// Get the pressure of each PSet after traversing this instruction bottom-up.
814void RegPressureTracker::
815getUpwardPressure(const MachineInstr *MI,
816                  std::vector<unsigned> &PressureResult,
817                  std::vector<unsigned> &MaxPressureResult) {
818  // Snapshot pressure.
819  PressureResult = CurrSetPressure;
820  MaxPressureResult = P.MaxSetPressure;
821
822  bumpUpwardPressure(MI);
823
824  // Current pressure becomes the result. Restore current pressure.
825  P.MaxSetPressure.swap(MaxPressureResult);
826  CurrSetPressure.swap(PressureResult);
827}
828
829/// Get the pressure of each PSet after traversing this instruction top-down.
830void RegPressureTracker::
831getDownwardPressure(const MachineInstr *MI,
832                    std::vector<unsigned> &PressureResult,
833                    std::vector<unsigned> &MaxPressureResult) {
834  // Snapshot pressure.
835  PressureResult = CurrSetPressure;
836  MaxPressureResult = P.MaxSetPressure;
837
838  bumpDownwardPressure(MI);
839
840  // Current pressure becomes the result. Restore current pressure.
841  P.MaxSetPressure.swap(MaxPressureResult);
842  CurrSetPressure.swap(PressureResult);
843}
844