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