/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/CodeGen/LiveVariables.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- 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 | | // This file implements the LiveVariables analysis pass. For each machine |
11 | | // instruction in the function, this pass calculates the set of registers that |
12 | | // are immediately dead after the instruction (i.e., the instruction calculates |
13 | | // the value, but it is never used) and the set of registers that are used by |
14 | | // the instruction, but are never used after the instruction (i.e., they are |
15 | | // killed). |
16 | | // |
17 | | // This class computes live variables using a sparse implementation based on |
18 | | // the machine code SSA form. This class computes live variable information for |
19 | | // each virtual and _register allocatable_ physical register in a function. It |
20 | | // uses the dominance properties of SSA form to efficiently compute live |
21 | | // variables for virtual registers, and assumes that physical registers are only |
22 | | // live within a single basic block (allowing it to do a single local analysis |
23 | | // to resolve physical register lifetimes in each basic block). If a physical |
24 | | // register is not register allocatable, it is not tracked. This is useful for |
25 | | // things like the stack pointer and condition codes. |
26 | | // |
27 | | //===----------------------------------------------------------------------===// |
28 | | |
29 | | #ifndef LLVM_CODEGEN_LIVEVARIABLES_H |
30 | | #define LLVM_CODEGEN_LIVEVARIABLES_H |
31 | | |
32 | | #include "llvm/ADT/DenseMap.h" |
33 | | #include "llvm/ADT/IndexedMap.h" |
34 | | #include "llvm/ADT/SmallSet.h" |
35 | | #include "llvm/ADT/SmallVector.h" |
36 | | #include "llvm/ADT/SparseBitVector.h" |
37 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
38 | | #include "llvm/CodeGen/MachineInstr.h" |
39 | | #include "llvm/Target/TargetRegisterInfo.h" |
40 | | |
41 | | namespace llvm { |
42 | | |
43 | | class MachineBasicBlock; |
44 | | class MachineRegisterInfo; |
45 | | |
46 | | class LiveVariables : public MachineFunctionPass { |
47 | | public: |
48 | | static char ID; // Pass identification, replacement for typeid |
49 | 33.0k | LiveVariables() : MachineFunctionPass(ID) { |
50 | 33.0k | initializeLiveVariablesPass(*PassRegistry::getPassRegistry()); |
51 | 33.0k | } |
52 | | |
53 | | /// VarInfo - This represents the regions where a virtual register is live in |
54 | | /// the program. We represent this with three different pieces of |
55 | | /// information: the set of blocks in which the instruction is live |
56 | | /// throughout, the set of blocks in which the instruction is actually used, |
57 | | /// and the set of non-phi instructions that are the last users of the value. |
58 | | /// |
59 | | /// In the common case where a value is defined and killed in the same block, |
60 | | /// There is one killing instruction, and AliveBlocks is empty. |
61 | | /// |
62 | | /// Otherwise, the value is live out of the block. If the value is live |
63 | | /// throughout any blocks, these blocks are listed in AliveBlocks. Blocks |
64 | | /// where the liveness range ends are not included in AliveBlocks, instead |
65 | | /// being captured by the Kills set. In these blocks, the value is live into |
66 | | /// the block (unless the value is defined and killed in the same block) and |
67 | | /// lives until the specified instruction. Note that there cannot ever be a |
68 | | /// value whose Kills set contains two instructions from the same basic block. |
69 | | /// |
70 | | /// PHI nodes complicate things a bit. If a PHI node is the last user of a |
71 | | /// value in one of its predecessor blocks, it is not listed in the kills set, |
72 | | /// but does include the predecessor block in the AliveBlocks set (unless that |
73 | | /// block also defines the value). This leads to the (perfectly sensical) |
74 | | /// situation where a value is defined in a block, and the last use is a phi |
75 | | /// node in the successor. In this case, AliveBlocks is empty (the value is |
76 | | /// not live across any blocks) and Kills is empty (phi nodes are not |
77 | | /// included). This is sensical because the value must be live to the end of |
78 | | /// the block, but is not live in any successor blocks. |
79 | | struct VarInfo { |
80 | | /// AliveBlocks - Set of blocks in which this value is alive completely |
81 | | /// through. This is a bit set which uses the basic block number as an |
82 | | /// index. |
83 | | /// |
84 | | SparseBitVector<> AliveBlocks; |
85 | | |
86 | | /// Kills - List of MachineInstruction's which are the last use of this |
87 | | /// virtual register (kill it) in their basic block. |
88 | | /// |
89 | | std::vector<MachineInstr*> Kills; |
90 | | |
91 | | /// removeKill - Delete a kill corresponding to the specified |
92 | | /// machine instruction. Returns true if there was a kill |
93 | | /// corresponding to this instruction, false otherwise. |
94 | 262k | bool removeKill(MachineInstr &MI) { |
95 | 262k | std::vector<MachineInstr *>::iterator I = find(Kills, &MI); |
96 | 262k | if (I == Kills.end()) |
97 | 557 | return false; |
98 | 262k | Kills.erase(I); |
99 | 262k | return true; |
100 | 262k | } |
101 | | |
102 | | /// findKill - Find a kill instruction in MBB. Return NULL if none is found. |
103 | | MachineInstr *findKill(const MachineBasicBlock *MBB) const; |
104 | | |
105 | | /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through |
106 | | /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in |
107 | | /// MBB, it is not considered live in. |
108 | | bool isLiveIn(const MachineBasicBlock &MBB, |
109 | | unsigned Reg, |
110 | | MachineRegisterInfo &MRI); |
111 | | |
112 | | void dump() const; |
113 | | }; |
114 | | |
115 | | private: |
116 | | /// VirtRegInfo - This list is a mapping from virtual register number to |
117 | | /// variable information. |
118 | | /// |
119 | | IndexedMap<VarInfo, VirtReg2IndexFunctor> VirtRegInfo; |
120 | | |
121 | | /// PHIJoins - list of virtual registers that are PHI joins. These registers |
122 | | /// may have multiple definitions, and they require special handling when |
123 | | /// building live intervals. |
124 | | SparseBitVector<> PHIJoins; |
125 | | |
126 | | private: // Intermediate data structures |
127 | | MachineFunction *MF; |
128 | | |
129 | | MachineRegisterInfo* MRI; |
130 | | |
131 | | const TargetRegisterInfo *TRI; |
132 | | |
133 | | // PhysRegInfo - Keep track of which instruction was the last def of a |
134 | | // physical register. This is a purely local property, because all physical |
135 | | // register references are presumed dead across basic blocks. |
136 | | std::vector<MachineInstr *> PhysRegDef; |
137 | | |
138 | | // PhysRegInfo - Keep track of which instruction was the last use of a |
139 | | // physical register. This is a purely local property, because all physical |
140 | | // register references are presumed dead across basic blocks. |
141 | | std::vector<MachineInstr *> PhysRegUse; |
142 | | |
143 | | std::vector<SmallVector<unsigned, 4>> PHIVarInfo; |
144 | | |
145 | | // DistanceMap - Keep track the distance of a MI from the start of the |
146 | | // current basic block. |
147 | | DenseMap<MachineInstr*, unsigned> DistanceMap; |
148 | | |
149 | | /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the |
150 | | /// uses. Pay special attention to the sub-register uses which may come below |
151 | | /// the last use of the whole register. |
152 | | bool HandlePhysRegKill(unsigned Reg, MachineInstr *MI); |
153 | | |
154 | | /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask. |
155 | | void HandleRegMask(const MachineOperand&); |
156 | | |
157 | | void HandlePhysRegUse(unsigned Reg, MachineInstr &MI); |
158 | | void HandlePhysRegDef(unsigned Reg, MachineInstr *MI, |
159 | | SmallVectorImpl<unsigned> &Defs); |
160 | | void UpdatePhysRegDefs(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs); |
161 | | |
162 | | /// FindLastRefOrPartRef - Return the last reference or partial reference of |
163 | | /// the specified register. |
164 | | MachineInstr *FindLastRefOrPartRef(unsigned Reg); |
165 | | |
166 | | /// FindLastPartialDef - Return the last partial def of the specified |
167 | | /// register. Also returns the sub-registers that're defined by the |
168 | | /// instruction. |
169 | | MachineInstr *FindLastPartialDef(unsigned Reg, |
170 | | SmallSet<unsigned,4> &PartDefRegs); |
171 | | |
172 | | /// analyzePHINodes - Gather information about the PHI nodes in here. In |
173 | | /// particular, we want to map the variable information of a virtual |
174 | | /// register which is used in a PHI node. We map that to the BB the vreg |
175 | | /// is coming from. |
176 | | void analyzePHINodes(const MachineFunction& Fn); |
177 | | |
178 | | void runOnInstr(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs); |
179 | | |
180 | | void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs); |
181 | | public: |
182 | | |
183 | | bool runOnMachineFunction(MachineFunction &MF) override; |
184 | | |
185 | | /// RegisterDefIsDead - Return true if the specified instruction defines the |
186 | | /// specified register, but that definition is dead. |
187 | | bool RegisterDefIsDead(MachineInstr &MI, unsigned Reg) const; |
188 | | |
189 | | //===--------------------------------------------------------------------===// |
190 | | // API to update live variable information |
191 | | |
192 | | /// replaceKillInstruction - Update register kill info by replacing a kill |
193 | | /// instruction with a new one. |
194 | | void replaceKillInstruction(unsigned Reg, MachineInstr &OldMI, |
195 | | MachineInstr &NewMI); |
196 | | |
197 | | /// addVirtualRegisterKilled - Add information about the fact that the |
198 | | /// specified register is killed after being used by the specified |
199 | | /// instruction. If AddIfNotFound is true, add a implicit operand if it's |
200 | | /// not found. |
201 | | void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr &MI, |
202 | 3.29M | bool AddIfNotFound = false) { |
203 | 3.29M | if (MI.addRegisterKilled(IncomingReg, TRI, AddIfNotFound)) |
204 | 3.29M | getVarInfo(IncomingReg).Kills.push_back(&MI); |
205 | 3.29M | } |
206 | | |
207 | | /// removeVirtualRegisterKilled - Remove the specified kill of the virtual |
208 | | /// register from the live variable information. Returns true if the |
209 | | /// variable was marked as killed by the specified instruction, |
210 | | /// false otherwise. |
211 | 1.75k | bool removeVirtualRegisterKilled(unsigned reg, MachineInstr &MI) { |
212 | 1.75k | if (!getVarInfo(reg).removeKill(MI)) |
213 | 0 | return false; |
214 | 1.75k | |
215 | 1.75k | bool Removed = false; |
216 | 4.46k | for (unsigned i = 0, e = MI.getNumOperands(); i != e4.46k ; ++i2.70k ) { |
217 | 4.46k | MachineOperand &MO = MI.getOperand(i); |
218 | 4.46k | if (MO.isReg() && 4.46k MO.isKill()4.29k && MO.getReg() == reg2.27k ) { |
219 | 1.75k | MO.setIsKill(false); |
220 | 1.75k | Removed = true; |
221 | 1.75k | break; |
222 | 1.75k | } |
223 | 4.46k | } |
224 | 1.75k | |
225 | 1.75k | assert(Removed && "Register is not used by this instruction!"); |
226 | 1.75k | (void)Removed; |
227 | 1.75k | return true; |
228 | 1.75k | } |
229 | | |
230 | | /// removeVirtualRegistersKilled - Remove all killed info for the specified |
231 | | /// instruction. |
232 | | void removeVirtualRegistersKilled(MachineInstr &MI); |
233 | | |
234 | | /// addVirtualRegisterDead - Add information about the fact that the specified |
235 | | /// register is dead after being used by the specified instruction. If |
236 | | /// AddIfNotFound is true, add a implicit operand if it's not found. |
237 | | void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr &MI, |
238 | 1 | bool AddIfNotFound = false) { |
239 | 1 | if (MI.addRegisterDead(IncomingReg, TRI, AddIfNotFound)) |
240 | 1 | getVarInfo(IncomingReg).Kills.push_back(&MI); |
241 | 1 | } |
242 | | |
243 | | /// removeVirtualRegisterDead - Remove the specified kill of the virtual |
244 | | /// register from the live variable information. Returns true if the |
245 | | /// variable was marked dead at the specified instruction, false |
246 | | /// otherwise. |
247 | 558 | bool removeVirtualRegisterDead(unsigned reg, MachineInstr &MI) { |
248 | 558 | if (!getVarInfo(reg).removeKill(MI)) |
249 | 557 | return false; |
250 | 558 | |
251 | 1 | bool Removed = false; |
252 | 1 | for (unsigned i = 0, e = MI.getNumOperands(); i != e1 ; ++i0 ) { |
253 | 1 | MachineOperand &MO = MI.getOperand(i); |
254 | 1 | if (MO.isReg() && 1 MO.isDef()1 && MO.getReg() == reg1 ) { |
255 | 1 | MO.setIsDead(false); |
256 | 1 | Removed = true; |
257 | 1 | break; |
258 | 1 | } |
259 | 1 | } |
260 | 1 | assert(Removed && "Register is not defined by this instruction!"); |
261 | 1 | (void)Removed; |
262 | 1 | return true; |
263 | 558 | } |
264 | | |
265 | | void getAnalysisUsage(AnalysisUsage &AU) const override; |
266 | | |
267 | 594k | void releaseMemory() override { |
268 | 594k | VirtRegInfo.clear(); |
269 | 594k | } |
270 | | |
271 | | /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL |
272 | | /// register. |
273 | | VarInfo &getVarInfo(unsigned RegIdx); |
274 | | |
275 | | void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, |
276 | | MachineBasicBlock *BB); |
277 | | void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, |
278 | | MachineBasicBlock *BB, |
279 | | std::vector<MachineBasicBlock*> &WorkList); |
280 | | void HandleVirtRegDef(unsigned reg, MachineInstr &MI); |
281 | | void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MachineInstr &MI); |
282 | | |
283 | 175k | bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB) { |
284 | 175k | return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI); |
285 | 175k | } |
286 | | |
287 | | /// isLiveOut - Determine if Reg is live out from MBB, when not considering |
288 | | /// PHI nodes. This means that Reg is either killed by a successor block or |
289 | | /// passed through one. |
290 | | bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB); |
291 | | |
292 | | /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All |
293 | | /// variables that are live out of DomBB and live into SuccBB will be marked |
294 | | /// as passing live through BB. This method assumes that the machine code is |
295 | | /// still in SSA form. |
296 | | void addNewBlock(MachineBasicBlock *BB, |
297 | | MachineBasicBlock *DomBB, |
298 | | MachineBasicBlock *SuccBB); |
299 | | |
300 | | /// isPHIJoin - Return true if Reg is a phi join register. |
301 | 0 | bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); } |
302 | | |
303 | | /// setPHIJoin - Mark Reg as a phi join register. |
304 | 936k | void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); } |
305 | | }; |
306 | | |
307 | | } // End llvm namespace |
308 | | |
309 | | #endif |