# SCM Repository

# View of /sml/branches/SMLNJ/src/MLRISC/ir-moved/derived-graph.sml

Parent Directory | Revision Log

Revision

File size: 1538 byte(s)

**429**- (**download**) (**annotate**)*Wed Sep 8 09:47:00 1999 UTC*(20 years, 3 months ago) by*monnier*File size: 1538 byte(s)

version 110.21

(* * Compute Tarjan's dominator derived graph from a dominator tree. * This is used partly to computing path expressions. Alternatively, * it can also be used for testing for reducibility. In particular, * cycles involving more than one node represent irreducible loops * in the flow graph. * * -- Allen *) functor DerivedGraphFn (structure Dom : DOMINATOR_TREE structure GraphImpl : GRAPH_IMPLEMENTATION): DERIVED_GRAPH = struct structure Dom = Dom structure G = Graph structure GI = GraphImpl structure A = Array type ('n,'e) derived_graph = ('n,'e Graph.edge,unit) Graph.graph fun derived_graph (Dom as G.GRAPH dom) = let val N = #capacity dom () val D as G.GRAPH d = GI.graph("derived graph",(),N) val G.GRAPH cfg = Dom.cfg Dom val ancestors = A.array(Dom.max_levels Dom,0) val levelsMap = Dom.levelsMap Dom fun dfs lvl i = let val _ = A.update(ancestors,lvl,i) val _ = #add_node d (i,#node_info cfg i) fun add_edge (e as (i,j,_)) = let val level = A.sub(levelsMap,j) in if lvl < level then #add_edge d (i,j,e) (* i idom j ! *) else #add_edge d (A.sub(ancestors,level),j,e) end in app add_edge (#out_edges cfg i); app (dfs (lvl+1)) (#succ dom i) end in app (dfs 0) (#entries dom ()); #set_entries d (#entries dom ()); D end end

root@smlnj-gforge.cs.uchicago.edu | ViewVC Help |

Powered by ViewVC 1.0.0 |