testing register allocation

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

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