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/// \file
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_COMBINERHELPER_H
18#define LLVM_CODEGEN_GLOBALISEL_COMBINERHELPER_H
19
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
23#include "llvm/CodeGen/Register.h"
24#include "llvm/CodeGenTypes/LowLevelType.h"
25#include "llvm/IR/InstrTypes.h"
26#include <functional>
27
28namespace llvm {
29
30class GISelChangeObserver;
31class APInt;
32class ConstantFP;
33class GPtrAdd;
34class GZExtLoad;
35class MachineIRBuilder;
36class MachineInstrBuilder;
37class MachineRegisterInfo;
38class MachineInstr;
39class MachineOperand;
40class GISelKnownBits;
41class MachineDominatorTree;
42class LegalizerInfo;
43struct LegalityQuery;
44class RegisterBank;
45class RegisterBankInfo;
46class TargetLowering;
47class TargetRegisterInfo;
48
49struct PreferredTuple {
50 LLT Ty; // The result type of the extend.
51 unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
52 MachineInstr *MI;
53};
54
55struct IndexedLoadStoreMatchInfo {
56 Register Addr;
57 Register Base;
58 Register Offset;
59 bool RematOffset; // True if Offset is a constant that needs to be
60 // rematerialized before the new load/store.
61 bool IsPre;
62};
63
64struct PtrAddChain {
65 int64_t Imm;
66 Register Base;
67 const RegisterBank *Bank;
68};
69
70struct RegisterImmPair {
71 Register Reg;
72 int64_t Imm;
73};
74
75struct ShiftOfShiftedLogic {
76 MachineInstr *Logic;
77 MachineInstr *Shift2;
78 Register LogicNonShiftReg;
79 uint64_t ValSum;
80};
81
82using BuildFnTy = std::function<void(MachineIRBuilder &)>;
83
84using OperandBuildSteps =
85 SmallVector<std::function<void(MachineInstrBuilder &)>, 4>;
86struct InstructionBuildSteps {
87 unsigned Opcode = 0; /// The opcode for the produced instruction.
88 OperandBuildSteps OperandFns; /// Operands to be added to the instruction.
89 InstructionBuildSteps() = default;
90 InstructionBuildSteps(unsigned Opcode, const OperandBuildSteps &OperandFns)
91 : Opcode(Opcode), OperandFns(OperandFns) {}
92};
93
94struct InstructionStepsMatchInfo {
95 /// Describes instructions to be built during a combine.
96 SmallVector<InstructionBuildSteps, 2> InstrsToBuild;
97 InstructionStepsMatchInfo() = default;
98 InstructionStepsMatchInfo(
99 std::initializer_list<InstructionBuildSteps> InstrsToBuild)
100 : InstrsToBuild(InstrsToBuild) {}
101};
102
103class CombinerHelper {
104protected:
105 MachineIRBuilder &Builder;
106 MachineRegisterInfo &MRI;
107 GISelChangeObserver &Observer;
108 GISelKnownBits *KB;
109 MachineDominatorTree *MDT;
110 bool IsPreLegalize;
111 const LegalizerInfo *LI;
112 const RegisterBankInfo *RBI;
113 const TargetRegisterInfo *TRI;
114
115public:
116 CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B,
117 bool IsPreLegalize,
118 GISelKnownBits *KB = nullptr,
119 MachineDominatorTree *MDT = nullptr,
120 const LegalizerInfo *LI = nullptr);
121
122 GISelKnownBits *getKnownBits() const {
123 return KB;
124 }
125
126 MachineIRBuilder &getBuilder() const {
127 return Builder;
128 }
129
130 const TargetLowering &getTargetLowering() const;
131
132 /// \returns true if the combiner is running pre-legalization.
133 bool isPreLegalize() const;
134
135 /// \returns true if \p Query is legal on the target.
136 bool isLegal(const LegalityQuery &Query) const;
137
138 /// \return true if the combine is running prior to legalization, or if \p
139 /// Query is legal on the target.
140 bool isLegalOrBeforeLegalizer(const LegalityQuery &Query) const;
141
142 /// \return true if the combine is running prior to legalization, or if \p Ty
143 /// is a legal integer constant type on the target.
144 bool isConstantLegalOrBeforeLegalizer(const LLT Ty) const;
145
146 /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes
147 void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const;
148
149 /// Replace a single register operand with a new register and inform the
150 /// observer of the changes.
151 void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp,
152 Register ToReg) const;
153
154 /// Replace the opcode in instruction with a new opcode and inform the
155 /// observer of the changes.
156 void replaceOpcodeWith(MachineInstr &FromMI, unsigned ToOpcode) const;
157
158 /// Get the register bank of \p Reg.
159 /// If Reg has not been assigned a register, a register class,
160 /// or a register bank, then this returns nullptr.
161 ///
162 /// \pre Reg.isValid()
163 const RegisterBank *getRegBank(Register Reg) const;
164
165 /// Set the register bank of \p Reg.
166 /// Does nothing if the RegBank is null.
167 /// This is the counterpart to getRegBank.
168 void setRegBank(Register Reg, const RegisterBank *RegBank);
169
170 /// If \p MI is COPY, try to combine it.
171 /// Returns true if MI changed.
172 bool tryCombineCopy(MachineInstr &MI);
173 bool matchCombineCopy(MachineInstr &MI);
174 void applyCombineCopy(MachineInstr &MI);
175
176 /// Returns true if \p DefMI precedes \p UseMI or they are the same
177 /// instruction. Both must be in the same basic block.
178 bool isPredecessor(const MachineInstr &DefMI, const MachineInstr &UseMI);
179
180 /// Returns true if \p DefMI dominates \p UseMI. By definition an
181 /// instruction dominates itself.
182 ///
183 /// If we haven't been provided with a MachineDominatorTree during
184 /// construction, this function returns a conservative result that tracks just
185 /// a single basic block.
186 bool dominates(const MachineInstr &DefMI, const MachineInstr &UseMI);
187
188 /// If \p MI is extend that consumes the result of a load, try to combine it.
189 /// Returns true if MI changed.
190 bool tryCombineExtendingLoads(MachineInstr &MI);
191 bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
192 void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
193
194 /// Match (and (load x), mask) -> zextload x
195 bool matchCombineLoadWithAndMask(MachineInstr &MI, BuildFnTy &MatchInfo);
196
197 /// Combine a G_EXTRACT_VECTOR_ELT of a load into a narrowed
198 /// load.
199 bool matchCombineExtractedVectorLoad(MachineInstr &MI, BuildFnTy &MatchInfo);
200
201 bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo);
202 void applyCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo);
203
204 bool matchSextTruncSextLoad(MachineInstr &MI);
205 void applySextTruncSextLoad(MachineInstr &MI);
206
207 /// Match sext_inreg(load p), imm -> sextload p
208 bool matchSextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo);
209 void applySextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo);
210
211 /// Try to combine G_[SU]DIV and G_[SU]REM into a single G_[SU]DIVREM
212 /// when their source operands are identical.
213 bool matchCombineDivRem(MachineInstr &MI, MachineInstr *&OtherMI);
214 void applyCombineDivRem(MachineInstr &MI, MachineInstr *&OtherMI);
215
216 /// If a brcond's true block is not the fallthrough, make it so by inverting
217 /// the condition and swapping operands.
218 bool matchOptBrCondByInvertingCond(MachineInstr &MI, MachineInstr *&BrCond);
219 void applyOptBrCondByInvertingCond(MachineInstr &MI, MachineInstr *&BrCond);
220
221 /// If \p MI is G_CONCAT_VECTORS, try to combine it.
222 /// Returns true if MI changed.
223 /// Right now, we support:
224 /// - concat_vector(undef, undef) => undef
225 /// - concat_vector(build_vector(A, B), build_vector(C, D)) =>
226 /// build_vector(A, B, C, D)
227 ///
228 /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
229 bool tryCombineConcatVectors(MachineInstr &MI);
230 /// Check if the G_CONCAT_VECTORS \p MI is undef or if it
231 /// can be flattened into a build_vector.
232 /// In the first case \p IsUndef will be true.
233 /// In the second case \p Ops will contain the operands needed
234 /// to produce the flattened build_vector.
235 ///
236 /// \pre MI.getOpcode() == G_CONCAT_VECTORS.
237 bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef,
238 SmallVectorImpl<Register> &Ops);
239 /// Replace \p MI with a flattened build_vector with \p Ops or an
240 /// implicit_def if IsUndef is true.
241 void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef,
242 const ArrayRef<Register> Ops);
243
244 /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS.
245 /// Returns true if MI changed.
246 ///
247 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
248 bool tryCombineShuffleVector(MachineInstr &MI);
249 /// Check if the G_SHUFFLE_VECTOR \p MI can be replaced by a
250 /// concat_vectors.
251 /// \p Ops will contain the operands needed to produce the flattened
252 /// concat_vectors.
253 ///
254 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR.
255 bool matchCombineShuffleVector(MachineInstr &MI,
256 SmallVectorImpl<Register> &Ops);
257 /// Replace \p MI with a concat_vectors with \p Ops.
258 void applyCombineShuffleVector(MachineInstr &MI,
259 const ArrayRef<Register> Ops);
260 bool matchShuffleToExtract(MachineInstr &MI);
261 void applyShuffleToExtract(MachineInstr &MI);
262
263 /// Optimize memcpy intrinsics et al, e.g. constant len calls.
264 /// /p MaxLen if non-zero specifies the max length of a mem libcall to inline.
265 ///
266 /// For example (pre-indexed):
267 ///
268 /// $addr = G_PTR_ADD $base, $offset
269 /// [...]
270 /// $val = G_LOAD $addr
271 /// [...]
272 /// $whatever = COPY $addr
273 ///
274 /// -->
275 ///
276 /// $val, $addr = G_INDEXED_LOAD $base, $offset, 1 (IsPre)
277 /// [...]
278 /// $whatever = COPY $addr
279 ///
280 /// or (post-indexed):
281 ///
282 /// G_STORE $val, $base
283 /// [...]
284 /// $addr = G_PTR_ADD $base, $offset
285 /// [...]
286 /// $whatever = COPY $addr
287 ///
288 /// -->
289 ///
290 /// $addr = G_INDEXED_STORE $val, $base, $offset
291 /// [...]
292 /// $whatever = COPY $addr
293 bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0);
294
295 bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
296 void applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo);
297
298 /// Fold (shift (shift base, x), y) -> (shift base (x+y))
299 bool matchShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo);
300 void applyShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo);
301
302 /// If we have a shift-by-constant of a bitwise logic op that itself has a
303 /// shift-by-constant operand with identical opcode, we may be able to convert
304 /// that into 2 independent shifts followed by the logic op.
305 bool matchShiftOfShiftedLogic(MachineInstr &MI,
306 ShiftOfShiftedLogic &MatchInfo);
307 void applyShiftOfShiftedLogic(MachineInstr &MI,
308 ShiftOfShiftedLogic &MatchInfo);
309
310 bool matchCommuteShift(MachineInstr &MI, BuildFnTy &MatchInfo);
311
312 /// Transform a multiply by a power-of-2 value to a left shift.
313 bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal);
314 void applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal);
315
316 // Transform a G_SHL with an extended source into a narrower shift if
317 // possible.
318 bool matchCombineShlOfExtend(MachineInstr &MI, RegisterImmPair &MatchData);
319 void applyCombineShlOfExtend(MachineInstr &MI,
320 const RegisterImmPair &MatchData);
321
322 /// Fold away a merge of an unmerge of the corresponding values.
323 bool matchCombineMergeUnmerge(MachineInstr &MI, Register &MatchInfo);
324
325 /// Reduce a shift by a constant to an unmerge and a shift on a half sized
326 /// type. This will not produce a shift smaller than \p TargetShiftSize.
327 bool matchCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftSize,
328 unsigned &ShiftVal);
329 void applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal);
330 bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount);
331
332 /// Transform <ty,...> G_UNMERGE(G_MERGE ty X, Y, Z) -> ty X, Y, Z.
333 bool
334 matchCombineUnmergeMergeToPlainValues(MachineInstr &MI,
335 SmallVectorImpl<Register> &Operands);
336 void
337 applyCombineUnmergeMergeToPlainValues(MachineInstr &MI,
338 SmallVectorImpl<Register> &Operands);
339
340 /// Transform G_UNMERGE Constant -> Constant1, Constant2, ...
341 bool matchCombineUnmergeConstant(MachineInstr &MI,
342 SmallVectorImpl<APInt> &Csts);
343 void applyCombineUnmergeConstant(MachineInstr &MI,
344 SmallVectorImpl<APInt> &Csts);
345
346 /// Transform G_UNMERGE G_IMPLICIT_DEF -> G_IMPLICIT_DEF, G_IMPLICIT_DEF, ...
347 bool
348 matchCombineUnmergeUndef(MachineInstr &MI,
349 std::function<void(MachineIRBuilder &)> &MatchInfo);
350
351 /// Transform X, Y<dead> = G_UNMERGE Z -> X = G_TRUNC Z.
352 bool matchCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI);
353 void applyCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI);
354
355 /// Transform X, Y = G_UNMERGE(G_ZEXT(Z)) -> X = G_ZEXT(Z); Y = G_CONSTANT 0
356 bool matchCombineUnmergeZExtToZExt(MachineInstr &MI);
357 void applyCombineUnmergeZExtToZExt(MachineInstr &MI);
358
359 /// Transform fp_instr(cst) to constant result of the fp operation.
360 void applyCombineConstantFoldFpUnary(MachineInstr &MI, const ConstantFP *Cst);
361
362 /// Transform IntToPtr(PtrToInt(x)) to x if cast is in the same address space.
363 bool matchCombineI2PToP2I(MachineInstr &MI, Register &Reg);
364 void applyCombineI2PToP2I(MachineInstr &MI, Register &Reg);
365
366 /// Transform PtrToInt(IntToPtr(x)) to x.
367 void applyCombineP2IToI2P(MachineInstr &MI, Register &Reg);
368
369 /// Transform G_ADD (G_PTRTOINT x), y -> G_PTRTOINT (G_PTR_ADD x, y)
370 /// Transform G_ADD y, (G_PTRTOINT x) -> G_PTRTOINT (G_PTR_ADD x, y)
371 bool matchCombineAddP2IToPtrAdd(MachineInstr &MI,
372 std::pair<Register, bool> &PtrRegAndCommute);
373 void applyCombineAddP2IToPtrAdd(MachineInstr &MI,
374 std::pair<Register, bool> &PtrRegAndCommute);
375
376 // Transform G_PTR_ADD (G_PTRTOINT C1), C2 -> C1 + C2
377 bool matchCombineConstPtrAddToI2P(MachineInstr &MI, APInt &NewCst);
378 void applyCombineConstPtrAddToI2P(MachineInstr &MI, APInt &NewCst);
379
380 /// Transform anyext(trunc(x)) to x.
381 bool matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg);
382
383 /// Transform zext(trunc(x)) to x.
384 bool matchCombineZextTrunc(MachineInstr &MI, Register &Reg);
385
386 /// Transform [asz]ext([asz]ext(x)) to [asz]ext x.
387 bool matchCombineExtOfExt(MachineInstr &MI,
388 std::tuple<Register, unsigned> &MatchInfo);
389 void applyCombineExtOfExt(MachineInstr &MI,
390 std::tuple<Register, unsigned> &MatchInfo);
391
392 /// Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x).
393 bool matchCombineTruncOfExt(MachineInstr &MI,
394 std::pair<Register, unsigned> &MatchInfo);
395 void applyCombineTruncOfExt(MachineInstr &MI,
396 std::pair<Register, unsigned> &MatchInfo);
397
398 /// Transform trunc (shl x, K) to shl (trunc x), K
399 /// if K < VT.getScalarSizeInBits().
400 ///
401 /// Transforms trunc ([al]shr x, K) to (trunc ([al]shr (MidVT (trunc x)), K))
402 /// if K <= (MidVT.getScalarSizeInBits() - VT.getScalarSizeInBits())
403 /// MidVT is obtained by finding a legal type between the trunc's src and dst
404 /// types.
405 bool matchCombineTruncOfShift(MachineInstr &MI,
406 std::pair<MachineInstr *, LLT> &MatchInfo);
407 void applyCombineTruncOfShift(MachineInstr &MI,
408 std::pair<MachineInstr *, LLT> &MatchInfo);
409
410 /// Return true if any explicit use operand on \p MI is defined by a
411 /// G_IMPLICIT_DEF.
412 bool matchAnyExplicitUseIsUndef(MachineInstr &MI);
413
414 /// Return true if all register explicit use operands on \p MI are defined by
415 /// a G_IMPLICIT_DEF.
416 bool matchAllExplicitUsesAreUndef(MachineInstr &MI);
417
418 /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask.
419 bool matchUndefShuffleVectorMask(MachineInstr &MI);
420
421 /// Return true if a G_STORE instruction \p MI is storing an undef value.
422 bool matchUndefStore(MachineInstr &MI);
423
424 /// Return true if a G_SELECT instruction \p MI has an undef comparison.
425 bool matchUndefSelectCmp(MachineInstr &MI);
426
427 /// Return true if a G_{EXTRACT,INSERT}_VECTOR_ELT has an out of range index.
428 bool matchInsertExtractVecEltOutOfBounds(MachineInstr &MI);
429
430 /// Return true if a G_SELECT instruction \p MI has a constant comparison. If
431 /// true, \p OpIdx will store the operand index of the known selected value.
432 bool matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx);
433
434 /// Replace an instruction with a G_FCONSTANT with value \p C.
435 void replaceInstWithFConstant(MachineInstr &MI, double C);
436
437 /// Replace an instruction with an G_FCONSTANT with value \p CFP.
438 void replaceInstWithFConstant(MachineInstr &MI, ConstantFP *CFP);
439
440 /// Replace an instruction with a G_CONSTANT with value \p C.
441 void replaceInstWithConstant(MachineInstr &MI, int64_t C);
442
443 /// Replace an instruction with a G_CONSTANT with value \p C.
444 void replaceInstWithConstant(MachineInstr &MI, APInt C);
445
446 /// Replace an instruction with a G_IMPLICIT_DEF.
447 void replaceInstWithUndef(MachineInstr &MI);
448
449 /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand.
450 void replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx);
451
452 /// Delete \p MI and replace all of its uses with \p Replacement.
453 void replaceSingleDefInstWithReg(MachineInstr &MI, Register Replacement);
454
455 /// @brief Replaces the shift amount in \p MI with ShiftAmt % BW
456 /// @param MI
457 void applyFunnelShiftConstantModulo(MachineInstr &MI);
458
459 /// Return true if \p MOP1 and \p MOP2 are register operands are defined by
460 /// equivalent instructions.
461 bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2);
462
463 /// Return true if \p MOP is defined by a G_CONSTANT or splat with a value equal to
464 /// \p C.
465 bool matchConstantOp(const MachineOperand &MOP, int64_t C);
466
467 /// Return true if \p MOP is defined by a G_FCONSTANT or splat with a value exactly
468 /// equal to \p C.
469 bool matchConstantFPOp(const MachineOperand &MOP, double C);
470
471 /// @brief Checks if constant at \p ConstIdx is larger than \p MI 's bitwidth
472 /// @param ConstIdx Index of the constant
473 bool matchConstantLargerBitWidth(MachineInstr &MI, unsigned ConstIdx);
474
475 /// Optimize (cond ? x : x) -> x
476 bool matchSelectSameVal(MachineInstr &MI);
477
478 /// Optimize (x op x) -> x
479 bool matchBinOpSameVal(MachineInstr &MI);
480
481 /// Check if operand \p OpIdx is zero.
482 bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx);
483
484 /// Check if operand \p OpIdx is undef.
485 bool matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx);
486
487 /// Check if operand \p OpIdx is known to be a power of 2.
488 bool matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI, unsigned OpIdx);
489
490 /// Erase \p MI
491 void eraseInst(MachineInstr &MI);
492
493 /// Return true if MI is a G_ADD which can be simplified to a G_SUB.
494 bool matchSimplifyAddToSub(MachineInstr &MI,
495 std::tuple<Register, Register> &MatchInfo);
496 void applySimplifyAddToSub(MachineInstr &MI,
497 std::tuple<Register, Register> &MatchInfo);
498
499 /// Match (logic_op (op x...), (op y...)) -> (op (logic_op x, y))
500 bool
501 matchHoistLogicOpWithSameOpcodeHands(MachineInstr &MI,
502 InstructionStepsMatchInfo &MatchInfo);
503
504 /// Replace \p MI with a series of instructions described in \p MatchInfo.
505 void applyBuildInstructionSteps(MachineInstr &MI,
506 InstructionStepsMatchInfo &MatchInfo);
507
508 /// Match ashr (shl x, C), C -> sext_inreg (C)
509 bool matchAshrShlToSextInreg(MachineInstr &MI,
510 std::tuple<Register, int64_t> &MatchInfo);
511 void applyAshShlToSextInreg(MachineInstr &MI,
512 std::tuple<Register, int64_t> &MatchInfo);
513
514 /// Fold and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0
515 bool matchOverlappingAnd(MachineInstr &MI,
516 BuildFnTy &MatchInfo);
517
518 /// \return true if \p MI is a G_AND instruction whose operands are x and y
519 /// where x & y == x or x & y == y. (E.g., one of operands is all-ones value.)
520 ///
521 /// \param [in] MI - The G_AND instruction.
522 /// \param [out] Replacement - A register the G_AND should be replaced with on
523 /// success.
524 bool matchRedundantAnd(MachineInstr &MI, Register &Replacement);
525
526 /// \return true if \p MI is a G_OR instruction whose operands are x and y
527 /// where x | y == x or x | y == y. (E.g., one of operands is all-zeros
528 /// value.)
529 ///
530 /// \param [in] MI - The G_OR instruction.
531 /// \param [out] Replacement - A register the G_OR should be replaced with on
532 /// success.
533 bool matchRedundantOr(MachineInstr &MI, Register &Replacement);
534
535 /// \return true if \p MI is a G_SEXT_INREG that can be erased.
536 bool matchRedundantSExtInReg(MachineInstr &MI);
537
538 /// Combine inverting a result of a compare into the opposite cond code.
539 bool matchNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate);
540 void applyNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate);
541
542 /// Fold (xor (and x, y), y) -> (and (not x), y)
543 ///{
544 bool matchXorOfAndWithSameReg(MachineInstr &MI,
545 std::pair<Register, Register> &MatchInfo);
546 void applyXorOfAndWithSameReg(MachineInstr &MI,
547 std::pair<Register, Register> &MatchInfo);
548 ///}
549
550 /// Combine G_PTR_ADD with nullptr to G_INTTOPTR
551 bool matchPtrAddZero(MachineInstr &MI);
552 void applyPtrAddZero(MachineInstr &MI);
553
554 /// Combine G_UREM x, (known power of 2) to an add and bitmasking.
555 void applySimplifyURemByPow2(MachineInstr &MI);
556
557 /// Push a binary operator through a select on constants.
558 ///
559 /// binop (select cond, K0, K1), K2 ->
560 /// select cond, (binop K0, K2), (binop K1, K2)
561 bool matchFoldBinOpIntoSelect(MachineInstr &MI, unsigned &SelectOpNo);
562 void applyFoldBinOpIntoSelect(MachineInstr &MI, const unsigned &SelectOpNo);
563
564 bool matchCombineInsertVecElts(MachineInstr &MI,
565 SmallVectorImpl<Register> &MatchInfo);
566
567 void applyCombineInsertVecElts(MachineInstr &MI,
568 SmallVectorImpl<Register> &MatchInfo);
569
570 /// Match expression trees of the form
571 ///
572 /// \code
573 /// sN *a = ...
574 /// sM val = a[0] | (a[1] << N) | (a[2] << 2N) | (a[3] << 3N) ...
575 /// \endcode
576 ///
577 /// And check if the tree can be replaced with a M-bit load + possibly a
578 /// bswap.
579 bool matchLoadOrCombine(MachineInstr &MI, BuildFnTy &MatchInfo);
580
581 bool matchExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI);
582 void applyExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI);
583
584 bool matchExtractVecEltBuildVec(MachineInstr &MI, Register &Reg);
585 void applyExtractVecEltBuildVec(MachineInstr &MI, Register &Reg);
586
587 bool matchExtractAllEltsFromBuildVector(
588 MachineInstr &MI,
589 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo);
590 void applyExtractAllEltsFromBuildVector(
591 MachineInstr &MI,
592 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo);
593
594 /// Use a function which takes in a MachineIRBuilder to perform a combine.
595 /// By default, it erases the instruction \p MI from the function.
596 void applyBuildFn(MachineInstr &MI, BuildFnTy &MatchInfo);
597 /// Use a function which takes in a MachineIRBuilder to perform a combine.
598 /// This variant does not erase \p MI after calling the build function.
599 void applyBuildFnNoErase(MachineInstr &MI, BuildFnTy &MatchInfo);
600
601 bool matchOrShiftToFunnelShift(MachineInstr &MI, BuildFnTy &MatchInfo);
602 bool matchFunnelShiftToRotate(MachineInstr &MI);
603 void applyFunnelShiftToRotate(MachineInstr &MI);
604 bool matchRotateOutOfRange(MachineInstr &MI);
605 void applyRotateOutOfRange(MachineInstr &MI);
606
607 /// \returns true if a G_ICMP instruction \p MI can be replaced with a true
608 /// or false constant based off of KnownBits information.
609 bool matchICmpToTrueFalseKnownBits(MachineInstr &MI, int64_t &MatchInfo);
610
611 /// \returns true if a G_ICMP \p MI can be replaced with its LHS based off of
612 /// KnownBits information.
613 bool
614 matchICmpToLHSKnownBits(MachineInstr &MI,
615 BuildFnTy &MatchInfo);
616
617 /// \returns true if (and (or x, c1), c2) can be replaced with (and x, c2)
618 bool matchAndOrDisjointMask(MachineInstr &MI, BuildFnTy &MatchInfo);
619
620 bool matchBitfieldExtractFromSExtInReg(MachineInstr &MI,
621 BuildFnTy &MatchInfo);
622 /// Match: and (lshr x, cst), mask -> ubfx x, cst, width
623 bool matchBitfieldExtractFromAnd(MachineInstr &MI, BuildFnTy &MatchInfo);
624
625 /// Match: shr (shl x, n), k -> sbfx/ubfx x, pos, width
626 bool matchBitfieldExtractFromShr(MachineInstr &MI, BuildFnTy &MatchInfo);
627
628 /// Match: shr (and x, n), k -> ubfx x, pos, width
629 bool matchBitfieldExtractFromShrAnd(MachineInstr &MI, BuildFnTy &MatchInfo);
630
631 // Helpers for reassociation:
632 bool matchReassocConstantInnerRHS(GPtrAdd &MI, MachineInstr *RHS,
633 BuildFnTy &MatchInfo);
634 bool matchReassocFoldConstantsInSubTree(GPtrAdd &MI, MachineInstr *LHS,
635 MachineInstr *RHS,
636 BuildFnTy &MatchInfo);
637 bool matchReassocConstantInnerLHS(GPtrAdd &MI, MachineInstr *LHS,
638 MachineInstr *RHS, BuildFnTy &MatchInfo);
639 /// Reassociate pointer calculations with G_ADD involved, to allow better
640 /// addressing mode usage.
641 bool matchReassocPtrAdd(MachineInstr &MI, BuildFnTy &MatchInfo);
642
643 /// Try to reassociate to reassociate operands of a commutative binop.
644 bool tryReassocBinOp(unsigned Opc, Register DstReg, Register Op0,
645 Register Op1, BuildFnTy &MatchInfo);
646 /// Reassociate commutative binary operations like G_ADD.
647 bool matchReassocCommBinOp(MachineInstr &MI, BuildFnTy &MatchInfo);
648
649 /// Do constant folding when opportunities are exposed after MIR building.
650 bool matchConstantFoldCastOp(MachineInstr &MI, APInt &MatchInfo);
651
652 /// Do constant folding when opportunities are exposed after MIR building.
653 bool matchConstantFoldBinOp(MachineInstr &MI, APInt &MatchInfo);
654
655 /// Do constant FP folding when opportunities are exposed after MIR building.
656 bool matchConstantFoldFPBinOp(MachineInstr &MI, ConstantFP* &MatchInfo);
657
658 /// Constant fold G_FMA/G_FMAD.
659 bool matchConstantFoldFMA(MachineInstr &MI, ConstantFP *&MatchInfo);
660
661 /// \returns true if it is possible to narrow the width of a scalar binop
662 /// feeding a G_AND instruction \p MI.
663 bool matchNarrowBinopFeedingAnd(MachineInstr &MI, BuildFnTy &MatchInfo);
664
665 /// Given an G_UDIV \p MI expressing a divide by constant, return an
666 /// expression that implements it by multiplying by a magic number.
667 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
668 MachineInstr *buildUDivUsingMul(MachineInstr &MI);
669 /// Combine G_UDIV by constant into a multiply by magic constant.
670 bool matchUDivByConst(MachineInstr &MI);
671 void applyUDivByConst(MachineInstr &MI);
672
673 /// Given an G_SDIV \p MI expressing a signed divide by constant, return an
674 /// expression that implements it by multiplying by a magic number.
675 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
676 MachineInstr *buildSDivUsingMul(MachineInstr &MI);
677 bool matchSDivByConst(MachineInstr &MI);
678 void applySDivByConst(MachineInstr &MI);
679
680 // G_UMULH x, (1 << c)) -> x >> (bitwidth - c)
681 bool matchUMulHToLShr(MachineInstr &MI);
682 void applyUMulHToLShr(MachineInstr &MI);
683
684 /// Try to transform \p MI by using all of the above
685 /// combine functions. Returns true if changed.
686 bool tryCombine(MachineInstr &MI);
687
688 /// Emit loads and stores that perform the given memcpy.
689 /// Assumes \p MI is a G_MEMCPY_INLINE
690 /// TODO: implement dynamically sized inline memcpy,
691 /// and rename: s/bool tryEmit/void emit/
692 bool tryEmitMemcpyInline(MachineInstr &MI);
693
694 /// Match:
695 /// (G_UMULO x, 2) -> (G_UADDO x, x)
696 /// (G_SMULO x, 2) -> (G_SADDO x, x)
697 bool matchMulOBy2(MachineInstr &MI, BuildFnTy &MatchInfo);
698
699 /// Match:
700 /// (G_*MULO x, 0) -> 0 + no carry out
701 bool matchMulOBy0(MachineInstr &MI, BuildFnTy &MatchInfo);
702
703 /// Match:
704 /// (G_*ADDO x, 0) -> x + no carry out
705 bool matchAddOBy0(MachineInstr &MI, BuildFnTy &MatchInfo);
706
707 /// Match:
708 /// (G_*ADDE x, y, 0) -> (G_*ADDO x, y)
709 /// (G_*SUBE x, y, 0) -> (G_*SUBO x, y)
710 bool matchAddEToAddO(MachineInstr &MI, BuildFnTy &MatchInfo);
711
712 /// Transform (fadd x, fneg(y)) -> (fsub x, y)
713 /// (fadd fneg(x), y) -> (fsub y, x)
714 /// (fsub x, fneg(y)) -> (fadd x, y)
715 /// (fmul fneg(x), fneg(y)) -> (fmul x, y)
716 /// (fdiv fneg(x), fneg(y)) -> (fdiv x, y)
717 /// (fmad fneg(x), fneg(y), z) -> (fmad x, y, z)
718 /// (fma fneg(x), fneg(y), z) -> (fma x, y, z)
719 bool matchRedundantNegOperands(MachineInstr &MI, BuildFnTy &MatchInfo);
720
721 bool matchFsubToFneg(MachineInstr &MI, Register &MatchInfo);
722 void applyFsubToFneg(MachineInstr &MI, Register &MatchInfo);
723
724 bool canCombineFMadOrFMA(MachineInstr &MI, bool &AllowFusionGlobally,
725 bool &HasFMAD, bool &Aggressive,
726 bool CanReassociate = false);
727
728 /// Transform (fadd (fmul x, y), z) -> (fma x, y, z)
729 /// (fadd (fmul x, y), z) -> (fmad x, y, z)
730 bool matchCombineFAddFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo);
731
732 /// Transform (fadd (fpext (fmul x, y)), z) -> (fma (fpext x), (fpext y), z)
733 /// (fadd (fpext (fmul x, y)), z) -> (fmad (fpext x), (fpext y), z)
734 bool matchCombineFAddFpExtFMulToFMadOrFMA(MachineInstr &MI,
735 BuildFnTy &MatchInfo);
736
737 /// Transform (fadd (fma x, y, (fmul u, v)), z) -> (fma x, y, (fma u, v, z))
738 /// (fadd (fmad x, y, (fmul u, v)), z) -> (fmad x, y, (fmad u, v, z))
739 bool matchCombineFAddFMAFMulToFMadOrFMA(MachineInstr &MI,
740 BuildFnTy &MatchInfo);
741
742 // Transform (fadd (fma x, y, (fpext (fmul u, v))), z)
743 // -> (fma x, y, (fma (fpext u), (fpext v), z))
744 // (fadd (fmad x, y, (fpext (fmul u, v))), z)
745 // -> (fmad x, y, (fmad (fpext u), (fpext v), z))
746 bool matchCombineFAddFpExtFMulToFMadOrFMAAggressive(MachineInstr &MI,
747 BuildFnTy &MatchInfo);
748
749 /// Transform (fsub (fmul x, y), z) -> (fma x, y, -z)
750 /// (fsub (fmul x, y), z) -> (fmad x, y, -z)
751 bool matchCombineFSubFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo);
752
753 /// Transform (fsub (fneg (fmul, x, y)), z) -> (fma (fneg x), y, (fneg z))
754 /// (fsub (fneg (fmul, x, y)), z) -> (fmad (fneg x), y, (fneg z))
755 bool matchCombineFSubFNegFMulToFMadOrFMA(MachineInstr &MI,
756 BuildFnTy &MatchInfo);
757
758 /// Transform (fsub (fpext (fmul x, y)), z)
759 /// -> (fma (fpext x), (fpext y), (fneg z))
760 /// (fsub (fpext (fmul x, y)), z)
761 /// -> (fmad (fpext x), (fpext y), (fneg z))
762 bool matchCombineFSubFpExtFMulToFMadOrFMA(MachineInstr &MI,
763 BuildFnTy &MatchInfo);
764
765 /// Transform (fsub (fpext (fneg (fmul x, y))), z)
766 /// -> (fneg (fma (fpext x), (fpext y), z))
767 /// (fsub (fpext (fneg (fmul x, y))), z)
768 /// -> (fneg (fmad (fpext x), (fpext y), z))
769 bool matchCombineFSubFpExtFNegFMulToFMadOrFMA(MachineInstr &MI,
770 BuildFnTy &MatchInfo);
771
772 bool matchCombineFMinMaxNaN(MachineInstr &MI, unsigned &Info);
773
774 /// Transform G_ADD(x, G_SUB(y, x)) to y.
775 /// Transform G_ADD(G_SUB(y, x), x) to y.
776 bool matchAddSubSameReg(MachineInstr &MI, Register &Src);
777
778 bool matchBuildVectorIdentityFold(MachineInstr &MI, Register &MatchInfo);
779 bool matchTruncBuildVectorFold(MachineInstr &MI, Register &MatchInfo);
780 bool matchTruncLshrBuildVectorFold(MachineInstr &MI, Register &MatchInfo);
781
782 /// Transform:
783 /// (x + y) - y -> x
784 /// (x + y) - x -> y
785 /// x - (y + x) -> 0 - y
786 /// x - (x + z) -> 0 - z
787 bool matchSubAddSameReg(MachineInstr &MI, BuildFnTy &MatchInfo);
788
789 /// \returns true if it is possible to simplify a select instruction \p MI
790 /// to a min/max instruction of some sort.
791 bool matchSimplifySelectToMinMax(MachineInstr &MI, BuildFnTy &MatchInfo);
792
793 /// Transform:
794 /// (X + Y) == X -> Y == 0
795 /// (X - Y) == X -> Y == 0
796 /// (X ^ Y) == X -> Y == 0
797 /// (X + Y) != X -> Y != 0
798 /// (X - Y) != X -> Y != 0
799 /// (X ^ Y) != X -> Y != 0
800 bool matchRedundantBinOpInEquality(MachineInstr &MI, BuildFnTy &MatchInfo);
801
802 /// Match shifts greater or equal to the bitwidth of the operation.
803 bool matchShiftsTooBig(MachineInstr &MI);
804
805 /// Match constant LHS ops that should be commuted.
806 bool matchCommuteConstantToRHS(MachineInstr &MI);
807
808 /// Match constant LHS FP ops that should be commuted.
809 bool matchCommuteFPConstantToRHS(MachineInstr &MI);
810
811 // Given a binop \p MI, commute operands 1 and 2.
812 void applyCommuteBinOpOperands(MachineInstr &MI);
813
814 /// Combine selects.
815 bool matchSelect(MachineInstr &MI, BuildFnTy &MatchInfo);
816
817 /// Combine ands,
818 bool matchAnd(MachineInstr &MI, BuildFnTy &MatchInfo);
819
820 /// Combine ors,
821 bool matchOr(MachineInstr &MI, BuildFnTy &MatchInfo);
822
823private:
824 /// Checks for legality of an indexed variant of \p LdSt.
825 bool isIndexedLoadStoreLegal(GLoadStore &LdSt) const;
826 /// Given a non-indexed load or store instruction \p MI, find an offset that
827 /// can be usefully and legally folded into it as a post-indexing operation.
828 ///
829 /// \returns true if a candidate is found.
830 bool findPostIndexCandidate(GLoadStore &MI, Register &Addr, Register &Base,
831 Register &Offset, bool &RematOffset);
832
833 /// Given a non-indexed load or store instruction \p MI, find an offset that
834 /// can be usefully and legally folded into it as a pre-indexing operation.
835 ///
836 /// \returns true if a candidate is found.
837 bool findPreIndexCandidate(GLoadStore &MI, Register &Addr, Register &Base,
838 Register &Offset);
839
840 /// Helper function for matchLoadOrCombine. Searches for Registers
841 /// which may have been produced by a load instruction + some arithmetic.
842 ///
843 /// \param [in] Root - The search root.
844 ///
845 /// \returns The Registers found during the search.
846 std::optional<SmallVector<Register, 8>>
847 findCandidatesForLoadOrCombine(const MachineInstr *Root) const;
848
849 /// Helper function for matchLoadOrCombine.
850 ///
851 /// Checks if every register in \p RegsToVisit is defined by a load
852 /// instruction + some arithmetic.
853 ///
854 /// \param [out] MemOffset2Idx - Maps the byte positions each load ends up
855 /// at to the index of the load.
856 /// \param [in] MemSizeInBits - The number of bits each load should produce.
857 ///
858 /// \returns On success, a 3-tuple containing lowest-index load found, the
859 /// lowest index, and the last load in the sequence.
860 std::optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>>
861 findLoadOffsetsForLoadOrCombine(
862 SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx,
863 const SmallVector<Register, 8> &RegsToVisit,
864 const unsigned MemSizeInBits);
865
866 /// Examines the G_PTR_ADD instruction \p PtrAdd and determines if performing
867 /// a re-association of its operands would break an existing legal addressing
868 /// mode that the address computation currently represents.
869 bool reassociationCanBreakAddressingModePattern(MachineInstr &PtrAdd);
870
871 /// Behavior when a floating point min/max is given one NaN and one
872 /// non-NaN as input.
873 enum class SelectPatternNaNBehaviour {
874 NOT_APPLICABLE = 0, /// NaN behavior not applicable.
875 RETURNS_NAN, /// Given one NaN input, returns the NaN.
876 RETURNS_OTHER, /// Given one NaN input, returns the non-NaN.
877 RETURNS_ANY /// Given one NaN input, can return either (or both operands are
878 /// known non-NaN.)
879 };
880
881 /// \returns which of \p LHS and \p RHS would be the result of a non-equality
882 /// floating point comparison where one of \p LHS and \p RHS may be NaN.
883 ///
884 /// If both \p LHS and \p RHS may be NaN, returns
885 /// SelectPatternNaNBehaviour::NOT_APPLICABLE.
886 SelectPatternNaNBehaviour
887 computeRetValAgainstNaN(Register LHS, Register RHS,
888 bool IsOrderedComparison) const;
889
890 /// Determines the floating point min/max opcode which should be used for
891 /// a G_SELECT fed by a G_FCMP with predicate \p Pred.
892 ///
893 /// \returns 0 if this G_SELECT should not be combined to a floating point
894 /// min or max. If it should be combined, returns one of
895 ///
896 /// * G_FMAXNUM
897 /// * G_FMAXIMUM
898 /// * G_FMINNUM
899 /// * G_FMINIMUM
900 ///
901 /// Helper function for matchFPSelectToMinMax.
902 unsigned getFPMinMaxOpcForSelect(CmpInst::Predicate Pred, LLT DstTy,
903 SelectPatternNaNBehaviour VsNaNRetVal) const;
904
905 /// Handle floating point cases for matchSimplifySelectToMinMax.
906 ///
907 /// E.g.
908 ///
909 /// select (fcmp uge x, 1.0) x, 1.0 -> fmax x, 1.0
910 /// select (fcmp uge x, 1.0) 1.0, x -> fminnm x, 1.0
911 bool matchFPSelectToMinMax(Register Dst, Register Cond, Register TrueVal,
912 Register FalseVal, BuildFnTy &MatchInfo);
913
914 /// Try to fold selects to logical operations.
915 bool tryFoldBoolSelectToLogic(GSelect *Select, BuildFnTy &MatchInfo);
916
917 bool tryFoldSelectOfConstants(GSelect *Select, BuildFnTy &MatchInfo);
918
919 /// Try to fold (icmp X, Y) ? X : Y -> integer minmax.
920 bool tryFoldSelectToIntMinMax(GSelect *Select, BuildFnTy &MatchInfo);
921
922 bool isOneOrOneSplat(Register Src, bool AllowUndefs);
923 bool isZeroOrZeroSplat(Register Src, bool AllowUndefs);
924 bool isConstantSplatVector(Register Src, int64_t SplatValue,
925 bool AllowUndefs);
926
927 std::optional<APInt> getConstantOrConstantSplatVector(Register Src);
928
929 /// Fold (icmp Pred1 V1, C1) && (icmp Pred2 V2, C2)
930 /// or (icmp Pred1 V1, C1) || (icmp Pred2 V2, C2)
931 /// into a single comparison using range-based reasoning.
932 bool tryFoldAndOrOrICmpsUsingRanges(GLogicalBinOp *Logic,
933 BuildFnTy &MatchInfo);
934};
935} // namespace llvm
936
937#endif
938

source code of llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h