[Local] replaceAllDbgUsesWith: Update debug values before RAUW

The replaceAllDbgUsesWith utility helps passes preserve debug info when
replacing one value with another.

This improves upon the existing insertReplacementDbgValues API by:

- Updating debug intrinsics in-place, while preventing use-before-def of
  the replacement value.
- Falling back to salvageDebugInfo when a replacement can't be made.
- Moving the responsibiliy for rewriting llvm.dbg.* DIExpressions into
  common utility code.

Along with the API change, this teaches replaceAllDbgUsesWith how to
create DIExpressions for three basic integer and pointer conversions:

- The no-op conversion. Applies when the values have the same width, or
  have bit-for-bit compatible pointer representations.
- Truncation. Applies when the new value is wider than the old one.
- Zero/sign extension. Applies when the new value is narrower than the
  old one.

Testing:

- check-llvm, check-clang, a stage2 `-g -O3` build of clang,
  regression/unit testing.
- This resolves a number of mis-sized dbg.value diagnostics from
  Debugify.

Differential Revision: https://reviews.llvm.org/D48676

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@336451 91177308-0d34-0410-b5e6-96231b3b80d8

12 files changed, 544 insertions, 69 deletions

diff --git a/include/llvm/IR/DebugInfoMetadata.h b/include/llvm/IR/DebugInfoMetadata.h
index 1e3aebb5ede..df689185ef8 100644
--- a/include/llvm/IR/DebugInfoMetadata.h
+++ b/include/llvm/IR/DebugInfoMetadata.h
@@ -778,6 +778,12 @@ public:
 
   unsigned getEncoding() const { return Encoding; }
 
+  enum class Signedness { Signed, Unsigned };
+
+  /// Return the signedness of this type, or None if this type is neither
+  /// signed nor unsigned.
+  Optional<Signedness> getSignedness() const;
+
   static bool classof(const Metadata *MD) {
     return MD->getMetadataID() == DIBasicTypeKind;
   }
@@ -2206,6 +2212,14 @@ public:
   /// Determines the size of the variable's type.
   Optional<uint64_t> getSizeInBits() const;
 
+  /// Return the signedness of this variable's type, or None if this type is
+  /// neither signed nor unsigned.
+  Optional<DIBasicType::Signedness> getSignedness() const {
+    if (auto *BT = dyn_cast<DIBasicType>(getType().resolve()))
+      return BT->getSignedness();
+    return None;
+  }
+
   StringRef getFilename() const {
     if (auto *F = getFile())
       return F->getFilename();
@@ -2312,6 +2326,11 @@ public:
     ///
     /// Return the number of elements in the operand (1 + args).
     unsigned getSize() const;
+
+    /// Append the elements of this operand to \p V.
+    void appendToVector(SmallVectorImpl<uint64_t> &V) const {
+      V.append(getSize(), *get());
+    }
   };
 
   /// An iterator for expression operands.
@@ -2425,6 +2444,13 @@ public:
                                       SmallVectorImpl<uint64_t> &Ops,
                                       bool StackValue = false);
 
+  /// Convert \p DIExpr into a stack value if it isn't one already by appending
+  /// DW_OP_deref if needed, and applying \p Ops to the resulting expression.
+  /// If \p DIExpr is a fragment, the returned expression will contain the same
+  /// fragment.
+  static DIExpression *appendToStack(const DIExpression *DIExpr,
+                                     ArrayRef<uint64_t> Ops);
+
   /// Create a DIExpression to describe one part of an aggregate variable that
   /// is fragmented across multiple Values. The DW_OP_LLVM_fragment operation
   /// will be appended to the elements of \c Expr. If \c Expr already contains
diff --git a/include/llvm/IR/Type.h b/include/llvm/IR/Type.h
index ae120645dbd..9c1f99d1b3a 100644
--- a/include/llvm/IR/Type.h
+++ b/include/llvm/IR/Type.h
@@ -208,6 +208,9 @@ public:
     return getScalarType()->isIntegerTy(BitWidth);
   }
 
+  /// Return true if this is an integer type or a pointer type.
+  bool isIntOrPtrTy() const { return isIntegerTy() || isPointerTy(); }
+
   /// True if this is an instance of FunctionType.
   bool isFunctionTy() const { return getTypeID() == FunctionTyID; }
 
diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
index 363533f25d3..8e92813869c 100644
--- a/include/llvm/Transforms/Utils/Local.h
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -329,27 +329,27 @@ bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
 void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
                               DIBuilder &Builder, int Offset = 0);
 
-/// Assuming the instruction \p I is going to be deleted, attempt to salvage any
-/// dbg.value intrinsics referring to \p I by rewriting its effect into a
-/// DIExpression.
-void salvageDebugInfo(Instruction &I);
-
-/// Assuming the value \p From is going to be deleted, insert replacement
-/// dbg.value intrinsics for each debug user of \p From. The newly-inserted
-/// dbg.values refer to \p To instead of \p From. Each replacement dbg.value
-/// has the same location and variable as the debug user it replaces, has a
-/// DIExpression determined by the result of \p RewriteExpr applied to an old
-/// debug user of \p From, and is placed before \p InsertBefore. If
-/// \p RewriteExpr returns nullptr, no replacement for the specified debug
-/// user is emitted.
-void insertReplacementDbgValues(
-    Value &From, Value &To, Instruction &InsertBefore,
-    function_ref<DIExpression *(DbgInfoIntrinsic &OldDII)> RewriteExpr);
-
-/// An overload of insertReplacementDbgValues() for the common case where
-/// the replacement dbg.values have the same DIExpressions as the originals.
-void insertReplacementDbgValues(Value &From, Value &To,
-                                Instruction &InsertBefore);
+/// Assuming the instruction \p I is going to be deleted, attempt to salvage
+/// debug users of \p I by writing the effect of \p I in a DIExpression.
+/// Returns true if any debug users were updated.
+bool salvageDebugInfo(Instruction &I);
+
+/// Point debug users of \p From to \p To or salvage them. Use this function
+/// only when replacing all uses of \p From with \p To, with a guarantee that
+/// \p From is going to be deleted.
+///
+/// Follow these rules to prevent use-before-def of \p To:
+///   . If \p To is a linked Instruction, set \p DomPoint to \p To.
+///   . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction
+///     \p To will be inserted after.
+///   . If \p To is not an Instruction (e.g a Constant), the choice of
+///     \p DomPoint is arbitrary. Pick \p From for simplicity.
+///
+/// If a debug user cannot be preserved without reordering variable updates or
+/// introducing a use-before-def, it is either salvaged (\ref salvageDebugInfo)
+/// or deleted. Returns true if any debug users were updated.
+bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint,
+                           DominatorTree &DT);
 
 /// Remove all instructions from a basic block other than it's terminator
 /// and any present EH pad instructions.
diff --git a/lib/CodeGen/AsmPrinter/DwarfExpression.cpp b/lib/CodeGen/AsmPrinter/DwarfExpression.cpp
index 043d02e3ce4..d8d1a5e8f84 100644
--- a/lib/CodeGen/AsmPrinter/DwarfExpression.cpp
+++ b/lib/CodeGen/AsmPrinter/DwarfExpression.cpp
@@ -357,6 +357,9 @@ void DwarfExpression::addExpression(DIExpressionCursor &&ExprCursor,
     case dwarf::DW_OP_shl:
     case dwarf::DW_OP_shr:
     case dwarf::DW_OP_shra:
+    case dwarf::DW_OP_lit0:
+    case dwarf::DW_OP_not:
+    case dwarf::DW_OP_dup:
       emitOp(Op->getOp());
       break;
     case dwarf::DW_OP_deref:
diff --git a/lib/IR/DebugInfoMetadata.cpp b/lib/IR/DebugInfoMetadata.cpp
index 5d9e3405880..0124980485d 100644
--- a/lib/IR/DebugInfoMetadata.cpp
+++ b/lib/IR/DebugInfoMetadata.cpp
@@ -283,6 +283,19 @@ DIBasicType *DIBasicType::getImpl(LLVMContext &Context, unsigned Tag,
                        Ops);
 }
 
+Optional<DIBasicType::Signedness> DIBasicType::getSignedness() const {
+  switch (getEncoding()) {
+  case dwarf::DW_ATE_signed:
+  case dwarf::DW_ATE_signed_char:
+    return Signedness::Signed;
+  case dwarf::DW_ATE_unsigned:
+  case dwarf::DW_ATE_unsigned_char:
+    return Signedness::Unsigned;
+  default:
+    return None;
+  }
+}
+
 DIDerivedType *DIDerivedType::getImpl(
     LLVMContext &Context, unsigned Tag, MDString *Name, Metadata *File,
     unsigned Line, Metadata *Scope, Metadata *BaseType, uint64_t SizeInBits,
@@ -733,6 +746,9 @@ bool DIExpression::isValid() const {
     case dwarf::DW_OP_shra:
     case dwarf::DW_OP_deref:
     case dwarf::DW_OP_xderef:
+    case dwarf::DW_OP_lit0:
+    case dwarf::DW_OP_not:
+    case dwarf::DW_OP_dup:
       break;
     }
   }
@@ -826,6 +842,42 @@ DIExpression *DIExpression::prependOpcodes(const DIExpression *Expr,
   return DIExpression::get(Expr->getContext(), Ops);
 }
 
+DIExpression *DIExpression::appendToStack(const DIExpression *Expr,
+                                          ArrayRef<uint64_t> Ops) {
+  assert(Expr && !Ops.empty() && "Can't append ops to this expression");
+
+  // Append a DW_OP_deref after Expr's current op list if it's non-empty and
+  // has no DW_OP_stack_value.
+  //
+  // Match .* DW_OP_stack_value (DW_OP_LLVM_fragment A B)?.
+  Optional<FragmentInfo> FI = Expr->getFragmentInfo();
+  unsigned DropUntilStackValue = FI.hasValue() ? 3 : 0;
+  bool NeedsDeref =
+      (Expr->getNumElements() > DropUntilStackValue) &&
+      (Expr->getElements().drop_back(DropUntilStackValue).back() !=
+       dwarf::DW_OP_stack_value);
+
+  // Copy Expr's current op list, add a DW_OP_deref if needed, and ensure that
+  // a DW_OP_stack_value is present.
+  SmallVector<uint64_t, 16> NewOps;
+  for (auto Op : Expr->expr_ops()) {
+    if (Op.getOp() == dwarf::DW_OP_stack_value ||
+        Op.getOp() == dwarf::DW_OP_LLVM_fragment)
+      break;
+    Op.appendToVector(NewOps);
+  }
+  if (NeedsDeref)
+    NewOps.push_back(dwarf::DW_OP_deref);
+  NewOps.append(Ops.begin(), Ops.end());
+  NewOps.push_back(dwarf::DW_OP_stack_value);
+
+  // If Expr is a fragment, make the new expression a fragment as well.
+  if (FI)
+    NewOps.append(
+        {dwarf::DW_OP_LLVM_fragment, FI->OffsetInBits, FI->SizeInBits});
+  return DIExpression::get(Expr->getContext(), NewOps);
+}
+
 Optional<DIExpression *> DIExpression::createFragmentExpression(
     const DIExpression *Expr, unsigned OffsetInBits, unsigned SizeInBits) {
   SmallVector<uint64_t, 8> Ops;
diff --git a/lib/Transforms/InstCombine/InstCombineCasts.cpp b/lib/Transforms/InstCombine/InstCombineCasts.cpp
index 842ea8b4b88..481e40612c3 100644
--- a/lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -268,11 +268,9 @@ Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
       // the second cast (CI). CSrc will then have a good chance of being dead.
       auto *Ty = CI.getType();
       auto *Res = CastInst::Create(NewOpc, CSrc->getOperand(0), Ty);
-      // Replace debug users of the eliminable cast by emitting debug values
-      // which refer to the new cast.
-      if (Ty->isIntegerTy() || Ty->isPointerTy())
-        // TODO: Support floats and vectors (see DW_OP_convert, fragment).
-        insertReplacementDbgValues(*CSrc, *Res, *std::next(CI.getIterator()));
+      // Point debug users of the dying cast to the new one.
+      if (CSrc->hasOneUse())
+        replaceAllDbgUsesWith(*CSrc, *Res, CI, DT);
       return Res;
     }
   }
@@ -1079,16 +1077,10 @@ Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
     Value *Res = EvaluateInDifferentType(Src, DestTy, false);
     assert(Res->getType() == DestTy);
 
-    // When DestTy is integer, try to preserve any debug values referring
-    // to the zext being replaced.
-    // TODO: This should work for vectors as well, possibly via the use
-    // of DWARF fragments.
-    if (DestTy->isIntegerTy()) {
-      insertReplacementDbgValues(
-          *Src, *Res, CI, [](DbgInfoIntrinsic &OldDII) -> DIExpression * {
-            return OldDII.getExpression();
-          });
-    }
+    // Preserve debug values referring to Src if the zext is its last use.
+    if (auto *SrcOp = dyn_cast<Instruction>(Src))
+      if (SrcOp->hasOneUse())
+        replaceAllDbgUsesWith(*SrcOp, *Res, CI, DT);
 
     uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear;
     uint32_t DestBitSize = DestTy->getScalarSizeInBits();
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index 722f645d1a5..4081e0465da 100644
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -1590,18 +1590,21 @@ void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
       }
 }
 
-void llvm::salvageDebugInfo(Instruction &I) {
+/// Wrap \p V in a ValueAsMetadata instance.
+static MetadataAsValue *wrapValueInMetadata(LLVMContext &C, Value *V) {
+  return MetadataAsValue::get(C, ValueAsMetadata::get(V));
+}
+
+bool llvm::salvageDebugInfo(Instruction &I) {
   SmallVector<DbgInfoIntrinsic *, 1> DbgUsers;
   findDbgUsers(DbgUsers, &I);
   if (DbgUsers.empty())
-    return;
+    return false;
 
   auto &M = *I.getModule();
   auto &DL = M.getDataLayout();
-
-  auto wrapMD = [&](Value *V) {
-    return MetadataAsValue::get(I.getContext(), ValueAsMetadata::get(V));
-  };
+  auto &Ctx = I.getContext();
+  auto wrapMD = [&](Value *V) { return wrapValueInMetadata(Ctx, V); };
 
   auto doSalvage = [&](DbgInfoIntrinsic *DII, SmallVectorImpl<uint64_t> &Ops) {
     auto *DIExpr = DII->getExpression();
@@ -1613,7 +1616,7 @@ void llvm::salvageDebugInfo(Instruction &I) {
       DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue);
     }
     DII->setOperand(0, wrapMD(I.getOperand(0)));
-    DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr));
+    DII->setOperand(2, MetadataAsValue::get(Ctx, DIExpr));
     LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
   };
 
@@ -1631,7 +1634,7 @@ void llvm::salvageDebugInfo(Instruction &I) {
 
   if (auto *CI = dyn_cast<CastInst>(&I)) {
     if (!CI->isNoopCast(DL))
-      return;
+      return false;
 
     // No-op casts are irrelevant for debug info.
     MetadataAsValue *CastSrc = wrapMD(I.getOperand(0));
@@ -1639,6 +1642,7 @@ void llvm::salvageDebugInfo(Instruction &I) {
       DII->setOperand(0, CastSrc);
       LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
     }
+    return true;
   } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
     unsigned BitWidth =
         M.getDataLayout().getIndexSizeInBits(GEP->getPointerAddressSpace());
@@ -1649,11 +1653,12 @@ void llvm::salvageDebugInfo(Instruction &I) {
     if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset))
       for (auto *DII : DbgUsers)
         applyOffset(DII, Offset.getSExtValue());
+    return true;
   } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) {
     // Rewrite binary operations with constant integer operands.
     auto *ConstInt = dyn_cast<ConstantInt>(I.getOperand(1));
     if (!ConstInt || ConstInt->getBitWidth() > 64)
-      return;
+      return false;
 
     uint64_t Val = ConstInt->getSExtValue();
     for (auto *DII : DbgUsers) {
@@ -1693,9 +1698,10 @@ void llvm::salvageDebugInfo(Instruction &I) {
         break;
       default:
         // TODO: Salvage constants from each kind of binop we know about.
-        continue;
+        return false;
       }
     }
+    return true;
   } else if (isa<LoadInst>(&I)) {
     MetadataAsValue *AddrMD = wrapMD(I.getOperand(0));
     for (auto *DII : DbgUsers) {
@@ -1703,39 +1709,174 @@ void llvm::salvageDebugInfo(Instruction &I) {
       auto *DIExpr = DII->getExpression();
       DIExpr = DIExpression::prepend(DIExpr, DIExpression::WithDeref);
       DII->setOperand(0, AddrMD);
-      DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr));
+      DII->setOperand(2, MetadataAsValue::get(Ctx, DIExpr));
       LLVM_DEBUG(dbgs() << "SALVAGE:  " << *DII << '\n');
     }
+    return true;
   }
+  return false;
 }
 
-void llvm::insertReplacementDbgValues(
-    Value &From, Value &To, Instruction &InsertBefore,
-    function_ref<DIExpression *(DbgInfoIntrinsic &OldDII)> RewriteExpr) {
-  // Collect all debug users of From.
+/// A replacement for a dbg.value expression.
+using DbgValReplacement = Optional<DIExpression *>;
+
+/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
+/// possibly moving/deleting users to prevent use-before-def. Returns true if
+/// changes are made.
+static bool rewriteDebugUsers(
+    Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
+    function_ref<DbgValReplacement(DbgInfoIntrinsic &DII)> RewriteExpr) {
+  // Find debug users of From.
   SmallVector<DbgInfoIntrinsic *, 1> Users;
   findDbgUsers(Users, &From);
   if (Users.empty())
-    return;
+    return false;
+
+  // Prevent use-before-def of To.
+  bool Changed = false;
+  SmallPtrSet<DbgInfoIntrinsic *, 1> DeleteOrSalvage;
+  if (isa<Instruction>(&To)) {
+    bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint;
+
+    for (auto *DII : Users) {
+      // It's common to see a debug user between From and DomPoint. Move it
+      // after DomPoint to preserve the variable update without any reordering.
+      if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) {
+        LLVM_DEBUG(dbgs() << "MOVE:  " << *DII << '\n');
+        DII->moveAfter(&DomPoint);
+        Changed = true;
+
+      // Users which otherwise aren't dominated by the replacement value must
+      // be salvaged or deleted.
+      } else if (!DT.dominates(&DomPoint, DII)) {
+        DeleteOrSalvage.insert(DII);
+      }
+    }
+  }
+
+  // Update debug users without use-before-def risk.
+  for (auto *DII : Users) {
+    if (DeleteOrSalvage.count(DII))
+      continue;
+
+    LLVMContext &Ctx = DII->getContext();
+    DbgValReplacement DVR = RewriteExpr(*DII);
+    if (!DVR)
+      continue;
+
+    DII->setOperand(0, wrapValueInMetadata(Ctx, &To));
+    DII->setOperand(2, MetadataAsValue::get(Ctx, *DVR));
+    LLVM_DEBUG(dbgs() << "REWRITE:  " << *DII << '\n');
+    Changed = true;
+  }
+
+  if (!DeleteOrSalvage.empty()) {
+    // Try to salvage the remaining debug users.
+    Changed |= salvageDebugInfo(From);
 
-  // Insert a replacement debug value for each old debug user. It's assumed
-  // that the old debug users will be erased later.
-  DIBuilder DIB(*InsertBefore.getModule());
-  for (auto *OldDII : Users)
-    if (DIExpression *Expr = RewriteExpr(*OldDII)) {
-      auto *I = DIB.insertDbgValueIntrinsic(&To, OldDII->getVariable(), Expr,
-                                            OldDII->getDebugLoc().get(),
-                                            &InsertBefore);
-      (void)I;
-      LLVM_DEBUG(dbgs() << "REPLACE:  " << *I << '\n');
+    // Delete the debug users which weren't salvaged.
+    for (auto *DII : DeleteOrSalvage) {
+      if (DII->getVariableLocation() == &From) {
+        LLVM_DEBUG(dbgs() << "Erased UseBeforeDef:  " << *DII << '\n');
+        DII->eraseFromParent();
+        Changed = true;
+      }
     }
+  }
+
+  return Changed;
+}
+
+/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
+/// losslessly preserve the bits and semantics of the value. This predicate is
+/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
+///
+/// Note that Type::canLosslesslyBitCastTo is not suitable here because it
+/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
+/// and also does not allow lossless pointer <-> integer conversions.
+static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy,
+                                         Type *ToTy) {
+  // Trivially compatible types.
+  if (FromTy == ToTy)
+    return true;
+
+  // Handle compatible pointer <-> integer conversions.
+  if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
+    bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy);
+    bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) &&
+                              !DL.isNonIntegralPointerType(ToTy);
+    return SameSize && LosslessConversion;
+  }
+
+  // TODO: This is not exhaustive.
+  return false;
 }
 
-void llvm::insertReplacementDbgValues(Value &From, Value &To,
-                                      Instruction &InsertBefore) {
-  return llvm::insertReplacementDbgValues(
-      From, To, InsertBefore,
-      [](DbgInfoIntrinsic &OldDII) { return OldDII.getExpression(); });
+bool llvm::replaceAllDbgUsesWith(Instruction &From, Value &To,
+                                 Instruction &DomPoint, DominatorTree &DT) {
+  // Exit early if From has no debug users.
+  if (!From.isUsedByMetadata())
+    return false;
+
+  assert(&From != &To && "Can't replace something with itself");
+
+  Type *FromTy = From.getType();
+  Type *ToTy = To.getType();
+
+  auto Identity = [&](DbgInfoIntrinsic &DII) -> DbgValReplacement {
+    return DII.getExpression();
+  };
+
+  // Handle no-op conversions.
+  Module &M = *From.getModule();
+  const DataLayout &DL = M.getDataLayout();
+  if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
+    return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
+
+  // Handle integer-to-integer widening and narrowing.
+  // FIXME: Use DW_OP_convert when it's available everywhere.
+  if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
+    uint64_t FromBits = FromTy->getPrimitiveSizeInBits();
+    uint64_t ToBits = ToTy->getPrimitiveSizeInBits();
+    assert(FromBits != ToBits && "Unexpected no-op conversion");
+
+    // When the width of the result grows, assume that a debugger will only
+    // access the low `FromBits` bits when inspecting the source variable.
+    if (FromBits < ToBits)
+      return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
+
+    // The width of the result has shrunk. Use sign/zero extension to describe
+    // the source variable's high bits.
+    auto SignOrZeroExt = [&](DbgInfoIntrinsic &DII) -> DbgValReplacement {
+      DILocalVariable *Var = DII.getVariable();
+
+      // Without knowing signedness, sign/zero extension isn't possible.
+      auto Signedness = Var->getSignedness();
+      if (!Signedness)
+        return None;
+
+      bool Signed = *Signedness == DIBasicType::Signedness::Signed;
+
+      if (!Signed) {
+        // In the unsigned case, assume that a debugger will initialize the
+        // high bits to 0 and do a no-op conversion.
+        return Identity(DII);
+      } else {
+        // In the signed case, the high bits are given by sign extension, i.e:
+        //   (To >> (ToBits - 1)) * ((2 ^ FromBits) - 1)
+        // Calculate the high bits and OR them together with the low bits.
+        SmallVector<uint64_t, 8> Ops({dwarf::DW_OP_dup, dwarf::DW_OP_constu,
+                                      (ToBits - 1), dwarf::DW_OP_shr,
+                                      dwarf::DW_OP_lit0, dwarf::DW_OP_not,
+                                      dwarf::DW_OP_mul, dwarf::DW_OP_or});
+        return DIExpression::appendToStack(DII.getExpression(), Ops);
+      }
+    };
+    return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
+  }
+
+  // TODO: Floating-point conversions, vectors.
+  return false;
 }
 
 unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) {
diff --git a/test/Transforms/InstCombine/alloca-cast-debuginfo.ll b/test/Transforms/InstCombine/alloca-cast-debuginfo.ll
index bbed1ec75cf..b5a1f34ee05 100644
--- a/test/Transforms/InstCombine/alloca-cast-debuginfo.ll
+++ b/test/Transforms/InstCombine/alloca-cast-debuginfo.ll
@@ -41,7 +41,10 @@ entry:
 ; CHECK: %local = alloca i64, align 8
 ; CHECK: call void @llvm.dbg.declare(metadata i64* %local, metadata !22, metadata !DIExpression())
 ; CHECK: [[simplified:%.*]] = bitcast i64* %local to i8*
-; CHECK: call void @llvm.dbg.value(metadata i8* [[simplified]], metadata !22, metadata !DIExpression())
+;
+; Another dbg.value for "local" would be redundant here.
+; CHECK-NOT: call void @llvm.dbg.value(metadata i8* [[simplified]], metadata !22, metadata !DIExpression())
+;
 ; CHECK: call void @escape(i8* [[simplified]])
 ; CHECK: ret void
 
diff --git a/test/Transforms/InstCombine/cast-mul-select.ll b/test/Transforms/InstCombine/cast-mul-select.ll
index a59d954dac7..b140dfa2229 100644
--- a/test/Transforms/InstCombine/cast-mul-select.ll
+++ b/test/Transforms/InstCombine/cast-mul-select.ll
@@ -14,8 +14,8 @@ define i32 @mul(i32 %x, i32 %y) {
 ; instruction.
 ; DBGINFO-LABEL: @mul(
 ; DBGINFO-NEXT:    [[C:%.*]] = mul i32 {{.*}}
-; DBGINFO-NEXT:    call void @llvm.dbg.value(metadata i32 [[C]]
 ; DBGINFO-NEXT:    [[D:%.*]] = and i32 {{.*}}
+; DBGINFO-NEXT:    call void @llvm.dbg.value(metadata i32 [[C]]
 ; DBGINFO-NEXT:    call void @llvm.dbg.value(metadata i32 [[D]]
 
   %A = trunc i32 %x to i8
diff --git a/test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll b/test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll
new file mode 100644
index 00000000000..74fdfa88cd1
--- /dev/null
+++ b/test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll
@@ -0,0 +1,50 @@
+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+; CHECK-LABEL: define {{.*}} @test5
+define i16 @test5(i16 %A) !dbg !34 {
+  ; CHECK: [[and:%.*]] = and i16 %A, 15
+
+  %B = sext i16 %A to i32, !dbg !40
+  call void @llvm.dbg.value(metadata i32 %B, metadata !36, metadata !DIExpression()), !dbg !40
+
+  %C = and i32 %B, 15, !dbg !41
+  call void @llvm.dbg.value(metadata i32 %C, metadata !37, metadata !DIExpression()), !dbg !41
+
+  ; Preserve the dbg.value for the DCE'd 32-bit 'and'.
+  ;
+  ; The high 16 bits of the original 'and' require sign-extending the new 16-bit and:
+  ; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[and]], metadata [[C:![0-9]+]],
+  ; CHECK-SAME:    metadata !DIExpression(DW_OP_dup, DW_OP_constu, 15, DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or, DW_OP_stack_value)
+
+  %D = trunc i32 %C to i16, !dbg !42
+  call void @llvm.dbg.value(metadata i16 %D, metadata !38, metadata !DIExpression()), !dbg !42
+
+  ; The dbg.value for a truncate should simply point to the result of the 16-bit 'and'.
+  ; CHECK-NEXT: call void @llvm.dbg.value(metadata i16 [[and]], metadata [[D:![0-9]+]], metadata !DIExpression())
+
+  ret i16 %D, !dbg !43
+  ; CHECK-NEXT: ret i16 [[and]]
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "void", directory: "/")
+!2 = !{}
+!5 = !{i32 2, !"Debug Info Version", i32 3}
+!7 = !DISubroutineType(types: !2)
+!10 = !DIBasicType(name: "ty32", size: 32, encoding: DW_ATE_signed)
+!12 = !DIBasicType(name: "ty8", size: 8, encoding: DW_ATE_signed)
+!34 = distinct !DISubprogram(name: "test5", linkageName: "test5", scope: null, file: !1, line: 12, type: !7, isLocal: false, isDefinition: true, scopeLine: 12, isOptimized: true, unit: !0, retainedNodes: !35)
+!35 = !{!36, !37, !38}
+!36 = !DILocalVariable(name: "B", scope: !34, file: !1, line: 12, type: !10)
+!37 = !DILocalVariable(name: "C", scope: !34, file: !1, line: 13, type: !10)
+!38 = !DILocalVariable(name: "D", scope: !34, file: !1, line: 14, type: !39)
+!39 = !DIBasicType(name: "ty16", size: 16, encoding: DW_ATE_signed)
+!40 = !DILocation(line: 12, column: 1, scope: !34)
+!41 = !DILocation(line: 13, column: 1, scope: !34)
+!42 = !DILocation(line: 14, column: 1, scope: !34)
+!43 = !DILocation(line: 15, column: 1, scope: !34)
diff --git a/test/Transforms/InstCombine/debuginfo-variables.ll b/test/Transforms/InstCombine/debuginfo-variables.ll
index 8c4aba8de8a..50fffbf88b1 100644
--- a/test/Transforms/InstCombine/debuginfo-variables.ll
+++ b/test/Transforms/InstCombine/debuginfo-variables.ll
@@ -1,5 +1,7 @@
 ; RUN: opt < %s -debugify -instcombine -S | FileCheck %s
 
+declare void @escape32(i32)
+
 define i64 @test_sext_zext(i16 %A) {
 ; CHECK-LABEL: @test_sext_zext(
 ; CHECK-NEXT:  [[C2:%.*]] = zext i16 %A to i64
@@ -10,6 +12,20 @@ define i64 @test_sext_zext(i16 %A) {
   ret i64 %c2
 }
 
+define i64 @test_used_sext_zext(i16 %A) {
+; CHECK-LABEL: @test_used_sext_zext(
+; CHECK-NEXT:  [[C1:%.*]] = zext i16 %A to i32
+; CHECK-NEXT:  call void @llvm.dbg.value(metadata i32 [[C1]], {{.*}}, metadata !DIExpression())
+; CHECK-NEXT:  [[C2:%.*]] = zext i16 %A to i64
+; CHECK-NEXT:  call void @llvm.dbg.value(metadata i64 [[C2]], {{.*}}, metadata !DIExpression())
+; CHECK-NEXT:  call void @escape32(i32 %c1)
+; CHECK-NEXT:  ret i64 %c2, !dbg !23
+  %c1 = zext i16 %A to i32
+  %c2 = sext i32 %c1 to i64
+  call void @escape32(i32 %c1)
+  ret i64 %c2
+}
+
 define void @test_or(i64 %A) {
 ; CHECK-LABEL: @test_or(
 ; CHECK-NEXT:  call void @llvm.dbg.value(metadata i64 %A, {{.*}}, metadata !DIExpression(DW_OP_constu, 256, DW_OP_or, DW_OP_stack_value))
diff --git a/unittests/Transforms/Utils/Local.cpp b/unittests/Transforms/Utils/Local.cpp
index 96446cc529e..5850910403f 100644
--- a/unittests/Transforms/Utils/Local.cpp
+++ b/unittests/Transforms/Utils/Local.cpp
@@ -15,6 +15,7 @@
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Verifier.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
@@ -429,3 +430,191 @@ TEST_F(SalvageDebugInfoTest, RecursiveBlockSimplification) {
   ASSERT_TRUE(Deleted);
   verifyDebugValuesAreSalvaged();
 }
+
+TEST(Local, ReplaceAllDbgUsesWith) {
+  using namespace llvm::dwarf;
+
+  LLVMContext Ctx;
+
+  // Note: The datalayout simulates Darwin/x86_64.
+  std::unique_ptr<Module> M = parseIR(Ctx,
+                                      R"(
+    target datalayout = "e-m:o-i63:64-f80:128-n8:16:32:64-S128"
+
+    declare i32 @escape(i32)
+
+    define void @f() !dbg !6 {
+    entry:
+      %a = add i32 0, 1, !dbg !15
+      call void @llvm.dbg.value(metadata i32 %a, metadata !9, metadata !DIExpression()), !dbg !15
+
+      %b = add i64 0, 1, !dbg !16
+      call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression()), !dbg !16
+      call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul)), !dbg !16
+      call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_stack_value)), !dbg !16
+      call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !16
+      call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_LLVM_fragment, 0, 8)), !dbg !16
+      call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8)), !dbg !16
+
+      %c = inttoptr i64 0 to i64*, !dbg !17
+      call void @llvm.dbg.declare(metadata i64* %c, metadata !13, metadata !DIExpression()), !dbg !17
+
+      %d = inttoptr i64 0 to i32*, !dbg !18
+      call void @llvm.dbg.addr(metadata i32* %d, metadata !20, metadata !DIExpression()), !dbg !18
+
+      %e = add <2 x i16> zeroinitializer, zeroinitializer
+      call void @llvm.dbg.value(metadata <2 x i16> %e, metadata !14, metadata !DIExpression()), !dbg !18
+
+      %f = call i32 @escape(i32 0)
+      call void @llvm.dbg.value(metadata i32 %f, metadata !9, metadata !DIExpression()), !dbg !15
+
+      %barrier = call i32 @escape(i32 0)
+
+      %g = call i32 @escape(i32 %f)
+      call void @llvm.dbg.value(metadata i32 %g, metadata !9, metadata !DIExpression()), !dbg !15
+
+      ret void, !dbg !19
+    }
+
+    declare void @llvm.dbg.addr(metadata, metadata, metadata)
+    declare void @llvm.dbg.declare(metadata, metadata, metadata)
+    declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+    !llvm.dbg.cu = !{!0}
+    !llvm.module.flags = !{!5}
+
+    !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+    !1 = !DIFile(filename: "/Users/vsk/Desktop/foo.ll", directory: "/")
+    !2 = !{}
+    !5 = !{i32 2, !"Debug Info Version", i32 3}
+    !6 = distinct !DISubprogram(name: "f", linkageName: "f", scope: null, file: !1, line: 1, type: !7, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, retainedNodes: !8)
+    !7 = !DISubroutineType(types: !2)
+    !8 = !{!9, !11, !13, !14}
+    !9 = !DILocalVariable(name: "1", scope: !6, file: !1, line: 1, type: !10)
+    !10 = !DIBasicType(name: "ty32", size: 32, encoding: DW_ATE_signed)
+    !11 = !DILocalVariable(name: "2", scope: !6, file: !1, line: 2, type: !12)
+    !12 = !DIBasicType(name: "ty64", size: 64, encoding: DW_ATE_signed)
+    !13 = !DILocalVariable(name: "3", scope: !6, file: !1, line: 3, type: !12)
+    !14 = !DILocalVariable(name: "4", scope: !6, file: !1, line: 4, type: !10)
+    !15 = !DILocation(line: 1, column: 1, scope: !6)
+    !16 = !DILocation(line: 2, column: 1, scope: !6)
+    !17 = !DILocation(line: 3, column: 1, scope: !6)
+    !18 = !DILocation(line: 4, column: 1, scope: !6)
+    !19 = !DILocation(line: 5, column: 1, scope: !6)
+    !20 = !DILocalVariable(name: "5", scope: !6, file: !1, line: 5, type: !10)
+  )");
+
+  bool BrokenDebugInfo = true;
+  verifyModule(*M, &errs(), &BrokenDebugInfo);
+  ASSERT_FALSE(BrokenDebugInfo);
+
+  Function &F = *cast<Function>(M->getNamedValue("f"));
+  DominatorTree DT{F};
+
+  BasicBlock &BB = F.front();
+  Instruction &A = BB.front();
+  Instruction &B = *A.getNextNonDebugInstruction();
+  Instruction &C = *B.getNextNonDebugInstruction();
+  Instruction &D = *C.getNextNonDebugInstruction();
+  Instruction &E = *D.getNextNonDebugInstruction();
+  Instruction &F_ = *E.getNextNonDebugInstruction();
+  Instruction &Barrier = *F_.getNextNonDebugInstruction();
+  Instruction &G = *Barrier.getNextNonDebugInstruction();
+
+  // Simulate i32 <-> i64* conversion. Expect no updates: the datalayout says
+  // pointers are 64 bits, so the conversion would be lossy.
+  EXPECT_FALSE(replaceAllDbgUsesWith(A, C, C, DT));
+  EXPECT_FALSE(replaceAllDbgUsesWith(C, A, A, DT));
+
+  // Simulate i32 <-> <2 x i16> conversion. This is unsupported.
+  EXPECT_FALSE(replaceAllDbgUsesWith(E, A, A, DT));
+  EXPECT_FALSE(replaceAllDbgUsesWith(A, E, E, DT));
+
+  // Simulate i32* <-> i64* conversion.
+  EXPECT_TRUE(replaceAllDbgUsesWith(D, C, C, DT));
+
+  SmallVector<DbgInfoIntrinsic *, 2> CDbgVals;
+  findDbgUsers(CDbgVals, &C);
+  EXPECT_EQ(2U, CDbgVals.size());
+  EXPECT_TRUE(any_of(CDbgVals, [](DbgInfoIntrinsic *DII) {
+    return isa<DbgAddrIntrinsic>(DII);
+  }));
+  EXPECT_TRUE(any_of(CDbgVals, [](DbgInfoIntrinsic *DII) {
+    return isa<DbgDeclareInst>(DII);
+  }));
+
+  EXPECT_TRUE(replaceAllDbgUsesWith(C, D, D, DT));
+
+  SmallVector<DbgInfoIntrinsic *, 2> DDbgVals;
+  findDbgUsers(DDbgVals, &D);
+  EXPECT_EQ(2U, DDbgVals.size());
+  EXPECT_TRUE(any_of(DDbgVals, [](DbgInfoIntrinsic *DII) {
+    return isa<DbgAddrIntrinsic>(DII);
+  }));
+  EXPECT_TRUE(any_of(DDbgVals, [](DbgInfoIntrinsic *DII) {
+    return isa<DbgDeclareInst>(DII);
+  }));
+
+  // Introduce a use-before-def. Check that the dbg.value for %a is salvaged.
+  EXPECT_TRUE(replaceAllDbgUsesWith(A, F_, F_, DT));
+
+  auto *ADbgVal = cast<DbgValueInst>(A.getNextNode());
+  EXPECT_EQ(ConstantInt::get(A.getType(), 0), ADbgVal->getVariableLocation());
+
+  // Introduce a use-before-def. Check that the dbg.values for %f are deleted.
+  EXPECT_TRUE(replaceAllDbgUsesWith(F_, G, G, DT));
+
+  SmallVector<DbgValueInst *, 1> FDbgVals;
+  findDbgValues(FDbgVals, &F);
+  EXPECT_EQ(0U, FDbgVals.size());
+
+  // Simulate i32 -> i64 conversion to test sign-extension. Here are some
+  // interesting cases to handle:
+  //  1) debug user has empty DIExpression
+  //  2) debug user has non-empty, non-stack-value'd DIExpression
+  //  3) debug user has non-empty, stack-value'd DIExpression
+  //  4-6) like (1-3), but with a fragment
+  EXPECT_TRUE(replaceAllDbgUsesWith(B, A, A, DT));
+
+  SmallVector<DbgValueInst *, 8> ADbgVals;
+  findDbgValues(ADbgVals, &A);
+  EXPECT_EQ(6U, ADbgVals.size());
+
+  // Check that %a has a dbg.value with a DIExpression matching \p Ops.
+  auto hasADbgVal = [&](ArrayRef<uint64_t> Ops) {
+    return any_of(ADbgVals, [&](DbgValueInst *DVI) {
+      assert(DVI->getVariable()->getName() == "2");
+      return DVI->getExpression()->getElements() == Ops;
+    });
+  };
+
+  // Case 1: The original expr is empty, so no deref is needed.
+  EXPECT_TRUE(hasADbgVal({DW_OP_dup, DW_OP_constu, 31, DW_OP_shr, DW_OP_lit0,
+                          DW_OP_not, DW_OP_mul, DW_OP_or, DW_OP_stack_value}));
+
+  // Case 2: Perform an address calculation with the original expr, deref it,
+  // then sign-extend the result.
+  EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_deref, DW_OP_dup,
+                          DW_OP_constu, 31, DW_OP_shr, DW_OP_lit0, DW_OP_not,
+                          DW_OP_mul, DW_OP_or, DW_OP_stack_value}));
+
+  // Case 3: Insert the sign-extension logic before the DW_OP_stack_value.
+  EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_dup, DW_OP_constu, 31,
+                          DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or,
+                          DW_OP_stack_value}));
+
+  // Cases 4-6: Just like cases 1-3, but preserve the fragment at the end.
+  EXPECT_TRUE(hasADbgVal({DW_OP_dup, DW_OP_constu, 31, DW_OP_shr, DW_OP_lit0,
+                          DW_OP_not, DW_OP_mul, DW_OP_or, DW_OP_stack_value,
+                          DW_OP_LLVM_fragment, 0, 8}));
+  EXPECT_TRUE(
+      hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_deref, DW_OP_dup, DW_OP_constu,
+                  31, DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or,
+                  DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8}));
+  EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_dup, DW_OP_constu, 31,
+                          DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or,
+                          DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8}));
+
+  verifyModule(*M, &errs(), &BrokenDebugInfo);
+  ASSERT_FALSE(BrokenDebugInfo);
+}