diff options
Diffstat (limited to 'contrib/llvm-project/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h')
| -rw-r--r-- | contrib/llvm-project/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h | 268 |
1 files changed, 263 insertions, 5 deletions
diff --git a/contrib/llvm-project/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h b/contrib/llvm-project/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h index c317b7ed4c54..8570f5ca5dd5 100644 --- a/contrib/llvm-project/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h +++ b/contrib/llvm-project/llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h @@ -17,6 +17,8 @@ #ifndef LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H #define LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H +#include "llvm/ADT/APFloat.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/CodeGen/LowLevelType.h" #include "llvm/CodeGen/Register.h" #include "llvm/Support/Alignment.h" @@ -25,12 +27,15 @@ namespace llvm { class GISelChangeObserver; class MachineIRBuilder; +class MachineInstrBuilder; class MachineRegisterInfo; class MachineInstr; class MachineOperand; class GISelKnownBits; class MachineDominatorTree; class LegalizerInfo; +struct LegalityQuery; +class TargetLowering; struct PreferredTuple { LLT Ty; // The result type of the extend. @@ -50,6 +55,37 @@ struct PtrAddChain { Register Base; }; +struct RegisterImmPair { + Register Reg; + int64_t Imm; +}; + +struct ShiftOfShiftedLogic { + MachineInstr *Logic; + MachineInstr *Shift2; + Register LogicNonShiftReg; + uint64_t ValSum; +}; + +using OperandBuildSteps = + SmallVector<std::function<void(MachineInstrBuilder &)>, 4>; +struct InstructionBuildSteps { + unsigned Opcode = 0; /// The opcode for the produced instruction. + OperandBuildSteps OperandFns; /// Operands to be added to the instruction. + InstructionBuildSteps() = default; + InstructionBuildSteps(unsigned Opcode, const OperandBuildSteps &OperandFns) + : Opcode(Opcode), OperandFns(OperandFns) {} +}; + +struct InstructionStepsMatchInfo { + /// Describes instructions to be built during a combine. + SmallVector<InstructionBuildSteps, 2> InstrsToBuild; + InstructionStepsMatchInfo() = default; + InstructionStepsMatchInfo( + std::initializer_list<InstructionBuildSteps> InstrsToBuild) + : InstrsToBuild(InstrsToBuild) {} +}; + class CombinerHelper { protected: MachineIRBuilder &Builder; @@ -69,6 +105,12 @@ public: return KB; } + const TargetLowering &getTargetLowering() const; + + /// \return true if the combine is running prior to legalization, or if \p + /// Query is legal on the target. + bool isLegalOrBeforeLegalizer(const LegalityQuery &Query) const; + /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const; @@ -107,12 +149,17 @@ public: bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); void applyCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); - bool matchSextAlreadyExtended(MachineInstr &MI); - bool applySextAlreadyExtended(MachineInstr &MI); + bool matchSextTruncSextLoad(MachineInstr &MI); + bool applySextTruncSextLoad(MachineInstr &MI); - bool matchElideBrByInvertingCond(MachineInstr &MI); - void applyElideBrByInvertingCond(MachineInstr &MI); - bool tryElideBrByInvertingCond(MachineInstr &MI); + /// Match sext_inreg(load p), imm -> sextload p + bool matchSextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo); + bool applySextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo); + + /// If a brcond's true block is not the fallthrough, make it so by inverting + /// the condition and swapping operands. + bool matchOptBrCondByInvertingCond(MachineInstr &MI); + void applyOptBrCondByInvertingCond(MachineInstr &MI); /// If \p MI is G_CONCAT_VECTORS, try to combine it. /// Returns true if MI changed. @@ -189,10 +236,28 @@ public: bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo); bool applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo); + /// Fold (shift (shift base, x), y) -> (shift base (x+y)) + bool matchShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo); + bool applyShiftImmedChain(MachineInstr &MI, RegisterImmPair &MatchInfo); + + /// If we have a shift-by-constant of a bitwise logic op that itself has a + /// shift-by-constant operand with identical opcode, we may be able to convert + /// that into 2 independent shifts followed by the logic op. + bool matchShiftOfShiftedLogic(MachineInstr &MI, + ShiftOfShiftedLogic &MatchInfo); + bool applyShiftOfShiftedLogic(MachineInstr &MI, + ShiftOfShiftedLogic &MatchInfo); + /// Transform a multiply by a power-of-2 value to a left shift. bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); bool applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); + // Transform a G_SHL with an extended source into a narrower shift if + // possible. + bool matchCombineShlOfExtend(MachineInstr &MI, RegisterImmPair &MatchData); + bool applyCombineShlOfExtend(MachineInstr &MI, + const RegisterImmPair &MatchData); + /// Reduce a shift by a constant to an unmerge and a shift on a half sized /// type. This will not produce a shift smaller than \p TargetShiftSize. bool matchCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftSize, @@ -200,6 +265,86 @@ public: bool applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal); bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount); + /// Transform <ty,...> G_UNMERGE(G_MERGE ty X, Y, Z) -> ty X, Y, Z. + bool + matchCombineUnmergeMergeToPlainValues(MachineInstr &MI, + SmallVectorImpl<Register> &Operands); + bool + applyCombineUnmergeMergeToPlainValues(MachineInstr &MI, + SmallVectorImpl<Register> &Operands); + + /// Transform G_UNMERGE Constant -> Constant1, Constant2, ... + bool matchCombineUnmergeConstant(MachineInstr &MI, + SmallVectorImpl<APInt> &Csts); + bool applyCombineUnmergeConstant(MachineInstr &MI, + SmallVectorImpl<APInt> &Csts); + + /// Transform X, Y<dead> = G_UNMERGE Z -> X = G_TRUNC Z. + bool matchCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI); + bool applyCombineUnmergeWithDeadLanesToTrunc(MachineInstr &MI); + + /// Transform X, Y = G_UNMERGE(G_ZEXT(Z)) -> X = G_ZEXT(Z); Y = G_CONSTANT 0 + bool matchCombineUnmergeZExtToZExt(MachineInstr &MI); + bool applyCombineUnmergeZExtToZExt(MachineInstr &MI); + + /// Transform fp_instr(cst) to constant result of the fp operation. + bool matchCombineConstantFoldFpUnary(MachineInstr &MI, + Optional<APFloat> &Cst); + bool applyCombineConstantFoldFpUnary(MachineInstr &MI, + Optional<APFloat> &Cst); + + /// Transform IntToPtr(PtrToInt(x)) to x if cast is in the same address space. + bool matchCombineI2PToP2I(MachineInstr &MI, Register &Reg); + bool applyCombineI2PToP2I(MachineInstr &MI, Register &Reg); + + /// Transform PtrToInt(IntToPtr(x)) to x. + bool matchCombineP2IToI2P(MachineInstr &MI, Register &Reg); + bool applyCombineP2IToI2P(MachineInstr &MI, Register &Reg); + + /// Transform G_ADD (G_PTRTOINT x), y -> G_PTRTOINT (G_PTR_ADD x, y) + /// Transform G_ADD y, (G_PTRTOINT x) -> G_PTRTOINT (G_PTR_ADD x, y) + bool matchCombineAddP2IToPtrAdd(MachineInstr &MI, + std::pair<Register, bool> &PtrRegAndCommute); + bool applyCombineAddP2IToPtrAdd(MachineInstr &MI, + std::pair<Register, bool> &PtrRegAndCommute); + + // Transform G_PTR_ADD (G_PTRTOINT C1), C2 -> C1 + C2 + bool matchCombineConstPtrAddToI2P(MachineInstr &MI, int64_t &NewCst); + bool applyCombineConstPtrAddToI2P(MachineInstr &MI, int64_t &NewCst); + + /// Transform anyext(trunc(x)) to x. + bool matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg); + bool applyCombineAnyExtTrunc(MachineInstr &MI, Register &Reg); + + /// Transform [asz]ext([asz]ext(x)) to [asz]ext x. + bool matchCombineExtOfExt(MachineInstr &MI, + std::tuple<Register, unsigned> &MatchInfo); + bool applyCombineExtOfExt(MachineInstr &MI, + std::tuple<Register, unsigned> &MatchInfo); + + /// Transform fneg(fneg(x)) to x. + bool matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg); + + /// Match fabs(fabs(x)) to fabs(x). + bool matchCombineFAbsOfFAbs(MachineInstr &MI, Register &Src); + bool applyCombineFAbsOfFAbs(MachineInstr &MI, Register &Src); + + /// Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x). + bool matchCombineTruncOfExt(MachineInstr &MI, + std::pair<Register, unsigned> &MatchInfo); + bool applyCombineTruncOfExt(MachineInstr &MI, + std::pair<Register, unsigned> &MatchInfo); + + /// Transform trunc (shl x, K) to shl (trunc x), + /// K => K < VT.getScalarSizeInBits(). + bool matchCombineTruncOfShl(MachineInstr &MI, + std::pair<Register, Register> &MatchInfo); + bool applyCombineTruncOfShl(MachineInstr &MI, + std::pair<Register, Register> &MatchInfo); + + /// Transform G_MUL(x, -1) to G_SUB(0, x) + bool applyCombineMulByNegativeOne(MachineInstr &MI); + /// Return true if any explicit use operand on \p MI is defined by a /// G_IMPLICIT_DEF. bool matchAnyExplicitUseIsUndef(MachineInstr &MI); @@ -214,6 +359,13 @@ public: /// Return true if a G_STORE instruction \p MI is storing an undef value. bool matchUndefStore(MachineInstr &MI); + /// Return true if a G_SELECT instruction \p MI has an undef comparison. + bool matchUndefSelectCmp(MachineInstr &MI); + + /// Return true if a G_SELECT instruction \p MI has a constant comparison. If + /// true, \p OpIdx will store the operand index of the known selected value. + bool matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx); + /// Replace an instruction with a G_FCONSTANT with value \p C. bool replaceInstWithFConstant(MachineInstr &MI, double C); @@ -226,6 +378,9 @@ public: /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand. bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx); + /// Delete \p MI and replace all of its uses with \p Replacement. + bool replaceSingleDefInstWithReg(MachineInstr &MI, Register Replacement); + /// Return true if \p MOP1 and \p MOP2 are register operands are defined by /// equivalent instructions. bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2); @@ -243,6 +398,12 @@ public: /// Check if operand \p OpIdx is zero. bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx); + /// Check if operand \p OpIdx is undef. + bool matchOperandIsUndef(MachineInstr &MI, unsigned OpIdx); + + /// Check if operand \p OpIdx is known to be a power of 2. + bool matchOperandIsKnownToBeAPowerOfTwo(MachineInstr &MI, unsigned OpIdx); + /// Erase \p MI bool eraseInst(MachineInstr &MI); @@ -252,6 +413,79 @@ public: bool applySimplifyAddToSub(MachineInstr &MI, std::tuple<Register, Register> &MatchInfo); + /// Match (logic_op (op x...), (op y...)) -> (op (logic_op x, y)) + bool + matchHoistLogicOpWithSameOpcodeHands(MachineInstr &MI, + InstructionStepsMatchInfo &MatchInfo); + + /// Replace \p MI with a series of instructions described in \p MatchInfo. + bool applyBuildInstructionSteps(MachineInstr &MI, + InstructionStepsMatchInfo &MatchInfo); + + /// Match ashr (shl x, C), C -> sext_inreg (C) + bool matchAshrShlToSextInreg(MachineInstr &MI, + std::tuple<Register, int64_t> &MatchInfo); + bool applyAshShlToSextInreg(MachineInstr &MI, + std::tuple<Register, int64_t> &MatchInfo); + /// \return true if \p MI is a G_AND instruction whose operands are x and y + /// where x & y == x or x & y == y. (E.g., one of operands is all-ones value.) + /// + /// \param [in] MI - The G_AND instruction. + /// \param [out] Replacement - A register the G_AND should be replaced with on + /// success. + bool matchRedundantAnd(MachineInstr &MI, Register &Replacement); + + /// \return true if \p MI is a G_OR instruction whose operands are x and y + /// where x | y == x or x | y == y. (E.g., one of operands is all-zeros + /// value.) + /// + /// \param [in] MI - The G_OR instruction. + /// \param [out] Replacement - A register the G_OR should be replaced with on + /// success. + bool matchRedundantOr(MachineInstr &MI, Register &Replacement); + + /// \return true if \p MI is a G_SEXT_INREG that can be erased. + bool matchRedundantSExtInReg(MachineInstr &MI); + + /// Combine inverting a result of a compare into the opposite cond code. + bool matchNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); + bool applyNotCmp(MachineInstr &MI, SmallVectorImpl<Register> &RegsToNegate); + + /// Fold (xor (and x, y), y) -> (and (not x), y) + ///{ + bool matchXorOfAndWithSameReg(MachineInstr &MI, + std::pair<Register, Register> &MatchInfo); + bool applyXorOfAndWithSameReg(MachineInstr &MI, + std::pair<Register, Register> &MatchInfo); + ///} + + /// Combine G_PTR_ADD with nullptr to G_INTTOPTR + bool matchPtrAddZero(MachineInstr &MI); + bool applyPtrAddZero(MachineInstr &MI); + + /// Combine G_UREM x, (known power of 2) to an add and bitmasking. + bool applySimplifyURemByPow2(MachineInstr &MI); + + bool matchCombineInsertVecElts(MachineInstr &MI, + SmallVectorImpl<Register> &MatchInfo); + + bool applyCombineInsertVecElts(MachineInstr &MI, + SmallVectorImpl<Register> &MatchInfo); + + /// Match expression trees of the form + /// + /// \code + /// sN *a = ... + /// sM val = a[0] | (a[1] << N) | (a[2] << 2N) | (a[3] << 3N) ... + /// \endcode + /// + /// And check if the tree can be replaced with a M-bit load + possibly a + /// bswap. + bool matchLoadOrCombine(MachineInstr &MI, + std::function<void(MachineIRBuilder &)> &MatchInfo); + bool applyLoadOrCombine(MachineInstr &MI, + std::function<void(MachineIRBuilder &)> &MatchInfo); + /// Try to transform \p MI by using all of the above /// combine functions. Returns true if changed. bool tryCombine(MachineInstr &MI); @@ -280,6 +514,30 @@ private: /// \returns true if a candidate is found. bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, Register &Offset); + + /// Helper function for matchLoadOrCombine. Searches for Registers + /// which may have been produced by a load instruction + some arithmetic. + /// + /// \param [in] Root - The search root. + /// + /// \returns The Registers found during the search. + Optional<SmallVector<Register, 8>> + findCandidatesForLoadOrCombine(const MachineInstr *Root) const; + + /// Helper function for matchLoadOrCombine. + /// + /// Checks if every register in \p RegsToVisit is defined by a load + /// instruction + some arithmetic. + /// + /// \param [out] MemOffset2Idx - Maps the byte positions each load ends up + /// at to the index of the load. + /// \param [in] MemSizeInBits - The number of bits each load should produce. + /// + /// \returns The lowest-index load found and the lowest index on success. + Optional<std::pair<MachineInstr *, int64_t>> findLoadOffsetsForLoadOrCombine( + SmallDenseMap<int64_t, int64_t, 8> &MemOffset2Idx, + const SmallVector<Register, 8> &RegsToVisit, + const unsigned MemSizeInBits); }; } // namespace llvm |