[BOLT][NFC] Add hash computation for basic blocks

Extending yaml profile format with block hashes, which are used for stale
profile matching. To avoid duplication of the code, created a new class with a
collection of utilities for computing hashes.

Reviewed By: Amir

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

5 files changed, 59 insertions, 0 deletions

diff --git a/bolt/include/bolt/Core/BinaryBasicBlock.h b/bolt/include/bolt/Core/BinaryBasicBlock.h
index 8c044597b5fd..c9694ab29d44 100644
--- a/bolt/include/bolt/Core/BinaryBasicBlock.h
+++ b/bolt/include/bolt/Core/BinaryBasicBlock.h
@@ -144,6 +144,9 @@ private:
   /// blocks may contain out of date or incorrect information.
   bool IsValid{true};
 
+  /// Last computed hash value.
+  mutable uint64_t Hash{0};
+
 private:
   BinaryBasicBlock() = delete;
   BinaryBasicBlock(const BinaryBasicBlock &) = delete;
@@ -939,6 +942,9 @@ public:
   /// Check if the block has a jump table instruction.
   bool hasJumpTable() const { return getJumpTable() != nullptr; }
 
+  /// Returns the last computed hash value of the block.
+  uint64_t getHash() const { return Hash; }
+
 private:
   void adjustNumPseudos(const MCInst &Inst, int Sign);
 
@@ -963,6 +969,9 @@ private:
   /// Set the index of this basic block.
   void setIndex(unsigned I) { Index = I; }
 
+  /// Sets the hash value of the basic block.
+  void setHash(uint64_t Value) const { Hash = Value; }
+
   template <typename T> void clearList(T &List) {
     T TempList;
     TempList.swap(List);
diff --git a/bolt/include/bolt/Core/BinaryFunction.h b/bolt/include/bolt/Core/BinaryFunction.h
index a96243c579eb..a54492c290f0 100644
--- a/bolt/include/bolt/Core/BinaryFunction.h
+++ b/bolt/include/bolt/Core/BinaryFunction.h
@@ -2205,6 +2205,9 @@ public:
         return std::string();
       }) const;
 
+  /// Compute hash values for each block of the function.
+  void computeBlockHashes() const;
+
   void setDWARFUnit(DWARFUnit *Unit) { DwarfUnit = Unit; }
 
   /// Return DWARF compile unit for this function.
diff --git a/bolt/include/bolt/Core/HashUtilities.h b/bolt/include/bolt/Core/HashUtilities.h
new file mode 100644
index 000000000000..8d445ff83756
--- /dev/null
+++ b/bolt/include/bolt/Core/HashUtilities.h
@@ -0,0 +1,41 @@
+//===- bolt/Core/HashUtilities.h - Misc hash utilities --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains functions for computing hash values over BinaryFunction
+// and BinaryBasicBlock.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef BOLT_CORE_HASH_UTILITIES_H
+#define BOLT_CORE_HASH_UTILITIES_H
+
+#include "bolt/Core/BinaryBasicBlock.h"
+#include "bolt/Core/BinaryContext.h"
+
+namespace llvm {
+namespace bolt {
+
+uint16_t hash_64_to_16(const uint64_t Hash);
+
+std::string hashInteger(uint64_t Value);
+
+std::string hashSymbol(BinaryContext &BC, const MCSymbol &Symbol);
+
+std::string hashExpr(BinaryContext &BC, const MCExpr &Expr);
+
+std::string hashInstOperand(BinaryContext &BC, const MCOperand &Operand);
+
+using OperandHashFuncTy = function_ref<typename std::string(const MCOperand &)>;
+
+std::string hashBlock(BinaryContext &BC, const BinaryBasicBlock &BB,
+                      OperandHashFuncTy OperandHashFunc);
+
+} // namespace bolt
+} // namespace llvm
+
+#endif
diff --git a/bolt/include/bolt/Core/MCPlusBuilder.h b/bolt/include/bolt/Core/MCPlusBuilder.h
index e6eb1429d3a1..86756a4434ed 100644
--- a/bolt/include/bolt/Core/MCPlusBuilder.h
+++ b/bolt/include/bolt/Core/MCPlusBuilder.h
@@ -466,6 +466,11 @@ public:
 
   virtual MCPhysReg getX86R11() const { llvm_unreachable("not implemented"); }
 
+  virtual unsigned getShortBranchOpcode(unsigned Opcode) const {
+    llvm_unreachable("not implemented");
+    return 0;
+  }
+
   /// Create increment contents of target by 1 for Instrumentation
   virtual InstructionListType createInstrIncMemory(const MCSymbol *Target,
                                                    MCContext *Ctx,
diff --git a/bolt/include/bolt/Profile/ProfileYAMLMapping.h b/bolt/include/bolt/Profile/ProfileYAMLMapping.h
index e20d449e0b93..f02f2197c469 100644
--- a/bolt/include/bolt/Profile/ProfileYAMLMapping.h
+++ b/bolt/include/bolt/Profile/ProfileYAMLMapping.h
@@ -126,6 +126,7 @@ template <> struct MappingTraits<bolt::BinaryBasicBlockProfile> {
   static void mapping(IO &YamlIO, bolt::BinaryBasicBlockProfile &BBP) {
     YamlIO.mapRequired("bid", BBP.Index);
     YamlIO.mapRequired("insns", BBP.NumInstructions);
+    YamlIO.mapOptional("hash", BBP.Hash, (llvm::yaml::Hex64)0);
     YamlIO.mapOptional("exec", BBP.ExecCount, (uint64_t)0);
     YamlIO.mapOptional("events", BBP.EventCount, (uint64_t)0);
     YamlIO.mapOptional("calls", BBP.CallSites,