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/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
 263   bool ExtendRanges(MachineFunction &MF);
 264
 265 public:
 266   static char ID;
 267
 268   /// Default construct and initialize the pass.
 269   LiveDebugValues();
 270
 271   /// Tell the pass manager which passes we depend on and what
 272   /// information we preserve.
 273   void getAnalysisUsage(AnalysisUsage &AU) const override;
 274
 275   MachineFunctionProperties getRequiredProperties() const override {
 276     return MachineFunctionProperties().set(
 277         MachineFunctionProperties::Property::NoVRegs);
 278   }
 279
 280   /// Print to ostream with a message.
 281   void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
 282                         const VarLocMap &VarLocIDs, const char *msg,
 283                         raw_ostream &Out) const;
 284
 285   /// Calculate the liveness information for the given machine function.
 286   bool runOnMachineFunction(MachineFunction &MF) override;
 287 };
 288
 289 } // end anonymous namespace
 290
 291 //===----------------------------------------------------------------------===//
 292 //            Implementation
 293 //===----------------------------------------------------------------------===//
 294
 295 char LiveDebugValues::ID = 0;
 296
 297 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
 298
 299 INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
 300                 false, false)
 301
 302 /// Default construct and initialize the pass.
 303 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
 304   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
 305 }
 306
 307 /// Tell the pass manager which passes we depend on and what information we
 308 /// preserve.
 309 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
 310   AU.setPreservesCFG();
 311   MachineFunctionPass::getAnalysisUsage(AU);
 312 }
 313
 314 //===----------------------------------------------------------------------===//
 315 //            Debug Range Extension Implementation
 316 //===----------------------------------------------------------------------===//
 317
 318 #ifndef NDEBUG
 319 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
 320                                        const VarLocInMBB &V,
 321                                        const VarLocMap &VarLocIDs,
 322                                        const char *msg,
 323                                        raw_ostream &Out) const {
 324   Out << '\n' << msg << '\n';
 325   for (const MachineBasicBlock &BB : MF) {
 326     const auto &L = V.lookup(&BB);
 327     Out << "MBB: " << BB.getName() << ":\n";
 328     for (unsigned VLL : L) {
 329       const VarLoc &VL = VarLocIDs[VLL];
 330       Out << " Var: " << VL.Var.getVar()->getName();
 331       Out << " MI: ";
 332       VL.dump();
 333     }
 334   }
 335   Out << "\n";
 336 }
 337 #endif
 338
 339 /// Given a spill instruction, extract the register and offset used to
 340 /// address the spill location in a target independent way.
 341 int LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI,
 342                                                   unsigned &Reg) {
 343   assert(MI.hasOneMemOperand() &&
 344          "Spill instruction does not have exactly one memory operand?");
 345   auto MMOI = MI.memoperands_begin();
 346   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
 347   assert(PVal->kind() == PseudoSourceValue::FixedStack &&
 348          "Inconsistent memory operand in spill instruction");
 349   int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
 350   const MachineBasicBlock *MBB = MI.getParent();
 351   return TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
 352 }
 353
 354 /// End all previous ranges related to @MI and start a new range from @MI
 355 /// if it is a DBG_VALUE instr.
 356 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
 357                                          OpenRangesSet &OpenRanges,
 358                                          VarLocMap &VarLocIDs) {
 359   if (!MI.isDebugValue())
 360     return;
 361   const DILocalVariable *Var = MI.getDebugVariable();
 362   const DILocation *DebugLoc = MI.getDebugLoc();
 363   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
 364   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
 365          "Expected inlined-at fields to agree");
 366
 367   // End all previous ranges of Var.
 368   DebugVariable V(Var, InlinedAt);
 369   OpenRanges.erase(V);
 370
 371   // Add the VarLoc to OpenRanges from this DBG_VALUE.
 372   // TODO: Currently handles DBG_VALUE which has only reg as location.
 373   if (isDbgValueDescribedByReg(MI)) {
 374     VarLoc VL(MI, LS);
 375     unsigned ID = VarLocIDs.insert(VL);
 376     OpenRanges.insert(ID, VL.Var);
 377   }
 378 }
 379
 380 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
 381 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
 382 /// new VarLoc. If \p NewReg is different than default zero value then the
 383 /// new location will be register location created by the copy like instruction,
 384 /// otherwise it is variable's location on the stack.
 385 void LiveDebugValues::insertTransferDebugPair(
 386     MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
 387     VarLocMap &VarLocIDs, unsigned OldVarID, unsigned NewReg) {
 388   const MachineInstr *DMI = &VarLocIDs[OldVarID].MI;
 389   MachineFunction *MF = MI.getParent()->getParent();
 390   MachineInstr *NewDMI;
 391   if (NewReg) {
 392     // Create a DBG_VALUE instruction to describe the Var in its new
 393     // register location.
 394     NewDMI = BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(),
 395                      DMI->isIndirectDebugValue(), NewReg,
 396                      DMI->getDebugVariable(), DMI->getDebugExpression());
 397     if (DMI->isIndirectDebugValue())
 398       NewDMI->getOperand(1).setImm(DMI->getOperand(1).getImm());
 399     LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register copy: ";
 400                NewDMI->print(dbgs(), false, false, false, TII));
 401   } else {
 402     // Create a DBG_VALUE instruction to describe the Var in its spilled
 403     // location.
 404     unsigned SpillBase;
 405     int SpillOffset = extractSpillBaseRegAndOffset(MI, SpillBase);
 406     auto *SpillExpr = DIExpression::prepend(DMI->getDebugExpression(),
 407                                             DIExpression::NoDeref, SpillOffset);
 408     NewDMI = BuildMI(*MF, DMI->getDebugLoc(), DMI->getDesc(), true, SpillBase,
 409                      DMI->getDebugVariable(), SpillExpr);
 410     LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
 411                NewDMI->print(dbgs(), false, false, false, TII));
 412   }
 413
 414   // The newly created DBG_VALUE instruction NewDMI must be inserted after
 415   // MI. Keep track of the pairing.
 416   TransferDebugPair MIP = {&MI, NewDMI};
 417   Transfers.push_back(MIP);
 418
 419   // End all previous ranges of Var.
 420   OpenRanges.erase(VarLocIDs[OldVarID].Var);
 421
 422   // Add the VarLoc to OpenRanges.
 423   VarLoc VL(*NewDMI, LS);
 424   unsigned LocID = VarLocIDs.insert(VL);
 425   OpenRanges.insert(LocID, VL.Var);
 426 }
 427
 428 /// A definition of a register may mark the end of a range.
 429 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
 430                                           OpenRangesSet &OpenRanges,
 431                                           const VarLocMap &VarLocIDs) {
 432   MachineFunction *MF = MI.getMF();
 433   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
 434   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
 435   SparseBitVector<> KillSet;
 436   for (const MachineOperand &MO : MI.operands()) {
 437     // Determine whether the operand is a register def.  Assume that call
 438     // instructions never clobber SP, because some backends (e.g., AArch64)
 439     // never list SP in the regmask.
 440     if (MO.isReg() && MO.isDef() && MO.getReg() &&
 441         TRI->isPhysicalRegister(MO.getReg()) &&
 442         !(MI.isCall() && MO.getReg() == SP)) {
 443       // Remove ranges of all aliased registers.
 444       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
 445         for (unsigned ID : OpenRanges.getVarLocs())
 446           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
 447             KillSet.set(ID);
 448     } else if (MO.isRegMask()) {
 449       // Remove ranges of all clobbered registers. Register masks don't usually
 450       // list SP as preserved.  While the debug info may be off for an
 451       // instruction or two around callee-cleanup calls, transferring the
 452       // DEBUG_VALUE across the call is still a better user experience.
 453       for (unsigned ID : OpenRanges.getVarLocs()) {
 454         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
 455         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
 456           KillSet.set(ID);
 457       }
 458     }
 459   }
 460   OpenRanges.erase(KillSet, VarLocIDs);
 461 }
 462
 463 /// Decide if @MI is a spill instruction and return true if it is. We use 2
 464 /// criteria to make this decision:
 465 /// - Is this instruction a store to a spill slot?
 466 /// - Is there a register operand that is both used and killed?
 467 /// TODO: Store optimization can fold spills into other stores (including
 468 /// other spills). We do not handle this yet (more than one memory operand).
 469 bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
 470                                          MachineFunction *MF, unsigned &Reg) {
 471   const MachineFrameInfo &FrameInfo = MF->getFrameInfo();
 472   int FI;
 473   const MachineMemOperand *MMO;
 474
 475   // TODO: Handle multiple stores folded into one.
 476   if (!MI.hasOneMemOperand())
 477     return false;
 478
 479   // To identify a spill instruction, use the same criteria as in AsmPrinter.
 480   if (!((TII->isStoreToStackSlotPostFE(MI, FI) ||
 481          TII->hasStoreToStackSlot(MI, MMO, FI)) &&
 482         FrameInfo.isSpillSlotObjectIndex(FI)))
 483     return false;
 484
 485   auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
 486     if (!MO.isReg() || !MO.isUse()) {
 487       Reg = 0;
 488       return false;
 489     }
 490     Reg = MO.getReg();
 491     return MO.isKill();
 492   };
 493
 494   for (const MachineOperand &MO : MI.operands()) {
 495     // In a spill instruction generated by the InlineSpiller the spilled
 496     // register has its kill flag set.
 497     if (isKilledReg(MO, Reg))
 498       return true;
 499     if (Reg != 0) {
 500       // Check whether next instruction kills the spilled register.
 501       // FIXME: Current solution does not cover search for killed register in
 502       // bundles and instructions further down the chain.
 503       auto NextI = std::next(MI.getIterator());
 504       // Skip next instruction that points to basic block end iterator.
 505       if (MI.getParent()->end() == NextI)
 506         continue;
 507       unsigned RegNext;
 508       for (const MachineOperand &MONext : NextI->operands()) {
 509         // Return true if we came across the register from the
 510         // previous spill instruction that is killed in NextI.
 511         if (isKilledReg(MONext, RegNext) && RegNext == Reg)
 512           return true;
 513       }
 514     }
 515   }
 516   // Return false if we didn't find spilled register.
 517   return false;
 518 }
 519
 520 /// A spilled register may indicate that we have to end the current range of
 521 /// a variable and create a new one for the spill location.
 522 /// We don't want to insert any instructions in process(), so we just create
 523 /// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
 524 /// It will be inserted into the BB when we're done iterating over the
 525 /// instructions.
 526 void LiveDebugValues::transferSpillInst(MachineInstr &MI,
 527                                         OpenRangesSet &OpenRanges,
 528                                         VarLocMap &VarLocIDs,
 529                                         TransferMap &Transfers) {
 530   unsigned Reg;
 531   MachineFunction *MF = MI.getMF();
 532   if (!isSpillInstruction(MI, MF, Reg))
 533     return;
 534
 535   // Check if the register is the location of a debug value.
 536   for (unsigned ID : OpenRanges.getVarLocs()) {
 537     if (VarLocIDs[ID].isDescribedByReg() == Reg) {
 538       LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
 539                         << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
 540       insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID);
 541       return;
 542     }
 543   }
 544 }
 545
 546 /// If \p MI is a register copy instruction, that copies a previously tracked
 547 /// value from one register to another register that is callee saved, we
 548 /// create new DBG_VALUE instruction  described with copy destination register.
 549 void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
 550                                            OpenRangesSet &OpenRanges,
 551                                            VarLocMap &VarLocIDs,
 552                                            TransferMap &Transfers) {
 553   const MachineOperand *SrcRegOp, *DestRegOp;
 554
 555   if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() ||
 556       !DestRegOp->isDef())
 557     return;
 558
 559   auto isCalleSavedReg = [&](unsigned Reg) {
 560     for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
 561       if (CalleeSavedRegs.test(*RAI))
 562         return true;
 563     return false;
 564   };
 565
 566   unsigned SrcReg = SrcRegOp->getReg();
 567   unsigned DestReg = DestRegOp->getReg();
 568
 569   // We want to recognize instructions where destination register is callee
 570   // saved register. If register that could be clobbered by the call is
 571   // included, there would be a great chance that it is going to be clobbered
 572   // soon. It is more likely that previous register location, which is callee
 573   // saved, is going to stay unclobbered longer, even if it is killed.
 574   if (!isCalleSavedReg(DestReg))
 575     return;
 576
 577   for (unsigned ID : OpenRanges.getVarLocs()) {
 578     if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
 579       insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
 580                               DestReg);
 581       return;
 582     }
 583   }
 584 }
 585
 586 /// Terminate all open ranges at the end of the current basic block.
 587 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
 588                                              OpenRangesSet &OpenRanges,
 589                                              VarLocInMBB &OutLocs,
 590                                              const VarLocMap &VarLocIDs) {
 591   bool Changed = false;
 592   const MachineBasicBlock *CurMBB = MI.getParent();
 593   if (!(MI.isTerminator() || (&MI == &CurMBB->back())))
 594     return false;
 595
 596   if (OpenRanges.empty())
 597     return false;
 598
 599   LLVM_DEBUG(for (unsigned ID
 600                   : OpenRanges.getVarLocs()) {
 601     // Copy OpenRanges to OutLocs, if not already present.
 602     dbgs() << "Add to OutLocs: ";
 603     VarLocIDs[ID].dump();
 604   });
 605   VarLocSet &VLS = OutLocs[CurMBB];
 606   Changed = VLS |= OpenRanges.getVarLocs();
 607   OpenRanges.clear();
 608   return Changed;
 609 }
 610
 611 /// This routine creates OpenRanges and OutLocs.
 612 bool LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
 613                               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
 614                               TransferMap &Transfers, bool transferChanges) {
 615   bool Changed = false;
 616   transferDebugValue(MI, OpenRanges, VarLocIDs);
 617   transferRegisterDef(MI, OpenRanges, VarLocIDs);
 618   if (transferChanges) {
 619     transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
 620     transferSpillInst(MI, OpenRanges, VarLocIDs, Transfers);
 621   }
 622   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
 623   return Changed;
 624 }
 625
 626 /// This routine joins the analysis results of all incoming edges in @MBB by
 627 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 628 /// source variable in all the predecessors of @MBB reside in the same location.
 629 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
 630                            VarLocInMBB &InLocs, const VarLocMap &VarLocIDs,
 631                            SmallPtrSet<const MachineBasicBlock *, 16> &Visited) {
 632   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
 633   bool Changed = false;
 634
 635   VarLocSet InLocsT; // Temporary incoming locations.
 636
 637   // For all predecessors of this MBB, find the set of VarLocs that
 638   // can be joined.
 639   int NumVisited = 0;
 640   for (auto p : MBB.predecessors()) {
 641     // Ignore unvisited predecessor blocks.  As we are processing
 642     // the blocks in reverse post-order any unvisited block can
 643     // be considered to not remove any incoming values.
 644     if (!Visited.count(p))
 645       continue;
 646     auto OL = OutLocs.find(p);
 647     // Join is null in case of empty OutLocs from any of the pred.
 648     if (OL == OutLocs.end())
 649       return false;
 650
 651     // Just copy over the Out locs to incoming locs for the first visited
 652     // predecessor, and for all other predecessors join the Out locs.
 653     if (!NumVisited)
 654       InLocsT = OL->second;
 655     else
 656       InLocsT &= OL->second;
 657     NumVisited++;
 658   }
 659
 660   // Filter out DBG_VALUES that are out of scope.
 661   VarLocSet KillSet;
 662   for (auto ID : InLocsT)
 663     if (!VarLocIDs[ID].dominates(MBB))
 664       KillSet.set(ID);
 665   InLocsT.intersectWithComplement(KillSet);
 666
 667   // As we are processing blocks in reverse post-order we
 668   // should have processed at least one predecessor, unless it
 669   // is the entry block which has no predecessor.
 670   assert((NumVisited || MBB.pred_empty()) &&
 671          "Should have processed at least one predecessor");
 672   if (InLocsT.empty())
 673     return false;
 674
 675   VarLocSet &ILS = InLocs[&MBB];
 676
 677   // Insert DBG_VALUE instructions, if not already inserted.
 678   VarLocSet Diff = InLocsT;
 679   Diff.intersectWithComplement(ILS);
 680   for (auto ID : Diff) {
 681     // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
 682     // new range is started for the var from the mbb's beginning by inserting
 683     // a new DBG_VALUE. process() will end this range however appropriate.
 684     const VarLoc &DiffIt = VarLocIDs[ID];
 685     const MachineInstr *DMI = &DiffIt.MI;
 686     MachineInstr *MI =
 687         BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
 688                 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(),
 689                 DMI->getDebugVariable(), DMI->getDebugExpression());
 690     if (DMI->isIndirectDebugValue())
 691       MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
 692     LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
 693     ILS.set(ID);
 694     ++NumInserted;
 695     Changed = true;
 696   }
 697   return Changed;
 698 }
 699
 700 /// Calculate the liveness information for the given machine function and
 701 /// extend ranges across basic blocks.
 702 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 703   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
 704
 705   bool Changed = false;
 706   bool OLChanged = false;
 707   bool MBBJoined = false;
 708
 709   VarLocMap VarLocIDs;      // Map VarLoc<>unique ID for use in bitvectors.
 710   OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
 711   VarLocInMBB OutLocs;      // Ranges that exist beyond bb.
 712   VarLocInMBB InLocs;       // Ranges that are incoming after joining.
 713   TransferMap Transfers;    // DBG_VALUEs associated with spills.
 714
 715   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
 716   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
 717   std::priority_queue<unsigned int, std::vector<unsigned int>,
 718                       std::greater<unsigned int>>
 719       Worklist;
 720   std::priority_queue<unsigned int, std::vector<unsigned int>,
 721                       std::greater<unsigned int>>
 722       Pending;
 723
 724   enum : bool { dontTransferChanges = false, transferChanges = true };
 725
 726   // Initialize every mbb with OutLocs.
 727   // We are not looking at any spill instructions during the initial pass
 728   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
 729   // instructions for spills of registers that are known to be user variables
 730   // within the BB in which the spill occurs.
 731   for (auto &MBB : MF)
 732     for (auto &MI : MBB)
 733       process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
 734               dontTransferChanges);
 735
 736   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
 737                               "OutLocs after initialization", dbgs()));
 738
 739   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
 740   unsigned int RPONumber = 0;
 741   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
 742     OrderToBB[RPONumber] = *RI;
 743     BBToOrder[*RI] = RPONumber;
 744     Worklist.push(RPONumber);
 745     ++RPONumber;
 746   }
 747   // This is a standard "union of predecessor outs" dataflow problem.
 748   // To solve it, we perform join() and process() using the two worklist method
 749   // until the ranges converge.
 750   // Ranges have converged when both worklists are empty.
 751   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
 752   while (!Worklist.empty() || !Pending.empty()) {
 753     // We track what is on the pending worklist to avoid inserting the same
 754     // thing twice.  We could avoid this with a custom priority queue, but this
 755     // is probably not worth it.
 756     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
 757     LLVM_DEBUG(dbgs() << "Processing Worklist\n");
 758     while (!Worklist.empty()) {
 759       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
 760       Worklist.pop();
 761       MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited);
 762       Visited.insert(MBB);
 763       if (MBBJoined) {
 764         MBBJoined = false;
 765         Changed = true;
 766         // Now that we have started to extend ranges across BBs we need to
 767         // examine spill instructions to see whether they spill registers that
 768         // correspond to user variables.
 769         for (auto &MI : *MBB)
 770           OLChanged |= process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
 771                                transferChanges);
 772
 773         // Add any DBG_VALUE instructions necessitated by spills.
 774         for (auto &TR : Transfers)
 775           MBB->insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
 776                            TR.DebugInst);
 777         Transfers.clear();
 778
 779         LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
 780                                     "OutLocs after propagating", dbgs()));
 781         LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
 782                                     "InLocs after propagating", dbgs()));
 783
 784         if (OLChanged) {
 785           OLChanged = false;
 786           for (auto s : MBB->successors())
 787             if (OnPending.insert(s).second) {
 788               Pending.push(BBToOrder[s]);
 789             }
 790         }
 791       }
 792     }
 793     Worklist.swap(Pending);
 794     // At this point, pending must be empty, since it was just the empty
 795     // worklist
 796     assert(Pending.empty() && "Pending should be empty");
 797   }
 798
 799   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
 800   LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
 801   return Changed;
 802 }
 803
 804 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
 805   if (!MF.getFunction().getSubprogram())
 806     // LiveDebugValues will already have removed all DBG_VALUEs.
 807     return false;
 808
 809   // Skip functions from NoDebug compilation units.
 810   if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
 811       DICompileUnit::NoDebug)
 812     return false;
 813
 814   TRI = MF.getSubtarget().getRegisterInfo();
 815   TII = MF.getSubtarget().getInstrInfo();
 816   TFI = MF.getSubtarget().getFrameLowering();
 817   TFI->determineCalleeSaves(MF, CalleeSavedRegs,
 818                             make_unique<RegScavenger>().get());
 819   LS.initialize(MF);
 820
 821   bool Changed = ExtendRanges(MF);
 822   return Changed;
 823 }