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

1 : jhr 369 (* check-il-fn.sml
2 :     *
3 : jhr 435 * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 : jhr 369 * 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 1116 (* return the type of a CONS, where the first argument is the annotated type
21 :     * and the second argument is the list of argument types. Returns false if
22 :     * there is a type error.
23 : jhr 410 *)
24 : jhr 1116 val typeOfCons : ty * ty list -> bool
25 : jhr 410
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 : jhr 1116 fun transfer (input, nd as IL.ND{kind, ...}) = (case kind
62 :     of IL.NULL => raise Fail("unexpected " ^ IL.Node.toString nd)
63 : jhr 417 | IL.JOIN{phis, ...} => let
64 : jhr 1232 (* add the lhs of the phi node. We do not remove the rhs variables, since
65 :     * after value numbering, they may have further uses.
66 :     *)
67 :     fun doPhi ((y, _), vs) = VSet.add(vs, y)
68 :     val output = List.foldl doPhi input (!phis)
69 : jhr 417 in
70 : jhr 1232 output
71 : jhr 417 end
72 : jhr 1116 | IL.ASSIGN{stm=(y, _), ...} => VSet.add(input, y)
73 : jhr 417 | _ => 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 : jhr 410 datatype token
88 : jhr 1232 = 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 : jhr 410
91 : jhr 414 fun error errBuf toks = let
92 : jhr 412 fun tok2str NL = "\n ** "
93 :     | tok2str (S s) = s
94 : jhr 1232 | tok2str (A s) = Atom.toString s
95 : jhr 412 | tok2str (V x) = V.toString x
96 :     | tok2str (VTYS xs) = tok2str(TYS(List.map V.ty xs))
97 :     | tok2str (TY ty) = Ty.toString ty
98 : jhr 410 | tok2str (TYS []) = "()"
99 : jhr 412 | tok2str (TYS[ty]) = Ty.toString ty
100 : jhr 410 | tok2str (TYS tys) = String.concat[
101 : jhr 412 "(", String.concatWith " * " (List.map Ty.toString tys), ")"
102 : jhr 410 ]
103 :     in
104 :     errBuf := concat ("**** Error: " :: List.map tok2str toks)
105 :     :: !errBuf
106 :     end
107 :    
108 : jhr 417
109 :     fun checkAssign errFn ((y, rhs), bvs) = let
110 :     (* check a variable use *)
111 : jhr 412 fun checkVar x = if VSet.member(bvs, x)
112 :     then ()
113 :     else errFn [
114 :     S "variable ", V x, S " is not bound in", NL,
115 :     S(IL.assignToString(y, rhs))
116 :     ]
117 :     fun tyError (ty1, ty2) = errFn [
118 :     S "type mismatch in \"", S(IL.assignToString (y, rhs)), S "\"",
119 :     NL, S "lhs: ", TY ty1, NL, S "rhs: ", TY ty2
120 :     ]
121 :     in
122 :     (* check that y is not bound twice *)
123 :     if VSet.member(bvs, y)
124 :     then errFn [
125 :     S "variable ", V y, S " is bound twice in", NL,
126 :     S(IL.assignToString (y, rhs))
127 :     ]
128 :     else ();
129 :     case rhs
130 :     of IL.VAR x => (
131 :     checkVar x;
132 :     if Ty.same(V.ty y, V.ty x)
133 : jhr 405 then ()
134 : jhr 412 else tyError (V.ty y, V.ty x))
135 :     | IL.LIT lit => let
136 :     val ty = (case lit
137 : jhr 417 of Literal.Int _ => Ty.intTy
138 : jhr 412 | Literal.Float _ => Ty.realTy
139 :     | Literal.String _ => Ty.StringTy
140 :     | Literal.Bool _ => Ty.BoolTy
141 :     (* end case *))
142 :     in
143 :     if Ty.same(V.ty y, ty)
144 : jhr 410 then ()
145 : jhr 412 else tyError (V.ty y, ty)
146 :     end
147 :     | IL.OP(rator, xs) => let
148 :     val (resTy, argTys) = OpTy.sigOf rator
149 :     in
150 :     List.app checkVar xs;
151 :     if Ty.same(V.ty y, resTy)
152 :     then ()
153 :     else tyError (V.ty y, resTy);
154 :     if ListPair.allEq (fn (x, ty) => Ty.same(V.ty x, ty)) (xs, argTys)
155 :     then ()
156 :     else errFn [
157 :     S "argument type mismatch in \"", S(IL.assignToString (y, rhs)), S "\"",
158 :     NL, S "expected: ", TYS argTys,
159 :     NL, S "found: ", VTYS xs
160 :     ]
161 :     end
162 : jhr 1116 | IL.APPLY(name, xs) => () (* FIXME: need functor parameter for typing name *)
163 :     | IL.CONS(ty, xs) => (
164 : jhr 412 List.app checkVar xs;
165 : jhr 1116 if OpTy.typeOfCons (ty, List.map V.ty xs)
166 :     then if Ty.same(V.ty y, ty)
167 :     then ()
168 :     else tyError (V.ty y, ty)
169 :     else errFn [S "invalid ", S(IL.assignToString(y, rhs))]
170 : jhr 412 (* end case *))
171 :     (* end case *);
172 :     VSet.add(bvs, y)
173 :     end
174 : jhr 405
175 : jhr 417 fun checkPhi errFn bvs (y, xs) = let
176 : jhr 405 val ty = V.ty y
177 :     in
178 :     (* check that y is not bound twice *)
179 : jhr 412 if VSet.member(bvs, y)
180 :     then errFn [
181 :     S "variable ", V y, S " is bound twice in", NL,
182 :     S(IL.phiToString (y, xs))
183 :     ]
184 : jhr 405 else ();
185 :     (* check that rhs vars have the correct type *)
186 :     if List.all (fn x => Ty.same(V.ty x, ty)) xs
187 :     then ()
188 : jhr 412 else errFn [
189 :     S "type mismatch in \"", S(IL.phiToString (y, xs)), S "\"",
190 :     NL, S "lhs: ", TY ty, NL, S "rhs: ", VTYS xs
191 :     ]
192 : jhr 405 end
193 :    
194 : jhr 1116 fun check (phase, IL.Program{globalInit, initially, strands}) = let
195 : jhr 413 val errBuf = ref []
196 : jhr 414 val errFn = error errBuf
197 : jhr 413 fun final () = (case !errBuf
198 :     of [] => false
199 :     | errs => (
200 :     Log.msg(concat["********** IL Errors detected after ", phase, " **********\n"]);
201 :     List.app (fn msg => Log.msg(msg ^ "\n")) (List.rev errs);
202 :     true)
203 :     (* end case *))
204 : jhr 417 val checkPhi = checkPhi errFn
205 :     val checkAssign = checkAssign errFn
206 : jhr 1116 fun checkCFG (vs, cfg) = let
207 : jhr 417 val bvs = VSet.fromList vs
208 :     (* compute the variables available on entry to each block *)
209 : jhr 1116 val nodes = Avail.analyse (bvs, cfg)
210 : jhr 417 fun checkNd (nd as IL.ND{kind, ...}) = (case kind
211 :     of IL.NULL => raise Fail "unexpected NULL"
212 :     | IL.JOIN{phis, ...} =>
213 :     List.app (checkPhi (VSet.union(Avail.inValue nd, bvs))) (!phis)
214 :     | IL.COND{cond, ...} =>
215 :     if VSet.member(Avail.inValue nd, cond)
216 :     orelse VSet.member(bvs, cond)
217 :     then ()
218 :     else errFn [S "unbound variable ", V cond, S " in conditional"]
219 : jhr 1116 | IL.ASSIGN{stm, ...} =>
220 :     ignore (checkAssign (stm, VSet.union(Avail.inValue nd, bvs)))
221 : jhr 511 | IL.NEW{strand, args, ...} => let
222 : jhr 417 val bvs = VSet.union(Avail.inValue nd, bvs)
223 :     (* check a variable use *)
224 :     fun checkVar x = if VSet.member(bvs, x)
225 :     then ()
226 :     else errFn [
227 :     S "variable ", V x, S " is not bound in new ",
228 : jhr 511 S(Atom.toString strand)
229 : jhr 417 ]
230 :     in
231 :     List.app checkVar args
232 :     end
233 :     | _ => ()
234 :     (* end case *))
235 :     in
236 :     List.app checkNd nodes;
237 :     (* cleanup *)
238 :     Avail.scrub nodes
239 :     end
240 : jhr 1116 (* the globals are those variables that are live at the exit of the global initialization *)
241 :     val globals = IL.CFG.liveAtExit globalInit
242 :     (* check a strand definition *)
243 : jhr 1232 fun checkStrand (IL.Strand{name, params, state, stateInit, methods}) = let
244 :     val nStateVars = List.length state
245 : jhr 1116 val extraVars = params @ globals
246 : jhr 1232 fun checkMethod (IL.Method{name, stateIn, body, ...}) = (
247 :     if (nStateVars <> List.length stateIn)
248 :     then errFn [
249 :     S "method ", A name, S " has incorrect number of state variables", NL,
250 :     S "expected ", S(Int.toString nStateVars), S ", but found ",
251 :     S(Int.toString(List.length stateIn))
252 :     ]
253 :     else ();
254 :     checkCFG (extraVars@stateIn, body))
255 : jhr 417 in
256 : jhr 1116 checkCFG (extraVars, stateInit);
257 : jhr 1232 if (nStateVars <> List.length(IL.CFG.liveAtExit stateInit))
258 :     then errFn [
259 :     S "strand ", A name, S "'s initialization has incorrect number of state variables", NL,
260 :     S "expected ", S(Int.toString nStateVars), S ", but found ",
261 :     S(Int.toString(List.length(IL.CFG.liveAtExit stateInit)))
262 :     ]
263 :     else ();
264 : jhr 417 List.app checkMethod methods
265 :     end
266 : jhr 413 in
267 : jhr 417 (* check the global part *)
268 : jhr 1116 checkCFG ([], globalInit);
269 :     (* FIXME: need to check initially *)
270 : jhr 511 (* check the strands *)
271 :     List.app checkStrand strands;
272 : jhr 417 (* check for errors *)
273 : jhr 413 final()
274 :     end
275 :    
276 : jhr 369 end

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