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