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