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 return MRI.getVRegDef(MO.getReg())->getOpcode(); 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 = 80 stable_hash_combine_array(Val.getRawData(), Val.getNumWords()); 81 return 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 StableHashBailingGlobalAddress++; 98 return 0; 99 case MachineOperand::MO_TargetIndex: { 100 if (const char *Name = MO.getTargetIndexName()) 101 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 102 stable_hash_combine_string(Name), 103 MO.getOffset()); 104 StableHashBailingTargetIndexNoName++; 105 return 0; 106 } 107 108 case MachineOperand::MO_FrameIndex: 109 case MachineOperand::MO_JumpTableIndex: 110 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 111 MO.getIndex()); 112 113 case MachineOperand::MO_ExternalSymbol: 114 return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(), 115 stable_hash_combine_string(MO.getSymbolName())); 116 117 case MachineOperand::MO_RegisterMask: 118 case MachineOperand::MO_RegisterLiveOut: 119 return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getRegMask()); 120 121 case MachineOperand::MO_ShuffleMask: { 122 std::vector<llvm::stable_hash> ShuffleMaskHashes; 123 124 llvm::transform( 125 MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes), 126 [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); }); 127 128 return hash_combine(MO.getType(), MO.getTargetFlags(), 129 stable_hash_combine_array(ShuffleMaskHashes.data(), 130 ShuffleMaskHashes.size())); 131 } 132 case MachineOperand::MO_MCSymbol: { 133 auto SymbolName = MO.getMCSymbol()->getName(); 134 return hash_combine(MO.getType(), MO.getTargetFlags(), 135 stable_hash_combine_string(SymbolName)); 136 } 137 case MachineOperand::MO_CFIIndex: 138 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 139 MO.getCFIIndex()); 140 case MachineOperand::MO_IntrinsicID: 141 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 142 MO.getIntrinsicID()); 143 case MachineOperand::MO_Predicate: 144 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 145 MO.getPredicate()); 146 } 147 llvm_unreachable("Invalid machine operand type"); 148 } 149 150 /// A stable hash value for machine instructions. 151 /// Returns 0 if no stable hash could be computed. 152 /// The hashing and equality testing functions ignore definitions so this is 153 /// useful for CSE, etc. 154 stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs, 155 bool HashConstantPoolIndices, 156 bool HashMemOperands) { 157 // Build up a buffer of hash code components. 158 SmallVector<stable_hash, 16> HashComponents; 159 HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2); 160 HashComponents.push_back(MI.getOpcode()); 161 HashComponents.push_back(MI.getFlags()); 162 for (const MachineOperand &MO : MI.operands()) { 163 if (!HashVRegs && MO.isReg() && MO.isDef() && 164 Register::isVirtualRegister(MO.getReg())) 165 continue; // Skip virtual register defs. 166 167 if (MO.isCPI()) { 168 HashComponents.push_back(stable_hash_combine( 169 MO.getType(), MO.getTargetFlags(), MO.getIndex())); 170 continue; 171 } 172 173 stable_hash StableHash = stableHashValue(MO); 174 if (!StableHash) 175 return 0; 176 HashComponents.push_back(StableHash); 177 } 178 179 for (const auto *Op : MI.memoperands()) { 180 if (!HashMemOperands) 181 break; 182 HashComponents.push_back(static_cast<unsigned>(Op->getSize())); 183 HashComponents.push_back(static_cast<unsigned>(Op->getFlags())); 184 HashComponents.push_back(static_cast<unsigned>(Op->getOffset())); 185 HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering())); 186 HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace())); 187 HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID())); 188 HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value())); 189 HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering())); 190 } 191 192 return stable_hash_combine_range(HashComponents.begin(), 193 HashComponents.end()); 194 } 195