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