// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will
// never be deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVTruncateExpr*> > SCEVTruncates;
SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVZeroExtendExpr*> > SCEVZeroExtends;
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVSignExtendExpr*> > SCEVSignExtends;
SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
+static ManagedStatic<std::map<std::pair<unsigned, std::vector<const SCEV*> >,
SCEVCommutativeExpr*> > SCEVCommExprs;
SCEVCommutativeExpr::~SCEVCommutativeExpr() {
- SCEVCommExprs->erase(std::make_pair(getSCEVType(),
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVCommExprs->erase(std::make_pair(getSCEVType(), SCEVOps));
}
void SCEVCommutativeExpr::print(raw_ostream &OS) const {
// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
// input. Don't use a SCEVHandle here, or else the object will never be
// deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const SCEV*>,
SCEVUDivExpr*> > SCEVUDivs;
SCEVUDivExpr::~SCEVUDivExpr() {
// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
+static ManagedStatic<std::map<std::pair<const Loop *,
+ std::vector<const SCEV*> >,
SCEVAddRecExpr*> > SCEVAddRecExprs;
SCEVAddRecExpr::~SCEVAddRecExpr() {
- SCEVAddRecExprs->erase(std::make_pair(L,
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVAddRecExprs->erase(std::make_pair(L, SCEVOps));
}
bool SCEVAddRecExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
// be extremely short in practice. Note that we take this approach because we
// do not want to depend on the addresses of the objects we are grouping.
for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
- SCEV *S = Ops[i];
+ const SCEV *S = Ops[i];
unsigned Complexity = S->getSCEVType();
// If there are any objects of the same complexity and same value as this
// something is not already an operand of the multiply. If so, merge it into
// the multiply.
for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
- SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
+ const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
- SCEV *MulOpSCEV = Mul->getOperand(MulOp);
+ const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) {
// Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
for (unsigned OtherMulIdx = Idx+1;
OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
++OtherMulIdx) {
- SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
+ const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
// If MulOp occurs in OtherMul, we can fold the two multiplies
// together.
for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
// Scan all of the other operands to this add and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
std::vector<SCEVHandle> LIOps;
- SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
+ const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
LIOps.push_back(Ops[i]);
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
- SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
+ const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
// Okay, it looks like we really DO need an add expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVAddExpr(Ops);
// Scan all of the other operands to this mul and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
std::vector<SCEVHandle> LIOps;
- SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
+ const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
LIOps.push_back(Ops[i]);
std::vector<SCEVHandle> NewOps;
NewOps.reserve(AddRec->getNumOperands());
if (LIOps.size() == 1) {
- SCEV *Scale = LIOps[0];
+ const SCEV *Scale = LIOps[0];
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
} else {
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
- SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
+ const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D}
- SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
+ const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
SCEVHandle NewStart = getMulExpr(F->getStart(),
G->getStart());
SCEVHandle B = F->getStepRecurrence(*this);
// Okay, it looks like we really DO need an mul expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
SCEVOps)];
if (Result == 0)
}
}
- SCEVAddRecExpr *&Result =
- (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
- Operands.end()))];
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVAddRecExpr *&Result = (*SCEVAddRecExprs)[std::make_pair(L, SCEVOps)];
if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
return Result;
}
// Okay, it looks like we really DO need an smax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVSMaxExpr(Ops);
// Okay, it looks like we really DO need a umax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVUMaxExpr(Ops);
// Basic SCEV Analysis and PHI Idiom Recognition Code
//
-/// deleteValueFromRecords - This method should be called by the
-/// client before it removes an instruction from the program, to make sure
-/// that no dangling references are left around.
-void ScalarEvolution::deleteValueFromRecords(Value *V) {
- SmallVector<Value *, 16> Worklist;
-
- if (Scalars.erase(V)) {
- if (PHINode *PN = dyn_cast<PHINode>(V))
- ConstantEvolutionLoopExitValue.erase(PN);
- Worklist.push_back(V);
- }
-
- while (!Worklist.empty()) {
- Value *VV = Worklist.back();
- Worklist.pop_back();
-
- for (Instruction::use_iterator UI = VV->use_begin(), UE = VV->use_end();
- UI != UE; ++UI) {
- Instruction *Inst = cast<Instruction>(*UI);
- if (Scalars.erase(Inst)) {
- if (PHINode *PN = dyn_cast<PHINode>(VV))
- ConstantEvolutionLoopExitValue.erase(PN);
- Worklist.push_back(Inst);
- }
- }
- }
-}
-
/// isSCEVable - Test if values of the given type are analyzable within
/// the SCEV framework. This primarily includes integer types, and it
/// can optionally include pointer types if the ScalarEvolution class
SCEVHandle ScalarEvolution::getSCEV(Value *V) {
assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
- std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator I = Scalars.find(V);
if (I != Scalars.end()) return I->second;
SCEVHandle S = createSCEV(V);
- Scalars.insert(std::make_pair(V, S));
+ Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S));
return S;
}
void ScalarEvolution::
ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
const SCEVHandle &NewVal) {
- std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator SI =
+ Scalars.find(SCEVCallbackVH(I, this));
if (SI == Scalars.end()) return;
SCEVHandle NV =
SCEVHandle SymbolicName = getUnknown(PN);
assert(Scalars.find(PN) == Scalars.end() &&
"PHI node already processed?");
- Scalars.insert(std::make_pair(PN, SymbolicName));
+ Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
// Using this symbolic name for the PHI, analyze the value coming around
// the back-edge.
/// PHI nodes in the given loop. This is used when the trip count of
/// the loop may have changed.
void ScalarEvolution::forgetLoopPHIs(const Loop *L) {
- for (BasicBlock::iterator I = L->getHeader()->begin();
+ BasicBlock *Header = L->getHeader();
+
+ SmallVector<Instruction *, 16> Worklist;
+ for (BasicBlock::iterator I = Header->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I)
- deleteValueFromRecords(PN);
+ Worklist.push_back(PN);
+
+ while (!Worklist.empty()) {
+ Instruction *I = Worklist.pop_back_val();
+ if (Scalars.erase(I))
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(cast<Instruction>(UI));
+ }
}
/// ComputeBackedgeTakenCount - Compute the number of times the backedge
// We can only recognize very limited forms of loop index expressions, in
// particular, only affine AddRec's like {C1,+,C2}.
- SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
+ const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
!isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
!isa<SCEVConstant>(IdxExpr->getOperand(1)))
/// getSCEVAtScope - Compute the value of the specified expression within the
/// indicated loop (which may be null to indicate in no loop). If the
/// expression cannot be evaluated, return UnknownValue.
-SCEVHandle ScalarEvolution::getSCEVAtScope(SCEV *V, const Loop *L) {
+SCEVHandle ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
// FIXME: this should be turned into a virtual method on SCEV!
if (isa<SCEVConstant>(V)) return V;
static std::pair<SCEVHandle,SCEVHandle>
SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
- SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
- SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
- SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
+ const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
+ const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
+ const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
// We currently can only solve this if the coefficients are constants.
if (!LC || !MC || !NC) {
- SCEV *CNC = SE.getCouldNotCompute();
+ const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
APInt NegB(-B);
APInt TwoA( A << 1 );
if (TwoA.isMinValue()) {
- SCEV *CNC = SE.getCouldNotCompute();
+ const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
/// HowFarToZero - Return the number of times a backedge comparing the specified
/// value to zero will execute. If not computable, return UnknownValue
-SCEVHandle ScalarEvolution::HowFarToZero(SCEV *V, const Loop *L) {
+SCEVHandle ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
// 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.
return UnknownValue; // Otherwise it will loop infinitely.
}
- SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
if (!AddRec || AddRec->getLoop() != L)
return UnknownValue;
// the quadratic equation to solve it.
std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec,
*this);
- SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
- SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
+ const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
+ const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
#if 0
errs() << "HFTZ: " << *V << " - sol#1: " << *R1
/// HowFarToNonZero - Return the number of times a backedge checking the
/// specified value for nonzero will execute. If not computable, return
/// UnknownValue
-SCEVHandle ScalarEvolution::HowFarToNonZero(SCEV *V, const Loop *L) {
+SCEVHandle ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
// Loops that look like: while (X == 0) are very strange indeed. We don't
// handle them yet except for the trivial case. This could be expanded in the
// future as needed.
/// expressions in loop trip counts.
bool ScalarEvolution::isLoopGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
- SCEV *LHS, SCEV *RHS) {
+ const SCEV *LHS, const SCEV *RHS) {
BasicBlock *Preheader = L->getLoopPreheader();
BasicBlock *PreheaderDest = L->getHeader();
/// specified less-than comparison will execute. If not computable, return
/// UnknownValue.
ScalarEvolution::BackedgeTakenInfo ScalarEvolution::
-HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) {
+HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
+ const Loop *L, bool isSigned) {
// Only handle: "ADDREC < LoopInvariant".
if (!RHS->isLoopInvariant(L)) return UnknownValue;
- SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
if (!AddRec || AddRec->getLoop() != L)
return UnknownValue;
// Next, solve the constructed addrec
std::pair<SCEVHandle,SCEVHandle> Roots =
SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
- SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
- SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
+ const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
+ const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
// Pick the smallest positive root value.
if (ConstantInt *CB =
+//===----------------------------------------------------------------------===//
+// SCEVCallbackVH Class Implementation
+//===----------------------------------------------------------------------===//
+
+void SCEVCallbackVH::deleted() {
+ assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
+ if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ SE->Scalars.erase(getValPtr());
+ // this now dangles!
+}
+
+void SCEVCallbackVH::allUsesReplacedWith(Value *) {
+ assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
+
+ // Forget all the expressions associated with users of the old value,
+ // so that future queries will recompute the expressions using the new
+ // value.
+ SmallVector<User *, 16> Worklist;
+ Value *Old = getValPtr();
+ bool DeleteOld = false;
+ for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(*UI);
+ while (!Worklist.empty()) {
+ User *U = Worklist.pop_back_val();
+ // Deleting the Old value will cause this to dangle. Postpone
+ // that until everything else is done.
+ if (U == Old) {
+ DeleteOld = true;
+ continue;
+ }
+ if (PHINode *PN = dyn_cast<PHINode>(U))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ if (SE->Scalars.erase(U))
+ for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(*UI);
+ }
+ if (DeleteOld) {
+ if (PHINode *PN = dyn_cast<PHINode>(Old))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ SE->Scalars.erase(Old);
+ // this now dangles!
+ }
+ // this may dangle!
+}
+
+SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
+ : CallbackVH(V), SE(se) {}
+
//===----------------------------------------------------------------------===//
// ScalarEvolution Class Implementation
//===----------------------------------------------------------------------===//
projects / oota-llvm.git / blobdiff