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

Diff of /MLRISC/trunk/IR/mlrisc-cfg2cluster.sml

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

revision 245, Sat Apr 17 18:47:12 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 1  Line 1 
1  (*  (*
2   *  Convert the new control flow graph format back into the old cluster format   *  Convert the new control flow graph format back into the old cluster format
3     *
4     *  -- Allen
5   *)   *)
6    
7  signature CFG2CLUSTER =  signature CFG2CLUSTER =
# Line 26  Line 28 
28         sharing CFG.I = F.I         sharing CFG.I = F.I
29         sharing CFG.P = F.P         sharing CFG.P = F.P
30         sharing CFG.B = F.B         sharing CFG.B = F.B
     val patchBranch : {instr:CFG.I.instruction, backwards:bool} ->  
                          CFG.I.instruction list  
31     ) : CFG2CLUSTER =     ) : CFG2CLUSTER =
32  struct  struct
33    
# Line 39  Line 39 
39      structure Set      = BitSet      structure Set      = BitSet
40      structure A        = Array      structure A        = Array
41    
42      fun error msg = MLRiscErrorMsg.impossible("CFG2Cluster."^msg)      fun error msg = MLRiscErrorMsg.error("CFG2Cluster",msg)
43    
44      fun pseudo_op (CFG.LABEL l) = F.LABEL l      fun pseudo_op (CFG.LABEL l) = F.LABEL l
45        | pseudo_op (CFG.PSEUDO p) = F.PSEUDO p        | pseudo_op (CFG.PSEUDO p) = F.PSEUDO p
46    
47          (* create a new BBLOCK with id i *)          (* create a new BBLOCK with id i *)
48      fun bblock M (i,b as      fun bblock M (i,b as
49                      CFG.BLOCK{kind,name,annotations,insns,labels,data,...}) =                   CFG.BLOCK{kind,freq,name,annotations,insns,labels,data,...}) =
50      let val labels = map F.LABEL (!labels)      let val labels = map F.LABEL (!labels)
51      in  case kind of      in  case kind of
52             CFG.STOP => map pseudo_op (!data)             CFG.STOP => map pseudo_op (!data)
53          |  _ =>          |  _ =>
54          let val block = F.BBLOCK{blknum  =i,          let fun filter(CFG.LIVEOUT _::an,an') = filter(an,an')
55                  | filter(a::an,an') = filter(an,a::an')
56                  | filter([],an') = an'
57                val block = F.BBLOCK{blknum      = i,
58                                     freq        = freq,
59                                     annotations = ref(filter(!annotations,[])),
60                                   name    =name,                                   name    =name,
61                                   insns   =ref(! insns),                                   insns       = insns,
62                                   liveIn  =ref F.C.empty,                                   liveIn  =ref F.C.empty,
63                                   liveOut =ref (CFG.liveOut b),                                   liveOut =ref (CFG.liveOut b),
64                                   pred    =ref [],                                   pred    =ref [],
# Line 72  Line 77 
77      end      end
78    
79          (* create a new ENTRY with id i *)          (* create a new ENTRY with id i *)
80      fun entry(M,i) =      fun entry(M,i,freq) =
81      let val entry = F.ENTRY{succ=ref [], blknum=i}      let val entry = F.ENTRY{succ=ref [], blknum=i, freq=freq}
82      in  A.update(M,i,entry);      in  A.update(M,i,entry);
83          entry          entry
84      end      end
85    
86      fun entry'(M,M',M'',i,id) =      fun entry'(M,M',M'',i,id,freq) =
87      let val entry = entry(M,i)      let val entry = entry(M,i,freq)
88      in  A.update(M',i,id); A.update(M'',id,i); entry      in  A.update(M',i,id); A.update(M'',id,i); entry
89      end      end
90    
91          (* create a new EXIT with id i *)          (* create a new EXIT with id i *)
92      fun exit(M,i) =      fun exit(M,i,freq) =
93      let val exit = F.EXIT{pred=ref [], blknum=i}      let val exit = F.EXIT{pred=ref [], blknum=i, freq=freq}
94      in  A.update(M,i,exit);      in  A.update(M,i,exit);
95          exit          exit
96      end      end
97    
98      fun exit'(M,M',M'',i,id) =      fun exit'(M,M',M'',i,id,freq) =
99      let val exit = exit(M,i)      let val exit = exit(M,i,freq)
100      in  A.update(M',i,id); A.update(M'',id,i); exit      in  A.update(M',i,id); A.update(M'',id,i); exit
101      end      end
102    
# Line 100  Line 105 
105        | id_of(F.EXIT{blknum,...})   = blknum        | id_of(F.EXIT{blknum,...})   = blknum
106    
107      fun delete_preentries (ENTRY,G.GRAPH cfg) =      fun delete_preentries (ENTRY,G.GRAPH cfg) =
108      let fun remove (ENTRY,i,_) =      let val CFG.INFO{regmap=ref regmap,...} = #graph_info cfg
109              let val CFG.BLOCK{kind,insns,...} = #node_info cfg i          fun remove (ENTRY,i,_) =
110                let val block as CFG.BLOCK{kind,insns,...} = #node_info cfg i
111              in  if kind = CFG.FUNCTION_ENTRY then              in  if kind = CFG.FUNCTION_ENTRY then
112                     let val out_edges = #out_edges cfg i                     let val out_edges = #out_edges cfg i
113                         val out_edges' = map (fn (i,j,e)=>(ENTRY,j,e)) out_edges                         val out_edges' = map (fn (i,j,e)=>(ENTRY,j,e)) out_edges
114                     in  case !insns of                     in  case !insns of
115                            [] => ()                            [] => ()
116                         |  _  => error "delete_preentries";                         |  _  => (print (CFG.show_block regmap block);
117                                     error "delete_preentries");
118                         app (#add_edge cfg) out_edges';                         app (#add_edge cfg) out_edges';
119                         #remove_node cfg i                         #remove_node cfg i
120                     end                     end
# Line 119  Line 126 
126      fun remove_entry_to_exit (ENTRY,EXIT,CFG) =      fun remove_entry_to_exit (ENTRY,EXIT,CFG) =
127          Graph.remove_edge CFG (ENTRY,EXIT)          Graph.remove_edge CFG (ENTRY,EXIT)
128    
129        fun freqOf (G.GRAPH cfg) id =
130            let val CFG.BLOCK{freq,...} = #node_info cfg id in freq end
131    
132         (*         (*
133          * Convert cfg -> cluster, assuming the layout is unchanged          * Convert cfg -> cluster, assuming the layout is unchanged
134          *)          *)
135      fun computeOldLayout (CFG as G.GRAPH cfg) =      fun computeOldLayout (CFG as G.GRAPH cfg) =
136      let val M       = #capacity cfg ()      let val M       = #capacity cfg ()
137          val [ENTRY] = #entries cfg ()          val ENTRY   = case #entries cfg () of
138          val [EXIT]  = #exits cfg ()                          [ENTRY] => ENTRY
139          val regmap  = CFG.regmap CFG                        | _ => raise Graph.NotSingleEntry
140            val EXIT    = case #exits cfg () of
141                            [EXIT] => EXIT
142                          | _ => raise Graph.NotSingleExit
143            val CFG.INFO{regmap,annotations,...} = #graph_info cfg
144          val _       = delete_preentries(ENTRY,CFG)          val _       = delete_preentries(ENTRY,CFG)
145          val _       = remove_entry_to_exit(ENTRY,EXIT,CFG)          val _       = remove_entry_to_exit(ENTRY,EXIT,CFG)
146          val A       = A.array(M,F.ORDERED [])          val A       = A.array(M,F.LABEL(Label.newLabel ""))
147          val nodes   = List.filter(fn (i,CFG.BLOCK{kind,...}) =>          val nodes   = List.filter(fn (i,CFG.BLOCK{kind,...}) =>
148                             i <> ENTRY andalso i <> EXIT andalso                             i <> ENTRY andalso i <> EXIT andalso
149                             kind <> CFG.FUNCTION_ENTRY)                             kind <> CFG.FUNCTION_ENTRY)
150                                   (#nodes cfg ())                                   (#nodes cfg ())
151          val blocks  = List.concat(          val blocks  = List.concat(
152                          map (bblock A) (nodes @ [(EXIT,#node_info cfg EXIT)]))                          map (bblock A) (nodes @ [(EXIT,#node_info cfg EXIT)]))
153          val entry   = entry (A,ENTRY)          val entry   = entry (A,ENTRY,freqOf CFG ENTRY)
154          val exit    = exit (A,EXIT)          val exit    = exit (A,EXIT,freqOf CFG EXIT)
155          fun succs i = map (fn i => A.sub(A,i)) (#succ cfg i)          fun succs i = map (fn (_,i,CFG.EDGE{w,...}) => (A.sub(A,i),w))
156          fun preds i = map (fn i => A.sub(A,i)) (#pred cfg i)                              (#out_edges cfg i)
157            fun preds i = map (fn (i,_,CFG.EDGE{w,...}) => (A.sub(A,i),w))
158                                (#in_edges cfg i)
159          fun set_links(F.BBLOCK{blknum,pred,succ,insns,...}) =          fun set_links(F.BBLOCK{blknum,pred,succ,insns,...}) =
160                    (pred := preds blknum; succ := succs blknum)                    (pred := preds blknum; succ := succs blknum)
161            | set_links(F.ENTRY{blknum,succ,...}) = succ := succs blknum            | set_links(F.ENTRY{blknum,succ,...}) = succ := succs blknum
# Line 147  Line 163 
163            | set_links _ = ()            | set_links _ = ()
164          val _ = A.app set_links A          val _ = A.app set_links A
165      in  F.CLUSTER{ blkCounter= ref M,      in  F.CLUSTER{ blkCounter= ref M,
166                     regmap    = regmap,                     regmap      = !regmap,
167                     blocks    = blocks,                     blocks    = blocks,
168                     entry     = entry,                     entry     = entry,
169                     exit      = exit                     exit        = exit,
170                       annotations = annotations
171                   }                   }
172      end      end
173    
# Line 159  Line 176 
176          *)          *)
177      fun computeNewLayout (CFG as G.GRAPH cfg) =      fun computeNewLayout (CFG as G.GRAPH cfg) =
178      let val M        = #capacity cfg ()      let val M        = #capacity cfg ()
179          val [ENTRY]  = #entries cfg ()          val ENTRY   = case #entries cfg () of
180          val [EXIT]   = #exits cfg ()                          [ENTRY] => ENTRY
181                          | _ => raise Graph.NotSingleEntry
182            val EXIT    = case #exits cfg () of
183                            [EXIT] => EXIT
184                          | _ => raise Graph.NotSingleExit
185          val _        = delete_preentries(ENTRY,CFG)          val _        = delete_preentries(ENTRY,CFG)
186          val CFG.INFO{firstBlock,regmap,...} = #graph_info cfg          val CFG.INFO{firstBlock,regmap=ref regmap,annotations,...} =
187          val A        = A.array(M,F.ORDERED []) (* new id -> F.block *)                 #graph_info cfg
188            val A        = A.array(M,F.LABEL(Label.newLabel "")) (* new id -> F.block *)
189          val A'       = A.array(M,~1)           (* new id -> old id *)          val A'       = A.array(M,~1)           (* new id -> old id *)
190          val A''      = A.array(M,~1)           (* old id -> new id *)          val A''      = A.array(M,~1)           (* old id -> new id *)
191          val min_pred = A.array(M,10000000)          val min_pred = A.array(M,10000000)
# Line 173  Line 195 
195          fun higher_freq(i,j) =          fun higher_freq(i,j) =
196              let val CFG.BLOCK{freq=w1,...} = #node_info cfg i              let val CFG.BLOCK{freq=w1,...} = #node_info cfg i
197                  val CFG.BLOCK{freq=w2,...} = #node_info cfg j                  val CFG.BLOCK{freq=w2,...} = #node_info cfg j
198              in  W.>(!w1,!w2)              in  !w1 > !w2
199              end              end
200    
201          fun older(i,j) = A.sub(min_pred,i) < A.sub(min_pred,j)          fun older(i,j) = A.sub(min_pred,i) < A.sub(min_pred,j)
# Line 237  Line 259 
259          val (id,blocks) = layout_all(0,(!firstBlock)::nodes,[])          val (id,blocks) = layout_all(0,(!firstBlock)::nodes,[])
260          (*val _ = print("M="^Int.toString M^ " id="^Int.toString id^"\n")*)          (*val _ = print("M="^Int.toString M^ " id="^Int.toString id^"\n")*)
261    
262          val exit    = exit'(A,A',A'',id,EXIT)          val exit    = exit'(A,A',A'',id,EXIT,freqOf CFG EXIT)
263          val entry   = entry'(A,A',A'',id+1,ENTRY)          val entry   = entry'(A,A',A'',id+1,ENTRY,freqOf CFG ENTRY)
264          val blocks  = blocks @ bblock A (EXIT,#node_info cfg EXIT)          val blocks  = blocks @ bblock A (EXIT,#node_info cfg EXIT)
265          fun succs i = map (fn i=> A.sub(A,A.sub(A'',i)))          fun succs i = map (fn (_,i,CFG.EDGE{w,...}) =>
266                                   (#succ cfg (A.sub(A',i)))                                 (A.sub(A,A.sub(A'',i)),w))
267          fun preds i = map (fn i=> A.sub(A,A.sub(A'',i)))                                   (#out_edges cfg (A.sub(A',i)))
268                                   (#pred cfg (A.sub(A',i)))          fun preds i = map (fn (i,_,CFG.EDGE{w,...}) =>
269                                   (A.sub(A,A.sub(A'',i)),w))
270                                     (#in_edges cfg (A.sub(A',i)))
271            local
272                val look = Intmap.map regmap
273            in  fun reglookup r = look r handle _ => r
274            end
275    
276          fun set_links(F.BBLOCK{blknum,pred,succ,insns,...}) =          fun set_links(F.BBLOCK{blknum,pred,succ,insns,...}) =
277              let fun isBackwardBranch(F.BBLOCK{blknum=next,...}::bs) =              let fun isBackwardBranch((F.BBLOCK{blknum=next,...},_)::bs) =
278                        next <= blknum orelse isBackwardBranch bs                        next <= blknum orelse isBackwardBranch bs
279                    | isBackwardBranch(_::bs) = isBackwardBranch bs                    | isBackwardBranch(_::bs) = isBackwardBranch bs
280                    | isBackwardBranch []     = false                    | isBackwardBranch []     = false
281              in  pred := preds blknum;              in  pred := preds blknum;
282                  succ := succs blknum;                  succ := succs blknum
                 case !insns of  
                   [] => ()  
                 | jmp::rest => insns :=  
                      patchBranch{instr=jmp,backwards=isBackwardBranch(!succ)}  
                     @rest  
283              end              end
284            | set_links(F.ENTRY{blknum,succ,...}) = succ := succs blknum            | set_links(F.ENTRY{blknum,succ,...}) = succ := succs blknum
285            | set_links(F.EXIT{blknum,pred,...})  = pred := preds blknum            | set_links(F.EXIT{blknum,pred,...})  = pred := preds blknum
# Line 267  Line 289 
289                     regmap    = regmap,                     regmap    = regmap,
290                     blocks    = blocks,                     blocks    = blocks,
291                     entry     = entry,                     entry     = entry,
292                     exit      = exit                     exit        = exit,
293                       annotations = annotations
294                   }                   }
295      end      end
296    
# Line 279  Line 302 
302    
303  end  end
304    
 (*  
  * $Log$  
  *)  

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

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