Annotation of /trunk/src/compiler/IL/ssa-fn.sml

Parent Directory | Revision Log

---

Revision 199 - (view) (download)

1 :	jhr	137	(* ssa-fn.sml
2 :	jhr	124	*
3 :			* COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
4 :			* All rights reserved.
5 :	jhr	137	*
6 :			* The IL is a combination of a block-structured tree and an SSA control-flow
7 :			* graph of blocks.
8 :	jhr	124	*)
9 :
10 :	jhr	198	signature SSA =
11 :			sig
12 :
13 :			structure Op : OPERATORS
14 :
15 :			datatype program = Program of {
16 :			globals : var list,
17 :			globalInit : stmt,
18 :			actors : actor list
19 :			(* initialization *)
20 :			}
21 :
22 :			and actor = Actor of {
23 :			name : Atom.atom,
24 :			params : var list,
25 :			state : var list,
26 :			stateInit : stmt,
27 :			methods : method list
28 :			}
29 :
30 :			and method = Method of Atom.atom * stmt
31 :
32 :			and stmt = STM of {
33 :			id : Stamp.stamp,
34 :			props : PropList.holder,
35 :			preds : stmt list ref,
36 :			phis : (var * var list) list ref, (* phi statements *)
37 :			kind : stmt_kind ref
38 :			}
39 :
40 :			and stmt_kind
41 :			= BLOCK of {
42 :			succ : stmt,
43 :			body : assign list
44 :			}
45 :			| IF of {
46 :			cond : var,
47 :			thenBranch : stmt,
48 :			elseBranch : stmt
49 :			}
50 :			| LOOP of {
51 :			hdr : stmt,
52 :			cond : var,
53 :			body : stmt,
54 :			exit : stmt
55 :			}
56 :			| NEW of {
57 :			actor : Atom.atom,
58 :			args : var list,
59 :			succ : stmt
60 :			}
61 :			| DIE
62 :			| STABILIZE
63 :			| EXIT
64 :
65 :			and rhs
66 :			= VAR of var
67 :			| LIT of Literal.literal
68 :			| OP of Op.rator * var list
69 :			| CONS of var list (* tensor-value construction *)
70 :
71 :			and var = V of {
72 :			name : string, (* name *)
73 :			id : Stamp.stamp, (* unique ID *)
74 :			useCnt : int ref, (* count of uses *)
75 :			props : PropList.holder
76 :			}
77 :
78 :			withtype assign = (var * rhs)
79 :
80 :			val same : stmt * stmt -> bool
81 :			val compare : stmt * stmt -> order
82 :			val hash : stmt -> word
83 :
84 :			val succs : stmt -> stmt list
85 :
86 :			(* set the successor of a statement *)
87 :			val setSucc : stmt * stmt -> unit
88 :
89 :			val preds : stmt -> stmt list
90 :
91 :			val addPred : stmt * stmt -> unit
92 :
93 :			val dummy : stmt
94 :
95 :			val mkBLOCK : {succ : stmt, body : assign list} -> stmt
96 :			val mkIF : {cond : var, thenBranch : stmt, elseBranch : stmt} -> stmt
97 :			val mkLOOP : {hdr : stmt, cond : var, body : stmt, exit : stmt} -> stmt
98 :			val mkNEW : {actor : Atom.atom, args : var list, succ : stmt} -> stmt
99 :			val mkDIE : unit -> stmt
100 :			val mkSTABILIZE : unit -> stmt
101 :			val mkEXIT : unit -> stmt
102 :
103 :	jhr	199	structure Var : sig
104 :			val new : string -> var
105 :			val same : var * var -> bool
106 :			val compare : var * var -> order
107 :			val hash : var -> word
108 :			val toString : var -> string
109 :			structure Map : ORD_MAP where type Key.ord_key = var
110 :			structure Set : ORD_SET where type Key.ord_key = var
111 :			structure Tbl : MONO_HASH_TABLE where type Key.hash_key = var
112 :			end
113 :	jhr	198
114 :			end
115 :
116 :			functor SSAFn (Op : OPERATORS) : SSA =
117 :	jhr	192	struct
118 :	jhr	137
119 :	jhr	192	structure Op = Op
120 :	jhr	137
121 :	jhr	197	datatype program = Program of {
122 :			globals : var list,
123 :			globalInit : stmt,
124 :			actors : actor list
125 :			(* initialization *)
126 :			}
127 :
128 :			and actor = Actor of {
129 :			name : Atom.atom,
130 :			params : var list,
131 :			state : var list,
132 :			stateInit : stmt,
133 :			methods : method list
134 :			}
135 :
136 :			and method = Method of Atom.atom * stmt
137 :
138 :			and stmt = STM of {
139 :	jhr	188	id : Stamp.stamp,
140 :			props : PropList.holder,
141 :	jhr	192	preds : stmt list ref,
142 :			phis : (var * var list) list ref, (* phi statements *)
143 :			kind : stmt_kind ref
144 :	jhr	188	}
145 :
146 :	jhr	192	and stmt_kind
147 :			= BLOCK of {
148 :			succ : stmt,
149 :			body : assign list
150 :			}
151 :			| IF of {
152 :			cond : var,
153 :			thenBranch : stmt,
154 :			elseBranch : stmt
155 :			}
156 :			| LOOP of {
157 :			hdr : stmt,
158 :			cond : var,
159 :			body : stmt,
160 :			exit : stmt
161 :			}
162 :			| NEW of {
163 :			actor : Atom.atom,
164 :			args : var list,
165 :			succ : stmt
166 :			}
167 :			| DIE
168 :			| STABILIZE
169 :			| EXIT
170 :
171 :	jhr	188	and rhs
172 :			= VAR of var
173 :			| LIT of Literal.literal
174 :			| OP of Op.rator * var list
175 :			| CONS of var list (* tensor-value construction *)
176 :
177 :	jhr	192	and var = V of {
178 :	jhr	137	name : string, (* name *)
179 :			id : Stamp.stamp, (* unique ID *)
180 :			useCnt : int ref, (* count of uses *)
181 :			props : PropList.holder
182 :	jhr	124	}
183 :
184 :	jhr	192	withtype assign = (var * rhs)
185 :	jhr	188
186 :	jhr	192	fun same (STM{id=a, ...}, STM{id=b, ...}) = Stamp.same(a, b)
187 :			fun compare (STM{id=a, ...}, STM{id=b, ...}) = Stamp.compare(a, b)
188 :			fun hash (STM{id, ...}) = Stamp.hash id
189 :	jhr	188
190 :	jhr	192	fun succs (STM{kind, ...}) = (case !kind
191 :			of BLOCK{succ, ...} => [succ]
192 :			| IF{thenBranch, elseBranch, ...} => [thenBranch, elseBranch]
193 :			| LOOP{exit, ...} => [exit]
194 :			| NEW{succ, ...} => [succ]
195 :			| _ => []
196 :			(* end case *))
197 :	jhr	188
198 :	jhr	192	(* set the successor of a statement *)
199 :			fun setSucc (STM{kind, ...}, stm) = (case !kind
200 :			of BLOCK{succ, body} => kind := BLOCK{succ=stm, body=body}
201 :			| IF{thenBranch, elseBranch, ...} => (
202 :			setSucc(thenBranch, stm);
203 :			setSucc(elseBranch, stm))
204 :			| LOOP{hdr, cond, body, exit} => kind := LOOP{hdr=hdr, cond=cond, body=body, exit=stm}
205 :			| NEW{actor, args, succ} => kind := NEW{actor=actor, args=args, succ=stm}
206 :			| _ => () (* no successor *)
207 :			(* end case *))
208 :	jhr	188
209 :	jhr	192	fun preds (STM{preds, ...}) = !preds
210 :	jhr	124
211 :	jhr	192	fun addPred (STM{preds, ...}, stm) =
212 :			if not(List.exists (fn b => same(stm, b)) (!preds))
213 :			then preds := stm :: !preds
214 :			else ();
215 :	jhr	137
216 :	jhr	192	fun mkSTM kind = STM{
217 :	jhr	137	id = Stamp.new(),
218 :	jhr	188	props = PropList.newHolder(),
219 :	jhr	192	preds = ref [],
220 :			phis = ref [],
221 :			kind = ref kind
222 :	jhr	137	}
223 :
224 :	jhr	192	val dummy = mkSTM EXIT
225 :	jhr	137
226 :	jhr	192	fun mkBLOCK args = mkSTM(BLOCK args)
227 :			fun mkIF args = mkSTM(IF args)
228 :			fun mkLOOP args = mkSTM(LOOP args)
229 :	jhr	197	fun mkNEW args = mkSTM(NEW args)
230 :	jhr	192	fun mkDIE () = mkSTM DIE
231 :			fun mkSTABILIZE () = mkSTM STABILIZE
232 :			fun mkEXIT () = mkSTM EXIT
233 :	jhr	137
234 :	jhr	199	structure Var =
235 :			struct
236 :			fun new name = V{
237 :			name = name,
238 :			id = Stamp.new(),
239 :			useCnt = ref 0,
240 :			props = PropList.newHolder()
241 :			}
242 :			fun same (V{id=a, ...}, V{id=b, ...}) = Stamp.same(a, b)
243 :			fun compare (V{id=a, ...}, V{id=b, ...}) = Stamp.compare(a, b)
244 :			fun hash (V{id, ...}) = Stamp.hash id
245 :			fun toString (V{name, id, ...}) = name ^ Stamp.toString id
246 :			local
247 :			structure V =
248 :			struct
249 :			type ord_key = var
250 :			val compare = compare
251 :			end
252 :			in
253 :			structure Map = RedBlackMapFn (V)
254 :			structure Set = RedBlackSetFn (V)
255 :			end
256 :			structure Tbl = HashTableFn (
257 :			struct
258 :			type hash_key = var
259 :			val hashVal = hash
260 :			val sameKey = same
261 :			end)
262 :			end
263 :	jhr	197
264 :	jhr	124	end

---

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