[Caml-list] flow optimisation q

[Caml-list] flow optimisation q

[skaller]

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

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.

I get the feeling there should be a way to do it
a bit more efficiently :-)

A generalisation of this problem is: how to inline?
If a procedure is inlined on all uses, it can be 
discarded. However, one cannot just inline everything,
code gets too bloated. It would seem the length
of a candidate helps decide whether to inline it
or not. However the length isn't well specified,
since calls in *that* procedure might be inlined too.
For example:

proc a {b c d}
proc b {x y z}
proc c {x y z}
proc d {x y z}

If you inline into a first, you get

proc a {x y z x y z x y z}

which is too big to inline, but if you inline
a into another procedure first, you might then
inline b, c, and d, since each is small enough.
[Recursion introduces a similar problem]

Any ideas on how to think about a strategy for this?

[One idea is.. inline everything, and then remove
common code segments .. seems very general but
I don't see any easy way to recognize common
code segments]


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

Re: [Caml-list] flow optimisation q

[Jean-Baptiste Rouquier]

> 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

Re: [Caml-list] flow optimisation q

[Damien Doligez]

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

Re: [Caml-list] flow optimisation q

[skaller]

On Sun, 2004-01-04 at 05:02, Damien Doligez wrote:
> On Saturday, January 3, 2004, at 03:54 AM, skaller wrote:

> > Problem: remove all empty procedures
> > (and of course calls to them).
> 
> This is a garbage collection problem.  

Oh! Of course! Thanks, that's a beautiful insight.

> -- 
> John Max Skaller, mailto:skaller@tpg.com.au
> snail:25/85c Wigram Rd, Glebe, NSW 2037, Australia.
> voice:61-2-9660-0850. Checkout Felix: http://felix.sf.net
> 
> 
> 

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