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 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. 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 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 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