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

SCM Repository

[smlnj] Annotation of /sml/branches/SMLNJ/src/MLRISC/ir-moved/loop-structure.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/ir-moved/loop-structure.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 429 - (view) (download)

1 : monnier 411 (*
2 :     * This module is responsible for locating loop structures (intervals).
3 :     * All loops have only one single entry (via the header) but
4 :     * potentially multiple exits, i.e. the header dominates all nodes
5 :     * within the loop. Other definitions are used for ``loops'' and ``headers''
6 :     * in the literature. We choose a structural definition that has nicer
7 :     * properties.
8 :     *
9 :     * I haven't seen this algorithm described in the literature but I'm
10 :     * quite sure that it works in linear time, given that the dominator tree
11 :     * has already been computed.
12 :     *
13 :     * -- Allen
14 :     *)
15 :    
16 : monnier 245 functor LoopStructureFn (structure GraphImpl : GRAPH_IMPLEMENTATION
17 :     structure Dom : DOMINATOR_TREE)
18 :     : LOOP_STRUCTURE =
19 :     struct
20 :    
21 :     structure G = Graph
22 :     structure GI = GraphImpl
23 :     structure Dom = Dom
24 :     structure A = Array
25 :    
26 :     datatype ('n,'e,'g) loop =
27 :     LOOP of { nesting : int,
28 :     header : G.node_id,
29 :     loop_nodes : G.node_id list,
30 :     backedges : 'e G.edge list,
31 :     exits : 'e G.edge list
32 :     }
33 :    
34 :     datatype ('n,'e,'g) loop_info =
35 :     INFO of { dom : ('n,'e,'g) Dom.dominator_tree }
36 :    
37 :     type ('n,'e,'g) loop_structure =
38 :     (('n,'e,'g) loop, unit, ('n,'e,'g) loop_info) Graph.graph
39 :    
40 : monnier 411 fun dom(G.GRAPH{graph_info=INFO{dom,...},...}) = dom
41 :    
42 : monnier 245 fun loop_structure DOM =
43 :     let val info = INFO{ dom = DOM }
44 :     val G.GRAPH cfg = Dom.cfg DOM
45 :     val G.GRAPH dom = DOM
46 :     val N = #capacity dom ()
47 : monnier 429 val dominates = Dom.dominates DOM
48 : monnier 411 val LS as G.GRAPH ls = GI.graph ("Loop structure",info,N)
49 :     val ENTRY = case #entries cfg () of
50 :     [ENTRY] => ENTRY
51 :     | _ => raise Graph.NotSingleEntry
52 :     val headers = A.array(N,~1) (* header forest *)
53 :     val visited = A.array(N,~1)
54 : monnier 245
55 : monnier 411 fun find_loops (header,level) i =
56 : monnier 245 let val backedges = List.filter (fn (j,i,_) => dominates(i,j))
57 :     (#in_edges cfg i)
58 :     val is_header = case backedges of [] => i = ENTRY
59 :     | _ => true
60 : monnier 411 in if is_header then (* i is now the new loop header *)
61 :     (* find all nested loops first *)
62 :     let val _ = app (find_loops (i,level+1)) (#succ dom i)
63 :     (* locate all loop nodes *)
64 :     fun find_loop_nodes([],nodes) = nodes
65 :     | find_loop_nodes((j,_,_)::es,nodes) =
66 :     if i = j then find_loop_nodes(es,nodes)
67 :     else find_loop_nodes(es,do_node(j,nodes))
68 :     and do_node(j,nodes) = (* j is not the header i *)
69 :     let val v = A.sub(visited,j)
70 :     in if v = ~1 then (* j is a new loop node *)
71 :     (A.update(headers,j,i);
72 :     A.update(visited,j,i);
73 :     find_loop_nodes(#in_edges cfg j,j::nodes))
74 :     else chase_header(v,j,nodes)
75 : monnier 245 end
76 : monnier 411 and chase_header(v,j,nodes) =
77 :     if v = i then nodes (* j has been visited before *)
78 :     else
79 :     (* j is in a nested loop *)
80 :     let val _ = A.update(visited,j,i) (* mark j as visited *)
81 :     val h = A.sub(headers,j)
82 :     in if h = i then
83 :     (* j is a header immediately nested under i *)
84 :     find_loop_nodes(#in_edges cfg j,nodes)
85 :     else (A.update(headers,j,i); (* path compression *)
86 :     chase_header(A.sub(visited,h),h,nodes))
87 :     end
88 :    
89 : monnier 245 fun find_entry_loop_nodes() =
90 :     map #1 (List.filter (fn (i,n) => A.sub(headers,i) = ~1)
91 :     (#nodes cfg ()))
92 :    
93 :     fun find_exits(header,[],exits) = exits
94 :     | find_exits(header,i::is,exits) =
95 :     let fun f((e as (i,j,_))::es,exits) =
96 : monnier 411 if A.sub(headers,j) = ~1
97 :     then f(es,e::exits) else f(es,exits)
98 : monnier 245 | f([], exits) = exits
99 :     in find_exits(header,is,f(#out_edges cfg i,exits)) end
100 : monnier 411 val _ = A.update(headers,i,header)
101 :     val _ = A.update(visited,i,i)
102 : monnier 245 val nodes = if i = ENTRY then
103 :     find_entry_loop_nodes()
104 :     else
105 :     find_loop_nodes(backedges,[])
106 :     val exits = if i = ENTRY then []
107 :     else find_exits(i,i::nodes,[])
108 :     val loop = LOOP { nesting = level,
109 :     header = i,
110 :     backedges = backedges,
111 :     loop_nodes = nodes,
112 :     exits = exits
113 :     }
114 :     in #add_node ls (i,loop);
115 :     if i = ENTRY then () else #add_edge ls (header,i,())
116 :     end
117 : monnier 411 else app (find_loops (header,level)) (#succ dom i)
118 : monnier 245 end
119 : monnier 411 in find_loops (ENTRY,0) ENTRY;
120 : monnier 245 #set_entries ls [ENTRY];
121 :     LS
122 :     end
123 :    
124 :     fun nesting_level(G.GRAPH L) =
125 :     let val INFO{dom=G.GRAPH dom,...} = #graph_info L
126 :     val N = #capacity dom ()
127 :     val levels = A.array(N,0)
128 :     fun tabulate(_,LOOP{nesting,header,loop_nodes,...}) =
129 :     (A.update(levels,header,nesting);
130 :     app (fn i => A.update(levels,i,nesting)) loop_nodes)
131 :     in #forall_nodes L tabulate;
132 :     levels
133 :     end
134 :    
135 :     fun header(G.GRAPH L) =
136 :     let val INFO{dom=G.GRAPH dom,...} = #graph_info L
137 :     val N = #capacity dom ()
138 :     val headers = A.array(N,0)
139 :     fun tabulate(_,LOOP{header,loop_nodes,...}) =
140 :     (A.update(headers,header,header);
141 :     app (fn i => A.update(headers,i,header)) loop_nodes)
142 :     in #forall_nodes L tabulate;
143 :     headers
144 :     end
145 :    
146 : monnier 411 fun entryEdges(Loop as G.GRAPH L) =
147 :     let val dom = dom Loop
148 :     val G.GRAPH cfg = Dom.cfg dom
149 : monnier 429 val dominates = Dom.dominates dom
150 : monnier 411 fun entryEdges(header) =
151 :     if #has_node L header then
152 :     List.filter(fn (i,j,_) => not(dominates(j,i)))
153 :     (#in_edges cfg header)
154 :     else []
155 :     in entryEdges
156 :     end
157 :    
158 : monnier 245 end
159 :    

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