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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 417 - (view) (download)

1 : jhr 369 (* check-il-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *
6 :     * Correctness checker for SSA-based ILs.
7 : jhr 417 *
8 :     * TODO:
9 :     * check that the state variables and method stateOut variables are all defined.
10 : jhr 369 *)
11 :    
12 : jhr 405 signature OPERATOR_TY =
13 :     sig
14 :     type rator
15 :     type ty
16 : jhr 369
17 : jhr 410 (* returns the signature of an operator as (rng, dom). *)
18 : jhr 405 val sigOf : rator -> ty * ty list
19 :    
20 : jhr 410 (* return the type of a CONS, where the argument types
21 :     * are given. Returns NONE if the argument types are
22 :     * invalid for the IL.
23 :     *)
24 :     val typeOfCons : ty list -> ty option
25 :    
26 : jhr 405 end
27 :    
28 :     functor CheckILFn (
29 :    
30 :     structure IL : SSA
31 :     structure OpTy : OPERATOR_TY
32 :     where type rator = IL.Op.rator
33 :     where type ty = IL.Ty.ty
34 :    
35 :     ) : sig
36 :    
37 : jhr 413 (* 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 : jhr 414 val check : string * IL.program -> bool
42 : jhr 413
43 : jhr 369 end = struct
44 :    
45 : jhr 405 structure IL = IL
46 :     structure Ty = IL.Ty
47 :     structure V = IL.Var
48 :     structure VSet = V.Set
49 :    
50 : jhr 417 (* 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 : jhr 410 datatype token
92 : jhr 412 = NL | S of string | V of IL.var | VTYS of IL.var list | TY of Ty.ty | TYS of Ty.ty list
93 : jhr 410
94 : jhr 414 fun error errBuf toks = let
95 : jhr 412 fun tok2str NL = "\n ** "
96 :     | tok2str (S s) = s
97 :     | tok2str (V x) = V.toString x
98 :     | tok2str (VTYS xs) = tok2str(TYS(List.map V.ty xs))
99 :     | tok2str (TY ty) = Ty.toString ty
100 : jhr 410 | tok2str (TYS []) = "()"
101 : jhr 412 | tok2str (TYS[ty]) = Ty.toString ty
102 : jhr 410 | tok2str (TYS tys) = String.concat[
103 : jhr 412 "(", String.concatWith " * " (List.map Ty.toString tys), ")"
104 : jhr 410 ]
105 :     in
106 :     errBuf := concat ("**** Error: " :: List.map tok2str toks)
107 :     :: !errBuf
108 :     end
109 :    
110 : jhr 417
111 :     fun checkAssign errFn ((y, rhs), bvs) = let
112 :     (* check a variable use *)
113 : jhr 412 fun checkVar x = if VSet.member(bvs, x)
114 :     then ()
115 :     else errFn [
116 :     S "variable ", V x, S " is not bound in", NL,
117 :     S(IL.assignToString(y, rhs))
118 :     ]
119 :     fun tyError (ty1, ty2) = errFn [
120 :     S "type mismatch in \"", S(IL.assignToString (y, rhs)), S "\"",
121 :     NL, S "lhs: ", TY ty1, NL, S "rhs: ", TY ty2
122 :     ]
123 :     in
124 :     (* check that y is not bound twice *)
125 :     if VSet.member(bvs, y)
126 :     then errFn [
127 :     S "variable ", V y, S " is bound twice in", NL,
128 :     S(IL.assignToString (y, rhs))
129 :     ]
130 :     else ();
131 :     case rhs
132 :     of IL.VAR x => (
133 :     checkVar x;
134 :     if Ty.same(V.ty y, V.ty x)
135 : jhr 405 then ()
136 : jhr 412 else tyError (V.ty y, V.ty x))
137 :     | IL.LIT lit => let
138 :     val ty = (case lit
139 : jhr 417 of Literal.Int _ => Ty.intTy
140 : jhr 412 | Literal.Float _ => Ty.realTy
141 :     | Literal.String _ => Ty.StringTy
142 :     | Literal.Bool _ => Ty.BoolTy
143 :     (* end case *))
144 :     in
145 :     if Ty.same(V.ty y, ty)
146 : jhr 410 then ()
147 : jhr 412 else tyError (V.ty y, ty)
148 :     end
149 :     | IL.OP(rator, xs) => let
150 :     val (resTy, argTys) = OpTy.sigOf rator
151 :     in
152 :     List.app checkVar xs;
153 :     if Ty.same(V.ty y, resTy)
154 :     then ()
155 :     else tyError (V.ty y, resTy);
156 :     if ListPair.allEq (fn (x, ty) => Ty.same(V.ty x, ty)) (xs, argTys)
157 :     then ()
158 :     else errFn [
159 :     S "argument type mismatch in \"", S(IL.assignToString (y, rhs)), S "\"",
160 :     NL, S "expected: ", TYS argTys,
161 :     NL, S "found: ", VTYS xs
162 :     ]
163 :     end
164 :     | IL.CONS xs => (
165 :     List.app checkVar xs;
166 :     case OpTy.typeOfCons (List.map V.ty xs)
167 :     of NONE => errFn [S "invalid ", S(IL.assignToString(y, rhs))]
168 :     | SOME ty => if Ty.same(V.ty y, ty)
169 :     then ()
170 :     else tyError (V.ty y, ty)
171 :     (* end case *))
172 :     (* end case *);
173 :     VSet.add(bvs, y)
174 :     end
175 : jhr 405
176 : jhr 417 fun checkPhi errFn bvs (y, xs) = let
177 : jhr 405 val ty = V.ty y
178 :     in
179 :     (* check that y is not bound twice *)
180 : jhr 412 if VSet.member(bvs, y)
181 :     then errFn [
182 :     S "variable ", V y, S " is bound twice in", NL,
183 :     S(IL.phiToString (y, xs))
184 :     ]
185 : jhr 405 else ();
186 :     (* check that rhs vars have the correct type *)
187 :     if List.all (fn x => Ty.same(V.ty x, ty)) xs
188 :     then ()
189 : jhr 412 else errFn [
190 :     S "type mismatch in \"", S(IL.phiToString (y, xs)), S "\"",
191 :     NL, S "lhs: ", TY ty, NL, S "rhs: ", VTYS xs
192 :     ]
193 : jhr 405 end
194 :    
195 : jhr 413 fun check (phase, IL.Program{globals, globalInit, actors}) = let
196 :     val errBuf = ref []
197 : jhr 414 val errFn = error errBuf
198 : jhr 413 fun final () = (case !errBuf
199 :     of [] => false
200 :     | errs => (
201 :     Log.msg(concat["********** IL Errors detected after ", phase, " **********\n"]);
202 :     List.app (fn msg => Log.msg(msg ^ "\n")) (List.rev errs);
203 :     true)
204 :     (* end case *))
205 : jhr 417 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
237 :     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 : jhr 413 in
250 : jhr 417 (* check the global part *)
251 :     checkStmt ([], globalInit);
252 :     (* check the actors *)
253 :     List.app checkActor actors;
254 :     (* check for errors *)
255 : jhr 413 final()
256 :     end
257 :    
258 : jhr 369 end

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