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/Passes.h"
15#include "llvm/InitializePasses.h"
16#include "llvm/Target/TargetMachine.h"
17
18using namespace llvm;
19
20uint64_t hashBlock(const MachineBasicBlock &MBB, bool HashOperands) {
21 uint64_t Hash = 0;
22 for (const MachineInstr &MI : MBB) {
23 if (MI.isMetaInstruction() || MI.isTerminator())
24 continue;
25 Hash = hashing::detail::hash_16_bytes(low: Hash, high: MI.getOpcode());
26 if (HashOperands) {
27 for (unsigned i = 0; i < MI.getNumOperands(); i++) {
28 Hash =
29 hashing::detail::hash_16_bytes(low: Hash, high: hash_value(MO: MI.getOperand(i)));
30 }
31 }
32 }
33 return Hash;
34}
35
36/// Fold a 64-bit integer to a 16-bit one.
37uint16_t fold_64_to_16(const uint64_t Value) {
38 uint16_t Res = static_cast<uint16_t>(Value);
39 Res ^= static_cast<uint16_t>(Value >> 16);
40 Res ^= static_cast<uint16_t>(Value >> 32);
41 Res ^= static_cast<uint16_t>(Value >> 48);
42 return Res;
43}
44
45INITIALIZE_PASS(MachineBlockHashInfo, "machine-block-hash",
46 "Machine Block Hash Analysis", true, true)
47
48char MachineBlockHashInfo::ID = 0;
49
50MachineBlockHashInfo::MachineBlockHashInfo() : MachineFunctionPass(ID) {}
51
52void MachineBlockHashInfo::getAnalysisUsage(AnalysisUsage &AU) const {
53 AU.setPreservesAll();
54 MachineFunctionPass::getAnalysisUsage(AU);
55}
56
57struct CollectHashInfo {
58 uint64_t Offset;
59 uint64_t OpcodeHash;
60 uint64_t InstrHash;
61 uint64_t NeighborHash;
62};
63
64bool MachineBlockHashInfo::runOnMachineFunction(MachineFunction &F) {
65 DenseMap<const MachineBasicBlock *, CollectHashInfo> HashInfos;
66 uint16_t Offset = 0;
67 // Initialize hash components
68 for (const MachineBasicBlock &MBB : F) {
69 // offset of the machine basic block
70 HashInfos[&MBB].Offset = Offset;
71 Offset += MBB.size();
72 // Hashing opcodes
73 HashInfos[&MBB].OpcodeHash = hashBlock(MBB, /*HashOperands=*/false);
74 // Hash complete instructions
75 HashInfos[&MBB].InstrHash = hashBlock(MBB, /*HashOperands=*/true);
76 }
77
78 // Initialize neighbor hash
79 for (const MachineBasicBlock &MBB : F) {
80 uint64_t Hash = HashInfos[&MBB].OpcodeHash;
81 // Append hashes of successors
82 for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
83 uint64_t SuccHash = HashInfos[SuccMBB].OpcodeHash;
84 Hash = hashing::detail::hash_16_bytes(low: Hash, high: SuccHash);
85 }
86 // Append hashes of predecessors
87 for (const MachineBasicBlock *PredMBB : MBB.predecessors()) {
88 uint64_t PredHash = HashInfos[PredMBB].OpcodeHash;
89 Hash = hashing::detail::hash_16_bytes(low: Hash, high: PredHash);
90 }
91 HashInfos[&MBB].NeighborHash = Hash;
92 }
93
94 // Assign hashes
95 for (const MachineBasicBlock &MBB : F) {
96 const auto &HashInfo = HashInfos[&MBB];
97 BlendedBlockHash BlendedHash(fold_64_to_16(Value: HashInfo.Offset),
98 fold_64_to_16(Value: HashInfo.OpcodeHash),
99 fold_64_to_16(Value: HashInfo.InstrHash),
100 fold_64_to_16(Value: HashInfo.NeighborHash));
101 MBBHashInfo[&MBB] = BlendedHash.combine();
102 }
103
104 return false;
105}
106
107uint64_t MachineBlockHashInfo::getMBBHash(const MachineBasicBlock &MBB) {
108 return MBBHashInfo[&MBB];
109}
110
111MachineFunctionPass *llvm::createMachineBlockHashInfoPass() {
112 return new MachineBlockHashInfo();
113}
114