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