LLVM  9.0.0svn
RegisterScavenging.h
Go to the documentation of this file.
1 //===- RegisterScavenging.h - Machine register scavenging -------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// This file declares the machine register scavenger class. It can provide
11 /// information such as unused register at any point in a machine basic block.
12 /// It also provides a mechanism to make registers available by evicting them
13 /// to spill slots.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H
18 #define LLVM_CODEGEN_REGISTERSCAVENGING_H
19 
20 #include "llvm/ADT/BitVector.h"
21 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/MC/LaneBitmask.h"
26 
27 namespace llvm {
28 
29 class MachineInstr;
30 class TargetInstrInfo;
31 class TargetRegisterClass;
32 class TargetRegisterInfo;
33 
34 class RegScavenger {
35  const TargetRegisterInfo *TRI;
36  const TargetInstrInfo *TII;
38  MachineBasicBlock *MBB = nullptr;
40  unsigned NumRegUnits = 0;
41 
42  /// True if RegScavenger is currently tracking the liveness of registers.
43  bool Tracking = false;
44 
45  /// Information on scavenged registers (held in a spill slot).
46  struct ScavengedInfo {
47  ScavengedInfo(int FI = -1) : FrameIndex(FI) {}
48 
49  /// A spill slot used for scavenging a register post register allocation.
50  int FrameIndex;
51 
52  /// If non-zero, the specific register is currently being
53  /// scavenged. That is, it is spilled to this scavenging stack slot.
54  unsigned Reg = 0;
55 
56  /// The instruction that restores the scavenged register from stack.
57  const MachineInstr *Restore = nullptr;
58  };
59 
60  /// A vector of information on scavenged registers.
62 
63  LiveRegUnits LiveUnits;
64 
65  // These BitVectors are only used internally to forward(). They are members
66  // to avoid frequent reallocations.
67  BitVector KillRegUnits, DefRegUnits;
68  BitVector TmpRegUnits;
69 
70 public:
71  RegScavenger() = default;
72 
73  /// Start tracking liveness from the begin of basic block \p MBB.
75 
76  /// Start tracking liveness from the end of basic block \p MBB.
77  /// Use backward() to move towards the beginning of the block. This is
78  /// preferred to enterBasicBlock() and forward() because it does not depend
79  /// on the presence of kill flags.
81 
82  /// Move the internal MBB iterator and update register states.
83  void forward();
84 
85  /// Move the internal MBB iterator and update register states until
86  /// it has processed the specific iterator.
88  if (!Tracking && MBB->begin() != I) forward();
89  while (MBBI != I) forward();
90  }
91 
92  /// Invert the behavior of forward() on the current instruction (undo the
93  /// changes to the available registers made by forward()).
94  void unprocess();
95 
96  /// Unprocess instructions until you reach the provided iterator.
98  while (MBBI != I) unprocess();
99  }
100 
101  /// Update internal register state and move MBB iterator backwards.
102  /// Contrary to unprocess() this method gives precise results even in the
103  /// absence of kill flags.
104  void backward();
105 
106  /// Call backward() as long as the internal iterator does not point to \p I.
108  while (MBBI != I)
109  backward();
110  }
111 
112  /// Move the internal MBB iterator but do not update register states.
114  if (I == MachineBasicBlock::iterator(nullptr))
115  Tracking = false;
116  MBBI = I;
117  }
118 
120 
121  /// Return if a specific register is currently used.
122  bool isRegUsed(unsigned Reg, bool includeReserved = true) const;
123 
124  /// Return all available registers in the register class in Mask.
126 
127  /// Find an unused register of the specified register class.
128  /// Return 0 if none is found.
129  unsigned FindUnusedReg(const TargetRegisterClass *RC) const;
130 
131  /// Add a scavenging frame index.
132  void addScavengingFrameIndex(int FI) {
133  Scavenged.push_back(ScavengedInfo(FI));
134  }
135 
136  /// Query whether a frame index is a scavenging frame index.
137  bool isScavengingFrameIndex(int FI) const {
139  IE = Scavenged.end(); I != IE; ++I)
140  if (I->FrameIndex == FI)
141  return true;
142 
143  return false;
144  }
145 
146  /// Get an array of scavenging frame indices.
149  IE = Scavenged.end(); I != IE; ++I)
150  if (I->FrameIndex >= 0)
151  A.push_back(I->FrameIndex);
152  }
153 
154  /// Make a register of the specific register class
155  /// available and do the appropriate bookkeeping. SPAdj is the stack
156  /// adjustment due to call frame, it's passed along to eliminateFrameIndex().
157  /// Returns the scavenged register.
158  /// This is deprecated as it depends on the quality of the kill flags being
159  /// present; Use scavengeRegisterBackwards() instead!
160  unsigned scavengeRegister(const TargetRegisterClass *RC,
161  MachineBasicBlock::iterator I, int SPAdj);
162  unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) {
163  return scavengeRegister(RegClass, MBBI, SPAdj);
164  }
165 
166  /// Make a register of the specific register class available from the current
167  /// position backwards to the place before \p To. If \p RestoreAfter is true
168  /// this includes the instruction following the current position.
169  /// SPAdj is the stack adjustment due to call frame, it's passed along to
170  /// eliminateFrameIndex().
171  /// Returns the scavenged register.
174  bool RestoreAfter, int SPAdj);
175 
176  /// Tell the scavenger a register is used.
177  void setRegUsed(unsigned Reg, LaneBitmask LaneMask = LaneBitmask::getAll());
178 
179 private:
180  /// Returns true if a register is reserved. It is never "unused".
181  bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); }
182 
183  /// setUsed / setUnused - Mark the state of one or a number of register units.
184  ///
185  void setUsed(const BitVector &RegUnits) {
186  LiveUnits.addUnits(RegUnits);
187  }
188  void setUnused(const BitVector &RegUnits) {
189  LiveUnits.removeUnits(RegUnits);
190  }
191 
192  /// Processes the current instruction and fill the KillRegUnits and
193  /// DefRegUnits bit vectors.
194  void determineKillsAndDefs();
195 
196  /// Add all Reg Units that Reg contains to BV.
197  void addRegUnits(BitVector &BV, unsigned Reg);
198 
199  /// Remove all Reg Units that \p Reg contains from \p BV.
200  void removeRegUnits(BitVector &BV, unsigned Reg);
201 
202  /// Return the candidate register that is unused for the longest after
203  /// StartMI. UseMI is set to the instruction where the search stopped.
204  ///
205  /// No more than InstrLimit instructions are inspected.
206  unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI,
207  BitVector &Candidates,
208  unsigned InstrLimit,
210 
211  /// Initialize RegisterScavenger.
212  void init(MachineBasicBlock &MBB);
213 
214  /// Mark live-in registers of basic block as used.
215  void setLiveInsUsed(const MachineBasicBlock &MBB);
216 
217  /// Spill a register after position \p After and reload it before position
218  /// \p UseMI.
219  ScavengedInfo &spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
222 };
223 
224 /// Replaces all frame index virtual registers with physical registers. Uses the
225 /// register scavenger to find an appropriate register to use.
227 
228 } // end namespace llvm
229 
230 #endif // LLVM_CODEGEN_REGISTERSCAVENGING_H
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.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void push_back(const T &Elt)
Definition: SmallVector.h:211
unsigned Reg
void removeUnits(const BitVector &RegUnits)
Removes all register units marked in the bitvector RegUnits.
Definition: LiveRegUnits.h:149
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:41
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:83
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.
unsigned FindUnusedReg(const TargetRegisterClass *RC) const
Find an unused register of the specified register class.
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
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:145
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:63
void enterBasicBlock(MachineBasicBlock &MBB)
Start tracking liveness from the begin of basic block MBB.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned scavengeRegister(const TargetRegisterClass *RC, MachineBasicBlock::iterator I, int SPAdj)
Make a register of the specific register class available and do the appropriate bookkeeping.
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.