Re: [Caml-list] flow optimisation q

[Damien Doligez <damien.doligez@inria.fr>]

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