1//===- llvm/CodeGen/MachineBlockHashInfo.cpp---------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Compute the hashes of basic blocks.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/MachineBlockHashInfo.h"
14#include "llvm/CodeGen/MachineFunction.h"
15#include "llvm/CodeGen/MachineStableHash.h"
16#include "llvm/CodeGen/Passes.h"
17#include "llvm/InitializePasses.h"
18#include "llvm/Support/CommandLine.h"
19#include "llvm/Support/raw_ostream.h"
20#include "llvm/Target/TargetMachine.h"
21
22using namespace llvm;
23
24static cl::opt<bool> EmitBBHash(
25 "emit-bb-hash",
26 cl::desc(
27 "Emit the hash of basic block in the SHT_LLVM_BB_ADDR_MAP section."),
28 cl::init(Val: false));
29
30bool llvm::shouldEmitBBHash() { return EmitBBHash; }
31
32// Frozen mixer; the block hashes computed below are serialized into BB
33// section profile data, so this function's exact output is part of the
34// on-disk format. Do not change without versioning that format.
35static constexpr uint64_t hash_16_bytes(uint64_t low, uint64_t high) {
36 const uint64_t kMul = 0x9ddfea08eb382d69ULL;
37 uint64_t a = (low ^ high) * kMul;
38 a ^= (a >> 47);
39 uint64_t b = (high ^ a) * kMul;
40 b ^= (b >> 47);
41 b *= kMul;
42 return b;
43}
44
45static uint64_t hashBlock(const MachineBasicBlock &MBB, bool HashOperands) {
46 uint64_t Hash = 0;
47 for (const MachineInstr &MI : MBB) {
48 if (MI.isMetaInstruction() || MI.isTerminator())
49 continue;
50 Hash = hash_16_bytes(low: Hash, high: MI.getOpcode());
51 if (HashOperands) {
52 for (unsigned i = 0; i < MI.getNumOperands(); i++) {
53 Hash = hash_16_bytes(low: Hash, high: stableHashValue(MO: MI.getOperand(i)));
54 }
55 }
56 }
57 return Hash;
58}
59
60/// Fold a 64-bit integer to a 16-bit one.
61static constexpr uint16_t fold_64_to_16(const uint64_t Value) {
62 uint16_t Res = static_cast<uint16_t>(Value);
63 Res ^= static_cast<uint16_t>(Value >> 16);
64 Res ^= static_cast<uint16_t>(Value >> 32);
65 Res ^= static_cast<uint16_t>(Value >> 48);
66 return Res;
67}
68
69static_assert(hash_16_bytes(low: 1, high: 2) == 9684580150926652833ull,
70 "Hash function must be stable");
71static_assert(hash_16_bytes(low: -1, high: -2) == 7819786907124864172ull,
72 "Hash function must be stable");
73static_assert(fold_64_to_16(Value: 1) == 1, "Fold function must be stable");
74static_assert(fold_64_to_16(Value: 12345678) == 25074, "Fold function must be stable");
75
76INITIALIZE_PASS(MachineBlockHashInfo, "machine-block-hash",
77 "Machine Block Hash Analysis", true, true)
78
79char MachineBlockHashInfo::ID = 0;
80
81MachineBlockHashInfo::MachineBlockHashInfo() : MachineFunctionPass(ID) {}
82
83void MachineBlockHashInfo::getAnalysisUsage(AnalysisUsage &AU) const {
84 AU.setPreservesAll();
85 MachineFunctionPass::getAnalysisUsage(AU);
86}
87
88struct CollectHashInfo {
89 uint64_t Offset;
90 uint64_t OpcodeHash;
91 uint64_t InstrHash;
92 uint64_t NeighborHash;
93};
94
95MachineBlockHashInfoResult::MachineBlockHashInfoResult() = default;
96
97MachineBlockHashInfoResult::MachineBlockHashInfoResult(
98 const MachineFunction &F) {
99 DenseMap<const MachineBasicBlock *, CollectHashInfo> HashInfos;
100 uint16_t Offset = 0;
101 // Initialize hash components
102 for (const MachineBasicBlock &MBB : F) {
103 auto &HashInfo = HashInfos[&MBB];
104 // offset of the machine basic block
105 HashInfo.Offset = Offset;
106 Offset += MBB.size();
107 // Hashing opcodes
108 HashInfo.OpcodeHash = hashBlock(MBB, /*HashOperands=*/false);
109 // Hash complete instructions
110 HashInfo.InstrHash = hashBlock(MBB, /*HashOperands=*/true);
111 }
112
113 // Initialize neighbor hash
114 for (const MachineBasicBlock &MBB : F) {
115 auto &HashInfo = HashInfos[&MBB];
116 uint64_t Hash = HashInfo.OpcodeHash;
117 // Append hashes of successors
118 for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
119 uint64_t SuccHash = HashInfos[SuccMBB].OpcodeHash;
120 Hash = hash_16_bytes(low: Hash, high: SuccHash);
121 }
122 // Append hashes of predecessors
123 for (const MachineBasicBlock *PredMBB : MBB.predecessors()) {
124 uint64_t PredHash = HashInfos[PredMBB].OpcodeHash;
125 Hash = hash_16_bytes(low: Hash, high: PredHash);
126 }
127 HashInfo.NeighborHash = Hash;
128 }
129
130 // Assign hashes
131 for (const MachineBasicBlock &MBB : F) {
132 const auto &HashInfo = HashInfos[&MBB];
133 BlendedBlockHash BlendedHash(fold_64_to_16(Value: HashInfo.Offset),
134 fold_64_to_16(Value: HashInfo.OpcodeHash),
135 fold_64_to_16(Value: HashInfo.InstrHash),
136 fold_64_to_16(Value: HashInfo.NeighborHash));
137 MBBHashInfo[&MBB] = BlendedHash.combine();
138 }
139}
140
141uint64_t
142MachineBlockHashInfoResult::getMBBHash(const MachineBasicBlock &MBB) const {
143 auto it = MBBHashInfo.find(Val: &MBB);
144 return it->second;
145}
146
147bool MachineBlockHashInfo::runOnMachineFunction(MachineFunction &F) {
148 Result = MachineBlockHashInfoResult{F};
149 return false;
150}
151
152uint64_t MachineBlockHashInfo::getMBBHash(const MachineBasicBlock &MBB) const {
153 return Result.getMBBHash(MBB);
154}
155
156MachineFunctionPass *llvm::createMachineBlockHashInfoPass() {
157 return new MachineBlockHashInfo();
158}
159
160AnalysisKey MachineBlockHashInfoAnalysis::Key;
161
162MachineBlockHashInfoResult
163MachineBlockHashInfoAnalysis::run(MachineFunction &MF,
164 MachineFunctionAnalysisManager &MFAM) {
165 return MachineBlockHashInfoResult{MF};
166}
167
168PreservedAnalyses
169MachineBlockHashInfoPrinterPass::run(MachineFunction &MF,
170 MachineFunctionAnalysisManager &MFAM) {
171 auto &MBHI = MFAM.getResult<MachineBlockHashInfoAnalysis>(IR&: MF);
172 OS << "Machine Block Hash Info for function: " << MF.getName() << "\n";
173 for (const auto &MBB : MF) {
174 OS << " BB#" << MBB.getNumber() << ": "
175 << format_hex(N: MBHI.getMBBHash(MBB), Width: 18) << "\n";
176 }
177 return PreservedAnalyses::all();
178}
179