LLVM  12.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 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,
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,
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
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