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

Parent Directory | Revision Log

---

Revision 246 - (view) (download)

1 :	jhr	181	(* lift.sml
2 :			*
3 :			* COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
4 :			* All rights reserved.
5 :			*
6 :	jhr	234	* Lift field operations to global scope and split global initialization to
7 :			* pre and post image loading phases.
8 :	jhr	246	*
9 :			* NOTE: this process can be streamlined as follows:
10 :			* 1) identify the static variables
11 :			* 2) evaluate eagerly, with the proviso that if the lhs is not static, then
12 :			* only evaluate if the rhs is static and the operation is supported
13 :			* 3) reduce code
14 :			* This evaluation process could be extended to the body of the actors too.
15 :	jhr	181	*)
16 :
17 :			structure Lift : sig
18 :
19 :			val transform : Simple.program -> Simple.program
20 :
21 :			end = struct
22 :
23 :			structure BV = BasisVars
24 :	jhr	227	structure S = Simple
25 :			structure VSet = Var.Set
26 :			structure VMap = Var.Map
27 :	jhr	181
28 :	jhr	227	(* the kinds of things a variable in Simple AST can be bound to *)
29 :			datatype var_binding
30 :			= RHS of S.exp
31 :			| Param
32 :	jhr	181
33 :	jhr	227	(* identify the image load operations and lift them and their antecedents; in terms of BTA,
34 :			* this phase is essentially determining what must be static in order to get the image
35 :			* info needed for the rest of the compile.
36 :			*)
37 :			fun liftLoads block = let
38 :			(* analysis to compute the set of static variables *)
39 :			fun mkStatic (env, statics, x) = if VSet.member(statics, x)
40 :			then statics
41 :			else let
42 :			val statics = VSet.add(statics, x)
43 :			in
44 :			case VMap.find(env, x)
45 :			of SOME(S.E_Var y) => mkStatic (env, statics, y)
46 :			| SOME(S.E_Tuple ys) => mkStatics (env, statics, ys)
47 :			| SOME(S.E_Apply(_, _, ys, _)) => mkStatics (env, statics, ys)
48 :			| SOME(S.E_Cons ys) => mkStatics (env, statics, ys)
49 :	jhr	229	| SOME(S.E_Input(_, _, SOME y)) => mkStatic (env, statics, y)
50 :	jhr	227	| SOME _ => statics
51 :			| NONE => raise Fail(concat["variable ", Var.uniqueNameOf x, " has no binding"])
52 :			(* 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 :			of S.E_Apply(f, _, xs, _) =>
72 :			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 :			if ((n <> VSet.numItems statics1) orelse (n <> VSet.numItems statics2))
84 :			then (env, mkStatic(env, statics, x))
85 :			else (env, statics)
86 :			end
87 :			| _ => (env, statics)
88 :			(* end case *))
89 :			val statics = doBlock (VMap.empty, VSet.empty, block)
90 :			(* lift out the static code *)
91 :			fun doBlock (S.Block stms) = let
92 :			fun doStmts ([], staticStms) = S.Block(List.rev staticStms)
93 :			| doStmts (stm::stms, staticStms) = (case doStmt stm
94 :			of SOME stm => doStmts (stms, stm::staticStms)
95 :			| NONE => doStmts (stms, staticStms)
96 :			(* end case *))
97 :			in
98 :			doStmts (stms, [])
99 :			end
100 :			and doStmt stm = (case stm
101 :			of S.S_Assign(x, e) => if VSet.member(statics, x)
102 :			then SOME stm
103 :			else NONE
104 :			| S.S_IfThenElse(x, b1, b2) => if VSet.member(statics, x)
105 :			then SOME(S.S_IfThenElse(x, doBlock b1, doBlock b2))
106 :			else NONE
107 :			| _ => NONE
108 :			(* end case *))
109 :			val staticBlock = doBlock block
110 :			in
111 :	jhr	246	Log.msg "**** static variables: ";
112 :			VSet.app (fn x => Log.msg(" "^Var.uniqueNameOf x)) statics;
113 :			Log.msg "\n";
114 :	jhr	227	staticBlock
115 :			end
116 :
117 :	jhr	240	(* given values for the static variables; reduce the static initialization code *)
118 :			fun reduce (env, blk) = let
119 :			fun doBlock (S.Block stms) =
120 :			List.foldr (fn (stm, stms) => doStmt stm @ stms) [] stms
121 :			and doStmt stm = (case stm
122 :			of S.S_Assign(x, e) => (case Var.Map.find(env, x)
123 :			of SOME v => let
124 :			val rhs = (case v
125 :			of (Eval.BV b) => S.E_Lit(Literal.Bool b)
126 :			| (Eval.SV s) => S.E_Lit(Literal.String s)
127 :			| (Eval.IV i) => S.E_Lit(Literal.Int i)
128 :			| (Eval.TV _) => e
129 :			| (Eval.FV fld) => S.E_Field fld
130 :			| (Eval.Img info) => S.E_LoadImage info
131 :			| (Eval.KV h) => e
132 :			(* end case *))
133 :			in
134 :			[S.S_Assign(x, rhs)]
135 :			end
136 :			| NONE => [stm]
137 :			(* end case *))
138 :			| S.S_IfThenElse(x, b1, b2) => (case Var.Map.find(env, x)
139 :			of SOME(Eval.BV b) => if b then doBlock b1 else doBlock b2
140 :			| NONE => [stm]
141 :			(* end case *))
142 :			| _ => [stm]
143 :			(* end case *))
144 :			in
145 :			S.Block(doBlock blk)
146 :			end
147 :
148 :			fun transform (prog as S.Program{globals, globalInit, actors}) = let
149 :	jhr	227	val staticInit = liftLoads globalInit
150 :	jhr	240	val staticEnv = Eval.evalStatics staticInit
151 :			val globalInit = reduce (staticEnv, globalInit)
152 :	jhr	227	in
153 :			S.Program{
154 :			globals = globals,
155 :			globalInit = globalInit,
156 :			actors = actors
157 :			}
158 :			end
159 :
160 :	jhr	181	end

---

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