diff options
author | Dan Gohman <gohman@apple.com> | 2010-06-18 19:26:04 +0000 |
---|---|---|
committer | Dan Gohman <gohman@apple.com> | 2010-06-18 19:26:04 +0000 |
commit | 78db186d2dbaf4745f7e4beab4029db40856b54b (patch) | |
tree | 62518c4f9f58afe1407ad840269e1d2d5e09a5a0 | |
parent | dd76f18f90f3d9934353d852e45271b3be747743 (diff) | |
download | external_llvm-78db186d2dbaf4745f7e4beab4029db40856b54b.zip external_llvm-78db186d2dbaf4745f7e4beab4029db40856b54b.tar.gz external_llvm-78db186d2dbaf4745f7e4beab4029db40856b54b.tar.bz2 |
Reapply 105540, 105542, and 105548, and revert r105732.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106304 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 16 | ||||
-rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpressions.h | 49 | ||||
-rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 176 | ||||
-rw-r--r-- | test/Analysis/ScalarEvolution/2008-07-29-SMinExpr.ll | 2 |
4 files changed, 78 insertions, 165 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 00b95c9..7bfd0ce 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -54,6 +54,10 @@ namespace llvm { /// 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; @@ -68,11 +72,18 @@ namespace llvm { 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; } @@ -663,6 +674,7 @@ namespace llvm { private: FoldingSet<SCEV> UniqueSCEVs; BumpPtrAllocator SCEVAllocator; + unsigned CurAllocationSequenceNumber; }; } diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 7424203..2e4fd7e 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -37,8 +37,8 @@ namespace llvm { 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; } @@ -81,7 +81,7 @@ namespace llvm { 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: @@ -120,7 +120,7 @@ namespace llvm { class SCEVTruncateExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVTruncateExpr(const FoldingSetNodeIDRef ID, + SCEVTruncateExpr(const FoldingSetNodeIDRef ID, unsigned Num, const SCEV *op, const Type *ty); public: @@ -140,7 +140,7 @@ namespace llvm { class SCEVZeroExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, + SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num, const SCEV *op, const Type *ty); public: @@ -160,7 +160,7 @@ namespace llvm { class SCEVSignExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, + SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num, const SCEV *op, const Type *ty); public: @@ -187,9 +187,9 @@ namespace llvm { 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; } @@ -262,9 +262,9 @@ namespace llvm { /// 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; @@ -288,9 +288,9 @@ namespace llvm { 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: @@ -316,9 +316,9 @@ namespace llvm { 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: @@ -340,8 +340,9 @@ namespace llvm { 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; } @@ -390,9 +391,9 @@ namespace llvm { 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!"); @@ -472,9 +473,9 @@ namespace llvm { 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); @@ -497,9 +498,9 @@ namespace llvm { 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); @@ -524,8 +525,8 @@ namespace llvm { 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; } diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 7e7fc75..8a653fe 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -141,7 +141,7 @@ bool SCEV::isAllOnesValue() const { } SCEVCouldNotCompute::SCEVCouldNotCompute() : - SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {} + SCEV(FoldingSetNodeIDRef(), 0, scCouldNotCompute) {} bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const { llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); @@ -177,7 +177,9 @@ const SCEV *ScalarEvolution::getConstant(ConstantInt *V) { 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; } @@ -198,9 +200,9 @@ void SCEVConstant::print(raw_ostream &OS) const { 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); @@ -210,9 +212,9 @@ bool SCEVCastExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { 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!"); @@ -222,9 +224,9 @@ void SCEVTruncateExpr::print(raw_ostream &OS) const { 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!"); @@ -234,9 +236,9 @@ void SCEVZeroExtendExpr::print(raw_ostream &OS) const { 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!"); @@ -505,109 +507,14 @@ namespace { return false; // Primarily, sort the SCEVs by their getSCEVType(). - if (LHS->getSCEVType() != RHS->getSCEVType()) - return LHS->getSCEVType() < RHS->getSCEVType(); - - // Aside from the getSCEVType() ordering, the particular ordering - // isn't very important except that it's beneficial to be consistent, - // so that (a + b) and (b + a) don't end up as different expressions. - - // Sort SCEVUnknown values with some loose heuristics. TODO: This is - // not as complete as it could be. - if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS)) { - const SCEVUnknown *RU = cast<SCEVUnknown>(RHS); - - // Order pointer values after integer values. This helps SCEVExpander - // form GEPs. - if (LU->getType()->isPointerTy() && !RU->getType()->isPointerTy()) - return false; - if (RU->getType()->isPointerTy() && !LU->getType()->isPointerTy()) - return true; - - // Compare getValueID values. - if (LU->getValue()->getValueID() != RU->getValue()->getValueID()) - return LU->getValue()->getValueID() < RU->getValue()->getValueID(); - - // Sort arguments by their position. - if (const Argument *LA = dyn_cast<Argument>(LU->getValue())) { - const Argument *RA = cast<Argument>(RU->getValue()); - return LA->getArgNo() < RA->getArgNo(); - } - - // For instructions, compare their loop depth, and their opcode. - // This is pretty loose. - if (Instruction *LV = dyn_cast<Instruction>(LU->getValue())) { - Instruction *RV = cast<Instruction>(RU->getValue()); - - // Compare loop depths. - if (LI->getLoopDepth(LV->getParent()) != - LI->getLoopDepth(RV->getParent())) - return LI->getLoopDepth(LV->getParent()) < - LI->getLoopDepth(RV->getParent()); - - // Compare opcodes. - if (LV->getOpcode() != RV->getOpcode()) - return LV->getOpcode() < RV->getOpcode(); - - // Compare the number of operands. - if (LV->getNumOperands() != RV->getNumOperands()) - return LV->getNumOperands() < RV->getNumOperands(); - } - - return false; - } - - // Compare constant values. - if (const SCEVConstant *LC = dyn_cast<SCEVConstant>(LHS)) { - const SCEVConstant *RC = cast<SCEVConstant>(RHS); - if (LC->getValue()->getBitWidth() != RC->getValue()->getBitWidth()) - return LC->getValue()->getBitWidth() < RC->getValue()->getBitWidth(); - return LC->getValue()->getValue().ult(RC->getValue()->getValue()); - } - - // Compare addrec loop depths. - if (const SCEVAddRecExpr *LA = dyn_cast<SCEVAddRecExpr>(LHS)) { - const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS); - if (LA->getLoop()->getLoopDepth() != RA->getLoop()->getLoopDepth()) - return LA->getLoop()->getLoopDepth() < RA->getLoop()->getLoopDepth(); - } - - // Lexicographically compare n-ary expressions. - if (const SCEVNAryExpr *LC = dyn_cast<SCEVNAryExpr>(LHS)) { - const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS); - for (unsigned i = 0, e = LC->getNumOperands(); i != e; ++i) { - if (i >= RC->getNumOperands()) - return false; - if (operator()(LC->getOperand(i), RC->getOperand(i))) - return true; - if (operator()(RC->getOperand(i), LC->getOperand(i))) - return false; - } - return LC->getNumOperands() < RC->getNumOperands(); - } - - // Lexicographically compare udiv expressions. - if (const SCEVUDivExpr *LC = dyn_cast<SCEVUDivExpr>(LHS)) { - const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS); - if (operator()(LC->getLHS(), RC->getLHS())) - return true; - if (operator()(RC->getLHS(), LC->getLHS())) - return false; - if (operator()(LC->getRHS(), RC->getRHS())) - return true; - if (operator()(RC->getRHS(), LC->getRHS())) - return false; - return false; - } - - // Compare cast expressions by operand. - if (const SCEVCastExpr *LC = dyn_cast<SCEVCastExpr>(LHS)) { - const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS); - return operator()(LC->getOperand(), RC->getOperand()); - } - - llvm_unreachable("Unknown SCEV kind!"); - return false; + unsigned LST = LHS->getSCEVType(); + unsigned RST = RHS->getSCEVType(); + if (LST != RST) + return LST < RST; + + // Then, pick an arbitrary deterministic sort. + return LHS->getAllocationSequenceNumber() < + RHS->getAllocationSequenceNumber(); } }; } @@ -625,36 +532,18 @@ namespace { static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops, LoopInfo *LI) { if (Ops.size() < 2) return; // Noop + + SCEVComplexityCompare Comp(LI); + if (Ops.size() == 2) { // This is the common case, which also happens to be trivially simple. // Special case it. - if (SCEVComplexityCompare(LI)(Ops[1], Ops[0])) + if (Comp(Ops[1], Ops[0])) std::swap(Ops[0], Ops[1]); return; } - // Do the rough sort by complexity. - std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI)); - - // Now that we are sorted by complexity, group elements of the same - // complexity. Note that this is, at worst, N^2, but the vector is likely to - // 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) { - const SCEV *S = Ops[i]; - unsigned Complexity = S->getSCEVType(); - - // If there are any objects of the same complexity and same value as this - // one, group them. - for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) { - if (Ops[j] == S) { // Found a duplicate. - // Move it to immediately after i'th element. - std::swap(Ops[i+1], Ops[j]); - ++i; // no need to rescan it. - if (i == e-2) return; // Done! - } - } - } + std::stable_sort(Ops.begin(), Ops.end(), Comp); } @@ -848,6 +737,7 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, // 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; @@ -983,6 +873,7 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, // 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; @@ -1118,6 +1009,7 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, // 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; @@ -1619,6 +1511,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, 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); } @@ -1821,6 +1714,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, 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); } @@ -1925,6 +1819,7 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, 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; @@ -2036,6 +1931,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 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); } @@ -2144,6 +2040,7 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { 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; @@ -2249,6 +2146,7 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { 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; @@ -2329,7 +2227,9 @@ const SCEV *ScalarEvolution::getUnknown(Value *V) { 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; } @@ -5682,7 +5582,7 @@ ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se) //===----------------------------------------------------------------------===// ScalarEvolution::ScalarEvolution() - : FunctionPass(&ID) { + : FunctionPass(&ID), CurAllocationSequenceNumber(0) { } bool ScalarEvolution::runOnFunction(Function &F) { diff --git a/test/Analysis/ScalarEvolution/2008-07-29-SMinExpr.ll b/test/Analysis/ScalarEvolution/2008-07-29-SMinExpr.ll index 3542ad2..cba20ee 100644 --- a/test/Analysis/ScalarEvolution/2008-07-29-SMinExpr.ll +++ b/test/Analysis/ScalarEvolution/2008-07-29-SMinExpr.ll @@ -22,5 +22,5 @@ afterfor: ; preds = %forinc, %entry ret i32 %j.0.lcssa } -; CHECK: backedge-taken count is (-2147483632 + ((-1 + (-1 * %{{[xy]}})) smax (-1 + (-1 * %{{[xy]}})))) +; CHECK: backedge-taken count is (-2147483632 + ((-1 + (-1 * %y)) smax (-1 + (-1 * %x)))) |