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/mlrisc-cfg-util.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/IR/mlrisc-cfg-util.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 411 - (view) (download)

1 : monnier 245 (*
2 : monnier 411 * Some basic local CFG transformations. See the signature for descriptions.
3 :     *
4 :     * -- Allen
5 : monnier 245 *)
6 :     functor CFGUtilFn
7 :     (structure CFG : CONTROL_FLOW_GRAPH
8 :     structure P : INSN_PROPERTIES
9 :     sharing CFG.I = P.I
10 :     ) : CFG_UTIL =
11 :     struct
12 :    
13 :     structure CFG = CFG
14 :     structure I = CFG.I
15 :     structure W = CFG.W
16 :     structure G = Graph
17 :     structure H = HashArray
18 :     structure S = BitSet
19 :    
20 :     exception Can'tMerge
21 :    
22 : monnier 411 fun error msg = MLRiscErrorMsg.error("CFGTransforms",msg)
23 : monnier 245
24 :     fun labelOf(G.GRAPH cfg) node = CFG.defineLabel(#node_info cfg node)
25 :    
26 :     fun copyEdge(CFG.EDGE{a,w,k}) = CFG.EDGE{a=ref(!a),w=ref(!w),k=k}
27 :    
28 :     (*=====================================================================
29 :     *
30 :     * Check whether block i must preceed block j in any linear layout.
31 :     * This may be true if i falls through to j (transitively)
32 :     *
33 :     *=====================================================================*)
34 :     fun mustPreceed (G.GRAPH cfg) (i,j) =
35 :     let val visited = H.array(23,false)
36 :     fun chase [] = false
37 :     | chase((u,v,CFG.EDGE{k=(CFG.FALLSTHRU|CFG.BRANCH false),...})::_) =
38 :     if H.sub(visited,u) then false
39 :     else u = i orelse (H.update(visited,u,true); chase(#in_edges cfg u))
40 :     | chase(_::es) = chase es
41 :     in i = j orelse chase(#in_edges cfg j)
42 :     end
43 :    
44 :     (*=====================================================================
45 :     *
46 :     * Predicates on nodes and edges
47 :     *
48 :     *=====================================================================*)
49 :     fun isMerge (G.GRAPH cfg) node = length(#in_edges cfg node) > 1
50 :     fun isSplit (G.GRAPH cfg) node = length(#out_edges cfg node) > 1
51 :     fun hasSideExits (G.GRAPH cfg) node =
52 :     List.exists (fn (_,_,CFG.EDGE{k=CFG.SIDEEXIT _,...}) => true
53 :     | _ => false) (#out_edges cfg node)
54 : monnier 411 fun isCriticalEdge CFG (_,_,CFG.EDGE{k=CFG.ENTRY,...}) = false
55 :     | isCriticalEdge CFG (_,_,CFG.EDGE{k=CFG.EXIT,...}) = false
56 :     | isCriticalEdge CFG (i,j,_) = isSplit CFG i andalso isMerge CFG j
57 : monnier 245
58 :     (*=====================================================================
59 :     *
60 :     * Update the label of the branch instruction in a certain block
61 :     * to be consistent with the control flow edges. This doesn't work
62 :     * on hyperblocks!!!
63 :     *
64 :     *=====================================================================*)
65 :     fun updateJumpLabel(CFG as G.GRAPH cfg) =
66 :     let val labelOf = labelOf CFG
67 :     fun update node =
68 :     case #node_info cfg node of
69 :     CFG.BLOCK{insns=ref [],...} => ()
70 :     | CFG.BLOCK{kind=CFG.START,...} => ()
71 :     | CFG.BLOCK{kind=CFG.STOP,...} => ()
72 :     | CFG.BLOCK{insns=insns as ref(jmp::rest),...} =>
73 :     (case #out_edges cfg node of
74 :     [] => ()
75 :     | [(_,_,CFG.EDGE{k=(CFG.ENTRY | CFG.EXIT),...})] => ()
76 :     | [(i,j,_)] =>
77 :     if P.instrKind jmp = P.IK_JUMP then
78 :     insns := P.setTargets(jmp,[labelOf j])::rest
79 :     else ()
80 :     | [(_,i,CFG.EDGE{k=CFG.BRANCH x,...}),
81 :     (_,j,CFG.EDGE{k=CFG.BRANCH y,...})] =>
82 :     let val (i,j) = if x then (j,i) else (i,j)
83 :     in insns := P.setTargets(jmp,[labelOf i,labelOf j])::rest
84 :     end
85 :     | es =>
86 :     let fun cmp ((_,_,CFG.EDGE{k=CFG.SWITCH i,...}),
87 :     (_,_,CFG.EDGE{k=CFG.SWITCH j,...})) = i < j
88 :     | cmp _ = error "cmp"
89 :     val es = Sorting.sort cmp es
90 :     val labels = map (fn (_,j,_) => labelOf j) es
91 : monnier 411 in insns := P.setTargets(jmp,labels)::rest;
92 :     error "updateJumpLabel"
93 : monnier 245 end
94 :     )
95 :     in update
96 :     end
97 :    
98 :     (*=====================================================================
99 :     *
100 :     * Merge a control flow edge i -> j.
101 :     * Raise Can't Merge if it is illegal.
102 :     * After merging blocks i and j will become block i.
103 :     *
104 :     *=====================================================================*)
105 :     fun mergeEdge (CFG as G.GRAPH cfg) (i,j,e as CFG.EDGE{w,k,...}) =
106 :     let val _ = case k of
107 :     (CFG.ENTRY | CFG.EXIT) => raise Can'tMerge
108 :     | _ => ()
109 :     val _ = case (#out_edges cfg i,#in_edges cfg j) of
110 :     ([(_,j',_)],[(i',_,_)]) =>
111 :     if j' <> j orelse i' <> i then raise Can'tMerge
112 :     else ()
113 :     | _ => raise Can'tMerge
114 :     val _ = if mustPreceed CFG (i,j) then raise Can'tMerge else ()
115 : monnier 411 val CFG.BLOCK{data=d2,name=n2,insns=i2,annotations=a2,...} =
116 :     #node_info cfg j
117 : monnier 245 val _ = case !d2 of [] => () | _ => raise Can'tMerge
118 : monnier 411 val CFG.BLOCK{data=d1,name=n1,insns=i1,annotations=a1,...} =
119 :     #node_info cfg i
120 :     (* If the two blocks have different names then don't merge them *)
121 :     val _ = if CFG.B.==(n1,n2) then () else raise Can'tMerge
122 : monnier 245 val insns1 = case !i1 of
123 :     [] => []
124 :     | insns as jmp::rest =>
125 :     if P.instrKind jmp = P.IK_JUMP then rest else insns
126 :     in i1 := !i2 @ insns1;
127 :     a1 := !a1 @ !a2;
128 :     #set_out_edges cfg (i,map (fn (_,j',e) => (i,j',e)) (#out_edges cfg j));
129 :     #remove_node cfg j;
130 :     updateJumpLabel CFG i;
131 :     true
132 :     end handle Can'tMerge => false
133 :    
134 :     (*=====================================================================
135 :     *
136 :     * Eliminate the jump at the end of a basic block if feasible
137 :     *
138 :     *=====================================================================*)
139 :     fun eliminateJump (CFG as G.GRAPH cfg) i =
140 :     (case #out_edges cfg i of
141 :     [e as (i,j,CFG.EDGE{k,w,a})] =>
142 :     (case CFG.fallsThruFrom(CFG,j) of
143 :     SOME _ => false
144 :     | NONE =>
145 :     if mustPreceed CFG (j,i) then false
146 :     else
147 :     let val CFG.BLOCK{insns,...} = #node_info cfg i
148 :     val CFG.BLOCK{data,...} = #node_info cfg j
149 :     in case (!data,!insns) of
150 :     ([],jmp::rest) =>
151 :     if P.instrKind jmp = P.IK_JUMP then
152 :     (insns := rest;
153 :     CFG.removeEdge CFG e;
154 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w=w,a=a});
155 :     true
156 :     )
157 :     else false
158 :     | _ => false
159 :     end
160 :     )
161 :     | _ => false
162 :     )
163 :    
164 :     (*=====================================================================
165 :     *
166 :     * Insert a jump at the end of a basic block if feasible
167 :     *
168 :     *=====================================================================*)
169 :     fun insertJump (CFG as G.GRAPH cfg) i =
170 :     (case #out_edges cfg i of
171 :     [e as (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w,a,...})] =>
172 :     let val CFG.BLOCK{insns,...} = #node_info cfg i
173 :     in insns := P.jump(labelOf CFG j) :: !insns;
174 :     CFG.removeEdge CFG e;
175 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.JUMP,w=w,a=a});
176 :     true
177 :     end
178 :     | _ => false
179 :     )
180 :    
181 :     (*=====================================================================
182 :     *
183 :     * Split a control flow edge, return a new edge and the new block
184 :     *
185 :     *=====================================================================*)
186 :     fun splitEdge (CFG as G.GRAPH cfg) {edge=(i,j,e as CFG.EDGE{w,...}),jump} =
187 :     let val k = #new_id cfg ()
188 :     val jump = jump orelse i = j orelse
189 :     (case CFG.fallsThruFrom(CFG,j) of
190 :     NONE => false
191 :     | SOME _ => true)
192 : monnier 411 val node as CFG.BLOCK{insns,...} = CFG.newBlock(k,CFG.B.default,ref(!w))
193 : monnier 245 val kind = if jump then CFG.JUMP else CFG.FALLSTHRU
194 :     val _ = if jump then insns := [P.jump(labelOf CFG j)] else ()
195 :     val edge = (k,j,CFG.EDGE{w=ref(!w),a=ref [],k=kind})
196 :     in CFG.removeEdge CFG (i,j,e);
197 :     #add_edge cfg (i,k,e);
198 :     #add_node cfg (k,node);
199 :     #add_edge cfg edge;
200 :     updateJumpLabel CFG i;
201 :     {node=(k,node),edge=edge}
202 :     end
203 :    
204 :     (*=====================================================================
205 :     *
206 :     * Split all critical edges in the CFG
207 :     *
208 :     *=====================================================================*)
209 :     fun splitAllCriticalEdges (CFG as G.GRAPH cfg) =
210 : monnier 411 (#forall_edges cfg (fn e => if isCriticalEdge CFG e then
211 :     (splitEdge CFG {edge=e,jump=false}; ())
212 :     else ());
213 :     CFG.changed CFG
214 :     )
215 : monnier 245
216 :     (*=====================================================================
217 :     *
218 :     * Tail duplicate a region until there are no side entry edges
219 :     * entering into the region. Return the set of new edges and nodes
220 :     *
221 :     *=====================================================================*)
222 :     fun tailDuplicate (CFG as G.GRAPH cfg : CFG.cfg)
223 :     {subgraph=G.GRAPH subgraph : CFG.cfg,root} =
224 :     let exception NotFound
225 :     val blockMap = H.array'(10,fn v => raise NotFound)
226 :     val _ = print("[root "^Int.toString root^"]\n")
227 :    
228 :     fun duplicate v =
229 :     H.sub(blockMap,v) handle NotFound =>
230 :     let val w = #new_id cfg ()
231 :     val w' = CFG.copyBlock(w,#node_info cfg v)
232 :     in #add_node cfg (w,w');
233 :     H.update(blockMap,v,(w,w'));
234 :     app (#add_edge cfg)
235 :     (map (fn (i,j,e) => (w,j,copyEdge e)) (#out_edges cfg v));
236 :     updateJumpLabel CFG w;
237 :     (w,w')
238 :     end
239 :    
240 :     fun process((n,_)::rest,ns,Ns,Es) =
241 :     process(rest,collect(#entry_edges subgraph n,ns),Ns,Es)
242 :     | process([],ns,Ns,Es) = dupl(ns,Ns,Es,false)
243 :    
244 :     and collect([],ns) = ns
245 :     | collect((i,_,_)::es,ns) = collect(es,if i = root then ns else i::ns)
246 :    
247 :     and dupl([],Ns,Es,changed) = (Ns,Es,changed)
248 :     | dupl(n::ns,Ns,Es,changed) =
249 :     redirect(#out_edges cfg n,ns,Ns,Es,changed)
250 :    
251 :     and redirect([],ns,Ns,Es,changed) = dupl(ns,Ns,Es,changed)
252 :     | redirect((u,v,e)::es,ns,Ns,Es,changed) =
253 :     if v <> root andalso
254 :     #has_edge cfg (u,v) andalso
255 :     #has_node subgraph v andalso
256 :     not(#has_edge subgraph (u,v)) then
257 :     (*
258 :     * u -> v is a side entry edge, duplicate v
259 :     *)
260 :     let val _ = print("[tail duplicating "^Int.toString u^" -> "^
261 :     Int.toString v^"]\n")
262 :     val (w,w') = duplicate v
263 :     in CFG.removeEdge CFG (u,v,e);
264 :     #add_edge cfg (u,w,e);
265 :     updateJumpLabel CFG u;
266 :     redirect(es,w::ns,(w,w')::Ns,(u,w,e)::Es,true)
267 :     end
268 :     else redirect(es,ns,Ns,Es,changed)
269 :    
270 :     fun iter(Ns,Es) =
271 :     let val (Ns,Es,changed) = process(#nodes subgraph (),[],Ns,Es)
272 :     in if changed then (CFG.changed CFG; iter(Ns,Es))
273 :     else {nodes=Ns,edges=Es}
274 :     end
275 :    
276 :     in iter([],[])
277 :     end
278 :    
279 :    
280 :     (*=====================================================================
281 :     *
282 :     * Remove unreachable code in the CFG
283 :     *
284 :     *=====================================================================*)
285 :     fun removeUnreachableCode(CFG as G.GRAPH cfg) =
286 :     let val N = #capacity cfg ()
287 :     val visited = S.create N
288 :     fun mark n = if S.markAndTest(visited,n) then ()
289 :     else app mark (#succ cfg n)
290 :     val changed = ref false
291 :     fun remove(b,CFG.BLOCK{data,insns,...}) =
292 :     if S.contains(visited,b) then ()
293 :     else
294 :     (changed :=true;
295 :     case #in_edges cfg b of
296 :     [] => #remove_node cfg b
297 :     | _ => (insns := []; #set_out_edges cfg (b,[]))
298 :     )
299 :     in app mark (#entries cfg ());
300 :     #forall_nodes cfg remove;
301 :     if !changed then CFG.changed CFG else ()
302 :     end
303 :    
304 :    
305 :     (*=====================================================================
306 :     *
307 :     * Merge all edges in the CFG
308 :     *
309 :     *=====================================================================*)
310 :     fun mergeAllEdges(CFG as G.GRAPH cfg) =
311 :     let val mergeEdge = mergeEdge CFG
312 : monnier 411 fun higherFreq((_,_,CFG.EDGE{w=x,...}),(_,_,CFG.EDGE{w=y,...}))= !x < !y
313 : monnier 245 fun mergeAll([],changed) = changed
314 :     | mergeAll(e::es,changed) = mergeAll(es,mergeEdge e orelse changed)
315 :     val changed = mergeAll(Sorting.sort higherFreq (#edges cfg ()),false)
316 :     in if changed then CFG.changed CFG else ()
317 :     end
318 :    
319 :     end
320 :    

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