Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[postdom] Post dominator set construction algorithm abuses memory #1053

Closed
lattner opened this issue Dec 27, 2005 · 3 comments
Closed

[postdom] Post dominator set construction algorithm abuses memory #1053

lattner opened this issue Dec 27, 2005 · 3 comments

Comments

@lattner
Copy link
Collaborator

@lattner lattner commented Dec 27, 2005

Bugzilla Link 681
Resolution FIXED
Resolved on Feb 22, 2010 12:46
Version 1.0
OS All

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

@lattner
Copy link
Collaborator Author

@lattner lattner commented Dec 27, 2005

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

@llvmbot
Copy link
Collaborator

@llvmbot llvmbot commented Mar 11, 2006

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.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 3, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants