Re: [Caml-list] flow optimisation q

["Jean-Baptiste Rouquier" <jean-baptiste.rouquier@ens-lyon.org>]

> 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 graph problem : draw a vertice for each proc and a vertice from a
to b when b calls a (so a -> b mean "a is called by b").
First suppose that there are no cycle. You just have to start from primitive
procs, mark recursively all their callers, and delete all non marked
vertices.
O(n).

If there are cycle and if you want to keep a structure like
a calls b
b calls a
where neither a nor b is a primitive proc, you can calculate strongly
connected components of your graph. Then draw the graph of this strongly
connected components (vertices are the strongly connected components, and
there is an edge A -> B iff there exists a in A and b in B such that there
is an edge a -> b in the first graph). Finnally apply the first algorithm
using components with two or more procs as primitives procs, plus the
initial primitives procs.


> My current algorithm is functional:
> make a new set of procedures which
> (a) excludes empty procedures
> (b) has calls to empty procedures elided
>
> To make this solve the problem requires
> repeated application until there are no
> empty procedures left.
 Seems O(n^2).

Jean-Baptiste Rouquier.


-------------------
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