Handle value uses wrapped in metadata for the use-list order

[dstenb]

Summary

When generating the use-list order, also consider value uses that are
operands which are wrapped in metadata; e.g. llvm.dbg.value operands.

This fixes PR36778. The test case is based on the reproducer from that
report.

[dstenb]

I thought I had built up some confidence for this after a night of fuzz testing. However, first after creating this review I encountered a crash in the LL parser, which happened due to the use-list order containing too many elements with this patch.

For my off-tree target this happens for a i16* null, which have the following uses:

call void @llvm.dbg.value(metadata i16* null, metadata !16, metadata !DIExpression()), !dbg !17 
call void @llvm.dbg.value(metadata i16* null, metadata !16, metadata !DIExpression()), !dbg !17 
call void @llvm.dbg.value(metadata i16* null, metadata !16, metadata !DIExpression()), !dbg !17 
%_tmp4 = call i16 bitcast (i16 (...) addrspace(40)* @fn2 to i16 (i16*, i16*, i16*) addrspace(40)*)(i16* null, i16* null, i16* null), !dbg !18

error: wrong number of indexes, expected 3

Maybe you see something obviously bad with the approach in this patch? In the meanwhile, I'll investigate the crash.

I'm sorry for the inconvenience!

[dstenb]

In the previous revision I had overlooked two things in the writers:

1. The code did not look for uses in metadata operands in predictUseListOrder(). This resulted in the use-list order being emitted too early (which caused the crash in my previous revision), or not at all if there were no non-metadata uses of the constant.
2. For bitcode files, constants used in metadata are emitted as module-level constants. I have had to change the order in orderModule() to account for that.

I have updated the test case to reflect those changes.

Also, I had missed to look at metadata operands when changing use-lists in verify-uselistorder, meaning that we would not fuzz test the use-list order for constants where we only have uses in metadata operands.

Also, as a minor cleanup, I removed the comment shown below from AsmWriter's orderModule(). I don't think the comment is correct, as things are ordered differently in assembly and bitcode, and I suspect that it was simply copy-pasted from the BitcodeWriter's orderModule() implementation.

// This needs to match the order used by ValueEnumerator::ValueEnumerator()
// and ValueEnumerator::incorporateFunction().

[dexonsmith]

test/Assembler/metadata-use-uselistorder.ll

5–6 ↗

(On Diff #173153)

Does this only cause problems for constants (like i64 0), or also for use lists of locals and globals?

The reason I ask: we *should* make it impossible for most constants to rely on use-list order, and then stop storing use-lists for them (in either bitcode or textual IR). When we get there, should we delete this test and the new code you've added? Or will it still be relevant for other values?

[dstenb]

test/Assembler/metadata-use-uselistorder.ll

5–6 ↗

(On Diff #173153)

Oh, okay! Do you know if someone is actively working on that at the moment?

The metadata operands can affect the use lists of globals in cases where they contain constant expressions using globals.

For example, the following file:

typedef struct { int a; int b; int c; } S;

extern void work(int *);

S g;

void foo() {
  int *local1 = &g.a;
}

void bar() {
  int *local2 = &g.b;
  work(local2);
  S l = {1, 2, 3};
  g = l;
}

compiled using the following, slightly contrived, command line:

$ clang -O0 -Xclang -disable-O0-optnone -g -S -emit-llvm di.c -o - | opt -S -instcombine -o di.ll
$ grep '@g' di.ll
@g = common dso_local global %struct.S zeroinitializer, align 4, !dbg !0
  call void @llvm.dbg.value(metadata i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 0), metadata !20, metadata !DIExpression()), !dbg !22
  call void @llvm.dbg.value(metadata i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 1), metadata !25, metadata !DIExpression()), !dbg !26
  call void @llvm.dbg.value(metadata i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1), metadata !25, metadata !DIExpression()), !dbg !26
  call void @work(i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1)) #4, !dbg !27
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 bitcast (%struct.S* @g to i8*), i8* align 4 bitcast (%struct.S* @bar.l to i8*), i64 12, i1 false), !dbg !28

gives without this patch:

$ verify-uselistorder di.ll -debug 2>&1 | grep -A10 fail:
 - fail: user mismatch: ID = 0
 - LHS value = @g = common dso_local global %struct.S zeroinitializer, align 4, !dbg !0
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 0)
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 1)
   => use: op = 0, user-id = 27, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1)
   => use: op = 0, user-id = 28, user = i8* bitcast (%struct.S* @g to i8*)
 - RHS value = @g = common dso_local global %struct.S zeroinitializer, align 4, !dbg !0
   => use: op = 0, user-id = 28, user = i8* bitcast (%struct.S* @g to i8*)
   => use: op = 0, user-id = 27, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1)
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 1)
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 0)

So, unless I have misunderstood something, I assume that this will code be relevant even after that.

A run of verify-uselistorder on the attached test case does unfortunately not bail out for @global_arr (even if it were changed so that it does not trigger for i64 0), due to there only being one mapped user of the global (the GEP in the load). I can update the patch so that the verification fails for the global, and update the comment in the test case so that it just does not refer to the i64 0.

[dstenb]

Add another non-metadata user of @global_arr to the test case so that the verification of the global's use-list order fails when running without this patch. Also generalize the comment in the test case.

[dstenb]

Ping.

[dexonsmith]

I totally lost track of this :/.

The patch looks correct, thanks very much for tracking this down. This LGTM if you add an explanation to the testcase of exactly what it’s testing (I worry it’s not obvious for someone trying to update the test later).

[dstenb]

Rebase, and update comment in test case.

[dstenb]

In D53758#2336719, @dexonsmith wrote:

I totally lost track of this :/.

The patch looks correct, thanks very much for tracking this down. This LGTM if you add an explanation to the testcase of exactly what it’s testing (I worry it’s not obvious for someone trying to update the test later).

Me too! Thanks a lot for reviewing this!

I have added an explanation to the test case.

llvm/lib/Bitcode/Writer/ValueEnumerator.cpp

void index(const Value *V) {
     // Explicitly sequence get-size and insert-value operations to avoid UB.
     unsigned ID = IDs.size() + 1;
     IDs[V].first = ID;
   }
 };
 
 } // end anonymous namespace
 
+/// Look for a value that might be wrapped as metadata, e.g. a value in a
+/// metadata operand. Returns nullptr for a non-wrapped input value if
+/// OnlyWrapped is true, or it returns the input value as-is if false.
+static const Value *skipMetadataWrapper(const Value *V, bool OnlyWrapped) {
+  if (const auto *MAV = dyn_cast<MetadataAsValue>(V))
+    if (const auto *VAM = dyn_cast<ValueAsMetadata>(MAV->getMetadata()))
+      return VAM->getValue();
+  return OnlyWrapped ? nullptr : V;
+}
+
 static void orderValue(const Value *V, OrderMap &OM) {
   if (OM.lookup(V).first)
     return;
 
   if (const Constant *C = dyn_cast<Constant>(V)) {
     if (C->getNumOperands() && !isa<GlobalValue>(C)) {
       for (const Value *Op : C->operands())
         if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
static OrderMap orderModule(const Module &M) {
   for (const GlobalIFunc &I : M.ifuncs())
     if (!isa<GlobalValue>(I.getResolver()))
       orderValue(I.getResolver(), OM);
   for (const Function &F : M) {
     for (const Use &U : F.operands())
       if (!isa<GlobalValue>(U.get()))
         orderValue(U.get(), OM);
   }
+
+  // As constants used in metadata operands are emitted as module-level
+  // constants, we must order them before other operands. Also, we must order
+  // these before global values, as these will be read before setting the
+  // global values' initializers. The latter matters for constants which have
+  // uses towards other constants that are used as initializers.
+  for (const Function &F : M) {
+    if (F.isDeclaration())
+      continue;
+    for (const BasicBlock &BB : F)
+      for (const Instruction &I : BB)
+        for (const Value *V : I.operands()) {
+          if (const Value *Op = skipMetadataWrapper(V, true)) {
+            if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
+                isa<InlineAsm>(*Op))
+              orderValue(Op, OM);
+          }
+        }
+  }
   OM.LastGlobalConstantID = OM.size();
 
   // Initializers of GlobalValues are processed in
   // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
   // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
   // by giving IDs in reverse order.
   //
   // Since GlobalValues never reference each other directly (just through

llvm/lib/IR/AsmWriter.cpp

void index(const Value *V) {
     // Explicitly sequence get-size and insert-value operations to avoid UB.
     unsigned ID = IDs.size() + 1;
     IDs[V].first = ID;
   }
 };
 
 } // end anonymous namespace
 
+/// Look for a value that might be wrapped as metadata, e.g. a value in a
+/// metadata operand. Returns the input value as-is if it is not wrapped.
+static const Value *skipMetadataWrapper(const Value *V) {
+  if (const auto *MAV = dyn_cast<MetadataAsValue>(V))
+    if (const auto *VAM = dyn_cast<ValueAsMetadata>(MAV->getMetadata()))
+      return VAM->getValue();
+  return V;
+}
+
 static void orderValue(const Value *V, OrderMap &OM) {
   if (OM.lookup(V).first)
     return;
 
   if (const Constant *C = dyn_cast<Constant>(V))
     if (C->getNumOperands() && !isa<GlobalValue>(C))
       for (const Value *Op : C->operands())
         if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
           orderValue(Op, OM);
 
   // Note: we cannot cache this lookup above, since inserting into the map
   // changes the map's size, and thus affects the other IDs.
   OM.index(V);
 }
 
 static OrderMap orderModule(const Module *M) {
-  // This needs to match the order used by ValueEnumerator::ValueEnumerator()
-  // and ValueEnumerator::incorporateFunction().
   OrderMap OM;
 
   for (const GlobalVariable &G : M->globals()) {
     if (G.hasInitializer())
       if (!isa<GlobalValue>(G.getInitializer()))
         orderValue(G.getInitializer(), OM);
     orderValue(&G, OM);
   }
for (const Function &F : *M) {
     if (F.isDeclaration())
       continue;
 
     for (const Argument &A : F.args())
       orderValue(&A, OM);
     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()) {
+          Op = skipMetadataWrapper(Op);
           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
               isa<InlineAsm>(*Op))
             orderValue(Op, OM);
+        }
         orderValue(&I, OM);
       }
     }
   }
   return OM;
 }
 
 static void predictValueUseListOrderImpl(const Value *V, const Function *F,
for (const Function &F : make_range(M->rbegin(), M->rend())) {
     if (F.isDeclaration())
       continue;
     for (const BasicBlock &BB : F)
       predictValueUseListOrder(&BB, &F, OM, Stack);
     for (const Argument &A : F.args())
       predictValueUseListOrder(&A, &F, OM, Stack);
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)
-        for (const Value *Op : I.operands())
+        for (const Value *Op : I.operands()) {
+          Op = skipMetadataWrapper(Op);
           if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
             predictValueUseListOrder(Op, &F, OM, Stack);
+        }
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)
         predictValueUseListOrder(&I, &F, OM, Stack);
   }
 
   // Visit globals last.
   for (const GlobalVariable &G : M->globals())
     predictValueUseListOrder(&G, nullptr, OM, Stack);

llvm/test/Assembler/metadata-use-uselistorder.ll

+; RUN: verify-uselistorder %s
+
+; Reproducer for PR36778.
+
+; Verify that uses in metadata operands are considered when generating the
+; use-list order. In this case the use-list order for @global_arr was not
+; correctly preserved due to the uses in the dbg.value contant expressions not
+; being considered, since they are wrapped in metadata.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@global = local_unnamed_addr global i64 0, align 8
+@global_arr = common local_unnamed_addr global [10 x i64] zeroinitializer, align 16
+
+define void @foo() local_unnamed_addr !dbg !6 {
+entry:
+  %0 = load i64, i64* getelementptr inbounds ([10 x i64], [10 x i64]* @global_arr, i64 0, i64 4), align 16
+  call void @llvm.dbg.value(metadata i64* getelementptr inbounds ([10 x i64], [10 x i64]* @global_arr, i64 0, i64 5), metadata !10, metadata !DIExpression()), !dbg !13
+  %1 = load i64, i64* getelementptr inbounds ([10 x i64], [10 x i64]* @global_arr, i64 0, i64 6), align 16
+  call void @llvm.dbg.value(metadata i64* getelementptr inbounds ([10 x i64], [10 x i64]* @global_arr, i64 0, i64 6), metadata !10, metadata !DIExpression()), !dbg !14
+  ret void
+}
+
+define void @bar() local_unnamed_addr !dbg !15 {
+entry:
+  call void @llvm.dbg.value(metadata i64* getelementptr inbounds ([10 x i64], [10 x i64]* @global_arr, i64 0, i64 7), metadata !17, metadata !DIExpression()), !dbg !18
+  ret void
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+attributes #0 = { 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 8.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, globals: !2, nameTableKind: None)
+!1 = !DIFile(filename: "uses.c", directory: "/")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 8.0.0"}
+!6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 6, type: !7, isLocal: false, isDefinition: true, scopeLine: 6, isOptimized: true, unit: !0, retainedNodes: !9)
+!7 = !DISubroutineType(types: !8)
+!8 = !{null}
+!9 = !{!10}
+!10 = !DILocalVariable(name: "local1", scope: !6, file: !1, line: 7, type: !11)
+!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !12, size: 64)
+!12 = !DIBasicType(name: "long int", size: 64, encoding: DW_ATE_signed)
+!13 = !DILocation(line: 8, column: 8, scope: !6)
+!14 = !DILocation(line: 7, column: 9, scope: !6)
+!15 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 12, type: !7, isLocal: false, isDefinition: true, scopeLine: 12, isOptimized: true, unit: !0, retainedNodes: !16)
+!16 = !{!17}
+!17 = !DILocalVariable(name: "local2", scope: !15, file: !1, line: 13, type: !11)
+!18 = !DILocation(line: 14, column: 1, scope: !15)

llvm/tools/verify-uselistorder/verify-uselistorder.cpp

for (const BasicBlock &BB : F)
       map(&BB);
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)
         map(&I);
 
     // 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);
         }
   }
+}
 
 void ValueMapping::map(const Value *V) {
   if (IDs.lookup(V))
     return;
 
   if (auto *C = dyn_cast<Constant>(V))
     if (!isa<GlobalValue>(C))
       for (const Value *Op : C->operands())
for (BasicBlock &BB : F)
       changeValueUseList(&BB);
     for (BasicBlock &BB : F)
       for (Instruction &I : BB)
         changeValueUseList(&I);
 
     // Constants used by instructions.
     for (BasicBlock &BB : F)
       for (Instruction &I : BB)
-        for (Value *Op : I.operands())
+        for (Value *Op : I.operands()) {
+          // Look through a metadata wrapper.
+          if (auto *MAV = dyn_cast<MetadataAsValue>(Op))
+            if (auto *VAM = dyn_cast<ValueAsMetadata>(MAV->getMetadata()))
+              Op = VAM->getValue();
           if ((isa<Constant>(Op) && !isa<GlobalValue>(*Op)) ||
               isa<InlineAsm>(Op))
             changeValueUseList(Op);
         }
+  }
 
   if (verifyModule(M, &errs()))
     report_fatal_error("verification failed");
 }
 
 static void shuffleUseLists(Module &M, unsigned SeedOffset) {
   std::minstd_rand0 Gen(std::minstd_rand0::default_seed + SeedOffset);
   DenseSet<Value *> Seen;