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