1 cananian 1.1.2.1 // MZFChooser.java, created Mon Nov 12 22:20:58 2001 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.SizeOpt;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import harpoon.Analysis.Transformation.MethodMutator;
7 cananian 1.1.2.2 import harpoon.ClassFile.HClass;
8 cananian 1.1.2.2 import harpoon.ClassFile.HCode;
9 cananian 1.1.2.2 import harpoon.ClassFile.HCodeAndMaps;
10 cananian 1.1.2.2 import harpoon.ClassFile.HCodeFactory;
11 cananian 1.1.2.2 import harpoon.ClassFile.HConstructor;
12 cananian 1.1.2.2 import harpoon.ClassFile.HField;
13 cananian 1.1.2.2 import harpoon.ClassFile.HMethod;
14 cananian 1.1.2.2 import harpoon.IR.Quads.CALL;
15 cananian 1.1.2.2 import harpoon.IR.Quads.CJMP;
16 cananian 1.1.2.2 import harpoon.IR.Quads.CONST;
17 cananian 1.1.2.2 import harpoon.IR.Quads.Code;
18 cananian 1.1.2.2 import harpoon.IR.Quads.Edge;
19 cananian 1.1.2.2 import harpoon.IR.Quads.NEW;
20 cananian 1.1.2.2 import harpoon.IR.Quads.OPER;
21 cananian 1.1.2.2 import harpoon.IR.Quads.PHI;
22 cananian 1.1.2.2 import harpoon.IR.Quads.Qop;
23 cananian 1.1.2.2 import harpoon.IR.Quads.Quad;
24 cananian 1.1.2.2 import harpoon.IR.Quads.QuadFactory;
25 cananian 1.1.2.2 import harpoon.IR.Quads.QuadRSSx;
26 cananian 1.1.2.2 import harpoon.IR.Quads.QuadSSA;
27 cananian 1.1.2.2 import harpoon.IR.Quads.QuadVisitor;
28 cananian 1.1.2.2 import harpoon.Temp.Temp;
29 cananian 1.7 import net.cscott.jutil.Default.PairList;
30 cananian 1.1.2.2 import harpoon.Util.Util;
31 cananian 1.1.2.1
32 cananian 1.1.2.2 import java.util.HashMap;
33 cananian 1.1.2.2 import java.util.HashSet;
34 cananian 1.1.2.2 import java.util.Iterator;
35 cananian 1.1.2.2 import java.util.List;
36 cananian 1.1.2.2 import java.util.Map;
37 cananian 1.1.2.2 import java.util.Set;
38 cananian 1.1.2.1 /**
39 cananian 1.1.2.1 * <code>MZFChooser</code> adds code to instantiate the correct
40 cananian 1.1.2.1 * MZF-compressed version of a class at run-time.
41 cananian 1.1.2.1 *
42 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
43 cananian 1.8 * @version $Id: MZFChooser.java,v 1.8 2004/02/08 03:20:22 cananian Exp $
44 cananian 1.1.2.1 */
45 cananian 1.5 class MZFChooser extends MethodMutator<Quad> {
46 cananian 1.1.2.1 /** an oracle to determine the properties of constructors. */
47 cananian 1.1.2.1 final ConstructorClassifier cc;
48 cananian 1.1.2.1 /** a map from HClasses to a list of sorted fields; the splitting has
49 cananian 1.1.2.1 * been done in the order of the list. */
50 cananian 1.6 final Map<HClass,List<PairList<HField,Number>>> listmap;
51 cananian 1.1.2.1 /** a map from <code>HField</code>s to the <code>HClass</code> which
52 cananian 1.1.2.1 * eliminates that field. */
53 cananian 1.5 final Map<HField,HClass> field2class;
54 cananian 1.1.2.1 /** Creates a <code>MZFChooser</code>. */
55 cananian 1.1.2.1 public MZFChooser(HCodeFactory hcf, ConstructorClassifier cc,
56 cananian 1.6 Map<HClass,List<PairList<HField,Number>>> listmap,
57 cananian 1.5 Map<HField,HClass> field2class) {
58 cananian 1.1.2.1 super(QuadSSA.codeFactory(hcf));
59 cananian 1.1.2.1 this.cc = cc;
60 cananian 1.1.2.1 this.listmap = listmap;
61 cananian 1.1.2.1 this.field2class = field2class;
62 cananian 1.1.2.1 }
63 cananian 1.1.2.2 protected String mutateCodeName(String codeName) {
64 cananian 1.1.2.2 // input SSA, output RSSx.
65 cananian 1.1.2.2 return QuadRSSx.codename;
66 cananian 1.1.2.2 }
67 cananian 1.5 protected HCodeAndMaps<Quad> cloneHCode(HCode<Quad> hc, HMethod newmethod){
68 cananian 1.1.2.2 // make SSA into RSSx.
69 cananian 1.3.2.1 assert hc.getName().equals(QuadSSA.codename);
70 cananian 1.1.2.2 return MyRSSx.cloneToRSSx((harpoon.IR.Quads.Code)hc, newmethod);
71 cananian 1.1.2.2 }
72 cananian 1.1.2.2 private static class MyRSSx extends QuadRSSx {
73 cananian 1.1.2.2 private MyRSSx(HMethod m) { super(m, null); }
74 cananian 1.5 public static HCodeAndMaps<Quad> cloneToRSSx(harpoon.IR.Quads.Code c,
75 cananian 1.1.2.2 HMethod m) {
76 cananian 1.1.2.2 MyRSSx r = new MyRSSx(m);
77 cananian 1.1.2.2 return r.cloneHelper(c, r);
78 cananian 1.1.2.2 }
79 cananian 1.1.2.2 }
80 cananian 1.5 protected HCode<Quad> mutateHCode(HCodeAndMaps<Quad> input) {
81 cananian 1.5 HCode<Quad> hc = input.hcode();
82 cananian 1.1.2.1 // first, find set of constructor-calls in this HCode.
83 cananian 1.1.2.1 QuadFinder qfinder = new QuadFinder();
84 cananian 1.5 for (Iterator<Quad> it=hc.getElementsI(); it.hasNext(); )
85 cananian 1.5 it.next().accept(qfinder);
86 cananian 1.1.2.1 // for each constructor:
87 cananian 1.8 for (CALL qC : qfinder.constructors) {
88 cananian 1.3.2.1 assert !qC.isVirtual();
89 cananian 1.1.2.1 // match it to a 'NEW'.
90 cananian 1.5 NEW qN = qfinder.temp2new.get(qC.params(0));
91 cananian 1.1.2.1 if (qN==null) continue; // typically call to super-constructor.
92 cananian 1.1.2.1 // if we know anything about this constructor...
93 cananian 1.1.2.1 if (!cc.isGood(qC.method())) continue;
94 cananian 1.3.2.1 assert qN.hclass().equals(qC.method().getDeclaringClass()) : qN+" / "+qC;
95 cananian 1.1.2.1 // fetch field list for this class.
96 cananian 1.6 List<PairList<HField,Number>> sortedFields =
97 cananian 1.5 listmap.get(qN.hclass());
98 cananian 1.1.2.1 if (sortedFields==null) continue; // nothing known about this class
99 cananian 1.1.2.1 // delete the NEW.
100 cananian 1.1.2.1 qN.remove();
101 cananian 1.1.2.1 // replace CALL with test-and-NEW-and-CALL.
102 cananian 1.1.2.1 refactor(qC.method(), qC, sortedFields);
103 cananian 1.1.2.1 }
104 cananian 1.1.2.1 return hc;
105 cananian 1.1.2.1 }
106 cananian 1.1.2.1 static class QuadFinder extends QuadVisitor {
107 cananian 1.1.2.1 /** map temps to 'NEW's where they are defined. */
108 cananian 1.5 Map<Temp,NEW> temp2new = new HashMap<Temp,NEW>();
109 cananian 1.1.2.1 /** set of constructor CALLs. */
110 cananian 1.5 Set<CALL> constructors = new HashSet<CALL>();
111 cananian 1.1.2.1 public void visit(Quad q) { /* not interesting */ }
112 cananian 1.1.2.1 public void visit(NEW q) {
113 cananian 1.3.2.1 assert !temp2new.containsKey(q.dst()) : "SSx form";
114 cananian 1.1.2.1 temp2new.put(q.dst(), q);
115 cananian 1.1.2.1 }
116 cananian 1.1.2.1 public void visit(CALL q) {
117 cananian 1.1.2.1 if (isConstructor(q.method()))
118 cananian 1.1.2.1 constructors.add(q);
119 cananian 1.1.2.1 }
120 cananian 1.1.2.1 ///////// copied from harpoon.Analysis.Quads.DefiniteInitOracle.
121 cananian 1.1.2.1 /** return an approximation to whether this is a constructor
122 cananian 1.1.2.1 * or not. it's always safe to return false. */
123 cananian 1.1.2.1 private static boolean isConstructor(HMethod hm) {
124 cananian 1.1.2.1 // this is tricky, because we want split constructors to
125 cananian 1.1.2.1 // count, too, even though renamed constructors (such as
126 cananian 1.1.2.1 // generated by initcheck, for instance) won't always be
127 cananian 1.1.2.1 // instanceof HConstructor. Look for names starting with
128 cananian 1.1.2.1 // '<init>', as well.
129 cananian 1.1.2.1 if (hm instanceof HConstructor) return true;
130 cananian 1.1.2.1 if (hm.getName().startsWith("<init>")) return true;
131 cananian 1.1.2.1 // XXX: what about methods generated by RuntimeMethod Cloner?
132 cananian 1.1.2.1 // we could try methods ending with <init>, but then the
133 cananian 1.1.2.1 // declaringclass information would be wrong.
134 cananian 1.1.2.1 //if (hm.getName().endsWidth("<init>")) return true;//not safe yet.
135 cananian 1.1.2.1 return false;
136 cananian 1.1.2.1 }
137 cananian 1.1.2.1 }
138 cananian 1.5 void refactor(HMethod constructor, CALL qC,
139 cananian 1.6 List<PairList<HField,Number>> sortedFields) {
140 cananian 1.1.2.2 QuadFactory qf = qC.getFactory();
141 cananian 1.1.2.1 if (sortedFields.size()==0) { // base case.
142 cananian 1.1.2.2 Quad qN = new NEW(qf, qC, qC.params(0),
143 cananian 1.1.2.1 qC.method().getDeclaringClass());
144 cananian 1.1.2.1 addAt(qC.prevEdge(0), qN);
145 cananian 1.1.2.1 return;
146 cananian 1.1.2.1 }
147 cananian 1.6 PairList<HField,Number> pair = sortedFields.get(0);
148 cananian 1.1.2.1 HField hf = (HField) pair.get(0); // field
149 cananian 1.1.2.1 Number num = (Number) pair.get(1); // 'mostly-what?'
150 cananian 1.1.2.2 // lookup 'spiffy constructor'
151 cananian 1.5 HClass newC = field2class.get(hf);
152 cananian 1.1.2.2 HMethod newM = newC.getDeclaredMethod
153 cananian 1.1.2.2 (constructor.getName(), constructor.getDescriptor());
154 cananian 1.1.2.1 // check whether this field is constant w/ this constructor.
155 cananian 1.1.2.1 if (cc.isConstant(constructor, hf)) {
156 cananian 1.1.2.1 Object val = cc.constantValue(constructor, hf);
157 cananian 1.1.2.1 if (val==null ? num.longValue()==0 :
158 cananian 1.1.2.2 (val instanceof Number && /* no String, etc constants */
159 cananian 1.1.2.2 ((Number)val).doubleValue()==num.doubleValue())) {
160 cananian 1.1.2.1 // okay, always a constant of the right value.
161 cananian 1.1.2.1 // we can replace original constructor with alternate.
162 cananian 1.1.2.2 CALL qCN = new CALL(qf, qC, newM,
163 cananian 1.1.2.1 qC.params(), qC.retval(), qC.retex(),
164 cananian 1.1.2.1 qC.isVirtual(), qC.isTailCall(),
165 cananian 1.1.2.1 qC.dst(), qC.src());
166 cananian 1.1.2.1 Quad.replace(qC, qCN);
167 cananian 1.1.2.1 // now recursively invoke on rest of list.
168 cananian 1.1.2.1 refactor(constructor, qCN,
169 cananian 1.1.2.1 sortedFields.subList(1, sortedFields.size()));
170 cananian 1.1.2.1 return;
171 cananian 1.1.2.1 }
172 cananian 1.1.2.1 }
173 cananian 1.1.2.1 // check whether this field is a function of a param.
174 cananian 1.1.2.3 // (oh, it also can't be a function of param#0, which isn't
175 cananian 1.1.2.3 // defined yet)
176 cananian 1.1.2.3 if (cc.isParam(constructor, hf) &&
177 cananian 1.1.2.3 0 != cc.paramNumber(constructor, hf)) {
178 cananian 1.1.2.1 int which = cc.paramNumber(constructor, hf);
179 cananian 1.1.2.2 // test whether param(which) is equal to 'num'.
180 cananian 1.1.2.1 // if so, use specialized class, else fall back.
181 cananian 1.1.2.2 Temp tZ = new Temp(qf.tempFactory(), "mostly");
182 cananian 1.1.2.2 Temp tC = new Temp(qf.tempFactory(), "lucky");
183 cananian 1.1.2.2 // tZ = CONST(mostlyN)
184 cananian 1.1.2.2 // tC = CMPEQ(tZ, param(which))
185 cananian 1.1.2.2 // if (tC)
186 cananian 1.1.2.2 // call spiffy constructor (recurse here)
187 cananian 1.1.2.2 // else
188 cananian 1.1.2.2 // NEW boring class
189 cananian 1.1.2.2 // call new boring constructor.
190 cananian 1.1.2.2 // PHI/return (output is SSx?) PHI/throw
191 cananian 1.1.2.2 HClass ty = widen(hf.getType());
192 cananian 1.1.2.2 Quad q0 = ty.isPrimitive() ?
193 cananian 1.1.2.2 new CONST(qf, qC, tZ, makeValue(ty, num), ty) :
194 cananian 1.1.2.2 new CONST(qf, qC, tZ, null, HClass.Void);
195 cananian 1.3.2.1 assert ty.isPrimitive()?true:num.intValue()==0;
196 cananian 1.1.2.2 Quad q1 = new OPER(qf, qC, makeEqOp(ty), tC,
197 cananian 1.1.2.2 new Temp[] { tZ, qC.params(which) });
198 cananian 1.1.2.2 Quad q2 = new CJMP(qf, qC, tC, new Temp[0]);
199 cananian 1.1.2.2 CALL q3 = new CALL(qf, qC, newM /* spiffy */,
200 cananian 1.1.2.2 qC.params(), qC.retval(), qC.retex(),
201 cananian 1.1.2.2 qC.isVirtual(), qC.isTailCall(),
202 cananian 1.1.2.2 qC.dst(), qC.src());
203 cananian 1.3.2.1 assert qC.retval()==null; // constructor should be void
204 cananian 1.1.2.2 Quad q4 = new NEW(qf, qC, qC.params(0), /* boring */
205 cananian 1.1.2.2 qC.method().getDeclaringClass());
206 cananian 1.1.2.2 Quad q5 = new PHI(qf, qC, new Temp[0], 2); //retval phi
207 cananian 1.1.2.2 Quad q6 = new PHI(qf, qC, new Temp[0], 2); //retex phi
208 cananian 1.1.2.2 Edge in = qC.prevEdge(0);
209 cananian 1.1.2.2 Edge retout=qC.nextEdge(0);
210 cananian 1.1.2.2 Edge exout=qC.nextEdge(1);
211 cananian 1.1.2.2 in = addAt(in, q0);
212 cananian 1.1.2.2 in = addAt(in, q1);
213 cananian 1.1.2.2 in = addAt(in, q2);
214 cananian 1.1.2.2 in = addAt(in, q4);
215 cananian 1.1.2.2 addAt(retout, q5);
216 cananian 1.1.2.2 addAt(exout, q6);
217 cananian 1.1.2.2 Quad.addEdge(q2, 1, q3, 0);
218 cananian 1.1.2.2 Quad.addEdge(q3, 0, q5, 1);
219 cananian 1.1.2.2 Quad.addEdge(q3, 1, q6, 1);
220 cananian 1.1.2.2 // now recursively invoke on rest of list.
221 cananian 1.1.2.2 refactor(constructor, q3,
222 cananian 1.1.2.2 sortedFields.subList(1, sortedFields.size()));
223 cananian 1.1.2.2 return;
224 cananian 1.1.2.1 }
225 cananian 1.1.2.1 // nothing known about this field w/ this constructor.
226 cananian 1.1.2.1 // clean up (add NEW) and go home.
227 cananian 1.1.2.2 Quad qN = new NEW(qf, qC, qC.params(0),
228 cananian 1.1.2.1 qC.method().getDeclaringClass());
229 cananian 1.1.2.1 addAt(qC.prevEdge(0), qN);
230 cananian 1.1.2.1 return;
231 cananian 1.1.2.1 }
232 cananian 1.1.2.1 // private helper functions.
233 cananian 1.1.2.1 private static Edge addAt(Edge e, Quad q) { return addAt(e, 0, q, 0); }
234 cananian 1.1.2.1 private static Edge addAt(Edge e, int which_pred, Quad q, int which_succ) {
235 cananian 1.5 Quad frm = e.from(); int frm_succ = e.which_succ();
236 cananian 1.5 Quad to = e.to(); int to_pred = e.which_pred();
237 cananian 1.1.2.1 Quad.addEdge(frm, frm_succ, q, which_pred);
238 cananian 1.1.2.1 Quad.addEdge(q, which_succ, to, to_pred);
239 cananian 1.1.2.1 return to.prevEdge(to_pred);
240 cananian 1.1.2.2 }
241 cananian 1.1.2.2 // widen sub-int primitive types.
242 cananian 1.1.2.2 private static HClass widen(HClass hc) {
243 cananian 1.1.2.2 return MZFCompressor.widen(hc);
244 cananian 1.1.2.2 }
245 cananian 1.1.2.2 // wrap a value w/ an object of the appropriate type.
246 cananian 1.1.2.2 private static Object makeValue(HClass type, Number num) {
247 cananian 1.1.2.2 return MZFCompressor.wrap(type, num);
248 cananian 1.1.2.2 }
249 cananian 1.1.2.2 private static int makeEqOp(HClass type) {
250 cananian 1.1.2.2 if (!type.isPrimitive()) return Qop.ACMPEQ;
251 cananian 1.1.2.2 if (type==HClass.Int) return Qop.ICMPEQ;
252 cananian 1.1.2.2 if (type==HClass.Long) return Qop.LCMPEQ;
253 cananian 1.1.2.2 if (type==HClass.Float) return Qop.FCMPEQ;
254 cananian 1.1.2.2 if (type==HClass.Double) return Qop.DCMPEQ;
255 cananian 1.3.2.1 assert false : ("unknown type: "+type);
256 cananian 1.1.2.2 return -1;
257 cananian 1.1.2.1 }
258 cananian 1.2 }