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 
23 namespace llvm {
24 
25 class GISelChangeObserver;
26 class MachineIRBuilder;
27 class MachineRegisterInfo;
28 class MachineInstr;
29 class MachineOperand;
30 class GISelKnownBits;
31 class MachineDominatorTree;
32 
33 struct PreferredTuple {
34   LLT Ty;                // The result type of the extend.
35   unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
36   MachineInstr *MI;
37 };
38 
39 struct IndexedLoadStoreMatchInfo {
40   Register Addr;
41   Register Base;
42   Register Offset;
43   bool IsPre;
44 };
45 
46 struct PtrAddChain {
47   int64_t Imm;
48   Register Base;
49 };
50 
51 class CombinerHelper {
52 protected:
53   MachineIRBuilder &Builder;
54   MachineRegisterInfo &MRI;
55   GISelChangeObserver &Observer;
56   GISelKnownBits *KB;
57   MachineDominatorTree *MDT;
58 
59 public:
60   CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B,
61                  GISelKnownBits *KB = nullptr,
62                  MachineDominatorTree *MDT = nullptr);
63 
64   /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes
65   void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const;
66 
67   /// Replace a single register operand with a new register and inform the
68   /// observer of the changes.
69   void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp,
70                         Register ToReg) const;
71 
72   /// If \p MI is COPY, try to combine it.
73   /// Returns true if MI changed.
74   bool tryCombineCopy(MachineInstr &MI);
75   bool matchCombineCopy(MachineInstr &MI);
76   void applyCombineCopy(MachineInstr &MI);
77 
78   /// Returns true if \p DefMI precedes \p UseMI or they are the same
79   /// instruction. Both must be in the same basic block.
80   bool isPredecessor(MachineInstr &DefMI, MachineInstr &UseMI);
81 
82   /// Returns true if \p DefMI dominates \p UseMI. By definition an
83   /// instruction dominates itself.
84   ///
85   /// If we haven't been provided with a MachineDominatorTree during
86   /// construction, this function returns a conservative result that tracks just
87   /// a single basic block.
88   bool dominates(MachineInstr &DefMI, MachineInstr &UseMI);
89 
90   /// If \p MI is extend that consumes the result of a load, try to combine it.
91   /// Returns true if MI changed.
92   bool tryCombineExtendingLoads(MachineInstr &MI);
93   bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
94   void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
95 
96   /// Combine \p MI into a pre-indexed or post-indexed load/store operation if
97   /// legal and the surrounding code makes it useful.
98   bool tryCombineIndexedLoadStore(MachineInstr &MI);
99   bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo);
100   void applyCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo);
101 
102   bool matchElideBrByInvertingCond(MachineInstr &MI);
103   void applyElideBrByInvertingCond(MachineInstr &MI);
104   bool tryElideBrByInvertingCond(MachineInstr &MI);
105 
106   /// If \p MI is G_CONCAT_VECTORS, try to combine it.
107   /// Returns true if MI changed.
108   /// Right now, we support:
109   /// - concat_vector(undef, undef) => undef
110   /// - concat_vector(build_vector(A, B), build_vector(C, D)) =>
111   ///   build_vector(A, B, C, D)
112   ///
113   /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
114   bool tryCombineConcatVectors(MachineInstr &MI);
115   /// Check if the G_CONCAT_VECTORS \p MI is undef or if it
116   /// can be flattened into a build_vector.
117   /// In the first case \p IsUndef will be true.
118   /// In the second case \p Ops will contain the operands needed
119   /// to produce the flattened build_vector.
120   ///
121   /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
122   bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef,
123                                  SmallVectorImpl<Register> &Ops);
124   /// Replace \p MI with a flattened build_vector with \p Ops or an
125   /// implicit_def if IsUndef is true.
126   void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef,
127                                  const ArrayRef<Register> Ops);
128 
129   /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS.
130   /// Returns true if MI changed.
131   ///
132   /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
133   bool tryCombineShuffleVector(MachineInstr &MI);
134   /// Check if the G_SHUFFLE_VECTOR \p MI can be replaced by a
135   /// concat_vectors.
136   /// \p Ops will contain the operands needed to produce the flattened
137   /// concat_vectors.
138   ///
139   /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
140   bool matchCombineShuffleVector(MachineInstr &MI,
141                                  SmallVectorImpl<Register> &Ops);
142   /// Replace \p MI with a concat_vectors with \p Ops.
143   void applyCombineShuffleVector(MachineInstr &MI,
144                                  const ArrayRef<Register> Ops);
145 
146   /// Optimize memcpy intrinsics et al, e.g. constant len calls.
147   /// /p MaxLen if non-zero specifies the max length of a mem libcall to inline.
148   ///
149   /// For example (pre-indexed):
150   ///
151   ///     $addr = G_PTR_ADD $base, $offset
152   ///     [...]
153   ///     $val = G_LOAD $addr
154   ///     [...]
155   ///     $whatever = COPY $addr
156   ///
157   /// -->
158   ///
159   ///     $val, $addr = G_INDEXED_LOAD $base, $offset, 1 (IsPre)
160   ///     [...]
161   ///     $whatever = COPY $addr
162   ///
163   /// or (post-indexed):
164   ///
165   ///     G_STORE $val, $base
166   ///     [...]
167   ///     $addr = G_PTR_ADD $base, $offset
168   ///     [...]
169   ///     $whatever = COPY $addr
170   ///
171   /// -->
172   ///
173   ///     $addr = G_INDEXED_STORE $val, $base, $offset
174   ///     [...]
175   ///     $whatever = COPY $addr
176   bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0);
177 
178   bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
179   bool applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
180 
181   /// Try to transform \p MI by using all of the above
182   /// combine functions. Returns true if changed.
183   bool tryCombine(MachineInstr &MI);
184 
185 private:
186   // Memcpy family optimization helpers.
187   bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,
188                       unsigned KnownLen, unsigned DstAlign, unsigned SrcAlign,
189                       bool IsVolatile);
190   bool optimizeMemmove(MachineInstr &MI, Register Dst, Register Src,
191                       unsigned KnownLen, unsigned DstAlign, unsigned SrcAlign,
192                       bool IsVolatile);
193   bool optimizeMemset(MachineInstr &MI, Register Dst, Register Val,
194                       unsigned KnownLen, unsigned DstAlign, bool IsVolatile);
195 
196   /// Given a non-indexed load or store instruction \p MI, find an offset that
197   /// can be usefully and legally folded into it as a post-indexing operation.
198   ///
199   /// \returns true if a candidate is found.
200   bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
201                               Register &Offset);
202 
203   /// Given a non-indexed load or store instruction \p MI, find an offset that
204   /// can be usefully and legally folded into it as a pre-indexing operation.
205   ///
206   /// \returns true if a candidate is found.
207   bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
208                              Register &Offset);
209 };
210 } // namespace llvm
211 
212 #endif
213