Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!decwrl!world!iecc!compilers-sender
From: kanamori@Neon.Stanford.EDU
Newsgroups: comp.compilers
Subject: Need reference to correctness proof of "worklist" algorithm
Keywords: theory, question, analysis
Message-ID: <1991Feb27.020950.21916@iecc.cambridge.ma.us>
Date: 27 Feb 91 02:09:50 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: kanamori@Neon.Stanford.EDU
Organization: Computer Science Department, Stanford University
Lines: 16
Approved: compilers@iecc.cambridge.ma.us
Can anybody give me a reference to a publication which gives a correctness
proof for the "worklist" algorithm for solving dataflow analysis problems?
That is, instead of recomputing the equation at every node on each pass like
it says to do in the Dragon book, the algorithm maintains a worklist of
nodes whose information has changed since the last time its equation
was applied.
I already have a proof worked out but since somebody has probably done the
proof already, I'd rather put a reference to that somebody in the paper
I'm writing rather than making my paper even longer by including the proof.
Answer by email only, please. Thanks in advance.
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.