1 kkz 1.1 // RCTransformer.java, created Fri Feb 8 20:02:15 2002 by kkz
2 kkz 1.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 kkz 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1 package harpoon.Analysis.PreciseGC;
5 kkz 1.1
6 kkz 1.1 import harpoon.Analysis.ClassHierarchy;
7 kkz 1.3 import harpoon.ClassFile.HClass;
8 kkz 1.1 import harpoon.ClassFile.HCodeFactory;
9 kkz 1.1 import harpoon.ClassFile.HCode;
10 kkz 1.1 import harpoon.ClassFile.HCodeAndMaps;
11 kkz 1.1 import harpoon.ClassFile.HMethod;
12 kkz 1.3 import harpoon.ClassFile.Linker;
13 kkz 1.1 import harpoon.IR.LowQuad.PCALL;
14 kkz 1.1 import harpoon.IR.Properties.CFGEdge;
15 kkz 1.1 import harpoon.IR.Properties.UseDefer;
16 kkz 1.1 import harpoon.IR.Quads.CALL;
17 kkz 1.1 import harpoon.IR.Quads.CJMP;
18 kkz 1.1 import harpoon.IR.Quads.Code;
19 kkz 1.1 import harpoon.IR.Quads.FOOTER;
20 kkz 1.1 import harpoon.IR.Quads.METHOD;
21 kkz 1.1 import harpoon.IR.Quads.NEW;
22 kkz 1.1 import harpoon.IR.Quads.OPER;
23 kkz 1.1 import harpoon.IR.Quads.PHI;
24 kkz 1.1 import harpoon.IR.Quads.Quad;
25 kkz 1.1 import harpoon.IR.Quads.QuadFactory;
26 kkz 1.1 import harpoon.IR.Quads.QuadKind;
27 kkz 1.1 import harpoon.IR.Quads.QuadVisitor;
28 kkz 1.1 import harpoon.IR.Quads.RETURN;
29 kkz 1.1 import harpoon.IR.Quads.SET;
30 kkz 1.1 import harpoon.IR.Quads.SIGMA;
31 kkz 1.1 import harpoon.IR.Quads.SWITCH;
32 kkz 1.1 import harpoon.IR.Quads.THROW;
33 kkz 1.1 import harpoon.IR.Quads.TYPESWITCH;
34 kkz 1.1 import harpoon.Temp.Temp;
35 kkz 1.1 import harpoon.Temp.TempFactory;
36 kkz 1.1 import harpoon.Util.Tuple;
37 kkz 1.1 import harpoon.Util.Util;
38 kkz 1.1 import harpoon.Util.Worklist;
39 cananian 1.2 import harpoon.Util.Collections.WorkSet;
40 kkz 1.1
41 kkz 1.1 import java.lang.reflect.Modifier;
42 kkz 1.1 import java.util.ArrayList;
43 kkz 1.1 import java.util.Collections;
44 kkz 1.1 import java.util.HashMap;
45 kkz 1.1 import java.util.HashSet;
46 kkz 1.1 import java.util.Iterator;
47 kkz 1.1 import java.util.List;
48 kkz 1.1 import java.util.Map;
49 kkz 1.1 import java.util.Set;
50 kkz 1.1
51 kkz 1.1 /**
52 kkz 1.1 * <code>RCTransformer</code> transforms recursive constructors
53 kkz 1.1 * that build their data structures in a top-down fashion into
54 kkz 1.1 * methods that build their data structures in a bottom-up fashion.
55 kkz 1.1 * Also transforms the callers of these methods.
56 kkz 1.1 *
57 kkz 1.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
58 cananian 1.5 * @version $Id: RCTransformer.java,v 1.5 2004/02/08 03:20:07 cananian Exp $
59 kkz 1.1 */
60 kkz 1.1 public class RCTransformer extends
61 kkz 1.1 harpoon.Analysis.Transformation.MethodSplitter {
62 kkz 1.1
63 kkz 1.1 private final Set recursiveConstructors;
64 kkz 1.1
65 kkz 1.1 /** Creates a <code>RCTransformer</code>. */
66 kkz 1.3 public RCTransformer(HCodeFactory parent, ClassHierarchy ch, Linker lnkr) {
67 kkz 1.1 super(parent, ch, true/* doesn't matter */);
68 kkz 1.1 this.recursiveConstructors = new HashSet();
69 kkz 1.3 scanConstructors(parent, ch, lnkr);
70 kkz 1.1 System.out.println(recursiveConstructors.size() + " constructors");
71 kkz 1.1 }
72 kkz 1.1
73 kkz 1.1 /** The <code>CREATOR</code> token represents the transformed
74 kkz 1.1 * version of the method. */
75 kkz 1.1 public static final Token CREATOR = new Token("creator") {
76 kkz 1.1 public Object readResolve() { return CREATOR; }
77 kkz 1.1 public String toString() { return "TOKEN<CREATOR>"; }
78 kkz 1.1 };
79 kkz 1.1
80 kkz 1.1 /** Mutated constructors have signatures differing from the
81 kkz 1.1 * original.
82 kkz 1.1 */
83 kkz 1.1 protected String mutateDescriptor(HMethod hm, Token which) {
84 kkz 1.1 if (which != CREATOR) {
85 kkz 1.1 return hm.getDescriptor();
86 kkz 1.1 } else {
87 kkz 1.1 String desc = hm.getDescriptor();
88 kkz 1.1 return desc.substring(0,desc.length()-1) +
89 kkz 1.1 hm.getDeclaringClass().getDescriptor();
90 kkz 1.1 }
91 kkz 1.1 }
92 kkz 1.1
93 kkz 1.1 /** Modifies two classes of methods:
94 kkz 1.1 * - mutates recursive constructors into "creators", methods
95 kkz 1.1 * that build objects in a bottom-up fashion
96 kkz 1.1 * - modifies callers of these constructors to call the new
97 kkz 1.1 * creator methods
98 kkz 1.1 */
99 kkz 1.1 protected HCode mutateHCode(HCodeAndMaps input, Token which) {
100 kkz 1.1 Code c = (Code) input.hcode();
101 kkz 1.1 if (recursiveConstructors.size() == 0) {
102 kkz 1.1 // no need to make changes if no
103 kkz 1.1 // constructors are modifiable
104 kkz 1.1 return c;
105 kkz 1.1 } else if (which == CREATOR) {
106 kkz 1.1 makeCreator(c);
107 kkz 1.1 }
108 kkz 1.1 // modify calls for all methods including
109 kkz 1.1 // newly-minted creator methods
110 kkz 1.1 return modifyCalls(c);
111 kkz 1.1 }
112 kkz 1.1
113 kkz 1.1 /** Convert recursive constructor to a recursive
114 kkz 1.1 * creator method.
115 kkz 1.1 */
116 kkz 1.1 private Code makeCreator(Code c) {
117 kkz 1.1 // find call to superclass constructor
118 kkz 1.3 //System.out.println("Making creator");
119 kkz 1.3 //c.print(new java.io.PrintWriter(System.out), null);
120 kkz 1.1 Quad q = (Quad) c.getRootElement();
121 kkz 1.1 CFGEdge[] succs = q.succ();
122 kkz 1.1 // first Quad should be the HEADER
123 cananian 1.4 assert q.kind() == QuadKind.HEADER && succs.length == 2;
124 kkz 1.1 q = (Quad) succs[1].to();
125 kkz 1.1 succs = q.succ();
126 kkz 1.1 // second Quad should be the METHOD
127 cananian 1.4 assert q.kind() == QuadKind.METHOD && succs.length == 1;
128 kkz 1.1 METHOD omethod = (METHOD)q;
129 kkz 1.1 // get a handle on the METHOD parameters
130 kkz 1.1 Temp[] oparams = omethod.params();
131 kkz 1.1 Temp retval = oparams[0];
132 kkz 1.1 // replace METHOD
133 kkz 1.1 METHOD nmethod = replaceMETHOD(omethod, oparams);
134 kkz 1.1 q = (Quad) succs[0].to();
135 kkz 1.1 succs = q.succ();
136 kkz 1.1 // third Quad should be the CALL to the superclass constructor
137 cananian 1.4 assert q.kind() == QuadKind.CALL;
138 kkz 1.1 CALL call = (CALL)q;
139 cananian 1.4 assert call.retval() == null && call.params(0).equals(retval);
140 kkz 1.1 // create a NEW
141 kkz 1.1 NEW nnew = new NEW(call.getFactory(), call, retval,
142 kkz 1.1 c.getMethod().getDeclaringClass());
143 kkz 1.1 // put NEW before CALL (and after METHOD)
144 cananian 1.4 assert call.prevLength() == 1;
145 kkz 1.1 Quad.addEdge(call.prev(0), call.prevEdge(0).which_succ(), nnew, 0);
146 kkz 1.1 Quad.addEdge(nnew, 0, call, 0);
147 kkz 1.1 // fix-up RETURN(s)
148 kkz 1.1 call.accept(new RETURNFixUp(retval));
149 kkz 1.3 //c.print(new java.io.PrintWriter(System.out), null);
150 kkz 1.1 // start with the Quad on the 0-edge (normal return)
151 kkz 1.1 // of the call to the superclass constructor, and
152 kkz 1.1 // find the straight-line code that we want to move
153 kkz 1.1 findChain fc = new findChain(retval, nnew, call);
154 kkz 1.1 Quad end = fc.end;
155 kkz 1.1 fc = null;
156 kkz 1.3 //System.out.println(end);
157 kkz 1.1 findTemps ft = new findTemps(nmethod, nnew, call, end);
158 kkz 1.1 checkDependencies cd = new checkDependencies(nmethod, nnew, call, end);
159 kkz 1.1 // only perform transformation if possible
160 kkz 1.1 if (ft.needs.size() == 0 && ft.safe && cd.safe) {
161 kkz 1.3 //System.out.println("Safe...");
162 kkz 1.1 updateDependencies ud = new updateDependencies(nmethod, nnew, call,
163 kkz 1.1 end, c.getMethod());
164 kkz 1.3 //c.print(new java.io.PrintWriter(System.out), null);
165 kkz 1.1 Map insertPts = ud.insertPts;
166 kkz 1.1 // null out for GC
167 kkz 1.1 ud = null;
168 kkz 1.3 /*
169 cananian 1.5 for(Object keyO : insertPts.keySet())
170 kkz 1.1 {
171 cananian 1.5 Quad key = (Quad) keyO;
172 kkz 1.1 Quad[] value = (Quad[]) insertPts.get(key);
173 kkz 1.1 System.out.println(key);
174 kkz 1.1 for(int i = 0; i < value.length; i++) {
175 kkz 1.1 System.out.println(":: "+value[i]);
176 kkz 1.1 }
177 kkz 1.1 }
178 kkz 1.1 System.out.println("Done...");
179 kkz 1.3 */
180 kkz 1.1 makeRecurse mr = new makeRecurse(insertPts, nnew);
181 kkz 1.3 //c.print(new java.io.PrintWriter(System.out), null);
182 kkz 1.1 nmethod.next(0).accept(mr);
183 kkz 1.3 //c.print(new java.io.PrintWriter(System.out), null);
184 kkz 1.1 }
185 kkz 1.1 return c;
186 kkz 1.1 }
187 kkz 1.1
188 kkz 1.1
189 kkz 1.1
190 kkz 1.1 /** Replaces the <code>METHOD</code> <code>Quad</code> of the
191 kkz 1.1 * creator method with a corrected one.
192 kkz 1.1 */
193 kkz 1.1 private METHOD replaceMETHOD(METHOD omethod, Temp[] oparams) {
194 kkz 1.1 Temp[] nparams = new Temp[oparams.length-1];
195 kkz 1.1 // create a new METHOD with the right parameters
196 kkz 1.1 System.arraycopy(oparams, 1, nparams, 0, nparams.length);
197 kkz 1.1 METHOD nmethod = new METHOD(omethod.getFactory(), omethod,
198 kkz 1.1 nparams, omethod.arity());
199 kkz 1.1 Quad.replace(omethod, nmethod);
200 kkz 1.1 return nmethod;
201 kkz 1.1 }
202 kkz 1.1
203 kkz 1.1
204 kkz 1.1 /** Replaces a call to a recursive constructor with a
205 kkz 1.1 * call to the new creator method.
206 kkz 1.1 */
207 kkz 1.1 private Code modifyCalls(Code c) {
208 kkz 1.1 for(Iterator it = c.getElementsI(); it.hasNext(); ) {
209 kkz 1.1 Quad q = (Quad) it.next();
210 kkz 1.1 // modify callers of recursive constructors
211 kkz 1.1 // so that they call "creators" instead
212 kkz 1.1 if (q.kind() == QuadKind.CALL) {
213 kkz 1.1 CALL call = (CALL) q;
214 kkz 1.1 if (recursiveConstructors.contains(call.method())) {
215 kkz 1.1 // find allocation site of object being initialized
216 kkz 1.1 CFGEdge[] preds = q.pred();
217 kkz 1.1 if (preds.length == 1) {
218 kkz 1.1 Quad pred = (Quad) preds[0].from();
219 kkz 1.1 if (pred.kind() == QuadKind.NEW &&
220 kkz 1.1 ((NEW)pred).dst().equals(call.params(0))) {
221 kkz 1.1 HMethod nhm = select(call.method(), CREATOR);
222 kkz 1.1 replaceCall(call, (NEW)pred, nhm);
223 kkz 1.1 //select(call.method(), CREATOR));
224 kkz 1.1 }
225 kkz 1.1 }
226 kkz 1.1 }
227 kkz 1.1 }
228 kkz 1.1 }
229 kkz 1.1 return c;
230 kkz 1.1 }
231 kkz 1.1
232 kkz 1.1 /** Helper method that actually updates the graph by
233 kkz 1.1 * replacing a call to a recursive constructor with
234 kkz 1.1 * a call to the new creator method.
235 kkz 1.1 */
236 kkz 1.1 private static void replaceCall(CALL ocall, NEW alloc, HMethod nhm) {
237 kkz 1.1 // hack to turn constructor into static method
238 kkz 1.1 nhm.getMutator().addModifiers(Modifier.STATIC);
239 kkz 1.1 Temp[] nparams = new Temp[ocall.paramsLength()-1];
240 kkz 1.1 System.arraycopy(ocall.params(), 1, nparams, 0, nparams.length);
241 cananian 1.4 assert ocall.retval() == null;
242 kkz 1.1 CALL ncall = new CALL(ocall.getFactory(), ocall, nhm, nparams,
243 kkz 1.1 ocall.params(0), ocall.retex(),
244 kkz 1.1 ocall.isVirtual(), ocall.isTailCall(),
245 kkz 1.1 ocall.dst(), ocall.src());
246 kkz 1.3 /*
247 kkz 1.3 System.out.println("Replacing:");
248 kkz 1.1 System.out.println(alloc);
249 kkz 1.1 System.out.println(ocall);
250 kkz 1.1 System.out.println("with");
251 kkz 1.1 System.out.println(ncall);
252 kkz 1.3 */
253 kkz 1.1 // update graph
254 kkz 1.1 alloc.remove();
255 kkz 1.1 Quad.replace(ocall,ncall);
256 kkz 1.1 Quad.transferHandlers(ocall,ncall);
257 kkz 1.1 }
258 kkz 1.1
259 kkz 1.3 private void scanConstructors(HCodeFactory parent, ClassHierarchy ch,
260 kkz 1.3 Linker lnkr) {
261 kkz 1.1 // first, find constructors that call themselves
262 cananian 1.5 for(Object hmO : ch.callableMethods()) {
263 cananian 1.5 HMethod hm = (HMethod) hmO;
264 kkz 1.1 // skip methods that are not constructors
265 kkz 1.1 if (!hm.getName().equals("<init>")) continue;
266 kkz 1.1 Code c = (Code) parent.convert(hm);
267 kkz 1.3 boolean recursive = false;
268 kkz 1.1 // look for constructors that call themselves
269 kkz 1.1 for(Iterator quads = c.getElementsI(); quads.hasNext(); ) {
270 kkz 1.1 Quad q = (Quad) quads.next();
271 kkz 1.1 if (q.kind() == QuadKind.CALL &&
272 kkz 1.1 ((CALL)q).method().equals(hm)) {
273 kkz 1.1 recursiveConstructors.add(hm);
274 kkz 1.3 recursive = true;
275 kkz 1.1 break;
276 kkz 1.1 }
277 kkz 1.1 }
278 kkz 1.3 // make sure we can handle all the Quads in them
279 kkz 1.3 if (recursive) {
280 kkz 1.3 HClass exc = lnkr.forName("java.lang.Throwable");
281 kkz 1.3 for(Iterator quads = c.getElementsI(); quads.hasNext(); ) {
282 kkz 1.3 Quad q = (Quad) quads.next();
283 kkz 1.3 // we currently only handle a subset of Quads
284 kkz 1.3 if (q.kind() == QuadKind.NEW) {
285 kkz 1.3 HClass hcls = ((NEW)q).hclass();
286 kkz 1.3 if (!hcls.equals(hm.getDeclaringClass()) &&
287 kkz 1.3 !hcls.isInstanceOf(exc)) {
288 kkz 1.3 recursiveConstructors.remove(hm);
289 kkz 1.3 break;
290 kkz 1.3 }
291 kkz 1.3 } else if (q.kind() != QuadKind.CALL &&
292 kkz 1.3 q.kind() != QuadKind.CJMP &&
293 kkz 1.3 q.kind() != QuadKind.CONST &&
294 kkz 1.3 q.kind() != QuadKind.FOOTER &&
295 kkz 1.3 q.kind() != QuadKind.HEADER &&
296 kkz 1.3 q.kind() != QuadKind.METHOD &&
297 kkz 1.3 q.kind() != QuadKind.OPER &&
298 kkz 1.3 q.kind() != QuadKind.PHI &&
299 kkz 1.3 q.kind() != QuadKind.RETURN &&
300 kkz 1.3 q.kind() != QuadKind.SET &&
301 kkz 1.3 q.kind() != QuadKind.THROW) {
302 kkz 1.3 recursiveConstructors.remove(hm);
303 kkz 1.3 break;
304 kkz 1.3 }
305 kkz 1.3 }
306 kkz 1.3 }
307 kkz 1.1 }
308 kkz 1.1 }
309 kkz 1.1
310 kkz 1.1 /** Check the validity of a given <code>MethodSplitter.Token</code>.
311 kkz 1.1 */
312 kkz 1.1 protected boolean isValidToken(Token which) {
313 kkz 1.1 return which == CREATOR || super.isValidToken(which);
314 kkz 1.1 }
315 kkz 1.1
316 kkz 1.1 /** private class for traversing the graph to fix-up the
317 kkz 1.1 * RETURN nodes.
318 kkz 1.1 */
319 kkz 1.1 private static class RETURNFixUp extends QuadVisitor
320 kkz 1.1 {
321 kkz 1.1 Temp retval;
322 kkz 1.1 int nParam;
323 kkz 1.1 Map done;
324 kkz 1.1
325 kkz 1.1 RETURNFixUp(Temp retval) {
326 kkz 1.1 this.retval = retval;
327 kkz 1.1 this.nParam = 0;
328 kkz 1.1 this.done = new HashMap();
329 kkz 1.1 }
330 kkz 1.1
331 kkz 1.1 public void visit(CALL q) {
332 kkz 1.1 for(int i = 0; i < q.numSigmas(); i++) {
333 kkz 1.1 if (q.src(i).equals(retval)) {
334 kkz 1.1 for(int j = i+1; j < q.numSigmas(); j++) {
335 cananian 1.4 assert !q.src(j).equals(retval);
336 kkz 1.1 }
337 kkz 1.1 // handle normal return
338 kkz 1.1 if (i < q.numSigmas() &&
339 kkz 1.1 (retval == null || !retval.equals(q.retval())))
340 kkz 1.1 retval = q.dst(i, 0);
341 kkz 1.1 else
342 kkz 1.1 retval = null;
343 kkz 1.1 nParam = q.nextEdge(0).which_pred();
344 kkz 1.1 q.next(0).accept(this);
345 kkz 1.1 // handle exceptional return
346 kkz 1.1 if (i < q.numSigmas() &&
347 kkz 1.1 (retval == null || !retval.equals(q.retex())))
348 kkz 1.1 retval = q.dst(i, 1);
349 kkz 1.1 else
350 kkz 1.1 retval = null;
351 kkz 1.1 nParam = q.nextEdge(1).which_pred();
352 kkz 1.1 q.next(1).accept(this);
353 kkz 1.1 break;
354 kkz 1.1 }
355 kkz 1.1 }
356 kkz 1.1 }
357 kkz 1.1
358 kkz 1.1 public void visit(Quad q) {
359 kkz 1.1 if (q.nextLength() != 0) {
360 cananian 1.4 assert q.nextLength() == 1 : q;
361 kkz 1.1 if (q.defC().contains(retval))
362 kkz 1.1 retval = null;
363 kkz 1.1 nParam = q.nextEdge(0).which_pred();
364 kkz 1.1 q.next(0).accept(this);
365 kkz 1.1 }
366 kkz 1.1 }
367 kkz 1.1
368 kkz 1.1 public void visit(PHI q) {
369 kkz 1.1 for(int i = 0; i < q.numPhis(); i++) {
370 kkz 1.1 if (q.src(i, nParam).equals(retval)) {
371 kkz 1.1 for(int j = i+1; j < q.numPhis(); j++) {
372 cananian 1.4 assert !q.src(j, nParam).equals(retval);
373 kkz 1.1 }
374 kkz 1.1 if (done.containsKey(q)) {
375 kkz 1.1 // already handled once, check correctness
376 cananian 1.4 assert q.dst(i).equals(done.get(q));
377 kkz 1.1 } else {
378 kkz 1.1 retval = q.dst(i);
379 kkz 1.1 done.put(q, retval);
380 cananian 1.4 assert q.nextLength() == 1;
381 kkz 1.1 nParam = q.nextEdge(0).which_pred();
382 kkz 1.1 q.next(0).accept(this);
383 kkz 1.1 }
384 kkz 1.1 return;
385 kkz 1.1 }
386 kkz 1.1 }
387 kkz 1.1 // in some cases, we may have to add a phi function to the PHI
388 kkz 1.1 if (done.containsKey(q) && !retval.equals(done.get(q))) {
389 cananian 1.4 assert retval != null;
390 kkz 1.1 Tuple tup = (Tuple) done.get(q);
391 kkz 1.1 Temp[] retvals = (Temp[]) tup.proj(0);
392 kkz 1.1 int count = ((Integer) tup.proj(1)).intValue();
393 kkz 1.1 if (count == q.arity()-1) {
394 kkz 1.1 // fix-up PHI
395 kkz 1.1 Temp dst[] = new Temp[q.numPhis()+1];
396 kkz 1.1 Temp src[][] = new Temp[q.numPhis()+1][];
397 kkz 1.1 for(int i = 0; i < q.numPhis(); i++)
398 kkz 1.1 dst[i] = q.dst(i);
399 kkz 1.1 // new destination Temp
400 kkz 1.1 dst[dst.length-1] = new Temp(q.getFactory().tempFactory());
401 kkz 1.1 for(int i = 0; i < q.numPhis(); i++)
402 kkz 1.1 src[i] = q.src(i);
403 kkz 1.1 retvals[nParam] = retval;
404 kkz 1.1 src[src.length-1] = retvals;
405 kkz 1.1 PHI phi = new PHI(q.getFactory(), q, dst, src, q.arity());
406 kkz 1.1 Quad.replace(q, phi);
407 kkz 1.1 retval = dst[dst.length-1];
408 cananian 1.4 assert phi.nextLength() == 1;
409 kkz 1.1 nParam = phi.nextEdge(0).which_pred();
410 kkz 1.1 phi.next(0).accept(this);
411 kkz 1.1 } else {
412 kkz 1.1 retvals[nParam] = retval;
413 kkz 1.1 done.put(q, new Tuple(new Object[]
414 kkz 1.1 { retvals, new Integer(count+1) }));
415 kkz 1.1 }
416 kkz 1.1 } else {
417 kkz 1.1 Temp[] retvals = new Temp[q.arity()];
418 cananian 1.4 assert retval != null;
419 kkz 1.1 retvals[nParam] = retval;
420 kkz 1.1 done.put(q, new Tuple(new Object[] {retvals, new Integer(1)}));
421 kkz 1.1 }
422 kkz 1.1 }
423 kkz 1.1
424 kkz 1.1 public void visit(RETURN q) {
425 cananian 1.4 assert retval != null;
426 kkz 1.1 RETURN nreturn = new RETURN(q.getFactory(), q, retval);
427 kkz 1.1 Quad.replace(q, nreturn);
428 kkz 1.1 // RETURNs only have one successor, the FOOTER node,
429 kkz 1.1 // which we don't need to visit
430 kkz 1.1 }
431 kkz 1.1
432 kkz 1.1 public void visit(SIGMA q) {
433 kkz 1.1 for(int i = 0; i < q.numSigmas(); i++) {
434 kkz 1.1 if (q.src(i).equals(retval)) {
435 kkz 1.1 for(int j = i+1; j < q.numSigmas(); j++) {
436 cananian 1.4 assert !q.src(j).equals(retval);
437 kkz 1.1 }
438 kkz 1.1 for(int k = 0; k < q.arity(); k++) {
439 kkz 1.1 retval = q.dst(i, k);
440 kkz 1.1 nParam = q.nextEdge(k).which_pred();
441 kkz 1.1 q.next(k).accept(this);
442 kkz 1.1 }
443 kkz 1.1 return;
444 kkz 1.1 }
445 kkz 1.1 }
446 cananian 1.4 assert false;
447 kkz 1.1 }
448 kkz 1.1 }
449 kkz 1.1
450 kkz 1.1 /** private class for traversing the graph to find the
451 kkz 1.1 * straight-line code that needs to be moved.
452 kkz 1.1 */
453 kkz 1.1 private static class findChain extends QuadVisitor
454 kkz 1.1 {
455 kkz 1.1 Temp thisObj;
456 kkz 1.1 Quad end; // last Quad that needs *this* before control flow split
457 kkz 1.1
458 kkz 1.1 findChain(Temp thisObj, NEW nnew, CALL call) {
459 kkz 1.1 this.thisObj = thisObj;
460 kkz 1.1 for(int i = 0; i < call.numSigmas(); i++) {
461 kkz 1.1 if (call.src(i).equals(thisObj)) {
462 kkz 1.1 this.thisObj = call.dst(i, 0);
463 kkz 1.1 break;
464 kkz 1.1 }
465 kkz 1.1 }
466 kkz 1.1 // start with the Quad on the 0-edge (normal return)
467 kkz 1.1 // of the call to the superclass constructor
468 kkz 1.1 call.next(0).accept(this);
469 kkz 1.1 }
470 kkz 1.1
471 kkz 1.1 // done when we hit a control flow split
472 kkz 1.1 public void visit(SIGMA q) {
473 kkz 1.1 return;
474 kkz 1.1 }
475 kkz 1.1
476 kkz 1.1 public void visit(PHI q) {
477 cananian 1.4 assert false : "Cannot be transformed.";
478 kkz 1.1 }
479 kkz 1.1
480 kkz 1.1 public void visit(Quad q) {
481 kkz 1.1 if (q.useC().contains(thisObj))
482 kkz 1.1 end = q;
483 cananian 1.4 assert q.nextLength() == 1 : "Unexpected Quad.";
484 kkz 1.1 q.next(0).accept(this);
485 kkz 1.1 }
486 kkz 1.1 }
487 kkz 1.1
488 kkz 1.1 /** private class for traversing the graph to find
489 kkz 1.1 * the <code>Temp</code>s used by a chain of
490 kkz 1.1 * straight-line code.
491 kkz 1.1 */
492 kkz 1.1 private static class findTemps extends QuadVisitor
493 kkz 1.1 {
494 kkz 1.1 Quad end; // last Quad
495 kkz 1.1 CALL call;
496 kkz 1.1 Set needs;
497 kkz 1.1 Set gen;
498 kkz 1.1 Set protect;
499 kkz 1.1 Map tMap;
500 kkz 1.1 boolean safe;
501 kkz 1.1
502 kkz 1.1 findTemps(METHOD method, NEW nnew, CALL call, Quad end) {
503 kkz 1.1 this.end = end;
504 kkz 1.1 this.call = call;
505 kkz 1.1 this.gen = new HashSet();
506 kkz 1.1 this.needs = new HashSet();
507 kkz 1.1 this.protect = new HashSet();
508 kkz 1.1 this.tMap = new HashMap();
509 kkz 1.1 this.safe = true;
510 kkz 1.1 // handle NEW
511 kkz 1.1 gen.add(nnew.dst());
512 kkz 1.1 // handle CALL
513 kkz 1.1 for(int i = 0; i < call.paramsLength(); i++) {
514 kkz 1.1 if (!gen.contains(call.params(0)))
515 kkz 1.1 needs.add(call.params(0));
516 kkz 1.1 }
517 kkz 1.1 gen.add(call.retval());
518 kkz 1.1 // build protected set of Temps
519 kkz 1.1 for(int i = 0; i < method.paramsLength(); i++) {
520 kkz 1.1 Temp t = method.params(i);
521 kkz 1.1 protect.add(t);
522 kkz 1.1 for(int j = 0; j < call.numSigmas(); j++) {
523 kkz 1.1 if (call.src(j).equals(t)) {
524 kkz 1.1 protect.remove(t);
525 kkz 1.1 protect.add(call.dst(j,0));
526 kkz 1.1 break;
527 kkz 1.1 }
528 kkz 1.1 }
529 kkz 1.1 }
530 kkz 1.1 // build mapping of Temps
531 kkz 1.1 for(int i = 0; i < call.numSigmas(); i++) {
532 kkz 1.1 tMap.put(call.dst(i,0), call.src(i));
533 kkz 1.1 }
534 kkz 1.1 // start with the Quad on the 0-edge (normal return)
535 kkz 1.1 // of the call to the superclass constructor
536 kkz 1.1 call.next(0).accept(this);
537 kkz 1.1 }
538 kkz 1.1
539 kkz 1.1 // done when we hit a control flow split
540 kkz 1.1 public void visit(SIGMA q) {
541 cananian 1.4 assert false : "Invalid sequence.";
542 kkz 1.1 }
543 kkz 1.1
544 kkz 1.1 public void visit(PHI q) {
545 cananian 1.4 assert false : "Invalid sequence.";
546 kkz 1.1 }
547 kkz 1.1
548 kkz 1.1 public void visit(Quad q) {
549 cananian 1.5 for(Object tO : q.useC()) {
550 cananian 1.5 Temp t = (Temp) tO;
551 kkz 1.1 Temp m = (Temp) tMap.get(t);
552 kkz 1.1 t = (m == null) ? t : m;
553 kkz 1.1 if (!gen.contains(t))
554 kkz 1.1 needs.add(t);
555 kkz 1.1 }
556 cananian 1.5 for(Object tO : q.defC()) {
557 cananian 1.5 Temp t = (Temp) tO;
558 kkz 1.1 if (protect.contains(t)) {
559 kkz 1.1 safe = false;
560 kkz 1.1 return;
561 kkz 1.1 }
562 kkz 1.1 Temp m = (Temp) tMap.get(t);
563 kkz 1.1 t = (m == null) ? t : m;
564 kkz 1.1 gen.add(t);
565 kkz 1.1 }
566 cananian 1.4 assert q.nextLength() == 1 : "Unexpected Quad.";
567 kkz 1.1 if (!q.equals(end))
568 kkz 1.1 q.next(0).accept(this);
569 kkz 1.1 }
570 kkz 1.1 }
571 kkz 1.1
572 kkz 1.1 /** private class for traversing the graph as setup for
573 kkz 1.1 * conversion to recursive form.
574 kkz 1.1 */
575 kkz 1.1 private static class checkDependencies extends QuadVisitor
576 kkz 1.1 {
577 kkz 1.1 Temp thisObj;
578 kkz 1.1 Set phis;
579 kkz 1.1 Set gen;
580 kkz 1.1 boolean safe;
581 kkz 1.1 int nParam;
582 kkz 1.1
583 kkz 1.1 checkDependencies(METHOD method, NEW nnew, CALL call, Quad start) {
584 kkz 1.1 this.gen = new HashSet();
585 kkz 1.1 this.safe = true;
586 kkz 1.1 this.phis = new HashSet();
587 kkz 1.1 this.thisObj = nnew.dst();
588 kkz 1.1 // map thisObj to appropriate post-call Temp
589 kkz 1.1 for(int i = 0; i < call.numSigmas(); i++) {
590 kkz 1.1 if (call.src(i).equals(thisObj))
591 kkz 1.1 thisObj = call.dst(i, 0);
592 kkz 1.1 }
593 kkz 1.1 // assumes that the only available Temps are
594 kkz 1.1 // the method parameters
595 kkz 1.1 for(int i = 0; i < method.paramsLength(); i++) {
596 kkz 1.1 Temp t = method.params(i);
597 kkz 1.1 gen.add(t);
598 kkz 1.1 for(int j = 0; j < call.numSigmas(); j++) {
599 kkz 1.1 if (call.src(j).equals(t)) {
600 kkz 1.1 gen.remove(t);
601 kkz 1.1 gen.add(call.dst(j, 0));
602 kkz 1.1 }
603 kkz 1.1 }
604 kkz 1.1 }
605 kkz 1.1 // start with the next Quad
606 cananian 1.4 assert start.nextLength() == 1;
607 kkz 1.1 nParam = start.nextEdge(0).which_pred();
608 kkz 1.1 start.next(0).accept(this);
609 kkz 1.1 }
610 kkz 1.1
611 kkz 1.1 public void visit(CALL q) {
612 kkz 1.1 for(int i = 0; i < q.paramsLength(); i++) {
613 kkz 1.1 if (!gen.contains(q.params(i))) {
614 kkz 1.1 safe = false;
615 kkz 1.3 //System.out.println(q + " needs " + q.params(i));
616 kkz 1.1 return;
617 kkz 1.1 }
618 kkz 1.1 }
619 kkz 1.1 Temp savedThis = thisObj;
620 kkz 1.1 Set savedGen = gen;
621 kkz 1.1 for(int i = 0; i < q.arity(); i++) {
622 kkz 1.1 // fixup thisObj
623 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
624 kkz 1.1 if (q.src(j).equals(savedThis)) {
625 kkz 1.1 thisObj = q.dst(j, i);
626 kkz 1.1 break;
627 kkz 1.1 }
628 kkz 1.1 }
629 kkz 1.1 // fixup gen
630 kkz 1.1 gen = new HashSet();
631 kkz 1.1 if (i == 0) {
632 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
633 kkz 1.1 if (q.src(j).equals(q.retval())) {
634 kkz 1.1 gen.add(q.dst(j, 0));
635 kkz 1.1 break;
636 kkz 1.1 }
637 kkz 1.1 }
638 kkz 1.1 } else {
639 cananian 1.4 assert i == 1;
640 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
641 kkz 1.1 if (q.src(j).equals(q.retex())) {
642 kkz 1.1 gen.add(q.dst(j, 1));
643 kkz 1.1 break;
644 kkz 1.1 }
645 kkz 1.1 }
646 kkz 1.1 }
647 cananian 1.5 for(Object tO : savedGen) {
648 cananian 1.5 Temp t = (Temp) tO;
649 kkz 1.1 gen.add(t);
650 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
651 kkz 1.1 if (q.src(j).equals(t)) {
652 kkz 1.1 gen.remove(t);
653 kkz 1.1 gen.add(q.dst(j, i));
654 kkz 1.1 }
655 kkz 1.1 }
656 kkz 1.1 }
657 kkz 1.1 // go down this path
658 kkz 1.1 nParam = q.nextEdge(i).which_pred();
659 kkz 1.1 q.next(i).accept(this);
660 kkz 1.1 }
661 kkz 1.1 }
662 kkz 1.1
663 kkz 1.1 public void visit(CJMP q) {
664 kkz 1.1 if (!gen.contains(q.test())) {
665 kkz 1.1 safe = false;
666 kkz 1.3 //System.out.println(q + " needs " + q.test());
667 kkz 1.1 return;
668 kkz 1.1 }
669 kkz 1.1 visit((SIGMA)q);
670 kkz 1.1 }
671 kkz 1.1
672 kkz 1.1 public void visit(PCALL q) {
673 cananian 1.4 assert false : "Unimplemented.";
674 kkz 1.1 }
675 kkz 1.1
676 kkz 1.1 public void visit(PHI q) {
677 kkz 1.1 if (!phis.contains(q)) {
678 kkz 1.1 phis.add(q);
679 kkz 1.1 // fixup thisObj
680 kkz 1.1 for(int i = 0; i < q.numPhis(); i++) {
681 kkz 1.1 if (q.src(i, nParam).equals(thisObj))
682 kkz 1.1 thisObj = q.dst(i);
683 kkz 1.1 }
684 kkz 1.1 // fixup gen
685 kkz 1.1 Set savedGen = gen;
686 kkz 1.1 gen = new HashSet();
687 cananian 1.5 for(Object tO : savedGen) {
688 cananian 1.5 Temp t = (Temp) tO;
689 kkz 1.1 gen.add(t);
690 kkz 1.1 for(int i = 0; i < q.numPhis(); i++) {
691 kkz 1.1 if (q.src(i, nParam).equals(t)) {
692 kkz 1.1 gen.remove(t);
693 kkz 1.1 gen.add(q.dst(i));
694 kkz 1.1 }
695 kkz 1.1 }
696 kkz 1.1 }
697 cananian 1.4 assert q.nextLength() == 1;
698 kkz 1.1 nParam = q.nextEdge(0).which_pred();
699 kkz 1.1 q.next(0).accept(this);
700 kkz 1.1 }
701 kkz 1.1 }
702 kkz 1.1
703 kkz 1.1 public void visit(Quad q) {
704 kkz 1.1 // check dependencies
705 cananian 1.5 for(Object tO : q.useC()) {
706 cananian 1.5 Temp t = (Temp) tO;
707 kkz 1.1 if (!gen.contains(t) && !t.equals(thisObj)) {
708 kkz 1.3 //System.out.println(thisObj);
709 kkz 1.1 safe = false;
710 kkz 1.3 //System.out.println(q + " needs " + t);
711 kkz 1.1 return;
712 kkz 1.1 }
713 kkz 1.1 }
714 kkz 1.1 // add defs
715 kkz 1.1 for(Iterator it = q.defC().iterator(); it.hasNext(); ) {
716 kkz 1.1 gen.add(it.next());
717 kkz 1.1 }
718 kkz 1.1 if (q.nextLength() == 0) return;
719 cananian 1.4 assert q.nextLength() == 1;
720 kkz 1.1 nParam = q.nextEdge(0).which_pred();
721 kkz 1.1 q.next(0).accept(this);
722 kkz 1.1 }
723 kkz 1.1
724 kkz 1.1 public void visit(SIGMA q) {
725 kkz 1.1 Temp savedThis = thisObj;
726 kkz 1.1 Set savedGen = gen;
727 kkz 1.1 for(int i = 0; i < q.arity(); i++) {
728 kkz 1.1 // fixup thisObj
729 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
730 kkz 1.1 if (q.src(j).equals(savedThis)) {
731 kkz 1.1 thisObj = q.dst(j, i);
732 kkz 1.1 break;
733 kkz 1.1 }
734 kkz 1.1 }
735 kkz 1.1 // fixup gen
736 kkz 1.1 gen = new HashSet();
737 cananian 1.5 for(Object tO : savedGen) {
738 cananian 1.5 Temp t = (Temp) tO;
739 kkz 1.1 gen.add(t);
740 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
741 kkz 1.1 if (q.src(j).equals(t)) {
742 kkz 1.1 gen.remove(t);
743 kkz 1.1 gen.add(q.dst(j, i));
744 kkz 1.1 }
745 kkz 1.1 }
746 kkz 1.1 }
747 kkz 1.1 // go down this path
748 kkz 1.1 nParam = q.nextEdge(i).which_pred();
749 kkz 1.1 q.next(i).accept(this);
750 kkz 1.1 }
751 kkz 1.1 }
752 kkz 1.1
753 kkz 1.1 public void visit(SWITCH q) {
754 cananian 1.4 assert false : "Unimplemented.";
755 kkz 1.1 }
756 kkz 1.1
757 kkz 1.1 public void visit(TYPESWITCH q) {
758 cananian 1.4 assert false : "Unimplemented.";
759 kkz 1.1 }
760 kkz 1.1 }
761 kkz 1.1
762 kkz 1.1 /** private class for traversing the graph for
763 kkz 1.1 * conversion to recursive form.
764 kkz 1.1 */
765 kkz 1.1 private static class updateDependencies extends QuadVisitor
766 kkz 1.1 {
767 kkz 1.1 PHI lastPhi;
768 kkz 1.1 Map phiMap;
769 kkz 1.1 int nParam;
770 kkz 1.1 Quad insertPt;
771 kkz 1.1 Map insertPts;
772 kkz 1.1 Map tMap;
773 kkz 1.1 HMethod hm;
774 kkz 1.1
775 kkz 1.1 updateDependencies(METHOD method, NEW nnew, CALL call, Quad start,
776 kkz 1.1 HMethod hm) {
777 kkz 1.1 this.insertPts = new HashMap();
778 kkz 1.1 this.phiMap = new HashMap();
779 kkz 1.1 this.tMap = new HashMap();
780 kkz 1.1 this.hm = hm;
781 kkz 1.1 // create map needed for updating Quads
782 kkz 1.1 // using post-call Temps to correct pre-call Temps
783 kkz 1.1 for(int i = 0; i < method.paramsLength(); i++) {
784 kkz 1.1 Temp t = method.params(i);
785 kkz 1.1 for(int j = 0; j < call.numSigmas(); j++) {
786 kkz 1.1 tMap.put(call.dst(j, 0), call.src(j));
787 kkz 1.1 }
788 kkz 1.1 }
789 kkz 1.1 // start with the next Quad
790 cananian 1.4 assert start.nextLength() == 1;
791 kkz 1.1 nParam = start.nextEdge(0).which_pred();
792 kkz 1.1 //start.next(0).accept(this);
793 kkz 1.1 call.next(0).accept(this);
794 kkz 1.1 }
795 kkz 1.1
796 kkz 1.1 public void visit(CALL q) {
797 kkz 1.3 //System.out.println(insertPt + " :: " + q);
798 kkz 1.1 if (q.method().equals(hm))
799 kkz 1.1 insertPt = q;
800 kkz 1.1 Temp[] oparams = q.params();
801 kkz 1.1 Temp[] nparams = null;
802 kkz 1.1 // remap params if necessary
803 kkz 1.1 for(int i = 0; i < oparams.length; i++) {
804 kkz 1.1 if (tMap.containsKey(oparams[i])) {
805 kkz 1.1 if (nparams == null) {
806 kkz 1.1 nparams = new Temp[oparams.length];
807 kkz 1.1 System.arraycopy(oparams, 0, nparams, 0,
808 kkz 1.1 nparams.length);
809 kkz 1.1 }
810 kkz 1.1 nparams[i] = (Temp) tMap.get(oparams[i]);
811 cananian 1.4 assert nparams[i] != null;
812 kkz 1.1 }
813 kkz 1.1 }
814 kkz 1.1 Temp[] osrc = q.src();
815 kkz 1.1 Temp[] nsrc = null;
816 kkz 1.1 // remap sigma if needed
817 kkz 1.1 for(int i = 0; i < q.numSigmas(); i++) {
818 kkz 1.1 if (tMap.containsKey(osrc[i])) {
819 kkz 1.1 if (nsrc == null) {
820 kkz 1.1 nsrc = new Temp[osrc.length];
821 kkz 1.1 System.arraycopy(osrc, 0, nsrc, 0, nsrc.length);
822 kkz 1.1 }
823 kkz 1.1 nsrc[i] = (Temp) tMap.get(osrc[i]);
824 cananian 1.4 assert nsrc[i] != null;
825 kkz 1.1 }
826 kkz 1.1 }
827 kkz 1.1 // replace call if necessary
828 kkz 1.1 if (nparams != null || nsrc != null) {
829 kkz 1.1 nparams = (nparams == null) ? oparams : nparams;
830 kkz 1.1 nsrc = (nsrc == null) ? osrc : nsrc;
831 kkz 1.1 CALL ncall = new CALL(q.getFactory(), q, q.method(),
832 kkz 1.1 nparams, q.retval(), q.retex(),
833 kkz 1.1 q.isVirtual(), q.isTailCall(),
834 kkz 1.1 q.dst(), nsrc);
835 kkz 1.1 Quad.replace(q, ncall);
836 kkz 1.1 q = ncall;
837 kkz 1.1 }
838 kkz 1.1 visit((SIGMA)q);
839 kkz 1.1 }
840 kkz 1.1
841 kkz 1.1 public void visit(CJMP q) {
842 kkz 1.3 //System.out.println(insertPt + " :: " + q);
843 kkz 1.1 Temp test = null;
844 kkz 1.1 // remap test if needed
845 kkz 1.1 if (tMap.containsKey(q.test())) {
846 kkz 1.1 test = (Temp) tMap.get(q.test());
847 cananian 1.4 assert test != null;
848 kkz 1.1 }
849 kkz 1.1 Temp[] osrc = q.src();
850 kkz 1.1 Temp[] nsrc = null;
851 kkz 1.1 // remap sigma if needed
852 kkz 1.1 for(int i = 0; i < q.numSigmas(); i++) {
853 kkz 1.1 if (tMap.containsKey(osrc[i])) {
854 kkz 1.1 if (nsrc == null) {
855 kkz 1.1 nsrc = new Temp[osrc.length];
856 kkz 1.1 System.arraycopy(osrc, 0, nsrc, 0, nsrc.length);
857 kkz 1.1 }
858 kkz 1.1 nsrc[i] = (Temp) tMap.get(osrc[i]);
859 cananian 1.4 assert nsrc[i] != null;
860 kkz 1.1 }
861 kkz 1.1 }
862 kkz 1.1 if (test != null || nsrc != null) {
863 kkz 1.1 test = (test == null) ? q.test() : test;
864 kkz 1.1 nsrc = (nsrc == null) ? q.src() : nsrc;
865 kkz 1.1 CJMP ncjmp = new CJMP(q.getFactory(), q, test, q.dst(), nsrc);
866 kkz 1.1 Quad.replace(q, ncjmp);
867 kkz 1.1 q = ncjmp;
868 kkz 1.1 }
869 kkz 1.1 visit((SIGMA)q);
870 kkz 1.1 }
871 kkz 1.1
872 kkz 1.1 public void visit(FOOTER q) {
873 kkz 1.3 //System.out.println(insertPt + " :: " + q);
874 kkz 1.1 if (lastPhi != null && insertPt != null)
875 kkz 1.1 phiMap.put(lastPhi, insertPt);
876 kkz 1.1 }
877 kkz 1.1
878 kkz 1.1 public void visit(OPER q) {
879 kkz 1.3 //System.out.println(insertPt + " :: " + q);
880 kkz 1.1 // update operands if necessary
881 kkz 1.1 Temp[] nt = null;
882 kkz 1.1 Temp[] ot = q.operands();
883 kkz 1.1 for(int i = 0; i < ot.length; i++) {
884 kkz 1.1 if (tMap.containsKey(ot[i])) {
885 kkz 1.1 if (nt == null) {
886 kkz 1.1 nt = new Temp[ot.length];
887 kkz 1.1 System.arraycopy(ot, 0, nt, 0, nt.length);
888 kkz 1.1 }
889 kkz 1.1 nt[i] = (Temp) tMap.get(ot[i]);
890 cananian 1.4 assert nt[i] != null;
891 kkz 1.1 }
892 kkz 1.1 }
893 kkz 1.1 // replace OPER if necessary
894 kkz 1.1 if (nt != null) {
895 kkz 1.1 OPER noper = new OPER(q.getFactory(), q, q.opcode(), q.dst(),
896 kkz 1.1 nt);
897 kkz 1.1 Quad.replace(q, noper);
898 kkz 1.1 q = noper;
899 kkz 1.1 }
900 kkz 1.1 // update map if necessary
901 kkz 1.1 tMap.remove(q.dst());
902 cananian 1.4 assert q.nextLength() == 1;
903 kkz 1.1 nParam = q.nextEdge(0).which_pred();
904 kkz 1.1 q.next(0).accept(this);
905 kkz 1.1 }
906 kkz 1.1
907 kkz 1.1 public void visit(PCALL q) {
908 cananian 1.4 assert false : "Unimplemented.";
909 kkz 1.1 }
910 kkz 1.1
911 kkz 1.1 public void visit(PHI q) {
912 kkz 1.3 //System.out.println(insertPt + " :: " + q);
913 kkz 1.1 // replace PHI if needed
914 kkz 1.1 Temp[][] nsrc = null;
915 kkz 1.1 for(int i = 0; i < q.numPhis(); i++) {
916 kkz 1.1 if (tMap.containsKey(q.src(i, nParam))) {
917 kkz 1.1 if (nsrc == null) {
918 kkz 1.1 nsrc = new Temp[q.numPhis()][];
919 kkz 1.1 for(int j = 0; j < nsrc.length; j++) {
920 kkz 1.1 nsrc[j] = new Temp[q.arity()];
921 kkz 1.1 System.arraycopy(q.src(i), 0, nsrc[j], 0,
922 kkz 1.1 nsrc[j].length);
923 kkz 1.1 }
924 kkz 1.1 nsrc[i][nParam] = (Temp) tMap.get(q.src(i, nParam));
925 cananian 1.4 assert nsrc[i][nParam] != null;
926 kkz 1.1 }
927 kkz 1.1 }
928 kkz 1.1 }
929 kkz 1.1 if (nsrc != null) {
930 kkz 1.1 Temp[] dst = new Temp[q.numPhis()];
931 kkz 1.1 for(int i = 0; i < dst.length; i++)
932 kkz 1.1 dst[i] = q.dst(i);
933 kkz 1.1 PHI phi = new PHI(q.getFactory(), q, dst, nsrc, q.arity());
934 kkz 1.1 Quad.replace(q, phi);
935 kkz 1.1 q = phi;
936 kkz 1.1 }
937 kkz 1.1 if (!phiMap.containsKey(q)) {
938 kkz 1.1 phiMap.put(q, null); // placeholder
939 kkz 1.1 lastPhi = q;
940 kkz 1.1 // fixup tMap
941 kkz 1.1 Map savedTMap = tMap;
942 kkz 1.1 tMap = new HashMap();
943 cananian 1.5 for(Object fromO : savedTMap.keySet()) {
944 cananian 1.5 Temp from = (Temp) fromO;
945 kkz 1.1 Temp to = (Temp) savedTMap.get(from);
946 kkz 1.1 tMap.put(from, to);
947 kkz 1.1 for(int i = 0; i < q.numPhis(); i++) {
948 kkz 1.1 if (q.src(i, nParam).equals(to))
949 kkz 1.1 tMap.put(from, q.dst(i));
950 kkz 1.1 if (q.src(i, nParam).equals(from))
951 kkz 1.1 tMap.put(from, null);
952 kkz 1.1 }
953 kkz 1.1 }
954 cananian 1.4 assert q.nextLength() == 1;
955 kkz 1.1 nParam = q.nextEdge(0).which_pred();
956 kkz 1.1 q.next(0).accept(this);
957 kkz 1.1 } else {
958 kkz 1.1 Quad lastIP = (Quad) phiMap.get(q);
959 kkz 1.1 if (lastIP == null && insertPt != null) {
960 kkz 1.1 phiMap.put(q, insertPt);
961 kkz 1.1 }
962 kkz 1.1 }
963 kkz 1.1 }
964 kkz 1.1
965 kkz 1.1 public void visit(Quad q) {
966 kkz 1.3 //System.out.println(insertPt + " :: " + q);
967 kkz 1.1 // we don't handle uses here
968 cananian 1.4 assert q.useC().isEmpty();
969 cananian 1.5 for(Object fromO : tMap.keySet()) {
970 cananian 1.5 Temp from = (Temp) fromO;
971 kkz 1.1 Temp to = (Temp) tMap.get(from);
972 kkz 1.1 if (q.defC().contains(from))
973 kkz 1.1 tMap.remove(from);
974 kkz 1.1 if (q.defC().contains(to))
975 kkz 1.1 tMap.put(from, null);
976 kkz 1.1 }
977 cananian 1.4 assert q.nextLength() == 1;
978 kkz 1.1 nParam = q.nextEdge(0).which_pred();
979 kkz 1.1 q.next(0).accept(this);
980 kkz 1.1 }
981 kkz 1.1
982 kkz 1.1 public void visit(RETURN q) {
983 kkz 1.3 //System.out.println(insertPt + " :: " + q);
984 kkz 1.1 if (tMap.containsKey(q.retval())) {
985 kkz 1.1 Temp t = (Temp) tMap.get(q.retval());
986 cananian 1.4 assert t != null;
987 kkz 1.1 RETURN nreturn = new RETURN(q.getFactory(), q, t);
988 kkz 1.1 Quad.replace(q, nreturn);
989 kkz 1.1 q = nreturn;
990 kkz 1.1 }
991 cananian 1.4 assert q.nextLength() == 1;
992 kkz 1.1 nParam = q.nextEdge(0).which_pred();
993 kkz 1.1 q.next(0).accept(this);
994 kkz 1.1 }
995 kkz 1.1
996 kkz 1.1 public void visit(SET q) {
997 kkz 1.3 //System.out.println(insertPt + " :: " + q);
998 kkz 1.1 // replace objectref if necessary
999 kkz 1.1 Temp objectref = null;
1000 kkz 1.1 if (tMap.containsKey(q.objectref())) {
1001 kkz 1.1 objectref = (Temp) tMap.get(q.objectref());
1002 cananian 1.4 assert objectref != null;;
1003 kkz 1.1 }
1004 kkz 1.1 // replace src if necessary
1005 kkz 1.1 Temp src = null;
1006 kkz 1.1 if (tMap.containsKey(q.src())) {
1007 kkz 1.1 src = (Temp) tMap.get(q.src());
1008 cananian 1.4 assert src != null;
1009 kkz 1.1 }
1010 kkz 1.1 // replace SET if necessary
1011 kkz 1.1 if (objectref != null || src != null) {
1012 kkz 1.1 objectref = (objectref == null) ? q.objectref() : objectref;
1013 kkz 1.1 src = (src == null) ? q.src() : src;
1014 kkz 1.1 SET set = new SET(q.getFactory(), q, q.field(), objectref,
1015 kkz 1.1 src);
1016 kkz 1.1 Quad.replace(q, set);
1017 kkz 1.1 q = set;
1018 kkz 1.1 }
1019 cananian 1.4 assert q.nextLength() == 1;
1020 kkz 1.1 nParam = q.nextEdge(0).which_pred();
1021 kkz 1.1 q.next(0).accept(this);
1022 kkz 1.1 }
1023 kkz 1.1
1024 kkz 1.1 public void visit(SIGMA q) {
1025 kkz 1.3 //System.out.println(insertPt + " :: " + q);
1026 kkz 1.1 Quad savedIP = insertPt;
1027 cananian 1.4 assert savedIP == null || savedIP.equals(q);
1028 kkz 1.1 Quad[] savedIPs = new Quad[q.arity()];
1029 kkz 1.1 Map savedTMap = tMap;
1030 kkz 1.1 PHI savedPhi = lastPhi;
1031 kkz 1.1 for(int i = 0; i < q.arity(); i++) {
1032 kkz 1.1 // fixup tMap
1033 kkz 1.1 tMap = new HashMap();
1034 cananian 1.5 for(Object fromO : savedTMap.keySet()) {
1035 cananian 1.5 Temp from = (Temp) fromO;
1036 kkz 1.1 Temp to = (Temp) savedTMap.get(from);
1037 kkz 1.1 tMap.put(from, to);
1038 kkz 1.1 if (q.kind() == QuadKind.CALL) {
1039 kkz 1.1 if (i == 0 && to.equals(((CALL)q).retval())) {
1040 kkz 1.1 tMap.put(from, null);
1041 kkz 1.1 continue;
1042 kkz 1.1 }
1043 kkz 1.1 if (i == 1 && to.equals(((CALL)q).retex())) {
1044 kkz 1.1 tMap.put(from, null);
1045 kkz 1.1 continue;
1046 kkz 1.1 }
1047 kkz 1.1 }
1048 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
1049 kkz 1.1 // if Temp needs remapping, do so
1050 kkz 1.1 if (q.src(j).equals(to))
1051 kkz 1.1 tMap.put(from, q.dst(j, i));
1052 kkz 1.1 // if Temp is being overwritten, flag
1053 kkz 1.1 if (q.src(j).equals(from))
1054 kkz 1.1 tMap.put(from, null);
1055 kkz 1.1 }
1056 kkz 1.1 }
1057 kkz 1.1 insertPt = null;
1058 kkz 1.1 // fixup lastPhi
1059 kkz 1.1 lastPhi = savedPhi;
1060 kkz 1.1 // go down this path
1061 kkz 1.1 nParam = q.nextEdge(i).which_pred();
1062 kkz 1.1 q.next(i).accept(this);
1063 kkz 1.1 // check what we got from this path
1064 kkz 1.1 savedIPs[i] = insertPt;
1065 kkz 1.1 }
1066 kkz 1.1 boolean all_null = true;
1067 kkz 1.1 for(int i = 0; i < q.arity(); i++) {
1068 kkz 1.1 if (savedIPs[i] != null) {
1069 kkz 1.1 all_null = false;
1070 kkz 1.1 break;
1071 kkz 1.1 }
1072 kkz 1.1 }
1073 kkz 1.1 if (!all_null || savedIP != null) {
1074 kkz 1.1 insertPts.put(q, savedIPs);
1075 kkz 1.1 insertPt = q;
1076 kkz 1.1 }
1077 kkz 1.1 }
1078 kkz 1.1
1079 kkz 1.1 public void visit(SWITCH q) {
1080 cananian 1.4 assert false : "Unimplemented.";
1081 kkz 1.1 }
1082 kkz 1.1
1083 kkz 1.1 public void visit(THROW q) {
1084 kkz 1.3 //System.out.println(insertPt + " :: " + q);
1085 kkz 1.1 if (tMap.containsKey(q.throwable())) {
1086 kkz 1.1 Temp t = (Temp) tMap.get(q.throwable());
1087 cananian 1.4 assert t != null;
1088 kkz 1.1 THROW nthrow = new THROW(q.getFactory(), q, t);
1089 kkz 1.1 Quad.replace(q, nthrow);
1090 kkz 1.1 q = nthrow;
1091 kkz 1.1 }
1092 cananian 1.4 assert q.nextLength() == 1;
1093 kkz 1.1 nParam = q.nextEdge(0).which_pred();
1094 kkz 1.1 q.next(0).accept(this);
1095 kkz 1.1 }
1096 kkz 1.1
1097 kkz 1.1 public void visit(TYPESWITCH q) {
1098 cananian 1.4 assert false : "Unimplemented.";
1099 kkz 1.1 }
1100 kkz 1.1 }
1101 kkz 1.1
1102 kkz 1.1 /** private class for traversing the graph to convert
1103 kkz 1.1 * to recursive form.
1104 kkz 1.1 */
1105 kkz 1.1 private static class makeRecurse extends QuadVisitor
1106 kkz 1.1 {
1107 kkz 1.1 Map quad2quadA;
1108 kkz 1.1 NEW begin;
1109 kkz 1.1 Temp thisObj;
1110 kkz 1.1 Set news = new HashSet();
1111 kkz 1.1
1112 kkz 1.1 makeRecurse(Map quad2quadA, NEW begin) {
1113 kkz 1.1 this.quad2quadA = quad2quadA;
1114 kkz 1.1 // prepare exception edge
1115 kkz 1.1 CALL ocall = (CALL) begin.next(0);
1116 kkz 1.1 // map receiver
1117 kkz 1.1 Map rcvrMap = (new mapTemp(begin.dst(), ocall.next(0),
1118 kkz 1.1 quad2quadA,
1119 kkz 1.1 Collections.EMPTY_SET)).quad2temp;
1120 kkz 1.1 PHI phi = null;
1121 kkz 1.1 int ex_pred = 0;
1122 kkz 1.1 if (ocall.next(1).kind() == QuadKind.PHI) {
1123 kkz 1.1 phi = (PHI) ocall.next(1);
1124 kkz 1.1 ex_pred = phi.arity();
1125 kkz 1.1 }
1126 kkz 1.1 // move things
1127 cananian 1.5 for(Object sigmaO : quad2quadA.keySet()) {
1128 cananian 1.5 SIGMA sigma = (SIGMA) sigmaO;
1129 kkz 1.1 Quad[] value = (Quad[]) quad2quadA.get(sigma);
1130 kkz 1.1 for(int i = 0; i < sigma.arity(); i++) {
1131 kkz 1.1 if (sigma.kind() == QuadKind.CALL && i == 1)
1132 kkz 1.1 // ignore exception edges
1133 kkz 1.1 continue;
1134 kkz 1.1 if (value[i] != null)
1135 kkz 1.1 // look elsewhere
1136 kkz 1.1 continue;
1137 kkz 1.1 Temp rcvr = (Temp) rcvrMap.get(sigma);
1138 cananian 1.4 assert rcvr != null : sigma;
1139 kkz 1.1 TempFactory tf = begin.getFactory().tempFactory();
1140 kkz 1.1 Temp rcvr0 = new Temp(tf);
1141 kkz 1.1 NEW nnew = new NEW(begin.getFactory(), begin, rcvr0,
1142 kkz 1.1 begin.hclass());
1143 kkz 1.1 news.add(nnew);
1144 kkz 1.1 Temp retval = (ocall.retval() == null) ? null :
1145 kkz 1.1 new Temp(tf);
1146 kkz 1.1 Temp retex = (ocall.retex() == null) ? null :
1147 kkz 1.1 new Temp(tf);
1148 kkz 1.1 // find out if any sigmas need to be propagated
1149 kkz 1.1 Temp[] dstSaved = new Temp[sigma.numSigmas()];
1150 kkz 1.1 Temp[] dst0 = new Temp[sigma.numSigmas()];
1151 kkz 1.1 int numSigmas = 0;
1152 kkz 1.1 for(int j = 0; j < sigma.numSigmas(); j++) {
1153 kkz 1.1 if (!sigma.dst(j, 0).equals(rcvr)) {
1154 kkz 1.1 dstSaved[j] = sigma.dst(j, 0);
1155 kkz 1.1 dst0[j] = new Temp(tf);
1156 kkz 1.1 numSigmas++;
1157 kkz 1.1 } else {
1158 kkz 1.1 dst0[j] = sigma.dst(j, 0);
1159 kkz 1.1 }
1160 kkz 1.1 }
1161 kkz 1.1 // fixup sigma
1162 kkz 1.1 sigma.assign(dst0, 0);
1163 kkz 1.1 // shrink src array to size
1164 kkz 1.1 Temp[] src = new Temp[numSigmas+1];
1165 kkz 1.1 src[0] = rcvr0;
1166 kkz 1.1 for(int j = 0, k = 1; j < sigma.numSigmas(); j++) {
1167 kkz 1.1 if (dstSaved[j] != null) {
1168 kkz 1.1 src[k] = sigma.dst(j, 0);
1169 kkz 1.1 k++;
1170 kkz 1.1 }
1171 kkz 1.1 }
1172 kkz 1.1 Temp[][] dst = new Temp[numSigmas+1][];
1173 kkz 1.1 dst[0] = new Temp[] { rcvr, new Temp(tf) };
1174 kkz 1.1 for(int j = 0, k = 1; j < sigma.numSigmas(); j++) {
1175 kkz 1.1 if (dstSaved[j] != null) {
1176 kkz 1.1 dst[k] = new Temp[] { dstSaved[j], new Temp(tf) };
1177 kkz 1.1 k++;
1178 kkz 1.1 }
1179 kkz 1.1 }
1180 kkz 1.1 // make CALL
1181 kkz 1.1 CALL ncall = new CALL(ocall.getFactory(), ocall,
1182 kkz 1.1 ocall.method(), new Temp[] { rcvr0 },
1183 kkz 1.1 retval, retex, ocall.isVirtual(),
1184 kkz 1.1 ocall.isTailCall(), dst, src);
1185 kkz 1.3 //System.out.println(ncall);
1186 kkz 1.1 Quad.addEdge(ncall, 0, sigma.next(i),
1187 kkz 1.1 sigma.nextEdge(i).which_pred());
1188 kkz 1.1 Quad.addEdge(nnew, 0, ncall, 0);
1189 kkz 1.1 Quad.addEdge(sigma, i, nnew, 0);
1190 kkz 1.1 if (phi == null) {
1191 cananian 1.4 assert retex != null;
1192 kkz 1.1 Temp[][] srcs = new Temp[1][];
1193 kkz 1.1 srcs[0] = new Temp[] { retex };
1194 kkz 1.1 phi = new PHI(ocall.getFactory(), ocall,
1195 kkz 1.1 new Temp[] { ocall.retex() }, srcs, 1);
1196 kkz 1.1 Quad.addEdge(phi, 0, ocall.next(1),
1197 kkz 1.1 ocall.nextEdge(1).which_pred());
1198 kkz 1.1 } else {
1199 kkz 1.1 phi = phi.grow(new Temp[] { retex }, ex_pred);
1200 kkz 1.1 }
1201 kkz 1.1 Quad.addEdge(ncall, 1, phi, ex_pred++);
1202 kkz 1.1 // update value to point to new CALL
1203 kkz 1.1 value[i] = ncall;
1204 kkz 1.1 }
1205 kkz 1.1 }
1206 kkz 1.1 // further updates on quad2quadA
1207 kkz 1.1 for(Iterator it = news.iterator(); it.hasNext(); ) {
1208 kkz 1.1 quad2quadA.put(((Quad)it.next()).next(0),
1209 kkz 1.1 new Quad[] { null, null });
1210 kkz 1.1 }
1211 kkz 1.1 // hang on to METHOD
1212 kkz 1.1 METHOD method = (METHOD) begin.prev(0);
1213 kkz 1.1 // remove original NEW and CALL
1214 kkz 1.1 if (ocall.next(1) != null & ocall.next(1).kind() == QuadKind.PHI)
1215 kkz 1.1 phi = phi.shrink(ocall.nextEdge(1).which_pred());
1216 kkz 1.1 Quad.addEdge(begin.prev(0), begin.prevEdge(0).which_succ(),
1217 kkz 1.1 ocall.next(0), ocall.nextEdge(0).which_pred());
1218 kkz 1.1 // start updating other Quads
1219 kkz 1.1 this.thisObj = begin.dst();
1220 kkz 1.1
1221 kkz 1.1 //method.next(0).accept(this);
1222 kkz 1.1 }
1223 kkz 1.1
1224 kkz 1.1 public void visit(SET q) {
1225 kkz 1.1 //System.out.println("VISITING: " + q);
1226 kkz 1.1 if (q.objectref() != null && q.objectref().equals(thisObj)) {
1227 kkz 1.1 // need to move this SET to the right place
1228 kkz 1.1 //System.out.println("Making srcMap");
1229 kkz 1.1 Map rcvrMap = (new mapTemp(thisObj, q, quad2quadA,
1230 kkz 1.1 news)).quad2temp;
1231 kkz 1.1 Map srcMap = (new mapTemp(q.src(), q, quad2quadA,
1232 kkz 1.1 Collections.EMPTY_SET)).quad2temp;
1233 kkz 1.1 // HACK! repeat to make sure the Quads don't change
1234 kkz 1.1 rcvrMap = (new mapTemp(thisObj, q, quad2quadA,
1235 kkz 1.1 news)).quad2temp;
1236 cananian 1.5 for(Object sigmaO : quad2quadA.keySet()) {
1237 cananian 1.5 SIGMA sigma = (SIGMA) sigmaO;
1238 kkz 1.1 Quad[] value = (Quad[]) quad2quadA.get(sigma);
1239 kkz 1.1 for(int i = 0; i < sigma.arity(); i++) {
1240 kkz 1.1 if (sigma.kind() == QuadKind.CALL && i == 1)
1241 kkz 1.1 // ignore exception edges
1242 kkz 1.1 continue;
1243 kkz 1.1 if (value[i] != null &&
1244 kkz 1.1 value[i].kind() != QuadKind.SET)
1245 kkz 1.1 // look elsewhere
1246 kkz 1.1 continue;
1247 kkz 1.1 Temp rcvr = (Temp) rcvrMap.get(sigma);
1248 cananian 1.4 assert rcvr != null : sigma;
1249 kkz 1.1 Temp src = (Temp) srcMap.get(sigma);
1250 kkz 1.1 //System.out.println("Printing srcMap");
1251 kkz 1.1 SET set = new SET(q.getFactory(), q, q.field(), rcvr,
1252 kkz 1.1 src);
1253 kkz 1.1 if (value[i] == null) {
1254 kkz 1.1 // attaching right after CALL
1255 kkz 1.1 Quad.addEdge(set, 0, sigma.next(0),
1256 kkz 1.1 sigma.nextEdge(0).which_pred());
1257 kkz 1.1 Quad.addEdge(sigma, 0, set, 0);
1258 kkz 1.1 } else {
1259 kkz 1.1 // attaching after another SET
1260 kkz 1.1 Quad.addEdge(set, 0, value[i].next(0),
1261 kkz 1.1 value[i].nextEdge(0).which_pred());
1262 kkz 1.1 Quad.addEdge(value[i], 0, set, 0);
1263 kkz 1.1 }
1264 kkz 1.1 // modify value
1265 kkz 1.1 value[i] = set;
1266 kkz 1.1 }
1267 kkz 1.1 }
1268 kkz 1.1 // remove original SET
1269 kkz 1.1 Quad next = q.next(0);
1270 kkz 1.1 q.remove();
1271 kkz 1.1 next.accept(this);
1272 kkz 1.1 } else {
1273 kkz 1.1 // irrelevant SET, just continue
1274 cananian 1.4 assert !q.useC().contains(thisObj);
1275 kkz 1.1 q.next(0).accept(this);
1276 kkz 1.1 }
1277 kkz 1.1 }
1278 kkz 1.1
1279 kkz 1.1 public void visit(NEW q) {
1280 kkz 1.1 // System.out.println("VISITING: " + q);
1281 kkz 1.1 // only continue if this isn't one of the NEWs we added
1282 kkz 1.1 if (!news.contains(q))
1283 kkz 1.1 q.next(0).accept(this);
1284 kkz 1.1 }
1285 kkz 1.1
1286 kkz 1.1 public void visit(Quad q) {
1287 kkz 1.1 // System.out.println("VISITING: " + q);
1288 kkz 1.1 // should not be referring to the receiver
1289 cananian 1.4 assert !q.useC().contains(thisObj);
1290 cananian 1.4 assert q.nextLength() == 1 && q.prevLength() == 1 : q;
1291 kkz 1.1 q.next(0).accept(this);
1292 kkz 1.1 }
1293 kkz 1.1
1294 kkz 1.1 public void visit(SIGMA q) {
1295 kkz 1.1 // System.out.println("VISITING: " + q);
1296 kkz 1.1 // only mapped sigmas should get here
1297 cananian 1.4 assert quad2quadA.containsKey(q);
1298 kkz 1.1 Quad[] quadA = (Quad[]) quad2quadA.get(q);
1299 kkz 1.1 int nSigma = q.numSigmas();
1300 kkz 1.1 // find sigma function for thisObj
1301 kkz 1.1 for(int i = 0; i < q.numSigmas(); i++) {
1302 kkz 1.1 if (q.src(i).equals(thisObj)) {
1303 kkz 1.1 nSigma = i;
1304 kkz 1.1 break;
1305 kkz 1.1 }
1306 kkz 1.1 }
1307 kkz 1.1 // go down branches
1308 kkz 1.1 Map savedQuad2QuadA = quad2quadA;
1309 kkz 1.1 for(int i = 0; i < q.arity(); i++) {
1310 kkz 1.1 if (q.kind() == QuadKind.CALL && i == 1)
1311 kkz 1.1 // skip exceptional branches
1312 kkz 1.1 continue;
1313 kkz 1.1 if (quadA[i] == null)
1314 kkz 1.1 // skip, no need to look
1315 kkz 1.1 continue;
1316 kkz 1.1 quad2quadA = new HashMap();
1317 kkz 1.1 if (quadA[i] != null && quadA[i].kind() != QuadKind.SET) {
1318 kkz 1.1 Worklist toDo = new WorkSet();
1319 kkz 1.1 toDo.push(quadA[i]);
1320 kkz 1.1 while(!toDo.isEmpty()) {
1321 kkz 1.1 SIGMA curr = (SIGMA) toDo.pull();
1322 kkz 1.1 Quad[] value = (Quad[]) savedQuad2QuadA.remove(curr);
1323 cananian 1.4 assert value != null : curr;
1324 kkz 1.1 quad2quadA.put(curr, value);
1325 kkz 1.1 for(int j = 0; j < value.length; j++) {
1326 kkz 1.1 if (value[j] != null &&
1327 kkz 1.1 value[j].kind() != QuadKind.SET) {
1328 kkz 1.1 toDo.push(value[j]);
1329 kkz 1.1 }
1330 kkz 1.1 }
1331 kkz 1.1 }
1332 kkz 1.1 }
1333 kkz 1.1 // setup thisObj
1334 kkz 1.1 thisObj = (nSigma < q.numSigmas()) ? q.dst(nSigma, i) : null;
1335 kkz 1.1 q.next(i).accept(this);
1336 kkz 1.1 // fixup savedQuad2QuadA with possibly changed mappings
1337 kkz 1.1 savedQuad2QuadA.putAll(quad2quadA);
1338 kkz 1.1 }
1339 kkz 1.1 // remove referencse to thisObj, if any
1340 kkz 1.1 if (nSigma < q.numSigmas()) {
1341 kkz 1.1 // create new src array
1342 kkz 1.1 Temp[] src = new Temp[q.numSigmas()-1];
1343 kkz 1.1 for(int i = 0; i < q.numSigmas(); i++) {
1344 kkz 1.1 if (i < nSigma)
1345 kkz 1.1 src[i] = q.src(i);
1346 kkz 1.1 else if (i > nSigma)
1347 kkz 1.1 src[i-1] = q.src(i);
1348 kkz 1.1 }
1349 kkz 1.1 // create new dst array
1350 kkz 1.1 Temp[][] dst = new Temp[q.numSigmas()-1][];
1351 kkz 1.1 for(int i = 0; i < q.numSigmas(); i++) {
1352 kkz 1.1 if (i < nSigma) {
1353 kkz 1.1 dst[i] = new Temp[q.arity()];
1354 kkz 1.1 System.arraycopy(q.dst(i), 0, dst[i], 0, q.arity());
1355 kkz 1.1 } else if (i > nSigma) {
1356 kkz 1.1 dst[i-1] = new Temp[q.arity()];
1357 kkz 1.1 System.arraycopy(q.dst(i), 0, dst[i-1], 0, q.arity());
1358 kkz 1.1 }
1359 kkz 1.1 }
1360 kkz 1.1 SIGMA nq = null;
1361 kkz 1.1 if (q.kind() == QuadKind.CALL) {
1362 kkz 1.1 CALL ocall = (CALL)q;
1363 kkz 1.1 CALL ncall = new CALL(ocall.getFactory(), ocall,
1364 kkz 1.1 ocall.method(), ocall.params(),
1365 kkz 1.1 ocall.retval(), ocall.retex(),
1366 kkz 1.1 ocall.isVirtual(),
1367 kkz 1.1 ocall.isTailCall(), dst, src);
1368 kkz 1.1 nq = ncall;
1369 kkz 1.1 } else {
1370 cananian 1.4 assert q.kind() == QuadKind.CJMP;
1371 kkz 1.1 CJMP ocjmp = (CJMP)q;
1372 kkz 1.1 CJMP ncjmp = new CJMP(ocjmp.getFactory(), ocjmp,
1373 kkz 1.1 ocjmp.test(), dst, src);
1374 kkz 1.1 nq = ncjmp;
1375 kkz 1.1 }
1376 kkz 1.1 // link up new SIGMA
1377 kkz 1.1 Quad.replace(q, nq);
1378 kkz 1.1 // fix up quad2quadA
1379 kkz 1.1 if (quad2quadA.containsKey(q))
1380 kkz 1.1 quad2quadA.put(nq, quad2quadA.remove(q));
1381 cananian 1.5 for(Object keyO : quad2quadA.keySet()) {
1382 cananian 1.5 Quad key = (Quad) keyO;
1383 kkz 1.1 Quad[] value = (Quad[]) quad2quadA.get(key);
1384 cananian 1.4 assert value != null : key;
1385 kkz 1.1 for(int j = 0; j < value.length; j++) {
1386 kkz 1.1 if (q.equals(value[j]))
1387 kkz 1.1 value[j] = nq;
1388 kkz 1.1 }
1389 kkz 1.1 }
1390 kkz 1.1 }
1391 kkz 1.1 }
1392 kkz 1.1 }
1393 kkz 1.1
1394 kkz 1.1 private static class mapTemp extends QuadVisitor
1395 kkz 1.1 {
1396 kkz 1.1 Map quad2temp;
1397 kkz 1.1 Temp target;
1398 kkz 1.1 Map quad2quadA;
1399 kkz 1.1 Set news;
1400 kkz 1.1
1401 kkz 1.1 mapTemp(Temp target, Quad begin, Map quad2quadA, Set news) {
1402 kkz 1.1 this.news = news;
1403 kkz 1.1 this.target = target;
1404 kkz 1.1 this.quad2quadA = quad2quadA;
1405 kkz 1.1 this.quad2temp = new HashMap();
1406 kkz 1.1 begin.accept(this);
1407 kkz 1.1 }
1408 kkz 1.1
1409 kkz 1.1 public void visit(NEW q) {
1410 kkz 1.1 // fixup for thisObj
1411 kkz 1.1 if (news.contains(q))
1412 kkz 1.1 target = q.dst();
1413 kkz 1.1 q.next(0).accept(this);
1414 kkz 1.1 }
1415 kkz 1.1
1416 kkz 1.1 public void visit(SIGMA q) {
1417 kkz 1.1 Temp savedTarget = target;
1418 kkz 1.1 // any SIGMA we visit should be mapped
1419 kkz 1.1 Quad[] quadA = (Quad[]) quad2quadA.get(q);
1420 cananian 1.4 assert quadA != null : q;
1421 kkz 1.1 for(int i = 0; i < q.arity(); i++) {
1422 kkz 1.1 boolean found = false;
1423 kkz 1.1 target = savedTarget;
1424 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
1425 kkz 1.1 //System.out.println(q.src(j) + " =? " + target);
1426 kkz 1.1 if (q.src(j).equals(target)) {
1427 kkz 1.1 target = q.dst(j, i);
1428 kkz 1.1 // check for repeats
1429 kkz 1.1 for(int k = j+1; k < q.numSigmas(); k++)
1430 cananian 1.4 assert !q.src(k).equals(target);
1431 kkz 1.1 found = true;
1432 kkz 1.1 break;
1433 kkz 1.1 }
1434 kkz 1.1 }
1435 kkz 1.1 if (q.kind() == QuadKind.CALL && i == 1) {
1436 kkz 1.1 // exception edge, ignore
1437 kkz 1.1 //target = savedTarget;
1438 kkz 1.1 continue;
1439 kkz 1.1 }
1440 kkz 1.1 // may need to add sigma function
1441 kkz 1.1 if (!found) {
1442 kkz 1.1 //System.out.println("CANNOT FIND " + target);
1443 kkz 1.1 //System.out.println(q + "\n");
1444 kkz 1.1 Temp[][] dsts = new Temp[q.numSigmas()+1][];
1445 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
1446 kkz 1.1 Temp[] dst = new Temp[q.arity()];
1447 kkz 1.1 System.arraycopy(q.dst(j), 0, dst, 0, dst.length);
1448 kkz 1.1 dsts[j] = dst;
1449 kkz 1.1 }
1450 kkz 1.1 // add sigma function
1451 kkz 1.1 dsts[dsts.length-1] = new Temp[q.arity()];
1452 kkz 1.1 TempFactory tf = q.getFactory().tempFactory();
1453 kkz 1.1 for(int j = 0; j < q.arity(); j++)
1454 kkz 1.1 dsts[dsts.length-1][j] = new Temp(tf);
1455 kkz 1.1 Temp[] src = new Temp[q.numSigmas()+1];
1456 kkz 1.1 System.arraycopy(q.src(), 0, src, 0, src.length-1);
1457 kkz 1.1 src[src.length-1] = target;
1458 kkz 1.1 SIGMA nq = null;
1459 kkz 1.1 if (q.kind() == QuadKind.CALL) {
1460 kkz 1.1 CALL ocall = (CALL)q;
1461 kkz 1.1 CALL ncall = new CALL(ocall.getFactory(), ocall,
1462 kkz 1.1 ocall.method(), ocall.params(),
1463 kkz 1.1 ocall.retval(), ocall.retex(),
1464 kkz 1.1 ocall.isVirtual(),
1465 kkz 1.1 ocall.isTailCall(), dsts, src);
1466 kkz 1.1 nq = ncall;
1467 kkz 1.1 } else {
1468 cananian 1.4 assert q.kind() == QuadKind.CJMP;
1469 kkz 1.1 CJMP ocjmp = (CJMP)q;
1470 kkz 1.1 CJMP ncjmp = new CJMP(ocjmp.getFactory(), ocjmp,
1471 kkz 1.1 ocjmp.test(), dsts, src);
1472 kkz 1.1 nq = ncjmp;
1473 kkz 1.1 }
1474 kkz 1.1 // link up new Quad
1475 kkz 1.1 Quad.replace(q, nq);
1476 kkz 1.1 // fix up maps
1477 kkz 1.1 quad2temp.remove(q);
1478 kkz 1.1 if (quad2quadA.containsKey(q))
1479 kkz 1.1 quad2quadA.put(nq, quad2quadA.remove(q));
1480 cananian 1.5 for(Object keyO : quad2quadA.keySet()) {
1481 cananian 1.5 Quad key = (Quad) keyO;
1482 kkz 1.1 Quad[] value = (Quad[]) quad2quadA.get(key);
1483 kkz 1.1 for(int j = 0; j < value.length; j++) {
1484 kkz 1.1 if (q.equals(value[j]))
1485 kkz 1.1 value[j] = nq;
1486 kkz 1.1 }
1487 kkz 1.1 }
1488 kkz 1.1 q = nq;
1489 kkz 1.1 target = q.dst(q.numSigmas()-1, i);
1490 kkz 1.1 //System.out.println("MADE new " + q);
1491 kkz 1.1 //System.out.println("Target is " + target);
1492 kkz 1.1 }
1493 kkz 1.1 //System.out.println("CHECKING "+quadA[i]);
1494 kkz 1.1 if (quadA[i] != null && quadA[i].kind() != QuadKind.SET) {
1495 kkz 1.1 // continue down this branch
1496 kkz 1.1 //System.out.println("Continuing");
1497 kkz 1.1 q.next(i).accept(this);
1498 kkz 1.1 } else {
1499 kkz 1.1 // end here
1500 kkz 1.1 //System.out.println("adding entry");
1501 kkz 1.1 quad2temp.put(q, target);
1502 kkz 1.1 }
1503 kkz 1.1 }
1504 kkz 1.1 }
1505 kkz 1.1
1506 kkz 1.1 public void visit(Quad q) {
1507 cananian 1.4 assert q.nextLength() == 1 && q.prevLength() == 1;
1508 kkz 1.1 q.next(0).accept(this);
1509 kkz 1.1 }
1510 kkz 1.1 }
1511 kkz 1.1 }
1512 kkz 1.1
1513 kkz 1.1
1514 kkz 1.1
1515 kkz 1.1
1516 kkz 1.1