lib/CodeGen/LiveDebugValues.cpp

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