1 //===-- llvm/CodeGen/GlobalISel/CombinerHelper.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 /// This contains common combine transformations that may be used in a combine
10 /// pass,or by the target elsewhere.
11 /// Targets can pick individual opcode transformations from the helper or use
12 /// tryCombine which invokes all transformations. All of the transformations
13 /// return true if the MachineInstruction changed and false otherwise.
14 //
15 //===--------------------------------------------------------------------===//
16 
17 #ifndef LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H
18 #define LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H
19 
20 #include "llvm/CodeGen/LowLevelType.h"
21 #include "llvm/CodeGen/Register.h"
22 #include "llvm/Support/Alignment.h"
23 
24 namespace llvm {
25 
26 class GISelChangeObserver;
27 class MachineIRBuilder;
28 class MachineRegisterInfo;
29 class MachineInstr;
30 class MachineOperand;
31 class GISelKnownBits;
32 class MachineDominatorTree;
33 class LegalizerInfo;
34 
35 struct PreferredTuple {
36   LLT Ty;                // The result type of the extend.
37   unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
38   MachineInstr *MI;
39 };
40 
41 struct IndexedLoadStoreMatchInfo {
42   Register Addr;
43   Register Base;
44   Register Offset;
45   bool IsPre;
46 };
47 
48 struct PtrAddChain {
49   int64_t Imm;
50   Register Base;
51 };
52 
53 class CombinerHelper {
54 protected:
55   MachineIRBuilder &Builder;
56   MachineRegisterInfo &MRI;
57   GISelChangeObserver &Observer;
58   GISelKnownBits *KB;
59   MachineDominatorTree *MDT;
60   const LegalizerInfo *LI;
61 
62 public:
63   CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B,
64                  GISelKnownBits *KB = nullptr,
65                  MachineDominatorTree *MDT = nullptr,
66                  const LegalizerInfo *LI = nullptr);
67 
68   GISelKnownBits *getKnownBits() const {
69     return KB;
70   }
71 
72   /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes
73   void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const;
74 
75   /// Replace a single register operand with a new register and inform the
76   /// observer of the changes.
77   void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp,
78                         Register ToReg) const;
79 
80   /// If \p MI is COPY, try to combine it.
81   /// Returns true if MI changed.
82   bool tryCombineCopy(MachineInstr &MI);
83   bool matchCombineCopy(MachineInstr &MI);
84   void applyCombineCopy(MachineInstr &MI);
85 
86   /// Returns true if \p DefMI precedes \p UseMI or they are the same
87   /// instruction. Both must be in the same basic block.
88   bool isPredecessor(const MachineInstr &DefMI, const MachineInstr &UseMI);
89 
90   /// Returns true if \p DefMI dominates \p UseMI. By definition an
91   /// instruction dominates itself.
92   ///
93   /// If we haven't been provided with a MachineDominatorTree during
94   /// construction, this function returns a conservative result that tracks just
95   /// a single basic block.
96   bool dominates(const MachineInstr &DefMI, const MachineInstr &UseMI);
97 
98   /// If \p MI is extend that consumes the result of a load, try to combine it.
99   /// Returns true if MI changed.
100   bool tryCombineExtendingLoads(MachineInstr &MI);
101   bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
102   void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
103 
104   /// Combine \p MI into a pre-indexed or post-indexed load/store operation if
105   /// legal and the surrounding code makes it useful.
106   bool tryCombineIndexedLoadStore(MachineInstr &MI);
107   bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo);
108   void applyCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo);
109 
110   bool matchSextAlreadyExtended(MachineInstr &MI);
111   bool applySextAlreadyExtended(MachineInstr &MI);
112 
113   bool matchElideBrByInvertingCond(MachineInstr &MI);
114   void applyElideBrByInvertingCond(MachineInstr &MI);
115   bool tryElideBrByInvertingCond(MachineInstr &MI);
116 
117   /// If \p MI is G_CONCAT_VECTORS, try to combine it.
118   /// Returns true if MI changed.
119   /// Right now, we support:
120   /// - concat_vector(undef, undef) => undef
121   /// - concat_vector(build_vector(A, B), build_vector(C, D)) =>
122   ///   build_vector(A, B, C, D)
123   ///
124   /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
125   bool tryCombineConcatVectors(MachineInstr &MI);
126   /// Check if the G_CONCAT_VECTORS \p MI is undef or if it
127   /// can be flattened into a build_vector.
128   /// In the first case \p IsUndef will be true.
129   /// In the second case \p Ops will contain the operands needed
130   /// to produce the flattened build_vector.
131   ///
132   /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
133   bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef,
134                                  SmallVectorImpl<Register> &Ops);
135   /// Replace \p MI with a flattened build_vector with \p Ops or an
136   /// implicit_def if IsUndef is true.
137   void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef,
138                                  const ArrayRef<Register> Ops);
139 
140   /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS.
141   /// Returns true if MI changed.
142   ///
143   /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
144   bool tryCombineShuffleVector(MachineInstr &MI);
145   /// Check if the G_SHUFFLE_VECTOR \p MI can be replaced by a
146   /// concat_vectors.
147   /// \p Ops will contain the operands needed to produce the flattened
148   /// concat_vectors.
149   ///
150   /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
151   bool matchCombineShuffleVector(MachineInstr &MI,
152                                  SmallVectorImpl<Register> &Ops);
153   /// Replace \p MI with a concat_vectors with \p Ops.
154   void applyCombineShuffleVector(MachineInstr &MI,
155                                  const ArrayRef<Register> Ops);
156 
157   /// Optimize memcpy intrinsics et al, e.g. constant len calls.
158   /// /p MaxLen if non-zero specifies the max length of a mem libcall to inline.
159   ///
160   /// For example (pre-indexed):
161   ///
162   ///     $addr = G_PTR_ADD $base, $offset
163   ///     [...]
164   ///     $val = G_LOAD $addr
165   ///     [...]
166   ///     $whatever = COPY $addr
167   ///
168   /// -->
169   ///
170   ///     $val, $addr = G_INDEXED_LOAD $base, $offset, 1 (IsPre)
171   ///     [...]
172   ///     $whatever = COPY $addr
173   ///
174   /// or (post-indexed):
175   ///
176   ///     G_STORE $val, $base
177   ///     [...]
178   ///     $addr = G_PTR_ADD $base, $offset
179   ///     [...]
180   ///     $whatever = COPY $addr
181   ///
182   /// -->
183   ///
184   ///     $addr = G_INDEXED_STORE $val, $base, $offset
185   ///     [...]
186   ///     $whatever = COPY $addr
187   bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0);
188 
189   bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
190   bool applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
191 
192   /// Transform a multiply by a power-of-2 value to a left shift.
193   bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal);
194   bool applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal);
195 
196   /// Reduce a shift by a constant to an unmerge and a shift on a half sized
197   /// type. This will not produce a shift smaller than \p TargetShiftSize.
198   bool matchCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftSize,
199                                  unsigned &ShiftVal);
200   bool applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal);
201   bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount);
202 
203   /// Return true if any explicit use operand on \p MI is defined by a
204   /// G_IMPLICIT_DEF.
205   bool matchAnyExplicitUseIsUndef(MachineInstr &MI);
206 
207   /// Return true if all register explicit use operands on \p MI are defined by
208   /// a G_IMPLICIT_DEF.
209   bool matchAllExplicitUsesAreUndef(MachineInstr &MI);
210 
211   /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask.
212   bool matchUndefShuffleVectorMask(MachineInstr &MI);
213 
214   /// Return true if a G_STORE instruction \p MI is storing an undef value.
215   bool matchUndefStore(MachineInstr &MI);
216 
217   /// Replace an instruction with a G_FCONSTANT with value \p C.
218   bool replaceInstWithFConstant(MachineInstr &MI, double C);
219 
220   /// Replace an instruction with a G_CONSTANT with value \p C.
221   bool replaceInstWithConstant(MachineInstr &MI, int64_t C);
222 
223   /// Replace an instruction with a G_IMPLICIT_DEF.
224   bool replaceInstWithUndef(MachineInstr &MI);
225 
226   /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand.
227   bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx);
228 
229   /// Return true if \p MOP1 and \p MOP2 are register operands are defined by
230   /// equivalent instructions.
231   bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2);
232 
233   /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to
234   /// \p C.
235   bool matchConstantOp(const MachineOperand &MOP, int64_t C);
236 
237   /// Optimize (cond ? x : x) -> x
238   bool matchSelectSameVal(MachineInstr &MI);
239 
240   /// Optimize (x op x) -> x
241   bool matchBinOpSameVal(MachineInstr &MI);
242 
243   /// Check if operand \p OpIdx is zero.
244   bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx);
245 
246   /// Erase \p MI
247   bool eraseInst(MachineInstr &MI);
248 
249   /// Return true if MI is a G_ADD which can be simplified to a G_SUB.
250   bool matchSimplifyAddToSub(MachineInstr &MI,
251                              std::tuple<Register, Register> &MatchInfo);
252   bool applySimplifyAddToSub(MachineInstr &MI,
253                              std::tuple<Register, Register> &MatchInfo);
254 
255   /// Try to transform \p MI by using all of the above
256   /// combine functions. Returns true if changed.
257   bool tryCombine(MachineInstr &MI);
258 
259 private:
260   // Memcpy family optimization helpers.
261   bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,
262                       unsigned KnownLen, Align DstAlign, Align SrcAlign,
263                       bool IsVolatile);
264   bool optimizeMemmove(MachineInstr &MI, Register Dst, Register Src,
265                        unsigned KnownLen, Align DstAlign, Align SrcAlign,
266                        bool IsVolatile);
267   bool optimizeMemset(MachineInstr &MI, Register Dst, Register Val,
268                       unsigned KnownLen, Align DstAlign, bool IsVolatile);
269 
270   /// Given a non-indexed load or store instruction \p MI, find an offset that
271   /// can be usefully and legally folded into it as a post-indexing operation.
272   ///
273   /// \returns true if a candidate is found.
274   bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
275                               Register &Offset);
276 
277   /// Given a non-indexed load or store instruction \p MI, find an offset that
278   /// can be usefully and legally folded into it as a pre-indexing operation.
279   ///
280   /// \returns true if a candidate is found.
281   bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
282                              Register &Offset);
283 };
284 } // namespace llvm
285 
286 #endif
287