RegisterPressure.cpp revision a7de4b99e47fc5061181ecdf7fd65e1b8441e2e7 
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 void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
567                                       ArrayRef<unsigned> NewPressureVec,
568                                       RegPressureDelta &Delta,
569                                       const TargetRegisterInfo *TRI) {
570  int ExcessUnits = 0;
571  unsigned PSetID = ~0U;
572  for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
573    unsigned POld = OldPressureVec[i];
574    unsigned PNew = NewPressureVec[i];
575    int PDiff = (int)PNew - (int)POld;
576    if (!PDiff) // No change in this set in the common case.
577      continue;
578    // Only consider change beyond the limit.
579    unsigned Limit = TRI->getRegPressureSetLimit(i);
580    if (Limit > POld) {
581      if (Limit > PNew)
582        PDiff = 0;            // Under the limit
583      else
584        PDiff = PNew - Limit; // Just exceeded limit.
585    }
586    else if (Limit > PNew)
587      PDiff = Limit - POld;   // Just obeyed limit.
588
589    if (std::abs(PDiff) > std::abs(ExcessUnits)) {
590      ExcessUnits = PDiff;
591      PSetID = i;
592    }
593  }
594  Delta.Excess.PSetID = PSetID;
595  Delta.Excess.UnitIncrease = ExcessUnits;
596}
597
598/// Find the max change in max pressure that either surpasses a critical PSet
599/// limit or exceeds the current MaxPressureLimit.
600///
601/// FIXME: comparing each element of the old and new MaxPressure vectors here is
602/// silly. It's done now to demonstrate the concept but will go away with a
603/// RegPressureTracker API change to work with pressure differences.
604static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
605                                    ArrayRef<unsigned> NewMaxPressureVec,
606                                    ArrayRef<PressureElement> CriticalPSets,
607                                    ArrayRef<unsigned> MaxPressureLimit,
608                                    RegPressureDelta &Delta) {
609  Delta.CriticalMax = PressureElement();
610  Delta.CurrentMax = PressureElement();
611
612  unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
613  for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
614    unsigned POld = OldMaxPressureVec[i];
615    unsigned PNew = NewMaxPressureVec[i];
616    if (PNew == POld) // No change in this set in the common case.
617      continue;
618
619    while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
620      ++CritIdx;
621
622    if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
623      int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
624      if (PDiff > Delta.CriticalMax.UnitIncrease) {
625        Delta.CriticalMax.PSetID = i;
626        Delta.CriticalMax.UnitIncrease = PDiff;
627      }
628    }
629
630    // Find the greatest increase above MaxPressureLimit.
631    // (Ignores negative MDiff).
632    int MDiff = (int)PNew - (int)MaxPressureLimit[i];
633    if (MDiff > Delta.CurrentMax.UnitIncrease) {
634      Delta.CurrentMax.PSetID = i;
635      Delta.CurrentMax.UnitIncrease = PNew;
636    }
637  }
638}
639
640/// Consider the pressure increase caused by traversing this instruction
641/// bottom-up. Find the pressure set with the most change beyond its pressure
642/// limit based on the tracker's current pressure, and return the change in
643/// number of register units of that pressure set introduced by this
644/// instruction.
645///
646/// This assumes that the current LiveOut set is sufficient.
647///
648/// FIXME: This is expensive for an on-the-fly query. We need to cache the
649/// result per-SUnit with enough information to adjust for the current
650/// scheduling position. But this works as a proof of concept.
651void RegPressureTracker::
652getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
653                          ArrayRef<PressureElement> CriticalPSets,
654                          ArrayRef<unsigned> MaxPressureLimit) {
655  // Account for register pressure similar to RegPressureTracker::recede().
656  PhysRegOperands PhysRegOpers;
657  VirtRegOperands VirtRegOpers;
658  collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
659
660  // Snapshot Pressure.
661  // FIXME: The snapshot heap space should persist. But I'm planning to
662  // summarize the pressure effect so we don't need to snapshot at all.
663  std::vector<unsigned> SavedPressure = CurrSetPressure;
664  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
665
666  // Boost max pressure for all dead defs together.
667  // Since CurrSetPressure and MaxSetPressure
668  increasePhysRegPressure(PhysRegOpers.DeadDefs);
669  increaseVirtRegPressure(VirtRegOpers.DeadDefs);
670  decreasePhysRegPressure(PhysRegOpers.DeadDefs);
671  decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
672
673  // Kill liveness at live defs.
674  decreasePhysRegPressure(PhysRegOpers.Defs);
675  decreaseVirtRegPressure(VirtRegOpers.Defs);
676
677  // Generate liveness for uses.
678  for (unsigned i = 0, e = PhysRegOpers.Uses.size(); i < e; ++i) {
679    unsigned Reg = PhysRegOpers.Uses[i];
680    if (!hasRegAlias(Reg, LivePhysRegs, TRI)
681        && (findRegAlias(Reg, PhysRegOpers.Defs, TRI)
682            == PhysRegOpers.Defs.end())) {
683      increasePhysRegPressure(Reg);
684    }
685  }
686  for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
687    unsigned Reg = VirtRegOpers.Uses[i];
688    if (!LiveVirtRegs.count(Reg)
689        && (std::find(VirtRegOpers.Defs.begin(), VirtRegOpers.Defs.end(), Reg)
690            != VirtRegOpers.Defs.end())) {
691      increaseVirtRegPressure(Reg);
692    }
693  }
694  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
695  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
696                          MaxPressureLimit, Delta);
697  assert(Delta.CriticalMax.UnitIncrease >= 0 &&
698         Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
699
700  // Restore the tracker's state.
701  P.MaxSetPressure.swap(SavedMaxPressure);
702  CurrSetPressure.swap(SavedPressure);
703}
704
705/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
706static bool findUseBetween(unsigned Reg,
707                           SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
708                           const MachineRegisterInfo *MRI,
709                           const LiveIntervals *LIS) {
710  for (MachineRegisterInfo::use_nodbg_iterator
711         UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
712         UI != UE; UI.skipInstruction()) {
713      const MachineInstr* MI = &*UI;
714      SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
715      if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
716        return true;
717  }
718  return false;
719}
720
721/// Consider the pressure increase caused by traversing this instruction
722/// top-down. Find the register class with the most change in its pressure limit
723/// based on the tracker's current pressure, and return the number of excess
724/// register units of that pressure set introduced by this instruction.
725///
726/// This assumes that the current LiveIn set is sufficient.
727void RegPressureTracker::
728getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
729                            ArrayRef<PressureElement> CriticalPSets,
730                            ArrayRef<unsigned> MaxPressureLimit) {
731  // Account for register pressure similar to RegPressureTracker::recede().
732  PhysRegOperands PhysRegOpers;
733  VirtRegOperands VirtRegOpers;
734  collectOperands(MI, PhysRegOpers, VirtRegOpers, TRI, RCI);
735
736  // Snapshot Pressure.
737  std::vector<unsigned> SavedPressure = CurrSetPressure;
738  std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
739
740  // Kill liveness at last uses. Assume allocatable physregs are single-use
741  // rather than checking LiveIntervals.
742  decreasePhysRegPressure(PhysRegOpers.Uses);
743  if (RequireIntervals) {
744    SlotIndex SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
745    for (unsigned i = 0, e = VirtRegOpers.Uses.size(); i < e; ++i) {
746      unsigned Reg = VirtRegOpers.Uses[i];
747      const LiveInterval *LI = &LIS->getInterval(Reg);
748      // FIXME: allow the caller to pass in the list of vreg uses that remain to
749      // be bottom-scheduled to avoid searching uses at each query.
750      SlotIndex CurrIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
751      if (LI->killedAt(SlotIdx)
752          && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
753        decreaseVirtRegPressure(Reg);
754      }
755    }
756  }
757
758  // Generate liveness for defs.
759  increasePhysRegPressure(PhysRegOpers.Defs);
760  increaseVirtRegPressure(VirtRegOpers.Defs);
761
762  // Boost pressure for all dead defs together.
763  increasePhysRegPressure(PhysRegOpers.DeadDefs);
764  increaseVirtRegPressure(VirtRegOpers.DeadDefs);
765  decreasePhysRegPressure(PhysRegOpers.DeadDefs);
766  decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
767
768  computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, TRI);
769  computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
770                          MaxPressureLimit, Delta);
771  assert(Delta.CriticalMax.UnitIncrease >= 0 &&
772         Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
773
774  // Restore the tracker's state.
775  P.MaxSetPressure.swap(SavedMaxPressure);
776  CurrSetPressure.swap(SavedPressure);
777}
778