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

SCM Repository

[diderot] Annotation of /branches/charisee/src/compiler/tree-il/low-to-tree-fn.sml
ViewVC logotype

Annotation of /branches/charisee/src/compiler/tree-il/low-to-tree-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2795 - (view) (download)

1 : jhr 1115 (* low-to-tree-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *
6 :     * This module translates the LowIL representation of a program (i.e., a pure CFG) to
7 :     * a block-structured AST with nested expressions.
8 :     *
9 :     * NOTE: this translation is pretty dumb about variable coalescing (i.e., it doesn't do any).
10 :     *)
11 :    
12 :     functor LowToTreeFn (Target : sig
13 :    
14 : jhr 1640 val supportsPrinting : unit -> bool (* does the target support the Print op? *)
15 :    
16 : jhr 1115 (* tests for whether various expression forms can appear inline *)
17 : jhr 2356 val inlineCons : int -> bool (* can n'th-order tensor construction appear inline *)
18 :     val inlineMatrixExp : bool (* can matrix-valued expressions appear inline? *)
19 : cchiw 2624 val isHwVec : int -> bool
20 :     val isVecTy : int -> bool
21 : jhr 2632 val getPieces : int -> int list
22 : cchiw 2671 val getVecTy : int -> bool * int *int list
23 :    
24 : jhr 1115 end) : sig
25 :    
26 :     val translate : LowIL.program -> TreeIL.program
27 :    
28 :     end = struct
29 :    
30 : cchiw 2646
31 :     structure Src = LowIL
32 :     structure SrcOp = LowOps
33 : cchiw 2691 structure SrcV = LowIL.Var
34 :     structure SrcSV = LowIL.StateVar
35 : cchiw 2646 structure VA = VarAnalysis
36 :     structure Ty = LowILTypes
37 : jhr 1115 structure Nd = LowIL.Node
38 :     structure CFG = LowIL.CFG
39 : cchiw 2691 structure LowOpToTreeOp = LowOpToTreeOp
40 :     structure Dst = TreeIL
41 :     structure DstOp = TreeOps
42 : cchiw 2795
43 :     structure SrcTy = LowILTypes
44 :     structure DstTy = TreeILTypes
45 :    
46 : cchiw 2692 structure DstV = Dst.Var
47 : cchiw 2691 structure TreeToOpr=TreeToOpr
48 :     structure Fnc=TreeFunc
49 :     structure TySet= Fnc.TySet
50 :     structure OprSet= Fnc.OprSet
51 : cchiw 2688
52 : jhr 1115 (* create new tree IL variables *)
53 :     local
54 : cchiw 2646 val newVar = Dst.Var.new
55 : jhr 1115 val cnt = ref 0
56 :     fun genName prefix = let
57 : jhr 2356 val n = !cnt
58 :     in
59 :     cnt := n+1;
60 :     String.concat[prefix, "_", Int.toString n]
61 :     end
62 : jhr 1115 in
63 : cchiw 2664 val testing=1
64 : cchiw 2628 fun pntTest str=(case testing
65 :     of 1=> (print(str);1)
66 :     | _ =>1
67 :     (*end case*))
68 : jhr 2632
69 : cchiw 2691 fun newGlobal x = newVar (genName("G_" ^ SrcV.name x), Dst.VK_Global, SrcV.ty x)
70 :     fun newParam x = newVar (genName("p_" ^ SrcV.name x), Dst.VK_Local, SrcV.ty x)
71 :     fun newLocal x = newVar (genName("l_" ^ SrcV.name x), Dst.VK_Local, SrcV.ty x)
72 :     fun newIter x = newVar (genName("i_" ^ SrcV.name x), Dst.VK_Local, SrcV.ty x)
73 :     fun newTmp (x,n) = newVar (genName("l_" ^ SrcV.name x^Int.toString n), Dst.VK_Local, SrcV.ty x)
74 : cchiw 2686
75 : cchiw 2791 fun newLocalWithTy (name,n)= newVar(genName("l_"^name^Int.toString(n)), Dst.VK_Local,Ty.TensorTy [n])
76 :     fun newGlobalWithTy (name,n)= newVar(genName("G_"^name^Int.toString(n)), Dst.VK_Global,Ty.TensorTy [n])
77 :    
78 : jhr 1115 end
79 :    
80 : jhr 1640 (* associate Tree IL state variables with Low IL variables using properties *)
81 :     local
82 : cchiw 2646 fun mkStateVar x = Dst.SV{
83 : cchiw 2691 name = SrcSV.name x,
84 : jhr 1640 id = Stamp.new(),
85 : cchiw 2691 ty = SrcSV.ty x,
86 : jhr 1640 varying = VA.isVarying x,
87 : cchiw 2691 output = SrcSV.isOutput x
88 : jhr 1640 }
89 :     in
90 : cchiw 2691 val {getFn = getStateVar, ...} = SrcSV.newProp mkStateVar
91 : jhr 1640 end
92 :    
93 : cchiw 2646 fun mkBlock stms = Dst.Block{locals=[], body=stms}
94 :     fun mkIf (x, stms, []) = Dst.S_IfThen(x, mkBlock stms)
95 :     | mkIf (x, stms1, stms2) = Dst.S_IfThenElse(x, mkBlock stms1, mkBlock stms2)
96 : jhr 1115
97 :     (* an environment that tracks bindings of variables to target expressions and the list
98 :     * of locals that have been defined.
99 :     *)
100 :     local
101 : cchiw 2691 structure VT = SrcV.Tbl
102 : cchiw 2646 fun decCount ( Src.V{useCnt, ...}) = let
103 : jhr 2356 val n = !useCnt - 1
104 :     in
105 :     useCnt := n; (n <= 0)
106 :     end
107 : jhr 1115 datatype target_binding
108 : cchiw 2646 = GLOB of Dst.var (* variable is global *)
109 :     | TREE of Dst.exp (* variable bound to target expression tree *)
110 :     | DEF of Dst.exp (* either a target variable or constant for a defined variable *)
111 : cchiw 2637
112 :    
113 :     fun insert (key, value) d =fn s =>
114 :     if s = key then SOME value
115 :     else d s
116 :    
117 :     fun lookup k d = d k
118 :    
119 :    
120 :     structure ListSetOfInts = ListSetFn (struct
121 :     type ord_key = int
122 :     val compare = Int.compare
123 :     end)
124 :    
125 :    
126 : jhr 1115 datatype env = E of {
127 : jhr 2356 tbl : target_binding VT.hash_table,
128 : cchiw 2637 types: TySet.set,
129 :     functs : OprSet.set,
130 : cchiw 2646 locals : Dst.var list
131 : jhr 2356 }
132 : cchiw 2637
133 :    
134 : jhr 1115 in
135 :     (* DEBUG *)
136 : cchiw 2637
137 :    
138 :     fun peelEnv(E{tbl, types, functs ,locals})=(types,functs)
139 : cchiw 2691 fun peelEnvLoc(E{tbl, types, functs ,locals})=locals
140 :     fun setEnv(E{tbl, types,functs,locals},types1,functs1)= E{tbl=tbl, types=types1, functs= functs1 ,locals=locals}
141 :    
142 : cchiw 2637
143 : jhr 1115 fun bindToString binding = (case binding
144 : cchiw 2646 of GLOB y => "GLOB " ^ Dst.Var.name y
145 : jhr 2356 | TREE e => "TREE"
146 : cchiw 2688 | DEF(Dst.E_Var y) => "DEFVar " ^ Dst.Var.name y
147 : cchiw 2692 | DEF e => "DEF"^Dst.toString e
148 : jhr 1115 (* end case *))
149 :     fun dumpEnv (E{tbl, ...}) = let
150 :     fun prEntry (x, binding) =
151 : cchiw 2646 print(concat[" ", Src.Var.toString x, " --> ", bindToString binding, "\n"])
152 : jhr 1115 in
153 : cchiw 2791 (* print "\n *** dump environment\n";
154 : jhr 2356 VT.appi prEntry tbl;
155 : cchiw 2791 print "***\n"*) print ""
156 : jhr 1115 end
157 :     (* DEBUG *)
158 :    
159 : cchiw 2637 fun newEnv () = E{tbl = VT.mkTable (512, Fail "tbl"), types=TySet.empty, functs=OprSet.empty, locals=[]}
160 : jhr 1115
161 :     (* use a variable. If it is a pending expression, we remove it from the table *)
162 : cchiw 2692 fun peek (env as E{tbl, ...}) x = (case (VT.find tbl x)
163 :     of NONE=>"none"
164 :     | SOME e=> bindToString e
165 :     (*end case *))
166 :    
167 :     fun useVar (env as E{tbl, ...}) x = (case VT.find tbl x
168 : cchiw 2791 of SOME(GLOB x') => ( (*print ("\n usevar found Glob "^SrcV.name x^"\n") ;*)Dst.E_Var x')
169 : jhr 2356 | SOME(TREE e) => (
170 : cchiw 2691 (*print(concat["useVar ", SrcV.toString x, " ==> TREE\n"]);*)
171 : jhr 2356 ignore(VT.remove tbl x);
172 :     e)
173 :     | SOME(DEF e) => (
174 : cchiw 2691 (*print(concat["useVar ", SrcV.toString x, " ==> ", bindToString(DEF e), "; use count = ", Int.toString(SrcV.useCount x), "\n"]);*)
175 : jhr 2356 (* if this is the last use of x, then remove it from the table *)
176 : cchiw 2791 (*if (decCount x) then ignore(VT.remove tbl x) else ();*)
177 :     (*print ("\n found Def "^SrcV.name x^"\n");*)
178 : jhr 2356 e)
179 :     | NONE => (
180 : jhr 1115 dumpEnv env;
181 : cchiw 2691 raise Fail(concat ["useVar(", SrcV.toString x, ")"])
182 : jhr 1115 )
183 : jhr 2356 (* end case *))
184 : jhr 1115
185 :     (* record a local variable *)
186 : cchiw 2692
187 :     fun getLocal(E{tbl, types,functs,locals})=let
188 :     val n=List.length locals
189 :     val _ =print ("No. of locals:" ^Int.toString n )
190 :     in
191 :     List.map (fn e=>print("\n\t VAr-"^DstV.name e)) locals
192 :    
193 :     end
194 : cchiw 2637 fun addLocal (E{tbl, types,functs,locals}, x) = E{tbl=tbl,types=types, functs=functs,locals=x::locals}
195 : cchiw 2692 fun addLocals (E{tbl, types,functs,locals}, x) =let
196 : cchiw 2789 (*val n=List.length locals
197 : cchiw 2692 val n2=List.length x
198 : cchiw 2789 val _ =print ("No. of locals:" ^Int.toString n^" newbies " ^Int.toString n2)*)
199 : cchiw 2692 val env= E{tbl=tbl,types=types, functs=functs,locals=x@locals}
200 : cchiw 2789 (*val _ = getLocal env*)
201 : cchiw 2692 in
202 :     env
203 :     end
204 :    
205 : cchiw 2691 fun testp t=print(String.concat t)
206 :     fun global (E{tbl, ...}, x, x') =( testp[("\n using global function "^SrcV.name x^":\n")];
207 : cchiw 2688 VT.insert tbl (x, GLOB x'))
208 : jhr 1115
209 :     (* insert a pending expression into the table. Note that x should only be used once! *)
210 :     fun insert (env as E{tbl, ...}, x, exp) = (
211 : jhr 2356 VT.insert tbl (x, TREE exp);
212 :     env)
213 : jhr 1115
214 :     fun rename (env as E{tbl, ...}, x, x') = (
215 : cchiw 2646 VT.insert tbl (x, DEF(Dst.E_Var x'));
216 : jhr 2356 env)
217 : cchiw 2687
218 : cchiw 2692 fun renameGlob (env as E{tbl, ...}, x, x') = (
219 :     VT.insert tbl (x, GLOB( x'));
220 : cchiw 2687 env)
221 : cchiw 2692
222 : cchiw 2789 fun renameExp (env as E{tbl, ...}, x, x') = (
223 : cchiw 2692 VT.insert tbl (x, DEF( x'));
224 :     env)
225 : cchiw 2688
226 : cchiw 2692
227 : cchiw 2688 fun peekGlobal (E{tbl, ...}, x) = (case VT.find tbl x
228 : cchiw 2691 of SOME(GLOB x') => SOME x'
229 :     | SOME e => NONE
230 :     | NONE => NONE
231 :     (* end case *))
232 : cchiw 2688
233 : cchiw 2692
234 : cchiw 2687 fun bindLocal (env, lhs, rhs) =let
235 : cchiw 2691 val n=SrcV.useCount lhs
236 : cchiw 2687 fun AL _=let
237 : jhr 2356 val t = newLocal lhs
238 : cchiw 2691 in
239 :     (rename(addLocal(env, t), lhs, t), [Dst.S_Assign([t], rhs)])
240 :     end
241 : cchiw 2791 val _=print(String.concat["\n In BindLocal: \n \t LHS: ",SrcV.name lhs, " Count \t",Int.toString n," rhs:", Dst.toString rhs ,"\n"])
242 : cchiw 2687
243 : cchiw 2688 in (case (n,rhs)
244 : cchiw 2791 of (0,_) => (env,[])
245 : cchiw 2695 | (1,_) => ((insert(env, lhs, rhs), []))
246 : cchiw 2795 | (_,Dst.E_Mux(A,isFill, nOrig,Tys as Ty.vectorLength tys,exps))=> let
247 : cchiw 2789 val name=SrcV.name lhs
248 : cchiw 2791 val vs=List.map (fn n=> newLocalWithTy(name,n) ) tys
249 : cchiw 2795 val rhs=Dst.E_Mux(A, isFill,nOrig,Tys,List.map (fn v=>Dst.E_Var v) vs)
250 : cchiw 2791 val stmts=ListPair.map (fn(x,e)=>Dst.S_Assign([x],e)) (vs,exps)
251 : cchiw 2692 in
252 : cchiw 2791 (renameExp(addLocals(env,vs),lhs,rhs),stmts)
253 : cchiw 2687 end
254 : cchiw 2695 |(_,_)=> (AL 1)
255 : cchiw 2688 (*end case*))
256 : cchiw 2687 end
257 :    
258 : cchiw 2691
259 :     fun bind (env, lhs, rhs) =(case peekGlobal (env, lhs)
260 : cchiw 2789 of SOME x =>((env, [Dst.S_Assign([x], rhs)]))
261 :     | NONE => (bindLocal (env, lhs, rhs))
262 : cchiw 2691 (* end case *))
263 : jhr 1115
264 :     (* set the definition of a variable, where the RHS is either a literal constant or a variable *)
265 : cchiw 2691 fun bindSimple (env as E{tbl, ...}, lhs, rhs) =(case peekGlobal (env, lhs)
266 :     of SOME x => (env, [Dst.S_Assign([x], rhs)])
267 :     | NONE => (VT.insert tbl (lhs, DEF rhs); (env, []))
268 :     (* end case *))
269 : cchiw 2688
270 : jhr 1115
271 :     (* at the end of a block, we need to assign any pending expressions to locals. The
272 :     * blkStms list and the resulting statement list are in reverse order.
273 :     *)
274 : cchiw 2637 fun flushPending (E{tbl,types, functs,locals}, blkStms) = let
275 : jhr 2356 fun doVar (x, TREE e, (locals, stms)) = let
276 :     val t = newLocal x
277 :     in
278 : cchiw 2646 VT.insert tbl (x, DEF(Dst.E_Var t));
279 :     (t::locals, Dst.S_Assign([t], e)::stms)
280 : jhr 2356 end
281 :     | doVar (_, _, acc) = acc
282 :     val (locals, stms) = VT.foldi doVar (locals, blkStms) tbl
283 :     in
284 : cchiw 2637 (E{tbl=tbl, types=types,functs=functs,locals=locals}, stms)
285 : jhr 2356 end
286 : jhr 1115
287 : cchiw 2646 fun doPhi ((lhs, rhs), (env, predBlks : Dst.stm list list)) = let
288 : jhr 2356 (* t will be the variable in the continuation of the JOIN *)
289 :     val t = newLocal lhs
290 :     val predBlks = ListPair.map
291 : cchiw 2646 (fn (x, stms) => Dst.S_Assign([t], useVar env x)::stms)
292 : jhr 2356 (rhs, predBlks)
293 :     in
294 :     (rename (addLocal(env, t), lhs, t), predBlks)
295 :     end
296 : cchiw 2637 (*
297 : cchiw 2646 fun endScope (E{locals, ...}, stms) = Dst.Block{
298 : jhr 2356 locals = List.rev locals,
299 :     body = stms
300 :     }
301 : cchiw 2637 *)
302 :     fun endScope (env, stms) = let
303 :     val (types,opr)=peelEnv(env)
304 :    
305 : cchiw 2646 in Dst.Pink{
306 : cchiw 2637
307 :     locals= List.rev(peelEnvLoc env),
308 :     types= types,
309 :     opr=opr,
310 :     body = stms
311 :     }
312 :     end
313 : jhr 1115 end
314 :    
315 :     (* Certain IL operators cannot be compiled to inline expressions. Return
316 :     * false for those and true for all others.
317 :     *)
318 : cchiw 2680
319 :     (*Move operator so it's it's on variable: y=sumOP+9
320 :     x=sumOp..y=x+9, =>
321 :    
322 :     *)
323 : jhr 1115 fun isInlineOp rator = let
324 : jhr 2356 fun chkTensorTy (Ty.TensorTy[]) = true
325 :     | chkTensorTy (Ty.TensorTy[_]) = true
326 :     | chkTensorTy (Ty.TensorTy[_, _]) = Target.inlineMatrixExp
327 :     | chkTensorTy _ = false
328 : cchiw 2688
329 : jhr 2356 in
330 :     case rator
331 : cchiw 2646 of SrcOp.LoadVoxels(_, 1) => true
332 :     | SrcOp.LoadVoxels _ => false
333 :     | SrcOp.EigenVecs2x2 => false
334 :     | SrcOp.EigenVecs3x3 => false
335 :     | SrcOp.EigenVals2x2 => false
336 :     | SrcOp.EigenVals3x3 => false
337 : cchiw 2691 (* | SrcOp.Zero _ => Target.inlineMatrixExp*)
338 : cchiw 2680
339 :     (*Added here *)
340 :     | SrcOp.imgAddr _ => false
341 :     | SrcOp.imgLoad _ => false
342 :     | _ => true (*when true calls binding *)
343 : jhr 2356 (* end case *)
344 :     end
345 : jhr 1115
346 : cchiw 2669 (*HERE- since we are using arrays, nothing can be inline
347 :     Fix later if it needs to be fixed*)
348 : cchiw 2525 (* is a CONS inline? *)
349 : cchiw 2669 fun isInlineCons ty = (*(case ty
350 : cchiw 2525 of Ty.SeqTy(Ty.IntTy, _) => true
351 :     | Ty.TensorTy dd => Target.inlineCons(List.length dd)
352 :     | Ty.SeqTy _ => false
353 :     (*CCCC-? DO we have this type*)
354 : cchiw 2615 (* | Ty.DynSeqTy ty => false*)
355 : cchiw 2525 | _ => raise Fail(concat["invalid CONS<", Ty.toString ty, ">"])
356 : cchiw 2669 (* end case *))*) false
357 : cchiw 2525
358 :     (* translate a LowIL assignment to a list of zero or more target statements in reverse
359 :     * order.
360 :     *)
361 : cchiw 2688
362 :    
363 :    
364 : jhr 1115 fun doAssign (env, (lhs, rhs)) = let
365 : cchiw 2688
366 : jhr 2356 fun doLHS () = (case peekGlobal(env, lhs)
367 : cchiw 2688 of SOME lhs' => (env, lhs')
368 :     | NONE => let
369 :     val t = newLocal lhs
370 :     in
371 :     (rename (addLocal(env, t), lhs, t), t)
372 :     end
373 :     (* end case *))
374 :    
375 : jhr 2356 (* for expressions that are going to be compiled to a call statement *)
376 :     fun assignExp (env, exp) = let
377 :     (* operations that return matrices may not be supported inline *)
378 :     val (env, t) = doLHS()
379 :     in
380 : cchiw 2646 (env, [Dst.S_Assign([t], exp)])
381 : jhr 2356 end
382 : cchiw 2680
383 : jhr 2632
384 : cchiw 2525 (* force an argument to be stored in something that will be mapped to an l-value *)
385 :     fun bindVar (env, x) = (case useVar env x
386 : cchiw 2688 of x' as Dst.E_State _ =>(env, x', [])
387 :     | x' as Dst.E_Var _ => (env, x', [])
388 :     | e => let
389 : cchiw 2525 val x' = newLocal x
390 :     in
391 : cchiw 2646 (addLocal(env, x'), Dst.E_Var x', [Dst.S_Assign([x'], e)])
392 : cchiw 2525 end
393 :     (* end case *))
394 : cchiw 2692
395 :     val _=toS.ASSIGNtoString(lhs,rhs)
396 : cchiw 2688
397 : jhr 2356 in
398 :     case rhs
399 : cchiw 2688 of Src.STATE x => bindSimple (env, lhs, Dst.E_State(getStateVar x))
400 :     | Src.VAR x => bindSimple (env, lhs, useVar env x)
401 :     | Src.LIT lit => bindSimple (env, lhs, Dst.E_Lit lit)
402 : jhr 2632
403 : cchiw 2646 (*| Src.OP( SrcOp.Prepend ty, [item, seq]) => let
404 : jhr 2356 val (env, t) = doLHS()
405 : cchiw 2525 val (env, item', stms) = bindVar (env, item)
406 : cchiw 2646 val exp = Dst.E_Op( DstOp.Prepend ty, [item', useVar env seq])
407 : jhr 2356 in
408 : cchiw 2646 (env, Dst.S_Assign([t], exp) :: stms)
409 : jhr 2356 end
410 : cchiw 2646 | Src.OP( SrcOpp.Append ty, [seq, item]) => let
411 : jhr 2356 val (env, t) = doLHS()
412 : cchiw 2525 val (env, item', stms) = bindVar (env, item)
413 : cchiw 2646 val exp = Dst.E_Op( DstOp.Append ty, [useVar env seq, item'])
414 : jhr 2356 in
415 : cchiw 2646 (env, Dst.S_Assign([t], exp) :: stms)
416 : cchiw 2615 end*)
417 : jhr 2632 (*
418 : cchiw 2646 | Src.OP( SrcOp.LoadImage(ty, nrrd, info), []) => let
419 : cchiw 2525 val (env, t) = doLHS()
420 : cchiw 2795 (env, [Dst.S_LoadNrrd(t, ty, nrrd)])
421 :     end*)
422 : cchiw 2670
423 :    
424 : cchiw 2791
425 : cchiw 2795 | Src.OP(rator,args) =>let
426 :     val args'=List.map (useVar env) args
427 :     val _ =List.map (fn e=> print (Dst.toString e)) args'
428 :    
429 : cchiw 2791 (*DstOP rator, original size of vector operation, args that are scalar and vectors*)
430 : cchiw 2795 fun foundVec(origrator,rator,oSize,argsS,argsV)= let
431 : cchiw 2691 val (isFill,nSize,Pieces)=Target.getVecTy oSize
432 : cchiw 2680 val (env, t) = doLHS()
433 : cchiw 2795 val stmt = LowOpToTreeOp.vecToTree(t,origrator,rator,nSize,oSize,Pieces,argsS,argsV,isFill)
434 :     val _ =testp(["\n Stmt Result: \n ", Dst.toStringS stmt,"\n******\n"])
435 : cchiw 2791 val (envv,stmts)=(case stmt
436 :     of Dst.S_Assign(_,exp)=> bind (env, lhs, exp)
437 :     | stmt=> (env,[stmt])
438 :     (*end case*))
439 : cchiw 2795 val _ = List.map (fn e=>print("\n \n\t"^Dst.toStringS e)) stmts
440 : cchiw 2691 in
441 : cchiw 2791 (envv,stmts)
442 : cchiw 2680 end
443 :     in (case (rator,args')
444 : cchiw 2795 of (SrcOp.addVec n,_) => foundVec(rator,DstOp.addVec,n,[],args')
445 :     | (SrcOp.subVec n,_) => foundVec(rator,DstOp.subVec,n,[],args')
446 :     | (SrcOp.prodScaV n,e1::es) => foundVec(rator,DstOp.prodScaV ,n, [e1], es)
447 :     | (SrcOp.prodVec n,_) => foundVec(rator,DstOp.prodVec,n,[],args')
448 :     | (SrcOp.dotVec n ,_) => foundVec(rator,DstOp.dotVec ,n,[],args')
449 :     | (SrcOp.sumVec n ,_) => foundVec(rator,DstOp.addVec ,n,[],args')
450 :     | (SrcOp.Floor n ,_) => foundVec(rator,DstOp.Floor ,n,[],args')
451 :     (* | (SrcOp.ProjectTensor(_,n,_,_),_)=>
452 :     foundVec(rator,DstOp.addVec ,n,[],args')*)
453 :    
454 :     | (SrcOp.IndexTensor(id,SrcTy.indexTy [indexTy],argTy),[Dst.E_Mux(A,isFill,oSize,DstTy.vectorLength pieces,ops)])=>let
455 :     val _ = print "\nfound indexTensor\n"
456 :     fun findVec(c,indexAt, v::vs,a1::args)=let
457 :     val newsize=c+v
458 :     in if(newsize>indexAt) then Dst.E_Op(DstOp.IndexTensor(id,DstTy.indexTy [indexAt],DstTy.TensorTy [v]), [a1])
459 :     else findVec(newsize,indexAt-v,vs,args)
460 :     end
461 :     val exp=findVec(0,indexTy,pieces,ops)
462 :     in bind (env, lhs, exp)
463 :     end
464 :    
465 :    
466 :    
467 : cchiw 2680 | (SrcOp.Kernel _,_) => (env, [])
468 :     | (SrcOp.LoadImage info,[a]) => let
469 :     (*Moved to outside*)
470 :     val dim = ImageInfo.dim info
471 :     val (env, t) = doLHS()
472 :     in
473 :     (env,[Dst.S_LoadImage(t, dim, a)])
474 :     end
475 :     | _ => let
476 : cchiw 2637 val Trator = LowOpToTreeOp.expandOp rator
477 : cchiw 2671 val exp = Dst.E_Op(Trator, args')
478 : cchiw 2620 in
479 : cchiw 2688 if isInlineOp rator then (bind (env, lhs, exp))
480 :     else (assignExp (env, exp))
481 : cchiw 2620 end
482 :     (*end case*))
483 :     end
484 : cchiw 2670
485 : cchiw 2646 | Src.APPLY(f, args) =>
486 :     bind (env, lhs, Dst.E_Apply(f, List.map (useVar env) args))
487 : cchiw 2692
488 :     | Src.CONS(ty as Ty.TensorTy[oSize], args) => let
489 :     val args'=List.map (useVar env) args
490 :     (*don't know how to tell if lhs of var is a local var, so we have to use assignExp first *)
491 :     val (envv, t) = doLHS()
492 : cchiw 2795 val _ =testp["*************\n CONS-Vector\n ",toS.rhsToString (Src.CONS(ty , args))^Dst.kindToString (DstV.kind t)]
493 : cchiw 2749
494 : cchiw 2795 val _= case peekGlobal(env, lhs)
495 :     of SOME y' =>testp["use someglobal: ", DstV.name y'," or ",DstV.name t]
496 :     | NONE => testp ["globalnone"]
497 :    
498 :    
499 : cchiw 2692 val (envvv,rst) =(case DstV.kind t
500 :     of TreeIL.VK_Local=> let
501 : cchiw 2795 val (isFill,nSize,Pieces)=Target.getVecTy oSize
502 :     val exp= LowOpToTreeOp.consVecToTree(nSize,oSize,Pieces,args',isFill)
503 : cchiw 2789 in
504 : cchiw 2692 bind (envv, lhs, exp)
505 :     end
506 : cchiw 2795 | _ =>(env,[Dst.S_Cons(t,oSize,args')])
507 : cchiw 2692 (*end case*))
508 : cchiw 2791
509 : cchiw 2795 val _ =testp[Dst.toStringSs rst,"\n END CONS \n *********************"]
510 : cchiw 2692 in
511 :     (envvv,rst)
512 :     end
513 :    
514 : cchiw 2791 | Src.CONS(ty as Ty.TensorTy [i,j], args) =>let
515 : cchiw 2795 val _ =testp["******************************\n CONS_Matrix \n "]
516 : cchiw 2791 val args' = List.map (useVar env) args
517 :     val _ =List.map (fn e=> print (Dst.toString e)) args'
518 :     (*Assume args are already Mux(Vecs)*)
519 : cchiw 2695
520 :     val (envv, t) = doLHS()
521 : cchiw 2795 val (isFill,nSize,Pieces)=Target.getVecTy j
522 :     fun multiple(0)=[]
523 :     | multiple i'=Pieces@multiple(i'-1)
524 :     val splitTy=LowILTypes.vectorLength (multiple i)
525 :     in
526 :    
527 :     (envv,[Dst.S_StoreVec(Dst.E_Var t,LowOpToTreeOp.isAligned isFill,isFill,j,ty,splitTy, args')])
528 : cchiw 2791 end
529 :    
530 : cchiw 2646 | Src.EINAPP _=> raise Fail "EINAPP in Low-IL to Tree-IL"
531 : jhr 2356 (* end case *)
532 :     end
533 : jhr 1115
534 :     (* In order to reconstruct the block-structure from the CFG, we keep a stack of open ifs.
535 :     * the items on this stack distinguish between when we are processing the then and else
536 :     * branches of the if.
537 :     *)
538 :     datatype open_if
539 :     (* working on the "then" branch. The fields are statments that preceed the if, the condition,
540 :     * and the else-branch node.
541 :     *)
542 : cchiw 2646 = THEN_BR of Dst.stm list * Dst.exp * Src.node
543 : jhr 1115 (* working on the "else" branch. The fields are statments that preceed the if, the condition,
544 :     * the "then" branch statements, and the node that terminated the "then" branch (will be
545 :     * a JOIN, DIE, or STABILIZE).
546 :     *)
547 : cchiw 2646 | ELSE_BR of Dst.stm list * Dst.exp * Dst.stm list * Src.node_kind
548 : jhr 1115
549 : cchiw 2628
550 : cchiw 2646 fun mkBlockOrig(Dst.Pink{ locals ,types,opr,body})=Dst.Block{locals=locals ,body=body}
551 :     fun peelBlockOrig(env,Dst.Pink{ locals ,types,opr,body})=let
552 : cchiw 2688 val env= setEnv(env,types,opr)
553 :     in
554 :     (env,Dst.Block{locals=locals ,body=body})
555 :     end
556 : cchiw 2637
557 : cchiw 2688
558 : cchiw 2691
559 : jhr 1115 fun trCFG (env, prefix, finish, cfg) = let
560 : cchiw 2637
561 :    
562 : cchiw 2691 (*look at stmts and collect oprSet and tySet*)
563 : cchiw 2688 fun getFNC(env,stms)=let
564 :     val t1=peelEnv(env)
565 : cchiw 2691 val (ty2,opr2)= List.foldr (fn(e1,e2) => TreeToOpr.stmtToOpr (e2,e1)) t1 stms
566 : cchiw 2688 in
567 :     setEnv(env, ty2,opr2)
568 :     end
569 :    
570 :    
571 : cchiw 2646 fun join (env, [], _, Src.JOIN _) = raise Fail "JOIN with no open if"
572 : jhr 2356 | join (env, [], stms, _) = endScope (env, prefix @ List.rev stms)
573 :     | join (env, THEN_BR(stms1, cond, elseBr)::stk, thenBlk, k) = let
574 :     val (env, thenBlk) = flushPending (env, thenBlk)
575 :     in
576 :     doNode (env, ELSE_BR(stms1, cond, thenBlk, k)::stk, [], elseBr)
577 :     end
578 :     | join (env, ELSE_BR(stms, cond, thenBlk, k1)::stk, elseBlk, k2) = let
579 :     val (env, elseBlk) = flushPending (env, elseBlk)
580 :     in
581 :     case (k1, k2)
582 : cchiw 2646 of ( Src.JOIN{phis, succ, ...}, Src.JOIN _) => let
583 : jhr 2356 val (env, [thenBlk, elseBlk]) =
584 :     List.foldl doPhi (env, [thenBlk, elseBlk]) (!phis)
585 :     val stm = mkIf(cond, List.rev thenBlk, List.rev elseBlk)
586 :     in
587 :     doNode (env, stk, stm::stms, !succ)
588 :     end
589 : cchiw 2646 | ( Src.JOIN{phis, succ, ...}, _) => let
590 : jhr 2356 val (env, [thenBlk]) = List.foldl doPhi (env, [thenBlk]) (!phis)
591 :     val stm = mkIf(cond, List.rev thenBlk, List.rev elseBlk)
592 :     in
593 :     doNode (env, stk, stm::stms, !succ)
594 :     end
595 : cchiw 2646 | (_, Src.JOIN{phis, succ, ...}) => let
596 : jhr 2356 val (env, [elseBlk]) = List.foldl doPhi (env, [elseBlk]) (!phis)
597 :     val stm = mkIf(cond, List.rev thenBlk, List.rev elseBlk)
598 :     in
599 :     doNode (env, stk, stm::stms, !succ)
600 :     end
601 :     | (_, _) => raise Fail "no path to exit unimplemented" (* FIXME *)
602 :     (* end case *)
603 :     end
604 : cchiw 2688 and doNode (env, ifStk : open_if list, stms, nd) =
605 :     (* testp ["******************* \n doNode\n ",toS.printNode (Nd.kind nd),"\n"]*)
606 :     (case Nd.kind nd
607 : cchiw 2646 of Src.NULL => raise Fail "unexpected NULL"
608 :     | Src.ENTRY{succ} => doNode (env, ifStk, stms, !succ)
609 :     | k as Src.JOIN{phis, succ, ...} => join (env, ifStk, stms, k)
610 :     | Src.COND{cond, trueBranch, falseBranch, ...} => let
611 : jhr 2356 val cond = useVar env cond
612 :     val (env, stms) = flushPending (env, stms)
613 :     in
614 :     doNode (env, THEN_BR(stms, cond, !falseBranch)::ifStk, [], !trueBranch)
615 :     end
616 : cchiw 2646 | Src.COM {text, succ, ...} =>
617 :     doNode (env, ifStk, Dst.S_Comment text :: stms, !succ)
618 :     | Src.ASSIGN{stm, succ, ...} => let
619 : jhr 2356 val (env, stms') = doAssign (env, stm)
620 : cchiw 2695
621 :    
622 : jhr 2356 in
623 : cchiw 2692 doNode (getFNC(env, stms') , ifStk, stms' @ stms, !succ)
624 : jhr 2356 end
625 : cchiw 2646 | Src.MASSIGN{stm=(ys, rator, xs), succ, ...} => let
626 : cchiw 2688
627 : jhr 1640 fun doit () = let
628 :     fun doLHSVar (y, (env, ys)) = (case peekGlobal(env, y)
629 : cchiw 2688 of SOME y' => ((env, y'::ys))
630 : cchiw 2687 | NONE => let
631 : jhr 1640 val t = newLocal y
632 : cchiw 2688
633 : jhr 1640 in
634 :     (rename (addLocal(env, t), y, t), t::ys)
635 :     end
636 :     (* end case *))
637 :     val (env, ys) = List.foldr doLHSVar (env, []) ys
638 : cchiw 2637 val Trator = LowOpToTreeOp.expandOp rator
639 : cchiw 2646 val exp = Dst.E_Op(Trator, List.map (useVar env) xs)
640 :     val stm = Dst.S_Assign(ys, exp)
641 : jhr 1640 in
642 :     doNode (env, ifStk, stm :: stms, !succ)
643 :     end
644 :     in
645 :     case rator
646 : cchiw 2646 of SrcOp.Print _ => if Target.supportsPrinting()
647 : jhr 1640 then doit ()
648 :     else doNode (env, ifStk, stms, !succ)
649 :     | _ => doit()
650 :     (* end case *)
651 :     end
652 : cchiw 2646 | Src.NEW{strand, args, succ, ...} => raise Fail "NEW unimplemented"
653 :     | Src.SAVE{lhs, rhs, succ, ...} => let
654 : cchiw 2688 (*How to get var form stateVar?*)
655 : cchiw 2692 val _=print ("\n *********** \n FOUND SAVE \n")
656 : cchiw 2680
657 : cchiw 2693 fun cat c = peek env c
658 : cchiw 2692 val n1=SrcV.useCount rhs
659 :     fun decCount ( Src.V{useCnt, ...}) = let
660 :     val n = !useCnt - 1
661 :     in
662 :     useCnt := n; (0 >= n)
663 :     end
664 : cchiw 2695
665 : cchiw 2688
666 : cchiw 2692 val stm=(case (getStateVar lhs,useVar env rhs)
667 : cchiw 2795 of (x,Dst.E_Mux(A,isFill, oSize,splitTy,args))
668 :     =>(decCount rhs ;Dst.S_StoreVec( Dst.E_State x,A,isFill, oSize,Ty.TensorTy [oSize],splitTy,args))
669 : cchiw 2789 | (x,v as Dst.E_Var rhs')=> let
670 :     val _ = print (String.concat["\t found var, rhs : ",Dst.toString v,"-- Peek ",cat rhs])
671 :     in ( case (DstV.kind rhs',DstV.rTy rhs')
672 : cchiw 2791 of (Dst.VK_Global,Ty.TensorTy [n]) => (print "copy_tensor";Dst.S_Copy([x], v,n))
673 :     | (_,Ty.TensorTy [n,m]) => (print "copy_matrix";Dst.S_Copy([x], v,n*m))
674 : cchiw 2789 | _ => Dst.S_Save([x], v)
675 :     (*end case*))
676 :     end
677 : cchiw 2749 | (x,rhs')=>(print (String.concat["\t Rest rhs: ",Dst.toString rhs',"--end "]);Dst.S_Save([x], rhs'))
678 :     (*end case*))
679 : cchiw 2795 val _ = testp (["Src.Save: ",toS.SAVEtoString(lhs,rhs),"\n New stmt --",Dst.toStringS stm])
680 : cchiw 2691 val stmts=stm::stms
681 : jhr 1640 in
682 : cchiw 2688 doNode (getFNC(env, stmts), ifStk, stmts, !succ)
683 : jhr 1640 end
684 : cchiw 2646 | k as Src.EXIT{kind, live, ...} => (case kind
685 : jhr 2356 of ExitKind.FRAGMENT =>
686 :     endScope (env, prefix @ List.revAppend(stms, finish env))
687 :     | ExitKind.SINIT => let
688 : jhr 1232 (* FIXME: we should probably call flushPending here! *)
689 : cchiw 2646 val suffix = finish env @ [Dst.S_Exit[]]
690 : jhr 2356 in
691 :     endScope (env, prefix @ List.revAppend(stms, suffix))
692 :     end
693 :     | ExitKind.RETURN => let
694 : jhr 1115 (* FIXME: we should probably call flushPending here! *)
695 : cchiw 2646 val suffix = finish env @ [Dst.S_Exit(List.map (useVar env) live)]
696 : jhr 2356 in
697 :     endScope (env, prefix @ List.revAppend(stms, suffix))
698 :     end
699 :     | ExitKind.ACTIVE => let
700 : jhr 1115 (* FIXME: we should probably call flushPending here! *)
701 : cchiw 2646 val suffix = finish env @ [Dst.S_Active]
702 : jhr 2356 in
703 :     endScope (env, prefix @ List.revAppend(stms, suffix))
704 :     end
705 :     | ExitKind.STABILIZE => let
706 : jhr 1115 (* FIXME: we should probably call flushPending here! *)
707 : cchiw 2646 val stms = Dst.S_Stabilize :: stms
708 : jhr 2356 in
709 : jhr 1115 (* FIXME: we should probably call flushPending here! *)
710 : jhr 2356 join (env, ifStk, stms, k)
711 :     end
712 : cchiw 2646 | ExitKind.DIE => join (env, ifStk, Dst.S_Die :: stms, k)
713 : jhr 2356 (* end case *))
714 :     (* end case *))
715 : jhr 2632
716 : cchiw 2628 val Y=doNode (env, [], [], CFG.entry cfg)
717 : cchiw 2637
718 : jhr 2632 in Y
719 : jhr 2356 end
720 : jhr 1115
721 : cchiw 2646 fun trInitially (env, Src.Initially{isArray, rangeInit, iters, create=(createInit, strand, args)}) =
722 : jhr 2356 let
723 : cchiw 2637 val iterPrefix = mkBlockOrig(trCFG (env, [], fn _ => [], rangeInit))
724 : jhr 2356 fun cvtIter ((param, lo, hi), (env, iters)) = let
725 :     val param' = newIter param
726 :     val env = rename (env, param, param')
727 :     in
728 :     (env, (param', useVar env lo, useVar env hi)::iters)
729 :     end
730 :     val (env, iters) = List.foldr cvtIter (env, []) iters
731 : cchiw 2637 val (env,createPrefix) = peelBlockOrig(env,trCFG (env, [], fn _ => [], createInit))
732 :     in (env,{
733 : jhr 2356 isArray = isArray,
734 :     iterPrefix = iterPrefix,
735 :     iters = iters,
736 :     createPrefix = createPrefix,
737 :     strand = strand,
738 :     args = List.map (useVar env) args
739 : cchiw 2637 }) end
740 : jhr 1115
741 : cchiw 2646 fun trMethod env ( Src.Method{name, body}) = Dst.Method{
742 : jhr 1640 name = name,
743 : cchiw 2637 body = mkBlockOrig(trCFG (env, [], fn _ => [], body))
744 : jhr 1640 }
745 : cchiw 2637
746 :    
747 :     fun trStrand(globalEnv, [],rest)=(globalEnv,rest)
748 : cchiw 2646 | trStrand(globalEnv ,( Src.Strand{name, params, state, stateInit, methods})::es,rest) = let
749 : cchiw 2637 val params' = List.map newParam params
750 :     val env = ListPair.foldlEq (fn (x, x', env) => rename(env, x, x')) globalEnv (params, params')
751 :     val (env',sInit) = peelBlockOrig(env,trCFG (env, [], fn _ => [], stateInit))
752 :    
753 : cchiw 2646 val strand'=Dst.Strand{
754 : cchiw 2637 name = name,
755 :     params = params',
756 :     state = List.map getStateVar state,
757 :     stateInit =sInit,
758 :     methods = List.map (trMethod env) methods
759 :     }
760 :     in trStrand(env', es, rest@[strand'])
761 :     end
762 :    
763 :    
764 : jhr 1115
765 : jhr 1301 (* split the globalInit into the part that specifies the inputs and the rest of
766 :     * the global initialization.
767 :     *)
768 :     fun splitGlobalInit globalInit = let
769 : cchiw 2525 (* FIXME: can split as soon as we see a non-Input statement! *)
770 : cchiw 2687
771 : cchiw 2688
772 : jhr 2356 fun walk (nd, lastInput, live) = (case Nd.kind nd
773 : cchiw 2646 of Src.ENTRY{succ} => walk (!succ, lastInput, live)
774 :     | Src.COM{succ, ...} => walk (!succ, lastInput, live)
775 :     | Src.ASSIGN{stm=(lhs, rhs), succ, ...} => (case rhs
776 :     of Src.OP(SrcOp.Input _, _) => walk (!succ, nd, lhs::live)
777 : jhr 2356 | _ => walk (!succ, lastInput, live)
778 :     (* end case *))
779 :     | _ => if Nd.isNULL lastInput
780 :     then let (* no inputs *)
781 :     val entry = Nd.mkENTRY()
782 :     val exit = Nd.mkEXIT(ExitKind.RETURN, [])
783 :     in
784 :     Nd.addEdge (entry, exit);
785 : cchiw 2646 {inputInit = Src.CFG{entry=entry, exit=exit}, globalInit = globalInit}
786 : jhr 2356 end
787 :     else let (* split at lastInput *)
788 :     val inputExit = Nd.mkEXIT(ExitKind.RETURN, live)
789 :     val globalEntry = Nd.mkENTRY()
790 :     val [gFirst] = Nd.succs lastInput
791 :     in
792 :     Nd.replaceInEdge {src = lastInput, oldDst = gFirst, dst = inputExit};
793 :     Nd.replaceOutEdge {oldSrc = lastInput, src = globalEntry, dst = gFirst};
794 :     {
795 : cchiw 2646 inputInit = Src.CFG{entry = Src.CFG.entry globalInit, exit = inputExit},
796 :     globalInit = Src.CFG{entry = globalEntry, exit = Src.CFG.exit globalInit}
797 : jhr 2356 }
798 :     end
799 :     (* end case *))
800 : cchiw 2637
801 : jhr 2356 in
802 : cchiw 2646 walk ( Src.CFG.entry globalInit, Nd.dummy, [])
803 : jhr 2356 end
804 : cchiw 2637 fun getInfo(env,Init)=let
805 :     val inputInit' = trCFG (env, [], fn _ => [], Init)
806 :     in
807 :     peelBlockOrig(env,inputInit')
808 :     end
809 :    
810 : jhr 1115 fun translate prog = let
811 : jhr 2356 (* first we do a variable analysis pass on the Low IL *)
812 : cchiw 2646 val prog as Src.Program{props, globalInit, initially, strands} = VA.optimize prog
813 : jhr 1115 (* FIXME: here we should do a contraction pass to eliminate unused variables that VA may have created *)
814 : jhr 2356 val _ = (* DEBUG *)
815 :     LowPP.output (Log.logFile(), "LowIL after variable analysis", prog)
816 : cchiw 2637 val envOrig = newEnv()
817 : jhr 2632 val globals = List.map
818 : cchiw 2637 (fn x => let val x' = newGlobal x in global(envOrig, x, x'); x' end)
819 : cchiw 2646 ( Src.CFG.liveAtExit globalInit)
820 : jhr 2356 val {inputInit, globalInit} = splitGlobalInit globalInit
821 : cchiw 2637
822 :     val (env,inputInit)=getInfo(envOrig,inputInit)
823 :     val (env,globalInit)=getInfo(env, globalInit)
824 :     val (env,strands) = trStrand (env, strands,[])
825 :     val (env, initially) = trInitially (env, initially)
826 :    
827 :     val (typs,opr)= peelEnv(env)
828 :     val typsList=TySet.listItems(typs);
829 :     val oprList=OprSet.listItems(opr);
830 : cchiw 2692 val _=testp[(Fnc.setListToString(typsList,oprList,"--FinalPostStrands--"))]
831 : cchiw 2637
832 : cchiw 2646 in Dst.Program{
833 : jhr 2632 props = props,
834 : cchiw 2637 types=typsList,
835 :     oprations = oprList,
836 : jhr 2632 globals = globals,
837 :     inputInit = inputInit,
838 :     globalInit = globalInit,
839 :     strands = strands,
840 : cchiw 2637 initially = initially
841 : jhr 2632 }
842 : jhr 2356 end
843 : jhr 1115
844 :     end

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