diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Analysis')
6 files changed, 147 insertions, 103 deletions
diff --git a/contrib/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp b/contrib/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp index 8a802515b6f4..35bdd869a88d 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp @@ -29,7 +29,6 @@ bool ConstraintSystem::eliminateUsingFM() { assert(!Constraints.empty() && "should only be called for non-empty constraint systems"); - uint32_t NewGCD = 1; unsigned LastIdx = NumVariables - 1; // First, either remove the variable in place if it is 0 or add the row to @@ -96,24 +95,20 @@ bool ConstraintSystem::eliminateUsingFM() { IdxUpper++; } - if (MulOverflow(UpperV, ((-1) * LowerLast / GCD), M1)) + if (MulOverflow(UpperV, ((-1) * LowerLast), M1)) return false; if (IdxLower < LowerRow.size() && LowerRow[IdxLower].Id == CurrentId) { LowerV = LowerRow[IdxLower].Coefficient; IdxLower++; } - if (MulOverflow(LowerV, (UpperLast / GCD), M2)) + if (MulOverflow(LowerV, (UpperLast), M2)) return false; if (AddOverflow(M1, M2, N)) return false; if (N == 0) continue; NR.emplace_back(N, CurrentId); - - NewGCD = - APIntOps::GreatestCommonDivisor({32, (uint32_t)N}, {32, NewGCD}) - .getZExtValue(); } if (NR.empty()) continue; @@ -124,7 +119,6 @@ bool ConstraintSystem::eliminateUsingFM() { } } NumVariables -= 1; - GCD = NewGCD; return true; } diff --git a/contrib/llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp b/contrib/llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp index 5beac5547d65..78a833476334 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp @@ -1189,14 +1189,26 @@ static Value *simplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, if (Value *V = simplifyDivRem(Opcode, Op0, Op1, Q, MaxRecurse)) return V; - // If this is an exact divide by a constant, then the dividend (Op0) must have - // at least as many trailing zeros as the divisor to divide evenly. If it has - // less trailing zeros, then the result must be poison. const APInt *DivC; - if (IsExact && match(Op1, m_APInt(DivC)) && DivC->countr_zero()) { - KnownBits KnownOp0 = computeKnownBits(Op0, /* Depth */ 0, Q); - if (KnownOp0.countMaxTrailingZeros() < DivC->countr_zero()) - return PoisonValue::get(Op0->getType()); + if (IsExact && match(Op1, m_APInt(DivC))) { + // If this is an exact divide by a constant, then the dividend (Op0) must + // have at least as many trailing zeros as the divisor to divide evenly. If + // it has less trailing zeros, then the result must be poison. + if (DivC->countr_zero()) { + KnownBits KnownOp0 = computeKnownBits(Op0, /* Depth */ 0, Q); + if (KnownOp0.countMaxTrailingZeros() < DivC->countr_zero()) + return PoisonValue::get(Op0->getType()); + } + + // udiv exact (mul nsw X, C), C --> X + // sdiv exact (mul nuw X, C), C --> X + // where C is not a power of 2. + Value *X; + if (!DivC->isPowerOf2() && + (Opcode == Instruction::UDiv + ? match(Op0, m_NSWMul(m_Value(X), m_Specific(Op1))) + : match(Op0, m_NUWMul(m_Value(X), m_Specific(Op1))))) + return X; } return nullptr; @@ -4857,14 +4869,12 @@ static Value *simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, // select ?, poison, X -> X // select ?, undef, X -> X if (isa<PoisonValue>(TrueVal) || - (Q.isUndefValue(TrueVal) && - isGuaranteedNotToBePoison(FalseVal, Q.AC, Q.CxtI, Q.DT))) + (Q.isUndefValue(TrueVal) && impliesPoison(FalseVal, Cond))) return FalseVal; // select ?, X, poison -> X // select ?, X, undef -> X if (isa<PoisonValue>(FalseVal) || - (Q.isUndefValue(FalseVal) && - isGuaranteedNotToBePoison(TrueVal, Q.AC, Q.CxtI, Q.DT))) + (Q.isUndefValue(FalseVal) && impliesPoison(TrueVal, Cond))) return TrueVal; // Deal with partial undef vector constants: select ?, VecC, VecC' --> VecC'' diff --git a/contrib/llvm-project/llvm/lib/Analysis/LazyValueInfo.cpp b/contrib/llvm-project/llvm/lib/Analysis/LazyValueInfo.cpp index 89cc7ea15ec1..360fc594ef7c 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/LazyValueInfo.cpp @@ -434,6 +434,28 @@ class LazyValueInfoImpl { void solve(); + // For the following methods, if UseBlockValue is true, the function may + // push additional values to the worklist and return nullopt. If + // UseBlockValue is false, it will never return nullopt. + + std::optional<ValueLatticeElement> + getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, Value *RHS, + const APInt &Offset, Instruction *CxtI, + bool UseBlockValue); + + std::optional<ValueLatticeElement> + getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest, + bool UseBlockValue); + + std::optional<ValueLatticeElement> + getValueFromCondition(Value *Val, Value *Cond, bool IsTrueDest, + bool UseBlockValue, unsigned Depth = 0); + + std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, + BasicBlock *BBFrom, + BasicBlock *BBTo, + bool UseBlockValue); + public: /// This is the query interface to determine the lattice value for the /// specified Value* at the context instruction (if specified) or at the @@ -755,14 +777,10 @@ LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) { return Result; } -static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, - bool isTrueDest = true, - unsigned Depth = 0); - // If we can determine a constraint on the value given conditions assumed by // the program, intersect those constraints with BBLV void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( - Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) { + Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) { BBI = BBI ? BBI : dyn_cast<Instruction>(Val); if (!BBI) return; @@ -779,17 +797,21 @@ void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( if (I->getParent() != BB || !isValidAssumeForContext(I, BBI)) continue; - BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0))); + BBLV = intersect(BBLV, *getValueFromCondition(Val, I->getArgOperand(0), + /*IsTrueDest*/ true, + /*UseBlockValue*/ false)); } // If guards are not used in the module, don't spend time looking for them if (GuardDecl && !GuardDecl->use_empty() && BBI->getIterator() != BB->begin()) { - for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()), - BB->rend())) { + for (Instruction &I : + make_range(std::next(BBI->getIterator().getReverse()), BB->rend())) { Value *Cond = nullptr; if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond)))) - BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); + BBLV = intersect(BBLV, + *getValueFromCondition(Val, Cond, /*IsTrueDest*/ true, + /*UseBlockValue*/ false)); } } @@ -886,10 +908,14 @@ LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) { // If the value is undef, a different value may be chosen in // the select condition. if (isGuaranteedNotToBeUndef(Cond, AC)) { - TrueVal = intersect(TrueVal, - getValueFromCondition(SI->getTrueValue(), Cond, true)); - FalseVal = intersect( - FalseVal, getValueFromCondition(SI->getFalseValue(), Cond, false)); + TrueVal = + intersect(TrueVal, *getValueFromCondition(SI->getTrueValue(), Cond, + /*IsTrueDest*/ true, + /*UseBlockValue*/ false)); + FalseVal = + intersect(FalseVal, *getValueFromCondition(SI->getFalseValue(), Cond, + /*IsTrueDest*/ false, + /*UseBlockValue*/ false)); } ValueLatticeElement Result = TrueVal; @@ -950,9 +976,11 @@ LazyValueInfoImpl::solveBlockValueBinaryOpImpl( // lets us pick up facts from expressions like "and i32 (call i32 // @foo()), 32" std::optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB); + if (!LHSRes) + return std::nullopt; + std::optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB); - if (!LHSRes || !RHSRes) - // More work to do before applying this transfer rule. + if (!RHSRes) return std::nullopt; const ConstantRange &LHSRange = *LHSRes; @@ -1068,15 +1096,26 @@ static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, } /// Get value range for a "(Val + Offset) Pred RHS" condition. -static ValueLatticeElement getValueFromSimpleICmpCondition( - CmpInst::Predicate Pred, Value *RHS, const APInt &Offset) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, + Value *RHS, + const APInt &Offset, + Instruction *CxtI, + bool UseBlockValue) { ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(), /*isFullSet=*/true); - if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) + if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { RHSRange = ConstantRange(CI->getValue()); - else if (Instruction *I = dyn_cast<Instruction>(RHS)) + } else if (UseBlockValue) { + std::optional<ValueLatticeElement> R = + getBlockValue(RHS, CxtI->getParent(), CxtI); + if (!R) + return std::nullopt; + RHSRange = toConstantRange(*R, RHS->getType()); + } else if (Instruction *I = dyn_cast<Instruction>(RHS)) { if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) RHSRange = getConstantRangeFromMetadata(*Ranges); + } ConstantRange TrueValues = ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); @@ -1103,8 +1142,8 @@ getRangeViaSLT(CmpInst::Predicate Pred, APInt RHS, return std::nullopt; } -static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, - bool isTrueDest) { +std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition( + Value *Val, ICmpInst *ICI, bool isTrueDest, bool UseBlockValue) { Value *LHS = ICI->getOperand(0); Value *RHS = ICI->getOperand(1); @@ -1128,11 +1167,13 @@ static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, unsigned BitWidth = Ty->getScalarSizeInBits(); APInt Offset(BitWidth, 0); if (matchICmpOperand(Offset, LHS, Val, EdgePred)) - return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset); + return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset, ICI, + UseBlockValue); CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred); if (matchICmpOperand(Offset, RHS, Val, SwappedPred)) - return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset); + return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset, ICI, + UseBlockValue); const APInt *Mask, *C; if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) && @@ -1212,10 +1253,12 @@ static ValueLatticeElement getValueFromOverflowCondition( return ValueLatticeElement::getRange(NWR); } -static ValueLatticeElement getValueFromCondition( - Value *Val, Value *Cond, bool IsTrueDest, unsigned Depth) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::getValueFromCondition(Value *Val, Value *Cond, + bool IsTrueDest, bool UseBlockValue, + unsigned Depth) { if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond)) - return getValueFromICmpCondition(Val, ICI, IsTrueDest); + return getValueFromICmpCondition(Val, ICI, IsTrueDest, UseBlockValue); if (auto *EVI = dyn_cast<ExtractValueInst>(Cond)) if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand())) @@ -1227,7 +1270,7 @@ static ValueLatticeElement getValueFromCondition( Value *N; if (match(Cond, m_Not(m_Value(N)))) - return getValueFromCondition(Val, N, !IsTrueDest, Depth); + return getValueFromCondition(Val, N, !IsTrueDest, UseBlockValue, Depth); Value *L, *R; bool IsAnd; @@ -1238,19 +1281,25 @@ static ValueLatticeElement getValueFromCondition( else return ValueLatticeElement::getOverdefined(); - ValueLatticeElement LV = getValueFromCondition(Val, L, IsTrueDest, Depth); - ValueLatticeElement RV = getValueFromCondition(Val, R, IsTrueDest, Depth); + std::optional<ValueLatticeElement> LV = + getValueFromCondition(Val, L, IsTrueDest, UseBlockValue, Depth); + if (!LV) + return std::nullopt; + std::optional<ValueLatticeElement> RV = + getValueFromCondition(Val, R, IsTrueDest, UseBlockValue, Depth); + if (!RV) + return std::nullopt; // if (L && R) -> intersect L and R // if (!(L || R)) -> intersect !L and !R // if (L || R) -> union L and R // if (!(L && R)) -> union !L and !R if (IsTrueDest ^ IsAnd) { - LV.mergeIn(RV); - return LV; + LV->mergeIn(*RV); + return *LV; } - return intersect(LV, RV); + return intersect(*LV, *RV); } // Return true if Usr has Op as an operand, otherwise false. @@ -1302,8 +1351,9 @@ static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, } /// Compute the value of Val on the edge BBFrom -> BBTo. -static ValueLatticeElement getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, + BasicBlock *BBTo, bool UseBlockValue) { // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we // know that v != 0. if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) { @@ -1324,13 +1374,16 @@ static ValueLatticeElement getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, // If the condition of the branch is an equality comparison, we may be // able to infer the value. - ValueLatticeElement Result = getValueFromCondition(Val, Condition, - isTrueDest); - if (!Result.isOverdefined()) + std::optional<ValueLatticeElement> Result = + getValueFromCondition(Val, Condition, isTrueDest, UseBlockValue); + if (!Result) + return std::nullopt; + + if (!Result->isOverdefined()) return Result; if (User *Usr = dyn_cast<User>(Val)) { - assert(Result.isOverdefined() && "Result isn't overdefined"); + assert(Result->isOverdefined() && "Result isn't overdefined"); // Check with isOperationFoldable() first to avoid linearly iterating // over the operands unnecessarily which can be expensive for // instructions with many operands. @@ -1356,8 +1409,8 @@ static ValueLatticeElement getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, // br i1 %Condition, label %then, label %else for (unsigned i = 0; i < Usr->getNumOperands(); ++i) { Value *Op = Usr->getOperand(i); - ValueLatticeElement OpLatticeVal = - getValueFromCondition(Op, Condition, isTrueDest); + ValueLatticeElement OpLatticeVal = *getValueFromCondition( + Op, Condition, isTrueDest, /*UseBlockValue*/ false); if (std::optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) { Result = constantFoldUser(Usr, Op, *OpConst, DL); @@ -1367,7 +1420,7 @@ static ValueLatticeElement getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, } } } - if (!Result.isOverdefined()) + if (!Result->isOverdefined()) return Result; } } @@ -1432,8 +1485,12 @@ LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, if (Constant *VC = dyn_cast<Constant>(Val)) return ValueLatticeElement::get(VC); - ValueLatticeElement LocalResult = getEdgeValueLocal(Val, BBFrom, BBTo); - if (hasSingleValue(LocalResult)) + std::optional<ValueLatticeElement> LocalResult = + getEdgeValueLocal(Val, BBFrom, BBTo, /*UseBlockValue*/ true); + if (!LocalResult) + return std::nullopt; + + if (hasSingleValue(*LocalResult)) // Can't get any more precise here return LocalResult; @@ -1453,7 +1510,7 @@ LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, // but then the result is not cached. intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); - return intersect(LocalResult, InBlock); + return intersect(*LocalResult, InBlock); } ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, @@ -1499,10 +1556,12 @@ getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, std::optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB, CxtI); - if (!Result) { + while (!Result) { + // As the worklist only explicitly tracks block values (but not edge values) + // we may have to call solve() multiple times, as the edge value calculation + // may request additional block values. solve(); Result = getEdgeValue(V, FromBB, ToBB, CxtI); - assert(Result && "More work to do after problem solved?"); } LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n"); @@ -1528,13 +1587,17 @@ ValueLatticeElement LazyValueInfoImpl::getValueAtUse(const Use &U) { if (!isGuaranteedNotToBeUndef(SI->getCondition(), AC)) break; if (CurrU->getOperandNo() == 1) - CondVal = getValueFromCondition(V, SI->getCondition(), true); + CondVal = + *getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ true, + /*UseBlockValue*/ false); else if (CurrU->getOperandNo() == 2) - CondVal = getValueFromCondition(V, SI->getCondition(), false); + CondVal = + *getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ false, + /*UseBlockValue*/ false); } else if (auto *PHI = dyn_cast<PHINode>(CurrI)) { // TODO: Use non-local query? - CondVal = - getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU), PHI->getParent()); + CondVal = *getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU), + PHI->getParent(), /*UseBlockValue*/ false); } if (CondVal) VL = intersect(VL, *CondVal); diff --git a/contrib/llvm-project/llvm/lib/Analysis/TargetTransformInfo.cpp b/contrib/llvm-project/llvm/lib/Analysis/TargetTransformInfo.cpp index 3f76dfdaac31..67246afa2314 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/TargetTransformInfo.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/TargetTransformInfo.cpp @@ -862,6 +862,15 @@ InstructionCost TargetTransformInfo::getArithmeticInstrCost( return Cost; } +InstructionCost TargetTransformInfo::getAltInstrCost( + VectorType *VecTy, unsigned Opcode0, unsigned Opcode1, + const SmallBitVector &OpcodeMask, TTI::TargetCostKind CostKind) const { + InstructionCost Cost = + TTIImpl->getAltInstrCost(VecTy, Opcode0, Opcode1, OpcodeMask, CostKind); + assert(Cost >= 0 && "TTI should not produce negative costs!"); + return Cost; +} + InstructionCost TargetTransformInfo::getShuffleCost( ShuffleKind Kind, VectorType *Ty, ArrayRef<int> Mask, TTI::TargetCostKind CostKind, int Index, VectorType *SubTp, diff --git a/contrib/llvm-project/llvm/lib/Analysis/ValueTracking.cpp b/contrib/llvm-project/llvm/lib/Analysis/ValueTracking.cpp index cac2602d455f..16d78c1ded6d 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/ValueTracking.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/ValueTracking.cpp @@ -983,45 +983,11 @@ static void computeKnownBitsFromOperator(const Operator *I, break; } case Instruction::Select: { - const Value *LHS = nullptr, *RHS = nullptr; - SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor; - if (SelectPatternResult::isMinOrMax(SPF)) { - computeKnownBits(RHS, Known, Depth + 1, Q); - computeKnownBits(LHS, Known2, Depth + 1, Q); - switch (SPF) { - default: - llvm_unreachable("Unhandled select pattern flavor!"); - case SPF_SMAX: - Known = KnownBits::smax(Known, Known2); - break; - case SPF_SMIN: - Known = KnownBits::smin(Known, Known2); - break; - case SPF_UMAX: - Known = KnownBits::umax(Known, Known2); - break; - case SPF_UMIN: - Known = KnownBits::umin(Known, Known2); - break; - } - break; - } - computeKnownBits(I->getOperand(2), Known, Depth + 1, Q); computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q); // Only known if known in both the LHS and RHS. Known = Known.intersectWith(Known2); - - if (SPF == SPF_ABS) { - // RHS from matchSelectPattern returns the negation part of abs pattern. - // If the negate has an NSW flag we can assume the sign bit of the result - // will be 0 because that makes abs(INT_MIN) undefined. - if (match(RHS, m_Neg(m_Specific(LHS))) && - Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(RHS))) - Known.Zero.setSignBit(); - } - break; } case Instruction::FPTrunc: diff --git a/contrib/llvm-project/llvm/lib/Analysis/VectorUtils.cpp b/contrib/llvm-project/llvm/lib/Analysis/VectorUtils.cpp index f90fca9d937f..5b57f0a25cec 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/VectorUtils.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/VectorUtils.cpp @@ -123,6 +123,8 @@ bool llvm::isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, bool llvm::isVectorIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID, int OpdIdx) { + assert(ID != Intrinsic::not_intrinsic && "Not an intrinsic!"); + switch (ID) { case Intrinsic::fptosi_sat: case Intrinsic::fptoui_sat: |