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 */
013package org.jikesrvm.adaptive.measurements.organizers;
014
015import org.jikesrvm.VM;
016import org.jikesrvm.adaptive.controller.Controller;
017import org.jikesrvm.adaptive.measurements.RuntimeMeasurements;
018import org.jikesrvm.adaptive.measurements.listeners.EdgeListener;
019import org.jikesrvm.classloader.RVMMethod;
020import org.jikesrvm.compilers.baseline.BaselineCompiledMethod;
021import org.jikesrvm.compilers.common.CompiledMethod;
022import org.jikesrvm.compilers.common.CompiledMethods;
023import org.jikesrvm.compilers.opt.OptimizingCompilerException;
024import org.jikesrvm.compilers.opt.runtimesupport.OptCompiledMethod;
025import org.jikesrvm.compilers.opt.runtimesupport.OptMachineCodeMap;
026import org.jikesrvm.scheduler.RVMThread;
027import org.jikesrvm.runtime.Magic;
028import org.vmmagic.unboxed.Offset;
029import 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
057public 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