Add an index for Module Metadata record in the bitcode

[mehdi_amini]

Summary

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.

[mehdi_amini]

Minor fixup

[tejohnson]

I assume D28113 is dependent on this? Code changes look fine (couple questions and comment nits below). Looks like this will be worth it from a time improvement standpoint, but what is the size overhead?

llvm/include/llvm/Bitcode/BitstreamWriter.h

287

This change seems unnecessary

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

1902

What change necessitated increasing this from 3 to 4 (I forget exactly how this is determined - is it the number of codes or the number of abbrevs?).

1950

Fix the FIXME? Also I assume it should be "comment the 64"?

llvm/test/Bitcode/mdnodes-in-post-order.ll

33

Isn't this emitting an offset to the metadata records, not to the index? Ditto for comments for INDEX block in other tests.

[mehdi_amini]

In D28083#631478, @tejohnson wrote:

I assume D28113 is dependent on this?

Yes seems like I didn't correctly update the dependencies, will do.

Looks like this will be worth it from a time improvement standpoint, but what is the size overhead?

Good question, I forgot to include this, here are some data from my build directory right now:

Index size (bits): 22120908
Total size (bits): 977531136
Relative size of the index: 2.26%

Details in CSV, FYI:

# Filename;{size of the index record in bits;{size of the file in bits;percentage of the index to the file size;
lib/Demangle/CMakeFiles/LLVMDemangle.dir/ItaniumDemangle.cpp.o,74122,22948096,.3229
lib/Support/CMakeFiles/LLVMSupport.dir/Allocator.cpp.o,33742,816896,4.1305
lib/Support/CMakeFiles/LLVMSupport.dir/APFloat.cpp.o,89140,7893504,1.1292
lib/Support/CMakeFiles/LLVMSupport.dir/APInt.cpp.o,74830,9255680,.8084
lib/Support/CMakeFiles/LLVMSupport.dir/APSInt.cpp.o,47032,1184128,3.9718
lib/Support/CMakeFiles/LLVMSupport.dir/ARMBuildAttrs.cpp.o,26614,685184,3.8842
lib/Support/CMakeFiles/LLVMSupport.dir/ARMWinEH.cpp.o,15076,278400,5.4152
lib/Support/CMakeFiles/LLVMSupport.dir/Atomic.cpp.o,5344,97024,5.5079
lib/Support/CMakeFiles/LLVMSupport.dir/BlockFrequency.cpp.o,35140,819328,4.2888
lib/Support/CMakeFiles/LLVMSupport.dir/BranchProbability.cpp.o,48004,1193600,4.0217
lib/Support/CMakeFiles/LLVMSupport.dir/CachePruning.cpp.o,69898,2595328,2.6932
lib/Support/CMakeFiles/LLVMSupport.dir/Chrono.cpp.o,48874,1179392,4.1439
lib/Support/CMakeFiles/LLVMSupport.dir/circular_raw_ostream.cpp.o,34402,839296,4.0989
lib/Support/CMakeFiles/LLVMSupport.dir/COM.cpp.o,436,34048,1.2805
lib/Support/CMakeFiles/LLVMSupport.dir/CommandLine.cpp.o,194878,11887488,1.6393
lib/Support/CMakeFiles/LLVMSupport.dir/Compression.cpp.o,32704,798464,4.0958
lib/Support/CMakeFiles/LLVMSupport.dir/ConvertUTF.cpp.o,11938,455552,2.6205
lib/Support/CMakeFiles/LLVMSupport.dir/ConvertUTFWrapper.cpp.o,57508,1851264,3.1064
lib/Support/CMakeFiles/LLVMSupport.dir/CrashRecoveryContext.cpp.o,23134,631424,3.6637
lib/Support/CMakeFiles/LLVMSupport.dir/DAGDeltaAlgorithm.cpp.o,110440,5489664,2.0117
lib/Support/CMakeFiles/LLVMSupport.dir/DataExtractor.cpp.o,31528,947328,3.3280
lib/Support/CMakeFiles/LLVMSupport.dir/Debug.cpp.o,50338,1475072,3.4125
lib/Support/CMakeFiles/LLVMSupport.dir/DeltaAlgorithm.cpp.o,57418,3345024,1.7165
lib/Support/CMakeFiles/LLVMSupport.dir/Dwarf.cpp.o,39796,6776192,.5872
lib/Support/CMakeFiles/LLVMSupport.dir/DynamicLibrary.cpp.o,45778,1497600,3.0567
lib/Support/CMakeFiles/LLVMSupport.dir/Errno.cpp.o,26200,591616,4.4285
lib/Support/CMakeFiles/LLVMSupport.dir/Error.cpp.o,69232,2737792,2.5287
lib/Support/CMakeFiles/LLVMSupport.dir/ErrorHandling.cpp.o,40792,1163520,3.5059
lib/Support/CMakeFiles/LLVMSupport.dir/FileOutputBuffer.cpp.o,47998,1425664,3.3667
lib/Support/CMakeFiles/LLVMSupport.dir/FileUtilities.cpp.o,43054,1372544,3.1368
lib/Support/CMakeFiles/LLVMSupport.dir/FoldingSet.cpp.o,46942,1803520,2.6027
lib/Support/CMakeFiles/LLVMSupport.dir/FormattedStream.cpp.o,35944,942208,3.8148
lib/Support/CMakeFiles/LLVMSupport.dir/FormatVariadic.cpp.o,59356,1942784,3.0552
lib/Support/CMakeFiles/LLVMSupport.dir/GlobPattern.cpp.o,64600,2006784,3.2190
lib/Support/CMakeFiles/LLVMSupport.dir/GraphWriter.cpp.o,71104,2771328,2.5657
lib/Support/CMakeFiles/LLVMSupport.dir/Hashing.cpp.o,14782,212992,6.9401
lib/Support/CMakeFiles/LLVMSupport.dir/Host.cpp.o,46828,1657344,2.8254
lib/Support/CMakeFiles/LLVMSupport.dir/IntEqClasses.cpp.o,12502,303744,4.1159
lib/Support/CMakeFiles/LLVMSupport.dir/IntervalMap.cpp.o,22486,585856,3.8381
lib/Support/CMakeFiles/LLVMSupport.dir/IntrusiveRefCntPtr.cpp.o,1594,59776,2.6666
lib/Support/CMakeFiles/LLVMSupport.dir/JamCRC.cpp.o,14830,259200,5.7214
lib/Support/CMakeFiles/LLVMSupport.dir/LEB128.cpp.o,14716,219520,6.7037
lib/Support/CMakeFiles/LLVMSupport.dir/LineIterator.cpp.o,36322,837120,4.3389
lib/Support/CMakeFiles/LLVMSupport.dir/Locale.cpp.o,10840,567424,1.9103
lib/Support/CMakeFiles/LLVMSupport.dir/LockFileManager.cpp.o,56734,2227968,2.5464
lib/Support/CMakeFiles/LLVMSupport.dir/ManagedStatic.cpp.o,11806,281728,4.1905
lib/Support/CMakeFiles/LLVMSupport.dir/MathExtras.cpp.o,8152,112768,7.2290
lib/Support/CMakeFiles/LLVMSupport.dir/MD5.cpp.o,48514,1527168,3.1767
lib/Support/CMakeFiles/LLVMSupport.dir/Memory.cpp.o,30940,900224,3.4369
lib/Support/CMakeFiles/LLVMSupport.dir/MemoryBuffer.cpp.o,52810,1786624,2.9558
lib/Support/CMakeFiles/LLVMSupport.dir/Mutex.cpp.o,5788,136576,4.2379
lib/Support/CMakeFiles/LLVMSupport.dir/NativeFormatting.cpp.o,51364,1532544,3.3515
lib/Support/CMakeFiles/LLVMSupport.dir/Options.cpp.o,57094,1590912,3.5887
lib/Support/CMakeFiles/LLVMSupport.dir/Path.cpp.o,71602,4444800,1.6109
lib/Support/CMakeFiles/LLVMSupport.dir/PluginLoader.cpp.o,51592,1534464,3.3622
lib/Support/CMakeFiles/LLVMSupport.dir/PrettyStackTrace.cpp.o,43174,1344768,3.2105
lib/Support/CMakeFiles/LLVMSupport.dir/Process.cpp.o,56242,1899648,2.9606
lib/Support/CMakeFiles/LLVMSupport.dir/Program.cpp.o,47494,2131328,2.2283
lib/Support/CMakeFiles/LLVMSupport.dir/RandomNumberGenerator.cpp.o,69268,2018432,3.4317
lib/Support/CMakeFiles/LLVMSupport.dir/raw_os_ostream.cpp.o,42568,996608,4.2712
lib/Support/CMakeFiles/LLVMSupport.dir/raw_ostream.cpp.o,71854,2636928,2.7249
lib/Support/CMakeFiles/LLVMSupport.dir/regcomp.c.o,3310,1124096,.2944
lib/Support/CMakeFiles/LLVMSupport.dir/regerror.c.o,298,87168,.3418
lib/Support/CMakeFiles/LLVMSupport.dir/Regex.cpp.o,39262,1363840,2.8787
lib/Support/CMakeFiles/LLVMSupport.dir/regexec.c.o,2452,774784,.3164
lib/Support/CMakeFiles/LLVMSupport.dir/regfree.c.o,148,46208,.3202
lib/Support/CMakeFiles/LLVMSupport.dir/regstrlcpy.c.o,106,29824,.3554
lib/Support/CMakeFiles/LLVMSupport.dir/RWMutex.cpp.o,5608,129152,4.3421
lib/Support/CMakeFiles/LLVMSupport.dir/ScaledNumber.cpp.o,55624,2002816,2.7772
lib/Support/CMakeFiles/LLVMSupport.dir/ScopedPrinter.cpp.o,48154,1414656,3.4039
lib/Support/CMakeFiles/LLVMSupport.dir/SearchForAddressOfSpecialSymbol.cpp.o,106,20480,.5175
lib/Support/CMakeFiles/LLVMSupport.dir/SHA1.cpp.o,38410,1520000,2.5269
lib/Support/CMakeFiles/LLVMSupport.dir/Signals.cpp.o,102994,3863168,2.6660
lib/Support/CMakeFiles/LLVMSupport.dir/SmallPtrSet.cpp.o,17902,553984,3.2315
lib/Support/CMakeFiles/LLVMSupport.dir/SmallVector.cpp.o,8134,142336,5.7146
lib/Support/CMakeFiles/LLVMSupport.dir/SourceMgr.cpp.o,96646,5161344,1.8724
lib/Support/CMakeFiles/LLVMSupport.dir/SpecialCaseList.cpp.o,107866,4198528,2.5691
lib/Support/CMakeFiles/LLVMSupport.dir/Statistic.cpp.o,91750,3406464,2.6934
lib/Support/CMakeFiles/LLVMSupport.dir/StringExtras.cpp.o,32344,807168,4.0070
lib/Support/CMakeFiles/LLVMSupport.dir/StringMap.cpp.o,31096,828544,3.7530
lib/Support/CMakeFiles/LLVMSupport.dir/StringPool.cpp.o,34456,846464,4.0705
lib/Support/CMakeFiles/LLVMSupport.dir/StringRef.cpp.o,46240,2299648,2.0107
lib/Support/CMakeFiles/LLVMSupport.dir/StringSaver.cpp.o,40774,980864,4.1569
lib/Support/CMakeFiles/LLVMSupport.dir/SystemUtils.cpp.o,33364,755072,4.4186
lib/Support/CMakeFiles/LLVMSupport.dir/TargetParser.cpp.o,50218,4640128,1.0822
lib/Support/CMakeFiles/LLVMSupport.dir/TargetRegistry.cpp.o,67798,2173952,3.1186
lib/Support/CMakeFiles/LLVMSupport.dir/Threading.cpp.o,15442,261760,5.8992
lib/Support/CMakeFiles/LLVMSupport.dir/ThreadLocal.cpp.o,9658,180736,5.3437
lib/Support/CMakeFiles/LLVMSupport.dir/ThreadPool.cpp.o,71932,2848128,2.5255
lib/Support/CMakeFiles/LLVMSupport.dir/Timer.cpp.o,110008,4896128,2.2468
lib/Support/CMakeFiles/LLVMSupport.dir/ToolOutputFile.cpp.o,40618,1080064,3.7607
lib/Support/CMakeFiles/LLVMSupport.dir/TrigramIndex.cpp.o,84280,2908928,2.8972
lib/Support/CMakeFiles/LLVMSupport.dir/Triple.cpp.o,53110,5037312,1.0543
lib/Support/CMakeFiles/LLVMSupport.dir/Twine.cpp.o,55378,1819136,3.0441
lib/Support/CMakeFiles/LLVMSupport.dir/Unicode.cpp.o,25624,1036032,2.4732
lib/Support/CMakeFiles/LLVMSupport.dir/Valgrind.cpp.o,316,32512,.9719
lib/Support/CMakeFiles/LLVMSupport.dir/Watchdog.cpp.o,514,37248,1.3799
lib/Support/CMakeFiles/LLVMSupport.dir/xxhash.cpp.o,16036,745088,2.1522
lib/Support/CMakeFiles/LLVMSupport.dir/YAMLParser.cpp.o,159484,10111232,1.5772
lib/Support/CMakeFiles/LLVMSupport.dir/YAMLTraits.cpp.o,192412,7667456,2.5094
lib/TableGen/CMakeFiles/LLVMTableGen.dir/Error.cpp.o,76996,1983744,3.8813
lib/TableGen/CMakeFiles/LLVMTableGen.dir/Main.cpp.o,244840,8866432,2.7614
lib/TableGen/CMakeFiles/LLVMTableGen.dir/Record.cpp.o,317338,17473152,1.8161
lib/TableGen/CMakeFiles/LLVMTableGen.dir/SetTheory.cpp.o,225964,8708224,2.5948
lib/TableGen/CMakeFiles/LLVMTableGen.dir/StringMatcher.cpp.o,92938,4419200,2.1030
lib/TableGen/CMakeFiles/LLVMTableGen.dir/TableGenBackend.cpp.o,35830,893824,4.0086
lib/TableGen/CMakeFiles/LLVMTableGen.dir/TGLexer.cpp.o,96670,3714560,2.6024
lib/TableGen/CMakeFiles/LLVMTableGen.dir/TGParser.cpp.o,297202,15863808,1.8734
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/AsmMatcherEmitter.cpp.o,794296,44961152,1.7666
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/AsmWriterEmitter.cpp.o,646408,30235904,2.1378
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/AsmWriterInst.cpp.o,426802,14633344,2.9166
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/Attributes.cpp.o,125842,4121216,3.0535
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CallingConvEmitter.cpp.o,147010,5557120,2.6454
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CodeEmitterGen.cpp.o,476032,17985152,2.6468
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CodeGenDAGPatterns.cpp.o,775966,41456896,1.8717
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CodeGenInstruction.cpp.o,467794,18237696,2.5649
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CodeGenMapTable.cpp.o,471352,18067072,2.6089
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CodeGenRegisters.cpp.o,609412,33188096,1.8362
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CodeGenSchedule.cpp.o,582616,27048320,2.1539
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CodeGenTarget.cpp.o,536530,23661568,2.2675
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/CTagsEmitter.cpp.o,158620,5429760,2.9213
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/DAGISelEmitter.cpp.o,588364,20618624,2.8535
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/DAGISelMatcher.cpp.o,593272,21057792,2.8173
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/DAGISelMatcherEmitter.cpp.o,648346,24775168,2.6169
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/DAGISelMatcherGen.cpp.o,583798,21305600,2.7401
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/DAGISelMatcherOpt.cpp.o,577996,20082688,2.8780
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/DFAPacketizerEmitter.cpp.o,531232,20281472,2.6192
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/DisassemblerEmitter.cpp.o,407650,13951232,2.9219
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/FastISelEmitter.cpp.o,799186,45522560,1.7555
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/FixedLenDecoderEmitter.cpp.o,677068,33592064,2.0155
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/GlobalISelEmitter.cpp.o,616762,22650496,2.7229
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/InstrInfoEmitter.cpp.o,726712,30686592,2.3681
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/IntrinsicEmitter.cpp.o,271840,13615488,1.9965
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/OptParserEmitter.cpp.o,162772,6967296,2.3362
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/PseudoLoweringEmitter.cpp.o,431350,15112064,2.8543
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/RegisterInfoEmitter.cpp.o,734248,40471552,1.8142
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/SearchableTableEmitter.cpp.o,185140,7934976,2.3332
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/SubtargetEmitter.cpp.o,578368,27214848,2.1251
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/SubtargetFeatureInfo.cpp.o,154174,5052416,3.0514
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/TableGen.cpp.o,184474,6075904,3.0361
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/Types.cpp.o,1318,45952,2.8682
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/X86DisassemblerTables.cpp.o,117346,5862272,2.0017
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/X86ModRMFilters.cpp.o,6652,176256,3.7740
utils/TableGen/CMakeFiles/obj.llvm-tblgen.dir/X86RecognizableInstr.cpp.o,431278,16599936,2.5980

llvm/include/llvm/Bitcode/BitstreamWriter.h

287

The offset that we back patch is emitted as a 64 bits fixed size, which wasn't possible without this change.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

1902

Yes, extra abbrev.

1950

Oh the FIXME was temporary: I had a 54 written here at some point, and when I came back to the patch after some time it seemed suspicious so I added the FIXME.
Later I figured that the 54 was wrong and 64 was right (and makes sense since we backpatch a 64bits value).

llvm/test/Bitcode/mdnodes-in-post-order.ll

33

Oh this comment was for the offset (15 lines above), copy/pasted and didn't update correctly, will do.

[mehdi_amini]

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

1937

The 64 is documented here, do you thinks it is worth repeating the comment below?

[mehdi_amini]

Remove FIXME and update comments in the tests

[tejohnson]

I guess you don't have any BitcodeReader changes since the unknown records are simply ignored? I think it would be useful to add a BitcodeReader change though to parse the index offset record and sanity check against the offset of the index record when it is later encountered.

llvm/include/llvm/Bitcode/BitstreamWriter.h

287

But you are casting V to unsigned aka unsigned int, which is 32 bits. It seems like you don't want to cast V at all if you change to Emit64, since Emit64 takes a uint64_t, and in order to pass in a 64-bit val the uintty of V should already be uint64_t. This is similar to how V is not cast when passed to EmitVBR64 below (which takes a uint64_t value).

Actually - I think you are getting lucky here because BackpatchWord also takes a 32-bit unsigned value. So you are never currently writing a 64-bit value for the offset.

For the VST offset we simply emit the number of 32-bit words since blocks are guaranteed to be 32-bit aligned. I guess you can't do that here since the index is not at the start of the block. Alternatively, emit into its own block, then you can emit the word offset.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

1937

I don't think you need to document it again below.

1938

Not the beginning of the block, so variable name should be changed.

1951

As noted earlier, this value gets passed to a 32-bit unsigned parameter. You'll need a new interface to write a 64-bit offset, or write 2 32-bit halves.

[tejohnson]

llvm/include/llvm/Bitcode/BitstreamWriter.h

287

Alternatively, emit into its own block, then you can emit the word offset.

Thinking more about this, it should be lower overhead to emit in the original block and just emit properly as a 64-bit value. I think that is just invoking Emit64 without the cast on V, and adding a new backpatch interface that takes a 64-bit unsigned and splits into two halves as Emit64 does in the >32 bit case.

[mehdi_amini]

In D28083#631731, @tejohnson wrote:

I guess you don't have any BitcodeReader changes since the unknown records are simply ignored?

Yes!

I think it would be useful to add a BitcodeReader change though to parse the index offset record and sanity check against the offset of the index record when it is later encountered.

Good idea, will do!

llvm/include/llvm/Bitcode/BitstreamWriter.h

287

Thinking more about this, it should be lower overhead to emit in the original block and just emit properly as a 64-bit value. I think that is just invoking Emit64 without the cast on V, and adding a new backpatch interface that takes a 64-bit unsigned and splits into two halves as Emit64 does in the >32 bit case.

Yes will do. Thanks for catching, it solved the assertion but would still have been broken on large files...

[mehdi_amini]

In D28083#631799, @mehdi_amini wrote:

In D28083#631731, @tejohnson wrote:

I think it would be useful to add a BitcodeReader change though to parse the index offset record and sanity check against the offset of the index record when it is later encountered.

Good idea, will do!

It does not fit well: when I get in the switch case for the index I already read the index record, and the bitcode position has moved so I can't use it to validate. It would require to always save the position before every record and thread it through a function call, which seems overkill for this. I'm leaning toward adding a llvm-bcanalyzer check instead.

[mehdi_amini]

• Fix 64 bits emit
• Fix backpatchword by adding a 64 bits version
• Add checks for the offset in llvm-bcanalyzer

[tejohnson]

LGTM with a couple nits below.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

1938

See this comment from earlier. Maybe IndexOffsetRecordBitPos?

llvm/tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

608

nit: "a the"

[mehdi_amini]

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

1938

Sorry, missed it! Fixed before pushing.

[mehdi_amini]

FYI: had trouble with:

1. Blocks that contains no record (or very little): the placeholder may not be flushed yet and the back patch will fail. I added a threshold optimization which workaround this (r290690)
2. On 32 bits platform, we can't have fixed fields of 64 bits, I reverted the change in EmitAbbreviatedField from this patch, and instead emit now 2 fields of 32 bits each (r290693)

llvm/include/llvm/Bitcode/BitstreamWriter.h

void BackpatchWord(uint64_t BitNo, unsigned NewWord) {
     unsigned ByteNo = BitNo / 8;
     assert((!endian::readAtBitAlignment<uint32_t, little, unaligned>(
                &Out[ByteNo], BitNo & 7)) &&
            "Expected to be patching over 0-value placeholders");
     endian::writeAtBitAlignment<uint32_t, little, unaligned>(
         &Out[ByteNo], NewWord, BitNo & 7);
   }
 
+  void BackpatchWord64(uint64_t BitNo, uint64_t Val) {
+    BackpatchWord(BitNo, (uint32_t)Val);
+    BackpatchWord(BitNo + 32, (uint32_t)(Val >> 32));
+  }
+
   void Emit(uint32_t Val, unsigned NumBits) {
     assert(NumBits && NumBits <= 32 && "Invalid value size!");
     assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
     CurValue |= Val << CurBit;
     if (CurBit + NumBits < 32) {
       CurBit += NumBits;
       return;
     }
private:
   void EmitAbbreviatedField(const BitCodeAbbrevOp &Op, uintty V) {
     assert(!Op.isLiteral() && "Literals should use EmitAbbreviatedLiteral!");
 
     // Encode the value as we are commanded.
     switch (Op.getEncoding()) {
     default: llvm_unreachable("Unknown encoding!");
     case BitCodeAbbrevOp::Fixed:
       if (Op.getEncodingData())
-        Emit((unsigned)V, (unsigned)Op.getEncodingData());
+        Emit64(V, (unsigned)Op.getEncodingData());
       break;
     case BitCodeAbbrevOp::VBR:
       if (Op.getEncodingData())
         EmitVBR64(V, (unsigned)Op.getEncodingData());
       break;
     case BitCodeAbbrevOp::Char6:
       Emit(BitCodeAbbrevOp::EncodeChar6((char)V), 6);
       break;

llvm/include/llvm/Bitcode/LLVMBitCodes.h

enum MetadataCodes {
   METADATA_FILE = 16,            // [distinct, filename, directory]
   METADATA_DERIVED_TYPE = 17,    // [distinct, ...]
   METADATA_COMPOSITE_TYPE = 18,  // [distinct, ...]
   METADATA_SUBROUTINE_TYPE = 19, // [distinct, flags, types, cc]
   METADATA_COMPILE_UNIT = 20,    // [distinct, ...]
   METADATA_SUBPROGRAM = 21,      // [distinct, ...]
   METADATA_LEXICAL_BLOCK = 22,   // [distinct, scope, file, line, column]
   METADATA_LEXICAL_BLOCK_FILE = 23, //[distinct, scope, file, discriminator]
-  METADATA_NAMESPACE = 24,       // [distinct, scope, file, name, line, exportSymbols]
+  METADATA_NAMESPACE = 24, // [distinct, scope, file, name, line, exportSymbols]
   METADATA_TEMPLATE_TYPE = 25,   // [distinct, scope, name, type, ...]
   METADATA_TEMPLATE_VALUE = 26,  // [distinct, scope, name, type, value, ...]
   METADATA_GLOBAL_VAR = 27,      // [distinct, ...]
   METADATA_LOCAL_VAR = 28,       // [distinct, ...]
   METADATA_EXPRESSION = 29,      // [distinct, n x element]
   METADATA_OBJC_PROPERTY = 30,   // [distinct, name, file, line, ...]
   METADATA_IMPORTED_ENTITY = 31, // [distinct, tag, scope, entity, line, name]
   METADATA_MODULE = 32,          // [distinct, scope, name, ...]
   METADATA_MACRO = 33,           // [distinct, macinfo, line, name, value]
   METADATA_MACRO_FILE = 34,      // [distinct, macinfo, line, file, ...]
   METADATA_STRINGS = 35,         // [count, offset] blob([lengths][chars])
   METADATA_GLOBAL_DECL_ATTACHMENT = 36, // [valueid, n x [id, mdnode]]
-  METADATA_GLOBAL_VAR_EXPR = 37, // [distinct, var, expr]
+  METADATA_GLOBAL_VAR_EXPR = 37,        // [distinct, var, expr]
+  METADATA_INDEX_OFFSET = 38,           // [offset]
+  METADATA_INDEX = 39,                  // [bitpos]
 };
 
 // The constants block (CONSTANTS_BLOCK_ID) describes emission for each
 // constant and maintains an implicit current type value.
 enum ConstantsCodes {
   CST_CODE_SETTYPE = 1,          // SETTYPE:       [typeid]
   CST_CODE_NULL = 2,             // NULL
   CST_CODE_UNDEF = 3,            // UNDEF

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

void writeDIImportedEntity(const DIImportedEntity *N,
                              SmallVectorImpl<uint64_t> &Record,
                              unsigned Abbrev);
   unsigned createNamedMetadataAbbrev();
   void writeNamedMetadata(SmallVectorImpl<uint64_t> &Record);
   unsigned createMetadataStringsAbbrev();
   void writeMetadataStrings(ArrayRef<const Metadata *> Strings,
                             SmallVectorImpl<uint64_t> &Record);
   void writeMetadataRecords(ArrayRef<const Metadata *> MDs,
-                            SmallVectorImpl<uint64_t> &Record);
+                            SmallVectorImpl<uint64_t> &Record,
+                            std::vector<unsigned> *MDAbbrevs = nullptr,
+                            std::vector<uint64_t> *IndexPos = nullptr);
   void writeModuleMetadata();
   void writeFunctionMetadata(const Function &F);
   void writeFunctionMetadataAttachment(const Function &F);
   void writeGlobalVariableMetadataAttachment(const GlobalVariable &GV);
   void pushGlobalMetadataAttachment(SmallVectorImpl<uint64_t> &Record,
                                     const GlobalObject &GO);
   void writeModuleMetadataKinds();
   void writeOperandBundleTags();
void ModuleBitcodeWriter::writeMetadataStrings(
   for (const Metadata *MD : Strings)
     Blob.append(cast<MDString>(MD)->getString());
 
   // Emit the final record.
   Stream.EmitRecordWithBlob(createMetadataStringsAbbrev(), Record, Blob);
   Record.clear();
 }
 
+// Generates an enum to use as an index in the Abbrev array of Metadata record.
+enum MetadataAbbrev : unsigned {
+#define HANDLE_MDNODE_LEAF(CLASS) CLASS##AbbrevID,
+#include "llvm/IR/Metadata.def"
+  LastPlusOne
+};
+
 void ModuleBitcodeWriter::writeMetadataRecords(
-    ArrayRef<const Metadata *> MDs, SmallVectorImpl<uint64_t> &Record) {
+    ArrayRef<const Metadata *> MDs, SmallVectorImpl<uint64_t> &Record,
+    std::vector<unsigned> *MDAbbrevs, std::vector<uint64_t> *IndexPos) {
   if (MDs.empty())
     return;
 
   // Initialize MDNode abbreviations.
 #define HANDLE_MDNODE_LEAF(CLASS) unsigned CLASS##Abbrev = 0;
 #include "llvm/IR/Metadata.def"
 
   for (const Metadata *MD : MDs) {
+    if (IndexPos)
+      IndexPos->push_back(Stream.GetCurrentBitNo());
     if (const MDNode *N = dyn_cast<MDNode>(MD)) {
       assert(N->isResolved() && "Expected forward references to be resolved");
 
       switch (N->getMetadataID()) {
       default:
         llvm_unreachable("Invalid MDNode subclass");
 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
   case Metadata::CLASS##Kind:                                                  \
-    write##CLASS(cast<CLASS>(N), Record, CLASS##Abbrev);                       \
+    if (MDAbbrevs)                                                             \
+      write##CLASS(cast<CLASS>(N), Record,                                     \
+                   (*MDAbbrevs)[MetadataAbbrev::CLASS##AbbrevID]);             \
+    else                                                                       \
+      write##CLASS(cast<CLASS>(N), Record, CLASS##Abbrev);                     \
     continue;
 #include "llvm/IR/Metadata.def"
       }
     }
     writeValueAsMetadata(cast<ValueAsMetadata>(MD), Record);
   }
 }
 
 void ModuleBitcodeWriter::writeModuleMetadata() {
   if (!VE.hasMDs() && M.named_metadata_empty())
     return;
 
-  Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
+  Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 4);
   SmallVector<uint64_t, 64> Record;
+
+  // Emit all abbrevs upfront, so that the reader can jump in the middle of the
+  // block and load any metadata.
+  std::vector<unsigned> MDAbbrevs;
+
+  MDAbbrevs.resize(MetadataAbbrev::LastPlusOne);
+  MDAbbrevs[MetadataAbbrev::DILocationAbbrevID] = createDILocationAbbrev();
+  MDAbbrevs[MetadataAbbrev::GenericDINodeAbbrevID] =
+      createGenericDINodeAbbrev();
+
+  BitCodeAbbrev *Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::METADATA_INDEX_OFFSET));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 64));
+  unsigned OffsetAbbrev = Stream.EmitAbbrev(Abbv);
+
+  Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::METADATA_INDEX));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
+  unsigned IndexAbbrev = Stream.EmitAbbrev(Abbv);
+
+  // Emit MDStrings together upfront.
   writeMetadataStrings(VE.getMDStrings(), Record);
-  writeMetadataRecords(VE.getNonMDStrings(), Record);
+
+  // Write a placeholder value in for the offset of the metadata index,
+  // which is written after the records, so that it can include
+  // the offset of each entry. The placeholder offset will be
+  // updated after all records are emitted.
+  uint64_t Vals[] = {0};
+  Stream.EmitRecord(bitc::METADATA_INDEX_OFFSET, Vals, OffsetAbbrev);
+
+  // Compute and save the bit offset to the current position, which will be
+  // patched when we emit the index later. We can simply subtract the 64-bit
+  // fixed size from the current bit number to get the location to backpatch.
+  uint64_t BeginBlockBitPos = Stream.GetCurrentBitNo();
+
+  // This index will contain the bitpos for each individual record.
+  std::vector<uint64_t> IndexPos;
+  IndexPos.reserve(VE.getNonMDStrings().size());
+
+  // Write all the records
+  writeMetadataRecords(VE.getNonMDStrings(), Record, &MDAbbrevs, &IndexPos);
+
+  // Now that we have emitted all the records we will emit the index. But first
+  // backpatch the forward reference so that the reader can skip the records
+  // efficiently.
+  Stream.BackpatchWord64(BeginBlockBitPos - 64,
+                         Stream.GetCurrentBitNo() - BeginBlockBitPos);
+
+  // Delta encode the index.
+  uint64_t PreviousValue = BeginBlockBitPos;
+  for (auto &Elt : IndexPos) {
+    auto EltDelta = Elt - PreviousValue;
+    PreviousValue = Elt;
+    Elt = EltDelta;
+  }
+  // Emit the index record.
+  Stream.EmitRecord(bitc::METADATA_INDEX, IndexPos, IndexAbbrev);
+  IndexPos.clear();
+
+  // Write the named metadata now.
   writeNamedMetadata(Record);
 
   auto AddDeclAttachedMetadata = [&](const GlobalObject &GO) {
     SmallVector<uint64_t, 4> Record;
     Record.push_back(VE.getValueID(&GO));
     pushGlobalMetadataAttachment(Record, GO);
     Stream.EmitRecord(bitc::METADATA_GLOBAL_DECL_ATTACHMENT, Record);
   };

llvm/test/Bitcode/mdnodes-distinct-in-post-order.ll

 !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}
 
+; 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
 ; CHECK-NEXT:  <NAMED_NODE op0=3/>
 !named = !{!4}

llvm/test/Bitcode/mdnodes-distinct-nodes-break-cycles.ll

 !1 = distinct !{!3}
 
 ; CHECK-NEXT:  <NODE op0=1/>
 !2 = !{!1}
 
 ; 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
 ; CHECK-NEXT:  <NAMED_NODE op0=1/>
 !named = !{!2}

llvm/test/Bitcode/mdnodes-distinct-nodes-first.ll

 ; 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}
 
+; 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
 ; CHECK-NEXT:  <NAMED_NODE op0=1/>
 !named = !{!2}

llvm/test/Bitcode/mdnodes-in-post-order.ll

 
 ; 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:  }
 
+; 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/>
 !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}
 
+; 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
 ; CHECK-NEXT:  <NAMED_NODE op0=5/>
 !named = !{!6}

llvm/test/Bitcode/metadata-function-blocks.ll

 ; CHECK-NEXT:     'named'
 ; CHECK-NEXT:     'named and foo'
 ; CHECK-NEXT:     'foo and bar'
 ; CHECK-NEXT:   }
 
 ; 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"}
 
 ; CHECK-NEXT:   <NODE op0=2/>
 !5 = !{!"named and foo"}
 
 ; CHECK-NEXT:   <NODE op0=1 op1=4 op2=5/>
 !6 = !{!"named", !4, !5}

llvm/tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

default:return nullptr;
       STRINGIFY_CODE(METADATA, TEMPLATE_TYPE)
       STRINGIFY_CODE(METADATA, TEMPLATE_VALUE)
       STRINGIFY_CODE(METADATA, GLOBAL_VAR)
       STRINGIFY_CODE(METADATA, LOCAL_VAR)
       STRINGIFY_CODE(METADATA, EXPRESSION)
       STRINGIFY_CODE(METADATA, OBJC_PROPERTY)
       STRINGIFY_CODE(METADATA, IMPORTED_ENTITY)
       STRINGIFY_CODE(METADATA, MODULE)
+      STRINGIFY_CODE(METADATA, INDEX_OFFSET)
+      STRINGIFY_CODE(METADATA, INDEX)
     }
   case bitc::METADATA_KIND_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(METADATA, KIND)
     }
   case bitc::USELIST_BLOCK_ID:
if (NonSymbolic && BlockName)
       outs() << " BlockID=" << BlockID;
 
     outs() << " NumWords=" << NumWords
            << " BlockCodeSize=" << Stream.getAbbrevIDWidth() << ">\n";
   }
 
   SmallVector<uint64_t, 64> Record;
 
+  // Keep the offset to the metadata index if seen.
+  uint64_t MetadataIndexOffset = 0;
+
   // Read all the records for this block.
   while (1) {
     if (Stream.AtEndOfStream())
       return ReportError("Premature end of bitstream");
 
     uint64_t RecordStartBit = Stream.GetCurrentBitNo();
 
     BitstreamEntry Entry =
if (DumpRecords) {
       if (Entry.ID != bitc::UNABBREV_RECORD) {
         Abbv = Stream.getAbbrev(Entry.ID);
         outs() << " abbrevid=" << Entry.ID;
       }
 
       for (unsigned i = 0, e = Record.size(); i != e; ++i)
         outs() << " op" << i << "=" << (int64_t)Record[i];
 
+      // If we found a the metadata index, let's verify that we had an offset
+      // and its position!
+      if (BlockID == bitc::METADATA_BLOCK_ID) {
+        if (Code == bitc::METADATA_INDEX_OFFSET) {
+          MetadataIndexOffset = Stream.GetCurrentBitNo() + Record[0];
+        }
+        if (Code == bitc::METADATA_INDEX) {
+          outs() << " (offset ";
+          if (MetadataIndexOffset == RecordStartBit)
+            outs() << "match)";
+          else
+            outs() << "mismatch: " << MetadataIndexOffset << " vs "
+                   << RecordStartBit << ")";
+        }
+      }
+
       // If we found a module hash, let's verify that it matches!
       if (BlockID == bitc::MODULE_BLOCK_ID && Code == bitc::MODULE_CODE_HASH) {
         if (Record.size() != 5)
           outs() << " (invalid)";
         else {
           // Recompute the hash and compare it to the one in the bitcode
           SHA1 Hasher;
           StringRef Hash;