[LLVMbugs] [Bug 13215] New: SSAUpdater can be very slow.

[bugzilla-daemon at llvm.org]

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

             Bug #: 13215
           Summary: SSAUpdater can be very slow.
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: Windows NT
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Core LLVM classes
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: nadav.rotem at intel.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


Running the LCSSA pass on a complex program with 5000 instruction function can
take 10 seconds (in debug) on my machine. 

To reproduce:

./bin/llvm-stress --size=5000 | ./bin/opt -mem2reg --lcssa -o /dev/null
--time-passes


LCSSA uses the SSAUpdater for rewriting the loop users. For each value that
needs to be rewritten, SSAUpdater calculates the reverse reachable block set
(in BuildBlockList). The block list needs to stop when reaching the roots of
the value that needs to be re-written, but it often leaks and scans the entire
function. 

Notice that we scan the entire function for each value that we need to rewrite,
even if there are multiple values in the same basic blocks. I am not sure if
this bug-report is a real life problem, but if we choose to address it, 
I suggest the following: Add a new analysis pass which computes the reverse
reachable block set for each basic block. It may be less efficient because it
will not stop at the roots of the value, but it will eliminate the need to
rebuild the block list for each value. We can also find the partial-cfg
dominators on this set of blocks.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.