Path: utzoo!attcan!uunet!world!iecc!compilers-sender From: johnson@cs.uiuc.edu (Ralph Johnson) Newsgroups: comp.compilers Subject: testing register allocation Keywords: code, debug, testing Message-ID: <9101121235.AA17441@m.cs.uiuc.edu> Date: 12 Jan 91 12:35:23 GMT Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Ralph Johnson Organization: Compilers Central Lines: 26 Approved: compilers@iecc.cambridge.ma.us 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.