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 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/IR/mlrisc-cfg-util.sml

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

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