BitcodeWriter: Emit metadata in post-order (again)

Emit metadata nodes in post-order.  The iterative algorithm from r266709
failed to maintain this property.  After understanding my mistake, it
wasn't too hard to write a test with llvm-bcanalyzer (and I've actually
made this change once before: see r220340).

This also reverts the "noisy" testcase change from r266709.  That should
have been more of a red flag :/.

Note: The same bug crept into the ValueMapper in r265456.  I'm still
working on the fix.

llvm-svn: 266947

2 files changed, 40 insertions, 6 deletions

diff --git a/llvm/test/Bitcode/mdnodes-in-post-order.ll b/llvm/test/Bitcode/mdnodes-in-post-order.ll
new file mode 100644
index 00000000000..fbe1c34cf00
--- /dev/null
+++ b/llvm/test/Bitcode/mdnodes-in-post-order.ll
@@ -0,0 +1,34 @@
+; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; Check that nodes are emitted in post-order to minimize the need for temporary
+; nodes.  The graph structure is designed to foil naive implementations of
+; iteratitive post-order traersals: the leaves, !3 and !4, are reachable from
+; the entry node, !6, as well as from !5.  There is one leaf on either side to
+; be sure it tickles bugs whether operands are visited forward or reverse.
+
+; Nodes in this testcase are numbered to match how they are referenced in
+; bitcode.  !3 is referenced as opN=3.
+
+; We don't care about the order of the strings (or of !3 and !4).  Let's just
+; make sure the strings are first and make it clear that there are two of them.
+; CHECK:       <STRINGS {{.*}} num-strings = 2 {
+; CHECK-NEXT:    'leaf
+; CHECK-NEXT:    'leaf
+; CHECK-NEXT:  }
+
+; The leafs should come first (in either order).
+; CHECK-NEXT:  <NODE op0=1/>
+; CHECK-NEXT:  <NODE op0=2/>
+!3 = !{!"leaf3"}
+!4 = !{!"leaf4"}
+
+; CHECK-NEXT:  <NODE op0=3 op1=4/>
+!5 = !{!3, !4}
+
+; CHECK-NEXT:  <NODE op0=3 op1=5 op2=4/>
+!6 = !{!3, !5, !4}
+
+; 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=5/>
+!named = !{!6}
diff --git a/llvm/test/Bitcode/metadata-function-blocks.ll b/llvm/test/Bitcode/metadata-function-blocks.ll
index 7b335f73313..f3e83c5074d 100644
--- a/llvm/test/Bitcode/metadata-function-blocks.ll
+++ b/llvm/test/Bitcode/metadata-function-blocks.ll
@@ -19,14 +19,14 @@
 ; Each node gets a new number.  Bottom-up traversal of nodes.
 !named = !{!6}
 
-; CHECK-NEXT:   <NODE op0=2/>
-!4 = !{!"named and foo"}
-
 ; CHECK-NEXT:   <NODE op0=1/>
-!5 = !{!"named"}
+!4 = !{!"named"}
+
+; CHECK-NEXT:   <NODE op0=2/>
+!5 = !{!"named and foo"}
 
-; CHECK-NEXT:   <NODE op0=1 op1=5 op2=4/>
-!6 = !{!"named", !5, !4}
+; CHECK-NEXT:   <NODE op0=1 op1=4 op2=5/>
+!6 = !{!"named", !4, !5}
 
 ; CHECK-NEXT:   <NODE op0=3/>
 !7 = !{!"foo and bar"}