Diff of /trunk/src/compiler/IL/backward-dfa-fn.sml

Parent Directory | Revision Log | Patch

	revision 413, Sat Oct 16 15:39:31 2010 UTC	revision 414, Sat Oct 16 18:00:43 2010 UTC
#	Line 10	Line 10
10
11	structure D : DOMAIN	structure D : DOMAIN
12
13	(* abstract representation of analysis results *)	(* given a function for defining out values for exits and the root node, do the
14	type result	* backward DFA on the CFG and return the list of nodes analysed.
	(* given a function for defining out values for exis and the root statement, do the
	* backward DFA on the CFG
15	*)	*)
16	val analyse : (D.IL.node -> D.t) * D.IL.stmt -> result	val analyse : (D.IL.node -> D.t) * D.IL.stmt -> D.IL.node list
17
18	(* get result for a node *)	(* get results for a node *)
19	val inValue : result * D.IL.node -> D.t	val inValue : D.IL.node -> D.t
20		val outValue : D.IL.node -> D.t
21
22	(* scrub results to reclaim space *)	(* scrub results to reclaim space *)
23	val scrub : result -> unit	val scrub : D.IL.node list -> unit
24
25	end = struct	end = struct
26
27	structure D = D	structure D = D
28	structure IL = D.IL	structure IL = D.IL
29
30	type result = IL.node list	val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
31		PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
32	val {setFn, getFn, clrFn, ...} =	val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
33	PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)	PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
34
35		fun clear node = (clrIn node; clrOut node)
36
37	fun analyse (exitVal, stm) = let	fun analyse (exitVal, stm) = let
38	(* use DFS order to get quicker convergence *)	(* use DFS order to get quicker convergence *)
39	val nodes = IL.sortNodes stm	val nodes = IL.sortNodes stm
40	(* set initial values for exit nodes *)	(* set initial values for exit nodes *)
41	val _ = List.app (fn nd => if IL.Node.hasSucc nd then () else setFn(nd, exitVal nd)) nodes	val _ = List.app (fn nd => if IL.Node.hasSucc nd then () else setIn(nd, exitVal nd)) nodes
42	fun iterate () = let	fun iterate () = let
43	val anyChange = ref false	val anyChange = ref false
44	fun doNode nd = let	fun doNode nd = let
45	val outValue = D.join (List.map getFn (IL.Node.succs nd))	val outValue = D.join (List.map getIn (IL.Node.succs nd))
46		in
47		if D.same(getOut nd, outValue)
48		then ()(* output unchanged, so output will be unchanged *)
49		else let
50	val inValue = D.transfer (outValue, nd)	val inValue = D.transfer (outValue, nd)
51	in	in
52	if D.same(getFn nd, inValue)	anyChange := true;
53		setOut (nd, outValue);
54		if D.same(getIn nd, inValue)
55	then ()	then ()
56	else (setFn(nd, inValue); anyChange := true)	else setIn(nd, inValue)
57		end
58	end	end
59	in	in
60	List.app doNode nodes;	List.app doNode nodes;
#	Line 57	Line 64
64	iterate (); nodes	iterate (); nodes
65	end	end
66
67	fun inValue (_, nd) = getFn nd	fun inValue nd = getIn nd
68		fun outValue nd = getOut nd
69
70	fun scrub nodes = List.app clrFn nodes	fun scrub nodes = List.app clear nodes
71
72	end	end

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

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

---

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