testing register allocation

Tim McNerney <TimMcN@Think.COM>
Mon, 14 Jan 91 15:17:27 EST

          From comp.compilers

Related articles
testing register allocation johnson@cs.uiuc.edu (Ralph Johnson) (1991-01-12)
testing register allocation TimMcN@Think.COM (Tim McNerney) (1991-01-14)
testing register allocation eggert@twinsun.com (1991-01-15)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Tim McNerney <TimMcN@Think.COM>
In-Reply-To: Mark Bromley's message of Mon, 14 Jan 91 14:09:08 EST <9101141909.AA11318@luna.think.com>
Organization: Compilers Central
Date: Mon, 14 Jan 91 15:17:27 EST
Keywords: optimize, testing, design

>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

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

Post a followup to this message

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