From 526c80bae4d9902fea9efd787c2f212bf111e85e Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Tue, 25 Oct 2011 09:26:43 +0000 Subject: Speculatively revert commits 142790 and 142843 to see if it fixes the dragonegg and llvm-gcc self-host buildbots. Original commit messages: - Reapply r142781 with fix. Original message: Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142916 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 72 +++++++++++++++------------------------- 1 file changed, 26 insertions(+), 46 deletions(-) (limited to 'lib/Analysis/ScalarEvolution.cpp') diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index f65cf34335..1e4bf19e84 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -4844,12 +4844,12 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, // EvaluateExpression adds non-phi values to the CurrentIterVals map. DenseMap NextIterVals; Constant *NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, TD); + if (NextPHI == CurrentIterVals[PN]) + return RetVal = NextPHI; // Stopped evolving! if (NextPHI == 0) return 0; // Couldn't evaluate! NextIterVals[PN] = NextPHI; - bool StoppedEvolving = NextPHI == CurrentIterVals[PN]; - // Also evaluate the other PHI nodes. However, we don't get to stop if we // cease to be able to evaluate one of them or if they stop evolving, // because that doesn't necessarily prevent us from computing PN. @@ -4858,19 +4858,11 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, PHINode *PHI = dyn_cast(I->first); if (!PHI || PHI == PN || PHI->getParent() != Header) continue; Constant *&NextPHI = NextIterVals[PHI]; - if (!NextPHI) { // Not already computed. - Value *BEValue = PHI->getIncomingValue(SecondIsBackedge); - NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, TD); - } - if (NextPHI != I->second) - StoppedEvolving = false; - } - - // If all entries in CurrentIterVals == NextIterVals then we can stop - // iterating, the loop can't continue to change. - if (StoppedEvolving) - return RetVal = CurrentIterVals[PN]; + if (NextPHI) continue; // Already computed! + Value *BEValue = PHI->getIncomingValue(SecondIsBackedge); + NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, TD); + } CurrentIterVals.swap(NextIterVals); } } @@ -4890,33 +4882,29 @@ const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L, // That's the only form we support here. if (PN->getNumIncomingValues() != 2) return getCouldNotCompute(); - DenseMap CurrentIterVals; - BasicBlock *Header = L->getHeader(); - assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!"); - // One entry must be a constant (coming in from outside of the loop), and the // second must be derived from the same PHI. bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); - PHINode *PHI = 0; - for (BasicBlock::iterator I = Header->begin(); - (PHI = dyn_cast(I)); ++I) { - Constant *StartCST = - dyn_cast(PHI->getIncomingValue(!SecondIsBackedge)); - if (StartCST == 0) continue; - CurrentIterVals[PHI] = StartCST; - } - if (!CurrentIterVals.count(PN)) - return getCouldNotCompute(); + Constant *StartCST = + dyn_cast(PN->getIncomingValue(!SecondIsBackedge)); + if (StartCST == 0) return getCouldNotCompute(); // Must be a constant. + + Value *BEValue = PN->getIncomingValue(SecondIsBackedge); + if (getConstantEvolvingPHI(BEValue, L) != PN && + !isa(BEValue)) + return getCouldNotCompute(); // Not derived from same PHI. // Okay, we find a PHI node that defines the trip count of this loop. Execute // the loop symbolically to determine when the condition gets a value of // "ExitWhen". - - unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. - for (unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){ + unsigned IterationNum = 0; + unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. + for (Constant *PHIVal = StartCST; + IterationNum != MaxIterations; ++IterationNum) { + DenseMap PHIValMap; + PHIValMap[PN] = PHIVal; ConstantInt *CondVal = - dyn_cast_or_null(EvaluateExpression(Cond, L, - CurrentIterVals, TD)); + dyn_cast_or_null(EvaluateExpression(Cond, L, PHIValMap, TD)); // Couldn't symbolically evaluate. if (!CondVal) return getCouldNotCompute(); @@ -4926,19 +4914,11 @@ const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L, return getConstant(Type::getInt32Ty(getContext()), IterationNum); } - // Update all the PHI nodes for the next iteration. - DenseMap NextIterVals; - for (DenseMap::const_iterator - I = CurrentIterVals.begin(), E = CurrentIterVals.end(); I != E; ++I){ - PHINode *PHI = dyn_cast(I->first); - if (!PHI || PHI->getParent() != Header) continue; - Constant *&NextPHI = NextIterVals[PHI]; - if (NextPHI) continue; // Already computed! - - Value *BEValue = PHI->getIncomingValue(SecondIsBackedge); - NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, TD); - } - CurrentIterVals.swap(NextIterVals); + // Compute the value of the PHI node for the next iteration. + Constant *NextPHI = EvaluateExpression(BEValue, L, PHIValMap, TD); + if (NextPHI == 0 || NextPHI == PHIVal) + return getCouldNotCompute();// Couldn't evaluate or not making progress... + PHIVal = NextPHI; } // Too many iterations were needed to evaluate. -- cgit v1.2.3