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