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-vars.sml
ViewVC logotype

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

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

revision 3458, Mon Nov 23 18:11:33 2015 UTC revision 3468, Mon Nov 30 16:26:17 2015 UTC
# Line 6  Line 6 
6   *   -- for any strand parameter that is used in a method, we create a shadow state   *   -- for any strand parameter that is used in a method, we create a shadow state
7   *      variable   *      variable
8   *   *
  *   -- unused constant and global variables are elminated  
  *  
  *   -- unused strand state variables are eliminated  
  *  
  *   -- unused local variables are eliminated  
  *  
9   *   -- strand-invariant state variables (except outputs) and expressions are   *   -- strand-invariant state variables (except outputs) and expressions are
10   *      lifted to global scope   *      lifted to global scope (TODO)
11     *
12     * We assume that contraction has already been run and that unused variables have
13     * been eliminated.
14   *   *
15   * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)   * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
16   *   *
# Line 28  Line 25 
25    end = struct    end = struct
26    
27      structure S = Simple      structure S = Simple
28        structure SV = SimpleVar
29        structure VMap = SimpleVar.Map
30    
31    (* analyze an expression using the `doVar` and `doFld`    (* track if a strand parameter is referenced in a strand method *)
32     * functions to analyze variable uses.      local
33     *)        val {setFn, getFn} = SV.newFlag()
     fun analyzeExp doVar doFld = let  
           fun anal (env, e) = (case e  
                  of S.E_Var x => doVar(x, env)  
                   | S.E_Lit _ => env  
                   | S.E_Select(x, fld) => doFld (fld, doVar(x, env))  
                   | S.E_Apply(f, xs, _) => List.foldl doVar env (f::xs)  
                   | S.E_Prim(_, _, xs, _) => List.foldl doVar env xs  
                   | S.E_Tensor(xs, _) => List.foldl doVar env xs  
                   | S.E_Seq(xs, _) => List.foldl doVar env xs  
                   | S.E_Slice(x, indices, _) => let  
                       fun doIndex (NONE, env) = env  
                         | doIndex (SOME ix, env) = doVar(ix, env)  
34                        in                        in
35                          doVar (x, List.foldl doIndex env indices)        fun markUsedInMethod x = (case SV.kindOf x
36                        end               of SV.StrandParam => setFn(x, true)
37                    | S.E_Coerce{x, ...} => doVar(x, env)                | _ => ()
38                (* end case *))
39          fun isUsedInMethod x = getFn x
40          fun clrUsedInMethodMark x = setFn(x, false)
41        end (* local *)
42    
43      (* analyze a method for uses of parameters *)
44        fun analyzeMethod blk = let
45              fun analyzeBlk (S.Block stms) = List.app analyzeStm stms
46              and analyzeStm stm = (case stm
47                     of S.S_Var(x, NONE) => ()
48                      | S.S_Var(x, SOME e) => analyzeExp e
49                      | S.S_Assign(x, e) => analyzeExp e
50                      | S.S_IfThenElse(x, b1, b2) => (markUsedInMethod x; analyzeBlk b1; analyzeBlk b2)
51                      | S.S_Foreach(x, xs, blk) => analyzeBlk blk
52                      | S.S_New(strnd, xs) => List.app markUsedInMethod xs
53                      | S.S_Continue => ()
54                      | S.S_Die => ()
55                      | S.S_Stabilize => ()
56                      | S.S_Return x => markUsedInMethod x
57                      | S.S_Print xs => List.app markUsedInMethod xs
58                      | S.S_MapReduce{args, ...} => raise Fail "unexpected MapReduce in method"
59                    (* end case *))
60              and analyzeExp exp = (case exp
61                     of S.E_Var x => markUsedInMethod x
62                      | S.E_Lit _ => ()
63                      | S.E_Select(x, fld) => markUsedInMethod x
64                      | S.E_Apply(f, xs, _) => List.app markUsedInMethod xs
65                      | S.E_Prim(_, _, xs, _) => List.app markUsedInMethod xs
66                      | S.E_Tensor(xs, _) => List.app markUsedInMethod xs
67                      | S.E_Seq(xs, _) => List.app markUsedInMethod xs
68                      | S.E_Slice(x, indices, _) => (
69                          markUsedInMethod x;
70                          List.app (Option.app markUsedInMethod) indices)
71                      | S.E_Coerce{x, ...} => markUsedInMethod x
72                    | S.E_LoadSeq _ => ()                    | S.E_LoadSeq _ => ()
73                    | S.E_LoadImage _ => ()                    | S.E_LoadImage _ => ()
74                  (* end case *))                  (* end case *))
75            in            in
76              anal              analyzeBlk blk
77              end
78    
79      (* rename the free variables in a block according to the given mapping.  Variables that are
80       * not in the domain of the map are unchanged.
81       *)
82        fun renameBlock env = let
83              fun rename x = (case VMap.find(env, x)
84                     of SOME x' => x'
85                      | NONE => x
86                    (* end case *))
87              val renameList = List.map rename
88              fun renameBlk (S.Block stms) = S.Block(List.map renameStm stms)
89              and renameStm stm = (case stm
90                     of S.S_Var(x, NONE) => stm
91                      | S.S_Var(x, SOME e) => S.S_Var(x, SOME(renameExp e))
92                      | S.S_Assign(x, e) => S.S_Assign(rename x, renameExp e)
93                      | S.S_IfThenElse(x, b1, b2) =>
94                          S.S_IfThenElse(rename x, renameBlk b1, renameBlk b2)
95                      | S.S_Foreach(x, xs, blk) =>
96                          S.S_Foreach(rename x, rename xs, renameBlk blk)
97                      | S.S_New(strnd, xs) => S.S_New(strnd, renameList xs)
98                      | S.S_Continue => stm
99                      | S.S_Die => stm
100                      | S.S_Stabilize => stm
101                      | S.S_Return x => S.S_Return(rename x)
102                      | S.S_Print xs => S.S_Print(renameList xs)
103                      | S.S_MapReduce{results, reductions, body, args, source} => S.S_MapReduce{
104                            results = results,
105                            reductions = reductions,
106                            body = body,
107                            args = renameList args,
108                            source = source
109                          }
110                    (* end case *))
111              and renameExp exp = (case exp
112                     of S.E_Var x => S.E_Var(rename x)
113                      | S.E_Select(x, fld) => S.E_Select(rename x, fld)
114                      | S.E_Lit _ => exp
115                      | S.E_Apply(f, xs, ty) => S.E_Apply(f, renameList xs, ty)
116                      | S.E_Prim(f, tys, xs, ty) =>
117                          S.E_Prim(f, tys, renameList xs, ty)
118                      | S.E_Tensor(xs, ty) => S.E_Tensor(renameList xs, ty)
119                      | S.E_Seq(xs, ty) => S.E_Seq(renameList xs, ty)
120                      | S.E_Slice(x, xs, ty) =>
121                          S.E_Slice(rename x, List.map (Option.map rename) xs, ty)
122                      | S.E_Coerce{srcTy, dstTy, x} =>
123                          S.E_Coerce{srcTy=srcTy, dstTy=dstTy, x=rename x}
124                      | S.E_LoadSeq _ => exp
125                      | S.E_LoadImage _ => exp
126                    (* end case *))
127              in
128                renameBlk
129            end            end
130    
131    (* transform a strand definition.  This includes introducing shadow state variables for    (* transform a strand definition by introducing shadow state variables for
132     * parameters, eliminating unused state variables, and identifying and lifting invariant     * parameters.
    * computations.  
133     *)     *)
134      fun doStrand (S.Strand{name, params, state, stateInit, initM, updateM, stabilizeM}) = let      fun doStrand (S.Strand{name, params, state, stateInit, initM, updateM, stabilizeM}) = let
135            (* analyze the methods *)
136              val () = (
137                    Option.app analyzeMethod initM;
138                    analyzeMethod updateM;
139                    Option.app analyzeMethod stabilizeM)
140            (* identify parameters that need to be shadowed *)
141              val shadowParams = List.filter (not o isUsedInMethod) params
142              in
143                case List.filter isUsedInMethod params
144                 of [] => NONE
145                  | used => let
146                      val (shadowParams, initStms, env) = let
147                            fun f (x, (xs, stms, env)) = let
148                                    val x' = SV.copy(x, SV.StrandStateVar)
149                                    val stm = S.S_Assign(x', S.E_Var x)
150                                    in
151                                      (x'::xs, stm::stms, VMap.insert(env, x, x'))
152                                    end
153            in            in
154  ()                            List.foldr f ([], [], VMap.empty) used
155                            end
156                      val rename = renameBlock env
157                      in
158                        SOME(S.Strand{
159                            name = name, params = params,
160                            state = state @ shadowParams,
161                            stateInit = let
162                              val S.Block stms = stateInit
163                              in
164                                S.Block(stms @ initStms)
165                              end,
166                            initM = Option.map rename initM,
167                            updateM = rename updateM,
168                            stabilizeM = Option.map rename stabilizeM
169                          })
170                      end
171                (* end case *)
172            end            end
173    
174      fun transform prog = prog      fun transform prog = let
175              val S.Program{
176                      props, consts, inputs, constInit, globals, funcs, init, strand, create, update
177                    } = prog
178              in
179                case doStrand strand
180                 of NONE => prog
181                  | SOME strand => S.Program{
182                        props = props, consts = consts, inputs = inputs, constInit = constInit,
183                        globals = globals, funcs = funcs, init = init, strand = strand,
184                        create = create, update = update
185                      }
186                (* end case *)
187              end
188    
189    end    end

Legend:
Removed from v.3458  
changed lines
  Added in v.3468

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