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/trunk/src/MLRISC/ir-archive/loop-structure.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ir-archive/loop-structure.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1095 - (view) (download)

1 : george 912 (*
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 :     functor LoopStructure (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 :     fun dom(G.GRAPH{graph_info=INFO{dom,...},...}) = dom
41 :    
42 :     fun loop_structure DOM = let
43 :     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 :     val dominates = Dom.dominates DOM
48 :     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 :    
55 :     fun find_loops (header,level) i = let
56 :     val backedges = List.filter (fn (j,i,_) => dominates(i,j)) (#in_edges cfg i)
57 :     val is_header = case backedges of [] => i = ENTRY | _ => true
58 :     in
59 :     if not(is_header) then
60 :     app (find_loops (header,level)) (#succ dom i)
61 :     else let (* i is now the new loop header *)
62 :     (* find all nested loops first *)
63 :     val _ = app (find_loops (i,level+1)) (#succ dom i)
64 :     (* locate all loop nodes *)
65 :     fun find_loop_nodes([],nodes) = nodes
66 :     | find_loop_nodes((j,_,_)::es,nodes) =
67 :     if i = j then find_loop_nodes(es,nodes)
68 :     else find_loop_nodes(es,do_node(j,nodes))
69 :     and do_node(j,nodes) = (* j is not the header i *)
70 :     let val v = A.sub(visited,j)
71 :     in if v = ~1 then (* j is a new loop node *)
72 :     (A.update(headers,j,i);
73 :     A.update(visited,j,i);
74 :     find_loop_nodes(#in_edges cfg j,j::nodes))
75 :     else chase_header(v,j,nodes)
76 :     end
77 :     and chase_header(v,j,nodes) =
78 :     if v = i then nodes (* j has been visited before *)
79 :     else
80 :     (* j is in a nested loop *)
81 :     let val _ = A.update(visited,j,i) (* mark j as visited *)
82 :     val h = A.sub(headers,j)
83 :     in if h = i then
84 :     (* j is a header immediately nested under i *)
85 :     find_loop_nodes(#in_edges cfg j,nodes)
86 :     else (A.update(headers,j,i); (* path compression *)
87 :     chase_header(A.sub(visited,h),h,nodes))
88 :     end
89 :    
90 :     fun find_entry_loop_nodes() =
91 :     map #1 (List.filter (fn (i,n) => A.sub(headers,i) = ~1)
92 :     (#nodes cfg ()))
93 :    
94 :     fun find_exits(header,[],exits) = exits
95 :     | find_exits(header,i::is,exits) =
96 :     let fun f((e as (i,j,_))::es,exits) =
97 :     if A.sub(headers,j) = ~1
98 :     then f(es,e::exits) else f(es,exits)
99 :     | f([], exits) = exits
100 :     in find_exits(header,is,f(#out_edges cfg i,exits)) end
101 :    
102 :     val _ = A.update(headers,i,header)
103 :     val _ = A.update(visited,i,i)
104 :    
105 :     val nodes =
106 :     if i = ENTRY then find_entry_loop_nodes()
107 :     else find_loop_nodes(backedges,[])
108 :     val exits =
109 :     if i = ENTRY then [] else find_exits(i,i::nodes,[])
110 :    
111 :     val loop =
112 :     LOOP { nesting = level,
113 :     header = i,
114 :     backedges = backedges,
115 :     loop_nodes = nodes,
116 :     exits = exits
117 :     }
118 :     in
119 :     #add_node ls (i,loop);
120 :     if i = ENTRY then () else #add_edge ls (header,i,())
121 :     end
122 :     end (* find_loops *)
123 :     in find_loops (ENTRY,0) ENTRY;
124 :     #set_entries ls [ENTRY];
125 :     LS
126 :     end (* loop_structure *)
127 :    
128 :     fun nesting_level(G.GRAPH L) = let
129 :     val INFO{dom=G.GRAPH dom,...} = #graph_info L
130 :     val N = #capacity dom ()
131 :     val levels = A.array(N,0)
132 :     fun tabulate(_,LOOP{nesting,header,loop_nodes,...}) =
133 :     (A.update(levels,header,nesting);
134 :     app (fn i => A.update(levels,i,nesting)) loop_nodes)
135 :     in
136 :     #forall_nodes L tabulate; levels
137 :     end
138 :    
139 :     fun header(G.GRAPH L) = let
140 :     val INFO{dom=G.GRAPH dom,...} = #graph_info L
141 :     val N = #capacity dom ()
142 :     val headers = A.array(N,0)
143 :     fun tabulate(_,LOOP{header,loop_nodes,...}) =
144 :     (A.update(headers,header,header);
145 :     app (fn i => A.update(headers,i,header)) loop_nodes)
146 :     in
147 :     #forall_nodes L tabulate; headers
148 :     end
149 :    
150 :    
151 :    
152 :     fun entryEdges(Loop as G.GRAPH L) = let
153 :     val dom = dom Loop
154 :     val G.GRAPH cfg = Dom.cfg dom
155 :     val dominates = Dom.dominates dom
156 :     fun entryEdges(header) =
157 :     if #has_node L header then
158 :     List.filter (fn (i,j,_) => not(dominates(j,i)))
159 :     (#in_edges cfg header)
160 :     else []
161 :     in entryEdges
162 :     end
163 :    
164 : leunga 1095 fun isBackEdge(Loop as G.GRAPH L) =
165 :     let val dom = Dom.dominates(dom Loop)
166 :     in fn (v,w) => #has_node L w andalso dom(w,v)
167 :     end
168 : george 912 end
169 :    

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