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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 470 - (view) (download)
Original Path: sml/trunk/src/MLRISC/IR/mlrisc-cfg-util.sml

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

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