Function bitcode index in Value Symbol Table and lazy reading support

[tejohnson]

Summary

Support for including the function bitcode indices in the Value Symbol
Table. This requires writing the VST after the function blocks, which in
turn requires a new VST forward declaration record encoding the offset of
the full VST (which is backpatched to contain the offset after the VST
is written).

This patch also enables the lazy function reader to use the new function
indices out of the VST. This support will be used by ThinLTO as well, which
will be in a follow on patch. Backwards compatibility with older bitcode
files is maintained.

A new test is also included.

The bitcode format (used for the lazy reader as well as the upcoming
ThinLTO patches) came out of discussions with Duncan and others and is
described here:
https://drive.google.com/file/d/0B036uwnWM6RWdnBLakxmeDdOeXc/view

[mehdi_amini]

Hi Teresa,

Thanks for this patch, it looks good to me overall.
Please find some comments inline.

Also does it change the behavior of the LazyReader?
I don't know it enough to know if the fact that you are populating DeferredFunctionInfo using the module VST means it no longer needs to visit all the blocks. I'd expect llvm-extract to be constant time now, independently of the number of functions in the module.

Best,

Mehdi

include/llvm/Bitcode/BitstreamReader.h

237 ↗

(On Diff #33710)

This is identical to getAbbrevIDWidth() two lines above, do you really need to alias it?

include/llvm/Bitcode/BitstreamWriter.h

126 ↗

(On Diff #33710)

(Note: this shift/insert seems ok to me but I am not certain about if it is endian independent)

129 ↗

(On Diff #33710)

It looks like the BackpatchWord change is independent, can it be in a separate commit?

521 ↗

(On Diff #33710)

It seems this is not needed for this patch? I don't see any use of getOrCreateBlockInfo in the diff?

lib/Bitcode/Reader/BitcodeReader.cpp

1589 ↗

(On Diff #33710)

I believe usually function argument are using the base class SmallVectorImpl<uint64_t> to avoid specializing on the size. The size is only relevant when you allocate it.

1693 ↗

(On Diff #33710)

Minor comment: You can avoid the extra dyn_cast.

GlobalObject *GO;
// If this is an alias, need to get the actual Function object
// it aliases, in order to set up the DeferredFunctionInfo entry below.
auto *GA = dyn_cast<GlobalAlias>(V);
if (GA)
  GO = GA->getBaseObject();
else
  GO = dyn_cast<GlobalObject>(V);
assert(GO);

2987 ↗

(On Diff #33710)

kudos for the comments everywhere! :)

3301 ↗

(On Diff #33710)

Is Record.size() > 1 a valid possibility here?

4744 ↗

(On Diff #33710)

Not sure from the comment: is there a possibility for the assert to fire on old format bitcode? LLVM is supposed to always be able to read old bitcode.

lib/Bitcode/Writer/BitcodeWriter.cpp

599 ↗

(On Diff #33710)

Could be directly:

SmallVector<unsigned, 2> Vals{llvm::bitc::MODULE_CODE_VSTOFFSET, 0};
Stream.EmitRecordWithAbbrev(VSTOffsetAbbrev, Rec);

2132 ↗

(On Diff #33710)

What if there has been a placeholder emitted in this case?

2188 ↗

(On Diff #33710)

Why did you need to change it to use an iterator?
I believe you can still use Name instead of SI to have getValue() below.

for (const ValueName &Name : VST) {
   Value &Val = Name.getValue();

(I may have missed a use-case).

2203 ↗

(On Diff #33710)

(Minor comment: Same extra dyn_cast as previously)

[tejohnson]

In D12536#237772, @joker.eph wrote:

Hi Teresa,

Thanks for this patch, it looks good to me overall.
Please find some comments inline.

Thanks, responses inline.

Also does it change the behavior of the LazyReader?
I don't know it enough to know if the fact that you are populating DeferredFunctionInfo using the module VST means it no longer needs to visit all the blocks.

Previously the lazy reader needs to parse through all the function blocks to populate DeferredFunctionInfo: Each time a function block is encountered by a call to parseModule, it records the bitcode offset (via BitcodeReader::rememberAndSkipFunctionBody) and stops parsing. Then whenever a function is materialized, it invokes BitcodeReader::findFunctionInStream, and if the DeferredFunctionInfo entry isn't found, parseModule is resumed from where it left off (and again records and skips the next function block and stops). findFunctionInStream will repeat this process until the function to be materialized is found. In the end, all the function blocks up through the last one materialized need to be walked through once to populate the full DeferredFunctionInfo (although their contents are skipped so it should be fairly fast).

With my patch, because the DeferredFunctionInfo is populated from the VST when we encounter the first function block, we can avoid this walk and stop parsing the module. I have an assert in findFunctionInStream that it should always find an entry for a function when the VSTOffset is not 0 - so essentially parseModule is never called from here to walk through the function blocks.

I'd expect llvm-extract to be constant time now, independently of the number of functions in the module.

Yes, that would be the case with this change.

Thanks,
Teresa

Best,

Mehdi

include/llvm/Bitcode/BitstreamReader.h

237 ↗

(On Diff #33710)

I will remove this and switch to using getAbbrevIDWidth.

I originally didn't use the same name since I thought abbrev ids was a specific use case. But looking at the LLVM Bitcode File Format doc online I see that it does refer to this number as the abbrev id width, and block IDs are also referred to as (possibly builtin) abbrev IDs.

Will change the corresponding interface I added to the BitstreamWriter to getAbbrevIDWidth to be consistent.

include/llvm/Bitcode/BitstreamWriter.h

126 ↗

(On Diff #33710)

It should be - this mirrors the way the CurValue is set in Emit() via shifting.

129 ↗

(On Diff #33710)

It is only needed because of the new use case of being called to backpatch the VSTOffset, which is the first time a non-word aligned location is backpatched. But it is independent in that it could presumably be used in other contexts in the future. If you feel this is better as a separate commit I can split it out and commit it first.

521 ↗

(On Diff #33710)

This was leftover from something else I tried and apparently forgot to clean up. Will move the public back down where it was.

lib/Bitcode/Reader/BitcodeReader.cpp

1589 ↗

(On Diff #33710)

Got it, will change.

1693 ↗

(On Diff #33710)

Good idea, will do.

2987 ↗

(On Diff #33710)

Thanks!

3301 ↗

(On Diff #33710)

Not in the current record design. It will only contain one record with a 32-bit word offset.

4744 ↗

(On Diff #33710)

Right, I left in the support for the old bitcode. This comment is meant to ensure that if we fall into the old format handling (no DeferredFunctionInfo entry that was pre-populated) that we indeed have the old format (in which case there should not have been a VSTOFFSET record in the bitcode). So the assert will not fire with the old format. Will clarify this in the comment.

lib/Bitcode/Writer/BitcodeWriter.cpp

599 ↗

(On Diff #33710)

True, hadn't seen that usage before but it looks like that would work. Will change.

2132 ↗

(On Diff #33710)

WriteValueSymbolTableForwardDecl has the same early return, so there won't be one. Will add an assert here to ensure that VSTOffsetPlaceholder is 0 so that the two routines are forced to stay in sync on that.

2188 ↗

(On Diff #33710)

Ah, looks like this loop was just rangified a few weeks back, and my merge went back to the old code since I was using the earlier code when I first implemented this handling. Will fix.

2203 ↗

(On Diff #33710)

Will fix.

[tejohnson]

New patch being uploaded. A few additional notes below.

lib/Bitcode/Reader/BitcodeReader.cpp

1693 ↗

(On Diff #33710)

Actually, did something similar but optimized for the common case where it isn't an alias: It does the dyn_cast to GlobalObject, and only does the dyn_cast to GlobalAlias if GO is null.

lib/Bitcode/Writer/BitcodeWriter.cpp

2203 ↗

(On Diff #33710)

Ditto here - dyn_cast to Function, if null, do the alias check.

[tejohnson]

Update per Mehdi's review comments.

[tejohnson]

Ping.

Please let me know if you have any other comments or if it looks ready to go in.

Thanks,
Teresa

llvm/trunk/include/llvm/Bitcode/LLVMBitCodes.h

enum BlockIDs {
     UNUSED_ID1,
 
     VALUE_SYMTAB_BLOCK_ID,
     METADATA_BLOCK_ID,
     METADATA_ATTACHMENT_ID,
 
     TYPE_BLOCK_ID_NEW,
 
-    USELIST_BLOCK_ID
+    USELIST_BLOCK_ID,
+
+    MODULE_STRTAB_BLOCK_ID,
+    FUNCTION_SUMMARY_BLOCK_ID
   };
 
 
   /// MODULE blocks have a number of optional fields and subblocks.
   enum ModuleCodes {
     MODULE_CODE_VERSION     = 1,    // VERSION:     [version#]
     MODULE_CODE_TRIPLE      = 2,    // TRIPLE:      [strchr x N]
     MODULE_CODE_DATALAYOUT  = 3,    // DATALAYOUT:  [strchr x N]
enum ModuleCodes {
     // ALIAS: [alias type, aliasee val#, linkage, visibility]
     MODULE_CODE_ALIAS       = 9,
 
     // MODULE_CODE_PURGEVALS: [numvals]
     MODULE_CODE_PURGEVALS   = 10,
 
     MODULE_CODE_GCNAME      = 11,  // GCNAME: [strchr x N]
     MODULE_CODE_COMDAT      = 12,  // COMDAT: [selection_kind, name]
+
+    MODULE_CODE_VSTOFFSET   = 13,  // VSTOFFSET: [offset]
   };
 
   /// PARAMATTR blocks have code for defining a parameter attribute set.
   enum AttributeCodes {
     // FIXME: Remove `PARAMATTR_CODE_ENTRY_OLD' in 4.0
     PARAMATTR_CODE_ENTRY_OLD  = 1, // ENTRY: [paramidx0, attr0,
                                    //         paramidx1, attr1...]
     PARAMATTR_CODE_ENTRY      = 2, // ENTRY: [paramidx0, attrgrp0,
enum TypeCodes {
     TYPE_CODE_TOKEN = 22        // TOKEN
   };
 
   // The type symbol table only has one code (TST_ENTRY_CODE).
   enum TypeSymtabCodes {
     TST_CODE_ENTRY = 1     // TST_ENTRY: [typeid, namechar x N]
   };
 
-  // The value symbol table only has one code (VST_ENTRY_CODE).
+  // Value symbol table codes.
   enum ValueSymtabCodes {
-    VST_CODE_ENTRY   = 1,  // VST_ENTRY: [valid, namechar x N]
-    VST_CODE_BBENTRY = 2   // VST_BBENTRY: [bbid, namechar x N]
+    VST_CODE_ENTRY   = 1,   // VST_ENTRY: [valueid, namechar x N]
+    VST_CODE_BBENTRY = 2,   // VST_BBENTRY: [bbid, namechar x N]
+    VST_CODE_FNENTRY = 3,   // VST_FNENTRY: [valueid, offset, namechar x N]
   };
 
   enum MetadataCodes {
     METADATA_STRING        = 1,   // MDSTRING:      [values]
     METADATA_VALUE         = 2,   // VALUE:         [type num, value num]
     METADATA_NODE          = 3,   // NODE:          [n x md num]
     METADATA_NAME          = 4,   // STRING:        [values]
     METADATA_DISTINCT_NODE = 5,   // DISTINCT_NODE: [n x md num]

llvm/trunk/lib/Bitcode/Reader/BitcodeReader.cpp

class BitcodeReader : public GVMaterializer {
   LLVMContext &Context;
   DiagnosticHandlerFunction DiagnosticHandler;
   Module *TheModule = nullptr;
   std::unique_ptr<MemoryBuffer> Buffer;
   std::unique_ptr<BitstreamReader> StreamFile;
   BitstreamCursor Stream;
   uint64_t NextUnreadBit = 0;
   bool SeenValueSymbolTable = false;
+  unsigned VSTOffset = 0;
 
   std::vector<Type*> TypeList;
   BitcodeReaderValueList ValueList;
   BitcodeReaderMDValueList MDValueList;
   std::vector<Comdat *> ComdatList;
   SmallVector<Instruction *, 64> InstructionList;
 
   std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInits;
private:
   std::error_code parseAlignmentValue(uint64_t Exponent, unsigned &Alignment);
   std::error_code parseAttrKind(uint64_t Code, Attribute::AttrKind *Kind);
   std::error_code parseModule(bool Resume, bool ShouldLazyLoadMetadata = false);
   std::error_code parseAttributeBlock();
   std::error_code parseAttributeGroupBlock();
   std::error_code parseTypeTable();
   std::error_code parseTypeTableBody();
 
-  std::error_code parseValueSymbolTable();
+  ErrorOr<Value *> recordValue(SmallVectorImpl<uint64_t> &Record,
+                               unsigned NameIndex, Triple &TT);
+  std::error_code parseValueSymbolTable(unsigned Offset = 0);
   std::error_code parseConstants();
   std::error_code rememberAndSkipFunctionBody();
   /// Save the positions of the Metadata blocks and skip parsing the blocks.
   std::error_code rememberAndSkipMetadata();
   std::error_code parseFunctionBody(Function *F);
   std::error_code globalCleanup();
   std::error_code resolveGlobalAndAliasInits();
   std::error_code parseMetadata();
while (1) {
     if (TypeList[NumRecords])
       return error(
           "Invalid TYPE table: Only named structs can be forward referenced");
     assert(ResultTy && "Didn't read a type?");
     TypeList[NumRecords++] = ResultTy;
   }
 }
 
-std::error_code BitcodeReader::parseValueSymbolTable() {
+/// Associate a value with its name from the given index in the provided record.
+ErrorOr<Value *> BitcodeReader::recordValue(SmallVectorImpl<uint64_t> &Record,
+                                            unsigned NameIndex, Triple &TT) {
+  SmallString<128> ValueName;
+  if (convertToString(Record, NameIndex, ValueName))
+    return error("Invalid record");
+  unsigned ValueID = Record[0];
+  if (ValueID >= ValueList.size() || !ValueList[ValueID])
+    return error("Invalid record");
+  Value *V = ValueList[ValueID];
+
+  V->setName(StringRef(ValueName.data(), ValueName.size()));
+  auto *GO = dyn_cast<GlobalObject>(V);
+  if (GO) {
+    if (GO->getComdat() == reinterpret_cast<Comdat *>(1)) {
+      if (TT.isOSBinFormatMachO())
+        GO->setComdat(nullptr);
+      else
+        GO->setComdat(TheModule->getOrInsertComdat(V->getName()));
+    }
+  }
+  return V;
+}
+
+/// Parse the value symbol table at either the current parsing location or
+/// at the given bit offset if provided.
+std::error_code BitcodeReader::parseValueSymbolTable(unsigned Offset) {
+  uint64_t CurrentBit;
+  // Pass in the Offset to distinguish between calling for the module-level
+  // VST (where we want to jump to the VST offset) and the function-level
+  // VST (where we don't).
+  if (Offset > 0) {
+    // Save the current parsing location so we can jump back at the end
+    // of the VST read.
+    CurrentBit = Stream.GetCurrentBitNo();
+    Stream.JumpToBit(Offset * 32);
+    BitstreamEntry Entry = Stream.advance();
+    assert(Entry.Kind == BitstreamEntry::SubBlock);
+    assert(Entry.ID == bitc::VALUE_SYMTAB_BLOCK_ID);
+  }
+
+  // Compute the delta between the bitcode indices in the VST (the word offset
+  // to the word-aligned ENTER_SUBBLOCK for the function block, and that
+  // expected by the lazy reader. The reader's EnterSubBlock expects to have
+  // already read the ENTER_SUBBLOCK code (size getAbbrevIDWidth) and BlockID
+  // (size BlockIDWidth). Note that we access the stream's AbbrevID width here
+  // just before entering the VST subblock because: 1) the EnterSubBlock
+  // changes the AbbrevID width; 2) the VST block is nested within the same
+  // outer MODULE_BLOCK as the FUNCTION_BLOCKs and therefore have the same
+  // AbbrevID width before calling EnterSubBlock; and 3) when we want to
+  // jump to the FUNCTION_BLOCK using this offset later, we don't want
+  // to rely on the stream's AbbrevID width being that of the MODULE_BLOCK.
+  unsigned FuncBitcodeOffsetDelta =
+      Stream.getAbbrevIDWidth() + bitc::BlockIDWidth;
+
   if (Stream.EnterSubBlock(bitc::VALUE_SYMTAB_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
 
   Triple TT(TheModule->getTargetTriple());
 
   // Read all the records for this value table.
   SmallString<128> ValueName;
   while (1) {
     BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
 
     switch (Entry.Kind) {
     case BitstreamEntry::SubBlock: // Handled for us already.
     case BitstreamEntry::Error:
       return error("Malformed block");
     case BitstreamEntry::EndBlock:
+      if (Offset > 0)
+        Stream.JumpToBit(CurrentBit);
       return std::error_code();
     case BitstreamEntry::Record:
       // The interesting case.
       break;
     }
 
     // Read a record.
     Record.clear();
     switch (Stream.readRecord(Entry.ID, Record)) {
     default:  // Default behavior: unknown type.
       break;
     case bitc::VST_CODE_ENTRY: {  // VST_ENTRY: [valueid, namechar x N]
-      if (convertToString(Record, 1, ValueName))
-        return error("Invalid record");
-      unsigned ValueID = Record[0];
-      if (ValueID >= ValueList.size() || !ValueList[ValueID])
-        return error("Invalid record");
-      Value *V = ValueList[ValueID];
-
-      V->setName(StringRef(ValueName.data(), ValueName.size()));
-      if (auto *GO = dyn_cast<GlobalObject>(V)) {
-        if (GO->getComdat() == reinterpret_cast<Comdat *>(1)) {
-          if (TT.isOSBinFormatMachO())
-            GO->setComdat(nullptr);
-          else
-            GO->setComdat(TheModule->getOrInsertComdat(V->getName()));
-        }
-      }
-      ValueName.clear();
+      ErrorOr<Value *> ValOrErr = recordValue(Record, 1, TT);
+      if (std::error_code EC = ValOrErr.getError())
+        return EC;
+      ValOrErr.get();
+      break;
+    case bitc::VST_CODE_FNENTRY: {
+      // VST_FNENTRY: [valueid, offset, namechar x N]
+      ErrorOr<Value *> ValOrErr = recordValue(Record, 2, TT);
+      if (std::error_code EC = ValOrErr.getError())
+        return EC;
+      Value *V = ValOrErr.get();
+
+      auto *GO = dyn_cast<GlobalObject>(V);
+      if (!GO) {
+        // If this is an alias, need to get the actual Function object
+        // it aliases, in order to set up the DeferredFunctionInfo entry below.
+        auto *GA = dyn_cast<GlobalAlias>(V);
+        if (GA)
+          GO = GA->getBaseObject();
+        assert(GO);
+      }
+
+      uint64_t FuncWordOffset = Record[1];
+      Function *F = dyn_cast<Function>(GO);
+      assert(F);
+      uint64_t FuncBitOffset = FuncWordOffset * 32;
+      DeferredFunctionInfo[F] = FuncBitOffset + FuncBitcodeOffsetDelta;
+      // Set the NextUnreadBit to point to the last function block.
+      // Later when parsing is resumed after function materialization,
+      // we can simply skip that last function block.
+      if (FuncBitOffset > NextUnreadBit)
+        NextUnreadBit = FuncBitOffset;
       break;
     }
     case bitc::VST_CODE_BBENTRY: {
       if (convertToString(Record, 1, ValueName))
         return error("Invalid record");
       BasicBlock *BB = getBasicBlock(Record[0]);
       if (!BB)
         return error("Invalid record");
case BitstreamEntry::SubBlock:
         if (std::error_code EC = parseAttributeGroupBlock())
           return EC;
         break;
       case bitc::TYPE_BLOCK_ID_NEW:
         if (std::error_code EC = parseTypeTable())
           return EC;
         break;
       case bitc::VALUE_SYMTAB_BLOCK_ID:
+        if (!SeenValueSymbolTable) {
+          // Either this is an old form VST without function index and an
+          // associated VST forward declaration record (which would have caused
+          // the VST to be jumped to and parsed before it was encountered
+          // normally in the stream), or there were no function blocks to
+          // trigger an earlier parsing of the VST.
+          assert(VSTOffset == 0 || FunctionsWithBodies.empty());
           if (std::error_code EC = parseValueSymbolTable())
             return EC;
           SeenValueSymbolTable = true;
+        } else {
+          // We must have had a VST forward declaration record, which caused
+          // the parser to jump to and parse the VST earlier.
+          assert(VSTOffset > 0);
+          if (Stream.SkipBlock())
+            return error("Invalid record");
+        }
         break;
       case bitc::CONSTANTS_BLOCK_ID:
         if (std::error_code EC = parseConstants())
           return EC;
         if (std::error_code EC = resolveGlobalAndAliasInits())
           return EC;
         break;
       case bitc::METADATA_BLOCK_ID:
case BitstreamEntry::SubBlock:
         // FunctionsWithBodies list.
         if (!SeenFirstFunctionBody) {
           std::reverse(FunctionsWithBodies.begin(), FunctionsWithBodies.end());
           if (std::error_code EC = globalCleanup())
             return EC;
           SeenFirstFunctionBody = true;
         }
 
+        if (VSTOffset > 0) {
+          // If we have a VST forward declaration record, make sure we
+          // parse the VST now if we haven't already. It is needed to
+          // set up the DeferredFunctionInfo vector for lazy reading.
+          if (!SeenValueSymbolTable) {
+            if (std::error_code EC =
+                    BitcodeReader::parseValueSymbolTable(VSTOffset))
+              return EC;
+            SeenValueSymbolTable = true;
+            return std::error_code();
+          } else {
+            // If we have a VST forward declaration record, but have already
+            // parsed the VST (just above, when the first function body was
+            // encountered here), then we are resuming the parse after
+            // materializing functions. The NextUnreadBit points to the start
+            // of the last function block recorded in the VST (set when
+            // parsing the VST function entries). Skip it.
+            if (Stream.SkipBlock())
+              return error("Invalid record");
+            continue;
+          }
+        }
+
+        // Support older bitcode files that did not have the function
+        // index in the VST, nor a VST forward declaration record.
+        // Build the DeferredFunctionInfo vector on the fly.
         if (std::error_code EC = rememberAndSkipFunctionBody())
           return EC;
         // Suspend parsing when we reach the function bodies. Subsequent
         // materialization calls will resume it when necessary. If the bitcode
         // file is old, the symbol table will be at the end instead and will not
         // have been seen yet. In this case, just finish the parse now.
         if (SeenValueSymbolTable) {
           NextUnreadBit = Stream.GetCurrentBitNo();
while (1) {
     }
     /// MODULE_CODE_PURGEVALS: [numvals]
     case bitc::MODULE_CODE_PURGEVALS:
       // Trim down the value list to the specified size.
       if (Record.size() < 1 || Record[0] > ValueList.size())
         return error("Invalid record");
       ValueList.shrinkTo(Record[0]);
       break;
+    /// MODULE_CODE_VSTOFFSET: [offset]
+    case bitc::MODULE_CODE_VSTOFFSET:
+      if (Record.size() < 1)
+        return error("Invalid record");
+      VSTOffset = Record[0];
+      break;
     }
     Record.clear();
   }
 }
 
 std::error_code
 BitcodeReader::parseBitcodeInto(std::unique_ptr<DataStreamer> Streamer,
                                 Module *M, bool ShouldLazyLoadMetadata) {
OutOfRecordLoop:
   return std::error_code();
 }
 
 /// Find the function body in the bitcode stream
 std::error_code BitcodeReader::findFunctionInStream(
     Function *F,
     DenseMap<Function *, uint64_t>::iterator DeferredFunctionInfoIterator) {
   while (DeferredFunctionInfoIterator->second == 0) {
+    // This is the fallback handling for the old format bitcode that
+    // didn't contain the function index in the VST. Assert if we end up
+    // here for the new format (which is the only time the VSTOffset would
+    // be non-zero).
+    assert(VSTOffset == 0);
     if (Stream.AtEndOfStream())
       return error("Could not find function in stream");
     // ParseModule will parse the next body in the stream and set its
     // position in the DeferredFunctionInfo map.
     if (std::error_code EC = parseModule(true))
       return EC;
   }
   return std::error_code();

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

for (const Comdat *C : VE.getComdats()) {
     Vals.push_back(Size);
     for (char Chr : C->getName())
       Vals.push_back((unsigned char)Chr);
     Stream.EmitRecord(bitc::MODULE_CODE_COMDAT, Vals, /*AbbrevToUse=*/0);
     Vals.clear();
   }
 }
 
-// Emit top-level description of module, including target triple, inline asm,
-// descriptors for global variables, and function prototype info.
-static void WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
+/// Write a record that will eventually hold the word offset of the
+/// module-level VST. For now the offset is 0, which will be backpatched
+/// after the real VST is written. Returns the bit offset to backpatch.
+static uint64_t WriteValueSymbolTableForwardDecl(const ValueSymbolTable &VST,
+                                                 BitstreamWriter &Stream) {
+  if (VST.empty()) return 0;
+
+  // Write a placeholder value in for the offset of the real VST,
+  // which is written after the function blocks so that it can include
+  // the offset of each function. The placeholder offset will be
+  // updated when the real VST is written.
+  BitCodeAbbrev *Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_VSTOFFSET));
+  // Blocks are 32-bit aligned, so we can use a 32-bit word offset to
+  // hold the real VST offset. Must use fixed instead of VBR as we don't
+  // know how many VBR chunks to reserve ahead of time.
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+  unsigned VSTOffsetAbbrev = Stream.EmitAbbrev(Abbv);
+
+  // Emit the placeholder
+  ArrayRef<unsigned> Vals = {llvm::bitc::MODULE_CODE_VSTOFFSET, 0};
+  Stream.EmitRecordWithAbbrev(VSTOffsetAbbrev, Vals);
+
+  // Compute and return the bit offset to the placeholder, which will be
+  // patched when the real VST is written. We can simply subtract the 32-bit
+  // fixed size from the current bit number to get the location to backpatch.
+  return Stream.GetCurrentBitNo() - 32;
+}
+
+/// Emit top-level description of module, including target triple, inline asm,
+/// descriptors for global variables, and function prototype info.
+/// Returns the bit offset to backpatch with the location of the real VST.
+static uint64_t WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
                                 BitstreamWriter &Stream) {
   // Emit various pieces of data attached to a module.
   if (!M->getTargetTriple().empty())
     WriteStringRecord(bitc::MODULE_CODE_TRIPLE, M->getTargetTriple(),
                       0/*TODO*/, Stream);
   const std::string &DL = M->getDataLayoutStr();
   if (!DL.empty())
     WriteStringRecord(bitc::MODULE_CODE_DATALAYOUT, DL, 0 /*TODO*/, Stream);
   if (!M->getModuleInlineAsm().empty())
for (const GlobalAlias &A : M->aliases()) {
     Vals.push_back(getEncodedVisibility(A));
     Vals.push_back(getEncodedDLLStorageClass(A));
     Vals.push_back(getEncodedThreadLocalMode(A));
     Vals.push_back(A.hasUnnamedAddr());
     unsigned AbbrevToUse = 0;
     Stream.EmitRecord(bitc::MODULE_CODE_ALIAS, Vals, AbbrevToUse);
     Vals.clear();
   }
+
+  uint64_t VSTOffsetPlaceholder =
+      WriteValueSymbolTableForwardDecl(M->getValueSymbolTable(), Stream);
+  return VSTOffsetPlaceholder;
 }
 
 static uint64_t GetOptimizationFlags(const Value *V) {
   uint64_t Flags = 0;
 
   if (const auto *OBO = dyn_cast<OverflowingBinaryOperator>(V)) {
     if (OBO->hasNoSignedWrap())
       Flags |= 1 << bitc::OBO_NO_SIGNED_WRAP;
if ((unsigned char)*C & 128)
       return SE_Fixed8;
   }
   if (isChar6)
     return SE_Char6;
   else
     return SE_Fixed7;
 }
 
-// Emit names for globals/functions etc.
-static void WriteValueSymbolTable(const ValueSymbolTable &VST,
-                                  const ValueEnumerator &VE,
-                                  BitstreamWriter &Stream) {
-  if (VST.empty()) return;
+/// Emit names for globals/functions etc. The VSTOffsetPlaceholder,
+/// BitcodeStartBit and FunctionIndex are only passed for the module-level
+/// VST, where we are including a function bitcode index and need to
+/// backpatch the VST forward declaration record.
+static void WriteValueSymbolTable(
+    const ValueSymbolTable &VST, const ValueEnumerator &VE,
+    BitstreamWriter &Stream, uint64_t VSTOffsetPlaceholder = 0,
+    uint64_t BitcodeStartBit = 0,
+    DenseMap<const Function *, uint64_t> *FunctionIndex = nullptr) {
+  if (VST.empty()) {
+    // WriteValueSymbolTableForwardDecl should have returned early as
+    // well. Ensure this handling remains in sync by asserting that
+    // the placeholder offset is not set.
+    assert(VSTOffsetPlaceholder == 0);
+    return;
+  }
+
+  if (VSTOffsetPlaceholder > 0) {
+    // Get the offset of the VST we are writing, and backpatch it into
+    // the VST forward declaration record.
+    uint64_t VSTOffset = Stream.GetCurrentBitNo();
+    // The BitcodeStartBit was the stream offset of the actual bitcode
+    // (e.g. excluding any initial darwin header).
+    VSTOffset -= BitcodeStartBit;
+    assert((VSTOffset & 31) == 0 && "VST block not 32-bit aligned");
+    Stream.BackpatchWord(VSTOffsetPlaceholder, VSTOffset / 32);
+  }
+
   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
 
+  // For the module-level VST, add abbrev Ids for the VST_CODE_FNENTRY
+  // records, which are not used in the per-function VSTs.
+  unsigned FnEntry8BitAbbrev;
+  unsigned FnEntry7BitAbbrev;
+  unsigned FnEntry6BitAbbrev;
+  if (VSTOffsetPlaceholder > 0) {
+    // 8-bit fixed-width VST_FNENTRY function strings.
+    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
+    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));  // value id
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));  // funcoffset
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
+    FnEntry8BitAbbrev = Stream.EmitAbbrev(Abbv);
+
+    // 7-bit fixed width VST_FNENTRY function strings.
+    Abbv = new BitCodeAbbrev();
+    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));  // value id
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));  // funcoffset
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
+    FnEntry7BitAbbrev = Stream.EmitAbbrev(Abbv);
+
+    // 6-bit char6 VST_FNENTRY function strings.
+    Abbv = new BitCodeAbbrev();
+    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));  // value id
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));  // funcoffset
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
+    FnEntry6BitAbbrev = Stream.EmitAbbrev(Abbv);
+  }
+
   // FIXME: Set up the abbrev, we know how many values there are!
   // FIXME: We know if the type names can use 7-bit ascii.
   SmallVector<unsigned, 64> NameVals;
 
   for (const ValueName &Name : VST) {
-
     // Figure out the encoding to use for the name.
     StringEncoding Bits =
         getStringEncoding(Name.getKeyData(), Name.getKeyLength());
 
     unsigned AbbrevToUse = VST_ENTRY_8_ABBREV;
+    NameVals.push_back(VE.getValueID(Name.getValue()));
+
+    Function *F = dyn_cast<Function>(Name.getValue());
+    if (!F) {
+      // If value is an alias, need to get the aliased base object to
+      // see if it is a function.
+      auto *GA = dyn_cast<GlobalAlias>(Name.getValue());
+      if (GA && GA->getBaseObject())
+        F = dyn_cast<Function>(GA->getBaseObject());
+    }
 
     // VST_ENTRY:   [valueid, namechar x N]
+    // VST_FNENTRY: [valueid, funcoffset, namechar x N]
     // VST_BBENTRY: [bbid, namechar x N]
     unsigned Code;
     if (isa<BasicBlock>(Name.getValue())) {
       Code = bitc::VST_CODE_BBENTRY;
       if (Bits == SE_Char6)
         AbbrevToUse = VST_BBENTRY_6_ABBREV;
+    } else if (F && !F->isDeclaration()) {
+      // Must be the module-level VST, where we pass in the Index and
+      // have a VSTOffsetPlaceholder. The function-level VST should not
+      // contain any Function symbols.
+      assert(FunctionIndex);
+      assert(VSTOffsetPlaceholder > 0);
+
+      // Save the word offset of the function (from the start of the
+      // actual bitcode written to the stream).
+      assert(FunctionIndex->count(F) == 1);
+      uint64_t BitcodeIndex = (*FunctionIndex)[F] - BitcodeStartBit;
+      assert((BitcodeIndex & 31) == 0 && "function block not 32-bit aligned");
+      NameVals.push_back(BitcodeIndex / 32);
+
+      Code = bitc::VST_CODE_FNENTRY;
+      AbbrevToUse = FnEntry8BitAbbrev;
+      if (Bits == SE_Char6)
+        AbbrevToUse = FnEntry6BitAbbrev;
+      else if (Bits == SE_Fixed7)
+        AbbrevToUse = FnEntry7BitAbbrev;
     } else {
       Code = bitc::VST_CODE_ENTRY;
       if (Bits == SE_Char6)
         AbbrevToUse = VST_ENTRY_6_ABBREV;
       else if (Bits == SE_Fixed7)
         AbbrevToUse = VST_ENTRY_7_ABBREV;
     }
 
-    NameVals.push_back(VE.getValueID(Name.getValue()));
     for (const char *P = Name.getKeyData(),
          *E = Name.getKeyData()+Name.getKeyLength(); P != E; ++P)
       NameVals.push_back((unsigned char)*P);
 
     // Emit the finished record.
     Stream.EmitRecord(Code, NameVals, AbbrevToUse);
     NameVals.clear();
   }
while (hasMore()) {
     WriteUseList(VE, std::move(VE.UseListOrders.back()), Stream);
     VE.UseListOrders.pop_back();
   }
   Stream.ExitBlock();
 }
 
 /// WriteFunction - Emit a function body to the module stream.
 static void WriteFunction(const Function &F, ValueEnumerator &VE,
-                          BitstreamWriter &Stream) {
+                          BitstreamWriter &Stream,
+                          DenseMap<const Function *, uint64_t> &FunctionIndex) {
+  // Save the bitcode index of the start of this function block for recording
+  // in the VST.
+  uint64_t BitcodeIndex = Stream.GetCurrentBitNo();
+  FunctionIndex[&F] = BitcodeIndex;
+
   Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 4);
   VE.incorporateFunction(F);
 
   SmallVector<unsigned, 64> Vals;
 
   // Emit the number of basic blocks, so the reader can create them ahead of
   // time.
   Vals.push_back(VE.getBasicBlocks().size());
if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID, Abbv) !=
       llvm_unreachable("Unexpected abbrev ordering!");
   }
 
   Stream.ExitBlock();
 }
 
 /// WriteModule - Emit the specified module to the bitstream.
 static void WriteModule(const Module *M, BitstreamWriter &Stream,
-                        bool ShouldPreserveUseListOrder) {
+                        bool ShouldPreserveUseListOrder,
+                        uint64_t BitcodeStartBit) {
   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
 
   SmallVector<unsigned, 1> Vals;
   unsigned CurVersion = 1;
   Vals.push_back(CurVersion);
   Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
 
   // Analyze the module, enumerating globals, functions, etc.
static void WriteModule(const Module *M, BitstreamWriter &Stream,
 
   // Emit information describing all of the types in the module.
   WriteTypeTable(VE, Stream);
 
   writeComdats(VE, Stream);
 
   // Emit top-level description of module, including target triple, inline asm,
   // descriptors for global variables, and function prototype info.
-  WriteModuleInfo(M, VE, Stream);
+  uint64_t VSTOffsetPlaceholder = WriteModuleInfo(M, VE, Stream);
 
   // Emit constants.
   WriteModuleConstants(VE, Stream);
 
   // Emit metadata.
   WriteModuleMetadata(M, VE, Stream);
 
   // Emit metadata.
   WriteModuleMetadataStore(M, Stream);
 
-  // Emit names for globals/functions etc.
-  WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream);
-
   // Emit module-level use-lists.
   if (VE.shouldPreserveUseListOrder())
     WriteUseListBlock(nullptr, VE, Stream);
 
   // Emit function bodies.
+  DenseMap<const Function *, uint64_t> FunctionIndex;
   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F)
     if (!F->isDeclaration())
-      WriteFunction(*F, VE, Stream);
+      WriteFunction(*F, VE, Stream, FunctionIndex);
+
+  WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream,
+                        VSTOffsetPlaceholder, BitcodeStartBit, &FunctionIndex);
 
   Stream.ExitBlock();
 }
 
 /// EmitDarwinBCHeader - If generating a bc file on darwin, we have to emit a
 /// header and trailer to make it compatible with the system archiver.  To do
 /// this we emit the following header, and then emit a trailer that pads the
 /// file out to be a multiple of 16 bytes.
void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out,
   // header.
   Triple TT(M->getTargetTriple());
   if (TT.isOSDarwin())
     Buffer.insert(Buffer.begin(), DarwinBCHeaderSize, 0);
 
   // Emit the module into the buffer.
   {
     BitstreamWriter Stream(Buffer);
+    // Save the start bit of the actual bitcode, in case there is space
+    // saved at the start for the darwin header above. The reader stream
+    // will start at the bitcode, and we need the offset of the VST
+    // to line up.
+    uint64_t BitcodeStartBit = Stream.GetCurrentBitNo();
 
     // Emit the file header.
     Stream.Emit((unsigned)'B', 8);
     Stream.Emit((unsigned)'C', 8);
     Stream.Emit(0x0, 4);
     Stream.Emit(0xC, 4);
     Stream.Emit(0xE, 4);
     Stream.Emit(0xD, 4);
 
     // Emit the module.
-    WriteModule(M, Stream, ShouldPreserveUseListOrder);
+    WriteModule(M, Stream, ShouldPreserveUseListOrder, BitcodeStartBit);
   }
 
   if (TT.isOSDarwin())
     EmitDarwinBCHeaderAndTrailer(Buffer, TT);
 
   // Write the generated bitstream to "Out".
   Out.write((char*)&Buffer.front(), Buffer.size());
 }

llvm/trunk/test/Bitcode/vst-forward-declaration.ll

+; RUN: llvm-as < %s | llvm-bcanalyzer -dump | FileCheck %s -check-prefix=BC
+; Check for VST forward declaration record and VST function index records.
+
+; BC: <VSTOFFSET
+; BC: <FNENTRY
+; BC: <FNENTRY
+
+; RUN: llvm-as < %s | llvm-dis | FileCheck %s
+; Check that this round-trips correctly.
+
+; ModuleID = '<stdin>'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: define i32 @foo()
+
+; Function Attrs: nounwind uwtable
+define i32 @foo() #0 {
+entry:
+  ret i32 1
+}
+
+; CHECK: define i32 @bar(i32 %x)
+
+; Function Attrs: nounwind uwtable
+define i32 @bar(i32 %x) #0 {
+entry:
+  ret i32 %x
+}

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

default: return nullptr;
       STRINGIFY_CODE(MODULE_CODE, ASM)
       STRINGIFY_CODE(MODULE_CODE, SECTIONNAME)
       STRINGIFY_CODE(MODULE_CODE, DEPLIB) // FIXME: Remove in 4.0
       STRINGIFY_CODE(MODULE_CODE, GLOBALVAR)
       STRINGIFY_CODE(MODULE_CODE, FUNCTION)
       STRINGIFY_CODE(MODULE_CODE, ALIAS)
       STRINGIFY_CODE(MODULE_CODE, PURGEVALS)
       STRINGIFY_CODE(MODULE_CODE, GCNAME)
+      STRINGIFY_CODE(MODULE_CODE, VSTOFFSET)
     }
   case bitc::PARAMATTR_BLOCK_ID:
     switch (CodeID) {
     default: return nullptr;
     // FIXME: Should these be different?
     case bitc::PARAMATTR_CODE_ENTRY_OLD: return "ENTRY";
     case bitc::PARAMATTR_CODE_ENTRY:     return "ENTRY";
     case bitc::PARAMATTR_GRP_CODE_ENTRY: return "ENTRY";
default: return nullptr;
       STRINGIFY_CODE(FUNC_CODE, DEBUG_LOC)
       STRINGIFY_CODE(FUNC_CODE, INST_GEP)
     }
   case bitc::VALUE_SYMTAB_BLOCK_ID:
     switch (CodeID) {
     default: return nullptr;
     STRINGIFY_CODE(VST_CODE, ENTRY)
     STRINGIFY_CODE(VST_CODE, BBENTRY)
+    STRINGIFY_CODE(VST_CODE, FNENTRY)
     }
   case bitc::METADATA_ATTACHMENT_ID:
     switch(CodeID) {
     default:return nullptr;
       STRINGIFY_CODE(METADATA, ATTACHMENT)
     }
   case bitc::METADATA_BLOCK_ID:
     switch(CodeID) {