[llvm-commits] CVS: llvm/lib/Transforms/Scalar/SimplifyCFG.cpp

2007-04-04 Thread Chris Lattner 


Changes in directory llvm/lib/Transforms/Scalar:

SimplifyCFG.cpp updated: 1.20 - 1.21
---
Log message:

Use a worklist-driven algorithm instead of a recursive one.


---
Diffs of the changes:  (+36 -27)

 SimplifyCFG.cpp |   63 
 1 files changed, 36 insertions(+), 27 deletions(-)


Index: llvm/lib/Transforms/Scalar/SimplifyCFG.cpp
diff -u llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.20 
llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.21
--- llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.20 Sat Mar  3 22:20:48 2007
+++ llvm/lib/Transforms/Scalar/SimplifyCFG.cpp  Wed Apr  4 20:27:02 2007
@@ -47,36 +47,45 @@
 
 static bool MarkAliveBlocks(BasicBlock *BB,
 SmallPtrSetBasicBlock*, 16 Reachable) {
-  if (!Reachable.insert(BB)) return false;
-
-  // Do a quick scan of the basic block, turning any obviously unreachable
-  // instructions into LLVM unreachable insts.  The instruction combining pass
-  // canonnicalizes unreachable insts into stores to null or undef.
-  for (BasicBlock::iterator BBI = BB-begin(), E = BB-end(); BBI != E; ++BBI)
-if (StoreInst *SI = dyn_castStoreInst(BBI))
-  if (isaConstantPointerNull(SI-getOperand(1)) ||
-  isaUndefValue(SI-getOperand(1))) {
-// Loop over all of the successors, removing BB's entry from any PHI
-// nodes.
-for (succ_iterator I = succ_begin(BB), SE = succ_end(BB); I != SE; ++I)
-  (*I)-removePredecessor(BB);
-
-new UnreachableInst(SI);
-
-// All instructions after this are dead.
-for (; BBI != E; ) {
-  if (!BBI-use_empty())
-BBI-replaceAllUsesWith(UndefValue::get(BBI-getType()));
-  BB-getInstList().erase(BBI++);
+  
+  std::vectorBasicBlock* Worklist;
+  Worklist.push_back(BB);
+  bool Changed = false;
+  while (!Worklist.empty()) {
+BB = Worklist.back();
+Worklist.pop_back();
+
+if (!Reachable.insert(BB))
+  continue;
+
+// Do a quick scan of the basic block, turning any obviously unreachable
+// instructions into LLVM unreachable insts.  The instruction combining 
pass
+// canonnicalizes unreachable insts into stores to null or undef.
+for (BasicBlock::iterator BBI = BB-begin(), E = BB-end(); BBI != E; 
++BBI)
+  if (StoreInst *SI = dyn_castStoreInst(BBI))
+if (isaConstantPointerNull(SI-getOperand(1)) ||
+isaUndefValue(SI-getOperand(1))) {
+  // Loop over all of the successors, removing BB's entry from any PHI
+  // nodes.
+  for (succ_iterator I = succ_begin(BB), SE = succ_end(BB); I != 
SE;++I)
+(*I)-removePredecessor(BB);
+
+  new UnreachableInst(SI);
+
+  // All instructions after this are dead.
+  while (BBI != E) {
+if (!BBI-use_empty())
+  BBI-replaceAllUsesWith(UndefValue::get(BBI-getType()));
+BB-getInstList().erase(BBI++);
+  }
+  break;
 }
-break;
-  }
 
 
-  bool Changed = ConstantFoldTerminator(BB);
-  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
-Changed |= MarkAliveBlocks(*SI, Reachable);
-
+Changed |= ConstantFoldTerminator(BB);
+for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
+  Worklist.push_back(*SI);
+  }
   return Changed;
 }
 



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/lib/Transforms/Scalar/SimplifyCFG.cpp

2007-03-03 Thread Chris Lattner 


Changes in directory llvm/lib/Transforms/Scalar:

SimplifyCFG.cpp updated: 1.19 - 1.20
---
Log message:

switch MarkAliveBlocks over to using SmallPtrSet instead of std::set, speeding
up simplifycfg by 20%



---
Diffs of the changes:  (+5 -5)

 SimplifyCFG.cpp |   10 +-
 1 files changed, 5 insertions(+), 5 deletions(-)


Index: llvm/lib/Transforms/Scalar/SimplifyCFG.cpp
diff -u llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.19 
llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.20
--- llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.19 Mon Feb  5 17:32:05 2007
+++ llvm/lib/Transforms/Scalar/SimplifyCFG.cpp  Sat Mar  3 22:20:48 2007
@@ -27,8 +27,8 @@
 #include llvm/Support/CFG.h
 #include llvm/Support/Compiler.h
 #include llvm/Pass.h
+#include llvm/ADT/SmallPtrSet.h
 #include llvm/ADT/Statistic.h
-#include set
 using namespace llvm;
 
 STATISTIC(NumSimpl, Number of blocks simplified);
@@ -45,9 +45,9 @@
   return new CFGSimplifyPass();
 }
 
-static bool MarkAliveBlocks(BasicBlock *BB, std::setBasicBlock* Reachable) {
-  if (Reachable.count(BB)) return false;
-  Reachable.insert(BB);
+static bool MarkAliveBlocks(BasicBlock *BB,
+SmallPtrSetBasicBlock*, 16 Reachable) {
+  if (!Reachable.insert(BB)) return false;
 
   // Do a quick scan of the basic block, turning any obviously unreachable
   // instructions into LLVM unreachable insts.  The instruction combining pass
@@ -85,7 +85,7 @@
 // simplify the CFG.
 //
 bool CFGSimplifyPass::runOnFunction(Function F) {
-  std::setBasicBlock* Reachable;
+  SmallPtrSetBasicBlock*, 16 Reachable;
   bool Changed = MarkAliveBlocks(F.begin(), Reachable);
 
   // If there are unreachable blocks in the CFG...



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[llvm-commits] CVS: llvm/lib/Transforms/Scalar/SimplifyCFG.cpp

2006-12-08 Thread Reid Spencer 


Changes in directory llvm/lib/Transforms/Scalar:

SimplifyCFG.cpp updated: 1.16 - 1.17
---
Log message:

Incorporate any changes in the successor blocks into the result of
MarkAliveBlocks.


---
Diffs of the changes:  (+1 -1)

 SimplifyCFG.cpp |2 +-
 1 files changed, 1 insertion(+), 1 deletion(-)


Index: llvm/lib/Transforms/Scalar/SimplifyCFG.cpp
diff -u llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.16 
llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.17
--- llvm/lib/Transforms/Scalar/SimplifyCFG.cpp:1.16 Wed Dec  6 11:46:33 2006
+++ llvm/lib/Transforms/Scalar/SimplifyCFG.cpp  Fri Dec  8 15:52:01 2006
@@ -73,7 +73,7 @@
 
   bool Changed = ConstantFoldTerminator(BB);
   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
-MarkAliveBlocks(*SI, Reachable);
+Changed |= MarkAliveBlocks(*SI, Reachable);
 
   return Changed;
 }



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits