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.compilers.opt.inlining;
014
015 import java.util.ArrayList;
016 import java.util.Iterator;
017
018 import org.jikesrvm.VM;
019 import org.jikesrvm.adaptive.controller.AdaptiveInlining;
020 import org.jikesrvm.adaptive.controller.Controller;
021 import org.jikesrvm.adaptive.database.callgraph.WeightedCallTargets;
022 import org.jikesrvm.classloader.NormalMethod;
023 import org.jikesrvm.classloader.RVMClass;
024 import org.jikesrvm.classloader.RVMMethod;
025 import org.jikesrvm.compilers.common.CompiledMethod;
026 import org.jikesrvm.compilers.opt.OptOptions;
027 import org.jikesrvm.compilers.opt.driver.OptimizingCompiler;
028 import org.jikesrvm.compilers.opt.runtimesupport.OptCompiledMethod;
029 import org.jikesrvm.objectmodel.ObjectModel;
030 import 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 */
041 public 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 callee The callee method
443 * @param codePatchSupported Can we use code patching at this call site?
444 */
445 private byte chooseGuard(RVMMethod caller, RVMMethod singleImpl, RVMMethod callee, CompilationState state,
446 boolean codePatchSupported) {
447 byte guard = state.getOptions().INLINE_GUARD_KIND;
448 if (codePatchSupported) {
449 if (VM.VerifyAssertions && VM.runningVM) {
450 VM._assert(ObjectModel.holdsLock(RVMClass.classLoadListener, RVMThread.getCurrentThread()));
451 }
452 if (guard == OptOptions.INLINE_GUARD_CODE_PATCH) {
453 ClassLoadingDependencyManager cldm = (ClassLoadingDependencyManager) RVMClass.classLoadListener;
454 if (ClassLoadingDependencyManager.TRACE || ClassLoadingDependencyManager.DEBUG) {
455 cldm.report("CODE PATCH: Inlined " + singleImpl + " into " + caller + "\n");
456 }
457 cldm.addNotOverriddenDependency(callee, state.getCompiledMethod());
458 }
459 } else if (guard == OptOptions.INLINE_GUARD_CODE_PATCH) {
460 guard = OptOptions.INLINE_GUARD_METHOD_TEST;
461 }
462
463 if (guard == OptOptions.INLINE_GUARD_METHOD_TEST && singleImpl.getDeclaringClass().isFinal()) {
464 // class test is more efficient and just as effective
465 guard = OptOptions.INLINE_GUARD_CLASS_TEST;
466 }
467 return guard;
468 }
469
470 /**
471 * Estimate the expected cost of the inlining action
472 * (includes both the inline body and the guard/off-branch code).
473 *
474 * @param inlinedBodyEstimate size estimate for inlined body
475 * @param needsGuard is it going to be a guarded inline?
476 * @param preEx can preEx inlining be used to avoid the guard?
477 * @param opts controlling options object
478 * @return the estimated cost of the inlining action
479 */
480 private int inliningActionCost(int inlinedBodyEstimate, boolean needsGuard, boolean preEx, OptOptions opts) {
481 int guardCost = 0;
482 if (needsGuard & !preEx) {
483 guardCost += NormalMethod.CALL_COST;
484 if (opts.guardWithMethodTest()) {
485 guardCost += 3 * NormalMethod.SIMPLE_OPERATION_COST;
486 } else if (opts.guardWithCodePatch()) {
487 guardCost += NormalMethod.SIMPLE_OPERATION_COST;
488 } else { // opts.guardWithClassTest()
489 guardCost += 2 * NormalMethod.SIMPLE_OPERATION_COST;
490 }
491 }
492 return guardCost + inlinedBodyEstimate;
493 }
494 }