1 cananian 1.1.2.1 // SCCOptimize.java, created Sun Sep 20 21:41:44 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads.SCC;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.Maps.ConstMap;
7 cananian 1.1.2.1 import harpoon.Analysis.Maps.ExecMap;
8 cananian 1.1.2.1 import harpoon.Analysis.Maps.TypeMap;
9 cananian 1.1.2.1 import harpoon.Analysis.Maps.UseDefMap;
10 cananian 1.1.2.1 import harpoon.Analysis.Quads.DeadCode;
11 cananian 1.1.2.4 import harpoon.ClassFile.HClass;
12 cananian 1.1.2.4 import harpoon.ClassFile.HCode;
13 cananian 1.1.2.4 import harpoon.ClassFile.HCodeEdge;
14 cananian 1.1.2.4 import harpoon.ClassFile.HCodeElement;
15 cananian 1.1.2.4 import harpoon.ClassFile.HCodeFactory;
16 cananian 1.1.2.4 import harpoon.ClassFile.HMethod;
17 cananian 1.1.2.11 import harpoon.IR.Quads.CALL;
18 cananian 1.1.2.4 import harpoon.IR.Quads.CONST;
19 cananian 1.1.2.4 import harpoon.IR.Quads.Edge;
20 cananian 1.1.2.4 import harpoon.IR.Quads.FOOTER;
21 cananian 1.1.2.10 import harpoon.IR.Quads.METHOD;
22 cananian 1.1.2.4 import harpoon.IR.Quads.MOVE;
23 cananian 1.1.2.4 import harpoon.IR.Quads.PHI;
24 cananian 1.1.2.4 import harpoon.IR.Quads.Quad;
25 cananian 1.1.2.4 import harpoon.IR.Quads.QuadFactory;
26 cananian 1.1.2.4 import harpoon.IR.Quads.QuadVisitor;
27 cananian 1.1.2.4 import harpoon.IR.Quads.SIGMA;
28 cananian 1.1.2.13 import harpoon.IR.Quads.SWITCH;
29 cananian 1.1.2.7 import harpoon.IR.Quads.TYPESWITCH;
30 cananian 1.1.2.1 import harpoon.Temp.Temp;
31 cananian 1.6 import net.cscott.jutil.SnapshotIterator;
32 cananian 1.1.2.1 import harpoon.Util.Util;
33 cananian 1.1.2.5
34 cananian 1.1.2.7 import java.util.ArrayList;
35 cananian 1.1.2.5 import java.util.HashSet;
36 cananian 1.5 import java.util.Iterator;
37 cananian 1.1.2.7 import java.util.List;
38 cananian 1.1.2.5 import java.util.Set;
39 cananian 1.1.2.1 /**
40 cananian 1.1.2.1 * <code>SCCOptimize</code> optimizes the code after <code>SCCAnalysis</code>.
41 cananian 1.1.2.1 * The optimization invalidates the <code>ExecMap</code> used.
42 cananian 1.1.2.1 * All edges in the graph after optimization are executable.
43 cananian 1.1.2.12 * (Edges leaving a <code>CALL</code> quad may be an exception if your
44 cananian 1.1.2.12 * <code>ExecMap</code> marks one or both of the edges leaving the
45 cananian 1.1.2.12 * <code>CALL</code> non-executable.)
46 cananian 1.1.2.1 *
47 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
48 cananian 1.6 * @version $Id: SCCOptimize.java,v 1.6 2004/02/08 01:53:44 cananian Exp $
49 cananian 1.1.2.1 */
50 cananian 1.1.2.9 public final class SCCOptimize implements ExecMap {
51 cananian 1.1.2.1 TypeMap ti;
52 cananian 1.1.2.1 ConstMap cm;
53 cananian 1.1.2.1 ExecMap em;
54 cananian 1.1.2.1
55 cananian 1.1.2.1 /** Creates an <code>SCCOptimize</code>. */
56 cananian 1.1.2.1 public SCCOptimize(TypeMap ti, ConstMap cm, ExecMap em) {
57 cananian 1.1.2.1 this.ti = ti;
58 cananian 1.1.2.1 this.cm = cm;
59 cananian 1.1.2.1 this.em = em;
60 cananian 1.1.2.1 }
61 cananian 1.1.2.1 public SCCOptimize(SCCAnalysis scc) { this(scc, scc, scc); }
62 cananian 1.1.2.1
63 cananian 1.1.2.1 /** Returns a code factory that uses SCCOptimize. */
64 cananian 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent) {
65 cananian 1.1.2.1 return new HCodeFactory() {
66 cananian 1.1.2.1 public HCode convert(HMethod m) {
67 cananian 1.1.2.1 HCode hc = parent.convert(m);
68 cananian 1.1.2.1 if (hc!=null) {
69 cananian 1.1.2.1 harpoon.Analysis.UseDef ud = new harpoon.Analysis.UseDef();
70 cananian 1.1.2.1 (new SCCOptimize(new SCCAnalysis(hc, ud))).optimize(hc);
71 cananian 1.1.2.1 }
72 cananian 1.1.2.1 return hc;
73 cananian 1.1.2.1 }
74 cananian 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
75 cananian 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
76 cananian 1.1.2.1 };
77 cananian 1.1.2.1 }
78 cananian 1.1.2.1
79 cananian 1.1.2.1 Set Ee = new HashSet();
80 cananian 1.1.2.9 public boolean execMap(HCodeEdge e) {
81 cananian 1.1.2.1 if (Ee.contains(e)) return true;
82 cananian 1.1.2.1 else return em.execMap(e);
83 cananian 1.1.2.1 }
84 cananian 1.1.2.9 public boolean execMap(HCodeElement node) {
85 cananian 1.1.2.3 HCodeEdge[] pred = ((harpoon.IR.Properties.CFGraphable)node).pred();
86 cananian 1.1.2.1 for (int i=0; i<pred.length; i++)
87 cananian 1.1.2.1 if (execMap(pred[i]))
88 cananian 1.1.2.1 return true;
89 cananian 1.1.2.1 return false;
90 cananian 1.1.2.1 }
91 cananian 1.1.2.1
92 cananian 1.1.2.1 // Utility class
93 cananian 1.1.2.1 private CONST newCONST(QuadFactory qf, HCodeElement source,
94 cananian 1.1.2.1 Temp dst, Object val, HClass type) {
95 cananian 1.1.2.1 if (type==HClass.Boolean) type=HClass.Int;
96 cananian 1.1.2.1 return new CONST(qf, source, dst, val, type);
97 cananian 1.1.2.1 }
98 cananian 1.1.2.1
99 cananian 1.1.2.1 public void optimize(final HCode hc) {
100 cananian 1.1.2.1
101 cananian 1.1.2.1 QuadVisitor visitor = new QuadVisitor() {
102 cananian 1.1.2.1 public void visit(Quad q) {
103 cananian 1.1.2.1 // if all defs are constants, replace the statement
104 cananian 1.1.2.1 // with a series of CONSTs.
105 cananian 1.1.2.1 Temp d[] = q.def();
106 cananian 1.1.2.1 if (d.length == 0) return; // nothing to do here.
107 cananian 1.1.2.1 int i; for (i=0; i<d.length; i++)
108 cananian 1.1.2.1 if (!cm.isConst(q, d[i]))
109 cananian 1.1.2.1 break;
110 cananian 1.1.2.1 if (i!=d.length) // not all args are constant
111 cananian 1.1.2.1 return;
112 cananian 1.1.2.1
113 cananian 1.1.2.1 // ok. Replace with a series of CONSTs.
114 cananian 1.3.2.1 assert q.next().length==1 && q.prev().length==1;
115 cananian 1.1.2.1 Quad header = q.prev(0);
116 cananian 1.1.2.1 int which_succ = q.prevEdge(0).which_succ();
117 cananian 1.1.2.1 Quad successor = q.next(0);
118 cananian 1.1.2.1 int which_pred = q.nextEdge(0).which_pred();
119 cananian 1.1.2.1
120 cananian 1.1.2.1 for (i=0; i<d.length; i++) {
121 cananian 1.1.2.1 Quad qq = newCONST(q.getFactory(), q, d[i],
122 cananian 1.1.2.1 cm.constMap(q, d[i]),
123 cananian 1.1.2.1 ti.typeMap(q, d[i]) );
124 cananian 1.1.2.1 Quad.addEdge(header, which_succ, qq, 0);
125 cananian 1.1.2.5 Ee.add(header.nextEdge(which_succ));
126 cananian 1.1.2.1 header = qq; which_succ = 0;
127 cananian 1.1.2.1 }
128 cananian 1.1.2.1 // link to successor.
129 cananian 1.1.2.1 Quad.addEdge(header, which_succ, successor, which_pred);
130 cananian 1.1.2.5 Ee.add(header.nextEdge(which_succ));
131 cananian 1.1.2.1 // done.
132 cananian 1.1.2.1 } // END VISIT quad.
133 cananian 1.1.2.1 public void visit(CONST q) { /* do nothing. */ }
134 cananian 1.1.2.11 public void visit(METHOD q) {
135 cananian 1.1.2.11 // can't optimize if entire method is not executable.
136 cananian 1.3.2.1 assert execMap(q) && execMap(q.nextEdge(0));
137 cananian 1.1.2.11 /* do nothing. */
138 cananian 1.1.2.11 }
139 cananian 1.1.2.1 public void visit(FOOTER q) {
140 cananian 1.1.2.1 // remove unexecutable FOOTER edges.
141 cananian 1.1.2.1 FOOTER newF = q;
142 cananian 1.1.2.1 Edge[] prv = q.prevEdge();
143 cananian 1.1.2.1 for (int i=prv.length-1; i>=0; i--)
144 cananian 1.1.2.1 if (!execMap(prv[i]))
145 cananian 1.1.2.1 newF = newF.remove(i);
146 cananian 1.1.2.1 // add new executable edges to set.
147 cananian 1.1.2.1 for (int i=0; i<newF.prevLength(); i++)
148 cananian 1.1.2.5 Ee.add(newF.prevEdge(i));
149 cananian 1.1.2.7 }
150 cananian 1.1.2.7 public void visit(TYPESWITCH q) {
151 cananian 1.1.2.7 /* multiple edges of this SIGMA may be executable */
152 cananian 1.1.2.7 List keylist = new ArrayList(q.arity());
153 cananian 1.1.2.7 List edgelist = new ArrayList(q.arity());
154 cananian 1.1.2.7 // collect executable edges.
155 cananian 1.1.2.7 for (int i=0; i < q.arity(); i++)
156 cananian 1.1.2.7 if (execMap(q.nextEdge(i))) {
157 cananian 1.1.2.7 if (i<q.keysLength())
158 cananian 1.1.2.7 keylist.add(q.keys(i));
159 cananian 1.1.2.7 edgelist.add(q.nextEdge(i));
160 cananian 1.1.2.7 }
161 cananian 1.1.2.8 // default edge may not be executable.
162 cananian 1.1.2.8 boolean hasDefault = !(keylist.size() == edgelist.size());
163 cananian 1.1.2.7 // make new keys and edge array.
164 cananian 1.1.2.7 HClass[] nkeys =
165 cananian 1.1.2.7 (HClass[]) keylist.toArray(new HClass[keylist.size()]);
166 cananian 1.1.2.7 Edge[] edges =
167 cananian 1.1.2.7 (Edge[]) edgelist.toArray(new Edge[edgelist.size()]);
168 cananian 1.1.2.7 // make new dst[][] array for sigmas
169 cananian 1.1.2.7 Temp[][] ndst = new Temp[q.numSigmas()][edgelist.size()];
170 cananian 1.1.2.7 for (int i=0; i < q.numSigmas(); i++)
171 cananian 1.1.2.7 for (int j=0; j < edges.length; j++)
172 cananian 1.1.2.7 ndst[i][j] = q.dst(i, edges[j].which_succ());
173 cananian 1.1.2.7 // make new TYPESWITCH
174 cananian 1.1.2.7 TYPESWITCH nts = new TYPESWITCH(q.getFactory(), q, q.index(),
175 cananian 1.1.2.8 nkeys, ndst, q.src(),
176 cananian 1.1.2.8 hasDefault);
177 cananian 1.1.2.7 // and link the new TYPESWITCH.
178 cananian 1.1.2.7 Edge pedge = q.prevEdge(0);
179 cananian 1.1.2.7 Quad.addEdge((Quad)pedge.from(), pedge.which_succ(), nts, 0);
180 cananian 1.1.2.7 Ee.add(nts.prevEdge(0));
181 cananian 1.1.2.7 for (int i=0; i < edges.length; i++) {
182 cananian 1.1.2.7 Quad.addEdge(nts, i,
183 cananian 1.1.2.7 (Quad) edges[i].to(), edges[i].which_pred());
184 cananian 1.1.2.7 Ee.add(nts.nextEdge(i));
185 cananian 1.1.2.7 }
186 cananian 1.1.2.7 // visit(SIGMA) to trim out TYPESWITCH iff only one edge is
187 cananian 1.1.2.7 // executable
188 cananian 1.1.2.8 // (no-default typeswitch with one edge is an *assertion*.
189 cananian 1.1.2.8 // we don't want to delete it.)
190 cananian 1.1.2.8 if (hasDefault) visit((SIGMA)nts);
191 cananian 1.1.2.7 // ta-da!
192 cananian 1.1.2.12 }
193 cananian 1.1.2.13 public void visit(SWITCH q) {
194 cananian 1.1.2.13 /* multiple edges of this SIGMA may be executable */
195 cananian 1.1.2.13 List keylist = new ArrayList(q.arity());
196 cananian 1.1.2.13 List edgelist = new ArrayList(q.arity());
197 cananian 1.1.2.13 // collect executable edges.
198 cananian 1.1.2.13 for (int i=0; i < q.arity(); i++)
199 cananian 1.1.2.13 if (execMap(q.nextEdge(i))) {
200 cananian 1.1.2.13 if (i<q.keysLength())
201 cananian 1.1.2.13 keylist.add(new Integer(q.keys(i)));
202 cananian 1.1.2.13 edgelist.add(q.nextEdge(i));
203 cananian 1.1.2.13 }
204 cananian 1.1.2.13 // default edge may not be executable.
205 cananian 1.1.2.13 boolean hasDefault = !(keylist.size() == edgelist.size());
206 cananian 1.1.2.13 // if default edge isn't executable, remove last key to make
207 cananian 1.1.2.13 // new default edge.
208 cananian 1.1.2.13 if (!hasDefault) keylist.remove(keylist.size()-1);
209 cananian 1.3.2.1 assert keylist.size()+1 == edgelist.size();
210 cananian 1.1.2.13 // make new keys and edge array.
211 cananian 1.1.2.13 int[] nkeys = new int[keylist.size()];
212 cananian 1.1.2.13 for (int i=0; i<nkeys.length; i++)
213 cananian 1.1.2.13 nkeys[i] = ((Integer)keylist.get(i)).intValue();
214 cananian 1.1.2.13 Edge[] edges =
215 cananian 1.1.2.13 (Edge[]) edgelist.toArray(new Edge[edgelist.size()]);
216 cananian 1.1.2.13 // make new dst[][] array for sigmas
217 cananian 1.1.2.13 Temp[][] ndst = new Temp[q.numSigmas()][edgelist.size()];
218 cananian 1.1.2.13 for (int i=0; i < q.numSigmas(); i++)
219 cananian 1.1.2.13 for (int j=0; j < edges.length; j++)
220 cananian 1.1.2.13 ndst[i][j] = q.dst(i, edges[j].which_succ());
221 cananian 1.1.2.13 // make new SWITCH
222 cananian 1.1.2.13 SWITCH nsw = new SWITCH(q.getFactory(), q, q.index(),
223 cananian 1.1.2.13 nkeys, ndst, q.src());
224 cananian 1.1.2.13 // and link the new SWITCH.
225 cananian 1.1.2.13 Edge pedge = q.prevEdge(0);
226 cananian 1.1.2.13 Quad.addEdge((Quad)pedge.from(), pedge.which_succ(), nsw, 0);
227 cananian 1.1.2.13 Ee.add(nsw.prevEdge(0));
228 cananian 1.1.2.13 for (int i=0; i < edges.length; i++) {
229 cananian 1.1.2.13 Quad.addEdge(nsw, i,
230 cananian 1.1.2.13 (Quad) edges[i].to(), edges[i].which_pred());
231 cananian 1.1.2.13 Ee.add(nsw.nextEdge(i));
232 cananian 1.1.2.13 }
233 cananian 1.1.2.13 // visit(SIGMA) to trim out SWITCH iff only one edge is
234 cananian 1.1.2.13 // executable
235 cananian 1.1.2.13 if (edgelist.size()==1) visit((SIGMA)nsw);
236 cananian 1.1.2.13 // ta-da!
237 cananian 1.1.2.13 }
238 cananian 1.1.2.12 public void visit(CALL q) {
239 cananian 1.1.2.12 // calls are like sigmas, but we can't actually
240 cananian 1.1.2.12 // remove either of the edges.
241 cananian 1.1.2.12 // Instead, we must stub out the bogus edge with an
242 cananian 1.1.2.12 // infinite loop.
243 cananian 1.1.2.12 for (int i=0; i<q.nextLength(); i++) {
244 cananian 1.1.2.12 if (!execMap(q.nextEdge(i))) {
245 cananian 1.1.2.12 Quad loop = new PHI(q.getFactory(), q, new Temp[0], 2);
246 cananian 1.1.2.12 Quad.addEdge(q, i, loop, 0);
247 cananian 1.1.2.12 Quad.addEdge(loop, 0, loop, 1);
248 cananian 1.1.2.12 // don't add these edges to Ee because they're still
249 cananian 1.1.2.12 // not executable.
250 cananian 1.1.2.12 }
251 cananian 1.1.2.12 }
252 cananian 1.1.2.1 }
253 cananian 1.1.2.1 public void visit(SIGMA q) {
254 cananian 1.1.2.1 // if the condition is constant, link this sigma (cjmp/switch)
255 cananian 1.1.2.1 // out of existence. Either all or exactly one edge will be
256 cananian 1.1.2.1 // executable.
257 cananian 1.1.2.1 Edge[] next = q.nextEdge();
258 cananian 1.1.2.1 int i; for (i=0; i < next.length; i++)
259 cananian 1.1.2.1 if (execMap(next[i]))
260 cananian 1.1.2.1 break;
261 cananian 1.3.2.1 assert i!=next.length : q/*NO EDGES EXECUTABLE!*/;
262 cananian 1.1.2.1 if (i==next.length-1 || !execMap(next[i+1])) {
263 cananian 1.1.2.13 for (int j=i+1; j<next.length; j++)
264 cananian 1.3.2.1 assert !execMap(next[j]);
265 cananian 1.1.2.1 // only one edge is executable.
266 cananian 1.1.2.1 int liveEdge = i;
267 cananian 1.3.2.1 assert !(q instanceof CALL);
268 cananian 1.1.2.1
269 cananian 1.1.2.1 // Grab the link information from the original CJMP/SWITCH.
270 cananian 1.1.2.1 Quad header = q.prev(0);
271 cananian 1.1.2.1 int which_succ = q.prevEdge(0).which_succ();
272 cananian 1.1.2.1 Quad successor = q.next(liveEdge);
273 cananian 1.1.2.1 int which_pred = q.nextEdge(liveEdge).which_pred();
274 cananian 1.1.2.1
275 cananian 1.1.2.1 // insert a series of MOVEs to implement SIGMAs
276 cananian 1.1.2.1 for (i=0; i < q.numSigmas(); i++) {
277 cananian 1.1.2.1 Quad qq = new MOVE(q.getFactory(), q,
278 cananian 1.1.2.1 q.dst(i,liveEdge), q.src(i));
279 cananian 1.1.2.1 Quad.addEdge(header, which_succ, qq, 0);
280 cananian 1.1.2.5 Ee.add(header.nextEdge(which_succ));
281 cananian 1.1.2.1 header = qq; which_succ = 0;
282 cananian 1.1.2.1 }
283 cananian 1.1.2.1 // link to successor.
284 cananian 1.1.2.1 Quad.addEdge(header, which_succ, successor, which_pred);
285 cananian 1.1.2.5 Ee.add(header.nextEdge(which_succ));
286 cananian 1.1.2.1 }
287 cananian 1.1.2.1 } // end VISIT SIGMA
288 cananian 1.1.2.1 public void visit(PHI q) {
289 cananian 1.1.2.1 // remove non-executable edges into this PHI.
290 cananian 1.1.2.1 for (int i=0; i < q.prev().length; ) {
291 cananian 1.1.2.1 if (!execMap(q.prevEdge(i)))
292 cananian 1.1.2.1 q.removePred(i);
293 cananian 1.1.2.1 else i++;
294 cananian 1.1.2.1 }
295 cananian 1.1.2.1 // replace any phi's with constant args with a CONST.
296 cananian 1.1.2.1 for (int i=0; i < q.numPhis(); ) {
297 cananian 1.1.2.1 if (cm.isConst(q, q.dst(i))) {
298 cananian 1.1.2.1 // insert CONST.
299 cananian 1.1.2.1 Quad qq = newCONST(q.getFactory(), q, q.dst(i),
300 cananian 1.1.2.1 cm.constMap(q, q.dst(i)),
301 cananian 1.1.2.1 ti.typeMap(q, q.dst(i)) );
302 cananian 1.1.2.1 Edge edge = q.nextEdge(0);
303 cananian 1.1.2.1 Quad.addEdge(qq, 0,(Quad)edge.to(), edge.which_pred());
304 cananian 1.1.2.1 Quad.addEdge(q, 0, qq, 0);
305 cananian 1.1.2.5 Ee.add(q.nextEdge(0));
306 cananian 1.1.2.5 Ee.add(qq.nextEdge(0));
307 cananian 1.1.2.1 q.removePhi(i); // remove i'th phi function.
308 cananian 1.1.2.1 } else i++;
309 cananian 1.1.2.1 }
310 cananian 1.1.2.1 } // end VISIT PHI.
311 cananian 1.1.2.1 };
312 cananian 1.1.2.1
313 cananian 1.1.2.1 // actual traversal code.
314 cananian 1.5 for (Iterator it=new SnapshotIterator(hc.getElementsI());
315 cananian 1.5 it.hasNext(); ) {
316 cananian 1.5 Quad q = (Quad) it.next();
317 cananian 1.5 if (execMap(q))
318 cananian 1.5 q.accept(visitor);
319 cananian 1.5 }
320 cananian 1.1.2.1
321 cananian 1.1.2.1 // clean up the mess
322 cananian 1.1.2.6 DeadCode.optimize((harpoon.IR.Quads.Code)hc,
323 cananian 1.1.2.6 null /* throw away AllocationInformation */);
324 cananian 1.1.2.1 }
325 cananian 1.2 }