1 cananian 1.1.2.1 // MostlyZeroFinder.java, created Thu Oct 25 14:37:24 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.3 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.Analysis.Counters.CounterFactory;
8 cananian 1.1.2.3 import harpoon.Analysis.Quads.DefiniteInitOracle;
9 cananian 1.1.2.1 import harpoon.Analysis.Transactions.BitFieldNumbering;
10 cananian 1.1.2.1 import harpoon.Analysis.Transactions.BitFieldNumbering.BitFieldTuple;
11 cananian 1.1.2.2 import harpoon.Analysis.Transformation.MethodMutator;
12 cananian 1.1.2.1 import harpoon.Backend.Generic.Frame;
13 cananian 1.1.2.3 import harpoon.ClassFile.CachingCodeFactory;
14 cananian 1.1.2.2 import harpoon.ClassFile.HClass;
15 cananian 1.1.2.2 import harpoon.ClassFile.HCode;
16 cananian 1.1.2.2 import harpoon.ClassFile.HCodeAndMaps;
17 cananian 1.1.2.2 import harpoon.ClassFile.HCodeElement;
18 cananian 1.1.2.2 import harpoon.ClassFile.HCodeFactory;
19 cananian 1.1.2.2 import harpoon.ClassFile.HField;
20 cananian 1.1.2.2 import harpoon.ClassFile.HMethod;
21 cananian 1.1.2.2 import harpoon.IR.Quads.CJMP;
22 cananian 1.1.2.2 import harpoon.IR.Quads.CONST;
23 cananian 1.1.2.2 import harpoon.IR.Quads.Edge;
24 cananian 1.1.2.2 import harpoon.IR.Quads.GET;
25 cananian 1.1.2.2 import harpoon.IR.Quads.NEW;
26 cananian 1.1.2.2 import harpoon.IR.Quads.OPER;
27 cananian 1.1.2.2 import harpoon.IR.Quads.PHI;
28 cananian 1.1.2.2 import harpoon.IR.Quads.Qop;
29 cananian 1.1.2.2 import harpoon.IR.Quads.Quad;
30 cananian 1.1.2.2 import harpoon.IR.Quads.QuadFactory;
31 cananian 1.1.2.2 import harpoon.IR.Quads.QuadNoSSA;
32 cananian 1.1.2.2 import harpoon.IR.Quads.QuadVisitor;
33 cananian 1.1.2.2 import harpoon.IR.Quads.SET;
34 cananian 1.1.2.2 import harpoon.Temp.Temp;
35 cananian 1.1.2.2 import harpoon.Util.ArrayIterator;
36 cananian 1.8 import net.cscott.jutil.SnapshotIterator;
37 cananian 1.1.2.2 import harpoon.Util.Util;
38 cananian 1.1.2.1
39 cananian 1.1.2.2 import java.util.Iterator;
40 cananian 1.1.2.1 /**
41 cananian 1.1.2.3 * The <code>MostlyZeroFinder</code> will add counters to find fields
42 cananian 1.1.2.3 * which are mostly zero (or mostly 1, 2, etc).
43 cananian 1.1.2.1 *
44 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
45 cananian 1.9 * @version $Id: MostlyZeroFinder.java,v 1.9 2004/02/08 03:20:22 cananian Exp $
46 cananian 1.1.2.1 */
47 cananian 1.5 public class MostlyZeroFinder extends MethodMutator<Quad> {
48 cananian 1.1.2.3 /** the mostly-zero analysis can actually find mostly-N fields. this
49 cananian 1.1.2.3 * parameter lets you chose what 'N' should be. */
50 cananian 1.1.2.3 final static int MOSTLY_WHAT =
51 cananian 1.1.2.3 Integer.parseInt(System.getProperty("harpoon.mzf.lookfor", "0"));
52 cananian 1.1.2.1 final BitFieldNumbering bfn;
53 cananian 1.1.2.1 final boolean pointersAreLong;
54 cananian 1.1.2.1 final String suffix = "$mzf";
55 cananian 1.1.2.3 final DefiniteInitOracle dio;
56 cananian 1.1.2.1
57 cananian 1.1.2.3 /** Creates a <code>MostlyZeroFinder</code> using the given
58 cananian 1.1.2.3 * code factory, class hierarchy, and frame. */
59 cananian 1.1.2.3 public MostlyZeroFinder(HCodeFactory parent, ClassHierarchy ch,
60 cananian 1.1.2.3 Frame frame) {
61 cananian 1.7 // force a caching quad-no-ssa code factory.
62 cananian 1.1.2.3 this(new CachingCodeFactory(QuadNoSSA.codeFactory(parent)), ch, frame);
63 cananian 1.1.2.3 }
64 cananian 1.1.2.3 // the private constructor knows the code factory is cached and produces
65 cananian 1.7 // quad-no-ssa form.
66 cananian 1.1.2.3 private MostlyZeroFinder(CachingCodeFactory parent, ClassHierarchy ch,
67 cananian 1.1.2.3 Frame frame) {
68 cananian 1.1.2.3 super(parent);
69 cananian 1.1.2.1 this.bfn = new BitFieldNumbering(frame.getLinker(), suffix);
70 cananian 1.1.2.1 this.pointersAreLong = frame.pointersAreLong();
71 cananian 1.1.2.3 this.dio = (MOSTLY_WHAT==0) ? null :
72 cananian 1.1.2.3 new DefiniteInitOracle(parent, ch);
73 cananian 1.1.2.1 }
74 cananian 1.5 protected HCode<Quad> mutateHCode(HCodeAndMaps<Quad> input) {
75 cananian 1.5 HCode<Quad> hc = input.hcode();
76 cananian 1.1.2.1 // prevent instrumentation of the instrumentation code.
77 cananian 1.1.2.1 if ("harpoon.Runtime.Counters".equals
78 cananian 1.1.2.1 (hc.getMethod().getDeclaringClass().getName()))
79 cananian 1.1.2.1 return hc;
80 cananian 1.1.2.1 // use visitor.
81 cananian 1.1.2.1 Visitor v = new Visitor(hc);
82 cananian 1.6 // use snapshot while visiting so as not to confuse iterator
83 cananian 1.6 for (Iterator<Quad> it=new SnapshotIterator<Quad>
84 cananian 1.6 (hc.getElementsI()); it.hasNext(); )
85 cananian 1.6 it.next().accept(v);
86 cananian 1.1.2.1 // done!
87 cananian 1.1.2.1 return hc;
88 cananian 1.1.2.1 }
89 cananian 1.1.2.1 private class Visitor extends QuadVisitor {
90 cananian 1.1.2.1 final QuadFactory qf;
91 cananian 1.5 Visitor(HCode<Quad> hc) { qf=hc.getRootElement().getFactory(); }
92 cananian 1.1.2.1 public void visit(Quad q) { /* do nothing */ }
93 cananian 1.1.2.1 // xxx: should we treat fields of subclasses differently?
94 cananian 1.1.2.1 // perhaps a superclass never uses field x, but subclasses do?
95 cananian 1.1.2.1 public void visit(NEW q) {
96 cananian 1.1.2.1 // add 1 to 'alloc field'
97 cananian 1.1.2.1 addFieldAllocCounters(q.nextEdge(0), q.hclass());
98 cananian 1.1.2.1 }
99 cananian 1.1.2.1 Edge addFieldAllocCounters(Edge e, HClass hc) {
100 cananian 1.1.2.1 if (hc==null) return e; // recursion termination condition.
101 cananian 1.3.2.1 assert !hc.isInterface() && !hc.isArray();
102 cananian 1.1.2.1 // one counter per declared non-static field.
103 cananian 1.9 for (HField hf : hc.getDeclaredFields()) {
104 cananian 1.3.2.1 assert hc==hf.getDeclaringClass();
105 cananian 1.1.2.1 if (hf.isStatic()) continue;
106 cananian 1.1.2.1 if (hf.getName().endsWith(suffix)) continue;//don't count bits
107 cananian 1.1.2.3 if (!isOkay(hf)) continue; // some limits if MOSTLY_WHAT!=0
108 cananian 1.1.2.1 e = CounterFactory.spliceIncrement
109 cananian 1.1.2.1 (qf, e, "mzf.alloc."+hc.getName()+"."+hf.getName());
110 cananian 1.1.2.1 e = CounterFactory.spliceIncrement
111 cananian 1.1.2.1 (qf, e, "mzf.savedbytes."+hc.getName()+"."+hf.getName(),
112 cananian 1.1.2.1 sizeOf(hf.getType()));
113 cananian 1.1.2.1 }
114 cananian 1.1.2.1 // recurse.
115 cananian 1.1.2.1 return addFieldAllocCounters(e, hc.getSuperclass());
116 cananian 1.1.2.1 }
117 cananian 1.1.2.1 public void visit(SET q) {
118 cananian 1.1.2.1 // skip static fields.
119 cananian 1.1.2.1 if (q.field().isStatic()) return;
120 cananian 1.1.2.3 // skip non-definitely-initialized fields if MOSTLY_WHAT != 0
121 cananian 1.1.2.3 if (!isOkay(q.field())) return;
122 cananian 1.1.2.1
123 cananian 1.1.2.1 // get bit.
124 cananian 1.1.2.1 // if zero and x != 0
125 cananian 1.1.2.1 // inc 'nonzero' counter
126 cananian 1.1.2.1 // set bit.
127 cananian 1.1.2.1 // do set
128 cananian 1.1.2.1 Edge e = q.prevEdge(0);
129 cananian 1.1.2.1 BitFieldTuple bft = bfn.bfLoc(q.field());
130 cananian 1.1.2.1 Temp bitT = new Temp(qf.tempFactory(), "mzf_bit");
131 cananian 1.1.2.1 Temp maskT = new Temp(qf.tempFactory(), "mzf_mask");
132 cananian 1.1.2.1 Temp cmpT = new Temp(qf.tempFactory(), "mzf_cmp");
133 cananian 1.1.2.1 e = addAt(e, new GET(qf, q, bitT, bft.field, q.objectref()));
134 cananian 1.1.2.1 e = addAt(e, new CONST(qf, q, maskT,
135 cananian 1.1.2.1 new Integer(1<<bft.bit), HClass.Int));
136 cananian 1.1.2.1 e = addAt(e, new OPER(qf, q, Qop.IAND, cmpT,
137 cananian 1.1.2.1 new Temp[] {bitT, maskT}));
138 cananian 1.1.2.1 e = addAt(e, new OPER(qf, q, Qop.ICMPEQ, cmpT,
139 cananian 1.1.2.1 new Temp[] {cmpT, maskT}));
140 cananian 1.1.2.1 Quad qH = new CJMP(qf, q, cmpT, new Temp[0]);
141 cananian 1.1.2.1 e = addAt(e, 0, qH, 1);
142 cananian 1.1.2.1 Quad qF = new PHI(qf, q, new Temp[0], 3);
143 cananian 1.1.2.1 e = addAt(e, qF);
144 cananian 1.1.2.1 // okay, handle case that bit is 0.
145 cananian 1.1.2.1 Temp zeroT = new Temp(qf.tempFactory(), "mzf_zero");
146 cananian 1.1.2.1 Quad q0 = zeroConst(qf, q, zeroT, q.field().getType());
147 cananian 1.1.2.1 Quad q1 = new OPER(qf, q, cmpEqOp(q.field().getType()), cmpT,
148 cananian 1.1.2.1 new Temp[] {zeroT, q.src()});
149 cananian 1.1.2.1 Quad q2 = new CJMP(qf, q, cmpT, new Temp[0]);
150 cananian 1.1.2.1 // bail if new value (q.src()) is zero.
151 cananian 1.1.2.1 Quad.addEdge(qH, 0, q0, 0);
152 cananian 1.1.2.1 Quad.addEdge(q0, 0, q1, 0);
153 cananian 1.1.2.1 Quad.addEdge(q1, 0, q2, 0);
154 cananian 1.1.2.1 Quad.addEdge(q2, 1, qF, 1);
155 cananian 1.1.2.1 // set bit and increment counter. XXX: NOT THREAD SAFE!!!
156 cananian 1.1.2.1 Quad q3 = new OPER(qf, q, Qop.IOR, bitT, new Temp[] {bitT, maskT});
157 cananian 1.1.2.1 Quad q4 = new SET(qf, q, bft.field, q.objectref(), bitT);
158 cananian 1.1.2.1 Quad.addEdge(q2, 0, q3, 0);
159 cananian 1.1.2.1 Quad.addEdge(q3, 0, q4, 0);
160 cananian 1.1.2.1 Quad.addEdge(q4, 0, qF, 2);
161 cananian 1.1.2.1 HField hf = q.field();
162 cananian 1.1.2.1 e = CounterFactory.spliceIncrement
163 cananian 1.1.2.1 (qf, q4.nextEdge(0),
164 cananian 1.1.2.1 "mzf.nonzero."+hf.getDeclaringClass().getName()+
165 cananian 1.1.2.1 "."+hf.getName());
166 cananian 1.1.2.1 e = CounterFactory.spliceIncrement
167 cananian 1.1.2.1 (qf, e, "mzf.savedbytes."+hf.getDeclaringClass().getName()+
168 cananian 1.1.2.1 "."+hf.getName(), -sizeOf(hf.getType()));
169 cananian 1.1.2.1 }
170 cananian 1.1.2.1 }
171 cananian 1.1.2.3 // we can only compile meaningful numbers for primitive fields that
172 cananian 1.1.2.3 // are definitely-initialized if MOSTLY_WHAT is not zero.
173 cananian 1.1.2.3 private boolean isOkay(HField hf) {
174 cananian 1.1.2.3 if (MOSTLY_WHAT!=0)
175 cananian 1.1.2.3 return dio.isDefinitelyInitialized(hf) &&
176 cananian 1.1.2.3 hf.getType().isPrimitive();
177 cananian 1.1.2.3 return true;
178 cananian 1.1.2.3 }
179 cananian 1.1.2.1 private static CONST zeroConst(QuadFactory qf, HCodeElement src,
180 cananian 1.1.2.1 Temp dst, HClass type) {
181 cananian 1.1.2.3 // psst: here's a secret. the 'zeroConst' is actually not
182 cananian 1.1.2.3 // zero if MOSTLY_WHAT is not zero.
183 cananian 1.1.2.1 if (!type.isPrimitive())
184 cananian 1.1.2.1 return new CONST(qf, src, dst, null, HClass.Void);
185 cananian 1.1.2.1 if (type==HClass.Boolean || type==HClass.Byte ||
186 cananian 1.1.2.1 type==HClass.Short || type==HClass.Int || type==HClass.Char)
187 cananian 1.1.2.3 return new CONST(qf, src, dst,
188 cananian 1.1.2.3 new Integer(MOSTLY_WHAT), HClass.Int);
189 cananian 1.1.2.1 if (type==HClass.Long)
190 cananian 1.1.2.3 return new CONST(qf, src, dst,
191 cananian 1.1.2.3 new Long(MOSTLY_WHAT), HClass.Long);
192 cananian 1.1.2.1 if (type==HClass.Float)
193 cananian 1.1.2.3 return new CONST(qf, src, dst,
194 cananian 1.1.2.3 new Float(MOSTLY_WHAT), HClass.Float);
195 cananian 1.1.2.1 if (type==HClass.Double)
196 cananian 1.1.2.3 return new CONST(qf, src, dst,
197 cananian 1.1.2.3 new Double(MOSTLY_WHAT), HClass.Double);
198 cananian 1.3.2.1 assert false : "forgot a primitive type?";
199 cananian 1.1.2.1 return null;
200 cananian 1.1.2.1 }
201 cananian 1.1.2.1 private static int cmpEqOp(HClass type) {
202 cananian 1.1.2.1 if (!type.isPrimitive()) return Qop.ACMPEQ;
203 cananian 1.1.2.1 if (type==HClass.Boolean || type==HClass.Byte || type==HClass.Char ||
204 cananian 1.1.2.1 type==HClass.Short || type==HClass.Int) return Qop.ICMPEQ;
205 cananian 1.1.2.1 if (type==HClass.Long) return Qop.LCMPEQ;
206 cananian 1.1.2.1 if (type==HClass.Float) return Qop.FCMPEQ;
207 cananian 1.1.2.1 if (type==HClass.Double) return Qop.DCMPEQ;
208 cananian 1.3.2.1 assert false : "forgot a primitive type?";
209 cananian 1.1.2.1 return -1;
210 cananian 1.1.2.1 }
211 cananian 1.1.2.1 private int sizeOf(HClass type) {
212 cananian 1.1.2.1 if (!type.isPrimitive()) return pointersAreLong ? 8 : 4;
213 cananian 1.1.2.1 if (type==HClass.Boolean || type==HClass.Byte) return 1;
214 cananian 1.1.2.1 if (type==HClass.Char || type==HClass.Short) return 2;
215 cananian 1.1.2.1 if (type==HClass.Int || type==HClass.Float) return 4;
216 cananian 1.1.2.1 if (type==HClass.Long || type==HClass.Double) return 8;
217 cananian 1.3.2.1 assert false : "forgot a primitive type?";
218 cananian 1.1.2.1 return 0;
219 cananian 1.1.2.1 }
220 cananian 1.1.2.1 // private helper functions.
221 cananian 1.1.2.1 private static Edge addAt(Edge e, Quad q) { return addAt(e, 0, q, 0); }
222 cananian 1.1.2.1 private static Edge addAt(Edge e, int which_pred, Quad q, int which_succ) {
223 cananian 1.5 Quad frm = e.from(); int frm_succ = e.which_succ();
224 cananian 1.5 Quad to = e.to(); int to_pred = e.which_pred();
225 cananian 1.1.2.1 Quad.addEdge(frm, frm_succ, q, which_pred);
226 cananian 1.1.2.1 Quad.addEdge(q, which_succ, to, to_pred);
227 cananian 1.1.2.1 return to.prevEdge(to_pred);
228 cananian 1.1.2.1 }
229 cananian 1.2 }