[BDCE] Skip metadata while replacing uses

[davide]

Summary

The fix committed in r288851 doesn't cover all the cases. In particular, if we have an instruction with side effects which has a no non-dbg use not depending on the bits, we still perform RAUW destroying the dbg.value's first argument.
Prevent metadata from being replaced here to avoid the issue.

[majnemer]

include/llvm/IR/Value.h

277

How about replaceNonMetadataUsesWith

lib/Transforms/Scalar/BDCE.cpp

42–45

I think we can remove this special case now.

[davide]

include/llvm/IR/Value.h

277

Sure.

lib/Transforms/Scalar/BDCE.cpp

42–45

Hal suggested to keep it as a micro-optimization. I'm fine either way.

[davide]

Renamed an API as suggested by David.

[hfinkel]

LGTM

lib/Transforms/Scalar/BDCE.cpp

42–45

I don't feel strongly about it. It does make sense as a micrp-optimization because it will avoid us computing known bits on an instruction where that will never help us.

include/llvm/IR/Value.h

public:
 
   // \brief All values can potentially be named.
   bool hasName() const { return HasName; }
   ValueName *getValueName() const;
   void setValueName(ValueName *VN);
 
 private:
   void destroyValueName();
+  void doRAUW(Value *New, bool NoMetadata);
   void setNameImpl(const Twine &Name);
 
 public:
   /// \brief Return a constant reference to the value's name.
   ///
   /// This is cheap and guaranteed to return the same reference as long as the
   /// value is not modified.
   StringRef getName() const;
public:
 
   /// \brief Change all uses of this to point to a new Value.
   ///
   /// Go through the uses list for this definition and make each use point to
   /// "V" instead of "this".  After this completes, 'this's use list is
   /// guaranteed to be empty.
   void replaceAllUsesWith(Value *V);
 
+  /// \brief Change non-metadata uses of this to point to a new Value.
+  ///
+  /// Go through the uses list for this definition and make each use point to
+  /// "V" instead of "this". This function skips metadata entries in the list.
+  void replaceNonMetadataUsesWith(Value *V);
+
   /// replaceUsesOutsideBlock - Go through the uses list for this definition and
   /// make each use point to "V" instead of "this" when the use is outside the
   /// block. 'This's use list is expected to have at least one element.
   /// Unlike replaceAllUsesWith this function does not support basic block
   /// values or constant users.
   void replaceUsesOutsideBlock(Value *V, BasicBlock *BB);
 
   //----------------------------------------------------------------------

lib/IR/Value.cpp

static bool contains(Value *Expr, Value *V) {
   if (!CE)
     return false;
 
   SmallPtrSet<ConstantExpr *, 4> Cache;
   return contains(Cache, CE, C);
 }
 #endif // NDEBUG
 
-void Value::replaceAllUsesWith(Value *New) {
+void Value::doRAUW(Value *New, bool NoMetadata) {
   assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
   assert(!contains(New, this) &&
          "this->replaceAllUsesWith(expr(this)) is NOT valid!");
   assert(New->getType() == getType() &&
          "replaceAllUses of value with new value of different type!");
 
   // Notify all ValueHandles (if present) that this value is going away.
   if (HasValueHandle)
     ValueHandleBase::ValueIsRAUWd(this, New);
-  if (isUsedByMetadata())
+  if (!NoMetadata && isUsedByMetadata())
     ValueAsMetadata::handleRAUW(this, New);
 
   while (!use_empty()) {
     Use &U = *UseList;
     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
     // constant because they are uniqued.
     if (auto *C = dyn_cast<Constant>(U.getUser())) {
       if (!isa<GlobalValue>(C)) {
         C->handleOperandChange(this, New);
         continue;
       }
     }
 
     U.set(New);
   }
 
   if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
     BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
 }
 
+void Value::replaceAllUsesWith(Value *New) {
+  doRAUW(New, false /* NoMetadata */);
+}
+
+void Value::replaceNonMetadataUsesWith(Value *New) {
+  doRAUW(New, true /* NoMetadata */);
+}
+
 // Like replaceAllUsesWith except it does not handle constants or basic blocks.
 // This routine leaves uses within BB.
 void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
   assert(New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!");
   assert(!contains(New, this) &&
          "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!");
   assert(New->getType() == getType() &&
          "replaceUses of value with new value of different type!");

lib/Transforms/Scalar/BDCE.cpp

 
 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
 
 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
   SmallVector<Instruction*, 128> Worklist;
   bool Changed = false;
   for (Instruction &I : instructions(F)) {
     // If the instruction has side effects and no non-dbg uses,
     // BDCE should skip it.
     if (I.mayHaveSideEffects() && I.use_empty())
       continue;
 
     if (I.getType()->isIntegerTy() &&
         !DB.getDemandedBits(&I).getBoolValue()) {
       // For live instructions that have all dead bits, first make them dead by
       // replacing all uses with something else. Then, if they don't need to
       // remain live (because they have side effects, etc.) we can remove them.
       DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
       // FIXME: In theory we could substitute undef here instead of zero.
       // This should be reconsidered once we settle on the semantics of
       // undef, poison, etc.
       Value *Zero = ConstantInt::get(I.getType(), 0);
       ++NumSimplified;
-      I.replaceAllUsesWith(Zero);
+      I.replaceNonMetadataUsesWith(Zero);
       Changed = true;
     }
     if (!DB.isInstructionDead(&I))
       continue;
 
     Worklist.push_back(&I);
     I.dropAllReferences();
     Changed = true;

test/Transforms/BDCE/dbg-multipleuses.ll

+; Test that BDCE doesn't destroy llvm.dbg.value's argument.
+; RUN: opt -bdce %s -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: define void @f()
+; CHECK-NEXT: entry:
+; CHECK-NEXT: tail call void (...) @h()
+; CHECK-NEXT: %[[CALL:.*]] = tail call i32 (...) @g()
+; CHECK-NEXT: tail call void @llvm.dbg.value(metadata i32 %[[CALL:.*]]
+
+define void @f() !dbg !6 {
+entry:
+  tail call void (...) @h(), !dbg !9
+  %call = tail call i32 (...) @g(), !dbg !10
+  tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !11, metadata !13), !dbg !14
+  %patatino = xor i32 %call, %call
+  tail call void (...) @h(), !dbg !15
+  ret void, !dbg !16
+}
+
+declare void @h(...)
+declare i32 @g(...)
+declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 4.0.0 (trunk 288665) (llvm/trunk 288725)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "patatino.c", directory: "/home/davide/work/llvm/build-clang/bin")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 4.0.0 (trunk 288665) (llvm/trunk 288725)"}
+!6 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 3, type: !7, isLocal: false, isDefinition: true, scopeLine: 3, isOptimized: false, unit: !0, variables: !2)
+!7 = !DISubroutineType(types: !8)
+!8 = !{null}
+!9 = !DILocation(line: 4, column: 3, scope: !6)
+!10 = !DILocation(line: 5, column: 11, scope: !6)
+!11 = !DILocalVariable(name: "a", scope: !6, file: !1, line: 5, type: !12)
+!12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!13 = !DIExpression()
+!14 = !DILocation(line: 5, column: 7, scope: !6)
+!15 = !DILocation(line: 6, column: 3, scope: !6)
+!16 = !DILocation(line: 7, column: 1, scope: !6)