[LLVMbugs] [Bug 174] NEW: [taildup] Tail duplication does not update SSA form correctly

[bugzilla-daemon at zion.cs.uiuc.edu]

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

           Summary: [taildup] Tail duplication does not update SSA form
                    correctly
           Product: libraries
           Version: 1.0
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Scalar Optimizations
        AssignedTo: sabre at nondot.org
        ReportedBy: sabre at nondot.org


The LLVM tail duplication pass, which is critical for getting good performance,
is not updating SSA information correctly.  The problem is that it modifies the
CFG, and there is no _easy_ way for it to perform incremental updates of the
dominance frontier information (or any other dominfo).  It is currently
"working" in GCCAS by being run before any register promotion happens, thus
there are no live ranges spanning basic blocks.

This is a problem because we want to run tail duplication AFTER register
promotion, so that its cost metric (which decides when it is ok to duplicate
code) is more accurate.

Tail duplication is critical for loops because it is the pass that turns
"while"loops" into "do loops", by cloning the termination condition if it is
small enough.

There are several papers describing techniques for incremental updates of
dominator information, including ones that actually work on non-reducible
flow-graphs.  Being able to update dominfo after arbitrary transformations would
be incredibly valuable in LLVM (allowing me to finish the -cee pass for
example), but will take much more time to figure out and implement than we have
for 1.1.  :(

-Chris



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