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.
Abstract:
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.
Comments:
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.
BibTeX:
@string{PLILP = { Int.\ Symposium on Programming Language Implementation and Logic Programming}}
@string{PROC={Proc.\ }}
@inproceedings{kpr91,
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}
}
Download:
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