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