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 (Register::isVirtualRegister(MO.getReg())) { 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 const uint32_t *RegMask = MO.getRegMask(); 124 const unsigned RegMaskSize = MO.getRegMaskSize(); 125 126 if (RegMaskSize != 0) { 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 return hash_combine(MO.getType(), MO.getTargetFlags()); 135 } 136 137 case MachineOperand::MO_ShuffleMask: { 138 std::vector<llvm::stable_hash> ShuffleMaskHashes; 139 140 llvm::transform( 141 MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes), 142 [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); }); 143 144 return hash_combine(MO.getType(), MO.getTargetFlags(), 145 stable_hash_combine_array(ShuffleMaskHashes.data(), 146 ShuffleMaskHashes.size())); 147 } 148 case MachineOperand::MO_MCSymbol: { 149 auto SymbolName = MO.getMCSymbol()->getName(); 150 return hash_combine(MO.getType(), MO.getTargetFlags(), 151 stable_hash_combine_string(SymbolName)); 152 } 153 case MachineOperand::MO_CFIIndex: 154 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 155 MO.getCFIIndex()); 156 case MachineOperand::MO_IntrinsicID: 157 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 158 MO.getIntrinsicID()); 159 case MachineOperand::MO_Predicate: 160 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 161 MO.getPredicate()); 162 } 163 llvm_unreachable("Invalid machine operand type"); 164 } 165 166 /// A stable hash value for machine instructions. 167 /// Returns 0 if no stable hash could be computed. 168 /// The hashing and equality testing functions ignore definitions so this is 169 /// useful for CSE, etc. 170 stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs, 171 bool HashConstantPoolIndices, 172 bool HashMemOperands) { 173 // Build up a buffer of hash code components. 174 SmallVector<stable_hash, 16> HashComponents; 175 HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2); 176 HashComponents.push_back(MI.getOpcode()); 177 HashComponents.push_back(MI.getFlags()); 178 for (const MachineOperand &MO : MI.operands()) { 179 if (!HashVRegs && MO.isReg() && MO.isDef() && 180 Register::isVirtualRegister(MO.getReg())) 181 continue; // Skip virtual register defs. 182 183 if (MO.isCPI()) { 184 HashComponents.push_back(stable_hash_combine( 185 MO.getType(), MO.getTargetFlags(), MO.getIndex())); 186 continue; 187 } 188 189 stable_hash StableHash = stableHashValue(MO); 190 if (!StableHash) 191 return 0; 192 HashComponents.push_back(StableHash); 193 } 194 195 for (const auto *Op : MI.memoperands()) { 196 if (!HashMemOperands) 197 break; 198 HashComponents.push_back(static_cast<unsigned>(Op->getSize())); 199 HashComponents.push_back(static_cast<unsigned>(Op->getFlags())); 200 HashComponents.push_back(static_cast<unsigned>(Op->getOffset())); 201 HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering())); 202 HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace())); 203 HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID())); 204 HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value())); 205 HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering())); 206 } 207 208 return stable_hash_combine_range(HashComponents.begin(), 209 HashComponents.end()); 210 } 211 212 stable_hash llvm::stableHashValue(const MachineBasicBlock &MBB) { 213 SmallVector<stable_hash> HashComponents; 214 // TODO: Hash more stuff like block alignment and branch probabilities. 215 for (const auto &MI : MBB) 216 HashComponents.push_back(stableHashValue(MI)); 217 return stable_hash_combine_range(HashComponents.begin(), 218 HashComponents.end()); 219 } 220 221 stable_hash llvm::stableHashValue(const MachineFunction &MF) { 222 SmallVector<stable_hash> HashComponents; 223 // TODO: Hash lots more stuff like function alignment and stack objects. 224 for (const auto &MBB : MF) 225 HashComponents.push_back(stableHashValue(MBB)); 226 return stable_hash_combine_range(HashComponents.begin(), 227 HashComponents.end()); 228 } 229