1 salcianu 1.1 // AllocationStatistics.java, created Sat Nov 30 22:21:12 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.Instrumentation.AllocationStatistics;
5 salcianu 1.1
6 salcianu 1.1 import harpoon.ClassFile.HClass;
7 salcianu 1.1 import harpoon.ClassFile.HMethod;
8 salcianu 1.1 import harpoon.ClassFile.Linker;
9 salcianu 1.1 import harpoon.ClassFile.HCodeFactory;
10 salcianu 1.1 import harpoon.Analysis.Quads.CallGraph;
11 salcianu 1.1 import harpoon.IR.Quads.Quad;
12 salcianu 1.1 import harpoon.IR.Quads.QuadVisitor;
13 salcianu 1.1 import harpoon.IR.Quads.Code;
14 salcianu 1.1 import harpoon.Analysis.PointerAnalysis.Debug;
15 salcianu 1.1
16 salcianu 1.5 import harpoon.Util.Util;
17 salcianu 1.5
18 salcianu 1.1 import java.util.Map;
19 salcianu 1.1 import java.util.HashMap;
20 salcianu 1.1 import java.util.Iterator;
21 salcianu 1.1 import java.util.Set;
22 salcianu 1.1 import java.util.Collection;
23 salcianu 1.1 import java.util.Arrays;
24 salcianu 1.1 import java.util.List;
25 salcianu 1.1 import java.util.LinkedList;
26 salcianu 1.1 import java.util.Collection;
27 salcianu 1.1
28 salcianu 1.1 import java.io.BufferedReader;
29 salcianu 1.1 import java.io.FileReader;
30 salcianu 1.1 import java.io.IOException;
31 salcianu 1.1 import java.io.PrintWriter;
32 salcianu 1.1
33 salcianu 1.1 /**
34 salcianu 1.1 * <code>AllocationStatistics</code> reads the output produced by the
35 salcianu 1.1 * allocation instrumentation and offers support for gathering and
36 salcianu 1.1 * displaying statistics about the number of times each allocation
37 salcianu 1.1 * site from an instrumented program was executed.
38 salcianu 1.1 *
39 salcianu 1.1 * @author Alexandru Salcianu <salcianu@MIT.EDU>
40 cananian 1.7 * @version $Id: AllocationStatistics.java,v 1.7 2004/02/08 03:21:32 cananian Exp $
41 salcianu 1.1 * @see InstrumentAllocs
42 salcianu 1.1 */
43 salcianu 1.1 public class AllocationStatistics {
44 salcianu 1.2
45 salcianu 1.2 /** Create an <code>AllocationStatistics</code> object.
46 salcianu 1.2
47 salcianu 1.2 @param ani <code>AllocationNumberingInterf</code> object that
48 salcianu 1.2 provides the mapping between allocation sites and globally
49 salcianu 1.2 unique integer IDs.
50 salcianu 1.2
51 salcianu 1.2 @param instrumentationResultFileName name of the file that
52 salcianu 1.2 holds the result of the instrumentation: for each unique ID,
53 salcianu 1.2 the number of times the associated allocation site was
54 salcianu 1.3 executed and the total amount of memory allocated there. */
55 salcianu 1.2 public AllocationStatistics(AllocationNumberingInterf ani,
56 salcianu 1.2 String instrumentationResultsFileName) {
57 salcianu 1.2 try {
58 salcianu 1.2 this.ani = ani;
59 salcianu 1.3 this.allocID2data =
60 salcianu 1.2 parseInstrumentationResults(instrumentationResultsFileName);
61 salcianu 1.2 }
62 salcianu 1.2 catch(IOException e) {
63 salcianu 1.2 System.err.println("Cannot create AllocStatistics: " + e);
64 salcianu 1.2 System.exit(1);
65 salcianu 1.2 }
66 salcianu 1.2 }
67 salcianu 1.2
68 salcianu 1.2
69 salcianu 1.2 /** Create a <code>AllocationStatistics</code>.
70 salcianu 1.2
71 salcianu 1.3 @param linker <code>Linker</code> used to load the classes.
72 salcianu 1.3
73 salcianu 1.3 @param allocNumberingFileName name of the file that stores the
74 salcianu 1.3 textualized form of the <code>AllocationNumberingStub</code>
75 salcianu 1.3 (that associates to each allocation site a unique integer ID).
76 salcianu 1.3
77 salcianu 1.3 @param instrumentationResultFileName name of the file that
78 salcianu 1.3 holds the result of the instrumentation: for each unique ID,
79 salcianu 1.3 the number of times the associated allocation site was
80 salcianu 1.3 executed. */
81 salcianu 1.1 public AllocationStatistics(Linker linker,
82 salcianu 1.1 String allocNumberingFileName,
83 salcianu 1.1 String instrumentationResultsFileName) {
84 salcianu 1.1 try {
85 salcianu 1.2 this.ani =
86 salcianu 1.1 new AllocationNumberingStub(linker, allocNumberingFileName);
87 salcianu 1.3 this.allocID2data =
88 salcianu 1.2 parseInstrumentationResults(instrumentationResultsFileName);
89 salcianu 1.1 }
90 salcianu 1.1 catch(IOException e) {
91 salcianu 1.1 System.err.println("Cannot create AllocStatistics: " + e);
92 salcianu 1.1 System.exit(1);
93 salcianu 1.1 }
94 salcianu 1.1 }
95 salcianu 1.1
96 salcianu 1.3 /** data computed by the instrumentation */
97 salcianu 1.3 private static class AllocData {
98 salcianu 1.3 public AllocData(final long objCount, final long memAmount) {
99 salcianu 1.3 this.objCount = objCount;
100 salcianu 1.3 this.memAmount = memAmount;
101 salcianu 1.3 }
102 salcianu 1.3 public final long objCount;
103 salcianu 1.3 public final long memAmount;
104 salcianu 1.3 }
105 salcianu 1.3
106 salcianu 1.3
107 salcianu 1.1 // provides the map quad -> allocID (an integer)
108 salcianu 1.2 private AllocationNumberingInterf ani;
109 salcianu 1.1 // map allocID -> count
110 salcianu 1.3 private Map/*<Integer,AllocData>*/ allocID2data;
111 salcianu 1.1
112 salcianu 1.1
113 salcianu 1.6 /** Returns the number of times the allocation <code>alloc</code>
114 salcianu 1.1 was executed.
115 salcianu 1.1
116 salcianu 1.1 @param alloc allocation site
117 salcianu 1.1
118 salcianu 1.1 @return number of times <code>alloc</code> was executed */
119 salcianu 1.3 public long getCount(Quad alloc) {
120 salcianu 1.3 AllocData ad =
121 salcianu 1.3 (AllocData) allocID2data.get(new Integer(ani.allocID(alloc)));
122 salcianu 1.3 return (ad == null) ? 0 : ad.objCount;
123 salcianu 1.3 }
124 salcianu 1.3
125 salcianu 1.3
126 salcianu 1.6 /** Returns the total amount of memory allocated at the allocation
127 salcianu 1.3 <code>alloc</code>.
128 salcianu 1.3
129 salcianu 1.3 @param alloc allocation site
130 salcianu 1.3
131 salcianu 1.3 @return total amount of memory allocated at <code>alloc</code> */
132 salcianu 1.3 public long getMemAmount(Quad alloc) {
133 salcianu 1.3 AllocData ad =
134 salcianu 1.3 (AllocData) allocID2data.get(new Integer(ani.allocID(alloc)));
135 salcianu 1.3 return (ad == null) ? 0 : ad.memAmount;
136 salcianu 1.6 }
137 salcianu 1.6
138 salcianu 1.6
139 salcianu 1.6 /** Returns the unique ID for <code>alloc</code>. */
140 salcianu 1.6 public int allocID(Quad alloc) {
141 salcianu 1.6 return ani.allocID(alloc);
142 salcianu 1.1 }
143 salcianu 1.1
144 salcianu 1.1
145 salcianu 1.1 /** Prints statitistics about the allocation sites from the
146 salcianu 1.1 collection <code>allocs</code>. If <code>visitor</code> is
147 salcianu 1.1 non-null, it is called on each allocation site (this way, one
148 salcianu 1.1 can customize the displayed statistics). The allocation sites
149 salcianu 1.1 are listed/visited in the decreasing order of the number of
150 salcianu 1.1 objects allocated there. Sites that allocate too few objects
151 salcianu 1.2 (less than 1% of the total objects) are not considered. */
152 salcianu 1.1 public void printStatistics(Collection allocs, QuadVisitor visitor) {
153 salcianu 1.1
154 salcianu 1.1 class SiteStat implements Comparable {
155 salcianu 1.3 public final Quad allocSite;
156 salcianu 1.3 public final long allocCount;
157 salcianu 1.3 public final long memAmount;
158 salcianu 1.3 public SiteStat(Quad allocSite,
159 salcianu 1.3 long allocCount, long memAmount) {
160 salcianu 1.3 this.allocSite = allocSite;
161 salcianu 1.3 this.allocCount = allocCount;
162 salcianu 1.3 this.memAmount = memAmount;
163 salcianu 1.1 }
164 salcianu 1.1 public int compareTo(Object o) {
165 salcianu 1.1 if(! (o instanceof SiteStat)) return -1;
166 salcianu 1.1 SiteStat s2 = (SiteStat) o;
167 salcianu 1.3 if (allocCount < s2.allocCount) return +1;
168 salcianu 1.3 else if (allocCount > s2.allocCount) return -1;
169 salcianu 1.1 else return 0;
170 salcianu 1.1 }
171 salcianu 1.1 };
172 salcianu 1.1
173 salcianu 1.1 int ss_size = 0;
174 cananian 1.7 for(Object allocSiteO : allocs) {
175 cananian 1.7 Quad allocSite = (Quad) allocSiteO;
176 salcianu 1.3 if(getCount(allocSite) != 0) ss_size++;
177 salcianu 1.1 }
178 salcianu 1.1 SiteStat[] ss = new SiteStat[ss_size];
179 salcianu 1.1
180 salcianu 1.1 long total_count = 0;
181 salcianu 1.1 int i = 0;
182 cananian 1.7 for(Object allocSiteO : allocs) {
183 cananian 1.7 Quad allocSite = (Quad) allocSiteO;
184 salcianu 1.3 long allocCount = getCount(allocSite);
185 salcianu 1.3 if(allocCount != 0) {
186 salcianu 1.3 total_count += allocCount;
187 salcianu 1.3 ss[i++] = new SiteStat(allocSite, allocCount,
188 salcianu 1.3 getMemAmount(allocSite));
189 salcianu 1.1 }
190 salcianu 1.1 }
191 salcianu 1.1 Arrays.sort(ss);
192 salcianu 1.1
193 salcianu 1.1 long partial_count = 0;
194 salcianu 1.1 System.out.println("Allocation Statistics BEGIN");
195 salcianu 1.1 for(i = 0; i < ss.length; i++) {
196 salcianu 1.3 Quad site = ss[i].allocSite;
197 salcianu 1.3 long count = ss[i].allocCount;
198 salcianu 1.1 double frac = (count*100.0) / total_count;
199 salcianu 1.1 partial_count += count;
200 salcianu 1.1 System.out.println
201 salcianu 1.5 (Util.code2str(site) + "\n\t" +
202 salcianu 1.3 count + " object(s)\n\t" +
203 salcianu 1.3 ss[i].memAmount + " byte(s)\n\t" +
204 salcianu 1.5 Util.doubleRep(frac, 5, 2) + "% of all objects\n\t" +
205 salcianu 1.1 site.getFactory().getMethod());
206 salcianu 1.1 if(visitor != null)
207 salcianu 1.1 site.accept(visitor);
208 salcianu 1.1 if((frac < 1) || // don't print sites with < 1% allocations
209 salcianu 1.1 (((double) partial_count / (double) total_count) > 0.90)) {
210 salcianu 1.1 i++;
211 salcianu 1.1 break;
212 salcianu 1.1 }
213 salcianu 1.1 }
214 salcianu 1.1 System.out.println
215 salcianu 1.1 (i + ((i==1) ? " site allocates " : " sites allocate ") +
216 salcianu 1.5 Util.doubleRep((partial_count*100.0) / total_count, 5, 2) +
217 salcianu 1.1 "% of all objects");
218 salcianu 1.1 System.out.println("Allocation Statistics END");
219 salcianu 1.1 }
220 salcianu 1.1
221 salcianu 1.1
222 salcianu 1.1 public void printStatistics(Collection allocs) {
223 salcianu 1.1 printStatistics(allocs, null);
224 salcianu 1.1 }
225 salcianu 1.2
226 salcianu 1.2
227 salcianu 1.2 /** Parse the text file produced by an instrumented program.
228 salcianu 1.2
229 salcianu 1.2 @param instrumentationResultsFileName name of the file holding the
230 salcianu 1.2 instrumentation results
231 salcianu 1.2
232 salcianu 1.3 @return map that attaches to each unique ID the data collected
233 salcianu 1.3 by the instrumentation for the corresponding allocation
234 salcianu 1.3 site. */
235 salcianu 1.3 public static Map/*<Integer,AllocData>*/ parseInstrumentationResults
236 salcianu 1.2 (String instrumentationResultsFileName) throws IOException {
237 salcianu 1.2 BufferedReader br =
238 salcianu 1.2 new BufferedReader(new FileReader(instrumentationResultsFileName));
239 salcianu 1.3 Map/*<Integer, AllocData>*/ allocID2data = new HashMap();
240 salcianu 1.2 int size = readInt(br);
241 salcianu 1.2 for(int i = 0; i < size; i++) {
242 salcianu 1.3 long objCount = readLong(br);
243 salcianu 1.3 long memAmount = readLong(br);
244 salcianu 1.3 allocID2data.put
245 salcianu 1.3 (new Integer(i), new AllocData(objCount, memAmount));
246 salcianu 1.2 }
247 salcianu 1.3 return allocID2data;
248 salcianu 1.2 }
249 salcianu 1.2
250 salcianu 1.2
251 salcianu 1.2 private static int readInt(BufferedReader br) throws IOException {
252 salcianu 1.3 return Integer.parseInt(br.readLine());
253 salcianu 1.3 }
254 salcianu 1.3
255 salcianu 1.3 private static long readLong(BufferedReader br) throws IOException {
256 salcianu 1.3 return Long.parseLong(br.readLine());
257 salcianu 1.2 }
258 salcianu 1.2
259 salcianu 1.1
260 salcianu 1.1 /** Return a collection of all the allocation sites (quads) from
261 salcianu 1.1 the methods from the set <code>methods</code>.
262 salcianu 1.1
263 salcianu 1.1 @param methods methods where we look for allocation sites
264 salcianu 1.1 @param hcf code factory that provides the code of the methods
265 salcianu 1.1
266 salcianu 1.1 @return collection of all allocation sites (quads) from
267 salcianu 1.1 <code>methods</code> */
268 salcianu 1.1 public static Collection getAllocs(Set methods, HCodeFactory hcf) {
269 salcianu 1.1 List allocs = new LinkedList();
270 cananian 1.7 for(Object hmO : methods) {
271 cananian 1.7 HMethod hm = (HMethod) hmO;
272 salcianu 1.1 Code code = (Code) hcf.convert(hm);
273 salcianu 1.1 if(code != null)
274 salcianu 1.1 allocs.addAll(code.selectAllocations());
275 salcianu 1.1 }
276 salcianu 1.1 return allocs;
277 salcianu 1.1 }
278 salcianu 1.1 }