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 3349 - (view) (download)

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

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