Reapply 7d77bbef4ad92, adding new debug-info classes

This reverts commit 957efa4ce4f0391147cec62746e997226ee2b836.

Original commit message below -- in this follow up, I've shifted
un-necessary inclusions of DebugProgramInstruction.h into being forward
declarations (fixes clang-compile time I hope), and a memory leak in the
DebugInfoTest.cpp IR unittests.

I also tracked a compile-time regression in D154080, more explanation
there, but the result of which is hiding some of the changes behind the
EXPERIMENTAL_DEBUGINFO_ITERATORS compile-time flag. This is tested by the
"new-debug-iterators" buildbot.

[DebugInfo][RemoveDIs] Add prototype storage classes for "new" debug-info

This patch adds a variety of classes needed to record variable location
debug-info without using the existing intrinsic approach, see the rationale
at [0].

The two added files and corresponding unit tests are the majority of the
plumbing required for this, but at this point isn't accessible from the
rest of LLVM as we need to stage it into the repo gently. An overview is
that classes are added for recording variable information attached to Real
(TM) instructions, in the form of DPValues and DPMarker objects. The
metadata-uses of DPValues is plumbed into the metadata hierachy, and a
field added to class Instruction, which are all stimulated in the unit
tests. The next few patches in this series add utilities to convert to/from
this new debug-info format and add instruction/block utilities to have
debug-info automatically updated in the background when various operations
occur.

This patch was reviewed in Phab in D153990 and D154080, I've squashed them
together into this commit as there are dependencies between the two
patches, and there's little profit in landing them separately.

[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939

10 files changed, 696 insertions, 4 deletions

diff --git a/llvm/lib/IR/BasicBlock.cpp b/llvm/lib/IR/BasicBlock.cpp
index 46b1a3b..d238b65 100644
--- a/llvm/lib/IR/BasicBlock.cpp
+++ b/llvm/lib/IR/BasicBlock.cpp
@@ -16,16 +16,176 @@
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugProgramInstruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Type.h"
+#include "llvm/Support/CommandLine.h"
+
+#include "LLVMContextImpl.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "ir"
 STATISTIC(NumInstrRenumberings, "Number of renumberings across all blocks");
 
+cl::opt<bool>
+    UseNewDbgInfoFormat("experimental-debuginfo-iterators",
+                        cl::desc("Enable communicating debuginfo positions "
+                                 "through iterators, eliminating intrinsics"),
+                        cl::init(false));
+
+DPMarker *BasicBlock::createMarker(Instruction *I) {
+  assert(IsNewDbgInfoFormat &&
+         "Tried to create a marker in a non new debug-info block!");
+  assert(I->DbgMarker == nullptr &&
+         "Tried to create marker for instuction that already has one!");
+  DPMarker *Marker = new DPMarker();
+  Marker->MarkedInstr = I;
+  I->DbgMarker = Marker;
+  return Marker;
+}
+
+DPMarker *BasicBlock::createMarker(InstListType::iterator It) {
+  assert(IsNewDbgInfoFormat &&
+         "Tried to create a marker in a non new debug-info block!");
+  if (It != end())
+    return createMarker(&*It);
+  DPMarker *DPM = getTrailingDPValues();
+  if (DPM)
+    return DPM;
+  DPM = new DPMarker();
+  setTrailingDPValues(DPM);
+  return DPM;
+}
+
+void BasicBlock::convertToNewDbgValues() {
+  // Is the command line option set?
+  if (!UseNewDbgInfoFormat)
+    return;
+
+  IsNewDbgInfoFormat = true;
+
+  // Iterate over all instructions in the instruction list, collecting dbg.value
+  // instructions and converting them to DPValues. Once we find a "real"
+  // instruction, attach all those DPValues to a DPMarker in that instruction.
+  SmallVector<DPValue *, 4> DPVals;
+  for (Instruction &I : make_early_inc_range(InstList)) {
+    assert(!I.DbgMarker && "DbgMarker already set on old-format instrs?");
+    if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
+      // Convert this dbg.value to a DPValue.
+      DPValue *Value = new DPValue(DVI);
+      DPVals.push_back(Value);
+      DVI->eraseFromParent();
+      continue;
+    }
+
+    // Create a marker to store DPValues in. Technically we don't need to store
+    // one marker per instruction, but that's a future optimisation.
+    createMarker(&I);
+    DPMarker *Marker = I.DbgMarker;
+
+    for (DPValue *DPV : DPVals)
+      Marker->insertDPValue(DPV, false);
+
+    DPVals.clear();
+  }
+}
+
+void BasicBlock::convertFromNewDbgValues() {
+  invalidateOrders();
+  IsNewDbgInfoFormat = false;
+
+  // Iterate over the block, finding instructions annotated with DPMarkers.
+  // Convert any attached DPValues to dbg.values and insert ahead of the
+  // instruction.
+  for (auto &Inst : *this) {
+    if (!Inst.DbgMarker)
+      continue;
+
+    DPMarker &Marker = *Inst.DbgMarker;
+    for (DPValue &DPV : Marker.getDbgValueRange())
+      InstList.insert(Inst.getIterator(),
+                      DPV.createDebugIntrinsic(getModule(), nullptr));
+
+    Marker.eraseFromParent();
+  };
+
+  // Assume no trailing DPValues: we could technically create them at the end
+  // of the block, after a terminator, but this would be non-cannonical and
+  // indicates that something else is broken somewhere.
+  assert(!getTrailingDPValues());
+}
+
+bool BasicBlock::validateDbgValues(bool Assert, bool Msg, raw_ostream *OS) {
+  bool RetVal = false;
+  if (!OS)
+    OS = &errs();
+
+  // Helper lambda for reporting failures: via assertion, printing, and return
+  // value.
+  auto TestFailure = [Assert, Msg, &RetVal, OS](bool Val, const char *Text) {
+    // Did the test fail?
+    if (Val)
+      return;
+
+    // If we're asserting, then fire off an assertion.
+    if (Assert)
+      llvm_unreachable(Text);
+
+    if (Msg)
+      *OS << Text << "\n";
+    RetVal = true;
+  };
+
+  // We should have the same debug-format as the parent function.
+  TestFailure(getParent()->IsNewDbgInfoFormat == IsNewDbgInfoFormat,
+              "Parent function doesn't have the same debug-info format");
+
+  // Only validate if we are using the new format.
+  if (!IsNewDbgInfoFormat)
+    return RetVal;
+
+  // Match every DPMarker to every Instruction and vice versa, and
+  // verify that there are no invalid DPValues.
+  for (auto It = begin(); It != end(); ++It) {
+    if (!It->DbgMarker)
+      continue;
+
+    // Validate DebugProgramMarkers.
+    DPMarker *CurrentDebugMarker = It->DbgMarker;
+
+    // If this is a marker, it should match the instruction and vice versa.
+    TestFailure(CurrentDebugMarker->MarkedInstr == &*It,
+                "Debug Marker points to incorrect instruction?");
+
+    // Now validate any DPValues in the marker.
+    for (DPValue &DPV : CurrentDebugMarker->getDbgValueRange()) {
+      // Validate DebugProgramValues.
+      TestFailure(DPV.getMarker() == CurrentDebugMarker,
+                  "Not pointing at correct next marker!");
+
+      // Verify that no DbgValues appear prior to PHIs.
+      TestFailure(
+          !isa<PHINode>(It),
+          "DebugProgramValues must not appear before PHI nodes in a block!");
+    }
+  }
+
+  // Except transiently when removing + re-inserting the block terminator, there
+  // should be no trailing DPValues.
+  TestFailure(!getTrailingDPValues(), "Trailing DPValues in block");
+  return RetVal;
+}
+
+void BasicBlock::setIsNewDbgInfoFormat(bool NewFlag) {
+  if (NewFlag && !IsNewDbgInfoFormat)
+    convertToNewDbgValues();
+  else if (!NewFlag && IsNewDbgInfoFormat)
+    convertFromNewDbgValues();
+}
+
 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
   if (Function *F = getParent())
     return F->getValueSymbolTable();
@@ -47,7 +207,8 @@ template class llvm::SymbolTableListTraits<Instruction,
 
 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
                        BasicBlock *InsertBefore)
-  : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
+    : Value(Type::getLabelTy(C), Value::BasicBlockVal),
+      IsNewDbgInfoFormat(false), Parent(nullptr) {
 
   if (NewParent)
     insertInto(NewParent, InsertBefore);
@@ -56,12 +217,16 @@ BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
            "Cannot insert block before another block with no function!");
 
   setName(Name);
+  if (NewParent)
+    setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
 }
 
 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
   assert(NewParent && "Expected a parent");
   assert(!Parent && "Already has a parent");
 
+  setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
+
   if (InsertBefore)
     NewParent->insert(InsertBefore->getIterator(), this);
   else
@@ -91,6 +256,11 @@ BasicBlock::~BasicBlock() {
 
   assert(getParent() == nullptr && "BasicBlock still linked into the program!");
   dropAllReferences();
+  for (auto &Inst : *this) {
+    if (!Inst.DbgMarker)
+      continue;
+    Inst.DbgMarker->eraseFromParent();
+  }
   InstList.clear();
 }
 
@@ -588,3 +758,16 @@ void BasicBlock::validateInstrOrdering() const {
   }
 }
 #endif
+
+void BasicBlock::setTrailingDPValues(DPMarker *foo) {
+  getContext().pImpl->setTrailingDPValues(this, foo);
+}
+
+DPMarker *BasicBlock::getTrailingDPValues() {
+  return getContext().pImpl->getTrailingDPValues(this);
+}
+
+void BasicBlock::deleteTrailingDPValues() {
+  getContext().pImpl->deleteTrailingDPValues(this);
+}
+
diff --git a/llvm/lib/IR/CMakeLists.txt b/llvm/lib/IR/CMakeLists.txt
index d9656a2..5fe3d80 100644
--- a/llvm/lib/IR/CMakeLists.txt
+++ b/llvm/lib/IR/CMakeLists.txt
@@ -17,6 +17,7 @@ add_llvm_component_library(LLVMCore
   DataLayout.cpp
   DebugInfo.cpp
   DebugInfoMetadata.cpp
+  DebugProgramInstruction.cpp
   DebugLoc.cpp
   DiagnosticHandler.cpp
   DiagnosticInfo.cpp
diff --git a/llvm/lib/IR/DebugInfoMetadata.cpp b/llvm/lib/IR/DebugInfoMetadata.cpp
index f7f3612..48c4b62 100644
--- a/llvm/lib/IR/DebugInfoMetadata.cpp
+++ b/llvm/lib/IR/DebugInfoMetadata.cpp
@@ -2135,8 +2135,26 @@ void DIArgList::handleChangedOperand(void *Ref, Metadata *New) {
     }
   }
   if (Uniq) {
+    // In the RemoveDIs project (eliminating debug-info-intrinsics), DIArgLists
+    // can be referred to by DebugValueUser objects, which necessitates them
+    // being unique and replaceable metadata. This causes a slight
+    // performance regression that's to be avoided during the early stages of
+    // the RemoveDIs prototype, see D154080.
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+    MDNode *UniqueArgList = uniquify();
+    if (UniqueArgList != this) {
+      replaceAllUsesWith(UniqueArgList);
+      // Clear this here so we don't try to untrack in the destructor.
+      Args.clear();
+      delete this;
+      return;
+    }
+#else
+    // Otherwise, don't fully unique, become distinct instead. See D108968,
+    // there's a latent bug that presents here as nondeterminism otherwise.
     if (uniquify() != this)
       storeDistinctInContext();
+#endif
   }
   track();
 }
diff --git a/llvm/lib/IR/DebugProgramInstruction.cpp b/llvm/lib/IR/DebugProgramInstruction.cpp
new file mode 100644
index 0000000..3f39bae
--- /dev/null
+++ b/llvm/lib/IR/DebugProgramInstruction.cpp
@@ -0,0 +1,353 @@
+//======-- DebugProgramInstruction.cpp - Implement DPValues/DPMarkers --======//
+//
+// 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/IR/DebugProgramInstruction.h"
+#include "llvm/IR/DIBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+
+namespace llvm {
+
+DPValue::DPValue(const DbgVariableIntrinsic *DVI)
+    : DebugValueUser(DVI->getRawLocation()), Variable(DVI->getVariable()),
+      Expression(DVI->getExpression()), DbgLoc(DVI->getDebugLoc()) {
+  switch (DVI->getIntrinsicID()) {
+  case Intrinsic::dbg_value:
+    Type = LocationType::Value;
+    break;
+  case Intrinsic::dbg_declare:
+    Type = LocationType::Declare;
+    break;
+  default:
+    llvm_unreachable(
+        "Trying to create a DPValue with an invalid intrinsic type!");
+  }
+}
+
+DPValue::DPValue(const DPValue &DPV)
+    : DebugValueUser(DPV.getRawLocation()),
+      Variable(DPV.getVariable()), Expression(DPV.getExpression()),
+      DbgLoc(DPV.getDebugLoc()), Type(DPV.getType()) {}
+
+DPValue::DPValue(Metadata *Location, DILocalVariable *DV, DIExpression *Expr,
+                 const DILocation *DI)
+    : DebugValueUser(Location), Variable(DV), Expression(Expr), DbgLoc(DI),
+      Type(LocationType::Value) {
+}
+
+void DPValue::deleteInstr() { delete this; }
+
+iterator_range<DPValue::location_op_iterator> DPValue::location_ops() const {
+  auto *MD = getRawLocation();
+  // If a Value has been deleted, the "location" for this DPValue will be
+  // replaced by nullptr. Return an empty range.
+  if (!MD)
+    return {location_op_iterator(static_cast<ValueAsMetadata *>(nullptr)),
+            location_op_iterator(static_cast<ValueAsMetadata *>(nullptr))};
+
+  // If operand is ValueAsMetadata, return a range over just that operand.
+  if (auto *VAM = dyn_cast<ValueAsMetadata>(MD))
+    return {location_op_iterator(VAM), location_op_iterator(VAM + 1)};
+
+  // If operand is DIArgList, return a range over its args.
+  if (auto *AL = dyn_cast<DIArgList>(MD))
+    return {location_op_iterator(AL->args_begin()),
+            location_op_iterator(AL->args_end())};
+
+  // Operand is an empty metadata tuple, so return empty iterator.
+  assert(cast<MDNode>(MD)->getNumOperands() == 0);
+  return {location_op_iterator(static_cast<ValueAsMetadata *>(nullptr)),
+          location_op_iterator(static_cast<ValueAsMetadata *>(nullptr))};
+}
+
+Value *DPValue::getVariableLocationOp(unsigned OpIdx) const {
+  auto *MD = getRawLocation();
+  if (!MD)
+    return nullptr;
+
+  if (auto *AL = dyn_cast<DIArgList>(MD))
+    return AL->getArgs()[OpIdx]->getValue();
+  if (isa<MDNode>(MD))
+    return nullptr;
+  assert(isa<ValueAsMetadata>(MD) &&
+         "Attempted to get location operand from DPValue with none.");
+  auto *V = cast<ValueAsMetadata>(MD);
+  assert(OpIdx == 0 && "Operand Index must be 0 for a debug intrinsic with a "
+                       "single location operand.");
+  return V->getValue();
+}
+
+static ValueAsMetadata *getAsMetadata(Value *V) {
+  return isa<MetadataAsValue>(V) ? dyn_cast<ValueAsMetadata>(
+                                       cast<MetadataAsValue>(V)->getMetadata())
+                                 : ValueAsMetadata::get(V);
+}
+
+void DPValue::replaceVariableLocationOp(Value *OldValue, Value *NewValue,
+                                        bool AllowEmpty) {
+  assert(NewValue && "Values must be non-null");
+  auto Locations = location_ops();
+  auto OldIt = find(Locations, OldValue);
+  if (OldIt == Locations.end()) {
+    if (AllowEmpty)
+      return;
+    llvm_unreachable("OldValue must be a current location");
+  }
+
+  if (!hasArgList()) {
+    // Set our location to be the MAV wrapping the new Value.
+    setRawLocation(isa<MetadataAsValue>(NewValue)
+                       ? cast<MetadataAsValue>(NewValue)->getMetadata()
+                       : ValueAsMetadata::get(NewValue));
+    return;
+  }
+
+  // We must be referring to a DIArgList, produce a new operands vector with the
+  // old value replaced, generate a new DIArgList and set it as our location.
+  SmallVector<ValueAsMetadata *, 4> MDs;
+  ValueAsMetadata *NewOperand = getAsMetadata(NewValue);
+  for (auto *VMD : Locations)
+    MDs.push_back(VMD == *OldIt ? NewOperand : getAsMetadata(VMD));
+  setRawLocation(DIArgList::get(getVariableLocationOp(0)->getContext(), MDs));
+}
+
+void DPValue::replaceVariableLocationOp(unsigned OpIdx, Value *NewValue) {
+  assert(OpIdx < getNumVariableLocationOps() && "Invalid Operand Index");
+
+  if (!hasArgList()) {
+    setRawLocation(isa<MetadataAsValue>(NewValue)
+                       ? cast<MetadataAsValue>(NewValue)->getMetadata()
+                       : ValueAsMetadata::get(NewValue));
+    return;
+  }
+
+  SmallVector<ValueAsMetadata *, 4> MDs;
+  ValueAsMetadata *NewOperand = getAsMetadata(NewValue);
+  for (unsigned Idx = 0; Idx < getNumVariableLocationOps(); ++Idx)
+    MDs.push_back(Idx == OpIdx ? NewOperand
+                               : getAsMetadata(getVariableLocationOp(Idx)));
+
+  setRawLocation(DIArgList::get(getVariableLocationOp(0)->getContext(), MDs));
+}
+
+void DPValue::addVariableLocationOps(ArrayRef<Value *> NewValues,
+                                     DIExpression *NewExpr) {
+  assert(NewExpr->hasAllLocationOps(getNumVariableLocationOps() +
+                                    NewValues.size()) &&
+         "NewExpr for debug variable intrinsic does not reference every "
+         "location operand.");
+  assert(!is_contained(NewValues, nullptr) && "New values must be non-null");
+  setExpression(NewExpr);
+  SmallVector<ValueAsMetadata *, 4> MDs;
+  for (auto *VMD : location_ops())
+    MDs.push_back(getAsMetadata(VMD));
+  for (auto *VMD : NewValues)
+    MDs.push_back(getAsMetadata(VMD));
+  setRawLocation(DIArgList::get(getVariableLocationOp(0)->getContext(), MDs));
+}
+
+std::optional<uint64_t> DPValue::getFragmentSizeInBits() const {
+  if (auto Fragment = getExpression()->getFragmentInfo())
+    return Fragment->SizeInBits;
+  return getVariable()->getSizeInBits();
+}
+
+DPValue *DPValue::clone() const { return new DPValue(*this); }
+
+DbgVariableIntrinsic *
+DPValue::createDebugIntrinsic(Module *M, Instruction *InsertBefore) const {
+  [[maybe_unused]] DICompileUnit *Unit =
+      getDebugLoc().get()->getScope()->getSubprogram()->getUnit();
+  assert(M && Unit &&
+         "Cannot clone from BasicBlock that is not part of a Module or "
+         "DICompileUnit!");
+  LLVMContext &Context = getDebugLoc()->getContext();
+  Value *Args[] = {MetadataAsValue::get(Context, getRawLocation()),
+                   MetadataAsValue::get(Context, getVariable()),
+                   MetadataAsValue::get(Context, getExpression())};
+  Function *IntrinsicFn;
+
+  // Work out what sort of intrinsic we're going to produce.
+  switch (getType()) {
+  case DPValue::LocationType::Declare:
+    IntrinsicFn = Intrinsic::getDeclaration(M, Intrinsic::dbg_declare);
+    break;
+  case DPValue::LocationType::Value:
+    IntrinsicFn = Intrinsic::getDeclaration(M, Intrinsic::dbg_value);
+    break;
+  }
+
+  // Create the intrinsic from this DPValue's information, optionally insert
+  // into the target location.
+  DbgVariableIntrinsic *DVI = cast<DbgVariableIntrinsic>(
+      CallInst::Create(IntrinsicFn->getFunctionType(), IntrinsicFn, Args));
+  DVI->setTailCall();
+  DVI->setDebugLoc(getDebugLoc());
+  if (InsertBefore)
+    DVI->insertBefore(InsertBefore);
+
+  return DVI;
+}
+
+void DPValue::handleChangedLocation(Metadata *NewLocation) {
+  resetDebugValue(NewLocation);
+}
+
+const BasicBlock *DPValue::getParent() const {
+  return Marker->MarkedInstr->getParent();
+}
+
+BasicBlock *DPValue::getParent() { return Marker->MarkedInstr->getParent(); }
+
+BasicBlock *DPValue::getBlock() { return Marker->getParent(); }
+
+const BasicBlock *DPValue::getBlock() const { return Marker->getParent(); }
+
+Function *DPValue::getFunction() { return getBlock()->getParent(); }
+
+const Function *DPValue::getFunction() const { return getBlock()->getParent(); }
+
+Module *DPValue::getModule() { return getFunction()->getParent(); }
+
+const Module *DPValue::getModule() const { return getFunction()->getParent(); }
+
+LLVMContext &DPValue::getContext() { return getBlock()->getContext(); }
+
+const LLVMContext &DPValue::getContext() const {
+  return getBlock()->getContext();
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+// An empty, global, DPMarker for the purpose of describing empty ranges of
+// DPValues.
+DPMarker DPMarker::EmptyDPMarker;
+
+void DPMarker::dropDPValues() {
+  while (!StoredDPValues.empty()) {
+    auto It = StoredDPValues.begin();
+    DPValue *DPV = &*It;
+    StoredDPValues.erase(It);
+    DPV->deleteInstr();
+  }
+}
+
+void DPMarker::dropOneDPValue(DPValue *DPV) {
+  assert(DPV->getMarker() == this);
+  StoredDPValues.erase(DPV->getIterator());
+  DPV->deleteInstr();
+}
+
+const BasicBlock *DPMarker::getParent() const {
+  return MarkedInstr->getParent();
+}
+
+BasicBlock *DPMarker::getParent() { return MarkedInstr->getParent(); }
+
+void DPMarker::removeMarker() {
+  // Are there any DPValues in this DPMarker? If not, nothing to preserve.
+  Instruction *Owner = MarkedInstr;
+  if (StoredDPValues.empty()) {
+    eraseFromParent();
+    Owner->DbgMarker = nullptr;
+    return;
+  }
+
+  // The attached DPValues need to be preserved; attach them to the next
+  // instruction. If there isn't a next instruction, put them on the
+  // "trailing" list.
+  // (This logic gets refactored in a future patch, needed to break some
+  //  dependencies here).
+  BasicBlock::iterator NextInst = std::next(Owner->getIterator());
+  DPMarker *NextMarker;
+  if (NextInst == Owner->getParent()->end()) {
+    NextMarker = new DPMarker();
+    Owner->getParent()->setTrailingDPValues(NextMarker);
+  } else {
+    NextMarker = NextInst->DbgMarker;
+  }
+  NextMarker->absorbDebugValues(*this, true);
+
+  eraseFromParent();
+}
+
+void DPMarker::removeFromParent() {
+  MarkedInstr->DbgMarker = nullptr;
+  MarkedInstr = nullptr;
+}
+
+void DPMarker::eraseFromParent() {
+  if (MarkedInstr)
+    removeFromParent();
+  dropDPValues();
+  delete this;
+}
+
+iterator_range<DPValue::self_iterator> DPMarker::getDbgValueRange() {
+  return make_range(StoredDPValues.begin(), StoredDPValues.end());
+}
+
+void DPValue::removeFromParent() {
+  getMarker()->StoredDPValues.erase(getIterator());
+}
+
+void DPValue::eraseFromParent() {
+  removeFromParent();
+  deleteInstr();
+}
+
+void DPMarker::insertDPValue(DPValue *New, bool InsertAtHead) {
+  auto It = InsertAtHead ? StoredDPValues.begin() : StoredDPValues.end();
+  StoredDPValues.insert(It, *New);
+  New->setMarker(this);
+}
+
+void DPMarker::absorbDebugValues(DPMarker &Src, bool InsertAtHead) {
+  auto It = InsertAtHead ? StoredDPValues.begin() : StoredDPValues.end();
+  for (DPValue &DPV : Src.StoredDPValues)
+    DPV.setMarker(this);
+
+  StoredDPValues.splice(It, Src.StoredDPValues);
+}
+
+iterator_range<simple_ilist<DPValue>::iterator> DPMarker::cloneDebugInfoFrom(
+    DPMarker *From, std::optional<simple_ilist<DPValue>::iterator> from_here,
+    bool InsertAtHead) {
+  DPValue *First = nullptr;
+  // Work out what range of DPValues to clone: normally all the contents of the
+  // "From" marker, optionally we can start from the from_here position down to
+  // end().
+  auto Range =
+      make_range(From->StoredDPValues.begin(), From->StoredDPValues.end());
+  if (from_here.has_value())
+    Range = make_range(*from_here, From->StoredDPValues.end());
+
+  // Clone each DPValue and insert into StoreDPValues; optionally place them at
+  // the start or the end of the list.
+  auto Pos = (InsertAtHead) ? StoredDPValues.begin() : StoredDPValues.end();
+  for (DPValue &DPV : Range) {
+    DPValue *New = DPV.clone();
+    New->setMarker(this);
+    StoredDPValues.insert(Pos, *New);
+    if (!First)
+      First = New;
+  }
+
+  if (!First)
+    return {StoredDPValues.end(), StoredDPValues.end()};
+
+  if (InsertAtHead)
+    // If InsertAtHead is set, we cloned a range onto the front of of the
+    // StoredDPValues collection, return that range.
+    return {StoredDPValues.begin(), Pos};
+  else
+    // We inserted a block at the end, return that range.
+    return {First->getIterator(), StoredDPValues.end()};
+}
+
+} // end namespace llvm
+
diff --git a/llvm/lib/IR/Function.cpp b/llvm/lib/IR/Function.cpp
index 658aa67..49e0c1c 100644
--- a/llvm/lib/IR/Function.cpp
+++ b/llvm/lib/IR/Function.cpp
@@ -81,6 +81,27 @@ static cl::opt<unsigned> NonGlobalValueMaxNameSize(
     "non-global-value-max-name-size", cl::Hidden, cl::init(1024),
     cl::desc("Maximum size for the name of non-global values."));
 
+void Function::convertToNewDbgValues() {
+  IsNewDbgInfoFormat = true;
+  for (auto &BB : *this) {
+    BB.convertToNewDbgValues();
+  }
+}
+
+void Function::convertFromNewDbgValues() {
+  IsNewDbgInfoFormat = false;
+  for (auto &BB : *this) {
+    BB.convertFromNewDbgValues();
+  }
+}
+
+void Function::setIsNewDbgInfoFormat(bool NewFlag) {
+  if (NewFlag && !IsNewDbgInfoFormat)
+    convertToNewDbgValues();
+  else if (!NewFlag && IsNewDbgInfoFormat)
+    convertFromNewDbgValues();
+}
+
 //===----------------------------------------------------------------------===//
 // Argument Implementation
 //===----------------------------------------------------------------------===//
@@ -402,7 +423,7 @@ Function::Function(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace,
     : GlobalObject(Ty, Value::FunctionVal,
                    OperandTraits<Function>::op_begin(this), 0, Linkage, name,
                    computeAddrSpace(AddrSpace, ParentModule)),
-      NumArgs(Ty->getNumParams()) {
+      NumArgs(Ty->getNumParams()), IsNewDbgInfoFormat(false) {
   assert(FunctionType::isValidReturnType(getReturnType()) &&
          "invalid return type");
   setGlobalObjectSubClassData(0);
diff --git a/llvm/lib/IR/LLVMContextImpl.cpp b/llvm/lib/IR/LLVMContextImpl.cpp
index 2076eee..406850b 100644
--- a/llvm/lib/IR/LLVMContextImpl.cpp
+++ b/llvm/lib/IR/LLVMContextImpl.cpp
@@ -45,6 +45,14 @@ LLVMContextImpl::LLVMContextImpl(LLVMContext &C)
       Int16Ty(C, 16), Int32Ty(C, 32), Int64Ty(C, 64), Int128Ty(C, 128) {}
 
 LLVMContextImpl::~LLVMContextImpl() {
+#ifndef NDEBUG
+  // Check that any variable location records that fell off the end of a block
+  // when it's terminator was removed were eventually replaced. This assertion
+  // firing indicates that DPValues went missing during the lifetime of the
+  // LLVMContext.
+  assert(TrailingDPValues.empty() && "DPValue records in blocks not cleaned");
+#endif
+
   // NOTE: We need to delete the contents of OwnedModules, but Module's dtor
   // will call LLVMContextImpl::removeModule, thus invalidating iterators into
   // the container. Avoid iterators during this operation:
diff --git a/llvm/lib/IR/LLVMContextImpl.h b/llvm/lib/IR/LLVMContextImpl.h
index 4cc3f8d..ebc444f 100644
--- a/llvm/lib/IR/LLVMContextImpl.h
+++ b/llvm/lib/IR/LLVMContextImpl.h
@@ -57,6 +57,7 @@ class AttributeListImpl;
 class AttributeSetNode;
 class BasicBlock;
 struct DiagnosticHandler;
+class DPMarker;
 class ElementCount;
 class Function;
 class GlobalObject;
@@ -1633,6 +1634,36 @@ public:
   /// The lifetime of the object must be guaranteed to extend as long as the
   /// LLVMContext is used by compilation.
   void setOptPassGate(OptPassGate &);
+
+  /// Mapping of blocks to collections of "trailing" DPValues. As part of the
+  /// "RemoveDIs" project, debug-info variable location records are going to
+  /// cease being instructions... which raises the problem of where should they
+  /// be recorded when we remove the terminator of a blocks, such as:
+  ///
+  ///    %foo = add i32 0, 0
+  ///    br label %bar
+  ///
+  /// If the branch is removed, a legitimate transient state while editing a
+  /// block, any debug-records between those two instructions will not have a
+  /// location. Each block thus records any DPValue records that "trail" in
+  /// such a way. These are stored in LLVMContext because typically LLVM only
+  /// edits a small number of blocks at a time, so there's no need to bloat
+  /// BasicBlock with such a data structure.
+  SmallDenseMap<BasicBlock *, DPMarker *> TrailingDPValues;
+
+  // Set, get and delete operations for TrailingDPValues.
+  void setTrailingDPValues(BasicBlock *B, DPMarker *M) {
+    assert(!TrailingDPValues.count(B));
+    TrailingDPValues[B] = M;
+  }
+
+  DPMarker *getTrailingDPValues(BasicBlock *B) {
+    return TrailingDPValues.lookup(B);
+  }
+
+  void deleteTrailingDPValues(BasicBlock *B) {
+    TrailingDPValues.erase(B);
+  }
 };
 
 } // end namespace llvm
diff --git a/llvm/lib/IR/Metadata.cpp b/llvm/lib/IR/Metadata.cpp
index 7860280..61504e0 100644
--- a/llvm/lib/IR/Metadata.cpp
+++ b/llvm/lib/IR/Metadata.cpp
@@ -32,6 +32,7 @@
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DebugProgramInstruction.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/IR/GlobalVariable.h"
@@ -147,6 +148,32 @@ void MetadataAsValue::untrack() {
     MetadataTracking::untrack(MD);
 }
 
+DPValue *DebugValueUser::getUser() { return static_cast<DPValue *>(this); }
+const DPValue *DebugValueUser::getUser() const {
+  return static_cast<const DPValue *>(this);
+}
+void DebugValueUser::handleChangedValue(Metadata *NewMD) {
+  getUser()->handleChangedLocation(NewMD);
+}
+
+void DebugValueUser::trackDebugValue() {
+  if (DebugValue)
+    MetadataTracking::track(&DebugValue, *DebugValue, *this);
+}
+
+void DebugValueUser::untrackDebugValue() {
+  if (DebugValue)
+    MetadataTracking::untrack(DebugValue);
+}
+
+void DebugValueUser::retrackDebugValue(DebugValueUser &X) {
+  assert(DebugValue == X.DebugValue && "Expected values to match");
+  if (X.DebugValue) {
+    MetadataTracking::retrack(X.DebugValue, DebugValue);
+    X.DebugValue = nullptr;
+  }
+}
+
 bool MetadataTracking::track(void *Ref, Metadata &MD, OwnerTy Owner) {
   assert(Ref && "Expected live reference");
   assert((Owner || *static_cast<Metadata **>(Ref) == &MD) &&
@@ -195,6 +222,8 @@ SmallVector<Metadata *> ReplaceableMetadataImpl::getAllArgListUsers() {
   SmallVector<std::pair<OwnerTy, uint64_t> *> MDUsersWithID;
   for (auto Pair : UseMap) {
     OwnerTy Owner = Pair.second.first;
+    if (Owner.isNull())
+      continue;
     if (!isa<Metadata *>(Owner))
       continue;
     Metadata *OwnerMD = cast<Metadata *>(Owner);
@@ -210,6 +239,25 @@ SmallVector<Metadata *> ReplaceableMetadataImpl::getAllArgListUsers() {
   return MDUsers;
 }
 
+SmallVector<DPValue *> ReplaceableMetadataImpl::getAllDPValueUsers() {
+  SmallVector<std::pair<OwnerTy, uint64_t> *> DPVUsersWithID;
+  for (auto Pair : UseMap) {
+    OwnerTy Owner = Pair.second.first;
+    if (Owner.isNull())
+      continue;
+    if (!Owner.is<DebugValueUser *>())
+      continue;
+    DPVUsersWithID.push_back(&UseMap[Pair.first]);
+  }
+  llvm::sort(DPVUsersWithID, [](auto UserA, auto UserB) {
+    return UserA->second < UserB->second;
+  });
+  SmallVector<DPValue *> DPVUsers;
+  for (auto UserWithID : DPVUsersWithID)
+    DPVUsers.push_back(UserWithID->first.get<DebugValueUser *>()->getUser());
+  return DPVUsers;
+}
+
 void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) {
   bool WasInserted =
       UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex)))
@@ -308,6 +356,11 @@ void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) {
       continue;
     }
 
+    if (Owner.is<DebugValueUser *>()) {
+      Owner.get<DebugValueUser *>()->getUser()->handleChangedLocation(MD);
+      continue;
+    }
+
     // There's a Metadata owner -- dispatch.
     Metadata *OwnerMD = cast<Metadata *>(Owner);
     switch (OwnerMD->getMetadataID()) {
@@ -343,7 +396,7 @@ void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
     auto Owner = Pair.second.first;
     if (!Owner)
       continue;
-    if (isa<MetadataAsValue *>(Owner))
+    if (!Owner.is<Metadata *>())
       continue;
 
     // Resolve MDNodes that point at this.
@@ -356,19 +409,34 @@ void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
   }
 }
 
+// Special handing of DIArgList is required in the RemoveDIs project, see
+// commentry in DIArgList::handleChangedOperand for details. Hidden behind
+// conditional compilation to avoid a compile time regression.
 ReplaceableMetadataImpl *ReplaceableMetadataImpl::getOrCreate(Metadata &MD) {
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+  if (auto *ArgList = dyn_cast<DIArgList>(&MD))
+    return ArgList->Context.getOrCreateReplaceableUses();
+#endif
   if (auto *N = dyn_cast<MDNode>(&MD))
     return N->isResolved() ? nullptr : N->Context.getOrCreateReplaceableUses();
   return dyn_cast<ValueAsMetadata>(&MD);
 }
 
 ReplaceableMetadataImpl *ReplaceableMetadataImpl::getIfExists(Metadata &MD) {
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+  if (auto *ArgList = dyn_cast<DIArgList>(&MD))
+    return ArgList->Context.getReplaceableUses();
+#endif
   if (auto *N = dyn_cast<MDNode>(&MD))
     return N->isResolved() ? nullptr : N->Context.getReplaceableUses();
   return dyn_cast<ValueAsMetadata>(&MD);
 }
 
 bool ReplaceableMetadataImpl::isReplaceable(const Metadata &MD) {
+#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
+  if (isa<DIArgList>(&MD))
+    return true;
+#endif
   if (auto *N = dyn_cast<MDNode>(&MD))
     return !N->isResolved();
   return isa<ValueAsMetadata>(&MD);
diff --git a/llvm/lib/IR/Module.cpp b/llvm/lib/IR/Module.cpp
index dba660b..17efe79 100644
--- a/llvm/lib/IR/Module.cpp
+++ b/llvm/lib/IR/Module.cpp
@@ -71,7 +71,8 @@ template class llvm::SymbolTableListTraits<GlobalIFunc>;
 
 Module::Module(StringRef MID, LLVMContext &C)
     : Context(C), ValSymTab(std::make_unique<ValueSymbolTable>(-1)),
-      ModuleID(std::string(MID)), SourceFileName(std::string(MID)), DL("") {
+      ModuleID(std::string(MID)), SourceFileName(std::string(MID)), DL(""),
+      IsNewDbgInfoFormat(false) {
   Context.addModule(this);
 }
 
diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp
index 1fa6bc1..b1d1075 100644
--- a/llvm/lib/IR/Verifier.cpp
+++ b/llvm/lib/IR/Verifier.cpp
@@ -2945,6 +2945,14 @@ void Verifier::visitBasicBlock(BasicBlock &BB) {
   {
     Check(I.getParent() == &BB, "Instruction has bogus parent pointer!");
   }
+
+  // Confirm that no issues arise from the debug program.
+  if (BB.IsNewDbgInfoFormat) {
+    // Configure the validate function to not fire assertions, instead print
+    // errors and return true if there's a problem.
+    bool RetVal = BB.validateDbgValues(false, true, OS);
+    Check(!RetVal, "Invalid configuration of new-debug-info data found");
+  }
 }
 
 void Verifier::visitTerminator(Instruction &I) {