001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.adaptive.database.callgraph;
014
015 import java.io.BufferedWriter;
016 import java.io.FileOutputStream;
017 import java.io.IOException;
018 import java.io.OutputStreamWriter;
019 import java.util.Comparator;
020 import java.util.HashMap;
021 import java.util.TreeSet;
022 import org.jikesrvm.ArchitectureSpecific.CodeArray;
023 import org.jikesrvm.VM;
024 import org.jikesrvm.adaptive.controller.Controller;
025 import org.jikesrvm.adaptive.measurements.Decayable;
026 import org.jikesrvm.adaptive.measurements.Reportable;
027 import org.jikesrvm.adaptive.util.UnResolvedCallSite;
028 import org.jikesrvm.adaptive.util.UnResolvedWeightedCallTargets;
029 import org.jikesrvm.classloader.RVMMethod;
030 import org.jikesrvm.classloader.MethodReference;
031
032 /**
033 * A partial call graph (PCG) is a partial mapping from callsites
034 * to weighted targets.
035 */
036 public final class PartialCallGraph implements Decayable, Reportable {
037
038 /**
039 * The dynamic call graph, which is a mapping from
040 * CallSites to WeightedCallTargets.
041 */
042 private final HashMap<CallSite, WeightedCallTargets> callGraph =
043 new HashMap<CallSite, WeightedCallTargets>();
044 private final HashMap<UnResolvedCallSite, UnResolvedWeightedCallTargets> unresolvedCallGraph =
045 new HashMap<UnResolvedCallSite, UnResolvedWeightedCallTargets>();
046
047 /**
048 * sum of all edge weights in the call graph
049 */
050 private double totalEdgeWeights;
051
052 /**
053 * Initial seed weight; saved for use in the reset method
054 */
055 private final double seedWeight;
056
057 /**
058 * Create a partial call graph.
059 * @param initialWeight an initial value for totalEdgeWeights.
060 * Used by AOS to cause inlining based in the dynamic call graph
061 * to initially be conservative until sufficient samples have
062 * accumulated that there is more confidence in the accuracy
063 * of the call graph.
064 */
065 public PartialCallGraph(double initialWeight) {
066 seedWeight = initialWeight; // save for rest function
067 totalEdgeWeights = initialWeight;
068 }
069
070 /**
071 * Reset data
072 */
073 public synchronized void reset() {
074 callGraph.clear();
075 totalEdgeWeights = seedWeight;
076 }
077
078 /**
079 * @return sum of all edge weights in the partial call graph
080 */
081 public double getTotalEdgeWeights() { return totalEdgeWeights; }
082
083 /**
084 * Visit the WeightedCallTargets for every call site send them the
085 * decay message.
086 */
087 public synchronized void decay() {
088 double rate = Controller.options.DCG_DECAY_RATE;
089 // if we are dumping dynamic call graph, don't decay the graph
090 if (Controller.options.DYNAMIC_CALL_FILE_OUTPUT != null) return;
091
092 for (WeightedCallTargets ct : callGraph.values()) {
093 ct.decay(rate);
094 }
095 totalEdgeWeights /= rate;
096 }
097
098 /**
099 * @param caller caller method
100 * @param bcIndex bytecode index in caller method
101 * @return the WeightedCallTargets currently associated with the
102 * given caller bytecodeIndex pair.
103 */
104 public WeightedCallTargets getCallTargets(RVMMethod caller, int bcIndex) {
105 MethodReference callerRef = caller.getMemberRef().asMethodReference();
106 UnResolvedWeightedCallTargets unresolvedTargets =
107 unresolvedCallGraph.get(new UnResolvedCallSite(callerRef, bcIndex));
108 if (unresolvedTargets != null) {
109 final RVMMethod fCaller = caller;
110 final int fBcIndex = bcIndex;
111 final PartialCallGraph pg = this;
112 unresolvedTargets.visitTargets(new UnResolvedWeightedCallTargets.Visitor() {
113 public void visit(MethodReference calleeRef, double weight) {
114 RVMMethod callee = calleeRef.getResolvedMember();
115 if (callee != null) {
116 pg.incrementEdge(fCaller, fBcIndex, callee, (float) weight);
117 }
118 }
119 });
120 }
121 return getCallTargets(new CallSite(caller, bcIndex));
122 }
123
124 /**
125 * @param callSite the callsite to look for
126 * @return the WeightedCallTargets currently associated with callSite.
127 */
128 public synchronized WeightedCallTargets getCallTargets(CallSite callSite) {
129 return callGraph.get(callSite);
130 }
131
132 /**
133 * Increment the edge represented by the input parameters,
134 * creating it if it is not already in the call graph.
135 *
136 * @param caller method making the call
137 * @param bcIndex call site, if -1 then no call site is specified.
138 * @param callee method called
139 */
140 public synchronized void incrementEdge(RVMMethod caller, int bcIndex, RVMMethod callee) {
141 augmentEdge(caller, bcIndex, callee, 1);
142 }
143
144 /**
145 * Increment the edge represented by the input parameters,
146 * creating it if it is not already in the call graph.
147 *
148 * @param caller method making the call
149 * @param bcIndex call site, if -1 then no call site is specified.
150 * @param callee method called
151 * @param weight the frequency of this calling edge
152 */
153 public synchronized void incrementEdge(RVMMethod caller, int bcIndex, RVMMethod callee, float weight) {
154 augmentEdge(caller, bcIndex, callee, (double) weight);
155 }
156
157 /**
158 * For the calling edge we read from a profile, we may not have
159 * the methods loaded in yet. Therefore, we will record the method
160 * reference infomation first, the next time we resolved the method,
161 * we will promote it into the regular call graph.
162 * Increment the edge represented by the input parameters,
163 * creating it if it is not already in the call graph.
164 *
165 * @param callerRef method making the call
166 * @param bcIndex call site, if -1 then no call site is specified.
167 * @param calleeRef method called
168 * @param weight the frequency of this calling edge
169 */
170 public synchronized void incrementUnResolvedEdge(MethodReference callerRef, int bcIndex,
171 MethodReference calleeRef, float weight) {
172 UnResolvedCallSite callSite = new UnResolvedCallSite(callerRef, bcIndex);
173 UnResolvedWeightedCallTargets targets = unresolvedCallGraph.get(callSite);
174 if (targets == null) {
175 targets = UnResolvedWeightedCallTargets.create(calleeRef, weight);
176 unresolvedCallGraph.put(callSite, targets);
177 } else {
178 UnResolvedWeightedCallTargets orig = targets;
179 targets = targets.augmentCount(calleeRef, weight);
180 if (orig != targets) {
181 unresolvedCallGraph.put(callSite, targets);
182 }
183 }
184 }
185
186 /**
187 * Increment the edge represented by the input parameters,
188 * creating it if it is not already in the call graph.
189 *
190 * @param caller method making the call
191 * @param bcIndex call site, if -1 then no call site is specified.
192 * @param callee method called
193 * @param weight the frequency of this calling edge
194 */
195 private void augmentEdge(RVMMethod caller, int bcIndex, RVMMethod callee, double weight) {
196 CallSite callSite = new CallSite(caller, bcIndex);
197 WeightedCallTargets targets = callGraph.get(callSite);
198 if (targets == null) {
199 targets = WeightedCallTargets.create(callee, weight);
200 callGraph.put(callSite, targets);
201 } else {
202 WeightedCallTargets orig = targets;
203 targets = targets.augmentCount(callee, weight);
204 if (orig != targets) {
205 callGraph.put(callSite, targets);
206 }
207 }
208 totalEdgeWeights += weight;
209 }
210
211 /**
212 * Dump out set of edges in sorted order.
213 */
214 public synchronized void report() {
215 System.out.println("Partial Call Graph");
216 System.out.println(" Number of callsites " + callGraph.size() + ", total weight: " + totalEdgeWeights);
217 System.out.println();
218
219 TreeSet<CallSite> tmp = new TreeSet<CallSite>(new OrderByTotalWeight());
220 tmp.addAll(callGraph.keySet());
221
222 for (final CallSite cs : tmp) {
223 WeightedCallTargets ct = callGraph.get(cs);
224 ct.visitTargets(new WeightedCallTargets.Visitor() {
225 public void visit(RVMMethod callee, double weight) {
226 System.out.println(weight + " <" + cs.getMethod() + ", " + cs.getBytecodeIndex() + ", " + callee + ">");
227 }
228 });
229 System.out.println();
230 }
231 }
232
233 /**
234 * Dump all profile data to the given file
235 */
236 public synchronized void dumpGraph() {
237 dumpGraph(Controller.options.DYNAMIC_CALL_FILE_OUTPUT);
238 }
239
240 /**
241 * Dump all profile data to the given file
242 * @param fn output file name
243 */
244 public synchronized void dumpGraph(String fn) {
245 final BufferedWriter f;
246 try {
247 f = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fn), "ISO-8859-1"));
248 } catch (IOException e) {
249 VM.sysWrite("\n\nPartialCallGraph.dumpGraph: Error opening output file!!\n\n");
250 return;
251 }
252 TreeSet<CallSite> tmp = new TreeSet<CallSite>(new OrderByTotalWeight());
253 tmp.addAll(callGraph.keySet());
254
255 for (final CallSite cs : tmp) {
256 WeightedCallTargets ct = callGraph.get(cs);
257 ct.visitTargets(new WeightedCallTargets.Visitor() {
258 public void visit(RVMMethod callee, double weight) {
259 CodeArray callerArray = cs.getMethod().getCurrentEntryCodeArray();
260 CodeArray calleeArray = callee.getCurrentEntryCodeArray();
261 try {
262 f.write("CallSite " +
263 cs.getMethod().getMemberRef() +
264 " " +
265 callerArray.length() +
266 " " +
267 +cs.getBytecodeIndex() +
268 " " +
269 callee.getMemberRef() +
270 " " +
271 +calleeArray.length() +
272 " weight: " +
273 weight +
274 "\n");
275 f.flush();
276 } catch (IOException exc) {
277 System.err.println("I/O error writing to dynamic call graph profile.");
278 }
279 }
280 });
281 }
282 }
283
284 /**
285 * Used to compare two call sites by total weight.
286 */
287 private final class OrderByTotalWeight implements Comparator<CallSite> {
288 public int compare(CallSite o1, CallSite o2) {
289 if (o1.equals(o2)) return 0;
290 double w1 = callGraph.get(o1).totalWeight();
291 double w2 = callGraph.get(o2).totalWeight();
292 if (w1 < w2) { return 1; }
293 if (w1 > w2) { return -1; }
294 // equal weights; sort lexicographically
295 return o1.toString().compareTo(o2.toString());
296 }
297 }
298
299 }