LLVM  14.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();
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);
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);
204  break;
205  }
206  case TargetOpcode::G_SITOFP:
207  case TargetOpcode::G_UITOFP: {
208  // Try to constant fold these.
209  assert(SrcOps.size() == 1 && "Invalid sources");
210  assert(DstOps.size() == 1 && "Invalid dsts");
212  Opc, DstOps[0].getLLTTy(*getMRI()), SrcOps[0].getReg(), *getMRI()))
213  return buildFConstant(DstOps[0], *Cst);
214  break;
215  }
216  }
217  bool CanCopy = checkCopyToDefsPossible(DstOps);
218  if (!canPerformCSEForOpc(Opc))
219  return MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
220  // If we can CSE this instruction, but involves generating copies to multiple
221  // regs, give up. This frequently happens to UNMERGEs.
222  if (!CanCopy) {
223  auto MIB = MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
224  // CSEInfo would have tracked this instruction. Remove it from the temporary
225  // insts.
226  getCSEInfo()->handleRemoveInst(&*MIB);
227  return MIB;
228  }
230  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
231  void *InsertPos = nullptr;
232  profileEverything(Opc, DstOps, SrcOps, Flag, ProfBuilder);
233  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
234  if (MIB) {
235  // Handle generating copies here.
236  return generateCopiesIfRequired(DstOps, MIB);
237  }
238  // This instruction does not exist in the CSEInfo. Build it and CSE it.
239  MachineInstrBuilder NewMIB =
240  MachineIRBuilder::buildInstr(Opc, DstOps, SrcOps, Flag);
241  return memoizeMI(NewMIB, InsertPos);
242 }
243 
245  const ConstantInt &Val) {
246  constexpr unsigned Opc = TargetOpcode::G_CONSTANT;
247  if (!canPerformCSEForOpc(Opc))
248  return MachineIRBuilder::buildConstant(Res, Val);
249 
250  // For vectors, CSE the element only for now.
251  LLT Ty = Res.getLLTTy(*getMRI());
252  if (Ty.isVector())
253  return buildSplatVector(Res, buildConstant(Ty.getElementType(), Val));
254 
256  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
257  void *InsertPos = nullptr;
258  profileMBBOpcode(ProfBuilder, Opc);
259  profileDstOp(Res, ProfBuilder);
261  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
262  if (MIB) {
263  // Handle generating copies here.
264  return generateCopiesIfRequired({Res}, MIB);
265  }
266 
268  return memoizeMI(NewMIB, InsertPos);
269 }
270 
272  const ConstantFP &Val) {
273  constexpr unsigned Opc = TargetOpcode::G_FCONSTANT;
274  if (!canPerformCSEForOpc(Opc))
275  return MachineIRBuilder::buildFConstant(Res, Val);
276 
277  // For vectors, CSE the element only for now.
278  LLT Ty = Res.getLLTTy(*getMRI());
279  if (Ty.isVector())
280  return buildSplatVector(Res, buildFConstant(Ty.getElementType(), Val));
281 
283  GISelInstProfileBuilder ProfBuilder(ID, *getMRI());
284  void *InsertPos = nullptr;
285  profileMBBOpcode(ProfBuilder, Opc);
286  profileDstOp(Res, ProfBuilder);
288  MachineInstrBuilder MIB = getDominatingInstrForID(ID, InsertPos);
289  if (MIB) {
290  // Handle generating copies here.
291  return generateCopiesIfRequired({Res}, MIB);
292  }
294  return memoizeMI(NewMIB, InsertPos);
295 }
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DstOp::DstType::Ty_LLT
@ Ty_LLT
llvm::GISelCSEInfo::handleRemoveInst
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:206
llvm::DILocation::getMergedLocation
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...
Definition: DebugInfoMetadata.cpp:100
DebugInfoMetadata.h
llvm::MachineIRBuilder::getCSEInfo
GISelCSEInfo * getCSEInfo()
Definition: MachineIRBuilder.h:297
llvm::MachineIRBuilder::buildSplatVector
MachineInstrBuilder buildSplatVector(const DstOp &Res, const SrcOp &Src)
Build and insert Res = G_BUILD_VECTOR with Src replicated to fill the number of elements.
Definition: MachineIRBuilder.cpp:641
llvm::MachineIRBuilder::getMRI
MachineRegisterInfo * getMRI()
Getter for MRI.
Definition: MachineIRBuilder.h:280
llvm::GISelCSEInfo
The CSE Analysis object.
Definition: CSEInfo.h:69
llvm::GISelInstProfileBuilder::addNodeIDMachineOperand
const GISelInstProfileBuilder & addNodeIDMachineOperand(const MachineOperand &MO) const
Definition: CSEInfo.cpp:398
llvm::GISelCSEInfo::shouldCSE
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:221
llvm::Optional< unsigned >
llvm::MachineInstr::setDebugLoc
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
Definition: MachineInstr.h:1745
llvm::SrcOp::SrcType::Ty_Predicate
@ Ty_Predicate
llvm::MachineIRBuilder::getDebugLoc
const DebugLoc & getDebugLoc()
Get the current instruction's debug location.
Definition: MachineIRBuilder.h:358
llvm::MachineIRBuilder::buildConstant
virtual MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
Definition: MachineIRBuilder.cpp:255
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::all_of
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:1551
llvm::DstOp::DstType::Ty_RC
@ Ty_RC
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
CSEMIRBuilder.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ConstantFoldExtOp
Optional< APInt > ConstantFoldExtOp(unsigned Opcode, const Register Op1, uint64_t Imm, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:699
llvm::MCID::Flag
Flag
These should be considered private to the implementation of the MCInstrDesc class.
Definition: MCInstrDesc.h:146
llvm::MachineIRBuilder::getMF
MachineFunction & getMF()
Getter for the function we currently build.
Definition: MachineIRBuilder.h:262
llvm::ConstantFP
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:257
llvm::ConstantFoldIntToFloat
Optional< APFloat > ConstantFoldIntToFloat(unsigned Opcode, LLT DstTy, Register Src, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:716
llvm::GISelChangeObserver::changingInstr
virtual void changingInstr(MachineInstr &MI)=0
This instruction is about to be mutated in some way.
llvm::CSEMIRBuilder::buildFConstant
MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val) override
Build and insert Res = G_FCONSTANT Val.
Definition: CSEMIRBuilder.cpp:271
llvm::MachineInstrBuilder::getReg
Register getReg(unsigned Idx) const
Get the register for the operand index.
Definition: MachineInstrBuilder.h:94
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::CSEMIRBuilder::buildConstant
MachineInstrBuilder buildConstant(const DstOp &Res, const ConstantInt &Val) override
Build and insert Res = G_CONSTANT Val.
Definition: CSEMIRBuilder.cpp:244
llvm::SrcOp::getImm
int64_t getImm() const
Definition: MachineIRBuilder.h:193
llvm::GISelChangeObserver::changedInstr
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:418
llvm::MachineIRBuilder::buildFConstant
virtual MachineInstrBuilder buildFConstant(const DstOp &Res, const ConstantFP &Val)
Build and insert Res = G_FCONSTANT Val.
Definition: MachineIRBuilder.cpp:284
llvm::MachineIRBuilder::setInsertPt
void setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II)
Set the insertion point before the specified position.
Definition: MachineIRBuilder.h:306
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
llvm::MachineIRBuilder::getInsertPt
MachineBasicBlock::iterator getInsertPt()
Current insertion point for new instructions.
Definition: MachineIRBuilder.h:301
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LLT::isVector
bool isVector() const
Definition: LowLevelTypeImpl.h:123
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineIRBuilder::getMBB
const MachineBasicBlock & getMBB() const
Getter for the basic block we currently build.
Definition: MachineIRBuilder.h:287
llvm::MachineIRBuilderState::Observer
GISelChangeObserver * Observer
Definition: MachineIRBuilder.h:53
llvm::MachineIRBuilder::buildInstr
MachineInstrBuilder buildInstr(unsigned Opcode)
Build and insert <empty> = Opcode <empty>.
Definition: MachineIRBuilder.h:367
llvm::MachineBasicBlock::iterator
MachineInstrBundleIterator< MachineInstr > iterator
Definition: MachineBasicBlock.h:233
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::SrcOp::getReg
Register getReg() const
Definition: MachineIRBuilder.h:171
llvm::MachineBasicBlock::splice
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 '...
Definition: MachineBasicBlock.h:950
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:489
llvm::MachineIRBuilder::buildCopy
MachineInstrBuilder buildCopy(const DstOp &Res, const SrcOp &Op)
Build and insert Res = COPY Op.
Definition: MachineIRBuilder.cpp:238
llvm::GISelCSEInfo::countOpcodeHit
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:167
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
llvm::MachineOperand::CreateCImm
static MachineOperand CreateCImm(const ConstantInt *CI)
Definition: MachineOperand.h:779
llvm::GISelChangeObserver
Abstract class that contains various methods for clients to notify about changes.
Definition: GISelChangeObserver.h:29
llvm::DstOp::DstType
DstType
Definition: MachineIRBuilder.h:66
llvm::SrcOp::SrcType::Ty_Imm
@ Ty_Imm
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::GISelInstProfileBuilder
Definition: CSEInfo.h:167
llvm::DstOp::getLLTTy
LLT getLLTTy(const MachineRegisterInfo &MRI) const
Definition: MachineIRBuilder.h:87
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::DstOp::DstType::Ty_Reg
@ Ty_Reg
llvm::DstOp
Definition: MachineIRBuilder.h:58
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::MachineIRBuilder::getState
MachineIRBuilderState & getState()
Getter for the State.
Definition: MachineIRBuilder.h:284
GISelChangeObserver.h
llvm::LLT::getElementType
LLT getElementType() const
Returns the vector's element type. Only valid for vector types.
Definition: LowLevelTypeImpl.h:237
llvm::MachineInstrBundleIterator< const MachineInstr >
llvm::CSEMIRBuilder::buildInstr
MachineInstrBuilder buildInstr(unsigned Opc, ArrayRef< DstOp > DstOps, ArrayRef< SrcOp > SrcOps, Optional< unsigned > Flag=None) override
Definition: CSEMIRBuilder.cpp:167
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::MachineOperand::CreateFPImm
static MachineOperand CreateFPImm(const ConstantFP *CFP)
Definition: MachineOperand.h:785
llvm::SrcOp
Definition: MachineIRBuilder.h:119
getReg
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
Definition: MipsDisassembler.cpp:572
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::ConstantFoldBinOp
Optional< APInt > ConstantFoldBinOp(unsigned Opcode, const Register Op1, const Register Op2, const MachineRegisterInfo &MRI)
Definition: Utils.cpp:477
llvm::LLT
Definition: LowLevelTypeImpl.h:40