1 //===------ LiveDebugValues.cpp - Tracking Debug Value MIs ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
16 /// This is a separate pass from DbgValueHistoryCalculator to facilitate
17 /// testing and improve modularity.
19 //===----------------------------------------------------------------------===//
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/ADT/PostOrderIterator.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/CodeGen/MachineFunction.h"
26 #include "llvm/CodeGen/MachineFunctionPass.h"
27 #include "llvm/CodeGen/MachineInstrBuilder.h"
28 #include "llvm/CodeGen/Passes.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include "llvm/Target/TargetInstrInfo.h"
33 #include "llvm/Target/TargetRegisterInfo.h"
34 #include "llvm/Target/TargetSubtargetInfo.h"
40 #define DEBUG_TYPE "live-debug-values"
42 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
46 class LiveDebugValues : public MachineFunctionPass {
49 const TargetRegisterInfo *TRI;
50 const TargetInstrInfo *TII;
52 typedef std::pair<const DILocalVariable *, const DILocation *>
55 /// A potentially inlined instance of a variable.
56 struct DebugVariable {
57 const DILocalVariable *Var;
58 const DILocation *InlinedAt;
60 DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
61 : Var(_var), InlinedAt(_inlinedAt) {}
63 bool operator==(const DebugVariable &DV) const {
64 return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
68 /// Member variables and functions for Range Extension across basic blocks.
71 const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr.
73 VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
75 bool operator==(const VarLoc &V) const;
78 typedef std::list<VarLoc> VarLocList;
79 typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB;
81 void transferDebugValue(MachineInstr &MI, VarLocList &OpenRanges);
82 void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges);
83 bool transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges,
84 VarLocInMBB &OutLocs);
85 bool transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs);
87 bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs);
89 bool ExtendRanges(MachineFunction &MF);
94 /// Default construct and initialize the pass.
97 /// Tell the pass manager which passes we depend on and what
98 /// information we preserve.
99 void getAnalysisUsage(AnalysisUsage &AU) const override;
101 /// Print to ostream with a message.
102 void printVarLocInMBB(const VarLocInMBB &V, const char *msg,
103 raw_ostream &Out) const;
105 /// Calculate the liveness information for the given machine function.
106 bool runOnMachineFunction(MachineFunction &MF) override;
110 //===----------------------------------------------------------------------===//
112 //===----------------------------------------------------------------------===//
114 char LiveDebugValues::ID = 0;
115 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
116 INITIALIZE_PASS(LiveDebugValues, "livedebugvalues", "Live DEBUG_VALUE analysis",
119 /// Default construct and initialize the pass.
120 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
121 initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
124 /// Tell the pass manager which passes we depend on and what information we
126 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
127 MachineFunctionPass::getAnalysisUsage(AU);
130 // \brief If @MI is a DBG_VALUE with debug value described by a defined
131 // register, returns the number of this register. In the other case, returns 0.
132 static unsigned isDescribedByReg(const MachineInstr &MI) {
133 assert(MI.isDebugValue());
134 assert(MI.getNumOperands() == 4);
135 // If location of variable is described using a register (directly or
136 // indirecltly), this register is always a first operand.
137 return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
140 // \brief This function takes two DBG_VALUE instructions and returns true
141 // if their offsets are equal; otherwise returns false.
142 static bool areOffsetsEqual(const MachineInstr &MI1, const MachineInstr &MI2) {
143 assert(MI1.isDebugValue());
144 assert(MI1.getNumOperands() == 4);
146 assert(MI2.isDebugValue());
147 assert(MI2.getNumOperands() == 4);
149 if (!MI1.isIndirectDebugValue() && !MI2.isIndirectDebugValue())
152 // Check if both MIs are indirect and they are equal.
153 if (MI1.isIndirectDebugValue() && MI2.isIndirectDebugValue())
154 return MI1.getOperand(1).getImm() == MI2.getOperand(1).getImm();
159 //===----------------------------------------------------------------------===//
160 // Debug Range Extension Implementation
161 //===----------------------------------------------------------------------===//
163 void LiveDebugValues::printVarLocInMBB(const VarLocInMBB &V, const char *msg,
164 raw_ostream &Out) const {
165 Out << "Printing " << msg << ":\n";
166 for (const auto &L : V) {
167 Out << "MBB: " << L.first->getName() << ":\n";
168 for (const auto &VLL : L.second) {
169 Out << " Var: " << VLL.Var.Var->getName();
178 bool LiveDebugValues::VarLoc::operator==(const VarLoc &V) const {
179 return (Var == V.Var) && (isDescribedByReg(*MI) == isDescribedByReg(*V.MI)) &&
180 (areOffsetsEqual(*MI, *V.MI));
183 /// End all previous ranges related to @MI and start a new range from @MI
184 /// if it is a DBG_VALUE instr.
185 void LiveDebugValues::transferDebugValue(MachineInstr &MI,
186 VarLocList &OpenRanges) {
187 if (!MI.isDebugValue())
189 const DILocalVariable *RawVar = MI.getDebugVariable();
190 assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
191 "Expected inlined-at fields to agree");
192 DebugVariable Var(RawVar, MI.getDebugLoc()->getInlinedAt());
194 // End all previous ranges of Var.
196 std::remove_if(OpenRanges.begin(), OpenRanges.end(),
197 [&](const VarLoc &V) { return (Var == V.Var); }),
200 // Add Var to OpenRanges from this DBG_VALUE.
201 // TODO: Currently handles DBG_VALUE which has only reg as location.
202 if (isDescribedByReg(MI)) {
204 OpenRanges.push_back(std::move(V));
208 /// A definition of a register may mark the end of a range.
209 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
210 VarLocList &OpenRanges) {
211 for (const MachineOperand &MO : MI.operands()) {
212 if (!(MO.isReg() && MO.isDef() && MO.getReg() &&
213 TRI->isPhysicalRegister(MO.getReg())))
215 // Remove ranges of all aliased registers.
216 for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
217 OpenRanges.erase(std::remove_if(OpenRanges.begin(), OpenRanges.end(),
218 [&](const VarLoc &V) {
220 isDescribedByReg(*V.MI));
226 /// Terminate all open ranges at the end of the current basic block.
227 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
228 VarLocList &OpenRanges,
229 VarLocInMBB &OutLocs) {
230 bool Changed = false;
231 const MachineBasicBlock *CurMBB = MI.getParent();
232 if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
235 if (OpenRanges.empty())
238 VarLocList &VLL = OutLocs[CurMBB];
240 for (auto OR : OpenRanges) {
241 // Copy OpenRanges to OutLocs, if not already present.
242 assert(OR.MI->isDebugValue());
243 DEBUG(dbgs() << "Add to OutLocs: "; OR.MI->dump(););
244 if (std::find_if(VLL.begin(), VLL.end(),
245 [&](const VarLoc &V) { return (OR == V); }) == VLL.end()) {
246 VLL.push_back(std::move(OR));
254 /// This routine creates OpenRanges and OutLocs.
255 bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
256 VarLocInMBB &OutLocs) {
257 bool Changed = false;
258 transferDebugValue(MI, OpenRanges);
259 transferRegisterDef(MI, OpenRanges);
260 Changed = transferTerminatorInst(MI, OpenRanges, OutLocs);
264 /// This routine joins the analysis results of all incoming edges in @MBB by
265 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
266 /// source variable in all the predecessors of @MBB reside in the same location.
267 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
268 VarLocInMBB &InLocs) {
269 DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
270 bool Changed = false;
272 VarLocList InLocsT; // Temporary incoming locations.
274 // For all predecessors of this MBB, find the set of VarLocs that can be
276 for (auto p : MBB.predecessors()) {
277 auto OL = OutLocs.find(p);
278 // Join is null in case of empty OutLocs from any of the pred.
279 if (OL == OutLocs.end())
282 // Just copy over the Out locs to incoming locs for the first predecessor.
283 if (p == *MBB.pred_begin()) {
284 InLocsT = OL->second;
288 // Join with this predecessor.
289 VarLocList &VLL = OL->second;
291 std::remove_if(InLocsT.begin(), InLocsT.end(), [&](VarLoc &ILT) {
292 return (std::find_if(VLL.begin(), VLL.end(), [&](const VarLoc &V) {
301 VarLocList &ILL = InLocs[&MBB];
303 // Insert DBG_VALUE instructions, if not already inserted.
304 for (auto ILT : InLocsT) {
305 if (std::find_if(ILL.begin(), ILL.end(), [&](const VarLoc &I) {
308 // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
309 // new range is started for the var from the mbb's beginning by inserting
310 // a new DBG_VALUE. transfer() will end this range however appropriate.
311 const MachineInstr *DMI = ILT.MI;
313 BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
314 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0,
315 DMI->getDebugVariable(), DMI->getDebugExpression());
316 if (DMI->isIndirectDebugValue())
317 MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
318 DEBUG(dbgs() << "Inserted: "; MI->dump(););
322 VarLoc V(ILT.Var, MI);
323 ILL.push_back(std::move(V));
329 /// Calculate the liveness information for the given machine function and
330 /// extend ranges across basic blocks.
331 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
333 DEBUG(dbgs() << "\nDebug Range Extension\n");
335 bool Changed = false;
336 bool OLChanged = false;
337 bool MBBJoined = false;
339 VarLocList OpenRanges; // Ranges that are open until end of bb.
340 VarLocInMBB OutLocs; // Ranges that exist beyond bb.
341 VarLocInMBB InLocs; // Ranges that are incoming after joining.
343 DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
344 DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
345 std::priority_queue<unsigned int, std::vector<unsigned int>,
346 std::greater<unsigned int>> Worklist;
347 std::priority_queue<unsigned int, std::vector<unsigned int>,
348 std::greater<unsigned int>> Pending;
349 // Initialize every mbb with OutLocs.
352 transfer(MI, OpenRanges, OutLocs);
353 DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs()));
355 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
356 unsigned int RPONumber = 0;
357 for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
358 OrderToBB[RPONumber] = *RI;
359 BBToOrder[*RI] = RPONumber;
360 Worklist.push(RPONumber);
364 // This is a standard "union of predecessor outs" dataflow problem.
365 // To solve it, we perform join() and transfer() using the two worklist method
366 // until the ranges converge.
367 // Ranges have converged when both worklists are empty.
368 while (!Worklist.empty() || !Pending.empty()) {
369 // We track what is on the pending worklist to avoid inserting the same
370 // thing twice. We could avoid this with a custom priority queue, but this
371 // is probably not worth it.
372 SmallPtrSet<MachineBasicBlock *, 16> OnPending;
373 while (!Worklist.empty()) {
374 MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
376 MBBJoined = join(*MBB, OutLocs, InLocs);
381 for (auto &MI : *MBB)
382 OLChanged |= transfer(MI, OpenRanges, OutLocs);
383 DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
384 DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
388 for (auto s : MBB->successors())
389 if (!OnPending.count(s)) {
391 Pending.push(BBToOrder[s]);
396 Worklist.swap(Pending);
397 // At this point, pending must be empty, since it was just the empty
399 assert(Pending.empty() && "Pending should be empty");
402 DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
403 DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
407 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
408 TRI = MF.getSubtarget().getRegisterInfo();
409 TII = MF.getSubtarget().getInstrInfo();
411 bool Changed = false;
413 Changed |= ExtendRanges(MF);