[BOLT] Always match stale entry blocks

[spupyrev]

Summary

Two (minor) improvements for stale matching:

• always match entry blocks to each other, even if there is a hash mismatch;
• ignore nops in (loose) hash computation.

I record a small improvement in inference quality on my benchmarks. Tests are not affected

[Amir]

Thanks. We recently discussed a case where stale matching was unable to match any block in a function and so function exec count was not set. We thought it's still beneficial to set exec count in this case for function reordering. I assume the entry block match will also make stale matching set function exec count in this scenario?

[Amir]

Can you please retitle as imperative statement before landing?

[spupyrev]

Thanks. We recently discussed a case where stale matching was unable to match any block in a function and so function exec count was not set. We thought it's still beneficial to set exec count in this case for function reordering. I assume the entry block match will also make stale matching set function exec count in this scenario?

Once we get into the block-matching code path, the function is guaranteed to be marked as having valid profile, and thus, it will be considered for all optimizations. There are a few exceptions earlier (canApplyInference()) which may leave some functions without profile, and this is unchanged by the diff. To address your scenario, we'd need something else.

bolt/lib/Core/HashUtilities.cpp

 /// 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) {
   // 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))
+    // Skip pseudo instructions and nops.
+    if (BC.MIB->isPseudo(Inst) || BC.MIB->isNoop(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.

bolt/lib/Profile/StaleProfileMatching.cpp

void matchWeightsByHashes(BinaryContext &BC,
 
   // Index in yaml profile => corresponding (matched) block
   DenseMap<uint64_t, const FlowBlock *> MatchedBlocks;
   // Match blocks from the profile to the blocks in CFG
   for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
     assert(YamlBB.Hash != 0 && "empty hash of BinaryBasicBlockProfile");
     BlendedBlockHash YamlHash(YamlBB.Hash);
     const FlowBlock *MatchedBlock = Matcher.matchBlock(YamlHash);
+    // Always match the entry block.
+    if (MatchedBlock == nullptr && YamlBB.Index == 0)
+      MatchedBlock = Blocks[0];
     if (MatchedBlock != nullptr) {
       MatchedBlocks[YamlBB.Index] = MatchedBlock;
       BlendedBlockHash BinHash = BlendedHashes[MatchedBlock->Index - 1];
       LLVM_DEBUG(dbgs() << "Matched yaml block (bid = " << YamlBB.Index << ")"
                         << " with hash " << Twine::utohexstr(YamlBB.Hash)
                         << " to BB (index = " << MatchedBlock->Index - 1 << ")"
                         << " with hash " << Twine::utohexstr(BinHash.combine())
                         << "\n");