Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] flow optimisation q
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-01-03 (18:01)
From: Damien Doligez <damien.doligez@i...>
Subject: Re: [Caml-list] flow optimisation q
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

> A generalisation of this problem is: how to inline?

That's a much harder problem, of course.

-- Damien

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: