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-op-str-red.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-op-str-red.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 222 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/SSA/ssa-op-str-red.sml

1 : monnier 221
2 :     (*
3 :     * Operator strength reduction, Simpson/Cooper's algorithm
4 :     *)
5 :    
6 :     functor SSAOperatorStrengthReductionFn
7 :     (CF : SSA_CONSTANT_FOLDING) : SSA_OPTIMIZATION =
8 :     struct
9 :    
10 :     structure SSA = CF.SSA
11 :     structure Dom = SSA.Dom
12 :     structure I = SSA.I
13 :     structure E = SSAExp
14 :     structure G = Graph
15 :     structure A = Array
16 :     structure DA = DynamicArray
17 :     structure H = HashTable
18 :    
19 :     fun error msg =
20 :     MLRiscErrorMsg.impossible("SSAOperatorStrengthReduction."^msg)
21 :    
22 :     fun optimize(SSA as G.GRAPH ssa) =
23 :     let val Dom as G.GRAPH dom = SSA.dom SSA
24 :     val sdom = #strictly_dominates(Dom.methods Dom)
25 :     val replaceAllUses = SSA.replaceAllUses SSA
26 :     val show_op = SSA.show_op SSA
27 :     val N = #capacity ssa ()
28 :     val V = SSA.maxVar SSA
29 :    
30 :     val headers = DA.array(V,~1) (* headers of instructions *)
31 :     (* ~1 if it is not an induction variable *)
32 :     val inSCC = DA.array(N,~1) (* is the instruction in the SCC? *)
33 :    
34 :     exception NotThere
35 :    
36 :     val table = CF.hashTable(13,NotThere)
37 :     val search = H.lookup table
38 :     val insert = H.insert table
39 :     val inventName = I.C.newCell I.C.GP
40 :    
41 :     fun add(e,operands,name) = insert((e,operands),name)
42 :    
43 :     (* Return the position of an SSA op *)
44 :     fun posOf(SSA.OP{b,...}) = b
45 :     | posOf(SSA.PHI{b,...}) = b
46 :     | posOf(SSA.SINK{b,...}) = b
47 :     | posOf(SSA.SOURCE{b,...}) = b
48 :    
49 :     (* Check whether value x is a region constant *)
50 :     fun isRegionConstant(x,header) =
51 :     x < 0 orelse sdom(posOf(#node_info ssa x),header)
52 :    
53 :     (* Copy an instruction *)
54 :     fun copyDef'(SSA.OP{b,i,e,s,p,...},t) = SSA.OP{b=b,i=i,e=e,s=s,p=p,t=[t]}
55 :     | copyDef'(SSA.PHI{b,s,t',preds,...},t) =
56 :     SSA.PHI{b=b,t'=t',s=s,preds=preds,t=t}
57 :     | copyDef' _ = error "copyDef'"
58 :    
59 :     fun copyDef(x,t) =
60 :     let val i' = #node_info ssa x
61 :     val i = #new_id ssa ()
62 :     in #add_node ssa (i,copyDef'(i',t));
63 :     (i,i')
64 :     end
65 :    
66 :     (* Process each scc *)
67 :     fun processSCC ([],_) = ()
68 :     | processSCC ([n],_) = strengthReduce(n,#node_info ssa n)
69 :     | processSCC (scc as witness::_,_) =
70 :     let (* find the header block of the SCC *)
71 :     fun findHeader([],scc,h) = (scc,h)
72 :     | findHeader(i::ops,scc,h) =
73 :     let val i' = #node_info ssa i
74 :     in DA.update(inSCC,i,witness);
75 :     findHeader(ops,(i,i')::scc,
76 :     case i' of
77 :     SSA.PHI{b,...} => if h = ~1 orelse sdom(b,h)
78 :     then b else h
79 :     | _ => h
80 :     )
81 :     end
82 :     val (scc,header) = findHeader(scc,[],~1)
83 :    
84 :     (* Check whether the scc is an inductive variable *)
85 :     fun isIVSCC [] = true
86 :     | isIVSCC ((_,i')::ops) = isIVOp i' andalso isIVSCC ops
87 :    
88 :     (* is the operation a legal inductive cycle? *)
89 :     and isIVOp(SSA.PHI{s,...}) = List.all isIVorRC s
90 :     | isIVOp(SSA.OP{e=E.COPY,s=[s],...}) = isIVorRC s
91 :     | isIVOp(SSA.OP{e=E.BINOP((E.ADD | E.ADDT),_,E.ID 0 ,E.ID 1),
92 :     s=[a,b],...}) =
93 :     isIVRC(a,b) orelse isIVRC(b,a)
94 :     | isIVOp(SSA.OP{e=E.BINOP((E.SUB | E.SUBT),_,E.ID 0,E.ID 1),
95 :     s=[a,b],...}) =
96 :     isIVRC(a,b)
97 :     | isIVOp _ = false
98 :     and isIV x = x >= 0 andalso DA.sub(inSCC,x) = witness
99 :     and isRC x = x < 0 orelse isRegionConstant(x,header)
100 :     and isIVRC(a,b) = isIV a andalso isRC b
101 :     and isIVorRC x = isIV x orelse isRC x
102 :    
103 :     fun dumpSCC(title,scc) =
104 :     (print(title^"="^Int.toString header^"\n");
105 :     app (fn (_,i) => print("\t"^show_op i^"\n")) scc)
106 :    
107 :     in if isIVSCC scc then
108 :     (* found an induction variable *)
109 :     let fun mark t = DA.update(headers,t,header)
110 :     in dumpSCC("IV",scc);
111 :     app (fn (_,SSA.OP{t,...}) => app mark t
112 :     | (_,SSA.PHI{t,...}) => mark t
113 :     | _ => error "headers") scc
114 :     end
115 :     else
116 :     (app strengthReduce scc)
117 :     end
118 :    
119 :     (* perform strength reduction *)
120 :     and strengthReduce(n,n' as SSA.OP{e,t=[t],s=[a,b],...}) =
121 :     (case isInReducibleForm(e,a,b) of
122 :     SOME(iv,rc) => replace(t,e,iv,rc)
123 :     | NONE => ())
124 :     | strengthReduce _ = ()
125 :    
126 :     (* Check whether an instruction is in reducible form *)
127 :     and isInReducibleForm(e,a,b) =
128 :     let fun isIVRC(a,b) =
129 :     a >= 0 andalso
130 :     let val header_a = DA.sub(headers,a)
131 :     in header_a <> ~1 andalso isRegionConstant(b,header_a)
132 :     end
133 :     in case e of
134 :     E.BINOP((E.ADD | E.ADDT | E.MUL | E.MULT),_,E.ID 0,E.ID 1) =>
135 :     if isIVRC(a,b) then SOME(a,b)
136 :     else if isIVRC(b,a) then SOME(b,a)
137 :     else NONE
138 :     | E.BINOP((E.SUB | E.SUBT),_,E.ID 0,E.ID 1) =>
139 :     if isIVRC(a,b) then SOME(a,b) else NONE
140 :     | _ => NONE
141 :     end
142 :    
143 :     (*
144 :     * Replace the current operation with a copy from its
145 :     * reduced counterpart.
146 :     *)
147 :     and replace(t,e,iv,rc) =
148 :     let val t' = reduce(e,iv,rc)
149 :     in replaceAllUses{from=t,to=t'};
150 :     DA.update(headers,t,DA.sub(headers,iv))
151 :     end
152 :    
153 :     (*
154 :     * Insert code to strength reduce an induction variable
155 :     * and return the SSA name of the result
156 :     *)
157 :     and reduce(e,iv,rc) =
158 :     let val operands = [iv,rc]
159 :     in search(e,operands)
160 :     handle _ =>
161 :     let val result = inventName()
162 :     val _ = add(e,operands,result)
163 :     val (newDef,_) = copyDef(iv,result)
164 :     val iv_header = DA.sub(headers,iv)
165 :     val _ = DA.update(headers,result,iv_header)
166 :     fun doOperand r =
167 :     if r >= 0 andalso DA.sub(headers,r) = iv_header then
168 :     (replaceAllUses{from=r,to=reduce(e,r,rc)};())
169 :     else if r >= 0 orelse
170 :     (case e of
171 :     E.BINOP((E.MULT | E.MUL),_,E.ID 0,E.ID 1) =>
172 :     true
173 :     | _ => false
174 :     )
175 :     andalso
176 :     (case #node_info ssa r of
177 :     SSA.PHI _ => true
178 :     | _ => false) then
179 :     (replaceAllUses{from=r,to=apply(e,r,rc)}; ())
180 :     else ()
181 :     in app doOperand operands;
182 :     result
183 :     end
184 :     end
185 :    
186 :     and apply(e,op1,op2) =
187 :     let val operands = [op1,op2]
188 :     in search(e,operands)
189 :     handle _ =>
190 :     if op1 < 0 orelse
191 :     let val header_op1 = DA.sub(headers,op1)
192 :     in header_op1 <> ~1 andalso
193 :     isRegionConstant(op2,header_op1)
194 :     end then
195 :     reduce(e,op1,op2)
196 :     else if op2 < 0 orelse
197 :     let val header_op2 = DA.sub(headers,op2)
198 :     in header_op2 <> ~1 andalso
199 :     isRegionConstant(op1,header_op2)
200 :     end then
201 :     reduce(e,op2,op1)
202 :     else
203 :     let val result = inventName()
204 :     val _ = add(e,operands,result)
205 :     in result
206 :     end
207 :     end
208 :    
209 :     in (* process all loops *)
210 :     GraphSCC.scc (ReversedGraphView.rev_view SSA) processSCC ();
211 :     SSA
212 :     end
213 :    
214 :    
215 :     end
216 :    
217 :     (*
218 :     * $Log: ssa-op-str-red.sml,v $
219 :     * Revision 1.1.1.1 1998/11/16 21:47:06 george
220 :     * Version 110.10
221 :     *
222 :     *)

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