1 cananian 1.1.2.1 // DispatchTreeTransformation.java, created Fri Oct 13 19:33:06 2000 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 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;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.5 import harpoon.Analysis.Maps.ConstMapProxy;
8 cananian 1.1.2.1 import harpoon.Analysis.Maps.ExactTypeMap;
9 cananian 1.1.2.5 import harpoon.Analysis.Maps.ExactTypeMapProxy;
10 cananian 1.1.2.5 import harpoon.Analysis.Maps.ExecMapProxy;
11 cananian 1.1.2.1 import harpoon.Analysis.Quads.SCC.SCCAnalysis;
12 cananian 1.1.2.1 import harpoon.Analysis.Quads.SCC.SCCOptimize;
13 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
14 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
15 cananian 1.1.2.1 import harpoon.ClassFile.HCodeAndMaps;
16 cananian 1.1.2.4 import harpoon.ClassFile.HCodeEdge;
17 cananian 1.1.2.4 import harpoon.ClassFile.HCodeElement;
18 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
19 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
20 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
21 cananian 1.1.2.1 import harpoon.IR.Quads.Edge;
22 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
23 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
24 cananian 1.1.2.4 import harpoon.IR.Quads.QuadRSSx;
25 cananian 1.1.2.4 import harpoon.IR.Quads.QuadSSI;
26 cananian 1.1.2.1 import harpoon.IR.Quads.QuadFactory;
27 cananian 1.1.2.1 import harpoon.IR.Quads.TYPESWITCH;
28 cananian 1.1.2.1 import harpoon.Temp.Temp;
29 cananian 1.1.2.4 import harpoon.Temp.TempMap;
30 cananian 1.1.2.1 import harpoon.Util.Util;
31 cananian 1.1.2.1
32 cananian 1.1.2.1 import java.lang.reflect.Modifier;
33 cananian 1.1.2.1 import java.util.ArrayList;
34 cananian 1.1.2.4 import java.util.Collections;
35 cananian 1.1.2.4 import java.util.Comparator;
36 cananian 1.1.2.1 import java.util.Iterator;
37 cananian 1.1.2.1 import java.util.List;
38 cananian 1.1.2.4 import java.util.Map;
39 cananian 1.1.2.1 import java.util.Set;
40 cananian 1.1.2.1 /**
41 cananian 1.1.2.1 * <code>DispatchTreeTransformation</code> replaces dynamic dispatch
42 cananian 1.1.2.1 * call sites with TYPESWITCHes leading to static dispatch calls.
43 cananian 1.1.2.1 * Given proper optimization of the TYPESWITCH test, this should
44 cananian 1.1.2.1 * speed up dispatch.
45 cananian 1.1.2.1 *
46 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
47 cananian 1.5 * @version $Id: DispatchTreeTransformation.java,v 1.5 2004/02/08 05:09:40 cananian Exp $
48 cananian 1.1.2.1 */
49 cananian 1.1.2.1 public class DispatchTreeTransformation
50 cananian 1.1.2.1 extends harpoon.Analysis.Transformation.MethodMutator {
51 cananian 1.1.2.1 private final static int CUTOFF = 10;
52 cananian 1.1.2.1
53 cananian 1.1.2.1 final ClassHierarchy ch;
54 cananian 1.1.2.1
55 cananian 1.1.2.1 /** Creates a <code>DispatchTreeTransformation</code>. */
56 cananian 1.1.2.1 public DispatchTreeTransformation(HCodeFactory parent, ClassHierarchy ch) {
57 cananian 1.1.2.4 // we take in SSI, and output RSSx.
58 cananian 1.1.2.4 super(harpoon.IR.Quads.QuadSSI.codeFactory(parent));
59 cananian 1.1.2.1 this.ch = ch;
60 cananian 1.1.2.1 }
61 cananian 1.1.2.1 protected HCode mutateHCode(HCodeAndMaps input) {
62 cananian 1.1.2.4 HCode ahc = input.ancestorHCode();
63 cananian 1.1.2.1 HCode hc = input.hcode();
64 cananian 1.3.2.1 assert ahc.getName().equals(harpoon.IR.Quads.QuadSSI.codename);
65 cananian 1.3.2.1 assert hc.getName().equals(harpoon.IR.Quads.QuadRSSx.codename);
66 cananian 1.1.2.1 // do a type analysis of the method.
67 cananian 1.1.2.5 SCCAnalysis scc = new SCCAnalysis(ahc);
68 cananian 1.1.2.5 ExactTypeMap etm = new ExactTypeMapProxy(input, scc);
69 cananian 1.1.2.5 new SCCOptimize(etm,
70 cananian 1.1.2.5 new ConstMapProxy(input, scc),
71 cananian 1.1.2.5 new ExecMapProxy(input, scc)).optimize(hc);
72 cananian 1.1.2.1 // now look for CALLs & devirtualize some of them.
73 cananian 1.1.2.1 for (Iterator it=hc.getElementsI(); it.hasNext(); ) {
74 cananian 1.1.2.1 Quad q = (Quad) it.next();
75 cananian 1.1.2.1 if (q instanceof CALL && examineCALL((CALL)q, etm))
76 cananian 1.1.2.1 devirtualizeCALL((CALL)q, etm);
77 cananian 1.1.2.1 }
78 cananian 1.1.2.1 // done!
79 cananian 1.1.2.1 return hc;
80 cananian 1.1.2.4 }
81 cananian 1.1.2.4 protected HCodeAndMaps cloneHCode(HCode hc, HMethod newmethod) {
82 cananian 1.1.2.4 // make SSI into RSSx.
83 cananian 1.3.2.1 assert hc.getName().equals(QuadSSI.codename);
84 cananian 1.1.2.4 return MyRSSx.cloneToRSSx((harpoon.IR.Quads.Code)hc, newmethod);
85 cananian 1.1.2.4 }
86 cananian 1.1.2.4 private static class MyRSSx extends QuadRSSx {
87 cananian 1.1.2.4 private MyRSSx(HMethod m) { super(m, null); }
88 cananian 1.1.2.4 public static HCodeAndMaps cloneToRSSx(harpoon.IR.Quads.Code c,
89 cananian 1.1.2.4 HMethod m) {
90 cananian 1.1.2.4 MyRSSx r = new MyRSSx(m);
91 cananian 1.1.2.4 return r.cloneHelper(c, r);
92 cananian 1.1.2.4 }
93 cananian 1.1.2.4 }
94 cananian 1.1.2.4 protected String mutateCodeName(String codeName) {
95 cananian 1.3.2.1 assert codeName.equals(QuadSSI.codename);
96 cananian 1.1.2.4 return MyRSSx.codename;
97 cananian 1.1.2.4 }
98 cananian 1.1.2.1 private boolean examineCALL(CALL call, ExactTypeMap etm) {
99 cananian 1.1.2.1 // skip if !isVirtual
100 cananian 1.1.2.1 if (!call.isVirtual()) return false;
101 cananian 1.1.2.1 // skip tail calls, too, just cuz they're funky.
102 cananian 1.1.2.1 if (call.isTailCall()) return false;
103 cananian 1.1.2.1 // final methods and methods in final classes are good candidates.
104 cananian 1.1.2.1 if (Modifier.isFinal(call.method().getModifiers()) ||
105 cananian 1.1.2.1 Modifier.isFinal(call.method().getDeclaringClass().getModifiers()))
106 cananian 1.1.2.1 return true;
107 cananian 1.1.2.1 // look at the receiver.
108 cananian 1.1.2.1 Temp recv = call.params(0);
109 cananian 1.1.2.1 // exact types always have just one receiver.
110 cananian 1.1.2.1 if (etm.isExactType(null, recv)) return true;
111 cananian 1.1.2.1 HClass type = etm.typeMap(null, recv);
112 cananian 1.1.2.4 // now we have to count up possible receivers (excl. abstract classes)
113 cananian 1.1.2.4 int n = numChildren(type);
114 cananian 1.1.2.4 if (!Modifier.isAbstract(type.getModifiers())) n++;
115 cananian 1.1.2.1 // okay, figure out if it's worth it.
116 cananian 1.1.2.1 return n < CUTOFF;
117 cananian 1.1.2.1 }
118 cananian 1.1.2.1 // separate method as it's recursive.
119 cananian 1.1.2.1 private int numChildren(HClass hc) {
120 cananian 1.1.2.4 // note that we don't count abstract classes in the total.
121 cananian 1.1.2.1 int n=0;
122 cananian 1.5 for (HClass hcc : ch.children(hc)) {
123 cananian 1.1.2.4 if (!Modifier.isAbstract(hcc.getModifiers())) n += 1;
124 cananian 1.1.2.4 n += numChildren(hcc);
125 cananian 1.1.2.4 }
126 cananian 1.1.2.1 return n;
127 cananian 1.1.2.1 }
128 cananian 1.1.2.1
129 cananian 1.1.2.1 /** The meat of the transformation. */
130 cananian 1.1.2.1 void devirtualizeCALL(CALL call, ExactTypeMap etm) {
131 cananian 1.1.2.1 QuadFactory qf = call.getFactory();
132 cananian 1.1.2.1 Temp recvr = call.params(0);
133 cananian 1.1.2.1
134 cananian 1.1.2.1 // find the set of relevant calls.
135 cananian 1.1.2.1 List methods = new ArrayList();
136 cananian 1.1.2.6 { // find the actual method which will be called.
137 cananian 1.1.2.6 HClass hc = etm.typeMap(null, recvr);
138 cananian 1.1.2.6 HMethod declarM = call.method();
139 cananian 1.1.2.6 HMethod actualM = hc.getMethod(declarM.getName(),
140 cananian 1.1.2.6 declarM.getDescriptor());
141 cananian 1.1.2.6 methods.add(actualM);
142 cananian 1.1.2.6 if (!etm.isExactType(null, recvr))
143 cananian 1.1.2.6 methods.addAll(ch.overrides(hc, actualM, true));
144 cananian 1.1.2.6 }
145 cananian 1.1.2.4 // remove uncallable methods.
146 cananian 1.1.2.4 methods.retainAll(ch.callableMethods());
147 cananian 1.1.2.4 // remove interface and abstract methods.
148 cananian 1.1.2.4 for (Iterator it=methods.iterator(); it.hasNext(); ) {
149 cananian 1.1.2.4 HMethod hm = (HMethod) it.next();
150 cananian 1.1.2.4 if (Modifier.isAbstract(hm.getModifiers()) ||
151 cananian 1.1.2.4 hm.getDeclaringClass().isInterface())
152 cananian 1.1.2.4 it.remove();
153 cananian 1.1.2.4 }
154 cananian 1.1.2.4 // could be that this method is completely uncallable. SKIP IT.
155 cananian 1.1.2.4 if (methods.size()==0) return;
156 cananian 1.1.2.4 // now sort methods from most-specific to least-specific
157 cananian 1.1.2.4 Collections.sort(methods, new Comparator() {
158 cananian 1.1.2.4 // ascending order. smallest is most-specific
159 cananian 1.1.2.4 public int compare(Object o1, Object o2) { // neg if o1 more sp.
160 cananian 1.1.2.4 HMethod hm1 = (HMethod)o1, hm2 = (HMethod)o2;
161 cananian 1.1.2.4 HClass hc1=hm1.getDeclaringClass(),hc2=hm2.getDeclaringClass();
162 cananian 1.1.2.4 return hc1.isInstanceOf(hc2)? -1: hc2.isInstanceOf(hc1)? 1: 0;
163 cananian 1.1.2.4 }
164 cananian 1.1.2.4 });
165 cananian 1.1.2.1
166 cananian 1.1.2.1 // make devirtualized calls.
167 cananian 1.1.2.1 List spcalls = new ArrayList(methods.size());
168 cananian 1.5 for (Object hmO : methods) {
169 cananian 1.5 HMethod hm = (HMethod) hmO;
170 cananian 1.1.2.1 // note that the quad will no longer be in SSI form when
171 cananian 1.1.2.1 // we're done because all CALLs have the same sigma functions.
172 cananian 1.1.2.1 CALL ncall = new CALL(qf, call, hm, call.params(),
173 cananian 1.1.2.1 call.retval(), call.retex(),
174 cananian 1.1.2.1 false /* isVirtual */,
175 cananian 1.1.2.1 call.isTailCall(),
176 cananian 1.1.2.1 call.dst(), call.src());
177 cananian 1.1.2.1 spcalls.add(ncall);
178 cananian 1.1.2.1 }
179 cananian 1.3.2.1 assert spcalls.size()>0;
180 cananian 1.1.2.1 // make PHI node for regular and exceptional returns.
181 cananian 1.1.2.1 PHI rephi = new PHI(qf, call, new Temp[0], spcalls.size());
182 cananian 1.1.2.1 PHI exphi = new PHI(qf, call, new Temp[0], spcalls.size());
183 cananian 1.1.2.1 // and TYPESWITCH node
184 cananian 1.1.2.3 HClass[] keys = new HClass[methods.size()];
185 cananian 1.1.2.1 for (int i=0; i<keys.length; i++)
186 cananian 1.1.2.1 keys[i] = ((HMethod)methods.get(i)).getDeclaringClass();
187 cananian 1.1.2.1 TYPESWITCH ts = new TYPESWITCH(qf, call, recvr, keys,
188 cananian 1.1.2.3 new Temp[0], false/* no default*/);
189 cananian 1.1.2.1 // link everything up.
190 cananian 1.1.2.1 for (int i=0; i<spcalls.size(); i++) {
191 cananian 1.1.2.1 CALL ncall = (CALL) spcalls.get(i);
192 cananian 1.1.2.1 Quad.addEdge(ncall, 0, rephi, i);
193 cananian 1.1.2.1 Quad.addEdge(ncall, 1, exphi, i);
194 cananian 1.1.2.1 Quad.addEdge(ts, i, ncall, 0);
195 cananian 1.1.2.1 }
196 cananian 1.1.2.1 Edge toE = call.prevEdge(0);
197 cananian 1.1.2.1 Edge reE = call.nextEdge(0);
198 cananian 1.1.2.1 Edge exE = call.nextEdge(1);
199 cananian 1.1.2.1 if (spcalls.size()==1) { // don't link TYPESWITCH and PHIs
200 cananian 1.1.2.1 CALL thecall = (CALL)spcalls.get(0);
201 cananian 1.1.2.1 Quad.addEdge((Quad)toE.from(), toE.which_succ(), thecall, 0);
202 cananian 1.1.2.1 Quad.addEdge(thecall, 0, (Quad)reE.to(), reE.which_pred());
203 cananian 1.1.2.1 Quad.addEdge(thecall, 1, (Quad)exE.to(), exE.which_pred());
204 cananian 1.1.2.1 } else { // link up TYPESWITCH and PHIs
205 cananian 1.1.2.1 Quad.addEdge((Quad)toE.from(), toE.which_succ(), ts, 0);
206 cananian 1.1.2.1 Quad.addEdge(rephi, 0, (Quad)reE.to(), reE.which_pred());
207 cananian 1.1.2.1 Quad.addEdge(exphi, 0, (Quad)exE.to(), exE.which_pred());
208 cananian 1.1.2.1 }
209 cananian 1.1.2.1 }
210 cananian 1.2 }