LLVM  9.0.0svn
CSEMIRBuilder.cpp
Go to the documentation of this file.
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 
16 
17 using namespace llvm;
18 
19 bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
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 
34 CSEMIRBuilder::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 
51 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
52  const GISelCSEInfo *CSEInfo = getCSEInfo();
53  if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
54  return false;
55  return true;
56 }
57 
58 void CSEMIRBuilder::profileDstOp(const DstOp &Op,
59  GISelInstProfileBuilder &B) const {
60  switch (Op.getDstOpKind()) {
63  break;
64  default:
66  break;
67  }
68 }
69 
70 void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
71  GISelInstProfileBuilder &B) const {
72  switch (Op.getSrcOpKind()) {
74  B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
75  break;
76  default:
77  B.addNodeIDRegType(Op.getReg());
78  break;
79  }
80 }
81 
82 void 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 
90 void 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 
105 MachineInstrBuilder 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 
114 bool 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 
125 CSEMIRBuilder::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];
132  return buildCopy(Op.getReg(), MIB->getOperand(0).getReg());
133  }
134  return MIB;
135 }
136 
138  ArrayRef<DstOp> DstOps,
139  ArrayRef<SrcOp> SrcOps,
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  }
166  bool CanCopy = checkCopyToDefsPossible(DstOps);
167  if (!canPerformCSEForOpc(Opc))
168  return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
169  // If we can CSE this instruction, but involves generating copies to multiple
170  // regs, give up. This frequently happens to UNMERGEs.
171  if (!CanCopy) {
172  auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
173  // CSEInfo would have tracked this instruction. Remove it from the temporary
174  // insts.
175  getCSEInfo()->handleRemoveInst(&*MIB);
176  return MIB;
177  }
179  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
180  void *InsertPos = nullptr;
181  profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
182  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
183  if (MIB) {
184  // Handle generating copies here.
185  return generateCopiesIfRequired(DstOps, MIB);
186  }
187  // This instruction does not exist in the CSEInfo. Build it and CSE it.
188  MachineInstrBuilder NewMIB =
189  MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
190  return memoizeMI(NewMIB, InsertPos);
191 }
192 
194  const ConstantInt &Val) {
195  constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
196  if (!canPerformCSEForOpc(Opc))
197  return MachineIRBuilder::buildConstant(Res, Val);
198 
199  // For vectors, CSE the element only for now.
200  LLT Ty = Res.getLLTTy(*getMRI());
201  if (Ty.isVector())
202  return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
203 
205  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
206  void *InsertPos = nullptr;
207  profileMBBOpcode(ProfBuilder, Opc);
208  profileDstOp(Res, ProfBuilder);
210  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
211  if (MIB) {
212  // Handle generating copies here.
213  return generateCopiesIfRequired({Res}, MIB);
214  }
215 
217  return memoizeMI(NewMIB, InsertPos);
218 }
219 
221  const ConstantFP &Val) {
222  constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
223  if (!canPerformCSEForOpc(Opc))
224  return MachineIRBuilder::buildFConstant(Res, Val);
225 
226  // For vectors, CSE the element only for now.
227  LLT Ty = Res.getLLTTy(*getMRI());
228  if (Ty.isVector())
229  return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val));
230 
232  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
233  void *InsertPos = nullptr;
234  profileMBBOpcode(ProfBuilder, Opc);
235  profileDstOp(Res, ProfBuilder);
237  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
238  if (MIB) {
239  // Handle generating copies here.
240  return generateCopiesIfRequired({Res}, MIB);
241  }
243  return memoizeMI(NewMIB, InsertPos);
244 }
virtual MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
The CSE Analysis object.
Definition: CSEInfo.h:71
static MachineOperand CreateCImm(const ConstantInt *CI)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator begin() const
Definition: ArrayRef.h:136
DstType getDstOpKind() const
const GISelInstProfileBuilder & addNodeIDImmediate(int64_t Imm) const
Definition: CSEInfo.cpp:302
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
const GISelInstProfileBuilder & addNodeIDFlag(unsigned Flag) const
Definition: CSEInfo.cpp:326
bool isVector() const
const GISelInstProfileBuilder & addNodeIDOpcode(unsigned Opc) const
Definition: CSEInfo.cpp:277
GISelCSEInfo * getCSEInfo()
Optional< APInt > ConstantFoldBinOp(unsigned Opcode, const unsigned Op1, const unsigned Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:322
SrcType getSrcOpKind() const
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val) override
Build and insert Res = G_FCONSTANT Val.
LLT getElementType() const
Returns the vector&#39;s element type. Only valid for vector types.
const GISelInstProfileBuilder & addNodeIDRegType(const LLT &Ty) const
Definition: CSEInfo.cpp:283
MachineFunction & getMF()
Getter for the function we currently build.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:212
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:197
Flag
These should be considered private to the implementation of the MCInstrDesc class.
Definition: MCInstrDesc.h:117
MachineBasicBlock::iterator getInsertPt()
Current insertion point for new instructions.
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:305
MachineRegisterInfo * getMRI()
Getter for MRI.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineInstrBuilder buildInstr(unsigned Opcode)
Build and insert <empty> = Opcode <empty>.
static MachineOperand CreateFPImm(const ConstantFP *CFP)
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
This file implements a version of MachineIRBuilder which CSEs insts within a MachineBasicBlock.
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:263
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:158
MachineInstrBuilder buildCopy(const DstOp &Res, const SrcOp &Op)
Build and insert Res = COPY Op.
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
virtual MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val)
Build and insert Res = G_FCONSTANT Val.
Register getReg() const
iterator end() const
Definition: ArrayRef.h:137
LLT getLLTTy(const MachineRegisterInfo &MRI) const
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
Register getReg() const
Representation of each machine instruction.
Definition: MachineInstr.h:64
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
const TargetRegisterClass * getRegClass() const
const GISelInstProfileBuilder & addNodeIDMBB(const MachineBasicBlock *MBB) const
Definition: CSEInfo.cpp:320
const MachineBasicBlock & getMBB() const
Getter for the basic block we currently build.
MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val) override
Build and insert Res = G_CONSTANT Val.
#define I(x, y, z)
Definition: MD5.cpp:58
CmpInst::Predicate getPredicate() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineInstrBuilder buildInstr(unsigned Opc, ArrayRef< DstOp > DstOps, ArrayRef< SrcOp > SrcOps, Optional< unsigned > Flag=None) override
const GISelInstProfileBuilder & addNodeIDMachineOperand(const MachineOperand &MO) const
Definition: CSEInfo.cpp:332
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
MachineInstrBuilder buildSplatVector(const DstOp &Res, const SrcOp &Src)
Build and insert Res = G_BUILD_VECTOR with Src replicated to fill the number of elements.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416