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

SCM Repository

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

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

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

revision 414, Sat Oct 16 18:00:43 2010 UTC revision 417, Sun Oct 17 00:32:30 2010 UTC
# Line 4  Line 4 
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 44  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, IL.ND{kind, ...}) = (case kind
62                   of IL.NULL => raise Fail "unexpected NULL"
63                    | IL.JOIN{phis, ...} => let
64                      (* add the lhs of the phi node, while removing the rhs variables *)
65                        fun doPhi ((y, xs), vs) =
66                              VSet.add(
67                                VSet.difference(vs, VSet.fromList xs),
68                                y)
69                        in
70                          List.foldl doPhi input (!phis)
71                        end
72                    | IL.BLOCK{body, ...} => let
73                        fun doAssign ((y, _), vs) = VSet.add(vs, y)
74                        in
75                          List.foldl doAssign input (!body)
76                        end
77                    | _ => input
78                   (* end case *))
79    
80            val same = VSet.equal
81    
82            fun toString vs = let
83                  fun f (v, []) = [IL.Var.toString v, "}"]
84                    | f (v, l) = IL.Var.toString v :: "," :: l
85                  in
86                    if VSet.isEmpty vs then "{}" else String.concat("{" :: VSet.foldl f [] vs)
87                  end
88    
89          end)
90    
91      datatype token      datatype token
92        = 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 | V of IL.var | VTYS of IL.var list | TY of Ty.ty | TYS of Ty.ty list
93    
# Line 63  Line 107 
107                :: !errBuf                :: !errBuf
108            end            end
109    
110      fun chkAssign errFn (bvs, y, rhs) = let  
111        fun checkAssign errFn ((y, rhs), bvs) = let
112            (* check a variable use *)
113            fun checkVar x = if VSet.member(bvs, x)            fun checkVar x = if VSet.member(bvs, x)
114                  then ()                  then ()
115                  else errFn [                  else errFn [
# Line 90  Line 136 
136                        else tyError (V.ty y, V.ty x))                        else tyError (V.ty y, V.ty x))
137                  | IL.LIT lit => let                  | IL.LIT lit => let
138                      val ty = (case lit                      val ty = (case lit
139                             of Literal.Int _ => Ty.IntTy                             of Literal.Int _ => Ty.intTy
140                              | Literal.Float _ => Ty.realTy                              | Literal.Float _ => Ty.realTy
141                              | Literal.String _ => Ty.StringTy                              | Literal.String _ => Ty.StringTy
142                              | Literal.Bool _ => Ty.BoolTy                              | Literal.Bool _ => Ty.BoolTy
# Line 127  Line 173 
173                VSet.add(bvs, y)                VSet.add(bvs, y)
174              end              end
175    
176      fun checkPhi errFn (bvs, y, xs) = let      fun checkPhi errFn bvs (y, xs) = let
177            val ty = V.ty y            val ty = V.ty y
178            in            in
179            (* check that y is not bound twice *)            (* check that y is not bound twice *)
# Line 156  Line 202 
202                        List.app (fn msg => Log.msg(msg ^ "\n")) (List.rev errs);                        List.app (fn msg => Log.msg(msg ^ "\n")) (List.rev errs);
203                        true)                        true)
204                  (* end case *))                  (* end case *))
205              val checkPhi = checkPhi errFn
206              val checkAssign = checkAssign errFn
207              fun checkStmt (vs, stm) = let
208                    val bvs = VSet.fromList vs
209                  (* compute the variables available on entry to each block *)
210                    val nodes = Avail.analyse (bvs, stm)
211                    fun checkNd (nd as IL.ND{kind, ...}) = (case kind
212                           of IL.NULL => raise Fail "unexpected NULL"
213                            | IL.JOIN{phis, ...} =>
214                                List.app (checkPhi (VSet.union(Avail.inValue nd, bvs))) (!phis)
215                            | IL.COND{cond, ...} =>
216                                if VSet.member(Avail.inValue nd, cond)
217                                orelse VSet.member(bvs, cond)
218                                  then ()
219                                  else errFn [S "unbound variable ", V cond, S " in conditional"]
220                            | IL.BLOCK{body, ...} =>
221                                ignore (List.foldl checkAssign (VSet.union(Avail.inValue nd, bvs)) (!body))
222                            | IL.NEW{actor, args, ...} => let
223                                val bvs = VSet.union(Avail.inValue nd, bvs)
224                              (* check a variable use *)
225                                fun checkVar x = if VSet.member(bvs, x)
226                                      then ()
227                                      else errFn [
228                                          S "variable ", V x, S " is not bound in new ",
229                                          S(Atom.toString actor)
230                                        ]
231                                in
232                                  List.app checkVar args
233                                end
234                            | _ => ()
235                          (* end case *))
236            in            in
237  (* FIXME: check the program *)                    List.app checkNd nodes;
238                    (* cleanup *)
239                      Avail.scrub nodes
240                    end
241            (* check an actor definition *)
242              fun checkActor (IL.Actor{params, state, stateInit, methods, ...}) = let
243                    fun checkMethod (IL.Method{stateIn, body, ...}) =
244                          checkStmt (globals@stateIn, body)
245                    in
246                      checkStmt (globals@params, stateInit);
247                      List.app checkMethod methods
248                    end
249              in
250              (* check the global part *)
251                checkStmt ([], globalInit);
252              (* check the actors *)
253                List.app checkActor actors;
254              (* check for errors *)
255              final()              final()
256            end            end
257    

Legend:
Removed from v.414  
changed lines
  Added in v.417

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