[LLVMdev] Regalloc Refactoring

[Fernando Magno Quintao Pereira]

> Can you briefly explain what it simplifies?

Let me try to explain my algorithm first, and then you can try to compare 
with the others already described.

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