Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/SSA/ssa-gc-invariants.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-gc-invariants.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 695 - (view) (download)

1 : leunga 695 (*
2 :     * Annotate GC safety-invariants before performing SSA optimizations
3 :     *
4 :     * -- Allen (leunga@cs.nyu.edu)
5 :     *)
6 :     functor SSAGCInvariants
7 :     (structure SSA : SSA
8 :     structure TypeSys : GC_TYPE_SYSTEM
9 :     sharing SSA.RTL = TypeSys.RTL
10 :     ) : SSA_OPTIMIZATION =
11 :     struct
12 :     structure SSA = SSA
13 :     structure CFG = SSA.CFG
14 :     structure I = SSA.I
15 :     structure C = I.C
16 :     structure RTL = SSA.RTL
17 :     structure T = RTL.T
18 :     structure GCMap = TypeSys.GCMap
19 :     structure GC = GCMap.GC
20 :     structure G = Graph
21 :     structure A = Array
22 :    
23 :     type flowgraph = SSA.ssa
24 :    
25 :     val name = "GC Safety-Invariants"
26 :    
27 :     val debug = MLRiscControl.getFlag "ssa-debug-gc"
28 :    
29 :     fun error msg = MLRiscErrorMsg.error("SSAGCInvariants",msg)
30 :    
31 :     fun run SSA =
32 :     let val CFG = SSA.cfg SSA
33 :     in case #get GCMap.GCMAP (!(CFG.annotations CFG)) of
34 :     NONE => SSA
35 :     | SOME gcmap => doTheWork(SSA, CFG, gcmap)
36 :     end
37 :    
38 :     and doTheWork(SSA, CFG, gcmap) =
39 :     let val G.GRAPH ssa = SSA
40 :     val V = SSA.maxVar SSA (* maximum encoding of variables *)
41 :     val N = #capacity ssa ()
42 :     val const = SSA.const SSA (* constants map *)
43 :     val defSiteTbl = SSA.defSiteTbl SSA (* definition site *)
44 :     val cellKindMap = SSA.cellKindTbl SSA (* cellKind map *)
45 :     val defsTbl = SSA.defsTbl SSA
46 :     val usesTbl = SSA.usesTbl SSA
47 :     val rtlTbl = SSA.rtlTbl SSA
48 :     val cellKind = Intmap.mapWithDefault(cellKindMap, C.GP)
49 :     val updateTy = Intmap.add gcmap
50 :     val zeroR = case C.zeroReg C.GP of
51 :     SOME z => z
52 :     | NONE => ~1
53 :    
54 :     val gcTypes = A.array(V, GC.BOT)
55 :     val onQueue = BitSet.create N
56 :     val hasType = BitSet.create V
57 :    
58 :     fun joins [] = GC.BOT
59 :     | joins [x] = x
60 :     | joins (x::xs) = GC.join(x, joins xs)
61 :    
62 :     fun initializeTypes() =
63 :     (Intmap.app (fn (r,t) =>
64 :     (BitSet.set(hasType,r); A.update(gcTypes, r, t))) gcmap;
65 :     if zeroR >= 0 then A.update(gcTypes, zeroR, GC.CONST 0) else ()
66 :     )
67 :    
68 :     fun enqueueInsn(j, WL) =
69 :     if BitSet.markAndTest(onQueue, j) then WL
70 :     else j::WL
71 :    
72 :     fun enqueue(r, WL) =
73 :     let val i = A.sub(defSiteTbl,r)
74 :     fun ins([], WL) = WL
75 :     | ins((_,j,_)::es, WL) = ins(es, enqueueInsn(j, WL))
76 :     in ins(#out_edges ssa i, WL) end
77 :    
78 :     fun update(r, t, WL) =
79 :     if r = zeroR orelse BitSet.contains(hasType, r)
80 :     then WL
81 :     else let val t' = A.sub(gcTypes, r)
82 :     in if GC.==(t,t') then WL
83 :     else
84 :     ((* print("r"^Int.toString r^":"^GC.toString t^"\n");*)
85 :     A.update(gcTypes, r, t);
86 :     enqueue(r, WL))
87 :     end
88 :    
89 :     fun lookup r = A.sub(gcTypes, r)
90 :    
91 :     val effectOf = TypeSys.effectOf {lookup=lookup, update=update}
92 :    
93 :     fun iterate([]) = ()
94 :     | iterate(i::WL) =
95 :     let val _ = BitSet.reset(onQueue,i)
96 :     in iterate(process(i, WL)) end
97 :    
98 :     and process(i,WL) =
99 :     let val rtl = A.sub(rtlTbl,i)
100 :     val defs = A.sub(defsTbl,i)
101 :     val uses = A.sub(usesTbl,i)
102 :     in case (rtl,defs,uses) of
103 :     (T.PHI _,[t],s) => phi(t,s,WL)
104 :     | (T.SOURCE _,t,_) =>
105 :     let fun init([],WL) = WL
106 :     | init(t::ts,WL) = init(ts,setTop(t,WL))
107 :     and setTop(t,WL) =
108 :     if BitSet.contains(hasType, t) then WL
109 :     else (update(t, GC.TOP, WL))
110 :     in init(t, WL) end
111 :     | (T.SINK _, _, _) => WL
112 :     | (e, t, s) =>
113 :     let fun lookupN n =
114 :     let val r = List.nth(s,n)
115 :     in if r < 0 then GC.INT else A.sub(gcTypes,r) end
116 :     fun updateN(n, ty, WL) = update(List.nth(t,n), ty, WL)
117 :     in TypeSys.effectOf{lookup=lookupN, update=updateN}
118 :     {action=e,src=s,dst=t,effect=WL}
119 :     handle e => (print("["^Int.toString i^"] "^
120 :     SSA.showOp SSA i^"\n"); raise e)
121 :     end
122 :     end
123 :    
124 :     and phi(t, s, WL) =
125 :     if BitSet.contains(hasType, t) then WL
126 :     else let val tys = map lookup s
127 :     val ty = joins tys
128 :     in update(t, ty, WL) end
129 :    
130 :     fun updateTypes() =
131 :     A.appi (fn (r,t) => if GC.==(t,GC.TOP) then ()
132 :     else if GC.==(t,GC.BOT) then ()
133 :     else updateTy(r,t)) (gcTypes, 0, NONE)
134 :    
135 :     fun typeInference() =
136 :     let val WL = map #1 (#nodes ssa ())
137 :     in app (fn i => BitSet.set(onQueue,i)) WL;
138 :     iterate WL
139 :     end
140 :    
141 :     fun markConstraints() =
142 :     let val G.GRAPH dom = SSA.dom SSA
143 :     val {ops, ...} = SSA.nodes SSA
144 :     val showOp = SSA.showOp SSA
145 :     fun walk b =
146 :     let fun markAsNonMovable i =
147 :     (if !debug then
148 :     print("Block "^Int.toString b^" can't move: "^
149 :     showOp i^"\n")
150 :     else ();
151 :     A.update(rtlTbl, i, RTL.pin(A.sub(rtlTbl, i)))
152 :     )
153 :     fun mark(i) =
154 :     let fun isRecoverable [] = true
155 :     | isRecoverable(t::ts) =
156 :     (cellKind t = C.MEM orelse
157 :     cellKind t = C.CTRL orelse
158 :     TypeSys.isRecoverable(A.sub(gcTypes,t))) andalso
159 :     isRecoverable ts
160 :     in case A.sub(rtlTbl,i) of
161 :     (T.PHI _ | T.SOURCE _ | T.SINK _) => ()
162 :     | _ =>
163 :     if isRecoverable (A.sub(defsTbl,i)) then () (* okay *)
164 :     else markAsNonMovable i
165 :     end
166 :     in app mark (A.sub(ops, b));
167 :     app walk (#succ dom b)
168 :     end
169 :    
170 :     in walk(hd(#entries dom ()))
171 :     end
172 :    
173 :     in print "GC type inference\n";
174 :     initializeTypes();
175 :     typeInference();
176 :     updateTypes();
177 :     print "GC type inference done\n";
178 :     markConstraints();
179 :     SSA
180 :     end
181 :    
182 :     end

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