[LLVMdev] Register allocation in LLVM

[Fernando Magno Quintao Pereira]

Hello, all,

I want to implement the register allocation algorithm described in the
paper "Register Allocation via Coloring of Chordal Graphs, APLAS'05" in
LLVM. This is a graph coloring algorithm that can find an optimal coloring
of the interference graph in most of the cases. I've downloaded LLVM last
week, and started studying the code. Basically, I have to implement:

1) A new register allocation pass, similar to the class RA in
RegAllocLocal.cpp, for instance;

2) Replace the phi deconstruction algorithm, which I found in the class
PNE (PHIElimination.cpp); I would like to implement an algorithm that
uses XOR instructions instead of copy instructions to destroy phi
functions. It is the algorithm described in "Optimal register allocation
for SSA-form programs in polynomial time, Inf. Process. Lett, 98(4)", or
in "Register Allocation for Programs in SSA-Form, CC 2006". Basically,
this algorithm takes into consideration the results of the register
allocation phase, and adds one permutation of registers to each edge that
reaches the basic block where phi functions were destroyed. With three
xor, we can implement a swap without an extra register. For instance, if I
have (after RegAlloc), these PHI functions at the header of block B_d:
a(r1) <- (a1(r1), a2(r2))
b(r2) <- (b1(r2), b2(r1))

assuming that a2, b2 come from block B_s, at the end of block B_s I would
have to add the permutation: (r1, r2) <- perm (r2, r1)
which I can implement with six Xor instructions. Well, I would like to
get some comments about the best way to implement this in LLVM. Should I
change the function "copyRegToReg" in X86RegisterInfo.cpp? I am afraid
this function is used in other situations where copy instructions are
expected. On the other hand, if I create a separate function, and change
PHIElimination.cpp, I am afraid to lose retargability. Also, if
possible,  I would like to know if, besides the source code of the
register allocation classes (which is very well commented, and very
clean), if there is any online description of the register allocation
interface. For instance, concerning register allocation:

- To send registers to memory:
RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC);

- To bring registers from memory:
RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC);

- Given instruction i, virtual v, and machine reg m, allocate m to v at i:
MI->SetMachineOperandReg(i, physReg);

And PHI deconstruction:

- to remove instructions from Basic Blocks:
    MachineInstr *MPhi = MBB.remove(MBB.begin());
    delete MPhi;

- to create new instructions:
    BuildMI, http://llvm.org/docs/CodeGenerator.html

- to discover the origin block of each operand in the phi function:
    MachineBasicBlock &opBlock =
*MPhi->getOperand(i).getMachineBasicBlock();

Thank you in advance,

Fernando