Deleted Added
sdiff udiff text old ( 193574 ) new ( 193630 )
full compact
ScalarEvolution.cpp (193574) ScalarEvolution.cpp (193630)
1//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 1757 unchanged lines hidden (view full) ---

1766 if (Ty->isInteger())
1767 return Ty;
1768
1769 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
1770 return TD->getIntPtrType();
1771}
1772
1773SCEVHandle ScalarEvolution::getCouldNotCompute() {
1//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 1757 unchanged lines hidden (view full) ---

1766 if (Ty->isInteger())
1767 return Ty;
1768
1769 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
1770 return TD->getIntPtrType();
1771}
1772
1773SCEVHandle ScalarEvolution::getCouldNotCompute() {
1774 return UnknownValue;
1774 return CouldNotCompute;
1775}
1776
1777/// hasSCEV - Return true if the SCEV for this value has already been
1778/// computed.
1779bool ScalarEvolution::hasSCEV(Value *V) const {
1780 return Scalars.count(V);
1781}
1782

--- 607 unchanged lines hidden (view full) ---

2390 // succeeds, procede to actually compute a backedge-taken count and
2391 // update the value. The temporary CouldNotCompute value tells SCEV
2392 // code elsewhere that it shouldn't attempt to request a new
2393 // backedge-taken count, which could result in infinite recursion.
2394 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
2395 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
2396 if (Pair.second) {
2397 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
1775}
1776
1777/// hasSCEV - Return true if the SCEV for this value has already been
1778/// computed.
1779bool ScalarEvolution::hasSCEV(Value *V) const {
1780 return Scalars.count(V);
1781}
1782

--- 607 unchanged lines hidden (view full) ---

2390 // succeeds, procede to actually compute a backedge-taken count and
2391 // update the value. The temporary CouldNotCompute value tells SCEV
2392 // code elsewhere that it shouldn't attempt to request a new
2393 // backedge-taken count, which could result in infinite recursion.
2394 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
2395 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
2396 if (Pair.second) {
2397 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
2398 if (ItCount.Exact != UnknownValue) {
2398 if (ItCount.Exact != CouldNotCompute) {
2399 assert(ItCount.Exact->isLoopInvariant(L) &&
2400 ItCount.Max->isLoopInvariant(L) &&
2401 "Computed trip count isn't loop invariant for loop!");
2402 ++NumTripCountsComputed;
2403
2404 // Update the value in the map.
2405 Pair.first->second = ItCount;
2406 } else if (isa<PHINode>(L->getHeader()->begin())) {

--- 52 unchanged lines hidden (view full) ---

2459
2460/// ComputeBackedgeTakenCount - Compute the number of times the backedge
2461/// of the specified loop will execute.
2462ScalarEvolution::BackedgeTakenInfo
2463ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
2464 // If the loop has a non-one exit block count, we can't analyze it.
2465 BasicBlock *ExitBlock = L->getExitBlock();
2466 if (!ExitBlock)
2399 assert(ItCount.Exact->isLoopInvariant(L) &&
2400 ItCount.Max->isLoopInvariant(L) &&
2401 "Computed trip count isn't loop invariant for loop!");
2402 ++NumTripCountsComputed;
2403
2404 // Update the value in the map.
2405 Pair.first->second = ItCount;
2406 } else if (isa<PHINode>(L->getHeader()->begin())) {

--- 52 unchanged lines hidden (view full) ---

2459
2460/// ComputeBackedgeTakenCount - Compute the number of times the backedge
2461/// of the specified loop will execute.
2462ScalarEvolution::BackedgeTakenInfo
2463ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
2464 // If the loop has a non-one exit block count, we can't analyze it.
2465 BasicBlock *ExitBlock = L->getExitBlock();
2466 if (!ExitBlock)
2467 return UnknownValue;
2467 return CouldNotCompute;
2468
2469 // Okay, there is one exit block. Try to find the condition that causes the
2470 // loop to be exited.
2471 BasicBlock *ExitingBlock = L->getExitingBlock();
2472 if (!ExitingBlock)
2468
2469 // Okay, there is one exit block. Try to find the condition that causes the
2470 // loop to be exited.
2471 BasicBlock *ExitingBlock = L->getExitingBlock();
2472 if (!ExitingBlock)
2473 return UnknownValue; // More than one block exiting!
2473 return CouldNotCompute; // More than one block exiting!
2474
2475 // Okay, we've computed the exiting block. See what condition causes us to
2476 // exit.
2477 //
2478 // FIXME: we should be able to handle switch instructions (with a single exit)
2479 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
2474
2475 // Okay, we've computed the exiting block. See what condition causes us to
2476 // exit.
2477 //
2478 // FIXME: we should be able to handle switch instructions (with a single exit)
2479 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
2480 if (ExitBr == 0) return UnknownValue;
2480 if (ExitBr == 0) return CouldNotCompute;
2481 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
2482
2483 // At this point, we know we have a conditional branch that determines whether
2484 // the loop is exited. However, we don't know if the branch is executed each
2485 // time through the loop. If not, then the execution count of the branch will
2486 // not be equal to the trip count of the loop.
2487 //
2488 // Currently we check for this by checking to see if the Exit branch goes to
2489 // the loop header. If so, we know it will always execute the same number of
2490 // times as the loop. We also handle the case where the exit block *is* the
2491 // loop header. This is common for un-rotated loops. More extensive analysis
2492 // could be done to handle more cases here.
2493 if (ExitBr->getSuccessor(0) != L->getHeader() &&
2494 ExitBr->getSuccessor(1) != L->getHeader() &&
2495 ExitBr->getParent() != L->getHeader())
2481 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
2482
2483 // At this point, we know we have a conditional branch that determines whether
2484 // the loop is exited. However, we don't know if the branch is executed each
2485 // time through the loop. If not, then the execution count of the branch will
2486 // not be equal to the trip count of the loop.
2487 //
2488 // Currently we check for this by checking to see if the Exit branch goes to
2489 // the loop header. If so, we know it will always execute the same number of
2490 // times as the loop. We also handle the case where the exit block *is* the
2491 // loop header. This is common for un-rotated loops. More extensive analysis
2492 // could be done to handle more cases here.
2493 if (ExitBr->getSuccessor(0) != L->getHeader() &&
2494 ExitBr->getSuccessor(1) != L->getHeader() &&
2495 ExitBr->getParent() != L->getHeader())
2496 return UnknownValue;
2496 return CouldNotCompute;
2497
2498 ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
2499
2500 // If it's not an integer or pointer comparison then compute it the hard way.
2501 if (ExitCond == 0)
2502 return ComputeBackedgeTakenCountExhaustively(L, ExitBr->getCondition(),
2503 ExitBr->getSuccessor(0) == ExitBlock);
2504

--- 137 unchanged lines hidden (view full) ---

2642
2643/// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of
2644/// 'icmp op load X, cst', try to see if we can compute the backedge
2645/// execution count.
2646SCEVHandle ScalarEvolution::
2647ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS,
2648 const Loop *L,
2649 ICmpInst::Predicate predicate) {
2497
2498 ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
2499
2500 // If it's not an integer or pointer comparison then compute it the hard way.
2501 if (ExitCond == 0)
2502 return ComputeBackedgeTakenCountExhaustively(L, ExitBr->getCondition(),
2503 ExitBr->getSuccessor(0) == ExitBlock);
2504

--- 137 unchanged lines hidden (view full) ---

2642
2643/// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of
2644/// 'icmp op load X, cst', try to see if we can compute the backedge
2645/// execution count.
2646SCEVHandle ScalarEvolution::
2647ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS,
2648 const Loop *L,
2649 ICmpInst::Predicate predicate) {
2650 if (LI->isVolatile()) return UnknownValue;
2650 if (LI->isVolatile()) return CouldNotCompute;
2651
2652 // Check to see if the loaded pointer is a getelementptr of a global.
2653 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
2651
2652 // Check to see if the loaded pointer is a getelementptr of a global.
2653 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
2654 if (!GEP) return UnknownValue;
2654 if (!GEP) return CouldNotCompute;
2655
2656 // Make sure that it is really a constant global we are gepping, with an
2657 // initializer, and make sure the first IDX is really 0.
2658 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
2659 if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
2660 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
2661 !cast<Constant>(GEP->getOperand(1))->isNullValue())
2655
2656 // Make sure that it is really a constant global we are gepping, with an
2657 // initializer, and make sure the first IDX is really 0.
2658 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
2659 if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
2660 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
2661 !cast<Constant>(GEP->getOperand(1))->isNullValue())
2662 return UnknownValue;
2662 return CouldNotCompute;
2663
2664 // Okay, we allow one non-constant index into the GEP instruction.
2665 Value *VarIdx = 0;
2666 std::vector<ConstantInt*> Indexes;
2667 unsigned VarIdxNum = 0;
2668 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
2669 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
2670 Indexes.push_back(CI);
2671 } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
2663
2664 // Okay, we allow one non-constant index into the GEP instruction.
2665 Value *VarIdx = 0;
2666 std::vector<ConstantInt*> Indexes;
2667 unsigned VarIdxNum = 0;
2668 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
2669 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
2670 Indexes.push_back(CI);
2671 } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
2672 if (VarIdx) return UnknownValue; // Multiple non-constant idx's.
2672 if (VarIdx) return CouldNotCompute; // Multiple non-constant idx's.
2673 VarIdx = GEP->getOperand(i);
2674 VarIdxNum = i-2;
2675 Indexes.push_back(0);
2676 }
2677
2678 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
2679 // Check to see if X is a loop variant variable value now.
2680 SCEVHandle Idx = getSCEV(VarIdx);
2681 Idx = getSCEVAtScope(Idx, L);
2682
2683 // We can only recognize very limited forms of loop index expressions, in
2684 // particular, only affine AddRec's like {C1,+,C2}.
2685 const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
2686 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
2687 !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
2688 !isa<SCEVConstant>(IdxExpr->getOperand(1)))
2673 VarIdx = GEP->getOperand(i);
2674 VarIdxNum = i-2;
2675 Indexes.push_back(0);
2676 }
2677
2678 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
2679 // Check to see if X is a loop variant variable value now.
2680 SCEVHandle Idx = getSCEV(VarIdx);
2681 Idx = getSCEVAtScope(Idx, L);
2682
2683 // We can only recognize very limited forms of loop index expressions, in
2684 // particular, only affine AddRec's like {C1,+,C2}.
2685 const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
2686 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
2687 !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
2688 !isa<SCEVConstant>(IdxExpr->getOperand(1)))
2689 return UnknownValue;
2689 return CouldNotCompute;
2690
2691 unsigned MaxSteps = MaxBruteForceIterations;
2692 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
2693 ConstantInt *ItCst =
2694 ConstantInt::get(IdxExpr->getType(), IterationNum);
2695 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
2696
2697 // Form the GEP offset.

--- 10 unchanged lines hidden (view full) ---

2708 errs() << "\n***\n*** Computed loop count " << *ItCst
2709 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
2710 << "***\n";
2711#endif
2712 ++NumArrayLenItCounts;
2713 return getConstant(ItCst); // Found terminating iteration!
2714 }
2715 }
2690
2691 unsigned MaxSteps = MaxBruteForceIterations;
2692 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
2693 ConstantInt *ItCst =
2694 ConstantInt::get(IdxExpr->getType(), IterationNum);
2695 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
2696
2697 // Form the GEP offset.

--- 10 unchanged lines hidden (view full) ---

2708 errs() << "\n***\n*** Computed loop count " << *ItCst
2709 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
2710 << "***\n";
2711#endif
2712 ++NumArrayLenItCounts;
2713 return getConstant(ItCst); // Found terminating iteration!
2714 }
2715 }
2716 return UnknownValue;
2716 return CouldNotCompute;
2717}
2718
2719
2720/// CanConstantFold - Return true if we can constant fold an instruction of the
2721/// specified type, assuming that all operands were constants.
2722static bool CanConstantFold(const Instruction *I) {
2723 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
2724 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))

--- 122 unchanged lines hidden (view full) ---

2847 PHIVal = NextPHI;
2848 }
2849}
2850
2851/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
2852/// constant number of times (the condition evolves only from constants),
2853/// try to evaluate a few iterations of the loop until we get the exit
2854/// condition gets a value of ExitWhen (true or false). If we cannot
2717}
2718
2719
2720/// CanConstantFold - Return true if we can constant fold an instruction of the
2721/// specified type, assuming that all operands were constants.
2722static bool CanConstantFold(const Instruction *I) {
2723 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
2724 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))

--- 122 unchanged lines hidden (view full) ---

2847 PHIVal = NextPHI;
2848 }
2849}
2850
2851/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
2852/// constant number of times (the condition evolves only from constants),
2853/// try to evaluate a few iterations of the loop until we get the exit
2854/// condition gets a value of ExitWhen (true or false). If we cannot
2855/// evaluate the trip count of the loop, return UnknownValue.
2855/// evaluate the trip count of the loop, return CouldNotCompute.
2856SCEVHandle ScalarEvolution::
2857ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
2858 PHINode *PN = getConstantEvolvingPHI(Cond, L);
2856SCEVHandle ScalarEvolution::
2857ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
2858 PHINode *PN = getConstantEvolvingPHI(Cond, L);
2859 if (PN == 0) return UnknownValue;
2859 if (PN == 0) return CouldNotCompute;
2860
2861 // Since the loop is canonicalized, the PHI node must have two entries. One
2862 // entry must be a constant (coming in from outside of the loop), and the
2863 // second must be derived from the same PHI.
2864 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2865 Constant *StartCST =
2866 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2860
2861 // Since the loop is canonicalized, the PHI node must have two entries. One
2862 // entry must be a constant (coming in from outside of the loop), and the
2863 // second must be derived from the same PHI.
2864 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2865 Constant *StartCST =
2866 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2867 if (StartCST == 0) return UnknownValue; // Must be a constant.
2867 if (StartCST == 0) return CouldNotCompute; // Must be a constant.
2868
2869 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2870 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2868
2869 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2870 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2871 if (PN2 != PN) return UnknownValue; // Not derived from same PHI.
2871 if (PN2 != PN) return CouldNotCompute; // Not derived from same PHI.
2872
2873 // Okay, we find a PHI node that defines the trip count of this loop. Execute
2874 // the loop symbolically to determine when the condition gets a value of
2875 // "ExitWhen".
2876 unsigned IterationNum = 0;
2877 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
2878 for (Constant *PHIVal = StartCST;
2879 IterationNum != MaxIterations; ++IterationNum) {
2880 ConstantInt *CondVal =
2881 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
2882
2883 // Couldn't symbolically evaluate.
2872
2873 // Okay, we find a PHI node that defines the trip count of this loop. Execute
2874 // the loop symbolically to determine when the condition gets a value of
2875 // "ExitWhen".
2876 unsigned IterationNum = 0;
2877 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
2878 for (Constant *PHIVal = StartCST;
2879 IterationNum != MaxIterations; ++IterationNum) {
2880 ConstantInt *CondVal =
2881 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
2882
2883 // Couldn't symbolically evaluate.
2884 if (!CondVal) return UnknownValue;
2884 if (!CondVal) return CouldNotCompute;
2885
2886 if (CondVal->getValue() == uint64_t(ExitWhen)) {
2887 ConstantEvolutionLoopExitValue[PN] = PHIVal;
2888 ++NumBruteForceTripCountsComputed;
2889 return getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
2890 }
2891
2892 // Compute the value of the PHI node for the next iteration.
2893 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2894 if (NextPHI == 0 || NextPHI == PHIVal)
2885
2886 if (CondVal->getValue() == uint64_t(ExitWhen)) {
2887 ConstantEvolutionLoopExitValue[PN] = PHIVal;
2888 ++NumBruteForceTripCountsComputed;
2889 return getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
2890 }
2891
2892 // Compute the value of the PHI node for the next iteration.
2893 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2894 if (NextPHI == 0 || NextPHI == PHIVal)
2895 return UnknownValue; // Couldn't evaluate or not making progress...
2895 return CouldNotCompute; // Couldn't evaluate or not making progress...
2896 PHIVal = NextPHI;
2897 }
2898
2899 // Too many iterations were needed to evaluate.
2896 PHIVal = NextPHI;
2897 }
2898
2899 // Too many iterations were needed to evaluate.
2900 return UnknownValue;
2900 return CouldNotCompute;
2901}
2902
2903/// getSCEVAtScope - Return a SCEV expression handle for the specified value
2904/// at the specified scope in the program. The L value specifies a loop
2905/// nest to evaluate the expression at, where null is the top-level or a
2906/// specified loop is immediately inside of the loop.
2907///
2908/// This method can be used to compute the exit value for a variable defined

--- 138 unchanged lines hidden (view full) ---

3047
3048 // If this is a loop recurrence for a loop that does not contain L, then we
3049 // are dealing with the final value computed by the loop.
3050 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
3051 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
3052 // To evaluate this recurrence, we need to know how many times the AddRec
3053 // loop iterates. Compute this now.
3054 SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
2901}
2902
2903/// getSCEVAtScope - Return a SCEV expression handle for the specified value
2904/// at the specified scope in the program. The L value specifies a loop
2905/// nest to evaluate the expression at, where null is the top-level or a
2906/// specified loop is immediately inside of the loop.
2907///
2908/// This method can be used to compute the exit value for a variable defined

--- 138 unchanged lines hidden (view full) ---

3047
3048 // If this is a loop recurrence for a loop that does not contain L, then we
3049 // are dealing with the final value computed by the loop.
3050 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
3051 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
3052 // To evaluate this recurrence, we need to know how many times the AddRec
3053 // loop iterates. Compute this now.
3054 SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
3055 if (BackedgeTakenCount == UnknownValue) return AddRec;
3055 if (BackedgeTakenCount == CouldNotCompute) return AddRec;
3056
3057 // Then, evaluate the AddRec.
3058 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
3059 }
3060 return AddRec;
3061 }
3062
3063 if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {

--- 132 unchanged lines hidden (view full) ---

3196 ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
3197
3198 return std::make_pair(SE.getConstant(Solution1),
3199 SE.getConstant(Solution2));
3200 } // end APIntOps namespace
3201}
3202
3203/// HowFarToZero - Return the number of times a backedge comparing the specified
3056
3057 // Then, evaluate the AddRec.
3058 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
3059 }
3060 return AddRec;
3061 }
3062
3063 if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {

--- 132 unchanged lines hidden (view full) ---

3196 ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
3197
3198 return std::make_pair(SE.getConstant(Solution1),
3199 SE.getConstant(Solution2));
3200 } // end APIntOps namespace
3201}
3202
3203/// HowFarToZero - Return the number of times a backedge comparing the specified
3204/// value to zero will execute. If not computable, return UnknownValue.
3204/// value to zero will execute. If not computable, return CouldNotCompute.
3205SCEVHandle ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
3206 // If the value is a constant
3207 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3208 // If the value is already zero, the branch will execute zero times.
3209 if (C->getValue()->isZero()) return C;
3205SCEVHandle ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
3206 // If the value is a constant
3207 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3208 // If the value is already zero, the branch will execute zero times.
3209 if (C->getValue()->isZero()) return C;
3210 return UnknownValue; // Otherwise it will loop infinitely.
3210 return CouldNotCompute; // Otherwise it will loop infinitely.
3211 }
3212
3213 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
3214 if (!AddRec || AddRec->getLoop() != L)
3211 }
3212
3213 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
3214 if (!AddRec || AddRec->getLoop() != L)
3215 return UnknownValue;
3215 return CouldNotCompute;
3216
3217 if (AddRec->isAffine()) {
3218 // If this is an affine expression, the execution count of this branch is
3219 // the minimum unsigned root of the following equation:
3220 //
3221 // Start + Step*N = 0 (mod 2^BW)
3222 //
3223 // equivalent to:

--- 45 unchanged lines hidden (view full) ---

3269 // should not accept a root of 2.
3270 SCEVHandle Val = AddRec->evaluateAtIteration(R1, *this);
3271 if (Val->isZero())
3272 return R1; // We found a quadratic root!
3273 }
3274 }
3275 }
3276
3216
3217 if (AddRec->isAffine()) {
3218 // If this is an affine expression, the execution count of this branch is
3219 // the minimum unsigned root of the following equation:
3220 //
3221 // Start + Step*N = 0 (mod 2^BW)
3222 //
3223 // equivalent to:

--- 45 unchanged lines hidden (view full) ---

3269 // should not accept a root of 2.
3270 SCEVHandle Val = AddRec->evaluateAtIteration(R1, *this);
3271 if (Val->isZero())
3272 return R1; // We found a quadratic root!
3273 }
3274 }
3275 }
3276
3277 return UnknownValue;
3277 return CouldNotCompute;
3278}
3279
3280/// HowFarToNonZero - Return the number of times a backedge checking the
3281/// specified value for nonzero will execute. If not computable, return
3278}
3279
3280/// HowFarToNonZero - Return the number of times a backedge checking the
3281/// specified value for nonzero will execute. If not computable, return
3282/// UnknownValue
3282/// CouldNotCompute
3283SCEVHandle ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
3284 // Loops that look like: while (X == 0) are very strange indeed. We don't
3285 // handle them yet except for the trivial case. This could be expanded in the
3286 // future as needed.
3287
3288 // If the value is a constant, check to see if it is known to be non-zero
3289 // already. If so, the backedge will execute zero times.
3290 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3291 if (!C->getValue()->isNullValue())
3292 return getIntegerSCEV(0, C->getType());
3283SCEVHandle ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
3284 // Loops that look like: while (X == 0) are very strange indeed. We don't
3285 // handle them yet except for the trivial case. This could be expanded in the
3286 // future as needed.
3287
3288 // If the value is a constant, check to see if it is known to be non-zero
3289 // already. If so, the backedge will execute zero times.
3290 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3291 if (!C->getValue()->isNullValue())
3292 return getIntegerSCEV(0, C->getType());
3293 return UnknownValue; // Otherwise it will loop infinitely.
3293 return CouldNotCompute; // Otherwise it will loop infinitely.
3294 }
3295
3296 // We could implement others, but I really doubt anyone writes loops like
3297 // this, and if they did, they would already be constant folded.
3294 }
3295
3296 // We could implement others, but I really doubt anyone writes loops like
3297 // this, and if they did, they would already be constant folded.
3298 return UnknownValue;
3298 return CouldNotCompute;
3299}
3300
3301/// getLoopPredecessor - If the given loop's header has exactly one unique
3302/// predecessor outside the loop, return it. Otherwise return null.
3303///
3304BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
3305 BasicBlock *Header = L->getHeader();
3306 BasicBlock *Pred = 0;

--- 134 unchanged lines hidden (view full) ---

3441 return true;
3442 }
3443
3444 return false;
3445}
3446
3447/// HowManyLessThans - Return the number of times a backedge containing the
3448/// specified less-than comparison will execute. If not computable, return
3299}
3300
3301/// getLoopPredecessor - If the given loop's header has exactly one unique
3302/// predecessor outside the loop, return it. Otherwise return null.
3303///
3304BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
3305 BasicBlock *Header = L->getHeader();
3306 BasicBlock *Pred = 0;

--- 134 unchanged lines hidden (view full) ---

3441 return true;
3442 }
3443
3444 return false;
3445}
3446
3447/// HowManyLessThans - Return the number of times a backedge containing the
3448/// specified less-than comparison will execute. If not computable, return
3449/// UnknownValue.
3449/// CouldNotCompute.
3450ScalarEvolution::BackedgeTakenInfo ScalarEvolution::
3451HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
3452 const Loop *L, bool isSigned) {
3453 // Only handle: "ADDREC < LoopInvariant".
3450ScalarEvolution::BackedgeTakenInfo ScalarEvolution::
3451HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
3452 const Loop *L, bool isSigned) {
3453 // Only handle: "ADDREC < LoopInvariant".
3454 if (!RHS->isLoopInvariant(L)) return UnknownValue;
3454 if (!RHS->isLoopInvariant(L)) return CouldNotCompute;
3455
3456 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
3457 if (!AddRec || AddRec->getLoop() != L)
3455
3456 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
3457 if (!AddRec || AddRec->getLoop() != L)
3458 return UnknownValue;
3458 return CouldNotCompute;
3459
3460 if (AddRec->isAffine()) {
3461 // FORNOW: We only support unit strides.
3462 unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
3463 SCEVHandle Step = AddRec->getStepRecurrence(*this);
3464 SCEVHandle NegOne = getIntegerSCEV(-1, AddRec->getType());
3465
3466 // TODO: handle non-constant strides.
3467 const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
3468 if (!CStep || CStep->isZero())
3459
3460 if (AddRec->isAffine()) {
3461 // FORNOW: We only support unit strides.
3462 unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
3463 SCEVHandle Step = AddRec->getStepRecurrence(*this);
3464 SCEVHandle NegOne = getIntegerSCEV(-1, AddRec->getType());
3465
3466 // TODO: handle non-constant strides.
3467 const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
3468 if (!CStep || CStep->isZero())
3469 return UnknownValue;
3469 return CouldNotCompute;
3470 if (CStep->isOne()) {
3471 // With unit stride, the iteration never steps past the limit value.
3472 } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
3473 if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
3474 // Test whether a positive iteration iteration can step past the limit
3475 // value and past the maximum value for its type in a single step.
3476 if (isSigned) {
3477 APInt Max = APInt::getSignedMaxValue(BitWidth);
3478 if ((Max - CStep->getValue()->getValue())
3479 .slt(CLimit->getValue()->getValue()))
3470 if (CStep->isOne()) {
3471 // With unit stride, the iteration never steps past the limit value.
3472 } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
3473 if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
3474 // Test whether a positive iteration iteration can step past the limit
3475 // value and past the maximum value for its type in a single step.
3476 if (isSigned) {
3477 APInt Max = APInt::getSignedMaxValue(BitWidth);
3478 if ((Max - CStep->getValue()->getValue())
3479 .slt(CLimit->getValue()->getValue()))
3480 return UnknownValue;
3480 return CouldNotCompute;
3481 } else {
3482 APInt Max = APInt::getMaxValue(BitWidth);
3483 if ((Max - CStep->getValue()->getValue())
3484 .ult(CLimit->getValue()->getValue()))
3481 } else {
3482 APInt Max = APInt::getMaxValue(BitWidth);
3483 if ((Max - CStep->getValue()->getValue())
3484 .ult(CLimit->getValue()->getValue()))
3485 return UnknownValue;
3485 return CouldNotCompute;
3486 }
3487 } else
3488 // TODO: handle non-constant limit values below.
3486 }
3487 } else
3488 // TODO: handle non-constant limit values below.
3489 return UnknownValue;
3489 return CouldNotCompute;
3490 } else
3491 // TODO: handle negative strides below.
3490 } else
3491 // TODO: handle negative strides below.
3492 return UnknownValue;
3492 return CouldNotCompute;
3493
3494 // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
3495 // m. So, we count the number of iterations in which {n,+,s} < m is true.
3496 // Note that we cannot simply return max(m-n,0)/s because it's not safe to
3497 // treat m-n as signed nor unsigned due to overflow possibility.
3498
3499 // First, we get the value of the LHS in the first iteration: n
3500 SCEVHandle Start = AddRec->getOperand(0);

--- 30 unchanged lines hidden (view full) ---

3531 SCEVHandle MaxBECount = getUDivExpr(getAddExpr(getMinusSCEV(MaxEnd,
3532 MinStart),
3533 getAddExpr(Step, NegOne)),
3534 Step);
3535
3536 return BackedgeTakenInfo(BECount, MaxBECount);
3537 }
3538
3493
3494 // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
3495 // m. So, we count the number of iterations in which {n,+,s} < m is true.
3496 // Note that we cannot simply return max(m-n,0)/s because it's not safe to
3497 // treat m-n as signed nor unsigned due to overflow possibility.
3498
3499 // First, we get the value of the LHS in the first iteration: n
3500 SCEVHandle Start = AddRec->getOperand(0);

--- 30 unchanged lines hidden (view full) ---

3531 SCEVHandle MaxBECount = getUDivExpr(getAddExpr(getMinusSCEV(MaxEnd,
3532 MinStart),
3533 getAddExpr(Step, NegOne)),
3534 Step);
3535
3536 return BackedgeTakenInfo(BECount, MaxBECount);
3537 }
3538
3539 return UnknownValue;
3539 return CouldNotCompute;
3540}
3541
3542/// getNumIterationsInRange - Return the number of iterations of this loop that
3543/// produce values in the specified constant range. Another way of looking at
3544/// this is that it returns the first iteration number where the value is not in
3545/// the condition, thus computing the exit count. If the iteration count can't
3546/// be computed, an instance of SCEVCouldNotCompute is returned.
3547SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,

--- 171 unchanged lines hidden (view full) ---

3719ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
3720 : CallbackVH(V), SE(se) {}
3721
3722//===----------------------------------------------------------------------===//
3723// ScalarEvolution Class Implementation
3724//===----------------------------------------------------------------------===//
3725
3726ScalarEvolution::ScalarEvolution()
3540}
3541
3542/// getNumIterationsInRange - Return the number of iterations of this loop that
3543/// produce values in the specified constant range. Another way of looking at
3544/// this is that it returns the first iteration number where the value is not in
3545/// the condition, thus computing the exit count. If the iteration count can't
3546/// be computed, an instance of SCEVCouldNotCompute is returned.
3547SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,

--- 171 unchanged lines hidden (view full) ---

3719ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
3720 : CallbackVH(V), SE(se) {}
3721
3722//===----------------------------------------------------------------------===//
3723// ScalarEvolution Class Implementation
3724//===----------------------------------------------------------------------===//
3725
3726ScalarEvolution::ScalarEvolution()
3727 : FunctionPass(&ID), UnknownValue(new SCEVCouldNotCompute()) {
3727 : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
3728}
3729
3730bool ScalarEvolution::runOnFunction(Function &F) {
3731 this->F = &F;
3732 LI = &getAnalysis<LoopInfo>();
3733 TD = getAnalysisIfAvailable<TargetData>();
3734 return false;
3735}

--- 79 unchanged lines hidden --- 		3728}
3729
3730bool ScalarEvolution::runOnFunction(Function &F) {
3731 this->F = &F;
3732 LI = &getAnalysis<LoopInfo>();
3733 TD = getAnalysisIfAvailable<TargetData>();
3734 return false;
3735}

--- 79 unchanged lines hidden ---