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. Brought to you by Super Global Mega Corp .com