#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/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
INITIALIZE_PASS_BEGIN(ScalarEvolution, "scalar-evolution",
"Scalar Evolution Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
-INITIALIZE_PASS_DEPENDENCY(DominatorTree)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
INITIALIZE_PASS_END(ScalarEvolution, "scalar-evolution",
"Scalar Evolution Analysis", false, true)
void SCEV::print(raw_ostream &OS) const {
switch (getSCEVType()) {
case scConstant:
- WriteAsOperand(OS, cast<SCEVConstant>(this)->getValue(), false);
+ cast<SCEVConstant>(this)->getValue()->printAsOperand(OS, false);
return;
case scTruncate: {
const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(this);
if (AR->getNoWrapFlags(FlagNW) &&
!AR->getNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)))
OS << "nw><";
- WriteAsOperand(OS, AR->getLoop()->getHeader(), /*PrintType=*/false);
+ AR->getLoop()->getHeader()->printAsOperand(OS, /*PrintType=*/false);
OS << ">";
return;
}
Constant *FieldNo;
if (U->isOffsetOf(CTy, FieldNo)) {
OS << "offsetof(" << *CTy << ", ";
- WriteAsOperand(OS, FieldNo, false);
+ FieldNo->printAsOperand(OS, false);
OS << ")";
return;
}
// Otherwise just print it normally.
- WriteAsOperand(OS, U->getValue(), false);
+ U->getValue()->printAsOperand(OS, false);
return;
}
case scCouldNotCompute:
// Examine all exits and pick the most conservative values.
const SCEV *MaxBECount = getCouldNotCompute();
bool CouldComputeBECount = true;
+ BasicBlock *Latch = L->getLoopLatch(); // may be NULL.
+ const SCEV *LatchMaxCount = 0;
SmallVector<std::pair<BasicBlock *, const SCEV *>, 4> ExitCounts;
for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
ExitLimit EL = ComputeExitLimit(L, ExitingBlocks[i]);
// We cannot take the "min" MaxBECount, because non-unit stride loops may
// skip some loop tests. Taking the max over the exits is sufficiently
// conservative. TODO: We could do better taking into consideration
- // that (1) the loop has unit stride (2) the last loop test is
- // less-than/greater-than (3) any loop test is less-than/greater-than AND
- // falls-through some constant times less then the other tests.
- MaxBECount = getUMaxFromMismatchedTypes(MaxBECount, EL.Max);
+ // non-latch exits that dominate the latch.
+ if (EL.MustExit && ExitingBlocks[i] == Latch)
+ LatchMaxCount = EL.Max;
+ else
+ MaxBECount = getUMaxFromMismatchedTypes(MaxBECount, EL.Max);
}
}
-
+ // Be more precise in the easy case of a loop latch that must exit.
+ if (LatchMaxCount) {
+ MaxBECount = getUMinFromMismatchedTypes(MaxBECount, LatchMaxCount);
+ }
return BackedgeTakenInfo(ExitCounts, CouldComputeBECount, MaxBECount);
}
IsSubExpr || EitherMayExit);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
+ bool MustExit = false;
if (EitherMayExit) {
// Both conditions must be true for the loop to continue executing.
// Choose the less conservative count.
MaxBECount = EL0.Max;
else
MaxBECount = getUMinFromMismatchedTypes(EL0.Max, EL1.Max);
+ MustExit = EL0.MustExit || EL1.MustExit;
} else {
// Both conditions must be true at the same time for the loop to exit.
// For now, be conservative.
MaxBECount = EL0.Max;
if (EL0.Exact == EL1.Exact)
BECount = EL0.Exact;
+ MustExit = EL0.MustExit && EL1.MustExit;
}
- return ExitLimit(BECount, MaxBECount);
+ return ExitLimit(BECount, MaxBECount, MustExit);
}
if (BO->getOpcode() == Instruction::Or) {
// Recurse on the operands of the or.
IsSubExpr || EitherMayExit);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
+ bool MustExit = false;
if (EitherMayExit) {
// Both conditions must be false for the loop to continue executing.
// Choose the less conservative count.
MaxBECount = EL0.Max;
else
MaxBECount = getUMinFromMismatchedTypes(EL0.Max, EL1.Max);
+ MustExit = EL0.MustExit || EL1.MustExit;
} else {
// Both conditions must be false at the same time for the loop to exit.
// For now, be conservative.
MaxBECount = EL0.Max;
if (EL0.Exact == EL1.Exact)
BECount = EL0.Exact;
+ MustExit = EL0.MustExit && EL1.MustExit;
}
- return ExitLimit(BECount, MaxBECount);
+ return ExitLimit(BECount, MaxBECount, MustExit);
}
}
else
MaxBECount = getConstant(CountDown ? CR.getUnsignedMax()
: -CR.getUnsignedMin());
- return ExitLimit(Distance, MaxBECount);
+ return ExitLimit(Distance, MaxBECount, /*MustExit=*/true);
}
// If the recurrence is known not to wraparound, unsigned divide computes the
// 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.
+ // value, even with nonunit stride, and exit later via the same branch. Note
+ // that we can skip this exit if loop later exits via a different
+ // branch. Hence MustExit=false.
//
// 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);
-
+ if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW)) {
+ const SCEV *Exact =
+ getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
+ return ExitLimit(Exact, Exact, /*MustExit=*/false);
+ }
// 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(),
// LHS' type is checked for above.
if (getTypeSizeInBits(LHS->getType()) >
getTypeSizeInBits(FoundLHS->getType())) {
- if (CmpInst::isSigned(Pred)) {
+ if (CmpInst::isSigned(FoundPred)) {
FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType());
FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType());
} else {
if (isa<SCEVCouldNotCompute>(MaxBECount))
MaxBECount = BECount;
- return ExitLimit(BECount, MaxBECount);
+ return ExitLimit(BECount, MaxBECount, /*MustExit=*/true);
}
ScalarEvolution::ExitLimit
if (isa<SCEVCouldNotCompute>(MaxBECount))
MaxBECount = BECount;
- return ExitLimit(BECount, MaxBECount);
+ return ExitLimit(BECount, MaxBECount, /*MustExit=*/true);
}
/// getNumIterationsInRange - Return the number of iterations of this loop that
uint32_t BBW = B.getBitWidth();
if (ABW > BBW)
- B.zext(ABW);
+ B = B.zext(ABW);
else if (ABW < BBW)
- A.zext(BBW);
+ A = A.zext(BBW);
return APIntOps::GreatestCommonDivisor(A, B);
}
uint32_t BBW = B.getBitWidth();
if (ABW > BBW)
- B.sext(ABW);
+ B = B.sext(ABW);
else if (ABW < BBW)
- A.sext(BBW);
+ A = A.sext(BBW);
return APIntOps::srem(A, B);
}
uint32_t BBW = B.getBitWidth();
if (ABW > BBW)
- B.sext(ABW);
+ B = B.sext(ABW);
else if (ABW < BBW)
- A.sext(BBW);
+ A = A.sext(BBW);
return APIntOps::sdiv(A, B);
}
LI = &getAnalysis<LoopInfo>();
TD = getAnalysisIfAvailable<DataLayout>();
TLI = &getAnalysis<TargetLibraryInfo>();
- DT = &getAnalysis<DominatorTree>();
+ DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
return false;
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequiredTransitive<LoopInfo>();
- AU.addRequiredTransitive<DominatorTree>();
+ AU.addRequiredTransitive<DominatorTreeWrapperPass>();
AU.addRequired<TargetLibraryInfo>();
}
PrintLoopInfo(OS, SE, *I);
OS << "Loop ";
- WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false);
+ L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
OS << ": ";
SmallVector<BasicBlock *, 8> ExitBlocks;
OS << "\n"
"Loop ";
- WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false);
+ L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
OS << ": ";
if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) {
ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
OS << "Classifying expressions for: ";
- WriteAsOperand(OS, F, /*PrintType=*/false);
+ F->printAsOperand(OS, /*PrintType=*/false);
OS << "\n";
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
if (isSCEVable(I->getType()) && !isa<CmpInst>(*I)) {
}
OS << "Determining loop execution counts for: ";
- WriteAsOperand(OS, F, /*PrintType=*/false);
+ F->printAsOperand(OS, /*PrintType=*/false);
OS << "\n";
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
PrintLoopInfo(OS, &SE, *I);
projects / oota-llvm.git / blobdiff