[llvm-bugs] [Bug 41240] New: [CompileTime] Speed up SSA renaming

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=41240

            Bug ID: 41240
           Summary: [CompileTime] Speed up SSA renaming
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: florian_hahn at apple.com
                CC: llvm-bugs at lists.llvm.org

Currently LLVM does not do SSA renaming as efficiently as it could do. In some
places, like Mem2Reg, we use custom renaming implementations and at other
places we use SSAUpdater, which has to traverse the CFG for each renamed
variable, to decide where to place PHIs.

For bulk updates, like in Mem2Reg, we could use merge sets as described in Das
and Ramakrishna's paper (Dibyendu Das and U. Ramakrishna. 2005. A practical and
fast iterative algorithm for φ-function computation using DJ graphs) to
efficiently find the points where PHI nodes are needed, rather than using IDF,
which potentially has to traverse the full CFG for each variable.

This can be combined with a renamer similar to the one in PredicateInfo, which
does renaming in O(log(Uses to rename)).

The related PRs will be sped up by this infrastructure.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190326/3ccdf0a3/attachment.html>