diff options
Diffstat (limited to 'lib/Transforms/InstCombine/InstCombineInternal.h')
| -rw-r--r-- | lib/Transforms/InstCombine/InstCombineInternal.h | 165 |
1 files changed, 129 insertions, 36 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineInternal.h b/lib/Transforms/InstCombine/InstCombineInternal.h index f1f66d86cb73..58ef3d41415c 100644 --- a/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/lib/Transforms/InstCombine/InstCombineInternal.h @@ -20,6 +20,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetFolder.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/BasicBlock.h" @@ -40,7 +41,6 @@ #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" -#include "llvm/Transforms/Utils/Local.h" #include <cassert> #include <cstdint> @@ -122,17 +122,17 @@ static inline Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) { return V; } -/// \brief Add one to a Constant +/// Add one to a Constant static inline Constant *AddOne(Constant *C) { return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); } -/// \brief Subtract one from a Constant +/// Subtract one from a Constant static inline Constant *SubOne(Constant *C) { return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1)); } -/// \brief Return true if the specified value is free to invert (apply ~ to). +/// Return true if the specified value is free to invert (apply ~ to). /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses /// is true, work under the assumption that the caller intends to remove all /// uses of V and only keep uses of ~V. @@ -178,7 +178,7 @@ static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) { return false; } -/// \brief Specific patterns of overflow check idioms that we match. +/// Specific patterns of overflow check idioms that we match. enum OverflowCheckFlavor { OCF_UNSIGNED_ADD, OCF_SIGNED_ADD, @@ -190,7 +190,7 @@ enum OverflowCheckFlavor { OCF_INVALID }; -/// \brief Returns the OverflowCheckFlavor corresponding to a overflow_with_op +/// Returns the OverflowCheckFlavor corresponding to a overflow_with_op /// intrinsic. static inline OverflowCheckFlavor IntrinsicIDToOverflowCheckFlavor(unsigned ID) { @@ -212,7 +212,62 @@ IntrinsicIDToOverflowCheckFlavor(unsigned ID) { } } -/// \brief The core instruction combiner logic. +/// Some binary operators require special handling to avoid poison and undefined +/// behavior. If a constant vector has undef elements, replace those undefs with +/// identity constants if possible because those are always safe to execute. +/// If no identity constant exists, replace undef with some other safe constant. +static inline Constant *getSafeVectorConstantForBinop( + BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant) { + assert(In->getType()->isVectorTy() && "Not expecting scalars here"); + + Type *EltTy = In->getType()->getVectorElementType(); + auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant); + if (!SafeC) { + // TODO: Should this be available as a constant utility function? It is + // similar to getBinOpAbsorber(). + if (IsRHSConstant) { + switch (Opcode) { + case Instruction::SRem: // X % 1 = 0 + case Instruction::URem: // X %u 1 = 0 + SafeC = ConstantInt::get(EltTy, 1); + break; + case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe) + SafeC = ConstantFP::get(EltTy, 1.0); + break; + default: + llvm_unreachable("Only rem opcodes have no identity constant for RHS"); + } + } else { + switch (Opcode) { + case Instruction::Shl: // 0 << X = 0 + case Instruction::LShr: // 0 >>u X = 0 + case Instruction::AShr: // 0 >> X = 0 + case Instruction::SDiv: // 0 / X = 0 + case Instruction::UDiv: // 0 /u X = 0 + case Instruction::SRem: // 0 % X = 0 + case Instruction::URem: // 0 %u X = 0 + case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe) + case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe) + case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe) + case Instruction::FRem: // 0.0 % X = 0 + SafeC = Constant::getNullValue(EltTy); + break; + default: + llvm_unreachable("Expected to find identity constant for opcode"); + } + } + } + assert(SafeC && "Must have safe constant for binop"); + unsigned NumElts = In->getType()->getVectorNumElements(); + SmallVector<Constant *, 16> Out(NumElts); + for (unsigned i = 0; i != NumElts; ++i) { + Constant *C = In->getAggregateElement(i); + Out[i] = isa<UndefValue>(C) ? SafeC : C; + } + return ConstantVector::get(Out); +} + +/// The core instruction combiner logic. /// /// This class provides both the logic to recursively visit instructions and /// combine them. @@ -220,10 +275,10 @@ class LLVM_LIBRARY_VISIBILITY InstCombiner : public InstVisitor<InstCombiner, Instruction *> { // FIXME: These members shouldn't be public. public: - /// \brief A worklist of the instructions that need to be simplified. + /// A worklist of the instructions that need to be simplified. InstCombineWorklist &Worklist; - /// \brief An IRBuilder that automatically inserts new instructions into the + /// An IRBuilder that automatically inserts new instructions into the /// worklist. using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>; BuilderTy &Builder; @@ -261,7 +316,7 @@ public: ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), LI(LI) {} - /// \brief Run the combiner over the entire worklist until it is empty. + /// Run the combiner over the entire worklist until it is empty. /// /// \returns true if the IR is changed. bool run(); @@ -289,8 +344,6 @@ public: Instruction *visitSub(BinaryOperator &I); Instruction *visitFSub(BinaryOperator &I); Instruction *visitMul(BinaryOperator &I); - Value *foldFMulConst(Instruction *FMulOrDiv, Constant *C, - Instruction *InsertBefore); Instruction *visitFMul(BinaryOperator &I); Instruction *visitURem(BinaryOperator &I); Instruction *visitSRem(BinaryOperator &I); @@ -378,7 +431,6 @@ private: bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const; bool shouldChangeType(Type *From, Type *To) const; Value *dyn_castNegVal(Value *V) const; - Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const; Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset, SmallVectorImpl<Value *> &NewIndices); @@ -393,7 +445,7 @@ private: /// if it cannot already be eliminated by some other transformation. bool shouldOptimizeCast(CastInst *CI); - /// \brief Try to optimize a sequence of instructions checking if an operation + /// Try to optimize a sequence of instructions checking if an operation /// on LHS and RHS overflows. /// /// If this overflow check is done via one of the overflow check intrinsics, @@ -445,11 +497,22 @@ private: } bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS, - const Instruction &CxtI) const; + const Instruction &CxtI) const { + return computeOverflowForSignedSub(LHS, RHS, &CxtI) == + OverflowResult::NeverOverflows; + } + bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS, - const Instruction &CxtI) const; + const Instruction &CxtI) const { + return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) == + OverflowResult::NeverOverflows; + } + bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS, - const Instruction &CxtI) const; + const Instruction &CxtI) const { + return computeOverflowForSignedMul(LHS, RHS, &CxtI) == + OverflowResult::NeverOverflows; + } bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS, const Instruction &CxtI) const { @@ -462,6 +525,7 @@ private: Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask); Instruction *foldCastedBitwiseLogic(BinaryOperator &I); Instruction *narrowBinOp(TruncInst &Trunc); + Instruction *narrowMaskedBinOp(BinaryOperator &And); Instruction *narrowRotate(TruncInst &Trunc); Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN); @@ -490,7 +554,7 @@ private: Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS, bool JoinedByAnd, Instruction &CxtI); public: - /// \brief Inserts an instruction \p New before instruction \p Old + /// Inserts an instruction \p New before instruction \p Old /// /// Also adds the new instruction to the worklist and returns \p New so that /// it is suitable for use as the return from the visitation patterns. @@ -503,13 +567,13 @@ public: return New; } - /// \brief Same as InsertNewInstBefore, but also sets the debug loc. + /// Same as InsertNewInstBefore, but also sets the debug loc. Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) { New->setDebugLoc(Old.getDebugLoc()); return InsertNewInstBefore(New, Old); } - /// \brief A combiner-aware RAUW-like routine. + /// A combiner-aware RAUW-like routine. /// /// This method is to be used when an instruction is found to be dead, /// replaceable with another preexisting expression. Here we add all uses of @@ -527,8 +591,8 @@ public: if (&I == V) V = UndefValue::get(I.getType()); - DEBUG(dbgs() << "IC: Replacing " << I << "\n" - << " with " << *V << '\n'); + LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n" + << " with " << *V << '\n'); I.replaceAllUsesWith(V); return &I; @@ -544,13 +608,13 @@ public: return InsertValueInst::Create(Struct, Result, 0); } - /// \brief Combiner aware instruction erasure. + /// Combiner aware instruction erasure. /// /// When dealing with an instruction that has side effects or produces a void /// value, we can't rely on DCE to delete the instruction. Instead, visit /// methods should return the value returned by this function. Instruction *eraseInstFromFunction(Instruction &I) { - DEBUG(dbgs() << "IC: ERASE " << I << '\n'); + LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n'); assert(I.use_empty() && "Cannot erase instruction that is used!"); salvageDebugInfo(I); @@ -599,6 +663,12 @@ public: return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT); } + OverflowResult computeOverflowForSignedMul(const Value *LHS, + const Value *RHS, + const Instruction *CxtI) const { + return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT); + } + OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const { @@ -611,15 +681,26 @@ public: return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT); } + OverflowResult computeOverflowForUnsignedSub(const Value *LHS, + const Value *RHS, + const Instruction *CxtI) const { + return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT); + } + + OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, + const Instruction *CxtI) const { + return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT); + } + /// Maximum size of array considered when transforming. uint64_t MaxArraySizeForCombine; private: - /// \brief Performs a few simplifications for operators which are associative + /// Performs a few simplifications for operators which are associative /// or commutative. bool SimplifyAssociativeOrCommutative(BinaryOperator &I); - /// \brief Tries to simplify binary operations which some other binary + /// Tries to simplify binary operations which some other binary /// operation distributes over. /// /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)" @@ -628,6 +709,13 @@ private: /// value, or null if it didn't simplify. Value *SimplifyUsingDistributiveLaws(BinaryOperator &I); + /// Tries to simplify add operations using the definition of remainder. + /// + /// The definition of remainder is X % C = X - (X / C ) * C. The add + /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to + /// X % (C0 * C1) + Value *SimplifyAddWithRemainder(BinaryOperator &I); + // Binary Op helper for select operations where the expression can be // efficiently reorganized. Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS, @@ -647,7 +735,7 @@ private: ConstantInt *&Less, ConstantInt *&Equal, ConstantInt *&Greater); - /// \brief Attempts to replace V with a simpler value based on the demanded + /// Attempts to replace V with a simpler value based on the demanded /// bits. Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known, unsigned Depth, Instruction *CxtI); @@ -669,15 +757,19 @@ private: Instruction *Shr, const APInt &ShrOp1, Instruction *Shl, const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known); - /// \brief Tries to simplify operands to an integer instruction based on its + /// Tries to simplify operands to an integer instruction based on its /// demanded bits. bool SimplifyDemandedInstructionBits(Instruction &Inst); + Value *simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II, + APInt DemandedElts, + int DmaskIdx = -1); + Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth = 0); - Value *SimplifyVectorOp(BinaryOperator &Inst); - + /// Canonicalize the position of binops relative to shufflevector. + Instruction *foldShuffledBinop(BinaryOperator &Inst); /// Given a binary operator, cast instruction, or select which has a PHI node /// as operand #0, see if we can fold the instruction into the PHI (which is @@ -691,11 +783,11 @@ private: Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI); /// This is a convenience wrapper function for the above two functions. - Instruction *foldOpWithConstantIntoOperand(BinaryOperator &I); + Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I); Instruction *foldAddWithConstant(BinaryOperator &Add); - /// \brief Try to rotate an operation below a PHI node, using PHI nodes for + /// Try to rotate an operation below a PHI node, using PHI nodes for /// its operands. Instruction *FoldPHIArgOpIntoPHI(PHINode &PN); Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN); @@ -735,6 +827,8 @@ private: Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select, ConstantInt *C); + Instruction *foldICmpBitCastConstant(ICmpInst &Cmp, BitCastInst *Bitcast, + const APInt &C); Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc, const APInt &C); Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And, @@ -789,13 +883,12 @@ private: Instruction *MatchBSwap(BinaryOperator &I); bool SimplifyStoreAtEndOfBlock(StoreInst &SI); - Instruction *SimplifyElementUnorderedAtomicMemCpy(AtomicMemCpyInst *AMI); - Instruction *SimplifyMemTransfer(MemIntrinsic *MI); - Instruction *SimplifyMemSet(MemSetInst *MI); + Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI); + Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI); Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned); - /// \brief Returns a value X such that Val = X * Scale, or null if none. + /// Returns a value X such that Val = X * Scale, or null if none. /// /// If the multiplication is known not to overflow then NoSignedWrap is set. Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap); |