[LLVMbugs] [Bug 1409] NEW: Should merge etforest into domtree

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=1409

           Summary: Should merge etforest into domtree
           Product: libraries
           Version: trunk
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Global Analyses
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: sabre at nondot.org


ETForest and Domtree both build a tree structure that reflects the dominator tree, ETForest just has a 
cute numbering scheme which makes certain queries really fast.

Merging the two would be very good, both by reducing the number of distinct dominator analyses 
running around, but also by reducing memory usage (one tree instead of two) and it would make 
domtree the standard basic dominator analysis.

This would also fix specific other problems.  For example, domfrontier can be *very* slow right now in 
some cases because it calls DomTreeNode::properlyDominates.  This method is O(n) in the height of 
the domtree, which is extremely bad for compile time in some cases (e.g. 5186590).  If it had etforest 
available, it would be constant time.

-Chris



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