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-glb-value-num.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-glb-value-num.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 228 - (view) (download)

1 : monnier 221 (*
2 :     * SCC based global value numbering algorithm (L Taylor Simpson's algorithm)
3 :     *
4 :     * Note: there is a bug in Simpson's algorithm involving phi-nodes.
5 :     * His algorithm assigns the same value number to two structurally
6 :     * identical SCCs. This is fine if the two SCC are in the same loop.
7 :     * However, this causes problems if the SCCs appear in distinct loops,
8 :     * or if one is nested within another in the loop structure.
9 :     *
10 :     * Allen
11 :     *)
12 :    
13 :     functor SSAGlobalValueNumberingFn
14 :     (CF : SSA_CONSTANT_FOLDING) : SSA_GLOBAL_VALUE_NUMBERING =
15 :     struct
16 :    
17 :     structure SSA = CF.SSA
18 :     structure SP = SSA.SP
19 :     structure CFG = SSA.CFG
20 :     structure Dom = SSA.Dom
21 :     structure I = SSA.I
22 :     structure E = SSAExp
23 :     structure G = Graph
24 :     structure A = Array
25 :     structure H = HashTable
26 :    
27 :     val top = CF.top
28 :    
29 :     (*
30 :     * SCC based value numbering/constant folding
31 :     *)
32 :     fun computeValueNumbers (SSA as G.GRAPH ssa) =
33 :     let val CFG as G.GRAPH cfg = SSA.cfg SSA
34 :     val Dom as G.GRAPH dom = SSA.dom SSA
35 :     val nodes = SSA.nodes SSA
36 :     val N = #capacity ssa () (* number of instructions *)
37 :     val M = #capacity cfg () (* control flow graph *)
38 :     val V = SSA.maxVar SSA (* number of variables *)
39 :     val show_op = SSA.show_op SSA
40 :     val show_val = SSA.show_val SSA
41 :    
42 :     (*
43 :     * Table mapping variables -> value numbers
44 :     *)
45 :     val VN = A.array(V,CF.top) (* value numbers *)
46 :     val DomN = A.array(N,~1) (* dominator numbers *)
47 :     val visited = BitSet.create M
48 :     fun walk(b,n) =
49 :     let val {phis,ops,sink,source} = A.sub(nodes,b)
50 :     fun number([],n) = n
51 :     | number((i,_)::ops,n) =
52 :     (A.update(DomN,i,n); number(ops,n+1))
53 :     val n = number(source,n)
54 :     val n = number(phis,n)
55 :     val n = number(ops,n)
56 :     val n = number(sink,n)
57 :     fun walkSucc([],n) = n
58 :     | walkSucc((_,b',_)::es,n) = walkSucc(es,walk(b',n))
59 :     in walkSucc(#out_edges dom b,n) end
60 :    
61 :     val _ = walk(hd(#entries dom ()),0)
62 :    
63 :     exception NotFound
64 :     val validTable = CF.hashTable(V,NotFound)
65 :     val optimisticTable = CF.hashTable(V,NotFound)
66 :     val validLookup = H.lookup validTable
67 :     val validInsert = H.insert validTable
68 :     val optimisticLookup = H.lookup optimisticTable
69 :     val optimisticInsert = H.insert optimisticTable
70 :    
71 :     fun bad(E.PHI _,operands) = List.all (fn r => r = top) operands
72 :     | bad(_,operands) = List.exists (fn r => r = top) operands
73 :    
74 :     fun check(e,operands) =
75 :     (if bad(e,operands) then
76 :     print("Bad opcode "^E.toString (map Int.toString operands) e^" "^
77 :     String.concat(map (fn r => Int.toString r^" ") operands)
78 :     ^"\n")
79 :     else ();
80 :     (e,operands))
81 :    
82 :     (* lookup value number; create new vn if not found *)
83 :     val validSearch = CF.constantFolding SSA
84 :     (fn (e,operands,t) =>
85 :     validLookup(e,operands) handle _ =>
86 :     (validInsert((* check *)(e,operands),t); t))
87 :    
88 :     val optimisticSearch = CF.constantFolding SSA
89 :     (fn (e,operands,t) =>
90 :     optimisticLookup(e,operands) handle _ =>
91 :     (optimisticInsert((* check *)(e,operands),t); t))
92 :    
93 :     fun dumpSCC ops =
94 :     let fun printVN(i,i') =
95 :     let fun pr(t) =
96 :     let val vn = A.sub(VN,t)
97 :     in if vn <> t then print(" VN="^Int.toString vn)
98 :     else ()
99 :     end
100 :     in print("\t("^Int.toString(A.sub(DomN,i))^") "^show_op i');
101 :     case i' of
102 :     SSA.OP{t=[t],...} => pr t
103 :     | SSA.PHI{t=t,...} => pr t
104 :     | _ => ();
105 :     print "\n"
106 :     end
107 :     in print "SCC=\n";
108 :     app printVN ops
109 :     end
110 :    
111 :     (*
112 :     * compute the fixpoint of an scc
113 :     *)
114 :     fun unique ts = app (fn t => A.update(VN,t,t)) ts
115 :    
116 :     fun isVolatile r = List.exists (fn r' => r' = r) SP.volatile
117 :    
118 :     fun initSource(t,t') =
119 :     let fun init(t::ts,t'::ts') =
120 :     (A.update(VN,t,
121 :     if isVolatile t' then CF.volatile else t); init(ts,ts'))
122 :     | init _ = ()
123 :     in init(t,t') end
124 :    
125 :     fun processSCC (scc,()) =
126 :     let fun init t = A.update(VN,t,top)
127 :     fun initialize([],ops) = ops
128 :     | initialize(i::is,ops) =
129 :     let val i' = #node_info ssa i
130 :     in case i' of
131 :     SSA.SOURCE{t,t',...} => initSource(t,t')
132 :     | SSA.SINK _ => ()
133 :     | SSA.OP{t,e=E.COPY,...} => app init t
134 :     | SSA.OP{t=[t],...} => init t
135 :     | SSA.OP{t,...} => unique t
136 :     | SSA.PHI{t,...} => init t;
137 :     initialize(is,(i,i')::ops)
138 :     end
139 :    
140 :     val ops = initialize(scc,[])
141 :     fun byDomN((i,_),(j,_)) = A.sub(DomN,i) < A.sub(DomN,j)
142 :     val ops = Sorting.sort byDomN ops
143 :    
144 :     fun loop([],look,more) = more
145 :     | loop((_,SSA.SOURCE _)::ops,look,more) = loop(ops,look,more)
146 :     | loop((_,SSA.SINK _)::ops,look,more) = loop(ops,look,more)
147 :     | loop((_,SSA.OP{t=[],...})::ops,look,more) = loop(ops,look,more)
148 :     | loop((_,SSA.OP{e=E.COPY,t,s,...})::ops,look,more) =
149 :     loop(ops,look,processCopy(t,s,more))
150 :     | loop((_,SSA.PHI{t,s,b,...})::ops,look,more) =
151 :     loop(ops,look,process(look,E.PHI b,t,s,more))
152 :     | loop((_,SSA.OP{e,t=[t],s,...})::ops,look,more) =
153 :     loop(ops,look,process(look,e,t,s,more))
154 :     | loop((_,SSA.OP{e,t,s,...})::ops,look,more) =
155 :     loop(ops,look,more)
156 :    
157 :     and compute_vn [] = []
158 :     | compute_vn (r::rs) =
159 :     (if r < 0 then r else A.sub(VN,r))::compute_vn rs
160 :    
161 :     and process(look,e,t,s,changed) =
162 :     let val n = look(e,compute_vn s,t)
163 :     in if A.sub(VN,t) = n then changed
164 :     else (A.update(VN,t,n); true)
165 :     end
166 :    
167 :     and processCopy(t,s,changed) =
168 :     let val vn = map (fn r => A.sub(VN,r)) s
169 :     fun update(t::ts,vn::vns,changed) =
170 :     if A.sub(VN,t) = vn then update(ts,vns,changed)
171 :     else (A.update(VN,t,vn); update(ts,vns,true))
172 :     | update(_,_,changed) = changed
173 :     in update(t,vn,changed) end
174 :    
175 :     in case ops of
176 :     [i] => (loop(ops,validSearch,false); ())
177 :     | _ => let fun iterate count =
178 :     if loop(ops,optimisticSearch,false) then
179 :     iterate(count+1)
180 :     else count
181 :     val count = iterate 1
182 :     in (* dumpSCC ops;
183 :     print("["^Int.toString(length ops)^":"^
184 :     Int.toString(count)^"]"); *)
185 :     loop(ops,validSearch,false); ()
186 :     end
187 :     end
188 :    
189 :     (*
190 :     * Initialize all value numbers
191 :     *)
192 :     fun initializeValueNumbers() =
193 :     let val ENTRY = hd(#entries dom ())
194 :     fun init s =
195 :     let val SSA.SOURCE{t,b,...} = #node_info ssa s
196 :     in unique t;
197 :     if b = ENTRY then app initEdge(#out_edges ssa s) else ()
198 :     end
199 :     and initEdge(_,_,r) = A.update(VN,r,r)
200 :     in app init (#entries ssa ());
201 :     case I.C.zero I.C.GP of
202 :     SOME zeroR => A.update(VN,zeroR,CF.zero)
203 :     | NONE => ()
204 :     end
205 :    
206 :     in initializeValueNumbers();
207 :     GraphSCC.scc (ReversedGraphView.rev_view SSA) processSCC ();
208 :     VN
209 :     end
210 :    
211 :     end
212 :    
213 :     (*
214 : monnier 227 * $Log$
215 : monnier 221 *)

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