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.measurements.organizers;
014
015 import org.jikesrvm.VM;
016 import org.jikesrvm.adaptive.controller.Controller;
017 import org.jikesrvm.adaptive.measurements.RuntimeMeasurements;
018 import org.jikesrvm.adaptive.measurements.listeners.EdgeListener;
019 import org.jikesrvm.classloader.RVMMethod;
020 import org.jikesrvm.compilers.baseline.BaselineCompiledMethod;
021 import org.jikesrvm.compilers.common.CompiledMethod;
022 import org.jikesrvm.compilers.common.CompiledMethods;
023 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
024 import org.jikesrvm.compilers.opt.runtimesupport.OptCompiledMethod;
025 import org.jikesrvm.compilers.opt.runtimesupport.OptMachineCodeMap;
026 import org.jikesrvm.scheduler.RVMThread;
027 import org.jikesrvm.runtime.Magic;
028 import org.vmmagic.unboxed.Offset;
029 import org.vmmagic.pragma.NonMoving;
030
031 /**
032 * An organizer to build a dynamic call graph from call graph edge
033 * samples.
034 * <p>
035 * It communicates with an edge listener through a
036 * integer array, denoted buffer. When this organizer is woken up
037 * via threshold reached, it processes the sequence of triples
038 * that are contained in buffer.
039 * <p>
040 * After processing the buffer and updating the dynamic call graph,
041 * it optionally notifies the AdaptiveInliningOrganizer who is responsible
042 * for analyzing the dynamic call graph for the purposes of
043 * feedback-directed inlining.
044 * <p>
045 * Note: Since this information is intended to drive feedback-directed inlining,
046 * the organizer drops edges that are not relevant. For example, one of
047 * the methods is a native method, or the callee is a runtime service
048 * routine and thus can't be inlined into its caller even if it is reported
049 * as hot. Thus, the call graph may not contain some hot edges since they
050 * aren't viable inlining candidates. One may argue that this is not the right
051 * design. Perhaps instead the edges should be present for profiling purposes,
052 * but not reported as inlining candidates to the
053 * <p>
054 * EXPECTATION: buffer is filled all the way up with triples.
055 */
056 @NonMoving
057 public class DynamicCallGraphOrganizer extends Organizer {
058
059 private static final boolean DEBUG = false;
060
061 /*
062 * buffer provides the communication channel between the edge listener
063 * and the organizer.
064 * The buffer contains an array of triples <callee, caller, address> where
065 * the caller and callee are CompiledMethodID's, and address identifies
066 * the call site.
067 * bufferSize is the number of triples contained in buffer.
068 * The edge listener adds triples.
069 * At some point the listener deregisters itself and notifies the organizer
070 * by calling thresholdReached().
071 */
072 private int[] buffer;
073 private int bufferSize;
074 private int numberOfBufferTriples;
075
076 /**
077 * Countdown of times we have to have called thresholdReached before
078 * we believe the call graph has enough samples that it is reasonable
079 * to use it to guide profile-directed inlining. When this value reaches 0,
080 * we stop decrementing it and start letting other parts of the adaptive
081 * system use the profile data.
082 */
083 private int thresholdReachedCount;
084
085 /**
086 * Constructor
087 */
088 public DynamicCallGraphOrganizer(EdgeListener edgeListener) {
089 listener = edgeListener;
090 edgeListener.setOrganizer(this);
091 makeDaemon(true);
092 }
093
094 /**
095 * Initialization: set up data structures and sampling objects.
096 */
097 @Override
098 public void initialize() {
099 if (Controller.options.cgCBS()) {
100 numberOfBufferTriples = Controller.options.DCG_SAMPLE_SIZE * VM.CBSCallSamplesPerTick;
101 } else {
102 numberOfBufferTriples = Controller.options.DCG_SAMPLE_SIZE;
103 }
104 numberOfBufferTriples *= RVMThread.numProcessors;
105 bufferSize = numberOfBufferTriples * 3;
106 buffer = new int[bufferSize];
107
108 ((EdgeListener) listener).setBuffer(buffer);
109
110 /* We're looking for a thresholdReachedCount such that when we reach the count,
111 * a single sample contributes less than the AI_HOT_CALLSITE_THRESHOLD. In other words, we
112 * want the inequality
113 * thresholdReachedCount * samplesPerInvocationOfThresholdReached > 1 / AI_HOT_CALLSITE_THRESHOLD
114 * to be true.
115 */
116 thresholdReachedCount = (int)Math.ceil(1.0 /(numberOfBufferTriples * Controller.options.INLINE_AI_HOT_CALLSITE_THRESHOLD));;
117
118 // Install the edge listener
119 if (Controller.options.cgTimer()) {
120 RuntimeMeasurements.installTimerContextListener((EdgeListener) listener);
121 } else if (Controller.options.cgCBS()) {
122 RuntimeMeasurements.installCBSContextListener((EdgeListener) listener);
123 } else {
124 if (VM.VerifyAssertions) VM._assert(false, "Unexpected value of call_graph_listener_trigger");
125 }
126 }
127
128 /**
129 * Method that is called when the sampling threshold is reached.
130 * Process contents of buffer:
131 * add call graph edges and increment their weights.
132 */
133 void thresholdReached() {
134 if (DEBUG) VM.sysWriteln("DCG_Organizer.thresholdReached()");
135
136 for (int i = 0; i < bufferSize; i = i + 3) {
137 int calleeCMID=0;
138 // FIXME: This is necessary but hacky and may not even be correct.
139 while (calleeCMID == 0) {
140 calleeCMID = buffer[i + 0];
141 }
142 Magic.isync();
143 CompiledMethod compiledMethod = CompiledMethods.getCompiledMethod(calleeCMID);
144 if (compiledMethod == null) continue;
145 RVMMethod callee = compiledMethod.getMethod();
146 if (callee.isRuntimeServiceMethod()) {
147 if (DEBUG) VM.sysWrite("Skipping sample with runtime service callee");
148 continue;
149 }
150 int callerCMID = buffer[i + 1];
151 compiledMethod = CompiledMethods.getCompiledMethod(callerCMID);
152 if (compiledMethod == null) continue;
153 RVMMethod stackFrameCaller = compiledMethod.getMethod();
154
155 int MCOff = buffer[i + 2];
156 Offset MCOffset = Offset.fromIntSignExtend(buffer[i + 2]);
157 int bytecodeIndex = -1;
158 RVMMethod caller = null;
159
160 switch (compiledMethod.getCompilerType()) {
161 case CompiledMethod.TRAP:
162 case CompiledMethod.JNI:
163 if (DEBUG) VM.sysWrite("Skipping sample with TRAP/JNI caller");
164 continue;
165 case CompiledMethod.BASELINE: {
166 BaselineCompiledMethod baseCompiledMethod = (BaselineCompiledMethod) compiledMethod;
167 // note: the following call expects the offset in INSTRUCTIONS!
168 bytecodeIndex = baseCompiledMethod.findBytecodeIndexForInstruction(MCOffset);
169 caller = stackFrameCaller;
170 }
171 break;
172 case CompiledMethod.OPT: {
173 OptCompiledMethod optCompiledMethod = (OptCompiledMethod) compiledMethod;
174 OptMachineCodeMap mc_map = optCompiledMethod.getMCMap();
175 try {
176 bytecodeIndex = mc_map.getBytecodeIndexForMCOffset(MCOffset);
177 if (bytecodeIndex == -1) {
178 // this can happen we we sample a call
179 // to a runtimeSerivce routine.
180 // We aren't setup to inline such methods anyways,
181 // so skip the sample.
182 if (DEBUG) {
183 VM.sysWrite(" *** SKIP SAMPLE ", stackFrameCaller.toString());
184 VM.sysWrite("@", compiledMethod.toString());
185 VM.sysWrite(" at MC offset ", MCOff);
186 VM.sysWrite(" calling ", callee.toString());
187 VM.sysWriteln(" due to invalid bytecodeIndex");
188 }
189 continue; // skip sample.
190 }
191 } catch (java.lang.ArrayIndexOutOfBoundsException e) {
192 VM.sysWrite(" ***ERROR: getBytecodeIndexForMCOffset(", MCOffset);
193 VM.sysWrite(") ArrayIndexOutOfBounds!\n");
194 e.printStackTrace();
195 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
196 caller = stackFrameCaller;
197 continue; // skip sample
198 } catch (OptimizingCompilerException e) {
199 VM.sysWrite("***Error: SKIP SAMPLE: can't find bytecode index in OPT compiled " +
200 stackFrameCaller +
201 "@" +
202 compiledMethod +
203 " at MC offset ", MCOff);
204 VM.sysWrite("!\n");
205 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
206 continue; // skip sample
207 }
208
209 try {
210 caller = mc_map.getMethodForMCOffset(MCOffset);
211 } catch (java.lang.ArrayIndexOutOfBoundsException e) {
212 VM.sysWrite(" ***ERROR: getMethodForMCOffset(", MCOffset);
213 VM.sysWrite(") ArrayIndexOutOfBounds!\n");
214 e.printStackTrace();
215 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
216 caller = stackFrameCaller;
217 continue;
218 } catch (OptimizingCompilerException e) {
219 VM.sysWrite("***Error: SKIP SAMPLE: can't find caller in OPT compiled " +
220 stackFrameCaller +
221 "@" +
222 compiledMethod +
223 " at MC offset ", MCOff);
224 VM.sysWrite("!\n");
225 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
226 continue; // skip sample
227 }
228
229 if (caller == null) {
230 VM.sysWrite(" ***ERROR: getMethodForMCOffset(", MCOffset);
231 VM.sysWrite(") returned null!\n");
232 caller = stackFrameCaller;
233 continue; // skip sample
234 }
235 }
236 break;
237 }
238
239 // increment the call graph edge, adding it if needed
240 Controller.dcg.incrementEdge(caller, bytecodeIndex, callee);
241 }
242 if (thresholdReachedCount > 0) {
243 thresholdReachedCount--;
244 }
245 }
246
247 public boolean someDataAvailable() {
248 return thresholdReachedCount == 0;
249 }
250 }
251