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

Vladimir Makarov <>
Thu, 16 Jul 2015 16:34:08 -0400

          From comp.compilers

Related articles
Different approaches to register allocation (e.g. model transformer se (2015-07-06)
Re: Different approaches to register allocation (e.g. model transforme (Vladimir Makarov) (2015-07-16)
| List of all articles for this month |

From: Vladimir Makarov <>
Newsgroups: comp.compilers
Date: Thu, 16 Jul 2015 16:34:08 -0400
Organization: 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, wrote:
> I read this paper about register allocation: Register Allocation By
> Model Transformer Semantics <>
> 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).

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.