1 //===-- llvm/CodeGen/GlobalISel/CombinerHelper.h --------------*- C++ -*-===//
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
7 //===--------------------------------------------------------------------===//
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.
15 //===--------------------------------------------------------------------===//
17 #ifndef LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H
18 #define LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H
20 #include "llvm/CodeGen/LowLevelType.h"
21 #include "llvm/CodeGen/Register.h"
22 #include "llvm/Support/Alignment.h"
26 class GISelChangeObserver;
27 class MachineIRBuilder;
28 class MachineRegisterInfo;
32 class MachineDominatorTree;
35 struct PreferredTuple {
36 LLT Ty; // The result type of the extend.
37 unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
41 struct IndexedLoadStoreMatchInfo {
53 class CombinerHelper {
55 MachineIRBuilder &Builder;
56 MachineRegisterInfo &MRI;
57 GISelChangeObserver &Observer;
59 MachineDominatorTree *MDT;
60 const LegalizerInfo *LI;
63 CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B,
64 GISelKnownBits *KB = nullptr,
65 MachineDominatorTree *MDT = nullptr,
66 const LegalizerInfo *LI = nullptr);
68 GISelKnownBits *getKnownBits() const {
72 /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes
73 void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const;
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;
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);
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);
90 /// Returns true if \p DefMI dominates \p UseMI. By definition an
91 /// instruction dominates itself.
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);
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);
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);
110 bool matchSextAlreadyExtended(MachineInstr &MI);
111 bool applySextAlreadyExtended(MachineInstr &MI);
113 bool matchElideBrByInvertingCond(MachineInstr &MI);
114 void applyElideBrByInvertingCond(MachineInstr &MI);
115 bool tryElideBrByInvertingCond(MachineInstr &MI);
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)
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.
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);
140 /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS.
141 /// Returns true if MI changed.
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
147 /// \p Ops will contain the operands needed to produce the flattened
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);
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.
160 /// For example (pre-indexed):
162 /// $addr = G_PTR_ADD $base, $offset
164 /// $val = G_LOAD $addr
166 /// $whatever = COPY $addr
170 /// $val, $addr = G_INDEXED_LOAD $base, $offset, 1 (IsPre)
172 /// $whatever = COPY $addr
174 /// or (post-indexed):
176 /// G_STORE $val, $base
178 /// $addr = G_PTR_ADD $base, $offset
180 /// $whatever = COPY $addr
184 /// $addr = G_INDEXED_STORE $val, $base, $offset
186 /// $whatever = COPY $addr
187 bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0);
189 bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
190 bool applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
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);
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,
200 bool applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal);
201 bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount);
203 /// Return true if any explicit use operand on \p MI is defined by a
205 bool matchAnyExplicitUseIsUndef(MachineInstr &MI);
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);
211 /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask.
212 bool matchUndefShuffleVectorMask(MachineInstr &MI);
214 /// Return true if a G_STORE instruction \p MI is storing an undef value.
215 bool matchUndefStore(MachineInstr &MI);
217 /// Replace an instruction with a G_FCONSTANT with value \p C.
218 bool replaceInstWithFConstant(MachineInstr &MI, double C);
220 /// Replace an instruction with a G_CONSTANT with value \p C.
221 bool replaceInstWithConstant(MachineInstr &MI, int64_t C);
223 /// Replace an instruction with a G_IMPLICIT_DEF.
224 bool replaceInstWithUndef(MachineInstr &MI);
226 /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand.
227 bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx);
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);
233 /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to
235 bool matchConstantOp(const MachineOperand &MOP, int64_t C);
237 /// Optimize (cond ? x : x) -> x
238 bool matchSelectSameVal(MachineInstr &MI);
240 /// Optimize (x op x) -> x
241 bool matchBinOpSameVal(MachineInstr &MI);
243 /// Check if operand \p OpIdx is zero.
244 bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx);
247 bool eraseInst(MachineInstr &MI);
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);
255 /// Try to transform \p MI by using all of the above
256 /// combine functions. Returns true if changed.
257 bool tryCombine(MachineInstr &MI);
260 // Memcpy family optimization helpers.
261 bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,
262 unsigned KnownLen, Align DstAlign, Align SrcAlign,
264 bool optimizeMemmove(MachineInstr &MI, Register Dst, Register Src,
265 unsigned KnownLen, Align DstAlign, Align SrcAlign,
267 bool optimizeMemset(MachineInstr &MI, Register Dst, Register Val,
268 unsigned KnownLen, Align DstAlign, bool IsVolatile);
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.
273 /// \returns true if a candidate is found.
274 bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
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.
280 /// \returns true if a candidate is found.
281 bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,