1 cananian 1.1.2.1 // FieldReducer.java, created Thu Jul 19 18:55:44 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.ClassHierarchy;
7 cananian 1.1.2.2 import harpoon.Analysis.Maps.ConstMap;
8 cananian 1.1.2.2 import harpoon.Analysis.Maps.ExactTypeMap;
9 cananian 1.1.2.2 import harpoon.Analysis.Maps.ExecMap;
10 cananian 1.1.2.2 import harpoon.Analysis.Quads.SCC.SCCOptimize;
11 cananian 1.1.2.2 import harpoon.Analysis.Transformation.MethodMutator;
12 cananian 1.1.2.4 import harpoon.Backend.Generic.Frame;
13 cananian 1.1.2.2 import harpoon.ClassFile.CachingCodeFactory;
14 cananian 1.1.2.2 import harpoon.ClassFile.HClass;
15 cananian 1.1.2.2 import harpoon.ClassFile.HClassMutator;
16 cananian 1.1.2.2 import harpoon.ClassFile.HCode;
17 cananian 1.1.2.2 import harpoon.ClassFile.HCodeAndMaps;
18 cananian 1.1.2.2 import harpoon.ClassFile.HCodeEdge;
19 cananian 1.1.2.2 import harpoon.ClassFile.HCodeElement;
20 cananian 1.1.2.2 import harpoon.ClassFile.HCodeFactory;
21 cananian 1.1.2.2 import harpoon.ClassFile.HField;
22 cananian 1.1.2.2 import harpoon.ClassFile.HFieldMutator;
23 cananian 1.1.2.2 import harpoon.ClassFile.HMethod;
24 cananian 1.1.2.2 import harpoon.ClassFile.Linker;
25 cananian 1.1.2.3 import harpoon.IR.Quads.CALL;
26 cananian 1.1.2.2 import harpoon.IR.Quads.CONST;
27 cananian 1.1.2.2 import harpoon.IR.Quads.Edge;
28 cananian 1.1.2.2 import harpoon.IR.Quads.FOOTER;
29 cananian 1.1.2.2 import harpoon.IR.Quads.GET;
30 cananian 1.1.2.2 import harpoon.IR.Quads.HEADER;
31 cananian 1.1.2.3 import harpoon.IR.Quads.METHOD;
32 cananian 1.1.2.3 import harpoon.IR.Quads.NEW;
33 cananian 1.1.2.3 import harpoon.IR.Quads.PHI;
34 cananian 1.1.2.2 import harpoon.IR.Quads.Quad;
35 cananian 1.1.2.3 import harpoon.IR.Quads.QuadFactory;
36 cananian 1.1.2.2 import harpoon.IR.Quads.QuadSSI;
37 cananian 1.1.2.2 import harpoon.IR.Quads.SET;
38 cananian 1.1.2.3 import harpoon.IR.Quads.THROW;
39 cananian 1.1.2.2 import harpoon.Temp.Temp;
40 cananian 1.1.2.2 import harpoon.Temp.TempMap;
41 cananian 1.7 import net.cscott.jutil.SnapshotIterator;
42 cananian 1.1.2.2 import harpoon.Util.Util;
43 cananian 1.1.2.1
44 cananian 1.1.2.2 import java.util.Arrays;
45 cananian 1.1.2.3 import java.util.HashMap;
46 cananian 1.1.2.2 import java.util.HashSet;
47 cananian 1.1.2.2 import java.util.Iterator;
48 cananian 1.1.2.2 import java.util.Map;
49 cananian 1.1.2.2 import java.util.Set;
50 cananian 1.1.2.1 /**
51 cananian 1.1.2.1 * The <code>FieldReducer</code> code factory uses the results of a
52 cananian 1.1.2.1 * <code>BitWidthAnalysis</code> to shrink field types and eliminate
53 cananian 1.1.2.1 * unused and constant fields from objects.
54 cananian 1.1.2.1 *
55 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
56 cananian 1.8 * @version $Id: FieldReducer.java,v 1.8 2004/02/08 03:20:22 cananian Exp $
57 cananian 1.1.2.1 */
58 cananian 1.5 public class FieldReducer extends MethodMutator<Quad> {
59 cananian 1.1.2.5 private static final boolean no_mutate =
60 cananian 1.1.2.5 Boolean.getBoolean("harpoon.sizeopt.no-field-reducer");
61 cananian 1.1.2.3 private static final boolean DEBUG = false;
62 cananian 1.1.2.1 final BitWidthAnalysis bwa;
63 cananian 1.1.2.3 final Linker linker;
64 cananian 1.1.2.1
65 cananian 1.1.2.1 /** Creates a <code>FieldReducer</code>. */
66 cananian 1.1.2.4 public FieldReducer(HCodeFactory parent, Frame frame, ClassHierarchy ch,
67 cananian 1.1.2.3 Set roots, String fieldRootResourceName) {
68 cananian 1.1.2.1 this(new CachingCodeFactory(QuadSSI.codeFactory(parent)),
69 cananian 1.1.2.4 frame, ch, roots, fieldRootResourceName);
70 cananian 1.1.2.1 }
71 cananian 1.1.2.4 private FieldReducer(CachingCodeFactory parent, Frame frame,
72 cananian 1.1.2.3 ClassHierarchy ch, Set roots, String frrn) {
73 cananian 1.1.2.1 super(parent);
74 cananian 1.1.2.4 this.bwa = new BitWidthAnalysis(frame.getLinker(), parent,
75 cananian 1.1.2.4 ch, roots, frrn);
76 cananian 1.1.2.4 this.linker = frame.getLinker();
77 cananian 1.1.2.1 // pull all our classes through the mutator.
78 cananian 1.1.2.4 this.hcf = super.codeFactory();
79 cananian 1.5 for (Iterator<HMethod> it=ch.callableMethods().iterator();
80 cananian 1.5 it.hasNext(); )
81 cananian 1.5 hcf.convert(it.next());
82 cananian 1.1.2.1 // now munge class fields (after we've rewritten all field references)
83 cananian 1.1.2.1
84 cananian 1.1.2.1 // first, collect all non-static fields of this application.
85 cananian 1.5 Set<HField> flds = new HashSet<HField>(7*ch.classes().size());
86 cananian 1.5 for (Iterator<HClass> it=ch.classes().iterator(); it.hasNext(); )
87 cananian 1.5 flds.addAll(Arrays.asList(it.next().getFields()));
88 cananian 1.5 for (Iterator<HField> it=flds.iterator(); it.hasNext(); )
89 cananian 1.5 if (it.next().isStatic()) it.remove();
90 cananian 1.1.2.1 // now munge fields!
91 cananian 1.8 for (HField hf : flds) {
92 cananian 1.1.2.5 if (no_mutate) continue;
93 cananian 1.1.2.1 // remove all unread and constant fields.
94 cananian 1.1.2.1 // (which should have no more references in any HCode)
95 cananian 1.1.2.1 if (bwa.isConst(hf) || !bwa.isRead(hf)) {
96 cananian 1.1.2.3 if (DEBUG)
97 cananian 1.1.2.3 System.err.println("REMOVING "+hf+" BECAUSE "+
98 cananian 1.1.2.3 (bwa.isConst(hf)?"it is constant ":"")+
99 cananian 1.1.2.3 (bwa.isRead(hf)?"":"it is unread"));
100 cananian 1.1.2.1 hf.getDeclaringClass().getMutator().removeDeclaredField(hf);
101 cananian 1.1.2.1 continue;
102 cananian 1.1.2.1 }
103 cananian 1.1.2.1 // shrink field sizes
104 cananian 1.1.2.1 HClass hc = hf.getType();
105 cananian 1.1.2.1 if (!hc.isPrimitive()) continue;
106 cananian 1.1.2.1 if (hc==HClass.Float || hc==HClass.Double) continue;
107 cananian 1.1.2.1 int p = bwa.plusWidthMap(hf), m = bwa.minusWidthMap(hf);
108 cananian 1.1.2.1 // (pick a size)
109 cananian 1.1.2.1 HClass nhc = null;
110 cananian 1.1.2.1 if (hc==HClass.Long || (m<64 && p<=63)) nhc = HClass.Long;
111 cananian 1.1.2.1 if (hc==HClass.Int || (m<32 && p<=31)) nhc = HClass.Int;
112 cananian 1.1.2.1 if (hc==HClass.Char || (m==0 && p<=16)) nhc = HClass.Char;
113 cananian 1.1.2.1 if (hc==HClass.Short || (m<16 && p<=15)) nhc = HClass.Short;
114 cananian 1.1.2.1 if (hc==HClass.Byte || (m< 8 && p<= 7)) nhc = HClass.Byte;
115 cananian 1.1.2.1 if (hc==HClass.Boolean|| (m==0 && p<= 1)) nhc = HClass.Boolean;
116 cananian 1.3.2.1 assert nhc!=null; // one of these cases must have matched
117 cananian 1.1.2.3 if (DEBUG && hc!=nhc) System.err.print("REDUCING "+hf);
118 cananian 1.1.2.1 hf.getMutator().setType(nhc);
119 cananian 1.1.2.3 if (DEBUG && hc!=nhc) System.err.println(" TO "+hf);
120 cananian 1.1.2.1 }
121 cananian 1.1.2.5 // update field sizes in frame. (this is a bit of a hack)
122 cananian 1.1.2.5 frame.setClassHierarchy(ch);
123 cananian 1.1.2.4 // wrap a size counter around everything (maybe).
124 cananian 1.1.2.4 if (Boolean.getBoolean("harpoon.sizeopt.bitcounters")) {
125 cananian 1.1.2.4 this.hcf = new CachingCodeFactory
126 cananian 1.1.2.4 (new SizeCounters(this.hcf, frame, bwa).codeFactory());
127 cananian 1.1.2.4 // pull everything through.
128 cananian 1.5 for (Iterator<HMethod> it=ch.callableMethods().iterator();
129 cananian 1.5 it.hasNext(); )
130 cananian 1.5 hcf.convert(it.next());
131 cananian 1.1.2.4 }
132 cananian 1.1.2.1 // done!
133 cananian 1.1.2.1 }
134 cananian 1.1.2.4 // allow us to override the hcf.
135 cananian 1.1.2.4 private HCodeFactory hcf;
136 cananian 1.1.2.4 public HCodeFactory codeFactory() { return hcf; }
137 cananian 1.1.2.4
138 cananian 1.5 protected HCode<Quad> mutateHCode(HCodeAndMaps<Quad> input) {
139 cananian 1.5 HCode<Quad> hc = input.hcode();
140 cananian 1.1.2.3 final Wrapper w = new Wrapper(input);
141 cananian 1.1.2.3
142 cananian 1.1.2.3 // optimize only methods which this analysis knows are callable.
143 cananian 1.1.2.3 // (non-callable methods will be entirely eliminated by dead-code
144 cananian 1.1.2.3 // elimination, resulting in invalid quad hcodes)
145 cananian 1.1.2.3 boolean isCallable =
146 cananian 1.5 w.execMap((METHOD)hc.getRootElement().next(1));
147 cananian 1.1.2.3 if (!isCallable) return eviscerate(hc);
148 cananian 1.1.2.1 new SCCOptimize(w, w, w).optimize(hc);
149 cananian 1.1.2.5 if (no_mutate) return hc;
150 cananian 1.1.2.3
151 cananian 1.6 for (Iterator<Quad> it=new SnapshotIterator<Quad>
152 cananian 1.6 (hc.getElementsI()); it.hasNext(); ) {
153 cananian 1.6 Quad aquad = it.next();
154 cananian 1.6 if (aquad instanceof GET) {
155 cananian 1.6 GET q = (GET) aquad;
156 cananian 1.1.2.3 // if this GET is not dead, then the field is read.
157 cananian 1.3.2.1 assert bwa.isRead(q.field());
158 cananian 1.1.2.1 if (bwa.isConst(q.field())) {
159 cananian 1.1.2.1 // replace reads of constant fields with constant.
160 cananian 1.1.2.1 Quad.replace(q, new CONST
161 cananian 1.1.2.1 (q.getFactory(), q, q.dst(),
162 cananian 1.1.2.1 bwa.constMap(q.field()),
163 cananian 1.1.2.1 (bwa.constMap(q.field())==null) ?
164 cananian 1.1.2.1 HClass.Void :
165 cananian 1.1.2.1 toInternal(q.field().getType())));
166 cananian 1.1.2.1 }
167 cananian 1.1.2.1 }
168 cananian 1.6 if (aquad instanceof SET) {
169 cananian 1.6 SET q = (SET) aquad;
170 cananian 1.1.2.1 if (!bwa.isRead(q.field())) {
171 cananian 1.1.2.1 // throw away writes to unread fields.
172 cananian 1.1.2.1 q.remove();
173 cananian 1.1.2.3 } else if (bwa.isConst(q.field()))
174 cananian 1.1.2.3 // throw away writes to compile-time constant fields.
175 cananian 1.1.2.3 q.remove();
176 cananian 1.1.2.1 }
177 cananian 1.1.2.1 }
178 cananian 1.1.2.1 return hc;
179 cananian 1.1.2.1 }
180 cananian 1.1.2.3 // Eviscerate this uncallable method, replacing with a simple throw.
181 cananian 1.5 private HCode<Quad> eviscerate(HCode<Quad> hc) {
182 cananian 1.1.2.3 HEADER header = (HEADER) hc.getRootElement();
183 cananian 1.1.2.3 FOOTER footer = (FOOTER) header.next(0);
184 cananian 1.1.2.3 METHOD method = (METHOD) header.next(1);
185 cananian 1.1.2.3 footer = footer.resize(1); //eliminate all non-HEADER edges into footer
186 cananian 1.3.2.1 assert footer.prevLength()==1;
187 cananian 1.3.2.1 assert footer.prev(0)==header;
188 cananian 1.3.2.1 assert method.nextLength()==1;
189 cananian 1.1.2.3 // create new 'throw new RuntimeException()' body.
190 cananian 1.1.2.3 HClass HCrex = linker.forName("java.lang.RuntimeException");
191 cananian 1.1.2.3 QuadFactory qf = header.getFactory();
192 cananian 1.1.2.3 HCodeElement src = method;
193 cananian 1.1.2.3 Temp t0 = new Temp(qf.tempFactory());
194 cananian 1.1.2.3 Temp t1 = new Temp(qf.tempFactory());
195 cananian 1.1.2.3 Temp t2 = new Temp(qf.tempFactory());
196 cananian 1.1.2.3 // create new RuntimeException object.
197 cananian 1.1.2.3 Quad q0 = new NEW(qf, src, t0, HCrex);
198 cananian 1.1.2.3 // initialize it.
199 cananian 1.1.2.3 Quad q1 = new CALL(qf, src, HCrex.getConstructor(new HClass[0]),
200 cananian 1.1.2.3 new Temp[] { t0 }, null, t1, false, false,
201 cananian 1.1.2.3 new Temp[0]);
202 cananian 1.1.2.3 // merge all exceptions from call
203 cananian 1.1.2.3 Quad q2 = new PHI(qf, src, new Temp[] { t2 },
204 cananian 1.1.2.3 new Temp[][] { new Temp[] { t0, t1 } }, 2);
205 cananian 1.1.2.3 // throw!
206 cananian 1.1.2.3 Quad q3 = new THROW(qf, src, t2);
207 cananian 1.1.2.3 // link everything together.
208 cananian 1.1.2.3 Quad.addEdges(new Quad[] { method, q0, q1, q2, q3 });
209 cananian 1.1.2.3 Quad.addEdge(q1, 1, q2, 1);
210 cananian 1.1.2.3 footer = footer.attach(q3, 0);
211 cananian 1.1.2.3 return hc;
212 cananian 1.1.2.3 }
213 cananian 1.1.2.3
214 cananian 1.1.2.1 // Deal with the fact that external Byte/Short/Char/Boolean classes
215 cananian 1.1.2.1 // are represented internally as ints.
216 cananian 1.1.2.1 static HClass toInternal(HClass c) {
217 cananian 1.1.2.1 if (c.equals(HClass.Byte) || c.equals(HClass.Short) ||
218 cananian 1.1.2.1 c.equals(HClass.Char) || c.equals(HClass.Boolean))
219 cananian 1.1.2.1 return HClass.Int;
220 cananian 1.1.2.1 return c;
221 cananian 1.1.2.1 }
222 cananian 1.1.2.1 // wrapper to redirect maps through the hcodeandmaps
223 cananian 1.5 class Wrapper implements ExactTypeMap<Quad>, ConstMap<Quad>, ExecMap<Quad>{
224 cananian 1.5 final Map<Quad,Quad> aem; final TempMap atm;
225 cananian 1.5 Wrapper(HCodeAndMaps<Quad> hcam) {
226 cananian 1.1.2.1 this.aem = hcam.ancestorElementMap();
227 cananian 1.1.2.1 this.atm = hcam.ancestorTempMap();
228 cananian 1.1.2.1 }
229 cananian 1.5 Quad map(Quad hce) {
230 cananian 1.5 return aem.get(hce);
231 cananian 1.1.2.1 }
232 cananian 1.1.2.1 Temp map(Temp t) { return atm.tempMap(t); }
233 cananian 1.1.2.1 // ExactTypeMap
234 cananian 1.5 public boolean isExactType(Quad hce, Temp t) {
235 cananian 1.1.2.1 return bwa.isExactType(map(hce), map(t));
236 cananian 1.1.2.1 }
237 cananian 1.1.2.1 // TypeMap
238 cananian 1.5 public HClass typeMap(Quad hce, Temp t) {
239 cananian 1.1.2.1 return bwa.typeMap(map(hce), map(t));
240 cananian 1.1.2.1 }
241 cananian 1.1.2.1 // ConstMap
242 cananian 1.5 public boolean isConst(Quad hce, Temp t) {
243 cananian 1.1.2.1 return bwa.isConst(map(hce), map(t));
244 cananian 1.1.2.1 }
245 cananian 1.5 public Object constMap(Quad hce, Temp t) {
246 cananian 1.1.2.1 return bwa.constMap(map(hce), map(t));
247 cananian 1.1.2.1 }
248 cananian 1.1.2.1 // ExecMap
249 cananian 1.5 public boolean execMap(Quad hce) {
250 cananian 1.1.2.1 if (hce instanceof HEADER || hce instanceof FOOTER) return true;
251 cananian 1.1.2.1 return bwa.execMap(map(hce));
252 cananian 1.1.2.1 }
253 cananian 1.5 public boolean execMap(HCodeEdge<Quad> edge) {
254 cananian 1.1.2.1 Edge e = (Edge) edge;
255 cananian 1.1.2.1 if (e.from() instanceof HEADER) return true;
256 cananian 1.5 Edge ne = map(e.from()).nextEdge(e.which_succ());
257 cananian 1.1.2.1 return bwa.execMap(ne);
258 cananian 1.1.2.1 }
259 cananian 1.1.2.1 }
260 cananian 1.2 }