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.compilers.opt.inlining;
014
015import java.util.ArrayList;
016import java.util.Iterator;
017
018import org.jikesrvm.VM;
019import org.jikesrvm.adaptive.controller.AdaptiveInlining;
020import org.jikesrvm.adaptive.controller.Controller;
021import org.jikesrvm.adaptive.database.callgraph.WeightedCallTargets;
022import org.jikesrvm.classloader.NormalMethod;
023import org.jikesrvm.classloader.RVMClass;
024import org.jikesrvm.classloader.RVMMethod;
025import org.jikesrvm.compilers.common.CompiledMethod;
026import org.jikesrvm.compilers.opt.OptOptions;
027import org.jikesrvm.compilers.opt.driver.OptimizingCompiler;
028import org.jikesrvm.compilers.opt.runtimesupport.OptCompiledMethod;
029import org.jikesrvm.objectmodel.ObjectModel;
030import org.jikesrvm.scheduler.RVMThread;
031
032/**
033 * The default inlining oracle used by the optimizing compiler.
034 * The basic strategy is as follows:
035 * <ol>
036 *  <li>Always inline trivial methods that can be inlined without a guard
037 *  <li>At O1 and greater use a mix of profile information and static heuristics
038 *      to inline larger methods and methods that require guards.
039 * </ol>
040 */
041public final class DefaultInlineOracle extends InlineTools implements InlineOracle {
042
043  @Override
044  public InlineDecision shouldInline(final CompilationState state) {
045    final OptOptions opts = state.getOptions();
046    final boolean verbose = opts.PRINT_DETAILED_INLINE_REPORT;
047    if (!opts.INLINE) {
048      return InlineDecision.NO("inlining not enabled");
049    }
050
051    final RVMMethod staticCallee = state.obtainTarget();
052    final NormalMethod rootMethod = state.getRootMethod();
053    final RVMMethod caller = state.getMethod();
054    final int bcIndex = state.getRealBytecodeIndex();
055
056    if (verbose) VM.sysWriteln("Begin inline decision for " + "<" + caller + "," + bcIndex + "," + staticCallee + ">");
057
058    // Stage 1: We definitely don't inline certain methods
059    if (!state.isInvokeInterface()) {
060      if (staticCallee.isNative()) {
061        if (verbose) VM.sysWriteln("\tNO: native method\n");
062        return InlineDecision.NO("native method");
063      }
064      if (hasNoInlinePragma(staticCallee, state)) {
065        if (verbose) VM.sysWriteln("\tNO: pragmaNoInline\n");
066        return InlineDecision.NO("pragmaNoInline");
067      }
068      // We need throwable constructors to have their own compiled method IDs
069      // to correctly elide stack frames when generating stack traces (see
070      // StackTrace).
071      if (// are we calling the throwable constructor?
072          staticCallee.isObjectInitializer() &&
073          (staticCallee.getDeclaringClass().getClassForType() == Throwable.class) &&
074          // and not from a throwable constructor
075          !(caller.isObjectInitializer() &&
076           (caller.getDeclaringClass().getClassForType() == Throwable.class))) {
077        if (verbose) VM.sysWriteln("\tNO: throwable constructor\n");
078        return InlineDecision.NO("throwable constructor");
079      }
080    }
081    // Stage 2: At all optimization levels we should attempt to inline
082    //          trivial methods. Even if the inline code is never executed,
083    //          inlining a trivial method is a no cost operation as the impact
084    //          on code size should be negligible and compile time usually is
085    //          reduced since we expect to eliminate the call instruction (or
086    //          at worse replace one call instruction with another one).
087    if (!state.isInvokeInterface() && !staticCallee.isAbstract()) {
088      // NB when the destination is known we will have refined the target so the
089      // above test passes
090      if (state.getHasPreciseTarget() || !needsGuard(staticCallee)) {
091        // call is guardless
092        int inlinedSizeEstimate = inlinedSizeEstimate((NormalMethod) staticCallee, state);
093        if (inlinedSizeEstimate < opts.INLINE_MAX_ALWAYS_INLINE_TARGET_SIZE) {
094          // inlining is desirable
095          if (!state.getSequence().containsMethod(staticCallee)) {
096            // not recursive
097            if (verbose) VM.sysWriteln("\tYES: trivial guardless inline\n");
098            return InlineDecision.YES(staticCallee, "trivial inline");
099          }
100        }
101        if (hasInlinePragma(staticCallee, state)) {
102          // inlining is desirable
103          if (!state.getSequence().containsMethod(staticCallee)) {
104            // not recursive
105            if (verbose) VM.sysWriteln("\tYES: pragma inline\n");
106            return InlineDecision.YES(staticCallee, "pragma inline");
107          }
108        }
109      }
110    }
111
112    if (opts.getOptLevel() == 0) {
113      // at opt level 0, trivial unguarded inlines are the only kind we consider
114      if (verbose) VM.sysWriteln("\tNO: only do trivial inlines at O0\n");
115      return InlineDecision.NO("Only do trivial inlines at O0");
116    }
117
118    if (rootMethod.inlinedSizeEstimate() > opts.INLINE_MASSIVE_METHOD_SIZE) {
119      // In massive methods, we do not do any additional inlining to
120      // avoid completely blowing out compile time by making a bad situation worse
121      if (verbose) VM.sysWriteln("\tNO: only do trivial inlines into massive methods\n");
122      return InlineDecision.NO("Root method is massive; no non-trivial inlines");
123    }
124
125    // Stage 3: Determine based on profile data and static information
126    //          what are the possible targets of this call.
127    WeightedCallTargets targets = null;
128    boolean purelyStatic = true;
129    if (Controller.dcg != null && Controller.options.ADAPTIVE_INLINING) {
130      targets = Controller.dcg.getCallTargets(caller, bcIndex);
131      if (targets != null) {
132        if (verbose) VM.sysWriteln("\tFound profile data");
133        purelyStatic = false;
134        WeightedCallTargets filteredTargets = targets.filter(staticCallee, state.getHasPreciseTarget());
135        if (targets != filteredTargets) {
136          if (verbose) VM.sysWriteln("\tProfiled callees filtered based on static information");
137          targets = filteredTargets;
138          if (targets == null) {
139            if (verbose) VM.sysWriteln("\tAfter filterting no profile data...");
140            // After filtering, no matching profile data, fall back to
141            // static information to avoid degradations
142            targets = WeightedCallTargets.create(staticCallee, 0);
143            purelyStatic = true;
144          }
145        }
146      }
147    }
148
149    // Critical section: must prevent class hierarchy from changing while
150    // we are inspecting it to determine how/whether to do the inline guard.
151    synchronized (RVMClass.classLoadListener) {
152
153      boolean guardOverrideOnStaticCallee = false;
154      if (targets == null) {
155        if (verbose) VM.sysWriteln("\tNo profile data");
156        // No profile information.
157        // Fake up "profile data" based on static information to
158        // be able to share all the decision making logic.
159        if (state.isInvokeInterface()) {
160          if (opts.INLINE_GUARDED_INTERFACES) {
161            RVMMethod singleImpl = InterfaceHierarchy.getUniqueImplementation(staticCallee);
162            if (singleImpl != null && hasBody(singleImpl)) {
163              if (verbose) {
164                VM.sysWriteln("\tFound a single implementation " +
165                              singleImpl +
166                              " of an interface method " +
167                              staticCallee);
168              }
169              targets = WeightedCallTargets.create(singleImpl, 0);
170              guardOverrideOnStaticCallee = true;
171            }
172          }
173        } else {
174          // invokestatic, invokevirtual, invokespecial
175          if (staticCallee.isAbstract()) {
176            // look for single non-abstract implementation of the abstract method
177            RVMClass klass = staticCallee.getDeclaringClass();
178            while (true) {
179              RVMClass[] subClasses = klass.getSubClasses();
180              if (subClasses.length != 1) break; // multiple subclasses => multiple targets
181              RVMMethod singleImpl =
182                  subClasses[0].findDeclaredMethod(staticCallee.getName(), staticCallee.getDescriptor());
183              if (singleImpl != null && !singleImpl.isAbstract()) {
184                // found something
185                if (verbose) VM.sysWriteln("\tsingle impl of abstract method");
186                targets = WeightedCallTargets.create(singleImpl, 0);
187                guardOverrideOnStaticCallee = true;
188                break;
189              }
190              klass = subClasses[0]; // keep crawling down the hierarchy
191            }
192          } else {
193            targets = WeightedCallTargets.create(staticCallee, 0);
194          }
195        }
196      }
197
198      // At this point targets is either null, or accurately represents what we
199      // think are the likely target(s) of the call site.
200      // This information may be either derived from profile information or
201      // from static heuristics. To the first approximation, we don't care which.
202      // If there is a precise target, then targets contains exactly that target method.
203      if (targets == null) return InlineDecision.NO("No potential targets identified");
204
205      // Stage 4: We have one or more targets.  Determine what if anything should be done with them.
206      final ArrayList<RVMMethod> methodsToInline = new ArrayList<RVMMethod>();
207      final ArrayList<Boolean> methodsNeedGuard = new ArrayList<Boolean>();
208      final double callSiteWeight = targets.totalWeight();
209      final boolean goosc = guardOverrideOnStaticCallee; // real closures anyone?
210      final boolean ps = purelyStatic;                   // real closures anyone?
211      targets.visitTargets(new WeightedCallTargets.Visitor() {
212        @Override
213        public void visit(RVMMethod callee, double weight) {
214          if (hasBody(callee)) {
215            if (verbose) {
216              VM.sysWriteln("\tEvaluating target " +
217                            callee +
218                            " with " +
219                            weight +
220                            " samples (" +
221                            (100 * AdaptiveInlining.adjustedWeight(weight)) +
222                            "%)");
223            }
224            // Don't inline recursively and respect no inline pragmas
225            InlineSequence seq = state.getSequence();
226            if (seq.containsMethod(callee)) {
227              if (verbose) VM.sysWriteln("\t\tReject: recursive");
228              return;
229            }
230            if (hasNoInlinePragma(callee, state)) {
231              if (verbose) VM.sysWriteln("\t\tReject: noinline pragma");
232              return;
233            }
234
235            // more or less figure out the guard situation early -- impacts size estimate.
236            boolean needsGuard = !state.getHasPreciseTarget() && (staticCallee != callee || needsGuard(staticCallee));
237            if (needsGuard && isForbiddenSpeculation(state.getRootMethod(), callee)) {
238              if (verbose) VM.sysWriteln("\t\tReject: forbidden speculation");
239              return;
240            }
241            boolean currentlyFinal =
242                (goosc || (staticCallee == callee)) && isCurrentlyFinal(callee, !opts.guardWithClassTest());
243            boolean preEx = needsGuard && state.getIsExtant() && opts.INLINE_PREEX && currentlyFinal;
244            if (needsGuard && !preEx) {
245              if (!opts.INLINE_GUARDED) {
246                if (verbose) VM.sysWriteln("\t\tReject: guarded inlining disabled");
247                return;
248              }
249              if (!currentlyFinal && ps) {
250                if (verbose) VM.sysWriteln("\t\tReject: multiple targets and no profile data");
251                return;
252              }
253            }
254
255            // Estimate cost of performing this inlining action.
256            // Includes cost of guard & off-branch call if they are going to be generated.
257            boolean decideYes = false;
258            if (hasInlinePragma(callee, state)) {
259              if (verbose) VM.sysWriteln("\t\tSelect: pragma inline");
260              decideYes = true;
261            } else {
262              // Preserve previous inlining decisions
263              // Not the best thing in the world due to phase shifts, but
264              // it does buy some degree of stability. So, it is probably the lesser
265              // of two evils.
266              CompiledMethod prev = state.getRootMethod().getCurrentCompiledMethod();
267              if (prev != null && prev.getCompilerType() == CompiledMethod.OPT) {
268                if (((OptCompiledMethod)prev).getMCMap().hasInlinedEdge(caller, bcIndex, callee)) {
269                  if (verbose) VM.sysWriteln("\t\tSelect: Previously inlined");
270                  decideYes = true;
271                }
272              }
273
274              if (!decideYes) {
275                int inlinedSizeEstimate = inlinedSizeEstimate((NormalMethod) callee, state);
276                int cost = inliningActionCost(inlinedSizeEstimate, needsGuard, preEx, opts);
277                int maxCost = opts.INLINE_MAX_TARGET_SIZE;
278
279                if (callSiteWeight > Controller.options.INLINE_AI_SEED_MULTIPLIER) {
280                  // real profile data with enough samples for us to trust it.
281                  // Use weight and shape of call site distribution to compute
282                  // a higher maxCost.
283                  double fractionOfSample = weight / callSiteWeight;
284                  if (needsGuard && fractionOfSample < opts.INLINE_AI_MIN_CALLSITE_FRACTION) {
285                    // This call accounts for less than INLINE_AI_MIN_CALLSITE_FRACTION
286                    // of the profiled targets at this call site.
287                    // It is highly unlikely to be profitable to inline it.
288                    if (verbose) VM.sysWriteln("\t\tReject: less than INLINE_AI_MIN_CALLSITE_FRACTION of distribution");
289                    maxCost = 0;
290                  } else {
291                    if (cost > maxCost) {
292                      /* We're going to increase the maximum callee size (maxCost) we're willing
293                       * to inline based on how "hot" (what % of the total weight in the
294                       * dynamic call graph) the edge is.
295                       */
296                      double adjustedWeight = AdaptiveInlining.adjustedWeight(weight);
297                      if (adjustedWeight > Controller.options.INLINE_AI_HOT_CALLSITE_THRESHOLD) {
298                        /* A truly hot edge; use the max allowable callee size */
299                        maxCost = opts.INLINE_AI_MAX_TARGET_SIZE;
300                      } else {
301                        /* A warm edge, we will use a value between the static default and the max allowable.
302                         * The code below simply does a linear interpolation between 2x static default
303                         * and max allowable.
304                         * Other alternatives would be to do a log interpolation or some other step function.
305                         */
306                        int range = opts.INLINE_AI_MAX_TARGET_SIZE - 2 * opts.INLINE_MAX_TARGET_SIZE;
307                        double slope = (range) / Controller.options.INLINE_AI_HOT_CALLSITE_THRESHOLD;
308                        int scaledAdj = (int) (slope * adjustedWeight);
309                        maxCost += opts.INLINE_MAX_TARGET_SIZE + scaledAdj;
310                      }
311                    }
312                  }
313                }
314
315                // Somewhat bogus, but if we get really deeply inlined we start backing off.
316                int curDepth = state.getInlineDepth();
317                if (curDepth > opts.INLINE_MAX_INLINE_DEPTH) {
318                  maxCost /= (curDepth - opts.INLINE_MAX_INLINE_DEPTH + 1);
319                }
320
321                decideYes = cost <= maxCost;
322                if (verbose) {
323                  if (decideYes) {
324                    VM.sysWriteln("\t\tAccept: cost of " + cost + " was below threshold " + maxCost);
325                  } else {
326                    VM.sysWriteln("\t\tReject: cost of " + cost + " was above threshold " + maxCost);
327                  }
328                }
329              }
330            }
331
332            if (decideYes) {
333              // Ok, we're going to inline it.
334              // Record that and also whether or not we think it needs a guard.
335              methodsToInline.add(callee);
336              if (preEx) {
337                ClassLoadingDependencyManager cldm = (ClassLoadingDependencyManager) RVMClass.classLoadListener;
338                if (ClassLoadingDependencyManager.TRACE || ClassLoadingDependencyManager.DEBUG) {
339                  cldm.report("PREEX_INLINE: Inlined " + callee + " into " + caller + "\n");
340                }
341                cldm.addNotOverriddenDependency(callee, state.getCompiledMethod());
342                if (goosc) {
343                  cldm.addNotOverriddenDependency(staticCallee, state.getCompiledMethod());
344                }
345                methodsNeedGuard.add(Boolean.FALSE);
346              } else {
347                methodsNeedGuard.add(needsGuard);
348              }
349            }
350          }
351        }
352      });
353
354      // Stage 5: Choose guards and package up the results in an InlineDecision object
355      if (methodsToInline.isEmpty()) {
356        InlineDecision d = InlineDecision.NO("No desirable targets");
357        if (verbose) VM.sysWriteln("\tDecide: " + d);
358        return d;
359      } else if (methodsToInline.size() == 1) {
360        RVMMethod target = methodsToInline.get(0);
361        boolean needsGuard = methodsNeedGuard.get(0);
362        if (needsGuard) {
363          if ((guardOverrideOnStaticCallee || target == staticCallee) &&
364              isCurrentlyFinal(target, !opts.guardWithClassTest())) {
365            InlineDecision d =
366              InlineDecision.guardedYES(target,
367                  chooseGuard(caller, target, staticCallee, state, true),
368                  "Guarded inline of single static target");
369            /*
370             * Determine if it is allowable to put an OSR point in the failed case of
371             * the guarded inline instead of generating a real call instruction.
372             * There are several conditions that must be met for this to be allowable:
373             *   (1) OSR guarded inlining and recompilation must both be enabled
374             *   (2) The current context must be an interruptible method
375             *   (3) The application must be started.  This is a rough proxy for the VM
376             *       being fully booted so we can actually get through the OSR process.
377             *       Note: One implication of this requirement is that we will
378             *       never put an OSR on an off-branch of a guarded inline in bootimage
379             *       code.
380             */
381            if (opts.OSR_GUARDED_INLINING && Controller.options.ENABLE_RECOMPILATION &&
382                caller.isInterruptible() &&
383                OptimizingCompiler.getAppStarted()) {
384                if (VM.VerifyAssertions) VM._assert(VM.runningVM);
385                d.setOSRTestFailed();
386            }
387            if (verbose) VM.sysWriteln("\tDecide: " + d);
388            return d;
389          } else {
390            InlineDecision d =
391              InlineDecision.guardedYES(target,
392                  chooseGuard(caller, target, staticCallee, state, false),
393                  "Guarded inlining of one potential target");
394            if (verbose) VM.sysWriteln("\tDecide: " + d);
395            return d;
396          }
397        } else {
398          InlineDecision d = InlineDecision.YES(target, "Unique and desirable target");
399          if (verbose) VM.sysWriteln("\tDecide: " + d);
400          return d;
401        }
402      } else {
403        RVMMethod[] methods = new RVMMethod[methodsNeedGuard.size()];
404        byte[] guards = new byte[methods.length];
405        int idx = 0;
406        Iterator<RVMMethod> methodIterator = methodsToInline.iterator();
407        Iterator<Boolean> guardIterator = methodsNeedGuard.iterator();
408        while (methodIterator.hasNext()) {
409          RVMMethod target = methodIterator.next();
410          boolean needsGuard = guardIterator.next();
411          if (VM.VerifyAssertions) {
412            if (!needsGuard) {
413              VM.sysWriteln("Error, inlining for " + methodsToInline.size() + " targets");
414              VM.sysWriteln("Inlining into " + rootMethod + " at bytecode index " + bcIndex);
415              VM.sysWriteln("Method: " + target + " doesn't need a guard");
416              for (int i = 0; i < methodsToInline.size(); i++) {
417                VM.sysWriteln("  Method " + i + ": " + methodsToInline.get(i));
418                VM.sysWriteln("  NeedsGuard: " + methodsNeedGuard.get(i));
419              }
420              VM._assert(VM.NOT_REACHED);
421            }
422          }
423          methods[idx] = target;
424          guards[idx] = chooseGuard(caller, target, staticCallee, state, false);
425          idx++;
426        }
427        InlineDecision d = InlineDecision.guardedYES(methods, guards, "Inline multiple targets");
428        if (verbose) VM.sysWriteln("\tDecide: " + d);
429        return d;
430      }
431    }
432  }
433
434  /**
435   * Logic to select the appropriate guarding mechanism for the edge
436   * from caller to callee according to the controlling {@link OptOptions}.
437   * If we are using IG_CODE_PATCH, then this method also records
438   * the required dependency.
439   * Precondition: lock on {@link RVMClass#classLoadListener} is held.
440   *
441   * @param caller The caller method
442   * @param singleImpl the method implementation that will be protected by the guard
443   * @param callee The callee method
444   * @param state compilation state at this point
445   * @param codePatchSupported   Can we use code patching at this call site?
446   * @return the chosen guard
447   */
448  private byte chooseGuard(RVMMethod caller, RVMMethod singleImpl, RVMMethod callee, CompilationState state,
449                           boolean codePatchSupported) {
450    byte guard = state.getOptions().INLINE_GUARD_KIND;
451    if (codePatchSupported) {
452      if (VM.VerifyAssertions && VM.runningVM) {
453        VM._assert(ObjectModel.holdsLock(RVMClass.classLoadListener, RVMThread.getCurrentThread()));
454      }
455      if (guard == OptOptions.INLINE_GUARD_CODE_PATCH) {
456        ClassLoadingDependencyManager cldm = (ClassLoadingDependencyManager) RVMClass.classLoadListener;
457        if (ClassLoadingDependencyManager.TRACE || ClassLoadingDependencyManager.DEBUG) {
458          cldm.report("CODE PATCH: Inlined " + singleImpl + " into " + caller + "\n");
459        }
460        cldm.addNotOverriddenDependency(callee, state.getCompiledMethod());
461      }
462    } else if (guard == OptOptions.INLINE_GUARD_CODE_PATCH) {
463      guard = OptOptions.INLINE_GUARD_METHOD_TEST;
464    }
465
466    if (guard == OptOptions.INLINE_GUARD_METHOD_TEST && singleImpl.getDeclaringClass().isFinal()) {
467      // class test is more efficient and just as effective
468      guard = OptOptions.INLINE_GUARD_CLASS_TEST;
469    }
470    return guard;
471  }
472
473  /**
474   * Estimate the expected cost of the inlining action
475   * (includes both the inline body and the guard/off-branch code).
476   *
477   * @param inlinedBodyEstimate size estimate for inlined body
478   * @param needsGuard is it going to be a guarded inline?
479   * @param preEx      can preEx inlining be used to avoid the guard?
480   * @param opts       controlling options object
481   * @return the estimated cost of the inlining action
482   */
483  private int inliningActionCost(int inlinedBodyEstimate, boolean needsGuard, boolean preEx, OptOptions opts) {
484    int guardCost = 0;
485    if (needsGuard & !preEx) {
486      guardCost += NormalMethod.CALL_COST;
487      if (opts.guardWithMethodTest()) {
488        guardCost += 3 * NormalMethod.SIMPLE_OPERATION_COST;
489      } else if (opts.guardWithCodePatch()) {
490        guardCost += NormalMethod.SIMPLE_OPERATION_COST;
491      } else { // opts.guardWithClassTest()
492        guardCost += 2 * NormalMethod.SIMPLE_OPERATION_COST;
493      }
494    }
495    return guardCost + inlinedBodyEstimate;
496  }
497}