contrib/llvm-project/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
 695     const DIExpression *NewExpr;
 696     if (auto Fragment = DebugInstr->getDebugExpression()->getFragmentInfo())
 697       NewExpr = *DIExpression::createFragmentExpression(DIB.createExpression(),
 698         Fragment->OffsetInBits, Fragment->SizeInBits);
 699     else
 700       NewExpr = DIB.createExpression();
 701
 702     NewDebugInstr =
 703         BuildMI(*MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), false,
 704                 NewReg, DebugInstr->getDebugVariable(), NewExpr);
 705     VarLoc VL(*NewDebugInstr, LS);
 706     ProcessVarLoc(VL, NewDebugInstr);
 707     LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register restore: ";
 708                NewDebugInstr->print(dbgs(), /*IsStandalone*/false,
 709                                     /*SkipOpers*/false, /*SkipDebugLoc*/false,
 710                                     /*AddNewLine*/true, TII));
 711     return;
 712   }
 713   }
 714   llvm_unreachable("Invalid transfer kind");
 715 }
 716
 717 /// A definition of a register may mark the end of a range.
 718 void LiveDebugValues::transferRegisterDef(
 719     MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
 720     TransferMap &Transfers, DebugParamMap &DebugEntryVals) {
 721   MachineFunction *MF = MI.getMF();
 722   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
 723   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
 724   SparseBitVector<> KillSet;
 725   for (const MachineOperand &MO : MI.operands()) {
 726     // Determine whether the operand is a register def.  Assume that call
 727     // instructions never clobber SP, because some backends (e.g., AArch64)
 728     // never list SP in the regmask.
 729     if (MO.isReg() && MO.isDef() && MO.getReg() &&
 730         TRI->isPhysicalRegister(MO.getReg()) &&
 731         !(MI.isCall() && MO.getReg() == SP)) {
 732       // Remove ranges of all aliased registers.
 733       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
 734         for (unsigned ID : OpenRanges.getVarLocs())
 735           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
 736             KillSet.set(ID);
 737     } else if (MO.isRegMask()) {
 738       // Remove ranges of all clobbered registers. Register masks don't usually
 739       // list SP as preserved.  While the debug info may be off for an
 740       // instruction or two around callee-cleanup calls, transferring the
 741       // DEBUG_VALUE across the call is still a better user experience.
 742       for (unsigned ID : OpenRanges.getVarLocs()) {
 743         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
 744         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
 745           KillSet.set(ID);
 746       }
 747     }
 748   }
 749   OpenRanges.erase(KillSet, VarLocIDs);
 750
 751   if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
 752     auto &TM = TPC->getTM<TargetMachine>();
 753     if (TM.Options.EnableDebugEntryValues)
 754       emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, DebugEntryVals,
 755                       KillSet);
 756   }
 757 }
 758
 759 /// Decide if @MI is a spill instruction and return true if it is. We use 2
 760 /// criteria to make this decision:
 761 /// - Is this instruction a store to a spill slot?
 762 /// - Is there a register operand that is both used and killed?
 763 /// TODO: Store optimization can fold spills into other stores (including
 764 /// other spills). We do not handle this yet (more than one memory operand).
 765 bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
 766                                          MachineFunction *MF, unsigned &Reg) {
 767   SmallVector<const MachineMemOperand*, 1> Accesses;
 768
 769   // TODO: Handle multiple stores folded into one.
 770   if (!MI.hasOneMemOperand())
 771     return false;
 772
 773   if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
 774     return false; // This is not a spill instruction, since no valid size was
 775                   // returned from either function.
 776
 777   auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) {
 778     if (!MO.isReg() || !MO.isUse()) {
 779       Reg = 0;
 780       return false;
 781     }
 782     Reg = MO.getReg();
 783     return MO.isKill();
 784   };
 785
 786   for (const MachineOperand &MO : MI.operands()) {
 787     // In a spill instruction generated by the InlineSpiller the spilled
 788     // register has its kill flag set.
 789     if (isKilledReg(MO, Reg))
 790       return true;
 791     if (Reg != 0) {
 792       // Check whether next instruction kills the spilled register.
 793       // FIXME: Current solution does not cover search for killed register in
 794       // bundles and instructions further down the chain.
 795       auto NextI = std::next(MI.getIterator());
 796       // Skip next instruction that points to basic block end iterator.
 797       if (MI.getParent()->end() == NextI)
 798         continue;
 799       unsigned RegNext;
 800       for (const MachineOperand &MONext : NextI->operands()) {
 801         // Return true if we came across the register from the
 802         // previous spill instruction that is killed in NextI.
 803         if (isKilledReg(MONext, RegNext) && RegNext == Reg)
 804           return true;
 805       }
 806     }
 807   }
 808   // Return false if we didn't find spilled register.
 809   return false;
 810 }
 811
 812 Optional<LiveDebugValues::VarLoc::SpillLoc>
 813 LiveDebugValues::isRestoreInstruction(const MachineInstr &MI,
 814                                       MachineFunction *MF, unsigned &Reg) {
 815   if (!MI.hasOneMemOperand())
 816     return None;
 817
 818   // FIXME: Handle folded restore instructions with more than one memory
 819   // operand.
 820   if (MI.getRestoreSize(TII)) {
 821     Reg = MI.getOperand(0).getReg();
 822     return extractSpillBaseRegAndOffset(MI);
 823   }
 824   return None;
 825 }
 826
 827 /// A spilled register may indicate that we have to end the current range of
 828 /// a variable and create a new one for the spill location.
 829 /// A restored register may indicate the reverse situation.
 830 /// We don't want to insert any instructions in process(), so we just create
 831 /// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
 832 /// It will be inserted into the BB when we're done iterating over the
 833 /// instructions.
 834 void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
 835                                                  OpenRangesSet &OpenRanges,
 836                                                  VarLocMap &VarLocIDs,
 837                                                  TransferMap &Transfers) {
 838   MachineFunction *MF = MI.getMF();
 839   TransferKind TKind;
 840   unsigned Reg;
 841   Optional<VarLoc::SpillLoc> Loc;
 842
 843   LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
 844
 845   if (isSpillInstruction(MI, MF, Reg)) {
 846     TKind = TransferKind::TransferSpill;
 847     LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
 848     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
 849                       << "\n");
 850   } else {
 851     if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
 852       return;
 853     TKind = TransferKind::TransferRestore;
 854     LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
 855     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
 856                       << "\n");
 857   }
 858   // Check if the register or spill location is the location of a debug value.
 859   // FIXME: Don't create a spill transfer if there is a complex expression,
 860   // because we currently cannot recover the original expression on restore.
 861   for (unsigned ID : OpenRanges.getVarLocs()) {
 862     const MachineInstr *DebugInstr = &VarLocIDs[ID].MI;
 863
 864     if (TKind == TransferKind::TransferSpill &&
 865         VarLocIDs[ID].isDescribedByReg() == Reg &&
 866         !DebugInstr->getDebugExpression()->isComplex()) {
 867       LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
 868                         << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
 869     } else if (TKind == TransferKind::TransferRestore &&
 870                VarLocIDs[ID].Loc.SpillLocation == *Loc) {
 871       LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
 872                         << VarLocIDs[ID].Var.getVar()->getName() << ")\n");
 873     } else
 874       continue;
 875     insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind,
 876                             Reg);
 877     return;
 878   }
 879 }
 880
 881 /// If \p MI is a register copy instruction, that copies a previously tracked
 882 /// value from one register to another register that is callee saved, we
 883 /// create new DBG_VALUE instruction  described with copy destination register.
 884 void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
 885                                            OpenRangesSet &OpenRanges,
 886                                            VarLocMap &VarLocIDs,
 887                                            TransferMap &Transfers) {
 888   const MachineOperand *SrcRegOp, *DestRegOp;
 889
 890   if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() ||
 891       !DestRegOp->isDef())
 892     return;
 893
 894   auto isCalleSavedReg = [&](unsigned Reg) {
 895     for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
 896       if (CalleeSavedRegs.test(*RAI))
 897         return true;
 898     return false;
 899   };
 900
 901   unsigned SrcReg = SrcRegOp->getReg();
 902   unsigned DestReg = DestRegOp->getReg();
 903
 904   // We want to recognize instructions where destination register is callee
 905   // saved register. If register that could be clobbered by the call is
 906   // included, there would be a great chance that it is going to be clobbered
 907   // soon. It is more likely that previous register location, which is callee
 908   // saved, is going to stay unclobbered longer, even if it is killed.
 909   if (!isCalleSavedReg(DestReg))
 910     return;
 911
 912   for (unsigned ID : OpenRanges.getVarLocs()) {
 913     if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
 914       insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
 915                               TransferKind::TransferCopy, DestReg);
 916       return;
 917     }
 918   }
 919 }
 920
 921 /// Terminate all open ranges at the end of the current basic block.
 922 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
 923                                              OpenRangesSet &OpenRanges,
 924                                              VarLocInMBB &OutLocs,
 925                                              const VarLocMap &VarLocIDs) {
 926   bool Changed = false;
 927   const MachineBasicBlock *CurMBB = MI.getParent();
 928   if (!(MI.isTerminator() || (&MI == &CurMBB->back())))
 929     return false;
 930
 931   if (OpenRanges.empty())
 932     return false;
 933
 934   LLVM_DEBUG(for (unsigned ID
 935                   : OpenRanges.getVarLocs()) {
 936     // Copy OpenRanges to OutLocs, if not already present.
 937     dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
 938     VarLocIDs[ID].dump();
 939   });
 940   VarLocSet &VLS = OutLocs[CurMBB];
 941   Changed = VLS |= OpenRanges.getVarLocs();
 942   // New OutLocs set may be different due to spill, restore or register
 943   // copy instruction processing.
 944   if (Changed)
 945     VLS = OpenRanges.getVarLocs();
 946   OpenRanges.clear();
 947   return Changed;
 948 }
 949
 950 /// Accumulate a mapping between each DILocalVariable fragment and other
 951 /// fragments of that DILocalVariable which overlap. This reduces work during
 952 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
 953 /// known-to-overlap fragments are present".
 954 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
 955 ///           fragment usage.
 956 /// \param SeenFragments Map from DILocalVariable to all fragments of that
 957 ///           Variable which are known to exist.
 958 /// \param OverlappingFragments The overlap map being constructed, from one
 959 ///           Var/Fragment pair to a vector of fragments known to overlap.
 960 void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI,
 961                                             VarToFragments &SeenFragments,
 962                                             OverlapMap &OverlappingFragments) {
 963   DebugVariable MIVar(MI);
 964   FragmentInfo ThisFragment = MIVar.getFragmentDefault();
 965
 966   // If this is the first sighting of this variable, then we are guaranteed
 967   // there are currently no overlapping fragments either. Initialize the set
 968   // of seen fragments, record no overlaps for the current one, and return.
 969   auto SeenIt = SeenFragments.find(MIVar.getVar());
 970   if (SeenIt == SeenFragments.end()) {
 971     SmallSet<FragmentInfo, 4> OneFragment;
 972     OneFragment.insert(ThisFragment);
 973     SeenFragments.insert({MIVar.getVar(), OneFragment});
 974
 975     OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
 976     return;
 977   }
 978
 979   // If this particular Variable/Fragment pair already exists in the overlap
 980   // map, it has already been accounted for.
 981   auto IsInOLapMap =
 982       OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}});
 983   if (!IsInOLapMap.second)
 984     return;
 985
 986   auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
 987   auto &AllSeenFragments = SeenIt->second;
 988
 989   // Otherwise, examine all other seen fragments for this variable, with "this"
 990   // fragment being a previously unseen fragment. Record any pair of
 991   // overlapping fragments.
 992   for (auto &ASeenFragment : AllSeenFragments) {
 993     // Does this previously seen fragment overlap?
 994     if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
 995       // Yes: Mark the current fragment as being overlapped.
 996       ThisFragmentsOverlaps.push_back(ASeenFragment);
 997       // Mark the previously seen fragment as being overlapped by the current
 998       // one.
 999       auto ASeenFragmentsOverlaps =
1000           OverlappingFragments.find({MIVar.getVar(), ASeenFragment});
1001       assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
1002              "Previously seen var fragment has no vector of overlaps");
1003       ASeenFragmentsOverlaps->second.push_back(ThisFragment);
1004     }
1005   }
1006
1007   AllSeenFragments.insert(ThisFragment);
1008 }
1009
1010 /// This routine creates OpenRanges and OutLocs.
1011 bool LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
1012                               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
1013                               TransferMap &Transfers, DebugParamMap &DebugEntryVals,
1014                               bool transferChanges,
1015                               OverlapMap &OverlapFragments,
1016                               VarToFragments &SeenFragments) {
1017   bool Changed = false;
1018   transferDebugValue(MI, OpenRanges, VarLocIDs);
1019   transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers,
1020                       DebugEntryVals);
1021   if (transferChanges) {
1022     transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
1023     transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
1024   } else {
1025     // Build up a map of overlapping fragments on the first run through.
1026     if (MI.isDebugValue())
1027       accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
1028   }
1029   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
1030   return Changed;
1031 }
1032
1033 /// This routine joins the analysis results of all incoming edges in @MBB by
1034 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
1035 /// source variable in all the predecessors of @MBB reside in the same location.
1036 bool LiveDebugValues::join(
1037     MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
1038     const VarLocMap &VarLocIDs,
1039     SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
1040     SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
1041   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
1042   bool Changed = false;
1043
1044   VarLocSet InLocsT; // Temporary incoming locations.
1045
1046   // For all predecessors of this MBB, find the set of VarLocs that
1047   // can be joined.
1048   int NumVisited = 0;
1049   for (auto p : MBB.predecessors()) {
1050     // Ignore unvisited predecessor blocks.  As we are processing
1051     // the blocks in reverse post-order any unvisited block can
1052     // be considered to not remove any incoming values.
1053     if (!Visited.count(p)) {
1054       LLVM_DEBUG(dbgs() << "  ignoring unvisited pred MBB: " << p->getNumber()
1055                         << "\n");
1056       continue;
1057     }
1058     auto OL = OutLocs.find(p);
1059     // Join is null in case of empty OutLocs from any of the pred.
1060     if (OL == OutLocs.end())
1061       return false;
1062
1063     // Just copy over the Out locs to incoming locs for the first visited
1064     // predecessor, and for all other predecessors join the Out locs.
1065     if (!NumVisited)
1066       InLocsT = OL->second;
1067     else
1068       InLocsT &= OL->second;
1069
1070     LLVM_DEBUG({
1071       if (!InLocsT.empty()) {
1072         for (auto ID : InLocsT)
1073           dbgs() << "  gathered candidate incoming var: "
1074                  << VarLocIDs[ID].Var.getVar()->getName() << "\n";
1075       }
1076     });
1077
1078     NumVisited++;
1079   }
1080
1081   // Filter out DBG_VALUES that are out of scope.
1082   VarLocSet KillSet;
1083   bool IsArtificial = ArtificialBlocks.count(&MBB);
1084   if (!IsArtificial) {
1085     for (auto ID : InLocsT) {
1086       if (!VarLocIDs[ID].dominates(MBB)) {
1087         KillSet.set(ID);
1088         LLVM_DEBUG({
1089           auto Name = VarLocIDs[ID].Var.getVar()->getName();
1090           dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
1091         });
1092       }
1093     }
1094   }
1095   InLocsT.intersectWithComplement(KillSet);
1096
1097   // As we are processing blocks in reverse post-order we
1098   // should have processed at least one predecessor, unless it
1099   // is the entry block which has no predecessor.
1100   assert((NumVisited || MBB.pred_empty()) &&
1101          "Should have processed at least one predecessor");
1102   if (InLocsT.empty())
1103     return false;
1104
1105   VarLocSet &ILS = InLocs[&MBB];
1106
1107   // Insert DBG_VALUE instructions, if not already inserted.
1108   VarLocSet Diff = InLocsT;
1109   Diff.intersectWithComplement(ILS);
1110   for (auto ID : Diff) {
1111     // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
1112     // new range is started for the var from the mbb's beginning by inserting
1113     // a new DBG_VALUE. process() will end this range however appropriate.
1114     const VarLoc &DiffIt = VarLocIDs[ID];
1115     const MachineInstr *DebugInstr = &DiffIt.MI;
1116     MachineInstr *MI = nullptr;
1117     if (DiffIt.isConstant()) {
1118       MachineOperand MO(DebugInstr->getOperand(0));
1119       MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1120                    DebugInstr->getDesc(), false, MO,
1121                    DebugInstr->getDebugVariable(),
1122                    DebugInstr->getDebugExpression());
1123     } else {
1124       MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(),
1125                    DebugInstr->getDesc(), DebugInstr->isIndirectDebugValue(),
1126                    DebugInstr->getOperand(0).getReg(),
1127                    DebugInstr->getDebugVariable(),
1128                    DebugInstr->getDebugExpression());
1129       if (DebugInstr->isIndirectDebugValue())
1130         MI->getOperand(1).setImm(DebugInstr->getOperand(1).getImm());
1131     }
1132     LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
1133     ILS.set(ID);
1134     ++NumInserted;
1135     Changed = true;
1136   }
1137   return Changed;
1138 }
1139
1140 /// Calculate the liveness information for the given machine function and
1141 /// extend ranges across basic blocks.
1142 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
1143   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
1144
1145   bool Changed = false;
1146   bool OLChanged = false;
1147   bool MBBJoined = false;
1148
1149   VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors.
1150   OverlapMap OverlapFragments; // Map of overlapping variable fragments
1151   OpenRangesSet OpenRanges(OverlapFragments);
1152                               // Ranges that are open until end of bb.
1153   VarLocInMBB OutLocs;        // Ranges that exist beyond bb.
1154   VarLocInMBB InLocs;         // Ranges that are incoming after joining.
1155   TransferMap Transfers;      // DBG_VALUEs associated with spills.
1156
1157   VarToFragments SeenFragments;
1158
1159   // Blocks which are artificial, i.e. blocks which exclusively contain
1160   // instructions without locations, or with line 0 locations.
1161   SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
1162
1163   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
1164   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
1165   std::priority_queue<unsigned int, std::vector<unsigned int>,
1166                       std::greater<unsigned int>>
1167       Worklist;
1168   std::priority_queue<unsigned int, std::vector<unsigned int>,
1169                       std::greater<unsigned int>>
1170       Pending;
1171
1172   enum : bool { dontTransferChanges = false, transferChanges = true };
1173
1174   // Besides parameter's modification, check whether a DBG_VALUE is inlined
1175   // in order to deduce whether the variable that it tracks comes from
1176   // a different function. If that is the case we can't track its entry value.
1177   auto IsUnmodifiedFuncParam = [&](const MachineInstr &MI) {
1178     auto *DIVar = MI.getDebugVariable();
1179     return DIVar->isParameter() && DIVar->isNotModified() &&
1180            !MI.getDebugLoc()->getInlinedAt();
1181   };
1182
1183   const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
1184   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
1185   unsigned FP = TRI->getFrameRegister(MF);
1186   auto IsRegOtherThanSPAndFP = [&](const MachineOperand &Op) -> bool {
1187     return Op.isReg() && Op.getReg() != SP && Op.getReg() != FP;
1188   };
1189
1190   // Working set of currently collected debug variables mapped to DBG_VALUEs
1191   // representing candidates for production of debug entry values.
1192   DebugParamMap DebugEntryVals;
1193
1194   MachineBasicBlock &First_MBB = *(MF.begin());
1195   // Only in the case of entry MBB collect DBG_VALUEs representing
1196   // function parameters in order to generate debug entry values for them.
1197   // Currently, we generate debug entry values only for parameters that are
1198   // unmodified throughout the function and located in a register.
1199   // TODO: Add support for parameters that are described as fragments.
1200   // TODO: Add support for modified arguments that can be expressed
1201   // by using its entry value.
1202   // TODO: Add support for local variables that are expressed in terms of
1203   // parameters entry values.
1204   for (auto &MI : First_MBB)
1205     if (MI.isDebugValue() && IsUnmodifiedFuncParam(MI) &&
1206         !MI.isIndirectDebugValue() && IsRegOtherThanSPAndFP(MI.getOperand(0)) &&
1207         !DebugEntryVals.count(MI.getDebugVariable()) &&
1208         !MI.getDebugExpression()->isFragment())
1209       DebugEntryVals[MI.getDebugVariable()] = &MI;
1210
1211   // Initialize every mbb with OutLocs.
1212   // We are not looking at any spill instructions during the initial pass
1213   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
1214   // instructions for spills of registers that are known to be user variables
1215   // within the BB in which the spill occurs.
1216   for (auto &MBB : MF) {
1217     for (auto &MI : MBB) {
1218       process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers, DebugEntryVals,
1219               dontTransferChanges, OverlapFragments, SeenFragments);
1220     }
1221     // Add any entry DBG_VALUE instructions necessitated by parameter
1222     // clobbering.
1223     for (auto &TR : Transfers) {
1224       MBB.insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
1225                      TR.DebugInst);
1226     }
1227     Transfers.clear();
1228   }
1229
1230   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
1231     if (const DebugLoc &DL = MI.getDebugLoc())
1232       return DL.getLine() != 0;
1233     return false;
1234   };
1235   for (auto &MBB : MF)
1236     if (none_of(MBB.instrs(), hasNonArtificialLocation))
1237       ArtificialBlocks.insert(&MBB);
1238
1239   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1240                               "OutLocs after initialization", dbgs()));
1241
1242   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
1243   unsigned int RPONumber = 0;
1244   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
1245     OrderToBB[RPONumber] = *RI;
1246     BBToOrder[*RI] = RPONumber;
1247     Worklist.push(RPONumber);
1248     ++RPONumber;
1249   }
1250   // This is a standard "union of predecessor outs" dataflow problem.
1251   // To solve it, we perform join() and process() using the two worklist method
1252   // until the ranges converge.
1253   // Ranges have converged when both worklists are empty.
1254   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
1255   while (!Worklist.empty() || !Pending.empty()) {
1256     // We track what is on the pending worklist to avoid inserting the same
1257     // thing twice.  We could avoid this with a custom priority queue, but this
1258     // is probably not worth it.
1259     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
1260     LLVM_DEBUG(dbgs() << "Processing Worklist\n");
1261     while (!Worklist.empty()) {
1262       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
1263       Worklist.pop();
1264       MBBJoined =
1265           join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, ArtificialBlocks);
1266       Visited.insert(MBB);
1267       if (MBBJoined) {
1268         MBBJoined = false;
1269         Changed = true;
1270         // Now that we have started to extend ranges across BBs we need to
1271         // examine spill instructions to see whether they spill registers that
1272         // correspond to user variables.
1273         for (auto &MI : *MBB)
1274           OLChanged |=
1275               process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
1276                       DebugEntryVals, transferChanges, OverlapFragments,
1277                       SeenFragments);
1278
1279         // Add any DBG_VALUE instructions necessitated by spills.
1280         for (auto &TR : Transfers)
1281           MBB->insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
1282                            TR.DebugInst);
1283         Transfers.clear();
1284
1285         LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
1286                                     "OutLocs after propagating", dbgs()));
1287         LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
1288                                     "InLocs after propagating", dbgs()));
1289
1290         if (OLChanged) {
1291           OLChanged = false;
1292           for (auto s : MBB->successors())
1293             if (OnPending.insert(s).second) {
1294               Pending.push(BBToOrder[s]);
1295             }
1296         }
1297       }
1298     }
1299     Worklist.swap(Pending);
1300     // At this point, pending must be empty, since it was just the empty
1301     // worklist
1302     assert(Pending.empty() && "Pending should be empty");
1303   }
1304
1305   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
1306   LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
1307   return Changed;
1308 }
1309
1310 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
1311   if (!MF.getFunction().getSubprogram())
1312     // LiveDebugValues will already have removed all DBG_VALUEs.
1313     return false;
1314
1315   // Skip functions from NoDebug compilation units.
1316   if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
1317       DICompileUnit::NoDebug)
1318     return false;
1319
1320   TRI = MF.getSubtarget().getRegisterInfo();
1321   TII = MF.getSubtarget().getInstrInfo();
1322   TFI = MF.getSubtarget().getFrameLowering();
1323   TFI->determineCalleeSaves(MF, CalleeSavedRegs,
1324                             make_unique<RegScavenger>().get());
1325   LS.initialize(MF);
1326
1327   bool Changed = ExtendRanges(MF);
1328   return Changed;
1329 }