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

SCM Repository

[diderot] Diff of /branches/pure-cfg/src/compiler/codegen/low-to-tree.sml
ViewVC logotype

Diff of /branches/pure-cfg/src/compiler/codegen/low-to-tree.sml

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

revision 529, Mon Feb 14 15:03:54 2011 UTC revision 530, Mon Feb 14 16:34:57 2011 UTC
# Line 2  Line 2 
2   *   *
3   * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)   * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4   * All rights reserved.   * All rights reserved.
5     *
6     * This module translates the LowIL representation of a program (i.e., a pure CFG) to
7     * a block-structured AST with nested expressions.
8     *
9     * NOTE: this translation is pretty dumb about variable coalescing (i.e., it doesn't do any).
10   *)   *)
11    
12  structure LowToTree : sig  structure LowToTree : sig
# Line 38  Line 43 
43      fun newLocal x = newVar (genName(V.name x), T.VK_Local, V.ty x)      fun newLocal x = newVar (genName(V.name x), T.VK_Local, V.ty x)
44      end      end
45    
46    (* a property to map global IL variables to tree IL variables *)    (* an environment that tracks bindings of variables to target expressions and the list
47       * of locals that have been defined.
48       *)
49      local      local
50        val {peekFn : IL.var -> T.var option, setFn, ...} = V.newProp (fn _ => raise Fail "global prop")        structure VT = V.Tbl
51      in        fun decCount (IL.V{useCnt, ...}) = let
52      fun isGlobal x = (case peekFn x of NONE => false | _ => true)              val n = !useCnt - 1
53      fun markGlobal (x, x') = setFn (x, x')              in
54      fun toTreeGlobal x = (case peekFn x                useCnt := n;  (n <= 0)
55             of SOME x' => x'              end
56              | _ => raise Fail(concat["toTreeGlobal(", V.toString x, ")"])        datatype target_binding
57            (* end case *))          = GLOB of T.var         (* variable is global *)
58      end          | TREE of T.exp         (* variable bound to target expression tree *)
59            | DEF of T.exp          (* either a target variable or constant for a defined variable *)
60    (* an environment for treeification *)        datatype env = E of {
61      fun env = E of {            tbl : target_binding VT.hash_table,
         vdef : T.exp V.Map.map,  
62          locals : T.var list          locals : T.var list
63        }        }
64          fun peekGlobal (E{tbl, ...}, x) = (case VT.find tbl x
65                 of GLOB x' => SOME x'
66                  | _ => NONE
67                (* end case *))
68        in
69      (* use a variable.  If it is a pending expression, we decrement its use count *)
70        fun useVar (E{tbl, ...}) x = (case VT.find tbl x
71               of SOME(GLOB x') => T.E_Var x'
72                | SOME(TREE e) => (
73                    if (decCount x) then VT.remove tbl x else ();
74                    e)
75                | SOME(DEF e) => e
76              (* end case *))
77    
78      fun addLocal (E{vdef, locals}, x) = E{vdef=vdef, locals=x::locals}    (* record a local variable *)
79        fun addLocal (E{tbl, locals}, x) = E{tbl=tbl, locals=x::locals}
     fun insert (E{vdef, locals}, x, exp) = E{vdef=V.Map.insert(vdef, x, exp), locals=locals}  
80    
81      fun lookup (E{vdef, ...}) x = (case V.Map.find(vdef, x)      fun insert (env as E{tbl, ...}, x, exp) = (
82             of SOME exp => exp            VT.insert tbl (x, TREE exp);
83              | NONE => raise Fail(concat["LowIL variable ", V.toString x, " is not defined"])            env)
84            (* end case *))  
85        fun rename (env as E{tbl, ...}, x, x') = (
86              VT.insert tbl (x, DEF(T.E_Var x));
87              env)
88    
89      fun bind (env, lhs, rhs) = (case peekGlobal lhs      fun bind (env, lhs, rhs) = (case peekGlobal (env, lhs)
90             of SOME x => (insert(env, lhs, T.E_Var x), [T.S_Assign(x, rhs)])             of SOME x => (rename(env, lhs, x), [T.S_Assign(x, rhs)])
91              | NONE => if (V.useCount lhs = 1)              | NONE => if (V.useCount lhs = 1)
92                  then (insert(env, lhs, rhs), [])                  then (insert(env, lhs, rhs), [])
93                  else let                  else let
94                    val t = newLocal lhs                    val t = newLocal lhs
95                    in                    in
96                      (insert(env, lhs, T.E_Var t), [T.S_Assign(t, rhs)])                      (rename(env, lhs, t), [T.S_Assign(t, rhs)])
97                    end                    end
98            (* end case *))            (* end case *))
99    
100      fun setDef (env, lhs, rhs) = (case peekGlobal lhs      fun setDef (env, lhs, rhs) = (case peekGlobal (env, lhs)
101             of SOME x => (insert(env, lhs, T.E_Var x), [T.S_Assign(x, rhs)])             of SOME x => (rename(env, lhs, x), [T.S_Assign(x, rhs)])
102              | NONE => (insert(env, lhs, rhs), [])              | NONE => (insert(env, lhs, rhs), [])
103            (* end case *))            (* end case *))
104    
105      (* at the end of a block, we need to assign any pending expressions to locals.  The
106       * blkStms list and the resulting statement list are in reverse order.
107       *)
108        fun endBlock (E{tbl, locals}, blkStms) = let
109              fun doVar (x, TREE e, (locals, stms)) = let
110                     val t = newLocal x
111                      in
112                        VT.insert tbl (x, DEF(T.E_Var t));
113                        (t::locals, T.S_Assign(t, rhs)::stms)
114                      end
115              val (locals, stms) = VT.foldi doVar blkStms tbl
116              in
117                (E{tbl=tbl, locals=locals}, stms)
118              end
119    
120        fun doPhi ((lhs, rhs), (env, predBlks : T.stm list list)) = let
121              val t = newLocal lhs
122              val predBlks = ListPair.map
123                    (fn (x, stms) => T.Assign(t, useVar env x)::stms)
124                      (rhs, predBlks)
125              in
126                (rename (env, lhs, t), preBlks)
127              end
128    
129        end
130    
131    (* translate a LowIL assignment to a list of zero or more target statements *)    (* translate a LowIL assignment to a list of zero or more target statements *)
132      fun doAssign (env, lhs, rhs) = (case rhs      fun doAssign (env, lhs, rhs) = (case rhs
133             of IL.VAR x => setDef (lookup env x)             of IL.VAR x => setDef (useVar env x)
134              | IL.LIT lit => setDef (T.E_Lit lit)              | IL.LIT lit => setDef (T.E_Lit lit)
135              | IL.OP(rator, args) =>              | IL.OP(rator, args) =>
136                  bind (env, lhs, T.E_Op(rator, List.map (lookup env) args))                  bind (env, lhs, T.E_Op(rator, List.map (useVar env) args))
137              | IL.CONS args => let              | IL.CONS args => let
138                (* we give cons expressions names, since not all targets support them inline *)                (* we give cons expressions names, since not all targets support them inline *)
139                  val t = newLocal lhs                  val t = newLocal lhs
140                  val rhs = T.E_Cons(List.map (lookup env) args)                  val rhs = T.E_Cons(List.map (useVar env) args)
141                  in                  in
142                    (insert(env, lhs, T.E_Var t), [T.S_Assign(t, rhs)])                    (rename(env, lhs, t), [T.S_Assign(t, rhs)])
143                  end                  end
144            (* end case *))            (* end case *))
145    
# Line 103  Line 150 
150                    | IL.JOIN{phis, succ, ...} => ifCont (stms, Nd.kind nd)                    | IL.JOIN{phis, succ, ...} => ifCont (stms, Nd.kind nd)
151                    | IL.COND{cond, trueBranch, falseBranch, ...} => let                    | IL.COND{cond, trueBranch, falseBranch, ...} => let
152                        fun kThen (stms', _) = let                        fun kThen (stms', _) = let
153                              val thenBlk = T.Stmt.block (List.rev stms')                              val (env, thenBlk) = endBlock (env, stms')
154                              fun kElse (stms', IL.JOIN{phis, succ, ...}) = let                              fun kElse (stms', IL.JOIN{phis, succ, ...}) = let
155                                      val (env, elseBlk) = endBlock (env, stms')
156                                      val (env, [thenBlk, elseBlk]) =
157                                            List.foldl doPhi (env, [thenBlk, elseBlk]) (!phis)
158                                    val stm = T.Stmt.ifthenelse (                                    val stm = T.Stmt.ifthenelse (
159                                          lookup env cond,                                          useVar env cond,
160                                          thenBlk,                                          T.mkBlock (List.rev thenBlk),
161                                          T.Stmt.block (List.rev stms'))                                          T.mkBlock (List.rev elseBlk))
162                                    in                                    in
 (* FIXME: what do we do about phis? *)  
163                                      doNode (env, ifCont, stm::stms, !succ)                                      doNode (env, ifCont, stm::stms, !succ)
164                                    end                                    end
165                              in                              in

Legend:
Removed from v.529  
changed lines
  Added in v.530

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