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/DenseMap.h"
  22 #include "llvm/ADT/PostOrderIterator.h"
  23 #include "llvm/ADT/SmallPtrSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/SparseBitVector.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include "llvm/ADT/UniqueVector.h"
  28 #include "llvm/CodeGen/LexicalScopes.h"
  29 #include "llvm/CodeGen/MachineBasicBlock.h"
  30 #include "llvm/CodeGen/MachineFrameInfo.h"
  31 #include "llvm/CodeGen/MachineFunction.h"
  32 #include "llvm/CodeGen/MachineFunctionPass.h"
  33 #include "llvm/CodeGen/MachineInstr.h"
  34 #include "llvm/CodeGen/MachineInstrBuilder.h"
  35 #include "llvm/CodeGen/MachineMemOperand.h"
  36 #include "llvm/CodeGen/MachineOperand.h"
  37 #include "llvm/CodeGen/PseudoSourceValue.h"
  38 #include "llvm/CodeGen/TargetFrameLowering.h"
  39 #include "llvm/CodeGen/TargetInstrInfo.h"
  40 #include "llvm/CodeGen/TargetLowering.h"
  41 #include "llvm/CodeGen/TargetRegisterInfo.h"
  42 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  43 #include "llvm/IR/DebugInfoMetadata.h"
  44 #include "llvm/IR/DebugLoc.h"
  45 #include "llvm/IR/Function.h"
  46 #include "llvm/IR/Module.h"
  47 #include "llvm/MC/MCRegisterInfo.h"
  48 #include "llvm/Pass.h"
  49 #include "llvm/Support/Casting.h"
  50 #include "llvm/Support/Compiler.h"
  51 #include "llvm/Support/Debug.h"
  52 #include "llvm/Support/raw_ostream.h"
  53 #include <algorithm>
  54 #include <cassert>
  55 #include <cstdint>
  56 #include <functional>
  57 #include <queue>
  58 #include <utility>
  59 #include <vector>
  60
  61 using namespace llvm;
  62
  63 #define DEBUG_TYPE "livedebugvalues"
  64
  65 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
  66
  67 // \brief If @MI is a DBG_VALUE with debug value described by a defined
  68 // register, returns the number of this register. In the other case, returns 0.
  69 static unsigned isDbgValueDescribedByReg(const MachineInstr &MI) {
  70   assert(MI.isDebugValue() && "expected a DBG_VALUE");
  71   assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
  72   // If location of variable is described using a register (directly
  73   // or indirectly), this register is always a first operand.
  74   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
  75 }
  76
  77 namespace {
  78
  79 class LiveDebugValues : public MachineFunctionPass {
  80 private:
  81   const TargetRegisterInfo *TRI;
  82   const TargetInstrInfo *TII;
  83   const TargetFrameLowering *TFI;
  84   LexicalScopes LS;
  85
  86   /// Keeps track of lexical scopes associated with a user value's source
  87   /// location.
  88   class UserValueScopes {
  89     DebugLoc DL;
  90     LexicalScopes &LS;
  91     SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
  92
  93   public:
  94     UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {}
  95
  96     /// Return true if current scope dominates at least one machine
  97     /// instruction in a given machine basic block.
  98     bool dominates(MachineBasicBlock *MBB) {
  99       if (LBlocks.empty())
 100         LS.getMachineBasicBlocks(DL, LBlocks);
 101       return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB);
 102     }
 103   };
 104
 105   /// Based on std::pair so it can be used as an index into a DenseMap.
 106   using DebugVariableBase =
 107       std::pair<const DILocalVariable *, const DILocation *>;
 108   /// A potentially inlined instance of a variable.
 109   struct DebugVariable : public DebugVariableBase {
 110     DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt)
 111         : DebugVariableBase(Var, InlinedAt) {}
 112
 113     const DILocalVariable *getVar() const { return this->first; }
 114     const DILocation *getInlinedAt() const { return this->second; }
 115
 116     bool operator<(const DebugVariable &DV) const {
 117       if (getVar() == DV.getVar())
 118         return getInlinedAt() < DV.getInlinedAt();
 119       return getVar() < DV.getVar();
 120     }
 121   };
 122
 123   /// A pair of debug variable and value location.
 124   struct VarLoc {
 125     const DebugVariable Var;
 126     const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
 127     mutable UserValueScopes UVS;
 128     enum { InvalidKind = 0, RegisterKind } Kind = InvalidKind;
 129
 130     /// The value location. Stored separately to avoid repeatedly
 131     /// extracting it from MI.
 132     union {
 133       uint64_t RegNo;
 134       uint64_t Hash;
 135     } Loc;
 136
 137     VarLoc(const MachineInstr &MI, LexicalScopes &LS)
 138         : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
 139           UVS(MI.getDebugLoc(), LS) {
 140       static_assert((sizeof(Loc) == sizeof(uint64_t)),
 141                     "hash does not cover all members of Loc");
 142       assert(MI.isDebugValue() && "not a DBG_VALUE");
 143       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
 144       if (int RegNo = isDbgValueDescribedByReg(MI)) {
 145         Kind = RegisterKind;
 146         Loc.RegNo = RegNo;
 147       }
 148     }
 149
 150     /// If this variable is described by a register, return it,
 151     /// otherwise return 0.
 152     unsigned isDescribedByReg() const {
 153       if (Kind == RegisterKind)
 154         return Loc.RegNo;
 155       return 0;
 156     }
 157
 158     /// Determine whether the lexical scope of this value's debug location
 159     /// dominates MBB.
 160     bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
 161
 162 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 163     LLVM_DUMP_METHOD void dump() const { MI.dump(); }
 164 #endif
 165
 166     bool operator==(const VarLoc &Other) const {
 167       return Var == Other.Var && Loc.Hash == Other.Loc.Hash;
 168     }
 169
 170     /// This operator guarantees that VarLocs are sorted by Variable first.
 171     bool operator<(const VarLoc &Other) const {
 172       if (Var == Other.Var)
 173         return Loc.Hash < Other.Loc.Hash;
 174       return Var < Other.Var;
 175     }
 176   };
 177
 178   using VarLocMap = UniqueVector<VarLoc>;
 179   using VarLocSet = SparseBitVector<>;
 180   using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
 181   struct SpillDebugPair {
 182     MachineInstr *SpillInst;
 183     MachineInstr *DebugInst;
 184   };
 185   using SpillMap = SmallVector<SpillDebugPair, 4>;
 186
 187   /// This holds the working set of currently open ranges. For fast
 188   /// access, this is done both as a set of VarLocIDs, and a map of
 189   /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
 190   /// previous open ranges for the same variable.
 191   class OpenRangesSet {
 192     VarLocSet VarLocs;
 193     SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
 194
 195   public:
 196     const VarLocSet &getVarLocs() const { return VarLocs; }
 197
 198     /// Terminate all open ranges for Var by removing it from the set.
 199     void erase(DebugVariable Var) {
 200       auto It = Vars.find(Var);
 201       if (It != Vars.end()) {
 202         unsigned ID = It->second;
 203         VarLocs.reset(ID);
 204         Vars.erase(It);
 205       }
 206     }
 207
 208     /// Terminate all open ranges listed in \c KillSet by removing
 209     /// them from the set.
 210     void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
 211       VarLocs.intersectWithComplement(KillSet);
 212       for (unsigned ID : KillSet)
 213         Vars.erase(VarLocIDs[ID].Var);
 214     }
 215
 216     /// Insert a new range into the set.
 217     void insert(unsigned VarLocID, DebugVariableBase Var) {
 218       VarLocs.set(VarLocID);
 219       Vars.insert({Var, VarLocID});
 220     }
 221
 222     /// Empty the set.
 223     void clear() {
 224       VarLocs.clear();
 225       Vars.clear();
 226     }
 227
 228     /// Return whether the set is empty or not.
 229     bool empty() const {
 230       assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
 231       return VarLocs.empty();
 232     }
 233   };
 234
 235   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF,
 236                           unsigned &Reg);
 237   int extractSpillBaseRegAndOffset(const MachineInstr &MI, unsigned &Reg);
 238
 239   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
 240                           VarLocMap &VarLocIDs);
 241   void transferSpillInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
 242                          VarLocMap &VarLocIDs, SpillMap &Spills);
 243   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
 244                            const VarLocMap &VarLocIDs);
 245   bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
 246                               VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
 247   bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
 248                 VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, SpillMap &Spills,
 249                 bool transferSpills);
 250
 251   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
 252             const VarLocMap &VarLocIDs,
 253             SmallPtrSet<const MachineBasicBlock *, 16> &Visited);
 254
 255   bool ExtendRanges(MachineFunction &MF);
 256
 257 public:
 258   static char ID;
 259
 260   /// Default construct and initialize the pass.
 261   LiveDebugValues();
 262
 263   /// Tell the pass manager which passes we depend on and what
 264   /// information we preserve.
 265   void getAnalysisUsage(AnalysisUsage &AU) const override;
 266
 267   MachineFunctionProperties getRequiredProperties() const override {
 268     return MachineFunctionProperties().set(
 269         MachineFunctionProperties::Property::NoVRegs);
 270   }
 271
 272   /// Print to ostream with a message.
 273   void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
 274                         const VarLocMap &VarLocIDs, const char *msg,
 275                         raw_ostream &Out) const;
 276
 277   /// Calculate the liveness information for the given machine function.
 278   bool runOnMachineFunction(MachineFunction &MF) override;
 279 };
 280
 281 } // end anonymous namespace
 282
 283 //===----------------------------------------------------------------------===//
 284 //            Implementation
 285 //===----------------------------------------------------------------------===//
 286
 287 char LiveDebugValues::ID = 0;
 288
 289 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
 290
 291 INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
 292                 false, false)
 293
 294 /// Default construct and initialize the pass.
 295 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
 296   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
 297 }
 298
 299 /// Tell the pass manager which passes we depend on and what information we
 300 /// preserve.
 301 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
 302   AU.setPreservesCFG();
 303   MachineFunctionPass::getAnalysisUsage(AU);
 304 }
 305
 306 //===----------------------------------------------------------------------===//
 307 //            Debug Range Extension Implementation
 308 //===----------------------------------------------------------------------===//
 309
 310 #ifndef NDEBUG
 311 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
 312                                        const VarLocInMBB &V,
 313                                        const VarLocMap &VarLocIDs,
 314                                        const char *msg,
 315                                        raw_ostream &Out) const {
 316   Out << '\n' << msg << '\n';
 317   for (const MachineBasicBlock &BB : MF) {
 318     const auto &L = V.lookup(&BB);
 319     Out << "MBB: " << BB.getName() << ":\n";
 320     for (unsigned VLL : L) {
 321       const VarLoc &VL = VarLocIDs[VLL];
 322       Out << " Var: " << VL.Var.getVar()->getName();
 323       Out << " MI: ";
 324       VL.dump();
 325     }
 326   }
 327   Out << "\n";
 328 }
 329 #endif
 330
 331 /// Given a spill instruction, extract the register and offset used to
 332 /// address the spill location in a target independent way.
 333 int LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI,
 334                                                   unsigned &Reg) {
 335   assert(MI.hasOneMemOperand() &&
 336          "Spill instruction does not have exactly one memory operand?");
 337   auto MMOI = MI.memoperands_begin();
 338   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
 339   assert(PVal->kind() == PseudoSourceValue::FixedStack &&
 340          "Inconsistent memory operand in spill instruction");
 341   int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
 342   const MachineBasicBlock *MBB = MI.getParent();
 343   return TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
 344 }
 345
 346 /// End all previous ranges related to @MI and start a new range from @MI
 347 /// if it is a DBG_VALUE instr.
 348 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
 349                                          OpenRangesSet &OpenRanges,
 350                                          VarLocMap &VarLocIDs) {
 351   if (!MI.isDebugValue())
 352     return;
 353   const DILocalVariable *Var = MI.getDebugVariable();
 354   const DILocation *DebugLoc = MI.getDebugLoc();
 355   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
 356   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
 357          "Expected inlined-at fields to agree");
 358
 359   // End all previous ranges of Var.
 360   DebugVariable V(Var, InlinedAt);
 361   OpenRanges.erase(V);
 362
 363   // Add the VarLoc to OpenRanges from this DBG_VALUE.
 364   // TODO: Currently handles DBG_VALUE which has only reg as location.
 365   if (isDbgValueDescribedByReg(MI)) {
 366     VarLoc VL(MI, LS);
 367     unsigned ID = VarLocIDs.insert(VL);
 368     OpenRanges.insert(ID, VL.Var);
 369   }
 370 }
 371
 372 /// A definition of a register may mark the end of a range.
 373 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
 374                                           OpenRangesSet &OpenRanges,
 375                                           const VarLocMap &VarLocIDs) {
 376   MachineFunction *MF = MI.getMF();
 377   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
 378   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
 379   SparseBitVector<> KillSet;
 380   for (const MachineOperand &MO : MI.operands()) {
 381     // Determine whether the operand is a register def.  Assume that call
 382     // instructions never clobber SP, because some backends (e.g., AArch64)
 383     // never list SP in the regmask.
 384     if (MO.isReg() && MO.isDef() && MO.getReg() &&
 385         TRI->isPhysicalRegister(MO.getReg()) &&
 386         !(MI.isCall() && MO.getReg() == SP)) {
 387       // Remove ranges of all aliased registers.
 388       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
 389         for (unsigned ID : OpenRanges.getVarLocs())
 390           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
 391             KillSet.set(ID);
 392     } else if (MO.isRegMask()) {
 393       // Remove ranges of all clobbered registers. Register masks don't usually
 394       // list SP as preserved.  While the debug info may be off for an
 395       // instruction or two around callee-cleanup calls, transferring the
 396       // DEBUG_VALUE across the call is still a better user experience.
 397       for (unsigned ID : OpenRanges.getVarLocs()) {
 398         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
 399         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
 400           KillSet.set(ID);
 401       }
 402     }
 403   }
 404   OpenRanges.erase(KillSet, VarLocIDs);
 405 }
 406
 407 /// Decide if @MI is a spill instruction and return true if it is. We use 2
 408 /// criteria to make this decision:
 409 /// - Is this instruction a store to a spill slot?
 410 /// - Is there a register operand that is both used and killed?
 411 /// TODO: Store optimization can fold spills into other stores (including
 412 /// other spills). We do not handle this yet (more than one memory operand).
 413 bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
 414                                          MachineFunction *MF, unsigned &Reg) {
 415   const MachineFrameInfo &FrameInfo = MF->getFrameInfo();
 416   int FI;
 417   const MachineMemOperand *MMO;
 418
 419   // TODO: Handle multiple stores folded into one.
 420   if (!MI.hasOneMemOperand())
 421     return false;
 422
 423   // To identify a spill instruction, use the same criteria as in AsmPrinter.
 424   if (!((TII->isStoreToStackSlotPostFE(MI, FI) ||
 425          TII->hasStoreToStackSlot(MI, MMO, FI)) &&
 426         FrameInfo.isSpillSlotObjectIndex(FI)))
 427     return false;
 428
 429   // In a spill instruction generated by the InlineSpiller the spilled register
 430   // has its kill flag set. Return false if we don't find such a register.
 431   Reg = 0;
 432   for (const MachineOperand &MO : MI.operands()) {
 433     if (MO.isReg() && MO.isUse() && MO.isKill()) {
 434       Reg = MO.getReg();
 435       break;
 436     }
 437   }
 438   return Reg != 0;
 439 }
 440
 441 /// A spilled register may indicate that we have to end the current range of
 442 /// a variable and create a new one for the spill location.
 443 /// We don't want to insert any instructions in transfer(), so we just create
 444 /// the DBG_VALUE witout inserting it and keep track of it in @Spills.
 445 /// It will be inserted into the BB when we're done iterating over the
 446 /// instructions.
 447 void LiveDebugValues::transferSpillInst(MachineInstr &MI,
 448                                         OpenRangesSet &OpenRanges,
 449                                         VarLocMap &VarLocIDs,
 450                                         SpillMap &Spills) {
 451   unsigned Reg;
 452   MachineFunction *MF = MI.getMF();
 453   if (!isSpillInstruction(MI, MF, Reg))
 454     return;
 455
 456   // Check if the register is the location of a debug value.
 457   for (unsigned ID : OpenRanges.getVarLocs()) {
 458     if (VarLocIDs[ID].isDescribedByReg() == Reg) {
 459       DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
 460                    << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
 461
 462       // Create a DBG_VALUE instruction to describe the Var in its spilled
 463       // location, but don't insert it yet to avoid invalidating the
 464       // iterator in our caller.
 465       unsigned SpillBase;
 466       int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase);
 467       const MachineInstr *DMI = &VarLocIDs[ID].MI;
 468       auto *SpillExpr = DIExpression::prepend(
 469           DMI->getDebugExpression(), DIExpression::NoDeref, SpillOffset);
 470       MachineInstr *SpDMI =
 471           BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase,
 472                   DMI->getDebugVariable(), SpillExpr);
 473       DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
 474             SpDMI->print(dbgs(), false, TII));
 475
 476       // The newly created DBG_VALUE instruction SpDMI must be inserted after
 477       // MI. Keep track of the pairing.
 478       SpillDebugPair MIP = {&MI, SpDMI};
 479       Spills.push_back(MIP);
 480
 481       // End all previous ranges of Var.
 482       OpenRanges.erase(VarLocIDs[ID].Var);
 483
 484       // Add the VarLoc to OpenRanges.
 485       VarLoc VL(*SpDMI, LS);
 486       unsigned SpillLocID = VarLocIDs.insert(VL);
 487       OpenRanges.insert(SpillLocID, VL.Var);
 488       return;
 489     }
 490   }
 491 }
 492
 493 /// Terminate all open ranges at the end of the current basic block.
 494 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
 495                                              OpenRangesSet &OpenRanges,
 496                                              VarLocInMBB &OutLocs,
 497                                              const VarLocMap &VarLocIDs) {
 498   bool Changed = false;
 499   const MachineBasicBlock *CurMBB = MI.getParent();
 500   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
 501     return false;
 502
 503   if (OpenRanges.empty())
 504     return false;
 505
 506   DEBUG(for (unsigned ID : OpenRanges.getVarLocs()) {
 507           // Copy OpenRanges to OutLocs, if not already present.
 508           dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
 509         });
 510   VarLocSet &VLS = OutLocs[CurMBB];
 511   Changed = VLS |= OpenRanges.getVarLocs();
 512   OpenRanges.clear();
 513   return Changed;
 514 }
 515
 516 /// This routine creates OpenRanges and OutLocs.
 517 bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
 518                                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
 519                                SpillMap &Spills, bool transferSpills) {
 520   bool Changed = false;
 521   transferDebugValue(MI, OpenRanges, VarLocIDs);
 522   transferRegisterDef(MI, OpenRanges, VarLocIDs);
 523   if (transferSpills)
 524     transferSpillInst(MI, OpenRanges, VarLocIDs, Spills);
 525   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
 526   return Changed;
 527 }
 528
 529 /// This routine joins the analysis results of all incoming edges in @MBB by
 530 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 531 /// source variable in all the predecessors of @MBB reside in the same location.
 532 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
 533                            VarLocInMBB &InLocs, const VarLocMap &VarLocIDs,
 534                            SmallPtrSet<const MachineBasicBlock *, 16> &Visited) {
 535   DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
 536   bool Changed = false;
 537
 538   VarLocSet InLocsT; // Temporary incoming locations.
 539
 540   // For all predecessors of this MBB, find the set of VarLocs that
 541   // can be joined.
 542   int NumVisited = 0;
 543   for (auto p : MBB.predecessors()) {
 544     // Ignore unvisited predecessor blocks.  As we are processing
 545     // the blocks in reverse post-order any unvisited block can
 546     // be considered to not remove any incoming values.
 547     if (!Visited.count(p))
 548       continue;
 549     auto OL = OutLocs.find(p);
 550     // Join is null in case of empty OutLocs from any of the pred.
 551     if (OL == OutLocs.end())
 552       return false;
 553
 554     // Just copy over the Out locs to incoming locs for the first visited
 555     // predecessor, and for all other predecessors join the Out locs.
 556     if (!NumVisited)
 557       InLocsT = OL->second;
 558     else
 559       InLocsT &= OL->second;
 560     NumVisited++;
 561   }
 562
 563   // Filter out DBG_VALUES that are out of scope.
 564   VarLocSet KillSet;
 565   for (auto ID : InLocsT)
 566     if (!VarLocIDs[ID].dominates(MBB))
 567       KillSet.set(ID);
 568   InLocsT.intersectWithComplement(KillSet);
 569
 570   // As we are processing blocks in reverse post-order we
 571   // should have processed at least one predecessor, unless it
 572   // is the entry block which has no predecessor.
 573   assert((NumVisited || MBB.pred_empty()) &&
 574          "Should have processed at least one predecessor");
 575   if (InLocsT.empty())
 576     return false;
 577
 578   VarLocSet &ILS = InLocs[&MBB];
 579
 580   // Insert DBG_VALUE instructions, if not already inserted.
 581   VarLocSet Diff = InLocsT;
 582   Diff.intersectWithComplement(ILS);
 583   for (auto ID : Diff) {
 584     // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
 585     // new range is started for the var from the mbb's beginning by inserting
 586     // a new DBG_VALUE. transfer() will end this range however appropriate.
 587     const VarLoc &DiffIt = VarLocIDs[ID];
 588     const MachineInstr *DMI = &DiffIt.MI;
 589     MachineInstr *MI =
 590         BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
 591                 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(),
 592                 DMI->getDebugVariable(), DMI->getDebugExpression());
 593     if (DMI->isIndirectDebugValue())
 594       MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
 595     DEBUG(dbgs() << "Inserted: "; MI->dump(););
 596     ILS.set(ID);
 597     ++NumInserted;
 598     Changed = true;
 599   }
 600   return Changed;
 601 }
 602
 603 /// Calculate the liveness information for the given machine function and
 604 /// extend ranges across basic blocks.
 605 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 606   DEBUG(dbgs() << "\nDebug Range Extension\n");
 607
 608   bool Changed = false;
 609   bool OLChanged = false;
 610   bool MBBJoined = false;
 611
 612   VarLocMap VarLocIDs;      // Map VarLoc<>unique ID for use in bitvectors.
 613   OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
 614   VarLocInMBB OutLocs;      // Ranges that exist beyond bb.
 615   VarLocInMBB InLocs;       // Ranges that are incoming after joining.
 616   SpillMap Spills;          // DBG_VALUEs associated with spills.
 617
 618   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
 619   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
 620   std::priority_queue<unsigned int, std::vector<unsigned int>,
 621                       std::greater<unsigned int>>
 622       Worklist;
 623   std::priority_queue<unsigned int, std::vector<unsigned int>,
 624                       std::greater<unsigned int>>
 625       Pending;
 626
 627   // Initialize every mbb with OutLocs.
 628   // We are not looking at any spill instructions during the initial pass
 629   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
 630   // instructions for spills of registers that are known to be user variables
 631   // within the BB in which the spill occurs.
 632   for (auto &MBB : MF)
 633     for (auto &MI : MBB)
 634       transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
 635                /*transferSpills=*/false);
 636
 637   DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization",
 638                          dbgs()));
 639
 640   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
 641   unsigned int RPONumber = 0;
 642   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
 643     OrderToBB[RPONumber] = *RI;
 644     BBToOrder[*RI] = RPONumber;
 645     Worklist.push(RPONumber);
 646     ++RPONumber;
 647   }
 648   // This is a standard "union of predecessor outs" dataflow problem.
 649   // To solve it, we perform join() and transfer() using the two worklist method
 650   // until the ranges converge.
 651   // Ranges have converged when both worklists are empty.
 652   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
 653   while (!Worklist.empty() || !Pending.empty()) {
 654     // We track what is on the pending worklist to avoid inserting the same
 655     // thing twice.  We could avoid this with a custom priority queue, but this
 656     // is probably not worth it.
 657     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
 658     DEBUG(dbgs() << "Processing Worklist\n");
 659     while (!Worklist.empty()) {
 660       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
 661       Worklist.pop();
 662       MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited);
 663       Visited.insert(MBB);
 664       if (MBBJoined) {
 665         MBBJoined = false;
 666         Changed = true;
 667         // Now that we have started to extend ranges across BBs we need to
 668         // examine spill instructions to see whether they spill registers that
 669         // correspond to user variables.
 670         for (auto &MI : *MBB)
 671           OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs, Spills,
 672                                 /*transferSpills=*/true);
 673
 674         // Add any DBG_VALUE instructions necessitated by spills.
 675         for (auto &SP : Spills)
 676           MBB->insertAfter(MachineBasicBlock::iterator(*SP.SpillInst),
 677                            SP.DebugInst);
 678         Spills.clear();
 679
 680         DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
 681                                "OutLocs after propagating", dbgs()));
 682         DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
 683                                "InLocs after propagating", dbgs()));
 684
 685         if (OLChanged) {
 686           OLChanged = false;
 687           for (auto s : MBB->successors())
 688             if (OnPending.insert(s).second) {
 689               Pending.push(BBToOrder[s]);
 690             }
 691         }
 692       }
 693     }
 694     Worklist.swap(Pending);
 695     // At this point, pending must be empty, since it was just the empty
 696     // worklist
 697     assert(Pending.empty() && "Pending should be empty");
 698   }
 699
 700   DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
 701   DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
 702   return Changed;
 703 }
 704
 705 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
 706   if (!MF.getFunction().getSubprogram())
 707     // LiveDebugValues will already have removed all DBG_VALUEs.
 708     return false;
 709
 710   // Skip functions from NoDebug compilation units.
 711   if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
 712       DICompileUnit::NoDebug)
 713     return false;
 714
 715   TRI = MF.getSubtarget().getRegisterInfo();
 716   TII = MF.getSubtarget().getInstrInfo();
 717   TFI = MF.getSubtarget().getFrameLowering();
 718   LS.initialize(MF);
 719
 720   bool Changed = ExtendRanges(MF);
 721   return Changed;
 722 }