RegisterPressure.cpp revision 4dfeef100d940a0c1ca22055dcb29b02a4848f65 
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[*PSet] > MaxSetPressure[*PSet])
34      MaxSetPressure[*PSet] = CurrSetPressure[*PSet];
35  }
36}
37
38/// Decrease register pressure for each set impacted by this register class.
39static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
40                                const TargetRegisterClass *RC,
41                                const TargetRegisterInfo *TRI) {
42  unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
43  for (const int *PSet = TRI->getRegClassPressureSets(RC);
44       *PSet != -1; ++PSet) {
45    assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow");
46    CurrSetPressure[*PSet] -= Weight;
47  }
48}
49
50/// Directly increase pressure only within this RegisterPressure result.
51void RegisterPressure::increase(const TargetRegisterClass *RC,
52                                const TargetRegisterInfo *TRI) {
53  increaseSetPressure(MaxSetPressure, MaxSetPressure, RC, TRI);
54}
55
56/// Directly decrease pressure only within this RegisterPressure result.
57void RegisterPressure::decrease(const TargetRegisterClass *RC,
58                                const TargetRegisterInfo *TRI) {
59  decreaseSetPressure(MaxSetPressure, RC, TRI);
60}
61
62/// Increase the current pressure as impacted by this physical register and bump
63/// the high water mark if needed.
64void RegPressureTracker::increasePhysRegPressure(unsigned Reg) {
65  increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
66                      TRI->getMinimalPhysRegClass(Reg), TRI);
67}
68
69/// Simply decrease the current pressure as impacted by this physcial register.
70void RegPressureTracker::decreasePhysRegPressure(unsigned Reg) {
71  decreaseSetPressure(CurrSetPressure, TRI->getMinimalPhysRegClass(Reg), TRI);
72}
73
74/// Increase the current pressure as impacted by this virtual register and bump
75/// the high water mark if needed.
76void RegPressureTracker::increaseVirtRegPressure(unsigned Reg) {
77  increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
78                      MRI->getRegClass(Reg), TRI);
79}
80
81/// Simply decrease the current pressure as impacted by this virtual register.
82void RegPressureTracker::decreaseVirtRegPressure(unsigned Reg) {
83  decreaseSetPressure(CurrSetPressure, MRI->getRegClass(Reg), TRI);
84}
85
86/// Clear the result so it can be used for another round of pressure tracking.
87void IntervalPressure::reset() {
88  TopIdx = BottomIdx = SlotIndex();
89  MaxSetPressure.clear();
90  LiveInRegs.clear();
91  LiveOutRegs.clear();
92}
93
94/// Clear the result so it can be used for another round of pressure tracking.
95void RegionPressure::reset() {
96  TopPos = BottomPos = MachineBasicBlock::const_iterator();
97  MaxSetPressure.clear();
98  LiveInRegs.clear();
99  LiveOutRegs.clear();
100}
101
102/// If the current top is not less than or equal to the next index, open it.
103/// We happen to need the SlotIndex for the next top for pressure update.
104void IntervalPressure::openTop(SlotIndex NextTop) {
105  if (TopIdx <= NextTop)
106    return;
107  TopIdx = SlotIndex();
108  LiveInRegs.clear();
109}
110
111/// If the current top is the previous instruction (before receding), open it.
112void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
113  if (TopPos != PrevTop)
114    return;
115  TopPos = MachineBasicBlock::const_iterator();
116  LiveInRegs.clear();
117}
118
119/// If the current bottom is not greater than the previous index, open it.
120void IntervalPressure::openBottom(SlotIndex PrevBottom) {
121  if (BottomIdx > PrevBottom)
122    return;
123  BottomIdx = SlotIndex();
124  LiveInRegs.clear();
125}
126
127/// If the current bottom is the previous instr (before advancing), open it.
128void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
129  if (BottomPos != PrevBottom)
130    return;
131  BottomPos = MachineBasicBlock::const_iterator();
132  LiveInRegs.clear();
133}
134
135/// Setup the RegPressureTracker.
136///
137/// TODO: Add support for pressure without LiveIntervals.
138void RegPressureTracker::init(const MachineFunction *mf,
139                              const RegisterClassInfo *rci,
140                              const LiveIntervals *lis,
141                              const MachineBasicBlock *mbb,
142                              MachineBasicBlock::const_iterator pos)
143{
144  MF = mf;
145  TRI = MF->getTarget().getRegisterInfo();
146  RCI = rci;
147  MRI = &MF->getRegInfo();
148  MBB = mbb;
149
150  if (RequireIntervals) {
151    assert(lis && "IntervalPressure requires LiveIntervals");
152    LIS = lis;
153  }
154
155  CurrPos = pos;
156  while (CurrPos != MBB->end() && CurrPos->isDebugValue())
157    ++CurrPos;
158
159  CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
160
161  if (RequireIntervals)
162    static_cast<IntervalPressure&>(P).reset();
163  else
164    static_cast<RegionPressure&>(P).reset();
165  P.MaxSetPressure = CurrSetPressure;
166
167  LivePhysRegs.clear();
168  LivePhysRegs.setUniverse(TRI->getNumRegs());
169  LiveVirtRegs.clear();
170  LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
171}
172
173/// Does this pressure result have a valid top position and live ins.
174bool RegPressureTracker::isTopClosed() const {
175  if (RequireIntervals)
176    return static_cast<IntervalPressure&>(P).TopIdx.isValid();
177  return (static_cast<RegionPressure&>(P).TopPos ==
178          MachineBasicBlock::const_iterator());
179}
180
181/// Does this pressure result have a valid bottom position and live outs.
182bool RegPressureTracker::isBottomClosed() const {
183  if (RequireIntervals)
184    return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
185  return (static_cast<RegionPressure&>(P).BottomPos ==
186          MachineBasicBlock::const_iterator());
187}
188
189/// Set the boundary for the top of the region and summarize live ins.
190void RegPressureTracker::closeTop() {
191  if (RequireIntervals)
192    static_cast<IntervalPressure&>(P).TopIdx =
193      LIS->getInstructionIndex(CurrPos).getRegSlot();
194  else
195    static_cast<RegionPressure&>(P).TopPos = CurrPos;
196
197  assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
198  P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
199  P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
200  for (SparseSet<unsigned>::const_iterator I =
201         LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
202    P.LiveInRegs.push_back(*I);
203  std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
204  P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
205                     P.LiveInRegs.end());
206}
207
208/// Set the boundary for the bottom of the region and summarize live outs.
209void RegPressureTracker::closeBottom() {
210  if (RequireIntervals)
211    if (CurrPos == MBB->end())
212      static_cast<IntervalPressure&>(P).BottomIdx = LIS->getMBBEndIdx(MBB);
213    else
214      static_cast<IntervalPressure&>(P).BottomIdx =
215        LIS->getInstructionIndex(CurrPos).getRegSlot();
216  else
217    static_cast<RegionPressure&>(P).BottomPos = CurrPos;
218
219  assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
220  P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
221  P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
222  for (SparseSet<unsigned>::const_iterator I =
223         LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
224    P.LiveOutRegs.push_back(*I);
225  std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
226  P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
227                      P.LiveOutRegs.end());
228}
229
230/// Finalize the region boundaries and record live ins and live outs.
231void RegPressureTracker::closeRegion() {
232  if (!isTopClosed() && !isBottomClosed()) {
233    assert(LivePhysRegs.empty() && LiveVirtRegs.empty() &&
234           "no region boundary");
235    return;
236  }
237  if (!isBottomClosed())
238    closeBottom();
239  else if (!isTopClosed())
240    closeTop();
241  // If both top and bottom are closed, do nothing.
242}
243
244/// Return true if Reg aliases a register in Regs SparseSet.
245static bool hasRegAlias(unsigned Reg, SparseSet<unsigned> &Regs,
246                        const TargetRegisterInfo *TRI) {
247  assert(!TargetRegisterInfo::isVirtualRegister(Reg) && "only for physregs");
248  for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) {
249    if (Regs.count(*Alias))
250      return true;
251  }
252  return false;
253}
254
255/// Return true if Reg aliases a register in unsorted Regs SmallVector.
256/// This is only valid for physical registers.
257static SmallVectorImpl<unsigned>::iterator
258findRegAlias(unsigned Reg, SmallVectorImpl<unsigned> &Regs,
259             const TargetRegisterInfo *TRI) {
260  for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) {
261    SmallVectorImpl<unsigned>::iterator I =
262      std::find(Regs.begin(), Regs.end(), *Alias);
263    if (I != Regs.end())
264      return I;
265  }
266  return Regs.end();
267}
268
269/// Return true if Reg can be inserted into Regs SmallVector. For virtual
270/// register, do a linear search. For physical registers check for aliases.
271static SmallVectorImpl<unsigned>::iterator
272findReg(unsigned Reg, bool isVReg, SmallVectorImpl<unsigned> &Regs,
273        const TargetRegisterInfo *TRI) {
274  if(isVReg)
275    return std::find(Regs.begin(), Regs.end(), Reg);
276  return findRegAlias(Reg, Regs, TRI);
277}
278
279/// Collect this instruction's unique uses and defs into SmallVectors for
280/// processing defs and uses in order.
281template<bool isVReg>
282struct RegisterOperands {
283  SmallVector<unsigned, 8> Uses;
284  SmallVector<unsigned, 8> Defs;
285  SmallVector<unsigned, 8> DeadDefs;
286
287  /// Push this operand's register onto the correct vector.
288  void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
289    if (MO.readsReg()) {
290      if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end())
291      Uses.push_back(MO.getReg());
292    }
293    if (MO.isDef()) {
294      if (MO.isDead()) {
295        if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end())
296          DeadDefs.push_back(MO.getReg());
297      }
298      else {
299        if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
300          Defs.push_back(MO.getReg());
301      }
302    }
303  }
304};
305typedef RegisterOperands<false> PhysRegOperands;
306typedef RegisterOperands<true> VirtRegOperands;
307
308/// Collect physical and virtual register operands.
309static void collectOperands(const MachineInstr *MI,
310                            PhysRegOperands &PhysRegOpers,
311                            VirtRegOperands &VirtRegOpers,
312                            const TargetRegisterInfo *TRI,
313                            const RegisterClassInfo *RCI) {
314  for(ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) {
315    const MachineOperand &MO = *OperI;
316    if (!MO.isReg() || !MO.getReg())
317      continue;
318
319    if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
320      VirtRegOpers.collect(MO, TRI);
321    else if (RCI->isAllocatable(MO.getReg()))
322      PhysRegOpers.collect(MO, TRI);
323  }
324  // Remove redundant physreg dead defs.
325  for (unsigned i = PhysRegOpers.DeadDefs.size(); i > 0; --i) {
326    unsigned Reg = PhysRegOpers.DeadDefs[i-1];
327    if (findRegAlias(Reg, PhysRegOpers.Defs, TRI) != PhysRegOpers.Defs.end())
328      PhysRegOpers.DeadDefs.erase(&PhysRegOpers.DeadDefs[i-1]);
329  }
330}
331
332/// Add PhysReg to the live in set and increase max pressure.
333void RegPressureTracker::discoverPhysLiveIn(unsigned Reg) {
334  assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
335  if (findRegAlias(Reg, P.LiveInRegs, TRI) == P.LiveInRegs.end())
336    return;
337
338  // At live in discovery, unconditionally increase the high water mark.
339  P.LiveInRegs.push_back(Reg);
340  P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
341}
342
343/// Add PhysReg to the live out set and increase max pressure.
344void RegPressureTracker::discoverPhysLiveOut(unsigned Reg) {
345  assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
346  if (findRegAlias(Reg, P.LiveOutRegs, TRI) == P.LiveOutRegs.end())
347    return;
348
349  // At live out discovery, unconditionally increase the high water mark.
350  P.LiveOutRegs.push_back(Reg);
351  P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
352}
353
354/// Add VirtReg to the live in set and increase max pressure.
355void RegPressureTracker::discoverVirtLiveIn(unsigned Reg) {
356  assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
357  if (std::find(P.LiveInRegs.begin(), P.LiveInRegs.end(), Reg) !=
358      P.LiveInRegs.end())
359    return;
360
361  // At live in discovery, unconditionally increase the high water mark.
362  P.LiveInRegs.push_back(Reg);
363  P.increase(MRI->getRegClass(Reg), TRI);
364}
365
366/// Add VirtReg to the live out set and increase max pressure.
367void RegPressureTracker::discoverVirtLiveOut(unsigned Reg) {
368  assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
369  if (std::find(P.LiveOutRegs.begin(), P.LiveOutRegs.end(), Reg) !=
370      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(MRI->getRegClass(Reg), TRI);
376}
377
378/// Recede across the previous instruction.
379bool RegPressureTracker::recede() {
380  // Check for the top of the analyzable region.
381  if (CurrPos == MBB->begin()) {
382    closeRegion();
383    return false;
384  }
385  if (!isBottomClosed())
386    closeBottom();
387
388  // Open the top of the region using block iterators.
389  if (!RequireIntervals && isTopClosed())
390    static_cast<RegionPressure&>(P).openTop(CurrPos);
391
392  // Find the previous instruction.
393  while (--CurrPos != MBB->begin() && CurrPos->isDebugValue());
394
395  if (CurrPos->isDebugValue()) {
396    closeRegion();
397    return false;
398  }
399  SlotIndex SlotIdx;
400  if (RequireIntervals)
401    SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
402
403  // Open the top of the region using slot indexes.
404  if (RequireIntervals && isTopClosed())
405    static_cast<IntervalPressure&>(P).openTop(SlotIdx);
406
407  PhysRegOperands PhysRegOpers;
408  VirtRegOperands VirtRegOpers;
409  collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
410
411  // Boost pressure for all dead defs together.
412  for (unsigned i = 0; i < PhysRegOpers.DeadDefs.size(); ++i)
413      increasePhysRegPressure(PhysRegOpers.DeadDefs[i]);
414  for (unsigned i = 0; i < VirtRegOpers.DeadDefs.size(); ++i)
415      increaseVirtRegPressure(VirtRegOpers.DeadDefs[i]);
416  for (unsigned i = 0; i < PhysRegOpers.DeadDefs.size(); ++i)
417      decreasePhysRegPressure(PhysRegOpers.DeadDefs[i]);
418  for (unsigned i = 0; i < VirtRegOpers.DeadDefs.size(); ++i)
419      decreaseVirtRegPressure(VirtRegOpers.DeadDefs[i]);
420
421  // Kill liveness at live defs.
422  // TODO: consider earlyclobbers?
423  for (unsigned i = 0; i < PhysRegOpers.Defs.size(); ++i) {
424    unsigned Reg = PhysRegOpers.Defs[i];
425    if (LivePhysRegs.erase(Reg))
426      decreasePhysRegPressure(Reg);
427    else
428      discoverPhysLiveOut(Reg);
429  }
430  for (unsigned i = 0; i < VirtRegOpers.Defs.size(); ++i) {
431    unsigned Reg = VirtRegOpers.Defs[i];
432    if (LiveVirtRegs.erase(Reg))
433      decreaseVirtRegPressure(Reg);
434    else
435      discoverVirtLiveOut(Reg);
436  }
437
438  // Generate liveness for uses.
439  for (unsigned i = 0; i < PhysRegOpers.Uses.size(); ++i) {
440    unsigned Reg = PhysRegOpers.Uses[i];
441    if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
442      increasePhysRegPressure(Reg);
443      LivePhysRegs.insert(Reg);
444    }
445  }
446  for (unsigned i = 0; i < VirtRegOpers.Uses.size(); ++i) {
447    unsigned Reg = VirtRegOpers.Uses[i];
448    if (!LiveVirtRegs.count(Reg)) {
449      // Adjust liveouts if LiveIntervals are available.
450      if (RequireIntervals) {
451        const LiveInterval *LI = &LIS->getInterval(Reg);
452        if (!LI->killedAt(SlotIdx))
453          discoverVirtLiveOut(Reg);
454      }
455      increaseVirtRegPressure(Reg);
456      LiveVirtRegs.insert(Reg);
457    }
458  }
459  return true;
460}
461
462/// Advance across the current instruction.
463bool RegPressureTracker::advance() {
464  // Check for the bottom of the analyzable region.
465  if (CurrPos == MBB->end()) {
466    closeRegion();
467    return false;
468  }
469  if (!isTopClosed())
470    closeTop();
471
472  SlotIndex SlotIdx;
473  if (RequireIntervals)
474    SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
475
476  // Open the bottom of the region using slot indexes.
477  if (isBottomClosed()) {
478    if (RequireIntervals)
479      static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
480    else
481      static_cast<RegionPressure&>(P).openBottom(CurrPos);
482  }
483
484  PhysRegOperands PhysRegOpers;
485  VirtRegOperands VirtRegOpers;
486  collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
487
488  // Kill liveness at last uses.
489  for (unsigned i = 0; i < PhysRegOpers.Uses.size(); ++i) {
490    unsigned Reg = PhysRegOpers.Uses[i];
491    if (!hasRegAlias(Reg, LivePhysRegs, TRI))
492      discoverPhysLiveIn(Reg);
493    else {
494      // Allocatable physregs are always single-use before regalloc.
495      decreasePhysRegPressure(Reg);
496      LivePhysRegs.erase(Reg);
497    }
498  }
499  for (unsigned i = 0; i < VirtRegOpers.Uses.size(); ++i) {
500    unsigned Reg = VirtRegOpers.Uses[i];
501    if (RequireIntervals) {
502      const LiveInterval *LI = &LIS->getInterval(Reg);
503      if (LI->killedAt(SlotIdx)) {
504        if (LiveVirtRegs.erase(Reg))
505          decreaseVirtRegPressure(Reg);
506        else
507          discoverVirtLiveIn(Reg);
508      }
509    }
510    else if (!LiveVirtRegs.count(Reg)) {
511      discoverVirtLiveIn(Reg);
512      increaseVirtRegPressure(Reg);
513    }
514  }
515
516  // Generate liveness for defs.
517  for (unsigned i = 0; i < PhysRegOpers.Defs.size(); ++i) {
518    unsigned Reg = PhysRegOpers.Defs[i];
519    if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
520      increasePhysRegPressure(Reg);
521      LivePhysRegs.insert(Reg);
522    }
523  }
524  for (unsigned i = 0; i < VirtRegOpers.Defs.size(); ++i) {
525    unsigned Reg = VirtRegOpers.Defs[i];
526    if (LiveVirtRegs.insert(Reg).second)
527      increaseVirtRegPressure(Reg);
528  }
529
530  // Boost pressure for all dead defs together.
531  for (unsigned i = 0; i < PhysRegOpers.DeadDefs.size(); ++i)
532      increasePhysRegPressure(PhysRegOpers.DeadDefs[i]);
533  for (unsigned i = 0; i < VirtRegOpers.DeadDefs.size(); ++i)
534      increaseVirtRegPressure(VirtRegOpers.DeadDefs[i]);
535  for (unsigned i = 0; i < PhysRegOpers.DeadDefs.size(); ++i)
536      decreasePhysRegPressure(PhysRegOpers.DeadDefs[i]);
537  for (unsigned i = 0; i < VirtRegOpers.DeadDefs.size(); ++i)
538      decreaseVirtRegPressure(VirtRegOpers.DeadDefs[i]);
539
540  // Find the next instruction.
541  while (++CurrPos != MBB->end() && CurrPos->isDebugValue());
542  return true;
543}
544