CombinerHelper.h revision 360784 
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
23namespace llvm {
24
25class GISelChangeObserver;
26class MachineIRBuilder;
27class MachineRegisterInfo;
28class MachineInstr;
29class MachineOperand;
30class GISelKnownBits;
31class MachineDominatorTree;
32
33struct PreferredTuple {
34  LLT Ty;                // The result type of the extend.
35  unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
36  MachineInstr *MI;
37};
38
39struct IndexedLoadStoreMatchInfo {
40  Register Addr;
41  Register Base;
42  Register Offset;
43  bool IsPre;
44};
45
46struct PtrAddChain {
47  int64_t Imm;
48  Register Base;
49};
50
51class CombinerHelper {
52protected:
53  MachineIRBuilder &Builder;
54  MachineRegisterInfo &MRI;
55  GISelChangeObserver &Observer;
56  GISelKnownBits *KB;
57  MachineDominatorTree *MDT;
58
59public:
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
185private:
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