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/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
  60     DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
  61         : Var(_var), InlinedAt(_inlinedAt) {}
  62
  63     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
  73     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.
 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.
 126 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.
 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.
 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
 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();
 170       Out << " MI: ";
 171       (*VLL.MI).dump();
 172       Out << "\n";
 173     }
 174   }
 175   Out << "\n";
 176 }
 177
 178 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.
 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.
 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.
 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   VarLocList &VLL = OutLocs[CurMBB];
 239
 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));
 247       Changed = true;
 248     }
 249   }
 250   OpenRanges.clear();
 251   return Changed;
 252 }
 253
 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);
 261   return Changed;
 262 }
 263
 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;
 271
 272   VarLocList InLocsT; // Temporary incoming locations.
 273
 274   // For all predecessors of this MBB, find the set of VarLocs that can be
 275   // joined.
 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())
 280       return false;
 281
 282     // Just copy over the Out locs to incoming locs for the first predecessor.
 283     if (p == *MBB.pred_begin()) {
 284       InLocsT = OL->second;
 285       continue;
 286     }
 287
 288     // Join with this predecessor.
 289     VarLocList &VLL = OL->second;
 290     InLocsT.erase(
 291         std::remove_if(InLocsT.begin(), InLocsT.end(), [&](VarLoc &ILT) {
 292           return (std::find_if(VLL.begin(), VLL.end(), [&](const VarLoc &V) {
 293                     return (ILT == V);
 294                   }) == VLL.end());
 295         }), InLocsT.end());
 296   }
 297
 298   if (InLocsT.empty())
 299     return false;
 300
 301   VarLocList &ILL = InLocs[&MBB];
 302
 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) {
 306           return (ILT == I);
 307         }) == ILL.end()) {
 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;
 312       MachineInstr *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(););
 319       ++NumInserted;
 320       Changed = true;
 321
 322       VarLoc V(ILT.Var, MI);
 323       ILL.push_back(std::move(V));
 324     }
 325   }
 326   return Changed;
 327 }
 328
 329 /// Calculate the liveness information for the given machine function and
 330 /// extend ranges across basic blocks.
 331 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 332
 333   DEBUG(dbgs() << "\nDebug Range Extension\n");
 334
 335   bool Changed = false;
 336   bool OLChanged = false;
 337   bool MBBJoined = false;
 338
 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.
 342
 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.
 350   for (auto &MBB : MF)
 351     for (auto &MI : MBB)
 352       transfer(MI, OpenRanges, OutLocs);
 353   DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs()));
 354
 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);
 361     ++RPONumber;
 362   }
 363
 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()];
 375       Worklist.pop();
 376       MBBJoined = join(*MBB, OutLocs, InLocs);
 377
 378       if (MBBJoined) {
 379         MBBJoined = false;
 380         Changed = true;
 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()));
 385
 386         if (OLChanged) {
 387           OLChanged = false;
 388           for (auto s : MBB->successors())
 389             if (!OnPending.count(s)) {
 390               OnPending.insert(s);
 391               Pending.push(BBToOrder[s]);
 392             }
 393         }
 394       }
 395     }
 396     Worklist.swap(Pending);
 397     // At this point, pending must be empty, since it was just the empty
 398     // worklist
 399     assert(Pending.empty() && "Pending should be empty");
 400   }
 401
 402   DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
 403   DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
 404   return Changed;
 405 }
 406
 407 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
 408   TRI = MF.getSubtarget().getRegisterInfo();
 409   TII = MF.getSubtarget().getInstrInfo();
 410
 411   bool Changed = false;
 412
 413   Changed |= ExtendRanges(MF);
 414
 415   return Changed;
 416 }