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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 657 - (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 : george 545 functor CFGUtil
7 :     (structure CFG : CONTROL_FLOW_GRAPH
8 :     structure InsnProps : INSN_PROPERTIES
9 :     sharing CFG.I = InsnProps.I
10 : monnier 245 ) : 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 : leunga 657 fun error msg = MLRiscErrorMsg.error("CFGUtil",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 : george 545 if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
78 :     insns := InsnProps.setTargets(jmp,[labelOf j])::rest
79 : monnier 245 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 : george 545 in insns :=
84 :     InsnProps.setTargets(jmp,[labelOf i,labelOf j])::rest
85 : monnier 245 end
86 :     | es =>
87 : monnier 429 let fun gt ((_,_,CFG.EDGE{k=CFG.SWITCH i,...}),
88 :     (_,_,CFG.EDGE{k=CFG.SWITCH j,...})) = i > j
89 :     | gt _ = error "gt"
90 :     val es = ListMergeSort.sort gt es
91 : monnier 245 val labels = map (fn (_,j,_) => labelOf j) es
92 : george 545 in insns := InsnProps.setTargets(jmp,labels)::rest;
93 : monnier 411 error "updateJumpLabel"
94 : monnier 245 end
95 :     )
96 :     in update
97 :     end
98 :    
99 :     (*=====================================================================
100 :     *
101 :     * Merge a control flow edge i -> j.
102 :     * Raise Can't Merge if it is illegal.
103 :     * After merging blocks i and j will become block i.
104 :     *
105 :     *=====================================================================*)
106 :     fun mergeEdge (CFG as G.GRAPH cfg) (i,j,e as CFG.EDGE{w,k,...}) =
107 :     let val _ = case k of
108 :     (CFG.ENTRY | CFG.EXIT) => raise Can'tMerge
109 :     | _ => ()
110 :     val _ = case (#out_edges cfg i,#in_edges cfg j) of
111 :     ([(_,j',_)],[(i',_,_)]) =>
112 :     if j' <> j orelse i' <> i then raise Can'tMerge
113 :     else ()
114 :     | _ => raise Can'tMerge
115 :     val _ = if mustPreceed CFG (i,j) then raise Can'tMerge else ()
116 : monnier 469 val CFG.BLOCK{data=d2,insns=i2,annotations=a2,...} =
117 : monnier 411 #node_info cfg j
118 : monnier 245 val _ = case !d2 of [] => () | _ => raise Can'tMerge
119 : monnier 469 val CFG.BLOCK{data=d1,insns=i1,annotations=a1,...} =
120 : monnier 411 #node_info cfg i
121 : leunga 606 (* If both blocks have annotations then don't merge them.
122 :     * But instead, just try to removed the jump instruction instead.
123 :     *)
124 :     val canMerge = case (!a1, !a2) of
125 :     (_::_, _::_) => false
126 :     | _ => true
127 : monnier 245 val insns1 = case !i1 of
128 :     [] => []
129 :     | insns as jmp::rest =>
130 : george 545 if InsnProps.instrKind jmp = InsnProps.IK_JUMP
131 :     then rest else insns
132 : leunga 606 in if canMerge then
133 :     (i1 := !i2 @ insns1;
134 :     a1 := !a1 @ !a2;
135 :     #set_out_edges cfg
136 :     (i,map (fn (_,j',e) => (i,j',e)) (#out_edges cfg j));
137 :     #remove_node cfg j;
138 :     updateJumpLabel CFG i
139 :     )
140 :     else (* Just eliminate the jump instruction at the end *)
141 :     (i1 := insns1;
142 :     #set_out_edges cfg
143 :     (i,map (fn (i,j,CFG.EDGE{w,a,...}) =>
144 :     (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w=w,a=a}))
145 :     (#out_edges cfg i))
146 :     );
147 : monnier 245 true
148 :     end handle Can'tMerge => false
149 :    
150 :     (*=====================================================================
151 :     *
152 :     * Eliminate the jump at the end of a basic block if feasible
153 :     *
154 :     *=====================================================================*)
155 :     fun eliminateJump (CFG as G.GRAPH cfg) i =
156 :     (case #out_edges cfg i of
157 :     [e as (i,j,CFG.EDGE{k,w,a})] =>
158 :     (case CFG.fallsThruFrom(CFG,j) of
159 :     SOME _ => false
160 :     | NONE =>
161 :     if mustPreceed CFG (j,i) then false
162 :     else
163 :     let val CFG.BLOCK{insns,...} = #node_info cfg i
164 :     val CFG.BLOCK{data,...} = #node_info cfg j
165 :     in case (!data,!insns) of
166 :     ([],jmp::rest) =>
167 : george 545 if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
168 : monnier 245 (insns := rest;
169 :     CFG.removeEdge CFG e;
170 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w=w,a=a});
171 :     true
172 :     )
173 :     else false
174 :     | _ => false
175 :     end
176 :     )
177 :     | _ => false
178 :     )
179 :    
180 :     (*=====================================================================
181 :     *
182 :     * Insert a jump at the end of a basic block if feasible
183 :     *
184 :     *=====================================================================*)
185 :     fun insertJump (CFG as G.GRAPH cfg) i =
186 :     (case #out_edges cfg i of
187 :     [e as (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w,a,...})] =>
188 :     let val CFG.BLOCK{insns,...} = #node_info cfg i
189 : george 545 in insns := InsnProps.jump(labelOf CFG j) :: !insns;
190 : monnier 245 CFG.removeEdge CFG e;
191 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.JUMP,w=w,a=a});
192 :     true
193 :     end
194 :     | _ => false
195 :     )
196 :    
197 :     (*=====================================================================
198 :     *
199 :     * Split a control flow edge, return a new edge and the new block
200 :     *
201 :     *=====================================================================*)
202 : monnier 429 fun splitEdge (CFG as G.GRAPH cfg)
203 :     {kind, edge=(i,j,e as CFG.EDGE{w,...}),jump} =
204 : monnier 245 let val k = #new_id cfg ()
205 :     val jump = jump orelse i = j orelse
206 :     (case CFG.fallsThruFrom(CFG,j) of
207 :     NONE => false
208 :     | SOME _ => true)
209 : george 545 val insns = ref(if jump then [InsnProps.jump(labelOf CFG j)] else [])
210 : monnier 429 val node =
211 : monnier 469 CFG.BLOCK{id=k, kind=kind,
212 : monnier 429 freq= ref(!w), data=ref [], labels = ref [],
213 :     insns=insns, annotations=ref []}
214 : monnier 245 val kind = if jump then CFG.JUMP else CFG.FALLSTHRU
215 :     val edge = (k,j,CFG.EDGE{w=ref(!w),a=ref [],k=kind})
216 :     in CFG.removeEdge CFG (i,j,e);
217 :     #add_edge cfg (i,k,e);
218 :     #add_node cfg (k,node);
219 :     #add_edge cfg edge;
220 :     updateJumpLabel CFG i;
221 :     {node=(k,node),edge=edge}
222 :     end
223 :    
224 :     (*=====================================================================
225 :     *
226 :     * Split all critical edges in the CFG
227 :     *
228 :     *=====================================================================*)
229 :     fun splitAllCriticalEdges (CFG as G.GRAPH cfg) =
230 : leunga 606 let val changed = ref false
231 :     in #forall_edges cfg
232 :     (fn e => if isCriticalEdge CFG e then
233 :     (splitEdge CFG {edge=e,kind=CFG.NORMAL,jump=false}; changed := true)
234 :     else ());
235 :     if !changed then CFG.changed CFG else ()
236 :     end
237 : monnier 245
238 :     (*=====================================================================
239 :     *
240 :     * Tail duplicate a region until there are no side entry edges
241 :     * entering into the region. Return the set of new edges and nodes
242 :     *
243 :     *=====================================================================*)
244 :     fun tailDuplicate (CFG as G.GRAPH cfg : CFG.cfg)
245 :     {subgraph=G.GRAPH subgraph : CFG.cfg,root} =
246 :     let exception NotFound
247 :     val blockMap = H.array'(10,fn v => raise NotFound)
248 :     val _ = print("[root "^Int.toString root^"]\n")
249 :    
250 :     fun duplicate v =
251 :     H.sub(blockMap,v) handle NotFound =>
252 :     let val w = #new_id cfg ()
253 :     val w' = CFG.copyBlock(w,#node_info cfg v)
254 :     in #add_node cfg (w,w');
255 :     H.update(blockMap,v,(w,w'));
256 :     app (#add_edge cfg)
257 :     (map (fn (i,j,e) => (w,j,copyEdge e)) (#out_edges cfg v));
258 :     updateJumpLabel CFG w;
259 :     (w,w')
260 :     end
261 :    
262 :     fun process((n,_)::rest,ns,Ns,Es) =
263 :     process(rest,collect(#entry_edges subgraph n,ns),Ns,Es)
264 :     | process([],ns,Ns,Es) = dupl(ns,Ns,Es,false)
265 :    
266 :     and collect([],ns) = ns
267 :     | collect((i,_,_)::es,ns) = collect(es,if i = root then ns else i::ns)
268 :    
269 :     and dupl([],Ns,Es,changed) = (Ns,Es,changed)
270 :     | dupl(n::ns,Ns,Es,changed) =
271 :     redirect(#out_edges cfg n,ns,Ns,Es,changed)
272 :    
273 :     and redirect([],ns,Ns,Es,changed) = dupl(ns,Ns,Es,changed)
274 :     | redirect((u,v,e)::es,ns,Ns,Es,changed) =
275 :     if v <> root andalso
276 :     #has_edge cfg (u,v) andalso
277 :     #has_node subgraph v andalso
278 :     not(#has_edge subgraph (u,v)) then
279 :     (*
280 :     * u -> v is a side entry edge, duplicate v
281 :     *)
282 :     let val _ = print("[tail duplicating "^Int.toString u^" -> "^
283 :     Int.toString v^"]\n")
284 :     val (w,w') = duplicate v
285 :     in CFG.removeEdge CFG (u,v,e);
286 :     #add_edge cfg (u,w,e);
287 :     updateJumpLabel CFG u;
288 :     redirect(es,w::ns,(w,w')::Ns,(u,w,e)::Es,true)
289 :     end
290 :     else redirect(es,ns,Ns,Es,changed)
291 :    
292 :     fun iter(Ns,Es) =
293 :     let val (Ns,Es,changed) = process(#nodes subgraph (),[],Ns,Es)
294 :     in if changed then (CFG.changed CFG; iter(Ns,Es))
295 :     else {nodes=Ns,edges=Es}
296 :     end
297 :    
298 :     in iter([],[])
299 :     end
300 :    
301 :    
302 :     (*=====================================================================
303 :     *
304 :     * Remove unreachable code in the CFG
305 :     *
306 :     *=====================================================================*)
307 :     fun removeUnreachableCode(CFG as G.GRAPH cfg) =
308 :     let val N = #capacity cfg ()
309 :     val visited = S.create N
310 :     fun mark n = if S.markAndTest(visited,n) then ()
311 :     else app mark (#succ cfg n)
312 :     val changed = ref false
313 :     fun remove(b,CFG.BLOCK{data,insns,...}) =
314 :     if S.contains(visited,b) then ()
315 :     else
316 :     (changed :=true;
317 :     case #in_edges cfg b of
318 :     [] => #remove_node cfg b
319 :     | _ => (insns := []; #set_out_edges cfg (b,[]))
320 :     )
321 :     in app mark (#entries cfg ());
322 :     #forall_nodes cfg remove;
323 :     if !changed then CFG.changed CFG else ()
324 :     end
325 :    
326 :    
327 :     (*=====================================================================
328 :     *
329 : monnier 429 * Merge all edges in the CFG.
330 :     * Merge higher frequency edges first
331 : monnier 245 *
332 :     *=====================================================================*)
333 :     fun mergeAllEdges(CFG as G.GRAPH cfg) =
334 :     let val mergeEdge = mergeEdge CFG
335 : monnier 411 fun higherFreq((_,_,CFG.EDGE{w=x,...}),(_,_,CFG.EDGE{w=y,...}))= !x < !y
336 : monnier 245 fun mergeAll([],changed) = changed
337 :     | mergeAll(e::es,changed) = mergeAll(es,mergeEdge e orelse changed)
338 : monnier 429 (* note: sort expects the gt operator and sorts in ascending order *)
339 :     val changed = mergeAll(ListMergeSort.sort higherFreq (#edges cfg ()),
340 :     false)
341 : monnier 245 in if changed then CFG.changed CFG else ()
342 :     end
343 :    
344 :     end
345 :    

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