LLVM  11.0.0git
CombinerHelper.h
Go to the documentation of this file.
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 
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 
36  LLT Ty; // The result type of the extend.
37  unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
39 };
40 
45  bool IsPre;
46 };
47 
48 struct PtrAddChain {
49  int64_t Imm;
51 };
52 
54 protected:
60  const LegalizerInfo *LI;
61 
62 public:
64  GISelKnownBits *KB = nullptr,
65  MachineDominatorTree *MDT = nullptr,
66  const LegalizerInfo *LI = nullptr);
67 
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 matchElideBrByInvertingCond(MachineInstr &MI);
111  void applyElideBrByInvertingCond(MachineInstr &MI);
112  bool tryElideBrByInvertingCond(MachineInstr &MI);
113 
114  /// If \p MI is G_CONCAT_VECTORS, try to combine it.
115  /// Returns true if MI changed.
116  /// Right now, we support:
117  /// - concat_vector(undef, undef) => undef
118  /// - concat_vector(build_vector(A, B), build_vector(C, D)) =>
119  /// build_vector(A, B, C, D)
120  ///
121  /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
122  bool tryCombineConcatVectors(MachineInstr &MI);
123  /// Check if the G_CONCAT_VECTORS \p MI is undef or if it
124  /// can be flattened into a build_vector.
125  /// In the first case \p IsUndef will be true.
126  /// In the second case \p Ops will contain the operands needed
127  /// to produce the flattened build_vector.
128  ///
129  /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
130  bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef,
132  /// Replace \p MI with a flattened build_vector with \p Ops or an
133  /// implicit_def if IsUndef is true.
134  void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef,
135  const ArrayRef<Register> Ops);
136 
137  /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS.
138  /// Returns true if MI changed.
139  ///
140  /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
141  bool tryCombineShuffleVector(MachineInstr &MI);
142  /// Check if the G_SHUFFLE_VECTOR \p MI can be replaced by a
143  /// concat_vectors.
144  /// \p Ops will contain the operands needed to produce the flattened
145  /// concat_vectors.
146  ///
147  /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
148  bool matchCombineShuffleVector(MachineInstr &MI,
150  /// Replace \p MI with a concat_vectors with \p Ops.
151  void applyCombineShuffleVector(MachineInstr &MI,
152  const ArrayRef<Register> Ops);
153 
154  /// Optimize memcpy intrinsics et al, e.g. constant len calls.
155  /// /p MaxLen if non-zero specifies the max length of a mem libcall to inline.
156  ///
157  /// For example (pre-indexed):
158  ///
159  /// $addr = G_PTR_ADD $base, $offset
160  /// [...]
161  /// $val = G_LOAD $addr
162  /// [...]
163  /// $whatever = COPY $addr
164  ///
165  /// -->
166  ///
167  /// $val, $addr = G_INDEXED_LOAD $base, $offset, 1 (IsPre)
168  /// [...]
169  /// $whatever = COPY $addr
170  ///
171  /// or (post-indexed):
172  ///
173  /// G_STORE $val, $base
174  /// [...]
175  /// $addr = G_PTR_ADD $base, $offset
176  /// [...]
177  /// $whatever = COPY $addr
178  ///
179  /// -->
180  ///
181  /// $addr = G_INDEXED_STORE $val, $base, $offset
182  /// [...]
183  /// $whatever = COPY $addr
184  bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0);
185 
186  bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
187  bool applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
188 
189  /// Transform a multiply by a power-of-2 value to a left shift.
190  bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal);
191  bool applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal);
192 
193  /// Reduce a shift by a constant to an unmerge and a shift on a half sized
194  /// type. This will not produce a shift smaller than \p TargetShiftSize.
195  bool matchCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftSize,
196  unsigned &ShiftVal);
197  bool applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal);
198  bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount);
199 
200  /// Return true if any explicit use operand on \p MI is defined by a
201  /// G_IMPLICIT_DEF.
202  bool matchAnyExplicitUseIsUndef(MachineInstr &MI);
203 
204  /// Return true if all register explicit use operands on \p MI are defined by
205  /// a G_IMPLICIT_DEF.
206  bool matchAllExplicitUsesAreUndef(MachineInstr &MI);
207 
208  /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask.
209  bool matchUndefShuffleVectorMask(MachineInstr &MI);
210 
211  /// Return true if a G_STORE instruction \p MI is storing an undef value.
212  bool matchUndefStore(MachineInstr &MI);
213 
214  /// Replace an instruction with a G_FCONSTANT with value \p C.
215  bool replaceInstWithFConstant(MachineInstr &MI, double C);
216 
217  /// Replace an instruction with a G_CONSTANT with value \p C.
218  bool replaceInstWithConstant(MachineInstr &MI, int64_t C);
219 
220  /// Replace an instruction with a G_IMPLICIT_DEF.
221  bool replaceInstWithUndef(MachineInstr &MI);
222 
223  /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand.
224  bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx);
225 
226  /// Return true if \p MOP1 and \p MOP2 are register operands are defined by
227  /// equivalent instructions.
228  bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2);
229 
230  /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to
231  /// \p C.
232  bool matchConstantOp(const MachineOperand &MOP, int64_t C);
233 
234  /// Optimize (cond ? x : x) -> x
235  bool matchSelectSameVal(MachineInstr &MI);
236 
237  /// Optimize (x op x) -> x
238  bool matchBinOpSameVal(MachineInstr &MI);
239 
240  /// Check if operand \p OpIdx is zero.
241  bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx);
242 
243  /// Erase \p MI
244  bool eraseInst(MachineInstr &MI);
245 
246  /// Return true if MI is a G_ADD which can be simplified to a G_SUB.
247  bool matchSimplifyAddToSub(MachineInstr &MI,
248  std::tuple<Register, Register> &MatchInfo);
249  bool applySimplifyAddToSub(MachineInstr &MI,
250  std::tuple<Register, Register> &MatchInfo);
251 
252  /// Try to transform \p MI by using all of the above
253  /// combine functions. Returns true if changed.
254  bool tryCombine(MachineInstr &MI);
255 
256 private:
257  // Memcpy family optimization helpers.
258  bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,
259  unsigned KnownLen, Align DstAlign, Align SrcAlign,
260  bool IsVolatile);
261  bool optimizeMemmove(MachineInstr &MI, Register Dst, Register Src,
262  unsigned KnownLen, Align DstAlign, Align SrcAlign,
263  bool IsVolatile);
264  bool optimizeMemset(MachineInstr &MI, Register Dst, Register Val,
265  unsigned KnownLen, Align DstAlign, bool IsVolatile);
266 
267  /// Given a non-indexed load or store instruction \p MI, find an offset that
268  /// can be usefully and legally folded into it as a post-indexing operation.
269  ///
270  /// \returns true if a candidate is found.
271  bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
272  Register &Offset);
273 
274  /// Given a non-indexed load or store instruction \p MI, find an offset that
275  /// can be usefully and legally folded into it as a pre-indexing operation.
276  ///
277  /// \returns true if a candidate is found.
278  bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
279  Register &Offset);
280 };
281 } // namespace llvm
282 
283 #endif
uint64_t CallInst * C
This class represents lattice values for constants.
Definition: AllocatorList.h:23
constexpr char IsVolatile[]
Key for Kernel::Arg::Metadata::mIsVolatile.
GISelKnownBits * KB
GISelChangeObserver & Observer
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
MachineIRBuilder & Builder
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
const LegalizerInfo * LI
Abstract class that contains various methods for clients to notify about changes. ...
GISelKnownBits * getKnownBits() const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineInstrBuilder & UseMI
Helper class to build MachineInstr.
MachineDominatorTree * MDT
MachineRegisterInfo & MRI
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
MachineOperand class - Representation of each machine instruction operand.
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineInstr * MI
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:62
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19