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

bugzilla-daemon at zion.cs.uiuc.edu bugzilla-daemon at zion.cs.uiuc.edu
Thu Dec 11 09:37:23 PST 2003


           Summary: [taildup] Tail duplication does not update SSA form
           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.  :(


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

More information about the llvm-bugs mailing list