A randomized heuristic approach to register allocation

Christoph W. Keßler, Wolfgang J. Paul, Thomas Rauber

Proc. of 3rd Int. Symposium on Progr. Lang. Implementation and Logic Programming (PLILP'91), Passau, Germany, Aug. 1991, Springer LNCS 528.


We present a randomized algorithm to generate contiguous evaluations for expression DAGs representing basic blocks of straight line code with nearly minimal register need. This heuristic may be used to reorder the statements in a basic block before applying a global register allocation scheme like Graph Coloring. Experiments have shown that the new heuristic produces results which are about 30% better on the average than without reordering.


This was my first conference paper, summarizing a part of my master thesis work done 1989/90 at Saarbrucken University. In contrast to the title, its main concern is about instruction scheduling, as it contributes a heuristic solution to the so-called MRIS problem (minimum register instruction sequencing). Later I developed several other solutions for this problem.


@string{PLILP = { Int.\ Symposium on Programming Language Implementation and Logic Programming}}
@string{PROC={Proc.\ }}

 author = {Christoph W.\ Ke{\ss}ler and Wolfgang J.\ Paul and Thomas Rauber},
 title = {A {R}andomized {H}euristic {A}pproach to {R}egister {A}llocation},
 booktitle = PROC # {3rd} # PLILP,
 location = {Passau (Germany)},
 publisher = {Springer LNCS vol.\ 528},
 year = {1991}, month = {Aug.},
 pages = {195--206}


Copyright notice: This section contains links to material covered by copyright; copyright may be held by the author and/or the publisher. You may browse them at your convenience (in the same spirit as you may read a journal or a proceedings article in a public library). Retrieving, copying, or distributing these files, however, may violate the copyright protection law. We recommend that the user obey international law in accessing this directory.
Note also that the material made accessible below may be based on a submitted version and thus differ in minor details from the published version.

Christoph Kessler