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