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

SCM Repository

[diderot] Diff of /branches/vis15/src/compiler/simplify/simplify.sml
ViewVC logotype

Diff of /branches/vis15/src/compiler/simplify/simplify.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 3465, Sun Nov 29 20:04:16 2015 UTC revision 4045, Sun Jun 26 14:54:01 2016 UTC
# Line 5  Line 5 
5   * COPYRIGHT (c) 2015 The University of Chicago   * COPYRIGHT (c) 2015 The University of Chicago
6   * All rights reserved.   * All rights reserved.
7   *   *
8   * Simplify the AST representation.   * Simplify the AST representation.  This phase involves the following transformations:
9     *
10     *      - types are simplified by removing meta variables (which will have been resolved)
11     *
12     *      - expressions are simplified to involve a single operation on variables
13     *
14     *      - global reductions are converted to MapReduce statements
15     *
16     *      - other comprehensions and reductions are converted to foreach loops
17     *
18     *      - unreachable code is pruned
19     *
20     *      - negation of literal integers and reals are constant folded
21   *)   *)
22    
23  structure Simplify : sig  structure Simplify : sig
# Line 31  Line 43 
43              | Ty.T_String => STy.T_String              | Ty.T_String => STy.T_String
44              | Ty.T_Sequence(ty, NONE) => STy.T_Sequence(cvtTy ty, NONE)              | Ty.T_Sequence(ty, NONE) => STy.T_Sequence(cvtTy ty, NONE)
45              | Ty.T_Sequence(ty, SOME dim) => STy.T_Sequence(cvtTy ty, SOME(TU.monoDim dim))              | Ty.T_Sequence(ty, SOME dim) => STy.T_Sequence(cvtTy ty, SOME(TU.monoDim dim))
46              | Ty.T_Named id => STy.T_Named id              | Ty.T_Strand id => STy.T_Strand id
47              | Ty.T_Kernel n => STy.T_Kernel(TU.monoDiff n)              | Ty.T_Kernel n => STy.T_Kernel(TU.monoDiff n)
48              | Ty.T_Tensor shape => STy.T_Tensor(TU.monoShape shape)              | Ty.T_Tensor shape => STy.T_Tensor(TU.monoShape shape)
49              | Ty.T_Image{dim, shape} => STy.T_Image{              | Ty.T_Image{dim, shape} => STy.T_Image{
# Line 47  Line 59 
59              | Ty.T_Error => raise Fail "unexpected T_Error in Simplify"              | Ty.T_Error => raise Fail "unexpected T_Error in Simplify"
60            (* end case *))            (* end case *))
61    
62        fun apiTypeOf x = let
63              fun cvtTy STy.T_Bool = APITypes.BoolTy
64                | cvtTy STy.T_Int = APITypes.IntTy
65                | cvtTy STy.T_String = APITypes.StringTy
66                | cvtTy (STy.T_Sequence(ty, len)) = APITypes.SeqTy(cvtTy ty, len)
67                | cvtTy (STy.T_Tensor shape) = APITypes.TensorTy shape
68                | cvtTy (STy.T_Image{dim, shape}) = APITypes.ImageTy(dim, shape)
69                | cvtTy ty = raise Fail "bogus API type"
70              in
71                cvtTy (SimpleVar.typeOf x)
72              end
73    
74      fun newTemp ty = SimpleVar.new ("_t", SimpleVar.LocalVar, ty)      fun newTemp ty = SimpleVar.new ("_t", SimpleVar.LocalVar, ty)
75    
76    (* a property to map AST variables to SimpleAST variables *)    (* a property to map AST variables to SimpleAST variables *)
# Line 59  Line 83 
83      fun cvtVars xs = List.map cvtVar xs      fun cvtVars xs = List.map cvtVar xs
84    
85    (* make a block out of a list of statements that are in reverse order *)    (* make a block out of a list of statements that are in reverse order *)
86      fun mkBlock stms = S.Block(List.rev stms)      fun mkBlock stms = S.Block{props = PropList.newHolder(), code = List.rev stms}
87    
88      fun inputImage (errStrm, nrrd, dim, shape) = (      fun inputImage (errStrm, nrrd, dim, shape) = (
89            case ImageInfo.fromNrrd(NrrdInfo.getInfo(errStrm, nrrd), dim, shape)            case ImageInfo.fromNrrd(NrrdInfo.getInfo(errStrm, nrrd), dim, shape)
# Line 74  Line 98 
98        | CONT                    (* stm sequence falls through *)        | CONT                    (* stm sequence falls through *)
99        | EDIT of 'a              (* pruned code that has non-exiting paths *)        | EDIT of 'a              (* pruned code that has non-exiting paths *)
100    
101      fun pruneUnreachableCode (blk as S.Block stms) = let      fun pruneUnreachableCode blk = let
102            fun isExit S.S_Die = true            fun isExit S.S_Die = true
103              | isExit S.S_Stabilize = true              | isExit S.S_Stabilize = true
104              | isExit (S.S_Return _) = true              | isExit (S.S_Return _) = true
# Line 129  Line 153 
153                    | (PRUNE blk1, EXIT      ) => PRUNE(S.S_IfThenElse(x, blk1, blk2))                    | (PRUNE blk1, EXIT      ) => PRUNE(S.S_IfThenElse(x, blk1, blk2))
154                    | (PRUNE blk1, PRUNE blk2) => PRUNE(S.S_IfThenElse(x, blk1, blk2))                    | (PRUNE blk1, PRUNE blk2) => PRUNE(S.S_IfThenElse(x, blk1, blk2))
155                  (* end case *))                  (* end case *))
156            and pruneBlk (S.Block stms) = (case pruneStms stms            and pruneBlk (S.Block{props, code}) = (case pruneStms code
157                   of PRUNE stms => PRUNE(S.Block stms)                   of PRUNE stms => PRUNE(S.Block{props=props, code=stms})
158                    | EDIT stms => EDIT(S.Block stms)                    | EDIT stms => EDIT(S.Block{props=props, code=stms})
159                    | EXIT => EXIT (* different instances of ctl_flow_info *)                    | EXIT => EXIT (* different instances of ctl_flow_info *)
160                    | CONT => CONT                    | CONT => CONT
161                  (* end case *))                  (* end case *))
# Line 239  Line 263 
263                      | _ => (stms, S.E_Var(cvtVar x))                      | _ => (stms, S.E_Var(cvtVar x))
264                    (* end case *))                    (* end case *))
265                | AST.E_Lit lit => (stms, S.E_Lit lit)                | AST.E_Lit lit => (stms, S.E_Lit lit)
266                  | AST.E_Kernel h => (stms, S.E_Kernel h)
267                | AST.E_Select(e, (fld, _)) => let                | AST.E_Select(e, (fld, _)) => let
268                    val (stms, x) = simplifyExpToVar (errStrm, e, stms)                    val (stms, x) = simplifyExpToVar (errStrm, e, stms)
269                    in                    in
# Line 311  Line 336 
336                    in                    in
337                      (foreachStm :: initStm :: stms, S.E_Var acc)                      (foreachStm :: initStm :: stms, S.E_Var acc)
338                    end                    end
339                | AST.E_ParallelMap(e, x, xs, ty) => raise Fail "FIXME"                | AST.E_ParallelMap(e, x, xs, ty) => raise Fail "FIXME: ParallelMap"
340                | AST.E_Tensor(es, ty) => let                | AST.E_Tensor(es, ty) => let
341                    val (stms, xs) = simplifyExpsToVars (errStrm, es, stms)                    val (stms, xs) = simplifyExpsToVars (errStrm, es, stms)
342                    in                    in
# Line 324  Line 349 
349                    end                    end
350                | AST.E_Slice(e, indices, ty) => let (* tensor slicing *)                | AST.E_Slice(e, indices, ty) => let (* tensor slicing *)
351                    val (stms, x) = simplifyExpToVar (errStrm, e, stms)                    val (stms, x) = simplifyExpToVar (errStrm, e, stms)
352                    fun f ([], ys, stms) = (stms, List.rev ys)                    fun f NONE = NONE
353                      | f (NONE::es, ys, stms) = f (es, NONE::ys, stms)                      | f (SOME(AST.E_Lit(Literal.Int i))) = SOME(Int.fromLarge i)
354                      | f (SOME e::es, ys, stms) = let                      | f _ = raise Fail "expected integer literal in slice"
355                          val (stms, y) = simplifyExpToVar (errStrm, e, stms)                    val indices = List.map f indices
                         in  
                           f (es, SOME y::ys, stms)  
                         end  
                   val (stms, indices) = f (indices, [], stms)  
356                    in                    in
357                      (stms, S.E_Slice(x, indices, cvtTy ty))                      (stms, S.E_Slice(x, indices, cvtTy ty))
358                    end                    end
# Line 360  Line 381 
381                          (* end case *))                          (* end case *))
382                      | _ => raise Fail "bogus type for E_LoadNrrd"                      | _ => raise Fail "bogus type for E_LoadNrrd"
383                    (* end case *))                    (* end case *))
384                  | AST.E_Coerce{dstTy, e=AST.E_Lit(Literal.Int n), ...} => (case cvtTy dstTy
385                       of SimpleTypes.T_Tensor[] => (stms, S.E_Lit(Literal.Real(RealLit.fromInt n)))
386                        | _ => raise Fail "impossible: bad coercion"
387                      (* end case *))
388                | AST.E_Coerce{srcTy, dstTy, e} => let                | AST.E_Coerce{srcTy, dstTy, e} => let
389                    val (stms, x) = simplifyExpToVar (errStrm, e, stms)                    val (stms, x) = simplifyExpToVar (errStrm, e, stms)
390                    val dstTy = cvtTy dstTy                    val dstTy = cvtTy dstTy
# Line 395  Line 420 
420              f (exps, [], stms)              f (exps, [], stms)
421            end            end
422    
423      fun simplifyStrand (errStrm, AST.Strand{name, params, state, initM, updateM, stabilizeM}) = let      fun simplifyStrand (errStrm, strand) = let
424              val AST.Strand{name, params, state, stateInit, initM, updateM, stabilizeM} = strand
425            val params' = cvtVars params            val params' = cvtVars params
426            fun simplifyState ([], xs, stms) = (List.rev xs, mkBlock stms)            fun simplifyState ([], xs, stms) = (List.rev xs, mkBlock stms)
427              | simplifyState ((x, optE) :: r, xs, stms) = let              | simplifyState ((x, optE) :: r, xs, stms) = let
# Line 406  Line 432 
432                      | SOME e => let                      | SOME e => let
433                          val (stms, e') = simplifyExp (errStrm, e, stms)                          val (stms, e') = simplifyExp (errStrm, e, stms)
434                          in                          in
435                            simplifyState (r, x'::xs, S.S_Var(x', SOME e') :: stms)                            simplifyState (r, x'::xs, S.S_Assign(x', e') :: stms)
436                          end                          end
437                    (* end case *)                    (* end case *)
438                  end                  end
# Line 423  Line 449 
449                }                }
450            end            end
451    
     fun simplifyCreate (errStrm, AST.C_Grid(dim, stm)) = S.C_Grid(dim, simplifyBlock errStrm stm)  
       | simplifyCreate (errStrm, AST.C_Collection stm) = S.C_Collection(simplifyBlock errStrm stm)  
   
452      fun transform (errStrm, prog) = let      fun transform (errStrm, prog) = let
453            val AST.Program{            val AST.Program{
454                    props, const_dcls, input_dcls, globals, init, strand, create, update                    props, const_dcls, input_dcls, globals, globInit, strand, create, init, update
455                  } = prog                  } = prog
456            val consts' = ref[]            val consts' = ref[]
457            val constInit = ref[]            val constInit = ref[]
# Line 446  Line 469 
469            fun simplifyInputDcl ((x, NONE), desc) = let            fun simplifyInputDcl ((x, NONE), desc) = let
470                  val x' = cvtVar x                  val x' = cvtVar x
471                  val init = (case SimpleVar.typeOf x'                  val init = (case SimpleVar.typeOf x'
472                         of SimpleTypes.T_Image{dim, shape} => let                         of STy.T_Image{dim, shape} => let
473                              val info = ImageInfo.mkInfo(dim, shape)                              val info = ImageInfo.mkInfo(dim, shape)
474                              in                              in
475                                S.Image info                                S.Image info
# Line 455  Line 478 
478                        (* end case *))                        (* end case *))
479                  val inp = S.INP{                  val inp = S.INP{
480                          var = x',                          var = x',
481                            name = Var.nameOf x,
482                            ty =  apiTypeOf x',
483                          desc = desc,                          desc = desc,
484                          init = init                          init = init
485                        }                        }
# Line 472  Line 497 
497                        (* end case *))                        (* end case *))
498                  val inp = S.INP{                  val inp = S.INP{
499                          var = x',                          var = x',
500                            name = Var.nameOf x,
501                            ty = apiTypeOf x',
502                          desc = desc,                          desc = desc,
503                          init = init                          init = init
504                        }                        }
# Line 483  Line 510 
510                  val (stms, e') = simplifyExp (errStrm, e, [])                  val (stms, e') = simplifyExp (errStrm, e, [])
511                  val inp = S.INP{                  val inp = S.INP{
512                          var = x',                          var = x',
513                            name = Var.nameOf x,
514                            ty = apiTypeOf x',
515                          desc = desc,                          desc = desc,
516                          init = S.ConstExpr                          init = S.ConstExpr
517                        }                        }
# Line 510  Line 539 
539                  in                  in
540                    funcs := S.Func{f=f', params=params', body=body'} :: !funcs                    funcs := S.Func{f=f', params=params', body=body'} :: !funcs
541                  end                  end
542            in            val () = (
543              List.app simplifyConstDcl const_dcls;              List.app simplifyConstDcl const_dcls;
544              List.app simplifyInputDcl input_dcls;              List.app simplifyInputDcl input_dcls;
545              List.app simplifyGlobalDcl globals;                  List.app simplifyGlobalDcl globals)
546            (* make the global-initialization block *)
547              val globInit = (case globInit
548                     of SOME stm => mkBlock (simplifyStmt (errStrm, stm, !globalInit))
549                      | NONE => mkBlock (!globalInit)
550                    (* end case *))
551              in
552              S.Program{              S.Program{
553                  props = props,                  props = props,
554                  consts = List.rev(!consts'),                  consts = List.rev(!consts'),
555                  inputs = List.rev(!inputs'),                  inputs = List.rev(!inputs'),
556                  constInit = mkBlock (!constInit),                  constInit = mkBlock (!constInit),
557                  globals = List.rev(!globals'),                  globals = List.rev(!globals'),
558                  init = mkBlock (!globalInit),                  globInit = globInit,
559                  funcs = List.rev(!funcs),                  funcs = List.rev(!funcs),
560                  strand = simplifyStrand (errStrm, strand),                  strand = simplifyStrand (errStrm, strand),
561                  create = simplifyCreate (errStrm, create),                  create = Create.map (simplifyBlock errStrm) create,
562                    init = Option.map (simplifyBlock errStrm) init,
563                  update = Option.map (simplifyBlock errStrm) update                  update = Option.map (simplifyBlock errStrm) update
564                }                }
565            end            end

Legend:
Removed from v.3465  
changed lines
  Added in v.4045

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