LLVM  12.0.0git
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 
17 
18 using namespace llvm;
19 
20 bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
22  auto MBBEnd = getMBB().end();
23  if (B == MBBEnd)
24  return true;
25  assert(A->getParent() == B->getParent() &&
26  "Iterators should be in same block");
27  const MachineBasicBlock *BBA = A->getParent();
28  MachineBasicBlock::const_iterator I = BBA->begin();
29  for (; &*I != A && &*I != B; ++I)
30  ;
31  return &*I == A;
32 }
33 
35 CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
36  void *&NodeInsertPos) {
37  GISelCSEInfo *CSEInfo = getCSEInfo();
38  assert(CSEInfo && "Can't get here without setting CSEInfo");
39  MachineBasicBlock *CurMBB = &getMBB();
40  MachineInstr *MI =
41  CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
42  if (MI) {
43  CSEInfo->countOpcodeHit(MI->getOpcode());
44  auto CurrPos = getInsertPt();
45  auto MII = MachineBasicBlock::iterator(MI);
46  if (MII == CurrPos) {
47  // Move the insert point ahead of the instruction so any future uses of
48  // this builder will have the def ready.
49  setInsertPt(*CurMBB, std::next(MII));
50  } else if (!dominates(MI, CurrPos)) {
51  CurMBB->splice(CurrPos, CurMBB, MI);
52  }
53  return MachineInstrBuilder(getMF(), MI);
54  }
55  return MachineInstrBuilder();
56 }
57 
58 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
59  const GISelCSEInfo *CSEInfo = getCSEInfo();
60  if (!CSEInfo || !CSEInfo->shouldCSE(Opc))
61  return false;
62  return true;
63 }
64 
65 void CSEMIRBuilder::profileDstOp(const DstOp &Op,
66  GISelInstProfileBuilder &B) const {
67  switch (Op.getDstOpKind()) {
69  B.addNodeIDRegType(Op.getRegClass());
70  break;
72  // Regs can have LLT&(RB|RC). If those exist, profile them as well.
73  B.addNodeIDReg(Op.getReg());
74  break;
75  }
76  default:
77  B.addNodeIDRegType(Op.getLLTTy(*getMRI()));
78  break;
79  }
80 }
81 
82 void CSEMIRBuilder::profileSrcOp(const SrcOp &Op,
83  GISelInstProfileBuilder &B) const {
84  switch (Op.getSrcOpKind()) {
86  B.addNodeIDImmediate(static_cast<int64_t>(Op.getImm()));
87  break;
89  B.addNodeIDImmediate(static_cast<int64_t>(Op.getPredicate()));
90  break;
91  default:
92  B.addNodeIDRegType(Op.getReg());
93  break;
94  }
95 }
96 
97 void CSEMIRBuilder::profileMBBOpcode(GISelInstProfileBuilder &B,
98  unsigned Opc) const {
99  // First add the MBB (Local CSE).
100  B.addNodeIDMBB(&getMBB());
101  // Then add the opcode.
102  B.addNodeIDOpcode(Opc);
103 }
104 
105 void CSEMIRBuilder::profileEverything(unsigned Opc, ArrayRef<DstOp> DstOps,
106  ArrayRef<SrcOp> SrcOps,
107  Optional<unsigned> Flags,
108  GISelInstProfileBuilder &B) const {
109 
110  profileMBBOpcode(B, Opc);
111  // Then add the DstOps.
112  profileDstOps(DstOps, B);
113  // Then add the SrcOps.
114  profileSrcOps(SrcOps, B);
115  // Add Flags if passed in.
116  if (Flags)
117  B.addNodeIDFlag(*Flags);
118 }
119 
120 MachineInstrBuilder CSEMIRBuilder::memoizeMI(MachineInstrBuilder MIB,
121  void *NodeInsertPos) {
122  assert(canPerformCSEForOpc(MIB->getOpcode()) &&
123  "Attempting to CSE illegal op");
124  MachineInstr *MIBInstr = MIB;
125  getCSEInfo()->insertInstr(MIBInstr, NodeInsertPos);
126  return MIB;
127 }
128 
129 bool CSEMIRBuilder::checkCopyToDefsPossible(ArrayRef<DstOp> DstOps) {
130  if (DstOps.size() == 1)
131  return true; // always possible to emit copy to just 1 vreg.
132 
133  return llvm::all_of(DstOps, [](const DstOp &Op) {
134  DstOp::DstType DT = Op.getDstOpKind();
135  return DT == DstOp::DstType::Ty_LLT || DT == DstOp::DstType::Ty_RC;
136  });
137 }
138 
140 CSEMIRBuilder::generateCopiesIfRequired(ArrayRef<DstOp> DstOps,
141  MachineInstrBuilder &MIB) {
142  assert(checkCopyToDefsPossible(DstOps) &&
143  "Impossible return a single MIB with copies to multiple defs");
144  if (DstOps.size() == 1) {
145  const DstOp &Op = DstOps[0];
146  if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
147  return buildCopy(Op.getReg(), MIB.getReg(0));
148  }
149 
150  // If we didn't generate a copy then we're re-using an existing node directly
151  // instead of emitting any code. Merge the debug location we wanted to emit
152  // into the instruction we're CSE'ing with. Debug locations arent part of the
153  // profile so we don't need to recompute it.
154  if (getDebugLoc()) {
155  GISelChangeObserver *Observer = getState().Observer;
156  if (Observer)
157  Observer->changingInstr(*MIB);
158  MIB->setDebugLoc(
160  if (Observer)
161  Observer->changedInstr(*MIB);
162  }
163 
164  return MIB;
165 }
166 
168  ArrayRef<DstOp> DstOps,
169  ArrayRef<SrcOp> SrcOps,
171  switch (Opc) {
172  default:
173  break;
174  case TargetOpcode::G_ADD:
175  case TargetOpcode::G_AND:
176  case TargetOpcode::G_ASHR:
177  case TargetOpcode::G_LSHR:
178  case TargetOpcode::G_MUL:
179  case TargetOpcode::G_OR:
180  case TargetOpcode::G_SHL:
181  case TargetOpcode::G_SUB:
182  case TargetOpcode::G_XOR:
183  case TargetOpcode::G_UDIV:
184  case TargetOpcode::G_SDIV:
185  case TargetOpcode::G_UREM:
186  case TargetOpcode::G_SREM: {
187  // Try to constant fold these.
188  assert(SrcOps.size() == 2 && "Invalid sources");
189  assert(DstOps.size() == 1 && "Invalid dsts");
190  if (Optional<APInt> Cst = ConstantFoldBinOp(Opc, SrcOps[0].getReg(),
191  SrcOps[1].getReg(), *getMRI()))
192  return buildConstant(DstOps[0], Cst->getSExtValue());
193  break;
194  }
195  case TargetOpcode::G_SEXT_INREG: {
196  assert(DstOps.size() == 1 && "Invalid dst ops");
197  assert(SrcOps.size() == 2 && "Invalid src ops");
198  const DstOp &Dst = DstOps[0];
199  const SrcOp &Src0 = SrcOps[0];
200  const SrcOp &Src1 = SrcOps[1];
201  if (auto MaybeCst =
202  ConstantFoldExtOp(Opc, Src0.getReg(), Src1.getImm(), *getMRI()))
203  return buildConstant(Dst, MaybeCst->getSExtValue());
204  break;
205  }
206  }
207  bool CanCopy = checkCopyToDefsPossible(DstOps);
208  if (!canPerformCSEForOpc(Opc))
209  return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
210  // If we can CSE this instruction, but involves generating copies to multiple
211  // regs, give up. This frequently happens to UNMERGEs.
212  if (!CanCopy) {
213  auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
214  // CSEInfo would have tracked this instruction. Remove it from the temporary
215  // insts.
216  getCSEInfo()->handleRemoveInst(&*MIB);
217  return MIB;
218  }
220  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
221  void *InsertPos = nullptr;
222  profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
223  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
224  if (MIB) {
225  // Handle generating copies here.
226  return generateCopiesIfRequired(DstOps, MIB);
227  }
228  // This instruction does not exist in the CSEInfo. Build it and CSE it.
229  MachineInstrBuilder NewMIB =
230  MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
231  return memoizeMI(NewMIB, InsertPos);
232 }
233 
235  const ConstantInt &Val) {
236  constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
237  if (!canPerformCSEForOpc(Opc))
238  return MachineIRBuilder::buildConstant(Res, Val);
239 
240  // For vectors, CSE the element only for now.
241  LLT Ty = Res.getLLTTy(*getMRI());
242  if (Ty.isVector())
243  return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
244 
246  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
247  void *InsertPos = nullptr;
248  profileMBBOpcode(ProfBuilder, Opc);
249  profileDstOp(Res, ProfBuilder);
251  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
252  if (MIB) {
253  // Handle generating copies here.
254  return generateCopiesIfRequired({Res}, MIB);
255  }
256 
258  return memoizeMI(NewMIB, InsertPos);
259 }
260 
262  const ConstantFP &Val) {
263  constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
264  if (!canPerformCSEForOpc(Opc))
265  return MachineIRBuilder::buildFConstant(Res, Val);
266 
267  // For vectors, CSE the element only for now.
268  LLT Ty = Res.getLLTTy(*getMRI());
269  if (Ty.isVector())
270  return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val));
271 
273  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
274  void *InsertPos = nullptr;
275  profileMBBOpcode(ProfBuilder, Opc);
276  profileDstOp(Res, ProfBuilder);
278  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
279  if (MIB) {
280  // Handle generating copies here.
281  return generateCopiesIfRequired({Res}, MIB);
282  }
284  return memoizeMI(NewMIB, InsertPos);
285 }
virtual MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
The CSE Analysis object.
Definition: CSEInfo.h:69
static MachineOperand CreateCImm(const ConstantInt *CI)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
Register getReg(unsigned Idx) const
Get the register for the operand index.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:416
GISelChangeObserver * Observer
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:1498
Optional< APInt > ConstantFoldBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:411
int64_t getImm() const
bool isVector() const
GISelCSEInfo * getCSEInfo()
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:475
MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val) override
Build and insert Res = G_FCONSTANT Val.
LLT getElementType() const
Returns the vector's element type. Only valid for vector types.
void setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II)
Set the insertion point before the specified position.
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:220
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:205
Flag
These should be considered private to the implementation of the MCInstrDesc class.
Definition: MCInstrDesc.h:147
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:313
MachineInstrBundleIterator< MachineInstr > iterator
MachineRegisterInfo * getMRI()
Getter for MRI.
Abstract class that contains various methods for clients to notify about changes.
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:156
This file implements a version of MachineIRBuilder which CSEs insts within a MachineBasicBlock.
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:273
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:166
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:77
virtual MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val)
Build and insert Res = G_FCONSTANT Val.
DebugLoc getDebugLoc()
Get the current instruction's debug location.
LLT getLLTTy(const MachineRegisterInfo &MRI) const
virtual void changingInstr(MachineInstr &MI)=0
This instruction is about to be mutated in some way.
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
Register getReg() const
Representation of each machine instruction.
Definition: MachineInstr.h:62
MachineIRBuilderState & getState()
Getter for the State.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
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:59
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:385
IRTranslator LLVM IR MI
MachineInstrBuilder buildSplatVector(const DstOp &Res, const SrcOp &Src)
Build and insert Res = G_BUILD_VECTOR with Src replicated to fill the number of elements.
Optional< APInt > ConstantFoldExtOp(unsigned Opcode, const Register Op1, uint64_t Imm, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:538
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.