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 
stableHashValue(const MachineOperand & MO)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.
stableHashValue(const MachineInstr & MI,bool HashVRegs,bool HashConstantPoolIndices,bool HashMemOperands)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->getOrdering()));
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