1//===- lib/CodeGen/MachineStableHash.cpp ----------------------------------===//
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// Stable hashing for MachineInstr and MachineOperand. Useful or getting a
10// hash across runs, modules, etc.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/MachineStableHash.h"
15#include "llvm/ADT/APFloat.h"
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/StableHashing.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineFunction.h"
23#include "llvm/CodeGen/MachineInstr.h"
24#include "llvm/CodeGen/MachineMemOperand.h"
25#include "llvm/CodeGen/MachineOperand.h"
26#include "llvm/CodeGen/MachineRegisterInfo.h"
27#include "llvm/CodeGen/Register.h"
28#include "llvm/Config/llvm-config.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/GlobalVariable.h"
31#include "llvm/IR/StructuralHash.h"
32#include "llvm/MC/MCSymbol.h"
33#include "llvm/Support/Alignment.h"
34#include "llvm/Support/ErrorHandling.h"
35
36#define DEBUG_TYPE "machine-stable-hash"
37
38using namespace llvm;
39
40STATISTIC(StableHashBailingMachineBasicBlock,
41 "Number of encountered unsupported MachineOperands that were "
42 "MachineBasicBlocks while computing stable hashes");
43STATISTIC(StableHashBailingConstantPoolIndex,
44 "Number of encountered unsupported MachineOperands that were "
45 "ConstantPoolIndex while computing stable hashes");
46STATISTIC(StableHashBailingTargetIndexNoName,
47 "Number of encountered unsupported MachineOperands that were "
48 "TargetIndex with no name");
49STATISTIC(StableHashBailingGlobalAddress,
50 "Number of encountered unsupported MachineOperands that were "
51 "GlobalAddress while computing stable hashes");
52STATISTIC(StableHashBailingBlockAddress,
53 "Number of encountered unsupported MachineOperands that were "
54 "BlockAddress while computing stable hashes");
55STATISTIC(StableHashBailingMetadataUnsupported,
56 "Number of encountered unsupported MachineOperands that were "
57 "Metadata of an unsupported kind while computing stable hashes");
58
59stable_hash llvm::stableHashValue(const MachineOperand &MO) {
60 switch (MO.getType()) {
61 case MachineOperand::MO_Register:
62 if (MO.getReg().isVirtual()) {
63 const MachineRegisterInfo &MRI = MO.getParent()->getMF()->getRegInfo();
64 SmallVector<stable_hash> DefOpcodes;
65 for (auto &Def : MRI.def_instructions(Reg: MO.getReg()))
66 DefOpcodes.push_back(Elt: Def.getOpcode());
67 return stable_hash_combine(Buffer: DefOpcodes);
68 }
69
70 // Register operands don't have target flags.
71 return stable_hash_combine(A: MO.getType(), B: MO.getReg().id(), C: MO.getSubReg(),
72 D: MO.isDef());
73 case MachineOperand::MO_Immediate:
74 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(), C: MO.getImm());
75 case MachineOperand::MO_CImmediate:
76 case MachineOperand::MO_FPImmediate: {
77 auto Val = MO.isCImm() ? MO.getCImm()->getValue()
78 : MO.getFPImm()->getValueAPF().bitcastToAPInt();
79 auto ValHash = stable_hash_combine(
80 Buffer: ArrayRef<stable_hash>(Val.getRawData(), Val.getNumWords()));
81 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(), C: ValHash);
82 }
83
84 case MachineOperand::MO_MachineBasicBlock:
85 ++StableHashBailingMachineBasicBlock;
86 return 0;
87 case MachineOperand::MO_ConstantPoolIndex:
88 ++StableHashBailingConstantPoolIndex;
89 return 0;
90 case MachineOperand::MO_BlockAddress:
91 ++StableHashBailingBlockAddress;
92 return 0;
93 case MachineOperand::MO_Metadata:
94 ++StableHashBailingMetadataUnsupported;
95 return 0;
96 case MachineOperand::MO_GlobalAddress: {
97 const GlobalValue *GV = MO.getGlobal();
98 stable_hash GVHash = 0;
99 if (auto *GVar = dyn_cast<GlobalVariable>(Val: GV))
100 GVHash = StructuralHash(G: *GVar);
101 if (!GVHash) {
102 if (!GV->hasName()) {
103 ++StableHashBailingGlobalAddress;
104 return 0;
105 }
106 GVHash = stable_hash_name(Name: GV->getName());
107 }
108
109 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(), C: GVHash,
110 D: MO.getOffset());
111 }
112
113 case MachineOperand::MO_TargetIndex: {
114 if (const char *Name = MO.getTargetIndexName())
115 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
116 C: stable_hash_name(Name), D: MO.getOffset());
117 ++StableHashBailingTargetIndexNoName;
118 return 0;
119 }
120
121 case MachineOperand::MO_FrameIndex:
122 case MachineOperand::MO_JumpTableIndex:
123 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
124 C: MO.getIndex());
125
126 case MachineOperand::MO_ExternalSymbol:
127 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
128 C: MO.getOffset(),
129 D: stable_hash_name(Name: MO.getSymbolName()));
130
131 case MachineOperand::MO_RegisterMask:
132 case MachineOperand::MO_RegisterLiveOut: {
133 if (const MachineInstr *MI = MO.getParent()) {
134 if (const MachineBasicBlock *MBB = MI->getParent()) {
135 if (const MachineFunction *MF = MBB->getParent()) {
136 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
137 unsigned RegMaskSize =
138 MachineOperand::getRegMaskSize(NumRegs: TRI->getNumRegs());
139 const uint32_t *RegMask = MO.getRegMask();
140 std::vector<llvm::stable_hash> RegMaskHashes(RegMask,
141 RegMask + RegMaskSize);
142 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
143 C: stable_hash_combine(Buffer: RegMaskHashes));
144 }
145 }
146 }
147
148 assert(0 && "MachineOperand not associated with any MachineFunction");
149 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags());
150 }
151
152 case MachineOperand::MO_ShuffleMask: {
153 std::vector<llvm::stable_hash> ShuffleMaskHashes;
154
155 llvm::transform(
156 Range: MO.getShuffleMask(), d_first: std::back_inserter(x&: ShuffleMaskHashes),
157 F: [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });
158
159 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
160 C: stable_hash_combine(Buffer: ShuffleMaskHashes));
161 }
162 case MachineOperand::MO_MCSymbol: {
163 auto SymbolName = MO.getMCSymbol()->getName();
164 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
165 C: stable_hash_name(Name: SymbolName));
166 }
167 case MachineOperand::MO_CFIIndex:
168 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
169 C: MO.getCFIIndex());
170 case MachineOperand::MO_IntrinsicID:
171 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
172 C: MO.getIntrinsicID());
173 case MachineOperand::MO_Predicate:
174 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
175 C: MO.getPredicate());
176 case MachineOperand::MO_DbgInstrRef:
177 return stable_hash_combine(A: MO.getType(), B: MO.getInstrRefInstrIndex(),
178 C: MO.getInstrRefOpIndex());
179 }
180 llvm_unreachable("Invalid machine operand type");
181}
182
183/// A stable hash value for machine instructions.
184/// Returns 0 if no stable hash could be computed.
185/// The hashing and equality testing functions ignore definitions so this is
186/// useful for CSE, etc.
187stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs,
188 bool HashConstantPoolIndices,
189 bool HashMemOperands) {
190 // Build up a buffer of hash code components.
191 SmallVector<stable_hash, 16> HashComponents;
192 HashComponents.reserve(N: MI.getNumOperands() + MI.getNumMemOperands() + 2);
193 HashComponents.push_back(Elt: MI.getOpcode());
194 HashComponents.push_back(Elt: MI.getFlags());
195 for (const MachineOperand &MO : MI.operands()) {
196 if (!HashVRegs && MO.isReg() && MO.isDef() && MO.getReg().isVirtual())
197 continue; // Skip virtual register defs.
198
199 if (MO.isCPI()) {
200 HashComponents.push_back(Elt: stable_hash_combine(
201 A: MO.getType(), B: MO.getTargetFlags(), C: MO.getIndex()));
202 continue;
203 }
204
205 stable_hash StableHash = stableHashValue(MO);
206 if (!StableHash)
207 return 0;
208 HashComponents.push_back(Elt: StableHash);
209 }
210
211 for (const auto *Op : MI.memoperands()) {
212 if (!HashMemOperands)
213 break;
214 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getSize().getValue()));
215 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getFlags()));
216 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getOffset()));
217 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getSuccessOrdering()));
218 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getAddrSpace()));
219 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getSyncScopeID()));
220 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getBaseAlign().value()));
221 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getFailureOrdering()));
222 }
223
224 return stable_hash_combine(Buffer: HashComponents);
225}
226
227stable_hash llvm::stableHashValue(const MachineBasicBlock &MBB) {
228 SmallVector<stable_hash> HashComponents;
229 // TODO: Hash more stuff like block alignment and branch probabilities.
230 for (const auto &MI : MBB)
231 HashComponents.push_back(Elt: stableHashValue(MI));
232 return stable_hash_combine(Buffer: HashComponents);
233}
234
235stable_hash llvm::stableHashValue(const MachineFunction &MF) {
236 SmallVector<stable_hash> HashComponents;
237 // TODO: Hash lots more stuff like function alignment and stack objects.
238 for (const auto &MBB : MF)
239 HashComponents.push_back(Elt: stableHashValue(MBB));
240 return stable_hash_combine(Buffer: HashComponents);
241}
242