lib/CodeGen/LiveDebugValues.cpp

   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/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/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetRegisterInfo.h"
  32 #include "llvm/Target/TargetSubtargetInfo.h"
  33 #include <deque>
  34 #include <list>
  35
  36 using namespace llvm;
  37
  38 #define DEBUG_TYPE "live-debug-values"
  39
  40 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
  41
  42 namespace {
  43
  44 class LiveDebugValues : public MachineFunctionPass {
  45
  46 private:
  47   const TargetRegisterInfo *TRI;
  48   const TargetInstrInfo *TII;
  49
  50   typedef std::pair<const DILocalVariable *, const DILocation *>
  51       InlinedVariable;
  52
  53   /// A potentially inlined instance of a variable.
  54   struct DebugVariable {
  55     const DILocalVariable *Var;
  56     const DILocation *InlinedAt;
  57
  58     DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
  59         : Var(_var), InlinedAt(_inlinedAt) {}
  60
  61     bool operator==(const DebugVariable &DV) const {
  62       return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
  63     }
  64   };
  65
  66   /// Member variables and functions for Range Extension across basic blocks.
  67   struct VarLoc {
  68     DebugVariable Var;
  69     const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr.
  70
  71     VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
  72
  73     bool operator==(const VarLoc &V) const;
  74   };
  75
  76   typedef std::list<VarLoc> VarLocList;
  77   typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB;
  78
  79   bool OLChanged; // OutgoingLocs got changed for this bb.
  80   bool MBBJoined; // The MBB was joined.
  81
  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);
  87
  88   void join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs);
  89
  90   bool ExtendRanges(MachineFunction &MF);
  91
  92 public:
  93   static char ID;
  94
  95   /// Default construct and initialize the pass.
  96   LiveDebugValues();
  97
  98   /// Tell the pass manager which passes we depend on and what
  99   /// information we preserve.
 100   void getAnalysisUsage(AnalysisUsage &AU) const override;
 101
 102   /// Print to ostream with a message.
 103   void printVarLocInMBB(const VarLocInMBB &V, const char *msg,
 104                         raw_ostream &Out) const;
 105
 106   /// Calculate the liveness information for the given machine function.
 107   bool runOnMachineFunction(MachineFunction &MF) override;
 108 };
 109 } // namespace
 110
 111 //===----------------------------------------------------------------------===//
 112 //            Implementation
 113 //===----------------------------------------------------------------------===//
 114
 115 char LiveDebugValues::ID = 0;
 116 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
 117 INITIALIZE_PASS(LiveDebugValues, "livedebugvalues", "Live DEBUG_VALUE analysis",
 118                 false, false)
 119
 120 /// Default construct and initialize the pass.
 121 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
 122   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
 123 }
 124
 125 /// Tell the pass manager which passes we depend on and what information we
 126 /// preserve.
 127 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
 128   MachineFunctionPass::getAnalysisUsage(AU);
 129 }
 130
 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;
 139 }
 140
 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);
 146
 147   assert(MI2.isDebugValue());
 148   assert(MI2.getNumOperands() == 4);
 149
 150   if (!MI1.isIndirectDebugValue() && !MI2.isIndirectDebugValue())
 151     return true;
 152
 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();
 156
 157   return false;
 158 }
 159
 160 //===----------------------------------------------------------------------===//
 161 //            Debug Range Extension Implementation
 162 //===----------------------------------------------------------------------===//
 163
 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();
 171       Out << " MI: ";
 172       (*VLL.MI).dump();
 173       Out << "\n";
 174     }
 175   }
 176   Out << "\n";
 177 }
 178
 179 bool LiveDebugValues::VarLoc::operator==(const VarLoc &V) const {
 180   return (Var == V.Var) && (isDescribedByReg(*MI) == isDescribedByReg(*V.MI)) &&
 181          (areOffsetsEqual(*MI, *V.MI));
 182 }
 183
 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())
 189     return;
 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());
 194
 195   // End all previous ranges of Var.
 196   OpenRanges.erase(
 197       std::remove_if(OpenRanges.begin(), OpenRanges.end(),
 198                      [&](const VarLoc &V) { return (Var == V.Var); }),
 199       OpenRanges.end());
 200
 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)) {
 204     VarLoc V(Var, &MI);
 205     OpenRanges.push_back(std::move(V));
 206   }
 207 }
 208
 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() &&
 214           TRI->isPhysicalRegister(MO.getReg())))
 215       continue;
 216     // Remove ranges of all aliased registers.
 217     for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
 218       OpenRanges.erase(std::remove_if(OpenRanges.begin(), OpenRanges.end(),
 219                                       [&](const VarLoc &V) {
 220                                         return (*RAI ==
 221                                                 isDescribedByReg(*V.MI));
 222                                       }),
 223                        OpenRanges.end());
 224   }
 225 }
 226
 227 /// Terminate all open ranges at the end of the current basic block.
 228 void LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
 229                                              VarLocList &OpenRanges,
 230                                              VarLocInMBB &OutLocs) {
 231   const MachineBasicBlock *CurMBB = MI.getParent();
 232   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
 233     return;
 234
 235   if (OpenRanges.empty())
 236     return;
 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       OLChanged = true;
 255     }
 256   }
 257   OpenRanges.clear();
 258 }
 259
 260 /// This routine creates OpenRanges and OutLocs.
 261 void LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
 262                                VarLocInMBB &OutLocs) {
 263   transferDebugValue(MI, OpenRanges);
 264   transferRegisterDef(MI, OpenRanges);
 265   transferTerminatorInst(MI, OpenRanges, OutLocs);
 266 }
 267
 268 /// This routine joins the analysis results of all incoming edges in @MBB by
 269 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 270 /// source variable in all the predecessors of @MBB reside in the same location.
 271 void LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
 272                            VarLocInMBB &InLocs) {
 273   DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
 274
 275   MBBJoined = false;
 276
 277   VarLocList InLocsT; // Temporary incoming locations.
 278
 279   // For all predecessors of this MBB, find the set of VarLocs that can be
 280   // joined.
 281   for (auto p : MBB.predecessors()) {
 282     auto OL = OutLocs.find(p);
 283     // Join is null in case of empty OutLocs from any of the pred.
 284     if (OL == OutLocs.end())
 285       return;
 286
 287     // Just copy over the Out locs to incoming locs for the first predecessor.
 288     if (p == *MBB.pred_begin()) {
 289       InLocsT = OL->second;
 290       continue;
 291     }
 292
 293     // Join with this predecessor.
 294     VarLocList &VLL = OL->second;
 295     InLocsT.erase(std::remove_if(InLocsT.begin(), InLocsT.end(),
 296                                  [&](VarLoc &ILT) {
 297                                    return (std::find_if(VLL.begin(), VLL.end(),
 298                                                         [&](const VarLoc &V) {
 299                                                           return (ILT == V);
 300                                                         }) == VLL.end());
 301                                  }),
 302                   InLocsT.end());
 303   }
 304
 305   if (InLocsT.empty())
 306     return;
 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       MBBJoined = true; // rerun transfer().
 335
 336       VarLoc V(ILT.Var, MI);
 337       ILL.push_back(std::move(V));
 338     }
 339   }
 340 }
 341
 342 /// Calculate the liveness information for the given machine function and
 343 /// extend ranges across basic blocks.
 344 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 345
 346   DEBUG(dbgs() << "\nDebug Range Extension\n");
 347
 348   bool Changed = false;
 349   OLChanged = MBBJoined = false;
 350
 351   VarLocList OpenRanges; // Ranges that are open until end of bb.
 352   VarLocInMBB OutLocs;   // Ranges that exist beyond bb.
 353   VarLocInMBB InLocs;    // Ranges that are incoming after joining.
 354
 355   std::deque<MachineBasicBlock *> BBWorklist;
 356
 357   // Initialize every mbb with OutLocs.
 358   for (auto &MBB : MF)
 359     for (auto &MI : MBB)
 360       transfer(MI, OpenRanges, OutLocs);
 361   DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs()));
 362
 363   // Construct a worklist of MBBs.
 364   for (auto &MBB : MF)
 365     BBWorklist.push_back(&MBB);
 366
 367   // Perform join() and transfer() using the worklist until the ranges converge
 368   // Ranges have converged when the worklist is empty.
 369   while (!BBWorklist.empty()) {
 370     MachineBasicBlock *MBB = BBWorklist.front();
 371     BBWorklist.pop_front();
 372
 373     join(*MBB, OutLocs, InLocs);
 374
 375     if (MBBJoined) {
 376       Changed = true;
 377       for (auto &MI : *MBB)
 378         transfer(MI, OpenRanges, OutLocs);
 379       DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
 380       DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
 381
 382       if (OLChanged) {
 383         OLChanged = false;
 384         for (auto s : MBB->successors())
 385           if (std::find(BBWorklist.begin(), BBWorklist.end(), s) ==
 386               BBWorklist.end()) // add if not already present.
 387             BBWorklist.push_back(s);
 388       }
 389     }
 390   }
 391   DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
 392   DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
 393   return Changed;
 394 }
 395
 396 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
 397   TRI = MF.getSubtarget().getRegisterInfo();
 398   TII = MF.getSubtarget().getInstrInfo();
 399
 400   bool Changed = false;
 401
 402   Changed |= ExtendRanges(MF);
 403
 404   return Changed;
 405 }