[llvm-dev] Register Allocation Graph Coloring algorithm and Others

[Leslie Zhai via llvm-dev]

Hi Dr. Rhydian,

I am trying to build Dimacs Graph with VirtReg (pseudo) I could counting 
G.Nodes and Edges 
https://github.com/xiangzhai/llvm/blob/avr/lib/CodeGen/RegAllocGraphColoring.cpp#L359

It just translated gCol/HybridEA's inputDimacsGraph to LLVM pseudo 
registers' traverse, but I am not clear what is Node1 or Node2,  is it 
refer to the Index of vertices?

In the gCol/HybridEA/graph.txt, for example:

e 2 1

Is it means there is an edge between Node2 and Node1? if so, it might be 
equivalent to LLVM's VirtReg1->overlaps(*VirtReg2)

And follow your mind,
Node1 = 2, Node2 =1;
if (Node1 < 1 || Node1 > G.Nodes || Node2 < 1 || Node2 > G.Nodes) errs() 
<< "Node is out of range\n";
Node1--, Node2--; // Why minus?
if (G[Node1][Node2] == 0) G.Edges++;
G[Node1][Node2] = 1, G[Node2][Node1] = 1;

Please give me some hint, thanks a lot!

在 2017年12月15日 11:18, Leslie Zhai 写道:
> Hi GCC and LLVM developers,
>
> I am learning Register Allocation algorithms and I am clear that:
>
> * Unlimited VirtReg (pseudo) -> limited or fixed or alias[1] PhysReg 
> (hard)
>
> * Memory (20 - 100 cycles) is expensive than Register (1 cycle), but 
> it has to spill code when PhysReg is unavailable
>
> * Folding spill code into instructions, handling register coallescing, 
> splitting live ranges, doing rematerialization, doing shrink wrapping 
> are harder than RegAlloc
>
> * LRA and IRA is default Passes in RA for GCC:
>
> $ /opt/gcc-git/bin/gcc hello.c
> DEBUG: ../../gcc/lra.c, lra_init_once, line 2441
> DEBUG: ../../gcc/ira-build.c, ira_build, line 3409
>
> * Greedy is default Pass for LLVM
>
> But I have some questions, please give me some hint, thanks a lot!
>
> * IRA is regional register allocator performing graph coloring on a 
> top-down traversal of nested regions, is it Global? compares with 
> Local LRA
>
> * The papers by Briggs and Chaiten contradict[2] themselves when 
> examine the text of the paper vs. the pseudocode provided?
>
> * Why  interference graph is expensive to build[3]?
>
> And I am practicing[4] to use HEA, developed by Dr. Rhydian Lewis, for 
> LLVM firstly.
>
>
> [1] https://reviews.llvm.org/D39712
>
> [2] http://lists.llvm.org/pipermail/llvm-dev/2008-March/012940.html
>
> [3] https://github.com/joaotavio/llvm-register-allocator
>
> [4] https://github.com/xiangzhai/llvm/tree/avr/include/llvm/CodeGen/GCol
>

-- 
Regards,
Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/