From 6f69035970fa24380f94c668b3e549cc83c4db4b Mon Sep 17 00:00:00 2001
From: Bob Wilson <bob.wilson@apple.com>
Date: Thu, 1 Apr 2010 23:05:58 +0000
Subject: [PATCH] Rewrite another SSAUpdater function to avoid recursion.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@100147 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Transforms/Utils/SSAUpdater.h |  4 +-
 lib/Transforms/Utils/SSAUpdater.cpp        | 78 +++++++++++++---------
 2 files changed, 48 insertions(+), 34 deletions(-)

diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h
index f550d0285b8..b29b749e8d9 100644
--- a/include/llvm/Transforms/Utils/SSAUpdater.h
+++ b/include/llvm/Transforms/Utils/SSAUpdater.h
@@ -108,8 +108,8 @@ private:
   void FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed,
                         unsigned Counter);
   void FindAvailableVal(BasicBlock *BB, BBInfo *Info, unsigned Counter);
-  void FindExistingPHI(BasicBlock *BB, BBInfo *Info);
-  bool CheckIfPHIMatches(BasicBlock *BB, BBInfo *Info, Value *Val);
+  void FindExistingPHI(BasicBlock *BB);
+  bool CheckIfPHIMatches(PHINode *PHI);
   void RecordMatchingPHI(PHINode *PHI);
   void ClearPHITags(PHINode *PHI);
 
diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp
index 4460381b30a..28ea00e8d9b 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
-- 
2.34.1