1 salcianu 1.1 // IAStatistics.java, created Tue Apr 23 19:00:41 2002 by salcianu
2 salcianu 1.1 // Copyright (C) 2000 Alexandru Salcianu <salcianu@MIT.EDU>
3 salcianu 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1 package harpoon.Analysis.MemOpt;
5 salcianu 1.1
6 salcianu 1.1 import java.util.Set;
7 salcianu 1.2 import java.util.HashSet;
8 salcianu 1.1 import java.util.Iterator;
9 salcianu 1.1 import java.util.Map;
10 salcianu 1.1 import java.util.HashMap;
11 salcianu 1.1 import java.util.Arrays;
12 salcianu 1.1 import java.util.Collection;
13 salcianu 1.1
14 salcianu 1.1 import java.lang.Comparable;
15 salcianu 1.1
16 salcianu 1.1 import java.io.ObjectInputStream;
17 salcianu 1.1 import java.io.FileInputStream;
18 salcianu 1.1 import java.io.FileReader;
19 salcianu 1.1 import java.io.BufferedReader;
20 salcianu 1.1
21 salcianu 1.1 import gnu.getopt.Getopt;
22 salcianu 1.1
23 salcianu 1.1 import harpoon.ClassFile.Linker;
24 salcianu 1.1 import harpoon.ClassFile.HMethod;
25 salcianu 1.1 import harpoon.ClassFile.HClass;
26 salcianu 1.1 import harpoon.ClassFile.HCode;
27 salcianu 1.1 import harpoon.ClassFile.HCodeFactory;
28 salcianu 1.1 import harpoon.ClassFile.CachingCodeFactory;
29 salcianu 1.1 import harpoon.ClassFile.SerializableCodeFactory;
30 salcianu 1.1
31 salcianu 1.4 import harpoon.Backend.Generic.Frame;
32 salcianu 1.4
33 salcianu 1.9 import harpoon.Util.Timer;
34 salcianu 1.2 import harpoon.Util.Util;
35 salcianu 1.2
36 salcianu 1.1 import harpoon.Analysis.ClassHierarchy;
37 salcianu 1.1 import harpoon.Analysis.Quads.QuadClassHierarchy;
38 salcianu 1.1 import harpoon.Analysis.MetaMethods.SmartCallGraph;
39 salcianu 1.1 import harpoon.Analysis.MetaMethods.MetaCallGraphImpl;
40 salcianu 1.1 import harpoon.Analysis.Quads.CallGraph;
41 salcianu 1.6 import harpoon.Instrumentation.AllocationStatistics.AllocationStatistics;
42 salcianu 1.1
43 salcianu 1.1 import harpoon.Analysis.MemOpt.IncompatibilityAnalysis;
44 salcianu 1.1
45 salcianu 1.1 import harpoon.IR.Quads.Quad;
46 salcianu 1.2 import harpoon.IR.Quads.QuadVisitor;
47 salcianu 1.3 import harpoon.IR.Quads.QuadWithTry;
48 salcianu 1.1 import harpoon.IR.Quads.QuadNoSSA;
49 salcianu 1.1 import harpoon.IR.Quads.QuadSSI;
50 salcianu 1.1 import harpoon.IR.Quads.NEW;
51 salcianu 1.1 import harpoon.IR.Quads.ANEW;
52 salcianu 1.1
53 salcianu 1.1 /**
54 salcianu 1.1 * <code>IAStatistics</code>
55 salcianu 1.1 *
56 salcianu 1.1 * @author Alexandru Salcianu <salcianu@MIT.EDU>
57 cananian 1.13 * @version $Id: IAStatistics.java,v 1.13 2004/02/08 03:19:53 cananian Exp $
58 salcianu 1.1 */
59 salcianu 1.1 public abstract class IAStatistics {
60 salcianu 1.1
61 salcianu 1.3 private static class TypeStat implements Comparable, Cloneable {
62 salcianu 1.3 public HClass hclass;
63 salcianu 1.7 public long[][] count = new long[3][2];
64 salcianu 1.1
65 salcianu 1.3 public TypeStat(HClass hclass) { this.hclass = hclass; }
66 salcianu 1.1
67 salcianu 1.1 public String toString() {
68 salcianu 1.1 return
69 salcianu 1.2 count[SITE][PREALLOC] + "\t" + count[SITE][HEAP] + "\t| " +
70 salcianu 1.7 count[OBJECT][PREALLOC] + "\t" + count[OBJECT][HEAP] + "\t| " +
71 salcianu 1.9 Util.memSizeFormat(count[SPACE][PREALLOC]) +
72 salcianu 1.8 "\t" +
73 salcianu 1.9 Util.memSizeFormat(count[SPACE][HEAP]) +
74 salcianu 1.2 "\t|| " + (hclass != null ? hclass.toString() : "");
75 salcianu 1.2 }
76 salcianu 1.2
77 salcianu 1.2 public long totalAlloc(int kind) {
78 salcianu 1.2 return count[kind][HEAP] + count[kind][PREALLOC];
79 salcianu 1.2 }
80 salcianu 1.2
81 salcianu 1.2 public int compareTo(Object o) {
82 salcianu 1.2 if(! (o instanceof TypeStat)) return -1;
83 salcianu 1.2 TypeStat ts2 = (TypeStat) o;
84 salcianu 1.2 return
85 salcianu 1.2 new Long(totalAlloc(OBJECT))
86 salcianu 1.2 .compareTo(new Long(ts2.totalAlloc(OBJECT)));
87 salcianu 1.1 }
88 salcianu 1.3
89 salcianu 1.3 public TypeStat add(TypeStat ts) {
90 salcianu 1.7 for(int i = 0; i < 3; i++)
91 salcianu 1.3 for(int j = 0; j < 2; j++)
92 salcianu 1.3 this.count[i][j] += ts.count[i][j];
93 salcianu 1.3 return this;
94 salcianu 1.3 }
95 salcianu 1.3
96 salcianu 1.3 public TypeStat diff(TypeStat ts) {
97 salcianu 1.7 for(int i = 0; i < 3; i++)
98 salcianu 1.3 for(int j = 0; j < 2; j++)
99 salcianu 1.3 this.count[i][j] -= ts.count[i][j];
100 salcianu 1.3 return this;
101 salcianu 1.3 }
102 salcianu 1.3
103 salcianu 1.3 public Object clone() {
104 salcianu 1.3 try {
105 salcianu 1.3 TypeStat copy = (TypeStat) super.clone();
106 salcianu 1.7 copy.count = new long[3][2];
107 salcianu 1.7 for(int i = 0; i < 3; i++)
108 salcianu 1.3 for(int j = 0; j < 2; j++)
109 salcianu 1.3 copy.count[i][j] = this.count[i][j];
110 salcianu 1.3 return copy;
111 salcianu 1.3 }
112 salcianu 1.3 catch(CloneNotSupportedException e) {
113 salcianu 1.3 e.printStackTrace();
114 salcianu 1.3 System.exit(1);
115 salcianu 1.3 return null; // never executed; makes compiler happy
116 salcianu 1.3 }
117 salcianu 1.3 }
118 salcianu 1.3
119 salcianu 1.3 public static TypeStat diff(TypeStat a, TypeStat b) {
120 salcianu 1.3 return ((TypeStat) a.clone()).diff(b);
121 salcianu 1.3 }
122 salcianu 1.1 }
123 salcianu 1.1
124 salcianu 1.1 private static final int SITE = 0;
125 salcianu 1.1 private static final int OBJECT = 1;
126 salcianu 1.7 private static final int SPACE = 2;
127 salcianu 1.1 private static final int HEAP = 0;
128 salcianu 1.1 private static final int PREALLOC = 1;
129 salcianu 1.1
130 salcianu 1.2
131 salcianu 1.2 /** Prints static and dynamic statisticis about the memory
132 salcianu 1.2 preallocation optimization through incompatibility analysis.
133 salcianu 1.2
134 salcianu 1.2 @param ia incompatibility analysis object that tells whether an
135 salcianu 1.2 allocation site is unitary (ie, can be preallocated) or not
136 salcianu 1.2
137 salcianu 1.2 @param as allocation statistics object that provides the
138 salcianu 1.2 dynamic data: how many times each allocation site was
139 salcianu 1.2 executed
140 salcianu 1.2
141 salcianu 1.4 @param hcf_nossa factory used to produce the SSI factory used
142 salcianu 1.4 by the <code>IncompatibilityAnalysis</code> <code>ia</code>.
143 salcianu 1.4
144 salcianu 1.4 @param linker Linker to get the classes
145 salcianu 1.4
146 salcianu 1.4 @param frame Frame used by the back-end. Useful for computing
147 salcianu 1.4 the size of the objects at runtime.
148 salcianu 1.4 */
149 salcianu 1.1 public static void printStatistics(IncompatibilityAnalysis ia,
150 salcianu 1.1 AllocationStatistics as,
151 salcianu 1.3 HCodeFactory hcf_nossa,
152 salcianu 1.4 Linker linker,
153 salcianu 1.4 Frame frame) {
154 salcianu 1.3
155 salcianu 1.4 if(frame != null)
156 salcianu 1.4 ia.printStatistics(frame, linker);
157 salcianu 1.3
158 salcianu 1.4 Set analyzedMethods = new HashSet(ia.allMethods());
159 salcianu 1.3
160 salcianu 1.4 // stats on the time required by the NoSSA -> SSI conversion
161 salcianu 1.4 ssiConversionStatistics(analyzedMethods, hcf_nossa);
162 salcianu 1.4 // stats on NEWs introduced for exception explicit handling
163 salcianu 1.4 withTry2NoSSAConversionStatistics(analyzedMethods, hcf_nossa);
164 salcianu 1.1
165 salcianu 1.4 Collection allocs =
166 salcianu 1.4 AllocationStatistics.getAllocs(analyzedMethods, hcf_nossa);
167 salcianu 1.1
168 salcianu 1.4 // stats on most executed allocation sites
169 salcianu 1.2 as.printStatistics(allocs, new MyVisitor(ia));
170 salcianu 1.2
171 salcianu 1.4 TypeStat[] tss = buildStatistics(ia, as, allocs);
172 salcianu 1.4
173 salcianu 1.4 HClass hThrowable = linker.forName("java.lang.Throwable");
174 salcianu 1.10 HClass hStringBuffer = linker.forName("java.lang.StringBuffer");
175 salcianu 1.2 TypeStat total = new TypeStat(null);
176 salcianu 1.3 TypeStat total_arrays = new TypeStat(null);
177 salcianu 1.3 TypeStat total_throwables = new TypeStat(null);
178 salcianu 1.10 TypeStat total_sb = new TypeStat(null);
179 salcianu 1.4 TypeStat total_program = new TypeStat(null);
180 salcianu 1.2
181 salcianu 1.8 System.out.println
182 salcianu 1.8 ("SITES\t\t|OBJECTS\t|SPACE\t\t||");
183 salcianu 1.8 System.out.println
184 salcianu 1.8 ("PREALLOC HEAP\t|PREALLOC HEAP\t|PREALLOC HEAP\t||CLASS");
185 salcianu 1.2 System.out.println
186 salcianu 1.2 ("------------------------------------------------------------");
187 salcianu 1.2 for(int index_ts = 0; index_ts < tss.length; index_ts++) {
188 salcianu 1.2 TypeStat ts = tss[index_ts];
189 salcianu 1.2 System.out.println(ts);
190 salcianu 1.3 total.add(ts);
191 salcianu 1.3 if(ts.hclass.isArray())
192 salcianu 1.3 total_arrays.add(ts);
193 salcianu 1.3 if(ts.hclass.isInstanceOf(hThrowable))
194 salcianu 1.3 total_throwables.add(ts);
195 salcianu 1.10 if(ts.hclass.isInstanceOf(hStringBuffer))
196 salcianu 1.10 total_sb.add(ts);
197 salcianu 1.1 }
198 salcianu 1.1
199 salcianu 1.2 System.out.println
200 salcianu 1.2 ("------------------------------------------------------------");
201 salcianu 1.2 System.out.println(total);
202 salcianu 1.2
203 salcianu 1.3 printTotal("OVERALL", total);
204 salcianu 1.3 printTotal("ARRAYS", total_arrays);
205 salcianu 1.3 printTotal("NON-ARRAYS", TypeStat.diff(total, total_arrays));
206 salcianu 1.3 printTotal("THROWABLES", total_throwables);
207 salcianu 1.3 printTotal("NON_THROWABLES", TypeStat.diff(total, total_throwables));
208 salcianu 1.10 printTotal("STRINGBUFFERS", total_sb);
209 salcianu 1.4 }
210 salcianu 1.4
211 salcianu 1.4
212 salcianu 1.4 // prints statistics on how many allocation sites were introduced
213 salcianu 1.4 // by the QuadWithTry -> QuadNoSSA conversion (quite MANY!)
214 salcianu 1.4 private static void withTry2NoSSAConversionStatistics
215 salcianu 1.4 (Set methods, HCodeFactory hcf_nossa) {
216 salcianu 1.4 Collection allocs = AllocationStatistics.getAllocs(methods, hcf_nossa);
217 salcianu 1.4 Collection initial_allocs =
218 salcianu 1.4 AllocationStatistics.getAllocs(methods, QuadWithTry.codeFactory());
219 salcianu 1.4
220 salcianu 1.4 long delta_sites = allocs.size() - initial_allocs.size();
221 salcianu 1.4
222 salcianu 1.4 System.out.println
223 salcianu 1.9 (Util.longProportion(delta_sites, initial_allocs.size(), 5, 2) +
224 salcianu 1.4 " allocations introduced by QuadWithTry -> QuadNoSSA");
225 salcianu 1.3 }
226 salcianu 1.3
227 salcianu 1.3
228 salcianu 1.3 private static void printTotal(String label, TypeStat total) {
229 salcianu 1.1 System.out.println
230 salcianu 1.4 (label + " PREALLOCATED SITES:\t" +
231 salcianu 1.9 Util.longProportion(total.count[SITE][PREALLOC],
232 salcianu 1.9 total.count[SITE][HEAP], 5, 2));
233 salcianu 1.1 System.out.println
234 salcianu 1.4 (label + " PREALLOCATED OBJECTS:\t" +
235 salcianu 1.9 Util.longProportion(total.count[OBJECT][PREALLOC],
236 salcianu 1.9 total.count[OBJECT][HEAP], 5, 2));
237 salcianu 1.7 System.out.println
238 salcianu 1.7 (label + " PREALLOCATED SPACE:\t" +
239 salcianu 1.10 Util.longProportion(total.count[SPACE][PREALLOC],
240 salcianu 1.10 total.count[SPACE][HEAP], 5, 2));
241 salcianu 1.10 System.out.println
242 salcianu 1.10 (label + " Preallocated Space:\t" +
243 salcianu 1.9 Util.longProportion(total.count[SPACE][PREALLOC],
244 salcianu 1.9 total.count[SPACE][HEAP], 5, 2, true));
245 salcianu 1.2 }
246 salcianu 1.2
247 salcianu 1.2
248 salcianu 1.2 private static class MyVisitor extends QuadVisitor {
249 salcianu 1.2 public MyVisitor(IncompatibilityAnalysis ia) { this.ia = ia; }
250 salcianu 1.2
251 salcianu 1.2 private IncompatibilityAnalysis ia;
252 salcianu 1.2
253 salcianu 1.2 public void visit(Quad quad) {
254 salcianu 1.2 System.out.println
255 salcianu 1.2 (selfIncompatible(quad, ia) ? "\tnon-unitary" : "\tunitary");
256 salcianu 1.2 }
257 salcianu 1.1 }
258 salcianu 1.1
259 salcianu 1.1
260 salcianu 1.4 private static TypeStat get_type_stat(Map hclass2stat, HClass hclass) {
261 salcianu 1.4 TypeStat result = (TypeStat) hclass2stat.get(hclass);
262 salcianu 1.4 if(result == null)
263 salcianu 1.4 hclass2stat.put(hclass, result = new TypeStat(hclass));
264 salcianu 1.4 return result;
265 salcianu 1.4 }
266 salcianu 1.2
267 salcianu 1.4 private static TypeStat[] buildStatistics
268 salcianu 1.4 (IncompatibilityAnalysis ia, AllocationStatistics as,
269 salcianu 1.4 Collection allocs) {
270 salcianu 1.4 Map hclass2stat = new HashMap();
271 salcianu 1.4
272 cananian 1.13 for(Object qO : allocs) {
273 cananian 1.13 Quad q = (Quad) qO;
274 salcianu 1.4
275 salcianu 1.4 /*
276 salcianu 1.1 HMethod hm = q.getFactory().getMethod();
277 salcianu 1.1
278 salcianu 1.4 // methods called only by the startup code are not analyzed;
279 salcianu 1.4 // (they are not transitively called from the entry method)
280 salcianu 1.4 // hence, we ignore all the allocation sites from there
281 salcianu 1.4 if(!ia.allMethods().contains(hm))
282 salcianu 1.1 continue;
283 salcianu 1.3 */
284 salcianu 1.1
285 salcianu 1.4 TypeStat ts = get_type_stat(hclass2stat, allocatedClass(q));
286 salcianu 1.8 int place =
287 salcianu 1.12 (selfIncompatible(q, ia) ||
288 salcianu 1.12 !PreallocOpt.extraCond(q) ||
289 salcianu 1.12 PreallocOpt.hasFinalizer(q)) ?
290 salcianu 1.8 HEAP : PREALLOC;
291 salcianu 1.8 ts.count[OBJECT][place] += as.getCount(q);
292 salcianu 1.8 ts.count[SITE][place]++;
293 salcianu 1.8 ts.count[SPACE][place] += as.getMemAmount(q);
294 salcianu 1.1 }
295 salcianu 1.2
296 salcianu 1.4 Collection tss_coll = hclass2stat.values();
297 salcianu 1.4 TypeStat[] tss =
298 salcianu 1.4 (TypeStat[]) tss_coll.toArray(new TypeStat[tss_coll.size()]);
299 salcianu 1.4 Arrays.sort(tss);
300 salcianu 1.4
301 salcianu 1.4 return tss;
302 salcianu 1.1 }
303 salcianu 1.1
304 salcianu 1.1 private static HClass allocatedClass(Quad q) {
305 salcianu 1.1 if(q instanceof NEW)
306 salcianu 1.1 return ((NEW) q).hclass();
307 salcianu 1.1 else if(q instanceof ANEW)
308 salcianu 1.1 return ((ANEW) q).hclass();
309 salcianu 1.1 else throw new IllegalArgumentException
310 salcianu 1.9 ("Not an allocation " + Util.code2str(q));
311 salcianu 1.1 }
312 salcianu 1.1
313 salcianu 1.1 private static boolean selfIncompatible
314 salcianu 1.1 (Quad q, IncompatibilityAnalysis ia) {
315 salcianu 1.1 if(q instanceof ANEW) return true;
316 salcianu 1.2 assert q instanceof NEW;
317 salcianu 1.1 Quad qssi = ia.getSSIQuad(q);
318 salcianu 1.1 assert qssi != null : "null qssi";
319 salcianu 1.4 return
320 salcianu 1.4 ia.isSelfIncompatible(qssi);
321 salcianu 1.4 }
322 salcianu 1.4
323 salcianu 1.4
324 salcianu 1.4 // prints statistics regarding the noSSA -> SSI conversion time
325 salcianu 1.4 // for the set of analyzed methods (not all methods; we want to
326 salcianu 1.4 // compare it with the analysis time)
327 salcianu 1.4 private static void ssiConversionStatistics(Collection methods,
328 salcianu 1.4 HCodeFactory hcf_nossa) {
329 salcianu 1.4 Timer timer = new Timer();
330 salcianu 1.4 timer.start();
331 salcianu 1.4 HCodeFactory hcf_ssi = QuadSSI.codeFactory(hcf_nossa);
332 salcianu 1.4 for(Iterator it = methods.iterator(); it.hasNext(); )
333 salcianu 1.4 hcf_ssi.convert((HMethod) it.next());
334 salcianu 1.4 timer.stop();
335 salcianu 1.4 System.out.println("SSI conversion time: " + timer);
336 salcianu 1.1 }
337 salcianu 1.1 }