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