[BOLT] (Minor) Changes in stale inference

[spupyrev]

Summary

1. Using ADT/Bitfields.h for hash computation; this is equivalent but shorter than the existing implementation
2. Getting rid of Layout indices for stale matching; using BB->getIndex for indexing

[spupyrev]

rebase to latest

[spupyrev]

reverting accidentally attached changes

[spupyrev]

rebase

bolt/lib/Profile/StaleProfileMatching.cpp

 //   reconstruct "realistic" block and jump counts from the partial profile
 //   generated at the first stage. In practice, we don't always produce proper
 //   profile data but the majority (e.g., >90%) of CFGs get the correct counts.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Core/HashUtilities.h"
 #include "bolt/Profile/YAMLProfileReader.h"
+#include "llvm/ADT/Bitfields.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils/SampleProfileInference.h"
 
 #include <queue>
 
+using namespace llvm;
+
 #undef DEBUG_TYPE
 #define DEBUG_TYPE "bolt-prof"
 
-using namespace llvm;
-
 namespace opts {
 
 extern cl::OptionCategory BoltOptCategory;
 
 cl::opt<bool>
     InferStaleProfile("infer-stale-profile",
                       cl::desc("Infer counts from stale profile data."),
                       cl::init(false), cl::Hidden, cl::cat(BoltOptCategory));

 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:
-  static uint64_t combineHashes(uint16_t Hash1, uint16_t Hash2, uint16_t Hash3,
-                                uint16_t Hash4) {
-    uint64_t Hash = 0;
-
-    Hash |= uint64_t(Hash4);
-    Hash <<= 16;
-
-    Hash |= uint64_t(Hash3);
-    Hash <<= 16;
-
-    Hash |= uint64_t(Hash2);
-    Hash <<= 16;
-
-    Hash |= uint64_t(Hash1);
-
-    return Hash;
-  }
-
-  static void parseHashes(uint64_t Hash, uint16_t &Hash1, uint16_t &Hash2,
-                          uint16_t &Hash3, uint16_t &Hash4) {
-    Hash1 = Hash & 0xffff;
-    Hash >>= 16;
-
-    Hash2 = Hash & 0xffff;
-    Hash >>= 16;
-
-    Hash3 = Hash & 0xffff;
-    Hash >>= 16;
-
-    Hash4 = Hash & 0xffff;
-    Hash >>= 16;
-  }
+  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>;
 
 public:
   explicit BlendedBlockHash() {}
 
-  explicit BlendedBlockHash(uint64_t CombinedHash) {
-    parseHashes(CombinedHash, Offset, OpcodeHash, InstrHash, NeighborHash);
+  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);
   }
 
   /// Combine the blended hash into uint64_t.
   uint64_t combine() const {
-    return combineHashes(Offset, OpcodeHash, InstrHash, NeighborHash);
+    uint64_t Hash = 0;
+    Bitfield::set<ValueOffset>(Hash, Offset);
+    Bitfield::set<ValueOpcode>(Hash, OpcodeHash);
+    Bitfield::set<ValueInstr>(Hash, InstrHash);
+    Bitfield::set<ValueNeighbor>(Hash, NeighborHash);
+    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");
void BinaryFunction::computeBlockHashes() const {
   }
 
   //  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.
 FlowFunction
 createFlowFunction(const BinaryFunction::BasicBlockOrderType &BlockOrder) {
   FlowFunction Func;
 
   // Add a special "dummy" source so that there is always a unique entry point.
   // Because of the extra source, for all other blocks in FlowFunction it holds
-  // that Block.Index == BB->getLayoutIndex() + 1
+  // that Block.Index == BB->getIndex() + 1
   FlowBlock EntryBlock;
   EntryBlock.Index = 0;
   Func.Blocks.push_back(EntryBlock);
 
   // Create FlowBlock for every basic block in the binary function
   for (const BinaryBasicBlock *BB : BlockOrder) {
     Func.Blocks.emplace_back();
     FlowBlock &Block = Func.Blocks.back();
     Block.Index = Func.Blocks.size() - 1;
     (void)BB;
-    assert(Block.Index == BB->getLayoutIndex() + 1 &&
+    assert(Block.Index == BB->getIndex() + 1 &&
            "incorrectly assigned basic block index");
   }
 
   // Create FlowJump for each jump between basic blocks in the binary function
   std::vector<uint64_t> InDegree(Func.Blocks.size(), 0);
   for (const BinaryBasicBlock *SrcBB : BlockOrder) {
     std::unordered_set<const BinaryBasicBlock *> UniqueSuccs;
     // Collect regular jumps
     for (const BinaryBasicBlock *DstBB : SrcBB->successors()) {
       // Ignoring parallel edges
       if (UniqueSuccs.find(DstBB) != UniqueSuccs.end())
         continue;
 
       Func.Jumps.emplace_back();
       FlowJump &Jump = Func.Jumps.back();
-      Jump.Source = SrcBB->getLayoutIndex() + 1;
-      Jump.Target = DstBB->getLayoutIndex() + 1;
+      Jump.Source = SrcBB->getIndex() + 1;
+      Jump.Target = DstBB->getIndex() + 1;
       InDegree[Jump.Target]++;
       UniqueSuccs.insert(DstBB);
     }
     // Collect jumps to landing pads
     for (const BinaryBasicBlock *DstBB : SrcBB->landing_pads()) {
       // Ignoring parallel edges
       if (UniqueSuccs.find(DstBB) != UniqueSuccs.end())
         continue;
 
       Func.Jumps.emplace_back();
       FlowJump &Jump = Func.Jumps.back();
-      Jump.Source = SrcBB->getLayoutIndex() + 1;
-      Jump.Target = DstBB->getLayoutIndex() + 1;
+      Jump.Source = SrcBB->getIndex() + 1;
+      Jump.Target = DstBB->getIndex() + 1;
       InDegree[Jump.Target]++;
       UniqueSuccs.insert(DstBB);
     }
   }
 
   // Add dummy edges to the extra sources. If there are multiple entry blocks,
   // add an unlikely edge from 0 to the subsequent ones
   assert(InDegree[0] == 0 && "dummy entry blocks shouldn't have predecessors");
void assignProfile(BinaryFunction &BF,
 
   // Update function's execution count and mark the function inferred.
   BF.setExecutionCount(Func.Blocks[0].Flow);
   BF.setHasInferredProfile(true);
 }
 
 bool YAMLProfileReader::inferStaleProfile(
     BinaryFunction &BF, const yaml::bolt::BinaryFunctionProfile &YamlBF) {
-  // Make sure that block indices and hashes are up to date
-  BF.getLayout().updateLayoutIndices();
+  LLVM_DEBUG(dbgs() << "BOLT-INFO: applying profile inference for "
+                    << "\"" << BF.getPrintName() << "\"\n");
+
+  // Make sure that block hashes are up to date.
   BF.computeBlockHashes();
 
   const BinaryFunction::BasicBlockOrderType BlockOrder(
       BF.getLayout().block_begin(), BF.getLayout().block_end());
 
-  // Create a wrapper flow function to use with the profile inference algorithm
+  // Create a wrapper flow function to use with the profile inference algorithm.
   FlowFunction Func = createFlowFunction(BlockOrder);
 
   // Match as many block/jump counts from the stale profile as possible
   matchWeightsByHashes(BF.getBinaryContext(), BlockOrder, YamlBF, Func);
 
   // Adjust the flow function by marking unreachable blocks Unlikely so that
-  // they don't get any counts assigned
+  // they don't get any counts assigned.
   preprocessUnreachableBlocks(Func);
 
-  // Check if profile inference can be applied for the instance
+  // Check if profile inference can be applied for the instance.
   if (!canApplyInference(Func))
     return false;
 
-  // Apply the profile inference algorithm
+  // Apply the profile inference algorithm.
   applyInference(Func);
 
-  // Collect inferred counts and update function annotations
+  // Collect inferred counts and update function annotations.
   assignProfile(BF, BlockOrder, Func);
 
   // As of now, we always mark the binary function having "correct" profile.
   // In the future, we may discard the results for instances with poor inference
   // metrics and keep such functions un-optimized.
   return true;
 }
 
 } // end namespace bolt
 } // end namespace llvm

bolt/lib/Profile/YAMLProfileReader.cpp

if (ProfileMatched)
     BF.markProfiled(YamlBP.Header.Flags);
 
   if (!ProfileMatched && opts::Verbosity >= 1)
     errs() << "BOLT-WARNING: " << MismatchedBlocks << " blocks, "
            << MismatchedCalls << " calls, and " << MismatchedEdges
            << " edges in profile did not match function " << BF << '\n';
 
   if (!ProfileMatched && opts::InferStaleProfile) {
-    if (opts::Verbosity >= 1)
-      outs() << "BOLT-INFO: applying profile inference for "
-             << "\"" << BF.getPrintName() << "\"\n";
     if (inferStaleProfile(BF, YamlBF)) {
       ProfileMatched = true;
       BF.markProfiled(YamlBP.Header.Flags);
     }
   }
 
   return ProfileMatched;
 }