[Local] replaceAllDbgUsesWith: Update debug values before RAUW

[vsk]

Summary

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.

[aprantl]

include/llvm/IR/DebugInfoMetadata.h

785 ↗

(On Diff #153187)

Why not make an enum { Unknown, Signed, Unsigned } ?

test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll

17 ↗

(On Diff #153187)

wouldn't DW_OP_lit0 DW_OP_not be shorter than DW_OP_constu 0xfffffff ?

[aprantl]

test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll

17 ↗

(On Diff #153187)

To keep the IR simple we could also recognize and normalize this sequence in DwarfExpression.cpp

[vsk]

I've incorporated some offline review feedback from @aprantl. We can assume that a debugger will set the high bits of a value to 0, so we can make zero-extension a no-op.

include/llvm/IR/DebugInfoMetadata.h

785 ↗

(On Diff #153187)

It makes it a bit too easy to make this mistake:

bool IsUnsigned = T.getSignedness() != Signedness::Signed;

test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll

17 ↗

(On Diff #153187)

Sounds good, thanks! I'll save the normalizing change for later.

[vsk]

I'm double-checking the DWARF for sign extension. Here is what I see in the stage2 llc binary:

0x00754923:                     DW_TAG_inlined_subroutine
                                  DW_AT_abstract_origin	(0x0000000000751e3a "_ZL28isPotentialBlockedMemCpyPairii")
                                  DW_AT_ranges [... snip]
                                  DW_AT_call_file	("/Users/vsk/src/llvm.org-master/llvm/lib/Target/X86/X86AvoidStoreForwardingBlocks.cpp")
                                  DW_AT_call_line	(546)

0x00754930:                       DW_TAG_formal_parameter
                                    DW_AT_location	(0x00186529
                                       [0x00000000000008a4,  0x00000000000008bb): DW_OP_reg2 RCX, DW_OP_piece 0x2, DW_OP_breg2 RCX+0, DW_OP_constu 0xffff, DW_OP_and, DW_OP_constu 0xf, DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_stack_value, DW_OP_piece 0x2
                                       [0x00000000000008fe,  0x0000000000000906): DW_OP_reg2 RCX, DW_OP_piece 0x2, DW_OP_breg2 RCX+0, DW_OP_constu 0xffff, DW_OP_and, DW_OP_constu 0xf, DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_stack_value, DW_OP_piece 0x2
                                       [0x000000000000096e,  0x0000000000000971): DW_OP_reg2 RCX, DW_OP_piece 0x2, DW_OP_breg2 RCX+0, DW_OP_constu 0xffff, DW_OP_and, DW_OP_constu 0xf, DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_stack_value, DW_OP_piece 0x2)
                                    DW_AT_abstract_origin	(0x0000000000751e4b "LdOpcode")

This shows that the DIExpression is lowered correctly, I think. The variable "LdOpcode" is an "int" in the source, but some optimization has us using only its lower 16 bits. Unfortunately, lldb doesn't accept this variable description:

~/src/builds/llvm.org-master-RA-stage2 (0) $ lldb -- ./bin/llc /Users/vsk/src/llvm.org-master/llvm/test/CodeGen/X86/avoid-sfb-overlaps.ll -mtriple=x86_64-linux -o -
(lldb) b isPotentialBlockedMemCpyPair
Breakpoint 1: where = llc`(anonymous namespace)::X86AvoidSFBPass::runOnMachineFunction(llvm::MachineFunction&) + 1188 [inlined] isPotentialBlockedMemCpyPair(int, int) at X86AvoidStoreForwardingBlocks.cpp:546, address = 0x0000000100078cb4
...
Process 24842 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
    frame #0: 0x0000000100078cb4 llc`(anonymous namespace)::X86AvoidSFBPass::runOnMachineFunction(llvm::MachineFunction&) [inlined] isPotentialBlockedMemCpyPair(LdOpcode=<unavailable>, StOpcode=<unavailable>) at X86AvoidStoreForwardingBlocks.cpp:162 [opt]
   159  }
   160
   161  static bool isPotentialBlockedMemCpyPair(int LdOpcode, int StOpcode) {
-> 162    switch (LdOpcode) {
 
(lldb) p LdOpcode
error: Couldn't materialize: couldn't get the value of variable LdOpcode: DW_OP_piece for offset 2 but top of stack is of size 8
error: errored out in DoExecute, couldn't PrepareToExecuteJITExpression

Here is what the DWARF4 standard says:

The DW_OP_piece operation takes a single operand, which is an unsigned LEB128 number. The number describes the size in bytes of the piece of the object referenced by the preceding simple location description. If the piece is located in a register, but does not occupy the entire register, the placement of the piece within that register is defined by the ABI.

With this patch, LLVM emits DW_OP_reg2 RCX, DW_OP_piece 0x2. LLDB should know to interpret this as the low 16 bits of %rcx. We'll have to teach it.

[aprantl]

test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll

17 ↗

(On Diff #153187)

While you're at it:

DW_OP_constu, 15 could be shortened to DW_OP_lit15 :-)

It should also be more efficient to join the two fragments <lower> <upper> DW_OP_lit16 DW_OP_shl DW_OP_or
That saves two DW_OP_LLVM_fragment expressions and one dbg.value.

[vsk]

test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll

17 ↗

(On Diff #153187)

Nice, I've made a note of the DW_OP_litX (X < 32) normalization :).

I don't see how to use a single dbg.value to describe a sign-extended variable. You need to refer to the value operand of the dbg.value twice: once for the initial SHR, and again at the end for the OR. Are you suggesting making this work using DW_OP_dup? So, for this example:

DW_OP_dup /* Duplicate the 16-bit and */, lit15, SHR, lit0, NOT, MUL /* Calculate the high bits */, OR /* Combine the high bits with the duplicated low bits */?

[vsk]

In this update I've taken @aprantl's suggestion and used DW_OP_dup to get the sign-extension down to one dbg.value. This is a neat simplification. One benefit is that LLDB actually understands DW_OP_dup :). The failing "LdOpcode" example now works:

    frame #0: 0x0000000100077f24 llc`(anonymous namespace)::X86AvoidSFBPass::runOnMachineFunction(llvm::MachineFunction&) [inlined] isPotentialBlockedMemCpyPair(LdOpcode=1899, StOpcode=1898) at X86AvoidStoreForwardingBlocks.cpp:162 [opt]
   159  }
   160 
   161  static bool isPotentialBlockedMemCpyPair(int LdOpcode, int StOpcode) {
-> 162    switch (LdOpcode) {
   163    case X86::MOVUPSrm:
   164    case X86::MOVAPSrm:
   165      return StOpcode == X86::MOVUPSmr || StOpcode == X86::MOVAPSmr;
Target 0: (llc) stopped.
(lldb) p LdOpcode
(int) $0 = 1899

[vsk]

• Remove some defensive code meant to deal with failed fragment creation. This patch doesn't rely on creating fragments any more.

[bjope]

lib/Transforms/Utils/Local.cpp

1752 ↗

(On Diff #153249)

Not sure that I understand this. You say that if at least one of the types is a pointer, and neither is a non-integral pointer type, then they are compatible.
Don't you need to check that the sizes match here? Or in what sense are they compatible?

1806 ↗

(On Diff #153249)

Some day I think we need to implement support for the types expression stack from DWARF 5. Currently I think LLVM assumes that the DWARF expression stack is 64 bits wide (or in LLVM IR we maybe assume that we have infinite bits and can do DW_OP_shr etc on any type).

For our target the expression stack is 32 bits. And when legalizing larger types like i64 at ISel we end up trying to split these dbg.intrinsics into several DBG_VALUE instruction, using DW_OP_LLVM_fragment for to identify the different parts. Right now we have no simple way in rewriting a complex DIExpression (using 64-bit expressions) into smaller pieces, so we need to discard the debug info.

1811 ↗

(On Diff #153249)

I don't think WithStackValue is correct if there could be users from findDbgUsers that is a dbg.declare (because dbg.declare is indirect).
Maybe unlikely to happen here, but I don't know. The same kind of fault exist in salvageDebugInfo, and I've been trying to understand if we ever expect to have non-empty DIExpressions in dbg.declare (except for DW_OP_LLVM_fragment). For example having a DW_OP_stack_value in dbg.declare seems weird, right?

And what happens if we have a dbg.value and the DIExpression already got a non-empty DIExpression, ending without a DW_OP_stack_value. Then it is indirect, and adding DW_OP_stack_value would turn it into being direct. Or should it perhaps be illegal to have an indirect dbg.value like that?

[aprantl]

test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll

17 ↗

(On Diff #153187)

You are correct, DW_OP_dup exists exactly for this kind of use-case.

[vsk]

lib/Transforms/Utils/Local.cpp

1752 ↗

(On Diff #153249)

I'd like this to be a target-aware way to identify semantically-equivalent bitcasts, inttoptr, and ptrtoint conversions. I'm using isNonIntegralPointerType because, AFAIK, inttoptr/ptrtoint are not lossy on targets with integral pointers. I assumed that the sizes of FromTy and ToTy are equal when at least one of the types is a pointer type, but I'm no longer sure this is a valid assumption. I'll rewrite this to be cleaner and add an explicit check.

1806 ↗

(On Diff #153249)

I think LLVM does assume a 64-bit width for the expression stack (at least, we can't represent any DW_OP_constu wider than 64-bits in the IR).

The scheme you describe of splitting up the dbg intrinsics for i64 values and rewriting their expressions sounds very difficult. I'm not familiar with any backends, but IIRC legalization occurs early, so a split i32 may be optimized out leaving you with an incomplete (actually, incorrect) variable description? Does DWARF5 alleviate the issue at all? Maybe you could introduce a vendor extension to apply DW_OP_convert to a subset of a source variable's bits?

1811 ↗

(On Diff #153249)

You're correct to point out that the operand of a dbg.{addr,declare} is the address of a variable, not the variable itself. But I don't see how we'd take the sign-extension code path here when the dbg intrinsic operand is a pointer. Actually, allowing this utility and salvageDI to operate on dbg.addr seems useful, because they can preserve debug info across no-op pointer bitcasts.

I don't think we have any code that would add a DW_OP_stack_value to a dbg.{addr, declare}, but if we did, I don't think it would be weird. IIUC, it would just mean the debugger needs to do pointer arithmetic before loading a variable. That seems just like having a dbg.value for a pointer operand and adding a DW_OP_deref at the end (before DW_OP_stack_value).

I don't understand your last question about dbg.values with non-empty, non-stack-value expressions. It seems reasonable to create these (say, by using DW_OP_deref), and I don't see why they can't also be treated as stack values.

[dblaikie]

Side note: please don't depend on what type a pointer points to, if
possible (& it should be possible everywhere except where necessary to
match the IR constraints - eg: you may need to check a pointer's pointee
type to ensure a use of a value of that type matches up with its
definition). Eventually pointee types will go away & someone will have to
fix up that code... best to avoid that if we can.

[bjope]

lib/Transforms/Utils/Local.cpp

1811 ↗

(On Diff #153249)

I don't understand your last question about dbg.values with non-empty, non-stack-value expressions. It seems reasonable to create these (say, by using DW_OP_deref), and I don't see why they can't also be treated as stack values.

Let's say that we have

dbg.value  i32 %x, !y, DIExpression(DW_OP_lit1, DW_OP_add)

then it means that the value of !y is given by dereferencing (%x+1).
If %x can be rewritten as a sign-extend of some value %z, and you use

prependOpcodes(OldDII.getExpression(), Ops, DIExpression::WithStackValue);

then, afaik, the DW_OP_stack_value is added at the end of the expression, while the Ops are prepended. So you end up with

dbg.value  i32 %z, !y, DIExpression(Ops, DW_OP_lit1, DW_OP_add, DW_OP_stack_value)

So we will end up saying that !y is equal to (%x + 1) instead of that (%x + 1) points to the value.

This could be an unexpected situation here, never supposed to happen. Then some asserts showing those assumptions might be good. Maybe such asserts could be put inside prependOpcodes.

[vsk]

lib/Transforms/Utils/Local.cpp

1811 ↗

(On Diff #153249)

Now I understand, thanks. The key language from the docs I was missing is:
"DIExpressions also follow this model: A DIExpression that doesn’t have a trailing DW_OP_stack_value will describe an address when combined with a concrete location."

This means the current patch does not handle any dbg.{addr,declare} or non-empty DIExpressions properly. It would mess up the variable's address calculation and/or pre-existing stack_value computations.

I think we should handle this case. I'll try to find a way to normalize expressions as stack values before appending any DW_OPs to them.

[vsk]

• Introduce and use DIExpression::appendToStack() to create sign extension stack values. It takes care of dereferencing indirect values when needed.
• Rename insertReplacementDbgValues to replaceAllDbgUsesWith. The main change is that debug intrinsics are now updated in-place. The previous behavior of inserting new debug values could reorder the way variable updates are seen in the debugger.

[gramanas]

lib/Transforms/Utils/Local.cpp

1844 ↗

(On Diff #154033)

Could FromBits be equal to ToBits? In that case neither zext nor sext is needed. Could this be if (FromBits <= ToBits)?

[aprantl]

include/llvm/IR/DebugInfoMetadata.h

2332 ↗

(On Diff #154033)

This looks very dangerous. DIExpressions are not distinct so they may be shared by many users. Shouldn't we create a new DIExpression instead of modifying the old one?

[vsk]

include/llvm/IR/DebugInfoMetadata.h

2332 ↗

(On Diff #154033)

Why does this modify an existing expression? I think I'm only using it to create a new expression (in DIExpression::appendToStack, appendToVector(NewOps)).

lib/Transforms/Utils/Local.cpp

1844 ↗

(On Diff #154033)

No, that case should be handled earlier, in isBitCastSemanticsPreserving().

[aprantl]

include/llvm/IR/DebugInfoMetadata.h

2332 ↗

(On Diff #154033)

My bad. I overlooked that this is a const member and that V is the one being modified. Sorry for the noise!

[bjope]

FYI: Looks like you have address my earlier comments. So I have no blocking remarks.

The addition of DomPoint / DT was interesting (not sure that I have figured out exactly which scenarios that are handled)
I think that we still have the problem with only checking dominance of the moved/replaced value though.
As was discussed earlier somewhere (a patch in post RA MachineSink) we also might have the problem that there are other dbg.value intrinsics, referring to the same variable (or an overlapping fragment). And the question is if it is correct to reorder such dbg.value intrinsics, or what to do. Matt wrote a TR about it here https://bugs.llvm.org/show_bug.cgi?id=37897

lib/Transforms/Utils/Local.cpp

1844 ↗

(On Diff #154033)

It would still be more correct to enter the if in case FromBits==ToBits. So I don't think it hurts to use <= here.

[vsk]

• Rebase.
• Address the FromBits == ToBits case.
• Extend the unit test. There are two new values, %f and %g, which are used to demonstrate what happens in the two use-before-def scenarios: either we're able to salvage the debug user, or we need to delete it.

[aprantl]

lib/Transforms/Utils/Local.cpp

1853 ↗

(On Diff #154291)

There is no way to sign-extend, that's right, but zero-extension as a concept doesn't make much sense in the untyped DWARF (4) stack, since we don't know how large the stack values are anyway. Looks like the code knows this but the comment hasn't been updated yet.

[aprantl]

Thanks, I think this looks good now!

[vsk]

In D48676#1153467, @bjope wrote:

FYI: Looks like you have address my earlier comments. So I have no blocking remarks.

Thanks for taking a look, I really appreciate your detailed feedback.

The addition of DomPoint / DT was interesting (not sure that I have figured out exactly which scenarios that are handled)

The two scenarios are:

1. The replacement value is a Constant, will be inserted at a position which dominates the original instruction, or will be inserted immediately after the original instruction (which is deleted later). In this scenario there's no risk of introducing debug value use-before-def.
2. The original value dominates the position where the replacement value will be inserted. A good example of this is the 'alloca-cast-debuginfo.ll' test. In an intermediate step, InstCombine inserts a temporary cast of an alloca:

%local = alloca %struct.Foo
%tmpcast = bitcast %local
call dbg.declare(%tmpcast, "local")
<some instructions follow>
%castOfTmpcast = bitcast %tmpcast

InstCombine recognizes that it can remove 'tmpcast' and simplify 'castOfTmpcast' if it promotes the type of the alloca. Since 'tmpcast' has only one use, we try to save its debug users, anticipating that 'tmpcast' will be deleted. The DomPoint / DT machinery gives us a way to prevent this use-before-def for the unlinked 'simplifiedCast':

%local = alloca i64
call dbg.declare(%simplifiedCast, "local")
<some instructions follow>
%simplifiedCast = bitcast %local

We either salvage the debug user or delete it. The unit test has examples of both situations.

I think that we still have the problem with only checking dominance of the moved/replaced value though.
As was discussed earlier somewhere (a patch in post RA MachineSink) we also might have the problem that there are other dbg.value intrinsics, referring to the same variable (or an overlapping fragment). And the question is if it is correct to reorder such dbg.value intrinsics, or what to do. Matt wrote a TR about it here https://bugs.llvm.org/show_bug.cgi?id=37897

Doesn't this patch sidestep issues with reordering variable updates, because the updates are now all done in-place?

[bjope]

In D48676#1153642, @vsk wrote:

In D48676#1153467, @bjope wrote:

FYI: Looks like you have address my earlier comments. So I have no blocking remarks.

Thanks for taking a look, I really appreciate your detailed feedback.

The addition of DomPoint / DT was interesting (not sure that I have figured out exactly which scenarios that are handled)

The two scenarios are:

1. The replacement value is a Constant, will be inserted at a position which dominates the original instruction, or will be inserted immediately after the original instruction (which is deleted later). In this scenario there's no risk of introducing debug value use-before-def.
2. The original value dominates the position where the replacement value will be inserted. A good example of this is the 'alloca-cast-debuginfo.ll' test. In an intermediate step, InstCombine inserts a temporary cast of an alloca:

%local = alloca %struct.Foo
%tmpcast = bitcast %local
call dbg.declare(%tmpcast, "local")
<some instructions follow>
%castOfTmpcast = bitcast %tmpcast

InstCombine recognizes that it can remove 'tmpcast' and simplify 'castOfTmpcast' if it promotes the type of the alloca. Since 'tmpcast' has only one use, we try to save its debug users, anticipating that 'tmpcast' will be deleted. The DomPoint / DT machinery gives us a way to prevent this use-before-def for the unlinked 'simplifiedCast':

%local = alloca i64
call dbg.declare(%simplifiedCast, "local")
<some instructions follow>
%simplifiedCast = bitcast %local

We either salvage the debug user or delete it. The unit test has examples of both situations.

I think that we still have the problem with only checking dominance of the moved/replaced value though.
As was discussed earlier somewhere (a patch in post RA MachineSink) we also might have the problem that there are other dbg.value intrinsics, referring to the same variable (or an overlapping fragment). And the question is if it is correct to reorder such dbg.value intrinsics, or what to do. Matt wrote a TR about it here https://bugs.llvm.org/show_bug.cgi?id=37897

Doesn't this patch sidestep issues with reordering variable updates, because the updates are now all done in-place?

I thought that

DII->moveAfter(&DomPoint);

still could move the DII without really taking other dbg.value intrinsics, potentially describing the same variable, into account.
But I see now that the moveAfter only happens when

DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint

which means that we do not move the DII arbitrarely (it's just moving to the other side of the DomPoint). So it should be ok.

llvm/trunk/include/llvm/IR/DebugInfoMetadata.h

DEFINE_MDNODE_GET(DIBasicType,
                     (unsigned Tag, MDString *Name, uint64_t SizeInBits,
                      uint32_t AlignInBits, unsigned Encoding),
                     (Tag, Name, SizeInBits, AlignInBits, Encoding))
 
   TempDIBasicType clone() const { return cloneImpl(); }
 
   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;
   }
 };
 
 /// Derived types.
 ///
 /// This includes qualified types, pointers, references, friends, typedefs, and
public:
   StringRef getName() const { return getStringOperand(1); }
   DIFile *getFile() const { return cast_or_null<DIFile>(getRawFile()); }
   DITypeRef getType() const { return DITypeRef(getRawType()); }
   uint32_t getAlignInBits() const { return AlignInBits; }
   uint32_t getAlignInBytes() const { return getAlignInBits() / CHAR_BIT; }
   /// 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();
     return "";
   }
 
   StringRef getDirectory() const {
     if (auto *F = getFile())
public:
     uint64_t getArg(unsigned I) const { return Op[I + 1]; }
 
     unsigned getNumArgs() const { return getSize() - 1; }
 
     /// Return the size of the operand.
     ///
     /// 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.
   class expr_op_iterator
       : public std::iterator<std::input_iterator_tag, ExprOperand> {
     ExprOperand Op;
 
   public:
static DIExpression *prepend(const DIExpression *DIExpr, bool DerefBefore,
                                bool StackValue = false);
 
   /// Prepend \p DIExpr with the given opcodes and optionally turn it into a
   /// stack value.
   static DIExpression *prependOpcodes(const DIExpression *DIExpr,
                                       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
   /// a \c DW_OP_LLVM_fragment \c OffsetInBits is interpreted as an offset
   /// into the existing fragment.
   ///
   /// \param OffsetInBits Offset of the piece in bits.
   /// \param SizeInBits   Size of the piece in bits.

llvm/trunk/include/llvm/IR/Type.h

public:
   bool isIntOrIntVectorTy() const { return getScalarType()->isIntegerTy(); }
 
   /// Return true if this is an integer type or a vector of integer types of
   /// the given width.
   bool isIntOrIntVectorTy(unsigned BitWidth) const {
     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; }
 
   /// True if this is an instance of StructType.
   bool isStructTy() const { return getTypeID() == StructTyID; }
 
   /// True if this is an instance of ArrayType.
   bool isArrayTy() const { return getTypeID() == ArrayTyID; }

llvm/trunk/include/llvm/Transforms/Utils/Local.h

 /// Replaces multiple llvm.dbg.value instructions when the alloca it describes
 /// is replaced with a new value. If Offset is non-zero, a constant displacement
 /// is added to the expression (after the mandatory Deref). Offset can be
 /// negative. New llvm.dbg.value instructions are inserted at the locations of
 /// the instructions they replace.
 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.
 unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
 
 /// Insert an unreachable instruction before the specified
 /// instruction, making it and the rest of the code in the block dead.
 unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfExpression.cpp

while (ExprCursor) {
     case dwarf::DW_OP_div:
     case dwarf::DW_OP_mod:
     case dwarf::DW_OP_or:
     case dwarf::DW_OP_and:
     case dwarf::DW_OP_xor:
     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:
       assert(LocationKind != Register);
       if (LocationKind != Memory && ::isMemoryLocation(ExprCursor))
         // Turning this into a memory location description makes the deref
         // implicit.
         LocationKind = Memory;

llvm/trunk/lib/IR/DebugInfoMetadata.cpp

DIBasicType *DIBasicType::getImpl(LLVMContext &Context, unsigned Tag,
   assert(isCanonical(Name) && "Expected canonical MDString");
   DEFINE_GETIMPL_LOOKUP(DIBasicType,
                         (Tag, Name, SizeInBits, AlignInBits, Encoding));
   Metadata *Ops[] = {nullptr, nullptr, Name};
   DEFINE_GETIMPL_STORE(DIBasicType, (Tag, SizeInBits, AlignInBits, Encoding),
                        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,
     uint32_t AlignInBits, uint64_t OffsetInBits,
     Optional<unsigned> DWARFAddressSpace, DIFlags Flags, Metadata *ExtraData,
     StorageType Storage, bool ShouldCreate) {
   assert(isCanonical(Name) && "Expected canonical MDString");
   DEFINE_GETIMPL_LOOKUP(DIDerivedType,
for (auto I = expr_op_begin(), E = expr_op_end(); I != E; ++I) {
     case dwarf::DW_OP_or:
     case dwarf::DW_OP_and:
     case dwarf::DW_OP_xor:
     case dwarf::DW_OP_shl:
     case dwarf::DW_OP_shr:
     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;
     }
   }
   return true;
 }
 
 Optional<DIExpression::FragmentInfo>
 DIExpression::getFragmentInfo(expr_op_iterator Start, expr_op_iterator End) {
for (auto Op : Expr->expr_ops()) {
       for (unsigned I = 0; I < Op.getNumArgs(); ++I)
         Ops.push_back(Op.getArg(I));
     }
   if (StackValue)
     Ops.push_back(dwarf::DW_OP_stack_value);
   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;
   // Copy over the expression, but leave off any trailing DW_OP_LLVM_fragment.
   if (Expr) {
     for (auto Op : Expr->expr_ops()) {
       switch (Op.getOp()) {
       default: break;

llvm/trunk/lib/Transforms/InstCombine/InstCombineCasts.cpp

Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
 
   // Try to eliminate a cast of a cast.
   if (auto *CSrc = dyn_cast<CastInst>(Src)) {   // A->B->C cast
     if (Instruction::CastOps NewOpc = isEliminableCastPair(CSrc, &CI)) {
       // The first cast (CSrc) is eliminable so we need to fix up or replace
       // 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;
     }
   }
 
   if (auto *Sel = dyn_cast<SelectInst>(Src)) {
     // We are casting a select. Try to fold the cast into the select, but only
     // if the select does not have a compare instruction with matching operand
     // types. Creating a select with operands that are different sizes than its
if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) &&
     // Okay, we can transform this!  Insert the new expression now.
     LLVM_DEBUG(
         dbgs() << "ICE: EvaluateInDifferentType converting expression type"
                   " to avoid zero extend: "
                << CI << '\n');
     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();
 
     // If the high bits are already filled with zeros, just replace this
     // cast with the result.
     if (MaskedValueIsZero(Res,
                           APInt::getHighBitsSet(DestBitSize,

llvm/trunk/lib/Transforms/Utils/Local.cpp

if (auto *L = LocalAsMetadata::getIfExists(AI))
     if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
       for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) {
         Use &U = *UI++;
         if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
           replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
       }
 }
 
-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();
     if (!Ops.empty()) {
       // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they
       // are implicitly pointing out the value as a DWARF memory location
       // description.
       bool WithStackValue = isa<DbgValueInst>(DII);
       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');
   };
 
   auto applyOffset = [&](DbgInfoIntrinsic *DII, uint64_t Offset) {
     SmallVector<uint64_t, 8> Ops;
     DIExpression::appendOffset(Ops, Offset);
     doSalvage(DII, Ops);
   };
 
   auto applyOps = [&](DbgInfoIntrinsic *DII,
                       std::initializer_list<uint64_t> Opcodes) {
     SmallVector<uint64_t, 8> Ops(Opcodes);
     doSalvage(DII, Ops);
   };
 
   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));
     for (auto *DII : DbgUsers) {
       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());
     // Rewrite a constant GEP into a DIExpression.  Since we are performing
     // arithmetic to compute the variable's *value* in the DIExpression, we
     // need to mark the expression with a DW_OP_stack_value.
     APInt Offset(BitWidth, 0);
     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) {
       switch (BI->getOpcode()) {
       case Instruction::Add:
         applyOffset(DII, Val);
         break;
       case Instruction::Sub:
for (auto *DII : DbgUsers) {
       case Instruction::LShr:
         applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shr});
         break;
       case Instruction::AShr:
         applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shra});
         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) {
       // Rewrite the load into DW_OP_deref.
       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);
+
+    // 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;
 
-  // 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');
-    }
+  // 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) {
   unsigned NumDeadInst = 0;
   // Delete the instructions backwards, as it has a reduced likelihood of
   // having to update as many def-use and use-def chains.
   Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
   while (EndInst != &BB->front()) {

llvm/trunk/test/Transforms/InstCombine/alloca-cast-debuginfo.ll

entry:
   %5 = bitcast %struct.Foo* %local to i8*, !dbg !35
   ret void, !dbg !35
 }
 
 ; CHECK-LABEL: define void @f(%struct.Foo* %p)
 ; 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
 
 declare void @llvm.dbg.declare(metadata, metadata, metadata)
 
 declare void @escape(i8*)
 
 !llvm.dbg.cu = !{!0}

llvm/trunk/test/Transforms/InstCombine/cast-mul-select.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 ; RUN: opt -debugify -instcombine -S < %s | FileCheck %s -check-prefix DBGINFO
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32"
 
 define i32 @mul(i32 %x, i32 %y) {
 ; CHECK-LABEL: @mul(
 ; CHECK-NEXT:    [[C:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], 255
 ; CHECK-NEXT:    ret i32 [[D]]
 
 ; Test that when zext is evaluated in different type
 ; we preserve the debug information in the resulting
 ; 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
   %B = trunc i32 %y to i8
   %C = mul i8 %A, %B
   %D = zext i8 %C to i32
   ret i32 %D
 }

llvm/trunk/test/Transforms/InstCombine/cast-set-preserve-signed-dbg-val.ll

+; 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)

llvm/trunk/test/Transforms/InstCombine/debuginfo-variables.ll

 ; 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
 ; CHECK-NEXT:  call void @llvm.dbg.value(metadata i64 [[C2]], {{.*}}, metadata !DIExpression())
 ; CHECK-NEXT:  call void @llvm.dbg.value(metadata i64 [[C2]], {{.*}}, metadata !DIExpression())
   %c1 = zext i16 %A to i32
   %c2 = sext i32 %c1 to i64
   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))
   %1 = or i64 %A, 256
   ret void
 }
 
 define void @test_xor(i32 %A) {

llvm/trunk/unittests/Transforms/Utils/Local.cpp

 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/IRBuilder.h"
 #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"
 
 using namespace llvm;
 
 TEST(Local, RecursivelyDeleteDeadPHINodes) {
   LLVMContext C;
 

 
 TEST_F(SalvageDebugInfoTest, RecursiveBlockSimplification) {
   BasicBlock *BB = &F->front();
   ASSERT_TRUE(BB);
   bool Deleted = SimplifyInstructionsInBlock(BB);
   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);
+}