Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Annotation of /trunk/src/compiler/IL/ssa-fn.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 198 - (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 :     val newVar : string -> var
104 :    
105 :     end
106 :    
107 :     functor SSAFn (Op : OPERATORS) : SSA =
108 : jhr 192 struct
109 : jhr 137
110 : jhr 192 structure Op = Op
111 : jhr 137
112 : jhr 197 datatype program = Program of {
113 :     globals : var list,
114 :     globalInit : stmt,
115 :     actors : actor list
116 :     (* initialization *)
117 :     }
118 :    
119 :     and actor = Actor of {
120 :     name : Atom.atom,
121 :     params : var list,
122 :     state : var list,
123 :     stateInit : stmt,
124 :     methods : method list
125 :     }
126 :    
127 :     and method = Method of Atom.atom * stmt
128 :    
129 :     and stmt = STM of {
130 : jhr 188 id : Stamp.stamp,
131 :     props : PropList.holder,
132 : jhr 192 preds : stmt list ref,
133 :     phis : (var * var list) list ref, (* phi statements *)
134 :     kind : stmt_kind ref
135 : jhr 188 }
136 :    
137 : jhr 192 and stmt_kind
138 :     = BLOCK of {
139 :     succ : stmt,
140 :     body : assign list
141 :     }
142 :     | IF of {
143 :     cond : var,
144 :     thenBranch : stmt,
145 :     elseBranch : stmt
146 :     }
147 :     | LOOP of {
148 :     hdr : stmt,
149 :     cond : var,
150 :     body : stmt,
151 :     exit : stmt
152 :     }
153 :     | NEW of {
154 :     actor : Atom.atom,
155 :     args : var list,
156 :     succ : stmt
157 :     }
158 :     | DIE
159 :     | STABILIZE
160 :     | EXIT
161 :    
162 : jhr 188 and rhs
163 :     = VAR of var
164 :     | LIT of Literal.literal
165 :     | OP of Op.rator * var list
166 :     | CONS of var list (* tensor-value construction *)
167 :    
168 : jhr 192 and var = V of {
169 : jhr 137 name : string, (* name *)
170 :     id : Stamp.stamp, (* unique ID *)
171 :     useCnt : int ref, (* count of uses *)
172 :     props : PropList.holder
173 : jhr 124 }
174 :    
175 : jhr 192 withtype assign = (var * rhs)
176 : jhr 188
177 : jhr 192 fun same (STM{id=a, ...}, STM{id=b, ...}) = Stamp.same(a, b)
178 :     fun compare (STM{id=a, ...}, STM{id=b, ...}) = Stamp.compare(a, b)
179 :     fun hash (STM{id, ...}) = Stamp.hash id
180 : jhr 188
181 : jhr 192 fun succs (STM{kind, ...}) = (case !kind
182 :     of BLOCK{succ, ...} => [succ]
183 :     | IF{thenBranch, elseBranch, ...} => [thenBranch, elseBranch]
184 :     | LOOP{exit, ...} => [exit]
185 :     | NEW{succ, ...} => [succ]
186 :     | _ => []
187 :     (* end case *))
188 : jhr 188
189 : jhr 192 (* set the successor of a statement *)
190 :     fun setSucc (STM{kind, ...}, stm) = (case !kind
191 :     of BLOCK{succ, body} => kind := BLOCK{succ=stm, body=body}
192 :     | IF{thenBranch, elseBranch, ...} => (
193 :     setSucc(thenBranch, stm);
194 :     setSucc(elseBranch, stm))
195 :     | LOOP{hdr, cond, body, exit} => kind := LOOP{hdr=hdr, cond=cond, body=body, exit=stm}
196 :     | NEW{actor, args, succ} => kind := NEW{actor=actor, args=args, succ=stm}
197 :     | _ => () (* no successor *)
198 :     (* end case *))
199 : jhr 188
200 : jhr 192 fun preds (STM{preds, ...}) = !preds
201 : jhr 124
202 : jhr 192 fun addPred (STM{preds, ...}, stm) =
203 :     if not(List.exists (fn b => same(stm, b)) (!preds))
204 :     then preds := stm :: !preds
205 :     else ();
206 : jhr 137
207 : jhr 192 fun mkSTM kind = STM{
208 : jhr 137 id = Stamp.new(),
209 : jhr 188 props = PropList.newHolder(),
210 : jhr 192 preds = ref [],
211 :     phis = ref [],
212 :     kind = ref kind
213 : jhr 137 }
214 :    
215 : jhr 192 val dummy = mkSTM EXIT
216 : jhr 137
217 : jhr 192 fun mkBLOCK args = mkSTM(BLOCK args)
218 :     fun mkIF args = mkSTM(IF args)
219 :     fun mkLOOP args = mkSTM(LOOP args)
220 : jhr 197 fun mkNEW args = mkSTM(NEW args)
221 : jhr 192 fun mkDIE () = mkSTM DIE
222 :     fun mkSTABILIZE () = mkSTM STABILIZE
223 :     fun mkEXIT () = mkSTM EXIT
224 : jhr 137
225 : jhr 197 fun newVar name = V{
226 :     name = name,
227 :     id = Stamp.new(),
228 :     useCnt = ref 0,
229 :     props = PropList.newHolder()
230 :     }
231 :    
232 : jhr 124 end

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