Make use of "external" depth-first iterators to avoid revisiting nodes
multiple times. This reduces the time to construct post-dominance sets a LOT.
For example, optimizing perlbmk goes from taking 12.9894s to 1.4074s.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9091 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index f97fda8..2ff5fd3 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -51,12 +51,12 @@
do {
Changed = false;
- std::set<const BasicBlock*> Visited;
+ std::set<BasicBlock*> Visited;
DomSetType WorkingSet;
for (unsigned i = 0, e = Roots.size(); i != e; ++i)
- for (idf_iterator<BasicBlock*> It = idf_begin(Roots[i]),
- E = idf_end(Roots[i]); It != E; ++It) {
+ for (idf_ext_iterator<BasicBlock*> It = idf_ext_begin(Roots[i], Visited),
+ E = idf_ext_end(Roots[i], Visited); It != E; ++It) {
BasicBlock *BB = *It;
succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
if (SI != SE) { // Is there SOME successor?