You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
The text was updated successfully, but these errors were encountered:
// 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).
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.
Extended Description
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
The text was updated successfully, but these errors were encountered: