diff options
author | Bob Wilson <bob.wilson@apple.com> | 2010-04-01 23:05:58 +0000 |
---|---|---|
committer | Bob Wilson <bob.wilson@apple.com> | 2010-04-01 23:05:58 +0000 |
commit | 6f69035970fa24380f94c668b3e549cc83c4db4b (patch) | |
tree | 411e7f8f2fb6708e521b2c9edf21ff5fd2f61d8b /lib/Transforms/Utils/SSAUpdater.cpp | |
parent | 1d8f83d0a00e912c55ec0974eba6122666cc6fa1 (diff) |
Rewrite another SSAUpdater function to avoid recursion.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@100147 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms/Utils/SSAUpdater.cpp')
-rw-r--r-- | lib/Transforms/Utils/SSAUpdater.cpp | 78 |
1 files changed, 46 insertions, 32 deletions
diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp index 4460381b30..28ea00e8d9 100644 --- a/lib/Transforms/Utils/SSAUpdater.cpp +++ b/lib/Transforms/Utils/SSAUpdater.cpp @@ -366,7 +366,7 @@ void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info, PHINode *NewPHI = 0; if (Info->DefBB == BB) { // Look for an existing PHI. - FindExistingPHI(BB, Info); + FindExistingPHI(BB); if (!Info->AvailableVal) { NewPHI = PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(), &BB->front()); @@ -401,11 +401,11 @@ void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info, /// FindExistingPHI - Look through the PHI nodes in a block to see if any of /// them match what is needed. -void SSAUpdater::FindExistingPHI(BasicBlock *BB, BBInfo *Info) { +void SSAUpdater::FindExistingPHI(BasicBlock *BB) { PHINode *SomePHI; for (BasicBlock::iterator It = BB->begin(); (SomePHI = dyn_cast<PHINode>(It)); ++It) { - if (CheckIfPHIMatches(BB, Info, SomePHI)) { + if (CheckIfPHIMatches(SomePHI)) { RecordMatchingPHI(SomePHI); break; } @@ -413,40 +413,54 @@ void SSAUpdater::FindExistingPHI(BasicBlock *BB, BBInfo *Info) { } } -/// CheckIfPHIMatches - Check if Val is a PHI node in block BB that matches -/// the placement and values in the BBMap. -bool SSAUpdater::CheckIfPHIMatches(BasicBlock *BB, BBInfo *Info, Value *Val) { - if (Info->AvailableVal) - return Val == Info->AvailableVal; +/// CheckIfPHIMatches - Check if a PHI node matches the placement and values +/// in the BBMap. +bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) { + BBMapTy *BBMap = getBBMap(BM); + SmallVector<PHINode*, 20> WorkList; + WorkList.push_back(PHI); - // Check if Val is a PHI in this block. - PHINode *PHI = dyn_cast<PHINode>(Val); - if (!PHI || PHI->getParent() != BB) - return false; + // Mark that the block containing this PHI has been visited. + (*BBMap)[PHI->getParent()]->PHITag = PHI; - // If this block has already been visited, check if this PHI matches. - if (Info->PHITag) - return PHI == Info->PHITag; - Info->PHITag = PHI; - bool IsMatch = true; + while (!WorkList.empty()) { + PHI = WorkList.pop_back_val(); - // Iterate through the predecessors. - BBMapTy *BBMap = getBBMap(BM); - for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { - BasicBlock *Pred = PHI->getIncomingBlock(i); - Value *IncomingVal = PHI->getIncomingValue(i); - BBInfo *PredInfo = (*BBMap)[Pred]; - // Skip to the nearest preceding definition. - if (PredInfo->DefBB != Pred) { - Pred = PredInfo->DefBB; - PredInfo = (*BBMap)[Pred]; - } - if (!CheckIfPHIMatches(Pred, PredInfo, IncomingVal)) { - IsMatch = false; - break; + // Iterate through the PHI's incoming values. + for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { + Value *IncomingVal = PHI->getIncomingValue(i); + BasicBlock *Pred = PHI->getIncomingBlock(i); + BBInfo *PredInfo = (*BBMap)[Pred]; + // Skip to the nearest preceding definition. + if (PredInfo->DefBB != Pred) { + Pred = PredInfo->DefBB; + PredInfo = (*BBMap)[Pred]; + } + + // Check if it matches the expected value. + if (PredInfo->AvailableVal) { + if (IncomingVal == PredInfo->AvailableVal) + continue; + return false; + } + + // Check if the value is a PHI in the correct block. + PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal); + if (!IncomingPHIVal || IncomingPHIVal->getParent() != Pred) + return false; + + // If this block has already been visited, check if this PHI matches. + if (PredInfo->PHITag) { + if (IncomingPHIVal == PredInfo->PHITag) + continue; + return false; + } + PredInfo->PHITag = IncomingPHIVal; + + WorkList.push_back(IncomingPHIVal); } } - return IsMatch; + return true; } /// RecordMatchingPHI - For a PHI node that matches, record it and its input |