search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.63k stars 11.83k forks source link

[CompileTime] Speed up SSA renaming #40585

Open fhahn opened 5 years ago

fhahn commented 5 years ago
Bugzilla Link 41240
Version trunk
OS All
CC @fhahn,@yuanfang-chen

Extended Description

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.

fhahn commented 5 years ago

Example where ~20% of the -O2 compile time is spent in SSA renaming in JT

fhahn commented 5 years ago

If we can incrementally update the merge sets based on DT updates, this should fix PR 16756. Daniel Berlin indicated something like that a while ago https://reviews.llvm.org/D44282#1032242

fhahn commented 5 years ago

And there is already a patch to add a merge set implementation: https://reviews.llvm.org/D57123

fhahn commented 5 years ago

Other places where this potentially could help is LCSSA & MemorySSA, at least to limit worst case compile time

fhahn commented 5 years ago

assigned to @fhahn