Weekly Edition
Return to the Development page
| |||||||||||||
Greedy register allocation in LLVM 3.0
Readers interested in the grungy details of compilers may enjoy this
LLVM project blog entry on their new register allocation algorithm.
"The new basic allocator does away with linear scan's dependence on
visiting live ranges in linear order. Instead, it uses a priority queue to
visit live range in order of decreasing spill weight. The active list used
for interference checks is replaced with a set of live interval
unions. Implemented as a B+ tree per physical register, they are an
efficient way of checking for interference with already assigned live
ranges. Unlike the active list, live interval unions work with any priority
queue order."
(Log in to post comments)
Greedy register allocation in LLVM 3.0 Posted Sep 20, 2011 15:18 UTC (Tue) by zlynx (subscriber, #2285) [Link]
No one commented on this?
I just want to say that I found the article really interesting and I'd like to thank LWN for posting it.
Greedy register allocation in LLVM 3.0 Posted Sep 21, 2011 20:04 UTC (Wed) by alvieboy (subscriber, #51617) [Link]
Well, most of my work relates to a stack-based CPU, so register allocation does not apply (at least not directly), but I do agree, it's a nice reading.
It takes a lot of work to get a compiler to generate "optimal" code for your processor - most people do not realise this. They also do not realise that, for improved efficiency, one must not only take care of branching, but avoid (at an higher level) cache misses, refills, and write-backs. We are moving now into the massive-multi-core, and still our memories have to be shared among all those cores - since memories have high r/w latencies, what we want is to avoid touching memory at all, due to contention.
Register optimizations might show up in microbenchmarks, but I doubt they will be that significant on the real world.
I always recall an old AMD486 system I had, who could operate at 80MHz and 66MHz. It was faster at 66, because the memory bus could actually run at higher speeds.
Greedy register allocation in LLVM 3.0 Posted Sep 22, 2011 2:24 UTC (Thu) by vonbrand (subscriber, #4458) [Link] I'd disagree. Look at the code some simplistic compiler like tcc generates; or what a compiler with not too much more than rather sophisticated code selection, like lcc, does; and compare with more mainstream compilers like GCC of LLVM.
Greedy register allocation in LLVM 3.0 Posted Sep 23, 2011 4:30 UTC (Fri) by wahern (subscriber, #37304) [Link]
Well written code will use lots of local, temporary variables. The more efficient the allocator the fewer and smaller the spills to the stack. So, yeah, register allocation is important _because_ of finite memory bandwidth and latency.
Greedy register allocation in LLVM 3.0 Posted Sep 23, 2011 10:31 UTC (Fri) by etienne (subscriber, #25256) [Link]
Register allocation is also very complex if you target Intel/AMD processors, with their 8/16/32 or 8/32/64 registers size: if the lower 8 bits (AL) are taken you can still use the upper 8 bits (AH), but then using the 16/32 bits register (AX/EAX) makes register allocation very complex.
Most code use boolean variables, and using 32/64 bits to store a boolean is very inefficient on Intel/AMD processor. I wonder if LLVM is able to coalesce multiple boolean into a single register and use bits-and/or/test to manage them, I didn't see GCC doing it nicely (and it is probably very complex to implement).
Greedy register allocation in LLVM 3.0 Posted Sep 23, 2011 18:36 UTC (Fri) by daglwn (subscriber, #65432) [Link]
> Register optimizations might show up in microbenchmarks, but I doubt they
> will be that significant on the real world.
I strongly disagree. I have done a lot of work in register allocation and I have seen performance swings of +/- 10% simply by changing a heuristic that picks which register to assign next. I have seen similar swings when mucking with other heuristics such as picking a register to spill.
Register allocation is extremely important.
Greedy register allocation in LLVM 3.0 Posted Sep 22, 2011 14:12 UTC (Thu) by piggy (subscriber, #18693) [Link]
I would like to second this. The article was interesting reading.
|
|||||||||||||