[LLVMdev] Regalloc Refactoring

Fernando Magno Quintao Pereira fernando at CS.UCLA.EDU
Fri Apr 13 22:09:17 PDT 2007

> Can you briefly explain what it simplifies?

Let me try to explain my algorithm first, and then you can try to compare

The objective is to convert the SSA-form program into a conventional
SSA-form program (CSSA). In this flavor of SSA, the variables related by
phi-functions do not interfere, and can be assigned the same register, as
in Budimlic's case, or the same memory address if spilled (that is what I
am doing). One way to convert a program in CSSA-form is to split the live
range of each virtual that is part of a phi function. You can do this
using the algorithm below:

PhiLifting
For each instruction
(a_i := phi(a_{i1}:B_1, a_{i2}:B_2, ..., a_{im}:B_m))
Create new virtual v_i
Add copy instruction I =  ( a_i := v_i ) at the end of block B_j
Replace a_i by v_i in phi
For each virtual  a_{ij} in phi
Create new virtual v_{ij}
Add copy instruction I =  (v_{ij} := a_{ij})
at the end of block B_j
Replace a_{ij} by v_{ij} in \phi

This algorithm will add one copy for each virtual that is a parameter of a
phi-function, and one copy for each virtual that is the result of a
phi-function. After you run it, given a phi function (a := phi(b, c)), you
can assign the same register to a, b and c, because their live ranges
don't overlap. But this is too convervative, because now the live ranges
are very small. In order to increase this, you can merge classes of
phi-related virtuals using the algorithm below:

PhiMemCoalesce
(S_I = { I_1, I_2, ..., I_q } // instructions created by PhiLifting.
S_Q = { Q_1, Q_2, ..., Q_r }) /// Classes of phi-related virtuals.
For each instruction  I = ( v_{ij} := a_{ij} ) in S_I
S_I := S_I - { I }
Let Q_v be the equivalence class of v_{ij}
Let Q_a be the equivalence class of a_{ij}
if Q_v intersection Q_v = {} // they don't overlap
S_Q := S_Q - { Q_v }
S_Q := S_Q - { Q_a }
S_Q := S_Q + { Q_a union Q_v }

Virtuals that are in the same phi function are said to be in the same
equivalence class of phi-related virtuals. For instance, for a := phi(b,
c), the equivalence class is Q = {a, b, c}.

To make it efficient, I do not build the interference graph of the source
program in order to perform operations such as 'Q_i intersection Q_j'.
Instead, I rely on the interval representation of live ranges commonly
used in versions of the linear scan algorithm. Each virtual is represented
as a collection of ordered intervals on the linearized control flow graph.
Thus, a set Q of virtuals is a set of ordered integer intervals. In this
way, the intersection of two phi-equivalence classes Q_i and Q_j can be
found in time linear on the number of disjoint intervals in both sets.
Because a phi-equivalence class can have O(V) disjoint intervals, the
final complexity of algorithm PhiMemCoalesce is O(|L_i| * V). In my
experiments, the interval based implementation of PhiMemCoalesce accounts
for less than 1% of the total compilation time, whereas the interference
graph based algorithm takes more than 30% of the compilation time!

Fernando