LLVM  6.0.0svn
RegisterScavenging.h
Go to the documentation of this file.
1 //===- RegisterScavenging.h - Machine register scavenging -------*- C++ -*-===//
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 /// \file
11 /// This file declares the machine register scavenger class. It can provide
12 /// information such as unused register at any point in a machine basic block.
13 /// It also provides a mechanism to make registers available by evicting them
14 /// to spill slots.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H
19 #define LLVM_CODEGEN_REGISTERSCAVENGING_H
20 
21 #include "llvm/ADT/BitVector.h"
22 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/MC/LaneBitmask.h"
27 
28 namespace llvm {
29 
30 class MachineInstr;
31 class TargetInstrInfo;
32 class TargetRegisterClass;
33 class TargetRegisterInfo;
34 
35 class RegScavenger {
36  const TargetRegisterInfo *TRI;
37  const TargetInstrInfo *TII;
39  MachineBasicBlock *MBB = nullptr;
41  unsigned NumRegUnits = 0;
42 
43  /// True if RegScavenger is currently tracking the liveness of registers.
44  bool Tracking = false;
45 
46  /// Information on scavenged registers (held in a spill slot).
47  struct ScavengedInfo {
48  ScavengedInfo(int FI = -1) : FrameIndex(FI) {}
49 
50  /// A spill slot used for scavenging a register post register allocation.
51  int FrameIndex;
52 
53  /// If non-zero, the specific register is currently being
54  /// scavenged. That is, it is spilled to this scavenging stack slot.
55  unsigned Reg = 0;
56 
57  /// The instruction that restores the scavenged register from stack.
58  const MachineInstr *Restore = nullptr;
59  };
60 
61  /// A vector of information on scavenged registers.
63 
64  LiveRegUnits LiveUnits;
65 
66  // These BitVectors are only used internally to forward(). They are members
67  // to avoid frequent reallocations.
68  BitVector KillRegUnits, DefRegUnits;
69  BitVector TmpRegUnits;
70 
71 public:
72  RegScavenger() = default;
73 
74  /// Start tracking liveness from the begin of basic block \p MBB.
76 
77  /// Start tracking liveness from the end of basic block \p MBB.
78  /// Use backward() to move towards the beginning of the block. This is
79  /// preferred to enterBasicBlock() and forward() because it does not depend
80  /// on the presence of kill flags.
82 
83  /// Move the internal MBB iterator and update register states.
84  void forward();
85 
86  /// Move the internal MBB iterator and update register states until
87  /// it has processed the specific iterator.
89  if (!Tracking && MBB->begin() != I) forward();
90  while (MBBI != I) forward();
91  }
92 
93  /// Invert the behavior of forward() on the current instruction (undo the
94  /// changes to the available registers made by forward()).
95  void unprocess();
96 
97  /// Unprocess instructions until you reach the provided iterator.
99  while (MBBI != I) unprocess();
100  }
101 
102  /// Update internal register state and move MBB iterator backwards.
103  /// Contrary to unprocess() this method gives precise results even in the
104  /// absence of kill flags.
105  void backward();
106 
107  /// Call backward() as long as the internal iterator does not point to \p I.
109  while (MBBI != I)
110  backward();
111  }
112 
113  /// Move the internal MBB iterator but do not update register states.
115  if (I == MachineBasicBlock::iterator(nullptr))
116  Tracking = false;
117  MBBI = I;
118  }
119 
121 
122  /// Return if a specific register is currently used.
123  bool isRegUsed(unsigned Reg, bool includeReserved = true) const;
124 
125  /// Return all available registers in the register class in Mask.
127 
128  /// Find an unused register of the specified register class.
129  /// Return 0 if none is found.
130  unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const;
131 
132  /// Add a scavenging frame index.
133  void addScavengingFrameIndex(int FI) {
134  Scavenged.push_back(ScavengedInfo(FI));
135  }
136 
137  /// Query whether a frame index is a scavenging frame index.
138  bool isScavengingFrameIndex(int FI) const {
140  IE = Scavenged.end(); I != IE; ++I)
141  if (I->FrameIndex == FI)
142  return true;
143 
144  return false;
145  }
146 
147  /// Get an array of scavenging frame indices.
150  IE = Scavenged.end(); I != IE; ++I)
151  if (I->FrameIndex >= 0)
152  A.push_back(I->FrameIndex);
153  }
154 
155  /// Make a register of the specific register class
156  /// available and do the appropriate bookkeeping. SPAdj is the stack
157  /// adjustment due to call frame, it's passed along to eliminateFrameIndex().
158  /// Returns the scavenged register.
159  /// This is deprecated as it depends on the quality of the kill flags being
160  /// present; Use scavengeRegisterBackwards() instead!
161  unsigned scavengeRegister(const TargetRegisterClass *RegClass,
162  MachineBasicBlock::iterator I, int SPAdj);
163  unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) {
164  return scavengeRegister(RegClass, MBBI, SPAdj);
165  }
166 
167  /// Make a register of the specific register class available from the current
168  /// position backwards to the place before \p To. If \p RestoreAfter is true
169  /// this includes the instruction following the current position.
170  /// SPAdj is the stack adjustment due to call frame, it's passed along to
171  /// eliminateFrameIndex().
172  /// Returns the scavenged register.
175  bool RestoreAfter, int SPAdj);
176 
177  /// Tell the scavenger a register is used.
178  void setRegUsed(unsigned Reg, LaneBitmask LaneMask = LaneBitmask::getAll());
179 
180 private:
181  /// Returns true if a register is reserved. It is never "unused".
182  bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); }
183 
184  /// setUsed / setUnused - Mark the state of one or a number of register units.
185  ///
186  void setUsed(const BitVector &RegUnits) {
187  LiveUnits.addUnits(RegUnits);
188  }
189  void setUnused(const BitVector &RegUnits) {
190  LiveUnits.removeUnits(RegUnits);
191  }
192 
193  /// Processes the current instruction and fill the KillRegUnits and
194  /// DefRegUnits bit vectors.
195  void determineKillsAndDefs();
196 
197  /// Add all Reg Units that Reg contains to BV.
198  void addRegUnits(BitVector &BV, unsigned Reg);
199 
200  /// Remove all Reg Units that \p Reg contains from \p BV.
201  void removeRegUnits(BitVector &BV, unsigned Reg);
202 
203  /// Return the candidate register that is unused for the longest after
204  /// StartMI. UseMI is set to the instruction where the search stopped.
205  ///
206  /// No more than InstrLimit instructions are inspected.
207  unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI,
208  BitVector &Candidates,
209  unsigned InstrLimit,
211 
212  /// Initialize RegisterScavenger.
213  void init(MachineBasicBlock &MBB);
214 
215  /// Mark live-in registers of basic block as used.
216  void setLiveInsUsed(const MachineBasicBlock &MBB);
217 
218  /// Spill a register after position \p After and reload it before position
219  /// \p UseMI.
220  ScavengedInfo &spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
223 };
224 
225 /// Replaces all frame index virtual registers with physical registers. Uses the
226 /// register scavenger to find an appropriate register to use.
228 
229 } // end namespace llvm
230 
231 #endif // LLVM_CODEGEN_REGISTERSCAVENGING_H
void push_back(const T &Elt)
Definition: SmallVector.h:212
A common definition of LaneBitmask for use in TableGen and CodeGen.
bool isScavengingFrameIndex(int FI) const
Query whether a frame index is a scavenging frame index.
void skipTo(MachineBasicBlock::iterator I)
Move the internal MBB iterator but do not update register states.
void backward(MachineBasicBlock::iterator I)
Call backward() as long as the internal iterator does not point to I.
bool isRegUsed(unsigned Reg, bool includeReserved=true) const
Return if a specific register is currently used.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static LaneBitmask getAll()
Definition: LaneBitmask.h:84
unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const
Find an unused register of the specified register class.
void removeUnits(const BitVector &RegUnits)
Removes all register units marked in the bitvector RegUnits.
Definition: LiveRegUnits.h:119
unsigned scavengeRegisterBackwards(const TargetRegisterClass &RC, MachineBasicBlock::iterator To, bool RestoreAfter, int SPAdj)
Make a register of the specific register class available from the current position backwards to the p...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
Reg
All possible values of the reg field in the ModR/M byte.
void backward()
Update internal register state and move MBB iterator backwards.
void scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS)
Replaces all frame index virtual registers with physical registers.
void forward()
Move the internal MBB iterator and update register states.
MachineBasicBlock::iterator getCurrentPosition() const
BitVector getRegsAvailable(const TargetRegisterClass *RC)
Return all available registers in the register class in Mask.
void unprocess(MachineBasicBlock::iterator I)
Unprocess instructions until you reach the provided iterator.
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder & UseMI
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
void unprocess()
Invert the behavior of forward() on the current instruction (undo the changes to the available regist...
void forward(MachineBasicBlock::iterator I)
Move the internal MBB iterator and update register states until it has processed the specific iterato...
void addUnits(const BitVector &RegUnits)
Adds all register units marked in the bitvector RegUnits.
Definition: LiveRegUnits.h:115
A set of register units.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
void addScavengingFrameIndex(int FI)
Add a scavenging frame index.
void enterBasicBlockEnd(MachineBasicBlock &MBB)
Start tracking liveness from the end of basic block MBB.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:59
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
void enterBasicBlock(MachineBasicBlock &MBB)
Start tracking liveness from the begin of basic block MBB.
#define I(x, y, z)
Definition: MD5.cpp:58
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))
void setRegUsed(unsigned Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Tell the scavenger a register is used.
unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj)
void getScavengingFrameIndices(SmallVectorImpl< int > &A) const
Get an array of scavenging frame indices.
RegScavenger()=default
bool isReserved(unsigned PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
unsigned scavengeRegister(const TargetRegisterClass *RegClass, MachineBasicBlock::iterator I, int SPAdj)
Make a register of the specific register class available and do the appropriate bookkeeping.