Diff of /trunk/src/compiler/IL/forward-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 the entry value and root statement, do the forward DFA on the CFG and
14	type result	* return the list of nodes analysed.
15		*)
16	(* given the entry value and root statement, do the forward DFA on the CFG *)	val analyse : D.t * D.IL.stmt -> D.IL.node list
17	val analyse : D.t * D.IL.stmt -> result
18		(* get results for a node *)
19	(* get result for a node *)	val inValue : D.IL.node -> D.t
20	val outValue : result * D.IL.node -> D.t	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
#	Line 29	Line 29
29
30	type result = IL.node list	type result = IL.node list
31
32	val {setFn, getFn, clrFn, ...} =	val {setFn=setIn, getFn=getIn, clrFn= clrIn, ...} =
33	PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)	PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
34		val {setFn=setOut, getFn=getOut, clrFn=clrOut, ...} =
35		PropList.newProp (fn (IL.ND{props, ...}) => props, fn _ => D.bottom)
36
37		fun clear node = (clrIn node; clrOut node)
38
39	fun analyse (entryVal, stm) = let	fun analyse (entryVal, stm) = let
40	val _ = setFn(IL.Stmt.entry stm, entryVal)	val _ = setOut(IL.Stmt.entry stm, entryVal)
41	(* use reverse DFS order to get quicker convergence *)	(* use reverse DFS order to get quicker convergence *)
42	val nodes = List.rev (IL.sortNodes stm)	val nodes = List.rev (IL.sortNodes stm)
43	fun iterate () = let	fun iterate () = let
44	val anyChange = ref false	val anyChange = ref false
45	fun doNode nd = let	fun doNode nd = let
46	val inValue = D.join (List.map getFn (IL.Node.preds nd))	val inValue = D.join (List.map getOut (IL.Node.preds nd))
47	val outValue = D.transfer (inValue, nd)	val outValue = D.transfer (inValue, nd)
48	in	in
49	if D.same(getFn nd, outValue)	if D.same(getIn nd, inValue)
50	then ()	then () (* input unchanged, so output will be unchanged *)
51	else (setFn(nd, outValue); anyChange := true)	else let
52		val outValue = D.transfer (inValue, nd)
53		in
54		anyChange := true;
55		setIn (nd, inValue);
56		if D.same(getOut nd, outValue)
57		then setOut(nd, outValue)
58		else ()
59		end
60	end	end
61	in	in
62	List.app doNode nodes;	List.app doNode nodes;
#	Line 54	Line 66
66	iterate (); nodes	iterate (); nodes
67	end	end
68
69	fun outValue (_, nd) = getFn nd	fun inValue nd = getIn nd
70		fun outValue nd = getOut nd
71
72	fun scrub nodes = List.app clrFn nodes	fun scrub nodes = List.app clear nodes
73
74	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