1 /* 2 * Copyright (c) 2010, 2014, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package jdk.nashorn.internal.codegen; 27 28 import static jdk.nashorn.internal.codegen.CompilerConstants.ARGUMENTS_VAR; 29 import static jdk.nashorn.internal.codegen.CompilerConstants.EXPLODED_ARGUMENT_PREFIX; 30 31 import java.lang.invoke.MethodType; 32 import java.net.URL; 33 import java.util.ArrayDeque; 34 import java.util.ArrayList; 35 import java.util.Deque; 36 import java.util.HashSet; 37 import java.util.List; 38 import java.util.Set; 39 import jdk.nashorn.internal.ir.AccessNode; 40 import jdk.nashorn.internal.ir.CallNode; 41 import jdk.nashorn.internal.ir.Expression; 42 import jdk.nashorn.internal.ir.FunctionNode; 43 import jdk.nashorn.internal.ir.IdentNode; 44 import jdk.nashorn.internal.ir.Node; 45 import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor; 46 import jdk.nashorn.internal.objects.Global; 47 import jdk.nashorn.internal.runtime.Context; 48 import jdk.nashorn.internal.runtime.logging.DebugLogger; 49 import jdk.nashorn.internal.runtime.logging.Loggable; 50 import jdk.nashorn.internal.runtime.logging.Logger; 51 import jdk.nashorn.internal.runtime.options.Options; 52 53 /** 54 * An optimization that attempts to turn applies into calls. This pattern 55 * is very common for fake class instance creation, and apply 56 * introduces expensive args collection and boxing 57 * 58 * <pre> 59 * var Class = { 60 * create: function() { 61 * return function() { //vararg 62 * this.initialize.apply(this, arguments); 63 * } 64 * } 65 * }; 66 * 67 * Color = Class.create(); 68 * 69 * Color.prototype = { 70 * red: 0, green: 0, blue: 0, 71 * initialize: function(r,g,b) { 72 * this.red = r; 73 * this.green = g; 74 * this.blue = b; 75 * } 76 * } 77 * 78 * new Color(17, 47, 11); 79 * </pre> 80 */ 81 82 @Logger(name="apply2call") 83 public final class ApplySpecialization extends SimpleNodeVisitor implements Loggable { 84 85 private static final boolean USE_APPLY2CALL = Options.getBooleanProperty("nashorn.apply2call", true); 86 87 private final DebugLogger log; 88 89 private final Compiler compiler; 90 91 private final Set<Integer> changed = new HashSet<>(); 92 93 private final Deque<List<IdentNode>> explodedArguments = new ArrayDeque<>(); 94 95 private final Deque<MethodType> callSiteTypes = new ArrayDeque<>(); 96 97 private static final String ARGUMENTS = ARGUMENTS_VAR.symbolName(); 98 99 /** 100 * Apply specialization optimization. Try to explode arguments and call 101 * applies as calls if they just pass on the "arguments" array and 102 * "arguments" doesn't escape. 103 * 104 * @param compiler compiler 105 */ 106 public ApplySpecialization(final Compiler compiler) { 107 this.compiler = compiler; 108 this.log = initLogger(compiler.getContext()); 109 } 110 111 @Override 112 public DebugLogger getLogger() { 113 return log; 114 } 115 116 @Override 117 public DebugLogger initLogger(final Context context) { 118 return context.getLogger(this.getClass()); 119 } 120 121 @SuppressWarnings("serial") 122 private static class TransformFailedException extends RuntimeException { 123 TransformFailedException(final FunctionNode fn, final String message) { 124 super(massageURL(fn.getSource().getURL()) + '.' + fn.getName() + " => " + message, null, false, false); 125 } 126 } 127 128 @SuppressWarnings("serial") 129 private static class AppliesFoundException extends RuntimeException { 130 AppliesFoundException() { 131 super("applies_found", null, false, false); 132 } 133 } 134 135 private static final AppliesFoundException HAS_APPLIES = new AppliesFoundException(); 136 137 private boolean hasApplies(final FunctionNode functionNode) { 138 try { 139 functionNode.accept(new SimpleNodeVisitor() { 140 @Override 141 public boolean enterFunctionNode(final FunctionNode fn) { 142 return fn == functionNode; 143 } 144 145 @Override 146 public boolean enterCallNode(final CallNode callNode) { 147 if (isApply(callNode)) { 148 throw HAS_APPLIES; 149 } 150 return true; 151 } 152 }); 153 } catch (final AppliesFoundException e) { 154 return true; 155 } 156 157 log.fine("There are no applies in ", DebugLogger.quote(functionNode.getName()), " - nothing to do."); 158 return false; // no applies 159 } 160 161 /** 162 * Arguments may only be used as args to the apply. Everything else is disqualified 163 * We cannot control arguments if they escape from the method and go into an unknown 164 * scope, thus we are conservative and treat any access to arguments outside the 165 * apply call as a case of "we cannot apply the optimization". 166 */ 167 private static void checkValidTransform(final FunctionNode functionNode) { 168 169 final Set<Expression> argumentsFound = new HashSet<>(); 170 final Deque<Set<Expression>> stack = new ArrayDeque<>(); 171 172 //ensure that arguments is only passed as arg to apply 173 functionNode.accept(new SimpleNodeVisitor() { 174 175 private boolean isCurrentArg(final Expression expr) { 176 return !stack.isEmpty() && stack.peek().contains(expr); //args to current apply call 177 } 178 179 private boolean isArguments(final Expression expr) { 180 if (expr instanceof IdentNode && ARGUMENTS.equals(((IdentNode)expr).getName())) { 181 argumentsFound.add(expr); 182 return true; 183 } 184 return false; 185 } 186 187 private boolean isParam(final String name) { 188 for (final IdentNode param : functionNode.getParameters()) { 189 if (param.getName().equals(name)) { 190 return true; 191 } 192 } 193 return false; 194 } 195 196 @Override 197 public Node leaveIdentNode(final IdentNode identNode) { 198 if (isParam(identNode.getName())) { 199 throw new TransformFailedException(lc.getCurrentFunction(), "parameter: " + identNode.getName()); 200 } 201 // it's OK if 'argument' occurs as the current argument of an apply 202 if (isArguments(identNode) && !isCurrentArg(identNode)) { 203 throw new TransformFailedException(lc.getCurrentFunction(), "is 'arguments': " + identNode.getName()); 204 } 205 return identNode; 206 } 207 208 @Override 209 public boolean enterCallNode(final CallNode callNode) { 210 final Set<Expression> callArgs = new HashSet<>(); 211 if (isApply(callNode)) { 212 final List<Expression> argList = callNode.getArgs(); 213 if (argList.size() != 2 || !isArguments(argList.get(argList.size() - 1))) { 214 throw new TransformFailedException(lc.getCurrentFunction(), "argument pattern not matched: " + argList); 215 } 216 callArgs.addAll(callNode.getArgs()); 217 } 218 stack.push(callArgs); 219 return true; 220 } 221 222 @Override 223 public Node leaveCallNode(final CallNode callNode) { 224 stack.pop(); 225 return callNode; 226 } 227 }); 228 } 229 230 @Override 231 public boolean enterCallNode(final CallNode callNode) { 232 return !explodedArguments.isEmpty(); 233 } 234 235 @Override 236 public Node leaveCallNode(final CallNode callNode) { 237 //apply needs to be a global symbol or we don't allow it 238 239 final List<IdentNode> newParams = explodedArguments.peek(); 240 if (isApply(callNode)) { 241 final List<Expression> newArgs = new ArrayList<>(); 242 for (final Expression arg : callNode.getArgs()) { 243 if (arg instanceof IdentNode && ARGUMENTS.equals(((IdentNode)arg).getName())) { 244 newArgs.addAll(newParams); 245 } else { 246 newArgs.add(arg); 247 } 248 } 249 250 changed.add(lc.getCurrentFunction().getId()); 251 252 final CallNode newCallNode = callNode.setArgs(newArgs).setIsApplyToCall(); 253 254 if (log.isEnabled()) { 255 log.fine("Transformed ", 256 callNode, 257 " from apply to call => ", 258 newCallNode, 259 " in ", 260 DebugLogger.quote(lc.getCurrentFunction().getName())); 261 } 262 263 return newCallNode; 264 } 265 266 return callNode; 267 } 268 269 private void pushExplodedArgs(final FunctionNode functionNode) { 270 int start = 0; 271 272 final MethodType actualCallSiteType = compiler.getCallSiteType(functionNode); 273 if (actualCallSiteType == null) { 274 throw new TransformFailedException(lc.getCurrentFunction(), "No callsite type"); 275 } 276 assert actualCallSiteType.parameterType(actualCallSiteType.parameterCount() - 1) != Object[].class : "error vararg callsite passed to apply2call " + functionNode.getName() + " " + actualCallSiteType; 277 278 final TypeMap ptm = compiler.getTypeMap(); 279 if (ptm.needsCallee()) { 280 start++; 281 } 282 283 start++; // we always use this 284 285 assert functionNode.getNumOfParams() == 0 : "apply2call on function with named paramaters!"; 286 final List<IdentNode> newParams = new ArrayList<>(); 287 final long to = actualCallSiteType.parameterCount() - start; 288 for (int i = 0; i < to; i++) { 289 newParams.add(new IdentNode(functionNode.getToken(), functionNode.getFinish(), EXPLODED_ARGUMENT_PREFIX.symbolName() + (i))); 290 } 291 292 callSiteTypes.push(actualCallSiteType); 293 explodedArguments.push(newParams); 294 } 295 296 @Override 297 public boolean enterFunctionNode(final FunctionNode functionNode) { 298 // Cheap tests first 299 if (!( 300 // is the transform globally enabled? 301 USE_APPLY2CALL 302 303 // Are we compiling lazily? We can't known the number and types of the actual parameters at 304 // the caller when compiling eagerly, so this only works with on-demand compilation. 305 && compiler.isOnDemandCompilation() 306 307 // Does the function even reference the "arguments" identifier (without redefining it)? If not, 308 // it trivially can't have an expression of form "f.apply(self, arguments)" that this transform 309 // is targeting. 310 && functionNode.needsArguments() 311 312 // Does the function have eval? If so, it can arbitrarily modify arguments so we can't touch it. 313 && !functionNode.hasEval() 314 315 // Finally, does the function declare any parameters explicitly? We don't support that. It could 316 // be done, but has some complications. Therefore only a function with no explicit parameters 317 // is considered. 318 && functionNode.getNumOfParams() == 0)) 319 { 320 return false; 321 } 322 323 if (!Global.isBuiltinFunctionPrototypeApply()) { 324 log.fine("Apply transform disabled: apply/call overridden"); 325 assert !Global.isBuiltinFunctionPrototypeCall() : "call and apply should have the same SwitchPoint"; 326 return false; 327 } 328 329 if (!hasApplies(functionNode)) { 330 return false; 331 } 332 333 if (log.isEnabled()) { 334 log.info("Trying to specialize apply to call in '", 335 functionNode.getName(), 336 "' params=", 337 functionNode.getParameters(), 338 " id=", 339 functionNode.getId(), 340 " source=", 341 massageURL(functionNode.getSource().getURL())); 342 } 343 344 try { 345 checkValidTransform(functionNode); 346 pushExplodedArgs(functionNode); 347 } catch (final TransformFailedException e) { 348 log.info("Failure: ", e.getMessage()); 349 return false; 350 } 351 352 return true; 353 } 354 355 /** 356 * Try to do the apply to call transformation 357 * @return true if successful, false otherwise 358 */ 359 @Override 360 public Node leaveFunctionNode(final FunctionNode functionNode) { 361 FunctionNode newFunctionNode = functionNode; 362 final String functionName = newFunctionNode.getName(); 363 364 if (changed.contains(newFunctionNode.getId())) { 365 newFunctionNode = newFunctionNode.clearFlag(lc, FunctionNode.USES_ARGUMENTS). 366 setFlag(lc, FunctionNode.HAS_APPLY_TO_CALL_SPECIALIZATION). 367 setParameters(lc, explodedArguments.peek()); 368 369 if (log.isEnabled()) { 370 log.info("Success: ", 371 massageURL(newFunctionNode.getSource().getURL()), 372 '.', 373 functionName, 374 "' id=", 375 newFunctionNode.getId(), 376 " params=", 377 callSiteTypes.peek()); 378 } 379 } 380 381 callSiteTypes.pop(); 382 explodedArguments.pop(); 383 384 return newFunctionNode; 385 } 386 387 private static boolean isApply(final CallNode callNode) { 388 final Expression f = callNode.getFunction(); 389 return f instanceof AccessNode && "apply".equals(((AccessNode)f).getProperty()); 390 } 391 392 private static String massageURL(final URL url) { 393 if (url == null) { 394 return "<null>"; 395 } 396 final String str = url.toString(); 397 final int slash = str.lastIndexOf('/'); 398 if (slash == -1) { 399 return str; 400 } 401 return str.substring(slash + 1); 402 } 403 }