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.<p>
064 * The buffer contains an array of triples {@code <callee, caller, address>} where
065 * the caller and callee are CompiledMethodID's, and address identifies
066 * the call site.
067 * The edge listener adds triples.
068 * At some point the listener deregisters itself and notifies the organizer
069 * by calling thresholdReached().
070 */
071 private int[] buffer;
072 /** the buffer's size, i.e. length of {@link #buffer} */
073 private int bufferSize;
074 /** the maximum number of triples contained in buffer */
075 private int numberOfBufferTriples;
076
077 /**
078 * Countdown of times we have to have called thresholdReached before
079 * we believe the call graph has enough samples that it is reasonable
080 * to use it to guide profile-directed inlining. When this value reaches 0,
081 * we stop decrementing it and start letting other parts of the adaptive
082 * system use the profile data.
083 */
084 private int thresholdReachedCount;
085
086 /**
087 * Constructs a new dynamic call graph organizer that will get its data from the given edge listener.
088 * @param edgeListener the listener that provides data for this organizer
089 */
090 public DynamicCallGraphOrganizer(EdgeListener edgeListener) {
091 listener = edgeListener;
092 edgeListener.setOrganizer(this);
093 }
094
095 /**
096 * Initialization: set up data structures and sampling objects.
097 * <p>
098 * Uses either timer based sampling or counter based sampling,
099 * depending on {@link Controller#options}.
100 */
101 @Override
102 public void initialize() {
103 if (Controller.options.cgCBS()) {
104 numberOfBufferTriples = Controller.options.DCG_SAMPLE_SIZE * VM.CBSCallSamplesPerTick;
105 } else {
106 numberOfBufferTriples = Controller.options.DCG_SAMPLE_SIZE;
107 }
108 numberOfBufferTriples *= RVMThread.availableProcessors;
109 bufferSize = numberOfBufferTriples * 3;
110 buffer = new int[bufferSize];
111
112 ((EdgeListener) listener).setBuffer(buffer);
113
114 /* We're looking for a thresholdReachedCount such that when we reach the count,
115 * a single sample contributes less than the AI_HOT_CALLSITE_THRESHOLD. In other words, we
116 * want the inequality
117 * thresholdReachedCount * samplesPerInvocationOfThresholdReached > 1 / AI_HOT_CALLSITE_THRESHOLD
118 * to be true.
119 */
120 thresholdReachedCount = (int)Math.ceil(1.0 /(numberOfBufferTriples * Controller.options.INLINE_AI_HOT_CALLSITE_THRESHOLD));;
121
122 // Install the edge listener
123 if (Controller.options.cgTimer()) {
124 RuntimeMeasurements.installTimerContextListener((EdgeListener) listener);
125 } else if (Controller.options.cgCBS()) {
126 RuntimeMeasurements.installCBSContextListener((EdgeListener) listener);
127 } else {
128 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED, "Unexpected value of call_graph_listener_trigger");
129 }
130 }
131
132 /**
133 * Process contents of buffer:
134 * add call graph edges and increment their weights.
135 */
136 @Override
137 void thresholdReached() {
138 if (DEBUG) VM.sysWriteln("DCG_Organizer.thresholdReached()");
139
140 for (int i = 0; i < bufferSize; i = i + 3) {
141 int calleeCMID=0;
142 // FIXME: This is necessary but hacky and may not even be correct.
143 while (calleeCMID == 0) {
144 calleeCMID = buffer[i + 0];
145 }
146 Magic.isync();
147 CompiledMethod compiledMethod = CompiledMethods.getCompiledMethod(calleeCMID);
148 if (compiledMethod == null) continue;
149 RVMMethod callee = compiledMethod.getMethod();
150 if (callee.isRuntimeServiceMethod()) {
151 if (DEBUG) VM.sysWrite("Skipping sample with runtime service callee");
152 continue;
153 }
154 int callerCMID = buffer[i + 1];
155 compiledMethod = CompiledMethods.getCompiledMethod(callerCMID);
156 if (compiledMethod == null) continue;
157 RVMMethod stackFrameCaller = compiledMethod.getMethod();
158
159 int MCOff = buffer[i + 2];
160 Offset MCOffset = Offset.fromIntSignExtend(buffer[i + 2]);
161 int bytecodeIndex = -1;
162 RVMMethod caller = null;
163
164 switch (compiledMethod.getCompilerType()) {
165 case CompiledMethod.TRAP:
166 case CompiledMethod.JNI:
167 if (DEBUG) VM.sysWrite("Skipping sample with TRAP/JNI caller");
168 continue;
169 case CompiledMethod.BASELINE: {
170 BaselineCompiledMethod baseCompiledMethod = (BaselineCompiledMethod) compiledMethod;
171 // note: the following call expects the offset in INSTRUCTIONS!
172 bytecodeIndex = baseCompiledMethod.findBytecodeIndexForInstruction(MCOffset);
173 caller = stackFrameCaller;
174 }
175 break;
176 case CompiledMethod.OPT: {
177 OptCompiledMethod optCompiledMethod = (OptCompiledMethod) compiledMethod;
178 OptMachineCodeMap mc_map = optCompiledMethod.getMCMap();
179 try {
180 bytecodeIndex = mc_map.getBytecodeIndexForMCOffset(MCOffset);
181 if (bytecodeIndex == -1) {
182 // this can happen we we sample a call
183 // to a runtimeSerivce routine.
184 // We aren't setup to inline such methods anyways,
185 // so skip the sample.
186 if (DEBUG) {
187 VM.sysWrite(" *** SKIP SAMPLE ", stackFrameCaller.toString());
188 VM.sysWrite("@", compiledMethod.toString());
189 VM.sysWrite(" at MC offset ", MCOff);
190 VM.sysWrite(" calling ", callee.toString());
191 VM.sysWriteln(" due to invalid bytecodeIndex");
192 }
193 continue; // skip sample.
194 }
195 } catch (java.lang.ArrayIndexOutOfBoundsException e) {
196 VM.sysWrite(" ***ERROR: getBytecodeIndexForMCOffset(", MCOffset);
197 VM.sysWrite(") ArrayIndexOutOfBounds!\n");
198 e.printStackTrace();
199 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
200 caller = stackFrameCaller;
201 continue; // skip sample
202 } catch (OptimizingCompilerException e) {
203 VM.sysWrite("***Error: SKIP SAMPLE: can't find bytecode index in OPT compiled " +
204 stackFrameCaller +
205 "@" +
206 compiledMethod +
207 " at MC offset ", MCOff);
208 VM.sysWrite("!\n");
209 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
210 continue; // skip sample
211 }
212
213 try {
214 caller = mc_map.getMethodForMCOffset(MCOffset);
215 } catch (java.lang.ArrayIndexOutOfBoundsException e) {
216 VM.sysWrite(" ***ERROR: getMethodForMCOffset(", MCOffset);
217 VM.sysWrite(") ArrayIndexOutOfBounds!\n");
218 e.printStackTrace();
219 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
220 caller = stackFrameCaller;
221 continue;
222 } catch (OptimizingCompilerException e) {
223 VM.sysWrite("***Error: SKIP SAMPLE: can't find caller in OPT compiled " +
224 stackFrameCaller +
225 "@" +
226 compiledMethod +
227 " at MC offset ", MCOff);
228 VM.sysWrite("!\n");
229 if (VM.ErrorsFatal) VM.sysFail("Exception in AI organizer.");
230 continue; // skip sample
231 }
232
233 if (caller == null) {
234 VM.sysWrite(" ***ERROR: getMethodForMCOffset(", MCOffset);
235 VM.sysWrite(") returned null!\n");
236 caller = stackFrameCaller;
237 continue; // skip sample
238 }
239 }
240 break;
241 }
242
243 // increment the call graph edge, adding it if needed
244 Controller.dcg.incrementEdge(caller, bytecodeIndex, callee);
245 }
246 if (thresholdReachedCount > 0) {
247 thresholdReachedCount--;
248 }
249 }
250
251 /**
252 * Checks if the dynamic call graph organizer has gathered and processed enough samples to support decisions.
253 * @return {@code true} if enough data is available, {@code false} otherwise
254 */
255 public boolean someDataAvailable() {
256 return thresholdReachedCount == 0;
257 }
258 }
259