2 files changed, 53 insertions, 0 deletions
diff --git a/llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll b/llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll
new file mode 100644
index 00000000000..6e6ba604235
--- /dev/null
+++ b/llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll
@@ -0,0 +1,24 @@
+; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; Check that distinct nodes are emitted in post-order to avoid unnecessary
+; forward references.
+
+; Nodes in this testcase are numbered to match how they are referenced in
+; bitcode.  !3 is referenced as opN=3.
+
+; The leafs should come first (in either order).
+; CHECK:       <DISTINCT_NODE/>
+; CHECK-NEXT:  <DISTINCT_NODE/>
+!1 = distinct !{}
+!2 = distinct !{}
+
+; CHECK-NEXT:  <DISTINCT_NODE op0=1 op1=2/>
+!3 = distinct !{!1, !2}
+
+; CHECK-NEXT:  <DISTINCT_NODE op0=1 op1=3 op2=2/>
+!4 = distinct !{!1, !3, !2}
+
+; Note: named metadata nodes are not cannot reference null so their operands
+; are numbered off-by-one.
+; CHECK-NEXT:  <NAME
+; CHECK-NEXT:  <NAMED_NODE op0=3/>
+!named = !{!4}
diff --git a/llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll b/llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll
new file mode 100644
index 00000000000..51701d10c03
--- /dev/null
+++ b/llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll
@@ -0,0 +1,29 @@
+; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; Check that distinct nodes break uniquing cycles, so that uniqued subgraphs
+; are always in post-order.
+;
+; It may not be immediately obvious why this is an interesting graph.  There
+; are three nodes in a cycle, and one of them (!1) is distinct.  Because the
+; entry point is !2, a naive post-order traversal would give !3, !1, !2; but
+; this means when !3 is parsed the reader will need a forward reference for !2.
+; Forward references for uniqued node operands are expensive, whereas they're
+; cheap for distinct node operands.  If the distinct node is emitted first, the
+; uniqued nodes don't need any forward references at all.
+
+; Nodes in this testcase are numbered to match how they are referenced in
+; bitcode.  !3 is referenced as opN=3.
+
+; CHECK:       <DISTINCT_NODE op0=3/>
+!1 = distinct !{!3}
+
+; CHECK-NEXT:  <NODE op0=1/>
+!2 = !{!1}
+
+; CHECK-NEXT:  <NODE op0=2/>
+!3 = !{!2}
+
+; Note: named metadata nodes are not cannot reference null so their operands
+; are numbered off-by-one.
+; CHECK-NEXT:  <NAME
+; CHECK-NEXT:  <NAMED_NODE op0=1/>
+!named = !{!2}