Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/IR/mlrisc-cfg-util.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 410, Fri Sep 3 00:25:03 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 1  Line 1 
1  (*  (*
2   * Some basic local CFG transformations   * Some basic local CFG transformations.  See the signature for descriptions.
3     *
4     * -- Allen
5   *)   *)
6  functor CFGUtilFn  functor CFGUtilFn
7       (structure CFG : CONTROL_FLOW_GRAPH       (structure CFG : CONTROL_FLOW_GRAPH
# Line 17  Line 19 
19    
20     exception Can'tMerge     exception Can'tMerge
21    
22     fun error msg = MLRiscErrorMsg.impossible("CFGTransforms."^msg)     fun error msg = MLRiscErrorMsg.error("CFGTransforms",msg)
23    
24     fun labelOf(G.GRAPH cfg) node = CFG.defineLabel(#node_info cfg node)     fun labelOf(G.GRAPH cfg) node = CFG.defineLabel(#node_info cfg node)
25    
# Line 49  Line 51 
51     fun hasSideExits (G.GRAPH cfg) node =     fun hasSideExits (G.GRAPH cfg) node =
52           List.exists (fn (_,_,CFG.EDGE{k=CFG.SIDEEXIT _,...}) => true           List.exists (fn (_,_,CFG.EDGE{k=CFG.SIDEEXIT _,...}) => true
53                         | _ => false) (#out_edges cfg node)                         | _ => false) (#out_edges cfg node)
54     fun isCriticalEdge CFG (i,j,_) = isMerge CFG i andalso isSplit CFG j     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    
58     (*=====================================================================     (*=====================================================================
59      *      *
# Line 84  Line 88 
88                          | cmp _ = error "cmp"                          | cmp _ = error "cmp"
89                        val es = Sorting.sort cmp es                        val es = Sorting.sort cmp es
90                        val labels = map (fn (_,j,_) => labelOf j) es                        val labels = map (fn (_,j,_) => labelOf j) es
91                    in  insns := P.setTargets(jmp,labels)::rest                    in  insns := P.setTargets(jmp,labels)::rest;
92                          error "updateJumpLabel"
93                    end                    end
94               )               )
95     in  update     in  update
# Line 107  Line 112 
112                       else ()                       else ()
113                 |  _ => raise Can'tMerge                 |  _ => raise Can'tMerge
114         val _ = if mustPreceed CFG (i,j) then raise Can'tMerge else ()         val _ = if mustPreceed CFG (i,j) then raise Can'tMerge else ()
115         val CFG.BLOCK{data=d2,insns=i2,annotations=a2,...} = #node_info cfg j         val CFG.BLOCK{data=d2,name=n2,insns=i2,annotations=a2,...} =
116                  #node_info cfg j
117         val _  = case !d2 of [] => () | _ => raise Can'tMerge         val _  = case !d2 of [] => () | _ => raise Can'tMerge
118         val CFG.BLOCK{data=d1,insns=i1,annotations=a1,...} = #node_info cfg i         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         val insns1 = case !i1 of         val insns1 = case !i1 of
123                        [] => []                        [] => []
124                      | insns as jmp::rest =>                      | insns as jmp::rest =>
# Line 180  Line 189 
189                (case CFG.fallsThruFrom(CFG,j) of                (case CFG.fallsThruFrom(CFG,j) of
190                  NONE => false                  NONE => false
191                | SOME _ => true)                | SOME _ => true)
192         val node as CFG.BLOCK{insns,freq,...} = CFG.newBlock(k,CFG.B.default)         val node as CFG.BLOCK{insns,...} = CFG.newBlock(k,CFG.B.default,ref(!w))
193         val kind = if jump then CFG.JUMP else CFG.FALLSTHRU         val kind = if jump then CFG.JUMP else CFG.FALLSTHRU
194         val _    = if jump then insns := [P.jump(labelOf CFG j)] else ()         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})         val edge = (k,j,CFG.EDGE{w=ref(!w),a=ref [],k=kind})
# Line 188  Line 197 
197         #add_edge cfg (i,k,e);         #add_edge cfg (i,k,e);
198         #add_node cfg (k,node);         #add_node cfg (k,node);
199         #add_edge cfg edge;         #add_edge cfg edge;
        freq := !w;  
200         updateJumpLabel CFG i;         updateJumpLabel CFG i;
201         {node=(k,node),edge=edge}         {node=(k,node),edge=edge}
202     end     end
# Line 199  Line 207 
207      *      *
208      *=====================================================================*)      *=====================================================================*)
209     fun splitAllCriticalEdges (CFG as G.GRAPH cfg) =     fun splitAllCriticalEdges (CFG as G.GRAPH cfg) =
210         #forall_edges cfg (fn e => if isCriticalEdge CFG e then         (#forall_edges cfg (fn e => if isCriticalEdge CFG e then
211                                      (splitEdge CFG {edge=e,jump=false}; ())                                      (splitEdge CFG {edge=e,jump=false}; ())
212                                    else ())                                    else ());
213            CFG.changed CFG
214           )
215    
216     (*=====================================================================     (*=====================================================================
217      *      *
# Line 299  Line 309 
309      *=====================================================================*)      *=====================================================================*)
310     fun mergeAllEdges(CFG as G.GRAPH cfg) =     fun mergeAllEdges(CFG as G.GRAPH cfg) =
311     let val mergeEdge = mergeEdge CFG     let val mergeEdge = mergeEdge CFG
312         fun higherFreq((_,_,CFG.EDGE{w=x,...}),(_,_,CFG.EDGE{w=y,...})) =         fun higherFreq((_,_,CFG.EDGE{w=x,...}),(_,_,CFG.EDGE{w=y,...}))= !x < !y
            W.<(!x,!y)  
313         fun mergeAll([],changed) = changed         fun mergeAll([],changed) = changed
314           | mergeAll(e::es,changed) = mergeAll(es,mergeEdge e orelse changed)           | mergeAll(e::es,changed) = mergeAll(es,mergeEdge e orelse changed)
315         val changed = mergeAll(Sorting.sort higherFreq (#edges cfg ()),false)         val changed = mergeAll(Sorting.sort higherFreq (#edges cfg ()),false)
# Line 309  Line 318 
318    
319  end  end
320    
 (*  
  * $Log$  
  *)  

Legend:
Removed from v.410  
changed lines
  Added in v.411

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