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/LowLevelType.h" 23 #include "llvm/CodeGen/Register.h" 24 #include "llvm/IR/InstrTypes.h" 25 #include <functional> 26 27 namespace llvm { 28 29 class GISelChangeObserver; 30 class APFloat; 31 class APInt; 32 class ConstantFP; 33 class GPtrAdd; 34 class GStore; 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 IsPre; 61 }; 62 63 struct PtrAddChain { 64 int64_t Imm; 65 Register Base; 66 const RegisterBank *Bank; 67 }; 68 69 struct RegisterImmPair { 70 Register Reg; 71 int64_t Imm; 72 }; 73 74 struct ShiftOfShiftedLogic { 75 MachineInstr *Logic; 76 MachineInstr *Shift2; 77 Register LogicNonShiftReg; 78 uint64_t ValSum; 79 }; 80 81 using BuildFnTy = std::function<void(MachineIRBuilder &)>; 82 83 using OperandBuildSteps = 84 SmallVector<std::function<void(MachineInstrBuilder &)>, 4>; 85 struct InstructionBuildSteps { 86 unsigned Opcode = 0; /// The opcode for the produced instruction. 87 OperandBuildSteps OperandFns; /// Operands to be added to the instruction. 88 InstructionBuildSteps() = default; 89 InstructionBuildSteps(unsigned Opcode, const OperandBuildSteps &OperandFns) 90 : Opcode(Opcode), OperandFns(OperandFns) {} 91 }; 92 93 struct InstructionStepsMatchInfo { 94 /// Describes instructions to be built during a combine. 95 SmallVector<InstructionBuildSteps, 2> InstrsToBuild; 96 InstructionStepsMatchInfo() = default; 97 InstructionStepsMatchInfo( 98 std::initializer_list<InstructionBuildSteps> InstrsToBuild) 99 : InstrsToBuild(InstrsToBuild) {} 100 }; 101 102 class CombinerHelper { 103 protected: 104 MachineIRBuilder &Builder; 105 MachineRegisterInfo &MRI; 106 GISelChangeObserver &Observer; 107 GISelKnownBits *KB; 108 MachineDominatorTree *MDT; 109 bool IsPreLegalize; 110 const LegalizerInfo *LI; 111 const RegisterBankInfo *RBI; 112 const TargetRegisterInfo *TRI; 113 114 public: 115 CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B, 116 bool IsPreLegalize, 117 GISelKnownBits *KB = nullptr, 118 MachineDominatorTree *MDT = nullptr, 119 const LegalizerInfo *LI = nullptr); 120 121 GISelKnownBits *getKnownBits() const { 122 return KB; 123 } 124 125 MachineIRBuilder &getBuilder() const { 126 return Builder; 127 } 128 129 const TargetLowering &getTargetLowering() const; 130 131 /// \returns true if the combiner is running pre-legalization. 132 bool isPreLegalize() const; 133 134 /// \returns true if \p Query is legal on the target. 135 bool isLegal(const LegalityQuery &Query) const; 136 137 /// \return true if the combine is running prior to legalization, or if \p 138 /// Query is legal on the target. 139 bool isLegalOrBeforeLegalizer(const LegalityQuery &Query) const; 140 141 /// \return true if the combine is running prior to legalization, or if \p Ty 142 /// is a legal integer constant type on the target. 143 bool isConstantLegalOrBeforeLegalizer(const LLT Ty) const; 144 145 /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes 146 void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const; 147 148 /// Replace a single register operand with a new register and inform the 149 /// observer of the changes. 150 void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp, 151 Register ToReg) const; 152 153 /// Replace the opcode in instruction with a new opcode and inform the 154 /// observer of the changes. 155 void replaceOpcodeWith(MachineInstr &FromMI, unsigned ToOpcode) const; 156 157 /// Get the register bank of \p Reg. 158 /// If Reg has not been assigned a register, a register class, 159 /// or a register bank, then this returns nullptr. 160 /// 161 /// \pre Reg.isValid() 162 const RegisterBank *getRegBank(Register Reg) const; 163 164 /// Set the register bank of \p Reg. 165 /// Does nothing if the RegBank is null. 166 /// This is the counterpart to getRegBank. 167 void setRegBank(Register Reg, const RegisterBank *RegBank); 168 169 /// If \p MI is COPY, try to combine it. 170 /// Returns true if MI changed. 171 bool tryCombineCopy(MachineInstr &MI); 172 bool matchCombineCopy(MachineInstr &MI); 173 void applyCombineCopy(MachineInstr &MI); 174 175 /// Returns true if \p DefMI precedes \p UseMI or they are the same 176 /// instruction. Both must be in the same basic block. 177 bool isPredecessor(const MachineInstr &DefMI, const MachineInstr &UseMI); 178 179 /// Returns true if \p DefMI dominates \p UseMI. By definition an 180 /// instruction dominates itself. 181 /// 182 /// If we haven't been provided with a MachineDominatorTree during 183 /// construction, this function returns a conservative result that tracks just 184 /// a single basic block. 185 bool dominates(const MachineInstr &DefMI, const MachineInstr &UseMI); 186 187 /// If \p MI is extend that consumes the result of a load, try to combine it. 188 /// Returns true if MI changed. 189 bool tryCombineExtendingLoads(MachineInstr &MI); 190 bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo); 191 void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo); 192 193 /// Match (and (load x), mask) -> zextload x 194 bool matchCombineLoadWithAndMask(MachineInstr &MI, BuildFnTy &MatchInfo); 195 196 /// Combine \p MI into a pre-indexed or post-indexed load/store operation if 197 /// legal and the surrounding code makes it useful. 198 bool tryCombineIndexedLoadStore(MachineInstr &MI); 199 bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); 200 void applyCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); 201 202 bool matchSextTruncSextLoad(MachineInstr &MI); 203 void applySextTruncSextLoad(MachineInstr &MI); 204 205 /// Match sext_inreg(load p), imm -> sextload p 206 bool matchSextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo); 207 void applySextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo); 208 209 /// Try to combine G_[SU]DIV and G_[SU]REM into a single G_[SU]DIVREM 210 /// when their source operands are identical. 211 bool matchCombineDivRem(MachineInstr &MI, MachineInstr *&OtherMI); 212 void applyCombineDivRem(MachineInstr &MI, MachineInstr *&OtherMI); 213 214 /// If a brcond's true block is not the fallthrough, make it so by inverting 215 /// the condition and swapping operands. 216 bool matchOptBrCondByInvertingCond(MachineInstr &MI, MachineInstr *&BrCond); 217 void applyOptBrCondByInvertingCond(MachineInstr &MI, MachineInstr *&BrCond); 218 219 /// If \p MI is G_CONCAT_VECTORS, try to combine it. 220 /// Returns true if MI changed. 221 /// Right now, we support: 222 /// - concat_vector(undef, undef) => undef 223 /// - concat_vector(build_vector(A, B), build_vector(C, D)) => 224 /// build_vector(A, B, C, D) 225 /// 226 /// \pre MI.getOpcode() == G_CONCAT_VECTORS. 227 bool tryCombineConcatVectors(MachineInstr &MI); 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 IsUndef will be true. 231 /// In the second case \p Ops will contain the operands needed 232 /// to produce the flattened build_vector. 233 /// 234 /// \pre MI.getOpcode() == G_CONCAT_VECTORS. 235 bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef, 236 SmallVectorImpl<Register> &Ops); 237 /// Replace \p MI with a flattened build_vector with \p Ops or an 238 /// implicit_def if IsUndef is true. 239 void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef, 240 const ArrayRef<Register> Ops); 241 242 /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS. 243 /// Returns true if MI changed. 244 /// 245 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR. 246 bool tryCombineShuffleVector(MachineInstr &MI); 247 /// Check if the G_SHUFFLE_VECTOR \p MI can be replaced by a 248 /// concat_vectors. 249 /// \p Ops will contain the operands needed to produce the flattened 250 /// concat_vectors. 251 /// 252 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR. 253 bool matchCombineShuffleVector(MachineInstr &MI, 254 SmallVectorImpl<Register> &Ops); 255 /// Replace \p MI with a concat_vectors with \p Ops. 256 void applyCombineShuffleVector(MachineInstr &MI, 257 const ArrayRef<Register> Ops); 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 void applyCombineAnyExtTrunc(MachineInstr &MI, Register &Reg); 379 380 /// Transform zext(trunc(x)) to x. 381 bool matchCombineZextTrunc(MachineInstr &MI, Register &Reg); 382 383 /// Transform [asz]ext([asz]ext(x)) to [asz]ext x. 384 bool matchCombineExtOfExt(MachineInstr &MI, 385 std::tuple<Register, unsigned> &MatchInfo); 386 void applyCombineExtOfExt(MachineInstr &MI, 387 std::tuple<Register, unsigned> &MatchInfo); 388 389 /// Transform fabs(fabs(x)) to fabs(x). 390 void applyCombineFAbsOfFAbs(MachineInstr &MI, Register &Src); 391 392 /// Transform fabs(fneg(x)) to fabs(x). 393 bool matchCombineFAbsOfFNeg(MachineInstr &MI, BuildFnTy &MatchInfo); 394 395 /// Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x). 396 bool matchCombineTruncOfExt(MachineInstr &MI, 397 std::pair<Register, unsigned> &MatchInfo); 398 void applyCombineTruncOfExt(MachineInstr &MI, 399 std::pair<Register, unsigned> &MatchInfo); 400 401 /// Transform trunc (shl x, K) to shl (trunc x), K 402 /// if K < VT.getScalarSizeInBits(). 403 /// 404 /// Transforms trunc ([al]shr x, K) to (trunc ([al]shr (MidVT (trunc x)), K)) 405 /// if K <= (MidVT.getScalarSizeInBits() - VT.getScalarSizeInBits()) 406 /// MidVT is obtained by finding a legal type between the trunc's src and dst 407 /// types. 408 bool matchCombineTruncOfShift(MachineInstr &MI, 409 std::pair<MachineInstr *, LLT> &MatchInfo); 410 void applyCombineTruncOfShift(MachineInstr &MI, 411 std::pair<MachineInstr *, LLT> &MatchInfo); 412 413 /// Transform G_MUL(x, -1) to G_SUB(0, x) 414 void applyCombineMulByNegativeOne(MachineInstr &MI); 415 416 /// Return true if any explicit use operand on \p MI is defined by a 417 /// G_IMPLICIT_DEF. 418 bool matchAnyExplicitUseIsUndef(MachineInstr &MI); 419 420 /// Return true if all register explicit use operands on \p MI are defined by 421 /// a G_IMPLICIT_DEF. 422 bool matchAllExplicitUsesAreUndef(MachineInstr &MI); 423 424 /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask. 425 bool matchUndefShuffleVectorMask(MachineInstr &MI); 426 427 /// Return true if a G_STORE instruction \p MI is storing an undef value. 428 bool matchUndefStore(MachineInstr &MI); 429 430 /// Return true if a G_SELECT instruction \p MI has an undef comparison. 431 bool matchUndefSelectCmp(MachineInstr &MI); 432 433 /// Return true if a G_{EXTRACT,INSERT}_VECTOR_ELT has an out of range index. 434 bool matchInsertExtractVecEltOutOfBounds(MachineInstr &MI); 435 436 /// Return true if a G_SELECT instruction \p MI has a constant comparison. If 437 /// true, \p OpIdx will store the operand index of the known selected value. 438 bool matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx); 439 440 /// Replace an instruction with a G_FCONSTANT with value \p C. 441 void replaceInstWithFConstant(MachineInstr &MI, double C); 442 443 /// Replace an instruction with a G_CONSTANT with value \p C. 444 void replaceInstWithConstant(MachineInstr &MI, int64_t C); 445 446 /// Replace an instruction with a G_CONSTANT with value \p C. 447 void replaceInstWithConstant(MachineInstr &MI, APInt C); 448 449 /// Replace an instruction with a G_IMPLICIT_DEF. 450 void replaceInstWithUndef(MachineInstr &MI); 451 452 /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand. 453 void replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx); 454 455 /// Delete \p MI and replace all of its uses with \p Replacement. 456 void replaceSingleDefInstWithReg(MachineInstr &MI, Register Replacement); 457 458 /// Return true if \p MOP1 and \p MOP2 are register operands are defined by 459 /// equivalent instructions. 460 bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2); 461 462 /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to 463 /// \p C. 464 bool matchConstantOp(const MachineOperand &MOP, int64_t C); 465 466 /// Optimize (cond ? x : x) -> x 467 bool matchSelectSameVal(MachineInstr &MI); 468 469 /// Optimize (x op x) -> x 470 bool matchBinOpSameVal(MachineInstr &MI); 471 472 /// Check if operand \p OpIdx is zero. 473 bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx); 474 475 /// Check if operand \p OpIdx is undef. 476 bool matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx); 477 478 /// Check if operand \p OpIdx is known to be a power of 2. 479 bool matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI, unsigned OpIdx); 480 481 /// Erase \p MI 482 void eraseInst(MachineInstr &MI); 483 484 /// Return true if MI is a G_ADD which can be simplified to a G_SUB. 485 bool matchSimplifyAddToSub(MachineInstr &MI, 486 std::tuple<Register, Register> &MatchInfo); 487 void applySimplifyAddToSub(MachineInstr &MI, 488 std::tuple<Register, Register> &MatchInfo); 489 490 /// Match (logic_op (op x...), (op y...)) -> (op (logic_op x, y)) 491 bool 492 matchHoistLogicOpWithSameOpcodeHands(MachineInstr &MI, 493 InstructionStepsMatchInfo &MatchInfo); 494 495 /// Replace \p MI with a series of instructions described in \p MatchInfo. 496 void applyBuildInstructionSteps(MachineInstr &MI, 497 InstructionStepsMatchInfo &MatchInfo); 498 499 /// Match ashr (shl x, C), C -> sext_inreg (C) 500 bool matchAshrShlToSextInreg(MachineInstr &MI, 501 std::tuple<Register, int64_t> &MatchInfo); 502 void applyAshShlToSextInreg(MachineInstr &MI, 503 std::tuple<Register, int64_t> &MatchInfo); 504 505 /// Fold and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0 506 bool matchOverlappingAnd(MachineInstr &MI, 507 BuildFnTy &MatchInfo); 508 509 /// \return true if \p MI is a G_AND instruction whose operands are x and y 510 /// where x & y == x or x & y == y. (E.g., one of operands is all-ones value.) 511 /// 512 /// \param [in] MI - The G_AND instruction. 513 /// \param [out] Replacement - A register the G_AND should be replaced with on 514 /// success. 515 bool matchRedundantAnd(MachineInstr &MI, Register &Replacement); 516 517 /// \return true if \p MI is a G_OR instruction whose operands are x and y 518 /// where x | y == x or x | y == y. (E.g., one of operands is all-zeros 519 /// value.) 520 /// 521 /// \param [in] MI - The G_OR instruction. 522 /// \param [out] Replacement - A register the G_OR should be replaced with on 523 /// success. 524 bool matchRedundantOr(MachineInstr &MI, Register &Replacement); 525 526 /// \return true if \p MI is a G_SEXT_INREG that can be erased. 527 bool matchRedundantSExtInReg(MachineInstr &MI); 528 529 /// Combine inverting a result of a compare into the opposite cond code. 530 bool matchNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); 531 void applyNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); 532 533 /// Fold (xor (and x, y), y) -> (and (not x), y) 534 ///{ 535 bool matchXorOfAndWithSameReg(MachineInstr &MI, 536 std::pair<Register, Register> &MatchInfo); 537 void applyXorOfAndWithSameReg(MachineInstr &MI, 538 std::pair<Register, Register> &MatchInfo); 539 ///} 540 541 /// Combine G_PTR_ADD with nullptr to G_INTTOPTR 542 bool matchPtrAddZero(MachineInstr &MI); 543 void applyPtrAddZero(MachineInstr &MI); 544 545 /// Combine G_UREM x, (known power of 2) to an add and bitmasking. 546 void applySimplifyURemByPow2(MachineInstr &MI); 547 548 /// Push a binary operator through a select on constants. 549 /// 550 /// binop (select cond, K0, K1), K2 -> 551 /// select cond, (binop K0, K2), (binop K1, K2) 552 bool matchFoldBinOpIntoSelect(MachineInstr &MI, unsigned &SelectOpNo); 553 void applyFoldBinOpIntoSelect(MachineInstr &MI, const unsigned &SelectOpNo); 554 555 bool matchCombineInsertVecElts(MachineInstr &MI, 556 SmallVectorImpl<Register> &MatchInfo); 557 558 void applyCombineInsertVecElts(MachineInstr &MI, 559 SmallVectorImpl<Register> &MatchInfo); 560 561 /// Match expression trees of the form 562 /// 563 /// \code 564 /// sN *a = ... 565 /// sM val = a[0] | (a[1] << N) | (a[2] << 2N) | (a[3] << 3N) ... 566 /// \endcode 567 /// 568 /// And check if the tree can be replaced with a M-bit load + possibly a 569 /// bswap. 570 bool matchLoadOrCombine(MachineInstr &MI, BuildFnTy &MatchInfo); 571 572 bool matchExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI); 573 void applyExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI); 574 575 bool matchExtractVecEltBuildVec(MachineInstr &MI, Register &Reg); 576 void applyExtractVecEltBuildVec(MachineInstr &MI, Register &Reg); 577 578 bool matchExtractAllEltsFromBuildVector( 579 MachineInstr &MI, 580 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo); 581 void applyExtractAllEltsFromBuildVector( 582 MachineInstr &MI, 583 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo); 584 585 /// Use a function which takes in a MachineIRBuilder to perform a combine. 586 /// By default, it erases the instruction \p MI from the function. 587 void applyBuildFn(MachineInstr &MI, BuildFnTy &MatchInfo); 588 /// Use a function which takes in a MachineIRBuilder to perform a combine. 589 /// This variant does not erase \p MI after calling the build function. 590 void applyBuildFnNoErase(MachineInstr &MI, BuildFnTy &MatchInfo); 591 592 bool matchOrShiftToFunnelShift(MachineInstr &MI, BuildFnTy &MatchInfo); 593 bool matchFunnelShiftToRotate(MachineInstr &MI); 594 void applyFunnelShiftToRotate(MachineInstr &MI); 595 bool matchRotateOutOfRange(MachineInstr &MI); 596 void applyRotateOutOfRange(MachineInstr &MI); 597 598 /// \returns true if a G_ICMP instruction \p MI can be replaced with a true 599 /// or false constant based off of KnownBits information. 600 bool matchICmpToTrueFalseKnownBits(MachineInstr &MI, int64_t &MatchInfo); 601 602 /// \returns true if a G_ICMP \p MI can be replaced with its LHS based off of 603 /// KnownBits information. 604 bool 605 matchICmpToLHSKnownBits(MachineInstr &MI, 606 BuildFnTy &MatchInfo); 607 608 /// \returns true if (and (or x, c1), c2) can be replaced with (and x, c2) 609 bool matchAndOrDisjointMask(MachineInstr &MI, BuildFnTy &MatchInfo); 610 611 bool matchBitfieldExtractFromSExtInReg(MachineInstr &MI, 612 BuildFnTy &MatchInfo); 613 /// Match: and (lshr x, cst), mask -> ubfx x, cst, width 614 bool matchBitfieldExtractFromAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 615 616 /// Match: shr (shl x, n), k -> sbfx/ubfx x, pos, width 617 bool matchBitfieldExtractFromShr(MachineInstr &MI, BuildFnTy &MatchInfo); 618 619 /// Match: shr (and x, n), k -> ubfx x, pos, width 620 bool matchBitfieldExtractFromShrAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 621 622 // Helpers for reassociation: 623 bool matchReassocConstantInnerRHS(GPtrAdd &MI, MachineInstr *RHS, 624 BuildFnTy &MatchInfo); 625 bool matchReassocFoldConstantsInSubTree(GPtrAdd &MI, MachineInstr *LHS, 626 MachineInstr *RHS, 627 BuildFnTy &MatchInfo); 628 bool matchReassocConstantInnerLHS(GPtrAdd &MI, MachineInstr *LHS, 629 MachineInstr *RHS, BuildFnTy &MatchInfo); 630 /// Reassociate pointer calculations with G_ADD involved, to allow better 631 /// addressing mode usage. 632 bool matchReassocPtrAdd(MachineInstr &MI, BuildFnTy &MatchInfo); 633 634 /// Try to reassociate to reassociate operands of a commutative binop. 635 bool tryReassocBinOp(unsigned Opc, Register DstReg, Register Op0, 636 Register Op1, BuildFnTy &MatchInfo); 637 /// Reassociate commutative binary operations like G_ADD. 638 bool matchReassocCommBinOp(MachineInstr &MI, BuildFnTy &MatchInfo); 639 640 /// Do constant folding when opportunities are exposed after MIR building. 641 bool matchConstantFold(MachineInstr &MI, APInt &MatchInfo); 642 643 /// \returns true if it is possible to narrow the width of a scalar binop 644 /// feeding a G_AND instruction \p MI. 645 bool matchNarrowBinopFeedingAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 646 647 /// Given an G_UDIV \p MI expressing a divide by constant, return an 648 /// expression that implements it by multiplying by a magic number. 649 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide". 650 MachineInstr *buildUDivUsingMul(MachineInstr &MI); 651 /// Combine G_UDIV by constant into a multiply by magic constant. 652 bool matchUDivByConst(MachineInstr &MI); 653 void applyUDivByConst(MachineInstr &MI); 654 655 /// Given an G_SDIV \p MI expressing a signed divide by constant, return an 656 /// expression that implements it by multiplying by a magic number. 657 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide". 658 MachineInstr *buildSDivUsingMul(MachineInstr &MI); 659 bool matchSDivByConst(MachineInstr &MI); 660 void applySDivByConst(MachineInstr &MI); 661 662 // G_UMULH x, (1 << c)) -> x >> (bitwidth - c) 663 bool matchUMulHToLShr(MachineInstr &MI); 664 void applyUMulHToLShr(MachineInstr &MI); 665 666 /// Try to transform \p MI by using all of the above 667 /// combine functions. Returns true if changed. 668 bool tryCombine(MachineInstr &MI); 669 670 /// Emit loads and stores that perform the given memcpy. 671 /// Assumes \p MI is a G_MEMCPY_INLINE 672 /// TODO: implement dynamically sized inline memcpy, 673 /// and rename: s/bool tryEmit/void emit/ 674 bool tryEmitMemcpyInline(MachineInstr &MI); 675 676 /// Match: 677 /// (G_UMULO x, 2) -> (G_UADDO x, x) 678 /// (G_SMULO x, 2) -> (G_SADDO x, x) 679 bool matchMulOBy2(MachineInstr &MI, BuildFnTy &MatchInfo); 680 681 /// Match: 682 /// (G_*MULO x, 0) -> 0 + no carry out 683 bool matchMulOBy0(MachineInstr &MI, BuildFnTy &MatchInfo); 684 685 /// Match: 686 /// (G_*ADDO x, 0) -> x + no carry out 687 bool matchAddOBy0(MachineInstr &MI, BuildFnTy &MatchInfo); 688 689 /// Match: 690 /// (G_*ADDE x, y, 0) -> (G_*ADDO x, y) 691 /// (G_*SUBE x, y, 0) -> (G_*SUBO x, y) 692 bool matchAddEToAddO(MachineInstr &MI, BuildFnTy &MatchInfo); 693 694 /// Transform (fadd x, fneg(y)) -> (fsub x, y) 695 /// (fadd fneg(x), y) -> (fsub y, x) 696 /// (fsub x, fneg(y)) -> (fadd x, y) 697 /// (fmul fneg(x), fneg(y)) -> (fmul x, y) 698 /// (fdiv fneg(x), fneg(y)) -> (fdiv x, y) 699 /// (fmad fneg(x), fneg(y), z) -> (fmad x, y, z) 700 /// (fma fneg(x), fneg(y), z) -> (fma x, y, z) 701 bool matchRedundantNegOperands(MachineInstr &MI, BuildFnTy &MatchInfo); 702 703 bool matchFsubToFneg(MachineInstr &MI, Register &MatchInfo); 704 void applyFsubToFneg(MachineInstr &MI, Register &MatchInfo); 705 706 bool canCombineFMadOrFMA(MachineInstr &MI, bool &AllowFusionGlobally, 707 bool &HasFMAD, bool &Aggressive, 708 bool CanReassociate = false); 709 710 /// Transform (fadd (fmul x, y), z) -> (fma x, y, z) 711 /// (fadd (fmul x, y), z) -> (fmad x, y, z) 712 bool matchCombineFAddFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo); 713 714 /// Transform (fadd (fpext (fmul x, y)), z) -> (fma (fpext x), (fpext y), z) 715 /// (fadd (fpext (fmul x, y)), z) -> (fmad (fpext x), (fpext y), z) 716 bool matchCombineFAddFpExtFMulToFMadOrFMA(MachineInstr &MI, 717 BuildFnTy &MatchInfo); 718 719 /// Transform (fadd (fma x, y, (fmul u, v)), z) -> (fma x, y, (fma u, v, z)) 720 /// (fadd (fmad x, y, (fmul u, v)), z) -> (fmad x, y, (fmad u, v, z)) 721 bool matchCombineFAddFMAFMulToFMadOrFMA(MachineInstr &MI, 722 BuildFnTy &MatchInfo); 723 724 // Transform (fadd (fma x, y, (fpext (fmul u, v))), z) 725 // -> (fma x, y, (fma (fpext u), (fpext v), z)) 726 // (fadd (fmad x, y, (fpext (fmul u, v))), z) 727 // -> (fmad x, y, (fmad (fpext u), (fpext v), z)) 728 bool matchCombineFAddFpExtFMulToFMadOrFMAAggressive(MachineInstr &MI, 729 BuildFnTy &MatchInfo); 730 731 /// Transform (fsub (fmul x, y), z) -> (fma x, y, -z) 732 /// (fsub (fmul x, y), z) -> (fmad x, y, -z) 733 bool matchCombineFSubFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo); 734 735 /// Transform (fsub (fneg (fmul, x, y)), z) -> (fma (fneg x), y, (fneg z)) 736 /// (fsub (fneg (fmul, x, y)), z) -> (fmad (fneg x), y, (fneg z)) 737 bool matchCombineFSubFNegFMulToFMadOrFMA(MachineInstr &MI, 738 BuildFnTy &MatchInfo); 739 740 /// Transform (fsub (fpext (fmul x, y)), z) 741 /// -> (fma (fpext x), (fpext y), (fneg z)) 742 /// (fsub (fpext (fmul x, y)), z) 743 /// -> (fmad (fpext x), (fpext y), (fneg z)) 744 bool matchCombineFSubFpExtFMulToFMadOrFMA(MachineInstr &MI, 745 BuildFnTy &MatchInfo); 746 747 /// Transform (fsub (fpext (fneg (fmul x, y))), z) 748 /// -> (fneg (fma (fpext x), (fpext y), z)) 749 /// (fsub (fpext (fneg (fmul x, y))), z) 750 /// -> (fneg (fmad (fpext x), (fpext y), z)) 751 bool matchCombineFSubFpExtFNegFMulToFMadOrFMA(MachineInstr &MI, 752 BuildFnTy &MatchInfo); 753 754 /// Fold boolean selects to logical operations. 755 bool matchSelectToLogical(MachineInstr &MI, BuildFnTy &MatchInfo); 756 757 bool matchCombineFMinMaxNaN(MachineInstr &MI, unsigned &Info); 758 759 /// Transform G_ADD(x, G_SUB(y, x)) to y. 760 /// Transform G_ADD(G_SUB(y, x), x) to y. 761 bool matchAddSubSameReg(MachineInstr &MI, Register &Src); 762 763 bool matchBuildVectorIdentityFold(MachineInstr &MI, Register &MatchInfo); 764 bool matchTruncBuildVectorFold(MachineInstr &MI, Register &MatchInfo); 765 bool matchTruncLshrBuildVectorFold(MachineInstr &MI, Register &MatchInfo); 766 767 /// Transform: 768 /// (x + y) - y -> x 769 /// (x + y) - x -> y 770 /// x - (y + x) -> 0 - y 771 /// x - (x + z) -> 0 - z 772 bool matchSubAddSameReg(MachineInstr &MI, BuildFnTy &MatchInfo); 773 774 /// \returns true if it is possible to simplify a select instruction \p MI 775 /// to a min/max instruction of some sort. 776 bool matchSimplifySelectToMinMax(MachineInstr &MI, BuildFnTy &MatchInfo); 777 778 /// Transform: 779 /// (X + Y) == X -> Y == 0 780 /// (X - Y) == X -> Y == 0 781 /// (X ^ Y) == X -> Y == 0 782 /// (X + Y) != X -> Y != 0 783 /// (X - Y) != X -> Y != 0 784 /// (X ^ Y) != X -> Y != 0 785 bool matchRedundantBinOpInEquality(MachineInstr &MI, BuildFnTy &MatchInfo); 786 787 /// Match shifts greater or equal to the bitwidth of the operation. 788 bool matchShiftsTooBig(MachineInstr &MI); 789 790 private: 791 /// Given a non-indexed load or store instruction \p MI, find an offset that 792 /// can be usefully and legally folded into it as a post-indexing operation. 793 /// 794 /// \returns true if a candidate is found. 795 bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 796 Register &Offset); 797 798 /// Given a non-indexed load or store instruction \p MI, find an offset that 799 /// can be usefully and legally folded into it as a pre-indexing operation. 800 /// 801 /// \returns true if a candidate is found. 802 bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 803 Register &Offset); 804 805 /// Helper function for matchLoadOrCombine. Searches for Registers 806 /// which may have been produced by a load instruction + some arithmetic. 807 /// 808 /// \param [in] Root - The search root. 809 /// 810 /// \returns The Registers found during the search. 811 std::optional<SmallVector<Register, 8>> 812 findCandidatesForLoadOrCombine(const MachineInstr *Root) const; 813 814 /// Helper function for matchLoadOrCombine. 815 /// 816 /// Checks if every register in \p RegsToVisit is defined by a load 817 /// instruction + some arithmetic. 818 /// 819 /// \param [out] MemOffset2Idx - Maps the byte positions each load ends up 820 /// at to the index of the load. 821 /// \param [in] MemSizeInBits - The number of bits each load should produce. 822 /// 823 /// \returns On success, a 3-tuple containing lowest-index load found, the 824 /// lowest index, and the last load in the sequence. 825 std::optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>> 826 findLoadOffsetsForLoadOrCombine( 827 SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx, 828 const SmallVector<Register, 8> &RegsToVisit, 829 const unsigned MemSizeInBits); 830 831 /// Examines the G_PTR_ADD instruction \p PtrAdd and determines if performing 832 /// a re-association of its operands would break an existing legal addressing 833 /// mode that the address computation currently represents. 834 bool reassociationCanBreakAddressingModePattern(MachineInstr &PtrAdd); 835 836 /// Behavior when a floating point min/max is given one NaN and one 837 /// non-NaN as input. 838 enum class SelectPatternNaNBehaviour { 839 NOT_APPLICABLE = 0, /// NaN behavior not applicable. 840 RETURNS_NAN, /// Given one NaN input, returns the NaN. 841 RETURNS_OTHER, /// Given one NaN input, returns the non-NaN. 842 RETURNS_ANY /// Given one NaN input, can return either (or both operands are 843 /// known non-NaN.) 844 }; 845 846 /// \returns which of \p LHS and \p RHS would be the result of a non-equality 847 /// floating point comparison where one of \p LHS and \p RHS may be NaN. 848 /// 849 /// If both \p LHS and \p RHS may be NaN, returns 850 /// SelectPatternNaNBehaviour::NOT_APPLICABLE. 851 SelectPatternNaNBehaviour 852 computeRetValAgainstNaN(Register LHS, Register RHS, 853 bool IsOrderedComparison) const; 854 855 /// Determines the floating point min/max opcode which should be used for 856 /// a G_SELECT fed by a G_FCMP with predicate \p Pred. 857 /// 858 /// \returns 0 if this G_SELECT should not be combined to a floating point 859 /// min or max. If it should be combined, returns one of 860 /// 861 /// * G_FMAXNUM 862 /// * G_FMAXIMUM 863 /// * G_FMINNUM 864 /// * G_FMINIMUM 865 /// 866 /// Helper function for matchFPSelectToMinMax. 867 unsigned getFPMinMaxOpcForSelect(CmpInst::Predicate Pred, LLT DstTy, 868 SelectPatternNaNBehaviour VsNaNRetVal) const; 869 870 /// Handle floating point cases for matchSimplifySelectToMinMax. 871 /// 872 /// E.g. 873 /// 874 /// select (fcmp uge x, 1.0) x, 1.0 -> fmax x, 1.0 875 /// select (fcmp uge x, 1.0) 1.0, x -> fminnm x, 1.0 876 bool matchFPSelectToMinMax(Register Dst, Register Cond, Register TrueVal, 877 Register FalseVal, BuildFnTy &MatchInfo); 878 }; 879 } // namespace llvm 880 881 #endif 882