[LiveDebugValues] 1/4 Install an implementation-picking LiveDebugValues pass

[jmorse]

Summary

(Context: this thread http://lists.llvm.org/pipermail/llvm-dev/2020-June/142368.html )

This patch series is preceeded by:

mkdir llvm/lib/CodeGen/LiveDebugValues
git mv llvm/lib/CodeGen/LiveDebugValues.cpp llvm/lib/CodeGen/VarLocBasedImpl.cpp

Plus moving the source file in CMakeLists.txt. I've assumed that such a file movement doesn't need reviewing; I can upload a review if anyone wants a closer look though.

This patch renames the current LiveDebugValues class to "InstrRefBasedLDV" and removes the pass-registration code from it. It creates a separate LiveDebugValues class that deals with pass registration and management, that calls through to InstrRefBasedLDV::ExtendRanges when runOnMachineFunction is called. This is done through the "LDVImpl" abstract class, so that a future patch can install the new instruction-referencing LiveDebugValues implementation and have it picked at runtime.

I'm not fixed to any particular symbol name in this, very happy to receive feedback on naming. I'm also aware of the "favour composition over inheritance" principle, but I believe this situation is exactly what abstract base classes (LDVImpl) are for.

[djtodoro]

llvm/lib/CodeGen/CMakeLists.txt

185

We can add new subdirectory here as:
add_subdirectory(LiveDebugValues)

and then, add another CMakeLists.txt with in LiveDebugValues/ and play with all of this within that CMake file locally? wdyt?

[djtodoro]

Thanks a lot for this work!

[jmorse]

llvm/lib/CodeGen/CMakeLists.txt

185

I've shied away from this due to being a CMake novice, but my understanding is we'd need to either:

• Append the sources to the "LLVMCodeGen" library sources list from inside that new CMakeLists.txt, or
• Define a new "llvm_component_library" for LiveDebugValues, which seems like overkill.

Referring to the source files from this CMakeList avoided me having to think about that; I can implement the first item if it's preferable for each directory to have a CMakeLists.txt.

[vsk]

Neat! Could you please clang-format the diff and add in license headers?

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

52

Can this remain private?

70

nit, this seems simpler to just inline into the class definition?

[djtodoro]

llvm/lib/CodeGen/CMakeLists.txt

185

I am OK with either way. If other folks do not have impression about that, this part is OK for me as well.

Referring to the source files from this CMakeList avoided me having to think about that; I can implement the first item if it's preferable for each directory to have a CMakeLists.txt.

I am not sure we need that if we do not consider the item 2.

[djtodoro]

Instead of git mv llvm/lib/CodeGen/LiveDebugValues.cpp llvm/lib/CodeGen/VarLocBasedImpl.cpp
it should be as following:
git mv llvm/lib/CodeGen/LiveDebugValues.cpp llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

Plus moving the source file in CMakeLists.txt. I've assumed that such a file movement doesn't need reviewing; I can upload a review if anyone wants a closer look though.

I'd prefer adding all the patches in the stack, since there might be developers using some scripts for applying the patches automatically from Phabricator.

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

2

Same as above.

23

According to the LLVM coding standard, this should be included first.

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.h

2

I think we are missing the file header at the beginning of the file.

21

// namespace SharedLiveDebugValues

25

// namespace llvm

[jmorse]

clang-format, add file headers, address some review comments

[jmorse]

Thanks for the feedback,

In D83046#2135151, @djtodoro wrote:

Instead of git mv llvm/lib/CodeGen/LiveDebugValues.cpp llvm/lib/CodeGen/VarLocBasedImpl.cpp
it should be as following:
git mv llvm/lib/CodeGen/LiveDebugValues.cpp llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

Ah yep, missed that,

I'd prefer adding all the patches in the stack, since there might be developers using some scripts for applying the patches automatically from Phabricator.

Sure, I'll upload that shortly.

[djtodoro]

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

18

According to the LLVM coding standard, this should be included first.

[djtodoro]

Thanks for addressing comments! One nit included.

[jmorse]

Move include to start of file; was on autopilot sorry.

[djtodoro]

Super nits included.

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

14

I think this include is redundant.

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

1792

clang-format please

[djtodoro]

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.h

2

And since this is a header file we need:
-*- C++ -*-

[jmorse]

Address @djtodoro 's comments (remove header, add C++ indicator, clang-format).

I'd prefer to leave CMakeLists.txt as it is (in this revision) unless anyone has strong feelings about it.

[jmorse]

NB: landing now-ish as recent feedback is all nits, and in the "main" patch (D83047) we've come to the conclusion that this should land guarded by an experimental switch (which is what this patch does).

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   TwoAddressInstructionPass.cpp
   UnreachableBlockElim.cpp
   ValueTypes.cpp
   VirtRegMap.cpp
   WasmEHPrepare.cpp
   WinEHPrepare.cpp
   XRayInstrumentation.cpp
 
+  LiveDebugValues/LiveDebugValues.cpp
   LiveDebugValues/VarLocBasedImpl.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/CodeGen
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/CodeGen/PBQP
 
   LINK_LIBS ${LLVM_PTHREAD_LIB}
 
   DEPENDS
   intrinsics_gen
   )
 
 add_subdirectory(SelectionDAG)
 add_subdirectory(AsmPrinter)
 add_subdirectory(MIRParser)
 add_subdirectory(GlobalISel)

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.h

+//===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------*- C++ -*---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/TargetPassConfig.h"
+
+namespace llvm {
+
+// Inline namespace for types / symbols shared between different
+// LiveDebugValues implementations.
+inline namespace SharedLiveDebugValues {
+
+// Expose a base class for LiveDebugValues interfaces to inherit from. This
+// allows the generic LiveDebugValues pass handles to call into the
+// implementation.
+class LDVImpl {
+public:
+  virtual bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) = 0;
+  virtual ~LDVImpl() {}
+};
+
+} // namespace SharedLiveDebugValues
+
+// Factory functions for LiveDebugValues implementations.
+extern LDVImpl *makeVarLocBasedLiveDebugValues();
+} // namespace llvm

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

+//===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "LiveDebugValues.h"
+
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+
+/// \file LiveDebugValues.cpp
+///
+/// The LiveDebugValues pass extends the range of variable locations
+/// (specified by DBG_VALUE instructions) from single blocks to successors
+/// and any other code locations where the variable location is valid.
+/// There are currently two implementations: the "VarLoc" implementation
+/// explicitly tracks the location of a variable, while the "InstrRef"
+/// implementation tracks the values defined by instructions through locations.
+///
+/// This file implements neither; it merely registers the pass, allows the
+/// user to pick which implementation will be used to propagate variable
+/// locations.
+
+#define DEBUG_TYPE "livedebugvalues"
+
+using namespace llvm;
+
+/// Generic LiveDebugValues pass. Calls through to VarLocBasedLDV or
+/// InstrRefBasedLDV to perform location propagation, via the LDVImpl
+/// base class.
+class LiveDebugValues : public MachineFunctionPass {
+public:
+  static char ID;
+
+  LiveDebugValues();
+  ~LiveDebugValues() { delete TheImpl; }
+
+  /// Calculate the liveness information for the given machine function.
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  MachineFunctionProperties getRequiredProperties() const override {
+    return MachineFunctionProperties().set(
+        MachineFunctionProperties::Property::NoVRegs);
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+private:
+  LDVImpl *TheImpl;
+};
+
+char LiveDebugValues::ID = 0;
+
+char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
+
+INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis", false,
+                false)
+
+/// Default construct and initialize the pass.
+LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
+  initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
+  TheImpl = llvm::makeVarLocBasedLiveDebugValues();
+}
+
+bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
+  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
+  return TheImpl->ExtendRanges(MF, TPC);
+}

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

-//===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------------------===//
+//===- VarLocBasedImpl.cpp - Tracking Debug Value MIs with VarLoc class----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
-/// \file LiveDebugValues.cpp
+/// \file VarLocBasedImpl.cpp
 ///
 /// LiveDebugValues is an optimistic "available expressions" dataflow
 /// algorithm. The set of expressions is the set of machine locations
 /// (registers, spill slots, constants) that a variable fragment might be
 /// located, qualified by a DIExpression and indirect-ness flag, while each
 /// variable is identified by a DebugVariable object. The availability of an
 /// expression begins when a DBG_VALUE instruction specifies the location of a
 /// DebugVariable, and continues until that location is clobbered or
 /// re-specified by a different DBG_VALUE for the same DebugVariable.
 ///
+/// The output of LiveDebugValues is additional DBG_VALUE instructions,
+/// placed to extend variable locations as far they're available. This file
+/// and the VarLocBasedLDV class is an implementation that explicitly tracks
+/// locations, using the VarLoc class.
+///
 /// The cannonical "available expressions" problem doesn't have expression
 /// clobbering, instead when a variable is re-assigned, any expressions using
 /// that variable get invalidated. LiveDebugValues can map onto "available
 /// expressions" by having every register represented by a variable, which is
 /// used in an expression that becomes available at a DBG_VALUE instruction.
 /// When the register is clobbered, its variable is effectively reassigned, and
 /// expressions computed from it become unavailable. A similar construct is
 /// needed when a DebugVariable has its location re-specified, to invalidate

 /// don't enumerate all possible variable locations before exploring the
 /// function: when a new location is discovered, all blocks previously explored
 /// were implicitly "False" but unrecorded, and become explicitly "False" when
 /// a new VarLoc is created with its bit not set in predecessor InLocs or
 /// OutLocs.
 ///
 //===----------------------------------------------------------------------===//
 
+#include "LiveDebugValues.h"
+
 #include "llvm/ADT/CoalescingBitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/UniqueVector.h"
struct LocIndex {
   static auto indexRangeForLocation(const VarLocSet &Set,
                                     u32_location_t Location) {
     uint64_t Start = LocIndex(Location, 0).getAsRawInteger();
     uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger();
     return Set.half_open_range(Start, End);
   }
 };
 
-class LiveDebugValues : public MachineFunctionPass {
+class VarLocBasedLDV : public LDVImpl {
 private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
+  TargetPassConfig *TPC;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
   VarLocSet::Allocator Alloc;
 
   enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
 
   using FragmentInfo = DIExpression::FragmentInfo;
   using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
MachineInstr *BuildDbgValue(MachineFunction &MF) const {
         return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr);
       }
       case EntryValueBackupKind:
       case EntryValueCopyBackupKind:
       case InvalidKind:
         llvm_unreachable(
             "Tried to produce DBG_VALUE for invalid or backup VarLoc");
       }
-      llvm_unreachable("Unrecognized LiveDebugValues.VarLoc.Kind enum");
+      llvm_unreachable("Unrecognized VarLocBasedLDV.VarLoc.Kind enum");
     }
 
     /// Is the Loc field a constant or constant object?
     bool isConstant() const { return Kind == ImmediateKind; }
 
     /// Check if the Loc field is an entry backup location.
     bool isEntryBackupLoc() const {
       return Kind == EntryValueBackupKind || Kind == EntryValueCopyBackupKind;
bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
             const VarLocMap &VarLocIDs,
             SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
             SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks);
 
   /// Create DBG_VALUE insts for inlocs that have been propagated but
   /// had their instruction creation deferred.
   void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs);
 
-  bool ExtendRanges(MachineFunction &MF);
+  bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC);
 
 public:
-  static char ID;
-
   /// Default construct and initialize the pass.
-  LiveDebugValues();
+  VarLocBasedLDV();
 
-  /// Tell the pass manager which passes we depend on and what
-  /// information we preserve.
-  void getAnalysisUsage(AnalysisUsage &AU) const override;
-
-  MachineFunctionProperties getRequiredProperties() const override {
-    return MachineFunctionProperties().set(
-        MachineFunctionProperties::Property::NoVRegs);
-  }
+  ~VarLocBasedLDV();
 
   /// Print to ostream with a message.
   void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
                         const VarLocMap &VarLocIDs, const char *msg,
                         raw_ostream &Out) const;
-
-  /// Calculate the liveness information for the given machine function.
-  bool runOnMachineFunction(MachineFunction &MF) override;
 };
 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 //            Implementation
 //===----------------------------------------------------------------------===//
 
-char LiveDebugValues::ID = 0;
-
-char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
-
-INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
-                false, false)
-
-/// Default construct and initialize the pass.
-LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
-  initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
-}
+VarLocBasedLDV::VarLocBasedLDV() { }
 
-/// Tell the pass manager which passes we depend on and what information we
-/// preserve.
-void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesCFG();
-  MachineFunctionPass::getAnalysisUsage(AU);
-}
+VarLocBasedLDV::~VarLocBasedLDV() { }
 
 /// Erase a variable from the set of open ranges, and additionally erase any
 /// fragments that may overlap it. If the VarLoc is a buckup location, erase
 /// the variable from the EntryValuesBackupVars set, indicating we should stop
 /// tracking its backup entry location. Otherwise, if the VarLoc is primary
 /// location, erase the variable from the Vars set.
-void LiveDebugValues::OpenRangesSet::erase(const VarLoc &VL) {
+void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
   // Erasure helper.
   auto DoErase = [VL, this](DebugVariable VarToErase) {
     auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
     auto It = EraseFrom->find(VarToErase);
     if (It != EraseFrom->end()) {
       LocIndex ID = It->second;
       VarLocs.reset(ID.getAsRawInteger());
       EraseFrom->erase(It);
void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
   // possible bits.
   FragmentInfo ThisFragment = Var.getFragmentOrDefault();
 
   // There may be fragments that overlap the designated fragment. Look them up
   // in the pre-computed overlap map, and erase them too.
   auto MapIt = OverlappingFragments.find({Var.getVariable(), ThisFragment});
   if (MapIt != OverlappingFragments.end()) {
     for (auto Fragment : MapIt->second) {
-      LiveDebugValues::OptFragmentInfo FragmentHolder;
+      VarLocBasedLDV::OptFragmentInfo FragmentHolder;
       if (!DebugVariable::isDefaultFragment(Fragment))
-        FragmentHolder = LiveDebugValues::OptFragmentInfo(Fragment);
+        FragmentHolder = VarLocBasedLDV::OptFragmentInfo(Fragment);
       DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()});
     }
   }
 }
 
-void LiveDebugValues::OpenRangesSet::erase(const VarLocSet &KillSet,
+void VarLocBasedLDV::OpenRangesSet::erase(const VarLocSet &KillSet,
                                            const VarLocMap &VarLocIDs) {
   VarLocs.intersectWithComplement(KillSet);
   for (uint64_t ID : KillSet) {
     const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)];
     auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
     EraseFrom->erase(VL->Var);
   }
 }
 
-void LiveDebugValues::OpenRangesSet::insert(LocIndex VarLocID,
+void VarLocBasedLDV::OpenRangesSet::insert(LocIndex VarLocID,
                                             const VarLoc &VL) {
   auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
   VarLocs.set(VarLocID.getAsRawInteger());
   InsertInto->insert({VL.Var, VarLocID});
 }
 
 /// Return the Loc ID of an entry value backup location, if it exists for the
 /// variable.
 llvm::Optional<LocIndex>
-LiveDebugValues::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
+VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
   auto It = EntryValuesBackupVars.find(Var);
   if (It != EntryValuesBackupVars.end())
     return It->second;
 
   return llvm::None;
 }
 
-void LiveDebugValues::collectIDsForRegs(VarLocSet &Collected,
+void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected,
                                         const DefinedRegsSet &Regs,
                                         const VarLocSet &CollectFrom) const {
   assert(!Regs.empty() && "Nothing to collect");
   SmallVector<uint32_t, 32> SortedRegs;
   for (Register Reg : Regs)
     SortedRegs.push_back(Reg);
   array_pod_sort(SortedRegs.begin(), SortedRegs.end());
   auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front()));
for (uint32_t Reg : SortedRegs) {
     for (; It != End && *It < FirstInvalidIndex; ++It)
       Collected.set(*It);
 
     if (It == End)
       return;
   }
 }
 
-void LiveDebugValues::getUsedRegs(const VarLocSet &CollectFrom,
+void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom,
                                   SmallVectorImpl<uint32_t> &UsedRegs) const {
   // All register-based VarLocs are assigned indices greater than or equal to
   // FirstRegIndex.
   uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1);
   uint64_t FirstInvalidIndex =
       LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation);
   for (auto It = CollectFrom.find(FirstRegIndex),
             End = CollectFrom.find(FirstInvalidIndex);
void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom,
   }
 }
 
 //===----------------------------------------------------------------------===//
 //            Debug Range Extension Implementation
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG
-void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
+void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF,
                                        const VarLocInMBB &V,
                                        const VarLocMap &VarLocIDs,
                                        const char *msg,
                                        raw_ostream &Out) const {
   Out << '\n' << msg << '\n';
   for (const MachineBasicBlock &BB : MF) {
     if (!V.count(&BB))
       continue;
     const VarLocSet &L = getVarLocsInMBB(&BB, V);
     if (L.empty())
       continue;
     Out << "MBB: " << BB.getNumber() << ":\n";
     for (uint64_t VLL : L) {
       const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)];
       Out << " Var: " << VL.Var.getVariable()->getName();
       Out << " MI: ";
       VL.dump(TRI, Out);
     }
   }
   Out << "\n";
 }
 #endif
 
-LiveDebugValues::VarLoc::SpillLoc
-LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
+VarLocBasedLDV::VarLoc::SpillLoc
+VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
   assert(MI.hasOneMemOperand() &&
          "Spill instruction does not have exactly one memory operand?");
   auto MMOI = MI.memoperands_begin();
   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
   assert(PVal->kind() == PseudoSourceValue::FixedStack &&
          "Inconsistent memory operand in spill instruction");
   int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
   const MachineBasicBlock *MBB = MI.getParent();
   Register Reg;
   int Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
   return {Reg, Offset};
 }
 
 /// Try to salvage the debug entry value if we encounter a new debug value
 /// describing the same parameter, otherwise stop tracking the value. Return
 /// true if we should stop tracking the entry value, otherwise return false.
-bool LiveDebugValues::removeEntryValue(const MachineInstr &MI,
+bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
                                        OpenRangesSet &OpenRanges,
                                        VarLocMap &VarLocIDs,
                                        const VarLoc &EntryVL) {
   // Skip the DBG_VALUE which is the debug entry value itself.
   if (MI.isIdenticalTo(EntryVL.MI))
     return false;
 
   // If the parameter's location is not register location, we can not track
if (TrySalvageEntryValue) {
     }
   }
 
   return true;
 }
 
 /// End all previous ranges related to @MI and start a new range from @MI
 /// if it is a DBG_VALUE instr.
-void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
+void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
                                          OpenRangesSet &OpenRanges,
                                          VarLocMap &VarLocIDs) {
   if (!MI.isDebugValue())
     return;
   const DILocalVariable *Var = MI.getDebugVariable();
   const DIExpression *Expr = MI.getDebugExpression();
   const DILocation *DebugLoc = MI.getDebugLoc();
   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
assert(MI.getDebugOperand(0).isReg() &&
            MI.getDebugOperand(0).getReg() == 0 &&
            "Unexpected non-undef DBG_VALUE encountered");
     VarLoc VL(MI, LS);
     OpenRanges.erase(VL);
   }
 }
 
 /// Turn the entry value backup locations into primary locations.
-void LiveDebugValues::emitEntryValues(MachineInstr &MI,
+void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
                                       OpenRangesSet &OpenRanges,
                                       VarLocMap &VarLocIDs,
                                       TransferMap &Transfers,
                                       VarLocSet &KillSet) {
   // Do not insert entry value locations after a terminator.
   if (MI.isTerminator())
     return;
 
void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
   }
 }
 
 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
 /// new VarLoc. If \p NewReg is different than default zero value then the
 /// new location will be register location created by the copy like instruction,
 /// otherwise it is variable's location on the stack.
-void LiveDebugValues::insertTransferDebugPair(
+void VarLocBasedLDV::insertTransferDebugPair(
     MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
     VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
     Register NewReg) {
   const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
 
   auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) {
     LocIndex LocId = VarLocIDs.insert(VL);
 
case TransferKind::TransferRestore: {
     });
     return;
   }
   }
   llvm_unreachable("Invalid transfer kind");
 }
 
 /// A definition of a register may mark the end of a range.
-void LiveDebugValues::transferRegisterDef(
+void VarLocBasedLDV::transferRegisterDef(
     MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
     TransferMap &Transfers) {
 
   // Meta Instructions do not affect the debug liveness of any register they
   // define.
   if (MI.isMetaInstruction())
     return;
 
void VarLocBasedLDV::transferRegisterDef(
 
   if (DeadRegs.empty())
     return;
 
   VarLocSet KillSet(Alloc);
   collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs());
   OpenRanges.erase(KillSet, VarLocIDs);
 
-  if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
+  if (TPC) {
     auto &TM = TPC->getTM<TargetMachine>();
     if (TM.Options.ShouldEmitDebugEntryValues())
       emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
   }
 }
 
-bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI,
+bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI,
                                          MachineFunction *MF) {
   // TODO: Handle multiple stores folded into one.
   if (!MI.hasOneMemOperand())
     return false;
 
   if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
     return false; // This is not a spill instruction, since no valid size was
                   // returned from either function.
 
   return true;
 }
 
-bool LiveDebugValues::isLocationSpill(const MachineInstr &MI,
+bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI,
                                       MachineFunction *MF, Register &Reg) {
   if (!isSpillInstruction(MI, MF))
     return false;
 
   auto isKilledReg = [&](const MachineOperand MO, Register &Reg) {
     if (!MO.isReg() || !MO.isUse()) {
       Reg = 0;
       return false;
if (Reg != 0) {
           return true;
       }
     }
   }
   // Return false if we didn't find spilled register.
   return false;
 }
 
-Optional<LiveDebugValues::VarLoc::SpillLoc>
-LiveDebugValues::isRestoreInstruction(const MachineInstr &MI,
+Optional<VarLocBasedLDV::VarLoc::SpillLoc>
+VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI,
                                       MachineFunction *MF, Register &Reg) {
   if (!MI.hasOneMemOperand())
     return None;
 
   // FIXME: Handle folded restore instructions with more than one memory
   // operand.
   if (MI.getRestoreSize(TII)) {
     Reg = MI.getOperand(0).getReg();
     return extractSpillBaseRegAndOffset(MI);
   }
   return None;
 }
 
 /// A spilled register may indicate that we have to end the current range of
 /// a variable and create a new one for the spill location.
 /// A restored register may indicate the reverse situation.
 /// We don't want to insert any instructions in process(), so we just create
 /// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
 /// It will be inserted into the BB when we're done iterating over the
 /// instructions.
-void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
+void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
                                                  OpenRangesSet &OpenRanges,
                                                  VarLocMap &VarLocIDs,
                                                  TransferMap &Transfers) {
   MachineFunction *MF = MI.getMF();
   TransferKind TKind;
   Register Reg;
   Optional<VarLoc::SpillLoc> Loc;
 
for (uint64_t ID : TransferCandidates) {
     // if that is in fact correct.
     return;
   }
 }
 
 /// If \p MI is a register copy instruction, that copies a previously tracked
 /// value from one register to another register that is callee saved, we
 /// create new DBG_VALUE instruction  described with copy destination register.
-void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
+void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
                                            OpenRangesSet &OpenRanges,
                                            VarLocMap &VarLocIDs,
                                            TransferMap &Transfers) {
   auto DestSrc = TII->isCopyInstr(MI);
   if (!DestSrc)
     return;
 
   const MachineOperand *DestRegOp = DestSrc->Destination;
insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx,
                             TransferKind::TransferCopy, DestReg);
     // FIXME: A comment should explain why it's correct to return early here,
     // if that is in fact correct.
     return;
   }
 }
 
 /// Terminate all open ranges at the end of the current basic block.
-bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB,
+bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
                                          OpenRangesSet &OpenRanges,
                                          VarLocInMBB &OutLocs,
                                          const VarLocMap &VarLocIDs) {
   bool Changed = false;
 
   LLVM_DEBUG(for (uint64_t ID
                   : OpenRanges.getVarLocs()) {
     // Copy OpenRanges to OutLocs, if not already present.

 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
 /// known-to-overlap fragments are present".
 /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
 ///           fragment usage.
 /// \param SeenFragments Map from DILocalVariable to all fragments of that
 ///           Variable which are known to exist.
 /// \param OverlappingFragments The overlap map being constructed, from one
 ///           Var/Fragment pair to a vector of fragments known to overlap.
-void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI,
+void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI,
                                             VarToFragments &SeenFragments,
                                             OverlapMap &OverlappingFragments) {
   DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
   FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
 
   // If this is the first sighting of this variable, then we are guaranteed
   // there are currently no overlapping fragments either. Initialize the set
if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
       ASeenFragmentsOverlaps->second.push_back(ThisFragment);
     }
   }
 
   AllSeenFragments.insert(ThisFragment);
 }
 
 /// This routine creates OpenRanges.
-void LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
+void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
                               VarLocMap &VarLocIDs, TransferMap &Transfers) {
   transferDebugValue(MI, OpenRanges, VarLocIDs);
   transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers);
   transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
   transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
 }
 
 /// This routine joins the analysis results of all incoming edges in @MBB by
 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 /// source variable in all the predecessors of @MBB reside in the same location.
-bool LiveDebugValues::join(
+bool VarLocBasedLDV::join(
     MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
     const VarLocMap &VarLocIDs,
     SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
     SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
 
   VarLocSet InLocsT(Alloc); // Temporary incoming locations.
 
bool VarLocBasedLDV::join(
   if (ILS != InLocsT) {
     ILS = InLocsT;
     Changed = true;
   }
 
   return Changed;
 }
 
-void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
+void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                        VarLocMap &VarLocIDs) {
   // PendingInLocs records all locations propagated into blocks, which have
   // not had DBG_VALUE insts created. Go through and create those insts now.
   for (auto &Iter : PendingInLocs) {
     // Map is keyed on a constant pointer, unwrap it so we can insert insts.
     auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
     VarLocSet &Pending = *Iter.second.get();
 
     for (uint64_t ID : Pending) {
       // The ID location is live-in to MBB -- work out what kind of machine
       // location it is and create a DBG_VALUE.
       const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)];
       if (DiffIt.isEntryBackupLoc())
         continue;
       MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent());
       MBB.insert(MBB.instr_begin(), MI);
 
       (void)MI;
       LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
     }
   }
 }
 
-bool LiveDebugValues::isEntryValueCandidate(
+bool VarLocBasedLDV::isEntryValueCandidate(
     const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const {
   assert(MI.isDebugValue() && "This must be DBG_VALUE.");
 
   // TODO: Add support for local variables that are expressed in terms of
   // parameters entry values.
   // TODO: Add support for modified arguments that can be expressed
   // by using its entry value.
   auto *DIVar = MI.getDebugVariable();
for (const MachineOperand &MO : MI.operands())
     if (MO.isReg() && MO.isDef() && MO.getReg())
       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
         Regs.insert(*AI);
 }
 
 /// This routine records the entry values of function parameters. The values
 /// could be used as backup values. If we loose the track of some unmodified
 /// parameters, the backup values will be used as a primary locations.
-void LiveDebugValues::recordEntryValue(const MachineInstr &MI,
+void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
                                        const DefinedRegsSet &DefinedRegs,
                                        OpenRangesSet &OpenRanges,
                                        VarLocMap &VarLocIDs) {
-  if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
+  if (TPC) {
     auto &TM = TPC->getTM<TargetMachine>();
     if (!TM.Options.ShouldEmitDebugEntryValues())
       return;
   }
 
   DebugVariable V(MI.getDebugVariable(), MI.getDebugExpression(),
                   MI.getDebugLoc()->getInlinedAt());
 
DIExpression *NewExpr =
       DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue);
   VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr);
   LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup);
   OpenRanges.insert(EntryValLocID, EntryValLocAsBackup);
 }
 
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
-bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
+bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) {
   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
 
+  if (!MF.getFunction().getSubprogram())
+    // VarLocBaseLDV will already have removed all DBG_VALUEs.
+    return false;
+
+  // Skip functions from NoDebug compilation units.
+  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
+      DICompileUnit::NoDebug)
+    return false;
+
+  TRI = MF.getSubtarget().getRegisterInfo();
+  TII = MF.getSubtarget().getInstrInfo();
+  TFI = MF.getSubtarget().getFrameLowering();
+  TFI->getCalleeSaves(MF, CalleeSavedRegs);
+  this->TPC = TPC;
+  LS.initialize(MF);
+
   bool Changed = false;
   bool OLChanged = false;
   bool MBBJoined = false;
 
   VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors.
   OverlapMap OverlapFragments; // Map of overlapping variable fragments.
   OpenRangesSet OpenRanges(Alloc, OverlapFragments);
                               // Ranges that are open until end of bb.
bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) {
 
   if (RPONumber > InputBBLimit) {
     unsigned NumInputDbgValues = 0;
     for (auto &MBB : MF)
       for (auto &MI : MBB)
         if (MI.isDebugValue())
           ++NumInputDbgValues;
     if (NumInputDbgValues > InputDbgValueLimit) {
-      LLVM_DEBUG(dbgs() << "Disabling LiveDebugValues: " << MF.getName()
+      LLVM_DEBUG(dbgs() << "Disabling VarLocBasedLDV: " << MF.getName()
                         << " has " << RPONumber << " basic blocks and "
                         << NumInputDbgValues
                         << " input DBG_VALUEs, exceeding limits.\n");
       return false;
     }
   }
 
   // This is a standard "union of predecessor outs" dataflow problem.
bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) {
   // that now.
   flushPendingLocs(InLocs, VarLocIDs);
 
   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
   LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
   return Changed;
 }
 
-bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
-  if (!MF.getFunction().getSubprogram())
-    // LiveDebugValues will already have removed all DBG_VALUEs.
-    return false;
-
-  // Skip functions from NoDebug compilation units.
-  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
-      DICompileUnit::NoDebug)
-    return false;
-
-  TRI = MF.getSubtarget().getRegisterInfo();
-  TII = MF.getSubtarget().getInstrInfo();
-  TFI = MF.getSubtarget().getFrameLowering();
-  TFI->getCalleeSaves(MF, CalleeSavedRegs);
-  LS.initialize(MF);
-
-  bool Changed = ExtendRanges(MF);
-  return Changed;
+LDVImpl *
+llvm::makeVarLocBasedLiveDebugValues()
+{
+  return new VarLocBasedLDV();
 }