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