1//===- CSEInfo.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//
10//===----------------------------------------------------------------------===//
11#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
12#include "llvm/CodeGen/MachineRegisterInfo.h"
13#include "llvm/InitializePasses.h"
14
15#define DEBUG_TYPE "cseinfo"
16
17using namespace llvm;
18char llvm::GISelCSEAnalysisWrapperPass::ID = 0;
19GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass()
20    : MachineFunctionPass(ID) {
21  initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());
22}
23INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
24                      "Analysis containing CSE Info", false, true)
25INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
26                    "Analysis containing CSE Info", false, true)
27
28/// -------- UniqueMachineInstr -------------//
29
30void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
31  GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
32}
33/// -----------------------------------------
34
35/// --------- CSEConfigFull ---------- ///
36bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {
37  switch (Opc) {
38  default:
39    break;
40  case TargetOpcode::G_ADD:
41  case TargetOpcode::G_AND:
42  case TargetOpcode::G_ASHR:
43  case TargetOpcode::G_LSHR:
44  case TargetOpcode::G_MUL:
45  case TargetOpcode::G_OR:
46  case TargetOpcode::G_SHL:
47  case TargetOpcode::G_SUB:
48  case TargetOpcode::G_XOR:
49  case TargetOpcode::G_UDIV:
50  case TargetOpcode::G_SDIV:
51  case TargetOpcode::G_UREM:
52  case TargetOpcode::G_SREM:
53  case TargetOpcode::G_CONSTANT:
54  case TargetOpcode::G_FCONSTANT:
55  case TargetOpcode::G_ZEXT:
56  case TargetOpcode::G_SEXT:
57  case TargetOpcode::G_ANYEXT:
58  case TargetOpcode::G_UNMERGE_VALUES:
59  case TargetOpcode::G_TRUNC:
60  case TargetOpcode::G_PTR_ADD:
61    return true;
62  }
63  return false;
64}
65
66bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
67  return Opc == TargetOpcode::G_CONSTANT;
68}
69
70std::unique_ptr<CSEConfigBase>
71llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) {
72  std::unique_ptr<CSEConfigBase> Config;
73  if (Level == CodeGenOpt::None)
74    Config = std::make_unique<CSEConfigConstantOnly>();
75  else
76    Config = std::make_unique<CSEConfigFull>();
77  return Config;
78}
79
80/// -----------------------------------------
81
82/// -------- GISelCSEInfo -------------//
83void GISelCSEInfo::setMF(MachineFunction &MF) {
84  this->MF = &MF;
85  this->MRI = &MF.getRegInfo();
86}
87
88GISelCSEInfo::~GISelCSEInfo() {}
89
90bool GISelCSEInfo::isUniqueMachineInstValid(
91    const UniqueMachineInstr &UMI) const {
92  // Should we check here and assert that the instruction has been fully
93  // constructed?
94  // FIXME: Any other checks required to be done here? Remove this method if
95  // none.
96  return true;
97}
98
99void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
100  bool Removed = CSEMap.RemoveNode(UMI);
101  (void)Removed;
102  assert(Removed && "Invalidation called on invalid UMI");
103  // FIXME: Should UMI be deallocated/destroyed?
104}
105
106UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
107                                                  MachineBasicBlock *MBB,
108                                                  void *&InsertPos) {
109  auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
110  if (Node) {
111    if (!isUniqueMachineInstValid(*Node)) {
112      invalidateUniqueMachineInstr(Node);
113      return nullptr;
114    }
115
116    if (Node->MI->getParent() != MBB)
117      return nullptr;
118  }
119  return Node;
120}
121
122void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
123  handleRecordedInsts();
124  assert(UMI);
125  UniqueMachineInstr *MaybeNewNode = UMI;
126  if (InsertPos)
127    CSEMap.InsertNode(UMI, InsertPos);
128  else
129    MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
130  if (MaybeNewNode != UMI) {
131    // A similar node exists in the folding set. Let's ignore this one.
132    return;
133  }
134  assert(InstrMapping.count(UMI->MI) == 0 &&
135         "This instruction should not be in the map");
136  InstrMapping[UMI->MI] = MaybeNewNode;
137}
138
139UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
140  assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
141  auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
142  return Node;
143}
144
145void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
146  assert(MI);
147  // If it exists in temporary insts, remove it.
148  TemporaryInsts.remove(MI);
149  auto *Node = getUniqueInstrForMI(MI);
150  insertNode(Node, InsertPos);
151}
152
153MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
154                                                    MachineBasicBlock *MBB,
155                                                    void *&InsertPos) {
156  handleRecordedInsts();
157  if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
158    LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
159    return const_cast<MachineInstr *>(Inst->MI);
160  }
161  return nullptr;
162}
163
164void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
165#ifndef NDEBUG
166  if (OpcodeHitTable.count(Opc))
167    OpcodeHitTable[Opc] += 1;
168  else
169    OpcodeHitTable[Opc] = 1;
170#endif
171  // Else do nothing.
172}
173
174void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
175  if (shouldCSE(MI->getOpcode())) {
176    TemporaryInsts.insert(MI);
177    LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
178  }
179}
180
181void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
182  assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
183  auto *UMI = InstrMapping.lookup(MI);
184  LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
185  if (UMI) {
186    // Invalidate this MI.
187    invalidateUniqueMachineInstr(UMI);
188    InstrMapping.erase(MI);
189  }
190  /// Now insert the new instruction.
191  if (UMI) {
192    /// We'll reuse the same UniqueMachineInstr to avoid the new
193    /// allocation.
194    *UMI = UniqueMachineInstr(MI);
195    insertNode(UMI, nullptr);
196  } else {
197    /// This is a new instruction. Allocate a new UniqueMachineInstr and
198    /// Insert.
199    insertInstr(MI);
200  }
201}
202
203void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
204  if (auto *UMI = InstrMapping.lookup(MI)) {
205    invalidateUniqueMachineInstr(UMI);
206    InstrMapping.erase(MI);
207  }
208  TemporaryInsts.remove(MI);
209}
210
211void GISelCSEInfo::handleRecordedInsts() {
212  while (!TemporaryInsts.empty()) {
213    auto *MI = TemporaryInsts.pop_back_val();
214    handleRecordedInst(MI);
215  }
216}
217
218bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
219  // Only GISel opcodes are CSEable
220  if (!isPreISelGenericOpcode(Opc))
221    return false;
222  assert(CSEOpt.get() && "CSEConfig not set");
223  return CSEOpt->shouldCSEOpc(Opc);
224}
225
226void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
227void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
228void GISelCSEInfo::changingInstr(MachineInstr &MI) {
229  // For now, perform erase, followed by insert.
230  erasingInstr(MI);
231  createdInstr(MI);
232}
233void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
234
235void GISelCSEInfo::analyze(MachineFunction &MF) {
236  setMF(MF);
237  for (auto &MBB : MF) {
238    if (MBB.empty())
239      continue;
240    for (MachineInstr &MI : MBB) {
241      if (!shouldCSE(MI.getOpcode()))
242        continue;
243      LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
244      insertInstr(&MI);
245    }
246  }
247}
248
249void GISelCSEInfo::releaseMemory() {
250  print();
251  CSEMap.clear();
252  InstrMapping.clear();
253  UniqueInstrAllocator.Reset();
254  TemporaryInsts.clear();
255  CSEOpt.reset();
256  MRI = nullptr;
257  MF = nullptr;
258#ifndef NDEBUG
259  OpcodeHitTable.clear();
260#endif
261}
262
263void GISelCSEInfo::print() {
264  LLVM_DEBUG(for (auto &It
265                  : OpcodeHitTable) {
266    dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
267           << "\n";
268  };);
269}
270/// -----------------------------------------
271// ---- Profiling methods for FoldingSetNode --- //
272const GISelInstProfileBuilder &
273GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
274  addNodeIDMBB(MI->getParent());
275  addNodeIDOpcode(MI->getOpcode());
276  for (auto &Op : MI->operands())
277    addNodeIDMachineOperand(Op);
278  addNodeIDFlag(MI->getFlags());
279  return *this;
280}
281
282const GISelInstProfileBuilder &
283GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
284  ID.AddInteger(Opc);
285  return *this;
286}
287
288const GISelInstProfileBuilder &
289GISelInstProfileBuilder::addNodeIDRegType(const LLT &Ty) const {
290  uint64_t Val = Ty.getUniqueRAWLLTData();
291  ID.AddInteger(Val);
292  return *this;
293}
294
295const GISelInstProfileBuilder &
296GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
297  ID.AddPointer(RC);
298  return *this;
299}
300
301const GISelInstProfileBuilder &
302GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
303  ID.AddPointer(RB);
304  return *this;
305}
306
307const GISelInstProfileBuilder &
308GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
309  ID.AddInteger(Imm);
310  return *this;
311}
312
313const GISelInstProfileBuilder &
314GISelInstProfileBuilder::addNodeIDRegNum(unsigned Reg) const {
315  ID.AddInteger(Reg);
316  return *this;
317}
318
319const GISelInstProfileBuilder &
320GISelInstProfileBuilder::addNodeIDRegType(const unsigned Reg) const {
321  addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
322  return *this;
323}
324
325const GISelInstProfileBuilder &
326GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
327  ID.AddPointer(MBB);
328  return *this;
329}
330
331const GISelInstProfileBuilder &
332GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
333  if (Flag)
334    ID.AddInteger(Flag);
335  return *this;
336}
337
338const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
339    const MachineOperand &MO) const {
340  if (MO.isReg()) {
341    Register Reg = MO.getReg();
342    if (!MO.isDef())
343      addNodeIDRegNum(Reg);
344    LLT Ty = MRI.getType(Reg);
345    if (Ty.isValid())
346      addNodeIDRegType(Ty);
347    auto *RB = MRI.getRegBankOrNull(Reg);
348    if (RB)
349      addNodeIDRegType(RB);
350    auto *RC = MRI.getRegClassOrNull(Reg);
351    if (RC)
352      addNodeIDRegType(RC);
353    assert(!MO.isImplicit() && "Unhandled case");
354  } else if (MO.isImm())
355    ID.AddInteger(MO.getImm());
356  else if (MO.isCImm())
357    ID.AddPointer(MO.getCImm());
358  else if (MO.isFPImm())
359    ID.AddPointer(MO.getFPImm());
360  else if (MO.isPredicate())
361    ID.AddInteger(MO.getPredicate());
362  else
363    llvm_unreachable("Unhandled operand type");
364  // Handle other types
365  return *this;
366}
367
368GISelCSEInfo &
369GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
370                             bool Recompute) {
371  if (!AlreadyComputed || Recompute) {
372    Info.setCSEConfig(std::move(CSEOpt));
373    Info.analyze(*MF);
374    AlreadyComputed = true;
375  }
376  return Info;
377}
378void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
379  AU.setPreservesAll();
380  MachineFunctionPass::getAnalysisUsage(AU);
381}
382
383bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
384  releaseMemory();
385  Wrapper.setMF(MF);
386  return false;
387}
388