CSEMIRBuilder.cpp revision 360784 
1//===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.cpp - MIBuilder--*- C++ -*-==//
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/// \file
9/// This file implements the CSEMIRBuilder class which CSEs as it builds
10/// instructions.
11//===----------------------------------------------------------------------===//
12//
13
14#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
15#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
16
17using namespace llvm;
18
19bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
20                              MachineBasicBlock::const_iterator B) const {
21  auto MBBEnd = getMBB().end();
22  if (B == MBBEnd)
23    return true;
24  assert(A->getParent() == B->getParent() &&
25         "Iterators should be in same block");
26  const MachineBasicBlock *BBA = A->getParent();
27  MachineBasicBlock::const_iterator I = BBA->begin();
28  for (; &*I != A && &*I != B; ++I)
29    ;
30  return &*I == A;
31}
32
33MachineInstrBuilder
34CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
35                                       void *&NodeInsertPos) {
36  GISelCSEInfo *CSEInfo = getCSEInfo();
37  assert(CSEInfo && "Can't get here without setting CSEInfo");
38  MachineBasicBlock *CurMBB = &getMBB();
39  MachineInstr *MI =
40      CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
41  if (MI) {
42    CSEInfo->countOpcodeHit(MI->getOpcode());
43    auto CurrPos = getInsertPt();
44    if (!dominates(MI, CurrPos))
45      CurMBB->splice(CurrPos, CurMBB, MI);
46    return MachineInstrBuilder(getMF(), MI);
47  }
48  return MachineInstrBuilder();
49}
50
51bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
52  const GISelCSEInfo *CSEInfo = getCSEInfo();
53  if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
54    return false;
55  return true;
56}
57
58void CSEMIRBuilder::profileDstOp(const DstOp &Op,
59                                 GISelInstProfileBuilder &B) const {
60  switch (Op.getDstOpKind()) {
61  case DstOp::DstType::Ty_RC:
62    B.addNodeIDRegType(Op.getRegClass());
63    break;
64  default:
65    B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
66    break;
67  }
68}
69
70void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
71                                 GISelInstProfileBuilder &B) const {
72  switch (Op.getSrcOpKind()) {
73  case SrcOp::SrcType::Ty_Predicate:
74    B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
75    break;
76  default:
77    B.addNodeIDRegType(Op.getReg());
78    break;
79  }
80}
81
82void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
83                                     unsigned Opc) const {
84  // First add the MBB (Local CSE).
85  B.addNodeIDMBB(&getMBB());
86  // Then add the opcode.
87  B.addNodeIDOpcode(Opc);
88}
89
90void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
91                                      ArrayRef<SrcOp> SrcOps,
92                                      Optional<unsigned> Flags,
93                                      GISelInstProfileBuilder &B) const {
94
95  profileMBBOpcode(B, Opc);
96  // Then add the DstOps.
97  profileDstOps(DstOps, B);
98  // Then add the SrcOps.
99  profileSrcOps(SrcOps, B);
100  // Add Flags if passed in.
101  if (Flags)
102    B.addNodeIDFlag(*Flags);
103}
104
105MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
106                                             void *NodeInsertPos) {
107  assert(canPerformCSEForOpc(MIB->getOpcode()) &&
108         "Attempting to CSE illegal op");
109  MachineInstr *MIBInstr = MIB;
110  getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);
111  return MIB;
112}
113
114bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
115  if (DstOps.size() == 1)
116    return true; // always possible to emit copy to just 1 vreg.
117
118  return std::all_of(DstOps.begin(), DstOps.end(), [](const DstOp &Op) {
119    DstOp::DstType DT = Op.getDstOpKind();
120    return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
121  });
122}
123
124MachineInstrBuilder
125CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
126                                        MachineInstrBuilder &MIB) {
127  assert(checkCopyToDefsPossible(DstOps) &&
128         "Impossible return a single MIB with copies to multiple defs");
129  if (DstOps.size() == 1) {
130    const DstOp &Op = DstOps[0];
131    if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
132      return buildCopy(Op.getReg(), MIB->getOperand(0).getReg());
133  }
134  return MIB;
135}
136
137MachineInstrBuilder CSEMIRBuilder::buildInstr(unsigned Opc,
138                                              ArrayRef<DstOp> DstOps,
139                                              ArrayRef<SrcOp> SrcOps,
140                                              Optional<unsigned> Flag) {
141  switch (Opc) {
142  default:
143    break;
144  case TargetOpcode::G_ADD:
145  case TargetOpcode::G_AND:
146  case TargetOpcode::G_ASHR:
147  case TargetOpcode::G_LSHR:
148  case TargetOpcode::G_MUL:
149  case TargetOpcode::G_OR:
150  case TargetOpcode::G_SHL:
151  case TargetOpcode::G_SUB:
152  case TargetOpcode::G_XOR:
153  case TargetOpcode::G_UDIV:
154  case TargetOpcode::G_SDIV:
155  case TargetOpcode::G_UREM:
156  case TargetOpcode::G_SREM: {
157    // Try to constant fold these.
158    assert(SrcOps.size() == 2 && "Invalid sources");
159    assert(DstOps.size() == 1 && "Invalid dsts");
160    if (Optional<APInt> Cst = ConstantFoldBinOp(Opc, SrcOps[0].getReg(),
161                                                SrcOps[1].getReg(), *getMRI()))
162      return buildConstant(DstOps[0], Cst->getSExtValue());
163    break;
164  }
165  case TargetOpcode::G_SEXT_INREG: {
166    assert(DstOps.size() == 1 && "Invalid dst ops");
167    assert(SrcOps.size() == 2 && "Invalid src ops");
168    const DstOp &Dst = DstOps[0];
169    const SrcOp &Src0 = SrcOps[0];
170    const SrcOp &Src1 = SrcOps[1];
171    if (auto MaybeCst =
172            ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
173      return buildConstant(Dst, MaybeCst->getSExtValue());
174    break;
175  }
176  }
177  bool CanCopy = checkCopyToDefsPossible(DstOps);
178  if (!canPerformCSEForOpc(Opc))
179    return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
180  // If we can CSE this instruction, but involves generating copies to multiple
181  // regs, give up. This frequently happens to UNMERGEs.
182  if (!CanCopy) {
183    auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
184    // CSEInfo would have tracked this instruction. Remove it from the temporary
185    // insts.
186    getCSEInfo()->handleRemoveInst(&*MIB);
187    return MIB;
188  }
189  FoldingSetNodeID ID;
190  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
191  void *InsertPos = nullptr;
192  profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
193  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
194  if (MIB) {
195    // Handle generating copies here.
196    return generateCopiesIfRequired(DstOps, MIB);
197  }
198  // This instruction does not exist in the CSEInfo. Build it and CSE it.
199  MachineInstrBuilder NewMIB =
200      MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
201  return memoizeMI(NewMIB, InsertPos);
202}
203
204MachineInstrBuilder CSEMIRBuilder::buildConstant(const DstOp &Res,
205                                                 const ConstantInt &Val) {
206  constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
207  if (!canPerformCSEForOpc(Opc))
208    return MachineIRBuilder::buildConstant(Res, Val);
209
210  // For vectors, CSE the element only for now.
211  LLT Ty = Res.getLLTTy(*getMRI());
212  if (Ty.isVector())
213    return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
214
215  FoldingSetNodeID ID;
216  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
217  void *InsertPos = nullptr;
218  profileMBBOpcode(ProfBuilder, Opc);
219  profileDstOp(Res, ProfBuilder);
220  ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateCImm(&Val));
221  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
222  if (MIB) {
223    // Handle generating copies here.
224    return generateCopiesIfRequired({Res}, MIB);
225  }
226
227  MachineInstrBuilder NewMIB = MachineIRBuilder::buildConstant(Res, Val);
228  return memoizeMI(NewMIB, InsertPos);
229}
230
231MachineInstrBuilder CSEMIRBuilder::buildFConstant(const DstOp &Res,
232                                                  const ConstantFP &Val) {
233  constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
234  if (!canPerformCSEForOpc(Opc))
235    return MachineIRBuilder::buildFConstant(Res, Val);
236
237  // For vectors, CSE the element only for now.
238  LLT Ty = Res.getLLTTy(*getMRI());
239  if (Ty.isVector())
240    return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val));
241
242  FoldingSetNodeID ID;
243  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
244  void *InsertPos = nullptr;
245  profileMBBOpcode(ProfBuilder, Opc);
246  profileDstOp(Res, ProfBuilder);
247  ProfBuilder.addNodeIDMachineOperand(MachineOperand::CreateFPImm(&Val));
248  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
249  if (MIB) {
250    // Handle generating copies here.
251    return generateCopiesIfRequired({Res}, MIB);
252  }
253  MachineInstrBuilder NewMIB = MachineIRBuilder::buildFConstant(Res, Val);
254  return memoizeMI(NewMIB, InsertPos);
255}
256