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

Parent Directory | Revision Log | Patch

	revision 416, Sun Oct 17 00:32:07 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

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

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

---

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