/// The ScalarEvolution's BumpPtrAllocator holds the data.
FoldingSetNodeIDRef FastID;
+ /// AllocationSequenceNumber - This is used as a deterministic tie
+ /// breaker when sorting SCEVs.
+ unsigned AllocationSequenceNumber;
+
// The SCEV baseclass this node corresponds to
const unsigned short SCEVType;
protected:
virtual ~SCEV();
public:
- explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) :
- FastID(ID), SCEVType(SCEVTy), SubclassData(0) {}
+ explicit SCEV(const FoldingSetNodeIDRef ID, unsigned num, unsigned SCEVTy) :
+ FastID(ID), AllocationSequenceNumber(num),
+ SCEVType(SCEVTy), SubclassData(0) {}
unsigned getSCEVType() const { return SCEVType; }
+ /// getAllocationSequenceNumber - Return an arbitrary value which can be
+ /// used to deterministically order a sequence of SCEVs.
+ unsigned getAllocationSequenceNumber() const {
+ return AllocationSequenceNumber;
+ }
+
/// Profile - FoldingSet support.
void Profile(FoldingSetNodeID& ID) { ID = FastID; }
- /// getProfile - Like Profile, but a different interface which doesn't copy.
- const FoldingSetNodeIDRef &getProfile() const { return FastID; }
-
/// isLoopInvariant - Return true if the value of this SCEV is unchanging in
/// the specified loop.
virtual bool isLoopInvariant(const Loop *L) const = 0;
private:
FoldingSet<SCEV> UniqueSCEVs;
BumpPtrAllocator SCEVAllocator;
+ unsigned CurAllocationSequenceNumber;
};
}
friend class ScalarEvolution;
ConstantInt *V;
- SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
- SCEV(ID, scConstant), V(v) {}
+ SCEVConstant(const FoldingSetNodeIDRef ID, unsigned Num, ConstantInt *v)
+ : SCEV(ID, Num, scConstant), V(v) {}
public:
ConstantInt *getValue() const { return V; }
const SCEV *Op;
const Type *Ty;
- SCEVCastExpr(const FoldingSetNodeIDRef ID,
+ SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned Num,
unsigned SCEVTy, const SCEV *op, const Type *ty);
public:
class SCEVTruncateExpr : public SCEVCastExpr {
friend class ScalarEvolution;
- SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
+ SCEVTruncateExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *op, const Type *ty);
public:
class SCEVZeroExtendExpr : public SCEVCastExpr {
friend class ScalarEvolution;
- SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
+ SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *op, const Type *ty);
public:
class SCEVSignExtendExpr : public SCEVCastExpr {
friend class ScalarEvolution;
- SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
+ SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *op, const Type *ty);
public:
const SCEV *const *Operands;
size_t NumOperands;
- SCEVNAryExpr(const FoldingSetNodeIDRef ID,
+ SCEVNAryExpr(const FoldingSetNodeIDRef ID, unsigned Num,
enum SCEVTypes T, const SCEV *const *O, size_t N)
- : SCEV(ID, T), Operands(O), NumOperands(N) {}
+ : SCEV(ID, Num, T), Operands(O), NumOperands(N) {}
public:
size_t getNumOperands() const { return NumOperands; }
///
class SCEVCommutativeExpr : public SCEVNAryExpr {
protected:
- SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
+ SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, unsigned Num,
enum SCEVTypes T, const SCEV *const *O, size_t N)
- : SCEVNAryExpr(ID, T, O, N) {}
+ : SCEVNAryExpr(ID, Num, T, O, N) {}
public:
virtual const char *getOperationStr() const = 0;
class SCEVAddExpr : public SCEVCommutativeExpr {
friend class ScalarEvolution;
- SCEVAddExpr(const FoldingSetNodeIDRef ID,
+ SCEVAddExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *const *O, size_t N)
- : SCEVCommutativeExpr(ID, scAddExpr, O, N) {
+ : SCEVCommutativeExpr(ID, Num, scAddExpr, O, N) {
}
public:
class SCEVMulExpr : public SCEVCommutativeExpr {
friend class ScalarEvolution;
- SCEVMulExpr(const FoldingSetNodeIDRef ID,
+ SCEVMulExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *const *O, size_t N)
- : SCEVCommutativeExpr(ID, scMulExpr, O, N) {
+ : SCEVCommutativeExpr(ID, Num, scMulExpr, O, N) {
}
public:
const SCEV *LHS;
const SCEV *RHS;
- SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
- : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
+ SCEVUDivExpr(const FoldingSetNodeIDRef ID, unsigned Num,
+ const SCEV *lhs, const SCEV *rhs)
+ : SCEV(ID, Num, scUDivExpr), LHS(lhs), RHS(rhs) {}
public:
const SCEV *getLHS() const { return LHS; }
const Loop *L;
- SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
+ SCEVAddRecExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *const *O, size_t N, const Loop *l)
- : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {
+ : SCEVNAryExpr(ID, Num, scAddRecExpr, O, N), L(l) {
for (size_t i = 0, e = NumOperands; i != e; ++i)
assert(Operands[i]->isLoopInvariant(l) &&
"Operands of AddRec must be loop-invariant!");
class SCEVSMaxExpr : public SCEVCommutativeExpr {
friend class ScalarEvolution;
- SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
+ SCEVSMaxExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *const *O, size_t N)
- : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
+ : SCEVCommutativeExpr(ID, Num, scSMaxExpr, O, N) {
// Max never overflows.
setHasNoUnsignedWrap(true);
setHasNoSignedWrap(true);
class SCEVUMaxExpr : public SCEVCommutativeExpr {
friend class ScalarEvolution;
- SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
+ SCEVUMaxExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *const *O, size_t N)
- : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
+ : SCEVCommutativeExpr(ID, Num, scUMaxExpr, O, N) {
// Max never overflows.
setHasNoUnsignedWrap(true);
setHasNoSignedWrap(true);
friend class ScalarEvolution;
Value *V;
- SCEVUnknown(const FoldingSetNodeIDRef ID, Value *v) :
- SCEV(ID, scUnknown), V(v) {}
+ SCEVUnknown(const FoldingSetNodeIDRef ID, unsigned Num, Value *v)
+ : SCEV(ID, Num, scUnknown), V(v) {}
public:
Value *getValue() const { return V; }
}
SCEVCouldNotCompute::SCEVCouldNotCompute() :
- SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {}
+ SCEV(FoldingSetNodeIDRef(), 0, scCouldNotCompute) {}
bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
ID.AddPointer(V);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
- SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
+ SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
+ V);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
WriteAsOperand(OS, V, false);
}
-SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID,
+SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned Num,
unsigned SCEVTy, const SCEV *op, const Type *ty)
- : SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
+ : SCEV(ID, Num, SCEVTy), Op(op), Ty(ty) {}
bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
return Op->dominates(BB, DT);
return Op->properlyDominates(BB, DT);
}
-SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
+SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *op, const Type *ty)
- : SCEVCastExpr(ID, scTruncate, op, ty) {
+ : SCEVCastExpr(ID, Num, scTruncate, op, ty) {
assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot truncate non-integer value!");
OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
-SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
+SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *op, const Type *ty)
- : SCEVCastExpr(ID, scZeroExtend, op, ty) {
+ : SCEVCastExpr(ID, Num, scZeroExtend, op, ty) {
assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot zero extend non-integer value!");
OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
-SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
+SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num,
const SCEV *op, const Type *ty)
- : SCEVCastExpr(ID, scSignExtend, op, ty) {
+ : SCEVCastExpr(ID, Num, scSignExtend, op, ty) {
assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot sign extend non-integer value!");
if (LST != RST)
return LST < RST;
- // Then, pick an arbitrary sort. Use the profiling data for speed.
- const FoldingSetNodeIDRef &L = LHS->getProfile();
- const FoldingSetNodeIDRef &R = RHS->getProfile();
- size_t LSize = L.getSize();
- size_t RSize = R.getSize();
- if (LSize != RSize)
- return LSize < RSize;
- return memcmp(L.getData(), R.getData(),
- LSize * sizeof(*L.getData())) < 0;
+ // Then, pick an arbitrary deterministic sort.
+ return LHS->getAllocationSequenceNumber() <
+ RHS->getAllocationSequenceNumber();
}
};
}
// Recompute the insert position, as it may have been invalidated.
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
Op, Ty);
UniqueSCEVs.InsertNode(S, IP);
return S;
// Recompute the insert position, as it may have been invalidated.
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
Op, Ty);
UniqueSCEVs.InsertNode(S, IP);
return S;
// Recompute the insert position, as it may have been invalidated.
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
Op, Ty);
UniqueSCEVs.InsertNode(S, IP);
return S;
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
S = new (SCEVAllocator) SCEVAddExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
}
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
}
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
LHS, RHS);
UniqueSCEVs.InsertNode(S, IP);
return S;
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Operands.size());
std::uninitialized_copy(Operands.begin(), Operands.end(), O);
S = new (SCEVAllocator) SCEVAddRecExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
O, Operands.size(), L);
UniqueSCEVs.InsertNode(S, IP);
}
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
return S;
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
SCEV *S = new (SCEVAllocator) SCEVUMaxExpr(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
return S;
ID.AddPointer(V);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
- SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V);
+ SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator),
+ CurAllocationSequenceNumber++,
+ V);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
//===----------------------------------------------------------------------===//
ScalarEvolution::ScalarEvolution()
- : FunctionPass(&ID) {
+ : FunctionPass(&ID), CurAllocationSequenceNumber(0) {
}
bool ScalarEvolution::runOnFunction(Function &F) {