contrib/llvm/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/PostOrderIterator.h"
  22 #include "llvm/ADT/SmallPtrSet.h"
  23 #include "llvm/ADT/SparseBitVector.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/ADT/UniqueVector.h"
  26 #include "llvm/CodeGen/MachineFunction.h"
  27 #include "llvm/CodeGen/MachineFunctionPass.h"
  28 #include "llvm/CodeGen/MachineInstrBuilder.h"
  29 #include "llvm/CodeGen/Passes.h"
  30 #include "llvm/IR/DebugInfo.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include "llvm/Target/TargetInstrInfo.h"
  34 #include "llvm/Target/TargetLowering.h"
  35 #include "llvm/Target/TargetRegisterInfo.h"
  36 #include "llvm/Target/TargetSubtargetInfo.h"
  37 #include <list>
  38 #include <queue>
  39
  40 using namespace llvm;
  41
  42 #define DEBUG_TYPE "live-debug-values"
  43
  44 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
  45
  46 namespace {
  47
  48 // \brief If @MI is a DBG_VALUE with debug value described by a defined
  49 // register, returns the number of this register. In the other case, returns 0.
  50 static unsigned isDbgValueDescribedByReg(const MachineInstr &MI) {
  51   assert(MI.isDebugValue() && "expected a DBG_VALUE");
  52   assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
  53   // If location of variable is described using a register (directly
  54   // or indirectly), this register is always a first operand.
  55   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
  56 }
  57
  58 class LiveDebugValues : public MachineFunctionPass {
  59
  60 private:
  61   const TargetRegisterInfo *TRI;
  62   const TargetInstrInfo *TII;
  63
  64   /// Based on std::pair so it can be used as an index into a DenseMap.
  65   typedef std::pair<const DILocalVariable *, const DILocation *>
  66       DebugVariableBase;
  67   /// A potentially inlined instance of a variable.
  68   struct DebugVariable : public DebugVariableBase {
  69     DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt)
  70         : DebugVariableBase(Var, InlinedAt) {}
  71
  72     const DILocalVariable *getVar() const { return this->first; };
  73     const DILocation *getInlinedAt() const { return this->second; };
  74
  75     bool operator<(const DebugVariable &DV) const {
  76       if (getVar() == DV.getVar())
  77         return getInlinedAt() < DV.getInlinedAt();
  78       return getVar() < DV.getVar();
  79     }
  80   };
  81
  82   /// A pair of debug variable and value location.
  83   struct VarLoc {
  84     const DebugVariable Var;
  85     const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
  86
  87     enum { InvalidKind = 0, RegisterKind } Kind;
  88
  89     /// The value location. Stored separately to avoid repeatedly
  90     /// extracting it from MI.
  91     union {
  92       struct {
  93         uint32_t RegNo;
  94         uint32_t Offset;
  95       } RegisterLoc;
  96       uint64_t Hash;
  97     } Loc;
  98
  99     VarLoc(const MachineInstr &MI)
 100         : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
 101           Kind(InvalidKind) {
 102       static_assert((sizeof(Loc) == sizeof(uint64_t)),
 103                     "hash does not cover all members of Loc");
 104       assert(MI.isDebugValue() && "not a DBG_VALUE");
 105       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
 106       if (int RegNo = isDbgValueDescribedByReg(MI)) {
 107         Kind = RegisterKind;
 108         Loc.RegisterLoc.RegNo = RegNo;
 109         uint64_t Offset =
 110             MI.isIndirectDebugValue() ? MI.getOperand(1).getImm() : 0;
 111         // We don't support offsets larger than 4GiB here. They are
 112         // slated to be replaced with DIExpressions anyway.
 113         if (Offset >= (1ULL << 32))
 114           Kind = InvalidKind;
 115         else
 116           Loc.RegisterLoc.Offset = Offset;
 117       }
 118     }
 119
 120     /// If this variable is described by a register, return it,
 121     /// otherwise return 0.
 122     unsigned isDescribedByReg() const {
 123       if (Kind == RegisterKind)
 124         return Loc.RegisterLoc.RegNo;
 125       return 0;
 126     }
 127
 128     void dump() const { MI.dump(); }
 129
 130     bool operator==(const VarLoc &Other) const {
 131       return Var == Other.Var && Loc.Hash == Other.Loc.Hash;
 132     }
 133
 134     /// This operator guarantees that VarLocs are sorted by Variable first.
 135     bool operator<(const VarLoc &Other) const {
 136       if (Var == Other.Var)
 137         return Loc.Hash < Other.Loc.Hash;
 138       return Var < Other.Var;
 139     }
 140   };
 141
 142   typedef UniqueVector<VarLoc> VarLocMap;
 143   typedef SparseBitVector<> VarLocSet;
 144   typedef SmallDenseMap<const MachineBasicBlock *, VarLocSet> VarLocInMBB;
 145
 146   /// This holds the working set of currently open ranges. For fast
 147   /// access, this is done both as a set of VarLocIDs, and a map of
 148   /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
 149   /// previous open ranges for the same variable.
 150   class OpenRangesSet {
 151     VarLocSet VarLocs;
 152     SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
 153
 154   public:
 155     const VarLocSet &getVarLocs() const { return VarLocs; }
 156
 157     /// Terminate all open ranges for Var by removing it from the set.
 158     void erase(DebugVariable Var) {
 159       auto It = Vars.find(Var);
 160       if (It != Vars.end()) {
 161         unsigned ID = It->second;
 162         VarLocs.reset(ID);
 163         Vars.erase(It);
 164       }
 165     }
 166
 167     /// Terminate all open ranges listed in \c KillSet by removing
 168     /// them from the set.
 169     void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
 170       VarLocs.intersectWithComplement(KillSet);
 171       for (unsigned ID : KillSet)
 172         Vars.erase(VarLocIDs[ID].Var);
 173     }
 174
 175     /// Insert a new range into the set.
 176     void insert(unsigned VarLocID, DebugVariableBase Var) {
 177       VarLocs.set(VarLocID);
 178       Vars.insert({Var, VarLocID});
 179     }
 180
 181     /// Empty the set.
 182     void clear() {
 183       VarLocs.clear();
 184       Vars.clear();
 185     }
 186
 187     /// Return whether the set is empty or not.
 188     bool empty() const {
 189       assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
 190       return VarLocs.empty();
 191     }
 192   };
 193
 194   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
 195                           VarLocMap &VarLocIDs);
 196   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
 197                            const VarLocMap &VarLocIDs);
 198   bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
 199                               VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
 200   bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
 201                 VarLocInMBB &OutLocs, VarLocMap &VarLocIDs);
 202
 203   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
 204             const VarLocMap &VarLocIDs);
 205
 206   bool ExtendRanges(MachineFunction &MF);
 207
 208 public:
 209   static char ID;
 210
 211   /// Default construct and initialize the pass.
 212   LiveDebugValues();
 213
 214   /// Tell the pass manager which passes we depend on and what
 215   /// information we preserve.
 216   void getAnalysisUsage(AnalysisUsage &AU) const override;
 217
 218   MachineFunctionProperties getRequiredProperties() const override {
 219     return MachineFunctionProperties().set(
 220         MachineFunctionProperties::Property::AllVRegsAllocated);
 221   }
 222
 223   /// Print to ostream with a message.
 224   void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
 225                         const VarLocMap &VarLocIDs, const char *msg,
 226                         raw_ostream &Out) const;
 227
 228   /// Calculate the liveness information for the given machine function.
 229   bool runOnMachineFunction(MachineFunction &MF) override;
 230 };
 231 } // namespace
 232
 233 //===----------------------------------------------------------------------===//
 234 //            Implementation
 235 //===----------------------------------------------------------------------===//
 236
 237 char LiveDebugValues::ID = 0;
 238 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
 239 INITIALIZE_PASS(LiveDebugValues, "livedebugvalues", "Live DEBUG_VALUE analysis",
 240                 false, false)
 241
 242 /// Default construct and initialize the pass.
 243 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
 244   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
 245 }
 246
 247 /// Tell the pass manager which passes we depend on and what information we
 248 /// preserve.
 249 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
 250   AU.setPreservesCFG();
 251   MachineFunctionPass::getAnalysisUsage(AU);
 252 }
 253
 254 //===----------------------------------------------------------------------===//
 255 //            Debug Range Extension Implementation
 256 //===----------------------------------------------------------------------===//
 257
 258 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
 259                                        const VarLocInMBB &V,
 260                                        const VarLocMap &VarLocIDs,
 261                                        const char *msg,
 262                                        raw_ostream &Out) const {
 263   for (const MachineBasicBlock &BB : MF) {
 264     const auto &L = V.lookup(&BB);
 265     Out << "MBB: " << BB.getName() << ":\n";
 266     for (unsigned VLL : L) {
 267       const VarLoc &VL = VarLocIDs[VLL];
 268       Out << " Var: " << VL.Var.getVar()->getName();
 269       Out << " MI: ";
 270       VL.dump();
 271       Out << "\n";
 272     }
 273   }
 274   Out << "\n";
 275 }
 276
 277 /// End all previous ranges related to @MI and start a new range from @MI
 278 /// if it is a DBG_VALUE instr.
 279 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
 280                                          OpenRangesSet &OpenRanges,
 281                                          VarLocMap &VarLocIDs) {
 282   if (!MI.isDebugValue())
 283     return;
 284   const DILocalVariable *Var = MI.getDebugVariable();
 285   const DILocation *DebugLoc = MI.getDebugLoc();
 286   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
 287   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
 288          "Expected inlined-at fields to agree");
 289
 290   // End all previous ranges of Var.
 291   DebugVariable V(Var, InlinedAt);
 292   OpenRanges.erase(V);
 293
 294   // Add the VarLoc to OpenRanges from this DBG_VALUE.
 295   // TODO: Currently handles DBG_VALUE which has only reg as location.
 296   if (isDbgValueDescribedByReg(MI)) {
 297     VarLoc VL(MI);
 298     unsigned ID = VarLocIDs.insert(VL);
 299     OpenRanges.insert(ID, VL.Var);
 300   }
 301 }
 302
 303 /// A definition of a register may mark the end of a range.
 304 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
 305                                           OpenRangesSet &OpenRanges,
 306                                           const VarLocMap &VarLocIDs) {
 307   MachineFunction *MF = MI.getParent()->getParent();
 308   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
 309   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
 310   SparseBitVector<> KillSet;
 311   for (const MachineOperand &MO : MI.operands()) {
 312     if (MO.isReg() && MO.isDef() && MO.getReg() &&
 313         TRI->isPhysicalRegister(MO.getReg())) {
 314       // Remove ranges of all aliased registers.
 315       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
 316         for (unsigned ID : OpenRanges.getVarLocs())
 317           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
 318             KillSet.set(ID);
 319     } else if (MO.isRegMask()) {
 320       // Remove ranges of all clobbered registers. Register masks don't usually
 321       // list SP as preserved.  While the debug info may be off for an
 322       // instruction or two around callee-cleanup calls, transferring the
 323       // DEBUG_VALUE across the call is still a better user experience.
 324       for (unsigned ID : OpenRanges.getVarLocs()) {
 325         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
 326         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
 327           KillSet.set(ID);
 328       }
 329     }
 330   }
 331   OpenRanges.erase(KillSet, VarLocIDs);
 332 }
 333
 334 /// Terminate all open ranges at the end of the current basic block.
 335 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
 336                                              OpenRangesSet &OpenRanges,
 337                                              VarLocInMBB &OutLocs,
 338                                              const VarLocMap &VarLocIDs) {
 339   bool Changed = false;
 340   const MachineBasicBlock *CurMBB = MI.getParent();
 341   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
 342     return false;
 343
 344   if (OpenRanges.empty())
 345     return false;
 346
 347   DEBUG(for (unsigned ID : OpenRanges.getVarLocs()) {
 348           // Copy OpenRanges to OutLocs, if not already present.
 349           dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
 350         });
 351   VarLocSet &VLS = OutLocs[CurMBB];
 352   Changed = VLS |= OpenRanges.getVarLocs();
 353   OpenRanges.clear();
 354   return Changed;
 355 }
 356
 357 /// This routine creates OpenRanges and OutLocs.
 358 bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
 359                                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs) {
 360   bool Changed = false;
 361   transferDebugValue(MI, OpenRanges, VarLocIDs);
 362   transferRegisterDef(MI, OpenRanges, VarLocIDs);
 363   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
 364   return Changed;
 365 }
 366
 367 /// This routine joins the analysis results of all incoming edges in @MBB by
 368 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 369 /// source variable in all the predecessors of @MBB reside in the same location.
 370 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
 371                            VarLocInMBB &InLocs, const VarLocMap &VarLocIDs) {
 372   DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
 373   bool Changed = false;
 374
 375   VarLocSet InLocsT; // Temporary incoming locations.
 376
 377   // For all predecessors of this MBB, find the set of VarLocs that
 378   // can be joined.
 379   for (auto p : MBB.predecessors()) {
 380     auto OL = OutLocs.find(p);
 381     // Join is null in case of empty OutLocs from any of the pred.
 382     if (OL == OutLocs.end())
 383       return false;
 384
 385     // Just copy over the Out locs to incoming locs for the first predecessor.
 386     if (p == *MBB.pred_begin()) {
 387       InLocsT = OL->second;
 388       continue;
 389     }
 390     // Join with this predecessor.
 391     InLocsT &= OL->second;
 392   }
 393
 394   if (InLocsT.empty())
 395     return false;
 396
 397   VarLocSet &ILS = InLocs[&MBB];
 398
 399   // Insert DBG_VALUE instructions, if not already inserted.
 400   VarLocSet Diff = InLocsT;
 401   Diff.intersectWithComplement(ILS);
 402   for (auto ID : Diff) {
 403     // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
 404     // new range is started for the var from the mbb's beginning by inserting
 405     // a new DBG_VALUE. transfer() will end this range however appropriate.
 406     const VarLoc &DiffIt = VarLocIDs[ID];
 407     const MachineInstr *DMI = &DiffIt.MI;
 408     MachineInstr *MI =
 409         BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
 410                 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0,
 411                 DMI->getDebugVariable(), DMI->getDebugExpression());
 412     if (DMI->isIndirectDebugValue())
 413       MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
 414     DEBUG(dbgs() << "Inserted: "; MI->dump(););
 415     ILS.set(ID);
 416     ++NumInserted;
 417     Changed = true;
 418   }
 419   return Changed;
 420 }
 421
 422 /// Calculate the liveness information for the given machine function and
 423 /// extend ranges across basic blocks.
 424 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 425
 426   DEBUG(dbgs() << "\nDebug Range Extension\n");
 427
 428   bool Changed = false;
 429   bool OLChanged = false;
 430   bool MBBJoined = false;
 431
 432   VarLocMap VarLocIDs;   // Map VarLoc<>unique ID for use in bitvectors.
 433   OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
 434   VarLocInMBB OutLocs;   // Ranges that exist beyond bb.
 435   VarLocInMBB InLocs;    // Ranges that are incoming after joining.
 436
 437   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
 438   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
 439   std::priority_queue<unsigned int, std::vector<unsigned int>,
 440                       std::greater<unsigned int>>
 441       Worklist;
 442   std::priority_queue<unsigned int, std::vector<unsigned int>,
 443                       std::greater<unsigned int>>
 444       Pending;
 445
 446   // Initialize every mbb with OutLocs.
 447   for (auto &MBB : MF)
 448     for (auto &MI : MBB)
 449       transfer(MI, OpenRanges, OutLocs, VarLocIDs);
 450
 451   DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization",
 452                          dbgs()));
 453
 454   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
 455   unsigned int RPONumber = 0;
 456   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
 457     OrderToBB[RPONumber] = *RI;
 458     BBToOrder[*RI] = RPONumber;
 459     Worklist.push(RPONumber);
 460     ++RPONumber;
 461   }
 462   // This is a standard "union of predecessor outs" dataflow problem.
 463   // To solve it, we perform join() and transfer() using the two worklist method
 464   // until the ranges converge.
 465   // Ranges have converged when both worklists are empty.
 466   while (!Worklist.empty() || !Pending.empty()) {
 467     // We track what is on the pending worklist to avoid inserting the same
 468     // thing twice.  We could avoid this with a custom priority queue, but this
 469     // is probably not worth it.
 470     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
 471     while (!Worklist.empty()) {
 472       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
 473       Worklist.pop();
 474       MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs);
 475
 476       if (MBBJoined) {
 477         MBBJoined = false;
 478         Changed = true;
 479         for (auto &MI : *MBB)
 480           OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs);
 481
 482         DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
 483                                "OutLocs after propagating", dbgs()));
 484         DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
 485                                "InLocs after propagating", dbgs()));
 486
 487         if (OLChanged) {
 488           OLChanged = false;
 489           for (auto s : MBB->successors())
 490             if (OnPending.insert(s).second) {
 491               Pending.push(BBToOrder[s]);
 492             }
 493         }
 494       }
 495     }
 496     Worklist.swap(Pending);
 497     // At this point, pending must be empty, since it was just the empty
 498     // worklist
 499     assert(Pending.empty() && "Pending should be empty");
 500   }
 501
 502   DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
 503   DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
 504   return Changed;
 505 }
 506
 507 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
 508   TRI = MF.getSubtarget().getRegisterInfo();
 509   TII = MF.getSubtarget().getInstrInfo();
 510
 511   bool Changed = false;
 512
 513   Changed |= ExtendRanges(MF);
 514
 515   return Changed;
 516 }