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