The code in lib/Analysis/PostDominators.cpp uses a really braindead
implementation of the dominator set construction algorithm.  On some testcases
(e.g. the bc file here
http://lists.cs.uiuc.edu/pipermail/llvmdev/2005-December/005122.html with 'opt
-break-crit-edges -adce) with some mallocs (e.g. darwin or freebsd), it can take
hundreds of megs of memory.

The solution is to use the standard Lengauer & Tarjan algorithm for dominator
set construction:

   A Fast Algorithm for Finding Dominators in a Flowgraph
   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.

This is currently used by the forward dom set implementation, but I never got
around to updating the post-dom implementation.  It would be nice if someone
would pick this up. :)

-Chris

note that these loops in the postdom impl:

          // Loop until we get to a successor that has had it's dom set filled
          // in at least once.  We are guaranteed to have this because we are
          // traversing the graph in DFO and have handled start nodes specially.
          //
          while (Doms[*SI].size() == 0) ++SI;
          WorkingSet = Doms[*SI];

          for (++SI; SI != SE; ++SI) { // Intersect all of the successor sets
            DomSetType &SuccSet = Doms[*SI];
            if (SuccSet.size())
              set_intersect(WorkingSet, SuccSet);
          }
 

are causing most of the problem.  They are using std::set's to do iterative
dataflow, which is braindead (they should at least be bitvectors).

-Chris

Implemented postdom based on Lengauer and Tarjan implementation in forward dom.
 Speeds up this 
testcase from 32.8 to 0.8 seconds on my G5, drops memory requirement from 496MB
to 26MB.  Patch out 
to sabre for review.

Fixed.

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060306/032533.html
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060306/032534.html