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

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