Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Diff of /trunk/src/compiler/IL/translate-fn.sml
ViewVC logotype

Diff of /trunk/src/compiler/IL/translate-fn.sml

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

revision 1115, Thu May 5 04:42:18 2011 UTC revision 1116, Thu May 5 04:49:02 2011 UTC
# Line 5  Line 5 
5   *   *
6   * This functor supports the common parts of translating between different   * This functor supports the common parts of translating between different
7   * instances of the SSA-based ILs (e.g., from HighIL to MidIL).   * instances of the SSA-based ILs (e.g., from HighIL to MidIL).
8     *
9     * FIXME: the handling of global variables needs more care.  For example, when translating from
10     * HighIL to LowIL, field variables go away, but are replaced by the underlying image variable
11     * in many uses.  If the image variable was not a user-defined global, then it is not visible
12     * to the strand method code, which causes a IL check failure.
13     *
14     * FIXME: both this code and the Census code sets the bindings of variables (but the translation
15     * from SimpleAST does not).
16   *)   *)
17    
18  signature TRANSLATE_PARAMS =  signature TRANSLATE_PARAMS =
# Line 16  Line 24 
24      type var_env = DstIL.var SrcIL.Var.Tbl.hash_table      type var_env = DstIL.var SrcIL.Var.Tbl.hash_table
25    
26      val rename : (var_env * SrcIL.var) -> DstIL.var      val rename : (var_env * SrcIL.var) -> DstIL.var
27      val expand : (var_env * SrcIL.assign) -> DstIL.assign list      val renameList : (var_env * SrcIL.var list) -> DstIL.var list
28        val expand : (var_env * SrcIL.assign) -> DstIL.cfg
29    
30    end    end
31    
# Line 25  Line 34 
34      structure SrcIL : SSA      structure SrcIL : SSA
35      structure DstIL : SSA      structure DstIL : SSA
36    
37      type var_env = DstIL.var SrcIL.Var.Tbl.hash_table      type var_env = Params.var_env
38    
39      val translate : var_env * SrcIL.stmt -> DstIL.stmt      val translate : SrcIL.program -> DstIL.program
40    
41    end = struct    end = struct
42    
43      structure SrcIL : SSA = Params.SrcIL      structure SrcIL = Params.SrcIL
44      structure SrcNd = SrcIL.Node      structure SrcNd = SrcIL.Node
45      structure DstIL : SSA = Params.DstIL      structure VTbl = SrcIL.Var.Tbl
46        structure DstIL = Params.DstIL
47      structure DstNd = DstIL.Node      structure DstNd = DstIL.Node
48      structure DstStm = DstIL.Stmt      structure DstCFG = DstIL.CFG
49    
50      type var_env = Params.var_env      type var_env = Params.var_env
51    
# Line 46  Line 56 
56    
57      fun rename (E{vMap, ...}) x = Params.rename(vMap, x)      fun rename (E{vMap, ...}) x = Params.rename(vMap, x)
58    
59      fun expand (E{vMap, ...}) (assign, assigns') =      fun renameList (E{vMap, ...}, xs) = Params.renameList(vMap, xs)
60            Params.expand (vMap, assign) @ assigns'  
61        fun expand (E{vMap, ...}, assign) = Params.expand (vMap, assign)
62    
63      fun insertNd (E{ndMap, ...}, id, nd) = Stamp.Tbl.insert ndMap (id, nd)      fun insertNd (E{ndMap, ...}, id, nd) = Stamp.Tbl.insert ndMap (id, nd)
64    
65        fun findNd (E{ndMap, ...}) = Stamp.Tbl.find ndMap
66    
67      fun renameNd (E{ndMap, ...}) (nd as SrcIL.ND{id, ...}) = (      fun renameNd (E{ndMap, ...}) (nd as SrcIL.ND{id, ...}) = (
68            case Stamp.Tbl.find ndMap id            case Stamp.Tbl.find ndMap id
69             of SOME nd' => nd'             of SOME nd' => nd'
70              | NONE => raise Fail("unable to find " ^ SrcNd.toString nd)              | NONE => raise Fail("unable to find " ^ SrcNd.toString nd)
71            (* end case *))            (* end case *))
72    
73    (* the first pass creates the nodes of the DstIL CFG and defines      fun translateCFG (env, SrcIL.CFG{entry, exit}) = let
74     * the environment that maps from SrcIL nodes and variables to            val findNd = findNd env
75     * DstIL nodes and variables.            fun trans (srcNd as SrcIL.ND{id, kind, ...}) = let
76     *)                  fun newNd nd = (insertNd (env, id, nd); nd)
77      fun translateNodes (env, stm) = let                  in
78            fun trans (SrcIL.ND{id, kind, ...}) = let                    case findNd id
79                  val newNd = (case kind                     of SOME nd => nd
80                        | NONE => (case kind
81                       of SrcIL.NULL => raise Fail "unexpected NULL node"                       of SrcIL.NULL => raise Fail "unexpected NULL node"
82                        | SrcIL.ENTRY _ => DstNd.mkENTRY()                            | SrcIL.ENTRY{succ} => let
83                        | SrcIL.JOIN{phis, ...} => let                                val nd = newNd (DstNd.mkENTRY())
                           fun cvtPhi (x, xs) =  
                                 (rename env x, List.map (rename env) xs)  
84                            in                            in
85                              DstNd.mkJOIN(List.map cvtPhi (!phis))                                  DstNd.addEdge (nd, trans (!succ));
86                                    nd
87                            end                            end
88                        | SrcIL.COND{cond, ...} => DstNd.mkCOND{                            | SrcIL.JOIN{phis, succ, ...} => let
89                                  fun cvtPhi (x, xs) = let
90                                        val x = rename env x
91                                        val xs = List.map (rename env) xs
92                                        in
93                                          DstIL.Var.setBinding (x, DstIL.VB_PHI xs);
94                                          (x, xs)
95                                        end
96                                  val nd = newNd (DstNd.mkJOIN(List.map cvtPhi (!phis)))
97                                  in
98                                    DstNd.addEdge (nd, trans (!succ));
99                                    nd
100                                  end
101                              | SrcIL.COND{cond, trueBranch, falseBranch, ...} => let
102                                  val nd = newNd (DstNd.mkCOND{
103                              cond = rename env cond,                              cond = rename env cond,
104                              trueBranch = DstNd.dummy,                              trueBranch = DstNd.dummy,
105                              falseBranch = DstNd.dummy                              falseBranch = DstNd.dummy
106                            }                                      })
107                        | SrcIL.BLOCK{body, ...} => let                                val trueB = trans (!trueBranch)
108                            val body' = List.foldr (expand env) [] (!body)                                val _ = (DstNd.setTrueBranch (nd, trueB); DstNd.setPred(trueB, nd))
109                            in                                val falseB = trans (!falseBranch)
110                              DstNd.mkBLOCK body'                                val _ = (DstNd.setFalseBranch (nd, falseB); DstNd.setPred(falseB, nd))
111                                  in
112                                    nd
113                                  end
114                              | SrcIL.COM{text, succ, ...} => let
115                                  val nd = newNd (DstNd.mkCOM text)
116                                  in
117                                    DstNd.addEdge (nd, trans (!succ));
118                                    nd
119                                  end
120                              | SrcIL.ASSIGN{stm, succ, ...} => let
121                                  val cfg = expand (env, stm)
122                                  in
123                                    if DstCFG.isEmpty cfg
124                                      then trans (!succ)
125                                      else (
126                                        DstNd.addEdge (DstCFG.exit cfg, trans (!succ));
127                                        DstCFG.entry cfg)
128                            end                            end
129                        | SrcIL.NEW{strand, args, ...} => DstNd.mkNEW{                            | SrcIL.NEW{strand, args, succ, ...} => let
130                                  val nd = newNd (DstNd.mkNEW{
131                              strand = strand,                              strand = strand,
132                              args = List.map (rename env) args                              args = List.map (rename env) args
133                            }                                      })
                       | SrcIL.DIE _ => DstNd.mkDIE()  
                       | SrcIL.STABILIZE _ => DstNd.mkSTABILIZE()  
                       | SrcIL.EXIT _ => DstNd.mkEXIT()  
                    (* end case *))  
                 in  
                   insertNd (env, id, newNd)  
                 end  
           in  
             SrcIL.applyToNodes trans stm  
           end  
   
   (* the second pass copys the statement tree and sets the CFG edges; it  
    * returns the new statement tree.  
    *)  
     fun translateStmts (env, stm) = let  
           val renameNd = renameNd env  
         (* set the CFG edges of the node corresponding to the source node *)  
           fun setEdges (srcNd as SrcIL.ND{kind, ...}) = let  
                 val dstNd as DstIL.ND{kind=dstKind, ...} = renameNd srcNd  
134                  in                  in
135                    case kind                                  DstNd.addEdge (nd, trans (!succ));
136                     of SrcIL.NULL => raise Fail "unexpected NULL node"                                  nd
                     | SrcIL.ENTRY{succ} => DstNd.setSucc(dstNd, renameNd(!succ))  
                     | SrcIL.JOIN{preds, succ, ...} => let  
                         val DstIL.JOIN{preds=dstPreds, ...} = dstKind  
                         in  
                           dstPreds := List.map renameNd (!preds);  
                           DstNd.setSucc (dstNd, renameNd(!succ))  
                         end  
                     | SrcIL.COND{pred, trueBranch, falseBranch, ...} => (  
                         DstNd.setPred (dstNd, renameNd(!pred));  
                         DstNd.setTrueBranch (dstNd, renameNd(!trueBranch));  
                         DstNd.setFalseBranch (dstNd, renameNd(!falseBranch)))  
                     | SrcIL.BLOCK{pred, succ, ...} => (  
                         DstNd.setPred (dstNd, renameNd(!pred));  
                         DstNd.setSucc (dstNd, renameNd(!succ)))  
                     | SrcIL.NEW{pred, succ, ...} => (  
                         DstNd.setPred (dstNd, renameNd(!pred));  
                         DstNd.setSucc (dstNd, renameNd(!succ)))  
                     | SrcIL.DIE{pred} => DstNd.setPred (dstNd, renameNd(!pred))  
                     | SrcIL.STABILIZE{pred} => DstNd.setPred (dstNd, renameNd(!pred))  
                     | SrcIL.EXIT{pred} => DstNd.setPred (dstNd, renameNd(!pred))  
                   (* end case *)  
137                  end                  end
138          (* translate statements *)                            | SrcIL.EXIT{kind, live, ...} =>
139            fun trans (SrcIL.STM{kind, next, ...}) = let                                newNd (DstNd.mkEXIT(kind, List.map (rename env) live))
140                  fun new kind' = DstStm.new(kind', Option.map trans next)                         (* end case *))
                 in  
                   case kind  
                    of SrcIL.S_SIMPLE nd => new (DstIL.S_SIMPLE(renameNd nd))  
                     | SrcIL.S_IF{cond, thenBranch, elseBranch} => new (DstIL.S_IF{  
                           cond = renameNd cond,  
                           thenBranch = trans thenBranch,  
                           elseBranch = trans elseBranch  
                         })  
                     | SrcIL.S_LOOP{hdr, cond, body} => new (DstIL.S_LOOP{  
                           hdr = trans hdr,  
                           cond = renameNd cond,  
                           body = trans body  
                         })  
141                    (* end case *)                    (* end case *)
142                  end                  end
143              val entry = trans entry
144              val exit = (case findNd (SrcNd.id exit)
145                     of SOME nd => nd
146                      | NONE => DstNd.mkACTIVE[]    (* exit is unreachable *)
147                    (* end case *))
148            in            in
149              SrcIL.applyToNodes setEdges stm;              DstIL.CFG{entry = entry, exit = exit}
             trans stm  
150            end            end
151    
152      fun translate (vMap, stm) = let      fun translate (SrcIL.Program{globalInit, initially, strands}) = let
153            val env = E{            val env = E{
154                    ndMap = Stamp.Tbl.mkTable (256, Fail "ndMap"),                    ndMap = Stamp.Tbl.mkTable (256, Fail "ndMap"),
155                    vMap = vMap                    vMap = VTbl.mkTable (256, Fail "env")
156                    }
157              fun transInitially (SrcIL.Initially{isArray, rangeInit, iters, create}) = let
158                    val (argInit, strand, args) = create
159                    fun trIter (param, lo, hi) = let
160                          val param = rename env param
161                          in
162                            DstIL.Var.setBinding(param, DstIL.VB_PARAM);
163                            (param, rename env lo, rename env hi)
164                          end
165                    val iters = List.map trIter iters
166                    in
167                      DstIL.Initially{
168                          isArray = isArray,
169                          rangeInit = translateCFG (env, rangeInit),
170                          create = (translateCFG (env, argInit), strand, renameList(env, args)),
171                          iters = iters
172                        }
173                    end
174              fun transMethod state (SrcIL.Method{name, stateIn, body}) = let
175                    val stateIn = renameList (env, stateIn)
176                    in
177                      ListPair.app
178                        (fn (x, (_, x')) => DstIL.Var.setBinding(x, DstIL.VB_RHS(DstIL.VAR x')))
179                          (stateIn, state);
180                      DstIL.Method{
181                          name = name,
182                          stateIn = stateIn,
183                          body = translateCFG (env, body)
184                        }
185                    end
186              fun transStrand (SrcIL.Strand{name, params, state, stateInit, methods}) = let
187                    val params = renameList (env, params)
188                    val state = List.map (fn (isOut, x) => (isOut, rename env x)) state
189                    in
190                      List.app (fn x => DstIL.Var.setBinding(x, DstIL.VB_PARAM)) params;
191                      DstIL.Strand{
192                          name = name,
193                          params = params,
194                          state = state,
195                          stateInit = translateCFG (env, stateInit),
196                          methods = List.map (transMethod state) methods
197                        }
198                    end
199              val prog = DstIL.Program{
200                      globalInit = translateCFG (env, globalInit),
201                      initially = transInitially initially,
202                      strands = List.map transStrand strands
203                  }                  }
           val _ = translateNodes (env, stm)  
204            in            in
205              translateStmts (env, stm)              prog
206            end            end
207    
208    end    end

Legend:
Removed from v.1115  
changed lines
  Added in v.1116

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