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 @Override
071 public synchronized void reset() {
072 callGraph.clear();
073 totalEdgeWeights = seedWeight;
074 }
075
076 /**
077 * @return sum of all edge weights in the partial call graph
078 */
079 public double getTotalEdgeWeights() { return totalEdgeWeights; }
080
081 /**
082 * Visit the WeightedCallTargets for every call site send them the
083 * decay message.
084 */
085 @Override
086 public synchronized void decay() {
087 double rate = Controller.options.DCG_DECAY_RATE;
088 // if we are dumping dynamic call graph, don't decay the graph
089 if (Controller.options.DYNAMIC_CALL_FILE_OUTPUT != null) return;
090
091 for (WeightedCallTargets ct : callGraph.values()) {
092 ct.decay(rate);
093 }
094 totalEdgeWeights /= rate;
095 }
096
097 /**
098 * @param caller caller method
099 * @param bcIndex bytecode index in caller method
100 * @return the WeightedCallTargets currently associated with the
101 * given caller bytecodeIndex pair.
102 */
103 public WeightedCallTargets getCallTargets(RVMMethod caller, int bcIndex) {
104 MethodReference callerRef = caller.getMemberRef().asMethodReference();
105 UnResolvedWeightedCallTargets unresolvedTargets =
106 unresolvedCallGraph.get(new UnResolvedCallSite(callerRef, bcIndex));
107 if (unresolvedTargets != null) {
108 final RVMMethod fCaller = caller;
109 final int fBcIndex = bcIndex;
110 final PartialCallGraph pg = this;
111 unresolvedTargets.visitTargets(new UnResolvedWeightedCallTargets.Visitor() {
112 @Override
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, 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 information 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 @Override
215 public synchronized void report() {
216 System.out.println("Partial Call Graph");
217 System.out.println(" Number of callsites " + callGraph.size() + ", total weight: " + totalEdgeWeights);
218 System.out.println();
219
220 TreeSet<CallSite> tmp = new TreeSet<CallSite>(new OrderByTotalWeight());
221 tmp.addAll(callGraph.keySet());
222
223 for (final CallSite cs : tmp) {
224 WeightedCallTargets ct = callGraph.get(cs);
225 ct.visitTargets(new WeightedCallTargets.Visitor() {
226 @Override
227 public void visit(RVMMethod callee, double weight) {
228 System.out.println(weight + " <" + cs.getMethod() + ", " + cs.getBytecodeIndex() + ", " + callee + ">");
229 }
230 });
231 System.out.println();
232 }
233 }
234
235 /**
236 * Dump all profile data to the given file
237 */
238 public synchronized void dumpGraph() {
239 dumpGraph(Controller.options.DYNAMIC_CALL_FILE_OUTPUT);
240 }
241
242 /**
243 * Dump all profile data to the given file
244 * @param fn output file name
245 */
246 public synchronized void dumpGraph(String fn) {
247 final BufferedWriter f;
248 try {
249 f = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fn), "ISO-8859-1"));
250 } catch (IOException e) {
251 VM.sysWrite("\n\nPartialCallGraph.dumpGraph: Error opening output file!!\n\n");
252 return;
253 }
254 TreeSet<CallSite> tmp = new TreeSet<CallSite>(new OrderByTotalWeight());
255 tmp.addAll(callGraph.keySet());
256
257 for (final CallSite cs : tmp) {
258 WeightedCallTargets ct = callGraph.get(cs);
259 ct.visitTargets(new WeightedCallTargets.Visitor() {
260 @Override
261 public void visit(RVMMethod callee, double weight) {
262 CodeArray callerArray = cs.getMethod().getCurrentEntryCodeArray();
263 CodeArray calleeArray = callee.getCurrentEntryCodeArray();
264 try {
265 f.write("CallSite " +
266 cs.getMethod().getMemberRef() +
267 " " +
268 callerArray.length() +
269 " " +
270 +cs.getBytecodeIndex() +
271 " " +
272 callee.getMemberRef() +
273 " " +
274 +calleeArray.length() +
275 " weight: " +
276 weight +
277 "\n");
278 f.flush();
279 } catch (IOException exc) {
280 System.err.println("I/O error writing to dynamic call graph profile.");
281 }
282 }
283 });
284 }
285 }
286
287 /**
288 * Used to compare two call sites by total weight.
289 */
290 private final class OrderByTotalWeight implements Comparator<CallSite> {
291 @Override
292 public int compare(CallSite o1, CallSite o2) {
293 if (o1.equals(o2)) return 0;
294 double w1 = callGraph.get(o1).totalWeight();
295 double w2 = callGraph.get(o2).totalWeight();
296 if (w1 < w2) { return 1; }
297 if (w1 > w2) { return -1; }
298 // equal weights; sort lexicographically
299 return o1.toString().compareTo(o2.toString());
300 }
301 }
302
303 }