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