-//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
+//===- ScalarEvolution.cpp - Scalar Evolution Analysis --------------------===//
//
// The LLVM Compiler Infrastructure
//
//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "scalar-evolution"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionTracker.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include <algorithm>
using namespace llvm;
+#define DEBUG_TYPE "scalar-evolution"
+
STATISTIC(NumArrayLenItCounts,
"Number of trip counts computed with array length");
STATISTIC(NumTripCountsComputed,
INITIALIZE_PASS_BEGIN(ScalarEvolution, "scalar-evolution",
"Scalar Evolution Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(AssumptionTracker)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
case scUMaxExpr:
case scSMaxExpr: {
const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(this);
- const char *OpStr = 0;
+ const char *OpStr = nullptr;
switch (NAry->getSCEVType()) {
case scAddExpr: OpStr = " + "; break;
case scMulExpr: OpStr = " * "; break;
FoldingSetNodeID ID;
ID.AddInteger(scConstant);
ID.AddPointer(V);
- void *IP = 0;
+ void *IP = nullptr;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
UniqueSCEVs.InsertNode(S, IP);
SE->UniqueSCEVs.RemoveNode(this);
// Release the value.
- setValPtr(0);
+ setValPtr(nullptr);
}
void SCEVUnknown::allUsesReplacedWith(Value *New) {
ID.AddInteger(scTruncate);
ID.AddPointer(Op);
ID.AddPointer(Ty);
- void *IP = 0;
+ void *IP = nullptr;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
// Fold if the operand is constant.
ID.AddInteger(scZeroExtend);
ID.AddPointer(Op);
ID.AddPointer(Ty);
- void *IP = 0;
+ void *IP = nullptr;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
// zext(trunc(x)) --> zext(x) or x or trunc(x)
return SE->getConstant(APInt::getSignedMaxValue(BitWidth) -
SE->getSignedRange(Step).getSignedMin());
}
- return 0;
+ return nullptr;
}
// The recurrence AR has been shown to have no signed wrap. Typically, if we can
// Check for a simple looking step prior to loop entry.
const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Start);
if (!SA)
- return 0;
+ return nullptr;
// Create an AddExpr for "PreStart" after subtracting Step. Full SCEV
// subtraction is expensive. For this purpose, perform a quick and dirty
// difference, by checking for Step in the operand list.
SmallVector<const SCEV *, 4> DiffOps;
- for (SCEVAddExpr::op_iterator I = SA->op_begin(), E = SA->op_end();
- I != E; ++I) {
- if (*I != Step)
- DiffOps.push_back(*I);
- }
+ for (const SCEV *Op : SA->operands())
+ if (Op != Step)
+ DiffOps.push_back(Op);
+
if (DiffOps.size() == SA->getNumOperands())
- return 0;
+ return nullptr;
// This is a postinc AR. Check for overflow on the preinc recurrence using the
// same three conditions that getSignExtendedExpr checks.
SE->isLoopEntryGuardedByCond(L, Pred, PreStart, OverflowLimit)) {
return PreStart;
}
- return 0;
+ return nullptr;
}
// Get the normalized sign-extended expression for this AddRec's Start.
ID.AddInteger(scSignExtend);
ID.AddPointer(Op);
ID.AddPointer(Ty);
- void *IP = 0;
+ void *IP = nullptr;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
// If the input value is provably positive, build a zext instead.
return getTruncateOrSignExtend(X, Ty);
}
+ // sext(C1 + (C2 * x)) --> C1 + sext(C2 * x) if C1 < C2
+ if (auto SA = dyn_cast<SCEVAddExpr>(Op)) {
+ if (SA->getNumOperands() == 2) {
+ auto SC1 = dyn_cast<SCEVConstant>(SA->getOperand(0));
+ auto SMul = dyn_cast<SCEVMulExpr>(SA->getOperand(1));
+ if (SMul && SC1) {
+ if (auto SC2 = dyn_cast<SCEVConstant>(SMul->getOperand(0))) {
+ const APInt &C1 = SC1->getValue()->getValue();
+ const APInt &C2 = SC2->getValue()->getValue();
+ if (C1.isStrictlyPositive() && C2.isStrictlyPositive() &&
+ C2.ugt(C1) && C2.isPowerOf2())
+ return getAddExpr(getSignExtendExpr(SC1, Ty),
+ getSignExtendExpr(SMul, Ty));
+ }
+ }
+ }
+ }
// If the input value is a chrec scev, and we can prove that the value
// did not overflow the old, smaller, value, we can sign extend all of the
// operands (often constants). This allows analysis of something like
L, AR->getNoWrapFlags());
}
}
+ // If Start and Step are constants, check if we can apply this
+ // transformation:
+ // sext{C1,+,C2} --> C1 + sext{0,+,C2} if C1 < C2
+ auto SC1 = dyn_cast<SCEVConstant>(Start);
+ auto SC2 = dyn_cast<SCEVConstant>(Step);
+ if (SC1 && SC2) {
+ const APInt &C1 = SC1->getValue()->getValue();
+ const APInt &C2 = SC2->getValue()->getValue();
+ if (C1.isStrictlyPositive() && C2.isStrictlyPositive() && C2.ugt(C1) &&
+ C2.isPowerOf2()) {
+ Start = getSignExtendExpr(Start, Ty);
+ const SCEV *NewAR = getAddRecExpr(getConstant(AR->getType(), 0), Step,
+ L, AR->getNoWrapFlags());
+ return getAddExpr(Start, getSignExtendExpr(NewAR, Ty));
+ }
+ }
}
// The cast wasn't folded; create an explicit cast node.
// Force the cast to be folded into the operands of an addrec.
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) {
SmallVector<const SCEV *, 4> Ops;
- for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
- I != E; ++I)
- Ops.push_back(getAnyExtendExpr(*I, Ty));
+ for (const SCEV *Op : AR->operands())
+ Ops.push_back(getAnyExtendExpr(Op, Ty));
return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
}
ID.AddInteger(scAddExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
- void *IP = 0;
+ void *IP = nullptr;
SCEVAddExpr *S =
static_cast<SCEVAddExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
if (!S) {
// 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
// multiplied together. If so, we can fold them.
+
+ // {A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L>
+ // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [
+ // choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z
+ // ]]],+,...up to x=2n}.
+ // Note that the arguments to choose() are always integers with values
+ // known at compile time, never SCEV objects.
+ //
+ // The implementation avoids pointless extra computations when the two
+ // 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;
- OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
+ OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
++OtherIdx) {
- if (AddRecLoop != cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop())
+ const SCEVAddRecExpr *OtherAddRec =
+ dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
+ if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop)
continue;
- // {A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L>
- // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [
- // choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z
- // ]]],+,...up to x=2n}.
- // Note that the arguments to choose() are always integers with values
- // known at compile time, never SCEV objects.
- //
- // The implementation avoids pointless extra computations when the two
- // addrec's are of different length (mathematically, it's equivalent to
- // an infinite stream of zeros on the right).
- bool OpsModified = false;
- for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
- ++OtherIdx) {
- const SCEVAddRecExpr *OtherAddRec =
- dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
- if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop)
- continue;
-
- bool Overflow = false;
- Type *Ty = AddRec->getType();
- bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64;
- SmallVector<const SCEV*, 7> AddRecOps;
- for (int x = 0, xe = AddRec->getNumOperands() +
- OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
- const SCEV *Term = getConstant(Ty, 0);
- 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 Coeff;
- if (LargerThan64Bits)
- Coeff = umul_ov(Coeff1, Coeff2, Overflow);
- else
- Coeff = Coeff1*Coeff2;
- const SCEV *CoeffTerm = getConstant(Ty, Coeff);
- const SCEV *Term1 = AddRec->getOperand(y-z);
- const SCEV *Term2 = OtherAddRec->getOperand(z);
- Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1,Term2));
- }
+ bool Overflow = false;
+ Type *Ty = AddRec->getType();
+ bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64;
+ SmallVector<const SCEV*, 7> AddRecOps;
+ for (int x = 0, xe = AddRec->getNumOperands() +
+ OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
+ const SCEV *Term = getConstant(Ty, 0);
+ 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 Coeff;
+ if (LargerThan64Bits)
+ Coeff = umul_ov(Coeff1, Coeff2, Overflow);
+ else
+ Coeff = Coeff1*Coeff2;
+ const SCEV *CoeffTerm = getConstant(Ty, Coeff);
+ const SCEV *Term1 = AddRec->getOperand(y-z);
+ const SCEV *Term2 = OtherAddRec->getOperand(z);
+ Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1,Term2));
}
- AddRecOps.push_back(Term);
- }
- if (!Overflow) {
- const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
- SCEV::FlagAnyWrap);
- if (Ops.size() == 2) return NewAddRec;
- Ops[Idx] = NewAddRec;
- Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
- OpsModified = true;
- AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
- if (!AddRec)
- break;
}
+ AddRecOps.push_back(Term);
+ }
+ if (!Overflow) {
+ const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
+ SCEV::FlagAnyWrap);
+ if (Ops.size() == 2) return NewAddRec;
+ Ops[Idx] = NewAddRec;
+ Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
+ OpsModified = true;
+ AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
+ if (!AddRec)
+ break;
}
- if (OpsModified)
- return getMulExpr(Ops);
}
+ if (OpsModified)
+ return getMulExpr(Ops);
// Otherwise couldn't fold anything into this recurrence. Move onto the
// next one.
ID.AddInteger(scMulExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
- void *IP = 0;
+ void *IP = nullptr;
SCEVMulExpr *S =
static_cast<SCEVMulExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
if (!S) {
ID.AddInteger(scUDivExpr);
ID.AddPointer(LHS);
ID.AddPointer(RHS);
- void *IP = 0;
+ void *IP = nullptr;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
LHS, RHS);
for (unsigned i = 0, e = Operands.size(); i != e; ++i)
ID.AddPointer(Operands[i]);
ID.AddPointer(L);
- void *IP = 0;
+ void *IP = nullptr;
SCEVAddRecExpr *S =
static_cast<SCEVAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
if (!S) {
ID.AddInteger(scSMaxExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
- void *IP = 0;
+ void *IP = nullptr;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
ID.AddInteger(scUMaxExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
- void *IP = 0;
+ void *IP = nullptr;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
FoldingSetNodeID ID;
ID.AddInteger(scUnknown);
ID.AddPointer(V);
- void *IP = 0;
+ void *IP = nullptr;
if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
assert(cast<SCEVUnknown>(S)->getValue() == V &&
"Stale SCEVUnknown in uniquing map!");
return getPointerBase(Cast->getOperand());
}
else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) {
- const SCEV *PtrOp = 0;
+ const SCEV *PtrOp = nullptr;
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
I != E; ++I) {
if ((*I)->getType()->isPointerTy()) {
// The loop may have multiple entrances or multiple exits; we can analyze
// this phi as an addrec if it has a unique entry value and a unique
// backedge value.
- Value *BEValueV = 0, *StartValueV = 0;
+ Value *BEValueV = nullptr, *StartValueV = nullptr;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
Value *V = PN->getIncomingValue(i);
if (L->contains(PN->getIncomingBlock(i))) {
if (!BEValueV) {
BEValueV = V;
} else if (BEValueV != V) {
- BEValueV = 0;
+ BEValueV = nullptr;
break;
}
} else if (!StartValueV) {
StartValueV = V;
} else if (StartValueV != V) {
- StartValueV = 0;
+ StartValueV = nullptr;
break;
}
}
// PHI's incoming blocks are in a different loop, in which case doing so
// risks breaking LCSSA form. Instcombine would normally zap these, but
// it doesn't have DominatorTree information, so it may miss cases.
- if (Value *V = SimplifyInstruction(PN, DL, TLI, DT))
+ if (Value *V = SimplifyInstruction(PN, DL, TLI, DT, AT))
if (LI->replacementPreservesLCSSAForm(PN, V))
return getSCEV(V);
// For a SCEVUnknown, ask ValueTracking.
unsigned BitWidth = getTypeSizeInBits(U->getType());
APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
- ComputeMaskedBits(U->getValue(), Zeros, Ones);
+ computeKnownBits(U->getValue(), Zeros, Ones, DL, 0, AT, nullptr, DT);
return Zeros.countTrailingOnes();
}
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
// For a SCEVUnknown, ask ValueTracking.
APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
- ComputeMaskedBits(U->getValue(), Zeros, Ones, DL);
+ computeKnownBits(U->getValue(), Zeros, Ones, DL, 0, AT, nullptr, DT);
if (Ones == ~Zeros + 1)
return setUnsignedRange(U, ConservativeResult);
return setUnsignedRange(U,
// For a SCEVUnknown, ask ValueTracking.
if (!U->getValue()->getType()->isIntegerTy() && !DL)
return setSignedRange(U, ConservativeResult);
- unsigned NS = ComputeNumSignBits(U->getValue(), DL);
+ unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, AT, nullptr, DT);
if (NS <= 1)
return setSignedRange(U, ConservativeResult);
return setSignedRange(U, ConservativeResult.intersectWith(
// Instcombine's ShrinkDemandedConstant may strip bits out of
// constants, obscuring what would otherwise be a low-bits mask.
- // Use ComputeMaskedBits to compute what ShrinkDemandedConstant
+ // Use computeKnownBits to compute what ShrinkDemandedConstant
// knew about to reconstruct a low-bits mask value.
unsigned LZ = A.countLeadingZeros();
unsigned TZ = A.countTrailingZeros();
unsigned BitWidth = A.getBitWidth();
APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
- ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, DL);
+ computeKnownBits(U->getOperand(0), KnownZero, KnownOne, DL,
+ 0, AT, nullptr, DT);
APInt EffectiveMask =
APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ);
if (!ExitNotTaken.ExitingBlock) return SE->getCouldNotCompute();
assert(ExitNotTaken.ExactNotTaken && "uninitialized not-taken info");
- const SCEV *BECount = 0;
+ const SCEV *BECount = nullptr;
for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
- ENT != 0; ENT = ENT->getNextExit()) {
+ ENT != nullptr; ENT = ENT->getNextExit()) {
assert(ENT->ExactNotTaken != SE->getCouldNotCompute() && "bad exit SCEV");
ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock,
ScalarEvolution *SE) const {
for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
- ENT != 0; ENT = ENT->getNextExit()) {
+ ENT != nullptr; ENT = ENT->getNextExit()) {
if (ENT->ExitingBlock == ExitingBlock)
return ENT->ExactNotTaken;
return false;
for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
- ENT != 0; ENT = ENT->getNextExit()) {
+ ENT != nullptr; ENT = ENT->getNextExit()) {
if (ENT->ExactNotTaken != SE->getCouldNotCompute()
&& SE->hasOperand(ENT->ExactNotTaken, S)) {
/// clear - Invalidate this result and free the ExitNotTakenInfo array.
void ScalarEvolution::BackedgeTakenInfo::clear() {
- ExitNotTaken.ExitingBlock = 0;
- ExitNotTaken.ExactNotTaken = 0;
+ ExitNotTaken.ExitingBlock = nullptr;
+ ExitNotTaken.ExactNotTaken = nullptr;
delete[] ExitNotTaken.getNextExit();
}
SmallVector<BasicBlock *, 8> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
- // Examine all exits and pick the most conservative values.
- const SCEV *MaxBECount = getCouldNotCompute();
+ SmallVector<std::pair<BasicBlock *, const SCEV *>, 4> ExitCounts;
bool CouldComputeBECount = true;
BasicBlock *Latch = L->getLoopLatch(); // may be NULL.
- const SCEV *LatchMaxCount = 0;
- SmallVector<std::pair<BasicBlock *, const SCEV *>, 4> ExitCounts;
+ const SCEV *MustExitMaxBECount = nullptr;
+ const SCEV *MayExitMaxBECount = nullptr;
+
+ // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts
+ // and compute maxBECount.
for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
- ExitLimit EL = ComputeExitLimit(L, ExitingBlocks[i]);
+ BasicBlock *ExitBB = ExitingBlocks[i];
+ ExitLimit EL = ComputeExitLimit(L, ExitBB);
+
+ // 1. For each exit that can be computed, add an entry to ExitCounts.
+ // CouldComputeBECount is true only if all exits can be computed.
if (EL.Exact == getCouldNotCompute())
// We couldn't compute an exact value for this exit, so
// we won't be able to compute an exact value for the loop.
CouldComputeBECount = false;
else
- ExitCounts.push_back(std::make_pair(ExitingBlocks[i], EL.Exact));
-
- if (MaxBECount == getCouldNotCompute())
- MaxBECount = EL.Max;
- else if (EL.Max != getCouldNotCompute()) {
- // 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
- // non-latch exits that dominate the latch.
- if (EL.MustExit && ExitingBlocks[i] == Latch)
- LatchMaxCount = EL.Max;
- else
- MaxBECount = getUMaxFromMismatchedTypes(MaxBECount, EL.Max);
+ ExitCounts.push_back(std::make_pair(ExitBB, EL.Exact));
+
+ // 2. Derive the loop's MaxBECount from each exit's max number of
+ // non-exiting iterations. Partition the loop exits into two kinds:
+ // LoopMustExits and LoopMayExits.
+ //
+ // A LoopMustExit meets two requirements:
+ //
+ // (a) Its ExitLimit.MustExit flag must be set which indicates that the exit
+ // test condition cannot be skipped (the tested variable has unit stride or
+ // the test is less-than or greater-than, rather than a strict inequality).
+ //
+ // (b) It must dominate the loop latch, hence must be tested on every loop
+ // iteration.
+ //
+ // If any computable LoopMustExit is found, then MaxBECount is the minimum
+ // EL.Max of computable LoopMustExits. Otherwise, MaxBECount is
+ // conservatively the maximum EL.Max, where CouldNotCompute is considered
+ // greater than any computable EL.Max.
+ if (EL.MustExit && EL.Max != getCouldNotCompute() && Latch &&
+ DT->dominates(ExitBB, Latch)) {
+ if (!MustExitMaxBECount)
+ MustExitMaxBECount = EL.Max;
+ else {
+ MustExitMaxBECount =
+ getUMinFromMismatchedTypes(MustExitMaxBECount, EL.Max);
+ }
+ } else if (MayExitMaxBECount != getCouldNotCompute()) {
+ if (!MayExitMaxBECount || EL.Max == getCouldNotCompute())
+ MayExitMaxBECount = EL.Max;
+ else {
+ MayExitMaxBECount =
+ getUMaxFromMismatchedTypes(MayExitMaxBECount, EL.Max);
+ }
}
}
- // Be more precise in the easy case of a loop latch that must exit.
- if (LatchMaxCount) {
- MaxBECount = getUMinFromMismatchedTypes(MaxBECount, LatchMaxCount);
- }
+ const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
+ (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute());
return BackedgeTakenInfo(ExitCounts, CouldComputeBECount, MaxBECount);
}
// exit at this block and remember the exit block and whether all other targets
// lead to the loop header.
bool MustExecuteLoopHeader = true;
- BasicBlock *Exit = 0;
+ BasicBlock *Exit = nullptr;
for (succ_iterator SI = succ_begin(ExitingBlock), SE = succ_end(ExitingBlock);
SI != SE; ++SI)
if (!L->contains(*SI)) {
return getCouldNotCompute();
// Okay, we allow one non-constant index into the GEP instruction.
- Value *VarIdx = 0;
+ Value *VarIdx = nullptr;
std::vector<Constant*> Indexes;
unsigned VarIdxNum = 0;
for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
if (VarIdx) return getCouldNotCompute(); // Multiple non-constant idx's.
VarIdx = GEP->getOperand(i);
VarIdxNum = i-2;
- Indexes.push_back(0);
+ Indexes.push_back(nullptr);
}
// Loop-invariant loads may be a byproduct of loop optimization. Skip them.
Constant *Result = ConstantFoldLoadThroughGEPIndices(GV->getInitializer(),
Indexes);
- if (Result == 0) break; // Cannot compute!
+ if (!Result) break; // Cannot compute!
// Evaluate the condition for this iteration.
Result = ConstantExpr::getICmp(predicate, Result, RHS);
// Otherwise, we can evaluate this instruction if all of its operands are
// constant or derived from a PHI node themselves.
- PHINode *PHI = 0;
+ PHINode *PHI = nullptr;
for (Instruction::op_iterator OpI = UseInst->op_begin(),
OpE = UseInst->op_end(); OpI != OpE; ++OpI) {
if (isa<Constant>(*OpI)) continue;
Instruction *OpInst = dyn_cast<Instruction>(*OpI);
- if (!OpInst || !canConstantEvolve(OpInst, L)) return 0;
+ if (!OpInst || !canConstantEvolve(OpInst, L)) return nullptr;
PHINode *P = dyn_cast<PHINode>(OpInst);
if (!P)
P = getConstantEvolvingPHIOperands(OpInst, L, PHIMap);
PHIMap[OpInst] = P;
}
- if (P == 0) return 0; // Not evolving from PHI
- if (PHI && PHI != P) return 0; // Evolving from multiple different PHIs.
+ if (!P)
+ return nullptr; // Not evolving from PHI
+ if (PHI && PHI != P)
+ return nullptr; // Evolving from multiple different PHIs.
PHI = P;
}
// This is a expression evolving from a constant PHI!
/// constraints, return null.
static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
Instruction *I = dyn_cast<Instruction>(V);
- if (I == 0 || !canConstantEvolve(I, L)) return 0;
+ if (!I || !canConstantEvolve(I, L)) return nullptr;
if (PHINode *PN = dyn_cast<PHINode>(I)) {
return PN;
// Convenient constant check, but redundant for recursive calls.
if (Constant *C = dyn_cast<Constant>(V)) return C;
Instruction *I = dyn_cast<Instruction>(V);
- if (!I) return 0;
+ if (!I) return nullptr;
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 0;
+ 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<PHINode>(I)) return 0;
+ if (isa<PHINode>(I)) return nullptr;
std::vector<Constant*> Operands(I->getNumOperands());
Instruction *Operand = dyn_cast<Instruction>(I->getOperand(i));
if (!Operand) {
Operands[i] = dyn_cast<Constant>(I->getOperand(i));
- if (!Operands[i]) return 0;
+ if (!Operands[i]) return nullptr;
continue;
}
Constant *C = EvaluateExpression(Operand, L, Vals, DL, TLI);
Vals[Operand] = C;
- if (!C) return 0;
+ if (!C) return nullptr;
Operands[i] = C;
}
return I->second;
if (BEs.ugt(MaxBruteForceIterations))
- return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it.
+ return ConstantEvolutionLoopExitValue[PN] = nullptr; // Not going to evaluate it.
Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
// entry must be a constant (coming in from outside of the loop), and the
// second must be derived from the same PHI.
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
- PHINode *PHI = 0;
+ PHINode *PHI = nullptr;
for (BasicBlock::iterator I = Header->begin();
(PHI = dyn_cast<PHINode>(I)); ++I) {
Constant *StartCST =
dyn_cast<Constant>(PHI->getIncomingValue(!SecondIsBackedge));
- if (StartCST == 0) continue;
+ if (!StartCST) continue;
CurrentIterVals[PHI] = StartCST;
}
if (!CurrentIterVals.count(PN))
- return RetVal = 0;
+ return RetVal = nullptr;
Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
// Execute the loop symbolically to determine the exit value.
if (BEs.getActiveBits() >= 32)
- return RetVal = 0; // More than 2^32-1 iterations?? Not doing it!
+ return RetVal = nullptr; // More than 2^32-1 iterations?? Not doing it!
unsigned NumIterations = BEs.getZExtValue(); // must be in range
unsigned IterationNum = 0;
DenseMap<Instruction *, Constant *> NextIterVals;
Constant *NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL,
TLI);
- if (NextPHI == 0)
- return 0; // Couldn't evaluate!
+ if (!NextPHI)
+ return nullptr; // Couldn't evaluate!
NextIterVals[PN] = NextPHI;
bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
Value *Cond,
bool ExitWhen) {
PHINode *PN = getConstantEvolvingPHI(Cond, L);
- if (PN == 0) 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.
// One entry must be a constant (coming in from outside of the loop), and the
// second must be derived from the same PHI.
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
- PHINode *PHI = 0;
+ PHINode *PHI = nullptr;
for (BasicBlock::iterator I = Header->begin();
(PHI = dyn_cast<PHINode>(I)); ++I) {
Constant *StartCST =
dyn_cast<Constant>(PHI->getIncomingValue(!SecondIsBackedge));
- if (StartCST == 0) continue;
+ if (!StartCST) continue;
CurrentIterVals[PHI] = StartCST;
}
if (!CurrentIterVals.count(PN))
if (Values[u].first == L)
return Values[u].second ? Values[u].second : V;
}
- Values.push_back(std::make_pair(L, static_cast<const SCEV *>(0)));
+ Values.push_back(std::make_pair(L, static_cast<const SCEV *>(nullptr)));
// Otherwise compute it.
const SCEV *C = computeSCEVAtScope(V, L);
SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values2 = ValuesAtScopes[V];
}
for (unsigned i = 1, e = SA->getNumOperands(); i != e; ++i) {
Constant *C2 = BuildConstantFromSCEV(SA->getOperand(i));
- if (!C2) return 0;
+ if (!C2) return nullptr;
// First pointer!
if (!C->getType()->isPointerTy() && C2->getType()->isPointerTy()) {
// Don't bother trying to sum two pointers. We probably can't
// statically compute a load that results from it anyway.
if (C2->getType()->isPointerTy())
- return 0;
+ return nullptr;
if (PointerType *PTy = dyn_cast<PointerType>(C->getType())) {
if (PTy->getElementType()->isStructTy())
const SCEVMulExpr *SM = cast<SCEVMulExpr>(V);
if (Constant *C = BuildConstantFromSCEV(SM->getOperand(0))) {
// Don't bother with pointers at all.
- if (C->getType()->isPointerTy()) return 0;
+ if (C->getType()->isPointerTy()) return nullptr;
for (unsigned i = 1, e = SM->getNumOperands(); i != e; ++i) {
Constant *C2 = BuildConstantFromSCEV(SM->getOperand(i));
- if (!C2 || C2->getType()->isPointerTy()) return 0;
+ if (!C2 || C2->getType()->isPointerTy()) return nullptr;
C = ConstantExpr::getMul(C, C2);
}
return C;
case scUMaxExpr:
break; // TODO: smax, umax.
}
- return 0;
+ return nullptr;
}
const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
// Check to see if getSCEVAtScope actually made an improvement.
if (MadeImprovement) {
- Constant *C = 0;
+ Constant *C = nullptr;
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(),
Operands[0], Operands[1], DL,
// to 0, it must be counting down to equal 0. Consequently, N = Start / -Step.
// We have not yet seen any such cases.
const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step);
- if (StepC == 0 || StepC->getValue()->equalsInt(0))
+ if (!StepC || StepC->getValue()->equalsInt(0))
return getCouldNotCompute();
// For positive steps (counting up until unsigned overflow):
// If LHS or RHS is an addrec, check to see if the condition is true in
// every iteration of the loop.
- if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
- if (isLoopEntryGuardedByCond(
- AR->getLoop(), Pred, AR->getStart(), RHS) &&
- isLoopBackedgeGuardedByCond(
- AR->getLoop(), Pred, AR->getPostIncExpr(*this), RHS))
- return true;
- if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(RHS))
- if (isLoopEntryGuardedByCond(
- AR->getLoop(), Pred, LHS, AR->getStart()) &&
- isLoopBackedgeGuardedByCond(
- AR->getLoop(), Pred, LHS, AR->getPostIncExpr(*this)))
- return true;
+ // If LHS and RHS are both addrec, both conditions must be true in
+ // every iteration of the loop.
+ const SCEVAddRecExpr *LAR = dyn_cast<SCEVAddRecExpr>(LHS);
+ const SCEVAddRecExpr *RAR = dyn_cast<SCEVAddRecExpr>(RHS);
+ bool LeftGuarded = false;
+ bool RightGuarded = false;
+ if (LAR) {
+ const Loop *L = LAR->getLoop();
+ if (isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) &&
+ isLoopBackedgeGuardedByCond(L, Pred, LAR->getPostIncExpr(*this), RHS)) {
+ if (!RAR) return true;
+ LeftGuarded = true;
+ }
+ }
+ if (RAR) {
+ const Loop *L = RAR->getLoop();
+ if (isLoopEntryGuardedByCond(L, Pred, LHS, RAR->getStart()) &&
+ isLoopBackedgeGuardedByCond(L, Pred, LHS, RAR->getPostIncExpr(*this))) {
+ if (!LAR) return true;
+ RightGuarded = true;
+ }
+ }
+ if (LeftGuarded && RightGuarded)
+ return true;
// Otherwise see what can be done with known constant ranges.
return isKnownPredicateWithRanges(Pred, LHS, RHS);
BranchInst *LoopContinuePredicate =
dyn_cast<BranchInst>(Latch->getTerminator());
- if (!LoopContinuePredicate ||
- LoopContinuePredicate->isUnconditional())
- return false;
+ if (LoopContinuePredicate && LoopContinuePredicate->isConditional() &&
+ isImpliedCond(Pred, LHS, RHS,
+ LoopContinuePredicate->getCondition(),
+ LoopContinuePredicate->getSuccessor(0) != L->getHeader()))
+ return true;
- return isImpliedCond(Pred, LHS, RHS,
- LoopContinuePredicate->getCondition(),
- LoopContinuePredicate->getSuccessor(0) != L->getHeader());
+ // Check conditions due to any @llvm.assume intrinsics.
+ for (auto &CI : AT->assumptions(F)) {
+ if (!DT->dominates(CI, Latch->getTerminator()))
+ continue;
+
+ if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
+ return true;
+ }
+
+ return false;
}
/// isLoopEntryGuardedByCond - Test whether entry to the loop is protected
return true;
}
+ // Check conditions due to any @llvm.assume intrinsics.
+ for (auto &CI : AT->assumptions(F)) {
+ if (!DT->dominates(CI, L->getHeader()))
+ continue;
+
+ if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
+ return true;
+ }
+
return false;
}
return SE.getCouldNotCompute();
}
+namespace {
+struct FindUndefs {
+ bool Found;
+ FindUndefs() : Found(false) {}
+
+ bool follow(const SCEV *S) {
+ if (const SCEVUnknown *C = dyn_cast<SCEVUnknown>(S)) {
+ if (isa<UndefValue>(C->getValue()))
+ Found = true;
+ } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
+ if (isa<UndefValue>(C->getValue()))
+ Found = true;
+ }
+
+ // Keep looking if we haven't found it yet.
+ return !Found;
+ }
+ bool isDone() const {
+ // Stop recursion if we have found an undef.
+ return Found;
+ }
+};
+}
+
+// Return true when S contains at least an undef value.
+static inline bool
+containsUndefs(const SCEV *S) {
+ FindUndefs F;
+ SCEVTraversal<FindUndefs> ST(F);
+ ST.visitAll(S);
+
+ return F.Found;
+}
+
+namespace {
+// Collect all steps of SCEV expressions.
+struct SCEVCollectStrides {
+ ScalarEvolution &SE;
+ SmallVectorImpl<const SCEV *> &Strides;
+
+ SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &S)
+ : SE(SE), Strides(S) {}
+
+ bool follow(const SCEV *S) {
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
+ Strides.push_back(AR->getStepRecurrence(SE));
+ return true;
+ }
+ bool isDone() const { return false; }
+};
+
+// Collect all SCEVUnknown and SCEVMulExpr expressions.
+struct SCEVCollectTerms {
+ SmallVectorImpl<const SCEV *> &Terms;
+
+ SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T)
+ : Terms(T) {}
+
+ bool follow(const SCEV *S) {
+ if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S)) {
+ if (!containsUndefs(S))
+ Terms.push_back(S);
+
+ // Stop recursion: once we collected a term, do not walk its operands.
+ return false;
+ }
+
+ // Keep looking.
+ return true;
+ }
+ bool isDone() const { return false; }
+};
+}
+
+/// Find parametric terms in this SCEVAddRecExpr.
+void SCEVAddRecExpr::collectParametricTerms(
+ ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &Terms) const {
+ SmallVector<const SCEV *, 4> Strides;
+ SCEVCollectStrides StrideCollector(SE, Strides);
+ visitAll(this, StrideCollector);
+
+ DEBUG({
+ dbgs() << "Strides:\n";
+ for (const SCEV *S : Strides)
+ dbgs() << *S << "\n";
+ });
+
+ for (const SCEV *S : Strides) {
+ SCEVCollectTerms TermCollector(Terms);
+ visitAll(S, TermCollector);
+ }
+
+ DEBUG({
+ dbgs() << "Terms:\n";
+ for (const SCEV *T : Terms)
+ dbgs() << *T << "\n";
+ });
+}
+
static const APInt srem(const SCEVConstant *C1, const SCEVConstant *C2) {
APInt A = C1->getValue()->getValue();
APInt B = C2->getValue()->getValue();
}
namespace {
-struct SCEVGCD : public SCEVVisitor<SCEVGCD, const SCEV *> {
-public:
- // Pattern match Step into Start. When Step is a multiply expression, find
- // the largest subexpression of Step that appears in Start. When Start is an
- // add expression, try to match Step in the subexpressions of Start, non
- // matching subexpressions are returned under Remainder.
- static const SCEV *findGCD(ScalarEvolution &SE, const SCEV *Start,
- const SCEV *Step, const SCEV **Remainder) {
- assert(Remainder && "Remainder should not be NULL");
- SCEVGCD R(SE, Step, SE.getConstant(Step->getType(), 0));
- const SCEV *Res = R.visit(Start);
- *Remainder = R.Remainder;
- return Res;
- }
+struct FindSCEVSize {
+ int Size;
+ FindSCEVSize() : Size(0) {}
- SCEVGCD(ScalarEvolution &S, const SCEV *G, const SCEV *R)
- : SE(S), GCD(G), Remainder(R) {
- Zero = SE.getConstant(GCD->getType(), 0);
- One = SE.getConstant(GCD->getType(), 1);
+ bool follow(const SCEV *S) {
+ ++Size;
+ // Keep looking at all operands of S.
+ return true;
}
+ bool isDone() const {
+ return false;
+ }
+};
+}
- const SCEV *visitConstant(const SCEVConstant *Constant) {
- if (GCD == Constant || Constant == Zero)
- return GCD;
+// Returns the size of the SCEV S.
+static inline int sizeOfSCEV(const SCEV *S) {
+ FindSCEVSize F;
+ SCEVTraversal<FindSCEVSize> ST(F);
+ ST.visitAll(S);
+ return F.Size;
+}
- if (const SCEVConstant *CGCD = dyn_cast<SCEVConstant>(GCD)) {
- const SCEV *Res = SE.getConstant(gcd(Constant, CGCD));
- if (Res != One)
- return Res;
+namespace {
- Remainder = SE.getConstant(srem(Constant, CGCD));
- Constant = cast<SCEVConstant>(SE.getMinusSCEV(Constant, Remainder));
- Res = SE.getConstant(gcd(Constant, CGCD));
- return Res;
+struct SCEVDivision : public SCEVVisitor<SCEVDivision, void> {
+public:
+ // Computes the Quotient and Remainder of the division of Numerator by
+ // Denominator.
+ static void divide(ScalarEvolution &SE, const SCEV *Numerator,
+ const SCEV *Denominator, const SCEV **Quotient,
+ const SCEV **Remainder) {
+ assert(Numerator && Denominator && "Uninitialized SCEV");
+
+ SCEVDivision D(SE, Numerator, Denominator);
+
+ // Check for the trivial case here to avoid having to check for it in the
+ // rest of the code.
+ if (Numerator == Denominator) {
+ *Quotient = D.One;
+ *Remainder = D.Zero;
+ return;
}
- // When GCD is not a constant, it could be that the GCD is an Add, Mul,
- // AddRec, etc., in which case we want to find out how many times the
- // Constant divides the GCD: we then return that as the new GCD.
- const SCEV *Rem = Zero;
- const SCEV *Res = findGCD(SE, GCD, Constant, &Rem);
+ if (Numerator->isZero()) {
+ *Quotient = D.Zero;
+ *Remainder = D.Zero;
+ return;
+ }
- if (Res == One || Rem != Zero) {
- Remainder = Constant;
- return One;
+ // Split the Denominator when it is a product.
+ if (const SCEVMulExpr *T = dyn_cast<const SCEVMulExpr>(Denominator)) {
+ const SCEV *Q, *R;
+ *Quotient = Numerator;
+ for (const SCEV *Op : T->operands()) {
+ divide(SE, *Quotient, Op, &Q, &R);
+ *Quotient = Q;
+
+ // Bail out when the Numerator is not divisible by one of the terms of
+ // the Denominator.
+ if (!R->isZero()) {
+ *Quotient = D.Zero;
+ *Remainder = Numerator;
+ return;
+ }
+ }
+ *Remainder = D.Zero;
+ return;
}
- assert(isa<SCEVConstant>(Res) && "Res should be a constant");
- Remainder = SE.getConstant(srem(Constant, cast<SCEVConstant>(Res)));
- return Res;
+ D.visit(Numerator);
+ *Quotient = D.Quotient;
+ *Remainder = D.Remainder;
+ }
+
+ SCEVDivision(ScalarEvolution &S, const SCEV *Numerator, const SCEV *Denominator)
+ : SE(S), Denominator(Denominator) {
+ Zero = SE.getConstant(Denominator->getType(), 0);
+ One = SE.getConstant(Denominator->getType(), 1);
+
+ // By default, we don't know how to divide Expr by Denominator.
+ // Providing the default here simplifies the rest of the code.
+ Quotient = Zero;
+ Remainder = Numerator;
+ }
+
+ // Except in the trivial case described above, we do not know how to divide
+ // Expr by Denominator for the following functions with empty implementation.
+ void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {}
+ void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {}
+ void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {}
+ void visitUDivExpr(const SCEVUDivExpr *Numerator) {}
+ void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {}
+ void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {}
+ void visitUnknown(const SCEVUnknown *Numerator) {}
+ void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
+
+ void visitConstant(const SCEVConstant *Numerator) {
+ if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
+ Quotient = SE.getConstant(sdiv(Numerator, D));
+ Remainder = SE.getConstant(srem(Numerator, D));
+ return;
+ }
}
- const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
- if (GCD != Expr)
- Remainder = Expr;
- return GCD;
+ void visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
+ const SCEV *StartQ, *StartR, *StepQ, *StepR;
+ assert(Numerator->isAffine() && "Numerator should be affine");
+ divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);
+ divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR);
+ Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
+ Numerator->getNoWrapFlags());
+ Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
+ Numerator->getNoWrapFlags());
}
- const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
- if (GCD != Expr)
- Remainder = Expr;
- return GCD;
- }
+ void visitAddExpr(const SCEVAddExpr *Numerator) {
+ SmallVector<const SCEV *, 2> Qs, Rs;
+ Type *Ty = Denominator->getType();
- const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
- if (GCD != Expr)
- Remainder = Expr;
- return GCD;
- }
+ for (const SCEV *Op : Numerator->operands()) {
+ const SCEV *Q, *R;
+ divide(SE, Op, Denominator, &Q, &R);
- const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
- if (GCD == Expr)
- return GCD;
+ // Bail out if types do not match.
+ if (Ty != Q->getType() || Ty != R->getType()) {
+ Quotient = Zero;
+ Remainder = Numerator;
+ return;
+ }
- for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
- const SCEV *Rem = Zero;
- const SCEV *Res = findGCD(SE, Expr->getOperand(e - 1 - i), GCD, &Rem);
+ Qs.push_back(Q);
+ Rs.push_back(R);
+ }
- // FIXME: There may be ambiguous situations: for instance,
- // GCD(-4 + (3 * %m), 2 * %m) where 2 divides -4 and %m divides (3 * %m).
- // The order in which the AddExpr is traversed computes a different GCD
- // and Remainder.
- if (Res != One)
- GCD = Res;
- if (Rem != Zero)
- Remainder = SE.getAddExpr(Remainder, Rem);
+ if (Qs.size() == 1) {
+ Quotient = Qs[0];
+ Remainder = Rs[0];
+ return;
}
- return GCD;
+ Quotient = SE.getAddExpr(Qs);
+ Remainder = SE.getAddExpr(Rs);
}
- const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
- if (GCD == Expr)
- return GCD;
+ void visitMulExpr(const SCEVMulExpr *Numerator) {
+ SmallVector<const SCEV *, 2> Qs;
+ Type *Ty = Denominator->getType();
- for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
- if (Expr->getOperand(i) == GCD)
- return GCD;
- }
+ bool FoundDenominatorTerm = false;
+ for (const SCEV *Op : Numerator->operands()) {
+ // Bail out if types do not match.
+ if (Ty != Op->getType()) {
+ Quotient = Zero;
+ Remainder = Numerator;
+ return;
+ }
- // If we have not returned yet, it means that GCD is not part of Expr.
- const SCEV *PartialGCD = One;
- for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
- const SCEV *Rem = Zero;
- const SCEV *Res = findGCD(SE, Expr->getOperand(i), GCD, &Rem);
- if (Rem != Zero)
- // GCD does not divide Expr->getOperand(i).
+ if (FoundDenominatorTerm) {
+ Qs.push_back(Op);
continue;
+ }
- if (Res == GCD)
- return GCD;
- PartialGCD = SE.getMulExpr(PartialGCD, Res);
- if (PartialGCD == GCD)
- return GCD;
- }
-
- if (PartialGCD != One)
- return PartialGCD;
-
- // Failed to find a PartialGCD: set the Remainder to the full expression,
- // and return the GCD.
- Remainder = Expr;
- const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(GCD);
- if (!Mul)
- return GCD;
-
- // When the GCD is a multiply expression, try to decompose it:
- // this occurs when Step does not divide the Start expression
- // as in: {(-4 + (3 * %m)),+,(2 * %m)}
- for (int i = 0, e = Mul->getNumOperands(); i < e; ++i) {
- const SCEV *Rem = Zero;
- const SCEV *Res = findGCD(SE, Expr, Mul->getOperand(i), &Rem);
- if (Rem == Zero) {
- Remainder = Rem;
- return Res;
+ // Check whether Denominator divides one of the product operands.
+ const SCEV *Q, *R;
+ divide(SE, Op, Denominator, &Q, &R);
+ if (!R->isZero()) {
+ Qs.push_back(Op);
+ continue;
}
- }
- return GCD;
- }
+ // Bail out if types do not match.
+ if (Ty != Q->getType()) {
+ Quotient = Zero;
+ Remainder = Numerator;
+ return;
+ }
- const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
- if (GCD != Expr)
- Remainder = Expr;
- return GCD;
- }
+ FoundDenominatorTerm = true;
+ Qs.push_back(Q);
+ }
- const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
- if (GCD == Expr)
- return GCD;
+ if (FoundDenominatorTerm) {
+ Remainder = Zero;
+ if (Qs.size() == 1)
+ Quotient = Qs[0];
+ else
+ Quotient = SE.getMulExpr(Qs);
+ return;
+ }
- if (!Expr->isAffine()) {
- Remainder = Expr;
- return GCD;
+ if (!isa<SCEVUnknown>(Denominator)) {
+ Quotient = Zero;
+ Remainder = Numerator;
+ return;
}
- const SCEV *Rem = Zero;
- const SCEV *Res = findGCD(SE, Expr->getOperand(0), GCD, &Rem);
- if (Res == One || Res->isAllOnesValue()) {
- Remainder = Expr;
- return GCD;
+ // The Remainder is obtained by replacing Denominator by 0 in Numerator.
+ ValueToValueMap RewriteMap;
+ RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
+ cast<SCEVConstant>(Zero)->getValue();
+ Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);
+
+ if (Remainder->isZero()) {
+ // The Quotient is obtained by replacing Denominator by 1 in Numerator.
+ RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
+ cast<SCEVConstant>(One)->getValue();
+ Quotient =
+ SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);
+ return;
+ }
+
+ // Quotient is (Numerator - Remainder) divided by Denominator.
+ const SCEV *Q, *R;
+ const SCEV *Diff = SE.getMinusSCEV(Numerator, Remainder);
+ if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator)) {
+ // This SCEV does not seem to simplify: fail the division here.
+ Quotient = Zero;
+ Remainder = Numerator;
+ return;
}
+ divide(SE, Diff, Denominator, &Q, &R);
+ assert(R == Zero &&
+ "(Numerator - Remainder) should evenly divide Denominator");
+ Quotient = Q;
+ }
+
+private:
+ ScalarEvolution &SE;
+ const SCEV *Denominator, *Quotient, *Remainder, *Zero, *One;
+};
+}
- if (Rem != Zero)
- Remainder = SE.getAddExpr(Remainder, Rem);
+static bool findArrayDimensionsRec(ScalarEvolution &SE,
+ SmallVectorImpl<const SCEV *> &Terms,
+ SmallVectorImpl<const SCEV *> &Sizes) {
+ int Last = Terms.size() - 1;
+ const SCEV *Step = Terms[Last];
- Rem = Zero;
- Res = findGCD(SE, Expr->getOperand(1), Res, &Rem);
- if (Rem != Zero || Res == One || Res->isAllOnesValue()) {
- Remainder = Expr;
- return GCD;
+ // End of recursion.
+ if (Last == 0) {
+ if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Step)) {
+ SmallVector<const SCEV *, 2> Qs;
+ for (const SCEV *Op : M->operands())
+ if (!isa<SCEVConstant>(Op))
+ Qs.push_back(Op);
+
+ Step = SE.getMulExpr(Qs);
}
- return Res;
+ Sizes.push_back(Step);
+ return true;
}
- const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
- if (GCD != Expr)
- Remainder = Expr;
- return GCD;
- }
+ for (const SCEV *&Term : Terms) {
+ // Normalize the terms before the next call to findArrayDimensionsRec.
+ const SCEV *Q, *R;
+ SCEVDivision::divide(SE, Term, Step, &Q, &R);
- const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
- if (GCD != Expr)
- Remainder = Expr;
- return GCD;
- }
+ // Bail out when GCD does not evenly divide one of the terms.
+ if (!R->isZero())
+ return false;
- const SCEV *visitUnknown(const SCEVUnknown *Expr) {
- if (GCD != Expr)
- Remainder = Expr;
- return GCD;
+ Term = Q;
}
- const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
- return One;
- }
+ // Remove all SCEVConstants.
+ Terms.erase(std::remove_if(Terms.begin(), Terms.end(), [](const SCEV *E) {
+ return isa<SCEVConstant>(E);
+ }),
+ Terms.end());
-private:
- ScalarEvolution &SE;
- const SCEV *GCD, *Remainder, *Zero, *One;
-};
+ if (Terms.size() > 0)
+ if (!findArrayDimensionsRec(SE, Terms, Sizes))
+ return false;
-struct SCEVDivision : public SCEVVisitor<SCEVDivision, const SCEV *> {
-public:
- // Remove from Start all multiples of Step.
- static const SCEV *divide(ScalarEvolution &SE, const SCEV *Start,
- const SCEV *Step) {
- SCEVDivision D(SE, Step);
- const SCEV *Rem = D.Zero;
- (void)Rem;
- // The division is guaranteed to succeed: Step should divide Start with no
- // remainder.
- assert(Step == SCEVGCD::findGCD(SE, Start, Step, &Rem) && Rem == D.Zero &&
- "Step should divide Start with no remainder.");
- return D.visit(Start);
- }
+ Sizes.push_back(Step);
+ return true;
+}
+
+namespace {
+struct FindParameter {
+ bool FoundParameter;
+ FindParameter() : FoundParameter(false) {}
- SCEVDivision(ScalarEvolution &S, const SCEV *G) : SE(S), GCD(G) {
- Zero = SE.getConstant(GCD->getType(), 0);
- One = SE.getConstant(GCD->getType(), 1);
+ bool follow(const SCEV *S) {
+ if (isa<SCEVUnknown>(S)) {
+ FoundParameter = true;
+ // Stop recursion: we found a parameter.
+ return false;
+ }
+ // Keep looking.
+ return true;
+ }
+ bool isDone() const {
+ // Stop recursion if we have found a parameter.
+ return FoundParameter;
}
+};
+}
+
+// Returns true when S contains at least a SCEVUnknown parameter.
+static inline bool
+containsParameters(const SCEV *S) {
+ FindParameter F;
+ SCEVTraversal<FindParameter> ST(F);
+ ST.visitAll(S);
- const SCEV *visitConstant(const SCEVConstant *Constant) {
- if (GCD == Constant)
- return One;
+ return F.FoundParameter;
+}
- if (const SCEVConstant *CGCD = dyn_cast<SCEVConstant>(GCD))
- return SE.getConstant(sdiv(Constant, CGCD));
- return Constant;
- }
+// Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter.
+static inline bool
+containsParameters(SmallVectorImpl<const SCEV *> &Terms) {
+ for (const SCEV *T : Terms)
+ if (containsParameters(T))
+ return true;
+ return false;
+}
- const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
- if (GCD == Expr)
- return One;
- return Expr;
- }
+// Return the number of product terms in S.
+static inline int numberOfTerms(const SCEV *S) {
+ if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
+ return Expr->getNumOperands();
+ return 1;
+}
- const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
- if (GCD == Expr)
- return One;
- return Expr;
- }
+static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {
+ if (isa<SCEVConstant>(T))
+ return nullptr;
+
+ if (isa<SCEVUnknown>(T))
+ return T;
- const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
- if (GCD == Expr)
- return One;
- return Expr;
+ if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(T)) {
+ SmallVector<const SCEV *, 2> Factors;
+ for (const SCEV *Op : M->operands())
+ if (!isa<SCEVConstant>(Op))
+ Factors.push_back(Op);
+
+ return SE.getMulExpr(Factors);
}
- const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
- if (GCD == Expr)
- return One;
+ return T;
+}
- SmallVector<const SCEV *, 2> Operands;
- for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
- Operands.push_back(divide(SE, Expr->getOperand(i), GCD));
+/// Return the size of an element read or written by Inst.
+const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) {
+ Type *Ty;
+ if (StoreInst *Store = dyn_cast<StoreInst>(Inst))
+ Ty = Store->getValueOperand()->getType();
+ else if (LoadInst *Load = dyn_cast<LoadInst>(Inst))
+ Ty = Load->getType();
+ else
+ return nullptr;
- if (Operands.size() == 1)
- return Operands[0];
- return SE.getAddExpr(Operands);
- }
+ Type *ETy = getEffectiveSCEVType(PointerType::getUnqual(Ty));
+ return getSizeOfExpr(ETy, Ty);
+}
- const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
- if (GCD == Expr)
- return One;
+/// Second step of delinearization: compute the array dimensions Sizes from the
+/// set of Terms extracted from the memory access function of this SCEVAddRec.
+void ScalarEvolution::findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
+ SmallVectorImpl<const SCEV *> &Sizes,
+ const SCEV *ElementSize) const {
- bool FoundGCDTerm = false;
- for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
- if (Expr->getOperand(i) == GCD)
- FoundGCDTerm = true;
+ if (Terms.size() < 1 || !ElementSize)
+ return;
- SmallVector<const SCEV *, 2> Operands;
- if (FoundGCDTerm) {
- FoundGCDTerm = false;
- for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
- if (FoundGCDTerm)
- Operands.push_back(Expr->getOperand(i));
- else if (Expr->getOperand(i) == GCD)
- FoundGCDTerm = true;
- else
- Operands.push_back(Expr->getOperand(i));
- }
- } else {
- const SCEV *PartialGCD = One;
- for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
- if (PartialGCD == GCD) {
- Operands.push_back(Expr->getOperand(i));
- continue;
- }
+ // Early return when Terms do not contain parameters: we do not delinearize
+ // non parametric SCEVs.
+ if (!containsParameters(Terms))
+ return;
- const SCEV *Rem = Zero;
- const SCEV *Res = SCEVGCD::findGCD(SE, Expr->getOperand(i), GCD, &Rem);
- if (Rem == Zero) {
- PartialGCD = SE.getMulExpr(PartialGCD, Res);
- Operands.push_back(divide(SE, Expr->getOperand(i), GCD));
- } else {
- Operands.push_back(Expr->getOperand(i));
- }
- }
- }
+ DEBUG({
+ dbgs() << "Terms:\n";
+ for (const SCEV *T : Terms)
+ dbgs() << *T << "\n";
+ });
- if (Operands.size() == 1)
- return Operands[0];
- return SE.getMulExpr(Operands);
- }
+ // Remove duplicates.
+ std::sort(Terms.begin(), Terms.end());
+ Terms.erase(std::unique(Terms.begin(), Terms.end()), Terms.end());
+
+ // Put larger terms first.
+ std::sort(Terms.begin(), Terms.end(), [](const SCEV *LHS, const SCEV *RHS) {
+ return numberOfTerms(LHS) > numberOfTerms(RHS);
+ });
+
+ ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
- const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
- if (GCD == Expr)
- return One;
- return Expr;
+ // Divide all terms by the element size.
+ for (const SCEV *&Term : Terms) {
+ const SCEV *Q, *R;
+ SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);
+ Term = Q;
}
- const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
- if (GCD == Expr)
- return One;
+ SmallVector<const SCEV *, 4> NewTerms;
- assert(Expr->isAffine() && "Expr should be affine");
+ // Remove constant factors.
+ for (const SCEV *T : Terms)
+ if (const SCEV *NewT = removeConstantFactors(SE, T))
+ NewTerms.push_back(NewT);
- const SCEV *Start = divide(SE, Expr->getStart(), GCD);
- const SCEV *Step = divide(SE, Expr->getStepRecurrence(SE), GCD);
+ DEBUG({
+ dbgs() << "Terms after sorting:\n";
+ for (const SCEV *T : NewTerms)
+ dbgs() << *T << "\n";
+ });
- return SE.getAddRecExpr(Start, Step, Expr->getLoop(),
- Expr->getNoWrapFlags());
+ if (NewTerms.empty() ||
+ !findArrayDimensionsRec(SE, NewTerms, Sizes)) {
+ Sizes.clear();
+ return;
}
- const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
- if (GCD == Expr)
- return One;
- return Expr;
- }
+ // The last element to be pushed into Sizes is the size of an element.
+ Sizes.push_back(ElementSize);
- const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
- if (GCD == Expr)
- return One;
- return Expr;
- }
+ DEBUG({
+ dbgs() << "Sizes:\n";
+ for (const SCEV *S : Sizes)
+ dbgs() << *S << "\n";
+ });
+}
- const SCEV *visitUnknown(const SCEVUnknown *Expr) {
- if (GCD == Expr)
- return One;
- return Expr;
- }
+/// Third step of delinearization: compute the access functions for the
+/// Subscripts based on the dimensions in Sizes.
+void SCEVAddRecExpr::computeAccessFunctions(
+ ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &Subscripts,
+ SmallVectorImpl<const SCEV *> &Sizes) const {
+
+ // Early exit in case this SCEV is not an affine multivariate function.
+ if (Sizes.empty() || !this->isAffine())
+ return;
- const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
- return Expr;
+ const SCEV *Res = this;
+ int Last = Sizes.size() - 1;
+ for (int i = Last; i >= 0; i--) {
+ const SCEV *Q, *R;
+ SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R);
+
+ DEBUG({
+ dbgs() << "Res: " << *Res << "\n";
+ dbgs() << "Sizes[i]: " << *Sizes[i] << "\n";
+ dbgs() << "Res divided by Sizes[i]:\n";
+ dbgs() << "Quotient: " << *Q << "\n";
+ dbgs() << "Remainder: " << *R << "\n";
+ });
+
+ Res = Q;
+
+ // Do not record the last subscript corresponding to the size of elements in
+ // the array.
+ if (i == Last) {
+
+ // Bail out if the remainder is too complex.
+ if (isa<SCEVAddRecExpr>(R)) {
+ Subscripts.clear();
+ Sizes.clear();
+ return;
+ }
+
+ continue;
+ }
+
+ // Record the access function for the current subscript.
+ Subscripts.push_back(R);
}
-private:
- ScalarEvolution &SE;
- const SCEV *GCD, *Zero, *One;
-};
+ // Also push in last position the remainder of the last division: it will be
+ // the access function of the innermost dimension.
+ Subscripts.push_back(Res);
+
+ std::reverse(Subscripts.begin(), Subscripts.end());
+
+ DEBUG({
+ dbgs() << "Subscripts:\n";
+ for (const SCEV *S : Subscripts)
+ dbgs() << *S << "\n";
+ });
}
/// Splits the SCEV into two vectors of SCEVs representing the subscripts and
/// asking for the SCEV of the memory access with respect to all enclosing
/// loops, calling SCEV->delinearize on that and printing the results.
-const SCEV *
-SCEVAddRecExpr::delinearize(ScalarEvolution &SE,
- SmallVectorImpl<const SCEV *> &Subscripts,
- SmallVectorImpl<const SCEV *> &Sizes) const {
- // Early exit in case this SCEV is not an affine multivariate function.
- if (!this->isAffine())
- return this;
-
- const SCEV *Start = this->getStart();
- const SCEV *Step = this->getStepRecurrence(SE);
-
- // Build the SCEV representation of the canonical induction variable in the
- // loop of this SCEV.
- const SCEV *Zero = SE.getConstant(this->getType(), 0);
- const SCEV *One = SE.getConstant(this->getType(), 1);
- const SCEV *IV =
- SE.getAddRecExpr(Zero, One, this->getLoop(), this->getNoWrapFlags());
-
- DEBUG(dbgs() << "(delinearize: " << *this << "\n");
-
- // When the stride of this SCEV is 1, do not compute the GCD: the size of this
- // subscript is 1, and this same SCEV for the access function.
- const SCEV *Remainder = Zero;
- const SCEV *GCD = One;
-
- // Find the GCD and Remainder of the Start and Step coefficients of this SCEV.
- if (Step != One && !Step->isAllOnesValue())
- GCD = SCEVGCD::findGCD(SE, Start, Step, &Remainder);
-
- DEBUG(dbgs() << "GCD: " << *GCD << "\n");
- DEBUG(dbgs() << "Remainder: " << *Remainder << "\n");
-
- const SCEV *Quotient = Start;
- if (GCD != One && !GCD->isAllOnesValue())
- // As findGCD computed Remainder, GCD divides "Start - Remainder." The
- // Quotient is then this SCEV without Remainder, scaled down by the GCD. The
- // Quotient is what will be used in the next subscript delinearization.
- Quotient = SCEVDivision::divide(SE, SE.getMinusSCEV(Start, Remainder), GCD);
-
- DEBUG(dbgs() << "Quotient: " << *Quotient << "\n");
-
- const SCEV *Rem = Quotient;
- if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Quotient))
- // Recursively call delinearize on the Quotient until there are no more
- // multiples that can be recognized.
- Rem = AR->delinearize(SE, Subscripts, Sizes);
-
- // Scale up the canonical induction variable IV by whatever remains from the
- // Step after division by the GCD: the GCD is the size of all the sub-array.
- if (Step != One && !Step->isAllOnesValue() && GCD != One &&
- !GCD->isAllOnesValue() && Step != GCD) {
- Step = SCEVDivision::divide(SE, Step, GCD);
- IV = SE.getMulExpr(IV, Step);
- }
- // The access function in the current subscript is computed as the canonical
- // induction variable IV (potentially scaled up by the step) and offset by
- // Rem, the offset of delinearization in the sub-array.
- const SCEV *Index = SE.getAddExpr(IV, Rem);
-
- // Record the access function and the size of the current subscript.
- Subscripts.push_back(Index);
- Sizes.push_back(GCD);
+void SCEVAddRecExpr::delinearize(ScalarEvolution &SE,
+ SmallVectorImpl<const SCEV *> &Subscripts,
+ SmallVectorImpl<const SCEV *> &Sizes,
+ const SCEV *ElementSize) const {
+ // First step: collect parametric terms.
+ SmallVector<const SCEV *, 4> Terms;
+ collectParametricTerms(SE, Terms);
-#ifndef NDEBUG
- int Size = Sizes.size();
- DEBUG(dbgs() << "succeeded to delinearize " << *this << "\n");
- DEBUG(dbgs() << "ArrayDecl[UnknownSize]");
- for (int i = 0; i < Size - 1; i++)
- DEBUG(dbgs() << "[" << *Sizes[i] << "]");
- DEBUG(dbgs() << " with elements of " << *Sizes[Size - 1] << " bytes.\n");
-
- DEBUG(dbgs() << "ArrayRef");
- for (int i = 0; i < Size; i++)
- DEBUG(dbgs() << "[" << *Subscripts[i] << "]");
- DEBUG(dbgs() << "\n)\n");
-#endif
+ if (Terms.empty())
+ return;
+
+ // Second step: find subscript sizes.
+ SE.findArrayDimensions(Terms, Sizes, ElementSize);
+
+ if (Sizes.empty())
+ return;
+
+ // Third step: compute the access functions for each subscript.
+ computeAccessFunctions(SE, Subscripts, Sizes);
+
+ if (Subscripts.empty())
+ return;
+
+ DEBUG({
+ dbgs() << "succeeded to delinearize " << *this << "\n";
+ dbgs() << "ArrayDecl[UnknownSize]";
+ for (const SCEV *S : Sizes)
+ dbgs() << "[" << *S << "]";
- return Remainder;
+ dbgs() << "\nArrayRef";
+ for (const SCEV *S : Subscripts)
+ dbgs() << "[" << *S << "]";
+ dbgs() << "\n";
+ });
}
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
ScalarEvolution::ScalarEvolution()
- : FunctionPass(ID), ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64), FirstUnknown(0) {
+ : FunctionPass(ID), ValuesAtScopes(64), LoopDispositions(64),
+ BlockDispositions(64), FirstUnknown(nullptr) {
initializeScalarEvolutionPass(*PassRegistry::getPassRegistry());
}
bool ScalarEvolution::runOnFunction(Function &F) {
this->F = &F;
+ AT = &getAnalysis<AssumptionTracker>();
LI = &getAnalysis<LoopInfo>();
DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
- DL = DLP ? &DLP->getDataLayout() : 0;
+ DL = DLP ? &DLP->getDataLayout() : nullptr;
TLI = &getAnalysis<TargetLibraryInfo>();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
return false;
// destructors, so that they release their references to their values.
for (SCEVUnknown *U = FirstUnknown; U; U = U->Next)
U->~SCEVUnknown();
- FirstUnknown = 0;
+ FirstUnknown = nullptr;
ValueExprMap.clear();
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
+ AU.addRequired<AssumptionTracker>();
AU.addRequiredTransitive<LoopInfo>();
AU.addRequiredTransitive<DominatorTreeWrapperPass>();
AU.addRequired<TargetLibraryInfo>();