[LLVMbugs] [Bug 681] NEW: [postdom] Post dominator set construction algorithm abuses memory

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.cs.uiuc.edu/bugs/show_bug.cgi?id=681

           Summary: [postdom] Post dominator set construction algorithm
                    abuses memory
           Product: libraries
           Version: 1.0
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Global Analyses
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: sabre at nondot.org


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



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.