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/SmallVector.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/MachineFunctionPass.h"
25 #include "llvm/CodeGen/MachineInstrBuilder.h"
26 #include "llvm/CodeGen/Passes.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/Target/TargetRegisterInfo.h"
31 #include "llvm/Target/TargetInstrInfo.h"
32 #include "llvm/Target/TargetSubtargetInfo.h"
38 #define DEBUG_TYPE "live-debug-values"
40 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
44 class LiveDebugValues : public MachineFunctionPass {
47 const TargetRegisterInfo *TRI;
48 const TargetInstrInfo *TII;
50 typedef std::pair<const DILocalVariable *, const DILocation *>
53 /// A potentially inlined instance of a variable.
54 struct DebugVariable {
55 const DILocalVariable *Var;
56 const DILocation *InlinedAt;
58 DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
59 : Var(_var), InlinedAt(_inlinedAt) {}
61 bool operator==(const DebugVariable &DV) const {
62 return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
66 /// Member variables and functions for Range Extension across basic blocks.
69 const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr.
71 VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
73 bool operator==(const VarLoc &V) const;
76 typedef std::list<VarLoc> VarLocList;
77 typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB;
79 bool OLChanged; // OutgoingLocs got changed for this bb.
80 bool MBBJoined; // The MBB was joined.
82 void transferDebugValue(MachineInstr &MI, VarLocList &OpenRanges);
83 void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges);
84 void transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges,
85 VarLocInMBB &OutLocs);
86 void transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs);
88 void join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs);
90 bool ExtendRanges(MachineFunction &MF);
95 /// Default construct and initialize the pass.
98 /// Tell the pass manager which passes we depend on and what
99 /// information we preserve.
100 void getAnalysisUsage(AnalysisUsage &AU) const override;
102 /// Print to ostream with a message.
103 void printVarLocInMBB(const VarLocInMBB &V, const char *msg,
104 raw_ostream &Out) const;
106 /// Calculate the liveness information for the given machine function.
107 bool runOnMachineFunction(MachineFunction &MF) override;
111 //===----------------------------------------------------------------------===//
113 //===----------------------------------------------------------------------===//
115 char LiveDebugValues::ID = 0;
116 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
117 INITIALIZE_PASS(LiveDebugValues, "livedebugvalues", "Live DEBUG_VALUE analysis",
120 /// Default construct and initialize the pass.
121 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
122 initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
125 /// Tell the pass manager which passes we depend on and what information we
127 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
128 MachineFunctionPass::getAnalysisUsage(AU);
131 // \brief If @MI is a DBG_VALUE with debug value described by a defined
132 // register, returns the number of this register. In the other case, returns 0.
133 static unsigned isDescribedByReg(const MachineInstr &MI) {
134 assert(MI.isDebugValue());
135 assert(MI.getNumOperands() == 4);
136 // If location of variable is described using a register (directly or
137 // indirecltly), this register is always a first operand.
138 return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
141 // \brief This function takes two DBG_VALUE instructions and returns true
142 // if their offsets are equal; otherwise returns false.
143 static bool areOffsetsEqual(const MachineInstr &MI1, const MachineInstr &MI2) {
144 assert(MI1.isDebugValue());
145 assert(MI1.getNumOperands() == 4);
147 assert(MI2.isDebugValue());
148 assert(MI2.getNumOperands() == 4);
150 if (!MI1.isIndirectDebugValue() && !MI2.isIndirectDebugValue())
153 // Check if both MIs are indirect and they are equal.
154 if (MI1.isIndirectDebugValue() && MI2.isIndirectDebugValue())
155 return MI1.getOperand(1).getImm() == MI2.getOperand(1).getImm();
160 //===----------------------------------------------------------------------===//
161 // Debug Range Extension Implementation
162 //===----------------------------------------------------------------------===//
164 void LiveDebugValues::printVarLocInMBB(const VarLocInMBB &V, const char *msg,
165 raw_ostream &Out) const {
166 Out << "Printing " << msg << ":\n";
167 for (const auto &L : V) {
168 Out << "MBB: " << L.first->getName() << ":\n";
169 for (const auto &VLL : L.second) {
170 Out << " Var: " << VLL.Var.Var->getName();
179 bool LiveDebugValues::VarLoc::operator==(const VarLoc &V) const {
180 return (Var == V.Var) && (isDescribedByReg(*MI) == isDescribedByReg(*V.MI)) &&
181 (areOffsetsEqual(*MI, *V.MI));
184 /// End all previous ranges related to @MI and start a new range from @MI
185 /// if it is a DBG_VALUE instr.
186 void LiveDebugValues::transferDebugValue(MachineInstr &MI,
187 VarLocList &OpenRanges) {
188 if (!MI.isDebugValue())
190 const DILocalVariable *RawVar = MI.getDebugVariable();
191 assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
192 "Expected inlined-at fields to agree");
193 DebugVariable Var(RawVar, MI.getDebugLoc()->getInlinedAt());
195 // End all previous ranges of Var.
197 std::remove_if(OpenRanges.begin(), OpenRanges.end(),
198 [&](const VarLoc &V) { return (Var == V.Var); }),
201 // Add Var to OpenRanges from this DBG_VALUE.
202 // TODO: Currently handles DBG_VALUE which has only reg as location.
203 if (isDescribedByReg(MI)) {
205 OpenRanges.push_back(std::move(V));
209 /// A definition of a register may mark the end of a range.
210 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
211 VarLocList &OpenRanges) {
212 for (const MachineOperand &MO : MI.operands()) {
213 if (!(MO.isReg() && MO.isDef() && 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) {
219 return (*RAI == isDescribedByReg(*V.MI));
225 /// Terminate all open ranges at the end of the current basic block.
226 void LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
227 VarLocList &OpenRanges,
228 VarLocInMBB &OutLocs) {
229 const MachineBasicBlock *CurMBB = MI.getParent();
230 if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
233 if (OpenRanges.empty())
236 if (OutLocs.find(CurMBB) == OutLocs.end()) {
237 // Create space for new Outgoing locs entries.
239 OutLocs.insert(std::make_pair(CurMBB, std::move(VLL)));
241 auto OL = OutLocs.find(CurMBB);
242 assert(OL != OutLocs.end());
243 VarLocList &VLL = OL->second;
245 for (auto OR : OpenRanges) {
246 // Copy OpenRanges to OutLocs, if not already present.
247 assert(OR.MI->isDebugValue());
248 DEBUG(dbgs() << "Add to OutLocs: "; OR.MI->dump(););
249 if (std::find_if(VLL.begin(), VLL.end(),
250 [&](const VarLoc &V) { return (OR == V); }) == VLL.end()) {
251 VLL.push_back(std::move(OR));
258 /// This routine creates OpenRanges and OutLocs.
259 void LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
260 VarLocInMBB &OutLocs) {
261 transferDebugValue(MI, OpenRanges);
262 transferRegisterDef(MI, OpenRanges);
263 transferTerminatorInst(MI, OpenRanges, OutLocs);
266 /// This routine joins the analysis results of all incoming edges in @MBB by
267 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
268 /// source variable in all the predecessors of @MBB reside in the same location.
269 void LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
270 VarLocInMBB &InLocs) {
271 DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
275 VarLocList InLocsT; // Temporary incoming locations.
277 // For all predecessors of this MBB, find the set of VarLocs that can be
279 for (auto p : MBB.predecessors()) {
280 auto OL = OutLocs.find(p);
281 // Join is null in case of empty OutLocs from any of the pred.
282 if (OL == OutLocs.end())
285 // Just copy over the Out locs to incoming locs for the first predecessor.
286 if (p == *MBB.pred_begin()) {
287 InLocsT = OL->second;
291 // Join with this predecessor.
292 VarLocList &VLL = OL->second;
294 std::remove_if(InLocsT.begin(), InLocsT.end(), [&](VarLoc &ILT) {
295 return (std::find_if(VLL.begin(), VLL.end(), [&](const VarLoc &V) {
305 if (InLocs.find(&MBB) == InLocs.end()) {
306 // Create space for new Incoming locs entries.
308 InLocs.insert(std::make_pair(&MBB, std::move(VLL)));
310 auto IL = InLocs.find(&MBB);
311 assert(IL != InLocs.end());
312 VarLocList &ILL = IL->second;
314 // Insert DBG_VALUE instructions, if not already inserted.
315 for (auto ILT : InLocsT) {
316 if (std::find_if(ILL.begin(), ILL.end(), [&](const VarLoc &I) {
319 // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
320 // new range is started for the var from the mbb's beginning by inserting
321 // a new DBG_VALUE. transfer() will end this range however appropriate.
322 const MachineInstr *DMI = ILT.MI;
324 BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
325 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0,
326 DMI->getDebugVariable(), DMI->getDebugExpression());
327 if (DMI->isIndirectDebugValue())
328 MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
329 DEBUG(dbgs() << "Inserted: "; MI->dump(););
331 MBBJoined = true; // rerun transfer().
333 VarLoc V(ILT.Var, MI);
334 ILL.push_back(std::move(V));
339 /// Calculate the liveness information for the given machine function and
340 /// extend ranges across basic blocks.
341 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
343 DEBUG(dbgs() << "\nDebug Range Extension\n");
345 bool Changed = false;
346 OLChanged = MBBJoined = false;
348 VarLocList OpenRanges; // Ranges that are open until end of bb.
349 VarLocInMBB OutLocs; // Ranges that exist beyond bb.
350 VarLocInMBB InLocs; // Ranges that are incoming after joining.
352 std::deque<MachineBasicBlock *> BBWorklist;
354 // Initialize every mbb with OutLocs.
357 transfer(MI, OpenRanges, OutLocs);
358 DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs()));
360 // Construct a worklist of MBBs.
362 BBWorklist.push_back(&MBB);
364 // Perform join() and transfer() using the worklist until the ranges converge
365 // Ranges have converged when the worklist is empty.
366 while (!BBWorklist.empty()) {
367 MachineBasicBlock *MBB = BBWorklist.front();
368 BBWorklist.pop_front();
370 join(*MBB, OutLocs, InLocs);
374 for (auto &MI : *MBB)
375 transfer(MI, OpenRanges, OutLocs);
376 DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
377 DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
381 for (auto s : MBB->successors())
382 if (std::find(BBWorklist.begin(), BBWorklist.end(), s) ==
383 BBWorklist.end()) // add if not already present.
384 BBWorklist.push_back(s);
388 DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
389 DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
393 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
394 TRI = MF.getSubtarget().getRegisterInfo();
395 TII = MF.getSubtarget().getInstrInfo();
397 bool Changed = false;
399 Changed |= ExtendRanges(MF);