Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1569 > unrolled thread

Different approaches to register allocation (e.g. model transformer semantics)

Back to article view | Back to comp.compilers

Contents

  Different approaches to register allocation (e.g. model transformer semantics) orchid.hybrid@gmail.com - 2015-07-06 16:05 -0400
    Re: Different approaches to register allocation (e.g. model transformer semantics) Vladimir Makarov <vmakarov@redhat.com> - 2015-07-16 16:34 -0400

#1569 — Different approaches to register allocation (e.g. model transformer semantics)

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.

Has anyone implemented the algorithm? or are there more papers about
approaches like this I could read? I couldn't find any code and some
details are missing.

[toc] | [next] | [standalone]

#1573

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).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web