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