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/APFloat.h"
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/Hashing.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/StableHashing.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/ADT/ilist_iterator.h"
23#include "llvm/CodeGen/MachineBasicBlock.h"
24#include "llvm/CodeGen/MachineFunction.h"
25#include "llvm/CodeGen/MachineInstr.h"
26#include "llvm/CodeGen/MachineInstrBundleIterator.h"
27#include "llvm/CodeGen/MachineMemOperand.h"
28#include "llvm/CodeGen/MachineOperand.h"
29#include "llvm/CodeGen/MachineRegisterInfo.h"
30#include "llvm/CodeGen/Register.h"
31#include "llvm/Config/llvm-config.h"
32#include "llvm/IR/Constants.h"
33#include "llvm/MC/MCSymbol.h"
34#include "llvm/Support/Alignment.h"
35#include "llvm/Support/ErrorHandling.h"
36
37#define DEBUG_TYPE "machine-stable-hash"
38
39using namespace llvm;
40
41STATISTIC(StableHashBailingMachineBasicBlock,
42          "Number of encountered unsupported MachineOperands that were "
43          "MachineBasicBlocks while computing stable hashes");
44STATISTIC(StableHashBailingConstantPoolIndex,
45          "Number of encountered unsupported MachineOperands that were "
46          "ConstantPoolIndex while computing stable hashes");
47STATISTIC(StableHashBailingTargetIndexNoName,
48          "Number of encountered unsupported MachineOperands that were "
49          "TargetIndex with no name");
50STATISTIC(StableHashBailingGlobalAddress,
51          "Number of encountered unsupported MachineOperands that were "
52          "GlobalAddress while computing stable hashes");
53STATISTIC(StableHashBailingBlockAddress,
54          "Number of encountered unsupported MachineOperands that were "
55          "BlockAddress while computing stable hashes");
56STATISTIC(StableHashBailingMetadataUnsupported,
57          "Number of encountered unsupported MachineOperands that were "
58          "Metadata of an unsupported kind while computing stable hashes");
59
60stable_hash llvm::stableHashValue(const MachineOperand &MO) {
61  switch (MO.getType()) {
62  case MachineOperand::MO_Register:
63    if (MO.getReg().isVirtual()) {
64      const MachineRegisterInfo &MRI = MO.getParent()->getMF()->getRegInfo();
65      SmallVector<unsigned> DefOpcodes;
66      for (auto &Def : MRI.def_instructions(MO.getReg()))
67        DefOpcodes.push_back(Def.getOpcode());
68      return hash_combine_range(DefOpcodes.begin(), DefOpcodes.end());
69    }
70
71    // Register operands don't have target flags.
72    return stable_hash_combine(MO.getType(), MO.getReg(), MO.getSubReg(),
73                               MO.isDef());
74  case MachineOperand::MO_Immediate:
75    return stable_hash_combine(MO.getType(), MO.getTargetFlags(), MO.getImm());
76  case MachineOperand::MO_CImmediate:
77  case MachineOperand::MO_FPImmediate: {
78    auto Val = MO.isCImm() ? MO.getCImm()->getValue()
79                           : MO.getFPImm()->getValueAPF().bitcastToAPInt();
80    auto ValHash =
81        stable_hash_combine_array(Val.getRawData(), Val.getNumWords());
82    return hash_combine(MO.getType(), MO.getTargetFlags(), ValHash);
83  }
84
85  case MachineOperand::MO_MachineBasicBlock:
86    StableHashBailingMachineBasicBlock++;
87    return 0;
88  case MachineOperand::MO_ConstantPoolIndex:
89    StableHashBailingConstantPoolIndex++;
90    return 0;
91  case MachineOperand::MO_BlockAddress:
92    StableHashBailingBlockAddress++;
93    return 0;
94  case MachineOperand::MO_Metadata:
95    StableHashBailingMetadataUnsupported++;
96    return 0;
97  case MachineOperand::MO_GlobalAddress:
98    StableHashBailingGlobalAddress++;
99    return 0;
100  case MachineOperand::MO_TargetIndex: {
101    if (const char *Name = MO.getTargetIndexName())
102      return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
103                                 stable_hash_combine_string(Name),
104                                 MO.getOffset());
105    StableHashBailingTargetIndexNoName++;
106    return 0;
107  }
108
109  case MachineOperand::MO_FrameIndex:
110  case MachineOperand::MO_JumpTableIndex:
111    return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
112                               MO.getIndex());
113
114  case MachineOperand::MO_ExternalSymbol:
115    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
116                        stable_hash_combine_string(MO.getSymbolName()));
117
118  case MachineOperand::MO_RegisterMask:
119  case MachineOperand::MO_RegisterLiveOut: {
120    if (const MachineInstr *MI = MO.getParent()) {
121      if (const MachineBasicBlock *MBB = MI->getParent()) {
122        if (const MachineFunction *MF = MBB->getParent()) {
123          const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
124          unsigned RegMaskSize =
125              MachineOperand::getRegMaskSize(TRI->getNumRegs());
126          const uint32_t *RegMask = MO.getRegMask();
127          std::vector<llvm::stable_hash> RegMaskHashes(RegMask,
128                                                       RegMask + RegMaskSize);
129          return hash_combine(MO.getType(), MO.getTargetFlags(),
130                              stable_hash_combine_array(RegMaskHashes.data(),
131                                                        RegMaskHashes.size()));
132        }
133      }
134    }
135
136    assert(0 && "MachineOperand not associated with any MachineFunction");
137    return hash_combine(MO.getType(), MO.getTargetFlags());
138  }
139
140  case MachineOperand::MO_ShuffleMask: {
141    std::vector<llvm::stable_hash> ShuffleMaskHashes;
142
143    llvm::transform(
144        MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes),
145        [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });
146
147    return hash_combine(MO.getType(), MO.getTargetFlags(),
148                        stable_hash_combine_array(ShuffleMaskHashes.data(),
149                                                  ShuffleMaskHashes.size()));
150  }
151  case MachineOperand::MO_MCSymbol: {
152    auto SymbolName = MO.getMCSymbol()->getName();
153    return hash_combine(MO.getType(), MO.getTargetFlags(),
154                        stable_hash_combine_string(SymbolName));
155  }
156  case MachineOperand::MO_CFIIndex:
157    return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
158                               MO.getCFIIndex());
159  case MachineOperand::MO_IntrinsicID:
160    return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
161                               MO.getIntrinsicID());
162  case MachineOperand::MO_Predicate:
163    return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
164                               MO.getPredicate());
165  case MachineOperand::MO_DbgInstrRef:
166    return stable_hash_combine(MO.getType(), MO.getInstrRefInstrIndex(),
167                               MO.getInstrRefOpIndex());
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.
176stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs,
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() && MO.getReg().isVirtual())
186      continue; // Skip virtual register defs.
187
188    if (MO.isCPI()) {
189      HashComponents.push_back(stable_hash_combine(
190          MO.getType(), MO.getTargetFlags(), MO.getIndex()));
191      continue;
192    }
193
194    stable_hash StableHash = stableHashValue(MO);
195    if (!StableHash)
196      return 0;
197    HashComponents.push_back(StableHash);
198  }
199
200  for (const auto *Op : MI.memoperands()) {
201    if (!HashMemOperands)
202      break;
203    HashComponents.push_back(static_cast<unsigned>(Op->getSize()));
204    HashComponents.push_back(static_cast<unsigned>(Op->getFlags()));
205    HashComponents.push_back(static_cast<unsigned>(Op->getOffset()));
206    HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering()));
207    HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace()));
208    HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID()));
209    HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value()));
210    HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering()));
211  }
212
213  return stable_hash_combine_range(HashComponents.begin(),
214                                   HashComponents.end());
215}
216
217stable_hash llvm::stableHashValue(const MachineBasicBlock &MBB) {
218  SmallVector<stable_hash> HashComponents;
219  // TODO: Hash more stuff like block alignment and branch probabilities.
220  for (const auto &MI : MBB)
221    HashComponents.push_back(stableHashValue(MI));
222  return stable_hash_combine_range(HashComponents.begin(),
223                                   HashComponents.end());
224}
225
226stable_hash llvm::stableHashValue(const MachineFunction &MF) {
227  SmallVector<stable_hash> HashComponents;
228  // TODO: Hash lots more stuff like function alignment and stack objects.
229  for (const auto &MBB : MF)
230    HashComponents.push_back(stableHashValue(MBB));
231  return stable_hash_combine_range(HashComponents.begin(),
232                                   HashComponents.end());
233}
234