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.Stack;
016
017import org.jikesrvm.VM;
018import org.jikesrvm.classloader.RVMClass;
019import org.jikesrvm.classloader.RVMMethod;
020import org.jikesrvm.classloader.NormalMethod;
021import org.jikesrvm.classloader.TypeReference;
022import org.jikesrvm.compilers.opt.ir.Call;
023import org.jikesrvm.compilers.opt.ir.Instruction;
024import org.jikesrvm.compilers.opt.ir.operand.Operand;
025import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
026import org.jikesrvm.compilers.opt.OptOptions;
027import org.jikesrvm.runtime.Entrypoints;
028import org.vmmagic.pragma.Inline;
029
030/**
031 * This class provides some utilities that are useful for inlining.
032 */
033public abstract class InlineTools {
034
035  /**
036   * @param A a class
037   * @param B an interface
038   * @return whether class <code>A</code> directly implement the interface <code>B</code>?
039   */
040  public static boolean implementsInterface(Class<?> A, Class<?> B) {
041    for (Class<?> i : A.getInterfaces()) {
042      if (i == B) {
043        return true;
044      }
045    }
046    return false;
047  }
048
049  /**
050   * Does the callee method have a body?
051   * @param callee The callee method
052   * @return <code>true</code> if it has bytecodes, false otherwise.
053   */
054  public static boolean hasBody(RVMMethod callee) {
055    return !(callee.isNative() || callee.isAbstract());
056  }
057
058  /**
059   * Does an inlined call to callee need a guard, to protect against
060   * a mispredicted dynamic dispatch?
061   *
062   * @param callee the callee method
063   * @return whether a guard is needed
064   */
065  public static boolean needsGuard(RVMMethod callee) {
066    return !(callee.isFinal() ||
067             callee.getDeclaringClass().isFinal() ||
068             callee.isPrivate() ||
069             callee.isObjectInitializer() ||
070             callee.isStatic());
071  }
072
073  /**
074   * Is the method CURRENTLY final (not overridden by any subclass)?
075   * <p>
076   * Note that this says nothing about whether or not the method will
077   * be overridden by future dynamically loaded classes.
078   *
079   * @param callee the method to check
080   * @param searchSubclasses whether so search subclasses.
081   * @return whether the method is currently final. This will be a
082   *  conservative approximation if subclasses are not searched.
083   */
084  public static boolean isCurrentlyFinal(RVMMethod callee, boolean searchSubclasses) {
085    RVMClass klass = callee.getDeclaringClass();
086    if (klass.isInterface()) {
087      // interface methods are not final.
088      return false;
089    }
090    RVMClass[] subClasses = klass.getSubClasses();
091    if (subClasses.length == 0) {
092      //  Currently no subclasses, so trivially not overridden
093      return true;
094    } else if (searchSubclasses) {
095      // see if any subclasses have overridden the method
096      Stack<RVMClass> s = new Stack<RVMClass>();
097      for (RVMClass subClass1 : subClasses) {
098        s.push(subClass1);
099      }
100      while (!s.isEmpty()) {
101        RVMClass subClass = s.pop();
102        if (subClass.findDeclaredMethod(callee.getName(), callee.getDescriptor()) != null) {
103          return false;        // found an overridding method
104        }
105        subClasses = subClass.getSubClasses();
106        for (RVMClass subClass1 : subClasses) {
107          s.push(subClass1);
108        }
109      }
110      return true;  // didn't find an overridding method in all currently resolved subclasses
111    } else {
112      return false; // could be one, so be conservative.
113    }
114  }
115
116  /**
117   * Given the currently available information at the call site,
118   * what's our best guess on the inlined size of the callee?
119   * @param callee the method to be inlined
120   * @param state the compilation state decribing the call site where it
121   *              is to be inlined
122   * @return an inlined size estimate (number of machine code instructions)
123   */
124  public static int inlinedSizeEstimate(NormalMethod callee, CompilationState state) {
125    int sizeEstimate = callee.inlinedSizeEstimate();
126    // Adjust size estimate downward to account for optimizations
127    // that are typically enabled by constant parameters.
128    Instruction callInstr = state.getCallInstruction();
129    int numArgs = Call.getNumberOfParams(callInstr);
130    double reductionFactor = 1.0;               // no reduction.
131    OptOptions opts = state.getOptions();
132    for (int i = 0; i < numArgs; i++) {
133      Operand op = Call.getParam(callInstr, i);
134      if (op instanceof RegisterOperand) {
135        RegisterOperand rop = (RegisterOperand)op;
136        TypeReference type = rop.getType();
137        if (type.isReferenceType()) {
138          if (type.isArrayType()) {
139            // Reductions only come from optimization of dynamic type checks; all virtual methods on arrays are defined on Object.
140            if (rop.isPreciseType()) {
141              reductionFactor -= opts.INLINE_PRECISE_REG_ARRAY_ARG_BONUS;
142            } else if (rop.isDeclaredType() && callee.hasArrayWrite() && type.getArrayElementType().isReferenceType()) {
143              // potential to optimize checkstore portion of aastore bytecode on parameter
144              reductionFactor -= opts.INLINE_DECLARED_AASTORED_ARRAY_ARG_BONUS;
145            }
146          } else {
147            // Reductions come from optimization of dynamic type checks and improved inlining of virtual/interface calls
148            if (rop.isPreciseType()) {
149              reductionFactor -= opts.INLINE_PRECISE_REG_CLASS_ARG_BONUS;
150            } else if (rop.isExtant()) {
151              reductionFactor -= opts.INLINE_EXTANT_REG_CLASS_ARG_BONUS;
152            }
153          }
154        }
155      } else if (op.isIntConstant()) {
156        reductionFactor -= opts.INLINE_INT_CONST_ARG_BONUS;
157      } else if (op.isNullConstant()) {
158        reductionFactor -= opts.INLINE_NULL_CONST_ARG_BONUS;
159      } else if (op.isObjectConstant()) {
160        reductionFactor -= opts.INLINE_OBJECT_CONST_ARG_BONUS;
161      }
162    }
163    reductionFactor = Math.max(reductionFactor, 1.0 - opts.INLINE_MAX_ARG_BONUS);
164    if (opts.INLINE_CALL_DEPTH_COST != 0.00) {
165      double depthCost = Math.pow(1.0 + opts.INLINE_CALL_DEPTH_COST, state.getInlineDepth() + 1);
166      return (int) (sizeEstimate * reductionFactor * depthCost);
167    } else {
168      return (int) (sizeEstimate * reductionFactor);
169    }
170  }
171
172  /**
173   * Should the callee method always be inlined?
174   * Usually this is because of a programmer directive (InlinePragma),
175   * but we also use this mechanism to hardwire a couple special cases.
176   *
177   * @param callee the method being considered for inlining
178   * @param state the compilation state of the caller.
179   * @return whether or not the callee should be unconditionally inlined.
180   */
181  public static boolean hasInlinePragma(RVMMethod callee, CompilationState state) {
182    if (callee.hasInlineAnnotation()) {
183      Inline ann = callee.getAnnotation(Inline.class);
184      if (ann == null) {
185        // annotation was lost, assume it was Always
186        return true;
187      }
188
189      switch (ann.value()) {
190      case Always:
191        return true;
192      case AllArgumentsAreConstant: {
193        boolean result = true;
194        Instruction s = state.getCallInstruction();
195        for (int i = 0, n = Call.getNumberOfParams(s); i < n; i++) {
196          if (!Call.getParam(s, i).isConstant()) {
197            result = false;
198            break;
199          }
200        }
201        if (result) {
202          return true;
203        }
204        break;
205      }
206      case ArgumentsAreConstant: {
207        boolean result = true;
208        Instruction s = state.getCallInstruction();
209        int[] args = ann.arguments();
210        for (int arg : args) {
211          if (VM.VerifyAssertions) {
212            boolean biggerThanMin = arg >= 0;
213            boolean smallerThanMax = arg < Call.getNumberOfParams(s);
214            if (!(smallerThanMax && biggerThanMin)) {
215              String msg = "argument is invalid: " + arg;
216              VM._assert(VM.NOT_REACHED, msg);
217            }
218          }
219          if (!Call.getParam(s, arg).isConstant()) {
220            result = false;
221            break;
222          }
223        }
224        if (result) {
225          return true;
226        }
227        break;
228      }
229      case AssertionsDisabled: {
230        return !VM.VerifyAssertions;
231      }
232      }
233    }
234    // TODO: clean this hack up
235    // Hack to inline java.lang.VMSystem.arraycopy in the case that
236    // arg 0 isn't an Object
237    if (callee == Entrypoints.sysArrayCopy) {
238      Operand src = Call.getParam(state.getCallInstruction(), 0);
239      return src.getType() != TypeReference.JavaLangObject;
240    }
241    return false;
242  }
243
244  /**
245   * Should the callee method be barred from ever being considered for inlining?
246   *
247   * @param callee the method being considered for inlining
248   * @param state the compilation state of the caller.
249   * @return whether or not the callee should be unconditionally barred
250   *         from being inlined.
251   */
252  public static boolean hasNoInlinePragma(RVMMethod callee, CompilationState state) {
253    return callee.hasNoInlinePragma();
254  }
255
256  /**
257   * Is it safe to speculatively inline the callee into the caller?
258   * <p>
259   * Some forms of speculative inlining are unsafe to apply to
260   * methods of the core virtual machine because if we are forced to
261   * invalidate the methods, we will be unable to compile their
262   * replacement method.
263   * <p>
264   * TODO The current test is overly conservative, but past attempts at
265   * defining a more precise set of "third rail" classes have
266   * always resulted in missing some (only to discover them later
267   * when Jikes RVM hangs or crashes.)
268   *
269   * @param caller the caller method
270   * @param callee the callee method
271   * @return Whether or not we are allowed to speculatively inline
272   *         the callee into the caller.
273   */
274  public static boolean isForbiddenSpeculation(RVMMethod caller, RVMMethod callee) {
275    return caller.getDeclaringClass().isInBootImage() && !callee.getDeclaringClass().getDescriptor().isRVMDescriptor();
276  }
277}