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