Add an index for Module Metadata record in the bitcode

This index record the position for each metadata record in
the bitcode, so that the reader will be able to lazy-load
on demand each individual record.

We also make sure that every abbrev is emitted upfront so
that the block can be skipped while reading.

I don't plan to commit this before having the reader
counterpart, but I figured this can be reviewed mostly
independently.

Recommit r290684 (was reverted in r290686 because a test
was broken) after adding a threshold to avoid emitting
the index when unnecessary (little amount of metadata).
This optimization "hides" a limitation of the ability
to backpatch in the bitstream: we can only backpatch
safely when the position has been flushed. So if we emit
an index for one metadata, it is possible that (part of)
the offset placeholder hasn't been flushed and the backpatch
will fail.

Differential Revision: https://reviews.llvm.org/D28083

llvm-svn: 290690

5 files changed, 29 insertions, 5 deletions

diff --git a/llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll b/llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll
index 6e6ba604235..cefc1f5163f 100644
--- a/llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll
+++ b/llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll
@@ -1,4 +1,5 @@
-; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; RUN: llvm-as <%s -bitcode-mdindex-threshold=0 | llvm-bcanalyzer -dump | FileCheck %s -check-prefix=CHECK  -check-prefix=MDINDEX
+; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s -check-prefix=CHECK
 ; Check that distinct nodes are emitted in post-order to avoid unnecessary
 ; forward references.
 
@@ -17,6 +18,11 @@
 ; CHECK-NEXT:  <DISTINCT_NODE op0=1 op1=3 op2=2/>
 !4 = distinct !{!1, !3, !2}
 
+; Before the named records we emit the index containing the position of the
+; previously emitted records, but only if we have a number of record above
+; a threshold (can be controlled through `-bitcode-mdindex-threshold`).
+; MDINDEX:  <INDEX {{.*}} (offset match)
+
 ; Note: named metadata nodes are not cannot reference null so their operands
 ; are numbered off-by-one.
 ; CHECK-NEXT:  <NAME
diff --git a/llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll b/llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll
index 51701d10c03..0cebcbd1d7d 100644
--- a/llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll
+++ b/llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; RUN: llvm-as <%s -bitcode-mdindex-threshold=0 | llvm-bcanalyzer -dump | FileCheck %s
 ; Check that distinct nodes break uniquing cycles, so that uniqued subgraphs
 ; are always in post-order.
 ;
@@ -22,6 +22,10 @@
 ; CHECK-NEXT:  <NODE op0=2/>
 !3 = !{!2}
 
+; Before the named records we emit the index containing the position of the
+; previously emitted records
+; CHECK-NEXT:   <INDEX {{.*}} (offset match)
+
 ; Note: named metadata nodes are not cannot reference null so their operands
 ; are numbered off-by-one.
 ; CHECK-NEXT:  <NAME
diff --git a/llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll b/llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll
index 1d146817e6b..2d4dc6b0a27 100644
--- a/llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll
+++ b/llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; RUN: llvm-as <%s -bitcode-mdindex-threshold=0 | llvm-bcanalyzer -dump | FileCheck %s
 ; Check that distinct nodes are emitted before uniqued nodes, even if that
 ; breaks post-order traversals.
 
@@ -11,6 +11,10 @@
 ; CHECK-NEXT:  <NODE op0=1/>
 !2 = !{!1}
 
+; Before the named records we emit the index containing the position of the
+; previously emitted records
+; CHECK-NEXT:   <INDEX {{.*}} (offset match)
+
 ; Note: named metadata nodes are not cannot reference null so their operands
 ; are numbered off-by-one.
 ; CHECK-NEXT:  <NAME
diff --git a/llvm/test/Bitcode/mdnodes-in-post-order.ll b/llvm/test/Bitcode/mdnodes-in-post-order.ll
index fbe1c34cf00..3ab90e85821 100644
--- a/llvm/test/Bitcode/mdnodes-in-post-order.ll
+++ b/llvm/test/Bitcode/mdnodes-in-post-order.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as <%s | llvm-bcanalyzer -dump | FileCheck %s
+; RUN: llvm-as <%s -bitcode-mdindex-threshold=0 | 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
@@ -15,6 +15,9 @@
 ; CHECK-NEXT:    'leaf
 ; CHECK-NEXT:  }
 
+; Before the records we emit an offset to the index for the block
+; CHECK-NEXT:   <INDEX_OFFSET
+
 ; The leafs should come first (in either order).
 ; CHECK-NEXT:  <NODE op0=1/>
 ; CHECK-NEXT:  <NODE op0=2/>
@@ -27,6 +30,10 @@
 ; CHECK-NEXT:  <NODE op0=3 op1=5 op2=4/>
 !6 = !{!3, !5, !4}
 
+; Before the named records we emit the index containing the position of the
+; previously emitted records
+; CHECK-NEXT:   <INDEX {{.*}} (offset match)
+
 ; Note: named metadata nodes are not cannot reference null so their operands
 ; are numbered off-by-one.
 ; CHECK-NEXT:  <NAME
diff --git a/llvm/test/Bitcode/metadata-function-blocks.ll b/llvm/test/Bitcode/metadata-function-blocks.ll
index f3e83c5074d..e3c0cc67421 100644
--- a/llvm/test/Bitcode/metadata-function-blocks.ll
+++ b/llvm/test/Bitcode/metadata-function-blocks.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as < %s | llvm-bcanalyzer -dump | FileCheck %s
+; RUN: llvm-as < %s -bitcode-mdindex-threshold=0 | llvm-bcanalyzer -dump | FileCheck %s
 ; Test that metadata only used by a single function is serialized in that
 ; function instead of in the global pool.
 ;
@@ -19,6 +19,9 @@
 ; Each node gets a new number.  Bottom-up traversal of nodes.
 !named = !{!6}
 
+; Before the records we emit an offset to the index for the block
+; CHECK-NEXT:   <INDEX_OFFSET
+
 ; CHECK-NEXT:   <NODE op0=1/>
 !4 = !{!"named"}