• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/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"
35 #include <queue>
36 #include <list>
37 
38 using namespace llvm;
39 
40 #define DEBUG_TYPE "live-debug-values"
41 
42 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
43 
44 namespace {
45 
46 class LiveDebugValues : public MachineFunctionPass {
47 
48 private:
49   const TargetRegisterInfo *TRI;
50   const TargetInstrInfo *TII;
51 
52   typedef std::pair<const DILocalVariable *, const DILocation *>
53       InlinedVariable;
54 
55   /// A potentially inlined instance of a variable.
56   struct DebugVariable {
57     const DILocalVariable *Var;
58     const DILocation *InlinedAt;
59 
DebugVariable__anona651755e0111::LiveDebugValues::DebugVariable60     DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
61         : Var(_var), InlinedAt(_inlinedAt) {}
62 
operator ==__anona651755e0111::LiveDebugValues::DebugVariable63     bool operator==(const DebugVariable &DV) const {
64       return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
65     }
66   };
67 
68   /// Member variables and functions for Range Extension across basic blocks.
69   struct VarLoc {
70     DebugVariable Var;
71     const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr.
72 
VarLoc__anona651755e0111::LiveDebugValues::VarLoc73     VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
74 
75     bool operator==(const VarLoc &V) const;
76   };
77 
78   typedef std::list<VarLoc> VarLocList;
79   typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB;
80 
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);
86 
87   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs);
88 
89   bool ExtendRanges(MachineFunction &MF);
90 
91 public:
92   static char ID;
93 
94   /// Default construct and initialize the pass.
95   LiveDebugValues();
96 
97   /// Tell the pass manager which passes we depend on and what
98   /// information we preserve.
99   void getAnalysisUsage(AnalysisUsage &AU) const override;
100 
101   /// Print to ostream with a message.
102   void printVarLocInMBB(const VarLocInMBB &V, const char *msg,
103                         raw_ostream &Out) const;
104 
105   /// Calculate the liveness information for the given machine function.
106   bool runOnMachineFunction(MachineFunction &MF) override;
107 };
108 } // namespace
109 
110 //===----------------------------------------------------------------------===//
111 //            Implementation
112 //===----------------------------------------------------------------------===//
113 
114 char LiveDebugValues::ID = 0;
115 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
116 INITIALIZE_PASS(LiveDebugValues, "livedebugvalues", "Live DEBUG_VALUE analysis",
117                 false, false)
118 
119 /// Default construct and initialize the pass.
LiveDebugValues()120 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
121   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
122 }
123 
124 /// Tell the pass manager which passes we depend on and what information we
125 /// preserve.
getAnalysisUsage(AnalysisUsage & AU) const126 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
127   MachineFunctionPass::getAnalysisUsage(AU);
128 }
129 
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.
isDescribedByReg(const MachineInstr & MI)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;
138 }
139 
140 // \brief This function takes two DBG_VALUE instructions and returns true
141 // if their offsets are equal; otherwise returns false.
areOffsetsEqual(const MachineInstr & MI1,const MachineInstr & MI2)142 static bool areOffsetsEqual(const MachineInstr &MI1, const MachineInstr &MI2) {
143   assert(MI1.isDebugValue());
144   assert(MI1.getNumOperands() == 4);
145 
146   assert(MI2.isDebugValue());
147   assert(MI2.getNumOperands() == 4);
148 
149   if (!MI1.isIndirectDebugValue() && !MI2.isIndirectDebugValue())
150     return true;
151 
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();
155 
156   return false;
157 }
158 
159 //===----------------------------------------------------------------------===//
160 //            Debug Range Extension Implementation
161 //===----------------------------------------------------------------------===//
162 
printVarLocInMBB(const VarLocInMBB & V,const char * msg,raw_ostream & Out) const163 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();
170       Out << " MI: ";
171       (*VLL.MI).dump();
172       Out << "\n";
173     }
174   }
175   Out << "\n";
176 }
177 
operator ==(const VarLoc & V) const178 bool LiveDebugValues::VarLoc::operator==(const VarLoc &V) const {
179   return (Var == V.Var) && (isDescribedByReg(*MI) == isDescribedByReg(*V.MI)) &&
180          (areOffsetsEqual(*MI, *V.MI));
181 }
182 
183 /// End all previous ranges related to @MI and start a new range from @MI
184 /// if it is a DBG_VALUE instr.
transferDebugValue(MachineInstr & MI,VarLocList & OpenRanges)185 void LiveDebugValues::transferDebugValue(MachineInstr &MI,
186                                          VarLocList &OpenRanges) {
187   if (!MI.isDebugValue())
188     return;
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());
193 
194   // End all previous ranges of Var.
195   OpenRanges.erase(
196       std::remove_if(OpenRanges.begin(), OpenRanges.end(),
197                      [&](const VarLoc &V) { return (Var == V.Var); }),
198       OpenRanges.end());
199 
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)) {
203     VarLoc V(Var, &MI);
204     OpenRanges.push_back(std::move(V));
205   }
206 }
207 
208 /// A definition of a register may mark the end of a range.
transferRegisterDef(MachineInstr & MI,VarLocList & OpenRanges)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())))
214       continue;
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 ==
220                                                 isDescribedByReg(*V.MI));
221                                       }),
222                        OpenRanges.end());
223   }
224 }
225 
226 /// Terminate all open ranges at the end of the current basic block.
transferTerminatorInst(MachineInstr & MI,VarLocList & OpenRanges,VarLocInMBB & OutLocs)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())))
233     return false;
234 
235   if (OpenRanges.empty())
236     return false;
237 
238   if (OutLocs.find(CurMBB) == OutLocs.end()) {
239     // Create space for new Outgoing locs entries.
240     VarLocList VLL;
241     OutLocs.insert(std::make_pair(CurMBB, std::move(VLL)));
242   }
243   auto OL = OutLocs.find(CurMBB);
244   assert(OL != OutLocs.end());
245   VarLocList &VLL = OL->second;
246 
247   for (auto OR : OpenRanges) {
248     // Copy OpenRanges to OutLocs, if not already present.
249     assert(OR.MI->isDebugValue());
250     DEBUG(dbgs() << "Add to OutLocs: "; OR.MI->dump(););
251     if (std::find_if(VLL.begin(), VLL.end(),
252                      [&](const VarLoc &V) { return (OR == V); }) == VLL.end()) {
253       VLL.push_back(std::move(OR));
254       Changed = true;
255     }
256   }
257   OpenRanges.clear();
258   return Changed;
259 }
260 
261 /// This routine creates OpenRanges and OutLocs.
transfer(MachineInstr & MI,VarLocList & OpenRanges,VarLocInMBB & OutLocs)262 bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
263                                VarLocInMBB &OutLocs) {
264   bool Changed = false;
265   transferDebugValue(MI, OpenRanges);
266   transferRegisterDef(MI, OpenRanges);
267   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs);
268   return Changed;
269 }
270 
271 /// This routine joins the analysis results of all incoming edges in @MBB by
272 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
273 /// source variable in all the predecessors of @MBB reside in the same location.
join(MachineBasicBlock & MBB,VarLocInMBB & OutLocs,VarLocInMBB & InLocs)274 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
275                            VarLocInMBB &InLocs) {
276   DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
277   bool Changed = false;
278 
279   VarLocList InLocsT; // Temporary incoming locations.
280 
281   // For all predecessors of this MBB, find the set of VarLocs that can be
282   // joined.
283   for (auto p : MBB.predecessors()) {
284     auto OL = OutLocs.find(p);
285     // Join is null in case of empty OutLocs from any of the pred.
286     if (OL == OutLocs.end())
287       return false;
288 
289     // Just copy over the Out locs to incoming locs for the first predecessor.
290     if (p == *MBB.pred_begin()) {
291       InLocsT = OL->second;
292       continue;
293     }
294 
295     // Join with this predecessor.
296     VarLocList &VLL = OL->second;
297     InLocsT.erase(
298         std::remove_if(InLocsT.begin(), InLocsT.end(), [&](VarLoc &ILT) {
299           return (std::find_if(VLL.begin(), VLL.end(), [&](const VarLoc &V) {
300                     return (ILT == V);
301                   }) == VLL.end());
302         }), InLocsT.end());
303   }
304 
305   if (InLocsT.empty())
306     return false;
307 
308   if (InLocs.find(&MBB) == InLocs.end()) {
309     // Create space for new Incoming locs entries.
310     VarLocList VLL;
311     InLocs.insert(std::make_pair(&MBB, std::move(VLL)));
312   }
313   auto IL = InLocs.find(&MBB);
314   assert(IL != InLocs.end());
315   VarLocList &ILL = IL->second;
316 
317   // Insert DBG_VALUE instructions, if not already inserted.
318   for (auto ILT : InLocsT) {
319     if (std::find_if(ILL.begin(), ILL.end(), [&](const VarLoc &I) {
320           return (ILT == I);
321         }) == ILL.end()) {
322       // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
323       // new range is started for the var from the mbb's beginning by inserting
324       // a new DBG_VALUE. transfer() will end this range however appropriate.
325       const MachineInstr *DMI = ILT.MI;
326       MachineInstr *MI =
327           BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
328                   DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0,
329                   DMI->getDebugVariable(), DMI->getDebugExpression());
330       if (DMI->isIndirectDebugValue())
331         MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
332       DEBUG(dbgs() << "Inserted: "; MI->dump(););
333       ++NumInserted;
334       Changed = true;
335 
336       VarLoc V(ILT.Var, MI);
337       ILL.push_back(std::move(V));
338     }
339   }
340   return Changed;
341 }
342 
343 /// Calculate the liveness information for the given machine function and
344 /// extend ranges across basic blocks.
ExtendRanges(MachineFunction & MF)345 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
346 
347   DEBUG(dbgs() << "\nDebug Range Extension\n");
348 
349   bool Changed = false;
350   bool OLChanged = false;
351   bool MBBJoined = false;
352 
353   VarLocList OpenRanges; // Ranges that are open until end of bb.
354   VarLocInMBB OutLocs;   // Ranges that exist beyond bb.
355   VarLocInMBB InLocs;    // Ranges that are incoming after joining.
356 
357   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
358   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
359   std::priority_queue<unsigned int, std::vector<unsigned int>,
360                       std::greater<unsigned int>> Worklist;
361   std::priority_queue<unsigned int, std::vector<unsigned int>,
362                       std::greater<unsigned int>> Pending;
363   // Initialize every mbb with OutLocs.
364   for (auto &MBB : MF)
365     for (auto &MI : MBB)
366       transfer(MI, OpenRanges, OutLocs);
367   DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs()));
368 
369   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
370   unsigned int RPONumber = 0;
371   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
372     OrderToBB[RPONumber] = *RI;
373     BBToOrder[*RI] = RPONumber;
374     Worklist.push(RPONumber);
375     ++RPONumber;
376   }
377 
378   // This is a standard "union of predecessor outs" dataflow problem.
379   // To solve it, we perform join() and transfer() using the two worklist method
380   // until the ranges converge.
381   // Ranges have converged when both worklists are empty.
382   while (!Worklist.empty() || !Pending.empty()) {
383     // We track what is on the pending worklist to avoid inserting the same
384     // thing twice.  We could avoid this with a custom priority queue, but this
385     // is probably not worth it.
386     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
387     while (!Worklist.empty()) {
388       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
389       Worklist.pop();
390       MBBJoined = join(*MBB, OutLocs, InLocs);
391 
392       if (MBBJoined) {
393         MBBJoined = false;
394         Changed = true;
395         for (auto &MI : *MBB)
396           OLChanged |= transfer(MI, OpenRanges, OutLocs);
397         DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
398         DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
399 
400         if (OLChanged) {
401           OLChanged = false;
402           for (auto s : MBB->successors())
403             if (!OnPending.count(s)) {
404               OnPending.insert(s);
405               Pending.push(BBToOrder[s]);
406             }
407         }
408       }
409     }
410     Worklist.swap(Pending);
411     // At this point, pending must be empty, since it was just the empty
412     // worklist
413     assert(Pending.empty() && "Pending should be empty");
414   }
415 
416   DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
417   DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
418   return Changed;
419 }
420 
runOnMachineFunction(MachineFunction & MF)421 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
422   TRI = MF.getSubtarget().getRegisterInfo();
423   TII = MF.getSubtarget().getInstrInfo();
424 
425   bool Changed = false;
426 
427   Changed |= ExtendRanges(MF);
428 
429   return Changed;
430 }
431