Add a module Hash in the bitcode and the combined index.

[mehdi_amini]

Summary

This is the equivalent of a "build-id". The module that is written is hashed on the fly, and the last record will be the hash itself.
It is intended to be used for ThinLTO incremental build, so it is included along with each module entry in the combined index. The function importer will compute the set of imports and where they are coming from. Then before the actual import, the hashes of all modules that we are about to import from are combined together to produce a single hash. This hash identifies uniquely the module we're about to create with the importing and thus can be used as a key for a cache supporting incremental build.

The SHA1 implementation is not very optimized, on the performance part WriteModule() takes 1.9s when disabled and 2.1s when enabled (writing LTO llvm-tblgen with full dbg-info).
Note that is it only performed when we emit the summary information, i.e. only with ThinLTO and only by the frontend. The link stage is just consuming this information.

[• rafael]

lib/Bitcode/Writer/BitcodeWriter.cpp

3211

This produces different results in 32 and 64 bit machines, no?

[mehdi_amini]

Disable by default...

[mehdi_amini]

lib/Bitcode/Writer/BitcodeWriter.cpp

3211

Uh, dunno, is it a property of hash_combine_range?

[mehdi_amini]

Minor bug fix (forgot to nullptr check)

[mehdi_amini]

Insert the full 160bits of the SHA1 in the bitcode. Also add a unittests.

[vsk]

Have you considered adding a textual-IR representation of the module hash?

I can think of two uses for it: 1) we can add -module-summary to the run line in compatibility.ll and get additional coverage, 2) we can debug any future hash-related issues by looking at textual IR.

[mehdi_amini]

I would be quite tricky to add the hash at the IR level, because it requires to generate bitcode to get a hash any time you want to print textual IR.

[mehdi_amini]

Add missing Inputs/ for the lit test.

[tejohnson]

Can we make generation of the hashes conditional? They aren't needed if a module cache is not being used for incremental rebuilds. I anticipate we will use a different mechanism with our distributed build system, for example. It is simple to suppress generation of the new MODULE_CODE_HASH record, but would be good to also suppress the larger module string table as well. Maybe have a separate set of record types for when we want to include the hashes?

include/llvm/IR/ModuleSummaryIndex.h

234

Why not use uint32_t? That seems to be what is used in SHA1.h.

311–312

No longer returning an iterator. Ditto for non-const method below.

356

Comment needs update: "with the given Hash". Also, is it possible to combine this with the above using a default argument value of {{0}}?

lib/Bitcode/Reader/BitcodeReader.cpp

5649

5*i32? Assert below checking for 5 values. And 32*5==160, so that seems like the right number. And update the description of this record accordingly in LLVMBitCodes.h where it just says [unsigned].

5929

Why is this one 6*i32 whereas the MODULE_CODE_HASH is only expected to have 5 i32 (according to implementation, comment above incorrectly says it is 6*i32)?

lib/Bitcode/Writer/BitcodeWriter.cpp

2845

What is the added VBR8 here and in the 6-bit case below? I don't see anything else being written. And it isn't in the 8-bit case above.

3209

5*i32?

3237

Please make this conditional so it isn't generating a hash if we aren't using a module cache.

3292

ditto.

test/Bitcode/Inputs/module_hash.ll

5 ↗

(On Diff #51257)

Fix?

test/Bitcode/module_hash.ll

6 ↗

(On Diff #51257)

Won't these values change frequently as the compiler changes and generates slightly different bitcode? How about just checking if the per module values match the combined index values via FileCheck variables/pattern matching?

20 ↗

(On Diff #51257)

Fix?

[llvm-commits]

We can make it conditional (with a clang flag?), but the desired behavior is to be able to decide on enabling/disabling the caching at link time, so any bitcode static archive distributed would need to have a hash embedded. The user friendly choice would be to enabled it by *default* when -flto=thing, and an explicit option to disable it.

[tejohnson]

In D18213#380319, @llvm-commits wrote:

We can make it conditional (with a clang flag?), but the desired behavior is to be able to decide on enabling/disabling the caching at link time, so any bitcode static archive distributed would need to have a hash embedded. The user friendly choice would be to enabled it by *default* when -flto=thing, and an explicit option to disable it.

I'm less concerned about the default than just having a way to disable it.

[mehdi_amini]

Update after Teresa's comments

[mehdi_amini]

Thanks for the review Teresa, I updated accordingly (but for the FileCheck, see comment below).

test/Bitcode/module_hash.ll

6 ↗

(On Diff #51257)

The hope is that a "void foo()" won't change much, but yeah it's absolutely not nice.
What you suggest is fine for testing that we correctly read and propagate to the combined index.
HoweverI'm not comfortable not checking a value, because we lose coverage for the production of the hash. I.e. writing only zero in the first place would make the test pass :(
Would it be enough to add a comment here saying that is fine updating the value is someone change the IR/bitcode?
I'm gonna CC Duncan for an opinion on this.

[mehdi_amini]

Typo

[mehdi_amini]

Forgot to remote the SHA1 for the MST_ENTRY abbrev.

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

311–314

s/Table of module/Table of modules/ (here and below)

351

Now returns iterator not StringRef.

lib/Bitcode/Reader/BitcodeReader.cpp

5941

In order for this check to work after the first module id + hash is encountered, LastSeenModulePath needs to be set to the end() after it is used in the for loop below. Otherwise it will silently overwrite the earlier module path's values if not preceded by a new module path.

lib/Bitcode/Writer/BitcodeWriter.cpp

2857–2868

"Optionally emitted after..."

[mehdi_amini]

Taking comments into account.

[tejohnson]

Needs test with new llvm-as option then fed through llvm-bcanalyzer to trigger new matching check.

lib/Bitcode/Reader/BitcodeReader.cpp

5949

s/unexpectingly/unexpectedly/

[mehdi_amini]

The test are checking for "match" in the output of llvm-bcanalyzer

[tejohnson]

In D18213#386848, @joker.eph wrote:

The test are checking for "match" in the output of llvm-bcanalyzer

Which test? Is there a new test missing from the patch? The hash generation is off by default so I assume you need to add a new one (or modify an existing) to pass the new -module-hash option to llvm-as. Otherwise I don't think the checking in llvm-bcanalyzer will ever kick in.

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

599

Is the MODULE_CODE_HASH ever expected outside a module block? If not, can the first part of the if be turned into an assert inside the if body?

[mehdi_amini]

Add back the test, I lost it from the commit at some point

[mehdi_amini]

test/Bitcode/module_hash.ll

7 ↗

(On Diff #51672)

Came up with a different approach!

1. llvm-bcanalyzer will re-hash and check for mismatch
2. using a temporary file to collect the hash, I check that whatever is in the module is correctly propagated into the combined index.

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

599

I think the code a reused across Blocks, so you need to know that you are in a module block to interpret the code as being the hash. Did I misunderstand your point?

[mehdi_amini]

s/unexpectingly/unexpectedly/

[tejohnson]

test/Bitcode/module_hash.ll

7 ↗

(On Diff #51672)

Weird, I still don't see the test when I go to http://reviews.llvm.org/D18213, only when I click on this comment which opens up http://reviews.llvm.org/D18213?id=51672#inline-155131.

In any case, this sounds good. The version of the test I am seeing doesn't implement it yet (assume that is WIP).

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

630

Ok, got it, checking both does make sense.

[mehdi_amini]

Try to add the test, if it still does not work I'll make some coffee first...

[mehdi_amini]

I'm confident this one will work...

[tejohnson]

In D18213#386957, @joker.eph wrote:

I'm confident this one will work...

Yep, it is there now!

LGTM, but as Duncan suggested, do the NFC commit of the clang-formatted LLVMBitCodes.h first.

[mehdi_amini]

r265111

include/llvm/Bitcode/BitstreamReader.h

void init(BitstreamReader *R) {
     CurCodeSize = 2;
   }
 
   void freeState();
 
   using SimpleBitstreamCursor::canSkipToPos;
   using SimpleBitstreamCursor::AtEndOfStream;
   using SimpleBitstreamCursor::GetCurrentBitNo;
+  using SimpleBitstreamCursor::getCurrentByteNo;
+  using SimpleBitstreamCursor::getPointerToByte;
   using SimpleBitstreamCursor::getBitStreamReader;
   using SimpleBitstreamCursor::JumpToBit;
   using SimpleBitstreamCursor::fillCurWord;
   using SimpleBitstreamCursor::Read;
   using SimpleBitstreamCursor::ReadVBR;
   using SimpleBitstreamCursor::ReadVBR64;
 
   /// Return the number of bits used to encode an abbrev #.

include/llvm/Bitcode/LLVMBitCodes.h

 ///
 /// LLVM guarantees in a major release that a minor release can read bitcode
 /// generated by previous minor releases. We translate this by making the reader
 /// accepting only bitcode with the same epoch, except for the X.0 release which
 /// also accepts N-1.
 enum { BITCODE_CURRENT_EPOCH = 0 };
 
   /// 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]
-    MODULE_CODE_ASM         = 4,    // ASM:         [strchr x N]
-    MODULE_CODE_SECTIONNAME = 5,    // SECTIONNAME: [strchr x N]
+  MODULE_CODE_VERSION = 1,     // VERSION:     [version#]
+  MODULE_CODE_TRIPLE = 2,      // TRIPLE:      [strchr x N]
+  MODULE_CODE_DATALAYOUT = 3,  // DATALAYOUT:  [strchr x N]
+  MODULE_CODE_ASM = 4,         // ASM:         [strchr x N]
+  MODULE_CODE_SECTIONNAME = 5, // SECTIONNAME: [strchr x N]
 
-    // FIXME: Remove DEPLIB in 4.0.
-    MODULE_CODE_DEPLIB      = 6,    // DEPLIB:      [strchr x N]
+  MODULE_CODE_DEPLIB = 6, // DEPLIB:      [strchr x N]
 
-    // GLOBALVAR: [pointer type, isconst, initid,
-    //             linkage, alignment, section, visibility, threadlocal]
-    MODULE_CODE_GLOBALVAR   = 7,
+  MODULE_CODE_GLOBALVAR = 7,
 
-    // FUNCTION:  [type, callingconv, isproto, linkage, paramattrs, alignment,
-    //             section, visibility, gc, unnamed_addr]
-    MODULE_CODE_FUNCTION    = 8,
+  MODULE_CODE_FUNCTION = 8,
 
-    // ALIAS: [alias type, aliasee val#, linkage, visibility]
-    MODULE_CODE_ALIAS_OLD   = 9,
+  MODULE_CODE_ALIAS_OLD = 9,
 
-    // MODULE_CODE_PURGEVALS: [numvals]
-    MODULE_CODE_PURGEVALS   = 10,
+  MODULE_CODE_PURGEVALS = 10,
 
-    MODULE_CODE_GCNAME      = 11,  // GCNAME: [strchr x N]
-    MODULE_CODE_COMDAT      = 12,  // COMDAT: [selection_kind, name]
+  MODULE_CODE_GCNAME = 11, // GCNAME: [strchr x N]
+  MODULE_CODE_COMDAT = 12, // COMDAT: [selection_kind, name]
 
-    MODULE_CODE_VSTOFFSET   = 13,  // VSTOFFSET: [offset]
+  MODULE_CODE_VSTOFFSET = 13, // VSTOFFSET: [offset]
 
-    // ALIAS: [alias value type, addrspace, aliasee val#, linkage, visibility]
-    MODULE_CODE_ALIAS       = 14,
+  MODULE_CODE_ALIAS = 14,
 
-    MODULE_CODE_METADATA_VALUES_UNUSED = 15,
 
-    // SOURCE_FILENAME: [namechar x N]
-    MODULE_CODE_SOURCE_FILENAME = 16,
-  };
+
+  // HASH: [5*i32]
+  MODULE_CODE_HASH = 17,
 
   /// 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,
                                    //         paramidx1, attrgrp1, ...]
enum ValueSymtabCodes {
     // VST_COMBINED_GVDEFENTRY: [valueid, sumoffset, guid]
     VST_CODE_COMBINED_GVDEFENTRY = 4,
     // VST_COMBINED_ENTRY: [valueid, refguid]
     VST_CODE_COMBINED_ENTRY = 5
   };
 
   // The module path symbol table only has one code (MST_CODE_ENTRY).
   enum ModulePathSymtabCodes {
-    MST_CODE_ENTRY   = 1,  // MST_ENTRY: [modid, namechar x N]
+    MST_CODE_ENTRY = 1, // MST_ENTRY: [modid, namechar x N]
+    MST_CODE_HASH = 2,  // MST_HASH:  [5*i32]
   };
 
   // The summary section uses different codes in the per-module
   // and combined index cases.
   enum GlobalValueSummarySymtabCodes {
     // PERMODULE: [valueid, linkage, instcount, numrefs, numrefs x valueid,
     //             n x (valueid, callsitecount)]
     FS_PERMODULE = 1,

include/llvm/Bitcode/ReaderWriter.h

namespace llvm {
   /// If \c ShouldPreserveUseListOrder, encode the use-list order for each \a
   /// Value in \c M.  These will be reconstructed exactly when \a M is
   /// deserialized.
   ///
   /// If \c EmitSummaryIndex, emit the module's summary index (currently
   /// for use in ThinLTO optimization).
   void WriteBitcodeToFile(const Module *M, raw_ostream &Out,
                           bool ShouldPreserveUseListOrder = false,
-                          bool EmitSummaryIndex = false);
+                          bool EmitSummaryIndex = false,
+                          bool GenerateHash = false);
 
   /// Write the specified module summary index to the given raw output stream,
   /// where it will be written in a new bitcode block. This is used when
   /// writing the combined index file for ThinLTO.
   void WriteIndexToFile(const ModuleSummaryIndex &Index, raw_ostream &Out);
 
   /// isBitcodeWrapper - Return true if the given bytes are the magic bytes
   /// for an LLVM IR bitcode wrapper.

include/llvm/IR/ModuleSummaryIndex.h

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 
+#include <array>
+
 namespace llvm {
 
 /// \brief Class to accumulate and hold information about a callee.
 struct CalleeInfo {
   /// The static number of callsites calling corresponding function.
   unsigned CallsiteCount;
   /// The cumulative profile count of calls to corresponding function
   /// (if using PGO, otherwise 0).
public:
 
   /// Get the bitcode index recorded for this value symbol table entry.
   uint64_t bitcodeIndex() const { return BitcodeIndex; }
 
   /// Set the bitcode index recorded for this value symbol table entry.
   void setBitcodeIndex(uint64_t Offset) { BitcodeIndex = Offset; }
 };
 
+/// 160 bits SHA1
+typedef std::array<uint32_t, 5> ModuleHash;
+
 /// List of global value info structures for a particular value held
 /// in the GlobalValueMap. Requires a vector in the case of multiple
 /// COMDAT values of the same name.
 typedef std::vector<std::unique_ptr<GlobalValueInfo>> GlobalValueInfoList;
 
 /// Map from global value GUID to corresponding info structures.
 /// Use a std::map rather than a DenseMap since it will likely incur
 /// less overhead, as the value type is not very small and the size
 /// of the map is unknown, resulting in inefficiencies due to repeated
 /// insertions and resizing.
 typedef std::map<uint64_t, GlobalValueInfoList> GlobalValueInfoMapTy;
 
 /// Type used for iterating through the global value info map.
 typedef GlobalValueInfoMapTy::const_iterator const_globalvalueinfo_iterator;
 typedef GlobalValueInfoMapTy::iterator globalvalueinfo_iterator;
 
 /// String table to hold/own module path strings, which additionally holds the
-/// module ID assigned to each module during the plugin step. The StringMap
-/// makes a copy of and owns inserted strings.
-typedef StringMap<uint64_t> ModulePathStringTableTy;
+/// module ID assigned to each module during the plugin step, as well as a hash
+/// of the module. The StringMap makes a copy of and owns inserted strings.
+typedef StringMap<std::pair<uint64_t, ModuleHash>> ModulePathStringTableTy;
 
 /// Class to hold module path string table and global value map,
 /// and encapsulate methods for operating on them.
 class ModuleSummaryIndex {
 private:
   /// Map from value name to list of information instances for values of that
   /// name (may be duplicates in the COMDAT case, e.g.).
   GlobalValueInfoMapTy GlobalValueMap;
void addGlobalValueInfo(StringRef ValueName,
     GlobalValueMap[GlobalValue::getGUID(ValueName)].push_back(std::move(Info));
   }
 
   /// Add a global value info for a value of the given GUID.
   void addGlobalValueInfo(uint64_t ValueGUID,
                           std::unique_ptr<GlobalValueInfo> Info) {
     GlobalValueMap[ValueGUID].push_back(std::move(Info));
   }
 
-  /// Table of modules, containing an id.
-  const StringMap<uint64_t> &modulePaths() const {
+  /// Table of modules, containing module hash and id.
+  const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
     return ModulePathStringTable;
   }
 
-  /// Table of modules, containing an id.
-  StringMap<uint64_t> &modulePaths() { return ModulePathStringTable; }
+  /// Table of modules, containing hash and id.
+  StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
+    return ModulePathStringTable;
+  }
 
   /// Get the module ID recorded for the given module path.
   uint64_t getModuleId(const StringRef ModPath) const {
-    return ModulePathStringTable.lookup(ModPath);
+    return ModulePathStringTable.lookup(ModPath).first;
+  }
+
+  /// Get the module SHA1 hash recorded for the given module path.
+  const ModuleHash &getModuleHash(const StringRef ModPath) const {
+    auto It = ModulePathStringTable.find(ModPath);
+    assert(It != ModulePathStringTable.end() && "Module not registered");
+    return It->second.second;
   }
 
   /// Add the given per-module index into this module index/summary,
   /// assigning it the given module ID. Each module merged in should have
   /// a unique ID, necessary for consistent renaming of promoted
   /// static (local) variables.
   void mergeFrom(std::unique_ptr<ModuleSummaryIndex> Other,
                  uint64_t NextModuleId);
 
   /// Convenience method for creating a promoted global name
   /// for the given value name of a local, and its original module's ID.
   static std::string getGlobalNameForLocal(StringRef Name, uint64_t ModId) {
     SmallString<256> NewName(Name);
     NewName += ".llvm.";
     raw_svector_ostream(NewName) << ModId;
     return NewName.str();
   }
 
-  /// Add a new module path, mapped to the given module Id, and return StringRef
-  /// owned by string table map.
-  StringRef addModulePath(StringRef ModPath, uint64_t ModId) {
-    return ModulePathStringTable.insert(std::make_pair(ModPath, ModId))
-        .first->first();
+  /// Add a new module path with the given \p Hash, mapped to the given \p
+  /// ModID, and return an iterator to the entry in the index.
+  ModulePathStringTableTy::iterator
+  addModulePath(StringRef ModPath, uint64_t ModId,
+                ModuleHash Hash = ModuleHash{{0}}) {
+    return ModulePathStringTable.insert(std::make_pair(
+                                            ModPath,
+                                            std::make_pair(ModId, Hash))).first;
   }
 
   /// Check if the given Module has any functions available for exporting
   /// in the index. We consider any module present in the ModulePathStringTable
   /// to have exported functions.
   bool hasExportedFunctions(const Module &M) const {
     return ModulePathStringTable.count(M.getModuleIdentifier());
   }

lib/Bitcode/Reader/BitcodeReader.cpp

case BitstreamEntry::SubBlock:
         break;
       case bitc::MODULE_STRTAB_BLOCK_ID:
         if (std::error_code EC = parseModuleStringTable())
           return EC;
         break;
       }
       continue;
 
-    case BitstreamEntry::Record:
-      // Once we find the last record of interest, skip the rest.
-      if (VSTOffset > 0)
-        Stream.skipRecord(Entry.ID);
-      else {
+    case BitstreamEntry::Record: {
         Record.clear();
         auto BitCode = Stream.readRecord(Entry.ID, Record);
         switch (BitCode) {
         default:
           break; // Default behavior, ignore unknown content.
         /// MODULE_CODE_SOURCE_FILENAME: [namechar x N]
         case bitc::MODULE_CODE_SOURCE_FILENAME: {
           SmallString<128> ValueName;
           if (convertToString(Record, 0, ValueName))
             return error("Invalid record");
           SourceFileName = ValueName.c_str();
           break;
         }
+        /// MODULE_CODE_HASH: [5*i32]
+        case bitc::MODULE_CODE_HASH: {
+          if (Record.size() != 5)
+            return error("Invalid hash length " + Twine(Record.size()).str());
+          if (!TheIndex)
+            break;
+          if (TheIndex->modulePaths().empty())
+            // Does not have any summary emitted.
+            break;
+          if (TheIndex->modulePaths().size() != 1)
+            return error("Don't expect multiple modules defined?");
+          auto &Hash = TheIndex->modulePaths().begin()->second.second;
+          int Pos = 0;
+          for (auto &Val : Record) {
+            assert(!(Val >> 32) && "Unexpected high bits set");
+            Hash[Pos++] = Val;
+          }
+          break;
+        }
         /// MODULE_CODE_VSTOFFSET: [offset]
         case bitc::MODULE_CODE_VSTOFFSET:
           if (Record.size() < 1)
             return error("Invalid record");
           VSTOffset = Record[0];
           break;
         // GLOBALVAR: [pointer type, isconst, initid,
         //             linkage, alignment, section, visibility, threadlocal,
case bitc::FS_PERMODULE_PROFILE: {
       std::unique_ptr<FunctionSummary> FS = llvm::make_unique<FunctionSummary>(
           getDecodedLinkage(RawLinkage), InstCount);
       // The module path string ref set in the summary must be owned by the
       // index's module string table. Since we don't have a module path
       // string table section in the per-module index, we create a single
       // module path string table entry with an empty (0) ID to take
       // ownership.
       FS->setModulePath(
-          TheIndex->addModulePath(Buffer->getBufferIdentifier(), 0));
+          TheIndex->addModulePath(Buffer->getBufferIdentifier(), 0)->first());
       static int RefListStartIndex = 4;
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
       for (unsigned I = 4, E = CallGraphEdgeStartIndex; I != E; ++I) {
         unsigned RefValueId = Record[I];
         uint64_t RefGUID = getGUIDFromValueId(RefValueId);
         FS->addRefEdge(RefGUID);
while (1) {
     }
     // FS_PERMODULE_GLOBALVAR_INIT_REFS: [valueid, linkage, n x valueid]
     case bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS: {
       unsigned ValueID = Record[0];
       uint64_t RawLinkage = Record[1];
       std::unique_ptr<GlobalVarSummary> FS =
           llvm::make_unique<GlobalVarSummary>(getDecodedLinkage(RawLinkage));
       FS->setModulePath(
-          TheIndex->addModulePath(Buffer->getBufferIdentifier(), 0));
+          TheIndex->addModulePath(Buffer->getBufferIdentifier(), 0)->first());
       for (unsigned I = 2, E = Record.size(); I != E; ++I) {
         unsigned RefValueId = Record[I];
         uint64_t RefGUID = getGUIDFromValueId(RefValueId);
         FS->addRefEdge(RefGUID);
       }
       uint64_t GUID = getGUIDFromValueId(ValueID);
       auto InfoList = TheIndex->findGlobalValueInfoList(GUID);
       assert(InfoList != TheIndex->end() &&

 // This populates the ModulePathStringTable map in the index.
 std::error_code ModuleSummaryIndexBitcodeReader::parseModuleStringTable() {
   if (Stream.EnterSubBlock(bitc::MODULE_STRTAB_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
 
   SmallString<128> ModulePath;
+  ModulePathStringTableTy::iterator LastSeenModulePath;
   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:
       return std::error_code();
     case BitstreamEntry::Record:
       // The interesting case.
       break;
     }
 
     Record.clear();
     switch (Stream.readRecord(Entry.ID, Record)) {
     default: // Default behavior: ignore.
       break;
     case bitc::MST_CODE_ENTRY: {
       // MST_ENTRY: [modid, namechar x N]
+      uint64_t ModuleId = Record[0];
+
       if (convertToString(Record, 1, ModulePath))
         return error("Invalid record");
-      uint64_t ModuleId = Record[0];
-      StringRef ModulePathInMap = TheIndex->addModulePath(ModulePath, ModuleId);
-      ModuleIdMap[ModuleId] = ModulePathInMap;
+
+      LastSeenModulePath = TheIndex->addModulePath(ModulePath, ModuleId);
+      ModuleIdMap[ModuleId] = LastSeenModulePath->first();
+
       ModulePath.clear();
       break;
     }
+    /// MST_CODE_HASH: [5*i32]
+    case bitc::MST_CODE_HASH: {
+      if (Record.size() != 5)
+        return error("Invalid hash length " + Twine(Record.size()).str());
+      if (LastSeenModulePath == TheIndex->modulePaths().end())
+        return error("Invalid hash that does not follow a module path");
+      int Pos = 0;
+      for (auto &Val : Record) {
+        assert(!(Val >> 32) && "Unexpected high bits set");
+        LastSeenModulePath->second.second[Pos++] = Val;
+      }
+      // Reset the LastSeenModulePath to avoid overriding the hash entry
+      // unexpectingly
+      LastSeenModulePath = TheIndex->modulePaths().end();
+      break;
+    }
     }
   }
   llvm_unreachable("Exit infinite loop");
 }
 
 // Parse the function info index from the bitcode streamer into the given index.
 std::error_code ModuleSummaryIndexBitcodeReader::parseSummaryIndexInto(
     std::unique_ptr<DataStreamer> Streamer, ModuleSummaryIndex *I) {

lib/Bitcode/Writer/BitcodeWriter.cpp

 //===--- Bitcode/Writer/BitcodeWriter.cpp - Bitcode Writer ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Bitcode writer implementation.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ValueEnumerator.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Bitcode/BitstreamWriter.h"
 #include "llvm/Bitcode/LLVMBitCodes.h"

 #include "llvm/IR/Operator.h"
 #include "llvm/IR/UseListOrder.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/SHA1.h"
 #include <cctype>
 #include <map>
 using namespace llvm;
 
 /// These are manifest constants used by the bitcode writer. They do not need to
 /// be kept in sync with the reader, but need to be consistent within this file.
 enum {
   // VALUE_SYMTAB_BLOCK abbrev id's.
static void WriteModStrings(const ModuleSummaryIndex &I,
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
   unsigned Abbrev8Bit = Stream.EmitAbbrev(Abbv);
 
   // 7-bit fixed width MST_ENTRY strings.
   Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::MST_CODE_ENTRY));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
   unsigned Abbrev7Bit = Stream.EmitAbbrev(Abbv);
 
   // 6-bit char6 MST_ENTRY strings.
   Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::MST_CODE_ENTRY));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
   unsigned Abbrev6Bit = Stream.EmitAbbrev(Abbv);
 
-  SmallVector<unsigned, 64> NameVals;
-  for (const StringMapEntry<uint64_t> &MPSE : I.modulePaths()) {
+  // Module Hash, 160 bits SHA1. Optionally, emitted after each MST_CODE_ENTRY.
+  Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::MST_CODE_HASH));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+  unsigned AbbrevHash = Stream.EmitAbbrev(Abbv);
+
+  SmallVector<unsigned, 64> Vals;
+  for (const auto &MPSE : I.modulePaths()) {
     StringEncoding Bits =
         getStringEncoding(MPSE.getKey().data(), MPSE.getKey().size());
     unsigned AbbrevToUse = Abbrev8Bit;
     if (Bits == SE_Char6)
       AbbrevToUse = Abbrev6Bit;
     else if (Bits == SE_Fixed7)
       AbbrevToUse = Abbrev7Bit;
 
-    NameVals.push_back(MPSE.getValue());
+    Vals.push_back(MPSE.getValue().first);
 
     for (const auto P : MPSE.getKey())
-      NameVals.push_back((unsigned char)P);
+      Vals.push_back((unsigned char)P);
 
     // Emit the finished record.
-    Stream.EmitRecord(bitc::MST_CODE_ENTRY, NameVals, AbbrevToUse);
-    NameVals.clear();
+    Stream.EmitRecord(bitc::MST_CODE_ENTRY, Vals, AbbrevToUse);
+
+    Vals.clear();
+    // Emit an optional hash for the module now
+    auto &Hash = MPSE.getValue().second;
+    bool AllZero = true; // Detect if the hash is empty, and do not generate it
+    for (auto Val : Hash) {
+      if (Val)
+        AllZero = false;
+      Vals.push_back(Val);
+    }
+    if (!AllZero) {
+      // Emit the hash record.
+      Stream.EmitRecord(bitc::MST_CODE_HASH, Vals, AbbrevHash);
+    }
+
+    Vals.clear();
   }
   Stream.ExitBlock();
 }
 
 // Helper to emit a single function summary record.
 static void WritePerModuleFunctionSummaryRecord(
     SmallVector<uint64_t, 64> &NameVals, FunctionSummary *FS, unsigned ValueID,
     unsigned FSCallsAbbrev, unsigned FSCallsProfileAbbrev,
static void WriteIdentificationBlock(const Module *M, BitstreamWriter &Stream) {
   Abbv->Add(BitCodeAbbrevOp(bitc::IDENTIFICATION_CODE_EPOCH));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
   auto EpochAbbrev = Stream.EmitAbbrev(Abbv);
   SmallVector<unsigned, 1> Vals = {bitc::BITCODE_CURRENT_EPOCH};
   Stream.EmitRecord(bitc::IDENTIFICATION_CODE_EPOCH, Vals, EpochAbbrev);
   Stream.ExitBlock();
 }
 
+static void writeModuleHash(BitstreamWriter &Stream,
+                            SmallVectorImpl<char> &Buffer,
+                            size_t BlockStartPos) {
+  // Emit the module's hash.
+  // MODULE_CODE_HASH: [5*i32]
+  SHA1 Hasher;
+  Hasher.write(&Buffer[BlockStartPos], Buffer.size() - BlockStartPos);
+  auto Hash = Hasher.result();
+  SmallVector<uint64_t, 20> Vals;
+  auto LShift = [&](unsigned char Val, unsigned Amount)
+                    -> uint64_t { return ((uint64_t)Val) << Amount; };
+  for (int Pos = 0; Pos < 20; Pos += 4) {
+    uint32_t SubHash = LShift(Hash[Pos + 0], 24);
+    SubHash |= LShift(Hash[Pos + 1], 16) | LShift(Hash[Pos + 2], 8) |
+               (unsigned)(unsigned char)Hash[Pos + 3];
+    Vals.push_back(SubHash);
+  }
+
+  // Emit the finished record.
+  Stream.EmitRecord(bitc::MODULE_CODE_HASH, Vals);
+}
+
 /// WriteModule - Emit the specified module to the bitstream.
 static void WriteModule(const Module *M, BitstreamWriter &Stream,
                         bool ShouldPreserveUseListOrder,
-                        uint64_t BitcodeStartBit, bool EmitSummaryIndex) {
+                        uint64_t BitcodeStartBit, bool EmitSummaryIndex,
+                        bool GenerateHash, SmallVectorImpl<char> &Buffer) {
   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
+  size_t BlockStartPos = Buffer.size();
 
   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.
   ValueEnumerator VE(*M, ShouldPreserveUseListOrder);
 
   // Emit blockinfo, which defines the standard abbreviations etc.
static void WriteModule(const Module *M, BitstreamWriter &Stream,
   // Need to write after the above call to WriteFunction which populates
   // the summary information in the index.
   if (EmitSummaryIndex)
     WritePerModuleGlobalValueSummary(FunctionIndex, M, VE, Stream);
 
   WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream,
                         VSTOffsetPlaceholder, BitcodeStartBit, &FunctionIndex);
 
+  if (GenerateHash) {
+    writeModuleHash(Stream, Buffer, BlockStartPos);
+  }
+
   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.
 ///
static void WriteBitcodeHeader(BitstreamWriter &Stream) {
   Stream.Emit(0xE, 4);
   Stream.Emit(0xD, 4);
 }
 
 /// WriteBitcodeToFile - Write the specified module to the specified output
 /// stream.
 void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out,
                               bool ShouldPreserveUseListOrder,
-                              bool EmitSummaryIndex) {
+                              bool EmitSummaryIndex, bool GenerateHash) {
   SmallVector<char, 0> Buffer;
   Buffer.reserve(256*1024);
 
   // If this is darwin or another generic macho target, reserve space for the
   // header.
   Triple TT(M->getTargetTriple());
   if (TT.isOSDarwin() || TT.isOSBinFormatMachO())
     Buffer.insert(Buffer.begin(), BWH_HeaderSize, 0);
// Emit the module into the buffer.
 
     // Emit the file header.
     WriteBitcodeHeader(Stream);
 
     WriteIdentificationBlock(M, Stream);
 
     // Emit the module.
     WriteModule(M, Stream, ShouldPreserveUseListOrder, BitcodeStartBit,
-                EmitSummaryIndex);
+                EmitSummaryIndex, GenerateHash, Buffer);
   }
 
   if (TT.isOSDarwin() || TT.isOSBinFormatMachO())
     EmitDarwinBCHeaderAndTrailer(Buffer, TT);
 
   // Write the generated bitstream to "Out".
   Out.write((char*)&Buffer.front(), Buffer.size());
 }

lib/IR/ModuleSummaryIndex.cpp

for (auto &OtherGlobalValInfoLists : *Other) {
     std::unique_ptr<GlobalValueInfo> Info = std::move(List.front());
 
     // Skip if there was no summary section.
     if (!Info->summary())
       continue;
 
     // Add the module path string ref for this module if we haven't already
     // saved a reference to it.
-    if (ModPath.empty())
-      ModPath = addModulePath(Info->summary()->modulePath(), NextModuleId);
-    else
+    if (ModPath.empty()) {
+      auto Path = Info->summary()->modulePath();
+      ModPath = addModulePath(Path, NextModuleId, Other->getModuleHash(Path))
+                    ->first();
+    } else
       assert(ModPath == Info->summary()->modulePath() &&
              "Each module in the combined map should have a unique ID");
 
     // Note the module path string ref was copied above and is still owned by
     // the original per-module index. Reset it to the new module path
     // string reference owned by the combined index.
     Info->summary()->setModulePath(ModPath);
 

lib/Transforms/IPO/FunctionImport.cpp

static std::unique_ptr<Module> loadFile(const std::string &FileName,
   DEBUG(dbgs() << "Loading '" << FileName << "'\n");
   // Metadata isn't loaded until functions are imported, to minimize
   // the memory overhead.
   std::unique_ptr<Module> Result =
       getLazyIRFileModule(FileName, Err, Context,
                           /* ShouldLazyLoadMetadata = */ true);
   if (!Result) {
     Err.print("function-import", errs());
-    return nullptr;
+    report_fatal_error("Abort");
   }
 
   return Result;
 }
 
 namespace {
 
 /// Given a list of possible callee implementation for a call site, select one

tools/llvm-as/llvm-as.cpp

 
 static cl::opt<bool>
 DisableOutput("disable-output", cl::desc("Disable output"), cl::init(false));
 
 static cl::opt<bool> EmitSummaryIndex("module-summary",
                                       cl::desc("Emit module summary index"),
                                       cl::init(false));
 
+static cl::opt<bool> EmitModuleHash("module-hash", cl::desc("Emit module hash"),
+                                    cl::init(false));
+
 static cl::opt<bool>
 DumpAsm("d", cl::desc("Print assembly as parsed"), cl::Hidden);
 
 static cl::opt<bool>
 DisableVerify("disable-verify", cl::Hidden,
               cl::desc("Do not run verifier on input LLVM (dangerous!)"));
 
 static cl::opt<bool> PreserveBitcodeUseListOrder(
std::unique_ptr<tool_output_file> Out(
       new tool_output_file(OutputFilename, EC, sys::fs::F_None));
   if (EC) {
     errs() << EC.message() << '\n';
     exit(1);
   }
 
   if (Force || !CheckBitcodeOutputToConsole(Out->os(), true))
     WriteBitcodeToFile(M, Out->os(), PreserveBitcodeUseListOrder,
-                       EmitSummaryIndex);
+                       EmitSummaryIndex, EmitModuleHash);
 
   // Declare success.
   Out->keep();
 }
 
 int main(int argc, char **argv) {
   // Print a stack trace if we signal out.
   sys::PrintStackTraceOnErrorSignal();

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

 // The tool is also able to print a bitcode file in a straight forward text
 // format that shows the containment and relationships of the information in
 // the bitcode file (-dump option).
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Bitcode/BitstreamReader.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/Bitcode/LLVMBitCodes.h"
 #include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Signals.h"
+#include "llvm/Support/SHA1.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
+#include <array>
 #include <cctype>
 #include <map>
 #include <system_error>
 using namespace llvm;
 
 static cl::opt<std::string>
   InputFilename(cl::Positional, cl::desc("<input bitcode>"), cl::init("-"));
 
default: return nullptr;
       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)
       STRINGIFY_CODE(MODULE_CODE, METADATA_VALUES_UNUSED)
       STRINGIFY_CODE(MODULE_CODE, SOURCE_FILENAME)
+      STRINGIFY_CODE(MODULE_CODE, HASH)
     }
   case bitc::IDENTIFICATION_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(IDENTIFICATION_CODE, STRING)
       STRINGIFY_CODE(IDENTIFICATION_CODE, EPOCH)
     }
case bitc::VALUE_SYMTAB_BLOCK_ID:
     STRINGIFY_CODE(VST_CODE, COMBINED_GVDEFENTRY)
     STRINGIFY_CODE(VST_CODE, COMBINED_ENTRY)
     }
   case bitc::MODULE_STRTAB_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(MST_CODE, ENTRY)
+      STRINGIFY_CODE(MST_CODE, HASH)
     }
   case bitc::GLOBALVAL_SUMMARY_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(FS, PERMODULE)
       STRINGIFY_CODE(FS, PERMODULE_PROFILE)
       STRINGIFY_CODE(FS, PERMODULE_GLOBALVAR_INIT_REFS)
if (BlockID == bitc::BLOCKINFO_BLOCK_ID) {
     // It's not really interesting to dump the contents of the blockinfo block.
     DumpRecords = false;
   }
 
   unsigned NumWords = 0;
   if (Stream.EnterSubBlock(BlockID, &NumWords))
     return Error("Malformed block record");
 
+  // Keep it for later, when we see a MODULE_HASH record
+  uint64_t BlockEntryPos = Stream.getCurrentByteNo();
+
   const char *BlockName = nullptr;
   if (DumpRecords) {
     outs() << Indent << "<";
     if ((BlockName = GetBlockName(BlockID, *Stream.getBitStreamReader(),
                                   CurStreamType)))
       outs() << BlockName;
     else
       outs() << "UnknownBlock" << BlockID;
if (Entry.ID == bitc::DEFINE_ABBREV) {
       continue;
     }
     
     Record.clear();
 
     ++BlockStats.NumRecords;
 
     StringRef Blob;
+    unsigned CurrentRecordPos = Stream.getCurrentByteNo();
     unsigned Code = Stream.readRecord(Entry.ID, Record, &Blob);
 
     // Increment the # occurrences of this code.
     if (BlockStats.CodeFreq.size() <= Code)
       BlockStats.CodeFreq.resize(Code+1);
     BlockStats.CodeFreq[Code].NumInstances++;
     BlockStats.CodeFreq[Code].TotalBits +=
       Stream.GetCurrentBitNo()-RecordStartBit;
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 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;
+          {
+            int BlockSize = CurrentRecordPos - BlockEntryPos;
+            auto Ptr = Stream.getPointerToByte(BlockEntryPos, BlockSize);
+            Hasher.write((const char *)Ptr, BlockSize);
+            Hash = Hasher.result();
+          }
+          SmallString<20> RecordedHash;
+          RecordedHash.resize(20);
+          int Pos = 0;
+          for (auto &Val : Record) {
+            assert(!(Val >> 32) && "Unexpected high bits set");
+            RecordedHash[Pos++] = (Val >> 24) & 0xFF;
+            RecordedHash[Pos++] = (Val >> 16) & 0xFF;
+            RecordedHash[Pos++] = (Val >> 8) & 0xFF;
+            RecordedHash[Pos++] = (Val >> 0) & 0xFF;
+          }
+          if (Hash == RecordedHash)
+            outs() << " (match)";
+          else
+            outs() << " (!mismatch!)";
+        }
+      }
+
       outs() << "/>";
 
       if (Abbv) {
         for (unsigned i = 1, e = Abbv->getNumOperandInfos(); i != e; ++i) {
           const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
           if (!Op.isEncoding() || Op.getEncoding() != BitCodeAbbrevOp::Array)
             continue;
           assert(i + 2 == e && "Array op not second to last");
           std::string Str;
           bool ArrayIsPrintable = true;