From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA17009; Sat, 3 Jan 2004 19:01:56 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA17602 for ; Sat, 3 Jan 2004 19:01:55 +0100 (MET) Received: from mallaury.noc.nerim.net (smtp-106-saturday.noc.nerim.net [62.4.17.106]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id i03I1sH22063 for ; Sat, 3 Jan 2004 19:01:54 +0100 (MET) Received: from inria.fr (planar.net0.nerim.net [213.41.168.102]) by mallaury.noc.nerim.net (Postfix) with ESMTP id 6D97662D43 for ; Sat, 3 Jan 2004 19:01:52 +0100 (CET) Date: Sat, 3 Jan 2004 19:02:03 +0100 Subject: Re: [Caml-list] flow optimisation q Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v553) From: Damien Doligez To: caml-list Content-Transfer-Encoding: 7bit In-Reply-To: <1072936720.4626.18.camel@pelican> Message-Id: X-Mailer: Apple Mail (2.553) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 damien:01 damien:01 recursion:01 pointers:01 ocaml:01 garbage:01 doligez:01 doligez:01 harder:02 wrote:03 algorithm:03 algorithm:03 recursive:03 inline:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Saturday, January 3, 2004, at 03:54 AM, skaller wrote: > Nothing to do with ocaml, but some people here > might know.. Suppose there is a set of > primitive procedures pr1 pr2 and a procedure constructor: > > proc = proc list > > which defines a new procedure to be a list of calls > to other procedures, with mutual recursion allowed. > > A special procedure is the empty > procedure whose call list is empty. > > Problem: remove all empty procedures > (and of course calls to them). This is a garbage collection problem. I assume that you also want to remove recursive cycles of procedures that never call any primitive. Your roots are the primitive procedures, and your pointers are the is-called-by relation. You can use a two-pass mark-and-sweep algorithm, or a one-pass copying algorithm. You'll need to invert the graph first, making the called procedures point to its callers, and then it's straightforward. > A generalisation of this problem is: how to inline? That's a much harder problem, of course. -- Damien ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners