diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -215,15 +215,15 @@ cl::desc("Max coefficients in AddRec during evolving"), cl::init(8)); -static cl::opt - HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, - cl::desc("Size of the expression which is considered huge"), - cl::init(4096)); +static cl::opt HugeExprThreshold( + "scalar-evolution-huge-expr-threshold", cl::Hidden, + cl::desc("Size of the expression which is considered huge"), + cl::init(4096)); -static cl::opt -ClassifyExpressions("scalar-evolution-classify-expressions", - cl::Hidden, cl::init(true), - cl::desc("When printing analysis, include information on every instruction")); +static cl::opt ClassifyExpressions( + "scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), + cl::desc( + "When printing analysis, include information on every instruction")); static cl::opt UseExpensiveRangeSharpening( "scalar-evolution-use-expensive-range-sharpening", cl::Hidden, @@ -284,15 +284,15 @@ case scZeroExtend: { const SCEVZeroExtendExpr *ZExt = cast(this); const SCEV *Op = ZExt->getOperand(); - OS << "(zext " << *Op->getType() << " " << *Op << " to " - << *ZExt->getType() << ")"; + OS << "(zext " << *Op->getType() << " " << *Op << " to " << *ZExt->getType() + << ")"; return; } case scSignExtend: { const SCEVSignExtendExpr *SExt = cast(this); const SCEV *Op = SExt->getOperand(); - OS << "(sext " << *Op->getType() << " " << *Op << " to " - << *SExt->getType() << ")"; + OS << "(sext " << *Op->getType() << " " << *Op << " to " << *SExt->getType() + << ")"; return; } case scAddRecExpr: { @@ -322,10 +322,18 @@ const SCEVNAryExpr *NAry = cast(this); const char *OpStr = nullptr; switch (NAry->getSCEVType()) { - case scAddExpr: OpStr = " + "; break; - case scMulExpr: OpStr = " * "; break; - case scUMaxExpr: OpStr = " umax "; break; - case scSMaxExpr: OpStr = " smax "; break; + case scAddExpr: + OpStr = " + "; + break; + case scMulExpr: + OpStr = " * "; + break; + case scUMaxExpr: + OpStr = " umax "; + break; + case scSMaxExpr: + OpStr = " smax "; + break; case scUMinExpr: OpStr = " umin "; break; @@ -446,18 +454,20 @@ bool SCEV::isNonConstantNegative() const { const SCEVMulExpr *Mul = dyn_cast(this); - if (!Mul) return false; + if (!Mul) + return false; // If there is a constant factor, it will be first. const SCEVConstant *SC = dyn_cast(Mul->getOperand(0)); - if (!SC) return false; + if (!SC) + return false; // Return true if the value is negative, this matches things like (-42 * V). return SC->getAPInt().isNegative(); } -SCEVCouldNotCompute::SCEVCouldNotCompute() : - SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {} +SCEVCouldNotCompute::SCEVCouldNotCompute() + : SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {} bool SCEVCouldNotCompute::classof(const SCEV *S) { return S->getSCEVType() == scCouldNotCompute; @@ -468,7 +478,8 @@ ID.AddInteger(scConstant); ID.AddPointer(V); void *IP = nullptr; - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) + return S; SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V); UniqueSCEVs.InsertNode(S, IP); return S; @@ -478,8 +489,7 @@ return getConstant(ConstantInt::get(getContext(), Val)); } -const SCEV * -ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) { +const SCEV *ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) { IntegerType *ITy = cast(getEffectiveSCEVType(Ty)); return getConstant(ConstantInt::get(ITy, V, isSigned)); } @@ -550,8 +560,7 @@ if (VCE->getOpcode() == Instruction::PtrToInt) if (ConstantExpr *CE = dyn_cast(VCE->getOperand(0))) if (CE->getOpcode() == Instruction::GetElementPtr && - CE->getOperand(0)->isNullValue() && - CE->getNumOperands() == 2) + CE->getOperand(0)->isNullValue() && CE->getNumOperands() == 2) if (ConstantInt *CI = dyn_cast(CE->getOperand(1))) if (CI->isOne()) { AllocTy = cast(CE)->getSourceElementType(); @@ -569,12 +578,10 @@ CE->getOperand(0)->isNullValue()) { Type *Ty = cast(CE)->getSourceElementType(); if (StructType *STy = dyn_cast(Ty)) - if (!STy->isPacked() && - CE->getNumOperands() == 3 && + if (!STy->isPacked() && CE->getNumOperands() == 3 && CE->getOperand(1)->isNullValue()) { if (ConstantInt *CI = dyn_cast(CE->getOperand(2))) - if (CI->isOne() && - STy->getNumElements() == 2 && + if (CI->isOne() && STy->getNumElements() == 2 && STy->getElementType(0)->isIntegerTy(1)) { AllocTy = STy->getElementType(1); return true; @@ -590,8 +597,7 @@ if (VCE->getOpcode() == Instruction::PtrToInt) if (ConstantExpr *CE = dyn_cast(VCE->getOperand(0))) if (CE->getOpcode() == Instruction::GetElementPtr && - CE->getNumOperands() == 3 && - CE->getOperand(0)->isNullValue() && + CE->getNumOperands() == 3 && CE->getOperand(0)->isNullValue() && CE->getOperand(1)->isNullValue()) { Type *Ty = cast(CE)->getSourceElementType(); // Ignore vector types here so that ScalarEvolutionExpander doesn't @@ -865,9 +871,10 @@ /// results from this routine. In other words, we don't want the results of /// this to depend on where the addresses of various SCEV objects happened to /// land in memory. -static void GroupByComplexity(SmallVectorImpl &Ops, - LoopInfo *LI, DominatorTree &DT) { - if (Ops.size() < 2) return; // Noop +static void GroupByComplexity(SmallVectorImpl &Ops, LoopInfo *LI, + DominatorTree &DT) { + if (Ops.size() < 2) + return; // Noop EquivalenceClasses EqCacheSCEV; EquivalenceClasses EqCacheValue; @@ -896,18 +903,20 @@ // complexity. Note that this is, at worst, N^2, but the vector is likely to // be extremely short in practice. Note that we take this approach because we // do not want to depend on the addresses of the objects we are grouping. - for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) { + for (unsigned i = 0, e = Ops.size(); i != e - 2; ++i) { const SCEV *S = Ops[i]; unsigned Complexity = S->getSCEVType(); // If there are any objects of the same complexity and same value as this // one, group them. - for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) { + for (unsigned j = i + 1; j != e && Ops[j]->getSCEVType() == Complexity; + ++j) { if (Ops[j] == S) { // Found a duplicate. // Move it to immediately after i'th element. - std::swap(Ops[i+1], Ops[j]); - ++i; // no need to rescan it. - if (i == e-2) return; // Done! + std::swap(Ops[i + 1], Ops[j]); + ++i; // no need to rescan it. + if (i == e - 2) + return; // Done! } } } @@ -927,8 +936,7 @@ /// Compute BC(It, K). The result has width W. Assume, K > 0. static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, - ScalarEvolution &SE, - Type *ResultTy) { + ScalarEvolution &SE, Type *ResultTy) { // Handle the simplest case efficiently. if (K == 1) return SE.getTruncateOrZeroExtend(It, ResultTy); @@ -1012,19 +1020,19 @@ // Calculate the multiplicative inverse of K! / 2^T; // this multiplication factor will perform the exact division by // K! / 2^T. - APInt Mod = APInt::getSignedMinValue(W+1); - APInt MultiplyFactor = OddFactorial.zext(W+1); + APInt Mod = APInt::getSignedMinValue(W + 1); + APInt MultiplyFactor = OddFactorial.zext(W + 1); MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod); MultiplyFactor = MultiplyFactor.trunc(W); // Calculate the product, at width T+W - IntegerType *CalculationTy = IntegerType::get(SE.getContext(), - CalculationBits); + IntegerType *CalculationTy = + IntegerType::get(SE.getContext(), CalculationBits); const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); for (unsigned i = 1; i != K; ++i) { const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i)); - Dividend = SE.getMulExpr(Dividend, - SE.getTruncateOrZeroExtend(S, CalculationTy)); + Dividend = + SE.getMulExpr(Dividend, SE.getTruncateOrZeroExtend(S, CalculationTy)); } // Divide by 2^T @@ -1049,9 +1057,9 @@ return evaluateAtIteration(makeArrayRef(op_begin(), op_end()), It, SE); } -const SCEV * -SCEVAddRecExpr::evaluateAtIteration(ArrayRef Operands, - const SCEV *It, ScalarEvolution &SE) { +const SCEV *SCEVAddRecExpr::evaluateAtIteration(ArrayRef Operands, + const SCEV *It, + ScalarEvolution &SE) { assert(Operands.size() > 0); const SCEV *Result = Operands[0]; for (unsigned i = 1, e = Operands.size(); i != e; ++i) { @@ -1209,8 +1217,7 @@ unsigned Depth) { assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) && "This is not a truncating conversion!"); - assert(isSCEVable(Ty) && - "This is not a conversion to a SCEVable type!"); + assert(isSCEVable(Ty) && "This is not a conversion to a SCEVable type!"); assert(!Op->getType()->isPointerTy() && "Can't truncate pointer!"); Ty = getEffectiveSCEVType(Ty); @@ -1219,12 +1226,13 @@ ID.AddPointer(Op); ID.AddPointer(Ty); void *IP = nullptr; - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) + return S; // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast(Op)) return getConstant( - cast(ConstantExpr::getTrunc(SC->getValue(), Ty))); + cast(ConstantExpr::getTrunc(SC->getValue(), Ty))); // trunc(trunc(x)) --> trunc(x) if (const SCEVTruncateExpr *ST = dyn_cast(Op)) @@ -1293,8 +1301,8 @@ // The cast wasn't folded; create an explicit cast node. We can reuse // the existing insert position since if we get here, we won't have // made any changes which would invalidate it. - SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), - Op, Ty); + SCEV *S = + new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); registerUser(S, Op); return S; @@ -1366,8 +1374,9 @@ } }; -const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits< - SCEVSignExtendExpr>::GetExtendExpr = &ScalarEvolution::getSignExtendExpr; +const ExtendOpTraitsBase::GetExtendExprTy + ExtendOpTraits::GetExtendExpr = + &ScalarEvolution::getSignExtendExpr; template <> struct ExtendOpTraits : public ExtendOpTraitsBase { @@ -1382,8 +1391,9 @@ } }; -const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits< - SCEVZeroExtendExpr>::GetExtendExpr = &ScalarEvolution::getZeroExtendExpr; +const ExtendOpTraitsBase::GetExtendExprTy + ExtendOpTraits::GetExtendExpr = + &ScalarEvolution::getZeroExtendExpr; } // end anonymous namespace @@ -1425,7 +1435,7 @@ // 1. NSW/NUW flags on the step increment. auto PreStartFlags = - ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW); + ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW); const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags); const SCEVAddRecExpr *PreAR = dyn_cast( SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap)); @@ -1470,17 +1480,16 @@ // Get the normalized zero or sign extended expression for this AddRec's Start. template static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, - ScalarEvolution *SE, - unsigned Depth) { + ScalarEvolution *SE, unsigned Depth) { auto GetExtendExpr = ExtendOpTraits::GetExtendExpr; const SCEV *PreStart = getPreStartForExtend(AR, Ty, SE, Depth); if (!PreStart) return (SE->*GetExtendExpr)(AR->getStart(), Ty, Depth); - return SE->getAddExpr((SE->*GetExtendExpr)(AR->getStepRecurrence(*SE), Ty, - Depth), - (SE->*GetExtendExpr)(PreStart, Ty, Depth)); + return SE->getAddExpr( + (SE->*GetExtendExpr)(AR->getStepRecurrence(*SE), Ty, Depth), + (SE->*GetExtendExpr)(PreStart, Ty, Depth)); } // Try to prove away overflow by looking at "nearby" add recurrences. A @@ -1541,16 +1550,16 @@ ID.AddPointer(L); void *IP = nullptr; const auto *PreAR = - static_cast(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)); + static_cast(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)); // Give up if we don't already have the add recurrence we need because // actually constructing an add recurrence is relatively expensive. - if (PreAR && PreAR->getNoWrapFlags(WrapType)) { // proves (2) + if (PreAR && PreAR->getNoWrapFlags(WrapType)) { // proves (2) const SCEV *DeltaS = getConstant(StartC->getType(), Delta); ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE; const SCEV *Limit = ExtendOpTraits::getOverflowLimitForStep( DeltaS, &Pred, this); - if (Limit && isKnownPredicate(Pred, PreAR, Limit)) // proves (1) + if (Limit && isKnownPredicate(Pred, PreAR, Limit)) // proves (1) return true; } } @@ -1595,19 +1604,18 @@ return APInt(BitWidth, 0); } -const SCEV * -ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { +const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, + unsigned Depth) { assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && "This is not an extending conversion!"); - assert(isSCEVable(Ty) && - "This is not a conversion to a SCEVable type!"); + assert(isSCEVable(Ty) && "This is not a conversion to a SCEVable type!"); assert(!Op->getType()->isPointerTy() && "Can't extend pointer!"); Ty = getEffectiveSCEVType(Ty); // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast(Op)) return getConstant( - cast(ConstantExpr::getZExt(SC->getValue(), Ty))); + cast(ConstantExpr::getZExt(SC->getValue(), Ty))); // zext(zext(x)) --> zext(x) if (const SCEVZeroExtendExpr *SZ = dyn_cast(Op)) @@ -1620,10 +1628,11 @@ ID.AddPointer(Op); ID.AddPointer(Ty); void *IP = nullptr; - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) + return S; if (Depth > MaxCastDepth) { - SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), - Op, Ty); + SCEV *S = new (SCEVAllocator) + SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); registerUser(S, Op); return S; @@ -1688,21 +1697,20 @@ if (MaxBECount == RecastedMaxBECount) { Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no unsigned overflow. - const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step, - SCEV::FlagAnyWrap, Depth + 1); - const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul, - SCEV::FlagAnyWrap, - Depth + 1), - WideTy, Depth + 1); + const SCEV *ZMul = + getMulExpr(CastedMaxBECount, Step, SCEV::FlagAnyWrap, Depth + 1); + const SCEV *ZAdd = getZeroExtendExpr( + getAddExpr(Start, ZMul, SCEV::FlagAnyWrap, Depth + 1), WideTy, + Depth + 1); const SCEV *WideStart = getZeroExtendExpr(Start, WideTy, Depth + 1); const SCEV *WideMaxBECount = - getZeroExtendExpr(CastedMaxBECount, WideTy, Depth + 1); + getZeroExtendExpr(CastedMaxBECount, WideTy, Depth + 1); const SCEV *OperandExtendedAdd = - getAddExpr(WideStart, - getMulExpr(WideMaxBECount, - getZeroExtendExpr(Step, WideTy, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1); + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, + getZeroExtendExpr(Step, WideTy, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1); if (ZAdd == OperandExtendedAdd) { // Cache knowledge of AR NUW, which is propagated to this AddRec. setNoWrapFlags(const_cast(AR), SCEV::FlagNUW); @@ -1715,11 +1723,11 @@ // Similar to above, only this time treat the step value as signed. // This covers loops that count down. OperandExtendedAdd = - getAddExpr(WideStart, - getMulExpr(WideMaxBECount, - getSignExtendExpr(Step, WideTy, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1); + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, + getSignExtendExpr(Step, WideTy, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1); if (ZAdd == OperandExtendedAdd) { // Cache knowledge of AR NW, which is propagated to this AddRec. // Negative step causes unsigned wrap, but it still can't self-wrap. @@ -1755,9 +1763,9 @@ Step = getZeroExtendExpr(Step, Ty, Depth + 1); return getAddRecExpr(Start, Step, L, AR->getNoWrapFlags()); } - + // For a negative step, we can extend the operands iff doing so only - // traverses values in the range zext([0,UINT_MAX]). + // traverses values in the range zext([0,UINT_MAX]). if (isKnownNegative(Step)) { const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) - getSignedRangeMin(Step)); @@ -1889,27 +1897,27 @@ // The cast wasn't folded; create an explicit cast node. // Recompute the insert position, as it may have been invalidated. - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), - Op, Ty); + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) + return S; + SCEV *S = + new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); registerUser(S, Op); return S; } -const SCEV * -ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { +const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, + unsigned Depth) { assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && "This is not an extending conversion!"); - assert(isSCEVable(Ty) && - "This is not a conversion to a SCEVable type!"); + assert(isSCEVable(Ty) && "This is not a conversion to a SCEVable type!"); assert(!Op->getType()->isPointerTy() && "Can't extend pointer!"); Ty = getEffectiveSCEVType(Ty); // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast(Op)) return getConstant( - cast(ConstantExpr::getSExt(SC->getValue(), Ty))); + cast(ConstantExpr::getSExt(SC->getValue(), Ty))); // sext(sext(x)) --> sext(x) if (const SCEVSignExtendExpr *SS = dyn_cast(Op)) @@ -1926,11 +1934,12 @@ ID.AddPointer(Op); ID.AddPointer(Ty); void *IP = nullptr; - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) + return S; // Limit recursion depth. if (Depth > MaxCastDepth) { - SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), - Op, Ty); + SCEV *S = new (SCEVAllocator) + SCEVSignExtendExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); registerUser(S, Op); return S; @@ -2029,21 +2038,20 @@ if (MaxBECount == RecastedMaxBECount) { Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no signed overflow. - const SCEV *SMul = getMulExpr(CastedMaxBECount, Step, - SCEV::FlagAnyWrap, Depth + 1); - const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul, - SCEV::FlagAnyWrap, - Depth + 1), - WideTy, Depth + 1); + const SCEV *SMul = + getMulExpr(CastedMaxBECount, Step, SCEV::FlagAnyWrap, Depth + 1); + const SCEV *SAdd = getSignExtendExpr( + getAddExpr(Start, SMul, SCEV::FlagAnyWrap, Depth + 1), WideTy, + Depth + 1); const SCEV *WideStart = getSignExtendExpr(Start, WideTy, Depth + 1); const SCEV *WideMaxBECount = - getZeroExtendExpr(CastedMaxBECount, WideTy, Depth + 1); + getZeroExtendExpr(CastedMaxBECount, WideTy, Depth + 1); const SCEV *OperandExtendedAdd = - getAddExpr(WideStart, - getMulExpr(WideMaxBECount, - getSignExtendExpr(Step, WideTy, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1); + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, + getSignExtendExpr(Step, WideTy, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1); if (SAdd == OperandExtendedAdd) { // Cache knowledge of AR NSW, which is propagated to this AddRec. setNoWrapFlags(const_cast(AR), SCEV::FlagNSW); @@ -2056,11 +2064,11 @@ // Similar to above, only this time treat the step value as unsigned. // This covers loops that count up with an unsigned step. OperandExtendedAdd = - getAddExpr(WideStart, - getMulExpr(WideMaxBECount, - getZeroExtendExpr(Step, WideTy, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1); + getAddExpr(WideStart, + getMulExpr(WideMaxBECount, + getZeroExtendExpr(Step, WideTy, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1); if (SAdd == OperandExtendedAdd) { // If AR wraps around then // @@ -2127,11 +2135,12 @@ // The cast wasn't folded; create an explicit cast node. // Recompute the insert position, as it may have been invalidated. - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), - Op, Ty); + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) + return S; + SCEV *S = + new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); - registerUser(S, { Op }); + registerUser(S, {Op}); return S; } @@ -2153,12 +2162,10 @@ /// getAnyExtendExpr - Return a SCEV for the given operand extended with /// unspecified bits out to the given type. -const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, - Type *Ty) { +const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, Type *Ty) { assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && "This is not an extending conversion!"); - assert(isSCEVable(Ty) && - "This is not a conversion to a SCEVable type!"); + assert(isSCEVable(Ty) && "This is not a conversion to a SCEVable type!"); Ty = getEffectiveSCEVType(Ty); // Sign-extend negative constants. @@ -2223,13 +2230,12 @@ /// may be exposed. This helps getAddRecExpr short-circuit extra work in /// the common case where no interesting opportunities are present, and /// is also used as a check to avoid infinite recursion. -static bool -CollectAddOperandsWithScales(DenseMap &M, - SmallVectorImpl &NewOps, - APInt &AccumulatedConstant, - const SCEV *const *Ops, size_t NumOperands, - const APInt &Scale, - ScalarEvolution &SE) { +static bool CollectAddOperandsWithScales(DenseMap &M, + SmallVectorImpl &NewOps, + APInt &AccumulatedConstant, + const SCEV *const *Ops, + size_t NumOperands, const APInt &Scale, + ScalarEvolution &SE) { bool Interesting = false; // Iterate over the add operands. They are sorted, with constants first. @@ -2252,10 +2258,9 @@ if (Mul->getNumOperands() == 2 && isa(Mul->getOperand(1))) { // A multiplication of a constant with another add; recurse. const SCEVAddExpr *Add = cast(Mul->getOperand(1)); - Interesting |= - CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant, - Add->op_begin(), Add->getNumOperands(), - NewScale, SE); + Interesting |= CollectAddOperandsWithScales( + M, NewOps, AccumulatedConstant, Add->op_begin(), + Add->getNumOperands(), NewScale, SE); } else { // A multiplication of a constant with some other value. Update // the map. @@ -2396,10 +2401,10 @@ // We're trying to construct a SCEV of type `Type' with `Ops' as operands and // `OldFlags' as can't-wrap behavior. Infer a more aggressive set of // can't-overflow flags for the operation if possible. -static SCEV::NoWrapFlags -StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, - const ArrayRef Ops, - SCEV::NoWrapFlags Flags) { +static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, + SCEVTypes Type, + const ArrayRef Ops, + SCEV::NoWrapFlags Flags) { using namespace std::placeholders; using OBO = OverflowingBinaryOperator; @@ -2490,7 +2495,8 @@ assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) && "only nuw or nsw allowed"); assert(!Ops.empty() && "Cannot get empty add!"); - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) + return Ops[0]; #ifndef NDEBUG Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); for (unsigned i = 1, e = Ops.size(); i != e; ++i) @@ -2512,8 +2518,9 @@ while (const SCEVConstant *RHSC = dyn_cast(Ops[Idx])) { // We found two constants, fold them together! Ops[0] = getConstant(LHSC->getAPInt() + RHSC->getAPInt()); - if (Ops.size() == 2) return Ops[0]; - Ops.erase(Ops.begin()+1); // Erase the folded element + if (Ops.size() == 2) + return Ops[0]; + Ops.erase(Ops.begin() + 1); // Erase the folded element LHSC = cast(Ops[0]); } @@ -2523,7 +2530,8 @@ --Idx; } - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) + return Ops[0]; } // Delay expensive flag strengthening until necessary. @@ -2548,11 +2556,11 @@ // sorted the list, these values are required to be adjacent. Type *Ty = Ops[0]->getType(); bool FoundMatch = false; - for (unsigned i = 0, e = Ops.size(); i != e-1; ++i) - if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 + for (unsigned i = 0, e = Ops.size(); i != e - 1; ++i) + if (Ops[i] == Ops[i + 1]) { // X + Y + Y --> X + Y*2 // Scan ahead to count how many equal operands there are. unsigned Count = 2; - while (i+Count != e && Ops[i+Count] == Ops[i]) + while (i + Count != e && Ops[i + Count] == Ops[i]) ++Count; // Merge the values into a multiply. const SCEV *Scale = getConstant(Ty, Count); @@ -2560,8 +2568,9 @@ if (Ops.size() == Count) return Mul; Ops[i] = Mul; - Ops.erase(Ops.begin()+i+1, Ops.begin()+i+Count); - --i; e -= Count - 1; + Ops.erase(Ops.begin() + i + 1, Ops.begin() + i + Count); + --i; + e -= Count - 1; FoundMatch = true; } if (FoundMatch) @@ -2603,7 +2612,7 @@ SmallVector LargeMulOps; for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) { if (const SCEVTruncateExpr *T = - dyn_cast(M->getOperand(j))) { + dyn_cast(M->getOperand(j))) { if (T->getOperand()->getType() != SrcType) { Ok = false; break; @@ -2617,7 +2626,8 @@ } } if (Ok) - LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1)); + LargeOps.push_back( + getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1)); } else { Ok = false; break; @@ -2701,7 +2711,7 @@ break; // If we have an add, expand the add operands onto the end of the operands // list. - Ops.erase(Ops.begin()+Idx); + Ops.erase(Ops.begin() + Idx); Ops.append(Add->op_begin(), Add->op_end()); DeletedAdd = true; CommonFlags = maskFlags(CommonFlags, Add->getNoWrapFlags()); @@ -2725,9 +2735,8 @@ DenseMap M; SmallVector NewOps; APInt AccumulatedConstant(BitWidth, 0); - if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant, - Ops.data(), Ops.size(), - APInt(BitWidth, 1), *this)) { + if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant, Ops.data(), + Ops.size(), APInt(BitWidth, 1), *this)) { struct APIntCompare { bool operator()(const APInt &LHS, const APInt &RHS) const { return LHS.ult(RHS); @@ -2748,10 +2757,10 @@ if (MulOp.first == 1) { Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1)); } else if (MulOp.first != 0) { - Ops.push_back(getMulExpr( - getConstant(MulOp.first), - getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1), - SCEV::FlagAnyWrap, Depth + 1)); + Ops.push_back( + getMulExpr(getConstant(MulOp.first), + getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1), + SCEV::FlagAnyWrap, Depth + 1)); } } if (Ops.empty()) @@ -2779,49 +2788,51 @@ // If the multiply has more than two operands, we must get the // Y*Z term. SmallVector MulOps(Mul->op_begin(), - Mul->op_begin()+MulOp); - MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end()); + Mul->op_begin() + MulOp); + MulOps.append(Mul->op_begin() + MulOp + 1, Mul->op_end()); InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); } SmallVector TwoOps = {getOne(Ty), InnerMul}; const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); - const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV, - SCEV::FlagAnyWrap, Depth + 1); - if (Ops.size() == 2) return OuterMul; + const SCEV *OuterMul = + getMulExpr(AddOne, MulOpSCEV, SCEV::FlagAnyWrap, Depth + 1); + if (Ops.size() == 2) + return OuterMul; if (AddOp < Idx) { - Ops.erase(Ops.begin()+AddOp); - Ops.erase(Ops.begin()+Idx-1); + Ops.erase(Ops.begin() + AddOp); + Ops.erase(Ops.begin() + Idx - 1); } else { - Ops.erase(Ops.begin()+Idx); - Ops.erase(Ops.begin()+AddOp-1); + Ops.erase(Ops.begin() + Idx); + Ops.erase(Ops.begin() + AddOp - 1); } Ops.push_back(OuterMul); return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); } // Check this multiply against other multiplies being added together. - for (unsigned OtherMulIdx = Idx+1; + for (unsigned OtherMulIdx = Idx + 1; OtherMulIdx < Ops.size() && isa(Ops[OtherMulIdx]); ++OtherMulIdx) { const SCEVMulExpr *OtherMul = cast(Ops[OtherMulIdx]); // If MulOp occurs in OtherMul, we can fold the two multiplies // together. - for (unsigned OMulOp = 0, e = OtherMul->getNumOperands(); - OMulOp != e; ++OMulOp) + for (unsigned OMulOp = 0, e = OtherMul->getNumOperands(); OMulOp != e; + ++OMulOp) if (OtherMul->getOperand(OMulOp) == MulOpSCEV) { // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E)) const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0); if (Mul->getNumOperands() != 2) { SmallVector MulOps(Mul->op_begin(), - Mul->op_begin()+MulOp); - MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end()); + Mul->op_begin() + MulOp); + MulOps.append(Mul->op_begin() + MulOp + 1, Mul->op_end()); InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); } const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0); if (OtherMul->getNumOperands() != 2) { - SmallVector MulOps(OtherMul->op_begin(), - OtherMul->op_begin()+OMulOp); - MulOps.append(OtherMul->op_begin()+OMulOp+1, OtherMul->op_end()); + SmallVector MulOps( + OtherMul->op_begin(), OtherMul->op_begin() + OMulOp); + MulOps.append(OtherMul->op_begin() + OMulOp + 1, + OtherMul->op_end()); InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); } SmallVector TwoOps = {InnerMul1, InnerMul2}; @@ -2829,9 +2840,10 @@ getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum, SCEV::FlagAnyWrap, Depth + 1); - if (Ops.size() == 2) return OuterMul; - Ops.erase(Ops.begin()+Idx); - Ops.erase(Ops.begin()+OtherMulIdx-1); + if (Ops.size() == 2) + return OuterMul; + Ops.erase(Ops.begin() + Idx); + Ops.erase(Ops.begin() + OtherMulIdx - 1); Ops.push_back(OuterMul); return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); } @@ -2855,8 +2867,9 @@ for (unsigned i = 0, e = Ops.size(); i != e; ++i) if (isAvailableAtLoopEntry(Ops[i], AddRecLoop)) { LIOps.push_back(Ops[i]); - Ops.erase(Ops.begin()+i); - --i; --e; + Ops.erase(Ops.begin() + i); + --i; + --e; } // If we found some loop invariants, fold them into the recurrence. @@ -2899,7 +2912,8 @@ const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags); // If all of the other operands were loop invariant, we are done. - if (Ops.size() == 1) return NewRec; + if (Ops.size() == 1) + return NewRec; // Otherwise, add the folded AddRec by the non-invariant parts. for (unsigned i = 0;; ++i) @@ -2913,15 +2927,15 @@ // Okay, if there weren't any loop invariants to be folded, check to see if // there are multiple AddRec's with the same loop induction variable being // added together. If so, we can fold them. - for (unsigned OtherIdx = Idx+1; + for (unsigned OtherIdx = Idx + 1; OtherIdx < Ops.size() && isa(Ops[OtherIdx]); ++OtherIdx) { // We expect the AddRecExpr's to be sorted in reverse dominance order, // so that the 1st found AddRecExpr is dominated by all others. assert(DT.dominates( - cast(Ops[OtherIdx])->getLoop()->getHeader(), - AddRec->getLoop()->getHeader()) && - "AddRecExprs are not sorted in reverse dominance order?"); + cast(Ops[OtherIdx])->getLoop()->getHeader(), + AddRec->getLoop()->getHeader()) && + "AddRecExprs are not sorted in reverse dominance order?"); if (AddRecLoop == cast(Ops[OtherIdx])->getLoop()) { // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} SmallVector AddRecOps(AddRec->operands()); @@ -2929,10 +2943,10 @@ ++OtherIdx) { const auto *OtherAddRec = cast(Ops[OtherIdx]); if (OtherAddRec->getLoop() == AddRecLoop) { - for (unsigned i = 0, e = OtherAddRec->getNumOperands(); - i != e; ++i) { + for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; + ++i) { if (i >= AddRecOps.size()) { - AddRecOps.append(OtherAddRec->op_begin()+i, + AddRecOps.append(OtherAddRec->op_begin() + i, OtherAddRec->op_end()); break; } @@ -2940,7 +2954,8 @@ AddRecOps[i], OtherAddRec->getOperand(i)}; AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); } - Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; + Ops.erase(Ops.begin() + OtherIdx); + --OtherIdx; } } // Step size has changed, so we cannot guarantee no self-wraparound. @@ -2958,9 +2973,8 @@ return getOrCreateAddExpr(Ops, ComputeFlags(Ops)); } -const SCEV * -ScalarEvolution::getOrCreateAddExpr(ArrayRef Ops, - SCEV::NoWrapFlags Flags) { +const SCEV *ScalarEvolution::getOrCreateAddExpr(ArrayRef Ops, + SCEV::NoWrapFlags Flags) { FoldingSetNodeID ID; ID.AddInteger(scAddExpr); for (const SCEV *Op : Ops) @@ -2980,9 +2994,9 @@ return S; } -const SCEV * -ScalarEvolution::getOrCreateAddRecExpr(ArrayRef Ops, - const Loop *L, SCEV::NoWrapFlags Flags) { +const SCEV *ScalarEvolution::getOrCreateAddRecExpr(ArrayRef Ops, + const Loop *L, + SCEV::NoWrapFlags Flags) { FoldingSetNodeID ID; ID.AddInteger(scAddRecExpr); for (const SCEV *Op : Ops) @@ -3004,21 +3018,20 @@ return S; } -const SCEV * -ScalarEvolution::getOrCreateMulExpr(ArrayRef Ops, - SCEV::NoWrapFlags Flags) { +const SCEV *ScalarEvolution::getOrCreateMulExpr(ArrayRef Ops, + SCEV::NoWrapFlags Flags) { FoldingSetNodeID ID; ID.AddInteger(scMulExpr); for (const SCEV *Op : Ops) ID.AddPointer(Op); void *IP = nullptr; SCEVMulExpr *S = - static_cast(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)); + static_cast(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)); if (!S) { const SCEV **O = SCEVAllocator.Allocate(Ops.size()); std::uninitialized_copy(Ops.begin(), Ops.end(), O); - S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator), - O, Ops.size()); + S = new (SCEVAllocator) + SCEVMulExpr(ID.Intern(SCEVAllocator), O, Ops.size()); UniqueSCEVs.InsertNode(S, IP); registerUser(S, Ops); } @@ -3027,8 +3040,9 @@ } static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) { - uint64_t k = i*j; - if (j > 1 && k / j != i) Overflow = true; + uint64_t k = i * j; + if (j > 1 && k / j != i) + Overflow = true; return k; } @@ -3044,15 +3058,17 @@ // intermediate computations. However, we can still overflow even when the // final result would fit. - if (n == 0 || n == k) return 1; - if (k > n) return 0; + if (n == 0 || n == k) + return 1; + if (k > n) + return 0; - if (k > n/2) - k = n-k; + if (k > n / 2) + k = n - k; uint64_t r = 1; for (uint64_t i = 1; i <= k; ++i) { - r = umul_ov(r, n-(i-1), Overflow); + r = umul_ov(r, n - (i - 1), Overflow); r /= i; } return r; @@ -3069,9 +3085,7 @@ return isa(S) || isa(S); } - bool isDone() const { - return FoundConstant; - } + bool isDone() const { return FoundConstant; } }; FindConstantInAddMulChain F; @@ -3087,7 +3101,8 @@ assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) && "only nuw or nsw allowed"); assert(!Ops.empty() && "Cannot get empty mul!"); - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) + return Ops[0]; #ifndef NDEBUG Type *ETy = Ops[0]->getType(); assert(!ETy->isPointerTy()); @@ -3107,8 +3122,9 @@ while (const SCEVConstant *RHSC = dyn_cast(Ops[Idx])) { // We found two constants, fold them together! Ops[0] = getConstant(LHSC->getAPInt() * RHSC->getAPInt()); - if (Ops.size() == 2) return Ops[0]; - Ops.erase(Ops.begin()+1); // Erase the folded element + if (Ops.size() == 2) + return Ops[0]; + Ops.erase(Ops.begin() + 1); // Erase the folded element LHSC = cast(Ops[0]); } @@ -3168,9 +3184,10 @@ SmallVector NewOps; bool AnyFolded = false; for (const SCEV *AddOp : Add->operands()) { - const SCEV *Mul = getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap, - Depth + 1); - if (!isa(Mul)) AnyFolded = true; + const SCEV *Mul = + getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap, Depth + 1); + if (!isa(Mul)) + AnyFolded = true; NewOps.push_back(Mul); } if (AnyFolded) @@ -3179,8 +3196,8 @@ // Negation preserves a recurrence's no self-wrap property. SmallVector Operands; for (const SCEV *AddRecOp : AddRec->operands()) - Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap, - Depth + 1)); + Operands.push_back( + getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap, Depth + 1)); return getAddRecExpr(Operands, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW)); @@ -3201,7 +3218,7 @@ break; // If we have an mul, expand the mul operands onto the end of the // operands list. - Ops.erase(Ops.begin()+Idx); + Ops.erase(Ops.begin() + Idx); Ops.append(Mul->op_begin(), Mul->op_end()); DeletedMul = true; } @@ -3229,8 +3246,9 @@ for (unsigned i = 0, e = Ops.size(); i != e; ++i) if (isAvailableAtLoopEntry(Ops[i], AddRecLoop)) { LIOps.push_back(Ops[i]); - Ops.erase(Ops.begin()+i); - --i; --e; + Ops.erase(Ops.begin() + i); + --i; + --e; } // If we found some loop invariants, fold them into the recurrence. @@ -3249,11 +3267,12 @@ // No self-wrap cannot be guaranteed after changing the step size, but // will be inferred if either NUW or NSW is true. SCEV::NoWrapFlags Flags = ComputeFlags({Scale, AddRec}); - const SCEV *NewRec = getAddRecExpr( - NewOps, AddRecLoop, AddRec->getNoWrapFlags(Flags)); + const SCEV *NewRec = + getAddRecExpr(NewOps, AddRecLoop, AddRec->getNoWrapFlags(Flags)); // If all of the other operands were loop invariant, we are done. - if (Ops.size() == 1) return NewRec; + if (Ops.size() == 1) + return NewRec; // Otherwise, multiply the folded AddRec by the non-invariant parts. for (unsigned i = 0;; ++i) @@ -3279,40 +3298,42 @@ // addrec's are of different length (mathematically, it's equivalent to // an infinite stream of zeros on the right). bool OpsModified = false; - for (unsigned OtherIdx = Idx+1; + for (unsigned OtherIdx = Idx + 1; OtherIdx != Ops.size() && isa(Ops[OtherIdx]); ++OtherIdx) { const SCEVAddRecExpr *OtherAddRec = - dyn_cast(Ops[OtherIdx]); + dyn_cast(Ops[OtherIdx]); if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop) continue; // Limit max number of arguments to avoid creation of unreasonably big // SCEVAddRecs with very complex operands. if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 > - MaxAddRecSize || hasHugeExpression({AddRec, OtherAddRec})) + MaxAddRecSize || + hasHugeExpression({AddRec, OtherAddRec})) continue; bool Overflow = false; Type *Ty = AddRec->getType(); bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64; - SmallVector AddRecOps; + SmallVector AddRecOps; for (int x = 0, xe = AddRec->getNumOperands() + - OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) { - SmallVector SumOps; - for (int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) { - uint64_t Coeff1 = Choose(x, 2*x - y, Overflow); - for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1), - ze = std::min(x+1, (int)OtherAddRec->getNumOperands()); + OtherAddRec->getNumOperands() - 1; + x != xe && !Overflow; ++x) { + SmallVector SumOps; + for (int y = x, ye = 2 * x + 1; y != ye && !Overflow; ++y) { + uint64_t Coeff1 = Choose(x, 2 * x - y, Overflow); + for (int z = std::max(y - x, y - (int)AddRec->getNumOperands() + 1), + ze = std::min(x + 1, (int)OtherAddRec->getNumOperands()); z < ze && !Overflow; ++z) { - uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow); + uint64_t Coeff2 = Choose(2 * x - y, x - z, Overflow); uint64_t Coeff; if (LargerThan64Bits) Coeff = umul_ov(Coeff1, Coeff2, Overflow); else - Coeff = Coeff1*Coeff2; + Coeff = Coeff1 * Coeff2; const SCEV *CoeffTerm = getConstant(Ty, Coeff); - const SCEV *Term1 = AddRec->getOperand(y-z); + const SCEV *Term1 = AddRec->getOperand(y - z); const SCEV *Term2 = OtherAddRec->getOperand(z); SumOps.push_back(getMulExpr(CoeffTerm, Term1, Term2, SCEV::FlagAnyWrap, Depth + 1)); @@ -3323,11 +3344,13 @@ AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1)); } if (!Overflow) { - const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRecLoop, - SCEV::FlagAnyWrap); - if (Ops.size() == 2) return NewAddRec; + const SCEV *NewAddRec = + getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap); + if (Ops.size() == 2) + return NewAddRec; Ops[Idx] = NewAddRec; - Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; + Ops.erase(Ops.begin() + OtherIdx); + --OtherIdx; OpsModified = true; AddRec = dyn_cast(NewAddRec); if (!AddRec) @@ -3347,10 +3370,9 @@ } /// Represents an unsigned remainder expression based on unsigned division. -const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS, - const SCEV *RHS) { +const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS, const SCEV *RHS) { assert(getEffectiveSCEVType(LHS->getType()) == - getEffectiveSCEVType(RHS->getType()) && + getEffectiveSCEVType(RHS->getType()) && "SCEVURemExpr operand types don't match!"); // Short-circuit easy cases @@ -3376,8 +3398,7 @@ /// Get a canonical unsigned division expression, or something simpler if /// possible. -const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, - const SCEV *RHS) { +const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, const SCEV *RHS) { assert(!LHS->getType()->isPointerTy() && "SCEVUDivExpr operand can't be pointer!"); assert(LHS->getType() == RHS->getType() && @@ -3398,7 +3419,7 @@ if (const SCEVConstant *RHSC = dyn_cast(RHS)) { if (RHSC->getValue()->isOne()) - return LHS; // X udiv 1 --> x + return LHS; // X udiv 1 --> x // If the denominator is zero, the result of the udiv is undefined. Don't // try to analyze it, because the resolution chosen here may differ from // the resolution chosen in other parts of the compiler. @@ -3414,18 +3435,18 @@ if (!RHSC->getAPInt().isPowerOf2()) ++MaxShiftAmt; IntegerType *ExtTy = - IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt); + IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt); if (const SCEVAddRecExpr *AR = dyn_cast(LHS)) if (const SCEVConstant *Step = - dyn_cast(AR->getStepRecurrence(*this))) { + dyn_cast(AR->getStepRecurrence(*this))) { // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded. const APInt &StepInt = Step->getAPInt(); const APInt &DivInt = RHSC->getAPInt(); if (!StepInt.urem(DivInt) && getZeroExtendExpr(AR, ExtTy) == - getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), - getZeroExtendExpr(Step, ExtTy), - AR->getLoop(), SCEV::FlagAnyWrap)) { + getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), + getZeroExtendExpr(Step, ExtTy), AR->getLoop(), + SCEV::FlagAnyWrap)) { SmallVector Operands; for (const SCEV *Op : AR->operands()) Operands.push_back(getUDivExpr(Op, RHS)); @@ -3437,9 +3458,9 @@ const SCEVConstant *StartC = dyn_cast(AR->getStart()); if (StartC && !DivInt.urem(StepInt) && getZeroExtendExpr(AR, ExtTy) == - getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), - getZeroExtendExpr(Step, ExtTy), - AR->getLoop(), SCEV::FlagAnyWrap)) { + getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), + getZeroExtendExpr(Step, ExtTy), AR->getLoop(), + SCEV::FlagAnyWrap)) { const APInt &StartInt = StartC->getAPInt(); const APInt &StartRem = StartInt.urem(StepInt); if (StartRem != 0) { @@ -3522,9 +3543,10 @@ // The Insertion Point (IP) might be invalid by now (due to UniqueSCEVs // changes). Make sure we get a new one. IP = nullptr; - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator), - LHS, RHS); + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) + return S; + SCEV *S = + new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator), LHS, RHS); UniqueSCEVs.InsertNode(S, IP); registerUser(S, {LHS, RHS}); return S; @@ -3622,7 +3644,8 @@ const SCEV * ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, const Loop *L, SCEV::NoWrapFlags Flags) { - if (Operands.size() == 1) return Operands[0]; + if (Operands.size() == 1) + return Operands[0]; #ifndef NDEBUG Type *ETy = getEffectiveSCEVType(Operands[0]->getType()); for (unsigned i = 1, e = Operands.size(); i != e; ++i) { @@ -3640,8 +3663,8 @@ return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X } - // It's tempting to want to call getConstantMaxBackedgeTakenCount count here and - // use that information to infer NUW and NSW flags. However, computing a + // It's tempting to want to call getConstantMaxBackedgeTakenCount count here + // and use that information to infer NUW and NSW flags. However, computing a // BE count requires calling getAddRecExpr, so we may not yet have a // meaningful BE count at this point (and if we don't, we'd be stuck // with a SCEVCouldNotCompute as the cached BE count). @@ -3669,7 +3692,7 @@ // The outer recurrence keeps its NW flag but only keeps NUW/NSW if the // inner recurrence has the same property. SCEV::NoWrapFlags OuterFlags = - maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags()); + maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags()); NestedOperands[0] = getAddRecExpr(Operands, L, OuterFlags); AllInvariant = all_of(NestedOperands, [&](const SCEV *Op) { @@ -3682,7 +3705,7 @@ // The inner recurrence keeps its NW flag but only keeps NUW/NSW if // the outer recurrence has the same property. SCEV::NoWrapFlags InnerFlags = - maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags); + maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags); return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags); } } @@ -3717,7 +3740,7 @@ }(); SCEV::NoWrapFlags OffsetWrap = - AssumeInBoundsFlags ? SCEV::FlagNSW : SCEV::FlagAnyWrap; + AssumeInBoundsFlags ? SCEV::FlagNSW : SCEV::FlagAnyWrap; Type *CurTy = GEP->getType(); bool FirstIter = true; @@ -3764,7 +3787,8 @@ // base address is unsigned. However, if we know that the offset is // non-negative, we can use nuw. SCEV::NoWrapFlags BaseWrap = AssumeInBoundsFlags && isKnownNonNegative(Offset) - ? SCEV::FlagNUW : SCEV::FlagAnyWrap; + ? SCEV::FlagNUW + : SCEV::FlagAnyWrap; auto *GEPExpr = getAddExpr(BaseExpr, Offset, BaseWrap); assert(BaseExpr->getType() == GEPExpr->getType() && "GEP should not change type mid-flight."); @@ -3790,7 +3814,8 @@ SmallVectorImpl &Ops) { assert(SCEVMinMaxExpr::isMinMaxType(Kind) && "Not a SCEVMinMaxExpr!"); assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!"); - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) + return Ops[0]; #ifndef NDEBUG Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); for (unsigned i = 1, e = Ops.size(); i != e; ++i) { @@ -3835,8 +3860,9 @@ ConstantInt *Fold = ConstantInt::get( getContext(), FoldOp(LHSC->getAPInt(), RHSC->getAPInt())); Ops[0] = getConstant(Fold); - Ops.erase(Ops.begin()+1); // Erase the folded element - if (Ops.size() == 1) return Ops[0]; + Ops.erase(Ops.begin() + 1); // Erase the folded element + if (Ops.size() == 1) + return Ops[0]; LHSC = cast(Ops[0]); } @@ -3853,7 +3879,8 @@ return LHSC; } - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) + return Ops[0]; } // Find the first operation of the same kind @@ -3866,7 +3893,7 @@ bool DeletedAny = false; while (Ops[Idx]->getSCEVType() == Kind) { const SCEVMinMaxExpr *SMME = cast(Ops[Idx]); - Ops.erase(Ops.begin()+Idx); + Ops.erase(Ops.begin() + Idx); Ops.append(SMME->op_begin(), SMME->op_end()); DeletedAny = true; } @@ -3901,7 +3928,8 @@ } } - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) + return Ops[0]; assert(!Ops.empty() && "Reduced smax down to nothing!"); @@ -4227,9 +4255,8 @@ return getMinMaxExpr(scUMaxExpr, Ops); } -const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, - const SCEV *RHS) { - SmallVector Ops = { LHS, RHS }; +const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, const SCEV *RHS) { + SmallVector Ops = {LHS, RHS}; return getSMinExpr(Ops); } @@ -4239,7 +4266,7 @@ const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential) { - SmallVector Ops = { LHS, RHS }; + SmallVector Ops = {LHS, RHS}; return getUMinExpr(Ops, Sequential); } @@ -4279,8 +4306,7 @@ return getConstant(IntTy, getDataLayout().getTypeStoreSize(StoreTy)); } -const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy, - StructType *STy, +const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo) { // We can bypass creating a target-independent constant expression and then // folding it back into a ConstantInt. This is just a compile-time @@ -4304,8 +4330,8 @@ "Stale SCEVUnknown in uniquing map!"); return S; } - SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this, - FirstUnknown); + SCEV *S = new (SCEVAllocator) + SCEVUnknown(ID.Intern(SCEVAllocator), V, this, FirstUnknown); FirstUnknown = cast(S); UniqueSCEVs.InsertNode(S, IP); return S; @@ -4348,7 +4374,7 @@ } Type *ScalarEvolution::getWiderType(Type *T1, Type *T2) const { - return getTypeSizeInBits(T1) >= getTypeSizeInBits(T2) ? T1 : T2; + return getTypeSizeInBits(T1) >= getTypeSizeInBits(T2) ? T1 : T2; } bool ScalarEvolution::instructionCouldExistWitthOperands(const SCEV *A, @@ -4362,10 +4388,9 @@ // Can't tell. return false; return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) || - DT.dominates(ScopeB, ScopeA); + DT.dominates(ScopeB, ScopeA); } - const SCEV *ScalarEvolution::getCouldNotCompute() { return CouldNotCompute.get(); } @@ -4414,7 +4439,7 @@ if (I != ValueExprMap.end()) { auto EVIt = ExprValueMap.find(I->second); bool Removed = EVIt->second.remove(V); - (void) Removed; + (void)Removed; assert(Removed && "Value not in ExprValueMap?"); ValueExprMap.erase(I); } @@ -4458,8 +4483,7 @@ const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags) { if (const SCEVConstant *VC = dyn_cast(V)) - return getConstant( - cast(ConstantExpr::getNeg(VC->getValue()))); + return getConstant(cast(ConstantExpr::getNeg(VC->getValue()))); Type *Ty = V->getType(); Ty = getEffectiveSCEVType(Ty); @@ -4486,8 +4510,7 @@ assert(!V->getType()->isPointerTy() && "Can't negate pointer"); if (const SCEVConstant *VC = dyn_cast(V)) - return getConstant( - cast(ConstantExpr::getNot(VC->getValue()))); + return getConstant(cast(ConstantExpr::getNot(VC->getValue()))); // Fold ~(u|s)(min|max)(~x, ~y) to (u|s)(max|min)(x, y) if (const SCEVMinMaxExpr *MME = dyn_cast(V)) { @@ -4562,8 +4585,7 @@ // We represent LHS - RHS as LHS + (-1)*RHS. This transformation // makes it so that we cannot make much use of NUW. auto AddFlags = SCEV::FlagAnyWrap; - const bool RHSIsNotMinSigned = - !getSignedRangeMin(RHS).isMinSignedValue(); + const bool RHSIsNotMinSigned = !getSignedRangeMin(RHS).isMinSignedValue(); if (hasFlags(Flags, SCEV::FlagNSW)) { // Let M be the minimum representable signed value. Then (-1)*RHS // signed-wraps if and only if RHS is M. That can happen even for @@ -4597,7 +4619,7 @@ assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot truncate or zero extend with non-integer arguments!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) - return V; // No conversion + return V; // No conversion if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) return getTruncateExpr(V, Ty, Depth); return getZeroExtendExpr(V, Ty, Depth); @@ -4609,57 +4631,53 @@ assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot truncate or zero extend with non-integer arguments!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) - return V; // No conversion + return V; // No conversion if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) return getTruncateExpr(V, Ty, Depth); return getSignExtendExpr(V, Ty, Depth); } -const SCEV * -ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { +const SCEV *ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot noop or zero extend with non-integer arguments!"); assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && "getNoopOrZeroExtend cannot truncate!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) - return V; // No conversion + return V; // No conversion return getZeroExtendExpr(V, Ty); } -const SCEV * -ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { +const SCEV *ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot noop or sign extend with non-integer arguments!"); assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && "getNoopOrSignExtend cannot truncate!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) - return V; // No conversion + return V; // No conversion return getSignExtendExpr(V, Ty); } -const SCEV * -ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { +const SCEV *ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot noop or any extend with non-integer arguments!"); assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && "getNoopOrAnyExtend cannot truncate!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) - return V; // No conversion + return V; // No conversion return getAnyExtendExpr(V, Ty); } -const SCEV * -ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { +const SCEV *ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot truncate or noop with non-integer arguments!"); assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) && "getTruncateOrNoop cannot extend!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) - return V; // No conversion + return V; // No conversion return getTruncateExpr(V, Ty); } @@ -4679,7 +4697,7 @@ const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential) { - SmallVector Ops = { LHS, RHS }; + SmallVector Ops = {LHS, RHS}; return getUMinFromMismatchedTypes(Ops, Sequential); } @@ -4797,12 +4815,12 @@ /// If SCEV contains non-invariant unknown SCEV rewrite cannot be done. class SCEVPostIncRewriter : public SCEVRewriteVisitor { public: - static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE) { + static const SCEV *rewrite(const SCEV *S, const Loop *L, + ScalarEvolution &SE) { SCEVPostIncRewriter Rewriter(L, SE); const SCEV *Result = Rewriter.visit(S); - return Rewriter.hasSeenLoopVariantSCEVUnknown() - ? SE.getCouldNotCompute() - : Result; + return Rewriter.hasSeenLoopVariantSCEVUnknown() ? SE.getCouldNotCompute() + : Result; } const SCEV *visitUnknown(const SCEVUnknown *Expr) { @@ -5023,8 +5041,7 @@ // start value and the backedge is guarded by a comparison with the post-inc // value, the addrec is safe. ICmpInst::Predicate Pred; - const SCEV *OverflowLimit = - getSignedOverflowLimitForStep(Step, &Pred, this); + const SCEV *OverflowLimit = getSignedOverflowLimitForStep(Step, &Pred, this); if (OverflowLimit && (isLoopBackedgeGuardedByCond(L, Pred, AR, OverflowLimit) || isKnownOnEveryIteration(Pred, AR, OverflowLimit))) { @@ -5077,8 +5094,8 @@ // start value and the backedge is guarded by a comparison with the post-inc // value, the addrec is safe. if (isKnownPositive(Step)) { - const SCEV *N = getConstant(APInt::getMinValue(BitWidth) - - getUnsignedRangeMax(Step)); + const SCEV *N = + getConstant(APInt::getMinValue(BitWidth) - getUnsignedRangeMax(Step)); if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) || isKnownOnEveryIteration(ICmpInst::ICMP_ULT, AR, N)) { Result = setFlags(Result, SCEV::FlagNUW); @@ -5145,7 +5162,8 @@ case Instruction::Xor: if (auto *RHSC = dyn_cast(Op->getOperand(1))) // If the RHS of the xor is a signmask, then this is just an add. - // Instcombine turns add of signmask into xor as a strength reduction step. + // Instcombine turns add of signmask into xor as a strength reduction + // step. if (RHSC->getValue().isSignMask()) return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1)); // Binary `xor` is a bit-wise `add`. @@ -5285,9 +5303,10 @@ // will return the pair {NewAddRec, SmallPredsVec} where: // NewAddRec = {%Start,+,%Step} // SmallPredsVec = {P1, P2, P3} as follows: -// P1(WrapPred): AR: {trunc(%Start),+,(trunc %Step)} Flags: -// P2(EqualPred): %Start == (sext i32 (trunc i64 %Start to i32) to i64) -// P3(EqualPred): %Step == (sext i32 (trunc i64 %Step to i32) to i64) +// P1(WrapPred): AR: {trunc(%Start),+,(trunc %Step)} Flags: +// P2(EqualPred): %Start == (sext i32 (trunc i64 %Start to i32) +// to i64) P3(EqualPred): %Step == (sext i32 (trunc i64 %Step to i32) +// to i64) // The returned pair means that SymbolicPHI can be rewritten into NewAddRec // under the predicates {P1,P2,P3}. // This predicated rewrite will be cached in PredicatedSCEVRewrites: @@ -5316,7 +5335,8 @@ // // 3) Outline common code with createAddRecFromPHI to avoid duplication. Optional>> -ScalarEvolution::createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI) { +ScalarEvolution::createAddRecFromPHIWithCastsImpl( + const SCEVUnknown *SymbolicPHI) { SmallVector Predicates; // *** Part1: Analyze if we have a phi-with-cast pattern for which we can @@ -5549,7 +5569,7 @@ } Optional>> - Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI); + Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI); // Record in the cache that the analysis failed if (!Rewrite) { @@ -5771,8 +5791,7 @@ // PHI(f(0), f({1,+,1})) --> f({0,+,1}) const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *this); const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *this, false); - if (Shifted != getCouldNotCompute() && - Start != getCouldNotCompute()) { + if (Shifted != getCouldNotCompute() && Start != getCouldNotCompute()) { const SCEV *StartVal = getSCEV(StartValueV); if (Start == StartVal) { // Okay, for the entire analysis of this edge we assumed the PHI @@ -5802,12 +5821,12 @@ bool TraversalDone = false; bool Available = true; - const Loop *L = nullptr; // The loop BB is in (can be nullptr) + const Loop *L = nullptr; // The loop BB is in (can be nullptr) BasicBlock *BB = nullptr; DominatorTree &DT; CheckAvailable(const Loop *L, BasicBlock *BB, DominatorTree &DT) - : L(L), BB(BB), DT(DT) {} + : L(L), BB(BB), DT(DT) {} bool setUnavailable() { TraversalDone = true; @@ -5911,8 +5930,9 @@ } const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) { - auto IsReachable = - [&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); }; + auto IsReachable = [&](BasicBlock *BB) { + return DT.isReachableFromEntry(BB); + }; if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) { const Loop *L = LI.getLoopFor(PN->getParent()); @@ -6269,7 +6289,8 @@ if (const SCEVUnknown *U = dyn_cast(S)) { // For a SCEVUnknown, ask ValueTracking. - KnownBits Known = computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT); + KnownBits Known = + computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT); return Known.countMinTrailingZeros(); } @@ -6306,8 +6327,8 @@ } } -ConstantRange ScalarEvolution:: -getRangeForUnknownRecurrence(const SCEVUnknown *U) { +ConstantRange +ScalarEvolution::getRangeForUnknownRecurrence(const SCEVUnknown *U) { const DataLayout &DL = getDataLayout(); unsigned BitWidth = getTypeSizeInBits(U->getType()); @@ -6374,7 +6395,7 @@ // Compute total shift amount, being careful of overflow and bitwidths. auto MaxShiftAmt = KnownStep.getMaxValue(); - APInt TCAP(BitWidth, TC-1); + APInt TCAP(BitWidth, TC - 1); bool Overflow = false; auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow); if (Overflow) @@ -6389,8 +6410,8 @@ // saturation => 0 or -1 // other => a value closer to zero (of the same sign) // Thus, the end value is closer to zero than the start. - auto KnownEnd = KnownBits::ashr(KnownStart, - KnownBits::makeConstant(TotalShift)); + auto KnownEnd = + KnownBits::ashr(KnownStart, KnownBits::makeConstant(TotalShift)); if (KnownStart.isNonNegative()) // Analogous to lshr (simply not yet canonicalized) return ConstantRange::getNonEmpty(KnownEnd.getMinValue(), @@ -6407,15 +6428,15 @@ // saturation => 0 // other => a smaller positive number // Thus, the low end of the unsigned range is the last value produced. - auto KnownEnd = KnownBits::lshr(KnownStart, - KnownBits::makeConstant(TotalShift)); + auto KnownEnd = + KnownBits::lshr(KnownStart, KnownBits::makeConstant(TotalShift)); return ConstantRange::getNonEmpty(KnownEnd.getMinValue(), KnownStart.getMaxValue() + 1); } case Instruction::Shl: { // Iff no bits are shifted out, value increases on every shift. - auto KnownEnd = KnownBits::shl(KnownStart, - KnownBits::makeConstant(TotalShift)); + auto KnownEnd = + KnownBits::shl(KnownStart, KnownBits::makeConstant(TotalShift)); if (TotalShift.ult(KnownStart.countMinLeadingZeros())) return ConstantRange(KnownStart.getMinValue(), KnownEnd.getMaxValue() + 1); @@ -6435,8 +6456,8 @@ SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; ConstantRange::PreferredRangeType RangeType = - SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED - ? ConstantRange::Unsigned : ConstantRange::Signed; + SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? ConstantRange::Unsigned + : ConstantRange::Signed; // See if we've computed this range already. DenseMap::iterator I = Cache.find(S); @@ -6472,8 +6493,8 @@ if (Add->hasNoUnsignedWrap()) WrapType |= OBO::NoUnsignedWrap; for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) - X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), - WrapType, RangeType); + X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), WrapType, + RangeType); return setRange(Add, SignHint, ConservativeResult.intersectWith(X, RangeType)); } @@ -6523,16 +6544,16 @@ if (const SCEVZeroExtendExpr *ZExt = dyn_cast(S)) { ConstantRange X = getRangeRef(ZExt->getOperand(), SignHint); - return setRange(ZExt, SignHint, - ConservativeResult.intersectWith(X.zeroExtend(BitWidth), - RangeType)); + return setRange( + ZExt, SignHint, + ConservativeResult.intersectWith(X.zeroExtend(BitWidth), RangeType)); } if (const SCEVSignExtendExpr *SExt = dyn_cast(S)) { ConstantRange X = getRangeRef(SExt->getOperand(), SignHint); - return setRange(SExt, SignHint, - ConservativeResult.intersectWith(X.signExtend(BitWidth), - RangeType)); + return setRange( + SExt, SignHint, + ConservativeResult.intersectWith(X.signExtend(BitWidth), RangeType)); } if (const SCEVPtrToIntExpr *PtrToInt = dyn_cast(S)) { @@ -6542,9 +6563,9 @@ if (const SCEVTruncateExpr *Trunc = dyn_cast(S)) { ConstantRange X = getRangeRef(Trunc->getOperand(), SignHint); - return setRange(Trunc, SignHint, - ConservativeResult.intersectWith(X.truncate(BitWidth), - RangeType)); + return setRange( + Trunc, SignHint, + ConservativeResult.intersectWith(X.truncate(BitWidth), RangeType)); } if (const SCEVAddRecExpr *AddRec = dyn_cast(S)) { @@ -6578,15 +6599,16 @@ RangeType); else if (AllNonPos) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange::getNonEmpty( - APInt::getSignedMinValue(BitWidth), - getSignedRangeMax(AddRec->getStart()) + 1), + ConstantRange::getNonEmpty(APInt::getSignedMinValue(BitWidth), + getSignedRangeMax(AddRec->getStart()) + + 1), RangeType); } // TODO: non-affine addrec if (AddRec->isAffine()) { - const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(AddRec->getLoop()); + const SCEV *MaxBECount = + getConstantMaxBackedgeTakenCount(AddRec->getLoop()); if (!isa(MaxBECount) && getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) { auto RangeFromAffine = getRangeForAffineAR( @@ -6686,7 +6708,7 @@ ConservativeResult.intersectWith(RangeFromOps, RangeType); bool Erased = PendingPhiRanges.erase(Phi); assert(Erased && "Failed to erase Phi properly?"); - (void) Erased; + (void)Erased; } } @@ -6793,8 +6815,8 @@ // Next, consider step unsigned. ConstantRange UR = getRangeForAffineARHelper( - getUnsignedRangeMax(Step), getUnsignedRange(Start), - MaxBECountValue, BitWidth, /* Signed = */ false); + getUnsignedRangeMax(Step), getUnsignedRange(Start), MaxBECountValue, + BitWidth, /* Signed = */ false); // Finally, intersect signed and unsigned ranges. return SR.intersectWith(UR, ConstantRange::Smallest); @@ -6854,8 +6876,8 @@ if (RangeBetween.isFullSet()) return RangeBetween; // Only deal with ranges that do not wrap (i.e. RangeMin < RangeMax). - bool IsWrappedSet = IsSigned ? RangeBetween.isSignWrappedSet() - : RangeBetween.isWrappedSet(); + bool IsWrappedSet = + IsSigned ? RangeBetween.isSignWrappedSet() : RangeBetween.isWrappedSet(); if (IsWrappedSet) return ConstantRange::getFull(BitWidth); @@ -6885,8 +6907,7 @@ Optional CastOp; APInt Offset(BitWidth, 0); - assert(SE.getTypeSizeInBits(S->getType()) == BitWidth && - "Should be!"); + assert(SE.getTypeSizeInBits(S->getType()) == BitWidth && "Should be!"); // Peel off a constant offset: if (auto *SA = dyn_cast(S)) { @@ -6984,7 +7005,8 @@ } SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) { - if (isa(V)) return SCEV::FlagAnyWrap; + if (isa(V)) + return SCEV::FlagAnyWrap; const BinaryOperator *BinOp = cast(V); // Return early if there are no flags to propagate to the SCEV. @@ -7090,7 +7112,6 @@ return false; } - bool ScalarEvolution::isSCEVExprNeverPoison(const Instruction *I) { // Only proceed if we can prove that I does not yield poison. if (!programUndefinedIfPoison(I)) @@ -7315,8 +7336,8 @@ // CreateSCEV calls getNoWrapFlagsFromUB, which under certain conditions // requires a SCEV for the LHS. if (NewBO->Op && (NewBO->IsNSW || NewBO->IsNUW)) { - if (auto *I = dyn_cast(NewBO->Op); - I && programUndefinedIfPoison(I)) { + auto *I = dyn_cast(NewBO->Op); + if (I && programUndefinedIfPoison(I)) { Ops.push_back(BO->LHS); break; } @@ -7589,8 +7610,7 @@ unsigned TZ = A.countTrailingZeros(); unsigned BitWidth = A.getBitWidth(); KnownBits Known(BitWidth); - computeKnownBits(BO->LHS, Known, getDataLayout(), - 0, &AC, nullptr, &DT); + computeKnownBits(BO->LHS, Known, getDataLayout(), 0, &AC, nullptr, &DT); APInt EffectiveMask = APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ); @@ -7604,7 +7624,7 @@ unsigned MulZeros = OpC->getAPInt().countTrailingZeros(); unsigned GCD = std::min(MulZeros, TZ); APInt DivAmt = APInt::getOneBitSet(BitWidth, TZ - GCD); - SmallVector MulOps; + SmallVector MulOps; MulOps.push_back(getConstant(OpC->getAPInt().lshr(GCD))); MulOps.append(LHSMul->op_begin() + 1, LHSMul->op_end()); auto *NewMul = getMulExpr(MulOps, LHSMul->getNoWrapFlags()); @@ -7615,7 +7635,8 @@ ShiftedLHS = getUDivExpr(LHS, MulCount); return getMulExpr( getZeroExtendExpr( - getTruncateExpr(ShiftedLHS, + getTruncateExpr( + ShiftedLHS, IntegerType::get(getContext(), BitWidth - LZ - TZ)), BO->LHS->getType()), MulCount); @@ -7756,8 +7777,8 @@ if (L->getOperand(1) == BO->RHS) // For a two-shift sext-inreg, i.e. n = m, // use sext(trunc(x)) as the SCEV expression. - return getSignExtendExpr( - getTruncateExpr(ShlOp0SCEV, TruncTy), OuterTy); + return getSignExtendExpr(getTruncateExpr(ShlOp0SCEV, TruncTy), + OuterTy); ConstantInt *ShlAmtCI = dyn_cast(L->getOperand(1)); if (ShlAmtCI && ShlAmtCI->getValue().ult(BitWidth)) { @@ -7767,11 +7788,12 @@ // expression. We already checked that ShlAmt < BitWidth, so // the multiplier, 1 << (ShlAmt - AShrAmt), fits into TruncTy as // ShlAmt - AShrAmt < Amt. - APInt Mul = APInt::getOneBitSet(BitWidth - AShrAmt, - ShlAmt - AShrAmt); + APInt Mul = + APInt::getOneBitSet(BitWidth - AShrAmt, ShlAmt - AShrAmt); return getSignExtendExpr( getMulExpr(getTruncateExpr(ShlOp0SCEV, TruncTy), - getConstant(Mul)), OuterTy); + getConstant(Mul)), + OuterTy); } } } @@ -8159,9 +8181,8 @@ llvm_unreachable("Invalid ExitCountKind!"); } -const SCEV * -ScalarEvolution::getPredicatedBackedgeTakenCount(const Loop *L, - SmallVector &Preds) { +const SCEV *ScalarEvolution::getPredicatedBackedgeTakenCount( + const Loop *L, SmallVector &Preds) { return getPredicatedBackedgeTakenInfo(L).getExact(L, this, &Preds); } @@ -8322,7 +8343,7 @@ auto LoopUsersItr = LoopUsers.find(CurrL); if (LoopUsersItr != LoopUsers.end()) { ToForget.insert(ToForget.end(), LoopUsersItr->second.begin(), - LoopUsersItr->second.end()); + LoopUsersItr->second.end()); } // Drop information about expressions based on loop-header PHIs. @@ -8357,7 +8378,8 @@ void ScalarEvolution::forgetValue(Value *V) { Instruction *I = dyn_cast(V); - if (!I) return; + if (!I) + return; // Drop information about expressions based on loop-header PHIs. SmallVector Worklist; @@ -8369,7 +8391,7 @@ while (!Worklist.empty()) { I = Worklist.pop_back_val(); ValueExprMapType::iterator It = - ValueExprMap.find_as(static_cast(I)); + ValueExprMap.find_as(static_cast(I)); if (It != ValueExprMap.end()) { eraseValueFromMap(It->first); ToForget.push_back(It->second); @@ -8392,9 +8414,9 @@ /// is never skipped. This is a valid assumption as long as the loop exits via /// that test. For precise results, it is the caller's responsibility to specify /// the relevant loop exiting block using getExact(ExitingBlock, SE). -const SCEV * -ScalarEvolution::BackedgeTakenInfo::getExact(const Loop *L, ScalarEvolution *SE, - SmallVector *Preds) const { +const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact( + const Loop *L, ScalarEvolution *SE, + SmallVector *Preds) const { // If any exits were not computable, the loop is not computable. if (!isComplete() || ExitNotTaken.empty()) return SE->getCouldNotCompute(); @@ -8483,8 +8505,7 @@ } ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E) - : ExitLimit(E, E, false, None) { -} + : ExitLimit(E, E, false, None) {} ScalarEvolution::ExitLimit::ExitLimit( const SCEV *E, const SCEV *M, bool MaxOrZero, @@ -8514,13 +8535,11 @@ ScalarEvolution::ExitLimit::ExitLimit( const SCEV *E, const SCEV *M, bool MaxOrZero, const SmallPtrSetImpl &PredSet) - : ExitLimit(E, M, MaxOrZero, {&PredSet}) { -} + : ExitLimit(E, M, MaxOrZero, {&PredSet}) {} ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero) - : ExitLimit(E, M, MaxOrZero, None) { -} + : ExitLimit(E, M, MaxOrZero, None) {} /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each /// computable exit into a persistent ExitNotTakenInfo array. @@ -8531,14 +8550,14 @@ using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo; ExitNotTaken.reserve(ExitCounts.size()); - std::transform( - ExitCounts.begin(), ExitCounts.end(), std::back_inserter(ExitNotTaken), - [&](const EdgeExitInfo &EEI) { - BasicBlock *ExitBB = EEI.first; - const ExitLimit &EL = EEI.second; - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, - EL.Predicates); - }); + std::transform(ExitCounts.begin(), ExitCounts.end(), + std::back_inserter(ExitNotTaken), + [&](const EdgeExitInfo &EEI) { + BasicBlock *ExitBB = EEI.first; + const ExitLimit &EL = EEI.second; + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, + EL.MaxNotTaken, EL.Predicates); + }); assert((isa(ConstantMax) || isa(ConstantMax)) && "No point in having a non-constant max backedge taken count!"); @@ -8618,8 +8637,10 @@ } } } - const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount : - (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute()); + const SCEV *MaxBECount = + MustExitMaxBECount + ? MustExitMaxBECount + : (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute()); // The loop backedge will be taken the maximum or zero times if there's // a single exit that must be taken the maximum or zero times. bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1); @@ -8636,7 +8657,7 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, - bool AllowPredicates) { + bool AllowPredicates) { assert(L->contains(ExitingBlock) && "Exit count for non-loop block?"); // If our exiting block does not dominate the latch, then its connection with // loop's exit limit may be far from trivial. @@ -8652,9 +8673,9 @@ assert(ExitIfTrue == L->contains(BI->getSuccessor(1)) && "It should have one successor in loop and one exit block!"); // Proceed to the next level to examine the exit condition expression. - return computeExitLimitFromCond( - L, BI->getCondition(), ExitIfTrue, - /*ControlsExit=*/IsOnlyExit, AllowPredicates); + return computeExitLimitFromCond(L, BI->getCondition(), ExitIfTrue, + /*ControlsExit=*/IsOnlyExit, + AllowPredicates); } if (SwitchInst *SI = dyn_cast(Term)) { @@ -8674,9 +8695,10 @@ return getCouldNotCompute(); } -ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCond( - const Loop *L, Value *ExitCond, bool ExitIfTrue, - bool ControlsExit, bool AllowPredicates) { +ScalarEvolution::ExitLimit +ScalarEvolution::computeExitLimitFromCond(const Loop *L, Value *ExitCond, + bool ExitIfTrue, bool ControlsExit, + bool AllowPredicates) { ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates); return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue, ControlsExit, AllowPredicates); @@ -8700,8 +8722,7 @@ } void ScalarEvolution::ExitLimitCache::insert(const Loop *L, Value *ExitCond, - bool ExitIfTrue, - bool ControlsExit, + bool ExitIfTrue, bool ControlsExit, bool AllowPredicates, const ExitLimit &EL) { assert(this->L == L && this->ExitIfTrue == ExitIfTrue && @@ -8769,9 +8790,8 @@ const APInt *C; if (match(ExitCond, m_ExtractValue<1>(m_WithOverflowInst(WO))) && match(WO->getRHS(), m_APInt(C))) { - ConstantRange NWR = - ConstantRange::makeExactNoWrapRegion(WO->getBinaryOp(), *C, - WO->getNoWrapKind()); + ConstantRange NWR = ConstantRange::makeExactNoWrapRegion( + WO->getBinaryOp(), *C, WO->getNoWrapKind()); CmpInst::Predicate Pred; APInt NewRHSC, Offset; NWR.getEquivalentICmp(Pred, NewRHSC, Offset); @@ -8782,7 +8802,8 @@ LHS = getAddExpr(LHS, getConstant(Offset)); auto EL = computeExitLimitFromICmp(L, Pred, LHS, getConstant(NewRHSC), ControlsExit, AllowPredicates); - if (EL.hasAnyInfo()) return EL; + if (EL.hasAnyInfo()) + return EL; } // If it's not an integer or pointer comparison then compute it the hard way. @@ -8855,14 +8876,12 @@ MaxBECount = getConstant(getUnsignedRangeMax(BECount)); return ExitLimit(BECount, MaxBECount, false, - { &EL0.Predicates, &EL1.Predicates }); + {&EL0.Predicates, &EL1.Predicates}); } ScalarEvolution::ExitLimit -ScalarEvolution::computeExitLimitFromICmp(const Loop *L, - ICmpInst *ExitCond, - bool ExitIfTrue, - bool ControlsExit, +ScalarEvolution::computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, + bool ExitIfTrue, bool ControlsExit, bool AllowPredicates) { // If the condition was exit on true, convert the condition to exit on false ICmpInst::Predicate Pred; @@ -8877,10 +8896,10 @@ ExitLimit EL = computeExitLimitFromICmp(L, Pred, LHS, RHS, ControlsExit, AllowPredicates); - if (EL.hasAnyInfo()) return EL; + if (EL.hasAnyInfo()) + return EL; - auto *ExhaustiveCount = - computeExitCountExhaustively(L, ExitCond, ExitIfTrue); + auto *ExhaustiveCount = computeExitCountExhaustively(L, ExitCond, ExitIfTrue); if (!isa(ExhaustiveCount)) return ExhaustiveCount; @@ -8888,12 +8907,9 @@ return computeShiftCompareExitLimit(ExitCond->getOperand(0), ExitCond->getOperand(1), L, OriginalPred); } -ScalarEvolution::ExitLimit -ScalarEvolution::computeExitLimitFromICmp(const Loop *L, - ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - bool ControlsExit, - bool AllowPredicates) { +ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp( + const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, + bool ControlsExit, bool AllowPredicates) { // Try to evaluate any dependencies out of the loop. LHS = getSCEVAtScope(LHS, L); @@ -8910,9 +8926,9 @@ bool ControllingFiniteLoop = ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L); // Simplify the operands before analyzing them. - (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0, - (EnableFiniteLoopControl ? ControllingFiniteLoop - : false)); + (void)SimplifyICmpOperands( + Pred, LHS, RHS, /*Depth=*/0, + (EnableFiniteLoopControl ? ControllingFiniteLoop : false)); // If we have a comparison of a chrec against a constant, try to use value // ranges to answer this query. @@ -8924,7 +8940,8 @@ ConstantRange::makeExactICmpRegion(Pred, RHSC->getAPInt()); const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this); - if (!isa(Ret)) return Ret; + if (!isa(Ret)) + return Ret; } // If this loop must exit based on this condition (or execute undefined @@ -8940,11 +8957,11 @@ InnerLHS = ZExt->getOperand(); if (const SCEVAddRecExpr *AR = dyn_cast(InnerLHS)) { auto *StrideC = dyn_cast(AR->getStepRecurrence(*this)); - if (!AR->hasNoSelfWrap() && AR->getLoop() == L && AR->isAffine() && + if (!AR->hasNoSelfWrap() && AR->getLoop() == L && AR->isAffine() && StrideC && StrideC->getAPInt().isPowerOf2()) { auto Flags = AR->getNoWrapFlags(); Flags = setFlags(Flags, SCEV::FlagNW); - SmallVector Operands{AR->operands()}; + SmallVector Operands{AR->operands()}; Flags = StrengthenNoWrapFlags(this, scAddRecExpr, Operands, Flags); setNoWrapFlags(const_cast(AR), Flags); } @@ -8952,7 +8969,7 @@ } switch (Pred) { - case ICmpInst::ICMP_NE: { // while (X != Y) + case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) if (LHS->getType()->isPointerTy()) { LHS = getLosslessPtrToIntExpr(LHS); @@ -8964,12 +8981,13 @@ if (isa(RHS)) return RHS; } - ExitLimit EL = howFarToZero(getMinusSCEV(LHS, RHS), L, ControlsExit, - AllowPredicates); - if (EL.hasAnyInfo()) return EL; + ExitLimit EL = + howFarToZero(getMinusSCEV(LHS, RHS), L, ControlsExit, AllowPredicates); + if (EL.hasAnyInfo()) + return EL; break; } - case ICmpInst::ICMP_EQ: { // while (X == Y) + case ICmpInst::ICMP_EQ: { // while (X == Y) // Convert to: while (X-Y == 0) if (LHS->getType()->isPointerTy()) { LHS = getLosslessPtrToIntExpr(LHS); @@ -8982,24 +9000,26 @@ return RHS; } ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L); - if (EL.hasAnyInfo()) return EL; + if (EL.hasAnyInfo()) + return EL; break; } case ICmpInst::ICMP_SLT: - case ICmpInst::ICMP_ULT: { // while (X < Y) + case ICmpInst::ICMP_ULT: { // while (X < Y) bool IsSigned = Pred == ICmpInst::ICMP_SLT; - ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit, - AllowPredicates); - if (EL.hasAnyInfo()) return EL; + ExitLimit EL = + howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit, AllowPredicates); + if (EL.hasAnyInfo()) + return EL; break; } case ICmpInst::ICMP_SGT: - case ICmpInst::ICMP_UGT: { // while (X > Y) + case ICmpInst::ICMP_UGT: { // while (X > Y) bool IsSigned = Pred == ICmpInst::ICMP_SGT; - ExitLimit EL = - howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit, - AllowPredicates); - if (EL.hasAnyInfo()) return EL; + ExitLimit EL = howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit, + AllowPredicates); + if (EL.hasAnyInfo()) + return EL; break; } default: @@ -9059,9 +9079,8 @@ // Return true if V is of the form "LHS `shift_op` ". // Return LHS in OutLHS and shift_opt in OutOpCode. - auto MatchPositiveShift = - [](Value *V, Value *&OutLHS, Instruction::BinaryOps &OutOpCode) { - + auto MatchPositiveShift = [](Value *V, Value *&OutLHS, + Instruction::BinaryOps &OutOpCode) { using namespace PatternMatch; ConstantInt *ShiftAmt; @@ -9085,8 +9104,8 @@ // // Return true on a successful match. Return the corresponding PHI node (%iv // above) in PNOut and the opcode of the shift operation in OpCodeOut. - auto MatchShiftRecurrence = - [&](Value *V, PHINode *&PNOut, Instruction::BinaryOps &OpCodeOut) { + auto MatchShiftRecurrence = [&](Value *V, PHINode *&PNOut, + Instruction::BinaryOps &OpCodeOut) { Optional PostShiftOpCode; { @@ -9189,9 +9208,9 @@ /// Return true if we can constant fold an instruction of the specified type, /// assuming that all operands were constants. static bool CanConstantFold(const Instruction *I) { - if (isa(I) || isa(I) || - isa(I) || isa(I) || isa(I) || - isa(I) || isa(I)) + if (isa(I) || isa(I) || isa(I) || + isa(I) || isa(I) || isa(I) || + isa(I)) return true; if (const CallInst *CI = dyn_cast(I)) @@ -9204,7 +9223,8 @@ /// assuming its operands can all constant evolve. static bool canConstantEvolve(Instruction *I, const Loop *L) { // An instruction outside of the loop can't be derived from a loop PHI. - if (!L->contains(I)) return false; + if (!L->contains(I)) + return false; if (isa(I)) { // We don't currently keep track of the control flow needed to evaluate @@ -9230,10 +9250,12 @@ // constant or derived from a PHI node themselves. PHINode *PHI = nullptr; for (Value *Op : UseInst->operands()) { - if (isa(Op)) continue; + if (isa(Op)) + continue; Instruction *OpInst = dyn_cast(Op); - if (!OpInst || !canConstantEvolve(OpInst, L)) return nullptr; + if (!OpInst || !canConstantEvolve(OpInst, L)) + return nullptr; PHINode *P = dyn_cast(OpInst); if (!P) @@ -9248,9 +9270,9 @@ PHIMap[OpInst] = P; } if (!P) - return nullptr; // Not evolving from PHI + return nullptr; // Not evolving from PHI if (PHI && PHI != P) - return nullptr; // Evolving from multiple different PHIs. + return nullptr; // Evolving from multiple different PHIs. PHI = P; } // This is a expression evolving from a constant PHI! @@ -9264,7 +9286,8 @@ /// constraints, return null. static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { Instruction *I = dyn_cast(V); - if (!I || !canConstantEvolve(I, L)) return nullptr; + if (!I || !canConstantEvolve(I, L)) + return nullptr; if (PHINode *PN = dyn_cast(I)) return PN; @@ -9283,40 +9306,46 @@ const DataLayout &DL, const TargetLibraryInfo *TLI) { // Convenient constant check, but redundant for recursive calls. - if (Constant *C = dyn_cast(V)) return C; + if (Constant *C = dyn_cast(V)) + return C; Instruction *I = dyn_cast(V); - if (!I) return nullptr; + if (!I) + return nullptr; - if (Constant *C = Vals.lookup(I)) return C; + if (Constant *C = Vals.lookup(I)) + return C; // An instruction inside the loop depends on a value outside the loop that we // weren't given a mapping for, or a value such as a call inside the loop. - if (!canConstantEvolve(I, L)) return nullptr; + if (!canConstantEvolve(I, L)) + return nullptr; // An unmapped PHI can be due to a branch or another loop inside this loop, // or due to this not being the initial iteration through a loop where we // couldn't compute the evolution of this particular PHI last time. - if (isa(I)) return nullptr; + if (isa(I)) + return nullptr; - std::vector Operands(I->getNumOperands()); + std::vector Operands(I->getNumOperands()); for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Instruction *Operand = dyn_cast(I->getOperand(i)); if (!Operand) { Operands[i] = dyn_cast(I->getOperand(i)); - if (!Operands[i]) return nullptr; + if (!Operands[i]) + return nullptr; continue; } Constant *C = EvaluateExpression(Operand, L, Vals, DL, TLI); Vals[Operand] = C; - if (!C) return nullptr; + if (!C) + return nullptr; Operands[i] = C; } return ConstantFoldInstOperands(I, Operands, DL, TLI); } - // If every incoming value to PN except the one for BB is a specific Constant, // return that, else return nullptr. static Constant *getOtherIncomingValue(PHINode *PN, BasicBlock *BB) { @@ -9344,16 +9373,16 @@ /// in the header of its containing loop, we know the loop executes a /// constant number of times, and the PHI node is just a recurrence /// involving constants, fold it. -Constant * -ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, - const APInt &BEs, - const Loop *L) { +Constant *ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, + const APInt &BEs, + const Loop *L) { auto I = ConstantEvolutionLoopExitValue.find(PN); if (I != ConstantEvolutionLoopExitValue.end()) return I->second; if (BEs.ugt(MaxBruteForceIterations)) - return ConstantEvolutionLoopExitValue[PN] = nullptr; // Not going to evaluate it. + return ConstantEvolutionLoopExitValue[PN] = + nullptr; // Not going to evaluate it. Constant *&RetVal = ConstantEvolutionLoopExitValue[PN]; @@ -9381,9 +9410,9 @@ unsigned NumIterations = BEs.getZExtValue(); // must be in range unsigned IterationNum = 0; const DataLayout &DL = getDataLayout(); - for (; ; ++IterationNum) { + for (;; ++IterationNum) { if (IterationNum == NumIterations) - return RetVal = CurrentIterVals[PN]; // Got exit value! + return RetVal = CurrentIterVals[PN]; // Got exit value! // Compute the value of the PHIs for the next iteration. // EvaluateExpression adds non-phi values to the CurrentIterVals map. @@ -9391,7 +9420,7 @@ Constant *NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL, &TLI); if (!NextPHI) - return nullptr; // Couldn't evaluate! + return nullptr; // Couldn't evaluate! NextIterVals[PN] = NextPHI; bool StoppedEvolving = NextPHI == CurrentIterVals[PN]; @@ -9402,7 +9431,8 @@ SmallVector, 8> PHIsToCompute; for (const auto &I : CurrentIterVals) { PHINode *PHI = dyn_cast(I.first); - if (!PHI || PHI == PN || PHI->getParent() != Header) continue; + if (!PHI || PHI == PN || PHI->getParent() != Header) + continue; PHIsToCompute.emplace_back(PHI, I.second); } // We use two distinct loops because EvaluateExpression may invalidate any @@ -9410,7 +9440,7 @@ for (const auto &I : PHIsToCompute) { PHINode *PHI = I.first; Constant *&NextPHI = NextIterVals[PHI]; - if (!NextPHI) { // Not already computed. + if (!NextPHI) { // Not already computed. Value *BEValue = PHI->getIncomingValueForBlock(Latch); NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL, &TLI); } @@ -9431,11 +9461,13 @@ Value *Cond, bool ExitWhen) { PHINode *PN = getConstantEvolvingPHI(Cond, L); - if (!PN) return getCouldNotCompute(); + if (!PN) + return getCouldNotCompute(); // If the loop is canonicalized, the PHI will have exactly two entries. // That's the only form we support here. - if (PN->getNumIncomingValues() != 2) return getCouldNotCompute(); + if (PN->getNumIncomingValues() != 2) + return getCouldNotCompute(); DenseMap CurrentIterVals; BasicBlock *Header = L->getHeader(); @@ -9454,14 +9486,16 @@ // Okay, we find a PHI node that defines the trip count of this loop. Execute // the loop symbolically to determine when the condition gets a value of // "ExitWhen". - unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. + unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. const DataLayout &DL = getDataLayout(); - for (unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){ + for (unsigned IterationNum = 0; IterationNum != MaxIterations; + ++IterationNum) { auto *CondVal = dyn_cast_or_null( EvaluateExpression(Cond, L, CurrentIterVals, DL, &TLI)); // Couldn't symbolically evaluate. - if (!CondVal) return getCouldNotCompute(); + if (!CondVal) + return getCouldNotCompute(); if (CondVal->getValue() == uint64_t(ExitWhen)) { ++NumBruteForceTripCountsComputed; @@ -9477,12 +9511,14 @@ SmallVector PHIsToCompute; for (const auto &I : CurrentIterVals) { PHINode *PHI = dyn_cast(I.first); - if (!PHI || PHI->getParent() != Header) continue; + if (!PHI || PHI->getParent() != Header) + continue; PHIsToCompute.push_back(PHI); } for (PHINode *PHI : PHIsToCompute) { Constant *&NextPHI = NextIterVals[PHI]; - if (NextPHI) continue; // Already computed! + if (NextPHI) + continue; // Already computed! Value *BEValue = PHI->getIncomingValueForBlock(Latch); NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL, &TLI); @@ -9605,7 +9641,8 @@ } const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { - if (isa(V)) return V; + if (isa(V)) + return V; // If this instruction is evolved from a constant-evolving PHI, compute the // exit value from the loop without using SCEVs. @@ -9657,7 +9694,8 @@ // the specified iteration number. Constant *RV = getConstantEvolutionLoopExitValue( PN, BTCC->getAPInt(), CurrLoop); - if (RV) return getSCEV(RV); + if (RV) + return getSCEV(RV); } } @@ -9668,7 +9706,8 @@ const SCEV *InputAtScope = getSCEVAtScope(Input, L); // TODO: We can generalize it using LI.replacementPreservesLCSSAForm, // for the simplest case just support constants. - if (isa(InputAtScope)) return InputAtScope; + if (isa(InputAtScope)) + return InputAtScope; } } @@ -9696,12 +9735,12 @@ MadeImprovement |= OrigV != OpV; Constant *C = BuildConstantFromSCEV(OpV); - if (!C) return V; + if (!C) + return V; if (C->getType() != Op->getType()) - C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, - Op->getType(), - false), - C, Op->getType()); + C = ConstantExpr::getCast( + CastInst::getCastOpcode(C, false, Op->getType(), false), C, + Op->getType()); Operands.push_back(C); } @@ -9710,7 +9749,8 @@ Constant *C = nullptr; const DataLayout &DL = getDataLayout(); C = ConstantFoldInstOperands(I, Operands, DL, &TLI); - if (!C) return V; + if (!C) + return V; return getSCEV(C); } } @@ -9730,7 +9770,7 @@ // Okay, at least one of these operands is loop variant but might be // foldable. Build a new instance of the folded commutative expression. SmallVector NewOps(Comm->op_begin(), - Comm->op_begin()+i); + Comm->op_begin() + i); NewOps.push_back(OpAtScope); for (++i; i != e; ++i) { @@ -9756,7 +9796,7 @@ const SCEV *LHS = getSCEVAtScope(Div->getLHS(), L); const SCEV *RHS = getSCEVAtScope(Div->getRHS(), L); if (LHS == Div->getLHS() && RHS == Div->getRHS()) - return Div; // must be loop invariant + return Div; // must be loop invariant return getUDivExpr(LHS, RHS); } @@ -9774,14 +9814,13 @@ // Okay, at least one of these operands is loop variant but might be // foldable. Build a new instance of the folded commutative expression. SmallVector NewOps(AddRec->op_begin(), - AddRec->op_begin()+i); + AddRec->op_begin() + i); NewOps.push_back(OpAtScope); for (++i; i != e; ++i) NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L)); - const SCEV *FoldedRec = - getAddRecExpr(NewOps, AddRec->getLoop(), - AddRec->getNoWrapFlags(SCEV::FlagNW)); + const SCEV *FoldedRec = getAddRecExpr( + NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW)); AddRec = dyn_cast(FoldedRec); // The addrec may be folded to a nonrecurrence, for example, if the // induction variable is multiplied by zero after constant folding. Go @@ -9797,7 +9836,8 @@ // To evaluate this recurrence, we need to know how many times the AddRec // loop iterates. Compute this now. const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); - if (BackedgeTakenCount == getCouldNotCompute()) return AddRec; + if (BackedgeTakenCount == getCouldNotCompute()) + return AddRec; // Then, evaluate the AddRec. return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); @@ -9809,7 +9849,7 @@ if (const SCEVCastExpr *Cast = dyn_cast(V)) { const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L); if (Op == Cast->getOperand()) - return Cast; // must be loop invariant + return Cast; // must be loop invariant return getCastExpr(Cast->getSCEVType(), Op, Cast->getType()); } @@ -9837,7 +9877,7 @@ /// /// If the equation does not have a solution, SCEVCouldNotCompute is returned. static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, - ScalarEvolution &SE) { + ScalarEvolution &SE) { uint32_t BW = A.getBitWidth(); assert(BW == SE.getTypeSizeInBits(B->getType())); assert(A != 0 && "A must be non-zero."); @@ -9862,9 +9902,9 @@ // If D == 1, (N / D) == N == 2^BW, so we need one extra bit to represent // (N / D) in general. The inverse itself always fits into BW bits, though, // so we immediately truncate it. - APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D + APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D APInt Mod(BW + 1, 0); - Mod.setBit(BW - Mult2); // Mod = N / D + Mod.setBit(BW - Mult2); // Mod = N / D APInt I = AD.multiplicativeInverse(Mod).trunc(BW); // 4. Compute the minimum unsigned root of the equation: @@ -9890,8 +9930,8 @@ const SCEVConstant *LC = dyn_cast(AddRec->getOperand(0)); const SCEVConstant *MC = dyn_cast(AddRec->getOperand(1)); const SCEVConstant *NC = dyn_cast(AddRec->getOperand(2)); - LLVM_DEBUG(dbgs() << __func__ << ": analyzing quadratic addrec: " - << *AddRec << '\n'); + LLVM_DEBUG(dbgs() << __func__ << ": analyzing quadratic addrec: " << *AddRec + << '\n'); // We currently can only solve this if the coefficients are constants. if (!LC || !MC || !NC) { @@ -9906,8 +9946,7 @@ unsigned BitWidth = LC->getAPInt().getBitWidth(); unsigned NewWidth = BitWidth + 1; - LLVM_DEBUG(dbgs() << __func__ << ": addrec coeff bw: " - << BitWidth << '\n'); + LLVM_DEBUG(dbgs() << __func__ << ": addrec coeff bw: " << BitWidth << '\n'); // The sign-extension (as opposed to a zero-extension) here matches the // extension used in SolveQuadraticEquationWrap (with the same motivation). N = N.sext(NewWidth); @@ -9928,9 +9967,9 @@ APInt B = 2 * M - A; APInt C = 2 * L; APInt T = APInt(NewWidth, 2); - LLVM_DEBUG(dbgs() << __func__ << ": equation " << A << "x^2 + " << B - << "x + " << C << ", coeff bw: " << NewWidth - << ", multiplied by " << T << '\n'); + LLVM_DEBUG(dbgs() << __func__ << ": equation " << A << "x^2 + " << B << "x + " + << C << ", coeff bw: " << NewWidth << ", multiplied by " + << T << '\n'); return std::make_tuple(A, B, C, T, BitWidth); } @@ -9984,8 +10023,8 @@ /// (b) SolveQuadraticEquationWrap was unable to find a solution. For cases /// like x^2 = 5, no integer solutions exist, in other cases an integer /// solution may exist, but SolveQuadraticEquationWrap may fail to find it. -static Optional -SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { +static Optional SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, + ScalarEvolution &SE) { APInt A, B, C, M; unsigned BitWidth; auto T = GetQuadraticEquation(AddRec); @@ -9994,7 +10033,8 @@ std::tie(A, B, C, M, BitWidth) = *T; LLVM_DEBUG(dbgs() << __func__ << ": solving for unsigned overflow\n"); - Optional X = APIntOps::SolveQuadraticEquationWrap(A, B, C, BitWidth+1); + Optional X = + APIntOps::SolveQuadraticEquationWrap(A, B, C, BitWidth + 1); if (!X) return None; @@ -10016,9 +10056,9 @@ /// (a) the addrec coefficients are not constant, or /// (b) SolveQuadraticEquationWrap was unable to find a solution for the /// bounds of the range. -static Optional -SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, - const ConstantRange &Range, ScalarEvolution &SE) { +static Optional SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, + const ConstantRange &Range, + ScalarEvolution &SE) { assert(AddRec->getOperand(0)->isZero() && "Starting value of addrec should be 0"); LLVM_DEBUG(dbgs() << __func__ << ": solving boundary crossing for range " @@ -10042,7 +10082,7 @@ // cannot make any conclusions. // Return a pair: the optional solution and a flag indicating if the // solution was found. - auto SolveForBoundary = [&](APInt Bound) -> std::pair,bool> { + auto SolveForBoundary = [&](APInt Bound) -> std::pair, bool> { // Solve for signed overflow and unsigned overflow, pick the lower // solution. LLVM_DEBUG(dbgs() << "SolveQuadraticAddRecRange: checking boundary " @@ -10057,16 +10097,16 @@ } LLVM_DEBUG(dbgs() << "SolveQuadraticAddRecRange: solving for " "unsigned overflow\n"); - Optional UO = APIntOps::SolveQuadraticEquationWrap(A, B, -Bound, - BitWidth+1); + Optional UO = + APIntOps::SolveQuadraticEquationWrap(A, B, -Bound, BitWidth + 1); - auto LeavesRange = [&] (const APInt &X) { + auto LeavesRange = [&](const APInt &X) { ConstantInt *C0 = ConstantInt::get(SE.getContext(), X); ConstantInt *V0 = EvaluateConstantChrecAtConstant(AddRec, C0, SE); if (Range.contains(V0->getValue())) return false; // X should be at least 1, so X-1 is non-negative. - ConstantInt *C1 = ConstantInt::get(SE.getContext(), X-1); + ConstantInt *C1 = ConstantInt::get(SE.getContext(), X - 1); ConstantInt *V1 = EvaluateConstantChrecAtConstant(AddRec, C1, SE); if (Range.contains(V1->getValue())) return true; @@ -10077,19 +10117,19 @@ // be a solution, but the function failed to find it. We cannot treat it // as "no solution". if (!SO || !UO) - return { None, false }; + return {None, false}; // Check the smaller value first to see if it leaves the range. // At this point, both SO and UO must have values. Optional Min = MinOptional(SO, UO); if (LeavesRange(*Min)) - return { Min, true }; + return {Min, true}; Optional Max = Min == SO ? UO : SO; if (LeavesRange(*Max)) - return { Max, true }; + return {Max, true}; // Solutions were found, but were eliminated, hence the "true". - return { None, true }; + return {None, true}; }; std::tie(A, B, C, M, BitWidth) = *T; @@ -10144,9 +10184,10 @@ return TruncIfPossible(MinOptional(SL.first, SU.first), BitWidth); } -ScalarEvolution::ExitLimit -ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit, - bool AllowPredicates) { +ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V, + const Loop *L, + bool ControlsExit, + bool AllowPredicates) { // This is only used for loops with a "x != y" exit test. The exit condition // is now expressed as a single expression, V = x-y. So the exit test is @@ -10157,8 +10198,9 @@ // If the value is a constant if (const SCEVConstant *C = dyn_cast(V)) { // If the value is already zero, the branch will execute zero times. - if (C->getValue()->isZero()) return C; - return getCouldNotCompute(); // Otherwise it will loop infinitely. + if (C->getValue()->isZero()) + return C; + return getCouldNotCompute(); // Otherwise it will loop infinitely. } const SCEVAddRecExpr *AddRec = @@ -10230,9 +10272,9 @@ APInt MaxBECount = getUnsignedRangeMax(applyLoopGuards(Distance, L)); MaxBECount = APIntOps::umin(MaxBECount, getUnsignedRangeMax(Distance)); - // When a loop like "for (int i = 0; i != n; ++i) { /* body */ }" is rotated, - // we end up with a loop whose backedge-taken count is n - 1. Detect this - // case, and see if we can improve the bound. + // When a loop like "for (int i = 0; i != n; ++i) { /* body */ }" is + // rotated, we end up with a loop whose backedge-taken count is n - 1. + // Detect this case, and see if we can improve the bound. // // Explicitly handling this here is necessary because getUnsignedRange // isn't context-sensitive; it doesn't know that we only care about the @@ -10278,8 +10320,8 @@ return ExitLimit(E, M, false, Predicates); } -ScalarEvolution::ExitLimit -ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) { +ScalarEvolution::ExitLimit ScalarEvolution::howFarToNonZero(const SCEV *V, + const Loop *L) { // Loops that look like: while (X == 0) are very strange indeed. We don't // handle them yet except for the trivial case. This could be expanded in the // future as needed. @@ -10289,7 +10331,7 @@ if (const SCEVConstant *C = dyn_cast(V)) { if (!C->getValue()->isZero()) return getZero(C->getType()); - return getCouldNotCompute(); // Otherwise it will loop infinitely. + return getCouldNotCompute(); // Otherwise it will loop infinitely. } // We could implement others, but I really doubt anyone writes loops like @@ -10298,8 +10340,8 @@ } std::pair -ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) - const { +ScalarEvolution::getPredecessorWithUniqueSuccessorForBB( + const BasicBlock *BB) const { // If the block has a unique predecessor, then there is no path from the // predecessor to the block that does not go through the direct edge // from the predecessor to the block. @@ -10321,13 +10363,15 @@ /// front-end may have replicated the controlling expression. static bool HasSameValue(const SCEV *A, const SCEV *B) { // Quick check to see if they are the same SCEV. - if (A == B) return true; + if (A == B) + return true; auto ComputesEqualValues = [](const Instruction *A, const Instruction *B) { // Not all instructions that are "identical" compute the same value. For // instance, two distinct alloca instructions allocating the same type are // identical and do not read memory; but compute distinct values. - return A->isIdenticalTo(B) && (isa(A) || isa(A)); + return A->isIdenticalTo(B) && + (isa(A) || isa(A)); }; // Otherwise, if they're both SCEVUnknown, it's possible that they hold @@ -10363,9 +10407,8 @@ if (const SCEVConstant *LHSC = dyn_cast(LHS)) { // Check for both operands constant. if (const SCEVConstant *RHSC = dyn_cast(RHS)) { - if (ConstantExpr::getICmp(Pred, - LHSC->getValue(), - RHSC->getValue())->isNullValue()) + if (ConstantExpr::getICmp(Pred, LHSC->getValue(), RHSC->getValue()) + ->isNullValue()) return TrivialCase(false); else return TrivialCase(true); @@ -10432,7 +10475,6 @@ } break; - // The "Should have been caught earlier!" messages refer to the fact // that the ExactCR.isFullSet() or ExactCR.isEmptySet() check above // should have fired on the corresponding cases, and canonicalized the @@ -10484,8 +10526,8 @@ switch (Pred) { case ICmpInst::ICMP_SLE: if (ControllingFiniteLoop || !getSignedRangeMax(RHS).isMaxSignedValue()) { - RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, - SCEV::FlagNSW); + RHS = + getAddExpr(getConstant(RHS->getType(), 1, true), RHS, SCEV::FlagNSW); Pred = ICmpInst::ICMP_SLT; Changed = true; } else if (!getSignedRangeMin(LHS).isMinSignedValue()) { @@ -10502,16 +10544,16 @@ Pred = ICmpInst::ICMP_SGT; Changed = true; } else if (!getSignedRangeMax(LHS).isMaxSignedValue()) { - LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, - SCEV::FlagNSW); + LHS = + getAddExpr(getConstant(RHS->getType(), 1, true), LHS, SCEV::FlagNSW); Pred = ICmpInst::ICMP_SGT; Changed = true; } break; case ICmpInst::ICMP_ULE: if (ControllingFiniteLoop || !getUnsignedRangeMax(RHS).isMaxValue()) { - RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, - SCEV::FlagNUW); + RHS = + getAddExpr(getConstant(RHS->getType(), 1, true), RHS, SCEV::FlagNUW); Pred = ICmpInst::ICMP_ULT; Changed = true; } else if (!getUnsignedRangeMin(LHS).isMinValue()) { @@ -10526,8 +10568,8 @@ Pred = ICmpInst::ICMP_UGT; Changed = true; } else if (!getUnsignedRangeMax(LHS).isMaxValue()) { - LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, - SCEV::FlagNUW); + LHS = + getAddExpr(getConstant(RHS->getType(), 1, true), LHS, SCEV::FlagNUW); Pred = ICmpInst::ICMP_UGT; Changed = true; } @@ -10572,11 +10614,11 @@ // Compute SCEV on entry of loop L. const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *this); if (Start == getCouldNotCompute()) - return { Start, Start }; + return {Start, Start}; // Compute post increment SCEV for loop L. const SCEV *PostInc = SCEVPostIncRewriter::rewrite(S, L, *this); assert(PostInc != getCouldNotCompute() && "Unexpected could not compute"); - return { Start, PostInc }; + return {Start, PostInc}; } bool ScalarEvolution::isKnownViaInduction(ICmpInst::Predicate Pred, @@ -10589,7 +10631,7 @@ if (LoopsUsed.empty()) return false; - // Domination relationship must be a linear order on collected loops. + // Domination relationship must be a linear order on collected loops. #ifndef NDEBUG for (const auto *L1 : LoopsUsed) for (const auto *L2 : LoopsUsed) @@ -10598,24 +10640,23 @@ "Domination relationship is not a linear order"); #endif - const Loop *MDL = - *std::max_element(LoopsUsed.begin(), LoopsUsed.end(), - [&](const Loop *L1, const Loop *L2) { - return DT.properlyDominates(L1->getHeader(), L2->getHeader()); - }); + const Loop *MDL = *std::max_element( + LoopsUsed.begin(), LoopsUsed.end(), [&](const Loop *L1, const Loop *L2) { + return DT.properlyDominates(L1->getHeader(), L2->getHeader()); + }); // Get init and post increment value for LHS. auto SplitLHS = SplitIntoInitAndPostInc(MDL, LHS); // if LHS contains unknown non-invariant SCEV then bail out. if (SplitLHS.first == getCouldNotCompute()) return false; - assert (SplitLHS.second != getCouldNotCompute() && "Unexpected CNC"); + assert(SplitLHS.second != getCouldNotCompute() && "Unexpected CNC"); // Get init and post increment value for RHS. auto SplitRHS = SplitIntoInitAndPostInc(MDL, RHS); // if RHS contains unknown non-invariant SCEV then bail out. if (SplitRHS.first == getCouldNotCompute()) return false; - assert (SplitRHS.second != getCouldNotCompute() && "Unexpected CNC"); + assert(SplitRHS.second != getCouldNotCompute() && "Unexpected CNC"); // It is possible that init SCEV contains an invariant load but it does // not dominate MDL and is not available at MDL loop entry, so we should // check it here. @@ -11041,10 +11082,10 @@ /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is /// protected by a conditional between LHS and RHS. This is used to /// to eliminate casts. -bool -ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, - ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS) { +bool ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, + ICmpInst::Predicate Pred, + const SCEV *LHS, + const SCEV *RHS) { // Interpret a null as meaning no loop, where there is obviously no guard // (interprocedural conditions notwithstanding). Do not bother about // unreachable loops. @@ -11055,7 +11096,6 @@ assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()) && "This cannot be done on broken IR!"); - if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS)) return true; @@ -11064,10 +11104,9 @@ return false; BranchInst *LoopContinuePredicate = - dyn_cast(Latch->getTerminator()); + dyn_cast(Latch->getTerminator()); if (LoopContinuePredicate && LoopContinuePredicate->isConditional() && - isImpliedCond(Pred, LHS, RHS, - LoopContinuePredicate->getCondition(), + isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->getCondition(), LoopContinuePredicate->getSuccessor(0) != L->getHeader())) return true; @@ -11088,7 +11127,7 @@ Type *Ty = LatchBECount->getType(); auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW); const SCEV *LoopCounter = - getAddRecExpr(getZero(Ty), getOne(Ty), L, NoWrapFlags); + getAddRecExpr(getZero(Ty), getOne(Ty), L, NoWrapFlags); if (isImpliedCond(Pred, LHS, RHS, ICmpInst::ICMP_ULT, LoopCounter, LatchBECount)) return true; @@ -11169,7 +11208,7 @@ bool ProvedNonEquality = false; auto SplitAndProve = - [&](std::function Fn) -> bool { + [&](std::function Fn) -> bool { if (!ProvedNonStrictComparison) ProvedNonStrictComparison = Fn(NonStrictPredicate); if (!ProvedNonEquality) @@ -11202,9 +11241,9 @@ return false; }; - // Starting at the block's predecessor, climb up the predecessor chain, as long - // as there are predecessors that can be found that have unique successors - // leading to the original block. + // Starting at the block's predecessor, climb up the predecessor chain, as + // long as there are predecessors that can be found that have unique + // successors leading to the original block. const Loop *ContainingLoop = LI.getLoopFor(BB); const BasicBlock *PredBB; if (ContainingLoop && ContainingLoop->getHeader() == BB) @@ -11296,7 +11335,8 @@ } const ICmpInst *ICI = dyn_cast(FoundCondValue); - if (!ICI) return false; + if (!ICI) + return false; // Now that we found a conditional branch that dominates the loop or controls // the loop latch. Check to see if it is the comparison we are looking for. @@ -11352,8 +11392,9 @@ RHS = getZeroExtendExpr(RHS, FoundLHS->getType()); } } else if (getTypeSizeInBits(LHS->getType()) > - getTypeSizeInBits(FoundLHS->getType())) { - if (FoundLHS->getType()->isPointerTy() || FoundRHS->getType()->isPointerTy()) + getTypeSizeInBits(FoundLHS->getType())) { + if (FoundLHS->getType()->isPointerTy() || + FoundRHS->getType()->isPointerTy()) return false; if (CmpInst::isSigned(FoundPred)) { FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType()); @@ -11497,8 +11538,8 @@ // range we consider has to correspond to same signedness as the // predicate we're interested in folding. - APInt Min = ICmpInst::isSigned(Pred) ? - getSignedRangeMin(V) : getUnsignedRangeMin(V); + APInt Min = ICmpInst::isSigned(Pred) ? getSignedRangeMin(V) + : getUnsignedRangeMin(V); if (Min == C->getAPInt()) { // Given (V >= Min && V != Min) we conclude V >= (Min + 1). @@ -11508,48 +11549,49 @@ APInt SharperMin = Min + 1; switch (Pred) { - case ICmpInst::ICMP_SGE: - case ICmpInst::ICMP_UGE: - // We know V `Pred` SharperMin. If this implies LHS `Pred` - // RHS, we're done. - if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin), - CtxI)) - return true; - LLVM_FALLTHROUGH; + case ICmpInst::ICMP_SGE: + case ICmpInst::ICMP_UGE: + // We know V `Pred` SharperMin. If this implies LHS `Pred` + // RHS, we're done. + if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin), + CtxI)) + return true; + LLVM_FALLTHROUGH; - case ICmpInst::ICMP_SGT: - case ICmpInst::ICMP_UGT: - // We know from the range information that (V `Pred` Min || - // V == Min). We know from the guarding condition that !(V - // == Min). This gives us - // - // V `Pred` Min || V == Min && !(V == Min) - // => V `Pred` Min - // - // If V `Pred` Min implies LHS `Pred` RHS, we're done. + case ICmpInst::ICMP_SGT: + case ICmpInst::ICMP_UGT: + // We know from the range information that (V `Pred` Min || + // V == Min). We know from the guarding condition that !(V + // == Min). This gives us + // + // V `Pred` Min || V == Min && !(V == Min) + // => V `Pred` Min + // + // If V `Pred` Min implies LHS `Pred` RHS, we're done. - if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI)) - return true; - break; + if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI)) + return true; + break; - // `LHS < RHS` and `LHS <= RHS` are handled in the same way as `RHS > LHS` and `RHS >= LHS` respectively. - case ICmpInst::ICMP_SLE: - case ICmpInst::ICMP_ULE: - if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS, - LHS, V, getConstant(SharperMin), CtxI)) - return true; - LLVM_FALLTHROUGH; + // `LHS < RHS` and `LHS <= RHS` are handled in the same way as `RHS > LHS` + // and `RHS >= LHS` respectively. + case ICmpInst::ICMP_SLE: + case ICmpInst::ICMP_ULE: + if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS, LHS, + V, getConstant(SharperMin), CtxI)) + return true; + LLVM_FALLTHROUGH; - case ICmpInst::ICMP_SLT: - case ICmpInst::ICMP_ULT: - if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS, - LHS, V, getConstant(Min), CtxI)) - return true; - break; + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_ULT: + if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS, LHS, + V, getConstant(Min), CtxI)) + return true; + break; - default: - // No change - break; + default: + // No change + break; } } } @@ -11568,9 +11610,8 @@ return false; } -bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr, - const SCEV *&L, const SCEV *&R, - SCEV::NoWrapFlags &Flags) { +bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr, const SCEV *&L, + const SCEV *&R, SCEV::NoWrapFlags &Flags) { const auto *AE = dyn_cast(Expr); if (!AE || AE->getNumOperands() != 2) return false; @@ -11753,7 +11794,8 @@ FoundRHSLimit = -(*RDiff); } else { assert(Pred == CmpInst::ICMP_SLT && "Checked above!"); - FoundRHSLimit = APInt::getSignedMinValue(getTypeSizeInBits(RHS->getType())) - *RDiff; + FoundRHSLimit = + APInt::getSignedMinValue(getTypeSizeInBits(RHS->getType())) - *RDiff; } // Try to prove (1) or (2), as needed. @@ -11842,7 +11884,8 @@ // PHIs, for it we can compare incoming values of AddRec from above the loop // and latch with their respective incoming values of LPhi. // TODO: Generalize to handle loops with many inputs in a header. - if (LPhi->getNumIncomingValues() != 2) return false; + if (LPhi->getNumIncomingValues() != 2) + return false; auto *RLoop = RAR->getLoop(); auto *Predecessor = RLoop->getLoopPredecessor(); @@ -11936,8 +11979,7 @@ CtxI)) return true; - return isImpliedCondOperandsHelper(Pred, LHS, RHS, - FoundLHS, FoundRHS); + return isImpliedCondOperandsHelper(Pred, LHS, RHS, FoundLHS, FoundRHS); } /// Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values? @@ -11975,8 +12017,8 @@ if (LAR->getStepRecurrence(SE) != RAR->getStepRecurrence(SE)) return false; - SCEV::NoWrapFlags NW = ICmpInst::isSigned(Pred) ? - SCEV::FlagNSW : SCEV::FlagNUW; + SCEV::NoWrapFlags NW = + ICmpInst::isSigned(Pred) ? SCEV::FlagNSW : SCEV::FlagNUW; if (!LAR->getNoWrapFlags(NW) || !RAR->getNoWrapFlags(NW)) return false; @@ -12217,9 +12259,9 @@ return false; } -bool -ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS) { +bool ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, + const SCEV *LHS, + const SCEV *RHS) { return isKnownPredicateExtendIdiom(Pred, LHS, RHS) || isKnownPredicateViaConstantRanges(Pred, LHS, RHS) || IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) || @@ -12227,13 +12269,14 @@ isKnownPredicateViaNoOverflow(Pred, LHS, RHS); } -bool -ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - const SCEV *FoundLHS, - const SCEV *FoundRHS) { +bool ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, + const SCEV *LHS, + const SCEV *RHS, + const SCEV *FoundLHS, + const SCEV *FoundRHS) { switch (Pred) { - default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); + default: + llvm_unreachable("Unexpected ICmpInst::Predicate value!"); case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_NE: if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS)) @@ -12330,7 +12373,7 @@ bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned) { - + unsigned BitWidth = getTypeSizeInBits(RHS->getType()); const SCEV *One = getOne(Stride->getType()); @@ -12483,15 +12526,14 @@ const SCEV *Step = AR->getStepRecurrence(*this); Type *Ty = ZExt->getType(); auto *S = getAddRecExpr( - getExtendAddRecStart(AR, Ty, this, 0), - getZeroExtendExpr(Step, Ty, 0), L, AR->getNoWrapFlags()); + getExtendAddRecStart(AR, Ty, this, 0), + getZeroExtendExpr(Step, Ty, 0), L, AR->getNoWrapFlags()); IV = dyn_cast(S); } } } } - if (!IV && AllowPredicates) { // Try to make this an AddRec using runtime tests, in the first X // iterations of this loop, where X is the SCEV expression found by the @@ -12709,8 +12751,8 @@ // // FIXME: Should isLoopEntryGuardedByCond do this for us? auto CondGT = IsSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; - auto *StartMinusOne = getAddExpr(OrigStart, - getMinusOne(OrigStart->getType())); + auto *StartMinusOne = + getAddExpr(OrigStart, getMinusOne(OrigStart->getType())); return isLoopEntryGuardedByCond(L, CondGT, OrigRHS, StartMinusOne); }; @@ -12732,7 +12774,8 @@ // See what would happen if we assume the backedge is taken. This is // used to compute MaxBECount. - BECountIfBackedgeTaken = getUDivCeilSCEV(getMinusSCEV(RHS, Start), Stride); + BECountIfBackedgeTaken = + getUDivCeilSCEV(getMinusSCEV(RHS, Start), Stride); } // At this point, we know: @@ -12907,11 +12950,11 @@ const SCEV *BECount = getUDivExpr( getAddExpr(getMinusSCEV(Start, End), getMinusSCEV(Stride, One)), Stride); - APInt MaxStart = IsSigned ? getSignedRangeMax(Start) - : getUnsignedRangeMax(Start); + APInt MaxStart = + IsSigned ? getSignedRangeMax(Start) : getUnsignedRangeMax(Start); - APInt MinStride = IsSigned ? getSignedRangeMin(Stride) - : getUnsignedRangeMin(Stride); + APInt MinStride = + IsSigned ? getSignedRangeMin(Stride) : getUnsignedRangeMin(Stride); unsigned BitWidth = getTypeSizeInBits(LHS->getType()); APInt Limit = IsSigned ? APInt::getSignedMinValue(BitWidth) + (MinStride - 1) @@ -12920,9 +12963,8 @@ // Although End can be a MIN expression we estimate MinEnd considering only // the case End = RHS. This is safe because in the other case (Start - End) // is zero, leading to a zero maximum backedge taken count. - APInt MinEnd = - IsSigned ? APIntOps::smax(getSignedRangeMin(RHS), Limit) - : APIntOps::umax(getUnsignedRangeMin(RHS), Limit); + APInt MinEnd = IsSigned ? APIntOps::smax(getSignedRangeMin(RHS), Limit) + : APIntOps::umax(getUnsignedRangeMin(RHS), Limit); const SCEV *MaxBECount = isa(BECount) ? BECount @@ -12937,7 +12979,7 @@ const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const { - if (Range.isFullSet()) // Infinite loop. + if (Range.isFullSet()) // Infinite loop. return SE.getCouldNotCompute(); // If the start is a non-zero constant, shift the range to simplify things. @@ -12945,8 +12987,8 @@ if (!SC->getValue()->isZero()) { SmallVector Operands(operands()); Operands[0] = SE.getZero(SC->getType()); - const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(), - getNoWrapFlags(FlagNW)); + const SCEV *Shifted = + SE.getAddRecExpr(Operands, getLoop(), getNoWrapFlags(FlagNW)); if (const auto *ShiftedAddRec = dyn_cast(Shifted)) return ShiftedAddRec->getNumIterationsInRange( Range.subtract(SC->getAPInt()), SE); @@ -12988,12 +13030,13 @@ // things must have happened. ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE); if (Range.contains(Val->getValue())) - return SE.getCouldNotCompute(); // Something strange happened + return SE.getCouldNotCompute(); // Something strange happened // Ensure that the previous value is in the range. assert(Range.contains( - EvaluateConstantChrecAtConstant(this, - ConstantInt::get(SE.getContext(), ExitVal - 1), SE)->getValue()) && + EvaluateConstantChrecAtConstant( + this, ConstantInt::get(SE.getContext(), ExitVal - 1), SE) + ->getValue()) && "Linear scev computation is off in a bad way!"); return SE.getConstant(ExitValue); } @@ -13027,8 +13070,8 @@ const SCEV *Last = getOperand(getNumOperands() - 1); assert(!Last->isZero() && "Recurrency with zero step?"); Ops.push_back(Last); - return cast(SE.getAddRecExpr(Ops, getLoop(), - SCEV::FlagAnyWrap)); + return cast( + SE.getAddRecExpr(Ops, getLoop(), SCEV::FlagAnyWrap)); } // Return true when S contains at least an undef value. @@ -13105,7 +13148,7 @@ } ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se) - : CallbackVH(V), SE(se) {} + : CallbackVH(V), SE(se) {} //===----------------------------------------------------------------------===// // ScalarEvolution Class Implementation @@ -13190,8 +13233,7 @@ return !isa(getBackedgeTakenCount(L)); } -static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, - const Loop *L) { +static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L) { // Print all inner loops first for (Loop *I : *L) PrintLoopInfo(OS, SE, I); @@ -13221,7 +13263,8 @@ OS << ": "; if (!isa(SE->getConstantMaxBackedgeTakenCount(L))) { - OS << "max backedge-taken count is " << *SE->getConstantMaxBackedgeTakenCount(L); + OS << "max backedge-taken count is " + << *SE->getConstantMaxBackedgeTakenCount(L); if (SE->isBackedgeTakenCountMaxOrZero(L)) OS << ", actual taken count either this or zero."; } else { @@ -13306,7 +13349,8 @@ } if (L) { - OS << "\t\t" "Exits: "; + OS << "\t\t" + "Exits: "; const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); if (!SE.isLoopInvariant(ExitValue, L)) { OS << "<>"; @@ -13317,7 +13361,8 @@ bool First = true; for (const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) { if (First) { - OS << "\t\t" "LoopDispositions: { "; + OS << "\t\t" + "LoopDispositions: { "; First = false; } else { OS << ", "; @@ -13331,14 +13376,16 @@ if (InnerL == L) continue; if (First) { - OS << "\t\t" "LoopDispositions: { "; + OS << "\t\t" + "LoopDispositions: { "; First = false; } else { OS << ", "; } InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false); - OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); + OS << ": " + << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); } OS << " }"; @@ -13398,7 +13445,8 @@ // Everything that is not defined at loop entry is variant. if (DT.dominates(L->getHeader(), AR->getLoop()->getHeader())) return LoopVariant; - assert(!L->contains(AR->getLoop()) && "Containing loop's header does not" + assert(!L->contains(AR->getLoop()) && + "Containing loop's header does not" " dominate the contained loop's header?"); // This recurrence is invariant w.r.t. L if AR's loop contains L. @@ -13439,8 +13487,8 @@ LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L); if (RD == LoopVariant) return LoopVariant; - return (LD == LoopInvariant && RD == LoopInvariant) ? - LoopInvariant : LoopComputable; + return (LD == LoopInvariant && RD == LoopInvariant) ? LoopInvariant + : LoopComputable; } case scUnknown: // All non-instruction values are loop invariant. All instructions are loop @@ -13532,12 +13580,13 @@ BlockDisposition RD = getBlockDisposition(RHS, BB); if (RD == DoesNotDominateBlock) return DoesNotDominateBlock; - return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ? - ProperlyDominatesBlock : DominatesBlock; + return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) + ? ProperlyDominatesBlock + : DominatesBlock; } case scUnknown: if (Instruction *I = - dyn_cast(cast(S)->getValue())) { + dyn_cast(cast(S)->getValue())) { if (I->getParent() == BB) return DominatesBlock; if (DT.properlyDominates(I->getParent(), BB)) @@ -13655,9 +13704,8 @@ } } -void -ScalarEvolution::getUsedLoops(const SCEV *S, - SmallPtrSetImpl &LoopsUsed) { +void ScalarEvolution::getUsedLoops(const SCEV *S, + SmallPtrSetImpl &LoopsUsed) { struct FindUsedLoops { FindUsedLoops(SmallPtrSetImpl &LoopsUsed) : LoopsUsed(LoopsUsed) {} @@ -13888,8 +13936,9 @@ if (It != ValuesAtScopesUsers.end() && is_contained(It->second, std::make_pair(L, Value))) continue; - dbgs() << "Value: " << *Value << ", Loop: " << *L << ", ValueAtScope: " - << *ValueAtScope << " missing in ValuesAtScopesUsers\n"; + dbgs() << "Value: " << *Value << ", Loop: " << *L + << ", ValueAtScope: " << *ValueAtScope + << " missing in ValuesAtScopesUsers\n"; std::abort(); } } @@ -13905,8 +13954,9 @@ if (It != ValuesAtScopes.end() && is_contained(It->second, std::make_pair(L, ValueAtScope))) continue; - dbgs() << "Value: " << *Value << ", Loop: " << *L << ", ValueAtScope: " - << *ValueAtScope << " missing in ValuesAtScopes\n"; + dbgs() << "Value: " << *Value << ", Loop: " << *L + << ", ValueAtScope: " << *ValueAtScope + << " missing in ValuesAtScopes\n"; std::abort(); } } @@ -13920,7 +13970,7 @@ if (!isa(ENT.ExactNotTaken)) { auto UserIt = BECountUsers.find(ENT.ExactNotTaken); if (UserIt != BECountUsers.end() && - UserIt->second.contains({ LoopAndBEInfo.first, Predicated })) + UserIt->second.contains({LoopAndBEInfo.first, Predicated})) continue; dbgs() << "Value " << *ENT.ExactNotTaken << " for loop " << *LoopAndBEInfo.first << " missing from BECountUsers\n"; @@ -13933,9 +13983,8 @@ VerifyBECountUsers(/* Predicated */ true); } -bool ScalarEvolution::invalidate( - Function &F, const PreservedAnalyses &PA, - FunctionAnalysisManager::Invalidator &Inv) { +bool ScalarEvolution::invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { // Invalidate the ScalarEvolution object whenever it isn't preserved or one // of its dependencies is invalidated. auto PAC = PA.getChecker(); @@ -13961,8 +14010,8 @@ return PreservedAnalyses::all(); } -PreservedAnalyses -ScalarEvolutionPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { +PreservedAnalyses ScalarEvolutionPrinterPass::run(Function &F, + FunctionAnalysisManager &AM) { // For compatibility with opt's -analyze feature under legacy pass manager // which was not ported to NPM. This keeps tests using // update_analyze_test_checks.py working. @@ -14037,7 +14086,7 @@ if (const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP)) return S; SCEVComparePredicate *Eq = new (SCEVAllocator) - SCEVComparePredicate(ID.Intern(SCEVAllocator), Pred, LHS, RHS); + SCEVComparePredicate(ID.Intern(SCEVAllocator), Pred, LHS, RHS); UniquePreds.InsertNode(Eq, IP); return Eq; } @@ -14063,7 +14112,6 @@ class SCEVPredicateRewriter : public SCEVRewriteVisitor { public: - /// Rewrites \p S in the context of a loop L and the SCEV predication /// infrastructure. /// @@ -14129,9 +14177,10 @@ } private: - explicit SCEVPredicateRewriter(const Loop *L, ScalarEvolution &SE, - SmallPtrSetImpl *NewPreds, - const SCEVPredicate *Pred) + explicit SCEVPredicateRewriter( + const Loop *L, ScalarEvolution &SE, + SmallPtrSetImpl *NewPreds, + const SCEVPredicate *Pred) : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred), L(L) {} bool addOverflowAssumption(const SCEVPredicate *P) { @@ -14159,10 +14208,10 @@ if (!isa(Expr->getValue())) return Expr; Optional>> - PredicatedRewrite = SE.createAddRecFromPHIWithCasts(Expr); + PredicatedRewrite = SE.createAddRecFromPHIWithCasts(Expr); if (!PredicatedRewrite) return Expr; - for (const auto *P : PredicatedRewrite->second){ + for (const auto *P : PredicatedRewrite->second) { // Wrap predicates from outer loops are not supported. if (auto *WP = dyn_cast(P)) { if (L != WP->getExpr()->getLoop()) @@ -14181,9 +14230,8 @@ } // end anonymous namespace -const SCEV * -ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L, - const SCEVPredicate &Preds) { +const SCEV *ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L, + const SCEVPredicate &Preds) { return SCEVPredicateRewriter::rewrite(S, L, *this, nullptr, &Preds); } @@ -14211,9 +14259,9 @@ : FastID(ID), Kind(Kind) {} SCEVComparePredicate::SCEVComparePredicate(const FoldingSetNodeIDRef ID, - const ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS) - : SCEVPredicate(ID, P_Compare), Pred(Pred), LHS(LHS), RHS(RHS) { + const ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS) + : SCEVPredicate(ID, P_Compare), Pred(Pred), LHS(LHS), RHS(RHS) { assert(LHS->getType() == RHS->getType() && "LHS and RHS types don't match"); assert(LHS != RHS && "LHS and RHS are the same SCEV"); } @@ -14236,10 +14284,8 @@ if (Pred == ICmpInst::ICMP_EQ) OS.indent(Depth) << "Equal predicate: " << *LHS << " == " << *RHS << "\n"; else - OS.indent(Depth) << "Compare predicate: " << *LHS - << " " << CmpInst::getPredicateName(Pred) << ") " - << *RHS << "\n"; - + OS.indent(Depth) << "Compare predicate: " << *LHS << " " + << CmpInst::getPredicateName(Pred) << ") " << *RHS << "\n"; } SCEVWrapPredicate::SCEVWrapPredicate(const FoldingSetNodeIDRef ID, @@ -14297,7 +14343,7 @@ /// Union predicates don't get cached so create a dummy set ID for it. SCEVUnionPredicate::SCEVUnionPredicate(ArrayRef Preds) - : SCEVPredicate(FoldingSetNodeIDRef(nullptr, 0), P_Union) { + : SCEVPredicate(FoldingSetNodeIDRef(nullptr, 0), P_Union) { for (const auto *P : Preds) add(P); } @@ -14312,8 +14358,7 @@ return all_of(Set->Preds, [this](const SCEVPredicate *I) { return this->implies(I); }); - return any_of(Preds, - [N](const SCEVPredicate *I) { return I->implies(N); }); + return any_of(Preds, [N](const SCEVPredicate *I) { return I->implies(N); }); } void SCEVUnionPredicate::print(raw_ostream &OS, unsigned Depth) const { @@ -14334,7 +14379,7 @@ PredicatedScalarEvolution::PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L) : SE(SE), L(L) { - SmallVector Empty; + SmallVector Empty; Preds = std::make_unique(Empty); } @@ -14382,7 +14427,8 @@ return; auto &OldPreds = Preds->getPredicates(); - SmallVector NewPreds(OldPreds.begin(), OldPreds.end()); + SmallVector NewPreds(OldPreds.begin(), + OldPreds.end()); NewPreds.push_back(&Pred); Preds = std::make_unique(NewPreds); updateGeneration(); @@ -14451,9 +14497,9 @@ PredicatedScalarEvolution::PredicatedScalarEvolution( const PredicatedScalarEvolution &Init) - : RewriteMap(Init.RewriteMap), SE(Init.SE), L(Init.L), - Preds(std::make_unique(Init.Preds->getPredicates())), - Generation(Init.Generation), BackedgeCount(Init.BackedgeCount) { + : RewriteMap(Init.RewriteMap), SE(Init.SE), L(Init.L), + Preds(std::make_unique(Init.Preds->getPredicates())), + Generation(Init.Generation), BackedgeCount(Init.BackedgeCount) { for (auto I : Init.FlagsMap) FlagsMap.insert(I); } @@ -14541,18 +14587,17 @@ const SCEV * ScalarEvolution::computeSymbolicMaxBackedgeTakenCount(const Loop *L) { - SmallVector ExitingBlocks; + SmallVector ExitingBlocks; L->getExitingBlocks(ExitingBlocks); // Form an expression for the maximum exit count possible for this loop. We // merge the max and exact information to approximate a version of // getConstantMaxBackedgeTakenCount which isn't restricted to just constants. - SmallVector ExitCounts; + SmallVector ExitCounts; for (BasicBlock *ExitingBB : ExitingBlocks) { const SCEV *ExitCount = getExitCount(L, ExitingBB); if (isa(ExitCount)) - ExitCount = getExitCount(L, ExitingBB, - ScalarEvolution::ConstantMaximum); + ExitCount = getExitCount(L, ExitingBB, ScalarEvolution::ConstantMaximum); if (!isa(ExitCount)) { assert(DT.dominates(ExitingBB, L->getLoopLatch()) && "We should only have known counts for exiting blocks that "