testing register allocation

Ralph Johnson <johnson@cs.uiuc.edu>
Sat, 12 Jan 91 06:35:23 -0600

          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: Ralph Johnson <johnson@cs.uiuc.edu>
Keywords: code, debug, testing
Organization: Compilers Central
Date: Sat, 12 Jan 91 06:35:23 -0600

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

Post a followup to this message

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