johnson@cs.uiuc.edu (Ralph Johnson) (01/12/91)
We found it hard to debug our register allocation algorithm
because it was not very repeatable (it used hash tables and
the slightest change in execution would change the order that
registers were allocated) and because it is hard to eyeball
a program and see whether register allocation is correct.
We solved this problem by writing a program that checks the
result of register allocation and tells us whether it is
correct or not. After a couple of design iterations, we
have a linear time algorithm that is very fast. We are
very happy with the algorithm, and plan to keep it in the
compiler. It has detected all the recent register allocator
bugs, saving us a great deal of time and frustration.
Question: is this a common technique? Has anybody written
a paper about the linear time algorithm for checking the
output of register allocation? If not, I'll write a short
paper on the subject. I have not seen anything on the subject,
but maybe I have just missed it.
Ralph Johnson -- University of Illinois at Urbana-Champaign
johnson@cs.uiuc.edu
[I haven't seen anything on it. Even if you're not sure, I'd send in a note
to SIGPLAN so the next person who comes across it can't patent it. -John]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.TimMcN@Think.COM (Tim McNerney) (01/15/91)
>We found it hard to debug our register allocation algorithm because it was >not very repeatable (it used hash tables and the slightest change in >execution would change the order that registers were allocated) and because >it is hard to eyeball a program and see whether register allocation is >correct. We solved this problem by writing a program that checks the result >of register allocation and tells us whether it is correct or not. After a >couple of design iterations, we have a linear time algorithm that is very >fast. We are very happy with the algorithm, and plan to keep it in the >compiler. It has detected all the recent register allocator bugs, saving us >a great deal of time and frustration. >Question: is this a common technique? >Ralph Johnson -- University of Illinois at Urbana-Champaign >johnson@cs.uiuc.edu I have implemented a program that, for code emitted by our Fortran compiler and targeted for the processing elements of the Thinking Machines CM-2 SIMD parallel processor, proves the register allocator and instruction scheduler phases correct for a given piece of code. I have also written a paper entitled, "Verifying the Correctness of Compiler Transformations on Basic Blocks using Abstract Interpretation," that I submitted to the upcoming SIGPLAN Conference on Partial Evaluation and Semantics Based Program Manipulation. My techniques have proven extremely useful to our compiler project, but while they are mathematically rigorous, they are not completely general. I suspect that you have taken a different approach that is specific to testing register allocators but is applicable to a wider domain of programs. I am interested in hearing more, and would encourage you to write up your findings. Is your code in the public domain? I would include a copy of my paper here in machine-readable form, but it is on a Macintosh and would take some time to transfer and reformat. I will be glad to mail copies of my paper upon request. --Tim McNerney -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
eggert@twinsun.com (Paul Eggert) (01/16/91)
Hanan Samet implemented a register allocation tester that interfaced to two
Lisp-to-PDP-10 compilers as part of his PhD research way back in the mid
1970s. His tester was more general (and less efficient) than just a register
allocation tester: it tested every part of code generation and optimization,
including things like common subexpression elimination, changing calling
sequence conventions, replacement of recursion by iteration, and even many
hand-optimizations. Here's a reference:
Hanan Samet, Proving the Correctness of Heuristically Optimized Code,
CACM 21, 7 (July 1978), 570-582.
[From eggert@twinsun.com (Paul Eggert)]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.