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

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