1 //== llvm/CodeGen/GlobalISel/LegalizerHelper.h ---------------- -*- 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 //
9 /// \file A pass to convert the target-illegal operations created by IR -> MIR
10 /// translation into ones the target expects to be able to select. This may
11 /// occur in multiple phases, for example G_ADD <2 x i8> -> G_ADD <2 x i16> ->
12 /// G_ADD <4 x i16>.
13 ///
14 /// The LegalizerHelper class is where most of the work happens, and is
15 /// designed to be callable from other passes that find themselves with an
16 /// illegal instruction.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
21 #define LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
22 
23 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
24 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
25 #include "llvm/CodeGen/LowLevelType.h"
26 #include "llvm/CodeGen/MachineFunctionPass.h"
27 #include "llvm/CodeGen/RuntimeLibcalls.h"
28 
29 namespace llvm {
30 // Forward declarations.
31 class LegalizerInfo;
32 class Legalizer;
33 class MachineRegisterInfo;
34 class GISelChangeObserver;
35 
36 class LegalizerHelper {
37 public:
38   /// Expose MIRBuilder so clients can set their own RecordInsertInstruction
39   /// functions
40   MachineIRBuilder &MIRBuilder;
41 
42   /// To keep track of changes made by the LegalizerHelper.
43   GISelChangeObserver &Observer;
44 
45 private:
46   MachineRegisterInfo &MRI;
47   const LegalizerInfo &LI;
48 
49 public:
50   enum LegalizeResult {
51     /// Instruction was already legal and no change was made to the
52     /// MachineFunction.
53     AlreadyLegal,
54 
55     /// Instruction has been legalized and the MachineFunction changed.
56     Legalized,
57 
58     /// Some kind of error has occurred and we could not legalize this
59     /// instruction.
60     UnableToLegalize,
61   };
62 
63   /// Expose LegalizerInfo so the clients can re-use.
64   const LegalizerInfo &getLegalizerInfo() const { return LI; }
65 
66   LegalizerHelper(MachineFunction &MF, GISelChangeObserver &Observer,
67                   MachineIRBuilder &B);
68   LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI,
69                   GISelChangeObserver &Observer, MachineIRBuilder &B);
70 
71   /// Replace \p MI by a sequence of legal instructions that can implement the
72   /// same operation. Note that this means \p MI may be deleted, so any iterator
73   /// steps should be performed before calling this function. \p Helper should
74   /// be initialized to the MachineFunction containing \p MI.
75   ///
76   /// Considered as an opaque blob, the legal code will use and define the same
77   /// registers as \p MI.
78   LegalizeResult legalizeInstrStep(MachineInstr &MI);
79 
80   /// Legalize an instruction by emiting a runtime library call instead.
81   LegalizeResult libcall(MachineInstr &MI);
82 
83   /// Legalize an instruction by reducing the width of the underlying scalar
84   /// type.
85   LegalizeResult narrowScalar(MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy);
86 
87   /// Legalize an instruction by performing the operation on a wider scalar type
88   /// (for example a 16-bit addition can be safely performed at 32-bits
89   /// precision, ignoring the unused bits).
90   LegalizeResult widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
91 
92   /// Legalize an instruction by replacing the value type
93   LegalizeResult bitcast(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
94 
95   /// Legalize an instruction by splitting it into simpler parts, hopefully
96   /// understood by the target.
97   LegalizeResult lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
98 
99   /// Legalize a vector instruction by splitting into multiple components, each
100   /// acting on the same scalar type as the original but with fewer elements.
101   LegalizeResult fewerElementsVector(MachineInstr &MI, unsigned TypeIdx,
102                                      LLT NarrowTy);
103 
104   /// Legalize a vector instruction by increasing the number of vector elements
105   /// involved and ignoring the added elements later.
106   LegalizeResult moreElementsVector(MachineInstr &MI, unsigned TypeIdx,
107                                     LLT MoreTy);
108 
109   /// Cast the given value to an LLT::scalar with an equivalent size. Returns
110   /// the register to use if an instruction was inserted. Returns the original
111   /// register if no coercion was necessary.
112   //
113   // This may also fail and return Register() if there is no legal way to cast.
114   Register coerceToScalar(Register Val);
115 
116   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
117   /// Use by extending the operand's type to \p WideTy using the specified \p
118   /// ExtOpcode for the extension instruction, and replacing the vreg of the
119   /// operand in place.
120   void widenScalarSrc(MachineInstr &MI, LLT WideTy, unsigned OpIdx,
121                       unsigned ExtOpcode);
122 
123   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
124   /// Use by truncating the operand's type to \p NarrowTy using G_TRUNC, and
125   /// replacing the vreg of the operand in place.
126   void narrowScalarSrc(MachineInstr &MI, LLT NarrowTy, unsigned OpIdx);
127 
128   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
129   /// Def by extending the operand's type to \p WideTy and truncating it back
130   /// with the \p TruncOpcode, and replacing the vreg of the operand in place.
131   void widenScalarDst(MachineInstr &MI, LLT WideTy, unsigned OpIdx = 0,
132                       unsigned TruncOpcode = TargetOpcode::G_TRUNC);
133 
134   // Legalize a single operand \p OpIdx of the machine instruction \p MI as a
135   // Def by truncating the operand's type to \p NarrowTy, replacing in place and
136   // extending back with \p ExtOpcode.
137   void narrowScalarDst(MachineInstr &MI, LLT NarrowTy, unsigned OpIdx,
138                        unsigned ExtOpcode);
139   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
140   /// Def by performing it with additional vector elements and extracting the
141   /// result elements, and replacing the vreg of the operand in place.
142   void moreElementsVectorDst(MachineInstr &MI, LLT MoreTy, unsigned OpIdx);
143 
144   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
145   /// Use by producing a vector with undefined high elements, extracting the
146   /// original vector type, and replacing the vreg of the operand in place.
147   void moreElementsVectorSrc(MachineInstr &MI, LLT MoreTy, unsigned OpIdx);
148 
149   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
150   /// use by inserting a G_BITCAST to \p CastTy
151   void bitcastSrc(MachineInstr &MI, LLT CastTy, unsigned OpIdx);
152 
153   /// Legalize a single operand \p OpIdx of the machine instruction \p MI as a
154   /// def by inserting a G_BITCAST from \p CastTy
155   void bitcastDst(MachineInstr &MI, LLT CastTy, unsigned OpIdx);
156 
157 private:
158   LegalizeResult
159   widenScalarMergeValues(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
160   LegalizeResult
161   widenScalarUnmergeValues(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
162   LegalizeResult
163   widenScalarExtract(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
164   LegalizeResult
165   widenScalarInsert(MachineInstr &MI, unsigned TypeIdx, LLT WideTy);
166   LegalizeResult widenScalarAddSubSat(MachineInstr &MI, unsigned TypeIdx,
167                                       LLT WideTy);
168 
169   /// Helper function to split a wide generic register into bitwise blocks with
170   /// the given Type (which implies the number of blocks needed). The generic
171   /// registers created are appended to Ops, starting at bit 0 of Reg.
172   void extractParts(Register Reg, LLT Ty, int NumParts,
173                     SmallVectorImpl<Register> &VRegs);
174 
175   /// Version which handles irregular splits.
176   bool extractParts(Register Reg, LLT RegTy, LLT MainTy,
177                     LLT &LeftoverTy,
178                     SmallVectorImpl<Register> &VRegs,
179                     SmallVectorImpl<Register> &LeftoverVRegs);
180 
181   /// Helper function to build a wide generic register \p DstReg of type \p
182   /// RegTy from smaller parts. This will produce a G_MERGE_VALUES,
183   /// G_BUILD_VECTOR, G_CONCAT_VECTORS, or sequence of G_INSERT as appropriate
184   /// for the types.
185   ///
186   /// \p PartRegs must be registers of type \p PartTy.
187   ///
188   /// If \p ResultTy does not evenly break into \p PartTy sized pieces, the
189   /// remainder must be specified with \p LeftoverRegs of type \p LeftoverTy.
190   void insertParts(Register DstReg, LLT ResultTy,
191                    LLT PartTy, ArrayRef<Register> PartRegs,
192                    LLT LeftoverTy = LLT(), ArrayRef<Register> LeftoverRegs = {});
193 
194   /// Unmerge \p SrcReg into \p Parts with the greatest common divisor type with
195   /// \p DstTy and \p NarrowTy. Returns the GCD type.
196   LLT extractGCDType(SmallVectorImpl<Register> &Parts, LLT DstTy,
197                      LLT NarrowTy, Register SrcReg);
198 
199   /// Produce a merge of values in \p VRegs to define \p DstReg. Perform a merge
200   /// from the least common multiple type, and convert as appropriate to \p
201   /// DstReg.
202   ///
203   /// \p VRegs should each have type \p GCDTy. This type should be greatest
204   /// common divisor type of \p DstReg, \p NarrowTy, and an undetermined source
205   /// type.
206   ///
207   /// \p NarrowTy is the desired result merge source type. If the source value
208   /// needs to be widened to evenly cover \p DstReg, inserts high bits
209   /// corresponding to the extension opcode \p PadStrategy.
210   ///
211   /// \p VRegs will be cleared, and the the result \p NarrowTy register pieces
212   /// will replace it. Returns The complete LCMTy that \p VRegs will cover when
213   /// merged.
214   LLT buildLCMMergePieces(LLT DstTy, LLT NarrowTy, LLT GCDTy,
215                           SmallVectorImpl<Register> &VRegs,
216                           unsigned PadStrategy = TargetOpcode::G_ANYEXT);
217 
218   /// Merge the values in \p RemergeRegs to an \p LCMTy typed value. Extract the
219   /// low bits into \p DstReg. This is intended to use the outputs from
220   /// buildLCMMergePieces after processing.
221   void buildWidenedRemergeToDst(Register DstReg, LLT LCMTy,
222                                 ArrayRef<Register> RemergeRegs);
223 
224   /// Perform generic multiplication of values held in multiple registers.
225   /// Generated instructions use only types NarrowTy and i1.
226   /// Destination can be same or two times size of the source.
227   void multiplyRegisters(SmallVectorImpl<Register> &DstRegs,
228                          ArrayRef<Register> Src1Regs,
229                          ArrayRef<Register> Src2Regs, LLT NarrowTy);
230 
231 public:
232   LegalizeResult fewerElementsVectorImplicitDef(MachineInstr &MI,
233                                                 unsigned TypeIdx, LLT NarrowTy);
234 
235   /// Legalize a instruction with a vector type where each operand may have a
236   /// different element type. All type indexes must have the same number of
237   /// elements.
238   LegalizeResult fewerElementsVectorMultiEltType(MachineInstr &MI,
239                                                  unsigned TypeIdx, LLT NarrowTy);
240 
241   LegalizeResult fewerElementsVectorCasts(MachineInstr &MI, unsigned TypeIdx,
242                                           LLT NarrowTy);
243 
244   LegalizeResult
245   fewerElementsVectorCmp(MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy);
246 
247   LegalizeResult
248   fewerElementsVectorSelect(MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy);
249 
250   LegalizeResult fewerElementsVectorPhi(MachineInstr &MI,
251                                         unsigned TypeIdx, LLT NarrowTy);
252 
253   LegalizeResult moreElementsVectorPhi(MachineInstr &MI, unsigned TypeIdx,
254                                        LLT MoreTy);
255 
256   LegalizeResult fewerElementsVectorUnmergeValues(MachineInstr &MI,
257                                                   unsigned TypeIdx,
258                                                   LLT NarrowTy);
259   LegalizeResult fewerElementsVectorBuildVector(MachineInstr &MI,
260                                                 unsigned TypeIdx,
261                                                 LLT NarrowTy);
262 
263   LegalizeResult
264   reduceLoadStoreWidth(MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy);
265 
266   /// Legalize an instruction by reducing the operation width, either by
267   /// narrowing the type of the operation or by reducing the number of elements
268   /// of a vector.
269   /// The used strategy (narrow vs. fewerElements) is decided by \p NarrowTy.
270   /// Narrow is used if the scalar type of \p NarrowTy and \p DstTy differ,
271   /// fewerElements is used when the scalar type is the same but the number of
272   /// elements between \p NarrowTy and \p DstTy differ.
273   LegalizeResult reduceOperationWidth(MachineInstr &MI, unsigned TypeIdx,
274                                       LLT NarrowTy);
275 
276   LegalizeResult fewerElementsVectorSextInReg(MachineInstr &MI, unsigned TypeIdx,
277                                               LLT NarrowTy);
278 
279   LegalizeResult narrowScalarShiftByConstant(MachineInstr &MI, const APInt &Amt,
280                                              LLT HalfTy, LLT ShiftAmtTy);
281 
282   LegalizeResult narrowScalarShift(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
283   LegalizeResult narrowScalarMul(MachineInstr &MI, LLT Ty);
284   LegalizeResult narrowScalarExtract(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
285   LegalizeResult narrowScalarInsert(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
286 
287   LegalizeResult narrowScalarBasic(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
288   LegalizeResult narrowScalarExt(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
289   LegalizeResult narrowScalarSelect(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
290   LegalizeResult narrowScalarCTLZ(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
291   LegalizeResult narrowScalarCTTZ(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
292   LegalizeResult narrowScalarCTPOP(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
293 
294   LegalizeResult lowerBitcast(MachineInstr &MI);
295   LegalizeResult lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
296 
297   LegalizeResult lowerU64ToF32BitOps(MachineInstr &MI);
298   LegalizeResult lowerUITOFP(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
299   LegalizeResult lowerSITOFP(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
300   LegalizeResult lowerFPTOUI(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
301   LegalizeResult lowerFPTOSI(MachineInstr &MI);
302 
303   LegalizeResult lowerFPTRUNC_F64_TO_F16(MachineInstr &MI);
304   LegalizeResult lowerFPTRUNC(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
305 
306   LegalizeResult lowerMinMax(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
307   LegalizeResult lowerFCopySign(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
308   LegalizeResult lowerFMinNumMaxNum(MachineInstr &MI);
309   LegalizeResult lowerFMad(MachineInstr &MI);
310   LegalizeResult lowerIntrinsicRound(MachineInstr &MI);
311   LegalizeResult lowerFFloor(MachineInstr &MI);
312   LegalizeResult lowerMergeValues(MachineInstr &MI);
313   LegalizeResult lowerUnmergeValues(MachineInstr &MI);
314   LegalizeResult lowerShuffleVector(MachineInstr &MI);
315   LegalizeResult lowerDynStackAlloc(MachineInstr &MI);
316   LegalizeResult lowerExtract(MachineInstr &MI);
317   LegalizeResult lowerInsert(MachineInstr &MI);
318   LegalizeResult lowerSADDO_SSUBO(MachineInstr &MI);
319   LegalizeResult lowerBswap(MachineInstr &MI);
320   LegalizeResult lowerBitreverse(MachineInstr &MI);
321   LegalizeResult lowerReadWriteRegister(MachineInstr &MI);
322 };
323 
324 /// Helper function that creates a libcall to the given \p Name using the given
325 /// calling convention \p CC.
326 LegalizerHelper::LegalizeResult
327 createLibcall(MachineIRBuilder &MIRBuilder, const char *Name,
328               const CallLowering::ArgInfo &Result,
329               ArrayRef<CallLowering::ArgInfo> Args, CallingConv::ID CC);
330 
331 /// Helper function that creates the given libcall.
332 LegalizerHelper::LegalizeResult
333 createLibcall(MachineIRBuilder &MIRBuilder, RTLIB::Libcall Libcall,
334               const CallLowering::ArgInfo &Result,
335               ArrayRef<CallLowering::ArgInfo> Args);
336 
337 /// Create a libcall to memcpy et al.
338 LegalizerHelper::LegalizeResult createMemLibcall(MachineIRBuilder &MIRBuilder,
339                                                  MachineRegisterInfo &MRI,
340                                                  MachineInstr &MI);
341 
342 } // End namespace llvm.
343 
344 #endif
345