Add comment.

[oota-llvm.git] / lib / Transforms / Scalar / CondPropagate.cpp

diff --git a/lib/Transforms/Scalar/CondPropagate.cpp b/lib/Transforms/Scalar/CondPropagate.cpp
index 5eb5abd9f87898ebfa1131e9559d9a2c2776b60e..bed2b359a0e38b73a3e29cbde4531412deb1a0c9 100644 (file)
--- a/lib/Transforms/Scalar/CondPropagate.cpp
+++ b/lib/Transforms/Scalar/CondPropagate.cpp
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -22,16 +22,18 @@
 #include "llvm/Type.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
-#include <iostream>
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Streams.h"
 using namespace llvm;
 
+STATISTIC(NumBrThread, "Number of CFG edges threaded through branches");
+STATISTIC(NumSwThread, "Number of CFG edges threaded through switches");
+
 namespace {
-  Statistic<>
-  NumBrThread("condprop", "Number of CFG edges threaded through branches");
-  Statistic<>
-  NumSwThread("condprop", "Number of CFG edges threaded through switches");
+  struct VISIBILITY_HIDDEN CondProp : public FunctionPass {
+    static char ID; // Pass identification, replacement for typeid
+    CondProp() : FunctionPass((intptr_t)&ID) {}
 
-  struct CondProp : public FunctionPass {
     virtual bool runOnFunction(Function &F);
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
@@ -46,6 +48,8 @@ namespace {
     void SimplifyPredecessors(SwitchInst *SI);
     void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
   };
+  
+  char CondProp::ID = 0;
   RegisterPass<CondProp> X("condprop", "Conditional Propagation");
 }
 
@@ -61,7 +65,7 @@ bool CondProp::runOnFunction(Function &F) {
     MadeChange = false;
     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
       SimplifyBlock(BB);
-    EverMadeChange = MadeChange;
+    EverMadeChange = EverMadeChange || MadeChange;
   } while (MadeChange);
   return EverMadeChange;
 }
@@ -135,17 +139,18 @@ void CondProp::SimplifyPredecessors(BranchInst *BI) {
   // constants.  Walk from the end to remove operands from the end when
   // possible, and to avoid invalidating "i".
   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
-    if (ConstantBool *CB = dyn_cast<ConstantBool>(PN->getIncomingValue(i-1))) {
+    if (ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
       // If we have a constant, forward the edge from its current to its
       // ultimate destination.
-      bool PHIGone = PN->getNumIncomingValues() == 2;
       RevectorBlockTo(PN->getIncomingBlock(i-1),
-                      BI->getSuccessor(CB->getValue() == 0));
+                      BI->getSuccessor(CB->isZero()));
       ++NumBrThread;
 
-      // If there were two predecessors before this simplification, the PHI node
-      // will be deleted.  Don't iterate through it the last time.
-      if (PHIGone) return;
+      // If there were two predecessors before this simplification, or if the
+      // PHI node contained all the same value except for the one we just
+      // substituted, the PHI node may be deleted.  Don't iterate through it the
+      // last time.
+      if (BI->getCondition() != PN) return;
     }
 }
 
@@ -173,16 +178,17 @@ void CondProp::SimplifyPredecessors(SwitchInst *SI) {
     if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
       // If we have a constant, forward the edge from its current to its
       // ultimate destination.
-      bool PHIGone = PN->getNumIncomingValues() == 2;
       unsigned DestCase = SI->findCaseValue(CI);
       RevectorBlockTo(PN->getIncomingBlock(i-1),
                       SI->getSuccessor(DestCase));
       ++NumSwThread;
       RemovedPreds = true;
 
-      // If there were two predecessors before this simplification, the PHI node
-      // will be deleted.  Don't iterate through it the last time.
-      if (PHIGone) return;
+      // If there were two predecessors before this simplification, or if the
+      // PHI node contained all the same value except for the one we just
+      // substituted, the PHI node may be deleted.  Don't iterate through it the
+      // last time.
+      if (SI->getCondition() != PN) return;
     }
 }
 
@@ -196,11 +202,14 @@ void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
   // Get the old block we are threading through.
   BasicBlock *OldSucc = FromBr->getSuccessor(0);
 
-  // ToBB should not have any PHI nodes in it to update, because OldSucc had
-  // multiple successors.  If OldSucc had multiple successor and ToBB had
-  // multiple predecessors, the edge between them would be critical, which we
-  // already took care of.
-  assert(!isa<PHINode>(ToBB->begin()) && "Critical Edge Found!");
+  // OldSucc had multiple successors. If ToBB has multiple predecessors, then 
+  // the edge between them would be critical, which we already took care of.
+  // If ToBB has single operand PHI node then take care of it here.
+  while (PHINode *PN = dyn_cast<PHINode>(ToBB->begin())) {
+    assert(PN->getNumIncomingValues() == 1 && "Critical Edge Found!");    
+    PN->replaceAllUsesWith(PN->getIncomingValue(0));
+    PN->eraseFromParent();
+  }
 
   // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
   OldSucc->removePredecessor(FromBB);