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/MachineJumpTableInfo.h" 24 #include "llvm/CodeGen/MachineOperand.h" 25 #include "llvm/CodeGen/MachineRegisterInfo.h" 26 #include "llvm/CodeGen/StableHashing.h" 27 #include "llvm/CodeGen/TargetInstrInfo.h" 28 #include "llvm/CodeGen/TargetRegisterInfo.h" 29 #include "llvm/Config/llvm-config.h" 30 #include "llvm/IR/Constants.h" 31 #include "llvm/IR/IRPrintingPasses.h" 32 #include "llvm/IR/Instructions.h" 33 #include "llvm/IR/ModuleSlotTracker.h" 34 #include "llvm/MC/MCDwarf.h" 35 #include "llvm/Target/TargetIntrinsicInfo.h" 36 #include "llvm/Target/TargetMachine.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 (Register::isVirtualRegister(MO.getReg())) { 65 const MachineRegisterInfo &MRI = MO.getParent()->getMF()->getRegInfo(); 66 return MRI.getVRegDef(MO.getReg())->getOpcode(); 67 } 68 69 // Register operands don't have target flags. 70 return stable_hash_combine(MO.getType(), MO.getReg(), MO.getSubReg(), 71 MO.isDef()); 72 case MachineOperand::MO_Immediate: 73 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), MO.getImm()); 74 case MachineOperand::MO_CImmediate: 75 case MachineOperand::MO_FPImmediate: { 76 auto Val = MO.isCImm() ? MO.getCImm()->getValue() 77 : MO.getFPImm()->getValueAPF().bitcastToAPInt(); 78 auto ValHash = 79 stable_hash_combine_array(Val.getRawData(), Val.getNumWords()); 80 return hash_combine(MO.getType(), MO.getTargetFlags(), ValHash); 81 } 82 83 case MachineOperand::MO_MachineBasicBlock: 84 StableHashBailingMachineBasicBlock++; 85 return 0; 86 case MachineOperand::MO_ConstantPoolIndex: 87 StableHashBailingConstantPoolIndex++; 88 return 0; 89 case MachineOperand::MO_BlockAddress: 90 StableHashBailingBlockAddress++; 91 return 0; 92 case MachineOperand::MO_Metadata: 93 StableHashBailingMetadataUnsupported++; 94 return 0; 95 case MachineOperand::MO_GlobalAddress: 96 StableHashBailingGlobalAddress++; 97 return 0; 98 case MachineOperand::MO_TargetIndex: { 99 if (const char *Name = MO.getTargetIndexName()) 100 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 101 stable_hash_combine_string(Name), 102 MO.getOffset()); 103 StableHashBailingTargetIndexNoName++; 104 return 0; 105 } 106 107 case MachineOperand::MO_FrameIndex: 108 case MachineOperand::MO_JumpTableIndex: 109 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 110 MO.getIndex()); 111 112 case MachineOperand::MO_ExternalSymbol: 113 return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(), 114 stable_hash_combine_string(MO.getSymbolName())); 115 116 case MachineOperand::MO_RegisterMask: 117 case MachineOperand::MO_RegisterLiveOut: 118 return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getRegMask()); 119 120 case MachineOperand::MO_ShuffleMask: { 121 std::vector<llvm::stable_hash> ShuffleMaskHashes; 122 123 llvm::transform( 124 MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes), 125 [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); }); 126 127 return hash_combine(MO.getType(), MO.getTargetFlags(), 128 stable_hash_combine_array(ShuffleMaskHashes.data(), 129 ShuffleMaskHashes.size())); 130 } 131 case MachineOperand::MO_MCSymbol: { 132 auto SymbolName = MO.getMCSymbol()->getName(); 133 return hash_combine(MO.getType(), MO.getTargetFlags(), 134 stable_hash_combine_string(SymbolName)); 135 } 136 case MachineOperand::MO_CFIIndex: 137 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 138 MO.getCFIIndex()); 139 case MachineOperand::MO_IntrinsicID: 140 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 141 MO.getIntrinsicID()); 142 case MachineOperand::MO_Predicate: 143 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), 144 MO.getPredicate()); 145 } 146 llvm_unreachable("Invalid machine operand type"); 147 } 148 149 /// A stable hash value for machine instructions. 150 /// Returns 0 if no stable hash could be computed. 151 /// The hashing and equality testing functions ignore definitions so this is 152 /// useful for CSE, etc. 153 stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs, 154 bool HashConstantPoolIndices, 155 bool HashMemOperands) { 156 // Build up a buffer of hash code components. 157 SmallVector<stable_hash, 16> HashComponents; 158 HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2); 159 HashComponents.push_back(MI.getOpcode()); 160 HashComponents.push_back(MI.getFlags()); 161 for (const MachineOperand &MO : MI.operands()) { 162 if (!HashVRegs && MO.isReg() && MO.isDef() && 163 Register::isVirtualRegister(MO.getReg())) 164 continue; // Skip virtual register defs. 165 166 if (MO.isCPI()) { 167 HashComponents.push_back(stable_hash_combine( 168 MO.getType(), MO.getTargetFlags(), MO.getIndex())); 169 continue; 170 } 171 172 stable_hash StableHash = stableHashValue(MO); 173 if (!StableHash) 174 return 0; 175 HashComponents.push_back(StableHash); 176 } 177 178 for (const auto *Op : MI.memoperands()) { 179 if (!HashMemOperands) 180 break; 181 HashComponents.push_back(static_cast<unsigned>(Op->getSize())); 182 HashComponents.push_back(static_cast<unsigned>(Op->getFlags())); 183 HashComponents.push_back(static_cast<unsigned>(Op->getOffset())); 184 HashComponents.push_back(static_cast<unsigned>(Op->getOrdering())); 185 HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace())); 186 HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID())); 187 HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value())); 188 HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering())); 189 } 190 191 return stable_hash_combine_range(HashComponents.begin(), 192 HashComponents.end()); 193 } 194