File: | build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/LiveVariables.cpp |
Warning: | line 415, column 5 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// | |||
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 LiveVariable 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 | #include "llvm/CodeGen/LiveVariables.h" | |||
29 | #include "llvm/ADT/DenseSet.h" | |||
30 | #include "llvm/ADT/DepthFirstIterator.h" | |||
31 | #include "llvm/ADT/STLExtras.h" | |||
32 | #include "llvm/ADT/SmallPtrSet.h" | |||
33 | #include "llvm/ADT/SmallSet.h" | |||
34 | #include "llvm/CodeGen/MachineInstr.h" | |||
35 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
36 | #include "llvm/CodeGen/Passes.h" | |||
37 | #include "llvm/Config/llvm-config.h" | |||
38 | #include "llvm/Support/Debug.h" | |||
39 | #include "llvm/Support/ErrorHandling.h" | |||
40 | #include "llvm/Support/raw_ostream.h" | |||
41 | #include <algorithm> | |||
42 | using namespace llvm; | |||
43 | ||||
44 | char LiveVariables::ID = 0; | |||
45 | char &llvm::LiveVariablesID = LiveVariables::ID; | |||
46 | INITIALIZE_PASS_BEGIN(LiveVariables, "livevars",static void *initializeLiveVariablesPassOnce(PassRegistry & Registry) { | |||
47 | "Live Variable Analysis", false, false)static void *initializeLiveVariablesPassOnce(PassRegistry & Registry) { | |||
48 | INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim)initializeUnreachableMachineBlockElimPass(Registry); | |||
49 | INITIALIZE_PASS_END(LiveVariables, "livevars",PassInfo *PI = new PassInfo( "Live Variable Analysis", "livevars" , &LiveVariables::ID, PassInfo::NormalCtor_t(callDefaultCtor <LiveVariables>), false, false); Registry.registerPass( *PI, true); return PI; } static llvm::once_flag InitializeLiveVariablesPassFlag ; void llvm::initializeLiveVariablesPass(PassRegistry &Registry ) { llvm::call_once(InitializeLiveVariablesPassFlag, initializeLiveVariablesPassOnce , std::ref(Registry)); } | |||
50 | "Live Variable Analysis", false, false)PassInfo *PI = new PassInfo( "Live Variable Analysis", "livevars" , &LiveVariables::ID, PassInfo::NormalCtor_t(callDefaultCtor <LiveVariables>), false, false); Registry.registerPass( *PI, true); return PI; } static llvm::once_flag InitializeLiveVariablesPassFlag ; void llvm::initializeLiveVariablesPass(PassRegistry &Registry ) { llvm::call_once(InitializeLiveVariablesPassFlag, initializeLiveVariablesPassOnce , std::ref(Registry)); } | |||
51 | ||||
52 | ||||
53 | void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { | |||
54 | AU.addRequiredID(UnreachableMachineBlockElimID); | |||
55 | AU.setPreservesAll(); | |||
56 | MachineFunctionPass::getAnalysisUsage(AU); | |||
57 | } | |||
58 | ||||
59 | MachineInstr * | |||
60 | LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const { | |||
61 | for (MachineInstr *MI : Kills) | |||
62 | if (MI->getParent() == MBB) | |||
63 | return MI; | |||
64 | return nullptr; | |||
65 | } | |||
66 | ||||
67 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |||
68 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void LiveVariables::VarInfo::dump() const { | |||
69 | dbgs() << " Alive in blocks: "; | |||
70 | for (unsigned AB : AliveBlocks) | |||
71 | dbgs() << AB << ", "; | |||
72 | dbgs() << "\n Killed by:"; | |||
73 | if (Kills.empty()) | |||
74 | dbgs() << " No instructions.\n"; | |||
75 | else { | |||
76 | for (unsigned i = 0, e = Kills.size(); i != e; ++i) | |||
77 | dbgs() << "\n #" << i << ": " << *Kills[i]; | |||
78 | dbgs() << "\n"; | |||
79 | } | |||
80 | } | |||
81 | #endif | |||
82 | ||||
83 | /// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. | |||
84 | LiveVariables::VarInfo &LiveVariables::getVarInfo(Register Reg) { | |||
85 | assert(Reg.isVirtual() && "getVarInfo: not a virtual register!")(static_cast <bool> (Reg.isVirtual() && "getVarInfo: not a virtual register!" ) ? void (0) : __assert_fail ("Reg.isVirtual() && \"getVarInfo: not a virtual register!\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 85, __extension__ __PRETTY_FUNCTION__ )); | |||
86 | VirtRegInfo.grow(Reg); | |||
87 | return VirtRegInfo[Reg]; | |||
88 | } | |||
89 | ||||
90 | void LiveVariables::MarkVirtRegAliveInBlock( | |||
91 | VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *MBB, | |||
92 | SmallVectorImpl<MachineBasicBlock *> &WorkList) { | |||
93 | unsigned BBNum = MBB->getNumber(); | |||
94 | ||||
95 | // Check to see if this basic block is one of the killing blocks. If so, | |||
96 | // remove it. | |||
97 | for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) | |||
98 | if (VRInfo.Kills[i]->getParent() == MBB) { | |||
99 | VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry | |||
100 | break; | |||
101 | } | |||
102 | ||||
103 | if (MBB == DefBlock) return; // Terminate recursion | |||
104 | ||||
105 | if (VRInfo.AliveBlocks.test(BBNum)) | |||
106 | return; // We already know the block is live | |||
107 | ||||
108 | // Mark the variable known alive in this bb | |||
109 | VRInfo.AliveBlocks.set(BBNum); | |||
110 | ||||
111 | assert(MBB != &MF->front() && "Can't find reaching def for virtreg")(static_cast <bool> (MBB != &MF->front() && "Can't find reaching def for virtreg") ? void (0) : __assert_fail ("MBB != &MF->front() && \"Can't find reaching def for virtreg\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 111, __extension__ __PRETTY_FUNCTION__ )); | |||
112 | WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend()); | |||
113 | } | |||
114 | ||||
115 | void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, | |||
116 | MachineBasicBlock *DefBlock, | |||
117 | MachineBasicBlock *MBB) { | |||
118 | SmallVector<MachineBasicBlock *, 16> WorkList; | |||
119 | MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList); | |||
120 | ||||
121 | while (!WorkList.empty()) { | |||
122 | MachineBasicBlock *Pred = WorkList.pop_back_val(); | |||
123 | MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList); | |||
124 | } | |||
125 | } | |||
126 | ||||
127 | void LiveVariables::HandleVirtRegUse(Register Reg, MachineBasicBlock *MBB, | |||
128 | MachineInstr &MI) { | |||
129 | assert(MRI->getVRegDef(Reg) && "Register use before def!")(static_cast <bool> (MRI->getVRegDef(Reg) && "Register use before def!") ? void (0) : __assert_fail ("MRI->getVRegDef(Reg) && \"Register use before def!\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 129, __extension__ __PRETTY_FUNCTION__ )); | |||
130 | ||||
131 | unsigned BBNum = MBB->getNumber(); | |||
132 | ||||
133 | VarInfo &VRInfo = getVarInfo(Reg); | |||
134 | ||||
135 | // Check to see if this basic block is already a kill block. | |||
136 | if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { | |||
137 | // Yes, this register is killed in this basic block already. Increase the | |||
138 | // live range by updating the kill instruction. | |||
139 | VRInfo.Kills.back() = &MI; | |||
140 | return; | |||
141 | } | |||
142 | ||||
143 | #ifndef NDEBUG | |||
144 | for (MachineInstr *Kill : VRInfo.Kills) | |||
145 | assert(Kill->getParent() != MBB && "entry should be at end!")(static_cast <bool> (Kill->getParent() != MBB && "entry should be at end!") ? void (0) : __assert_fail ("Kill->getParent() != MBB && \"entry should be at end!\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 145, __extension__ __PRETTY_FUNCTION__ )); | |||
146 | #endif | |||
147 | ||||
148 | // This situation can occur: | |||
149 | // | |||
150 | // ,------. | |||
151 | // | | | |||
152 | // | v | |||
153 | // | t2 = phi ... t1 ... | |||
154 | // | | | |||
155 | // | v | |||
156 | // | t1 = ... | |||
157 | // | ... = ... t1 ... | |||
158 | // | | | |||
159 | // `------' | |||
160 | // | |||
161 | // where there is a use in a PHI node that's a predecessor to the defining | |||
162 | // block. We don't want to mark all predecessors as having the value "alive" | |||
163 | // in this case. | |||
164 | if (MBB == MRI->getVRegDef(Reg)->getParent()) | |||
165 | return; | |||
166 | ||||
167 | // Add a new kill entry for this basic block. If this virtual register is | |||
168 | // already marked as alive in this basic block, that means it is alive in at | |||
169 | // least one of the successor blocks, it's not a kill. | |||
170 | if (!VRInfo.AliveBlocks.test(BBNum)) | |||
171 | VRInfo.Kills.push_back(&MI); | |||
172 | ||||
173 | // Update all dominating blocks to mark them as "known live". | |||
174 | for (MachineBasicBlock *Pred : MBB->predecessors()) | |||
175 | MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(Reg)->getParent(), Pred); | |||
176 | } | |||
177 | ||||
178 | void LiveVariables::HandleVirtRegDef(Register Reg, MachineInstr &MI) { | |||
179 | VarInfo &VRInfo = getVarInfo(Reg); | |||
180 | ||||
181 | if (VRInfo.AliveBlocks.empty()) | |||
182 | // If vr is not alive in any block, then defaults to dead. | |||
183 | VRInfo.Kills.push_back(&MI); | |||
184 | } | |||
185 | ||||
186 | /// FindLastPartialDef - Return the last partial def of the specified register. | |||
187 | /// Also returns the sub-registers that're defined by the instruction. | |||
188 | MachineInstr * | |||
189 | LiveVariables::FindLastPartialDef(Register Reg, | |||
190 | SmallSet<unsigned, 4> &PartDefRegs) { | |||
191 | unsigned LastDefReg = 0; | |||
192 | unsigned LastDefDist = 0; | |||
193 | MachineInstr *LastDef = nullptr; | |||
194 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { | |||
195 | unsigned SubReg = *SubRegs; | |||
196 | MachineInstr *Def = PhysRegDef[SubReg]; | |||
197 | if (!Def) | |||
198 | continue; | |||
199 | unsigned Dist = DistanceMap[Def]; | |||
200 | if (Dist > LastDefDist) { | |||
201 | LastDefReg = SubReg; | |||
202 | LastDef = Def; | |||
203 | LastDefDist = Dist; | |||
204 | } | |||
205 | } | |||
206 | ||||
207 | if (!LastDef) | |||
208 | return nullptr; | |||
209 | ||||
210 | PartDefRegs.insert(LastDefReg); | |||
211 | for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) { | |||
212 | MachineOperand &MO = LastDef->getOperand(i); | |||
213 | if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0) | |||
214 | continue; | |||
215 | Register DefReg = MO.getReg(); | |||
216 | if (TRI->isSubRegister(Reg, DefReg)) { | |||
217 | for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true); | |||
218 | SubRegs.isValid(); ++SubRegs) | |||
219 | PartDefRegs.insert(*SubRegs); | |||
220 | } | |||
221 | } | |||
222 | return LastDef; | |||
223 | } | |||
224 | ||||
225 | /// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add | |||
226 | /// implicit defs to a machine instruction if there was an earlier def of its | |||
227 | /// super-register. | |||
228 | void LiveVariables::HandlePhysRegUse(Register Reg, MachineInstr &MI) { | |||
229 | MachineInstr *LastDef = PhysRegDef[Reg]; | |||
230 | // If there was a previous use or a "full" def all is well. | |||
231 | if (!LastDef && !PhysRegUse[Reg]) { | |||
232 | // Otherwise, the last sub-register def implicitly defines this register. | |||
233 | // e.g. | |||
234 | // AH = | |||
235 | // AL = ... implicit-def EAX, implicit killed AH | |||
236 | // = AH | |||
237 | // ... | |||
238 | // = EAX | |||
239 | // All of the sub-registers must have been defined before the use of Reg! | |||
240 | SmallSet<unsigned, 4> PartDefRegs; | |||
241 | MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs); | |||
242 | // If LastPartialDef is NULL, it must be using a livein register. | |||
243 | if (LastPartialDef) { | |||
244 | LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, | |||
245 | true/*IsImp*/)); | |||
246 | PhysRegDef[Reg] = LastPartialDef; | |||
247 | SmallSet<unsigned, 8> Processed; | |||
248 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { | |||
249 | unsigned SubReg = *SubRegs; | |||
250 | if (Processed.count(SubReg)) | |||
251 | continue; | |||
252 | if (PartDefRegs.count(SubReg)) | |||
253 | continue; | |||
254 | // This part of Reg was defined before the last partial def. It's killed | |||
255 | // here. | |||
256 | LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, | |||
257 | false/*IsDef*/, | |||
258 | true/*IsImp*/)); | |||
259 | PhysRegDef[SubReg] = LastPartialDef; | |||
260 | for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS) | |||
261 | Processed.insert(*SS); | |||
262 | } | |||
263 | } | |||
264 | } else if (LastDef && !PhysRegUse[Reg] && | |||
265 | !LastDef->findRegisterDefOperand(Reg)) | |||
266 | // Last def defines the super register, add an implicit def of reg. | |||
267 | LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, | |||
268 | true/*IsImp*/)); | |||
269 | ||||
270 | // Remember this use. | |||
271 | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); | |||
272 | SubRegs.isValid(); ++SubRegs) | |||
273 | PhysRegUse[*SubRegs] = &MI; | |||
274 | } | |||
275 | ||||
276 | /// FindLastRefOrPartRef - Return the last reference or partial reference of | |||
277 | /// the specified register. | |||
278 | MachineInstr *LiveVariables::FindLastRefOrPartRef(Register Reg) { | |||
279 | MachineInstr *LastDef = PhysRegDef[Reg]; | |||
280 | MachineInstr *LastUse = PhysRegUse[Reg]; | |||
281 | if (!LastDef && !LastUse) | |||
282 | return nullptr; | |||
283 | ||||
284 | MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; | |||
285 | unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; | |||
286 | unsigned LastPartDefDist = 0; | |||
287 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { | |||
288 | unsigned SubReg = *SubRegs; | |||
289 | MachineInstr *Def = PhysRegDef[SubReg]; | |||
290 | if (Def && Def != LastDef) { | |||
291 | // There was a def of this sub-register in between. This is a partial | |||
292 | // def, keep track of the last one. | |||
293 | unsigned Dist = DistanceMap[Def]; | |||
294 | if (Dist > LastPartDefDist) | |||
295 | LastPartDefDist = Dist; | |||
296 | } else if (MachineInstr *Use = PhysRegUse[SubReg]) { | |||
297 | unsigned Dist = DistanceMap[Use]; | |||
298 | if (Dist > LastRefOrPartRefDist) { | |||
299 | LastRefOrPartRefDist = Dist; | |||
300 | LastRefOrPartRef = Use; | |||
301 | } | |||
302 | } | |||
303 | } | |||
304 | ||||
305 | return LastRefOrPartRef; | |||
306 | } | |||
307 | ||||
308 | bool LiveVariables::HandlePhysRegKill(Register Reg, MachineInstr *MI) { | |||
309 | MachineInstr *LastDef = PhysRegDef[Reg]; | |||
310 | MachineInstr *LastUse = PhysRegUse[Reg]; | |||
311 | if (!LastDef && !LastUse) | |||
312 | return false; | |||
313 | ||||
314 | MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; | |||
315 | unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; | |||
316 | // The whole register is used. | |||
317 | // AL = | |||
318 | // AH = | |||
319 | // | |||
320 | // = AX | |||
321 | // = AL, implicit killed AX | |||
322 | // AX = | |||
323 | // | |||
324 | // Or whole register is defined, but not used at all. | |||
325 | // dead AX = | |||
326 | // ... | |||
327 | // AX = | |||
328 | // | |||
329 | // Or whole register is defined, but only partly used. | |||
330 | // dead AX = implicit-def AL | |||
331 | // = killed AL | |||
332 | // AX = | |||
333 | MachineInstr *LastPartDef = nullptr; | |||
334 | unsigned LastPartDefDist = 0; | |||
335 | SmallSet<unsigned, 8> PartUses; | |||
336 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { | |||
337 | unsigned SubReg = *SubRegs; | |||
338 | MachineInstr *Def = PhysRegDef[SubReg]; | |||
339 | if (Def && Def != LastDef) { | |||
340 | // There was a def of this sub-register in between. This is a partial | |||
341 | // def, keep track of the last one. | |||
342 | unsigned Dist = DistanceMap[Def]; | |||
343 | if (Dist > LastPartDefDist) { | |||
344 | LastPartDefDist = Dist; | |||
345 | LastPartDef = Def; | |||
346 | } | |||
347 | continue; | |||
348 | } | |||
349 | if (MachineInstr *Use = PhysRegUse[SubReg]) { | |||
350 | for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid(); | |||
351 | ++SS) | |||
352 | PartUses.insert(*SS); | |||
353 | unsigned Dist = DistanceMap[Use]; | |||
354 | if (Dist > LastRefOrPartRefDist) { | |||
355 | LastRefOrPartRefDist = Dist; | |||
356 | LastRefOrPartRef = Use; | |||
357 | } | |||
358 | } | |||
359 | } | |||
360 | ||||
361 | if (!PhysRegUse[Reg]) { | |||
362 | // Partial uses. Mark register def dead and add implicit def of | |||
363 | // sub-registers which are used. | |||
364 | // dead EAX = op implicit-def AL | |||
365 | // That is, EAX def is dead but AL def extends pass it. | |||
366 | PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); | |||
367 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { | |||
368 | unsigned SubReg = *SubRegs; | |||
369 | if (!PartUses.count(SubReg)) | |||
370 | continue; | |||
371 | bool NeedDef = true; | |||
372 | if (PhysRegDef[Reg] == PhysRegDef[SubReg]) { | |||
373 | MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg); | |||
374 | if (MO) { | |||
375 | NeedDef = false; | |||
376 | assert(!MO->isDead())(static_cast <bool> (!MO->isDead()) ? void (0) : __assert_fail ("!MO->isDead()", "llvm/lib/CodeGen/LiveVariables.cpp", 376 , __extension__ __PRETTY_FUNCTION__)); | |||
377 | } | |||
378 | } | |||
379 | if (NeedDef) | |||
380 | PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, | |||
381 | true/*IsDef*/, true/*IsImp*/)); | |||
382 | MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg); | |||
383 | if (LastSubRef) | |||
384 | LastSubRef->addRegisterKilled(SubReg, TRI, true); | |||
385 | else { | |||
386 | LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); | |||
387 | for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); | |||
388 | SS.isValid(); ++SS) | |||
389 | PhysRegUse[*SS] = LastRefOrPartRef; | |||
390 | } | |||
391 | for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS) | |||
392 | PartUses.erase(*SS); | |||
393 | } | |||
394 | } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { | |||
395 | if (LastPartDef) | |||
396 | // The last partial def kills the register. | |||
397 | LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, | |||
398 | true/*IsImp*/, true/*IsKill*/)); | |||
399 | else { | |||
400 | MachineOperand *MO = | |||
401 | LastRefOrPartRef->findRegisterDefOperand(Reg, false, false, TRI); | |||
402 | bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg; | |||
403 | // If the last reference is the last def, then it's not used at all. | |||
404 | // That is, unless we are currently processing the last reference itself. | |||
405 | LastRefOrPartRef->addRegisterDead(Reg, TRI, true); | |||
406 | if (NeedEC) { | |||
407 | // If we are adding a subreg def and the superreg def is marked early | |||
408 | // clobber, add an early clobber marker to the subreg def. | |||
409 | MO = LastRefOrPartRef->findRegisterDefOperand(Reg); | |||
410 | if (MO) | |||
411 | MO->setIsEarlyClobber(); | |||
412 | } | |||
413 | } | |||
414 | } else | |||
415 | LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); | |||
| ||||
416 | return true; | |||
417 | } | |||
418 | ||||
419 | void LiveVariables::HandleRegMask(const MachineOperand &MO) { | |||
420 | // Call HandlePhysRegKill() for all live registers clobbered by Mask. | |||
421 | // Clobbered registers are always dead, sp there is no need to use | |||
422 | // HandlePhysRegDef(). | |||
423 | for (unsigned Reg = 1, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg) { | |||
424 | // Skip dead regs. | |||
425 | if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) | |||
426 | continue; | |||
427 | // Skip mask-preserved regs. | |||
428 | if (!MO.clobbersPhysReg(Reg)) | |||
429 | continue; | |||
430 | // Kill the largest clobbered super-register. | |||
431 | // This avoids needless implicit operands. | |||
432 | unsigned Super = Reg; | |||
433 | for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) | |||
434 | if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR)) | |||
435 | Super = *SR; | |||
436 | HandlePhysRegKill(Super, nullptr); | |||
437 | } | |||
438 | } | |||
439 | ||||
440 | void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI, | |||
441 | SmallVectorImpl<unsigned> &Defs) { | |||
442 | // What parts of the register are previously defined? | |||
443 | SmallSet<unsigned, 32> Live; | |||
444 | if (PhysRegDef[Reg] || PhysRegUse[Reg]) { | |||
445 | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); | |||
446 | SubRegs.isValid(); ++SubRegs) | |||
447 | Live.insert(*SubRegs); | |||
448 | } else { | |||
449 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { | |||
450 | unsigned SubReg = *SubRegs; | |||
451 | // If a register isn't itself defined, but all parts that make up of it | |||
452 | // are defined, then consider it also defined. | |||
453 | // e.g. | |||
454 | // AL = | |||
455 | // AH = | |||
456 | // = AX | |||
457 | if (Live.count(SubReg)) | |||
458 | continue; | |||
459 | if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { | |||
460 | for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); | |||
461 | SS.isValid(); ++SS) | |||
462 | Live.insert(*SS); | |||
463 | } | |||
464 | } | |||
465 | } | |||
466 | ||||
467 | // Start from the largest piece, find the last time any part of the register | |||
468 | // is referenced. | |||
469 | HandlePhysRegKill(Reg, MI); | |||
470 | // Only some of the sub-registers are used. | |||
471 | for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { | |||
472 | unsigned SubReg = *SubRegs; | |||
473 | if (!Live.count(SubReg)) | |||
474 | // Skip if this sub-register isn't defined. | |||
475 | continue; | |||
476 | HandlePhysRegKill(SubReg, MI); | |||
477 | } | |||
478 | ||||
479 | if (MI) | |||
480 | Defs.push_back(Reg); // Remember this def. | |||
481 | } | |||
482 | ||||
483 | void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI, | |||
484 | SmallVectorImpl<unsigned> &Defs) { | |||
485 | while (!Defs.empty()) { | |||
486 | Register Reg = Defs.pop_back_val(); | |||
487 | for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); | |||
488 | SubRegs.isValid(); ++SubRegs) { | |||
489 | unsigned SubReg = *SubRegs; | |||
490 | PhysRegDef[SubReg] = &MI; | |||
491 | PhysRegUse[SubReg] = nullptr; | |||
492 | } | |||
493 | } | |||
494 | } | |||
495 | ||||
496 | void LiveVariables::runOnInstr(MachineInstr &MI, | |||
497 | SmallVectorImpl<unsigned> &Defs) { | |||
498 | assert(!MI.isDebugOrPseudoInstr())(static_cast <bool> (!MI.isDebugOrPseudoInstr()) ? void (0) : __assert_fail ("!MI.isDebugOrPseudoInstr()", "llvm/lib/CodeGen/LiveVariables.cpp" , 498, __extension__ __PRETTY_FUNCTION__)); | |||
499 | // Process all of the operands of the instruction... | |||
500 | unsigned NumOperandsToProcess = MI.getNumOperands(); | |||
501 | ||||
502 | // Unless it is a PHI node. In this case, ONLY process the DEF, not any | |||
503 | // of the uses. They will be handled in other basic blocks. | |||
504 | if (MI.isPHI()) | |||
505 | NumOperandsToProcess = 1; | |||
506 | ||||
507 | // Clear kill and dead markers. LV will recompute them. | |||
508 | SmallVector<unsigned, 4> UseRegs; | |||
509 | SmallVector<unsigned, 4> DefRegs; | |||
510 | SmallVector<unsigned, 1> RegMasks; | |||
511 | for (unsigned i = 0; i != NumOperandsToProcess; ++i) { | |||
512 | MachineOperand &MO = MI.getOperand(i); | |||
513 | if (MO.isRegMask()) { | |||
514 | RegMasks.push_back(i); | |||
515 | continue; | |||
516 | } | |||
517 | if (!MO.isReg() || MO.getReg() == 0) | |||
518 | continue; | |||
519 | Register MOReg = MO.getReg(); | |||
520 | if (MO.isUse()) { | |||
521 | if (!(Register::isPhysicalRegister(MOReg) && MRI->isReserved(MOReg))) | |||
522 | MO.setIsKill(false); | |||
523 | if (MO.readsReg()) | |||
524 | UseRegs.push_back(MOReg); | |||
525 | } else { | |||
526 | assert(MO.isDef())(static_cast <bool> (MO.isDef()) ? void (0) : __assert_fail ("MO.isDef()", "llvm/lib/CodeGen/LiveVariables.cpp", 526, __extension__ __PRETTY_FUNCTION__)); | |||
527 | // FIXME: We should not remove any dead flags. However the MIPS RDDSP | |||
528 | // instruction needs it at the moment: http://llvm.org/PR27116. | |||
529 | if (Register::isPhysicalRegister(MOReg) && !MRI->isReserved(MOReg)) | |||
530 | MO.setIsDead(false); | |||
531 | DefRegs.push_back(MOReg); | |||
532 | } | |||
533 | } | |||
534 | ||||
535 | MachineBasicBlock *MBB = MI.getParent(); | |||
536 | // Process all uses. | |||
537 | for (unsigned MOReg : UseRegs) { | |||
538 | if (Register::isVirtualRegister(MOReg)) | |||
539 | HandleVirtRegUse(MOReg, MBB, MI); | |||
540 | else if (!MRI->isReserved(MOReg)) | |||
541 | HandlePhysRegUse(MOReg, MI); | |||
542 | } | |||
543 | ||||
544 | // Process all masked registers. (Call clobbers). | |||
545 | for (unsigned Mask : RegMasks) | |||
546 | HandleRegMask(MI.getOperand(Mask)); | |||
547 | ||||
548 | // Process all defs. | |||
549 | for (unsigned MOReg : DefRegs) { | |||
550 | if (Register::isVirtualRegister(MOReg)) | |||
551 | HandleVirtRegDef(MOReg, MI); | |||
552 | else if (!MRI->isReserved(MOReg)) | |||
553 | HandlePhysRegDef(MOReg, &MI, Defs); | |||
554 | } | |||
555 | UpdatePhysRegDefs(MI, Defs); | |||
556 | } | |||
557 | ||||
558 | void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) { | |||
559 | // Mark live-in registers as live-in. | |||
560 | SmallVector<unsigned, 4> Defs; | |||
561 | for (const auto &LI : MBB->liveins()) { | |||
562 | assert(Register::isPhysicalRegister(LI.PhysReg) &&(static_cast <bool> (Register::isPhysicalRegister(LI.PhysReg ) && "Cannot have a live-in virtual register!") ? void (0) : __assert_fail ("Register::isPhysicalRegister(LI.PhysReg) && \"Cannot have a live-in virtual register!\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 563, __extension__ __PRETTY_FUNCTION__ )) | |||
563 | "Cannot have a live-in virtual register!")(static_cast <bool> (Register::isPhysicalRegister(LI.PhysReg ) && "Cannot have a live-in virtual register!") ? void (0) : __assert_fail ("Register::isPhysicalRegister(LI.PhysReg) && \"Cannot have a live-in virtual register!\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 563, __extension__ __PRETTY_FUNCTION__ )); | |||
564 | HandlePhysRegDef(LI.PhysReg, nullptr, Defs); | |||
565 | } | |||
566 | ||||
567 | // Loop over all of the instructions, processing them. | |||
568 | DistanceMap.clear(); | |||
569 | unsigned Dist = 0; | |||
570 | for (MachineInstr &MI : *MBB) { | |||
571 | if (MI.isDebugOrPseudoInstr()) | |||
572 | continue; | |||
573 | DistanceMap.insert(std::make_pair(&MI, Dist++)); | |||
574 | ||||
575 | runOnInstr(MI, Defs); | |||
576 | } | |||
577 | ||||
578 | // Handle any virtual assignments from PHI nodes which might be at the | |||
579 | // bottom of this basic block. We check all of our successor blocks to see | |||
580 | // if they have PHI nodes, and if so, we simulate an assignment at the end | |||
581 | // of the current block. | |||
582 | if (!PHIVarInfo[MBB->getNumber()].empty()) { | |||
583 | SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()]; | |||
584 | ||||
585 | for (unsigned I : VarInfoVec) | |||
586 | // Mark it alive only in the block we are representing. | |||
587 | MarkVirtRegAliveInBlock(getVarInfo(I), MRI->getVRegDef(I)->getParent(), | |||
588 | MBB); | |||
589 | } | |||
590 | ||||
591 | // MachineCSE may CSE instructions which write to non-allocatable physical | |||
592 | // registers across MBBs. Remember if any reserved register is liveout. | |||
593 | SmallSet<unsigned, 4> LiveOuts; | |||
594 | for (const MachineBasicBlock *SuccMBB : MBB->successors()) { | |||
595 | if (SuccMBB->isEHPad()) | |||
596 | continue; | |||
597 | for (const auto &LI : SuccMBB->liveins()) { | |||
598 | if (!TRI->isInAllocatableClass(LI.PhysReg)) | |||
599 | // Ignore other live-ins, e.g. those that are live into landing pads. | |||
600 | LiveOuts.insert(LI.PhysReg); | |||
601 | } | |||
602 | } | |||
603 | ||||
604 | // Loop over PhysRegDef / PhysRegUse, killing any registers that are | |||
605 | // available at the end of the basic block. | |||
606 | for (unsigned i = 0; i != NumRegs; ++i) | |||
607 | if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i)) | |||
608 | HandlePhysRegDef(i, nullptr, Defs); | |||
609 | } | |||
610 | ||||
611 | bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { | |||
612 | MF = &mf; | |||
613 | MRI = &mf.getRegInfo(); | |||
614 | TRI = MF->getSubtarget().getRegisterInfo(); | |||
615 | ||||
616 | const unsigned NumRegs = TRI->getNumRegs(); | |||
617 | PhysRegDef.assign(NumRegs, nullptr); | |||
618 | PhysRegUse.assign(NumRegs, nullptr); | |||
619 | PHIVarInfo.resize(MF->getNumBlockIDs()); | |||
620 | PHIJoins.clear(); | |||
621 | ||||
622 | // FIXME: LiveIntervals will be updated to remove its dependence on | |||
623 | // LiveVariables to improve compilation time and eliminate bizarre pass | |||
624 | // dependencies. Until then, we can't change much in -O0. | |||
625 | if (!MRI->isSSA()) | |||
| ||||
626 | report_fatal_error("regalloc=... not currently supported with -O0"); | |||
627 | ||||
628 | analyzePHINodes(mf); | |||
629 | ||||
630 | // Calculate live variable information in depth first order on the CFG of the | |||
631 | // function. This guarantees that we will see the definition of a virtual | |||
632 | // register before its uses due to dominance properties of SSA (except for PHI | |||
633 | // nodes, which are treated as a special case). | |||
634 | MachineBasicBlock *Entry = &MF->front(); | |||
635 | df_iterator_default_set<MachineBasicBlock*,16> Visited; | |||
636 | ||||
637 | for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) { | |||
638 | runOnBlock(MBB, NumRegs); | |||
639 | ||||
640 | PhysRegDef.assign(NumRegs, nullptr); | |||
641 | PhysRegUse.assign(NumRegs, nullptr); | |||
642 | } | |||
643 | ||||
644 | // Convert and transfer the dead / killed information we have gathered into | |||
645 | // VirtRegInfo onto MI's. | |||
646 | for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) { | |||
647 | const Register Reg = Register::index2VirtReg(i); | |||
648 | for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j) | |||
649 | if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg)) | |||
650 | VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI); | |||
651 | else | |||
652 | VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI); | |||
653 | } | |||
654 | ||||
655 | // Check to make sure there are no unreachable blocks in the MC CFG for the | |||
656 | // function. If so, it is due to a bug in the instruction selector or some | |||
657 | // other part of the code generator if this happens. | |||
658 | #ifndef NDEBUG | |||
659 | for (const MachineBasicBlock &MBB : *MF) | |||
660 | assert(Visited.contains(&MBB) && "unreachable basic block found")(static_cast <bool> (Visited.contains(&MBB) && "unreachable basic block found") ? void (0) : __assert_fail ( "Visited.contains(&MBB) && \"unreachable basic block found\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 660, __extension__ __PRETTY_FUNCTION__ )); | |||
661 | #endif | |||
662 | ||||
663 | PhysRegDef.clear(); | |||
664 | PhysRegUse.clear(); | |||
665 | PHIVarInfo.clear(); | |||
666 | ||||
667 | return false; | |||
668 | } | |||
669 | ||||
670 | void LiveVariables::recomputeForSingleDefVirtReg(Register Reg) { | |||
671 | assert(Reg.isVirtual())(static_cast <bool> (Reg.isVirtual()) ? void (0) : __assert_fail ("Reg.isVirtual()", "llvm/lib/CodeGen/LiveVariables.cpp", 671 , __extension__ __PRETTY_FUNCTION__)); | |||
672 | ||||
673 | VarInfo &VI = getVarInfo(Reg); | |||
674 | VI.AliveBlocks.clear(); | |||
675 | VI.Kills.clear(); | |||
676 | ||||
677 | MachineInstr &DefMI = *MRI->getUniqueVRegDef(Reg); | |||
678 | MachineBasicBlock &DefBB = *DefMI.getParent(); | |||
679 | ||||
680 | // Handle the case where all uses have been removed. | |||
681 | if (MRI->use_nodbg_empty(Reg)) { | |||
682 | VI.Kills.push_back(&DefMI); | |||
683 | DefMI.addRegisterDead(Reg, nullptr); | |||
684 | return; | |||
685 | } | |||
686 | DefMI.clearRegisterDeads(Reg); | |||
687 | ||||
688 | // Initialize a worklist of BBs that Reg is live-to-end of. (Here | |||
689 | // "live-to-end" means Reg is live at the end of a block even if it is only | |||
690 | // live because of phi uses in a successor. This is different from isLiveOut() | |||
691 | // which does not consider phi uses.) | |||
692 | SmallVector<MachineBasicBlock *> LiveToEndBlocks; | |||
693 | SparseBitVector<> UseBlocks; | |||
694 | for (auto &UseMO : MRI->use_nodbg_operands(Reg)) { | |||
695 | UseMO.setIsKill(false); | |||
696 | MachineInstr &UseMI = *UseMO.getParent(); | |||
697 | MachineBasicBlock &UseBB = *UseMI.getParent(); | |||
698 | UseBlocks.set(UseBB.getNumber()); | |||
699 | if (UseMI.isPHI()) { | |||
700 | // If Reg is used in a phi then it is live-to-end of the corresponding | |||
701 | // predecessor. | |||
702 | unsigned Idx = UseMI.getOperandNo(&UseMO); | |||
703 | LiveToEndBlocks.push_back(UseMI.getOperand(Idx + 1).getMBB()); | |||
704 | } else if (&UseBB == &DefBB) { | |||
705 | // A non-phi use in the same BB as the single def must come after the def. | |||
706 | } else { | |||
707 | // Otherwise Reg must be live-to-end of all predecessors. | |||
708 | LiveToEndBlocks.append(UseBB.pred_begin(), UseBB.pred_end()); | |||
709 | } | |||
710 | } | |||
711 | ||||
712 | // Iterate over the worklist adding blocks to AliveBlocks. | |||
713 | bool LiveToEndOfDefBB = false; | |||
714 | while (!LiveToEndBlocks.empty()) { | |||
715 | MachineBasicBlock &BB = *LiveToEndBlocks.pop_back_val(); | |||
716 | if (&BB == &DefBB) { | |||
717 | LiveToEndOfDefBB = true; | |||
718 | continue; | |||
719 | } | |||
720 | if (VI.AliveBlocks.test(BB.getNumber())) | |||
721 | continue; | |||
722 | VI.AliveBlocks.set(BB.getNumber()); | |||
723 | LiveToEndBlocks.append(BB.pred_begin(), BB.pred_end()); | |||
724 | } | |||
725 | ||||
726 | // Recompute kill flags. For each block in which Reg is used but is not | |||
727 | // live-through, find the last instruction that uses Reg. Ignore phi nodes | |||
728 | // because they should not be included in Kills. | |||
729 | for (unsigned UseBBNum : UseBlocks) { | |||
730 | if (VI.AliveBlocks.test(UseBBNum)) | |||
731 | continue; | |||
732 | MachineBasicBlock &UseBB = *MF->getBlockNumbered(UseBBNum); | |||
733 | if (&UseBB == &DefBB && LiveToEndOfDefBB) | |||
734 | continue; | |||
735 | for (auto &MI : reverse(UseBB)) { | |||
736 | if (MI.isDebugOrPseudoInstr()) | |||
737 | continue; | |||
738 | if (MI.isPHI()) | |||
739 | break; | |||
740 | if (MI.readsRegister(Reg)) { | |||
741 | assert(!MI.killsRegister(Reg))(static_cast <bool> (!MI.killsRegister(Reg)) ? void (0) : __assert_fail ("!MI.killsRegister(Reg)", "llvm/lib/CodeGen/LiveVariables.cpp" , 741, __extension__ __PRETTY_FUNCTION__)); | |||
742 | MI.addRegisterKilled(Reg, nullptr); | |||
743 | VI.Kills.push_back(&MI); | |||
744 | break; | |||
745 | } | |||
746 | } | |||
747 | } | |||
748 | } | |||
749 | ||||
750 | /// replaceKillInstruction - Update register kill info by replacing a kill | |||
751 | /// instruction with a new one. | |||
752 | void LiveVariables::replaceKillInstruction(Register Reg, MachineInstr &OldMI, | |||
753 | MachineInstr &NewMI) { | |||
754 | VarInfo &VI = getVarInfo(Reg); | |||
755 | std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI); | |||
756 | } | |||
757 | ||||
758 | /// removeVirtualRegistersKilled - Remove all killed info for the specified | |||
759 | /// instruction. | |||
760 | void LiveVariables::removeVirtualRegistersKilled(MachineInstr &MI) { | |||
761 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { | |||
762 | MachineOperand &MO = MI.getOperand(i); | |||
763 | if (MO.isReg() && MO.isKill()) { | |||
764 | MO.setIsKill(false); | |||
765 | Register Reg = MO.getReg(); | |||
766 | if (Register::isVirtualRegister(Reg)) { | |||
767 | bool removed = getVarInfo(Reg).removeKill(MI); | |||
768 | assert(removed && "kill not in register's VarInfo?")(static_cast <bool> (removed && "kill not in register's VarInfo?" ) ? void (0) : __assert_fail ("removed && \"kill not in register's VarInfo?\"" , "llvm/lib/CodeGen/LiveVariables.cpp", 768, __extension__ __PRETTY_FUNCTION__ )); | |||
769 | (void)removed; | |||
770 | } | |||
771 | } | |||
772 | } | |||
773 | } | |||
774 | ||||
775 | /// analyzePHINodes - Gather information about the PHI nodes in here. In | |||
776 | /// particular, we want to map the variable information of a virtual register | |||
777 | /// which is used in a PHI node. We map that to the BB the vreg is coming from. | |||
778 | /// | |||
779 | void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { | |||
780 | for (const auto &MBB : Fn) | |||
781 | for (const auto &BBI : MBB) { | |||
782 | if (!BBI.isPHI()) | |||
783 | break; | |||
784 | for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) | |||
785 | if (BBI.getOperand(i).readsReg()) | |||
786 | PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()] | |||
787 | .push_back(BBI.getOperand(i).getReg()); | |||
788 | } | |||
789 | } | |||
790 | ||||
791 | bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB, | |||
792 | Register Reg, MachineRegisterInfo &MRI) { | |||
793 | unsigned Num = MBB.getNumber(); | |||
794 | ||||
795 | // Reg is live-through. | |||
796 | if (AliveBlocks.test(Num)) | |||
797 | return true; | |||
798 | ||||
799 | // Registers defined in MBB cannot be live in. | |||
800 | const MachineInstr *Def = MRI.getVRegDef(Reg); | |||
801 | if (Def && Def->getParent() == &MBB) | |||
802 | return false; | |||
803 | ||||
804 | // Reg was not defined in MBB, was it killed here? | |||
805 | return findKill(&MBB); | |||
806 | } | |||
807 | ||||
808 | bool LiveVariables::isLiveOut(Register Reg, const MachineBasicBlock &MBB) { | |||
809 | LiveVariables::VarInfo &VI = getVarInfo(Reg); | |||
810 | ||||
811 | SmallPtrSet<const MachineBasicBlock *, 8> Kills; | |||
812 | for (MachineInstr *MI : VI.Kills) | |||
813 | Kills.insert(MI->getParent()); | |||
814 | ||||
815 | // Loop over all of the successors of the basic block, checking to see if | |||
816 | // the value is either live in the block, or if it is killed in the block. | |||
817 | for (const MachineBasicBlock *SuccMBB : MBB.successors()) { | |||
818 | // Is it alive in this successor? | |||
819 | unsigned SuccIdx = SuccMBB->getNumber(); | |||
820 | if (VI.AliveBlocks.test(SuccIdx)) | |||
821 | return true; | |||
822 | // Or is it live because there is a use in a successor that kills it? | |||
823 | if (Kills.count(SuccMBB)) | |||
824 | return true; | |||
825 | } | |||
826 | ||||
827 | return false; | |||
828 | } | |||
829 | ||||
830 | /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All | |||
831 | /// variables that are live out of DomBB will be marked as passing live through | |||
832 | /// BB. | |||
833 | void LiveVariables::addNewBlock(MachineBasicBlock *BB, | |||
834 | MachineBasicBlock *DomBB, | |||
835 | MachineBasicBlock *SuccBB) { | |||
836 | const unsigned NumNew = BB->getNumber(); | |||
837 | ||||
838 | DenseSet<unsigned> Defs, Kills; | |||
839 | ||||
840 | MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end(); | |||
841 | for (; BBI != BBE && BBI->isPHI(); ++BBI) { | |||
842 | // Record the def of the PHI node. | |||
843 | Defs.insert(BBI->getOperand(0).getReg()); | |||
844 | ||||
845 | // All registers used by PHI nodes in SuccBB must be live through BB. | |||
846 | for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) | |||
847 | if (BBI->getOperand(i+1).getMBB() == BB) | |||
848 | getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew); | |||
849 | } | |||
850 | ||||
851 | // Record all vreg defs and kills of all instructions in SuccBB. | |||
852 | for (; BBI != BBE; ++BBI) { | |||
853 | for (const MachineOperand &Op : BBI->operands()) { | |||
854 | if (Op.isReg() && Register::isVirtualRegister(Op.getReg())) { | |||
855 | if (Op.isDef()) | |||
856 | Defs.insert(Op.getReg()); | |||
857 | else if (Op.isKill()) | |||
858 | Kills.insert(Op.getReg()); | |||
859 | } | |||
860 | } | |||
861 | } | |||
862 | ||||
863 | // Update info for all live variables | |||
864 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { | |||
865 | Register Reg = Register::index2VirtReg(i); | |||
866 | ||||
867 | // If the Defs is defined in the successor it can't be live in BB. | |||
868 | if (Defs.count(Reg)) | |||
869 | continue; | |||
870 | ||||
871 | // If the register is either killed in or live through SuccBB it's also live | |||
872 | // through BB. | |||
873 | VarInfo &VI = getVarInfo(Reg); | |||
874 | if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber())) | |||
875 | VI.AliveBlocks.set(NumNew); | |||
876 | } | |||
877 | } | |||
878 | ||||
879 | /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All | |||
880 | /// variables that are live out of DomBB will be marked as passing live through | |||
881 | /// BB. LiveInSets[BB] is *not* updated (because it is not needed during | |||
882 | /// PHIElimination). | |||
883 | void LiveVariables::addNewBlock(MachineBasicBlock *BB, | |||
884 | MachineBasicBlock *DomBB, | |||
885 | MachineBasicBlock *SuccBB, | |||
886 | std::vector<SparseBitVector<>> &LiveInSets) { | |||
887 | const unsigned NumNew = BB->getNumber(); | |||
888 | ||||
889 | SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()]; | |||
890 | for (unsigned R : BV) { | |||
891 | Register VirtReg = Register::index2VirtReg(R); | |||
892 | LiveVariables::VarInfo &VI = getVarInfo(VirtReg); | |||
893 | VI.AliveBlocks.set(NumNew); | |||
894 | } | |||
895 | // All registers used by PHI nodes in SuccBB must be live through BB. | |||
896 | for (MachineBasicBlock::iterator BBI = SuccBB->begin(), | |||
897 | BBE = SuccBB->end(); | |||
898 | BBI != BBE && BBI->isPHI(); ++BBI) { | |||
899 | for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) | |||
900 | if (BBI->getOperand(i + 1).getMBB() == BB && | |||
901 | BBI->getOperand(i).readsReg()) | |||
902 | getVarInfo(BBI->getOperand(i).getReg()) | |||
903 | .AliveBlocks.set(NumNew); | |||
904 | } | |||
905 | } |