[Camllist] flow optimisation q

skaller
 JeanBaptiste Rouquier
 Damien Doligez
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20040102 (21:48) 
From:  JeanBaptiste Rouquier <jeanbaptiste.rouquier@e...> 
Subject:  Re: [Camllist] flow optimisation q 
> 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). JeanBaptiste Rouquier.  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners