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 39 using namespace llvm; 40 41 STATISTIC(StableHashBailingMachineBasicBlock, 42 "Number of encountered unsupported MachineOperands that were " 43 "MachineBasicBlocks while computing stable hashes"); 44 STATISTIC(StableHashBailingConstantPoolIndex, 45 "Number of encountered unsupported MachineOperands that were " 46 "ConstantPoolIndex while computing stable hashes"); 47 STATISTIC(StableHashBailingTargetIndexNoName, 48 "Number of encountered unsupported MachineOperands that were " 49 "TargetIndex with no name"); 50 STATISTIC(StableHashBailingGlobalAddress, 51 "Number of encountered unsupported MachineOperands that were " 52 "GlobalAddress while computing stable hashes"); 53 STATISTIC(StableHashBailingBlockAddress, 54 "Number of encountered unsupported MachineOperands that were " 55 "BlockAddress while computing stable hashes"); 56 STATISTIC(StableHashBailingMetadataUnsupported, 57 "Number of encountered unsupported MachineOperands that were " 58 "Metadata of an unsupported kind while computing stable hashes"); 59 60 stable_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(MO.getReg())) 67 DefOpcodes.push_back(Def.getOpcode()); 68 return hash_combine_range(DefOpcodes.begin(), DefOpcodes.end()); 69 } 70 71 // Register operands don't have target flags. 72 return stable_hash_combine(MO.getType(), MO.getReg(), MO.getSubReg(), 73 MO.isDef()); 74 case MachineOperand::MO_Immediate: 75 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 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(Val.getRawData(), Val.getNumWords()); 82 return hash_combine(MO.getType(), MO.getTargetFlags(), 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(MO.getType(), MO.getTargetFlags(), 103 stable_hash_combine_string(Name), 104 MO.getOffset()); 105 StableHashBailingTargetIndexNoName++; 106 return 0; 107 } 108 109 case MachineOperand::MO_FrameIndex: 110 case MachineOperand::MO_JumpTableIndex: 111 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 112 MO.getIndex()); 113 114 case MachineOperand::MO_ExternalSymbol: 115 return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(), 116 stable_hash_combine_string(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(TRI->getNumRegs()); 126 const uint32_t *RegMask = MO.getRegMask(); 127 std::vector<llvm::stable_hash> RegMaskHashes(RegMask, 128 RegMask + RegMaskSize); 129 return hash_combine(MO.getType(), MO.getTargetFlags(), 130 stable_hash_combine_array(RegMaskHashes.data(), 131 RegMaskHashes.size())); 132 } 133 } 134 } 135 136 assert(0 && "MachineOperand not associated with any MachineFunction"); 137 return hash_combine(MO.getType(), MO.getTargetFlags()); 138 } 139 140 case MachineOperand::MO_ShuffleMask: { 141 std::vector<llvm::stable_hash> ShuffleMaskHashes; 142 143 llvm::transform( 144 MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes), 145 [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); }); 146 147 return hash_combine(MO.getType(), MO.getTargetFlags(), 148 stable_hash_combine_array(ShuffleMaskHashes.data(), 149 ShuffleMaskHashes.size())); 150 } 151 case MachineOperand::MO_MCSymbol: { 152 auto SymbolName = MO.getMCSymbol()->getName(); 153 return hash_combine(MO.getType(), MO.getTargetFlags(), 154 stable_hash_combine_string(SymbolName)); 155 } 156 case MachineOperand::MO_CFIIndex: 157 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 158 MO.getCFIIndex()); 159 case MachineOperand::MO_IntrinsicID: 160 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 161 MO.getIntrinsicID()); 162 case MachineOperand::MO_Predicate: 163 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 164 MO.getPredicate()); 165 case MachineOperand::MO_DbgInstrRef: 166 return stable_hash_combine(MO.getType(), MO.getInstrRefInstrIndex(), 167 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. 176 stable_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(MI.getNumOperands() + MI.getNumMemOperands() + 2); 182 HashComponents.push_back(MI.getOpcode()); 183 HashComponents.push_back(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(stable_hash_combine( 190 MO.getType(), MO.getTargetFlags(), MO.getIndex())); 191 continue; 192 } 193 194 stable_hash StableHash = stableHashValue(MO); 195 if (!StableHash) 196 return 0; 197 HashComponents.push_back(StableHash); 198 } 199 200 for (const auto *Op : MI.memoperands()) { 201 if (!HashMemOperands) 202 break; 203 HashComponents.push_back(static_cast<unsigned>(Op->getSize().getValue())); 204 HashComponents.push_back(static_cast<unsigned>(Op->getFlags())); 205 HashComponents.push_back(static_cast<unsigned>(Op->getOffset())); 206 HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering())); 207 HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace())); 208 HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID())); 209 HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value())); 210 HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering())); 211 } 212 213 return stable_hash_combine_range(HashComponents.begin(), 214 HashComponents.end()); 215 } 216 217 stable_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(stableHashValue(MI)); 222 return stable_hash_combine_range(HashComponents.begin(), 223 HashComponents.end()); 224 } 225 226 stable_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(stableHashValue(MBB)); 231 return stable_hash_combine_range(HashComponents.begin(), 232 HashComponents.end()); 233 } 234