LLVM  8.0.0svn
LivePhysRegs.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/LivePhysRegs.h - Live Physical Register Set -*- 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 implements the LivePhysRegs utility for tracking liveness of
12 /// physical registers. This can be used for ad-hoc liveness tracking after
13 /// register allocation. You can start with the live-ins/live-outs at the
14 /// beginning/end of a block and update the information while walking the
15 /// instructions inside the block. This implementation tracks the liveness on a
16 /// sub-register granularity.
17 ///
18 /// We assume that the high bits of a physical super-register are not preserved
19 /// unless the instruction has an implicit-use operand reading the super-
20 /// register.
21 ///
22 /// X86 Example:
23 /// %ymm0 = ...
24 /// %xmm0 = ... (Kills %xmm0, all %xmm0s sub-registers, and %ymm0)
25 ///
26 /// %ymm0 = ...
27 /// %xmm0 = ..., implicit %ymm0 (%ymm0 and all its sub-registers are alive)
28 //===----------------------------------------------------------------------===//
29 
30 #ifndef LLVM_CODEGEN_LIVEPHYSREGS_H
31 #define LLVM_CODEGEN_LIVEPHYSREGS_H
32 
33 #include "llvm/ADT/SparseSet.h"
36 #include "llvm/MC/MCRegisterInfo.h"
37 #include <cassert>
38 #include <utility>
39 
40 namespace llvm {
41 
42 class MachineInstr;
43 class MachineOperand;
44 class MachineRegisterInfo;
45 class raw_ostream;
46 
47 /// A set of physical registers with utility functions to track liveness
48 /// when walking backward/forward through a basic block.
49 class LivePhysRegs {
50  const TargetRegisterInfo *TRI = nullptr;
52  RegisterSet LiveRegs;
53 
54 public:
55  /// Constructs an unitialized set. init() needs to be called to initialize it.
56  LivePhysRegs() = default;
57 
58  /// Constructs and initializes an empty set.
59  LivePhysRegs(const TargetRegisterInfo &TRI) : TRI(&TRI) {
60  LiveRegs.setUniverse(TRI.getNumRegs());
61  }
62 
63  LivePhysRegs(const LivePhysRegs&) = delete;
64  LivePhysRegs &operator=(const LivePhysRegs&) = delete;
65 
66  /// (re-)initializes and clears the set.
67  void init(const TargetRegisterInfo &TRI) {
68  this->TRI = &TRI;
69  LiveRegs.clear();
70  LiveRegs.setUniverse(TRI.getNumRegs());
71  }
72 
73  /// Clears the set.
74  void clear() { LiveRegs.clear(); }
75 
76  /// Returns true if the set is empty.
77  bool empty() const { return LiveRegs.empty(); }
78 
79  /// Adds a physical register and all its sub-registers to the set.
81  assert(TRI && "LivePhysRegs is not initialized.");
82  assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
83  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
84  SubRegs.isValid(); ++SubRegs)
85  LiveRegs.insert(*SubRegs);
86  }
87 
88  /// Removes a physical register, all its sub-registers, and all its
89  /// super-registers from the set.
91  assert(TRI && "LivePhysRegs is not initialized.");
92  assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
93  for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R)
94  LiveRegs.erase(*R);
95  }
96 
97  /// Removes physical registers clobbered by the regmask operand \p MO.
98  void removeRegsInMask(const MachineOperand &MO,
99  SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers =
100  nullptr);
101 
102  /// Returns true if register \p Reg is contained in the set. This also
103  /// works if only the super register of \p Reg has been defined, because
104  /// addReg() always adds all sub-registers to the set as well.
105  /// Note: Returns false if just some sub registers are live, use available()
106  /// when searching a free register.
107  bool contains(MCPhysReg Reg) const { return LiveRegs.count(Reg); }
108 
109  /// Returns true if register \p Reg and no aliasing register is in the set.
110  bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const;
111 
112  /// Remove defined registers and regmask kills from the set.
113  void removeDefs(const MachineInstr &MI);
114 
115  /// Add uses to the set.
116  void addUses(const MachineInstr &MI);
117 
118  /// Simulates liveness when stepping backwards over an instruction(bundle).
119  /// Remove Defs, add uses. This is the recommended way of calculating
120  /// liveness.
121  void stepBackward(const MachineInstr &MI);
122 
123  /// Simulates liveness when stepping forward over an instruction(bundle).
124  /// Remove killed-uses, add defs. This is the not recommended way, because it
125  /// depends on accurate kill flags. If possible use stepBackward() instead of
126  /// this function. The clobbers set will be the list of registers either
127  /// defined or clobbered by a regmask. The operand will identify whether this
128  /// is a regmask or register operand.
129  void stepForward(const MachineInstr &MI,
130  SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers);
131 
132  /// Adds all live-in registers of basic block \p MBB.
133  /// Live in registers are the registers in the blocks live-in list and the
134  /// pristine registers.
135  void addLiveIns(const MachineBasicBlock &MBB);
136 
137  /// Adds all live-out registers of basic block \p MBB.
138  /// Live out registers are the union of the live-in registers of the successor
139  /// blocks and pristine registers. Live out registers of the end block are the
140  /// callee saved registers.
141  void addLiveOuts(const MachineBasicBlock &MBB);
142 
143  /// Adds all live-out registers of basic block \p MBB but skips pristine
144  /// registers.
145  void addLiveOutsNoPristines(const MachineBasicBlock &MBB);
146 
148 
149  const_iterator begin() const { return LiveRegs.begin(); }
150  const_iterator end() const { return LiveRegs.end(); }
151 
152  /// Prints the currently live registers to \p OS.
153  void print(raw_ostream &OS) const;
154 
155  /// Dumps the currently live registers to the debug output.
156  void dump() const;
157 
158 private:
159  /// Adds live-in registers from basic block \p MBB, taking associated
160  /// lane masks into consideration.
161  void addBlockLiveIns(const MachineBasicBlock &MBB);
162 
163  /// Adds pristine registers. Pristine registers are callee saved registers
164  /// that are unused in the function.
165  void addPristines(const MachineFunction &MF);
166 };
167 
169  LR.print(OS);
170  return OS;
171 }
172 
173 /// Computes registers live-in to \p MBB assuming all of its successors
174 /// live-in lists are up-to-date. Puts the result into the given LivePhysReg
175 /// instance \p LiveRegs.
176 void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB);
177 
178 /// Recomputes dead and kill flags in \p MBB.
180 
181 /// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB.
182 /// Does not add reserved registers.
183 void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
184 
185 /// Convenience function combining computeLiveIns() and addLiveIns().
186 void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
187  MachineBasicBlock &MBB);
188 
189 /// Convenience function for recomputing live-in's for \p MBB.
190 static inline void recomputeLiveIns(MachineBasicBlock &MBB) {
191  LivePhysRegs LPR;
192  MBB.clearLiveIns();
193  computeAndAddLiveIns(LPR, MBB);
194 }
195 
196 } // end namespace llvm
197 
198 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void dump() const
Dumps the currently live registers to the debug output.
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:250
unsigned Reg
LivePhysRegs()=default
Constructs an unitialized set. init() needs to be called to initialize it.
bool contains(MCPhysReg Reg) const
Returns true if register Reg is contained in the set.
Definition: LivePhysRegs.h:107
const_iterator begin() const
Definition: LivePhysRegs.h:149
bool empty() const
Returns true if the set is empty.
Definition: LivePhysRegs.h:77
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise. ...
Definition: SparseSet.h:236
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:286
bool empty() const
empty - Returns true if the set is empty.
Definition: SparseSet.h:184
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
unsigned const MachineRegisterInfo * MRI
typename DenseT::const_iterator const_iterator
Definition: SparseSet.h:173
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
void addLiveIns(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB.
LivePhysRegs & operator=(const LivePhysRegs &)=delete
void addUses(const MachineInstr &MI)
Add uses to the set.
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:67
MCRegAliasIterator enumerates all registers aliasing Reg.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void clearLiveIns()
Clear live in list.
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:156
RegisterSet::const_iterator const_iterator
Definition: LivePhysRegs.h:147
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCSubRegIterator enumerates all sub-registers of Reg.
void addLiveOutsNoPristines(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB but skips pristine registers.
const_iterator end() const
Definition: SparseSet.h:176
void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)
Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date...
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
MachineOperand class - Representation of each machine instruction operand.
const_iterator begin() const
Definition: SparseSet.h:175
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
LivePhysRegs(const TargetRegisterInfo &TRI)
Constructs and initializes an empty set.
Definition: LivePhysRegs.h:59
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
void print(raw_ostream &OS) const
Prints the currently live registers to OS.
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:64
void removeDefs(const MachineInstr &MI)
Remove defined registers and regmask kills from the set.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:49
const_iterator end() const
Definition: LivePhysRegs.h:150
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2033
void clear()
clear - Clears the set.
Definition: SparseSet.h:195
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void clear()
Clears the set.
Definition: LivePhysRegs.h:74
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand *>> *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in&#39;s for MBB.
Definition: LivePhysRegs.h:190
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:80
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
IRTranslator LLVM IR MI
void removeReg(MCPhysReg Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set...
Definition: LivePhysRegs.h:90
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand *>> &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.