Index: lib/Bitcode/Writer/ValueEnumerator.cpp
===================================================================
--- lib/Bitcode/Writer/ValueEnumerator.cpp
+++ lib/Bitcode/Writer/ValueEnumerator.cpp
@@ -157,10 +157,16 @@
       orderValue(&A, OM);
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)
-        for (const Value *Op : I.operands())
+        for (const Value *Op : I.operands()) {
+          // Look through a metadata wrapper.
+          if (const auto *MAV = dyn_cast<MetadataAsValue>(Op))
+            if (const auto *VAM = dyn_cast<ValueAsMetadata>(MAV->getMetadata()))
+              Op = VAM->getValue();
+
           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
               isa<InlineAsm>(*Op))
             orderValue(Op, OM);
+        }
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)
         orderValue(&I, OM);
Index: lib/IR/AsmWriter.cpp
===================================================================
--- lib/IR/AsmWriter.cpp
+++ lib/IR/AsmWriter.cpp
@@ -169,10 +169,16 @@
     for (const BasicBlock &BB : F) {
       orderValue(&BB, OM);
       for (const Instruction &I : BB) {
-        for (const Value *Op : I.operands())
+        for (const Value *Op : I.operands()) {
+          // Look through a metadata wrapper.
+          if (const auto *MAV = dyn_cast<MetadataAsValue>(Op))
+            if (const auto *VAM = dyn_cast<ValueAsMetadata>(MAV->getMetadata()))
+              Op = VAM->getValue();
+
           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
               isa<InlineAsm>(*Op))
             orderValue(Op, OM);
+        }
         orderValue(&I, OM);
       }
     }
Index: test/Assembler/metadata-wrapped-use-uselistorder.ll
===================================================================
--- /dev/null
+++ test/Assembler/metadata-wrapped-use-uselistorder.ll
@@ -0,0 +1,49 @@
+; RUN: verify-uselistorder %s
+
+; Reproducer for PR36778.
+
+; Verify that the uses of i64 0 in the llvm.dbg.value operand are considered
+; when generating the use-list order.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str.2 = private unnamed_addr constant [4 x i8] c"foo\00", align 1
+@.str.3 = private unnamed_addr constant [3 x i8] c"%s\00", align 1
+
+; Function Attrs: nounwind uwtable
+define i32 @foo() local_unnamed_addr #0 !dbg !6 {
+  call void @llvm.dbg.value(metadata i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0), metadata !10, metadata !DIExpression()), !dbg !14
+  %1 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.3, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0))
+  ret i32 0
+}
+
+; Function Attrs: nounwind
+declare i32 @printf(i8* nocapture readonly, ...) local_unnamed_addr #1
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #2
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+attributes #2 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0 (tags/RELEASE_600/final)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, globals: !2)
+!1 = !DIFile(filename: "test.c", directory: "/")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 6.0.0 (tags/RELEASE_600/final)"}
+!6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 2, type: !7, isLocal: false, isDefinition: true, scopeLine: 2, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !9)
+!7 = !DISubroutineType(types: !8)
+!8 = !{null}
+!9 = !{!10}
+!10 = !DILocalVariable(name: "foo", scope: !6, file: !1, line: 7, type: !11)
+!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !12, size: 64)
+!12 = !DIDerivedType(tag: DW_TAG_const_type, baseType: !13)
+!13 = !DIBasicType(name: "char", size: 8, encoding: DW_ATE_signed_char)
+!14 = !DILocation(line: 7, column: 14, scope: !6)
Index: tools/verify-uselistorder/verify-uselistorder.cpp
===================================================================
--- tools/verify-uselistorder/verify-uselistorder.cpp
+++ tools/verify-uselistorder/verify-uselistorder.cpp
@@ -225,10 +225,16 @@
     // Constants used by instructions.
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)
-        for (const Value *Op : I.operands())
+        for (const Value *Op : I.operands()) {
+          // Look through a metadata wrapper.
+          if (const auto *MAV = dyn_cast<MetadataAsValue>(Op))
+            if (const auto *VAM = dyn_cast<ValueAsMetadata>(MAV->getMetadata()))
+              Op = VAM->getValue();
+
           if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
               isa<InlineAsm>(Op))
             map(Op);
+        }
   }
 }