/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LiveDebugValues.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | /// |
10 | | /// This pass implements a data flow analysis that propagates debug location |
11 | | /// information by inserting additional DBG_VALUE instructions into the machine |
12 | | /// instruction stream. The pass internally builds debug location liveness |
13 | | /// ranges to determine the points where additional DBG_VALUEs need to be |
14 | | /// inserted. |
15 | | /// |
16 | | /// This is a separate pass from DbgValueHistoryCalculator to facilitate |
17 | | /// testing and improve modularity. |
18 | | /// |
19 | | //===----------------------------------------------------------------------===// |
20 | | |
21 | | #include "llvm/ADT/DenseMap.h" |
22 | | #include "llvm/ADT/PostOrderIterator.h" |
23 | | #include "llvm/ADT/SmallPtrSet.h" |
24 | | #include "llvm/ADT/SmallVector.h" |
25 | | #include "llvm/ADT/SparseBitVector.h" |
26 | | #include "llvm/ADT/Statistic.h" |
27 | | #include "llvm/ADT/UniqueVector.h" |
28 | | #include "llvm/CodeGen/LexicalScopes.h" |
29 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
30 | | #include "llvm/CodeGen/MachineFrameInfo.h" |
31 | | #include "llvm/CodeGen/MachineFunction.h" |
32 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
33 | | #include "llvm/CodeGen/MachineInstr.h" |
34 | | #include "llvm/CodeGen/MachineInstrBuilder.h" |
35 | | #include "llvm/CodeGen/MachineMemOperand.h" |
36 | | #include "llvm/CodeGen/MachineModuleInfo.h" |
37 | | #include "llvm/CodeGen/MachineOperand.h" |
38 | | #include "llvm/CodeGen/PseudoSourceValue.h" |
39 | | #include "llvm/IR/DebugInfoMetadata.h" |
40 | | #include "llvm/IR/DebugLoc.h" |
41 | | #include "llvm/IR/Function.h" |
42 | | #include "llvm/IR/Module.h" |
43 | | #include "llvm/MC/MCRegisterInfo.h" |
44 | | #include "llvm/Pass.h" |
45 | | #include "llvm/Support/Casting.h" |
46 | | #include "llvm/Support/Compiler.h" |
47 | | #include "llvm/Support/Debug.h" |
48 | | #include "llvm/Support/raw_ostream.h" |
49 | | #include "llvm/Target/TargetFrameLowering.h" |
50 | | #include "llvm/Target/TargetInstrInfo.h" |
51 | | #include "llvm/Target/TargetLowering.h" |
52 | | #include "llvm/Target/TargetRegisterInfo.h" |
53 | | #include "llvm/Target/TargetSubtargetInfo.h" |
54 | | #include <algorithm> |
55 | | #include <cassert> |
56 | | #include <cstdint> |
57 | | #include <functional> |
58 | | #include <queue> |
59 | | #include <utility> |
60 | | #include <vector> |
61 | | |
62 | | using namespace llvm; |
63 | | |
64 | | #define DEBUG_TYPE "livedebugvalues" |
65 | | |
66 | | STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted"); |
67 | | |
68 | | // \brief If @MI is a DBG_VALUE with debug value described by a defined |
69 | | // register, returns the number of this register. In the other case, returns 0. |
70 | 3.46k | static unsigned isDbgValueDescribedByReg(const MachineInstr &MI) { |
71 | 3.46k | assert(MI.isDebugValue() && "expected a DBG_VALUE"); |
72 | 3.46k | assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); |
73 | 3.46k | // If location of variable is described using a register (directly |
74 | 3.46k | // or indirectly), this register is always a first operand. |
75 | 3.46k | return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg()3.33k : 0127 ; |
76 | 3.46k | } |
77 | | |
78 | | namespace { |
79 | | |
80 | | class LiveDebugValues : public MachineFunctionPass { |
81 | | private: |
82 | | const TargetRegisterInfo *TRI; |
83 | | const TargetInstrInfo *TII; |
84 | | const TargetFrameLowering *TFI; |
85 | | LexicalScopes LS; |
86 | | |
87 | | /// Keeps track of lexical scopes associated with a user value's source |
88 | | /// location. |
89 | | class UserValueScopes { |
90 | | DebugLoc DL; |
91 | | LexicalScopes &LS; |
92 | | SmallPtrSet<const MachineBasicBlock *, 4> LBlocks; |
93 | | |
94 | | public: |
95 | 1.65k | UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {} |
96 | | |
97 | | /// Return true if current scope dominates at least one machine |
98 | | /// instruction in a given machine basic block. |
99 | 1.22k | bool dominates(MachineBasicBlock *MBB) { |
100 | 1.22k | if (LBlocks.empty()) |
101 | 172 | LS.getMachineBasicBlocks(DL, LBlocks); |
102 | 284 | return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB); |
103 | 1.22k | } |
104 | | }; |
105 | | |
106 | | /// Based on std::pair so it can be used as an index into a DenseMap. |
107 | | using DebugVariableBase = |
108 | | std::pair<const DILocalVariable *, const DILocation *>; |
109 | | /// A potentially inlined instance of a variable. |
110 | | struct DebugVariable : public DebugVariableBase { |
111 | | DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt) |
112 | 3.46k | : DebugVariableBase(Var, InlinedAt) {} |
113 | | |
114 | 10.3k | const DILocalVariable *getVar() const { return this->first; } |
115 | 60 | const DILocation *getInlinedAt() const { return this->second; } |
116 | | |
117 | 2.60k | bool operator<(const DebugVariable &DV) const { |
118 | 2.60k | if (getVar() == DV.getVar()) |
119 | 30 | return getInlinedAt() < DV.getInlinedAt(); |
120 | 2.57k | return getVar() < DV.getVar(); |
121 | 2.57k | } |
122 | | }; |
123 | | |
124 | | /// A pair of debug variable and value location. |
125 | | struct VarLoc { |
126 | | const DebugVariable Var; |
127 | | const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE. |
128 | | mutable UserValueScopes UVS; |
129 | | enum { InvalidKind = 0, RegisterKind } Kind = InvalidKind; |
130 | | |
131 | | /// The value location. Stored separately to avoid repeatedly |
132 | | /// extracting it from MI. |
133 | | union { |
134 | | uint64_t RegNo; |
135 | | uint64_t Hash; |
136 | | } Loc; |
137 | | |
138 | | VarLoc(const MachineInstr &MI, LexicalScopes &LS) |
139 | | : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI), |
140 | 1.65k | UVS(MI.getDebugLoc(), LS) { |
141 | 1.65k | static_assert((sizeof(Loc) == sizeof(uint64_t)), |
142 | 1.65k | "hash does not cover all members of Loc"); |
143 | 1.65k | assert(MI.isDebugValue() && "not a DBG_VALUE"); |
144 | 1.65k | assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); |
145 | 1.65k | if (int RegNo1.65k = isDbgValueDescribedByReg(MI)) { |
146 | 1.65k | Kind = RegisterKind; |
147 | 1.65k | Loc.RegNo = RegNo; |
148 | 1.65k | } |
149 | 1.65k | } |
150 | | |
151 | | /// If this variable is described by a register, return it, |
152 | | /// otherwise return 0. |
153 | 24.0k | unsigned isDescribedByReg() const { |
154 | 24.0k | if (Kind == RegisterKind) |
155 | 24.0k | return Loc.RegNo; |
156 | 0 | return 0; |
157 | 0 | } |
158 | | |
159 | | /// Determine whether the lexical scope of this value's debug location |
160 | | /// dominates MBB. |
161 | 1.22k | bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); } |
162 | | |
163 | | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
164 | | LLVM_DUMP_METHOD void dump() const { MI.dump(); } |
165 | | #endif |
166 | | |
167 | 0 | bool operator==(const VarLoc &Other) const { |
168 | 0 | return Var == Other.Var && Loc.Hash == Other.Loc.Hash; |
169 | 0 | } |
170 | | |
171 | | /// This operator guarantees that VarLocs are sorted by Variable first. |
172 | 5.46k | bool operator<(const VarLoc &Other) const { |
173 | 5.46k | if (Var == Other.Var) |
174 | 2.86k | return Loc.Hash < Other.Loc.Hash; |
175 | 2.60k | return Var < Other.Var; |
176 | 2.60k | } |
177 | | }; |
178 | | |
179 | | using VarLocMap = UniqueVector<VarLoc>; |
180 | | using VarLocSet = SparseBitVector<>; |
181 | | using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>; |
182 | | struct SpillDebugPair { |
183 | | MachineInstr *SpillInst; |
184 | | MachineInstr *DebugInst; |
185 | | }; |
186 | | using SpillMap = SmallVector<SpillDebugPair, 4>; |
187 | | |
188 | | /// This holds the working set of currently open ranges. For fast |
189 | | /// access, this is done both as a set of VarLocIDs, and a map of |
190 | | /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all |
191 | | /// previous open ranges for the same variable. |
192 | | class OpenRangesSet { |
193 | | VarLocSet VarLocs; |
194 | | SmallDenseMap<DebugVariableBase, unsigned, 8> Vars; |
195 | | |
196 | | public: |
197 | 1.67M | const VarLocSet &getVarLocs() const { return VarLocs; } |
198 | | |
199 | | /// Terminate all open ranges for Var by removing it from the set. |
200 | 1.81k | void erase(DebugVariable Var) { |
201 | 1.81k | auto It = Vars.find(Var); |
202 | 1.81k | if (It != Vars.end()1.81k ) { |
203 | 331 | unsigned ID = It->second; |
204 | 331 | VarLocs.reset(ID); |
205 | 331 | Vars.erase(It); |
206 | 331 | } |
207 | 1.81k | } |
208 | | |
209 | | /// Terminate all open ranges listed in \c KillSet by removing |
210 | | /// them from the set. |
211 | 478k | void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) { |
212 | 478k | VarLocs.intersectWithComplement(KillSet); |
213 | 478k | for (unsigned ID : KillSet) |
214 | 387 | Vars.erase(VarLocIDs[ID].Var); |
215 | 478k | } |
216 | | |
217 | | /// Insert a new range into the set. |
218 | 1.65k | void insert(unsigned VarLocID, DebugVariableBase Var) { |
219 | 1.65k | VarLocs.set(VarLocID); |
220 | 1.65k | Vars.insert({Var, VarLocID}); |
221 | 1.65k | } |
222 | | |
223 | | /// Empty the set. |
224 | 456 | void clear() { |
225 | 456 | VarLocs.clear(); |
226 | 456 | Vars.clear(); |
227 | 456 | } |
228 | | |
229 | | /// Return whether the set is empty or not. |
230 | 69.3k | bool empty() const { |
231 | 69.3k | assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent"); |
232 | 69.3k | return VarLocs.empty(); |
233 | 69.3k | } |
234 | | }; |
235 | | |
236 | | bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF, |
237 | | unsigned &Reg); |
238 | | int extractSpillBaseRegAndOffset(const MachineInstr &MI, unsigned &Reg); |
239 | | |
240 | | void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, |
241 | | VarLocMap &VarLocIDs); |
242 | | void transferSpillInst(MachineInstr &MI, OpenRangesSet &OpenRanges, |
243 | | VarLocMap &VarLocIDs, SpillMap &Spills); |
244 | | void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges, |
245 | | const VarLocMap &VarLocIDs); |
246 | | bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges, |
247 | | VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); |
248 | | bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges, |
249 | | VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, SpillMap &Spills, |
250 | | bool transferSpills); |
251 | | |
252 | | bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, |
253 | | const VarLocMap &VarLocIDs, |
254 | | SmallPtrSet<const MachineBasicBlock *, 16> &Visited); |
255 | | |
256 | | bool ExtendRanges(MachineFunction &MF); |
257 | | |
258 | | public: |
259 | | static char ID; |
260 | | |
261 | | /// Default construct and initialize the pass. |
262 | | LiveDebugValues(); |
263 | | |
264 | | /// Tell the pass manager which passes we depend on and what |
265 | | /// information we preserve. |
266 | | void getAnalysisUsage(AnalysisUsage &AU) const override; |
267 | | |
268 | 33.2k | MachineFunctionProperties getRequiredProperties() const override { |
269 | 33.2k | return MachineFunctionProperties().set( |
270 | 33.2k | MachineFunctionProperties::Property::NoVRegs); |
271 | 33.2k | } |
272 | | |
273 | | /// Print to ostream with a message. |
274 | | void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V, |
275 | | const VarLocMap &VarLocIDs, const char *msg, |
276 | | raw_ostream &Out) const; |
277 | | |
278 | | /// Calculate the liveness information for the given machine function. |
279 | | bool runOnMachineFunction(MachineFunction &MF) override; |
280 | | }; |
281 | | |
282 | | } // end anonymous namespace |
283 | | |
284 | | //===----------------------------------------------------------------------===// |
285 | | // Implementation |
286 | | //===----------------------------------------------------------------------===// |
287 | | |
288 | | char LiveDebugValues::ID = 0; |
289 | | |
290 | | char &llvm::LiveDebugValuesID = LiveDebugValues::ID; |
291 | | |
292 | | INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis", |
293 | | false, false) |
294 | | |
295 | | /// Default construct and initialize the pass. |
296 | 33.3k | LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) { |
297 | 33.3k | initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry()); |
298 | 33.3k | } |
299 | | |
300 | | /// Tell the pass manager which passes we depend on and what information we |
301 | | /// preserve. |
302 | 33.2k | void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const { |
303 | 33.2k | AU.setPreservesCFG(); |
304 | 33.2k | MachineFunctionPass::getAnalysisUsage(AU); |
305 | 33.2k | } |
306 | | |
307 | | //===----------------------------------------------------------------------===// |
308 | | // Debug Range Extension Implementation |
309 | | //===----------------------------------------------------------------------===// |
310 | | |
311 | | #ifndef NDEBUG |
312 | | void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF, |
313 | | const VarLocInMBB &V, |
314 | | const VarLocMap &VarLocIDs, |
315 | | const char *msg, |
316 | | raw_ostream &Out) const { |
317 | | Out << '\n' << msg << '\n'; |
318 | | for (const MachineBasicBlock &BB : MF) { |
319 | | const auto &L = V.lookup(&BB); |
320 | | Out << "MBB: " << BB.getName() << ":\n"; |
321 | | for (unsigned VLL : L) { |
322 | | const VarLoc &VL = VarLocIDs[VLL]; |
323 | | Out << " Var: " << VL.Var.getVar()->getName(); |
324 | | Out << " MI: "; |
325 | | VL.dump(); |
326 | | } |
327 | | } |
328 | | Out << "\n"; |
329 | | } |
330 | | #endif |
331 | | |
332 | | /// Given a spill instruction, extract the register and offset used to |
333 | | /// address the spill location in a target independent way. |
334 | | int LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI, |
335 | 7 | unsigned &Reg) { |
336 | 7 | assert(MI.hasOneMemOperand() && |
337 | 7 | "Spill instruction does not have exactly one memory operand?"); |
338 | 7 | auto MMOI = MI.memoperands_begin(); |
339 | 7 | const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue(); |
340 | 7 | assert(PVal->kind() == PseudoSourceValue::FixedStack && |
341 | 7 | "Inconsistent memory operand in spill instruction"); |
342 | 7 | int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex(); |
343 | 7 | const MachineBasicBlock *MBB = MI.getParent(); |
344 | 7 | return TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg); |
345 | 7 | } |
346 | | |
347 | | /// End all previous ranges related to @MI and start a new range from @MI |
348 | | /// if it is a DBG_VALUE instr. |
349 | | void LiveDebugValues::transferDebugValue(const MachineInstr &MI, |
350 | | OpenRangesSet &OpenRanges, |
351 | 478k | VarLocMap &VarLocIDs) { |
352 | 478k | if (!MI.isDebugValue()) |
353 | 476k | return; |
354 | 1.80k | const DILocalVariable *Var = MI.getDebugVariable(); |
355 | 1.80k | const DILocation *DebugLoc = MI.getDebugLoc(); |
356 | 1.80k | const DILocation *InlinedAt = DebugLoc->getInlinedAt(); |
357 | 1.80k | assert(Var->isValidLocationForIntrinsic(DebugLoc) && |
358 | 1.80k | "Expected inlined-at fields to agree"); |
359 | 1.80k | |
360 | 1.80k | // End all previous ranges of Var. |
361 | 1.80k | DebugVariable V(Var, InlinedAt); |
362 | 1.80k | OpenRanges.erase(V); |
363 | 1.80k | |
364 | 1.80k | // Add the VarLoc to OpenRanges from this DBG_VALUE. |
365 | 1.80k | // TODO: Currently handles DBG_VALUE which has only reg as location. |
366 | 1.80k | if (isDbgValueDescribedByReg(MI)1.80k ) { |
367 | 1.65k | VarLoc VL(MI, LS); |
368 | 1.65k | unsigned ID = VarLocIDs.insert(VL); |
369 | 1.65k | OpenRanges.insert(ID, VL.Var); |
370 | 1.65k | } |
371 | 478k | } |
372 | | |
373 | | /// A definition of a register may mark the end of a range. |
374 | | void LiveDebugValues::transferRegisterDef(MachineInstr &MI, |
375 | | OpenRangesSet &OpenRanges, |
376 | 478k | const VarLocMap &VarLocIDs) { |
377 | 478k | MachineFunction *MF = MI.getParent()->getParent(); |
378 | 478k | const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); |
379 | 478k | unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); |
380 | 478k | SparseBitVector<> KillSet; |
381 | 1.92M | for (const MachineOperand &MO : MI.operands()) { |
382 | 1.92M | // Determine whether the operand is a register def. Assume that call |
383 | 1.92M | // instructions never clobber SP, because some backends (e.g., AArch64) |
384 | 1.92M | // never list SP in the regmask. |
385 | 1.92M | if (MO.isReg() && 1.92M MO.isDef()1.31M && MO.getReg()470k && |
386 | 470k | TRI->isPhysicalRegister(MO.getReg()) && |
387 | 1.92M | !(MI.isCall() && 470k MO.getReg() == SP55.3k )) { |
388 | 442k | // Remove ranges of all aliased registers. |
389 | 2.08M | for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid()2.08M ; ++RAI1.64M ) |
390 | 1.64M | for (unsigned ID : OpenRanges.getVarLocs()) |
391 | 23.4k | if (23.4k VarLocIDs[ID].isDescribedByReg() == *RAI23.4k ) |
392 | 394 | KillSet.set(ID); |
393 | 1.92M | } else if (1.47M MO.isRegMask()1.47M ) { |
394 | 29.9k | // Remove ranges of all clobbered registers. Register masks don't usually |
395 | 29.9k | // list SP as preserved. While the debug info may be off for an |
396 | 29.9k | // instruction or two around callee-cleanup calls, transferring the |
397 | 29.9k | // DEBUG_VALUE across the call is still a better user experience. |
398 | 476 | for (unsigned ID : OpenRanges.getVarLocs()) { |
399 | 476 | unsigned Reg = VarLocIDs[ID].isDescribedByReg(); |
400 | 476 | if (Reg && 476 Reg != SP476 && MO.clobbersPhysReg(Reg)316 ) |
401 | 100 | KillSet.set(ID); |
402 | 476 | } |
403 | 1.47M | } |
404 | 1.92M | } |
405 | 478k | OpenRanges.erase(KillSet, VarLocIDs); |
406 | 478k | } |
407 | | |
408 | | /// Decide if @MI is a spill instruction and return true if it is. We use 2 |
409 | | /// criteria to make this decision: |
410 | | /// - Is this instruction a store to a spill slot? |
411 | | /// - Is there a register operand that is both used and killed? |
412 | | /// TODO: Store optimization can fold spills into other stores (including |
413 | | /// other spills). We do not handle this yet (more than one memory operand). |
414 | | bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI, |
415 | 2.42k | MachineFunction *MF, unsigned &Reg) { |
416 | 2.42k | const MachineFrameInfo &FrameInfo = MF->getFrameInfo(); |
417 | 2.42k | int FI; |
418 | 2.42k | const MachineMemOperand *MMO; |
419 | 2.42k | |
420 | 2.42k | // TODO: Handle multiple stores folded into one. |
421 | 2.42k | if (!MI.hasOneMemOperand()) |
422 | 1.99k | return false; |
423 | 435 | |
424 | 435 | // To identify a spill instruction, use the same criteria as in AsmPrinter. |
425 | 435 | if (435 !((TII->isStoreToStackSlotPostFE(MI, FI) || |
426 | 407 | TII->hasStoreToStackSlot(MI, MMO, FI)) && |
427 | 44 | FrameInfo.isSpillSlotObjectIndex(FI))) |
428 | 393 | return false; |
429 | 42 | |
430 | 42 | // In a spill instruction generated by the InlineSpiller the spilled register |
431 | 42 | // has its kill flag set. Return false if we don't find such a register. |
432 | 42 | Reg = 0; |
433 | 167 | for (const MachineOperand &MO : MI.operands()) { |
434 | 167 | if (MO.isReg() && 167 MO.isUse()117 && MO.isKill()117 ) { |
435 | 42 | Reg = MO.getReg(); |
436 | 42 | break; |
437 | 42 | } |
438 | 42 | } |
439 | 42 | return Reg != 0; |
440 | 2.42k | } |
441 | | |
442 | | /// A spilled register may indicate that we have to end the current range of |
443 | | /// a variable and create a new one for the spill location. |
444 | | /// We don't want to insert any instructions in transfer(), so we just create |
445 | | /// the DBG_VALUE witout inserting it and keep track of it in @Spills. |
446 | | /// It will be inserted into the BB when we're done iterating over the |
447 | | /// instructions. |
448 | | void LiveDebugValues::transferSpillInst(MachineInstr &MI, |
449 | | OpenRangesSet &OpenRanges, |
450 | | VarLocMap &VarLocIDs, |
451 | 2.42k | SpillMap &Spills) { |
452 | 2.42k | unsigned Reg; |
453 | 2.42k | MachineFunction *MF = MI.getParent()->getParent(); |
454 | 2.42k | if (!isSpillInstruction(MI, MF, Reg)) |
455 | 2.38k | return; |
456 | 42 | |
457 | 42 | // Check if the register is the location of a debug value. |
458 | 42 | for (unsigned ID : OpenRanges.getVarLocs()) 42 { |
459 | 78 | if (VarLocIDs[ID].isDescribedByReg() == Reg78 ) { |
460 | 7 | DEBUG(dbgs() << "Spilling Register " << PrintReg(Reg, TRI) << '(' |
461 | 7 | << VarLocIDs[ID].Var.getVar()->getName() << ")\n"); |
462 | 7 | |
463 | 7 | // Create a DBG_VALUE instruction to describe the Var in its spilled |
464 | 7 | // location, but don't insert it yet to avoid invalidating the |
465 | 7 | // iterator in our caller. |
466 | 7 | unsigned SpillBase; |
467 | 7 | int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase); |
468 | 7 | const MachineInstr *DMI = &VarLocIDs[ID].MI; |
469 | 7 | auto *SpillExpr = DIExpression::prepend( |
470 | 7 | DMI->getDebugExpression(), DIExpression::NoDeref, SpillOffset); |
471 | 7 | MachineInstr *SpDMI = |
472 | 7 | BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase, |
473 | 7 | DMI->getDebugVariable(), SpillExpr); |
474 | 7 | DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: "; |
475 | 7 | SpDMI->print(dbgs(), false, TII)); |
476 | 7 | |
477 | 7 | // The newly created DBG_VALUE instruction SpDMI must be inserted after |
478 | 7 | // MI. Keep track of the pairing. |
479 | 7 | SpillDebugPair MIP = {&MI, SpDMI}; |
480 | 7 | Spills.push_back(MIP); |
481 | 7 | |
482 | 7 | // End all previous ranges of Var. |
483 | 7 | OpenRanges.erase(VarLocIDs[ID].Var); |
484 | 7 | |
485 | 7 | // Add the VarLoc to OpenRanges. |
486 | 7 | VarLoc VL(*SpDMI, LS); |
487 | 7 | unsigned SpillLocID = VarLocIDs.insert(VL); |
488 | 7 | OpenRanges.insert(SpillLocID, VL.Var); |
489 | 7 | return; |
490 | 7 | } |
491 | 35 | } |
492 | 2.42k | } |
493 | | |
494 | | /// Terminate all open ranges at the end of the current basic block. |
495 | | bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI, |
496 | | OpenRangesSet &OpenRanges, |
497 | | VarLocInMBB &OutLocs, |
498 | 478k | const VarLocMap &VarLocIDs) { |
499 | 478k | bool Changed = false; |
500 | 478k | const MachineBasicBlock *CurMBB = MI.getParent(); |
501 | 478k | if (!(MI.isTerminator() || 478k (&MI == &CurMBB->instr_back())426k )) |
502 | 409k | return false; |
503 | 69.3k | |
504 | 69.3k | if (69.3k OpenRanges.empty()69.3k ) |
505 | 68.9k | return false; |
506 | 456 | |
507 | 456 | DEBUG456 (for (unsigned ID : OpenRanges.getVarLocs()) { |
508 | 456 | // Copy OpenRanges to OutLocs, if not already present. |
509 | 456 | dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump(); |
510 | 456 | }); |
511 | 456 | VarLocSet &VLS = OutLocs[CurMBB]; |
512 | 456 | Changed = VLS |= OpenRanges.getVarLocs(); |
513 | 456 | OpenRanges.clear(); |
514 | 456 | return Changed; |
515 | 456 | } |
516 | | |
517 | | /// This routine creates OpenRanges and OutLocs. |
518 | | bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges, |
519 | | VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, |
520 | 478k | SpillMap &Spills, bool transferSpills) { |
521 | 478k | bool Changed = false; |
522 | 478k | transferDebugValue(MI, OpenRanges, VarLocIDs); |
523 | 478k | transferRegisterDef(MI, OpenRanges, VarLocIDs); |
524 | 478k | if (transferSpills) |
525 | 2.42k | transferSpillInst(MI, OpenRanges, VarLocIDs, Spills); |
526 | 478k | Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs); |
527 | 478k | return Changed; |
528 | 478k | } |
529 | | |
530 | | /// This routine joins the analysis results of all incoming edges in @MBB by |
531 | | /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same |
532 | | /// source variable in all the predecessors of @MBB reside in the same location. |
533 | | bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, |
534 | | VarLocInMBB &InLocs, const VarLocMap &VarLocIDs, |
535 | 65.8k | SmallPtrSet<const MachineBasicBlock *, 16> &Visited) { |
536 | 65.8k | DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n"); |
537 | 65.8k | bool Changed = false; |
538 | 65.8k | |
539 | 65.8k | VarLocSet InLocsT; // Temporary incoming locations. |
540 | 65.8k | |
541 | 65.8k | // For all predecessors of this MBB, find the set of VarLocs that |
542 | 65.8k | // can be joined. |
543 | 65.8k | int NumVisited = 0; |
544 | 57.4k | for (auto p : MBB.predecessors()) { |
545 | 57.4k | // Ignore unvisited predecessor blocks. As we are processing |
546 | 57.4k | // the blocks in reverse post-order any unvisited block can |
547 | 57.4k | // be considered to not remove any incoming values. |
548 | 57.4k | if (!Visited.count(p)) |
549 | 848 | continue; |
550 | 56.6k | auto OL = OutLocs.find(p); |
551 | 56.6k | // Join is null in case of empty OutLocs from any of the pred. |
552 | 56.6k | if (OL == OutLocs.end()) |
553 | 55.8k | return false; |
554 | 781 | |
555 | 781 | // Just copy over the Out locs to incoming locs for the first visited |
556 | 781 | // predecessor, and for all other predecessors join the Out locs. |
557 | 781 | if (781 !NumVisited781 ) |
558 | 556 | InLocsT = OL->second; |
559 | 781 | else |
560 | 225 | InLocsT &= OL->second; |
561 | 57.4k | NumVisited++; |
562 | 57.4k | } |
563 | 65.8k | |
564 | 65.8k | // Filter out DBG_VALUES that are out of scope. |
565 | 10.0k | VarLocSet KillSet; |
566 | 10.0k | for (auto ID : InLocsT) |
567 | 1.22k | if (1.22k !VarLocIDs[ID].dominates(MBB)1.22k ) |
568 | 53 | KillSet.set(ID); |
569 | 10.0k | InLocsT.intersectWithComplement(KillSet); |
570 | 10.0k | |
571 | 10.0k | // As we are processing blocks in reverse post-order we |
572 | 10.0k | // should have processed at least one predecessor, unless it |
573 | 10.0k | // is the entry block which has no predecessor. |
574 | 10.0k | assert((NumVisited || MBB.pred_empty()) && |
575 | 10.0k | "Should have processed at least one predecessor"); |
576 | 10.0k | if (InLocsT.empty()) |
577 | 9.53k | return false; |
578 | 523 | |
579 | 523 | VarLocSet &ILS = InLocs[&MBB]; |
580 | 523 | |
581 | 523 | // Insert DBG_VALUE instructions, if not already inserted. |
582 | 523 | VarLocSet Diff = InLocsT; |
583 | 523 | Diff.intersectWithComplement(ILS); |
584 | 680 | for (auto ID : Diff) { |
585 | 680 | // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a |
586 | 680 | // new range is started for the var from the mbb's beginning by inserting |
587 | 680 | // a new DBG_VALUE. transfer() will end this range however appropriate. |
588 | 680 | const VarLoc &DiffIt = VarLocIDs[ID]; |
589 | 680 | const MachineInstr *DMI = &DiffIt.MI; |
590 | 680 | MachineInstr *MI = |
591 | 680 | BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(), |
592 | 680 | DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), |
593 | 680 | DMI->getDebugVariable(), DMI->getDebugExpression()); |
594 | 680 | if (DMI->isIndirectDebugValue()) |
595 | 187 | MI->getOperand(1).setImm(DMI->getOperand(1).getImm()); |
596 | 680 | DEBUG(dbgs() << "Inserted: "; MI->dump();); |
597 | 680 | ILS.set(ID); |
598 | 680 | ++NumInserted; |
599 | 680 | Changed = true; |
600 | 680 | } |
601 | 65.8k | return Changed; |
602 | 65.8k | } |
603 | | |
604 | | /// Calculate the liveness information for the given machine function and |
605 | | /// extend ranges across basic blocks. |
606 | 9.51k | bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { |
607 | 9.51k | DEBUG(dbgs() << "\nDebug Range Extension\n"); |
608 | 9.51k | |
609 | 9.51k | bool Changed = false; |
610 | 9.51k | bool OLChanged = false; |
611 | 9.51k | bool MBBJoined = false; |
612 | 9.51k | |
613 | 9.51k | VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors. |
614 | 9.51k | OpenRangesSet OpenRanges; // Ranges that are open until end of bb. |
615 | 9.51k | VarLocInMBB OutLocs; // Ranges that exist beyond bb. |
616 | 9.51k | VarLocInMBB InLocs; // Ranges that are incoming after joining. |
617 | 9.51k | SpillMap Spills; // DBG_VALUEs associated with spills. |
618 | 9.51k | |
619 | 9.51k | DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; |
620 | 9.51k | DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; |
621 | 9.51k | std::priority_queue<unsigned int, std::vector<unsigned int>, |
622 | 9.51k | std::greater<unsigned int>> |
623 | 9.51k | Worklist; |
624 | 9.51k | std::priority_queue<unsigned int, std::vector<unsigned int>, |
625 | 9.51k | std::greater<unsigned int>> |
626 | 9.51k | Pending; |
627 | 9.51k | |
628 | 9.51k | // Initialize every mbb with OutLocs. |
629 | 9.51k | // We are not looking at any spill instructions during the initial pass |
630 | 9.51k | // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE |
631 | 9.51k | // instructions for spills of registers that are known to be user variables |
632 | 9.51k | // within the BB in which the spill occurs. |
633 | 9.51k | for (auto &MBB : MF) |
634 | 65.7k | for (auto &MI : MBB) |
635 | 476k | transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills, |
636 | 476k | /*transferSpills=*/false); |
637 | 9.51k | |
638 | 9.51k | DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization", |
639 | 9.51k | dbgs())); |
640 | 9.51k | |
641 | 9.51k | ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); |
642 | 9.51k | unsigned int RPONumber = 0; |
643 | 75.1k | for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE75.1k ; ++RI65.6k ) { |
644 | 65.6k | OrderToBB[RPONumber] = *RI; |
645 | 65.6k | BBToOrder[*RI] = RPONumber; |
646 | 65.6k | Worklist.push(RPONumber); |
647 | 65.6k | ++RPONumber; |
648 | 65.6k | } |
649 | 9.51k | // This is a standard "union of predecessor outs" dataflow problem. |
650 | 9.51k | // To solve it, we perform join() and transfer() using the two worklist method |
651 | 9.51k | // until the ranges converge. |
652 | 9.51k | // Ranges have converged when both worklists are empty. |
653 | 9.51k | SmallPtrSet<const MachineBasicBlock *, 16> Visited; |
654 | 19.0k | while (!Worklist.empty() || 19.0k !Pending.empty()9.51k ) { |
655 | 9.56k | // We track what is on the pending worklist to avoid inserting the same |
656 | 9.56k | // thing twice. We could avoid this with a custom priority queue, but this |
657 | 9.56k | // is probably not worth it. |
658 | 9.56k | SmallPtrSet<MachineBasicBlock *, 16> OnPending; |
659 | 9.56k | DEBUG(dbgs() << "Processing Worklist\n"); |
660 | 75.4k | while (!Worklist.empty()75.4k ) { |
661 | 65.8k | MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; |
662 | 65.8k | Worklist.pop(); |
663 | 65.8k | MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited); |
664 | 65.8k | Visited.insert(MBB); |
665 | 65.8k | if (MBBJoined65.8k ) { |
666 | 317 | MBBJoined = false; |
667 | 317 | Changed = true; |
668 | 317 | // Now that we have started to extend ranges across BBs we need to |
669 | 317 | // examine spill instructions to see whether they spill registers that |
670 | 317 | // correspond to user variables. |
671 | 317 | for (auto &MI : *MBB) |
672 | 2.42k | OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills, |
673 | 2.42k | /*transferSpills=*/true); |
674 | 317 | |
675 | 317 | // Add any DBG_VALUE instructions necessitated by spills. |
676 | 317 | for (auto &SP : Spills) |
677 | 7 | MBB->insertAfter(MachineBasicBlock::iterator(*SP.SpillInst), |
678 | 7 | SP.DebugInst); |
679 | 317 | Spills.clear(); |
680 | 317 | |
681 | 317 | DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, |
682 | 317 | "OutLocs after propagating", dbgs())); |
683 | 317 | DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, |
684 | 317 | "InLocs after propagating", dbgs())); |
685 | 317 | |
686 | 317 | if (OLChanged317 ) { |
687 | 242 | OLChanged = false; |
688 | 242 | for (auto s : MBB->successors()) |
689 | 287 | if (287 OnPending.insert(s).second287 ) { |
690 | 214 | Pending.push(BBToOrder[s]); |
691 | 214 | } |
692 | 242 | } |
693 | 317 | } |
694 | 65.8k | } |
695 | 9.56k | Worklist.swap(Pending); |
696 | 9.56k | // At this point, pending must be empty, since it was just the empty |
697 | 9.56k | // worklist |
698 | 9.56k | assert(Pending.empty() && "Pending should be empty"); |
699 | 9.56k | } |
700 | 9.51k | |
701 | 9.51k | DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs())); |
702 | 9.51k | DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs())); |
703 | 9.51k | return Changed; |
704 | 9.51k | } |
705 | | |
706 | 594k | bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) { |
707 | 594k | if (!MF.getFunction()->getSubprogram()) |
708 | 594k | // LiveDebugValues will already have removed all DBG_VALUEs. |
709 | 584k | return false; |
710 | 9.52k | |
711 | 9.52k | // Skip functions from NoDebug compilation units. |
712 | 9.52k | if (9.52k MF.getFunction()->getSubprogram()->getUnit()->getEmissionKind() == |
713 | 9.52k | DICompileUnit::NoDebug) |
714 | 15 | return false; |
715 | 9.50k | |
716 | 9.50k | TRI = MF.getSubtarget().getRegisterInfo(); |
717 | 9.50k | TII = MF.getSubtarget().getInstrInfo(); |
718 | 9.50k | TFI = MF.getSubtarget().getFrameLowering(); |
719 | 9.50k | LS.initialize(MF); |
720 | 9.50k | |
721 | 9.50k | bool Changed = ExtendRanges(MF); |
722 | 9.50k | return Changed; |
723 | 9.50k | } |