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 
17 using namespace llvm;
18 
19 bool 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 
33 MachineInstrBuilder
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()) {
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 
70 void 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 
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 
124 MachineInstrBuilder
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];
131     if (Op.getDstOpKind() == DstOp::DstType::Ty_Reg)
132       return buildCopy(Op.getReg(), MIB.getReg(0));
133   }
134   return MIB;
135 }
136 
137 MachineInstrBuilder 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 
204 MachineInstrBuilder 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 
231 MachineInstrBuilder 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