diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/InstructionSimplify.cpp')
| -rw-r--r-- | contrib/llvm/lib/Analysis/InstructionSimplify.cpp | 497 |
1 files changed, 362 insertions, 135 deletions
diff --git a/contrib/llvm/lib/Analysis/InstructionSimplify.cpp b/contrib/llvm/lib/Analysis/InstructionSimplify.cpp index 3fbbd7c..ec56d88 100644 --- a/contrib/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/contrib/llvm/lib/Analysis/InstructionSimplify.cpp @@ -45,13 +45,13 @@ STATISTIC(NumReassoc, "Number of reassociations"); namespace { struct Query { - const DataLayout *DL; + const DataLayout &DL; const TargetLibraryInfo *TLI; const DominatorTree *DT; AssumptionCache *AC; const Instruction *CxtI; - Query(const DataLayout *DL, const TargetLibraryInfo *tli, + Query(const DataLayout &DL, const TargetLibraryInfo *tli, const DominatorTree *dt, AssumptionCache *ac = nullptr, const Instruction *cxti = nullptr) : DL(DL), TLI(tli), DT(dt), AC(ac), CxtI(cxti) {} @@ -61,6 +61,8 @@ struct Query { static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned); static Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &, unsigned); +static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &, + const Query &, unsigned); static Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &, unsigned); static Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned); @@ -467,8 +469,7 @@ static Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, // Evaluate the BinOp on the incoming phi values. Value *CommonValue = nullptr; - for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { - Value *Incoming = PI->getIncomingValue(i); + for (Value *Incoming : PI->incoming_values()) { // If the incoming value is the phi node itself, it can safely be skipped. if (Incoming == PI) continue; Value *V = PI == LHS ? @@ -508,8 +509,7 @@ static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, // Evaluate the BinOp on the incoming phi values. Value *CommonValue = nullptr; - for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { - Value *Incoming = PI->getIncomingValue(i); + for (Value *Incoming : PI->incoming_values()) { // If the incoming value is the phi node itself, it can safely be skipped. if (Incoming == PI) continue; Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse); @@ -582,7 +582,7 @@ static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, } Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, - const DataLayout *DL, const TargetLibraryInfo *TLI, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), @@ -599,17 +599,11 @@ Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, /// This is very similar to GetPointerBaseWithConstantOffset except it doesn't /// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc. /// folding. -static Constant *stripAndComputeConstantOffsets(const DataLayout *DL, - Value *&V, +static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V, bool AllowNonInbounds = false) { assert(V->getType()->getScalarType()->isPointerTy()); - // Without DataLayout, just be conservative for now. Theoretically, more could - // be done in this case. - if (!DL) - return ConstantInt::get(IntegerType::get(V->getContext(), 64), 0); - - Type *IntPtrTy = DL->getIntPtrType(V->getType())->getScalarType(); + Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType(); APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); // Even though we don't look through PHI nodes, we could be called on an @@ -619,7 +613,7 @@ static Constant *stripAndComputeConstantOffsets(const DataLayout *DL, do { if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { if ((!AllowNonInbounds && !GEP->isInBounds()) || - !GEP->accumulateConstantOffset(*DL, Offset)) + !GEP->accumulateConstantOffset(DL, Offset)) break; V = GEP->getPointerOperand(); } else if (Operator::getOpcode(V) == Instruction::BitCast) { @@ -644,8 +638,8 @@ static Constant *stripAndComputeConstantOffsets(const DataLayout *DL, /// \brief Compute the constant difference between two pointer values. /// If the difference is not a constant, returns zero. -static Constant *computePointerDifference(const DataLayout *DL, - Value *LHS, Value *RHS) { +static Constant *computePointerDifference(const DataLayout &DL, Value *LHS, + Value *RHS) { Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); @@ -781,7 +775,7 @@ static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, } Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, - const DataLayout *DL, const TargetLibraryInfo *TLI, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), @@ -960,7 +954,7 @@ static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q, } Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -969,7 +963,7 @@ Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, } Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -978,7 +972,7 @@ Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, } Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -986,7 +980,7 @@ Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF, RecursionLimit); } -Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1090,7 +1084,7 @@ static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q, return nullptr; } -Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1108,7 +1102,7 @@ static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q, return nullptr; } -Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1116,8 +1110,8 @@ Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout *DL, RecursionLimit); } -static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const Query &Q, - unsigned) { +static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const Query &Q, unsigned) { // undef / X -> undef (the undef could be a snan). if (match(Op0, m_Undef())) return Op0; @@ -1126,14 +1120,21 @@ static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const Query &Q, if (match(Op1, m_Undef())) return Op1; + // 0 / X -> 0 + // Requires that NaNs are off (X could be zero) and signed zeroes are + // ignored (X could be positive or negative, so the output sign is unknown). + if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) + return Op0; + return nullptr; } -Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { - return ::SimplifyFDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), + return ::SimplifyFDivInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); } @@ -1208,7 +1209,7 @@ static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q, return nullptr; } -Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1226,7 +1227,7 @@ static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q, return nullptr; } -Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1234,8 +1235,8 @@ Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout *DL, RecursionLimit); } -static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const Query &, - unsigned) { +static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const Query &, unsigned) { // undef % X -> undef (the undef could be a snan). if (match(Op0, m_Undef())) return Op0; @@ -1244,14 +1245,21 @@ static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const Query &, if (match(Op1, m_Undef())) return Op1; + // 0 % X -> 0 + // Requires that NaNs are off (X could be zero) and signed zeroes are + // ignored (X could be positive or negative, so the output sign is unknown). + if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) + return Op0; + return nullptr; } -Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { - return ::SimplifyFRemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI), + return ::SimplifyFRemInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); } @@ -1371,7 +1379,7 @@ static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, } Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, - const DataLayout *DL, const TargetLibraryInfo *TLI, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI), @@ -1395,7 +1403,7 @@ static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, } Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1429,7 +1437,7 @@ static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, } Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1580,9 +1588,11 @@ static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, // A & (-A) = A if A is a power of two or zero. if (match(Op0, m_Neg(m_Specific(Op1))) || match(Op1, m_Neg(m_Specific(Op0)))) { - if (isKnownToBeAPowerOfTwo(Op0, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT)) + if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, + Q.DT)) return Op0; - if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, Q.AC, Q.CxtI, Q.DT)) + if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI, + Q.DT)) return Op1; } @@ -1627,7 +1637,7 @@ static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, return nullptr; } -Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1815,7 +1825,7 @@ static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q, return nullptr; } -Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1872,7 +1882,7 @@ static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q, return nullptr; } -Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout *DL, +Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -1932,10 +1942,10 @@ static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, // If the C and C++ standards are ever made sufficiently restrictive in this // area, it may be possible to update LLVM's semantics accordingly and reinstate // this optimization. -static Constant *computePointerICmp(const DataLayout *DL, +static Constant *computePointerICmp(const DataLayout &DL, const TargetLibraryInfo *TLI, - CmpInst::Predicate Pred, - Value *LHS, Value *RHS) { + CmpInst::Predicate Pred, Value *LHS, + Value *RHS) { // First, skip past any trivial no-ops. LHS = LHS->stripPointerCasts(); RHS = RHS->stripPointerCasts(); @@ -2353,8 +2363,8 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input // if the integer type is the same size as the pointer type. - if (MaxRecurse && Q.DL && isa<PtrToIntInst>(LI) && - Q.DL->getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) { + if (MaxRecurse && isa<PtrToIntInst>(LI) && + Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) { if (Constant *RHSC = dyn_cast<Constant>(RHS)) { // Transfer the cast to the constant. if (Value *V = SimplifyICmpInst(Pred, SrcOp, @@ -2966,10 +2976,12 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, // what constant folding can make out of it. Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType()); SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); - Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS); + Constant *NewLHS = ConstantExpr::getGetElementPtr( + GLHS->getSourceElementType(), Null, IndicesLHS); SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end()); - Constant *NewRHS = ConstantExpr::getGetElementPtr(Null, IndicesRHS); + Constant *NewRHS = ConstantExpr::getGetElementPtr( + GLHS->getSourceElementType(), Null, IndicesRHS); return ConstantExpr::getICmp(Pred, NewLHS, NewRHS); } } @@ -3008,7 +3020,7 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, Instruction *CxtI) { @@ -3038,8 +3050,13 @@ static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, if (Pred == FCmpInst::FCMP_TRUE) return ConstantInt::get(GetCompareTy(LHS), 1); - if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef - return UndefValue::get(GetCompareTy(LHS)); + // fcmp pred x, undef and fcmp pred undef, x + // fold to true if unordered, false if ordered + if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) { + // Choosing NaN for the undef will always make unordered comparison succeed + // and ordered comparison fail. + return ConstantInt::get(GetCompareTy(LHS), CmpInst::isUnordered(Pred)); + } // fcmp x,x -> true/false. Not all compares are foldable. if (LHS == RHS) { @@ -3050,44 +3067,57 @@ static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, } // Handle fcmp with constant RHS - if (Constant *RHSC = dyn_cast<Constant>(RHS)) { + if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { // If the constant is a nan, see if we can fold the comparison based on it. - if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { - if (CFP->getValueAPF().isNaN()) { - if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" + if (CFP->getValueAPF().isNaN()) { + if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" + return ConstantInt::getFalse(CFP->getContext()); + assert(FCmpInst::isUnordered(Pred) && + "Comparison must be either ordered or unordered!"); + // True if unordered. + return ConstantInt::getTrue(CFP->getContext()); + } + // Check whether the constant is an infinity. + if (CFP->getValueAPF().isInfinity()) { + if (CFP->getValueAPF().isNegative()) { + switch (Pred) { + case FCmpInst::FCMP_OLT: + // No value is ordered and less than negative infinity. return ConstantInt::getFalse(CFP->getContext()); - assert(FCmpInst::isUnordered(Pred) && - "Comparison must be either ordered or unordered!"); - // True if unordered. - return ConstantInt::getTrue(CFP->getContext()); - } - // Check whether the constant is an infinity. - if (CFP->getValueAPF().isInfinity()) { - if (CFP->getValueAPF().isNegative()) { - switch (Pred) { - case FCmpInst::FCMP_OLT: - // No value is ordered and less than negative infinity. - return ConstantInt::getFalse(CFP->getContext()); - case FCmpInst::FCMP_UGE: - // All values are unordered with or at least negative infinity. - return ConstantInt::getTrue(CFP->getContext()); - default: - break; - } - } else { - switch (Pred) { - case FCmpInst::FCMP_OGT: - // No value is ordered and greater than infinity. - return ConstantInt::getFalse(CFP->getContext()); - case FCmpInst::FCMP_ULE: - // All values are unordered with and at most infinity. - return ConstantInt::getTrue(CFP->getContext()); - default: - break; - } + case FCmpInst::FCMP_UGE: + // All values are unordered with or at least negative infinity. + return ConstantInt::getTrue(CFP->getContext()); + default: + break; + } + } else { + switch (Pred) { + case FCmpInst::FCMP_OGT: + // No value is ordered and greater than infinity. + return ConstantInt::getFalse(CFP->getContext()); + case FCmpInst::FCMP_ULE: + // All values are unordered with and at most infinity. + return ConstantInt::getTrue(CFP->getContext()); + default: + break; } } } + if (CFP->getValueAPF().isZero()) { + switch (Pred) { + case FCmpInst::FCMP_UGE: + if (CannotBeOrderedLessThanZero(LHS)) + return ConstantInt::getTrue(CFP->getContext()); + break; + case FCmpInst::FCMP_OLT: + // X < 0 + if (CannotBeOrderedLessThanZero(LHS)) + return ConstantInt::getFalse(CFP->getContext()); + break; + default: + break; + } + } } // If the comparison is with the result of a select instruction, check whether @@ -3106,7 +3136,7 @@ static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, } Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -3114,6 +3144,90 @@ Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, RecursionLimit); } +/// SimplifyWithOpReplaced - See if V simplifies when its operand Op is +/// replaced with RepOp. +static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp, + const Query &Q, + unsigned MaxRecurse) { + // Trivial replacement. + if (V == Op) + return RepOp; + + auto *I = dyn_cast<Instruction>(V); + if (!I) + return nullptr; + + // If this is a binary operator, try to simplify it with the replaced op. + if (auto *B = dyn_cast<BinaryOperator>(I)) { + // Consider: + // %cmp = icmp eq i32 %x, 2147483647 + // %add = add nsw i32 %x, 1 + // %sel = select i1 %cmp, i32 -2147483648, i32 %add + // + // We can't replace %sel with %add unless we strip away the flags. + if (isa<OverflowingBinaryOperator>(B)) + if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap()) + return nullptr; + if (isa<PossiblyExactOperator>(B)) + if (B->isExact()) + return nullptr; + + if (MaxRecurse) { + if (B->getOperand(0) == Op) + return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q, + MaxRecurse - 1); + if (B->getOperand(1) == Op) + return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q, + MaxRecurse - 1); + } + } + + // Same for CmpInsts. + if (CmpInst *C = dyn_cast<CmpInst>(I)) { + if (MaxRecurse) { + if (C->getOperand(0) == Op) + return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q, + MaxRecurse - 1); + if (C->getOperand(1) == Op) + return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q, + MaxRecurse - 1); + } + } + + // TODO: We could hand off more cases to instsimplify here. + + // If all operands are constant after substituting Op for RepOp then we can + // constant fold the instruction. + if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) { + // Build a list of all constant operands. + SmallVector<Constant *, 8> ConstOps; + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { + if (I->getOperand(i) == Op) + ConstOps.push_back(CRepOp); + else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i))) + ConstOps.push_back(COp); + else + break; + } + + // All operands were constants, fold it. + if (ConstOps.size() == I->getNumOperands()) { + if (CmpInst *C = dyn_cast<CmpInst>(I)) + return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0], + ConstOps[1], Q.DL, Q.TLI); + + if (LoadInst *LI = dyn_cast<LoadInst>(I)) + if (!LI->isVolatile()) + return ConstantFoldLoadFromConstPtr(ConstOps[0], Q.DL); + + return ConstantFoldInstOperands(I->getOpcode(), I->getType(), ConstOps, + Q.DL, Q.TLI); + } + } + + return nullptr; +} + /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold /// the result. If not, this returns null. static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, @@ -3142,29 +3256,28 @@ static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X return TrueVal; - const auto *ICI = dyn_cast<ICmpInst>(CondVal); - unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits(); - if (ICI && BitWidth) { + if (const auto *ICI = dyn_cast<ICmpInst>(CondVal)) { + unsigned BitWidth = Q.DL.getTypeSizeInBits(TrueVal->getType()); ICmpInst::Predicate Pred = ICI->getPredicate(); + Value *CmpLHS = ICI->getOperand(0); + Value *CmpRHS = ICI->getOperand(1); APInt MinSignedValue = APInt::getSignBit(BitWidth); Value *X; const APInt *Y; bool TrueWhenUnset; bool IsBitTest = false; if (ICmpInst::isEquality(Pred) && - match(ICI->getOperand(0), m_And(m_Value(X), m_APInt(Y))) && - match(ICI->getOperand(1), m_Zero())) { + match(CmpLHS, m_And(m_Value(X), m_APInt(Y))) && + match(CmpRHS, m_Zero())) { IsBitTest = true; TrueWhenUnset = Pred == ICmpInst::ICMP_EQ; - } else if (Pred == ICmpInst::ICMP_SLT && - match(ICI->getOperand(1), m_Zero())) { - X = ICI->getOperand(0); + } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) { + X = CmpLHS; Y = &MinSignedValue; IsBitTest = true; TrueWhenUnset = false; - } else if (Pred == ICmpInst::ICMP_SGT && - match(ICI->getOperand(1), m_AllOnes())) { - X = ICI->getOperand(0); + } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) { + X = CmpLHS; Y = &MinSignedValue; IsBitTest = true; TrueWhenUnset = true; @@ -3195,13 +3308,57 @@ static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, return TrueWhenUnset ? TrueVal : FalseVal; } } + if (ICI->hasOneUse()) { + const APInt *C; + if (match(CmpRHS, m_APInt(C))) { + // X < MIN ? T : F --> F + if (Pred == ICmpInst::ICMP_SLT && C->isMinSignedValue()) + return FalseVal; + // X < MIN ? T : F --> F + if (Pred == ICmpInst::ICMP_ULT && C->isMinValue()) + return FalseVal; + // X > MAX ? T : F --> F + if (Pred == ICmpInst::ICMP_SGT && C->isMaxSignedValue()) + return FalseVal; + // X > MAX ? T : F --> F + if (Pred == ICmpInst::ICMP_UGT && C->isMaxValue()) + return FalseVal; + } + } + + // If we have an equality comparison then we know the value in one of the + // arms of the select. See if substituting this value into the arm and + // simplifying the result yields the same value as the other arm. + if (Pred == ICmpInst::ICMP_EQ) { + if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) == + TrueVal || + SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) == + TrueVal) + return FalseVal; + if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) == + FalseVal || + SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) == + FalseVal) + return FalseVal; + } else if (Pred == ICmpInst::ICMP_NE) { + if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) == + FalseVal || + SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) == + FalseVal) + return TrueVal; + if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) == + TrueVal || + SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) == + TrueVal) + return TrueVal; + } } return nullptr; } Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, - const DataLayout *DL, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -3211,17 +3368,18 @@ Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can /// fold the result. If not, this returns null. -static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) { +static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops, + const Query &Q, unsigned) { // The type of the GEP pointer operand. - PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()->getScalarType()); - unsigned AS = PtrTy->getAddressSpace(); + unsigned AS = + cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace(); // getelementptr P -> P. if (Ops.size() == 1) return Ops[0]; // Compute the (pointer) type returned by the GEP instruction. - Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1)); + Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1)); Type *GEPTy = PointerType::get(LastType, AS); if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType())) GEPTy = VectorType::get(GEPTy, VT->getNumElements()); @@ -3234,11 +3392,11 @@ static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) { if (match(Ops[1], m_Zero())) return Ops[0]; - Type *Ty = PtrTy->getElementType(); - if (Q.DL && Ty->isSized()) { + Type *Ty = SrcTy; + if (Ty->isSized()) { Value *P; uint64_t C; - uint64_t TyAllocSize = Q.DL->getTypeAllocSize(Ty); + uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty); // getelementptr P, N -> P if P points to a type of zero size. if (TyAllocSize == 0) return Ops[0]; @@ -3246,7 +3404,7 @@ static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) { // The following transforms are only safe if the ptrtoint cast // doesn't truncate the pointers. if (Ops[1]->getType()->getScalarSizeInBits() == - Q.DL->getPointerSizeInBits(AS)) { + Q.DL.getPointerSizeInBits(AS)) { auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * { if (match(P, m_Zero())) return Constant::getNullValue(GEPTy); @@ -3288,14 +3446,17 @@ static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) { if (!isa<Constant>(Ops[i])) return nullptr; - return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1)); + return ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]), + Ops.slice(1)); } -Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *DL, +Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { - return ::SimplifyGEPInst(Ops, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); + return ::SimplifyGEPInst( + cast<PointerType>(Ops[0]->getType()->getScalarType())->getElementType(), + Ops, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); } /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we @@ -3328,7 +3489,7 @@ static Value *SimplifyInsertValueInst(Value *Agg, Value *Val, } Value *llvm::SimplifyInsertValueInst( - Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout *DL, + Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query(DL, TLI, DT, AC, CxtI), @@ -3341,8 +3502,7 @@ static Value *SimplifyPHINode(PHINode *PN, const Query &Q) { // with the common value. Value *CommonValue = nullptr; bool HasUndefInput = false; - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { - Value *Incoming = PN->getIncomingValue(i); + for (Value *Incoming : PN->incoming_values()) { // If the incoming value is the phi node itself, it can safely be skipped. if (Incoming == PN) continue; if (isa<UndefValue>(Incoming)) { @@ -3376,7 +3536,7 @@ static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) { return nullptr; } -Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *DL, +Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { @@ -3408,10 +3568,12 @@ static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse); case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse); - case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, Q, MaxRecurse); + case Instruction::FDiv: + return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse); case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse); - case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, Q, MaxRecurse); + case Instruction::FRem: + return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::Shl: return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, Q, MaxRecurse); @@ -3451,14 +3613,42 @@ static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, } } +/// SimplifyFPBinOp - Given operands for a BinaryOperator, see if we can +/// fold the result. If not, this returns null. +/// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the +/// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp. +static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, + const FastMathFlags &FMF, const Query &Q, + unsigned MaxRecurse) { + switch (Opcode) { + case Instruction::FAdd: + return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse); + case Instruction::FSub: + return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse); + case Instruction::FMul: + return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse); + default: + return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse); + } +} + Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, - const DataLayout *DL, const TargetLibraryInfo *TLI, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifyBinOp(Opcode, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); } +Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, + const FastMathFlags &FMF, const DataLayout &DL, + const TargetLibraryInfo *TLI, + const DominatorTree *DT, AssumptionCache *AC, + const Instruction *CxtI) { + return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Query(DL, TLI, DT, AC, CxtI), + RecursionLimit); +} + /// SimplifyCmpInst - Given operands for a CmpInst, see if we can /// fold the result. static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, @@ -3469,7 +3659,7 @@ static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, } Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const DataLayout *DL, const TargetLibraryInfo *TLI, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifyCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), @@ -3493,14 +3683,53 @@ static bool IsIdempotent(Intrinsic::ID ID) { } template <typename IterTy> -static Value *SimplifyIntrinsic(Intrinsic::ID IID, IterTy ArgBegin, IterTy ArgEnd, +static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd, const Query &Q, unsigned MaxRecurse) { + Intrinsic::ID IID = F->getIntrinsicID(); + unsigned NumOperands = std::distance(ArgBegin, ArgEnd); + Type *ReturnType = F->getReturnType(); + + // Binary Ops + if (NumOperands == 2) { + Value *LHS = *ArgBegin; + Value *RHS = *(ArgBegin + 1); + if (IID == Intrinsic::usub_with_overflow || + IID == Intrinsic::ssub_with_overflow) { + // X - X -> { 0, false } + if (LHS == RHS) + return Constant::getNullValue(ReturnType); + + // X - undef -> undef + // undef - X -> undef + if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) + return UndefValue::get(ReturnType); + } + + if (IID == Intrinsic::uadd_with_overflow || + IID == Intrinsic::sadd_with_overflow) { + // X + undef -> undef + if (isa<UndefValue>(RHS)) + return UndefValue::get(ReturnType); + } + + if (IID == Intrinsic::umul_with_overflow || + IID == Intrinsic::smul_with_overflow) { + // X * 0 -> { 0, false } + if (match(RHS, m_Zero())) + return Constant::getNullValue(ReturnType); + + // X * undef -> { 0, false } + if (match(RHS, m_Undef())) + return Constant::getNullValue(ReturnType); + } + } + // Perform idempotent optimizations if (!IsIdempotent(IID)) return nullptr; // Unary Ops - if (std::distance(ArgBegin, ArgEnd) == 1) + if (NumOperands == 1) if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) if (II->getIntrinsicID() == IID) return II; @@ -3524,9 +3753,8 @@ static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd, if (!F) return nullptr; - if (unsigned IID = F->getIntrinsicID()) - if (Value *Ret = - SimplifyIntrinsic((Intrinsic::ID) IID, ArgBegin, ArgEnd, Q, MaxRecurse)) + if (F->isIntrinsic()) + if (Value *Ret = SimplifyIntrinsic(F, ArgBegin, ArgEnd, Q, MaxRecurse)) return Ret; if (!canConstantFoldCallTo(F)) @@ -3545,7 +3773,7 @@ static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd, } Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin, - User::op_iterator ArgEnd, const DataLayout *DL, + User::op_iterator ArgEnd, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT, AC, CxtI), @@ -3553,7 +3781,7 @@ Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin, } Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args, - const DataLayout *DL, const TargetLibraryInfo *TLI, + const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { return ::SimplifyCall(V, Args.begin(), Args.end(), @@ -3562,7 +3790,7 @@ Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args, /// SimplifyInstruction - See if we can compute a simplified version of this /// instruction. If not, this returns null. -Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *DL, +Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC) { Value *Result; @@ -3608,8 +3836,8 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *DL, AC, I); break; case Instruction::FDiv: - Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, - AC, I); + Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), + I->getFastMathFlags(), DL, TLI, DT, AC, I); break; case Instruction::SRem: Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, @@ -3620,8 +3848,8 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *DL, AC, I); break; case Instruction::FRem: - Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, - AC, I); + Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), + I->getFastMathFlags(), DL, TLI, DT, AC, I); break; case Instruction::Shl: Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), @@ -3710,12 +3938,12 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *DL, /// This routine returns 'true' only when *it* simplifies something. The passed /// in simplified value does not count toward this. static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, - const DataLayout *DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC) { bool Simplified = false; SmallSetVector<Instruction *, 8> Worklist; + const DataLayout &DL = I->getModule()->getDataLayout(); // If we have an explicit value to collapse to, do that round of the // simplification loop by hand initially. @@ -3763,19 +3991,18 @@ static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, return Simplified; } -bool llvm::recursivelySimplifyInstruction(Instruction *I, const DataLayout *DL, +bool llvm::recursivelySimplifyInstruction(Instruction *I, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC) { - return replaceAndRecursivelySimplifyImpl(I, nullptr, DL, TLI, DT, AC); + return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC); } bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, - const DataLayout *DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC) { assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"); assert(SimpleV && "Must provide a simplified value."); - return replaceAndRecursivelySimplifyImpl(I, SimpleV, DL, TLI, DT, AC); + return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC); } |
