llvm dev - Dec 2011 - [LLVMdev] Greedy Register Allocation in LLVM 3.0

Hi Jakob,

  After reading your blog article, I have some questions. :-) In [1], it says: 

"It was an important design goal to make the algorithm as flexible as
possible,
and to avoid introducing arbitrary constraints. It is possible to change machine
code and live ranges at any time. Simply evict the relevant live ranges, make
the change, and put them back on the queue."

Q1.
  The "machine code" mentioned above means LLVM MI (MachineInstr) or? 

Q2.
  In [2], Evan illustrates current LLVM MI flow below.

1. DAG to MI lowering (and pre-RA schedule)
2. MI optimizations (LICM, CSE, etc.)
3. Register allocation super pass
   3a. De-ssa (2-address, phi slim)
   3b. Coalescing
   3c. Actual register allocation
4. Post-RA optimizations
5. PEI
6. Post-RA scheduling
 
  Does "change machine code and live ranges at any time" means we want
to change
the machine code at some points in the above flow? If so, could you point it
out?
If you can give me a small example, that would be great!

Q3.
  In the section "Lessons learned from linear scan", you say
"advanced register
allocation algorithms often need to build expensive data structures, or they
make
assumptions about live ranges being invariant".

  Does that imply the graph coloring algorithm? If an algorithm A requires the
live ranges being invariant, does it mean when we assign a register to a
variable
then it's done and cannot be changed latter on?


  Thanks!


Regards,
chenwj

[1] http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
[2] http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-December/045846.html

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

On Dec 9, 2011, at 12:10 AM, 陳韋任 <chenwj at iis.sinica.edu.tw>
wrote:
>  After reading your blog article, I have some questions. :-) In [1], it
says:
> 
> "It was an important design goal to make the algorithm as flexible as
possible,
> and to avoid introducing arbitrary constraints. It is possible to change
machine
> code and live ranges at any time. Simply evict the relevant live ranges,
make
> the change, and put them back on the queue."
> 
> Q1.
>  The "machine code" mentioned above means LLVM MI (MachineInstr)
or?
Yes.
> Q2.
>  In [2], Evan illustrates current LLVM MI flow below.
> 
> 1. DAG to MI lowering (and pre-RA schedule)
> 2. MI optimizations (LICM, CSE, etc.)
> 3. Register allocation super pass
>   3a. De-ssa (2-address, phi slim)
>   3b. Coalescing
>   3c. Actual register allocation
> 4. Post-RA optimizations
> 5. PEI
> 6. Post-RA scheduling
> 
>  Does "change machine code and live ranges at any time" means we
want to change
> the machine code at some points in the above flow? If so, could you point
it out?
> If you can give me a small example, that would be great!
The blog post is only about "3c. Actual register allocation". The
other passes naturally change the machine code.

In the classical formulations of register allocation like linear scan and graph
coloring, it is assumed that the machine instructions stay constant while only
the register assignments are changed. The register allocator may insert spill
code and copies, but the original instructions are never touched.

I want to allow the register allocator to change the original instructions as
well. For example, the scheduler likes to hoist loads:

  xmm3 = load(gpr2)
  xmm2 = addps xmm2, xmm1

The code requires three xmm registers, but if you sink the load, two is enough:

  xmm2 = addps xmm2, xmm1
  xmm1 = load(gpr2)
> Q3.
>  In the section "Lessons learned from linear scan", you say
"advanced register
> allocation algorithms often need to build expensive data structures, or
they make
> assumptions about live ranges being invariant".
> 
>  Does that imply the graph coloring algorithm? If an algorithm A requires
the
> live ranges being invariant, does it mean when we assign a register to a
variable
> then it's done and cannot be changed latter on?
No, graph coloring algorithms can change previous assignments.

The invariant live ranges problem is the same as above. If you move instructions
around, the live ranges change, and the interference graph is invalidated.

/jakob