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/APFloat.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h" 23 #include "llvm/CodeGen/LowLevelType.h" 24 #include "llvm/CodeGen/Register.h" 25 #include "llvm/Support/Alignment.h" 26 27 namespace llvm { 28 29 class GISelChangeObserver; 30 class MachineIRBuilder; 31 class MachineInstrBuilder; 32 class MachineRegisterInfo; 33 class MachineInstr; 34 class MachineOperand; 35 class GISelKnownBits; 36 class MachineDominatorTree; 37 class LegalizerInfo; 38 struct LegalityQuery; 39 class RegisterBank; 40 class RegisterBankInfo; 41 class TargetLowering; 42 class TargetRegisterInfo; 43 44 struct PreferredTuple { 45 LLT Ty; // The result type of the extend. 46 unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT 47 MachineInstr *MI; 48 }; 49 50 struct IndexedLoadStoreMatchInfo { 51 Register Addr; 52 Register Base; 53 Register Offset; 54 bool IsPre; 55 }; 56 57 struct PtrAddChain { 58 int64_t Imm; 59 Register Base; 60 const RegisterBank *Bank; 61 }; 62 63 struct RegisterImmPair { 64 Register Reg; 65 int64_t Imm; 66 }; 67 68 struct ShiftOfShiftedLogic { 69 MachineInstr *Logic; 70 MachineInstr *Shift2; 71 Register LogicNonShiftReg; 72 uint64_t ValSum; 73 }; 74 75 using BuildFnTy = std::function<void(MachineIRBuilder &)>; 76 77 struct MergeTruncStoresInfo { 78 SmallVector<GStore *> FoundStores; 79 GStore *LowestIdxStore = nullptr; 80 Register WideSrcVal; 81 bool NeedBSwap = false; 82 bool NeedRotate = false; 83 }; 84 85 using OperandBuildSteps = 86 SmallVector<std::function<void(MachineInstrBuilder &)>, 4>; 87 struct InstructionBuildSteps { 88 unsigned Opcode = 0; /// The opcode for the produced instruction. 89 OperandBuildSteps OperandFns; /// Operands to be added to the instruction. 90 InstructionBuildSteps() = default; 91 InstructionBuildSteps(unsigned Opcode, const OperandBuildSteps &OperandFns) 92 : Opcode(Opcode), OperandFns(OperandFns) {} 93 }; 94 95 struct InstructionStepsMatchInfo { 96 /// Describes instructions to be built during a combine. 97 SmallVector<InstructionBuildSteps, 2> InstrsToBuild; 98 InstructionStepsMatchInfo() = default; 99 InstructionStepsMatchInfo( 100 std::initializer_list<InstructionBuildSteps> InstrsToBuild) 101 : InstrsToBuild(InstrsToBuild) {} 102 }; 103 104 class CombinerHelper { 105 protected: 106 MachineIRBuilder &Builder; 107 MachineRegisterInfo &MRI; 108 GISelChangeObserver &Observer; 109 GISelKnownBits *KB; 110 MachineDominatorTree *MDT; 111 const LegalizerInfo *LI; 112 const RegisterBankInfo *RBI; 113 const TargetRegisterInfo *TRI; 114 115 public: 116 CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B, 117 GISelKnownBits *KB = nullptr, 118 MachineDominatorTree *MDT = nullptr, 119 const LegalizerInfo *LI = nullptr); 120 121 GISelKnownBits *getKnownBits() const { 122 return KB; 123 } 124 125 const TargetLowering &getTargetLowering() const; 126 127 /// \return true if the combine is running prior to legalization, or if \p 128 /// Query is legal on the target. 129 bool isLegalOrBeforeLegalizer(const LegalityQuery &Query) const; 130 131 /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes 132 void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const; 133 134 /// Replace a single register operand with a new register and inform the 135 /// observer of the changes. 136 void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp, 137 Register ToReg) const; 138 139 /// Replace the opcode in instruction with a new opcode and inform the 140 /// observer of the changes. 141 void replaceOpcodeWith(MachineInstr &FromMI, unsigned ToOpcode) const; 142 143 /// Get the register bank of \p Reg. 144 /// If Reg has not been assigned a register, a register class, 145 /// or a register bank, then this returns nullptr. 146 /// 147 /// \pre Reg.isValid() 148 const RegisterBank *getRegBank(Register Reg) const; 149 150 /// Set the register bank of \p Reg. 151 /// Does nothing if the RegBank is null. 152 /// This is the counterpart to getRegBank. 153 void setRegBank(Register Reg, const RegisterBank *RegBank); 154 155 /// If \p MI is COPY, try to combine it. 156 /// Returns true if MI changed. 157 bool tryCombineCopy(MachineInstr &MI); 158 bool matchCombineCopy(MachineInstr &MI); 159 void applyCombineCopy(MachineInstr &MI); 160 161 /// Returns true if \p DefMI precedes \p UseMI or they are the same 162 /// instruction. Both must be in the same basic block. 163 bool isPredecessor(const MachineInstr &DefMI, const MachineInstr &UseMI); 164 165 /// Returns true if \p DefMI dominates \p UseMI. By definition an 166 /// instruction dominates itself. 167 /// 168 /// If we haven't been provided with a MachineDominatorTree during 169 /// construction, this function returns a conservative result that tracks just 170 /// a single basic block. 171 bool dominates(const MachineInstr &DefMI, const MachineInstr &UseMI); 172 173 /// If \p MI is extend that consumes the result of a load, try to combine it. 174 /// Returns true if MI changed. 175 bool tryCombineExtendingLoads(MachineInstr &MI); 176 bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo); 177 void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo); 178 179 /// Match (and (load x), mask) -> zextload x 180 bool matchCombineLoadWithAndMask(MachineInstr &MI, BuildFnTy &MatchInfo); 181 182 /// Combine \p MI into a pre-indexed or post-indexed load/store operation if 183 /// legal and the surrounding code makes it useful. 184 bool tryCombineIndexedLoadStore(MachineInstr &MI); 185 bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); 186 void applyCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); 187 188 bool matchSextTruncSextLoad(MachineInstr &MI); 189 void applySextTruncSextLoad(MachineInstr &MI); 190 191 /// Match sext_inreg(load p), imm -> sextload p 192 bool matchSextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo); 193 void applySextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo); 194 195 /// Try to combine G_[SU]DIV and G_[SU]REM into a single G_[SU]DIVREM 196 /// when their source operands are identical. 197 bool matchCombineDivRem(MachineInstr &MI, MachineInstr *&OtherMI); 198 void applyCombineDivRem(MachineInstr &MI, MachineInstr *&OtherMI); 199 200 /// If a brcond's true block is not the fallthrough, make it so by inverting 201 /// the condition and swapping operands. 202 bool matchOptBrCondByInvertingCond(MachineInstr &MI, MachineInstr *&BrCond); 203 void applyOptBrCondByInvertingCond(MachineInstr &MI, MachineInstr *&BrCond); 204 205 /// If \p MI is G_CONCAT_VECTORS, try to combine it. 206 /// Returns true if MI changed. 207 /// Right now, we support: 208 /// - concat_vector(undef, undef) => undef 209 /// - concat_vector(build_vector(A, B), build_vector(C, D)) => 210 /// build_vector(A, B, C, D) 211 /// 212 /// \pre MI.getOpcode() == G_CONCAT_VECTORS. 213 bool tryCombineConcatVectors(MachineInstr &MI); 214 /// Check if the G_CONCAT_VECTORS \p MI is undef or if it 215 /// can be flattened into a build_vector. 216 /// In the first case \p IsUndef will be true. 217 /// In the second case \p Ops will contain the operands needed 218 /// to produce the flattened build_vector. 219 /// 220 /// \pre MI.getOpcode() == G_CONCAT_VECTORS. 221 bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef, 222 SmallVectorImpl<Register> &Ops); 223 /// Replace \p MI with a flattened build_vector with \p Ops or an 224 /// implicit_def if IsUndef is true. 225 void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef, 226 const ArrayRef<Register> Ops); 227 228 /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS. 229 /// Returns true if MI changed. 230 /// 231 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR. 232 bool tryCombineShuffleVector(MachineInstr &MI); 233 /// Check if the G_SHUFFLE_VECTOR \p MI can be replaced by a 234 /// concat_vectors. 235 /// \p Ops will contain the operands needed to produce the flattened 236 /// concat_vectors. 237 /// 238 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR. 239 bool matchCombineShuffleVector(MachineInstr &MI, 240 SmallVectorImpl<Register> &Ops); 241 /// Replace \p MI with a concat_vectors with \p Ops. 242 void applyCombineShuffleVector(MachineInstr &MI, 243 const ArrayRef<Register> Ops); 244 245 /// Optimize memcpy intrinsics et al, e.g. constant len calls. 246 /// /p MaxLen if non-zero specifies the max length of a mem libcall to inline. 247 /// 248 /// For example (pre-indexed): 249 /// 250 /// $addr = G_PTR_ADD $base, $offset 251 /// [...] 252 /// $val = G_LOAD $addr 253 /// [...] 254 /// $whatever = COPY $addr 255 /// 256 /// --> 257 /// 258 /// $val, $addr = G_INDEXED_LOAD $base, $offset, 1 (IsPre) 259 /// [...] 260 /// $whatever = COPY $addr 261 /// 262 /// or (post-indexed): 263 /// 264 /// G_STORE $val, $base 265 /// [...] 266 /// $addr = G_PTR_ADD $base, $offset 267 /// [...] 268 /// $whatever = COPY $addr 269 /// 270 /// --> 271 /// 272 /// $addr = G_INDEXED_STORE $val, $base, $offset 273 /// [...] 274 /// $whatever = COPY $addr 275 bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0); 276 277 bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo); 278 void applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo); 279 280 /// Fold (shift (shift base, x), y) -> (shift base (x+y)) 281 bool matchShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo); 282 void applyShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo); 283 284 /// If we have a shift-by-constant of a bitwise logic op that itself has a 285 /// shift-by-constant operand with identical opcode, we may be able to convert 286 /// that into 2 independent shifts followed by the logic op. 287 bool matchShiftOfShiftedLogic(MachineInstr &MI, 288 ShiftOfShiftedLogic &MatchInfo); 289 void applyShiftOfShiftedLogic(MachineInstr &MI, 290 ShiftOfShiftedLogic &MatchInfo); 291 292 /// Transform a multiply by a power-of-2 value to a left shift. 293 bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); 294 void applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); 295 296 // Transform a G_SHL with an extended source into a narrower shift if 297 // possible. 298 bool matchCombineShlOfExtend(MachineInstr &MI, RegisterImmPair &MatchData); 299 void applyCombineShlOfExtend(MachineInstr &MI, 300 const RegisterImmPair &MatchData); 301 302 /// Fold away a merge of an unmerge of the corresponding values. 303 bool matchCombineMergeUnmerge(MachineInstr &MI, Register &MatchInfo); 304 305 /// Reduce a shift by a constant to an unmerge and a shift on a half sized 306 /// type. This will not produce a shift smaller than \p TargetShiftSize. 307 bool matchCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftSize, 308 unsigned &ShiftVal); 309 void applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal); 310 bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount); 311 312 /// Transform <ty,...> G_UNMERGE(G_MERGE ty X, Y, Z) -> ty X, Y, Z. 313 bool 314 matchCombineUnmergeMergeToPlainValues(MachineInstr &MI, 315 SmallVectorImpl<Register> &Operands); 316 void 317 applyCombineUnmergeMergeToPlainValues(MachineInstr &MI, 318 SmallVectorImpl<Register> &Operands); 319 320 /// Transform G_UNMERGE Constant -> Constant1, Constant2, ... 321 bool matchCombineUnmergeConstant(MachineInstr &MI, 322 SmallVectorImpl<APInt> &Csts); 323 void applyCombineUnmergeConstant(MachineInstr &MI, 324 SmallVectorImpl<APInt> &Csts); 325 326 /// Transform G_UNMERGE G_IMPLICIT_DEF -> G_IMPLICIT_DEF, G_IMPLICIT_DEF, ... 327 bool 328 matchCombineUnmergeUndef(MachineInstr &MI, 329 std::function<void(MachineIRBuilder &)> &MatchInfo); 330 331 /// Transform X, Y<dead> = G_UNMERGE Z -> X = G_TRUNC Z. 332 bool matchCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI); 333 void applyCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI); 334 335 /// Transform X, Y = G_UNMERGE(G_ZEXT(Z)) -> X = G_ZEXT(Z); Y = G_CONSTANT 0 336 bool matchCombineUnmergeZExtToZExt(MachineInstr &MI); 337 void applyCombineUnmergeZExtToZExt(MachineInstr &MI); 338 339 /// Transform fp_instr(cst) to constant result of the fp operation. 340 bool matchCombineConstantFoldFpUnary(MachineInstr &MI, 341 Optional<APFloat> &Cst); 342 void applyCombineConstantFoldFpUnary(MachineInstr &MI, 343 Optional<APFloat> &Cst); 344 345 /// Transform IntToPtr(PtrToInt(x)) to x if cast is in the same address space. 346 bool matchCombineI2PToP2I(MachineInstr &MI, Register &Reg); 347 void applyCombineI2PToP2I(MachineInstr &MI, Register &Reg); 348 349 /// Transform PtrToInt(IntToPtr(x)) to x. 350 bool matchCombineP2IToI2P(MachineInstr &MI, Register &Reg); 351 void applyCombineP2IToI2P(MachineInstr &MI, Register &Reg); 352 353 /// Transform G_ADD (G_PTRTOINT x), y -> G_PTRTOINT (G_PTR_ADD x, y) 354 /// Transform G_ADD y, (G_PTRTOINT x) -> G_PTRTOINT (G_PTR_ADD x, y) 355 bool matchCombineAddP2IToPtrAdd(MachineInstr &MI, 356 std::pair<Register, bool> &PtrRegAndCommute); 357 void applyCombineAddP2IToPtrAdd(MachineInstr &MI, 358 std::pair<Register, bool> &PtrRegAndCommute); 359 360 // Transform G_PTR_ADD (G_PTRTOINT C1), C2 -> C1 + C2 361 bool matchCombineConstPtrAddToI2P(MachineInstr &MI, APInt &NewCst); 362 void applyCombineConstPtrAddToI2P(MachineInstr &MI, APInt &NewCst); 363 364 /// Transform anyext(trunc(x)) to x. 365 bool matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg); 366 void applyCombineAnyExtTrunc(MachineInstr &MI, Register &Reg); 367 368 /// Transform zext(trunc(x)) to x. 369 bool matchCombineZextTrunc(MachineInstr &MI, Register &Reg); 370 371 /// Transform [asz]ext([asz]ext(x)) to [asz]ext x. 372 bool matchCombineExtOfExt(MachineInstr &MI, 373 std::tuple<Register, unsigned> &MatchInfo); 374 void applyCombineExtOfExt(MachineInstr &MI, 375 std::tuple<Register, unsigned> &MatchInfo); 376 377 /// Transform fneg(fneg(x)) to x. 378 bool matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg); 379 380 /// Match fabs(fabs(x)) to fabs(x). 381 bool matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src); 382 void applyCombineFAbsOfFAbs(MachineInstr &MI, Register &Src); 383 384 /// Transform fabs(fneg(x)) to fabs(x). 385 bool matchCombineFAbsOfFNeg(MachineInstr &MI, BuildFnTy &MatchInfo); 386 387 /// Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x). 388 bool matchCombineTruncOfExt(MachineInstr &MI, 389 std::pair<Register, unsigned> &MatchInfo); 390 void applyCombineTruncOfExt(MachineInstr &MI, 391 std::pair<Register, unsigned> &MatchInfo); 392 393 /// Transform trunc (shl x, K) to shl (trunc x), 394 /// K => K < VT.getScalarSizeInBits(). 395 bool matchCombineTruncOfShl(MachineInstr &MI, 396 std::pair<Register, Register> &MatchInfo); 397 void applyCombineTruncOfShl(MachineInstr &MI, 398 std::pair<Register, Register> &MatchInfo); 399 400 /// Transform G_MUL(x, -1) to G_SUB(0, x) 401 void applyCombineMulByNegativeOne(MachineInstr &MI); 402 403 /// Return true if any explicit use operand on \p MI is defined by a 404 /// G_IMPLICIT_DEF. 405 bool matchAnyExplicitUseIsUndef(MachineInstr &MI); 406 407 /// Return true if all register explicit use operands on \p MI are defined by 408 /// a G_IMPLICIT_DEF. 409 bool matchAllExplicitUsesAreUndef(MachineInstr &MI); 410 411 /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask. 412 bool matchUndefShuffleVectorMask(MachineInstr &MI); 413 414 /// Return true if a G_STORE instruction \p MI is storing an undef value. 415 bool matchUndefStore(MachineInstr &MI); 416 417 /// Return true if a G_SELECT instruction \p MI has an undef comparison. 418 bool matchUndefSelectCmp(MachineInstr &MI); 419 420 /// Return true if a G_SELECT instruction \p MI has a constant comparison. If 421 /// true, \p OpIdx will store the operand index of the known selected value. 422 bool matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx); 423 424 /// Replace an instruction with a G_FCONSTANT with value \p C. 425 bool replaceInstWithFConstant(MachineInstr &MI, double C); 426 427 /// Replace an instruction with a G_CONSTANT with value \p C. 428 bool replaceInstWithConstant(MachineInstr &MI, int64_t C); 429 430 /// Replace an instruction with a G_CONSTANT with value \p C. 431 bool replaceInstWithConstant(MachineInstr &MI, APInt C); 432 433 /// Replace an instruction with a G_IMPLICIT_DEF. 434 bool replaceInstWithUndef(MachineInstr &MI); 435 436 /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand. 437 bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx); 438 439 /// Delete \p MI and replace all of its uses with \p Replacement. 440 bool replaceSingleDefInstWithReg(MachineInstr &MI, Register Replacement); 441 442 /// Return true if \p MOP1 and \p MOP2 are register operands are defined by 443 /// equivalent instructions. 444 bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2); 445 446 /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to 447 /// \p C. 448 bool matchConstantOp(const MachineOperand &MOP, int64_t C); 449 450 /// Optimize (cond ? x : x) -> x 451 bool matchSelectSameVal(MachineInstr &MI); 452 453 /// Optimize (x op x) -> x 454 bool matchBinOpSameVal(MachineInstr &MI); 455 456 /// Check if operand \p OpIdx is zero. 457 bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx); 458 459 /// Check if operand \p OpIdx is undef. 460 bool matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx); 461 462 /// Check if operand \p OpIdx is known to be a power of 2. 463 bool matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI, unsigned OpIdx); 464 465 /// Erase \p MI 466 bool eraseInst(MachineInstr &MI); 467 468 /// Return true if MI is a G_ADD which can be simplified to a G_SUB. 469 bool matchSimplifyAddToSub(MachineInstr &MI, 470 std::tuple<Register, Register> &MatchInfo); 471 void applySimplifyAddToSub(MachineInstr &MI, 472 std::tuple<Register, Register> &MatchInfo); 473 474 /// Match (logic_op (op x...), (op y...)) -> (op (logic_op x, y)) 475 bool 476 matchHoistLogicOpWithSameOpcodeHands(MachineInstr &MI, 477 InstructionStepsMatchInfo &MatchInfo); 478 479 /// Replace \p MI with a series of instructions described in \p MatchInfo. 480 void applyBuildInstructionSteps(MachineInstr &MI, 481 InstructionStepsMatchInfo &MatchInfo); 482 483 /// Match ashr (shl x, C), C -> sext_inreg (C) 484 bool matchAshrShlToSextInreg(MachineInstr &MI, 485 std::tuple<Register, int64_t> &MatchInfo); 486 void applyAshShlToSextInreg(MachineInstr &MI, 487 std::tuple<Register, int64_t> &MatchInfo); 488 489 /// Fold and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0 490 bool matchOverlappingAnd(MachineInstr &MI, 491 BuildFnTy &MatchInfo); 492 493 /// \return true if \p MI is a G_AND instruction whose operands are x and y 494 /// where x & y == x or x & y == y. (E.g., one of operands is all-ones value.) 495 /// 496 /// \param [in] MI - The G_AND instruction. 497 /// \param [out] Replacement - A register the G_AND should be replaced with on 498 /// success. 499 bool matchRedundantAnd(MachineInstr &MI, Register &Replacement); 500 501 /// \return true if \p MI is a G_OR instruction whose operands are x and y 502 /// where x | y == x or x | y == y. (E.g., one of operands is all-zeros 503 /// value.) 504 /// 505 /// \param [in] MI - The G_OR instruction. 506 /// \param [out] Replacement - A register the G_OR should be replaced with on 507 /// success. 508 bool matchRedundantOr(MachineInstr &MI, Register &Replacement); 509 510 /// \return true if \p MI is a G_SEXT_INREG that can be erased. 511 bool matchRedundantSExtInReg(MachineInstr &MI); 512 513 /// Combine inverting a result of a compare into the opposite cond code. 514 bool matchNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); 515 void applyNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); 516 517 /// Fold (xor (and x, y), y) -> (and (not x), y) 518 ///{ 519 bool matchXorOfAndWithSameReg(MachineInstr &MI, 520 std::pair<Register, Register> &MatchInfo); 521 void applyXorOfAndWithSameReg(MachineInstr &MI, 522 std::pair<Register, Register> &MatchInfo); 523 ///} 524 525 /// Combine G_PTR_ADD with nullptr to G_INTTOPTR 526 bool matchPtrAddZero(MachineInstr &MI); 527 void applyPtrAddZero(MachineInstr &MI); 528 529 /// Combine G_UREM x, (known power of 2) to an add and bitmasking. 530 void applySimplifyURemByPow2(MachineInstr &MI); 531 532 bool matchCombineInsertVecElts(MachineInstr &MI, 533 SmallVectorImpl<Register> &MatchInfo); 534 535 void applyCombineInsertVecElts(MachineInstr &MI, 536 SmallVectorImpl<Register> &MatchInfo); 537 538 /// Match expression trees of the form 539 /// 540 /// \code 541 /// sN *a = ... 542 /// sM val = a[0] | (a[1] << N) | (a[2] << 2N) | (a[3] << 3N) ... 543 /// \endcode 544 /// 545 /// And check if the tree can be replaced with a M-bit load + possibly a 546 /// bswap. 547 bool matchLoadOrCombine(MachineInstr &MI, BuildFnTy &MatchInfo); 548 549 bool matchTruncStoreMerge(MachineInstr &MI, MergeTruncStoresInfo &MatchInfo); 550 void applyTruncStoreMerge(MachineInstr &MI, MergeTruncStoresInfo &MatchInfo); 551 552 bool matchExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI); 553 void applyExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI); 554 555 bool matchExtractVecEltBuildVec(MachineInstr &MI, Register &Reg); 556 void applyExtractVecEltBuildVec(MachineInstr &MI, Register &Reg); 557 558 bool matchExtractAllEltsFromBuildVector( 559 MachineInstr &MI, 560 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo); 561 void applyExtractAllEltsFromBuildVector( 562 MachineInstr &MI, 563 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo); 564 565 /// Use a function which takes in a MachineIRBuilder to perform a combine. 566 /// By default, it erases the instruction \p MI from the function. 567 void applyBuildFn(MachineInstr &MI, BuildFnTy &MatchInfo); 568 /// Use a function which takes in a MachineIRBuilder to perform a combine. 569 /// This variant does not erase \p MI after calling the build function. 570 void applyBuildFnNoErase(MachineInstr &MI, BuildFnTy &MatchInfo); 571 572 bool matchOrShiftToFunnelShift(MachineInstr &MI, BuildFnTy &MatchInfo); 573 bool matchFunnelShiftToRotate(MachineInstr &MI); 574 void applyFunnelShiftToRotate(MachineInstr &MI); 575 bool matchRotateOutOfRange(MachineInstr &MI); 576 void applyRotateOutOfRange(MachineInstr &MI); 577 578 /// \returns true if a G_ICMP instruction \p MI can be replaced with a true 579 /// or false constant based off of KnownBits information. 580 bool matchICmpToTrueFalseKnownBits(MachineInstr &MI, int64_t &MatchInfo); 581 582 /// \returns true if a G_ICMP \p MI can be replaced with its LHS based off of 583 /// KnownBits information. 584 bool 585 matchICmpToLHSKnownBits(MachineInstr &MI, 586 BuildFnTy &MatchInfo); 587 588 /// \returns true if (and (or x, c1), c2) can be replaced with (and x, c2) 589 bool matchAndOrDisjointMask(MachineInstr &MI, BuildFnTy &MatchInfo); 590 591 bool matchBitfieldExtractFromSExtInReg(MachineInstr &MI, 592 BuildFnTy &MatchInfo); 593 /// Match: and (lshr x, cst), mask -> ubfx x, cst, width 594 bool matchBitfieldExtractFromAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 595 596 /// Match: shr (shl x, n), k -> sbfx/ubfx x, pos, width 597 bool matchBitfieldExtractFromShr(MachineInstr &MI, BuildFnTy &MatchInfo); 598 599 /// Match: shr (and x, n), k -> ubfx x, pos, width 600 bool matchBitfieldExtractFromShrAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 601 602 // Helpers for reassociation: 603 bool matchReassocConstantInnerRHS(GPtrAdd &MI, MachineInstr *RHS, 604 BuildFnTy &MatchInfo); 605 bool matchReassocFoldConstantsInSubTree(GPtrAdd &MI, MachineInstr *LHS, 606 MachineInstr *RHS, 607 BuildFnTy &MatchInfo); 608 bool matchReassocConstantInnerLHS(GPtrAdd &MI, MachineInstr *LHS, 609 MachineInstr *RHS, BuildFnTy &MatchInfo); 610 /// Reassociate pointer calculations with G_ADD involved, to allow better 611 /// addressing mode usage. 612 bool matchReassocPtrAdd(MachineInstr &MI, BuildFnTy &MatchInfo); 613 614 /// Do constant folding when opportunities are exposed after MIR building. 615 bool matchConstantFold(MachineInstr &MI, APInt &MatchInfo); 616 617 /// \returns true if it is possible to narrow the width of a scalar binop 618 /// feeding a G_AND instruction \p MI. 619 bool matchNarrowBinopFeedingAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 620 621 /// Given an G_UDIV \p MI expressing a divide by constant, return an 622 /// expression that implements it by multiplying by a magic number. 623 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide". 624 MachineInstr *buildUDivUsingMul(MachineInstr &MI); 625 /// Combine G_UDIV by constant into a multiply by magic constant. 626 bool matchUDivByConst(MachineInstr &MI); 627 void applyUDivByConst(MachineInstr &MI); 628 629 // G_UMULH x, (1 << c)) -> x >> (bitwidth - c) 630 bool matchUMulHToLShr(MachineInstr &MI); 631 void applyUMulHToLShr(MachineInstr &MI); 632 633 /// Try to transform \p MI by using all of the above 634 /// combine functions. Returns true if changed. 635 bool tryCombine(MachineInstr &MI); 636 637 /// Emit loads and stores that perform the given memcpy. 638 /// Assumes \p MI is a G_MEMCPY_INLINE 639 /// TODO: implement dynamically sized inline memcpy, 640 /// and rename: s/bool tryEmit/void emit/ 641 bool tryEmitMemcpyInline(MachineInstr &MI); 642 643 /// Match: 644 /// (G_UMULO x, 2) -> (G_UADDO x, x) 645 /// (G_SMULO x, 2) -> (G_SADDO x, x) 646 bool matchMulOBy2(MachineInstr &MI, BuildFnTy &MatchInfo); 647 648 /// Transform (fadd x, fneg(y)) -> (fsub x, y) 649 /// (fadd fneg(x), y) -> (fsub y, x) 650 /// (fsub x, fneg(y)) -> (fadd x, y) 651 /// (fmul fneg(x), fneg(y)) -> (fmul x, y) 652 /// (fdiv fneg(x), fneg(y)) -> (fdiv x, y) 653 /// (fmad fneg(x), fneg(y), z) -> (fmad x, y, z) 654 /// (fma fneg(x), fneg(y), z) -> (fma x, y, z) 655 bool matchRedundantNegOperands(MachineInstr &MI, BuildFnTy &MatchInfo); 656 657 bool canCombineFMadOrFMA(MachineInstr &MI, bool &AllowFusionGlobally, 658 bool &HasFMAD, bool &Aggressive, 659 bool CanReassociate = false); 660 661 /// Transform (fadd (fmul x, y), z) -> (fma x, y, z) 662 /// (fadd (fmul x, y), z) -> (fmad x, y, z) 663 bool matchCombineFAddFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo); 664 665 /// Transform (fadd (fpext (fmul x, y)), z) -> (fma (fpext x), (fpext y), z) 666 /// (fadd (fpext (fmul x, y)), z) -> (fmad (fpext x), (fpext y), z) 667 bool matchCombineFAddFpExtFMulToFMadOrFMA(MachineInstr &MI, 668 BuildFnTy &MatchInfo); 669 670 /// Transform (fadd (fma x, y, (fmul u, v)), z) -> (fma x, y, (fma u, v, z)) 671 /// (fadd (fmad x, y, (fmul u, v)), z) -> (fmad x, y, (fmad u, v, z)) 672 bool matchCombineFAddFMAFMulToFMadOrFMA(MachineInstr &MI, 673 BuildFnTy &MatchInfo); 674 675 // Transform (fadd (fma x, y, (fpext (fmul u, v))), z) 676 // -> (fma x, y, (fma (fpext u), (fpext v), z)) 677 // (fadd (fmad x, y, (fpext (fmul u, v))), z) 678 // -> (fmad x, y, (fmad (fpext u), (fpext v), z)) 679 bool matchCombineFAddFpExtFMulToFMadOrFMAAggressive(MachineInstr &MI, 680 BuildFnTy &MatchInfo); 681 682 /// Transform (fsub (fmul x, y), z) -> (fma x, y, -z) 683 /// (fsub (fmul x, y), z) -> (fmad x, y, -z) 684 bool matchCombineFSubFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo); 685 686 /// Transform (fsub (fneg (fmul, x, y)), z) -> (fma (fneg x), y, (fneg z)) 687 /// (fsub (fneg (fmul, x, y)), z) -> (fmad (fneg x), y, (fneg z)) 688 bool matchCombineFSubFNegFMulToFMadOrFMA(MachineInstr &MI, 689 BuildFnTy &MatchInfo); 690 691 /// Transform (fsub (fpext (fmul x, y)), z) 692 /// -> (fma (fpext x), (fpext y), (fneg z)) 693 /// (fsub (fpext (fmul x, y)), z) 694 /// -> (fmad (fpext x), (fpext y), (fneg z)) 695 bool matchCombineFSubFpExtFMulToFMadOrFMA(MachineInstr &MI, 696 BuildFnTy &MatchInfo); 697 698 /// Transform (fsub (fpext (fneg (fmul x, y))), z) 699 /// -> (fneg (fma (fpext x), (fpext y), z)) 700 /// (fsub (fpext (fneg (fmul x, y))), z) 701 /// -> (fneg (fmad (fpext x), (fpext y), z)) 702 bool matchCombineFSubFpExtFNegFMulToFMadOrFMA(MachineInstr &MI, 703 BuildFnTy &MatchInfo); 704 705 private: 706 /// Given a non-indexed load or store instruction \p MI, find an offset that 707 /// can be usefully and legally folded into it as a post-indexing operation. 708 /// 709 /// \returns true if a candidate is found. 710 bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 711 Register &Offset); 712 713 /// Given a non-indexed load or store instruction \p MI, find an offset that 714 /// can be usefully and legally folded into it as a pre-indexing operation. 715 /// 716 /// \returns true if a candidate is found. 717 bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 718 Register &Offset); 719 720 /// Helper function for matchLoadOrCombine. Searches for Registers 721 /// which may have been produced by a load instruction + some arithmetic. 722 /// 723 /// \param [in] Root - The search root. 724 /// 725 /// \returns The Registers found during the search. 726 Optional<SmallVector<Register, 8>> 727 findCandidatesForLoadOrCombine(const MachineInstr *Root) const; 728 729 /// Helper function for matchLoadOrCombine. 730 /// 731 /// Checks if every register in \p RegsToVisit is defined by a load 732 /// instruction + some arithmetic. 733 /// 734 /// \param [out] MemOffset2Idx - Maps the byte positions each load ends up 735 /// at to the index of the load. 736 /// \param [in] MemSizeInBits - The number of bits each load should produce. 737 /// 738 /// \returns On success, a 3-tuple containing lowest-index load found, the 739 /// lowest index, and the last load in the sequence. 740 Optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>> 741 findLoadOffsetsForLoadOrCombine( 742 SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx, 743 const SmallVector<Register, 8> &RegsToVisit, 744 const unsigned MemSizeInBits); 745 746 /// Examines the G_PTR_ADD instruction \p PtrAdd and determines if performing 747 /// a re-association of its operands would break an existing legal addressing 748 /// mode that the address computation currently represents. 749 bool reassociationCanBreakAddressingModePattern(MachineInstr &PtrAdd); 750 }; 751 } // namespace llvm 752 753 #endif 754