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

SCM Repository

[diderot] Annotation of /branches/vis15/src/compiler/translate/analyze-simple.sml
ViewVC logotype

Annotation of /branches/vis15/src/compiler/translate/analyze-simple.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3538 - (view) (download)

1 : jhr 3501 (* analyze-simple.sml
2 :     *
3 :     * Analysis for Simple AST blocks. We compute the set of free local variables that
4 :     * are assigned in the block and the live variables. These pieces of information
5 :     * are stored as properties in the block and are used to generate the phi nodes in
6 :     * the CFG representation.
7 :     *
8 :     * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
9 :     *
10 :     * COPYRIGHT (c) 2015 The University of Chicago
11 :     * All rights reserved.
12 :     *)
13 :    
14 :     structure AnalyzeSimple : sig
15 :    
16 :     val analyze : Simple.block -> unit
17 :    
18 : jhr 3538 val analyzeGlobalUpdate : Simple.block option -> unit
19 :    
20 : jhr 3501 val assignedVars : Simple.block -> SimpleVar.Set.set
21 : jhr 3502 val liveIn : Simple.block -> SimpleVar.Set.set
22 :     val liveOut : Simple.block -> SimpleVar.Set.set
23 : jhr 3501
24 : jhr 3538 (* a property set on global variables that are modified during the global-update code *)
25 :     val updatedGlobal : SimpleVar.t -> bool
26 :    
27 : jhr 3501 end = struct
28 :    
29 :     structure S = Simple
30 :     structure SV = SimpleVar
31 :     structure VMap = SV.Map
32 :     structure VSet = SV.Set
33 :    
34 :     local
35 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
36 :     in
37 :     val assignedVars = getFn
38 :     val setAssigned = setFn
39 :     end
40 :    
41 :     local
42 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
43 :     in
44 : jhr 3502 val liveIn = getFn
45 :     val setLiveIn = setFn
46 : jhr 3501 end
47 :    
48 : jhr 3502 local
49 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
50 :     in
51 :     val liveOut = getFn
52 :     val setLiveOut = setFn
53 :     end
54 :    
55 : jhr 3538 (* track if a global variable is updated in the global-update code *)
56 :     local
57 :     val {setFn, getFn} = SV.newFlag()
58 :     in
59 :     val updatedGlobal = getFn
60 :     fun markUpdatedGlobal x = (case SV.kindOf x
61 :     of SV.ConstVar => raise Fail "update of ConstVar"
62 :     | SV.InputVar => setFn(x, true)
63 :     | SV.GlobalVar => setFn(x, true)
64 :     | _ => ()
65 :     (* end case *))
66 :     end (* local *)
67 :    
68 : jhr 3501 (* does a variable have local scope *)
69 :     fun isLocal x = (case SV.kindOf x
70 :     of SV.LocalVar => true
71 :     | SV.IterVar => true
72 :     | _ => false
73 :     (* end case *))
74 :    
75 :     fun addVar (x, vs) = if isLocal x then VSet.add(vs, x) else vs
76 :    
77 :     fun addList (xs, vs) = List.foldl addVar vs xs
78 :    
79 :     (* compute the used local variables of a Simple AST expression *)
80 :     fun addUses (e, vs) = let
81 :     val u = (case e
82 :     of S.E_Var x => [x]
83 :     | S.E_Lit _ => []
84 :     | S.E_Select(x, _) => [x]
85 :     | S.E_Apply _ => raise Fail "unexpected E_Apply"
86 :     | S.E_Prim(_, _, xs, _) => xs
87 :     | S.E_Tensor(xs, _) => xs
88 :     | S.E_Seq(xs, _) => xs
89 :     | S.E_Slice(x, indices, _) => x :: List.mapPartial Fn.id indices
90 :     | S.E_Coerce{x, ...} => [x]
91 :     | S.E_LoadSeq _ => []
92 :     | S.E_LoadImage _ => []
93 :     (* end case *))
94 :     in
95 :     addList (u, VSet.empty)
96 :     end
97 :    
98 :     fun analyze blk = let
99 : jhr 3502 fun doBlock (blk as S.Block{code, ...}, liveIn) = let
100 :     val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
101 : jhr 3501 in
102 :     setAssigned (blk, assigns);
103 : jhr 3502 setLiveIn (blk, liveIn);
104 :     setLiveOut (blk, liveOut);
105 : jhr 3501 result
106 :     end
107 :     and doStm (S.S_Var(x, NONE), (live, assigns)) =
108 :     (VSet.subtract(live, x), VSet.subtract(assigns, x))
109 :     | doStm (S.S_Var(x, SOME e), (live, assigns)) =
110 :     (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
111 :     | doStm (S.S_Assign(x, e), (live, assigns)) =
112 :     (addUses(e, VSet.subtract(live, x)), addVar(x, assigns))
113 : jhr 3502 | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let
114 :     val (liveOut, assigns) = doBlock (b, liveIn)
115 :     val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
116 :     val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)
117 : jhr 3501 in
118 :     (* QUESTION: do we want to modify the properties of b? *)
119 :     (liveOut, assigns)
120 :     end
121 : jhr 3502 | doStm (S.S_IfThenElse(_, b1, b2), (liveIn, assignsIn)) = let
122 :     val (live1, assigns1) = doBlock (b1, liveIn)
123 :     val (live2, assigns2) = doBlock (b2, liveIn)
124 :     val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
125 : jhr 3501 in
126 : jhr 3502 (VSet.union(live1, live2), assigns)
127 : jhr 3501 end
128 :     | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
129 :     | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
130 :     | doStm (_, acc) = acc
131 : jhr 3502 val (bnd, assigns) = doBlock (blk, VSet.empty)
132 : jhr 3501 in
133 :     ()
134 :     end
135 :    
136 : jhr 3538 fun analyzeGlobalUpdate NONE = ()
137 :     | analyzeGlobalUpdate (SOME blk) = let
138 :     (* identify and mark globals that are modified in the global-update code *)
139 :     fun doBlk (S.Block{code, ...}) = List.app doStm code
140 :     and doStm stm = (case stm
141 :     of S.S_Assign(x, _) => markUpdatedGlobal x
142 :     | S.S_IfThenElse(_, b1, b2) => (doBlk b1; doBlk b2)
143 :     | S.S_Foreach(_, _, blk) => doBlk blk
144 :     | S.S_MapReduce{results, ...} => List.app markUpdatedGlobal results
145 :     | _ => ()
146 :     (* end case *))
147 :     in
148 :     doBlk blk
149 :     end
150 :    
151 : jhr 3501 end

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