X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FInstructionSimplify.cpp;h=0bd18c1a35cd447d4cb7c0e78b12955b89c4169f;hb=b013b28ec87299c64b5a1888dfea7c3883682775;hp=99c477d46236fc5792e8026f2c6ba99482e6bf9e;hpb=529919ff310cbfce1ba55ea252ff738d5b56b93d;p=oota-llvm.git diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 99c477d4623..0bd18c1a35c 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -24,6 +24,7 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/VectorUtils.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" @@ -122,9 +123,9 @@ static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { } // Otherwise, if the instruction is in the entry block, and is not an invoke, - // then it obviously dominates all phi nodes. + // and is not a catchpad, then it obviously dominates all phi nodes. if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && - !isa(I)) + !isa(I) && !isa(I)) return true; return false; @@ -469,8 +470,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 ? @@ -510,8 +510,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); @@ -856,8 +855,8 @@ static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, return X; } - // fsub nnan ninf x, x ==> 0.0 - if (FMF.noNaNs() && FMF.noInfs() && Op0 == Op1) + // fsub nnan x, x ==> 0.0 + if (FMF.noNaNs() && Op0 == Op1) return Constant::getNullValue(Op0->getType()); return nullptr; @@ -1128,6 +1127,21 @@ static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero())) return Op0; + if (FMF.noNaNs()) { + // X / X -> 1.0 is legal when NaNs are ignored. + if (Op0 == Op1) + return ConstantFP::get(Op0->getType(), 1.0); + + // -X / X -> -1.0 and + // X / -X -> -1.0 are legal when NaNs are ignored. + // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored. + if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) && + BinaryOperator::getFNegArgument(Op0) == Op1) || + (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) && + BinaryOperator::getFNegArgument(Op1) == Op0)) + return ConstantFP::get(Op0->getType(), -1.0); + } + return nullptr; } @@ -2076,8 +2090,7 @@ static Constant *computePointerICmp(const DataLayout &DL, // Is the set of underlying objects all noalias calls? auto IsNAC = [](SmallVectorImpl &Objects) { - return std::all_of(Objects.begin(), Objects.end(), - [](Value *V){ return isNoAliasCall(V); }); + return std::all_of(Objects.begin(), Objects.end(), isNoAliasCall); }; // Is the set of underlying objects all things which must be disjoint from @@ -2162,6 +2175,19 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, // X >=u 1 -> X if (match(RHS, m_One())) return LHS; + if (isImpliedCondition(RHS, LHS, Q.DL)) + return getTrue(ITy); + break; + case ICmpInst::ICMP_SGE: + /// For signed comparison, the values for an i1 are 0 and -1 + /// respectively. This maps into a truth table of: + /// LHS | RHS | LHS >=s RHS | LHS implies RHS + /// 0 | 0 | 1 (0 >= 0) | 1 + /// 0 | 1 | 1 (0 >= -1) | 1 + /// 1 | 0 | 0 (-1 >= 0) | 0 + /// 1 | 1 | 1 (-1 >= -1) | 1 + if (isImpliedCondition(LHS, RHS, Q.DL)) + return getTrue(ITy); break; case ICmpInst::ICMP_SLT: // X X @@ -2173,6 +2199,10 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, if (match(RHS, m_One())) return LHS; break; + case ICmpInst::ICMP_ULE: + if (isImpliedCondition(LHS, RHS, Q.DL)) + return getTrue(ITy); + break; } } @@ -2346,9 +2376,19 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { // 'and x, CI2' produces [0, CI2]. Upper = CI2->getValue() + 1; + } else if (match(LHS, m_NUWAdd(m_Value(), m_ConstantInt(CI2)))) { + // 'add nuw x, CI2' produces [CI2, UINT_MAX]. + Lower = CI2->getValue(); } - if (Lower != Upper) { - ConstantRange LHS_CR = ConstantRange(Lower, Upper); + + ConstantRange LHS_CR = Lower != Upper ? ConstantRange(Lower, Upper) + : ConstantRange(Width, true); + + if (auto *I = dyn_cast(LHS)) + if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) + LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges)); + + if (!LHS_CR.isFullSet()) { if (RHS_CR.contains(LHS_CR)) return ConstantInt::getTrue(RHS->getContext()); if (RHS_CR.inverse().contains(LHS_CR)) @@ -2356,6 +2396,30 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } } + // If both operands have range metadata, use the metadata + // to simplify the comparison. + if (isa(RHS) && isa(LHS)) { + auto RHS_Instr = dyn_cast(RHS); + auto LHS_Instr = dyn_cast(LHS); + + if (RHS_Instr->getMetadata(LLVMContext::MD_range) && + LHS_Instr->getMetadata(LLVMContext::MD_range)) { + auto RHS_CR = getConstantRangeFromMetadata( + *RHS_Instr->getMetadata(LLVMContext::MD_range)); + auto LHS_CR = getConstantRangeFromMetadata( + *LHS_Instr->getMetadata(LLVMContext::MD_range)); + + auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR); + if (Satisfied_CR.contains(LHS_CR)) + return ConstantInt::getTrue(RHS->getContext()); + + auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion( + CmpInst::getInversePredicate(Pred), RHS_CR); + if (InversedSatisfied_CR.contains(LHS_CR)) + return ConstantInt::getFalse(RHS->getContext()); + } + } + // Compare of cast, for example (zext X) != 0 -> X != 0 if (isa(LHS) && (isa(RHS) || isa(RHS))) { Instruction *LI = cast(LHS); @@ -2515,6 +2579,14 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } } + // icmp eq|ne X, Y -> false|true if X != Y + if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) && + isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) { + LLVMContext &Ctx = LHS->getType()->getContext(); + return Pred == ICmpInst::ICMP_NE ? + ConstantInt::getTrue(Ctx) : ConstantInt::getFalse(Ctx); + } + // Special logic for binary operators. BinaryOperator *LBO = dyn_cast(LHS); BinaryOperator *RBO = dyn_cast(RHS); @@ -2978,10 +3050,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 IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); - Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS); + Constant *NewLHS = ConstantExpr::getGetElementPtr( + GLHS->getSourceElementType(), Null, IndicesLHS); SmallVector 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); } } @@ -3031,7 +3105,8 @@ Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can /// fold the result. If not, this returns null. static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const Query &Q, unsigned MaxRecurse) { + FastMathFlags FMF, const Query &Q, + unsigned MaxRecurse) { CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); @@ -3050,6 +3125,14 @@ static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, if (Pred == FCmpInst::FCMP_TRUE) return ConstantInt::get(GetCompareTy(LHS), 1); + // UNO/ORD predicates can be trivially folded if NaNs are ignored. + if (FMF.noNaNs()) { + if (Pred == FCmpInst::FCMP_UNO) + return ConstantInt::get(GetCompareTy(LHS), 0); + if (Pred == FCmpInst::FCMP_ORD) + return ConstantInt::get(GetCompareTy(LHS), 1); + } + // fcmp pred x, undef and fcmp pred undef, x // fold to true if unordered, false if ordered if (isa(LHS) || isa(RHS)) { @@ -3136,12 +3219,96 @@ static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, } Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const DataLayout &DL, + FastMathFlags FMF, const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { - return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI), - RecursionLimit); + return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, + Query(DL, TLI, DT, AC, CxtI), 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(V); + if (!I) + return nullptr; + + // If this is a binary operator, try to simplify it with the replaced op. + if (auto *B = dyn_cast(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(B)) + if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap()) + return nullptr; + if (isa(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(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(RepOp)) { + // Build a list of all constant operands. + SmallVector 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(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(I)) + return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0], + ConstOps[1], Q.DL, Q.TLI); + + if (LoadInst *LI = dyn_cast(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 @@ -3172,29 +3339,28 @@ static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, if (isa(FalseVal)) // select C, X, undef -> X return TrueVal; - const auto *ICI = dyn_cast(CondVal); - unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits(); - if (ICI && BitWidth) { + if (const auto *ICI = dyn_cast(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; @@ -3225,6 +3391,50 @@ 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; @@ -3241,17 +3451,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 Ops, const Query &Q, unsigned) { +static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef Ops, + const Query &Q, unsigned) { // The type of the GEP pointer operand. - PointerType *PtrTy = cast(Ops[0]->getType()->getScalarType()); - unsigned AS = PtrTy->getAddressSpace(); + unsigned AS = + cast(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(Ops[0]->getType())) GEPTy = VectorType::get(GEPTy, VT->getNumElements()); @@ -3264,7 +3475,7 @@ static Value *SimplifyGEPInst(ArrayRef Ops, const Query &Q, unsigned) { if (match(Ops[1], m_Zero())) return Ops[0]; - Type *Ty = PtrTy->getElementType(); + Type *Ty = SrcTy; if (Ty->isSized()) { Value *P; uint64_t C; @@ -3318,14 +3529,17 @@ static Value *SimplifyGEPInst(ArrayRef Ops, const Query &Q, unsigned) { if (!isa(Ops[i])) return nullptr; - return ConstantExpr::getGetElementPtr(cast(Ops[0]), Ops.slice(1)); + return ConstantExpr::getGetElementPtr(SrcTy, cast(Ops[0]), + Ops.slice(1)); } Value *llvm::SimplifyGEPInst(ArrayRef 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(Ops[0]->getType()->getScalarType())->getElementType(), + Ops, Query(DL, TLI, DT, AC, CxtI), RecursionLimit); } /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we @@ -3365,14 +3579,80 @@ Value *llvm::SimplifyInsertValueInst( RecursionLimit); } +/// SimplifyExtractValueInst - Given operands for an ExtractValueInst, see if we +/// can fold the result. If not, this returns null. +static Value *SimplifyExtractValueInst(Value *Agg, ArrayRef Idxs, + const Query &, unsigned) { + if (auto *CAgg = dyn_cast(Agg)) + return ConstantFoldExtractValueInstruction(CAgg, Idxs); + + // extractvalue x, (insertvalue y, elt, n), n -> elt + unsigned NumIdxs = Idxs.size(); + for (auto *IVI = dyn_cast(Agg); IVI != nullptr; + IVI = dyn_cast(IVI->getAggregateOperand())) { + ArrayRef InsertValueIdxs = IVI->getIndices(); + unsigned NumInsertValueIdxs = InsertValueIdxs.size(); + unsigned NumCommonIdxs = std::min(NumInsertValueIdxs, NumIdxs); + if (InsertValueIdxs.slice(0, NumCommonIdxs) == + Idxs.slice(0, NumCommonIdxs)) { + if (NumIdxs == NumInsertValueIdxs) + return IVI->getInsertedValueOperand(); + break; + } + } + + return nullptr; +} + +Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef Idxs, + const DataLayout &DL, + const TargetLibraryInfo *TLI, + const DominatorTree *DT, + AssumptionCache *AC, + const Instruction *CxtI) { + return ::SimplifyExtractValueInst(Agg, Idxs, Query(DL, TLI, DT, AC, CxtI), + RecursionLimit); +} + +/// SimplifyExtractElementInst - Given operands for an ExtractElementInst, see if we +/// can fold the result. If not, this returns null. +static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const Query &, + unsigned) { + if (auto *CVec = dyn_cast(Vec)) { + if (auto *CIdx = dyn_cast(Idx)) + return ConstantFoldExtractElementInstruction(CVec, CIdx); + + // The index is not relevant if our vector is a splat. + if (auto *Splat = CVec->getSplatValue()) + return Splat; + + if (isa(Vec)) + return UndefValue::get(Vec->getType()->getVectorElementType()); + } + + // If extracting a specified index from the vector, see if we can recursively + // find a previously computed scalar that was inserted into the vector. + if (auto *IdxC = dyn_cast(Idx)) + if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue())) + return Elt; + + return nullptr; +} + +Value *llvm::SimplifyExtractElementInst( + Value *Vec, Value *Idx, const DataLayout &DL, const TargetLibraryInfo *TLI, + const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) { + return ::SimplifyExtractElementInst(Vec, Idx, Query(DL, TLI, DT, AC, CxtI), + RecursionLimit); +} + /// SimplifyPHINode - See if we can fold the given phi. If not, returns null. static Value *SimplifyPHINode(PHINode *PN, const Query &Q) { // If all of the PHI's incoming values are the same then replace the PHI node // 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(Incoming)) { @@ -3525,7 +3805,7 @@ static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const Query &Q, unsigned MaxRecurse) { if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse); - return SimplifyFCmpInst(Predicate, LHS, RHS, Q, MaxRecurse); + return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse); } Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, @@ -3553,14 +3833,53 @@ static bool IsIdempotent(Intrinsic::ID ID) { } template -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(LHS) || isa(RHS)) + return UndefValue::get(ReturnType); + } + + if (IID == Intrinsic::uadd_with_overflow || + IID == Intrinsic::sadd_with_overflow) { + // X + undef -> undef + if (isa(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(*ArgBegin)) if (II->getIntrinsicID() == IID) return II; @@ -3584,9 +3903,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)) @@ -3717,9 +4035,9 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL, I->getOperand(1), DL, TLI, DT, AC, I); break; case Instruction::FCmp: - Result = - SimplifyFCmpInst(cast(I)->getPredicate(), I->getOperand(0), - I->getOperand(1), DL, TLI, DT, AC, I); + Result = SimplifyFCmpInst(cast(I)->getPredicate(), + I->getOperand(0), I->getOperand(1), + I->getFastMathFlags(), DL, TLI, DT, AC, I); break; case Instruction::Select: Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), @@ -3737,6 +4055,18 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL, IV->getIndices(), DL, TLI, DT, AC, I); break; } + case Instruction::ExtractValue: { + auto *EVI = cast(I); + Result = SimplifyExtractValueInst(EVI->getAggregateOperand(), + EVI->getIndices(), DL, TLI, DT, AC, I); + break; + } + case Instruction::ExtractElement: { + auto *EEI = cast(I); + Result = SimplifyExtractElementInst( + EEI->getVectorOperand(), EEI->getIndexOperand(), DL, TLI, DT, AC, I); + break; + } case Instruction::PHI: Result = SimplifyPHINode(cast(I), Query(DL, TLI, DT, AC, I)); break; @@ -3752,6 +4082,17 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL, break; } + // In general, it is possible for computeKnownBits to determine all bits in a + // value even when the operands are not all constants. + if (!Result && I->getType()->isIntegerTy()) { + unsigned BitWidth = I->getType()->getScalarSizeInBits(); + APInt KnownZero(BitWidth, 0); + APInt KnownOne(BitWidth, 0); + computeKnownBits(I, KnownZero, KnownOne, DL, /*Depth*/0, AC, I, DT); + if ((KnownZero | KnownOne).isAllOnesValue()) + Result = ConstantInt::get(I->getContext(), KnownOne); + } + /// If called on unreachable code, the above logic may report that the /// instruction simplified to itself. Make life easier for users by /// detecting that case here, returning a safe value instead.