Related articles |
---|
Different approaches to register allocation (e.g. model transformer se orchid.hybrid@gmail.com (2015-07-06) |
Re: Different approaches to register allocation (e.g. model transforme vmakarov@redhat.com (Vladimir Makarov) (2015-07-16) |
From: | Vladimir Makarov <vmakarov@redhat.com> |
Newsgroups: | comp.compilers |
Date: | Thu, 16 Jul 2015 16:34:08 -0400 |
Organization: | Aioe.org NNTP Server |
References: | 15-07-001 |
Keywords: | optimize, registers |
Posted-Date: | 17 Jul 2015 21:47:43 EDT |
On 07/06/2015 04:05 PM, orchid.hybrid@gmail.com wrote:
> I read this paper about register allocation: Register Allocation By
> Model Transformer Semantics <http://arxiv.org/abs/1202.5539>
>
> It was eye opening to me because it explained that graph coloring is not the whole story.
>
I found this approach is very analogous to the old bin packing
algorithm, the difference only is in internal RA data representation
(a model) and rules for its update (model transformer semantics) but
that is because the author is probably from functional programming
world. The two pass algorithm itself (based on called there static
cache replacement) is mostly bin packing or Traub's second chance
bin-packing if you consider splitting.
Bin packing RA algorithm is pretty good for programs with regular
and simple CFGs with long BBs (Bob Morgan told me long ago an
interesting story about inventing it. According to him it was
originally implemented as a temporary simple solution for RA by DEC
engineers and after that they tried to implement a better and more
complicated RAs but the first one was still the best). It is pretty
fast too.
Still graph coloring based on Chatin (Kempe's coloring
criterium)-Briggs (optimistic coloring) approach is doing good
practically in most situations but especially good for complicated
CFG, e.g. regex interpreter in SPEC2K perlbmk benchmark benefits a lot
from using graph coloring in comparison with priority-based
coloring or liner scan. It is also the best in situations when code
execution frequencies are unknown, inaccurate, or changing (linear
scan or extended liner scan can sometimes generate a better code for
known frequency but as when we change the frequencies, graph coloring
produces a better code. At least that is what I found experimenting
with an extended linear scan implementation in GCC environment).
Return to the
comp.compilers page.
Search the
comp.compilers archives again.