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 3502 - (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 :     val assignedVars : Simple.block -> SimpleVar.Set.set
19 : jhr 3502 val liveIn : Simple.block -> SimpleVar.Set.set
20 :     val liveOut : Simple.block -> SimpleVar.Set.set
21 : jhr 3501
22 :     end = struct
23 :    
24 :     structure S = Simple
25 :     structure SV = SimpleVar
26 :     structure VMap = SV.Map
27 :     structure VSet = SV.Set
28 :    
29 :     local
30 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
31 :     in
32 :     val assignedVars = getFn
33 :     val setAssigned = setFn
34 :     end
35 :    
36 :     local
37 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
38 :     in
39 : jhr 3502 val liveIn = getFn
40 :     val setLiveIn = setFn
41 : jhr 3501 end
42 :    
43 : jhr 3502 local
44 :     val {getFn, setFn, ...} = S.newProp (fn _ => VSet.empty)
45 :     in
46 :     val liveOut = getFn
47 :     val setLiveOut = setFn
48 :     end
49 :    
50 : jhr 3501 (* does a variable have local scope *)
51 :     fun isLocal x = (case SV.kindOf x
52 :     of SV.LocalVar => true
53 :     | SV.IterVar => true
54 :     | _ => false
55 :     (* end case *))
56 :    
57 :     fun addVar (x, vs) = if isLocal x then VSet.add(vs, x) else vs
58 :    
59 :     fun addList (xs, vs) = List.foldl addVar vs xs
60 :    
61 :     (* compute the used local variables of a Simple AST expression *)
62 :     fun addUses (e, vs) = let
63 :     val u = (case e
64 :     of S.E_Var x => [x]
65 :     | S.E_Lit _ => []
66 :     | S.E_Select(x, _) => [x]
67 :     | S.E_Apply _ => raise Fail "unexpected E_Apply"
68 :     | S.E_Prim(_, _, xs, _) => xs
69 :     | S.E_Tensor(xs, _) => xs
70 :     | S.E_Seq(xs, _) => xs
71 :     | S.E_Slice(x, indices, _) => x :: List.mapPartial Fn.id indices
72 :     | S.E_Coerce{x, ...} => [x]
73 :     | S.E_LoadSeq _ => []
74 :     | S.E_LoadImage _ => []
75 :     (* end case *))
76 :     in
77 :     addList (u, VSet.empty)
78 :     end
79 :    
80 :     fun analyze blk = let
81 : jhr 3502 fun doBlock (blk as S.Block{code, ...}, liveIn) = let
82 :     val result as (liveOut, assigns) = List.foldr doStm (liveIn, VSet.empty) code
83 : jhr 3501 in
84 :     setAssigned (blk, assigns);
85 : jhr 3502 setLiveIn (blk, liveIn);
86 :     setLiveOut (blk, liveOut);
87 : jhr 3501 result
88 :     end
89 :     and doStm (S.S_Var(x, NONE), (live, assigns)) =
90 :     (VSet.subtract(live, x), VSet.subtract(assigns, x))
91 :     | doStm (S.S_Var(x, SOME e), (live, assigns)) =
92 :     (addUses(e, VSet.subtract(live, x)), VSet.subtract(assigns, x))
93 :     | doStm (S.S_Assign(x, e), (live, assigns)) =
94 :     (addUses(e, VSet.subtract(live, x)), addVar(x, assigns))
95 : jhr 3502 | doStm (S.S_Foreach(x, _, b), (liveIn, assignsIn)) = let
96 :     val (liveOut, assigns) = doBlock (b, liveIn)
97 :     val liveOut = VSet.union(VSet.subtract(liveOut, x), liveIn)
98 :     val assigns = VSet.union(VSet.subtract(assigns, x), assignsIn)
99 : jhr 3501 in
100 :     (* QUESTION: do we want to modify the properties of b? *)
101 :     (liveOut, assigns)
102 :     end
103 : jhr 3502 | doStm (S.S_IfThenElse(_, b1, b2), (liveIn, assignsIn)) = let
104 :     val (live1, assigns1) = doBlock (b1, liveIn)
105 :     val (live2, assigns2) = doBlock (b2, liveIn)
106 :     val assigns = VSet.union(assignsIn, VSet.union(assigns1, assigns2))
107 : jhr 3501 in
108 : jhr 3502 (VSet.union(live1, live2), assigns)
109 : jhr 3501 end
110 :     | doStm (S.S_Return x, (live, assigns)) = (addVar (x, live), assigns)
111 :     | doStm (S.S_Print xs, (live, assigns)) = (addList (xs, live), assigns)
112 :     | doStm (_, acc) = acc
113 : jhr 3502 val (bnd, assigns) = doBlock (blk, VSet.empty)
114 : jhr 3501 in
115 :     ()
116 :     end
117 :    
118 :     end

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