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, 24 insertions, 17 deletions

diff --git a/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp b/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp
index 989402977b1..7eb23f0b20a 100644
--- a/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp
+++ b/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp
@@ -568,19 +568,23 @@ void ValueEnumerator::dropFunctionFromMetadata(
 
 void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
   // Start by enumerating MD, and then work through its transitive operands in
-  // post-order.
-  SmallVector<std::pair<const MDNode *, bool>, 32> Worklist;
+  // post-order.  This requires a depth-first search.
+  SmallVector<std::pair<const MDNode *, const MDOperand *>, 32> Worklist;
   enumerateMetadataImpl(F, MD, Worklist);
   while (!Worklist.empty()) {
     const MDNode *N = Worklist.back().first;
-    if (!Worklist.back().second) {
-      // On the first visit, add the operands to the worklist.
-      Worklist.back().second = true;
-      unsigned F = MetadataMap.lookup(N).F;
-      for (const Metadata *Op : N->operands())
-        enumerateMetadataImpl(F, Op, Worklist);
+    const MDOperand *&Op = Worklist.back().second; // Be careful of lifetime...
+
+    // Enumerate operands until the worklist changes.  We need to traverse new
+    // nodes before visiting the rest of N's operands.
+    bool DidWorklistChange = false;
+    for (const MDOperand *E = N->op_end(); Op != E;)
+      if (enumerateMetadataImpl(F, *Op++, Worklist)) {
+        DidWorklistChange = true;
+        break;
+      }
+    if (DidWorklistChange)
       continue;
-    }
 
     // All the operands have been visited.  Now assign an ID.
     Worklist.pop_back();
@@ -590,11 +594,11 @@ void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
   }
 }
 
-void ValueEnumerator::enumerateMetadataImpl(
+bool ValueEnumerator::enumerateMetadataImpl(
     unsigned F, const Metadata *MD,
-    SmallVectorImpl<std::pair<const MDNode *, bool>> &Worklist) {
+    SmallVectorImpl<std::pair<const MDNode *, const MDOperand *>> &Worklist) {
   if (!MD)
-    return;
+    return false;
 
   assert(
       (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
@@ -606,13 +610,13 @@ void ValueEnumerator::enumerateMetadataImpl(
     // Already mapped.  If F doesn't match the function tag, drop it.
     if (Entry.hasDifferentFunction(F))
       dropFunctionFromMetadata(*Insertion.first);
-    return;
+    return false;
   }
 
   // MDNodes are handled separately to avoid recursion.
   if (auto *N = dyn_cast<MDNode>(MD)) {
-    Worklist.push_back(std::make_pair(N, false));
-    return;
+    Worklist.push_back(std::make_pair(N, N->op_begin()));
+    return true; // Changed the worklist.
   }
 
   // Save the metadata.
@@ -622,6 +626,8 @@ void ValueEnumerator::enumerateMetadataImpl(
   // Enumerate the constant, if any.
   if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
     EnumerateValue(C->getValue());
+
+  return false;
 }
 
 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
diff --git a/llvm/lib/Bitcode/Writer/ValueEnumerator.h b/llvm/lib/Bitcode/Writer/ValueEnumerator.h
index 98e2df15629..e858c7a5739 100644
--- a/llvm/lib/Bitcode/Writer/ValueEnumerator.h
+++ b/llvm/lib/Bitcode/Writer/ValueEnumerator.h
@@ -34,6 +34,7 @@ class Module;
 class Metadata;
 class LocalAsMetadata;
 class MDNode;
+class MDOperand;
 class NamedMDNode;
 class AttributeSet;
 class ValueSymbolTable;
@@ -245,9 +246,9 @@ private:
   /// function.
   void incorporateFunctionMetadata(const Function &F);
 
-  void enumerateMetadataImpl(
+  bool enumerateMetadataImpl(
       unsigned F, const Metadata *MD,
-      SmallVectorImpl<std::pair<const MDNode *, bool>> &Worklist);
+      SmallVectorImpl<std::pair<const MDNode *, const MDOperand *>> &Worklist);
 
   unsigned getMetadataFunctionID(const Function *F) const;
   void EnumerateMetadata(const Function *F, const Metadata *MD);