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/Register.h" 23 #include "llvm/Support/LowLevelTypeImpl.h" 24 #include <functional> 25 26 namespace llvm { 27 28 class GISelChangeObserver; 29 class APFloat; 30 class APInt; 31 class GPtrAdd; 32 class GStore; 33 class GZExtLoad; 34 class MachineIRBuilder; 35 class MachineInstrBuilder; 36 class MachineRegisterInfo; 37 class MachineInstr; 38 class MachineOperand; 39 class GISelKnownBits; 40 class MachineDominatorTree; 41 class LegalizerInfo; 42 struct LegalityQuery; 43 class RegisterBank; 44 class RegisterBankInfo; 45 class TargetLowering; 46 class TargetRegisterInfo; 47 48 struct PreferredTuple { 49 LLT Ty; // The result type of the extend. 50 unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT 51 MachineInstr *MI; 52 }; 53 54 struct IndexedLoadStoreMatchInfo { 55 Register Addr; 56 Register Base; 57 Register Offset; 58 bool IsPre; 59 }; 60 61 struct PtrAddChain { 62 int64_t Imm; 63 Register Base; 64 const RegisterBank *Bank; 65 }; 66 67 struct RegisterImmPair { 68 Register Reg; 69 int64_t Imm; 70 }; 71 72 struct ShiftOfShiftedLogic { 73 MachineInstr *Logic; 74 MachineInstr *Shift2; 75 Register LogicNonShiftReg; 76 uint64_t ValSum; 77 }; 78 79 using BuildFnTy = std::function<void(MachineIRBuilder &)>; 80 81 struct MergeTruncStoresInfo { 82 SmallVector<GStore *> FoundStores; 83 GStore *LowestIdxStore = nullptr; 84 Register WideSrcVal; 85 bool NeedBSwap = false; 86 bool NeedRotate = false; 87 }; 88 89 using OperandBuildSteps = 90 SmallVector<std::function<void(MachineInstrBuilder &)>, 4>; 91 struct InstructionBuildSteps { 92 unsigned Opcode = 0; /// The opcode for the produced instruction. 93 OperandBuildSteps OperandFns; /// Operands to be added to the instruction. 94 InstructionBuildSteps() = default; 95 InstructionBuildSteps(unsigned Opcode, const OperandBuildSteps &OperandFns) 96 : Opcode(Opcode), OperandFns(OperandFns) {} 97 }; 98 99 struct InstructionStepsMatchInfo { 100 /// Describes instructions to be built during a combine. 101 SmallVector<InstructionBuildSteps, 2> InstrsToBuild; 102 InstructionStepsMatchInfo() = default; 103 InstructionStepsMatchInfo( 104 std::initializer_list<InstructionBuildSteps> InstrsToBuild) 105 : InstrsToBuild(InstrsToBuild) {} 106 }; 107 108 class CombinerHelper { 109 protected: 110 MachineIRBuilder &Builder; 111 MachineRegisterInfo &MRI; 112 GISelChangeObserver &Observer; 113 GISelKnownBits *KB; 114 MachineDominatorTree *MDT; 115 const LegalizerInfo *LI; 116 const RegisterBankInfo *RBI; 117 const TargetRegisterInfo *TRI; 118 119 public: 120 CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B, 121 GISelKnownBits *KB = nullptr, 122 MachineDominatorTree *MDT = nullptr, 123 const LegalizerInfo *LI = nullptr); 124 125 GISelKnownBits *getKnownBits() const { 126 return KB; 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 /// Transform a multiply by a power-of-2 value to a left shift. 307 bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); 308 void applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); 309 310 // Transform a G_SHL with an extended source into a narrower shift if 311 // possible. 312 bool matchCombineShlOfExtend(MachineInstr &MI, RegisterImmPair &MatchData); 313 void applyCombineShlOfExtend(MachineInstr &MI, 314 const RegisterImmPair &MatchData); 315 316 /// Fold away a merge of an unmerge of the corresponding values. 317 bool matchCombineMergeUnmerge(MachineInstr &MI, Register &MatchInfo); 318 319 /// Reduce a shift by a constant to an unmerge and a shift on a half sized 320 /// type. This will not produce a shift smaller than \p TargetShiftSize. 321 bool matchCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftSize, 322 unsigned &ShiftVal); 323 void applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal); 324 bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount); 325 326 /// Transform <ty,...> G_UNMERGE(G_MERGE ty X, Y, Z) -> ty X, Y, Z. 327 bool 328 matchCombineUnmergeMergeToPlainValues(MachineInstr &MI, 329 SmallVectorImpl<Register> &Operands); 330 void 331 applyCombineUnmergeMergeToPlainValues(MachineInstr &MI, 332 SmallVectorImpl<Register> &Operands); 333 334 /// Transform G_UNMERGE Constant -> Constant1, Constant2, ... 335 bool matchCombineUnmergeConstant(MachineInstr &MI, 336 SmallVectorImpl<APInt> &Csts); 337 void applyCombineUnmergeConstant(MachineInstr &MI, 338 SmallVectorImpl<APInt> &Csts); 339 340 /// Transform G_UNMERGE G_IMPLICIT_DEF -> G_IMPLICIT_DEF, G_IMPLICIT_DEF, ... 341 bool 342 matchCombineUnmergeUndef(MachineInstr &MI, 343 std::function<void(MachineIRBuilder &)> &MatchInfo); 344 345 /// Transform X, Y<dead> = G_UNMERGE Z -> X = G_TRUNC Z. 346 bool matchCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI); 347 void applyCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI); 348 349 /// Transform X, Y = G_UNMERGE(G_ZEXT(Z)) -> X = G_ZEXT(Z); Y = G_CONSTANT 0 350 bool matchCombineUnmergeZExtToZExt(MachineInstr &MI); 351 void applyCombineUnmergeZExtToZExt(MachineInstr &MI); 352 353 /// Transform fp_instr(cst) to constant result of the fp operation. 354 bool matchCombineConstantFoldFpUnary(MachineInstr &MI, 355 Optional<APFloat> &Cst); 356 void applyCombineConstantFoldFpUnary(MachineInstr &MI, 357 Optional<APFloat> &Cst); 358 359 /// Transform IntToPtr(PtrToInt(x)) to x if cast is in the same address space. 360 bool matchCombineI2PToP2I(MachineInstr &MI, Register &Reg); 361 void applyCombineI2PToP2I(MachineInstr &MI, Register &Reg); 362 363 /// Transform PtrToInt(IntToPtr(x)) to x. 364 bool matchCombineP2IToI2P(MachineInstr &MI, Register &Reg); 365 void applyCombineP2IToI2P(MachineInstr &MI, Register &Reg); 366 367 /// Transform G_ADD (G_PTRTOINT x), y -> G_PTRTOINT (G_PTR_ADD x, y) 368 /// Transform G_ADD y, (G_PTRTOINT x) -> G_PTRTOINT (G_PTR_ADD x, y) 369 bool matchCombineAddP2IToPtrAdd(MachineInstr &MI, 370 std::pair<Register, bool> &PtrRegAndCommute); 371 void applyCombineAddP2IToPtrAdd(MachineInstr &MI, 372 std::pair<Register, bool> &PtrRegAndCommute); 373 374 // Transform G_PTR_ADD (G_PTRTOINT C1), C2 -> C1 + C2 375 bool matchCombineConstPtrAddToI2P(MachineInstr &MI, APInt &NewCst); 376 void applyCombineConstPtrAddToI2P(MachineInstr &MI, APInt &NewCst); 377 378 /// Transform anyext(trunc(x)) to x. 379 bool matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg); 380 void applyCombineAnyExtTrunc(MachineInstr &MI, Register &Reg); 381 382 /// Transform zext(trunc(x)) to x. 383 bool matchCombineZextTrunc(MachineInstr &MI, Register &Reg); 384 385 /// Transform [asz]ext([asz]ext(x)) to [asz]ext x. 386 bool matchCombineExtOfExt(MachineInstr &MI, 387 std::tuple<Register, unsigned> &MatchInfo); 388 void applyCombineExtOfExt(MachineInstr &MI, 389 std::tuple<Register, unsigned> &MatchInfo); 390 391 /// Transform fneg(fneg(x)) to x. 392 bool matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg); 393 394 /// Match fabs(fabs(x)) to fabs(x). 395 bool matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src); 396 void applyCombineFAbsOfFAbs(MachineInstr &MI, Register &Src); 397 398 /// Transform fabs(fneg(x)) to fabs(x). 399 bool matchCombineFAbsOfFNeg(MachineInstr &MI, BuildFnTy &MatchInfo); 400 401 /// Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x). 402 bool matchCombineTruncOfExt(MachineInstr &MI, 403 std::pair<Register, unsigned> &MatchInfo); 404 void applyCombineTruncOfExt(MachineInstr &MI, 405 std::pair<Register, unsigned> &MatchInfo); 406 407 /// Transform trunc (shl x, K) to shl (trunc x), 408 /// K => K < VT.getScalarSizeInBits(). 409 bool matchCombineTruncOfShl(MachineInstr &MI, 410 std::pair<Register, Register> &MatchInfo); 411 void applyCombineTruncOfShl(MachineInstr &MI, 412 std::pair<Register, Register> &MatchInfo); 413 414 /// Transform G_MUL(x, -1) to G_SUB(0, x) 415 void applyCombineMulByNegativeOne(MachineInstr &MI); 416 417 /// Return true if any explicit use operand on \p MI is defined by a 418 /// G_IMPLICIT_DEF. 419 bool matchAnyExplicitUseIsUndef(MachineInstr &MI); 420 421 /// Return true if all register explicit use operands on \p MI are defined by 422 /// a G_IMPLICIT_DEF. 423 bool matchAllExplicitUsesAreUndef(MachineInstr &MI); 424 425 /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask. 426 bool matchUndefShuffleVectorMask(MachineInstr &MI); 427 428 /// Return true if a G_STORE instruction \p MI is storing an undef value. 429 bool matchUndefStore(MachineInstr &MI); 430 431 /// Return true if a G_SELECT instruction \p MI has an undef comparison. 432 bool matchUndefSelectCmp(MachineInstr &MI); 433 434 /// Return true if a G_SELECT instruction \p MI has a constant comparison. If 435 /// true, \p OpIdx will store the operand index of the known selected value. 436 bool matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx); 437 438 /// Replace an instruction with a G_FCONSTANT with value \p C. 439 bool replaceInstWithFConstant(MachineInstr &MI, double C); 440 441 /// Replace an instruction with a G_CONSTANT with value \p C. 442 bool replaceInstWithConstant(MachineInstr &MI, int64_t C); 443 444 /// Replace an instruction with a G_CONSTANT with value \p C. 445 bool replaceInstWithConstant(MachineInstr &MI, APInt C); 446 447 /// Replace an instruction with a G_IMPLICIT_DEF. 448 bool replaceInstWithUndef(MachineInstr &MI); 449 450 /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand. 451 bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx); 452 453 /// Delete \p MI and replace all of its uses with \p Replacement. 454 bool replaceSingleDefInstWithReg(MachineInstr &MI, Register Replacement); 455 456 /// Return true if \p MOP1 and \p MOP2 are register operands are defined by 457 /// equivalent instructions. 458 bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2); 459 460 /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to 461 /// \p C. 462 bool matchConstantOp(const MachineOperand &MOP, int64_t C); 463 464 /// Optimize (cond ? x : x) -> x 465 bool matchSelectSameVal(MachineInstr &MI); 466 467 /// Optimize (x op x) -> x 468 bool matchBinOpSameVal(MachineInstr &MI); 469 470 /// Check if operand \p OpIdx is zero. 471 bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx); 472 473 /// Check if operand \p OpIdx is undef. 474 bool matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx); 475 476 /// Check if operand \p OpIdx is known to be a power of 2. 477 bool matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI, unsigned OpIdx); 478 479 /// Erase \p MI 480 bool eraseInst(MachineInstr &MI); 481 482 /// Return true if MI is a G_ADD which can be simplified to a G_SUB. 483 bool matchSimplifyAddToSub(MachineInstr &MI, 484 std::tuple<Register, Register> &MatchInfo); 485 void applySimplifyAddToSub(MachineInstr &MI, 486 std::tuple<Register, Register> &MatchInfo); 487 488 /// Match (logic_op (op x...), (op y...)) -> (op (logic_op x, y)) 489 bool 490 matchHoistLogicOpWithSameOpcodeHands(MachineInstr &MI, 491 InstructionStepsMatchInfo &MatchInfo); 492 493 /// Replace \p MI with a series of instructions described in \p MatchInfo. 494 void applyBuildInstructionSteps(MachineInstr &MI, 495 InstructionStepsMatchInfo &MatchInfo); 496 497 /// Match ashr (shl x, C), C -> sext_inreg (C) 498 bool matchAshrShlToSextInreg(MachineInstr &MI, 499 std::tuple<Register, int64_t> &MatchInfo); 500 void applyAshShlToSextInreg(MachineInstr &MI, 501 std::tuple<Register, int64_t> &MatchInfo); 502 503 /// Fold and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0 504 bool matchOverlappingAnd(MachineInstr &MI, 505 BuildFnTy &MatchInfo); 506 507 /// \return true if \p MI is a G_AND instruction whose operands are x and y 508 /// where x & y == x or x & y == y. (E.g., one of operands is all-ones value.) 509 /// 510 /// \param [in] MI - The G_AND instruction. 511 /// \param [out] Replacement - A register the G_AND should be replaced with on 512 /// success. 513 bool matchRedundantAnd(MachineInstr &MI, Register &Replacement); 514 515 /// \return true if \p MI is a G_OR instruction whose operands are x and y 516 /// where x | y == x or x | y == y. (E.g., one of operands is all-zeros 517 /// value.) 518 /// 519 /// \param [in] MI - The G_OR instruction. 520 /// \param [out] Replacement - A register the G_OR should be replaced with on 521 /// success. 522 bool matchRedundantOr(MachineInstr &MI, Register &Replacement); 523 524 /// \return true if \p MI is a G_SEXT_INREG that can be erased. 525 bool matchRedundantSExtInReg(MachineInstr &MI); 526 527 /// Combine inverting a result of a compare into the opposite cond code. 528 bool matchNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); 529 void applyNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); 530 531 /// Fold (xor (and x, y), y) -> (and (not x), y) 532 ///{ 533 bool matchXorOfAndWithSameReg(MachineInstr &MI, 534 std::pair<Register, Register> &MatchInfo); 535 void applyXorOfAndWithSameReg(MachineInstr &MI, 536 std::pair<Register, Register> &MatchInfo); 537 ///} 538 539 /// Combine G_PTR_ADD with nullptr to G_INTTOPTR 540 bool matchPtrAddZero(MachineInstr &MI); 541 void applyPtrAddZero(MachineInstr &MI); 542 543 /// Combine G_UREM x, (known power of 2) to an add and bitmasking. 544 void applySimplifyURemByPow2(MachineInstr &MI); 545 546 /// Push a binary operator through a select on constants. 547 /// 548 /// binop (select cond, K0, K1), K2 -> 549 /// select cond, (binop K0, K2), (binop K1, K2) 550 bool matchFoldBinOpIntoSelect(MachineInstr &MI, unsigned &SelectOpNo); 551 bool applyFoldBinOpIntoSelect(MachineInstr &MI, const unsigned &SelectOpNo); 552 553 bool matchCombineInsertVecElts(MachineInstr &MI, 554 SmallVectorImpl<Register> &MatchInfo); 555 556 void applyCombineInsertVecElts(MachineInstr &MI, 557 SmallVectorImpl<Register> &MatchInfo); 558 559 /// Match expression trees of the form 560 /// 561 /// \code 562 /// sN *a = ... 563 /// sM val = a[0] | (a[1] << N) | (a[2] << 2N) | (a[3] << 3N) ... 564 /// \endcode 565 /// 566 /// And check if the tree can be replaced with a M-bit load + possibly a 567 /// bswap. 568 bool matchLoadOrCombine(MachineInstr &MI, BuildFnTy &MatchInfo); 569 570 bool matchTruncStoreMerge(MachineInstr &MI, MergeTruncStoresInfo &MatchInfo); 571 void applyTruncStoreMerge(MachineInstr &MI, MergeTruncStoresInfo &MatchInfo); 572 573 bool matchExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI); 574 void applyExtendThroughPhis(MachineInstr &MI, MachineInstr *&ExtMI); 575 576 bool matchExtractVecEltBuildVec(MachineInstr &MI, Register &Reg); 577 void applyExtractVecEltBuildVec(MachineInstr &MI, Register &Reg); 578 579 bool matchExtractAllEltsFromBuildVector( 580 MachineInstr &MI, 581 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo); 582 void applyExtractAllEltsFromBuildVector( 583 MachineInstr &MI, 584 SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo); 585 586 /// Use a function which takes in a MachineIRBuilder to perform a combine. 587 /// By default, it erases the instruction \p MI from the function. 588 void applyBuildFn(MachineInstr &MI, BuildFnTy &MatchInfo); 589 /// Use a function which takes in a MachineIRBuilder to perform a combine. 590 /// This variant does not erase \p MI after calling the build function. 591 void applyBuildFnNoErase(MachineInstr &MI, BuildFnTy &MatchInfo); 592 593 bool matchOrShiftToFunnelShift(MachineInstr &MI, BuildFnTy &MatchInfo); 594 bool matchFunnelShiftToRotate(MachineInstr &MI); 595 void applyFunnelShiftToRotate(MachineInstr &MI); 596 bool matchRotateOutOfRange(MachineInstr &MI); 597 void applyRotateOutOfRange(MachineInstr &MI); 598 599 /// \returns true if a G_ICMP instruction \p MI can be replaced with a true 600 /// or false constant based off of KnownBits information. 601 bool matchICmpToTrueFalseKnownBits(MachineInstr &MI, int64_t &MatchInfo); 602 603 /// \returns true if a G_ICMP \p MI can be replaced with its LHS based off of 604 /// KnownBits information. 605 bool 606 matchICmpToLHSKnownBits(MachineInstr &MI, 607 BuildFnTy &MatchInfo); 608 609 /// \returns true if (and (or x, c1), c2) can be replaced with (and x, c2) 610 bool matchAndOrDisjointMask(MachineInstr &MI, BuildFnTy &MatchInfo); 611 612 bool matchBitfieldExtractFromSExtInReg(MachineInstr &MI, 613 BuildFnTy &MatchInfo); 614 /// Match: and (lshr x, cst), mask -> ubfx x, cst, width 615 bool matchBitfieldExtractFromAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 616 617 /// Match: shr (shl x, n), k -> sbfx/ubfx x, pos, width 618 bool matchBitfieldExtractFromShr(MachineInstr &MI, BuildFnTy &MatchInfo); 619 620 /// Match: shr (and x, n), k -> ubfx x, pos, width 621 bool matchBitfieldExtractFromShrAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 622 623 // Helpers for reassociation: 624 bool matchReassocConstantInnerRHS(GPtrAdd &MI, MachineInstr *RHS, 625 BuildFnTy &MatchInfo); 626 bool matchReassocFoldConstantsInSubTree(GPtrAdd &MI, MachineInstr *LHS, 627 MachineInstr *RHS, 628 BuildFnTy &MatchInfo); 629 bool matchReassocConstantInnerLHS(GPtrAdd &MI, MachineInstr *LHS, 630 MachineInstr *RHS, BuildFnTy &MatchInfo); 631 /// Reassociate pointer calculations with G_ADD involved, to allow better 632 /// addressing mode usage. 633 bool matchReassocPtrAdd(MachineInstr &MI, BuildFnTy &MatchInfo); 634 635 /// Do constant folding when opportunities are exposed after MIR building. 636 bool matchConstantFold(MachineInstr &MI, APInt &MatchInfo); 637 638 /// \returns true if it is possible to narrow the width of a scalar binop 639 /// feeding a G_AND instruction \p MI. 640 bool matchNarrowBinopFeedingAnd(MachineInstr &MI, BuildFnTy &MatchInfo); 641 642 /// Given an G_UDIV \p MI expressing a divide by constant, return an 643 /// expression that implements it by multiplying by a magic number. 644 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide". 645 MachineInstr *buildUDivUsingMul(MachineInstr &MI); 646 /// Combine G_UDIV by constant into a multiply by magic constant. 647 bool matchUDivByConst(MachineInstr &MI); 648 void applyUDivByConst(MachineInstr &MI); 649 650 // G_UMULH x, (1 << c)) -> x >> (bitwidth - c) 651 bool matchUMulHToLShr(MachineInstr &MI); 652 void applyUMulHToLShr(MachineInstr &MI); 653 654 /// Try to transform \p MI by using all of the above 655 /// combine functions. Returns true if changed. 656 bool tryCombine(MachineInstr &MI); 657 658 /// Emit loads and stores that perform the given memcpy. 659 /// Assumes \p MI is a G_MEMCPY_INLINE 660 /// TODO: implement dynamically sized inline memcpy, 661 /// and rename: s/bool tryEmit/void emit/ 662 bool tryEmitMemcpyInline(MachineInstr &MI); 663 664 /// Match: 665 /// (G_UMULO x, 2) -> (G_UADDO x, x) 666 /// (G_SMULO x, 2) -> (G_SADDO x, x) 667 bool matchMulOBy2(MachineInstr &MI, BuildFnTy &MatchInfo); 668 669 /// Match: 670 /// (G_*MULO x, 0) -> 0 + no carry out 671 bool matchMulOBy0(MachineInstr &MI, BuildFnTy &MatchInfo); 672 673 /// Match: 674 /// (G_*ADDO x, 0) -> x + no carry out 675 bool matchAddOBy0(MachineInstr &MI, BuildFnTy &MatchInfo); 676 677 /// Transform (fadd x, fneg(y)) -> (fsub x, y) 678 /// (fadd fneg(x), y) -> (fsub y, x) 679 /// (fsub x, fneg(y)) -> (fadd x, y) 680 /// (fmul fneg(x), fneg(y)) -> (fmul x, y) 681 /// (fdiv fneg(x), fneg(y)) -> (fdiv x, y) 682 /// (fmad fneg(x), fneg(y), z) -> (fmad x, y, z) 683 /// (fma fneg(x), fneg(y), z) -> (fma x, y, z) 684 bool matchRedundantNegOperands(MachineInstr &MI, BuildFnTy &MatchInfo); 685 686 bool canCombineFMadOrFMA(MachineInstr &MI, bool &AllowFusionGlobally, 687 bool &HasFMAD, bool &Aggressive, 688 bool CanReassociate = false); 689 690 /// Transform (fadd (fmul x, y), z) -> (fma x, y, z) 691 /// (fadd (fmul x, y), z) -> (fmad x, y, z) 692 bool matchCombineFAddFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo); 693 694 /// Transform (fadd (fpext (fmul x, y)), z) -> (fma (fpext x), (fpext y), z) 695 /// (fadd (fpext (fmul x, y)), z) -> (fmad (fpext x), (fpext y), z) 696 bool matchCombineFAddFpExtFMulToFMadOrFMA(MachineInstr &MI, 697 BuildFnTy &MatchInfo); 698 699 /// Transform (fadd (fma x, y, (fmul u, v)), z) -> (fma x, y, (fma u, v, z)) 700 /// (fadd (fmad x, y, (fmul u, v)), z) -> (fmad x, y, (fmad u, v, z)) 701 bool matchCombineFAddFMAFMulToFMadOrFMA(MachineInstr &MI, 702 BuildFnTy &MatchInfo); 703 704 // Transform (fadd (fma x, y, (fpext (fmul u, v))), z) 705 // -> (fma x, y, (fma (fpext u), (fpext v), z)) 706 // (fadd (fmad x, y, (fpext (fmul u, v))), z) 707 // -> (fmad x, y, (fmad (fpext u), (fpext v), z)) 708 bool matchCombineFAddFpExtFMulToFMadOrFMAAggressive(MachineInstr &MI, 709 BuildFnTy &MatchInfo); 710 711 /// Transform (fsub (fmul x, y), z) -> (fma x, y, -z) 712 /// (fsub (fmul x, y), z) -> (fmad x, y, -z) 713 bool matchCombineFSubFMulToFMadOrFMA(MachineInstr &MI, BuildFnTy &MatchInfo); 714 715 /// Transform (fsub (fneg (fmul, x, y)), z) -> (fma (fneg x), y, (fneg z)) 716 /// (fsub (fneg (fmul, x, y)), z) -> (fmad (fneg x), y, (fneg z)) 717 bool matchCombineFSubFNegFMulToFMadOrFMA(MachineInstr &MI, 718 BuildFnTy &MatchInfo); 719 720 /// Transform (fsub (fpext (fmul x, y)), z) 721 /// -> (fma (fpext x), (fpext y), (fneg z)) 722 /// (fsub (fpext (fmul x, y)), z) 723 /// -> (fmad (fpext x), (fpext y), (fneg z)) 724 bool matchCombineFSubFpExtFMulToFMadOrFMA(MachineInstr &MI, 725 BuildFnTy &MatchInfo); 726 727 /// Transform (fsub (fpext (fneg (fmul x, y))), z) 728 /// -> (fneg (fma (fpext x), (fpext y), z)) 729 /// (fsub (fpext (fneg (fmul x, y))), z) 730 /// -> (fneg (fmad (fpext x), (fpext y), z)) 731 bool matchCombineFSubFpExtFNegFMulToFMadOrFMA(MachineInstr &MI, 732 BuildFnTy &MatchInfo); 733 734 /// Fold boolean selects to logical operations. 735 bool matchSelectToLogical(MachineInstr &MI, BuildFnTy &MatchInfo); 736 737 bool matchCombineFMinMaxNaN(MachineInstr &MI, unsigned &Info); 738 739 /// Transform G_ADD(x, G_SUB(y, x)) to y. 740 /// Transform G_ADD(G_SUB(y, x), x) to y. 741 bool matchAddSubSameReg(MachineInstr &MI, Register &Src); 742 743 private: 744 /// Given a non-indexed load or store instruction \p MI, find an offset that 745 /// can be usefully and legally folded into it as a post-indexing operation. 746 /// 747 /// \returns true if a candidate is found. 748 bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 749 Register &Offset); 750 751 /// Given a non-indexed load or store instruction \p MI, find an offset that 752 /// can be usefully and legally folded into it as a pre-indexing operation. 753 /// 754 /// \returns true if a candidate is found. 755 bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 756 Register &Offset); 757 758 /// Helper function for matchLoadOrCombine. Searches for Registers 759 /// which may have been produced by a load instruction + some arithmetic. 760 /// 761 /// \param [in] Root - The search root. 762 /// 763 /// \returns The Registers found during the search. 764 Optional<SmallVector<Register, 8>> 765 findCandidatesForLoadOrCombine(const MachineInstr *Root) const; 766 767 /// Helper function for matchLoadOrCombine. 768 /// 769 /// Checks if every register in \p RegsToVisit is defined by a load 770 /// instruction + some arithmetic. 771 /// 772 /// \param [out] MemOffset2Idx - Maps the byte positions each load ends up 773 /// at to the index of the load. 774 /// \param [in] MemSizeInBits - The number of bits each load should produce. 775 /// 776 /// \returns On success, a 3-tuple containing lowest-index load found, the 777 /// lowest index, and the last load in the sequence. 778 Optional<std::tuple<GZExtLoad *, int64_t, GZExtLoad *>> 779 findLoadOffsetsForLoadOrCombine( 780 SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx, 781 const SmallVector<Register, 8> &RegsToVisit, 782 const unsigned MemSizeInBits); 783 784 /// Examines the G_PTR_ADD instruction \p PtrAdd and determines if performing 785 /// a re-association of its operands would break an existing legal addressing 786 /// mode that the address computation currently represents. 787 bool reassociationCanBreakAddressingModePattern(MachineInstr &PtrAdd); 788 }; 789 } // namespace llvm 790 791 #endif 792