Home My Page Projects Code Snippets Project Openings SML/NJ
 Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

# SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/ir-moved/djgraph.sml
 [smlnj] / sml / trunk / src / MLRISC / ir-moved / djgraph.sml

# View of /sml/trunk/src/MLRISC/ir-moved/djgraph.sml

Revision 545 - (download) (annotate)
Thu Feb 24 13:56:44 2000 UTC (19 years, 11 months ago) by george
File size: 4250 byte(s)
```  Changes to MLTREE
```
```(*
* The algorithm for dominance frontier and iterated dominance
* frontier is due to Sreedhar, Gao and Lee.   The algorithm as cited
* uses the DJgraph.  In order not to bother with constructing and
* maintaining the DJgraph, we'll just use a combination of the dominator tree
* and the original cfg.  This alteration does not change the linear
* complexity of the algorithm.  I'm also using a simple time stamp trick to
* avoid the data structure initialization step; this should make the
* algorithm sublinear in N in practice, where N is the number of nodes
* in the CFG.
*
* --Allen
*)

functor DJGraph (Dom : DOMINATOR_TREE) : DJ_GRAPH =
struct

structure G       = Graph
structure Dom     = Dom
structure A       = Array

type ('n,'e,'g) dj_graph = ('n,'e,'g) Dom.dominator_tree

fun dj_graph (D as G.GRAPH dom) =
let val G.GRAPH cfg = Dom.cfg D
val L           = Dom.max_levels D
val N           = #capacity dom ()
val levels      = Dom.levelsMap D
val in_DF       = A.array(N,0)  (* has appeared in the DF set? *)
val stamp       = ref 0
fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end

fun unmarked(marked,i,stamp : int) =
let val s = A.sub(marked,i)
in  if s = stamp then false else (A.update(marked,i,stamp); true)
end

(*
* Compute the dominance frontiers of a node
* Dominance frontier of x:
*   The set of all nodes y such that x dominates a predecessor
*   of y but x doesn't strictly dominates y.
*)
fun DF x =
let val stamp = new_stamp()
val level_x = A.sub(levels,x)
fun walk(z, S) =
let fun scan((_,y,_)::es,S) =
if A.sub(levels,y) <= level_x andalso
unmarked(in_DF,y,stamp) then scan(es,y::S)
else scan(es,S)
| scan([],S) = S
val S = scan(#out_edges cfg z,S)
fun walkList([],S) = S
| walkList((_,z,_)::es,S) = walkList(es,walk(z,S))
in  walkList(#out_edges dom z,S)
end
in  walk(x,[])
end

val in_alpha  = A.array(N,0)  (* has appeared in N_alpha? *)
val visited   = A.array(N,0)  (* has it been visited *)
val piggybank = A.array(L,[]) (* nodes in the piggy bank *)

(*
* This algorithm is described in POPL 95
*)
fun IDFs xs =
let val stamp = new_stamp()
fun init([],l) = l
| init(x::xs,l) =
let val l_x = A.sub(levels,x)
in  A.update(in_alpha,x,stamp);
A.update(piggybank,l_x,x::A.sub(piggybank,l_x));
init(xs,if l < l_x then l_x else l)
end
fun visit(y,level_x,S) =
let fun scan([],S) = S
| scan((_,z,_)::es,S) =
let val level_z = A.sub(levels,z)
in  if level_z <= level_x andalso unmarked(in_DF,z,stamp)
then (if A.sub(in_alpha,z) <> stamp
then A.update(piggybank,level_z,
z::A.sub(piggybank,level_z))
else ();
scan(es,z::S))
else scan(es,S)
end
fun visitSucc([],S) = S
| visitSucc((_,z,_)::es,S) =
visitSucc(es,if unmarked(visited,z,stamp)
then visit(z,level_x,S) else S)
val S = scan(#out_edges cfg y,S)
in  visitSucc(#out_edges dom y,S)
end

fun visitAll(~1,S) = S
| visitAll(l,S) =
case A.sub(piggybank,l) of
[] => visitAll(l-1,S)
| x::xs => (A.update(visited,x,stamp);
A.update(piggybank,l,xs);
visitAll(l,visit(x,A.sub(levels,x),S)))

val L = init(xs,~1)
in  visitAll(L,[])
end

fun IDF x = IDFs [x]
in
{ DF = DF, IDF = IDF, IDFs = IDFs }
end

end

```

 root@smlnj-gforge.cs.uchicago.edu ViewVC Help Powered by ViewVC 1.0.0