[BOLT] Fine-tuning hash computation for stale matching

[spupyrev]

Summary

Fine-tuning hash computation for stale matching:

• introducing a new "loose" basic block hash that allows to match many more blocks than before;
• tweaking params of the inference algorithm that find (slightly) better solutions;
• added more meaningful tests for stale matching.

Tested the changes on several open-source benchmarks (clang, rocksdb, chrome)
and one prod workload using different compiler modes (LTO/PGO etc). There is
always an improvement in the quality of inferred profiles.
(The current implementation is still not optimal but the diff is a step forward;
I am open to further suggestions)

[spupyrev]

minor tweaks

[spupyrev]

fixing tests

[spupyrev]

adding a test check

[spupyrev]

added a test

[spupyrev]

Ready for review now

[Amir]

Please fix a couple of nits, LGTM otherwise.

bolt/lib/Core/HashUtilities.cpp

160

As we discussed

bolt/lib/Target/X86/X86MCPlusBuilder.cpp

2875

This function doesn't do what we wanted it to do (return the short version

bolt/test/X86/reader-stale-yaml.test

41 ↗

(On Diff #544949)

49 ↗

(On Diff #544949)

[spupyrev]

Addressing comments by reverting the changes in MCPlusBuilder.h

[spupyrev]

Since the last change wasn't trivial, I'll wait for another review before landing this

[Amir]

Looks good. Thank you for updating it.

[spupyrev]

rebase

[spupyrev]

rebase

bolt/include/bolt/Core/HashUtilities.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);
 
+std::string hashBlockLoose(BinaryContext &BC, const BinaryBasicBlock &BB);
+
 } // namespace bolt
 } // namespace llvm
 
 #endif

bolt/include/bolt/Core/MCPlusBuilder.h

public:
 
   virtual MCPhysReg getX86R11() const { llvm_unreachable("not implemented"); }
 
   virtual unsigned getShortBranchOpcode(unsigned Opcode) const {
     llvm_unreachable("not implemented");
     return 0;
   }
 
+  virtual unsigned getShortOpcode(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,
                                                    bool IsLeaf) const {
     llvm_unreachable("not implemented");
     return InstructionListType();
   }
 

bolt/lib/Core/HashUtilities.cpp

for (const MCInst &Inst : BB) {
     }
 
     for (const MCOperand &Op : MCPlus::primeOperands(Inst))
       HashString.append(OperandHashFunc(Op));
   }
   return HashString;
 }
 
+/// A "loose" hash of a basic block to use with the stale profile matching. The
+/// computed value will be the same for blocks with minor changes (such as
+/// reordering of instructions or using different operands) but may result in
+/// collisions that need to be resolved by a stronger hashing.
+std::string hashBlockLoose(BinaryContext &BC, const BinaryBasicBlock &BB) {
+  const bool IsX86 = BC.isX86();
+
+  // The hash is computed by creating a string of all lexicographically ordered
+  // instruction opcodes, which is then hashed with std::hash.
+  std::set<std::string> Opcodes;
+  for (const MCInst &Inst : BB) {
+    if (BC.MIB->isPseudo(Inst))
+      continue;
+
+    // Ignore unconditional jumps, as they can be added / removed as a result
+    // of basic block reordering.
+    if (BC.MIB->isUnconditionalBranch(Inst))
+      continue;
+
+    // Do not distinguish different types of conditional jumps.
+    if (BC.MIB->isConditionalBranch(Inst)) {
+      Opcodes.insert("JMP");
+      continue;
+    }
+
+    unsigned Opcode = Inst.getOpcode();
+    if (IsX86)
+      Opcode = BC.MIB->getShortOpcode(Opcode);
+
+    if (Opcode > 0) {
+      std::string Mnemonic = BC.InstPrinter->getMnemonic(&Inst).first;
+      Mnemonic.erase(
+          std::find_if(Mnemonic.rbegin(), Mnemonic.rend(),
+                       [](unsigned char ch) { return !std::isspace(ch); })
+              .base(),
+          Mnemonic.end());
+      Opcodes.insert(Mnemonic);
+    }
+  }
+
+  std::string HashString;
+  for (const std::string &Opcode : Opcodes)
+    HashString.append(Opcode);
+  return HashString;
+}
+
 } // namespace bolt
 } // namespace llvm

bolt/lib/Profile/StaleProfileMatching.cpp

 
 cl::opt<bool> StaleMatchingJoinIslands(
     "stale-matching-join-islands",
     cl::desc("Join isolated components having positive flow."), cl::init(true),
     cl::ReallyHidden, cl::cat(BoltOptCategory));
 
 cl::opt<unsigned> StaleMatchingCostBlockInc(
     "stale-matching-cost-block-inc",
-    cl::desc("The cost of increasing a block's count by one."), cl::init(110),
+    cl::desc("The cost of increasing a block count by one."), cl::init(120),
     cl::ReallyHidden, cl::cat(BoltOptCategory));
 
-cl::opt<unsigned> StaleMatchingCostBlockDec(
-    "stale-matching-cost-block-dec",
-    cl::desc("The cost of decreasing a block's count by one."), cl::init(100),
-    cl::ReallyHidden, cl::cat(BoltOptCategory));
-
-cl::opt<unsigned> StaleMatchingCostBlockEntryInc(
-    "stale-matching-cost-block-entry-inc",
-    cl::desc("The cost of increasing the entry block's count by one."),
-    cl::init(110), cl::ReallyHidden, cl::cat(BoltOptCategory));
-
-cl::opt<unsigned> StaleMatchingCostBlockEntryDec(
-    "stale-matching-cost-block-entry-dec",
-    cl::desc("The cost of decreasing the entry block's count by one."),
-    cl::init(100), cl::ReallyHidden, cl::cat(BoltOptCategory));
-
-cl::opt<unsigned> StaleMatchingCostBlockZeroInc(
-    "stale-matching-cost-block-zero-inc",
-    cl::desc("The cost of increasing a count of zero-weight block by one."),
-    cl::init(10), cl::Hidden, cl::cat(BoltOptCategory));
-
-cl::opt<unsigned> StaleMatchingCostBlockUnknownInc(
-    "stale-matching-cost-block-unknown-inc",
-    cl::desc("The cost of increasing an unknown block's count by one."),
-    cl::init(10), cl::ReallyHidden, cl::cat(BoltOptCategory));
-
 cl::opt<unsigned> StaleMatchingCostJumpInc(
     "stale-matching-cost-jump-inc",
-    cl::desc("The cost of increasing a jump's count by one."), cl::init(100),
+    cl::desc("The cost of increasing a jump count by one."), cl::init(120),
     cl::ReallyHidden, cl::cat(BoltOptCategory));
 
-cl::opt<unsigned> StaleMatchingCostJumpFTInc(
-    "stale-matching-cost-jump-ft-inc",
-    cl::desc("The cost of increasing a fall-through jump's count by one."),
-    cl::init(100), cl::ReallyHidden, cl::cat(BoltOptCategory));
+cl::opt<unsigned> StaleMatchingCostBlockDec(
+    "stale-matching-cost-block-dec",
+    cl::desc("The cost of decreasing a block count by one."), cl::init(120),
+    cl::ReallyHidden, cl::cat(BoltOptCategory));
 
 cl::opt<unsigned> StaleMatchingCostJumpDec(
     "stale-matching-cost-jump-dec",
-    cl::desc("The cost of decreasing a jump's count by one."), cl::init(110),
+    cl::desc("The cost of decreasing a jump count by one."), cl::init(120),
     cl::ReallyHidden, cl::cat(BoltOptCategory));
 
-cl::opt<unsigned> StaleMatchingCostJumpFTDec(
-    "stale-matching-cost-jump-ft-dec",
-    cl::desc("The cost of decreasing a fall-through jump's count by one."),
-    cl::init(110), cl::ReallyHidden, cl::cat(BoltOptCategory));
+cl::opt<unsigned> StaleMatchingCostBlockUnknownInc(
+    "stale-matching-cost-block-unknown-inc",
+    cl::desc("The cost of increasing an unknown block count by one."),
+    cl::init(25), cl::ReallyHidden, cl::cat(BoltOptCategory));
 
 cl::opt<unsigned> StaleMatchingCostJumpUnknownInc(
     "stale-matching-cost-jump-unknown-inc",
-    cl::desc("The cost of increasing an unknown jump's count by one."),
+    cl::desc("The cost of increasing an unknown jump count by one."),
     cl::init(50), cl::ReallyHidden, cl::cat(BoltOptCategory));
 
 cl::opt<unsigned> StaleMatchingCostJumpUnknownFTInc(
     "stale-matching-cost-jump-unknown-ft-inc",
     cl::desc(
-        "The cost of increasing an unknown fall-through jump's count by one."),
-    cl::init(5), cl::ReallyHidden, cl::cat(BoltOptCategory));
+        "The cost of increasing an unknown fall-through jump count by one."),
+    cl::init(15), cl::ReallyHidden, cl::cat(BoltOptCategory));
 
 } // namespace opts
 
 namespace llvm {
 namespace bolt {
 
 /// An object wrapping several components of a basic block hash. The combined
 /// (blended) hash is represented and stored as one uint64_t, while individual
 /// components are of smaller size (e.g., uint16_t or uint8_t).
 struct BlendedBlockHash {
 private:
   using ValueOffset = Bitfield::Element<uint16_t, 0, 16>;
   using ValueOpcode = Bitfield::Element<uint16_t, 16, 16>;
   using ValueInstr = Bitfield::Element<uint16_t, 32, 16>;
-  using ValueNeighbor = Bitfield::Element<uint16_t, 48, 16>;
+  using ValuePred = Bitfield::Element<uint8_t, 48, 8>;
+  using ValueSucc = Bitfield::Element<uint8_t, 56, 8>;
 
 public:
   explicit BlendedBlockHash() {}
 
   explicit BlendedBlockHash(uint64_t Hash) {
     Offset = Bitfield::get<ValueOffset>(Hash);
     OpcodeHash = Bitfield::get<ValueOpcode>(Hash);
     InstrHash = Bitfield::get<ValueInstr>(Hash);
-    NeighborHash = Bitfield::get<ValueNeighbor>(Hash);
+    PredHash = Bitfield::get<ValuePred>(Hash);
+    SuccHash = Bitfield::get<ValueSucc>(Hash);
   }
 
   /// Combine the blended hash into uint64_t.
   uint64_t combine() const {
     uint64_t Hash = 0;
     Bitfield::set<ValueOffset>(Hash, Offset);
     Bitfield::set<ValueOpcode>(Hash, OpcodeHash);
     Bitfield::set<ValueInstr>(Hash, InstrHash);
-    Bitfield::set<ValueNeighbor>(Hash, NeighborHash);
+    Bitfield::set<ValuePred>(Hash, PredHash);
+    Bitfield::set<ValueSucc>(Hash, SuccHash);
     return Hash;
   }
 
   /// Compute a distance between two given blended hashes. The smaller the
   /// distance, the more similar two blocks are. For identical basic blocks,
   /// the distance is zero.
   uint64_t distance(const BlendedBlockHash &BBH) const {
     assert(OpcodeHash == BBH.OpcodeHash &&
            "incorrect blended hash distance computation");
     uint64_t Dist = 0;
     // Account for NeighborHash
-    Dist += NeighborHash == BBH.NeighborHash ? 0 : 1;
+    Dist += SuccHash == BBH.SuccHash ? 0 : 1;
+    Dist += PredHash == BBH.PredHash ? 0 : 1;
     Dist <<= 16;
     // Account for InstrHash
     Dist += InstrHash == BBH.InstrHash ? 0 : 1;
     Dist <<= 16;
     // Account for Offset
     Dist += (Offset >= BBH.Offset ? Offset - BBH.Offset : BBH.Offset - Offset);
     return Dist;
   }
 
   /// The offset of the basic block from the function start.
   uint16_t Offset{0};
   /// (Loose) Hash of the basic block instructions, excluding operands.
   uint16_t OpcodeHash{0};
   /// (Strong) Hash of the basic block instructions, including opcodes and
   /// operands.
   uint16_t InstrHash{0};
-  /// Hash of the (loose) basic block together with (loose) hashes of its
-  /// successors and predecessors.
-  uint16_t NeighborHash{0};
+  /// (Loose) Hashes of the predecessors of the basic block.
+  uint8_t PredHash{0};
+  /// (Loose) Hashes of the successors of the basic block.
+  uint8_t SuccHash{0};
 };
 
 /// The object is used to identify and match basic blocks in a BinaryFunction
 /// given their hashes computed on a binary built from several revisions behind
 /// release.
 class StaleMatcher {
 public:
   /// Initialize stale matcher.

 void BinaryFunction::computeBlockHashes() const {
   if (size() == 0)
     return;
 
   assert(hasCFG() && "the function is expected to have CFG");
 
   std::vector<BlendedBlockHash> BlendedHashes(BasicBlocks.size());
   std::vector<uint64_t> OpcodeHashes(BasicBlocks.size());
-  // Initialize hash components
+  // Initialize hash components.
   for (size_t I = 0; I < BasicBlocks.size(); I++) {
     const BinaryBasicBlock *BB = BasicBlocks[I];
     assert(BB->getIndex() == I && "incorrect block index");
     BlendedHashes[I].Offset = BB->getOffset();
-    // Hashing complete instructions
+    // Hashing complete instructions.
     std::string InstrHashStr = hashBlock(
         BC, *BB, [&](const MCOperand &Op) { return hashInstOperand(BC, Op); });
     uint64_t InstrHash = std::hash<std::string>{}(InstrHashStr);
-    BlendedHashes[I].InstrHash = hash_64_to_16(InstrHash);
-    // Hashing opcodes
-    std::string OpcodeHashStr =
-        hashBlock(BC, *BB, [](const MCOperand &Op) { return std::string(); });
+    BlendedHashes[I].InstrHash = (uint16_t)hash_value(InstrHash);
+    // Hashing opcodes.
+    std::string OpcodeHashStr = hashBlockLoose(BC, *BB);
     OpcodeHashes[I] = std::hash<std::string>{}(OpcodeHashStr);
-    BlendedHashes[I].OpcodeHash = hash_64_to_16(OpcodeHashes[I]);
+    BlendedHashes[I].OpcodeHash = (uint16_t)hash_value(OpcodeHashes[I]);
   }
 
-  // Initialize neighbor hash
+  // Initialize neighbor hash.
   for (size_t I = 0; I < BasicBlocks.size(); I++) {
     const BinaryBasicBlock *BB = BasicBlocks[I];
-    uint64_t Hash = OpcodeHashes[I];
-    // Append hashes of successors
+    // Append hashes of successors.
+    uint64_t Hash = 0;
     for (BinaryBasicBlock *SuccBB : BB->successors()) {
       uint64_t SuccHash = OpcodeHashes[SuccBB->getIndex()];
       Hash = hashing::detail::hash_16_bytes(Hash, SuccHash);
     }
-    // Append hashes of predecessors
+    BlendedHashes[I].SuccHash = (uint8_t)hash_value(Hash);
+
+    // Append hashes of predecessors.
+    Hash = 0;
     for (BinaryBasicBlock *PredBB : BB->predecessors()) {
       uint64_t PredHash = OpcodeHashes[PredBB->getIndex()];
       Hash = hashing::detail::hash_16_bytes(Hash, PredHash);
     }
-    BlendedHashes[I].NeighborHash = hash_64_to_16(Hash);
+    BlendedHashes[I].PredHash = (uint8_t)hash_value(Hash);
   }
 
-  //  Assign hashes
+  //  Assign hashes.
   for (size_t I = 0; I < BasicBlocks.size(); I++) {
     const BinaryBasicBlock *BB = BasicBlocks[I];
     BB->setHash(BlendedHashes[I].combine());
   }
 }
 
 /// Create a wrapper flow function to use with the profile inference algorithm,
 /// and initialize its jumps and metadata.

 void applyInference(FlowFunction &Func) {
   ProfiParams Params;
   // Set the params from the command-line flags.
   Params.EvenFlowDistribution = opts::StaleMatchingEvenFlowDistribution;
   Params.RebalanceUnknown = opts::StaleMatchingRebalanceUnknown;
   Params.JoinIslands = opts::StaleMatchingJoinIslands;
 
   Params.CostBlockInc = opts::StaleMatchingCostBlockInc;
+  Params.CostBlockEntryInc = opts::StaleMatchingCostBlockInc;
   Params.CostBlockDec = opts::StaleMatchingCostBlockDec;
-  Params.CostBlockEntryInc = opts::StaleMatchingCostBlockEntryInc;
-  Params.CostBlockEntryDec = opts::StaleMatchingCostBlockEntryDec;
-  Params.CostBlockZeroInc = opts::StaleMatchingCostBlockZeroInc;
+  Params.CostBlockEntryDec = opts::StaleMatchingCostBlockDec;
   Params.CostBlockUnknownInc = opts::StaleMatchingCostBlockUnknownInc;
 
   Params.CostJumpInc = opts::StaleMatchingCostJumpInc;
-  Params.CostJumpFTInc = opts::StaleMatchingCostJumpFTInc;
+  Params.CostJumpFTInc = opts::StaleMatchingCostJumpInc;
   Params.CostJumpDec = opts::StaleMatchingCostJumpDec;
-  Params.CostJumpFTDec = opts::StaleMatchingCostJumpFTDec;
+  Params.CostJumpFTDec = opts::StaleMatchingCostJumpDec;
   Params.CostJumpUnknownInc = opts::StaleMatchingCostJumpUnknownInc;
   Params.CostJumpUnknownFTInc = opts::StaleMatchingCostJumpUnknownFTInc;
 
   applyFlowInference(Params, Func);
 }
 
 /// Collect inferred counts from the flow function and update annotations in
 /// the binary function.

bolt/lib/Target/X86/X86MCPlusBuilder.cpp

case X86::JMP_4:
       return X86::JMP_1;
     case X86::JCC_2:
       return X86::JCC_1;
     case X86::JCC_4:
       return X86::JCC_1;
     }
   }
 
+  unsigned getShortOpcode(unsigned Opcode) const override {
+    return X86::getOpcodeForShortImmediateForm(Opcode);
+  }
+
   MCPhysReg getIntArgRegister(unsigned ArgNo) const override {
     // FIXME: this should depend on the calling convention.
     switch (ArgNo) {
     case 0:   return X86::RDI;
     case 1:   return X86::RSI;
     case 2:   return X86::RDX;
     case 3:   return X86::RCX;
     case 4:   return X86::R8;