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