From 69fbc7f477c21ce1d8ae5a4aa8a701e47aa2d163 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 13 Jul 2009 20:55:53 +0000 Subject: [PATCH] Move the memoization check for SCEVSignExtendExpr and SCEVZeroExtendExpr ahead of the most expensive analysis. This speeds up analysis and helps avoid pathologically bad behavior on the testcase in PR4534. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75496 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 32 ++++++++++++++++++++++---------- 1 file changed, 22 insertions(+), 10 deletions(-) diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 815a6f21cd2..6a028c19faf 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -772,6 +772,15 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, if (const SCEVZeroExtendExpr *SZ = dyn_cast(Op)) return getZeroExtendExpr(SZ->getOperand(), Ty); + // Before doing any expensive analysis, check to see if we've already + // computed a SCEV for this Op and Ty. + FoldingSetNodeID ID; + ID.AddInteger(scZeroExtend); + ID.AddPointer(Op); + ID.AddPointer(Ty); + void *IP = 0; + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + // If the input value is a chrec scev, and we can prove that the value // did not overflow the old, smaller, value, we can zero extend all of the // operands (often constants). This allows analysis of something like @@ -836,11 +845,8 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, } } - FoldingSetNodeID ID; - ID.AddInteger(scZeroExtend); - ID.AddPointer(Op); - ID.AddPointer(Ty); - void *IP = 0; + // The cast wasn't folded; create an explicit cast node. + // Recompute the insert position, as it may have been invalidated. if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; SCEV *S = SCEVAllocator.Allocate(); new (S) SCEVZeroExtendExpr(ID, Op, Ty); @@ -868,6 +874,15 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, if (const SCEVSignExtendExpr *SS = dyn_cast(Op)) return getSignExtendExpr(SS->getOperand(), Ty); + // Before doing any expensive analysis, check to see if we've already + // computed a SCEV for this Op and Ty. + FoldingSetNodeID ID; + ID.AddInteger(scSignExtend); + ID.AddPointer(Op); + ID.AddPointer(Ty); + void *IP = 0; + if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + // 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 @@ -916,11 +931,8 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, } } - FoldingSetNodeID ID; - ID.AddInteger(scSignExtend); - ID.AddPointer(Op); - ID.AddPointer(Ty); - void *IP = 0; + // The cast wasn't folded; create an explicit cast node. + // Recompute the insert position, as it may have been invalidated. if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; SCEV *S = SCEVAllocator.Allocate(); new (S) SCEVSignExtendExpr(ID, Op, Ty); -- 2.34.1