Annotation of /trunk/src/compiler/simplify/lift.sml

Parent Directory | Revision Log

---

Revision 3349 - (view) (download)

1 :	jhr	181	(* lift.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	181	* All rights reserved.
7 :			*
8 :	jhr	234	* Lift field operations to global scope and split global initialization to
9 :			* pre and post image loading phases.
10 :	jhr	246	*
11 :			* NOTE: this process can be streamlined as follows:
12 :			* 1) identify the static variables
13 :			* 2) evaluate eagerly, with the proviso that if the lhs is not static, then
14 :			* only evaluate if the rhs is static and the operation is supported
15 :			* 3) reduce code
16 :	jhr	511	* This evaluation process could be extended to the body of the strands too.
17 :	jhr	181	*)
18 :
19 :			structure Lift : sig
20 :
21 :			val transform : Simple.program -> Simple.program
22 :
23 :			end = struct
24 :
25 :			structure BV = BasisVars
26 :	jhr	227	structure S = Simple
27 :	jhr	2491	structure VSet = SimpleVar.Set
28 :			structure VMap = SimpleVar.Map
29 :	jhr	181
30 :	jhr	269	(* identify the image load operations and their antecedents; in terms of BTA,
31 :	jhr	227	* this phase is essentially determining what must be static in order to get the image
32 :			* info needed for the rest of the compile.
33 :			*)
34 :	jhr	269	fun findStatics block = let
35 :	jhr	227	(* analysis to compute the set of static variables *)
36 :			fun mkStatic (env, statics, x) = if VSet.member(statics, x)
37 :			then statics
38 :			else let
39 :			val statics = VSet.add(statics, x)
40 :			in
41 :			case VMap.find(env, x)
42 :			of SOME(S.E_Var y) => mkStatic (env, statics, y)
43 :			| SOME(S.E_Tuple ys) => mkStatics (env, statics, ys)
44 :	jhr	2491	| SOME(S.E_Apply(_, ys, _)) => mkStatics (env, statics, ys)
45 :			| SOME(S.E_Prim(_, _, ys, _)) => mkStatics (env, statics, ys)
46 :	jhr	227	| SOME(S.E_Cons ys) => mkStatics (env, statics, ys)
47 :	jhr	1301	| SOME(S.E_Input(_, _, _, SOME y)) => mkStatic (env, statics, y)
48 :	jhr	227	| SOME _ => statics
49 :	jhr	1113	| NONE => raise Fail(concat[
50 :	jhr	2491	"variable ", SimpleVar.uniqueNameOf x, " has no binding"
51 :	jhr	1113	])
52 :	jhr	227	(* end case *)
53 :			end
54 :			and mkStatics (env, statics, xs) =
55 :			List.foldl (fn (x, statics) => mkStatic(env, statics, x)) statics xs
56 :			fun doBlock (env, statics, S.Block stms) = let
57 :			fun doStmts (env, statics, []) = statics
58 :			| doStmts (env, statics, stm::stms) = let
59 :			val (env, statics) = doStmt (env, statics, stm)
60 :			in
61 :			doStmts (env, statics, stms)
62 :			end
63 :			in
64 :			doStmts (env, statics, stms)
65 :			end
66 :			and doStmt (env, statics, stm) = (case stm
67 :			of S.S_Assign(x, e) => let
68 :			val env = VMap.insert(env, x, e)
69 :			in
70 :			case e
71 :	jhr	2491	of S.E_Prim(f, _, xs, _) =>
72 :	jhr	227	if Var.same(f, BV.fn_load)
73 :			then (env, mkStatic(env, statics, x))
74 :			else (env, statics)
75 :			| _ => (env, statics)
76 :			(* end case *)
77 :			end
78 :			| S.S_IfThenElse(x, b1, b2) => let
79 :			val statics1 = doBlock (env, statics, b1)
80 :			val statics2 = doBlock (env, statics, b2)
81 :			val n = VSet.numItems statics
82 :			in
83 :	jhr	1113	if ((n <> VSet.numItems statics1)
84 :			orelse (n <> VSet.numItems statics2))
85 :	jhr	227	then (env, mkStatic(env, statics, x))
86 :			else (env, statics)
87 :			end
88 :			| _ => (env, statics)
89 :			(* end case *))
90 :			val statics = doBlock (VMap.empty, VSet.empty, block)
91 :			in
92 :	jhr	246	Log.msg "**** static variables: ";
93 :	jhr	2491	VSet.app (fn x => Log.msg(" "^SimpleVar.uniqueNameOf x)) statics;
94 :	jhr	246	Log.msg "\n";
95 :	jhr	269	statics
96 :	jhr	227	end
97 :
98 :	jhr	240	(* given values for the static variables; reduce the static initialization code *)
99 :			fun reduce (env, blk) = let
100 :			fun doBlock (S.Block stms) =
101 :			List.foldr (fn (stm, stms) => doStmt stm @ stms) [] stms
102 :			and doStmt stm = (case stm
103 :	jhr	2491	of S.S_Assign(x, e) => (case VMap.find(env, x)
104 :	jhr	240	of SOME v => let
105 :			val rhs = (case v
106 :			of (Eval.BV b) => S.E_Lit(Literal.Bool b)
107 :			| (Eval.SV s) => S.E_Lit(Literal.String s)
108 :			| (Eval.IV i) => S.E_Lit(Literal.Int i)
109 :			| (Eval.TV _) => e
110 :	jhr	1116	| (Eval.RV _) => e (* FIXME: need way to convert from real to float literal *)
111 :			| (Eval.ImgV arg) => S.E_LoadImage arg
112 :	jhr	240	(* end case *))
113 :			in
114 :			[S.S_Assign(x, rhs)]
115 :			end
116 :			| NONE => [stm]
117 :			(* end case *))
118 :	jhr	2491	| S.S_IfThenElse(x, b1, b2) => (case VMap.find(env, x)
119 :	jhr	240	of SOME(Eval.BV b) => if b then doBlock b1 else doBlock b2
120 :			| NONE => [stm]
121 :			(* end case *))
122 :			| _ => [stm]
123 :			(* end case *))
124 :			in
125 :			S.Block(doBlock blk)
126 :			end
127 :
128 :	jhr	1116	fun reduceInit (env, S.Initially{isArray, rangeInit, iters, create}) = let
129 :			fun reduceCreate (S.C_Create{argInit, name, args}) = S.C_Create{
130 :			argInit = reduce (env, argInit),
131 :			name = name, args = args
132 :			}
133 :			in
134 :			S.Initially{
135 :			isArray = isArray,
136 :			rangeInit = reduce (env, rangeInit),
137 :			iters = iters,
138 :			create = reduceCreate create
139 :			}
140 :			end
141 :
142 :	jhr	2356	fun transform (prog as S.Program{globals, globalInit, funcs, init, strands}) = let
143 :	jhr	269	val statics = findStatics globalInit
144 :			val staticEnv = Eval.evalStatics (statics, globalInit)
145 :	jhr	240	val globalInit = reduce (staticEnv, globalInit)
146 :	jhr	1116	val init = reduceInit (staticEnv, init)
147 :	jhr	227	in
148 :			S.Program{
149 :			globals = globals,
150 :			globalInit = globalInit,
151 :	jhr	2356	funcs = funcs,
152 :	jhr	1116	init = init,
153 :	jhr	511	strands = strands
154 :	jhr	227	}
155 :			end
156 :
157 :	jhr	181	end

---

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