contrib/llvm-project/llvm/lib/CodeGen/LiveDebugVariables.cpp

   1 //===- LiveDebugVariables.cpp - Tracking debug info variables -------------===//
   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 file implements the LiveDebugVariables analysis.
  10 //
  11 // Remove all DBG_VALUE instructions referencing virtual registers and replace
  12 // them with a data structure tracking where live user variables are kept - in a
  13 // virtual register or in a stack slot.
  14 //
  15 // Allow the data structure to be updated during register allocation when values
  16 // are moved between registers and stack slots. Finally emit new DBG_VALUE
  17 // instructions after register allocation is complete.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "LiveDebugVariables.h"
  22 #include "llvm/ADT/ArrayRef.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/IntervalMap.h"
  25 #include "llvm/ADT/MapVector.h"
  26 #include "llvm/ADT/STLExtras.h"
  27 #include "llvm/ADT/SmallSet.h"
  28 #include "llvm/ADT/SmallVector.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/ADT/StringRef.h"
  31 #include "llvm/CodeGen/LexicalScopes.h"
  32 #include "llvm/CodeGen/LiveInterval.h"
  33 #include "llvm/CodeGen/LiveIntervals.h"
  34 #include "llvm/CodeGen/MachineBasicBlock.h"
  35 #include "llvm/CodeGen/MachineDominators.h"
  36 #include "llvm/CodeGen/MachineFunction.h"
  37 #include "llvm/CodeGen/MachineInstr.h"
  38 #include "llvm/CodeGen/MachineInstrBuilder.h"
  39 #include "llvm/CodeGen/MachineOperand.h"
  40 #include "llvm/CodeGen/MachineRegisterInfo.h"
  41 #include "llvm/CodeGen/SlotIndexes.h"
  42 #include "llvm/CodeGen/TargetInstrInfo.h"
  43 #include "llvm/CodeGen/TargetOpcodes.h"
  44 #include "llvm/CodeGen/TargetRegisterInfo.h"
  45 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  46 #include "llvm/CodeGen/VirtRegMap.h"
  47 #include "llvm/Config/llvm-config.h"
  48 #include "llvm/IR/DebugInfoMetadata.h"
  49 #include "llvm/IR/DebugLoc.h"
  50 #include "llvm/IR/Function.h"
  51 #include "llvm/IR/Metadata.h"
  52 #include "llvm/MC/MCRegisterInfo.h"
  53 #include "llvm/Pass.h"
  54 #include "llvm/Support/Casting.h"
  55 #include "llvm/Support/CommandLine.h"
  56 #include "llvm/Support/Compiler.h"
  57 #include "llvm/Support/Debug.h"
  58 #include "llvm/Support/raw_ostream.h"
  59 #include <algorithm>
  60 #include <cassert>
  61 #include <iterator>
  62 #include <memory>
  63 #include <utility>
  64
  65 using namespace llvm;
  66
  67 #define DEBUG_TYPE "livedebugvars"
  68
  69 static cl::opt<bool>
  70 EnableLDV("live-debug-variables", cl::init(true),
  71           cl::desc("Enable the live debug variables pass"), cl::Hidden);
  72
  73 STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted");
  74 STATISTIC(NumInsertedDebugLabels, "Number of DBG_LABELs inserted");
  75
  76 char LiveDebugVariables::ID = 0;
  77
  78 INITIALIZE_PASS_BEGIN(LiveDebugVariables, DEBUG_TYPE,
  79                 "Debug Variable Analysis", false, false)
  80 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  81 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  82 INITIALIZE_PASS_END(LiveDebugVariables, DEBUG_TYPE,
  83                 "Debug Variable Analysis", false, false)
  84
  85 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
  86   AU.addRequired<MachineDominatorTree>();
  87   AU.addRequiredTransitive<LiveIntervals>();
  88   AU.setPreservesAll();
  89   MachineFunctionPass::getAnalysisUsage(AU);
  90 }
  91
  92 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID) {
  93   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
  94 }
  95
  96 enum : unsigned { UndefLocNo = ~0U };
  97
  98 /// Describes a location by number along with some flags about the original
  99 /// usage of the location.
 100 class DbgValueLocation {
 101 public:
 102   DbgValueLocation(unsigned LocNo, bool WasIndirect)
 103       : LocNo(LocNo), WasIndirect(WasIndirect) {
 104     static_assert(sizeof(*this) == sizeof(unsigned), "bad bitfield packing");
 105     assert(locNo() == LocNo && "location truncation");
 106   }
 107
 108   DbgValueLocation() : LocNo(0), WasIndirect(0) {}
 109
 110   unsigned locNo() const {
 111     // Fix up the undef location number, which gets truncated.
 112     return LocNo == INT_MAX ? UndefLocNo : LocNo;
 113   }
 114   bool wasIndirect() const { return WasIndirect; }
 115   bool isUndef() const { return locNo() == UndefLocNo; }
 116
 117   DbgValueLocation changeLocNo(unsigned NewLocNo) const {
 118     return DbgValueLocation(NewLocNo, WasIndirect);
 119   }
 120
 121   friend inline bool operator==(const DbgValueLocation &LHS,
 122                                 const DbgValueLocation &RHS) {
 123     return LHS.LocNo == RHS.LocNo && LHS.WasIndirect == RHS.WasIndirect;
 124   }
 125
 126   friend inline bool operator!=(const DbgValueLocation &LHS,
 127                                 const DbgValueLocation &RHS) {
 128     return !(LHS == RHS);
 129   }
 130
 131 private:
 132   unsigned LocNo : 31;
 133   unsigned WasIndirect : 1;
 134 };
 135
 136 /// Map of where a user value is live, and its location.
 137 using LocMap = IntervalMap<SlotIndex, DbgValueLocation, 4>;
 138
 139 /// Map of stack slot offsets for spilled locations.
 140 /// Non-spilled locations are not added to the map.
 141 using SpillOffsetMap = DenseMap<unsigned, unsigned>;
 142
 143 namespace {
 144
 145 class LDVImpl;
 146
 147 /// A user value is a part of a debug info user variable.
 148 ///
 149 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
 150 /// holds part of a user variable. The part is identified by a byte offset.
 151 ///
 152 /// UserValues are grouped into equivalence classes for easier searching. Two
 153 /// user values are related if they refer to the same variable, or if they are
 154 /// held by the same virtual register. The equivalence class is the transitive
 155 /// closure of that relation.
 156 class UserValue {
 157   const DILocalVariable *Variable; ///< The debug info variable we are part of.
 158   const DIExpression *Expression; ///< Any complex address expression.
 159   DebugLoc dl;            ///< The debug location for the variable. This is
 160                           ///< used by dwarf writer to find lexical scope.
 161   UserValue *leader;      ///< Equivalence class leader.
 162   UserValue *next = nullptr; ///< Next value in equivalence class, or null.
 163
 164   /// Numbered locations referenced by locmap.
 165   SmallVector<MachineOperand, 4> locations;
 166
 167   /// Map of slot indices where this value is live.
 168   LocMap locInts;
 169
 170   /// Insert a DBG_VALUE into MBB at Idx for LocNo.
 171   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
 172                         SlotIndex StopIdx, DbgValueLocation Loc, bool Spilled,
 173                         unsigned SpillOffset, LiveIntervals &LIS,
 174                         const TargetInstrInfo &TII,
 175                         const TargetRegisterInfo &TRI);
 176
 177   /// Replace OldLocNo ranges with NewRegs ranges where NewRegs
 178   /// is live. Returns true if any changes were made.
 179   bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
 180                      LiveIntervals &LIS);
 181
 182 public:
 183   /// Create a new UserValue.
 184   UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
 185             LocMap::Allocator &alloc)
 186       : Variable(var), Expression(expr), dl(std::move(L)), leader(this),
 187         locInts(alloc) {}
 188
 189   /// Get the leader of this value's equivalence class.
 190   UserValue *getLeader() {
 191     UserValue *l = leader;
 192     while (l != l->leader)
 193       l = l->leader;
 194     return leader = l;
 195   }
 196
 197   /// Return the next UserValue in the equivalence class.
 198   UserValue *getNext() const { return next; }
 199
 200   /// Does this UserValue match the parameters?
 201   bool match(const DILocalVariable *Var, const DIExpression *Expr,
 202              const DILocation *IA) const {
 203     // FIXME: The fragment should be part of the equivalence class, but not
 204     // other things in the expression like stack values.
 205     return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA;
 206   }
 207
 208   /// Merge equivalence classes.
 209   static UserValue *merge(UserValue *L1, UserValue *L2) {
 210     L2 = L2->getLeader();
 211     if (!L1)
 212       return L2;
 213     L1 = L1->getLeader();
 214     if (L1 == L2)
 215       return L1;
 216     // Splice L2 before L1's members.
 217     UserValue *End = L2;
 218     while (End->next) {
 219       End->leader = L1;
 220       End = End->next;
 221     }
 222     End->leader = L1;
 223     End->next = L1->next;
 224     L1->next = L2;
 225     return L1;
 226   }
 227
 228   /// Return the location number that matches Loc.
 229   ///
 230   /// For undef values we always return location number UndefLocNo without
 231   /// inserting anything in locations. Since locations is a vector and the
 232   /// location number is the position in the vector and UndefLocNo is ~0,
 233   /// we would need a very big vector to put the value at the right position.
 234   unsigned getLocationNo(const MachineOperand &LocMO) {
 235     if (LocMO.isReg()) {
 236       if (LocMO.getReg() == 0)
 237         return UndefLocNo;
 238       // For register locations we dont care about use/def and other flags.
 239       for (unsigned i = 0, e = locations.size(); i != e; ++i)
 240         if (locations[i].isReg() &&
 241             locations[i].getReg() == LocMO.getReg() &&
 242             locations[i].getSubReg() == LocMO.getSubReg())
 243           return i;
 244     } else
 245       for (unsigned i = 0, e = locations.size(); i != e; ++i)
 246         if (LocMO.isIdenticalTo(locations[i]))
 247           return i;
 248     locations.push_back(LocMO);
 249     // We are storing a MachineOperand outside a MachineInstr.
 250     locations.back().clearParent();
 251     // Don't store def operands.
 252     if (locations.back().isReg()) {
 253       if (locations.back().isDef())
 254         locations.back().setIsDead(false);
 255       locations.back().setIsUse();
 256     }
 257     return locations.size() - 1;
 258   }
 259
 260   /// Ensure that all virtual register locations are mapped.
 261   void mapVirtRegs(LDVImpl *LDV);
 262
 263   /// Add a definition point to this value.
 264   void addDef(SlotIndex Idx, const MachineOperand &LocMO, bool IsIndirect) {
 265     DbgValueLocation Loc(getLocationNo(LocMO), IsIndirect);
 266     // Add a singular (Idx,Idx) -> Loc mapping.
 267     LocMap::iterator I = locInts.find(Idx);
 268     if (!I.valid() || I.start() != Idx)
 269       I.insert(Idx, Idx.getNextSlot(), Loc);
 270     else
 271       // A later DBG_VALUE at the same SlotIndex overrides the old location.
 272       I.setValue(Loc);
 273   }
 274
 275   /// Extend the current definition as far as possible down.
 276   ///
 277   /// Stop when meeting an existing def or when leaving the live
 278   /// range of VNI. End points where VNI is no longer live are added to Kills.
 279   ///
 280   /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a
 281   /// data-flow analysis to propagate them beyond basic block boundaries.
 282   ///
 283   /// \param Idx Starting point for the definition.
 284   /// \param Loc Location number to propagate.
 285   /// \param LR Restrict liveness to where LR has the value VNI. May be null.
 286   /// \param VNI When LR is not null, this is the value to restrict to.
 287   /// \param [out] Kills Append end points of VNI's live range to Kills.
 288   /// \param LIS Live intervals analysis.
 289   void extendDef(SlotIndex Idx, DbgValueLocation Loc,
 290                  LiveRange *LR, const VNInfo *VNI,
 291                  SmallVectorImpl<SlotIndex> *Kills,
 292                  LiveIntervals &LIS);
 293
 294   /// The value in LI/LocNo may be copies to other registers. Determine if
 295   /// any of the copies are available at the kill points, and add defs if
 296   /// possible.
 297   ///
 298   /// \param LI Scan for copies of the value in LI->reg.
 299   /// \param LocNo Location number of LI->reg.
 300   /// \param WasIndirect Indicates if the original use of LI->reg was indirect
 301   /// \param Kills Points where the range of LocNo could be extended.
 302   /// \param [in,out] NewDefs Append (Idx, LocNo) of inserted defs here.
 303   void addDefsFromCopies(
 304       LiveInterval *LI, unsigned LocNo, bool WasIndirect,
 305       const SmallVectorImpl<SlotIndex> &Kills,
 306       SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
 307       MachineRegisterInfo &MRI, LiveIntervals &LIS);
 308
 309   /// Compute the live intervals of all locations after collecting all their
 310   /// def points.
 311   void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
 312                         LiveIntervals &LIS, LexicalScopes &LS);
 313
 314   /// Replace OldReg ranges with NewRegs ranges where NewRegs is
 315   /// live. Returns true if any changes were made.
 316   bool splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
 317                      LiveIntervals &LIS);
 318
 319   /// Rewrite virtual register locations according to the provided virtual
 320   /// register map. Record the stack slot offsets for the locations that
 321   /// were spilled.
 322   void rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
 323                         const TargetInstrInfo &TII,
 324                         const TargetRegisterInfo &TRI,
 325                         SpillOffsetMap &SpillOffsets);
 326
 327   /// Recreate DBG_VALUE instruction from data structures.
 328   void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
 329                        const TargetInstrInfo &TII,
 330                        const TargetRegisterInfo &TRI,
 331                        const SpillOffsetMap &SpillOffsets);
 332
 333   /// Return DebugLoc of this UserValue.
 334   DebugLoc getDebugLoc() { return dl;}
 335
 336   void print(raw_ostream &, const TargetRegisterInfo *);
 337 };
 338
 339 /// A user label is a part of a debug info user label.
 340 class UserLabel {
 341   const DILabel *Label; ///< The debug info label we are part of.
 342   DebugLoc dl;          ///< The debug location for the label. This is
 343                         ///< used by dwarf writer to find lexical scope.
 344   SlotIndex loc;        ///< Slot used by the debug label.
 345
 346   /// Insert a DBG_LABEL into MBB at Idx.
 347   void insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx,
 348                         LiveIntervals &LIS, const TargetInstrInfo &TII);
 349
 350 public:
 351   /// Create a new UserLabel.
 352   UserLabel(const DILabel *label, DebugLoc L, SlotIndex Idx)
 353       : Label(label), dl(std::move(L)), loc(Idx) {}
 354
 355   /// Does this UserLabel match the parameters?
 356   bool match(const DILabel *L, const DILocation *IA,
 357              const SlotIndex Index) const {
 358     return Label == L && dl->getInlinedAt() == IA && loc == Index;
 359   }
 360
 361   /// Recreate DBG_LABEL instruction from data structures.
 362   void emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII);
 363
 364   /// Return DebugLoc of this UserLabel.
 365   DebugLoc getDebugLoc() { return dl; }
 366
 367   void print(raw_ostream &, const TargetRegisterInfo *);
 368 };
 369
 370 /// Implementation of the LiveDebugVariables pass.
 371 class LDVImpl {
 372   LiveDebugVariables &pass;
 373   LocMap::Allocator allocator;
 374   MachineFunction *MF = nullptr;
 375   LiveIntervals *LIS;
 376   const TargetRegisterInfo *TRI;
 377
 378   /// Whether emitDebugValues is called.
 379   bool EmitDone = false;
 380
 381   /// Whether the machine function is modified during the pass.
 382   bool ModifiedMF = false;
 383
 384   /// All allocated UserValue instances.
 385   SmallVector<std::unique_ptr<UserValue>, 8> userValues;
 386
 387   /// All allocated UserLabel instances.
 388   SmallVector<std::unique_ptr<UserLabel>, 2> userLabels;
 389
 390   /// Map virtual register to eq class leader.
 391   using VRMap = DenseMap<unsigned, UserValue *>;
 392   VRMap virtRegToEqClass;
 393
 394   /// Map user variable to eq class leader.
 395   using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
 396   UVMap userVarMap;
 397
 398   /// Find or create a UserValue.
 399   UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
 400                           const DebugLoc &DL);
 401
 402   /// Find the EC leader for VirtReg or null.
 403   UserValue *lookupVirtReg(unsigned VirtReg);
 404
 405   /// Add DBG_VALUE instruction to our maps.
 406   ///
 407   /// \param MI DBG_VALUE instruction
 408   /// \param Idx Last valid SLotIndex before instruction.
 409   ///
 410   /// \returns True if the DBG_VALUE instruction should be deleted.
 411   bool handleDebugValue(MachineInstr &MI, SlotIndex Idx);
 412
 413   /// Add DBG_LABEL instruction to UserLabel.
 414   ///
 415   /// \param MI DBG_LABEL instruction
 416   /// \param Idx Last valid SlotIndex before instruction.
 417   ///
 418   /// \returns True if the DBG_LABEL instruction should be deleted.
 419   bool handleDebugLabel(MachineInstr &MI, SlotIndex Idx);
 420
 421   /// Collect and erase all DBG_VALUE instructions, adding a UserValue def
 422   /// for each instruction.
 423   ///
 424   /// \param mf MachineFunction to be scanned.
 425   ///
 426   /// \returns True if any debug values were found.
 427   bool collectDebugValues(MachineFunction &mf);
 428
 429   /// Compute the live intervals of all user values after collecting all
 430   /// their def points.
 431   void computeIntervals();
 432
 433 public:
 434   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
 435
 436   bool runOnMachineFunction(MachineFunction &mf);
 437
 438   /// Release all memory.
 439   void clear() {
 440     MF = nullptr;
 441     userValues.clear();
 442     userLabels.clear();
 443     virtRegToEqClass.clear();
 444     userVarMap.clear();
 445     // Make sure we call emitDebugValues if the machine function was modified.
 446     assert((!ModifiedMF || EmitDone) &&
 447            "Dbg values are not emitted in LDV");
 448     EmitDone = false;
 449     ModifiedMF = false;
 450   }
 451
 452   /// Map virtual register to an equivalence class.
 453   void mapVirtReg(unsigned VirtReg, UserValue *EC);
 454
 455   /// Replace all references to OldReg with NewRegs.
 456   void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
 457
 458   /// Recreate DBG_VALUE instruction from data structures.
 459   void emitDebugValues(VirtRegMap *VRM);
 460
 461   void print(raw_ostream&);
 462 };
 463
 464 } // end anonymous namespace
 465
 466 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 467 static void printDebugLoc(const DebugLoc &DL, raw_ostream &CommentOS,
 468                           const LLVMContext &Ctx) {
 469   if (!DL)
 470     return;
 471
 472   auto *Scope = cast<DIScope>(DL.getScope());
 473   // Omit the directory, because it's likely to be long and uninteresting.
 474   CommentOS << Scope->getFilename();
 475   CommentOS << ':' << DL.getLine();
 476   if (DL.getCol() != 0)
 477     CommentOS << ':' << DL.getCol();
 478
 479   DebugLoc InlinedAtDL = DL.getInlinedAt();
 480   if (!InlinedAtDL)
 481     return;
 482
 483   CommentOS << " @[ ";
 484   printDebugLoc(InlinedAtDL, CommentOS, Ctx);
 485   CommentOS << " ]";
 486 }
 487
 488 static void printExtendedName(raw_ostream &OS, const DINode *Node,
 489                               const DILocation *DL) {
 490   const LLVMContext &Ctx = Node->getContext();
 491   StringRef Res;
 492   unsigned Line;
 493   if (const auto *V = dyn_cast<const DILocalVariable>(Node)) {
 494     Res = V->getName();
 495     Line = V->getLine();
 496   } else if (const auto *L = dyn_cast<const DILabel>(Node)) {
 497     Res = L->getName();
 498     Line = L->getLine();
 499   }
 500
 501   if (!Res.empty())
 502     OS << Res << "," << Line;
 503   auto *InlinedAt = DL ? DL->getInlinedAt() : nullptr;
 504   if (InlinedAt) {
 505     if (DebugLoc InlinedAtDL = InlinedAt) {
 506       OS << " @[";
 507       printDebugLoc(InlinedAtDL, OS, Ctx);
 508       OS << "]";
 509     }
 510   }
 511 }
 512
 513 void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
 514   OS << "!\"";
 515   printExtendedName(OS, Variable, dl);
 516
 517   OS << "\"\t";
 518   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
 519     OS << " [" << I.start() << ';' << I.stop() << "):";
 520     if (I.value().isUndef())
 521       OS << "undef";
 522     else {
 523       OS << I.value().locNo();
 524       if (I.value().wasIndirect())
 525         OS << " ind";
 526     }
 527   }
 528   for (unsigned i = 0, e = locations.size(); i != e; ++i) {
 529     OS << " Loc" << i << '=';
 530     locations[i].print(OS, TRI);
 531   }
 532   OS << '\n';
 533 }
 534
 535 void UserLabel::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
 536   OS << "!\"";
 537   printExtendedName(OS, Label, dl);
 538
 539   OS << "\"\t";
 540   OS << loc;
 541   OS << '\n';
 542 }
 543
 544 void LDVImpl::print(raw_ostream &OS) {
 545   OS << "********** DEBUG VARIABLES **********\n";
 546   for (auto &userValue : userValues)
 547     userValue->print(OS, TRI);
 548   OS << "********** DEBUG LABELS **********\n";
 549   for (auto &userLabel : userLabels)
 550     userLabel->print(OS, TRI);
 551 }
 552 #endif
 553
 554 void UserValue::mapVirtRegs(LDVImpl *LDV) {
 555   for (unsigned i = 0, e = locations.size(); i != e; ++i)
 556     if (locations[i].isReg() &&
 557         TargetRegisterInfo::isVirtualRegister(locations[i].getReg()))
 558       LDV->mapVirtReg(locations[i].getReg(), this);
 559 }
 560
 561 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
 562                                  const DIExpression *Expr, const DebugLoc &DL) {
 563   UserValue *&Leader = userVarMap[Var];
 564   if (Leader) {
 565     UserValue *UV = Leader->getLeader();
 566     Leader = UV;
 567     for (; UV; UV = UV->getNext())
 568       if (UV->match(Var, Expr, DL->getInlinedAt()))
 569         return UV;
 570   }
 571
 572   userValues.push_back(
 573       llvm::make_unique<UserValue>(Var, Expr, DL, allocator));
 574   UserValue *UV = userValues.back().get();
 575   Leader = UserValue::merge(Leader, UV);
 576   return UV;
 577 }
 578
 579 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
 580   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
 581   UserValue *&Leader = virtRegToEqClass[VirtReg];
 582   Leader = UserValue::merge(Leader, EC);
 583 }
 584
 585 UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
 586   if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
 587     return UV->getLeader();
 588   return nullptr;
 589 }
 590
 591 bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
 592   // DBG_VALUE loc, offset, variable
 593   if (MI.getNumOperands() != 4 ||
 594       !(MI.getOperand(1).isReg() || MI.getOperand(1).isImm()) ||
 595       !MI.getOperand(2).isMetadata()) {
 596     LLVM_DEBUG(dbgs() << "Can't handle " << MI);
 597     return false;
 598   }
 599
 600   // Detect invalid DBG_VALUE instructions, with a debug-use of a virtual
 601   // register that hasn't been defined yet. If we do not remove those here, then
 602   // the re-insertion of the DBG_VALUE instruction after register allocation
 603   // will be incorrect.
 604   // TODO: If earlier passes are corrected to generate sane debug information
 605   // (and if the machine verifier is improved to catch this), then these checks
 606   // could be removed or replaced by asserts.
 607   bool Discard = false;
 608   if (MI.getOperand(0).isReg() &&
 609       TargetRegisterInfo::isVirtualRegister(MI.getOperand(0).getReg())) {
 610     const unsigned Reg = MI.getOperand(0).getReg();
 611     if (!LIS->hasInterval(Reg)) {
 612       // The DBG_VALUE is described by a virtual register that does not have a
 613       // live interval. Discard the DBG_VALUE.
 614       Discard = true;
 615       LLVM_DEBUG(dbgs() << "Discarding debug info (no LIS interval): " << Idx
 616                         << " " << MI);
 617     } else {
 618       // The DBG_VALUE is only valid if either Reg is live out from Idx, or Reg
 619       // is defined dead at Idx (where Idx is the slot index for the instruction
 620       // preceding the DBG_VALUE).
 621       const LiveInterval &LI = LIS->getInterval(Reg);
 622       LiveQueryResult LRQ = LI.Query(Idx);
 623       if (!LRQ.valueOutOrDead()) {
 624         // We have found a DBG_VALUE with the value in a virtual register that
 625         // is not live. Discard the DBG_VALUE.
 626         Discard = true;
 627         LLVM_DEBUG(dbgs() << "Discarding debug info (reg not live): " << Idx
 628                           << " " << MI);
 629       }
 630     }
 631   }
 632
 633   // Get or create the UserValue for (variable,offset) here.
 634   bool IsIndirect = MI.getOperand(1).isImm();
 635   if (IsIndirect)
 636     assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
 637   const DILocalVariable *Var = MI.getDebugVariable();
 638   const DIExpression *Expr = MI.getDebugExpression();
 639   UserValue *UV =
 640       getUserValue(Var, Expr, MI.getDebugLoc());
 641   if (!Discard)
 642     UV->addDef(Idx, MI.getOperand(0), IsIndirect);
 643   else {
 644     MachineOperand MO = MachineOperand::CreateReg(0U, false);
 645     MO.setIsDebug();
 646     UV->addDef(Idx, MO, false);
 647   }
 648   return true;
 649 }
 650
 651 bool LDVImpl::handleDebugLabel(MachineInstr &MI, SlotIndex Idx) {
 652   // DBG_LABEL label
 653   if (MI.getNumOperands() != 1 || !MI.getOperand(0).isMetadata()) {
 654     LLVM_DEBUG(dbgs() << "Can't handle " << MI);
 655     return false;
 656   }
 657
 658   // Get or create the UserLabel for label here.
 659   const DILabel *Label = MI.getDebugLabel();
 660   const DebugLoc &DL = MI.getDebugLoc();
 661   bool Found = false;
 662   for (auto const &L : userLabels) {
 663     if (L->match(Label, DL->getInlinedAt(), Idx)) {
 664       Found = true;
 665       break;
 666     }
 667   }
 668   if (!Found)
 669     userLabels.push_back(llvm::make_unique<UserLabel>(Label, DL, Idx));
 670
 671   return true;
 672 }
 673
 674 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
 675   bool Changed = false;
 676   for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
 677        ++MFI) {
 678     MachineBasicBlock *MBB = &*MFI;
 679     for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
 680          MBBI != MBBE;) {
 681       // Use the first debug instruction in the sequence to get a SlotIndex
 682       // for following consecutive debug instructions.
 683       if (!MBBI->isDebugInstr()) {
 684         ++MBBI;
 685         continue;
 686       }
 687       // Debug instructions has no slot index. Use the previous
 688       // non-debug instruction's SlotIndex as its SlotIndex.
 689       SlotIndex Idx =
 690           MBBI == MBB->begin()
 691               ? LIS->getMBBStartIdx(MBB)
 692               : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot();
 693       // Handle consecutive debug instructions with the same slot index.
 694       do {
 695         // Only handle DBG_VALUE in handleDebugValue(). Skip all other
 696         // kinds of debug instructions.
 697         if ((MBBI->isDebugValue() && handleDebugValue(*MBBI, Idx)) ||
 698             (MBBI->isDebugLabel() && handleDebugLabel(*MBBI, Idx))) {
 699           MBBI = MBB->erase(MBBI);
 700           Changed = true;
 701         } else
 702           ++MBBI;
 703       } while (MBBI != MBBE && MBBI->isDebugInstr());
 704     }
 705   }
 706   return Changed;
 707 }
 708
 709 void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
 710                           const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills,
 711                           LiveIntervals &LIS) {
 712   SlotIndex Start = Idx;
 713   MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
 714   SlotIndex Stop = LIS.getMBBEndIdx(MBB);
 715   LocMap::iterator I = locInts.find(Start);
 716
 717   // Limit to VNI's live range.
 718   bool ToEnd = true;
 719   if (LR && VNI) {
 720     LiveInterval::Segment *Segment = LR->getSegmentContaining(Start);
 721     if (!Segment || Segment->valno != VNI) {
 722       if (Kills)
 723         Kills->push_back(Start);
 724       return;
 725     }
 726     if (Segment->end < Stop) {
 727       Stop = Segment->end;
 728       ToEnd = false;
 729     }
 730   }
 731
 732   // There could already be a short def at Start.
 733   if (I.valid() && I.start() <= Start) {
 734     // Stop when meeting a different location or an already extended interval.
 735     Start = Start.getNextSlot();
 736     if (I.value() != Loc || I.stop() != Start)
 737       return;
 738     // This is a one-slot placeholder. Just skip it.
 739     ++I;
 740   }
 741
 742   // Limited by the next def.
 743   if (I.valid() && I.start() < Stop)
 744     Stop = I.start();
 745   // Limited by VNI's live range.
 746   else if (!ToEnd && Kills)
 747     Kills->push_back(Stop);
 748
 749   if (Start < Stop)
 750     I.insert(Start, Stop, Loc);
 751 }
 752
 753 void UserValue::addDefsFromCopies(
 754     LiveInterval *LI, unsigned LocNo, bool WasIndirect,
 755     const SmallVectorImpl<SlotIndex> &Kills,
 756     SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
 757     MachineRegisterInfo &MRI, LiveIntervals &LIS) {
 758   if (Kills.empty())
 759     return;
 760   // Don't track copies from physregs, there are too many uses.
 761   if (!TargetRegisterInfo::isVirtualRegister(LI->reg))
 762     return;
 763
 764   // Collect all the (vreg, valno) pairs that are copies of LI.
 765   SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues;
 766   for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
 767     MachineInstr *MI = MO.getParent();
 768     // Copies of the full value.
 769     if (MO.getSubReg() || !MI->isCopy())
 770       continue;
 771     unsigned DstReg = MI->getOperand(0).getReg();
 772
 773     // Don't follow copies to physregs. These are usually setting up call
 774     // arguments, and the argument registers are always call clobbered. We are
 775     // better off in the source register which could be a callee-saved register,
 776     // or it could be spilled.
 777     if (!TargetRegisterInfo::isVirtualRegister(DstReg))
 778       continue;
 779
 780     // Is LocNo extended to reach this copy? If not, another def may be blocking
 781     // it, or we are looking at a wrong value of LI.
 782     SlotIndex Idx = LIS.getInstructionIndex(*MI);
 783     LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
 784     if (!I.valid() || I.value().locNo() != LocNo)
 785       continue;
 786
 787     if (!LIS.hasInterval(DstReg))
 788       continue;
 789     LiveInterval *DstLI = &LIS.getInterval(DstReg);
 790     const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
 791     assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
 792     CopyValues.push_back(std::make_pair(DstLI, DstVNI));
 793   }
 794
 795   if (CopyValues.empty())
 796     return;
 797
 798   LLVM_DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI
 799                     << '\n');
 800
 801   // Try to add defs of the copied values for each kill point.
 802   for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 803     SlotIndex Idx = Kills[i];
 804     for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
 805       LiveInterval *DstLI = CopyValues[j].first;
 806       const VNInfo *DstVNI = CopyValues[j].second;
 807       if (DstLI->getVNInfoAt(Idx) != DstVNI)
 808         continue;
 809       // Check that there isn't already a def at Idx
 810       LocMap::iterator I = locInts.find(Idx);
 811       if (I.valid() && I.start() <= Idx)
 812         continue;
 813       LLVM_DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
 814                         << DstVNI->id << " in " << *DstLI << '\n');
 815       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
 816       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
 817       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
 818       DbgValueLocation NewLoc(LocNo, WasIndirect);
 819       I.insert(Idx, Idx.getNextSlot(), NewLoc);
 820       NewDefs.push_back(std::make_pair(Idx, NewLoc));
 821       break;
 822     }
 823   }
 824 }
 825
 826 void UserValue::computeIntervals(MachineRegisterInfo &MRI,
 827                                  const TargetRegisterInfo &TRI,
 828                                  LiveIntervals &LIS, LexicalScopes &LS) {
 829   SmallVector<std::pair<SlotIndex, DbgValueLocation>, 16> Defs;
 830
 831   // Collect all defs to be extended (Skipping undefs).
 832   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
 833     if (!I.value().isUndef())
 834       Defs.push_back(std::make_pair(I.start(), I.value()));
 835
 836   // Extend all defs, and possibly add new ones along the way.
 837   for (unsigned i = 0; i != Defs.size(); ++i) {
 838     SlotIndex Idx = Defs[i].first;
 839     DbgValueLocation Loc = Defs[i].second;
 840     const MachineOperand &LocMO = locations[Loc.locNo()];
 841
 842     if (!LocMO.isReg()) {
 843       extendDef(Idx, Loc, nullptr, nullptr, nullptr, LIS);
 844       continue;
 845     }
 846
 847     // Register locations are constrained to where the register value is live.
 848     if (TargetRegisterInfo::isVirtualRegister(LocMO.getReg())) {
 849       LiveInterval *LI = nullptr;
 850       const VNInfo *VNI = nullptr;
 851       if (LIS.hasInterval(LocMO.getReg())) {
 852         LI = &LIS.getInterval(LocMO.getReg());
 853         VNI = LI->getVNInfoAt(Idx);
 854       }
 855       SmallVector<SlotIndex, 16> Kills;
 856       extendDef(Idx, Loc, LI, VNI, &Kills, LIS);
 857       // FIXME: Handle sub-registers in addDefsFromCopies. The problem is that
 858       // if the original location for example is %vreg0:sub_hi, and we find a
 859       // full register copy in addDefsFromCopies (at the moment it only handles
 860       // full register copies), then we must add the sub1 sub-register index to
 861       // the new location. However, that is only possible if the new virtual
 862       // register is of the same regclass (or if there is an equivalent
 863       // sub-register in that regclass). For now, simply skip handling copies if
 864       // a sub-register is involved.
 865       if (LI && !LocMO.getSubReg())
 866         addDefsFromCopies(LI, Loc.locNo(), Loc.wasIndirect(), Kills, Defs, MRI,
 867                           LIS);
 868       continue;
 869     }
 870
 871     // For physregs, we only mark the start slot idx. DwarfDebug will see it
 872     // as if the DBG_VALUE is valid up until the end of the basic block, or
 873     // the next def of the physical register. So we do not need to extend the
 874     // range. It might actually happen that the DBG_VALUE is the last use of
 875     // the physical register (e.g. if this is an unused input argument to a
 876     // function).
 877   }
 878
 879   // The computed intervals may extend beyond the range of the debug
 880   // location's lexical scope. In this case, splitting of an interval
 881   // can result in an interval outside of the scope being created,
 882   // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
 883   // this, trim the intervals to the lexical scope.
 884
 885   LexicalScope *Scope = LS.findLexicalScope(dl);
 886   if (!Scope)
 887     return;
 888
 889   SlotIndex PrevEnd;
 890   LocMap::iterator I = locInts.begin();
 891
 892   // Iterate over the lexical scope ranges. Each time round the loop
 893   // we check the intervals for overlap with the end of the previous
 894   // range and the start of the next. The first range is handled as
 895   // a special case where there is no PrevEnd.
 896   for (const InsnRange &Range : Scope->getRanges()) {
 897     SlotIndex RStart = LIS.getInstructionIndex(*Range.first);
 898     SlotIndex REnd = LIS.getInstructionIndex(*Range.second);
 899
 900     // At the start of each iteration I has been advanced so that
 901     // I.stop() >= PrevEnd. Check for overlap.
 902     if (PrevEnd && I.start() < PrevEnd) {
 903       SlotIndex IStop = I.stop();
 904       DbgValueLocation Loc = I.value();
 905
 906       // Stop overlaps previous end - trim the end of the interval to
 907       // the scope range.
 908       I.setStopUnchecked(PrevEnd);
 909       ++I;
 910
 911       // If the interval also overlaps the start of the "next" (i.e.
 912       // current) range create a new interval for the remainder
 913       if (RStart < IStop)
 914         I.insert(RStart, IStop, Loc);
 915     }
 916
 917     // Advance I so that I.stop() >= RStart, and check for overlap.
 918     I.advanceTo(RStart);
 919     if (!I.valid())
 920       return;
 921
 922     // The end of a lexical scope range is the last instruction in the
 923     // range. To convert to an interval we need the index of the
 924     // instruction after it.
 925     REnd = REnd.getNextIndex();
 926
 927     // Advance I to first interval outside current range.
 928     I.advanceTo(REnd);
 929     if (!I.valid())
 930       return;
 931
 932     PrevEnd = REnd;
 933   }
 934
 935   // Check for overlap with end of final range.
 936   if (PrevEnd && I.start() < PrevEnd)
 937     I.setStopUnchecked(PrevEnd);
 938 }
 939
 940 void LDVImpl::computeIntervals() {
 941   LexicalScopes LS;
 942   LS.initialize(*MF);
 943
 944   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
 945     userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS);
 946     userValues[i]->mapVirtRegs(this);
 947   }
 948 }
 949
 950 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
 951   clear();
 952   MF = &mf;
 953   LIS = &pass.getAnalysis<LiveIntervals>();
 954   TRI = mf.getSubtarget().getRegisterInfo();
 955   LLVM_DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
 956                     << mf.getName() << " **********\n");
 957
 958   bool Changed = collectDebugValues(mf);
 959   computeIntervals();
 960   LLVM_DEBUG(print(dbgs()));
 961   ModifiedMF = Changed;
 962   return Changed;
 963 }
 964
 965 static void removeDebugValues(MachineFunction &mf) {
 966   for (MachineBasicBlock &MBB : mf) {
 967     for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) {
 968       if (!MBBI->isDebugValue()) {
 969         ++MBBI;
 970         continue;
 971       }
 972       MBBI = MBB.erase(MBBI);
 973     }
 974   }
 975 }
 976
 977 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
 978   if (!EnableLDV)
 979     return false;
 980   if (!mf.getFunction().getSubprogram()) {
 981     removeDebugValues(mf);
 982     return false;
 983   }
 984   if (!pImpl)
 985     pImpl = new LDVImpl(this);
 986   return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
 987 }
 988
 989 void LiveDebugVariables::releaseMemory() {
 990   if (pImpl)
 991     static_cast<LDVImpl*>(pImpl)->clear();
 992 }
 993
 994 LiveDebugVariables::~LiveDebugVariables() {
 995   if (pImpl)
 996     delete static_cast<LDVImpl*>(pImpl);
 997 }
 998
 999 //===----------------------------------------------------------------------===//
1000 //                           Live Range Splitting
1001 //===----------------------------------------------------------------------===//
1002
1003 bool
1004 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
1005                          LiveIntervals& LIS) {
1006   LLVM_DEBUG({
1007     dbgs() << "Splitting Loc" << OldLocNo << '\t';
1008     print(dbgs(), nullptr);
1009   });
1010   bool DidChange = false;
1011   LocMap::iterator LocMapI;
1012   LocMapI.setMap(locInts);
1013   for (unsigned i = 0; i != NewRegs.size(); ++i) {
1014     LiveInterval *LI = &LIS.getInterval(NewRegs[i]);
1015     if (LI->empty())
1016       continue;
1017
1018     // Don't allocate the new LocNo until it is needed.
1019     unsigned NewLocNo = UndefLocNo;
1020
1021     // Iterate over the overlaps between locInts and LI.
1022     LocMapI.find(LI->beginIndex());
1023     if (!LocMapI.valid())
1024       continue;
1025     LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
1026     LiveInterval::iterator LIE = LI->end();
1027     while (LocMapI.valid() && LII != LIE) {
1028       // At this point, we know that LocMapI.stop() > LII->start.
1029       LII = LI->advanceTo(LII, LocMapI.start());
1030       if (LII == LIE)
1031         break;
1032
1033       // Now LII->end > LocMapI.start(). Do we have an overlap?
1034       if (LocMapI.value().locNo() == OldLocNo && LII->start < LocMapI.stop()) {
1035         // Overlapping correct location. Allocate NewLocNo now.
1036         if (NewLocNo == UndefLocNo) {
1037           MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
1038           MO.setSubReg(locations[OldLocNo].getSubReg());
1039           NewLocNo = getLocationNo(MO);
1040           DidChange = true;
1041         }
1042
1043         SlotIndex LStart = LocMapI.start();
1044         SlotIndex LStop  = LocMapI.stop();
1045         DbgValueLocation OldLoc = LocMapI.value();
1046
1047         // Trim LocMapI down to the LII overlap.
1048         if (LStart < LII->start)
1049           LocMapI.setStartUnchecked(LII->start);
1050         if (LStop > LII->end)
1051           LocMapI.setStopUnchecked(LII->end);
1052
1053         // Change the value in the overlap. This may trigger coalescing.
1054         LocMapI.setValue(OldLoc.changeLocNo(NewLocNo));
1055
1056         // Re-insert any removed OldLocNo ranges.
1057         if (LStart < LocMapI.start()) {
1058           LocMapI.insert(LStart, LocMapI.start(), OldLoc);
1059           ++LocMapI;
1060           assert(LocMapI.valid() && "Unexpected coalescing");
1061         }
1062         if (LStop > LocMapI.stop()) {
1063           ++LocMapI;
1064           LocMapI.insert(LII->end, LStop, OldLoc);
1065           --LocMapI;
1066         }
1067       }
1068
1069       // Advance to the next overlap.
1070       if (LII->end < LocMapI.stop()) {
1071         if (++LII == LIE)
1072           break;
1073         LocMapI.advanceTo(LII->start);
1074       } else {
1075         ++LocMapI;
1076         if (!LocMapI.valid())
1077           break;
1078         LII = LI->advanceTo(LII, LocMapI.start());
1079       }
1080     }
1081   }
1082
1083   // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
1084   locations.erase(locations.begin() + OldLocNo);
1085   LocMapI.goToBegin();
1086   while (LocMapI.valid()) {
1087     DbgValueLocation v = LocMapI.value();
1088     if (v.locNo() == OldLocNo) {
1089       LLVM_DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
1090                         << LocMapI.stop() << ")\n");
1091       LocMapI.erase();
1092     } else {
1093       // Undef values always have location number UndefLocNo, so don't change
1094       // locNo in that case. See getLocationNo().
1095       if (!v.isUndef() && v.locNo() > OldLocNo)
1096         LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
1097       ++LocMapI;
1098     }
1099   }
1100
1101   LLVM_DEBUG({
1102     dbgs() << "Split result: \t";
1103     print(dbgs(), nullptr);
1104   });
1105   return DidChange;
1106 }
1107
1108 bool
1109 UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
1110                          LiveIntervals &LIS) {
1111   bool DidChange = false;
1112   // Split locations referring to OldReg. Iterate backwards so splitLocation can
1113   // safely erase unused locations.
1114   for (unsigned i = locations.size(); i ; --i) {
1115     unsigned LocNo = i-1;
1116     const MachineOperand *Loc = &locations[LocNo];
1117     if (!Loc->isReg() || Loc->getReg() != OldReg)
1118       continue;
1119     DidChange |= splitLocation(LocNo, NewRegs, LIS);
1120   }
1121   return DidChange;
1122 }
1123
1124 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
1125   bool DidChange = false;
1126   for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
1127     DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
1128
1129   if (!DidChange)
1130     return;
1131
1132   // Map all of the new virtual registers.
1133   UserValue *UV = lookupVirtReg(OldReg);
1134   for (unsigned i = 0; i != NewRegs.size(); ++i)
1135     mapVirtReg(NewRegs[i], UV);
1136 }
1137
1138 void LiveDebugVariables::
1139 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
1140   if (pImpl)
1141     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
1142 }
1143
1144 void UserValue::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
1145                                  const TargetInstrInfo &TII,
1146                                  const TargetRegisterInfo &TRI,
1147                                  SpillOffsetMap &SpillOffsets) {
1148   // Build a set of new locations with new numbers so we can coalesce our
1149   // IntervalMap if two vreg intervals collapse to the same physical location.
1150   // Use MapVector instead of SetVector because MapVector::insert returns the
1151   // position of the previously or newly inserted element. The boolean value
1152   // tracks if the location was produced by a spill.
1153   // FIXME: This will be problematic if we ever support direct and indirect
1154   // frame index locations, i.e. expressing both variables in memory and
1155   // 'int x, *px = &x'. The "spilled" bit must become part of the location.
1156   MapVector<MachineOperand, std::pair<bool, unsigned>> NewLocations;
1157   SmallVector<unsigned, 4> LocNoMap(locations.size());
1158   for (unsigned I = 0, E = locations.size(); I != E; ++I) {
1159     bool Spilled = false;
1160     unsigned SpillOffset = 0;
1161     MachineOperand Loc = locations[I];
1162     // Only virtual registers are rewritten.
1163     if (Loc.isReg() && Loc.getReg() &&
1164         TargetRegisterInfo::isVirtualRegister(Loc.getReg())) {
1165       unsigned VirtReg = Loc.getReg();
1166       if (VRM.isAssignedReg(VirtReg) &&
1167           TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) {
1168         // This can create a %noreg operand in rare cases when the sub-register
1169         // index is no longer available. That means the user value is in a
1170         // non-existent sub-register, and %noreg is exactly what we want.
1171         Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
1172       } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
1173         // Retrieve the stack slot offset.
1174         unsigned SpillSize;
1175         const MachineRegisterInfo &MRI = MF.getRegInfo();
1176         const TargetRegisterClass *TRC = MRI.getRegClass(VirtReg);
1177         bool Success = TII.getStackSlotRange(TRC, Loc.getSubReg(), SpillSize,
1178                                              SpillOffset, MF);
1179
1180         // FIXME: Invalidate the location if the offset couldn't be calculated.
1181         (void)Success;
1182
1183         Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
1184         Spilled = true;
1185       } else {
1186         Loc.setReg(0);
1187         Loc.setSubReg(0);
1188       }
1189     }
1190
1191     // Insert this location if it doesn't already exist and record a mapping
1192     // from the old number to the new number.
1193     auto InsertResult = NewLocations.insert({Loc, {Spilled, SpillOffset}});
1194     unsigned NewLocNo = std::distance(NewLocations.begin(), InsertResult.first);
1195     LocNoMap[I] = NewLocNo;
1196   }
1197
1198   // Rewrite the locations and record the stack slot offsets for spills.
1199   locations.clear();
1200   SpillOffsets.clear();
1201   for (auto &Pair : NewLocations) {
1202     bool Spilled;
1203     unsigned SpillOffset;
1204     std::tie(Spilled, SpillOffset) = Pair.second;
1205     locations.push_back(Pair.first);
1206     if (Spilled) {
1207       unsigned NewLocNo = std::distance(&*NewLocations.begin(), &Pair);
1208       SpillOffsets[NewLocNo] = SpillOffset;
1209     }
1210   }
1211
1212   // Update the interval map, but only coalesce left, since intervals to the
1213   // right use the old location numbers. This should merge two contiguous
1214   // DBG_VALUE intervals with different vregs that were allocated to the same
1215   // physical register.
1216   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
1217     DbgValueLocation Loc = I.value();
1218     // Undef values don't exist in locations (and thus not in LocNoMap either)
1219     // so skip over them. See getLocationNo().
1220     if (Loc.isUndef())
1221       continue;
1222     unsigned NewLocNo = LocNoMap[Loc.locNo()];
1223     I.setValueUnchecked(Loc.changeLocNo(NewLocNo));
1224     I.setStart(I.start());
1225   }
1226 }
1227
1228 /// Find an iterator for inserting a DBG_VALUE instruction.
1229 static MachineBasicBlock::iterator
1230 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
1231                    LiveIntervals &LIS) {
1232   SlotIndex Start = LIS.getMBBStartIdx(MBB);
1233   Idx = Idx.getBaseIndex();
1234
1235   // Try to find an insert location by going backwards from Idx.
1236   MachineInstr *MI;
1237   while (!(MI = LIS.getInstructionFromIndex(Idx))) {
1238     // We've reached the beginning of MBB.
1239     if (Idx == Start) {
1240       MachineBasicBlock::iterator I = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
1241       return I;
1242     }
1243     Idx = Idx.getPrevIndex();
1244   }
1245
1246   // Don't insert anything after the first terminator, though.
1247   return MI->isTerminator() ? MBB->getFirstTerminator() :
1248                               std::next(MachineBasicBlock::iterator(MI));
1249 }
1250
1251 /// Find an iterator for inserting the next DBG_VALUE instruction
1252 /// (or end if no more insert locations found).
1253 static MachineBasicBlock::iterator
1254 findNextInsertLocation(MachineBasicBlock *MBB,
1255                        MachineBasicBlock::iterator I,
1256                        SlotIndex StopIdx, MachineOperand &LocMO,
1257                        LiveIntervals &LIS,
1258                        const TargetRegisterInfo &TRI) {
1259   if (!LocMO.isReg())
1260     return MBB->instr_end();
1261   unsigned Reg = LocMO.getReg();
1262
1263   // Find the next instruction in the MBB that define the register Reg.
1264   while (I != MBB->end() && !I->isTerminator()) {
1265     if (!LIS.isNotInMIMap(*I) &&
1266         SlotIndex::isEarlierEqualInstr(StopIdx, LIS.getInstructionIndex(*I)))
1267       break;
1268     if (I->definesRegister(Reg, &TRI))
1269       // The insert location is directly after the instruction/bundle.
1270       return std::next(I);
1271     ++I;
1272   }
1273   return MBB->end();
1274 }
1275
1276 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
1277                                  SlotIndex StopIdx, DbgValueLocation Loc,
1278                                  bool Spilled, unsigned SpillOffset,
1279                                  LiveIntervals &LIS, const TargetInstrInfo &TII,
1280                                  const TargetRegisterInfo &TRI) {
1281   SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB);
1282   // Only search within the current MBB.
1283   StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx;
1284   MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS);
1285   // Undef values don't exist in locations so create new "noreg" register MOs
1286   // for them. See getLocationNo().
1287   MachineOperand MO = !Loc.isUndef() ?
1288     locations[Loc.locNo()] :
1289     MachineOperand::CreateReg(/* Reg */ 0, /* isDef */ false, /* isImp */ false,
1290                               /* isKill */ false, /* isDead */ false,
1291                               /* isUndef */ false, /* isEarlyClobber */ false,
1292                               /* SubReg */ 0, /* isDebug */ true);
1293
1294   ++NumInsertedDebugValues;
1295
1296   assert(cast<DILocalVariable>(Variable)
1297              ->isValidLocationForIntrinsic(getDebugLoc()) &&
1298          "Expected inlined-at fields to agree");
1299
1300   // If the location was spilled, the new DBG_VALUE will be indirect. If the
1301   // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate
1302   // that the original virtual register was a pointer. Also, add the stack slot
1303   // offset for the spilled register to the expression.
1304   const DIExpression *Expr = Expression;
1305   uint8_t DIExprFlags = DIExpression::ApplyOffset;
1306   bool IsIndirect = Loc.wasIndirect();
1307   if (Spilled) {
1308     if (IsIndirect)
1309       DIExprFlags |= DIExpression::DerefAfter;
1310     Expr =
1311         DIExpression::prepend(Expr, DIExprFlags, SpillOffset);
1312     IsIndirect = true;
1313   }
1314
1315   assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index");
1316
1317   do {
1318     BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE),
1319             IsIndirect, MO, Variable, Expr);
1320
1321     // Continue and insert DBG_VALUES after every redefinition of register
1322     // associated with the debug value within the range
1323     I = findNextInsertLocation(MBB, I, StopIdx, MO, LIS, TRI);
1324   } while (I != MBB->end());
1325 }
1326
1327 void UserLabel::insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx,
1328                                  LiveIntervals &LIS,
1329                                  const TargetInstrInfo &TII) {
1330   MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS);
1331   ++NumInsertedDebugLabels;
1332   BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_LABEL))
1333       .addMetadata(Label);
1334 }
1335
1336 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
1337                                 const TargetInstrInfo &TII,
1338                                 const TargetRegisterInfo &TRI,
1339                                 const SpillOffsetMap &SpillOffsets) {
1340   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
1341
1342   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
1343     SlotIndex Start = I.start();
1344     SlotIndex Stop = I.stop();
1345     DbgValueLocation Loc = I.value();
1346     auto SpillIt =
1347         !Loc.isUndef() ? SpillOffsets.find(Loc.locNo()) : SpillOffsets.end();
1348     bool Spilled = SpillIt != SpillOffsets.end();
1349     unsigned SpillOffset = Spilled ? SpillIt->second : 0;
1350
1351     LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo());
1352     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
1353     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
1354
1355     LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1356     insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII,
1357                      TRI);
1358     // This interval may span multiple basic blocks.
1359     // Insert a DBG_VALUE into each one.
1360     while (Stop > MBBEnd) {
1361       // Move to the next block.
1362       Start = MBBEnd;
1363       if (++MBB == MFEnd)
1364         break;
1365       MBBEnd = LIS.getMBBEndIdx(&*MBB);
1366       LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1367       insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII,
1368                        TRI);
1369     }
1370     LLVM_DEBUG(dbgs() << '\n');
1371     if (MBB == MFEnd)
1372       break;
1373
1374     ++I;
1375   }
1376 }
1377
1378 void UserLabel::emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII) {
1379   LLVM_DEBUG(dbgs() << "\t" << loc);
1380   MachineFunction::iterator MBB = LIS.getMBBFromIndex(loc)->getIterator();
1381
1382   LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB));
1383   insertDebugLabel(&*MBB, loc, LIS, TII);
1384
1385   LLVM_DEBUG(dbgs() << '\n');
1386 }
1387
1388 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
1389   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
1390   if (!MF)
1391     return;
1392   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1393   SpillOffsetMap SpillOffsets;
1394   for (auto &userValue : userValues) {
1395     LLVM_DEBUG(userValue->print(dbgs(), TRI));
1396     userValue->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets);
1397     userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets);
1398   }
1399   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG LABELS **********\n");
1400   for (auto &userLabel : userLabels) {
1401     LLVM_DEBUG(userLabel->print(dbgs(), TRI));
1402     userLabel->emitDebugLabel(*LIS, *TII);
1403   }
1404   EmitDone = true;
1405 }
1406
1407 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
1408   if (pImpl)
1409     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
1410 }
1411
1412 bool LiveDebugVariables::doInitialization(Module &M) {
1413   return Pass::doInitialization(M);
1414 }
1415
1416 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1417 LLVM_DUMP_METHOD void LiveDebugVariables::dump() const {
1418   if (pImpl)
1419     static_cast<LDVImpl*>(pImpl)->print(dbgs());
1420 }
1421 #endif