LLVM  16.0.0git
MachineStableHash.cpp
Go to the documentation of this file.
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 
15 #include "llvm/ADT/APFloat.h"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/DenseMapInfo.h"
19 #include "llvm/ADT/Hashing.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
32 #include "llvm/CodeGen/Register.h"
34 #include "llvm/Config/llvm-config.h"
35 #include "llvm/IR/Constants.h"
36 #include "llvm/MC/MCSymbol.h"
37 #include "llvm/Support/Alignment.h"
39 
40 #define DEBUG_TYPE "machine-stable-hash"
41 
42 using namespace llvm;
43 
44 STATISTIC(StableHashBailingMachineBasicBlock,
45  "Number of encountered unsupported MachineOperands that were "
46  "MachineBasicBlocks while computing stable hashes");
47 STATISTIC(StableHashBailingConstantPoolIndex,
48  "Number of encountered unsupported MachineOperands that were "
49  "ConstantPoolIndex while computing stable hashes");
50 STATISTIC(StableHashBailingTargetIndexNoName,
51  "Number of encountered unsupported MachineOperands that were "
52  "TargetIndex with no name");
53 STATISTIC(StableHashBailingGlobalAddress,
54  "Number of encountered unsupported MachineOperands that were "
55  "GlobalAddress while computing stable hashes");
56 STATISTIC(StableHashBailingBlockAddress,
57  "Number of encountered unsupported MachineOperands that were "
58  "BlockAddress while computing stable hashes");
59 STATISTIC(StableHashBailingMetadataUnsupported,
60  "Number of encountered unsupported MachineOperands that were "
61  "Metadata of an unsupported kind while computing stable hashes");
62 
64  switch (MO.getType()) {
67  const MachineRegisterInfo &MRI = MO.getParent()->getMF()->getRegInfo();
68  SmallVector<unsigned> DefOpcodes;
69  for (auto &Def : MRI.def_instructions(MO.getReg()))
70  DefOpcodes.push_back(Def.getOpcode());
71  return hash_combine_range(DefOpcodes.begin(), DefOpcodes.end());
72  }
73 
74  // Register operands don't have target flags.
75  return stable_hash_combine(MO.getType(), MO.getReg(), MO.getSubReg(),
76  MO.isDef());
78  return stable_hash_combine(MO.getType(), MO.getTargetFlags(), MO.getImm());
81  auto Val = MO.isCImm() ? MO.getCImm()->getValue()
83  auto ValHash =
84  stable_hash_combine_array(Val.getRawData(), Val.getNumWords());
85  return hash_combine(MO.getType(), MO.getTargetFlags(), ValHash);
86  }
87 
89  StableHashBailingMachineBasicBlock++;
90  return 0;
92  StableHashBailingConstantPoolIndex++;
93  return 0;
95  StableHashBailingBlockAddress++;
96  return 0;
98  StableHashBailingMetadataUnsupported++;
99  return 0;
101  StableHashBailingGlobalAddress++;
102  return 0;
104  if (const char *Name = MO.getTargetIndexName())
105  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
107  MO.getOffset());
108  StableHashBailingTargetIndexNoName++;
109  return 0;
110  }
111 
114  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
115  MO.getIndex());
116 
118  return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
120 
123  if (const MachineInstr *MI = MO.getParent()) {
124  if (const MachineBasicBlock *MBB = MI->getParent()) {
125  if (const MachineFunction *MF = MBB->getParent()) {
126  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
127  unsigned RegMaskSize =
129  const uint32_t *RegMask = MO.getRegMask();
130  std::vector<llvm::stable_hash> RegMaskHashes(RegMask,
131  RegMask + RegMaskSize);
132  return hash_combine(MO.getType(), MO.getTargetFlags(),
133  stable_hash_combine_array(RegMaskHashes.data(),
134  RegMaskHashes.size()));
135  }
136  }
137  }
138 
139  assert(0 && "MachineOperand not associated with any MachineFunction");
140  return hash_combine(MO.getType(), MO.getTargetFlags());
141  }
142 
144  std::vector<llvm::stable_hash> ShuffleMaskHashes;
145 
147  MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes),
148  [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });
149 
150  return hash_combine(MO.getType(), MO.getTargetFlags(),
151  stable_hash_combine_array(ShuffleMaskHashes.data(),
152  ShuffleMaskHashes.size()));
153  }
155  auto SymbolName = MO.getMCSymbol()->getName();
156  return hash_combine(MO.getType(), MO.getTargetFlags(),
158  }
160  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
161  MO.getCFIIndex());
163  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
164  MO.getIntrinsicID());
166  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
167  MO.getPredicate());
168  }
169  llvm_unreachable("Invalid machine operand type");
170 }
171 
172 /// A stable hash value for machine instructions.
173 /// Returns 0 if no stable hash could be computed.
174 /// The hashing and equality testing functions ignore definitions so this is
175 /// useful for CSE, etc.
177  bool HashConstantPoolIndices,
178  bool HashMemOperands) {
179  // Build up a buffer of hash code components.
180  SmallVector<stable_hash, 16> HashComponents;
181  HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2);
182  HashComponents.push_back(MI.getOpcode());
183  HashComponents.push_back(MI.getFlags());
184  for (const MachineOperand &MO : MI.operands()) {
185  if (!HashVRegs && MO.isReg() && MO.isDef() &&
186  Register::isVirtualRegister(MO.getReg()))
187  continue; // Skip virtual register defs.
188 
189  if (MO.isCPI()) {
190  HashComponents.push_back(stable_hash_combine(
191  MO.getType(), MO.getTargetFlags(), MO.getIndex()));
192  continue;
193  }
194 
195  stable_hash StableHash = stableHashValue(MO);
196  if (!StableHash)
197  return 0;
198  HashComponents.push_back(StableHash);
199  }
200 
201  for (const auto *Op : MI.memoperands()) {
202  if (!HashMemOperands)
203  break;
204  HashComponents.push_back(static_cast<unsigned>(Op->getSize()));
205  HashComponents.push_back(static_cast<unsigned>(Op->getFlags()));
206  HashComponents.push_back(static_cast<unsigned>(Op->getOffset()));
207  HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering()));
208  HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace()));
209  HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID()));
210  HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value()));
211  HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering()));
212  }
213 
214  return stable_hash_combine_range(HashComponents.begin(),
215  HashComponents.end());
216 }
217 
219  SmallVector<stable_hash> HashComponents;
220  // TODO: Hash more stuff like block alignment and branch probabilities.
221  for (const auto &MI : MBB)
222  HashComponents.push_back(stableHashValue(MI));
223  return stable_hash_combine_range(HashComponents.begin(),
224  HashComponents.end());
225 }
226 
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_range(HashComponents.begin(),
233  HashComponents.end());
234 }
llvm::MachineOperand::MO_BlockAddress
@ MO_BlockAddress
Address of a basic block.
Definition: MachineOperand.h:62
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
llvm::stable_hash_combine_string
stable_hash stable_hash_combine_string(const StringRef &S)
Definition: StableHashing.h:99
MachineInstr.h
llvm::MachineOperand::MO_Immediate
@ MO_Immediate
Immediate operand.
Definition: MachineOperand.h:52
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::stable_hash_combine_range
stable_hash stable_hash_combine_range(InputIteratorT First, InputIteratorT Last)
Compute a stable_hash for a sequence of values.
Definition: StableHashing.h:84
llvm::stable_hash_combine
stable_hash stable_hash_combine(stable_hash A, stable_hash B)
Definition: StableHashing.h:51
llvm::MachineOperand::MO_ShuffleMask
@ MO_ShuffleMask
Other IR Constant for ISel (shuffle masks)
Definition: MachineOperand.h:70
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::MachineOperand::MO_RegisterLiveOut
@ MO_RegisterLiveOut
Mask of live-out registers.
Definition: MachineOperand.h:64
llvm::stable_hash_combine_array
stable_hash stable_hash_combine_array(const stable_hash *P, size_t C)
Definition: StableHashing.h:92
llvm::MachineOperand::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Definition: MachineOperand.h:592
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector< unsigned >
Statistic.h
ErrorHandling.h
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
MachineBasicBlock.h
APInt.h
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::MachineOperand::MO_CFIIndex
@ MO_CFIIndex
MCCFIInstruction index.
Definition: MachineOperand.h:67
llvm::MachineOperand::getTargetIndexName
const char * getTargetIndexName() const
getTargetIndexName - If this MachineOperand is a TargetIndex that has a name, attempt to get the name...
Definition: MachineOperand.cpp:439
llvm::MachineOperand::isCImm
bool isCImm() const
isCImm - Test if this is a MO_CImmediate operand.
Definition: MachineOperand.h:324
llvm::MachineInstr::getMF
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
Definition: MachineInstr.cpp:678
llvm::ConstantFP::getValueAPF
const APFloat & getValueAPF() const
Definition: Constants.h:298
Hashing.h
STLExtras.h
llvm::MachineOperand::getOffset
int64_t getOffset() const
Return the offset from the symbol in this operand.
Definition: MachineOperand.h:609
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MachineOperand::getMCSymbol
MCSymbol * getMCSymbol() const
Definition: MachineOperand.h:582
llvm::MachineOperand::MO_Register
@ MO_Register
Register operand.
Definition: MachineOperand.h:51
MachineRegisterInfo.h
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
StableHashing.h
Constants.h
llvm::MachineOperand::MO_GlobalAddress
@ MO_GlobalAddress
Address of a global value.
Definition: MachineOperand.h:61
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:546
llvm::MachineOperand::getRegMaskSize
static unsigned getRegMaskSize(unsigned NumRegs)
Returns number of elements needed for a regmask array.
Definition: MachineOperand.h:645
llvm::MachineOperand::getRegMask
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
Definition: MachineOperand.h:639
llvm::MachineOperand::MO_FrameIndex
@ MO_FrameIndex
Abstract Stack Frame Index.
Definition: MachineOperand.h:56
MCSymbol.h
llvm::stableHashValue
stable_hash stableHashValue(const MachineOperand &MO)
Definition: MachineStableHash.cpp:63
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
APFloat.h
llvm::MCSymbol::getName
StringRef getName() const
getName - Get the symbol name.
Definition: MCSymbol.h:198
MachineStableHash.h
llvm::APFloat::bitcastToAPInt
APInt bitcastToAPInt() const
Definition: APFloat.h:1145
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineOperand::MO_Metadata
@ MO_Metadata
Metadata reference (for debug info)
Definition: MachineOperand.h:65
llvm::MachineOperand::getTargetFlags
unsigned getTargetFlags() const
Definition: MachineOperand.h:220
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineOperand::getCImm
const ConstantInt * getCImm() const
Definition: MachineOperand.h:551
uint64_t
llvm::MachineRegisterInfo::def_instructions
iterator_range< def_instr_iterator > def_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:413
llvm::MachineOperand::MO_Predicate
@ MO_Predicate
Generic predicate for ISel.
Definition: MachineOperand.h:69
llvm::MachineOperand::MO_MCSymbol
@ MO_MCSymbol
MCSymbol reference (for debug/eh info)
Definition: MachineOperand.h:66
ArrayRef.h
llvm::MachineOperand::getType
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
Definition: MachineOperand.h:218
llvm::MachineOperand::getFPImm
const ConstantFP * getFPImm() const
Definition: MachineOperand.h:556
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::MachineOperand::getPredicate
unsigned getPredicate() const
Definition: MachineOperand.h:597
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:261
llvm::MachineOperand::getShuffleMask
ArrayRef< int > getShuffleMask() const
Definition: MachineOperand.h:602
llvm::MachineOperand::MO_TargetIndex
@ MO_TargetIndex
Target-dependent index+offset operand.
Definition: MachineOperand.h:58
iterator_range.h
llvm::MachineOperand::MO_FPImmediate
@ MO_FPImmediate
Floating-point immediate operand.
Definition: MachineOperand.h:54
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::MachineOperand::MO_JumpTableIndex
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
Definition: MachineOperand.h:59
llvm::MachineOperand::MO_CImmediate
@ MO_CImmediate
Immediate >64bit operand.
Definition: MachineOperand.h:53
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::transform
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1909
MachineInstrBundleIterator.h
uint32_t
llvm::MachineOperand::MO_MachineBasicBlock
@ MO_MachineBasicBlock
MachineBasicBlock reference.
Definition: MachineOperand.h:55
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::MachineOperand::MO_IntrinsicID
@ MO_IntrinsicID
Intrinsic ID for ISel.
Definition: MachineOperand.h:68
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:364
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::AMDGPU::HSAMD::Kernel::Key::SymbolName
constexpr char SymbolName[]
Key for Kernel::Metadata::mSymbolName.
Definition: AMDGPUMetadata.h:386
Alignment.h
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::MachineOperand::MO_ExternalSymbol
@ MO_ExternalSymbol
Name of external global symbol.
Definition: MachineOperand.h:60
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:566
llvm::MachineOperand::getCFIIndex
unsigned getCFIIndex() const
Definition: MachineOperand.h:587
SmallVector.h
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
llvm::MachineOperand::getSymbolName
const char * getSymbolName() const
Definition: MachineOperand.h:617
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
MachineMemOperand.h
MachineOperand.h
DenseMapInfo.h
Register.h
llvm::MachineOperand::MO_RegisterMask
@ MO_RegisterMask
Mask of preserved registers.
Definition: MachineOperand.h:63
MachineFunction.h
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:667
ilist_iterator.h
llvm::MachineOperand::MO_ConstantPoolIndex
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
Definition: MachineOperand.h:57