aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/lib/Analysis/ScalarEvolution.cpp')
-rw-r--r--contrib/llvm/lib/Analysis/ScalarEvolution.cpp166
1 files changed, 114 insertions, 52 deletions
diff --git a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
index e3189ecc8994..f876748af3dc 100644
--- a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -59,22 +59,25 @@
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "scalar-evolution"
-#include "llvm/Analysis/ScalarEvolutionExpressions.h"
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/GlobalVariable.h"
-#include "llvm/GlobalAlias.h"
-#include "llvm/Instructions.h"
-#include "llvm/LLVMContext.h"
-#include "llvm/Operator.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
-#include "llvm/DataLayout.h"
-#include "llvm/Target/TargetLibraryInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/GlobalAlias.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/Debug.h"
@@ -83,9 +86,7 @@
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Target/TargetLibraryInfo.h"
#include <algorithm>
using namespace llvm;
@@ -3936,10 +3937,19 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) {
/// before taking the branch. For loops with multiple exits, it may not be the
/// number times that the loop header executes because the loop may exit
/// prematurely via another branch.
+///
+/// FIXME: We conservatively call getBackedgeTakenCount(L) instead of
+/// getExitCount(L, ExitingBlock) to compute a safe trip count considering all
+/// loop exits. getExitCount() may return an exact count for this branch
+/// assuming no-signed-wrap. The number of well-defined iterations may actually
+/// be higher than this trip count if this exit test is skipped and the loop
+/// exits via a different branch. Ideally, getExitCount() would know whether it
+/// depends on a NSW assumption, and we would only fall back to a conservative
+/// trip count in that case.
unsigned ScalarEvolution::
-getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock) {
+getSmallConstantTripCount(Loop *L, BasicBlock */*ExitingBlock*/) {
const SCEVConstant *ExitCount =
- dyn_cast<SCEVConstant>(getExitCount(L, ExitingBlock));
+ dyn_cast<SCEVConstant>(getBackedgeTakenCount(L));
if (!ExitCount)
return 0;
@@ -3966,8 +3976,8 @@ getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock) {
/// As explained in the comments for getSmallConstantTripCount, this assumes
/// that control exits the loop via ExitingBlock.
unsigned ScalarEvolution::
-getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock) {
- const SCEV *ExitCount = getExitCount(L, ExitingBlock);
+getSmallConstantTripMultiple(Loop *L, BasicBlock */*ExitingBlock*/) {
+ const SCEV *ExitCount = getBackedgeTakenCount(L);
if (ExitCount == getCouldNotCompute())
return 1;
@@ -3996,7 +4006,7 @@ getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock) {
}
// getExitCount - Get the expression for the number of loop iterations for which
-// this loop is guaranteed not to exit via ExitintBlock. Otherwise return
+// this loop is guaranteed not to exit via ExitingBlock. Otherwise return
// SCEVCouldNotCompute.
const SCEV *ScalarEvolution::getExitCount(Loop *L, BasicBlock *ExitingBlock) {
return getBackedgeTakenInfo(L).getExact(ExitingBlock, this);
@@ -4229,6 +4239,25 @@ ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const {
return Max ? Max : SE->getCouldNotCompute();
}
+bool ScalarEvolution::BackedgeTakenInfo::hasOperand(const SCEV *S,
+ ScalarEvolution *SE) const {
+ if (Max && Max != SE->getCouldNotCompute() && SE->hasOperand(Max, S))
+ return true;
+
+ if (!ExitNotTaken.ExitingBlock)
+ return false;
+
+ for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
+ ENT != 0; ENT = ENT->getNextExit()) {
+
+ if (ENT->ExactNotTaken != SE->getCouldNotCompute()
+ && SE->hasOperand(ENT->ExactNotTaken, S)) {
+ return true;
+ }
+ }
+ return false;
+}
+
/// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
/// computable exit into a persistent ExitNotTakenInfo array.
ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
@@ -4362,26 +4391,36 @@ ScalarEvolution::ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock) {
// Proceed to the next level to examine the exit condition expression.
return ComputeExitLimitFromCond(L, ExitBr->getCondition(),
ExitBr->getSuccessor(0),
- ExitBr->getSuccessor(1));
+ ExitBr->getSuccessor(1),
+ /*IsSubExpr=*/false);
}
/// ComputeExitLimitFromCond - Compute the number of times the
/// backedge of the specified loop will execute if its exit condition
/// were a conditional branch of ExitCond, TBB, and FBB.
+///
+/// @param IsSubExpr is true if ExitCond does not directly control the exit
+/// branch. In this case, we cannot assume that the loop only exits when the
+/// condition is true and cannot infer that failing to meet the condition prior
+/// to integer wraparound results in undefined behavior.
ScalarEvolution::ExitLimit
ScalarEvolution::ComputeExitLimitFromCond(const Loop *L,
Value *ExitCond,
BasicBlock *TBB,
- BasicBlock *FBB) {
+ BasicBlock *FBB,
+ bool IsSubExpr) {
// Check if the controlling expression for this loop is an And or Or.
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
if (BO->getOpcode() == Instruction::And) {
// Recurse on the operands of the and.
- ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB);
- ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB);
+ bool EitherMayExit = L->contains(TBB);
+ ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
+ IsSubExpr || EitherMayExit);
+ ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
+ IsSubExpr || EitherMayExit);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
- if (L->contains(TBB)) {
+ if (EitherMayExit) {
// Both conditions must be true for the loop to continue executing.
// Choose the less conservative count.
if (EL0.Exact == getCouldNotCompute() ||
@@ -4409,11 +4448,14 @@ ScalarEvolution::ComputeExitLimitFromCond(const Loop *L,
}
if (BO->getOpcode() == Instruction::Or) {
// Recurse on the operands of the or.
- ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB);
- ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB);
+ bool EitherMayExit = L->contains(FBB);
+ ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
+ IsSubExpr || EitherMayExit);
+ ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
+ IsSubExpr || EitherMayExit);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
- if (L->contains(FBB)) {
+ if (EitherMayExit) {
// Both conditions must be false for the loop to continue executing.
// Choose the less conservative count.
if (EL0.Exact == getCouldNotCompute() ||
@@ -4444,7 +4486,7 @@ ScalarEvolution::ComputeExitLimitFromCond(const Loop *L,
// With an icmp, it may be feasible to compute an exact backedge-taken count.
// Proceed to the next level to examine the icmp.
if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
- return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB);
+ return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, IsSubExpr);
// Check for a constant condition. These are normally stripped out by
// SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to
@@ -4470,7 +4512,8 @@ ScalarEvolution::ExitLimit
ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L,
ICmpInst *ExitCond,
BasicBlock *TBB,
- BasicBlock *FBB) {
+ BasicBlock *FBB,
+ bool IsSubExpr) {
// If the condition was exit on true, convert the condition to exit on false
ICmpInst::Predicate Cond;
@@ -4522,7 +4565,7 @@ ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L,
switch (Cond) {
case ICmpInst::ICMP_NE: { // while (X != Y)
// Convert to: while (X-Y != 0)
- ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L);
+ ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
@@ -4533,24 +4576,24 @@ ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L,
break;
}
case ICmpInst::ICMP_SLT: {
- ExitLimit EL = HowManyLessThans(LHS, RHS, L, true);
+ ExitLimit EL = HowManyLessThans(LHS, RHS, L, true, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_SGT: {
ExitLimit EL = HowManyLessThans(getNotSCEV(LHS),
- getNotSCEV(RHS), L, true);
+ getNotSCEV(RHS), L, true, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_ULT: {
- ExitLimit EL = HowManyLessThans(LHS, RHS, L, false);
+ ExitLimit EL = HowManyLessThans(LHS, RHS, L, false, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_UGT: {
ExitLimit EL = HowManyLessThans(getNotSCEV(LHS),
- getNotSCEV(RHS), L, false);
+ getNotSCEV(RHS), L, false, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
@@ -5419,7 +5462,7 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
/// effectively V != 0. We know and take advantage of the fact that this
/// expression only being used in a comparison by zero context.
ScalarEvolution::ExitLimit
-ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
+ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr) {
// If the value is a constant
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
// If the value is already zero, the branch will execute zero times.
@@ -5517,19 +5560,20 @@ ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
}
// If the recurrence is known not to wraparound, unsigned divide computes the
- // back edge count. We know that the value will either become zero (and thus
- // the loop terminates), that the loop will terminate through some other exit
- // condition first, or that the loop has undefined behavior. This means
- // we can't "miss" the exit value, even with nonunit stride.
+ // back edge count. (Ideally we would have an "isexact" bit for udiv). We know
+ // that the value will either become zero (and thus the loop terminates), that
+ // the loop will terminate through some other exit condition first, or that
+ // the loop has undefined behavior. This means we can't "miss" the exit
+ // value, even with nonunit stride.
//
- // FIXME: Prove that loops always exhibits *acceptable* undefined
- // behavior. Loops must exhibit defined behavior until a wrapped value is
- // actually used. So the trip count computed by udiv could be smaller than the
- // number of well-defined iterations.
- if (AddRec->getNoWrapFlags(SCEV::FlagNW)) {
- // FIXME: We really want an "isexact" bit for udiv.
+ // This is only valid for expressions that directly compute the loop exit. It
+ // is invalid for subexpressions in which the loop may exit through this
+ // branch even if this subexpression is false. In that case, the trip count
+ // computed by this udiv could be smaller than the number of well-defined
+ // iterations.
+ if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW))
return getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
- }
+
// Then, try to solve the above equation provided that Start is constant.
if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
@@ -6120,8 +6164,8 @@ bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred,
getTypeSizeInBits(ICI->getOperand(0)->getType()))
return false;
- // Now that we found a conditional branch that dominates the loop, check to
- // see if it is the comparison we are looking for.
+ // 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.
ICmpInst::Predicate FoundPred;
if (Inverse)
FoundPred = ICI->getInversePredicate();
@@ -6295,9 +6339,14 @@ const SCEV *ScalarEvolution::getBECount(const SCEV *Start,
/// HowManyLessThans - Return the number of times a backedge containing the
/// specified less-than comparison will execute. If not computable, return
/// CouldNotCompute.
+///
+/// @param IsSubExpr is true when the LHS < RHS condition does not directly
+/// control the branch. In this case, we can only compute an iteration count for
+/// a subexpression that cannot overflow before evaluating true.
ScalarEvolution::ExitLimit
ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
- const Loop *L, bool isSigned) {
+ const Loop *L, bool isSigned,
+ bool IsSubExpr) {
// Only handle: "ADDREC < LoopInvariant".
if (!isLoopInvariant(RHS, L)) return getCouldNotCompute();
@@ -6306,10 +6355,12 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
return getCouldNotCompute();
// Check to see if we have a flag which makes analysis easy.
- bool NoWrap = isSigned ?
- AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNW)) :
- AddRec->getNoWrapFlags((SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNW));
-
+ bool NoWrap = false;
+ if (!IsSubExpr) {
+ NoWrap = AddRec->getNoWrapFlags(
+ (SCEV::NoWrapFlags)(((isSigned ? SCEV::FlagNSW : SCEV::FlagNUW))
+ | SCEV::FlagNW));
+ }
if (AddRec->isAffine()) {
unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
const SCEV *Step = AddRec->getStepRecurrence(*this);
@@ -6939,6 +6990,17 @@ void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
BlockDispositions.erase(S);
UnsignedRanges.erase(S);
SignedRanges.erase(S);
+
+ for (DenseMap<const Loop*, BackedgeTakenInfo>::iterator I =
+ BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end(); I != E; ) {
+ BackedgeTakenInfo &BEInfo = I->second;
+ if (BEInfo.hasOperand(S, this)) {
+ BEInfo.clear();
+ BackedgeTakenCounts.erase(I++);
+ }
+ else
+ ++I;
+ }
}
typedef DenseMap<const Loop *, std::string> VerifyMap;
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-26 16:00:56 +0000