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