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

SCM Repository

[diderot] Diff of /branches/lamont_dev/src/compiler/IL/check-il-fn.sml
ViewVC logotype

Diff of /branches/lamont_dev/src/compiler/IL/check-il-fn.sml

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

revision 412, Sat Oct 16 15:19:19 2010 UTC revision 1640, Wed Nov 16 02:19:51 2011 UTC
# Line 1  Line 1 
1  (* check-il-fn.sml  (* check-il-fn.sml
2   *   *
3   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4   * All rights reserved.   * All rights reserved.
5   *   *
6   * Correctness checker for SSA-based ILs.   * Correctness checker for SSA-based ILs.
7     *
8     * TODO:
9     *      check that the state variables and method stateOut variables are all defined.
10   *)   *)
11    
12  signature OPERATOR_TY =  signature OPERATOR_TY =
# Line 14  Line 17 
17    (* returns the signature of an operator as (rng, dom). *)    (* returns the signature of an operator as (rng, dom). *)
18      val sigOf : rator -> ty * ty list      val sigOf : rator -> ty * ty list
19    
20    (* return the type of a CONS, where the argument types    (* return the type of a CONS, where the first argument is the annotated type
21     * are given.  Returns NONE if the argument types are     * and the second argument is the list of argument types.  Returns false if
22     * invalid for the IL.     * there is a type error.
23     *)     *)
24      val typeOfCons : ty list -> ty option      val typeOfCons : ty * ty list -> bool
25    
26    end    end
27    
# Line 31  Line 34 
34    
35    ) : sig    ) : sig
36    
37      (* check the program for type errors, etc.  The first argument will be used to
38       * identify the phase that the check follows and the return result will be true
39       * if any errors were detected.
40       *)
41        val check : string * IL.program -> bool
42    
43    end = struct    end = struct
44    
45      structure IL = IL      structure IL = IL
# Line 38  Line 47 
47      structure V = IL.Var      structure V = IL.Var
48      structure VSet = V.Set      structure VSet = V.Set
49    
50      (* forward analysis to determine the variables that are available in blocks *)
51        structure Avail = ForwardDFAFn (
52          struct
53    
54            structure IL = IL
55            type t = VSet.set
56    
57            val bottom = VSet.empty
58    
59            fun join inputs = List.foldl VSet.union bottom inputs
60    
61            fun transfer (input, nd as IL.ND{kind, ...}) = (case kind
62                   of IL.JOIN{phis, ...} => let
63                      (* add the lhs of the phi node.  We do not remove the rhs variables, since
64                       * after value numbering, they may have further uses.
65                       *)
66                        fun doPhi ((y, _), vs) = VSet.add(vs, y)
67                        val output = List.foldl doPhi input (!phis)
68                        in
69                          output
70                        end
71                    | IL.ASSIGN{stm=(y, _), ...} => VSet.add(input, y)
72                    | IL.MASSIGN{stm=(ys, _, _), ...} => VSet.addList(input, ys)
73                    | _ => input
74                   (* end case *))
75    
76            val same = VSet.equal
77    
78            fun toString vs = let
79                  fun f (v, []) = [IL.Var.toString v, "}"]
80                    | f (v, l) = IL.Var.toString v :: "," :: l
81                  in
82                    if VSet.isEmpty vs then "{}" else String.concat("{" :: VSet.foldl f [] vs)
83                  end
84    
85          end)
86    
87      datatype token      datatype token
88        = NL | S of string | V of IL.var | VTYS of IL.var list | TY of Ty.ty | TYS of Ty.ty list        = NL | S of string | A of Atom.atom | V of IL.var | VTYS of IL.var list
89          | TY of Ty.ty | TYS of Ty.ty list
90    
91      fun err errBuf toks = let      fun error errBuf toks = let
92            fun tok2str NL = "\n  ** "            fun tok2str NL = "\n  ** "
93              | tok2str (S s) = s              | tok2str (S s) = s
94                | tok2str (A s) = Atom.toString s
95              | tok2str (V x) = V.toString x              | tok2str (V x) = V.toString x
96              | tok2str (VTYS xs) = tok2str(TYS(List.map V.ty xs))              | tok2str (VTYS xs) = tok2str(TYS(List.map V.ty xs))
97              | tok2str (TY ty) = Ty.toString ty              | tok2str (TY ty) = Ty.toString ty
# Line 57  Line 105 
105                :: !errBuf                :: !errBuf
106            end            end
107    
108      fun chkAssign errFn (bvs, y, rhs) = let      fun checkAssign errFn ((y, rhs), bvs) = let
109            (* check a variable use *)
110            fun checkVar x = if VSet.member(bvs, x)            fun checkVar x = if VSet.member(bvs, x)
111                  then ()                  then ()
112                  else errFn [                  else errFn [
# Line 77  Line 126 
126                    ]                    ]
127                  else ();                  else ();
128                case rhs                case rhs
129                 of IL.VAR x => (                 of IL.STATE x =>
130                        if Ty.same(V.ty y, IL.StateVar.ty x)
131                          then ()
132                          else tyError (V.ty y, IL.StateVar.ty x)
133                    | IL.VAR x => (
134                      checkVar x;                      checkVar x;
135                      if Ty.same(V.ty y, V.ty x)                      if Ty.same(V.ty y, V.ty x)
136                        then ()                        then ()
137                        else tyError (V.ty y, V.ty x))                        else tyError (V.ty y, V.ty x))
138                  | IL.LIT lit => let                  | IL.LIT lit => let
139                      val ty = (case lit                      val ty = (case lit
140                             of Literal.Int _ => Ty.IntTy                             of Literal.Int _ => Ty.intTy
141                              | Literal.Float _ => Ty.realTy                              | Literal.Float _ => Ty.realTy
142                              | Literal.String _ => Ty.StringTy                              | Literal.String _ => Ty.StringTy
143                              | Literal.Bool _ => Ty.BoolTy                              | Literal.Bool _ => Ty.BoolTy
# Line 109  Line 162 
162                              NL, S "found:    ", VTYS xs                              NL, S "found:    ", VTYS xs
163                            ]                            ]
164                      end                      end
165                  | IL.CONS xs => (                  | IL.APPLY(name, xs) => () (* FIXME: need functor parameter for typing name *)
166                    | IL.CONS(ty, xs) => (
167                      List.app checkVar xs;                      List.app checkVar xs;
168                      case OpTy.typeOfCons (List.map V.ty xs)                      if OpTy.typeOfCons (ty, List.map V.ty xs)
169                       of NONE => errFn [S "invalid ", S(IL.assignToString(y, rhs))]                        then if Ty.same(V.ty y, ty)
                       | SOME ty => if Ty.same(V.ty y, ty)  
170                            then ()                            then ()
171                            else tyError (V.ty y, ty)                            else tyError (V.ty y, ty)
172                          else errFn [S "invalid ", S(IL.assignToString(y, rhs))]
173                      (* end case *))                      (* end case *))
174                (* end case *);                (* end case *);
175                VSet.add(bvs, y)                VSet.add(bvs, y)
176              end              end
177    
178      fun checkPhi errFn (bvs, y, xs) = let      fun checkMAssign errFn (stm as (ys, rator, xs), bvs) = let
179            (* check that a lhs variable is not bound twice *)
180              fun checkBind y = if VSet.member(bvs, y)
181                    then errFn [
182                        S "variable ", V y, S " is bound twice in", NL,
183                        S(IL.massignToString stm)
184                      ]
185                    else ()
186            (* check a variable use *)
187              fun checkVar x = if VSet.member(bvs, x)
188                    then ()
189                    else errFn [
190                        S "variable ", V x, S " is not bound in", NL,
191                        S(IL.massignToString stm)
192                      ]
193              fun tyError (ty1, ty2) = errFn [
194                      S "type mismatch in \"", S(IL.massignToString stm), S "\"",
195                      NL, S "lhs: ", TY ty1, NL, S "rhs: ", TY ty2
196                    ]
197              in
198                (* check that the lhs variables are not bound twice *)
199                  List.app checkBind ys;
200    (* FIXME:
201                (* check the types *)
202                  val (resTys, argTys) = OpTy.sigOf rator
203                  in
204                    List.app checkVar xs;
205                    if ListPair.allEq (fn (y, ty) => Ty.same(V.ty y, ty)) (ys, resTys)
206                      then ()
207                      else tyError (V.ty y, resTy);
208                    if ListPair.allEq (fn (x, ty) => Ty.same(V.ty x, ty)) (xs, argTys)
209                      then ()
210                      else errFn [
211                          S "argument type mismatch in \"", S(IL.massignToString stm), S "\"",
212                          NL, S "expected: ", TYS argTys,
213                          NL, S "found:    ", VTYS xs
214                        ]
215                  end
216    *)
217                  VSet.addList(bvs, ys)
218                end
219    
220        fun checkPhi errFn bvs (y, xs) = let
221            val ty = V.ty y            val ty = V.ty y
222            in            in
223            (* check that y is not bound twice *)            (* check that y is not bound twice *)
# Line 140  Line 236 
236                  ]                  ]
237            end            end
238    
239        fun check (phase, IL.Program{props, globalInit, initially, strands}) = let
240              val errBuf = ref []
241              val errFn = error errBuf
242              fun final () = (case !errBuf
243                     of [] => false
244                      | errs => (
245                          Log.msg(concat["********** IL Errors detected after ", phase, " **********\n"]);
246                          List.app (fn msg => Log.msg(msg ^ "\n")) (List.rev errs);
247                          true)
248                    (* end case *))
249              val checkPhi = checkPhi errFn
250              val checkAssign = checkAssign errFn
251              val checkMAssign = checkMAssign errFn
252              fun checkCFG (vs, cfg) = let
253                    val bvs = VSet.fromList vs
254                  (* compute the variables available on entry to each block *)
255                    val nodes = Avail.analyse (bvs, cfg)
256                    fun checkNd (nd as IL.ND{kind, ...}) = (case kind
257                           of IL.NULL => errFn [S "unexpected ", S(IL.Node.toString nd)]
258                            | IL.JOIN{phis, ...} =>
259                                List.app (checkPhi (VSet.union(Avail.inValue nd, bvs))) (!phis)
260                            | IL.COND{cond, ...} =>
261                                if VSet.member(Avail.inValue nd, cond)
262                                orelse VSet.member(bvs, cond)
263                                  then ()
264                                  else errFn [S "unbound variable ", V cond, S " in conditional"]
265                            | IL.ASSIGN{stm, ...} =>
266                                ignore (checkAssign (stm, VSet.union(Avail.inValue nd, bvs)))
267                            | IL.MASSIGN{stm, ...} =>
268                                ignore (checkMAssign (stm, VSet.union(Avail.inValue nd, bvs)))
269                            | IL.NEW{strand, args, ...} => let
270                                val bvs = VSet.union(Avail.inValue nd, bvs)
271                              (* check a variable use *)
272                                fun checkVar x = if VSet.member(bvs, x)
273                                      then ()
274                                      else errFn [
275                                          S "variable ", V x, S " is not bound in new ",
276                                          S(Atom.toString strand)
277                                        ]
278                                in
279                                  List.app checkVar args
280                                end
281                            | IL.SAVE{lhs, rhs, ...} => let
282                                val bvs = VSet.union(Avail.inValue nd, bvs)
283                                in
284                                  if VSet.member(bvs, rhs)
285                                    then ()
286                                    else errFn [
287                                        S "variable ", V rhs, S " is not bound in save ",
288                                        S(IL.StateVar.toString lhs)
289                                      ];
290                                  if Ty.same(IL.StateVar.ty lhs, V.ty rhs)
291                                    then ()
292                                    else errFn [
293                                        S "type mismatch in \"", S(IL.StateVar.toString lhs),
294                                        S " = ", S(V.toString rhs), S "\"",
295                                        NL, S "lhs: ", TY(IL.StateVar.ty lhs),
296                                        NL, S "rhs: ", TY(V.ty rhs)
297                                      ]
298                                end
299                            | _ => ()
300                          (* end case *))
301                    in
302                      List.app checkNd nodes;
303                    (* cleanup *)
304                      Avail.scrub nodes
305                    end
306            (* the globals are those variables that are live at the exit of the global initialization *)
307              val globals = IL.CFG.liveAtExit globalInit
308            (* check a strand definition *)
309              fun checkStrand (IL.Strand{name, params, state, stateInit, methods}) = let
310                    val nStateVars = List.length state
311                    val extraVars = params @ globals
312                    fun checkMethod (IL.Method{name, body, ...}) = checkCFG (extraVars, body)
313    (*DEBUG*)handle ex => raise ex
314                    in
315                      checkCFG (extraVars, stateInit)
316    (*DEBUG*)handle ex => raise ex;
317                      List.app checkMethod methods
318                    end
319            (* handle exceptions *)
320              fun onExn exn = errFn [S "uncaught exception: ", S(exnMessage exn)]
321              in
322              (* check the global part *)
323                checkCFG ([], globalInit) handle ex => onExn ex;
324    (* FIXME: need to check initially *)
325              (* check the strands *)
326                (List.app checkStrand strands) handle ex => onExn ex;
327              (* check for errors *)
328                final()
329              end
330    
331    end    end

Legend:
Removed from v.412  
changed lines
  Added in v.1640

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