contrib/llvm/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/SmallSet.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/RegisterScavenging.h"
  39 #include "llvm/CodeGen/TargetFrameLowering.h"
  40 #include "llvm/CodeGen/TargetInstrInfo.h"
  41 #include "llvm/CodeGen/TargetLowering.h"
  42 #include "llvm/CodeGen/TargetPassConfig.h"
  43 #include "llvm/CodeGen/TargetRegisterInfo.h"
  44 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  45 #include "llvm/Config/llvm-config.h"
  46 #include "llvm/IR/DIBuilder.h"
  47 #include "llvm/IR/DebugInfoMetadata.h"
  48 #include "llvm/IR/DebugLoc.h"
  49 #include "llvm/IR/Function.h"
  50 #include "llvm/IR/Module.h"
  51 #include "llvm/MC/MCRegisterInfo.h"
  52 #include "llvm/Pass.h"
  53 #include "llvm/Support/Casting.h"
  54 #include "llvm/Support/Compiler.h"
  55 #include "llvm/Support/Debug.h"
  56 #include "llvm/Support/raw_ostream.h"
  57 #include <algorithm>
  58 #include <cassert>
  59 #include <cstdint>
  60 #include <functional>
  61 #include <queue>
  62 #include <tuple>
  63 #include <utility>
  64 #include <vector>
  65
  66 using namespace llvm;
  67
  68 #define DEBUG_TYPE "livedebugvalues"
  69
  70 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
  71
  72 // If @MI is a DBG_VALUE with debug value described by a defined
  73 // register, returns the number of this register. In the other case, returns 0.
  74 static Register isDbgValueDescribedByReg(const MachineInstr &MI) {
  75   assert(MI.isDebugValue() && "expected a DBG_VALUE");
  76   assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
  77   // If location of variable is described using a register (directly
  78   // or indirectly), this register is always a first operand.
  79   return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : Register();
  80 }
  81
  82 namespace {
  83
  84 class LiveDebugValues : public MachineFunctionPass {
  85 private:
  86   const TargetRegisterInfo *TRI;
  87   const TargetInstrInfo *TII;
  88   const TargetFrameLowering *TFI;
  89   BitVector CalleeSavedRegs;
  90   LexicalScopes LS;
  91
  92   enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
  93
  94   /// Keeps track of lexical scopes associated with a user value's source
  95   /// location.
  96   class UserValueScopes {
  97     DebugLoc DL;
  98     LexicalScopes &LS;
  99     SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
 100
 101   public:
 102     UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {}
 103
 104     /// Return true if current scope dominates at least one machine
 105     /// instruction in a given machine basic block.
 106     bool dominates(MachineBasicBlock *MBB) {
 107       if (LBlocks.empty())
 108         LS.getMachineBasicBlocks(DL, LBlocks);
 109       return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB);
 110     }
 111   };
 112
 113   using FragmentInfo = DIExpression::FragmentInfo;
 114   using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
 115
 116   /// Storage for identifying a potentially inlined instance of a variable,
 117   /// or a fragment thereof.
 118   class DebugVariable {
 119     const DILocalVariable *Variable;
 120     OptFragmentInfo Fragment;
 121     const DILocation *InlinedAt;
 122
 123     /// Fragment that will overlap all other fragments. Used as default when
 124     /// caller demands a fragment.
 125     static const FragmentInfo DefaultFragment;
 126
 127   public:
 128     DebugVariable(const DILocalVariable *Var, OptFragmentInfo &&FragmentInfo,
 129                   const DILocation *InlinedAt)
 130         : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {}
 131
 132     DebugVariable(const DILocalVariable *Var, OptFragmentInfo &FragmentInfo,
 133                   const DILocation *InlinedAt)
 134         : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {}
 135
 136     DebugVariable(const DILocalVariable *Var, const DIExpression *DIExpr,
 137                   const DILocation *InlinedAt)
 138         : DebugVariable(Var, DIExpr->getFragmentInfo(), InlinedAt) {}
 139
 140     DebugVariable(const MachineInstr &MI)
 141         : DebugVariable(MI.getDebugVariable(),
 142                         MI.getDebugExpression()->getFragmentInfo(),
 143                         MI.getDebugLoc()->getInlinedAt()) {}
 144
 145     const DILocalVariable *getVar() const { return Variable; }
 146     const OptFragmentInfo &getFragment() const { return Fragment; }
 147     const DILocation *getInlinedAt() const { return InlinedAt; }
 148
 149     const FragmentInfo getFragmentDefault() const {
 150       return Fragment.getValueOr(DefaultFragment);
 151     }
 152
 153     static bool isFragmentDefault(FragmentInfo &F) {
 154       return F == DefaultFragment;
 155     }
 156
 157     bool operator==(const DebugVariable &Other) const {
 158       return std::tie(Variable, Fragment, InlinedAt) ==
 159              std::tie(Other.Variable, Other.Fragment, Other.InlinedAt);
 160     }
 161
 162     bool operator<(const DebugVariable &Other) const {
 163       return std::tie(Variable, Fragment, InlinedAt) <
 164              std::tie(Other.Variable, Other.Fragment, Other.InlinedAt);
 165     }
 166   };
 167
 168   friend struct llvm::DenseMapInfo<DebugVariable>;
 169
 170   /// A pair of debug variable and value location.
 171   struct VarLoc {
 172     // The location at which a spilled variable resides. It consists of a
 173     // register and an offset.
 174     struct SpillLoc {
 175       unsigned SpillBase;
 176       int SpillOffset;
 177       bool operator==(const SpillLoc &Other) const {
 178         return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset;
 179       }
 180     };
 181
 182     const DebugVariable Var;
 183     const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
 184     mutable UserValueScopes UVS;
 185     enum VarLocKind {
 186       InvalidKind = 0,
 187       RegisterKind,
 188       SpillLocKind,
 189       ImmediateKind,
 190       EntryValueKind
 191     } Kind = InvalidKind;
 192
 193     /// The value location. Stored separately to avoid repeatedly
 194     /// extracting it from MI.
 195     union {
 196       uint64_t RegNo;
 197       SpillLoc SpillLocation;
 198       uint64_t Hash;
 199       int64_t Immediate;
 200       const ConstantFP *FPImm;
 201       const ConstantInt *CImm;
 202     } Loc;
 203
 204     VarLoc(const MachineInstr &MI, LexicalScopes &LS,
 205           VarLocKind K = InvalidKind)
 206         : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS){
 207       static_assert((sizeof(Loc) == sizeof(uint64_t)),
 208                     "hash does not cover all members of Loc");
 209       assert(MI.isDebugValue() && "not a DBG_VALUE");
 210       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
 211       if (int RegNo = isDbgValueDescribedByReg(MI)) {
 212         Kind = MI.isDebugEntryValue() ? EntryValueKind : RegisterKind;
 213         Loc.RegNo = RegNo;
 214       } else if (MI.getOperand(0).isImm()) {
 215         Kind = ImmediateKind;
 216         Loc.Immediate = MI.getOperand(0).getImm();
 217       } else if (MI.getOperand(0).isFPImm()) {
 218         Kind = ImmediateKind;
 219         Loc.FPImm = MI.getOperand(0).getFPImm();
 220       } else if (MI.getOperand(0).isCImm()) {
 221         Kind = ImmediateKind;
 222         Loc.CImm = MI.getOperand(0).getCImm();
 223       }
 224       assert((Kind != ImmediateKind || !MI.isDebugEntryValue()) &&
 225              "entry values must be register locations");
 226     }
 227
 228     /// The constructor for spill locations.
 229     VarLoc(const MachineInstr &MI, unsigned SpillBase, int SpillOffset,
 230            LexicalScopes &LS)
 231         : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS) {
 232       assert(MI.isDebugValue() && "not a DBG_VALUE");
 233       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
 234       Kind = SpillLocKind;
 235       Loc.SpillLocation = {SpillBase, SpillOffset};
 236     }
 237
 238     // Is the Loc field a constant or constant object?
 239     bool isConstant() const { return Kind == ImmediateKind; }
 240
 241     /// If this variable is described by a register, return it,
 242     /// otherwise return 0.
 243     unsigned isDescribedByReg() const {
 244       if (Kind == RegisterKind)
 245         return Loc.RegNo;
 246       return 0;
 247     }
 248
 249     /// Determine whether the lexical scope of this value's debug location
 250     /// dominates MBB.
 251     bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
 252
 253 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 254     LLVM_DUMP_METHOD void dump() const { MI.dump(); }
 255 #endif
 256
 257     bool operator==(const VarLoc &Other) const {
 258       return Kind == Other.Kind && Var == Other.Var &&
 259              Loc.Hash == Other.Loc.Hash;
 260     }
 261
 262     /// This operator guarantees that VarLocs are sorted by Variable first.
 263     bool operator<(const VarLoc &Other) const {
 264       return std::tie(Var, Kind, Loc.Hash) <
 265              std::tie(Other.Var, Other.Kind, Other.Loc.Hash);
 266     }
 267   };
 268
 269   using DebugParamMap = SmallDenseMap<const DILocalVariable *, MachineInstr *>;
 270   using VarLocMap = UniqueVector<VarLoc>;
 271   using VarLocSet = SparseBitVector<>;
 272   using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
 273   struct TransferDebugPair {
 274     MachineInstr *TransferInst;
 275     MachineInstr *DebugInst;
 276   };
 277   using TransferMap = SmallVector<TransferDebugPair, 4>;
 278
 279   // Types for recording sets of variable fragments that overlap. For a given
 280   // local variable, we record all other fragments of that variable that could
 281   // overlap it, to reduce search time.
 282   using FragmentOfVar =
 283       std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
 284   using OverlapMap =
 285       DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
 286
 287   // Helper while building OverlapMap, a map of all fragments seen for a given
 288   // DILocalVariable.
 289   using VarToFragments =
 290       DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
 291
 292   /// This holds the working set of currently open ranges. For fast
 293   /// access, this is done both as a set of VarLocIDs, and a map of
 294   /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
 295   /// previous open ranges for the same variable.
 296   class OpenRangesSet {
 297     VarLocSet VarLocs;
 298     SmallDenseMap<DebugVariable, unsigned, 8> Vars;
 299     OverlapMap &OverlappingFragments;
 300
 301   public:
 302     OpenRangesSet(OverlapMap &_OLapMap) : OverlappingFragments(_OLapMap) {}
 303
 304     const VarLocSet &getVarLocs() const { return VarLocs; }
 305
 306     /// Terminate all open ranges for Var by removing it from the set.
 307     void erase(DebugVariable Var);
 308
 309     /// Terminate all open ranges listed in \c KillSet by removing
 310     /// them from the set.
 311     void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
 312       VarLocs.intersectWithComplement(KillSet);
 313       for (unsigned ID : KillSet)
 314         Vars.erase(VarLocIDs[ID].Var);
 315     }
 316
 317     /// Insert a new range into the set.
 318     void insert(unsigned VarLocID, DebugVariable Var) {
 319       VarLocs.set(VarLocID);
 320       Vars.insert({Var, VarLocID});
 321     }
 322
 323     /// Empty the set.
 324     void clear() {
 325       VarLocs.clear();
 326       Vars.clear();
 327     }
 328
 329     /// Return whether the set is empty or not.
 330     bool empty() const {
 331       assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
 332       return VarLocs.empty();
 333     }
 334   };
 335
 336   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF,
 337                           unsigned &Reg);
 338   /// If a given instruction is identified as a spill, return the spill location
 339   /// and set \p Reg to the spilled register.
 340   Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
 341                                                   MachineFunction *MF,
 342                                                   unsigned &Reg);
 343   /// Given a spill instruction, extract the register and offset used to
 344   /// address the spill location in a target independent way.
 345   VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
 346   void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
 347                                TransferMap &Transfers, VarLocMap &VarLocIDs,
 348                                unsigned OldVarID, TransferKind Kind,
 349                                unsigned NewReg = 0);
 350
 351   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
 352                           VarLocMap &VarLocIDs);
 353   void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
 354                                   VarLocMap &VarLocIDs, TransferMap &Transfers);
 355   void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
 356                        VarLocMap &VarLocIDs, TransferMap &Transfers,
 357                        DebugParamMap &DebugEntryVals,
 358                        SparseBitVector<> &KillSet);
 359   void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
 360                             VarLocMap &VarLocIDs, TransferMap &Transfers);
 361   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
 362                            VarLocMap &VarLocIDs, TransferMap &Transfers,
 363                            DebugParamMap &DebugEntryVals);
 364   bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
 365                               VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
 366
 367   bool process(MachineInstr &MI, OpenRangesSet &OpenRanges,
 368                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
 369                TransferMap &Transfers, DebugParamMap &DebugEntryVals,
 370                bool transferChanges, OverlapMap &OverlapFragments,
 371                VarToFragments &SeenFragments);
 372
 373   void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
 374                              OverlapMap &OLapMap);
 375
 376   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
 377             const VarLocMap &VarLocIDs,
 378             SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
 379             SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks);
 380
 381   bool ExtendRanges(MachineFunction &MF);
 382
 383 public:
 384   static char ID;
 385
 386   /// Default construct and initialize the pass.
 387   LiveDebugValues();
 388
 389   /// Tell the pass manager which passes we depend on and what
 390   /// information we preserve.
 391   void getAnalysisUsage(AnalysisUsage &AU) const override;
 392
 393   MachineFunctionProperties getRequiredProperties() const override {
 394     return MachineFunctionProperties().set(
 395         MachineFunctionProperties::Property::NoVRegs);
 396   }
 397
 398   /// Print to ostream with a message.
 399   void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
 400                         const VarLocMap &VarLocIDs, const char *msg,
 401                         raw_ostream &Out) const;
 402
 403   /// Calculate the liveness information for the given machine function.
 404   bool runOnMachineFunction(MachineFunction &MF) override;
 405 };
 406
 407 } // end anonymous namespace
 408
 409 namespace llvm {
 410
 411 template <> struct DenseMapInfo<LiveDebugValues::DebugVariable> {
 412   using DV = LiveDebugValues::DebugVariable;
 413   using OptFragmentInfo = LiveDebugValues::OptFragmentInfo;
 414   using FragmentInfo = LiveDebugValues::FragmentInfo;
 415
 416   // Empty key: no key should be generated that has no DILocalVariable.
 417   static inline DV getEmptyKey() {
 418     return DV(nullptr, OptFragmentInfo(), nullptr);
 419   }
 420
 421   // Difference in tombstone is that the Optional is meaningful
 422   static inline DV getTombstoneKey() {
 423     return DV(nullptr, OptFragmentInfo({0, 0}), nullptr);
 424   }
 425
 426   static unsigned getHashValue(const DV &D) {
 427     unsigned HV = 0;
 428     const OptFragmentInfo &Fragment = D.getFragment();
 429     if (Fragment)
 430       HV = DenseMapInfo<FragmentInfo>::getHashValue(*Fragment);
 431
 432     return hash_combine(D.getVar(), HV, D.getInlinedAt());
 433   }
 434
 435   static bool isEqual(const DV &A, const DV &B) { return A == B; }
 436 };
 437
 438 } // namespace llvm
 439
 440 //===----------------------------------------------------------------------===//
 441 //            Implementation
 442 //===----------------------------------------------------------------------===//
 443
 444 const DIExpression::FragmentInfo
 445     LiveDebugValues::DebugVariable::DefaultFragment = {
 446         std::numeric_limits<uint64_t>::max(),
 447         std::numeric_limits<uint64_t>::min()};
 448
 449 char LiveDebugValues::ID = 0;
 450
 451 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
 452
 453 INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
 454                 false, false)
 455
 456 /// Default construct and initialize the pass.
 457 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
 458   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
 459 }
 460
 461 /// Tell the pass manager which passes we depend on and what information we
 462 /// preserve.
 463 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
 464   AU.setPreservesCFG();
 465   MachineFunctionPass::getAnalysisUsage(AU);
 466 }
 467
 468 /// Erase a variable from the set of open ranges, and additionally erase any
 469 /// fragments that may overlap it.
 470 void LiveDebugValues::OpenRangesSet::erase(DebugVariable Var) {
 471   // Erasure helper.
 472   auto DoErase = [this](DebugVariable VarToErase) {
 473     auto It = Vars.find(VarToErase);
 474     if (It != Vars.end()) {
 475       unsigned ID = It->second;
 476       VarLocs.reset(ID);
 477       Vars.erase(It);
 478     }
 479   };
 480
 481   // Erase the variable/fragment that ends here.
 482   DoErase(Var);
 483
 484   // Extract the fragment. Interpret an empty fragment as one that covers all
 485   // possible bits.
 486   FragmentInfo ThisFragment = Var.getFragmentDefault();
 487
 488   // There may be fragments that overlap the designated fragment. Look them up
 489   // in the pre-computed overlap map, and erase them too.
 490   auto MapIt = OverlappingFragments.find({Var.getVar(), ThisFragment});
 491   if (MapIt != OverlappingFragments.end()) {
 492     for (auto Fragment : MapIt->second) {
 493       LiveDebugValues::OptFragmentInfo FragmentHolder;
 494       if (!DebugVariable::isFragmentDefault(Fragment))
 495         FragmentHolder = LiveDebugValues::OptFragmentInfo(Fragment);
 496       DoErase({Var.getVar(), FragmentHolder, Var.getInlinedAt()});
 497     }
 498   }
 499 }
 500
 501 //===----------------------------------------------------------------------===//
 502 //            Debug Range Extension Implementation
 503 //===----------------------------------------------------------------------===//
 504
 505 #ifndef NDEBUG
 506 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
 507                                        const VarLocInMBB &V,
 508                                        const VarLocMap &VarLocIDs,
 509                                        const char *msg,
 510                                        raw_ostream &Out) const {
 511   Out << '\n' << msg << '\n';
 512   for (const MachineBasicBlock &BB : MF) {
 513     const VarLocSet &L = V.lookup(&BB);
 514     if (L.empty())
 515       continue;
 516     Out << "MBB: " << BB.getNumber() << ":\n";
 517     for (unsigned VLL : L) {
 518       const VarLoc &VL = VarLocIDs[VLL];
 519       Out << " Var: " << VL.Var.getVar()->getName();
 520       Out << " MI: ";
 521       VL.dump();
 522     }
 523   }
 524   Out << "\n";
 525 }
 526 #endif
 527
 528 LiveDebugValues::VarLoc::SpillLoc
 529 LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
 530   assert(MI.hasOneMemOperand() &&
 531          "Spill instruction does not have exactly one memory operand?");
 532   auto MMOI = MI.memoperands_begin();
 533   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
 534   assert(PVal->kind() == PseudoSourceValue::FixedStack &&
 535          "Inconsistent memory operand in spill instruction");
 536   int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
 537   const MachineBasicBlock *MBB = MI.getParent();
 538   unsigned Reg;
 539   int Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
 540   return {Reg, Offset};
 541 }
 542
 543 /// End all previous ranges related to @MI and start a new range from @MI
 544 /// if it is a DBG_VALUE instr.
 545 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
 546                                          OpenRangesSet &OpenRanges,
 547                                          VarLocMap &VarLocIDs) {
 548   if (!MI.isDebugValue())
 549     return;
 550   const DILocalVariable *Var = MI.getDebugVariable();
 551   const DIExpression *Expr = MI.getDebugExpression();
 552   const DILocation *DebugLoc = MI.getDebugLoc();
 553   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
 554   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
 555          "Expected inlined-at fields to agree");
 556
 557   // End all previous ranges of Var.
 558   DebugVariable V(Var, Expr, InlinedAt);
 559   OpenRanges.erase(V);
 560
 561   // Add the VarLoc to OpenRanges from this DBG_VALUE.
 562   unsigned ID;
 563   if (isDbgValueDescribedByReg(MI) || MI.getOperand(0).isImm() ||
 564       MI.getOperand(0).isFPImm() || MI.getOperand(0).isCImm()) {
 565     // Use normal VarLoc constructor for registers and immediates.
 566     VarLoc VL(MI, LS);
 567     ID = VarLocIDs.insert(VL);
 568     OpenRanges.insert(ID, VL.Var);
 569   } else if (MI.hasOneMemOperand()) {
 570     // It's a stack spill -- fetch spill base and offset.
 571     VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
 572     VarLoc VL(MI, SpillLocation.SpillBase, SpillLocation.SpillOffset, LS);
 573     ID = VarLocIDs.insert(VL);
 574     OpenRanges.insert(ID, VL.Var);
 575   } else {
 576     // This must be an undefined location. We should leave OpenRanges closed.
 577     assert(MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == 0 &&
 578            "Unexpected non-undef DBG_VALUE encountered");
 579   }
 580 }
 581
 582 void LiveDebugValues::emitEntryValues(MachineInstr &MI,
 583                                       OpenRangesSet &OpenRanges,
 584                                       VarLocMap &VarLocIDs,
 585                                       TransferMap &Transfers,
 586                                       DebugParamMap &DebugEntryVals,
 587                                       SparseBitVector<> &KillSet) {
 588   MachineFunction *MF = MI.getParent()->getParent();
 589   for (unsigned ID : KillSet) {
 590     if (!VarLocIDs[ID].Var.getVar()->isParameter())
 591       continue;
 592
 593     const MachineInstr *CurrDebugInstr = &VarLocIDs[ID].MI;
 594
 595     // If parameter's DBG_VALUE is not in the map that means we can't
 596     // generate parameter's entry value.
 597     if (!DebugEntryVals.count(CurrDebugInstr->getDebugVariable()))
 598       continue;
 599
 600     auto ParamDebugInstr = DebugEntryVals[CurrDebugInstr->getDebugVariable()];
 601     DIExpression *NewExpr = DIExpression::prepend(
 602         ParamDebugInstr->getDebugExpression(), DIExpression::EntryValue);
 603     MachineInstr *EntryValDbgMI =
 604         BuildMI(*MF, ParamDebugInstr->getDebugLoc(), ParamDebugInstr->getDesc(),
 605                 ParamDebugInstr->isIndirectDebugValue(),
 606                 ParamDebugInstr->getOperand(0).getReg(),
 607                 ParamDebugInstr->getDebugVariable(), NewExpr);
 608
 609     if (ParamDebugInstr->isIndirectDebugValue())
 610       EntryValDbgMI->getOperand(1).setImm(
 611           ParamDebugInstr->getOperand(1).getImm());
 612
 613     Transfers.push_back({&MI, EntryValDbgMI});
 614     VarLoc VL(*EntryValDbgMI, LS);
 615     unsigned EntryValLocID = VarLocIDs.insert(VL);
 616     OpenRanges.insert(EntryValLocID, VL.Var);
 617   }
 618 }
 619
 620 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
 621 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
 622 /// new VarLoc. If \p NewReg is different than default zero value then the
 623 /// new location will be register location created by the copy like instruction,
 624 /// otherwise it is variable's location on the stack.
 625 void LiveDebugValues::insertTransferDebugPair(
 626     MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
 627     VarLocMap &VarLocIDs, unsigned OldVarID, TransferKind Kind,
 628     unsigned NewReg) {
 629   const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
 630   MachineFunction *MF = MI.getParent()->getParent();
 631   MachineInstr *NewDebugInstr;
 632
 633   auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &DebugInstr,
 634                         &VarLocIDs](VarLoc &VL, MachineInstr *NewDebugInstr) {
 635     unsigned LocId = VarLocIDs.insert(VL);
 636
 637     // Close this variable's previous location range.
 638     DebugVariable V(*DebugInstr);
 639     OpenRanges.erase(V);
 640
 641     OpenRanges.insert(LocId, VL.Var);
 642     // The newly created DBG_VALUE instruction NewDebugInstr must be inserted
 643     // after MI. Keep track of the pairing.
 644     TransferDebugPair MIP = {&MI, NewDebugInstr};
 645     Transfers.push_back(MIP);
 646   };
 647
 648   // End all previous ranges of Var.
 649   OpenRanges.erase(VarLocIDs[OldVarID].Var);
 650   switch (Kind) {
 651   case TransferKind::TransferCopy: {
 652     assert(NewReg &&
 653            "No register supplied when handling a copy of a debug value");
 654     // Create a DBG_VALUE instruction to describe the Var in its new
 655     // register location.
 656     NewDebugInstr = BuildMI(
 657         *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(),
 658         DebugInstr->isIndirectDebugValue(), NewReg,
 659         DebugInstr->getDebugVariable(), DebugInstr->getDebugExpression());
 660     if (DebugInstr->isIndirectDebugValue())
 661       NewDebugInstr->getOperand(1).setImm(DebugInstr->getOperand(1).getImm());
 662     VarLoc VL(*NewDebugInstr, LS);
 663     ProcessVarLoc(VL, NewDebugInstr);
 664     LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register copy: ";
 665                NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
 666                                     /*SkipOpers*/false, /*SkipDebugLoc*/false,
 667                                     /*AddNewLine*/true, TII));
 668     return;
 669   }
 670   case TransferKind::TransferSpill: {
 671     // Create a DBG_VALUE instruction to describe the Var in its spilled
 672     // location.
 673     VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
 674     auto *SpillExpr = DIExpression::prepend(DebugInstr->getDebugExpression(),
 675                                             DIExpression::ApplyOffset,
 676                                             SpillLocation.SpillOffset);
 677     NewDebugInstr = BuildMI(
 678         *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), true,
 679         SpillLocation.SpillBase, DebugInstr->getDebugVariable(), SpillExpr);
 680     VarLoc VL(*NewDebugInstr, SpillLocation.SpillBase,
 681               SpillLocation.SpillOffset, LS);
 682     ProcessVarLoc(VL, NewDebugInstr);
 683     LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: ";
 684                NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
 685                                     /*SkipOpers*/false, /*SkipDebugLoc*/false,
 686                                     /*AddNewLine*/true, TII));
 687     return;
 688   }
 689   case TransferKind::TransferRestore: {
 690     assert(NewReg &&
 691            "No register supplied when handling a restore of a debug value");
 692     MachineFunction *MF = MI.getMF();
 693     DIBuilder DIB(*const_cast<Function &>(MF->getFunction()).getParent());
 694     NewDebugInstr =
 695         BuildMI(*MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), false,
 696                 NewReg, DebugInstr->getDebugVariable(), DIB.createExpression());
 697     VarLoc VL(*NewDebugInstr, LS);
 698     ProcessVarLoc(VL, NewDebugInstr);
 699     LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register restore: ";
 700                NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
 701                                     /*SkipOpers*/false, /*SkipDebugLoc*/false,
 702                                     /*AddNewLine*/true, TII));
 703     return;
 704   }
 705   }
 706   llvm_unreachable("Invalid transfer kind");
 707 }
 708
 709 /// A definition of a register may mark the end of a range.
 710 void LiveDebugValues::transferRegisterDef(
 711     MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
 712     TransferMap &Transfers, DebugParamMap &DebugEntryVals) {
 713   MachineFunction *MF = MI.getMF();
 714   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
 715   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
 716   SparseBitVector<> KillSet;
 717   for (const MachineOperand &MO : MI.operands()) {
 718     // Determine whether the operand is a register def.  Assume that call
 719     // instructions never clobber SP, because some backends (e.g., AArch64)
 720     // never list SP in the regmask.
 721     if (MO.isReg() && MO.isDef() && MO.getReg() &&
 722         TRI->isPhysicalRegister(MO.getReg()) &&
 723         !(MI.isCall() && MO.getReg() == SP)) {
 724       // Remove ranges of all aliased registers.
 725       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
 726         for (unsigned ID : OpenRanges.getVarLocs())
 727           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
 728             KillSet.set(ID);
 729     } else if (MO.isRegMask()) {
 730       // Remove ranges of all clobbered registers. Register masks don't usually
 731       // list SP as preserved.  While the debug info may be off for an
 732       // instruction or two around callee-cleanup calls, transferring the
 733       // DEBUG_VALUE across the call is still a better user experience.
 734       for (unsigned ID : OpenRanges.getVarLocs()) {
 735         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
 736         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
 737           KillSet.set(ID);
 738       }
 739     }
 740   }
 741   OpenRanges.erase(KillSet, VarLocIDs);
 742
 743   if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
 744     auto &TM = TPC->getTM<TargetMachine>();
 745     if (TM.Options.EnableDebugEntryValues)
 746       emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, DebugEntryVals,
 747                       KillSet);
 748   }
 749 }
 750
 751 /// Decide if @MI is a spill instruction and return true if it is. We use 2
 752 /// criteria to make this decision:
 753 /// - Is this instruction a store to a spill slot?
 754 /// - Is there a register operand that is both used and killed?
 755 /// TODO: Store optimization can fold spills into other stores (including
 756 /// other spills). We do not handle this yet (more than one memory operand).
 757 bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
 758                                          MachineFunction *MF, unsigned &Reg) {
 759   SmallVector<const MachineMemOperand*, 1> Accesses;
 760
 761   // TODO: Handle multiple stores folded into one.
 762   if (!MI.hasOneMemOperand())
 763     return false;
 764
 765   if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
 766     return false; // This is not a spill instruction, since no valid size was
 767                   // returned from either function.
 768
 769   auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
 770     if (!MO.isReg() || !MO.isUse()) {
 771       Reg = 0;
 772       return false;
 773     }
 774     Reg = MO.getReg();
 775     return MO.isKill();
 776   };
 777
 778   for (const MachineOperand &MO : MI.operands()) {
 779     // In a spill instruction generated by the InlineSpiller the spilled
 780     // register has its kill flag set.
 781     if (isKilledReg(MO, Reg))
 782       return true;
 783     if (Reg != 0) {
 784       // Check whether next instruction kills the spilled register.
 785       // FIXME: Current solution does not cover search for killed register in
 786       // bundles and instructions further down the chain.
 787       auto NextI = std::next(MI.getIterator());
 788       // Skip next instruction that points to basic block end iterator.
 789       if (MI.getParent()->end() == NextI)
 790         continue;
 791       unsigned RegNext;
 792       for (const MachineOperand &MONext : NextI->operands()) {
 793         // Return true if we came across the register from the
 794         // previous spill instruction that is killed in NextI.
 795         if (isKilledReg(MONext, RegNext) && RegNext == Reg)
 796           return true;
 797       }
 798     }
 799   }
 800   // Return false if we didn't find spilled register.
 801   return false;
 802 }
 803
 804 Optional<LiveDebugValues::VarLoc::SpillLoc>
 805 LiveDebugValues::isRestoreInstruction(const MachineInstr &MI,
 806                                       MachineFunction *MF, unsigned &Reg) {
 807   if (!MI.hasOneMemOperand())
 808     return None;
 809
 810   // FIXME: Handle folded restore instructions with more than one memory
 811   // operand.
 812   if (MI.getRestoreSize(TII)) {
 813     Reg = MI.getOperand(0).getReg();
 814     return extractSpillBaseRegAndOffset(MI);
 815   }
 816   return None;
 817 }
 818
 819 /// A spilled register may indicate that we have to end the current range of
 820 /// a variable and create a new one for the spill location.
 821 /// A restored register may indicate the reverse situation.
 822 /// We don't want to insert any instructions in process(), so we just create
 823 /// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
 824 /// It will be inserted into the BB when we're done iterating over the
 825 /// instructions.
 826 void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
 827                                                  OpenRangesSet &OpenRanges,
 828                                                  VarLocMap &VarLocIDs,
 829                                                  TransferMap &Transfers) {
 830   MachineFunction *MF = MI.getMF();
 831   TransferKind TKind;
 832   unsigned Reg;
 833   Optional<VarLoc::SpillLoc> Loc;
 834
 835   LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
 836
 837   if (isSpillInstruction(MI, MF, Reg)) {
 838     TKind = TransferKind::TransferSpill;
 839     LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
 840     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
 841                       << "\n");
 842   } else {
 843     if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
 844       return;
 845     TKind = TransferKind::TransferRestore;
 846     LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
 847     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
 848                       << "\n");
 849   }
 850   // Check if the register or spill location is the location of a debug value.
 851   for (unsigned ID : OpenRanges.getVarLocs()) {
 852     if (TKind == TransferKind::TransferSpill &&
 853         VarLocIDs[ID].isDescribedByReg() == Reg) {
 854       LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
 855                         << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
 856     } else if (TKind == TransferKind::TransferRestore &&
 857                VarLocIDs[ID].Loc.SpillLocation == *Loc) {
 858       LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
 859                         << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
 860     } else
 861       continue;
 862     insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind,
 863                             Reg);
 864     return;
 865   }
 866 }
 867
 868 /// If \p MI is a register copy instruction, that copies a previously tracked
 869 /// value from one register to another register that is callee saved, we
 870 /// create new DBG_VALUE instruction  described with copy destination register.
 871 void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
 872                                            OpenRangesSet &OpenRanges,
 873                                            VarLocMap &VarLocIDs,
 874                                            TransferMap &Transfers) {
 875   const MachineOperand *SrcRegOp, *DestRegOp;
 876
 877   if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() ||
 878       !DestRegOp->isDef())
 879     return;
 880
 881   auto isCalleSavedReg = [&](unsigned Reg) {
 882     for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
 883       if (CalleeSavedRegs.test(*RAI))
 884         return true;
 885     return false;
 886   };
 887
 888   unsigned SrcReg = SrcRegOp->getReg();
 889   unsigned DestReg = DestRegOp->getReg();
 890
 891   // We want to recognize instructions where destination register is callee
 892   // saved register. If register that could be clobbered by the call is
 893   // included, there would be a great chance that it is going to be clobbered
 894   // soon. It is more likely that previous register location, which is callee
 895   // saved, is going to stay unclobbered longer, even if it is killed.
 896   if (!isCalleSavedReg(DestReg))
 897     return;
 898
 899   for (unsigned ID : OpenRanges.getVarLocs()) {
 900     if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
 901       insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
 902                               TransferKind::TransferCopy, DestReg);
 903       return;
 904     }
 905   }
 906 }
 907
 908 /// Terminate all open ranges at the end of the current basic block.
 909 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
 910                                              OpenRangesSet &OpenRanges,
 911                                              VarLocInMBB &OutLocs,
 912                                              const VarLocMap &VarLocIDs) {
 913   bool Changed = false;
 914   const MachineBasicBlock *CurMBB = MI.getParent();
 915   if (!(MI.isTerminator() || (&MI == &CurMBB->back())))
 916     return false;
 917
 918   if (OpenRanges.empty())
 919     return false;
 920
 921   LLVM_DEBUG(for (unsigned ID
 922                   : OpenRanges.getVarLocs()) {
 923     // Copy OpenRanges to OutLocs, if not already present.
 924     dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
 925     VarLocIDs[ID].dump();
 926   });
 927   VarLocSet &VLS = OutLocs[CurMBB];
 928   Changed = VLS |= OpenRanges.getVarLocs();
 929   // New OutLocs set may be different due to spill, restore or register
 930   // copy instruction processing.
 931   if (Changed)
 932     VLS = OpenRanges.getVarLocs();
 933   OpenRanges.clear();
 934   return Changed;
 935 }
 936
 937 /// Accumulate a mapping between each DILocalVariable fragment and other
 938 /// fragments of that DILocalVariable which overlap. This reduces work during
 939 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
 940 /// known-to-overlap fragments are present".
 941 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
 942 ///           fragment usage.
 943 /// \param SeenFragments Map from DILocalVariable to all fragments of that
 944 ///           Variable which are known to exist.
 945 /// \param OverlappingFragments The overlap map being constructed, from one
 946 ///           Var/Fragment pair to a vector of fragments known to overlap.
 947 void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI,
 948                                             VarToFragments &SeenFragments,
 949                                             OverlapMap &OverlappingFragments) {
 950   DebugVariable MIVar(MI);
 951   FragmentInfo ThisFragment = MIVar.getFragmentDefault();
 952
 953   // If this is the first sighting of this variable, then we are guaranteed
 954   // there are currently no overlapping fragments either. Initialize the set
 955   // of seen fragments, record no overlaps for the current one, and return.
 956   auto SeenIt = SeenFragments.find(MIVar.getVar());
 957   if (SeenIt == SeenFragments.end()) {
 958     SmallSet<FragmentInfo, 4> OneFragment;
 959     OneFragment.insert(ThisFragment);
 960     SeenFragments.insert({MIVar.getVar(), OneFragment});
 961
 962     OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
 963     return;
 964   }
 965
 966   // If this particular Variable/Fragment pair already exists in the overlap
 967   // map, it has already been accounted for.
 968   auto IsInOLapMap =
 969       OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
 970   if (!IsInOLapMap.second)
 971     return;
 972
 973   auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
 974   auto &AllSeenFragments = SeenIt->second;
 975
 976   // Otherwise, examine all other seen fragments for this variable, with "this"
 977   // fragment being a previously unseen fragment. Record any pair of
 978   // overlapping fragments.
 979   for (auto &ASeenFragment : AllSeenFragments) {
 980     // Does this previously seen fragment overlap?
 981     if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
 982       // Yes: Mark the current fragment as being overlapped.
 983       ThisFragmentsOverlaps.push_back(ASeenFragment);
 984       // Mark the previously seen fragment as being overlapped by the current
 985       // one.
 986       auto ASeenFragmentsOverlaps =
 987           OverlappingFragments.find({MIVar.getVar(), ASeenFragment});
 988       assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
 989              "Previously seen var fragment has no vector of overlaps");
 990       ASeenFragmentsOverlaps->second.push_back(ThisFragment);
 991     }
 992   }
 993
 994   AllSeenFragments.insert(ThisFragment);
 995 }
 996
 997 /// This routine creates OpenRanges and OutLocs.
 998 bool LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
 999                               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
1000                               TransferMap &Transfers, DebugParamMap &DebugEntryVals,
1001                               bool transferChanges,
1002                               OverlapMap &OverlapFragments,
1003                               VarToFragments &SeenFragments) {
1004   bool Changed = false;
1005   transferDebugValue(MI, OpenRanges, VarLocIDs);
1006   transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers,
1007                       DebugEntryVals);
1008   if (transferChanges) {
1009     transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
1010     transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
1011   } else {
1012     // Build up a map of overlapping fragments on the first run through.
1013     if (MI.isDebugValue())
1014       accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
1015   }
1016   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
1017   return Changed;
1018 }
1019
1020 /// This routine joins the analysis results of all incoming edges in @MBB by
1021 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
1022 /// source variable in all the predecessors of @MBB reside in the same location.
1023 bool LiveDebugValues::join(
1024     MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
1025     const VarLocMap &VarLocIDs,
1026     SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
1027     SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
1028   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
1029   bool Changed = false;
1030
1031   VarLocSet InLocsT; // Temporary incoming locations.
1032
1033   // For all predecessors of this MBB, find the set of VarLocs that
1034   // can be joined.
1035   int NumVisited = 0;
1036   for (auto p : MBB.predecessors()) {
1037     // Ignore unvisited predecessor blocks.  As we are processing
1038     // the blocks in reverse post-order any unvisited block can
1039     // be considered to not remove any incoming values.
1040     if (!Visited.count(p)) {
1041       LLVM_DEBUG(dbgs() << "  ignoring unvisited pred MBB: " << p->getNumber()
1042                         << "\n");
1043       continue;
1044     }
1045     auto OL = OutLocs.find(p);
1046     // Join is null in case of empty OutLocs from any of the pred.
1047     if (OL == OutLocs.end())
1048       return false;
1049
1050     // Just copy over the Out locs to incoming locs for the first visited
1051     // predecessor, and for all other predecessors join the Out locs.
1052     if (!NumVisited)
1053       InLocsT = OL->second;
1054     else
1055       InLocsT &= OL->second;
1056
1057     LLVM_DEBUG({
1058       if (!InLocsT.empty()) {
1059         for (auto ID : InLocsT)
1060           dbgs() << "  gathered candidate incoming var: "
1061                  << VarLocIDs[ID].Var.getVar()->getName() << "\n";
1062       }
1063     });
1064
1065     NumVisited++;
1066   }
1067
1068   // Filter out DBG_VALUES that are out of scope.
1069   VarLocSet KillSet;
1070   bool IsArtificial = ArtificialBlocks.count(&MBB);
1071   if (!IsArtificial) {
1072     for (auto ID : InLocsT) {
1073       if (!VarLocIDs[ID].dominates(MBB)) {
1074         KillSet.set(ID);
1075         LLVM_DEBUG({
1076           auto Name = VarLocIDs[ID].Var.getVar()->getName();
1077           dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
1078         });
1079       }
1080     }
1081   }
1082   InLocsT.intersectWithComplement(KillSet);
1083
1084   // As we are processing blocks in reverse post-order we
1085   // should have processed at least one predecessor, unless it
1086   // is the entry block which has no predecessor.
1087   assert((NumVisited || MBB.pred_empty()) &&
1088          "Should have processed at least one predecessor");
1089   if (InLocsT.empty())
1090     return false;
1091
1092   VarLocSet &ILS = InLocs[&MBB];
1093
1094   // Insert DBG_VALUE instructions, if not already inserted.
1095   VarLocSet Diff = InLocsT;
1096   Diff.intersectWithComplement(ILS);
1097   for (auto ID : Diff) {
1098     // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
1099     // new range is started for the var from the mbb's beginning by inserting
1100     // a new DBG_VALUE. process() will end this range however appropriate.
1101     const VarLoc &DiffIt = VarLocIDs[ID];
1102     const MachineInstr *DebugInstr = &DiffIt.MI;
1103     MachineInstr *MI = nullptr;
1104     if (DiffIt.isConstant()) {
1105       MachineOperand MO(DebugInstr->getOperand(0));
1106       MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1107                    DebugInstr->getDesc(), false, MO,
1108                    DebugInstr->getDebugVariable(),
1109                    DebugInstr->getDebugExpression());
1110     } else {
1111       MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1112                    DebugInstr->getDesc(), DebugInstr->isIndirectDebugValue(),
1113                    DebugInstr->getOperand(0).getReg(),
1114                    DebugInstr->getDebugVariable(),
1115                    DebugInstr->getDebugExpression());
1116       if (DebugInstr->isIndirectDebugValue())
1117         MI->getOperand(1).setImm(DebugInstr->getOperand(1).getImm());
1118     }
1119     LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
1120     ILS.set(ID);
1121     ++NumInserted;
1122     Changed = true;
1123   }
1124   return Changed;
1125 }
1126
1127 /// Calculate the liveness information for the given machine function and
1128 /// extend ranges across basic blocks.
1129 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
1130   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
1131
1132   bool Changed = false;
1133   bool OLChanged = false;
1134   bool MBBJoined = false;
1135
1136   VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors.
1137   OverlapMap OverlapFragments; // Map of overlapping variable fragments
1138   OpenRangesSet OpenRanges(OverlapFragments);
1139                               // Ranges that are open until end of bb.
1140   VarLocInMBB OutLocs;        // Ranges that exist beyond bb.
1141   VarLocInMBB InLocs;         // Ranges that are incoming after joining.
1142   TransferMap Transfers;      // DBG_VALUEs associated with spills.
1143
1144   VarToFragments SeenFragments;
1145
1146   // Blocks which are artificial, i.e. blocks which exclusively contain
1147   // instructions without locations, or with line 0 locations.
1148   SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
1149
1150   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
1151   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
1152   std::priority_queue<unsigned int, std::vector<unsigned int>,
1153                       std::greater<unsigned int>>
1154       Worklist;
1155   std::priority_queue<unsigned int, std::vector<unsigned int>,
1156                       std::greater<unsigned int>>
1157       Pending;
1158
1159   enum : bool { dontTransferChanges = false, transferChanges = true };
1160
1161   // Besides parameter's modification, check whether a DBG_VALUE is inlined
1162   // in order to deduce whether the variable that it tracks comes from
1163   // a different function. If that is the case we can't track its entry value.
1164   auto IsUnmodifiedFuncParam = [&](const MachineInstr &MI) {
1165     auto *DIVar = MI.getDebugVariable();
1166     return DIVar->isParameter() && DIVar->isNotModified() &&
1167            !MI.getDebugLoc()->getInlinedAt();
1168   };
1169
1170   const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
1171   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
1172   unsigned FP = TRI->getFrameRegister(MF);
1173   auto IsRegOtherThanSPAndFP = [&](const MachineOperand &Op) -> bool {
1174     return Op.isReg() && Op.getReg() != SP && Op.getReg() != FP;
1175   };
1176
1177   // Working set of currently collected debug variables mapped to DBG_VALUEs
1178   // representing candidates for production of debug entry values.
1179   DebugParamMap DebugEntryVals;
1180
1181   MachineBasicBlock &First_MBB = *(MF.begin());
1182   // Only in the case of entry MBB collect DBG_VALUEs representing
1183   // function parameters in order to generate debug entry values for them.
1184   // Currently, we generate debug entry values only for parameters that are
1185   // unmodified throughout the function and located in a register.
1186   // TODO: Add support for parameters that are described as fragments.
1187   // TODO: Add support for modified arguments that can be expressed
1188   // by using its entry value.
1189   // TODO: Add support for local variables that are expressed in terms of
1190   // parameters entry values.
1191   for (auto &MI : First_MBB)
1192     if (MI.isDebugValue() && IsUnmodifiedFuncParam(MI) &&
1193         !MI.isIndirectDebugValue() && IsRegOtherThanSPAndFP(MI.getOperand(0)) &&
1194         !DebugEntryVals.count(MI.getDebugVariable()) &&
1195         !MI.getDebugExpression()->isFragment())
1196       DebugEntryVals[MI.getDebugVariable()] = &MI;
1197
1198   // Initialize every mbb with OutLocs.
1199   // We are not looking at any spill instructions during the initial pass
1200   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
1201   // instructions for spills of registers that are known to be user variables
1202   // within the BB in which the spill occurs.
1203   for (auto &MBB : MF) {
1204     for (auto &MI : MBB) {
1205       process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers, DebugEntryVals,
1206               dontTransferChanges, OverlapFragments, SeenFragments);
1207     }
1208     // Add any entry DBG_VALUE instructions necessitated by parameter
1209     // clobbering.
1210     for (auto &TR : Transfers) {
1211       MBB.insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
1212                      TR.DebugInst);
1213     }
1214     Transfers.clear();
1215   }
1216
1217   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
1218     if (const DebugLoc &DL = MI.getDebugLoc())
1219       return DL.getLine() != 0;
1220     return false;
1221   };
1222   for (auto &MBB : MF)
1223     if (none_of(MBB.instrs(), hasNonArtificialLocation))
1224       ArtificialBlocks.insert(&MBB);
1225
1226   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1227                               "OutLocs after initialization", dbgs()));
1228
1229   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
1230   unsigned int RPONumber = 0;
1231   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
1232     OrderToBB[RPONumber] = *RI;
1233     BBToOrder[*RI] = RPONumber;
1234     Worklist.push(RPONumber);
1235     ++RPONumber;
1236   }
1237   // This is a standard "union of predecessor outs" dataflow problem.
1238   // To solve it, we perform join() and process() using the two worklist method
1239   // until the ranges converge.
1240   // Ranges have converged when both worklists are empty.
1241   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
1242   while (!Worklist.empty() || !Pending.empty()) {
1243     // We track what is on the pending worklist to avoid inserting the same
1244     // thing twice.  We could avoid this with a custom priority queue, but this
1245     // is probably not worth it.
1246     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
1247     LLVM_DEBUG(dbgs() << "Processing Worklist\n");
1248     while (!Worklist.empty()) {
1249       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
1250       Worklist.pop();
1251       MBBJoined =
1252           join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, ArtificialBlocks);
1253       Visited.insert(MBB);
1254       if (MBBJoined) {
1255         MBBJoined = false;
1256         Changed = true;
1257         // Now that we have started to extend ranges across BBs we need to
1258         // examine spill instructions to see whether they spill registers that
1259         // correspond to user variables.
1260         for (auto &MI : *MBB)
1261           OLChanged |=
1262               process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
1263                       DebugEntryVals, transferChanges, OverlapFragments,
1264                       SeenFragments);
1265
1266         // Add any DBG_VALUE instructions necessitated by spills.
1267         for (auto &TR : Transfers)
1268           MBB->insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
1269                            TR.DebugInst);
1270         Transfers.clear();
1271
1272         LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1273                                     "OutLocs after propagating", dbgs()));
1274         LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
1275                                     "InLocs after propagating", dbgs()));
1276
1277         if (OLChanged) {
1278           OLChanged = false;
1279           for (auto s : MBB->successors())
1280             if (OnPending.insert(s).second) {
1281               Pending.push(BBToOrder[s]);
1282             }
1283         }
1284       }
1285     }
1286     Worklist.swap(Pending);
1287     // At this point, pending must be empty, since it was just the empty
1288     // worklist
1289     assert(Pending.empty() && "Pending should be empty");
1290   }
1291
1292   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
1293   LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
1294   return Changed;
1295 }
1296
1297 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
1298   if (!MF.getFunction().getSubprogram())
1299     // LiveDebugValues will already have removed all DBG_VALUEs.
1300     return false;
1301
1302   // Skip functions from NoDebug compilation units.
1303   if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
1304       DICompileUnit::NoDebug)
1305     return false;
1306
1307   TRI = MF.getSubtarget().getRegisterInfo();
1308   TII = MF.getSubtarget().getInstrInfo();
1309   TFI = MF.getSubtarget().getFrameLowering();
1310   TFI->determineCalleeSaves(MF, CalleeSavedRegs,
1311                             make_unique<RegScavenger>().get());
1312   LS.initialize(MF);
1313
1314   bool Changed = ExtendRanges(MF);
1315   return Changed;
1316 }