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, SmallPtrSet<BasicBlock*, 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_cast<StoreInst>(BBI)) - if (isa<ConstantPointerNull>(SI->getOperand(1)) || - isa<UndefValue>(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::vector<BasicBlock*> 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_cast<StoreInst>(BBI)) + if (isa<ConstantPointerNull>(SI->getOperand(1)) || + isa<UndefValue>(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