Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!think.com!mintaka!spdcc!iecc!compilers-sender From: TimMcN@Think.COM (Tim McNerney) Newsgroups: comp.compilers Subject: testing register allocation Keywords: optimize, testing, design Message-ID: <9101142017.AA20207@mjolnir.think.com> Date: 14 Jan 91 20:17:27 GMT Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Tim McNerney Organization: Compilers Central Lines: 40 Approved: compilers@iecc.cambridge.ma.us In-Reply-To: Mark Bromley's message of Mon, 14 Jan 91 14:09:08 EST <9101141909.AA11318@luna.think.com> >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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.