#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"
errs() << '\n';
}
-void SCEV::print(std::ostream &o) const {
- raw_os_ostream OS(o);
- print(OS);
-}
-
bool SCEV::isZero() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isZero();
explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {}
bool operator()(const SCEV *LHS, const SCEV *RHS) const {
+ // Fast-path: SCEVs are uniqued so we can do a quick equality check.
+ if (LHS == RHS)
+ return false;
+
// Primarily, sort the SCEVs by their getSCEVType().
if (LHS->getSCEVType() != RHS->getSCEVType())
return LHS->getSCEVType() < RHS->getSCEVType();
// If we have special knowledge that this addrec won't overflow,
// we don't need to do any further analysis.
- if (AR->hasNoUnsignedOverflow())
+ if (AR->hasNoUnsignedWrap())
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
L);
// If we have special knowledge that this addrec won't overflow,
// we don't need to do any further analysis.
- if (AR->hasNoSignedOverflow())
+ if (AR->hasNoSignedWrap())
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
L);
if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
- return LHS; // X udiv 1 --> x
+ return LHS; // X udiv 1 --> x
if (RHSC->isZero())
return getIntegerSCEV(0, LHS->getType()); // value is undefined
// count information isn't going to change anything. In the later
// case, createNodeForPHI will perform the necessary updates on its
// own when it gets to that point.
- if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second))
+ if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second)) {
+ ValuesAtScopes.erase(It->second);
Scalars.erase(It);
- ValuesAtScopes.erase(I);
+ }
}
PushDefUseChildren(I, Worklist);
getSCEV(OBO->getOperand(1)) ==
PHISCEV->getStepRecurrence(*this)) {
const SCEVAddRecExpr *PostInc = PHISCEV->getPostIncExpr(*this);
- if (OBO->hasNoUnsignedOverflow()) {
+ if (OBO->hasNoUnsignedWrap()) {
const_cast<SCEVAddRecExpr *>(PHISCEV)
- ->setHasNoUnsignedOverflow(true);
+ ->setHasNoUnsignedWrap(true);
const_cast<SCEVAddRecExpr *>(PostInc)
- ->setHasNoUnsignedOverflow(true);
+ ->setHasNoUnsignedWrap(true);
}
- if (OBO->hasNoSignedOverflow()) {
+ if (OBO->hasNoSignedWrap()) {
const_cast<SCEVAddRecExpr *>(PHISCEV)
- ->setHasNoSignedOverflow(true);
+ ->setHasNoSignedWrap(true);
const_cast<SCEVAddRecExpr *>(PostInc)
- ->setHasNoSignedOverflow(true);
+ ->setHasNoSignedWrap(true);
}
}
return getIntegerSCEV(0, V->getType());
else if (isa<UndefValue>(V))
return getIntegerSCEV(0, V->getType());
+ else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
+ return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee());
else
return getUnknown(V);
// count information isn't going to change anything. In the later
// case, createNodeForPHI will perform the necessary updates on its
// own when it gets to that point.
- if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second))
+ if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second)) {
+ ValuesAtScopes.erase(It->second);
Scalars.erase(It);
- ValuesAtScopes.erase(I);
+ }
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
std::map<SCEVCallbackVH, const SCEV*>::iterator It =
Scalars.find(static_cast<Value *>(I));
if (It != Scalars.end()) {
+ ValuesAtScopes.erase(It->second);
Scalars.erase(It);
- ValuesAtScopes.erase(I);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
- case ICmpInst::ICMP_EQ: {
- // Convert to: while (X-Y == 0) // while (X == Y)
+ case ICmpInst::ICMP_EQ: { // while (X == Y)
+ // Convert to: while (X-Y == 0)
const SCEV *TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
return getCouldNotCompute();
}
-/// getSCEVAtScope - Return a SCEV expression handle for the specified value
+/// getSCEVAtScope - Return a SCEV expression for the specified value
/// at the specified scope in the program. The L value specifies a loop
/// nest to evaluate the expression at, where null is the top-level or a
/// specified loop is immediately inside of the loop.
/// In the case that a relevant loop exit value cannot be computed, the
/// original value V is returned.
const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
- // FIXME: this should be turned into a virtual method on SCEV!
+ // Check to see if we've folded this expression at this loop before.
+ std::map<const Loop *, const SCEV *> &Values = ValuesAtScopes[V];
+ std::pair<std::map<const Loop *, const SCEV *>::iterator, bool> Pair =
+ Values.insert(std::make_pair(L, static_cast<const SCEV *>(0)));
+ if (!Pair.second)
+ return Pair.first->second ? Pair.first->second : V;
+
+ // Otherwise compute it.
+ const SCEV *C = computeSCEVAtScope(V, L);
+ ValuesAtScopes[V][L] = C;
+ return C;
+}
+const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
if (isa<SCEVConstant>(V)) return V;
// If this instruction is evolved from a constant-evolving PHI, compute the
// the arguments into constants, and if so, try to constant propagate the
// result. This is particularly useful for computing loop exit values.
if (CanConstantFold(I)) {
- // Check to see if we've folded this instruction at this loop before.
- std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
- std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
- Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
- if (!Pair.second)
- return Pair.first->second ? &*getSCEV(Pair.first->second) : V;
-
std::vector<Constant*> Operands;
Operands.reserve(I->getNumOperands());
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
getContext());
else
C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
- &Operands[0], Operands.size(),
+ &Operands[0], Operands.size(),
getContext());
- Pair.first->second = C;
return getSCEV(C);
}
}
// First, handle unitary steps.
if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so:
- return getNegativeSCEV(Start); // N = -Start (as unsigned)
+ return getNegativeSCEV(Start); // N = -Start (as unsigned)
if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so:
return Start; // N = Start (as unsigned)
if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
- if (AI->isIdenticalTo(BI))
+ if (AI->isIdenticalTo(BI) && !AI->mayReadFromMemory())
return true;
// Otherwise assume they may have a different value.
assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
SE->ConstantEvolutionLoopExitValue.erase(PN);
- if (Instruction *I = dyn_cast<Instruction>(getValPtr()))
- SE->ValuesAtScopes.erase(I);
SE->Scalars.erase(getValPtr());
// this now dangles!
}
continue;
if (PHINode *PN = dyn_cast<PHINode>(U))
SE->ConstantEvolutionLoopExitValue.erase(PN);
- if (Instruction *I = dyn_cast<Instruction>(U))
- SE->ValuesAtScopes.erase(I);
SE->Scalars.erase(U);
for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
UI != UE; ++UI)
if (DeleteOld) {
if (PHINode *PN = dyn_cast<PHINode>(Old))
SE->ConstantEvolutionLoopExitValue.erase(PN);
- if (Instruction *I = dyn_cast<Instruction>(Old))
- SE->ValuesAtScopes.erase(I);
SE->Scalars.erase(Old);
// this now dangles!
}
PrintLoopInfo(OS, &SE, *I);
}
-void ScalarEvolution::print(std::ostream &o, const Module *M) const {
- raw_os_ostream OS(o);
- print(OS, M);
-}
projects / oota-llvm.git / blobdiff