BitcodeWriter: Emit distinct nodes before uniqued nodes

When an operand of a distinct node hasn't been read yet, the reader can
use a DistinctMDOperandPlaceholder.  This is much cheaper than forward
referencing from a uniqued node.  Change
ValueEnumerator::organizeMetadata to partition distinct nodes and
uniqued nodes to reduce the overhead of cycles broken by distinct nodes.

Mehdi measured this for me; this removes most of the RAUW from the
importing step of -flto=thin, even after a WIP patch that removes
string-based DITypeRefs (introducing many more cycles to the metadata
graph).

llvm-svn: 267276

1 files changed, 18 insertions, 0 deletions

diff --git a/llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll b/llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll
new file mode 100644
index 00000000000..1d146817e6b
--- /dev/null
+++ b/llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll
@@ -0,0 +1,18 @@
+; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; Check that distinct nodes are emitted before uniqued nodes, even if that
+; breaks post-order traversals.
+
+; Nodes in this testcase are numbered to match how they are referenced in
+; bitcode.  !1 is referenced as opN=1.
+
+; CHECK:       <DISTINCT_NODE op0=2/>
+!1 = distinct !{!2}
+
+; CHECK-NEXT:  <NODE op0=1/>
+!2 = !{!1}
+
+; 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}