| /* |
| * Copyright 2008 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| * use this file except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| * License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| package com.google.gwt.dev.js; |
| |
| import com.google.gwt.dev.jjs.HasSourceInfo; |
| import com.google.gwt.dev.jjs.InternalCompilerException; |
| import com.google.gwt.dev.jjs.SourceInfo; |
| import com.google.gwt.dev.jjs.impl.OptimizerStats; |
| import com.google.gwt.dev.js.ast.JsArrayAccess; |
| import com.google.gwt.dev.js.ast.JsArrayLiteral; |
| import com.google.gwt.dev.js.ast.JsBinaryOperation; |
| import com.google.gwt.dev.js.ast.JsBinaryOperator; |
| import com.google.gwt.dev.js.ast.JsBlock; |
| import com.google.gwt.dev.js.ast.JsBooleanLiteral; |
| import com.google.gwt.dev.js.ast.JsCase; |
| import com.google.gwt.dev.js.ast.JsCatchScope; |
| import com.google.gwt.dev.js.ast.JsConditional; |
| import com.google.gwt.dev.js.ast.JsContext; |
| import com.google.gwt.dev.js.ast.JsDefault; |
| import com.google.gwt.dev.js.ast.JsEmpty; |
| import com.google.gwt.dev.js.ast.JsExprStmt; |
| import com.google.gwt.dev.js.ast.JsExpression; |
| import com.google.gwt.dev.js.ast.JsFor; |
| import com.google.gwt.dev.js.ast.JsForIn; |
| import com.google.gwt.dev.js.ast.JsFunction; |
| import com.google.gwt.dev.js.ast.JsIf; |
| import com.google.gwt.dev.js.ast.JsInvocation; |
| import com.google.gwt.dev.js.ast.JsModVisitor; |
| import com.google.gwt.dev.js.ast.JsName; |
| import com.google.gwt.dev.js.ast.JsNameRef; |
| import com.google.gwt.dev.js.ast.JsNew; |
| import com.google.gwt.dev.js.ast.JsNode; |
| import com.google.gwt.dev.js.ast.JsNullLiteral; |
| import com.google.gwt.dev.js.ast.JsNumberLiteral; |
| import com.google.gwt.dev.js.ast.JsObjectLiteral; |
| import com.google.gwt.dev.js.ast.JsParameter; |
| import com.google.gwt.dev.js.ast.JsPostfixOperation; |
| import com.google.gwt.dev.js.ast.JsPrefixOperation; |
| import com.google.gwt.dev.js.ast.JsProgram; |
| import com.google.gwt.dev.js.ast.JsRegExp; |
| import com.google.gwt.dev.js.ast.JsReturn; |
| import com.google.gwt.dev.js.ast.JsRootScope; |
| import com.google.gwt.dev.js.ast.JsScope; |
| import com.google.gwt.dev.js.ast.JsStatement; |
| import com.google.gwt.dev.js.ast.JsStringLiteral; |
| import com.google.gwt.dev.js.ast.JsThisRef; |
| import com.google.gwt.dev.js.ast.JsVars; |
| import com.google.gwt.dev.js.ast.JsVars.JsVar; |
| import com.google.gwt.dev.js.ast.JsVisitor; |
| import com.google.gwt.dev.js.ast.JsWhile; |
| import com.google.gwt.dev.util.log.speedtracer.CompilerEventType; |
| import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger; |
| import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event; |
| |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.HashMap; |
| import java.util.HashSet; |
| import java.util.IdentityHashMap; |
| import java.util.List; |
| import java.util.ListIterator; |
| import java.util.Map; |
| import java.util.Set; |
| import java.util.Stack; |
| |
| /** |
| * Perform inlining optimizations on the JavaScript AST. |
| * |
| * TODO(bobv): remove anything that's duplicating work with {@link JsStaticEval} |
| * migrate other stuff to that class perhaps. |
| */ |
| public class JsInliner { |
| private static final String NAME = JsInliner.class.getSimpleName(); |
| |
| /** |
| * Determines if the evaluation of a JsNode may be affected by side effects. |
| */ |
| private static class AffectedBySideEffectsVisitor extends JsVisitor { |
| private boolean affectedBySideEffects; |
| private final JsScope safeScope; |
| |
| public AffectedBySideEffectsVisitor(JsScope safeScope) { |
| this.safeScope = safeScope; |
| } |
| |
| public boolean affectedBySideEffects() { |
| return affectedBySideEffects; |
| } |
| |
| @Override |
| public void endVisit(JsArrayLiteral x, JsContext ctx) { |
| affectedBySideEffects = true; |
| } |
| |
| @Override |
| public void endVisit(JsFunction x, JsContext ctx) { |
| affectedBySideEffects = true; |
| } |
| |
| @Override |
| public void endVisit(JsInvocation x, JsContext ctx) { |
| /* |
| * We could make this more accurate by analyzing the function that's being |
| * executed, but we'll bank on subsequent passes inlining simple function |
| * invocations. |
| */ |
| affectedBySideEffects = true; |
| } |
| |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| if (x.getQualifier() == null && x.getName() != null) { |
| // Special case the undefined literal. |
| if (x.getName() == JsRootScope.INSTANCE.getUndefined()) { |
| return; |
| } |
| // Locals in a safe scope are unaffected. |
| if (x.getName().getEnclosing() == safeScope) { |
| return; |
| } |
| } |
| |
| /* |
| * We can make this more accurate if we had single-assignment information |
| * (e.g. static final fields). |
| */ |
| affectedBySideEffects = true; |
| } |
| |
| @Override |
| public void endVisit(JsObjectLiteral x, JsContext ctx) { |
| affectedBySideEffects = true; |
| } |
| } |
| |
| /** |
| * Make comma binary operations left-nested since commas are naturally |
| * left-associative. We will define the comma-normal form such that a comma |
| * expression should never have a comma expression as its RHS and contains no |
| * side-effect-free expressions save for the outer, right-hand expression. |
| * This form has a nice side-effect of minimizing the number of generated |
| * parentheses. |
| * |
| * <pre> |
| * (X, b) is unchanged |
| * (X, (b, c) becomes ((X, b), c); b is guaranteed to have a side-effect |
| * (X, ((b, c), d)) becomes (((X, b), c), d) |
| * </pre> |
| */ |
| private static class CommaNormalizer extends JsModVisitor { |
| |
| /** |
| * Returns an expression as a JsBinaryOperation if it is a comma expression. |
| */ |
| private static JsBinaryOperation isComma(JsExpression x) { |
| if (!(x instanceof JsBinaryOperation)) { |
| return null; |
| } |
| JsBinaryOperation op = (JsBinaryOperation) x; |
| |
| return op.getOperator().equals(JsBinaryOperator.COMMA) ? op : null; |
| } |
| |
| private final List<JsName> localVariableNames; |
| |
| public CommaNormalizer(List<JsName> localVariableNames) { |
| this.localVariableNames = localVariableNames; |
| } |
| |
| @Override |
| public void endVisit(JsBinaryOperation x, JsContext ctx) { |
| if (isComma(x) == null) { |
| return; |
| } |
| |
| // If (X, a) and X has no side effects, replace with a |
| if (!x.getArg1().hasSideEffects()) { |
| ctx.replaceMe(x.getArg2()); |
| return; |
| } |
| |
| JsBinaryOperation toUpdate = isComma(x.getArg2()); |
| if (toUpdate == null) { |
| /* |
| * We have a JsBinaryOperation that's structurally normal: (X, a). Now |
| * it may be the case that the inner expression X is a comma expression |
| * (Y, b). If b creates no side-effects, we can remove it, leaving (Y, |
| * a) as the expression. |
| */ |
| JsBinaryOperation inner = isComma(x.getArg1()); |
| if (inner != null && !inner.getArg2().hasSideEffects()) { |
| x.setArg1(inner.getArg1()); |
| didChange = true; |
| } |
| |
| /* |
| * Eliminate the pattern (localVar = expr, localVar). This tends to |
| * occur when a method interacted with pruned fields or had statements |
| * removed. |
| */ |
| JsName assignmentRef = null; |
| JsExpression expr = null; |
| JsName returnRef = null; |
| |
| if (x.getArg1() instanceof JsBinaryOperation) { |
| JsBinaryOperation op = (JsBinaryOperation) x.getArg1(); |
| if (op.getOperator() == JsBinaryOperator.ASG |
| && op.getArg1() instanceof JsNameRef) { |
| JsNameRef nameRef = (JsNameRef) op.getArg1(); |
| if (nameRef.getQualifier() == null) { |
| assignmentRef = nameRef.getName(); |
| expr = op.getArg2(); |
| } |
| } |
| } |
| |
| if (x.getArg2() instanceof JsNameRef) { |
| JsNameRef nameRef = (JsNameRef) x.getArg2(); |
| if (nameRef.getQualifier() == null) { |
| returnRef = nameRef.getName(); |
| } |
| } |
| |
| if (assignmentRef != null && assignmentRef.equals(returnRef) |
| && localVariableNames.contains(assignmentRef)) { |
| assert expr != null; |
| localVariableNames.remove(assignmentRef); |
| ctx.replaceMe(expr); |
| } |
| return; |
| } |
| |
| // Find the left-most, nested comma expression |
| while (isComma(toUpdate.getArg1()) != null) { |
| toUpdate = (JsBinaryOperation) toUpdate.getArg1(); |
| } |
| |
| /* |
| * Create a new comma expression with the original LHS and the LHS of the |
| * nested comma expression. |
| */ |
| JsBinaryOperation newOp = new JsBinaryOperation(x.getSourceInfo(), |
| JsBinaryOperator.COMMA); |
| newOp.setArg1(x.getArg1()); |
| newOp.setArg2(toUpdate.getArg1()); |
| |
| // Set the LHS of the nested comma expression to the new comma expression |
| toUpdate.setArg1(newOp); |
| |
| // Replace the original node with its updated RHS |
| ctx.replaceMe(x.getArg2()); |
| } |
| } |
| |
| /** |
| * Provides a relative metric by which the syntactic complexity of a |
| * JsExpression can be gauged. |
| */ |
| private static class ComplexityEstimator extends JsVisitor { |
| /** |
| * The current measure of complexity. This measures the number of |
| * expressions that have been encountered by the visitor. |
| */ |
| private int complexity = 0; |
| |
| @Override |
| public void endVisit(JsArrayAccess x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsArrayLiteral x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsBinaryOperation x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsBooleanLiteral x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsConditional x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsFunction x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsInvocation x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsNew x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsNullLiteral x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsNumberLiteral x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsObjectLiteral x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsPostfixOperation x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsPrefixOperation x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsRegExp x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsStringLiteral x, JsContext ctx) { |
| complexity++; |
| } |
| |
| @Override |
| public void endVisit(JsThisRef x, JsContext ctx) { |
| complexity++; |
| } |
| |
| public int getComplexity() { |
| return complexity; |
| } |
| } |
| |
| /** |
| * This is used to clean up duplication invocations of functions that should |
| * only be executed once, such as clinit functions. Whenever there is a |
| * possible branch in program flow, the remover will create a new instance of |
| * itself to handle the possible branches. |
| * |
| * We don't look at combining branch choices. This will not produce the most |
| * efficient elimination of duplicated calls, but it handles the general case |
| * and is simple to verify. |
| */ |
| private static class DuplicateXORemover extends JsModVisitor { |
| /* |
| * TODO: Most of the special casing below can be removed if complex |
| * statements always use blocks, rather than plain statements. |
| */ |
| |
| /** |
| * Retains the the functions that we know have been called. |
| */ |
| private final Set<JsFunction> called; |
| private final JsProgram program; |
| |
| public DuplicateXORemover(JsProgram program) { |
| this.program = program; |
| called = new HashSet<JsFunction>(); |
| } |
| |
| public DuplicateXORemover(JsProgram program, Set<JsFunction> alreadyCalled) { |
| this.program = program; |
| called = new HashSet<JsFunction>(alreadyCalled); |
| } |
| |
| /** |
| * Look for comma expressions that contain duplicate calls and handle the |
| * conditional-evaluation case of logical and/or operations. |
| */ |
| @Override |
| public boolean visit(JsBinaryOperation x, JsContext ctx) { |
| if (x.getOperator() == JsBinaryOperator.COMMA) { |
| |
| boolean left = isDuplicateCall(x.getArg1()); |
| boolean right = isDuplicateCall(x.getArg2()); |
| |
| if (left && right) { |
| /* |
| * (clinit(), clinit()) --> delete or null. |
| * |
| * This construct is very unlikely since the InliningVisitor builds |
| * the comma expressions in a right-nested manner. |
| */ |
| if (ctx.canRemove()) { |
| ctx.removeMe(); |
| return false; |
| } else { |
| // The return value from an XO function is never used |
| ctx.replaceMe(JsNullLiteral.INSTANCE); |
| return false; |
| } |
| |
| } else if (left) { |
| // (clinit(), xyz) --> xyz |
| // This is the common case |
| ctx.replaceMe(accept(x.getArg2())); |
| return false; |
| |
| } else if (right) { |
| // (xyz, clinit()) --> xyz |
| // Possible if a clinit() were the last element |
| ctx.replaceMe(accept(x.getArg1())); |
| return false; |
| } |
| |
| } else if (x.getOperator().equals(JsBinaryOperator.AND) |
| || x.getOperator().equals(JsBinaryOperator.OR)) { |
| x.setArg1(accept(x.getArg1())); |
| // Possibility of conditional evaluation of second parameter |
| x.setArg2(branch(x.getArg2())); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /** |
| * Most of the branching statements (as well as JsFunctions) will visit with |
| * a JsBlock, so we don't need to explicitly enumerate all JsStatement |
| * subtypes. |
| */ |
| @Override |
| public boolean visit(JsBlock x, JsContext ctx) { |
| branch(x.getStatements()); |
| return false; |
| } |
| |
| @Override |
| public boolean visit(JsCase x, JsContext ctx) { |
| x.setCaseExpr(accept(x.getCaseExpr())); |
| branch(x.getStmts()); |
| return false; |
| } |
| |
| @Override |
| public boolean visit(JsConditional x, JsContext ctx) { |
| x.setTestExpression(accept(x.getTestExpression())); |
| x.setThenExpression(branch(x.getThenExpression())); |
| x.setElseExpression(branch(x.getElseExpression())); |
| return false; |
| } |
| |
| @Override |
| public boolean visit(JsDefault x, JsContext ctx) { |
| branch(x.getStmts()); |
| return false; |
| } |
| |
| @Override |
| public boolean visit(JsExprStmt x, JsContext ctx) { |
| if (isDuplicateCall(x.getExpression())) { |
| if (ctx.canRemove()) { |
| ctx.removeMe(); |
| } else { |
| ctx.replaceMe(new JsEmpty(x.getSourceInfo())); |
| } |
| return false; |
| |
| } else { |
| return true; |
| } |
| } |
| |
| @Override |
| public boolean visit(JsFor x, JsContext ctx) { |
| // The JsFor may have an expression xor a variable declaration. |
| if (x.getInitExpr() != null) { |
| x.setInitExpr(accept(x.getInitExpr())); |
| } else if (x.getInitVars() != null) { |
| x.setInitVars(accept(x.getInitVars())); |
| } |
| |
| // The condition is optional |
| if (x.getCondition() != null) { |
| x.setCondition(accept(x.getCondition())); |
| } |
| |
| // The increment expression is optional |
| if (x.getIncrExpr() != null) { |
| x.setIncrExpr(branch(x.getIncrExpr())); |
| } |
| |
| // The body is not guaranteed to be a JsBlock |
| x.setBody(branch(x.getBody())); |
| return false; |
| } |
| |
| @Override |
| public boolean visit(JsForIn x, JsContext ctx) { |
| if (x.getIterExpr() != null) { |
| x.setIterExpr(accept(x.getIterExpr())); |
| } |
| |
| x.setObjExpr(accept(x.getObjExpr())); |
| |
| // The body is not guaranteed to be a JsBlock |
| x.setBody(branch(x.getBody())); |
| return false; |
| } |
| |
| @Override |
| public boolean visit(JsIf x, JsContext ctx) { |
| x.setIfExpr(accept(x.getIfExpr())); |
| |
| x.setThenStmt(branch(x.getThenStmt())); |
| if (x.getElseStmt() != null) { |
| x.setElseStmt(branch(x.getElseStmt())); |
| } |
| |
| return false; |
| } |
| |
| /** |
| * Possibly record that we've seen a call in the current context. |
| */ |
| @Override |
| public boolean visit(JsInvocation x, JsContext ctx) { |
| JsFunction func = isExecuteOnce(x); |
| while (func != null) { |
| called.add(func); |
| func = func.getImpliedExecute(); |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JsWhile x, JsContext ctx) { |
| x.setCondition(accept(x.getCondition())); |
| |
| // The body is not guaranteed to be a JsBlock |
| x.setBody(branch(x.getBody())); |
| return false; |
| } |
| |
| private <T extends JsNode> void branch(List<T> x) { |
| DuplicateXORemover dup = new DuplicateXORemover(program, called); |
| dup.acceptWithInsertRemove(x); |
| didChange |= dup.didChange(); |
| } |
| |
| private <T extends JsNode> T branch(T x) { |
| DuplicateXORemover dup = new DuplicateXORemover(program, called); |
| T toReturn = dup.accept(x); |
| |
| if ((toReturn != x) && !dup.didChange()) { |
| throw new InternalCompilerException( |
| "node replacement should imply didChange()"); |
| } |
| |
| didChange |= dup.didChange(); |
| return toReturn; |
| } |
| |
| private boolean isDuplicateCall(JsExpression x) { |
| if (!(x instanceof JsInvocation)) { |
| return false; |
| } |
| |
| JsFunction func = isExecuteOnce((JsInvocation) x); |
| return (func != null && called.contains(func)); |
| } |
| } |
| |
| /** |
| * Determines that a list of names is guaranteed to be evaluated in a |
| * particular order. Also ensures that all names are evaluated before any |
| * invocations occur. |
| */ |
| private static class EvaluationOrderVisitor extends JsVisitor { |
| /** |
| * A dummy name to represent 'this' refs. |
| */ |
| public static final JsName THIS_NAME = new JsCatchScope( |
| JsRootScope.INSTANCE, "this").getAllNames().next(); |
| |
| private boolean maintainsOrder = true; |
| private final List<JsName> toEvaluate; |
| private final List<JsName> unevaluated; |
| private final Set<JsName> paramsOrLocals = new HashSet<JsName>(); |
| |
| public EvaluationOrderVisitor(List<JsName> toEvaluate, JsFunction callee) { |
| this.toEvaluate = toEvaluate; |
| this.unevaluated = new ArrayList<JsName>(toEvaluate); |
| // collect params and locals from callee function |
| new JsVisitor() { |
| @Override |
| public void endVisit(JsParameter x, JsContext ctx) { |
| paramsOrLocals.add(x.getName()); |
| } |
| |
| @Override |
| public boolean visit(JsVar x, JsContext ctx) { |
| // record this before visiting initializer |
| paramsOrLocals.add(x.getName()); |
| return true; |
| } |
| }.accept(callee); |
| } |
| |
| @Override |
| public void endVisit(JsBinaryOperation x, JsContext ctx) { |
| JsBinaryOperator op = x.getOperator(); |
| |
| /* |
| * We don't care about the left-hand expression, because it is guaranteed |
| * to be evaluated. |
| */ |
| boolean rightStrict = refersToRequiredName(x.getArg2()); |
| boolean conditionalEvaluation = JsBinaryOperator.AND.equals(op) |
| || JsBinaryOperator.OR.equals(op); |
| |
| if (rightStrict && conditionalEvaluation) { |
| maintainsOrder = false; |
| } |
| } |
| |
| /** |
| * If the condition would cause conditional evaluation of strict parameters, |
| * don't allow inlining. |
| */ |
| @Override |
| public void endVisit(JsConditional x, JsContext ctx) { |
| boolean thenStrict = refersToRequiredName(x.getThenExpression()); |
| boolean elseStrict = refersToRequiredName(x.getElseExpression()); |
| |
| if (thenStrict || elseStrict) { |
| maintainsOrder = false; |
| } |
| } |
| |
| /** |
| * The statement declares a function closure. This makes actual evaluation |
| * order of the parameters difficult or impossible to determine, so we'll |
| * just ignore them. |
| */ |
| @Override |
| public void endVisit(JsFunction x, JsContext ctx) { |
| maintainsOrder = false; |
| } |
| |
| /** |
| * The innermost invocation we see must consume all presently unevaluated |
| * parameters to ensure that an exception does not prevent their evaluation. |
| * |
| * In the case of a nested invocation, such as |
| * <code>F(r1, r2, G(r3, r4), f1);</code> the evaluation order is guaranteed |
| * to be maintained, provided that no required parameters occur after the |
| * nested invocation. |
| */ |
| @Override |
| public void endVisit(JsInvocation x, JsContext ctx) { |
| if (unevaluated.size() > 0) { |
| maintainsOrder = false; |
| } |
| } |
| |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| checkName(x.getName()); |
| } |
| |
| @Override |
| public void endVisit(JsNew x, JsContext ctx) { |
| /* |
| * Unless all arguments have already been evaluated, assume that invoking |
| * the new expression might interfere with the evaluation of the argument. |
| * |
| * It would be possible to allow this if the invoked function either does |
| * nothing or does nothing that affects the remaining arguments. However, |
| * currently there is no analysis of the invoked function. |
| */ |
| if (unevaluated.size() > 0) { |
| maintainsOrder = false; |
| } |
| } |
| |
| @Override |
| public void endVisit(JsThisRef x, JsContext ctx) { |
| checkName(THIS_NAME); |
| } |
| |
| public boolean maintainsOrder() { |
| return maintainsOrder && unevaluated.size() == 0; |
| } |
| |
| /** |
| * Check to see if the evaluation of this JsName will break program order assumptions given |
| * the parameters left to be substituted. |
| * |
| * The cases are as follows: |
| * 1) JsName is a function parameter name which has side effects or is affected by side effects |
| * (hereafter called 'volatile'), so it will be in 'toEvaluate' |
| * 2) JsName is a function parameter which is not volatile (not in toEvaluate) |
| * 3) JsName is a reference to a global variable |
| * 4) JsName is a reference to a local variable |
| * |
| * A reference to a global while there are still parameters left to evaluate / substitute |
| * implies an order violation. |
| * |
| * A reference to a volatile parameter is ok if it is the next parameter in sequence to |
| * be evaluated (beginning of unevaluated list). Else, it is either being evaluated out of |
| * order with respect to other parameters, or it is being evaluated more than once. |
| */ |
| private void checkName(JsName name) { |
| if (!toEvaluate.contains(name)) { |
| // if the name is a non-local/non-parameter (e.g. global) and there are params left to eval |
| if (!paramsOrLocals.contains(name) && unevaluated.size() > 0) { |
| maintainsOrder = false; |
| } |
| // else this may be a local, or all volatile params have already been evaluated, so it's ok. |
| return; |
| } |
| |
| // either this param is being evaled twice, or out of order |
| if (unevaluated.size() == 0 || !unevaluated.remove(0).equals(name)) { |
| maintainsOrder = false; |
| } |
| } |
| |
| /** |
| * Determine if an expression contains a reference to a strict parameter. |
| */ |
| private boolean refersToRequiredName(JsExpression e) { |
| RefersToNameVisitor v = new RefersToNameVisitor(toEvaluate); |
| v.accept(e); |
| return v.refersToName(); |
| } |
| } |
| |
| /** |
| * Collect all of the idents used in an AST node. The collector can be |
| * configured to collect idents from qualified xor unqualified JsNameRefs. |
| */ |
| private static class IdentCollector extends JsVisitor { |
| private final boolean collectQualified; |
| private final Set<String> idents = new HashSet<String>(); |
| |
| public IdentCollector(boolean collectQualified) { |
| this.collectQualified = collectQualified; |
| } |
| |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| boolean hasQualifier = x.getQualifier() != null; |
| |
| if ((collectQualified && !hasQualifier) |
| || (!collectQualified && hasQualifier)) { |
| return; |
| } |
| |
| assert x.getIdent() != null; |
| idents.add(x.getIdent()); |
| } |
| |
| public Set<String> getIdents() { |
| return idents; |
| } |
| } |
| |
| /** |
| * This class looks for function invocations that can be inlined and performs |
| * the replacement by replacing the JsInvocation with a comma expression |
| * consisting of the expressions evaluated by the target function. A second |
| * step may convert the expressions in the comma expression back to multiple |
| * statements if the context of the invocation would allow this. |
| */ |
| private static class InliningVisitor extends JsModVisitor { |
| private final Set<JsFunction> blacklist = new HashSet<JsFunction>(); |
| /** |
| * This reflects the functions that are currently being inlined to prevent |
| * infinite expansion. |
| */ |
| private final Stack<JsFunction> inlining = new Stack<JsFunction>(); |
| /** |
| * This reflects which function the visitor is currently visiting. |
| */ |
| private final Stack<JsFunction> functionStack = new Stack<JsFunction>(); |
| private final InvocationCountingVisitor invocationCountingVisitor = new InvocationCountingVisitor(); |
| private final Stack<List<JsName>> newLocalVariableStack = new Stack<List<JsName>>(); |
| |
| /** |
| * A map containing the next integer to try as an identifier suffix for a |
| * given JsScope. |
| */ |
| private IdentityHashMap<JsScope, HashMap<String, Integer>> startIdentForScope = new IdentityHashMap<JsScope, HashMap<String, Integer>>(); |
| |
| /** |
| * Not a stack because program fragments aren't nested. |
| */ |
| private JsFunction programFunction; |
| |
| public InliningVisitor(JsProgram program) { |
| invocationCountingVisitor.accept(program); |
| } |
| |
| /** |
| * Add to the list of JsFunctions that should not be inlined, regardless of |
| * whether or not they would normally be inlinable. |
| */ |
| public void blacklist(Collection<JsFunction> functions) { |
| blacklist.addAll(functions); |
| } |
| |
| /** |
| * This normalizes the comma expressions into multiple statements and |
| * removes statements with no side-effects. |
| */ |
| @Override |
| public void endVisit(JsExprStmt x, JsContext ctx) { |
| JsExpression e = x.getExpression(); |
| |
| // We will occasionally create JsExprStmts that have no side-effects. |
| if (ctx.canRemove() && !x.getExpression().hasSideEffects()) { |
| ctx.removeMe(); |
| return; |
| } |
| |
| List<JsExprStmt> statements = new ArrayList<JsExprStmt>(); |
| |
| /* |
| * Assemble the expressions back into a list of JsExprStmts. We will |
| * iteratively disassemble the nested comma expressions, stopping when the |
| * LHS is not a comma expression. |
| */ |
| while (e instanceof JsBinaryOperation) { |
| JsBinaryOperation op = (JsBinaryOperation) e; |
| |
| if (!op.getOperator().equals(JsBinaryOperator.COMMA)) { |
| break; |
| } |
| |
| /* |
| * We can ignore intermediate expressions as long as they have no |
| * side-effects. |
| */ |
| if (op.getArg2().hasSideEffects()) { |
| statements.add(0, op.getArg2().makeStmt()); |
| } |
| |
| e = op.getArg1(); |
| } |
| |
| /* |
| * We know the return value from the original invocation was ignored, so |
| * it may be possible to ignore the final expressions as long as it has no |
| * side-effects. |
| */ |
| if (e.hasSideEffects()) { |
| statements.add(0, e.makeStmt()); |
| } |
| |
| if (statements.size() == 0) { |
| // The expression contained no side effects at all. |
| if (ctx.canRemove()) { |
| ctx.removeMe(); |
| } else { |
| ctx.replaceMe(new JsEmpty(x.getSourceInfo())); |
| } |
| |
| } else if (x.getExpression() != statements.get(0).getExpression()) { |
| // Something has changed |
| |
| if (!ctx.canInsert()) { |
| /* |
| * This indicates that the function was attached to a clause of a |
| * control function and not into an existing block. We'll replace the |
| * single JsExprStmt with a JsBlock that contains all of the |
| * statements. |
| */ |
| JsBlock b = new JsBlock(x.getSourceInfo()); |
| b.getStatements().addAll(statements); |
| ctx.replaceMe(b); |
| return; |
| |
| } else { |
| // Insert the new statements into the original context |
| for (JsStatement s : statements) { |
| ctx.insertBefore(s); |
| } |
| ctx.removeMe(); |
| } |
| } |
| } |
| |
| @Override |
| public void endVisit(JsFunction x, JsContext ctx) { |
| if (!functionStack.pop().equals(x)) { |
| throw new InternalCompilerException("Unexpected function popped"); |
| } |
| |
| JsBlock body = x.getBody(); |
| List<JsName> newLocalVariables = newLocalVariableStack.pop(); |
| |
| addVars(x, body, newLocalVariables); |
| } |
| |
| @Override |
| public void endVisit(JsInvocation x, JsContext ctx) { |
| if (functionStack.isEmpty()) { |
| return; |
| } |
| JsFunction callerFunction = functionStack.peek(); |
| |
| /* |
| * We only want to look at invocations of things that we statically know |
| * to be functions. Otherwise, we can't know what statements the |
| * invocation would actually invoke. The static reference would be null |
| * when trying operate on references to external functions, or functions |
| * as arguments to another function. |
| */ |
| JsFunction invokedFunction = isFunction(x.getQualifier()); |
| if (invokedFunction == null) { |
| return; |
| } |
| |
| /* |
| * Don't inline huge functions into huge multi-expressions. Some JS |
| * engines will blow up. |
| */ |
| if (invokedFunction.getBody().getStatements().size() > 50) { |
| return; |
| } |
| |
| // Don't inline blacklisted functions |
| if (blacklist.contains(invokedFunction)) { |
| return; |
| } |
| |
| /* |
| * The current function has been mutated so as to be self-recursive. Ban |
| * it from any future inlining to prevent infinite expansion. |
| */ |
| if (invokedFunction == callerFunction) { |
| blacklist.add(invokedFunction); |
| return; |
| } |
| |
| /* |
| * We are already in the middle of attempting to inline a call to this |
| * function. This check prevents infinite expansion across |
| * mutually-recursive, inlinable functions. Any invocation skipped by this |
| * logic will be re-visited in the <code>op = accept(op)</code> call in |
| * the outermost JsInvocation. |
| */ |
| if (inlining.contains(invokedFunction)) { |
| return; |
| } |
| |
| inlining.push(invokedFunction); |
| x = tryToUnravelExplicitCall(x); |
| JsExpression op = process(x, callerFunction, invokedFunction); |
| |
| if (x != op) { |
| /* |
| * See if any further inlining can be performed in the current context. |
| * By attempting to maximize the level of inlining now, we can reduce |
| * the total number of passes required to finalize the AST. |
| */ |
| op = accept(op); |
| ctx.replaceMe(op); |
| } |
| |
| if (inlining.pop() != invokedFunction) { |
| throw new RuntimeException("Unexpected function popped"); |
| } |
| } |
| |
| @Override |
| public void endVisit(JsProgram x, JsContext ctx) { |
| if (!functionStack.pop().equals(programFunction)) { |
| throw new InternalCompilerException("Unexpected function popped"); |
| } |
| |
| assert programFunction.getBody().getStatements().size() == 0 : "Should not have moved statements into program"; |
| |
| List<JsName> newLocalVariables = newLocalVariableStack.pop(); |
| assert newLocalVariables.size() == 0 : "Should not have tried to create variables in program"; |
| } |
| |
| @Override |
| public boolean visit(JsExprStmt x, JsContext ctx) { |
| if (functionStack.peek() == programFunction) { |
| /* Don't inline top-level invocations. */ |
| if (x.getExpression() instanceof JsInvocation) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JsFunction x, JsContext ctx) { |
| functionStack.push(x); |
| newLocalVariableStack.push(new ArrayList<JsName>()); |
| return true; |
| } |
| |
| /** |
| * Create a synthetic context to attempt to simplify statements in the |
| * top-level of the program. |
| */ |
| @Override |
| public boolean visit(JsProgram x, JsContext ctx) { |
| programFunction = new JsFunction(x.getSourceInfo(), x.getScope()); |
| programFunction.setBody(new JsBlock(x.getSourceInfo())); |
| functionStack.push(programFunction); |
| newLocalVariableStack.push(new ArrayList<JsName>()); |
| return true; |
| } |
| |
| private void addVars(HasSourceInfo x, JsBlock body, |
| List<JsName> newLocalVariables) { |
| // Nothing to do |
| if (newLocalVariables.isEmpty()) { |
| return; |
| } |
| |
| List<JsStatement> statements = body.getStatements(); |
| |
| // The body can't be empty if we have local variables to create |
| assert !statements.isEmpty(); |
| |
| // Find or create the JsVars as the first statement |
| SourceInfo sourceInfo = x.getSourceInfo(); |
| JsVars vars; |
| if (statements.get(0) instanceof JsVars) { |
| vars = (JsVars) statements.get(0); |
| } else { |
| vars = new JsVars(sourceInfo); |
| statements.add(0, vars); |
| } |
| |
| // Add all variables |
| for (JsName name : newLocalVariables) { |
| vars.add(new JsVar(sourceInfo, name)); |
| } |
| } |
| |
| private boolean isInvokedMoreThanOnce(JsFunction f) { |
| Integer count = invocationCountingVisitor.invocationCount(f); |
| return count == null || count > 1; |
| } |
| |
| /** |
| * Determine if <code>invokedFunction</code> can be inlined into |
| * <code>callerFunction</code> at callsite <code>x</code>. |
| * |
| * @return An expression equivalent to <code>x</code> |
| */ |
| private JsExpression process(JsInvocation x, JsFunction callerFunction, |
| JsFunction invokedFunction) { |
| List<JsStatement> statements; |
| if (invokedFunction.getBody() != null) { |
| statements = new ArrayList<JsStatement>( |
| invokedFunction.getBody().getStatements()); |
| } else { |
| /* |
| * Will see this with certain classes whose clinits are folded into the |
| * main JsProgram body. |
| */ |
| statements = Collections.emptyList(); |
| } |
| |
| List<JsExpression> hoisted = new ArrayList<JsExpression>( |
| statements.size()); |
| JsExpression thisExpr = ((JsNameRef) x.getQualifier()).getQualifier(); |
| List<JsName> localVariableNames = new ArrayList<JsName>(); |
| boolean sawReturnStatement = false; |
| |
| for (JsStatement statement : statements) { |
| if (sawReturnStatement) { |
| /* |
| * We've already seen a return statement, but there are still more |
| * statements. The target is unsafe to inline, so bail. Note: in most |
| * cases JsStaticEval will have removed any statements following a |
| * return statement. |
| * |
| * The reason we have to bail is that the return statement's |
| * expression MUST be the last thing evaluated. |
| * |
| * TODO(bobv): maybe it could still be inlined with smart |
| * transformation? |
| */ |
| return x; |
| } |
| |
| /* |
| * Create replacement expressions to use in place of the original |
| * statements. It is important that the replacement is newly-minted and |
| * therefore not referenced by any other AST nodes. Consider the case of |
| * a common, delegating function. If the hoisted expressions were not |
| * distinct objects, it would not be possible to substitute different |
| * JsNameRefs at different call sites. |
| */ |
| JsExpression h = hoistedExpression(statement, localVariableNames); |
| if (h == null) { |
| return x; |
| } |
| |
| if (isReturnStatement(statement)) { |
| sawReturnStatement = true; |
| hoisted.add(h); |
| } else if (hasSideEffects(Collections.singletonList(h))) { |
| hoisted.add(h); |
| } |
| } |
| |
| /* |
| * If the inlined method has no return statement, synthesize an undefined |
| * reference. It will be reclaimed if the method call is from a |
| * JsExprStmt. |
| */ |
| if (!sawReturnStatement) { |
| hoisted.add(new JsNameRef(x.getSourceInfo(), |
| JsRootScope.INSTANCE.getUndefined())); |
| } |
| |
| assert (hoisted.size() > 0); |
| |
| /* |
| * Build up the new comma expression from right-to-left; building the |
| * rightmost comma expressions first. Bootstrapping with i.previous() |
| * ensures that this logic will function correctly in the case of a single |
| * expression. |
| */ |
| SourceInfo sourceInfo = x.getSourceInfo(); |
| ListIterator<JsExpression> i = hoisted.listIterator(hoisted.size()); |
| JsExpression op = i.previous(); |
| while (i.hasPrevious()) { |
| JsBinaryOperation outerOp = new JsBinaryOperation(sourceInfo, |
| JsBinaryOperator.COMMA); |
| outerOp.setArg1(i.previous()); |
| outerOp.setArg2(op); |
| op = outerOp; |
| } |
| |
| // Confirm that the expression conforms to the desired heuristics |
| if (!isInlinable(callerFunction, invokedFunction, thisExpr, |
| x.getArguments(), op)) { |
| return x; |
| } |
| |
| // Perform the name replacement |
| NameRefReplacerVisitor v = new NameRefReplacerVisitor(thisExpr, |
| x.getArguments(), invokedFunction.getParameters()); |
| for (ListIterator<JsName> nameIterator = localVariableNames.listIterator(); nameIterator.hasNext();) { |
| JsName name = nameIterator.next(); |
| |
| /* |
| * Find an unused identifier in the caller's scope. It's possible that |
| * the same function has been inlined in multiple places within the |
| * function so we'll use a counter for disambiguation. |
| */ |
| String ident; |
| String base = invokedFunction.getName() + "_" + name.getIdent(); |
| JsScope scope = callerFunction.getScope(); |
| HashMap<String, Integer> startIdent = startIdentForScope.get(scope); |
| if (startIdent == null) { |
| startIdent = new HashMap<String, Integer>(); |
| startIdentForScope.put(scope, startIdent); |
| } |
| |
| Integer s = startIdent.get(base); |
| int suffix = (s == null) ? 0 : s.intValue(); |
| do { |
| ident = base + "_" + suffix++; |
| } while (scope.findExistingName(ident) != null); |
| startIdent.put(base, suffix); |
| |
| JsName newName = scope.declareName(ident, name.getShortIdent()); |
| v.setReplacementName(name, newName); |
| nameIterator.set(newName); |
| } |
| op = v.accept(op); |
| |
| // Normalize any nested comma expressions that we may have generated. |
| op = (new CommaNormalizer(localVariableNames)).accept(op); |
| |
| /* |
| * Compare the relative complexity of the original invocation versus the |
| * inlined form. |
| */ |
| int originalComplexity = complexity(x); |
| int inlinedComplexity = complexity(op); |
| double ratio = ((double) inlinedComplexity) / originalComplexity; |
| if (ratio > MAX_COMPLEXITY_INCREASE |
| && isInvokedMoreThanOnce(invokedFunction)) { |
| return x; |
| } |
| |
| if (callerFunction == programFunction && localVariableNames.size() > 0) { |
| // Don't add additional variables to the top-level program. |
| return x; |
| } |
| |
| // We've committed to the inlining, ensure the vars are created |
| newLocalVariableStack.peek().addAll(localVariableNames); |
| |
| // update invocation counts according to this inlining |
| invocationCountingVisitor.removeCountsFor(x); |
| invocationCountingVisitor.accept(op); |
| return op; |
| } |
| } |
| |
| /** |
| * Counts the number of times a function is invoked. Functions that only have |
| * a single call site in the whole program are inlined, regardless of |
| * complexity. |
| */ |
| private static class InvocationCountingVisitor extends JsVisitor { |
| private boolean removingCounts = false; |
| private final Map<JsFunction, Integer> invocationCount = new IdentityHashMap<JsFunction, Integer>(); |
| |
| @Override |
| public void endVisit(JsInvocation x, JsContext ctx) { |
| checkFunctionCall(x.getQualifier()); |
| } |
| |
| @Override |
| public void endVisit(JsNew x, JsContext ctx) { |
| checkFunctionCall(x.getConstructorExpression()); |
| } |
| |
| public Integer invocationCount(JsFunction f) { |
| return invocationCount.get(f); |
| } |
| |
| /** |
| * Like accept(), but remove counts for all invocations in expr. |
| */ |
| public void removeCountsFor(JsExpression expr) { |
| assert (!removingCounts); |
| removingCounts = true; |
| accept(expr); |
| removingCounts = false; |
| } |
| |
| private void checkFunctionCall(JsExpression qualifier) { |
| JsFunction function = isFunction(qualifier); |
| if (function != null) { |
| Integer count = invocationCount.get(function); |
| if (count == null) { |
| assert (!removingCounts); |
| count = 1; |
| } else { |
| if (removingCounts) { |
| count -= 1; |
| } else { |
| count += 1; |
| } |
| } |
| invocationCount.put(function, count); |
| } |
| } |
| } |
| |
| /** |
| * Replace references to JsNames with the inlined JsExpression. |
| */ |
| private static class NameRefReplacerVisitor extends JsModVisitor { |
| /** |
| * Set up a map to record name replacements to perform. |
| */ |
| final Map<JsName, JsName> nameReplacements = new IdentityHashMap<JsName, JsName>(); |
| |
| /** |
| * Set up a map of parameter names back to the expressions that will be |
| * passed in from the outer call site. |
| */ |
| final Map<JsName, JsExpression> paramsToArgsMap = new IdentityHashMap<JsName, JsExpression>(); |
| |
| /** |
| * A replacement expression for this references. |
| */ |
| private JsExpression thisExpr; |
| |
| public NameRefReplacerVisitor(JsExpression thisExpr, |
| List<JsExpression> arguments, List<JsParameter> parameters) { |
| this.thisExpr = thisExpr; |
| if (parameters.size() != arguments.size()) { |
| // This shouldn't happen if the cloned JsInvocation has been properly |
| // configured |
| throw new InternalCompilerException( |
| "Mismatch on parameters and arguments"); |
| } |
| |
| for (int i = 0; i < parameters.size(); i++) { |
| JsParameter p = parameters.get(i); |
| JsExpression e = arguments.get(i); |
| paramsToArgsMap.put(p.getName(), e); |
| } |
| } |
| |
| /** |
| * Replace JsNameRefs that refer to parameters with the expression passed |
| * into the function invocation. |
| */ |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| if (x.getQualifier() != null) { |
| return; |
| } |
| |
| JsExpression replacement = tryGetReplacementExpression(x.getSourceInfo(), |
| x.getName()); |
| |
| if (replacement != null) { |
| ctx.replaceMe(replacement); |
| } |
| } |
| |
| @Override |
| public void endVisit(JsThisRef x, JsContext ctx) { |
| assert thisExpr != null; |
| ctx.replaceMe(thisExpr); |
| } |
| |
| /** |
| * Set a replacement JsName for all references to a JsName. |
| * |
| * @param name the name to replace |
| * @param newName the new name that should be used in place of references to |
| * <code>name</code> |
| * @return the previous JsName the name would have been replaced with or |
| * <code>null</code> if one was not previously set |
| */ |
| public JsName setReplacementName(JsName name, JsName newName) { |
| return nameReplacements.put(name, newName); |
| } |
| |
| /** |
| * Determine the replacement expression to use in place of a reference to a |
| * given name. Returns <code>null</code> if no replacement has been set for |
| * the name. |
| */ |
| private JsExpression tryGetReplacementExpression(SourceInfo sourceInfo, |
| JsName name) { |
| if (paramsToArgsMap.containsKey(name)) { |
| /* |
| * TODO if we ever allow mutable JsExpression types to be considered |
| * always flexible, then it would be necessary to clone the expression. |
| */ |
| return paramsToArgsMap.get(name); |
| |
| } else if (nameReplacements.containsKey(name)) { |
| return nameReplacements.get(name).makeRef(sourceInfo); |
| |
| } else { |
| return null; |
| } |
| } |
| } |
| |
| /** |
| * Detects function declarations. |
| */ |
| private static class NestedFunctionVisitor extends JsVisitor { |
| |
| private boolean containsNestedFunctions = false; |
| |
| public boolean containsNestedFunctions() { |
| return containsNestedFunctions; |
| } |
| |
| @Override |
| public void endVisit(JsFunction x, JsContext ctx) { |
| containsNestedFunctions = true; |
| } |
| } |
| |
| /** |
| * Detects uses of parameters that would produce incorrect results if inlined. |
| * Generally speaking, we disallow the use of parameters as lvalues. Also |
| * detects trying to inline a method which references 'this' where the call |
| * site has no qualifier. |
| */ |
| private static class ParameterUsageVisitor extends JsVisitor { |
| private final boolean hasThisExpr; |
| private final Set<JsName> parameterNames; |
| private boolean violation = false; |
| |
| public ParameterUsageVisitor(boolean hasThisExpr, Set<JsName> parameterNames) { |
| this.hasThisExpr = hasThisExpr; |
| this.parameterNames = parameterNames; |
| } |
| |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| if (ctx.isLvalue() && isParameter(x)) { |
| violation = true; |
| } |
| } |
| |
| @Override |
| public void endVisit(JsThisRef x, JsContext ctx) { |
| if (!hasThisExpr) { |
| violation = true; |
| } |
| } |
| |
| public boolean hasViolation() { |
| return violation; |
| } |
| |
| /** |
| * Determine if a JsExpression is a JsNameRef that refers to a parameter. |
| */ |
| private boolean isParameter(JsNameRef ref) { |
| if (ref.getQualifier() != null) { |
| return false; |
| } |
| |
| JsName name = ref.getName(); |
| return parameterNames.contains(name); |
| } |
| } |
| |
| /** |
| * Collect self-recursive functions. This visitor does not look for |
| * mutually-recursive functions because inlining one of the functions into the |
| * other would make the single resultant function self-recursive and not |
| * eligible for inlining in a subsequent pass. |
| */ |
| private static class RecursionCollector extends JsVisitor { |
| private final Stack<JsFunction> functionStack = new Stack<JsFunction>(); |
| private final Set<JsFunction> recursive = new HashSet<JsFunction>(); |
| |
| @Override |
| public void endVisit(JsFunction x, JsContext ctx) { |
| if (!functionStack.pop().equals(x)) { |
| throw new InternalCompilerException("Unexpected function popped"); |
| } |
| } |
| |
| @Override |
| public void endVisit(JsInvocation x, JsContext ctx) { |
| /* |
| * Because functions can encapsulate other functions, we look at the |
| * entire stack and not just the top element. This would prevent inlining |
| * |
| * function a() { function b() { a(); } b(); } |
| * |
| * in the case that we generally allow nested functions to be inlinable. |
| */ |
| JsFunction f = isFunction(x.getQualifier()); |
| if (functionStack.contains(f)) { |
| recursive.add(f); |
| } |
| } |
| |
| public Set<JsFunction> getRecursive() { |
| return recursive; |
| } |
| |
| @Override |
| public boolean visit(JsFunction x, JsContext ctx) { |
| functionStack.push(x); |
| return true; |
| } |
| } |
| |
| /** |
| * Determine which functions should not be inlined because they are redefined |
| * during program execution. This would violate the assumption that the |
| * statements to be executed by any given function invocation are stable over |
| * the lifetime of the program. |
| */ |
| private static class RedefinedFunctionCollector extends JsVisitor { |
| private final Map<JsName, JsFunction> nameMap = new IdentityHashMap<JsName, JsFunction>(); |
| private final Set<JsFunction> redefined = new HashSet<JsFunction>(); |
| |
| /** |
| * Look for assignments to JsNames whose static references are JsFunctions. |
| */ |
| @Override |
| public void endVisit(JsBinaryOperation x, JsContext ctx) { |
| |
| if (!x.getOperator().equals(JsBinaryOperator.ASG)) { |
| return; |
| } |
| |
| JsFunction f = isFunction(x.getArg1()); |
| if (f != null) { |
| redefined.add(f); |
| } |
| } |
| |
| /** |
| * Look for the case where a function is declared with the same name as an |
| * existing function. |
| */ |
| @Override |
| public void endVisit(JsFunction x, JsContext ctx) { |
| JsName name = x.getName(); |
| |
| if (name == null) { |
| // Ignore anonymous functions |
| return; |
| |
| } else if (nameMap.containsKey(name)) { |
| /* |
| * We have to add the current function as well as the original |
| * JsFunction that was declared to use that name. |
| */ |
| redefined.add(nameMap.get(name)); |
| redefined.add(x); |
| } else { |
| nameMap.put(name, x); |
| } |
| } |
| |
| public Collection<JsFunction> getRedefined() { |
| return redefined; |
| } |
| } |
| |
| /** |
| * Given a collection of JsNames, determine if an AST node refers to any of |
| * those names. |
| */ |
| private static class RefersToNameVisitor extends JsVisitor { |
| private final Collection<JsName> names; |
| private boolean refersToName; |
| private boolean refersToUnbound; |
| |
| public RefersToNameVisitor(Collection<JsName> names) { |
| this.names = names; |
| } |
| |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| JsName name = x.getName(); |
| |
| if (name == null) { |
| refersToUnbound = true; |
| } else { |
| refersToName = refersToName || names.contains(name); |
| } |
| } |
| |
| public boolean refersToName() { |
| return refersToName; |
| } |
| |
| public boolean refersToUnbound() { |
| return refersToUnbound; |
| } |
| } |
| |
| /** |
| * This ensures that changing the scope of an expression from its enclosing |
| * function into the scope of the call site will not cause unqualified |
| * identifiers to resolve to different values. |
| */ |
| private static class StableNameChecker extends JsVisitor { |
| private final JsScope calleeScope; |
| private final JsScope callerScope; |
| private final Collection<JsName> parameterNames; |
| private boolean stable = true; |
| |
| public StableNameChecker(JsScope callerScope, JsScope calleeScope, |
| Collection<JsName> parameterNames) { |
| this.callerScope = callerScope; |
| this.calleeScope = calleeScope; |
| this.parameterNames = parameterNames; |
| } |
| |
| @Override |
| public void endVisit(JsNameRef x, JsContext ctx) { |
| /* |
| * We can ignore qualified reference, since their scope is always that of |
| * the qualifier. |
| */ |
| if (x.getQualifier() != null) { |
| return; |
| } |
| |
| /* |
| * Attempt to resolve the ident in both scopes |
| */ |
| JsName callerName = callerScope.findExistingName(x.getIdent()); |
| JsName calleeName = calleeScope.findExistingName(x.getIdent()); |
| |
| if (callerName == null && calleeName == null) { |
| // They both reference out-of-module names |
| |
| } else if (parameterNames.contains(calleeName)) { |
| // A reference to a parameter, which will be replaced by an argument |
| |
| } else if (callerName != null && callerName.equals(calleeName)) { |
| // The names are known to us and are the same |
| |
| } else if (calleeName.getEnclosing().equals(calleeScope)) { |
| // It's a local variable in the callee |
| |
| } else { |
| stable = false; |
| } |
| } |
| |
| public boolean isStable() { |
| return stable; |
| } |
| } |
| |
| /** |
| * When attempting to inline an invocation, this constant determines the |
| * maximum allowable ratio of potential inlined complexity to initial |
| * complexity. This acts as a brake on very large expansions from bloating the |
| * the generated output. Increasing this number will allow larger sections of |
| * code to be inlined, but at a cost of larger JS output. |
| */ |
| private static final double MAX_COMPLEXITY_INCREASE = Double.parseDouble(System.getProperty( |
| "gwt.jsinlinerRatio", "1.7")); |
| |
| /** |
| * Static entry point used by JavaToJavaScriptCompiler. |
| */ |
| public static OptimizerStats exec(JsProgram program) { |
| Event optimizeJsEvent = SpeedTracerLogger.start( |
| CompilerEventType.OPTIMIZE_JS, "optimizer", NAME); |
| OptimizerStats stats = execImpl(program); |
| optimizeJsEvent.end("didChange", "" + stats.didChange()); |
| return stats; |
| } |
| |
| /** |
| * Determine whether or not a list of AST nodes are affected by side effects. |
| * The context parameter provides a scope in which local (and therefore |
| * immutable) variables are defined. |
| */ |
| private static boolean affectedBySideEffects(List<JsExpression> list, |
| JsFunction context) { |
| /* |
| * If the caller contains no nested functions, none of its locals can |
| * possibly be affected by side effects. |
| */ |
| JsScope safeScope = null; |
| if (context != null && !containsNestedFunctions(context)) { |
| safeScope = context.getScope(); |
| } |
| AffectedBySideEffectsVisitor v = new AffectedBySideEffectsVisitor(safeScope); |
| v.acceptList(list); |
| return v.affectedBySideEffects(); |
| } |
| |
| /** |
| * Generate an estimated measure of the syntactic complexity of a JsNode. |
| */ |
| private static int complexity(JsNode toEstimate) { |
| ComplexityEstimator e = new ComplexityEstimator(); |
| e.accept(toEstimate); |
| return e.getComplexity(); |
| } |
| |
| /** |
| * Examine a JsFunction to determine if it contains nested functions. |
| */ |
| private static boolean containsNestedFunctions(JsFunction func) { |
| NestedFunctionVisitor v = new NestedFunctionVisitor(); |
| v.accept(func.getBody()); |
| return v.containsNestedFunctions(); |
| } |
| |
| /** |
| * @param program |
| * @return |
| */ |
| private static OptimizerStats execImpl(JsProgram program) { |
| OptimizerStats stats = new OptimizerStats(NAME); |
| RedefinedFunctionCollector d = new RedefinedFunctionCollector(); |
| d.accept(program); |
| |
| RecursionCollector rc = new RecursionCollector(); |
| rc.accept(program); |
| |
| InliningVisitor v = new InliningVisitor(program); |
| v.blacklist(d.getRedefined()); |
| v.blacklist(rc.getRecursive()); |
| v.accept(program); |
| if (v.didChange()) { |
| stats.recordModified(); |
| } |
| |
| DuplicateXORemover r = new DuplicateXORemover(program); |
| r.accept(program); |
| if (r.didChange()) { |
| stats.recordModified(); |
| } |
| return stats; |
| } |
| |
| /** |
| * Check to see if the to-be-inlined statement shares any idents with the |
| * call-side arguments. Two passes are made: the first one looks for qualified |
| * names; the second pass looks for unqualified names, but ignores identifiers |
| * that refer to function parameters. |
| */ |
| private static boolean hasCommonIdents(List<JsExpression> arguments, |
| JsNode toInline, Collection<String> parameterIdents) { |
| |
| // This is a fire-twice loop |
| boolean checkQualified = false; |
| do { |
| checkQualified = !checkQualified; |
| |
| // Collect the idents used in the arguments and the statement |
| IdentCollector argCollector = new IdentCollector(checkQualified); |
| argCollector.acceptList(arguments); |
| IdentCollector statementCollector = new IdentCollector(checkQualified); |
| statementCollector.accept(toInline); |
| |
| Set<String> idents = argCollector.getIdents(); |
| |
| // Unqualified idents may be references to parameters, thus ignored |
| if (!checkQualified) { |
| idents.removeAll(parameterIdents); |
| } |
| |
| // Perform the set difference |
| idents.retainAll(statementCollector.getIdents()); |
| |
| if (idents.size() > 0) { |
| return true; |
| } |
| } while (checkQualified); |
| |
| return false; |
| } |
| |
| /** |
| * Determine whether or not a list of AST nodes have side effects. |
| */ |
| private static boolean hasSideEffects(List<JsExpression> list) { |
| for (JsExpression expr : list) { |
| if (expr.hasSideEffects()) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Given a delegated JsStatement, construct an expression to hoist into the |
| * outer caller. This does not perform any name replacement, but simply |
| * constructs a mutable copy of the expression that can be manipulated |
| * at-will. |
| * |
| * @param program the enclosing JsProgram |
| * @param statement the statement from which to extract the expressions |
| * @param localVariableNames accumulates any local varables declared by |
| * <code>statement</code> |
| * @return a JsExpression representing all expressions that would have been |
| * evaluated by the statement |
| */ |
| private static JsExpression hoistedExpression(JsStatement statement, |
| List<JsName> localVariableNames) { |
| JsExpression expression; |
| if (statement instanceof JsExprStmt) { |
| // Extract the expression |
| JsExprStmt exprStmt = (JsExprStmt) statement; |
| expression = exprStmt.getExpression(); |
| |
| } else if (statement instanceof JsReturn) { |
| // Extract the return value |
| JsReturn ret = (JsReturn) statement; |
| expression = ret.getExpr(); |
| if (expression == null) { |
| expression = new JsNameRef(ret.getSourceInfo(), |
| JsRootScope.INSTANCE.getUndefined()); |
| } |
| |
| } else if (statement instanceof JsVars) { |
| // Create a comma expression for variable initializers |
| JsVars vars = (JsVars) statement; |
| |
| // Rely on comma expression cleanup to remove this later. |
| expression = JsNullLiteral.INSTANCE; |
| |
| for (JsVar var : vars) { |
| // Record the locally-defined variable |
| localVariableNames.add(var.getName()); |
| |
| // Extract the initialization expression |
| JsExpression init = var.getInitExpr(); |
| if (init != null) { |
| SourceInfo sourceInfo = var.getSourceInfo(); |
| JsBinaryOperation assignment = new JsBinaryOperation(sourceInfo, |
| JsBinaryOperator.ASG); |
| assignment.setArg1(var.getName().makeRef(sourceInfo)); |
| assignment.setArg2(init); |
| |
| // Multiple initializers go into a comma expression |
| JsBinaryOperation comma = new JsBinaryOperation(sourceInfo, |
| JsBinaryOperator.COMMA); |
| comma.setArg1(expression); |
| comma.setArg2(assignment); |
| expression = comma; |
| } |
| } |
| } else { |
| return null; |
| } |
| |
| assert expression != null; |
| return JsHoister.hoist(expression); |
| } |
| |
| /** |
| * Given a JsInvocation, determine if it is invoking a JsFunction that is |
| * specified to be executed only once during the program's lifetime. |
| */ |
| private static JsFunction isExecuteOnce(JsInvocation invocation) { |
| JsFunction f = isFunction(invocation.getQualifier()); |
| if (f != null && f.getExecuteOnce()) { |
| return f; |
| } |
| return null; |
| } |
| |
| /** |
| * Given an expression, determine if it it is a JsNameRef that refers to a |
| * statically-defined JsFunction. |
| */ |
| private static JsFunction isFunction(JsExpression e) { |
| if (e instanceof JsNameRef) { |
| JsNameRef ref = (JsNameRef) e; |
| |
| // Unravel foo.call(...). |
| if (!ref.getName().isObfuscatable() && "call".equals(ref.getIdent())) { |
| if (ref.getQualifier() instanceof JsNameRef) { |
| ref = (JsNameRef) ref.getQualifier(); |
| } |
| } |
| |
| JsNode staticRef = ref.getName().getStaticRef(); |
| if (staticRef instanceof JsFunction) { |
| return (JsFunction) staticRef; |
| } |
| } |
| |
| return null; |
| } |
| |
| /** |
| * Determine if a statement can be inlined into a call site. |
| */ |
| private static boolean isInlinable(JsFunction caller, JsFunction callee, |
| JsExpression thisExpr, List<JsExpression> arguments, JsNode toInline) { |
| |
| /* |
| * This will happen with varargs-style JavaScript functions that rely on the |
| * "arguments" array. The reference to arguments would be detected in |
| * BoundedScopeVisitor, but the code below assumes the same number of |
| * parameters and arguments. |
| */ |
| if (arguments.size() != callee.getParameters().size()) { |
| return false; |
| } |
| |
| // Build up a list of all parameter names |
| Set<JsName> parameterNames = new HashSet<JsName>(); |
| Set<String> parameterIdents = new HashSet<String>(); |
| for (JsParameter param : callee.getParameters()) { |
| parameterNames.add(param.getName()); |
| parameterIdents.add(param.getName().getIdent()); |
| } |
| |
| /* |
| * Make sure that inlining won't change the final name of non-parameter |
| * idents due to the change of scope. The most likely cause would be the use |
| * of an unqualified variable reference in a JSNI block that happened to |
| * conflict with a Java-derived identifier. |
| */ |
| StableNameChecker detector = new StableNameChecker(caller.getScope(), |
| callee.getScope(), parameterNames); |
| detector.accept(toInline); |
| if (!detector.isStable()) { |
| return false; |
| } |
| |
| /* |
| * Ensure that the names referred to by the argument list and the statement |
| * are disjoint. This prevents inlining of the following: |
| * |
| * static int i; public void add(int a) { i += a; }; add(i++); |
| */ |
| if (hasCommonIdents(arguments, toInline, parameterIdents)) { |
| return false; |
| } |
| |
| List<JsExpression> evalArgs; |
| if (thisExpr == null) { |
| evalArgs = arguments; |
| } else { |
| evalArgs = new ArrayList<JsExpression>(1 + arguments.size()); |
| evalArgs.add(thisExpr); |
| evalArgs.addAll(arguments); |
| } |
| |
| /* |
| * Determine if the evaluation of the invocation's arguments may create side |
| * effects. This will determine how aggressively the parameters may be |
| * reordered. |
| */ |
| if (isVolatile(evalArgs, caller)) { |
| /* |
| * Determine the order in which the parameters must be evaluated. This |
| * will vary between call sites, based on whether or not the invocation's |
| * arguments can be repeated without ill effect. |
| */ |
| List<JsName> requiredOrder = new ArrayList<JsName>(); |
| if (thisExpr != null && isVolatile(thisExpr, callee)) { |
| requiredOrder.add(EvaluationOrderVisitor.THIS_NAME); |
| } |
| for (int i = 0; i < arguments.size(); i++) { |
| JsExpression e = arguments.get(i); |
| JsParameter p = callee.getParameters().get(i); |
| |
| if (isVolatile(e, callee)) { |
| requiredOrder.add(p.getName()); |
| } |
| } |
| |
| // This would indicate that isVolatile changed its output between |
| // the if statement and the loop. |
| assert requiredOrder.size() > 0; |
| |
| /* |
| * Verify that the non-reorderable arguments are evaluated in the right |
| * order. |
| */ |
| EvaluationOrderVisitor orderVisitor = new EvaluationOrderVisitor( |
| requiredOrder, callee); |
| orderVisitor.accept(toInline); |
| if (!orderVisitor.maintainsOrder()) { |
| return false; |
| } |
| } |
| |
| // Check that parameters aren't used in such a way as to prohibit inlining |
| ParameterUsageVisitor v = new ParameterUsageVisitor(thisExpr != null, |
| parameterNames); |
| v.accept(toInline); |
| if (v.hasViolation()) { |
| return false; |
| } |
| |
| // Hooray! |
| return true; |
| } |
| |
| /** |
| * This is used in combination with {@link #hoistedExpression(JsStatement)} to |
| * indicate if a given statement would terminate the list of hoisted |
| * expressions. |
| */ |
| private static boolean isReturnStatement(JsStatement statement) { |
| return statement instanceof JsReturn; |
| } |
| |
| /** |
| * Indicates if an expression would create side effects or possibly be |
| * affected by side effects when evaluated within a particular function |
| * context. |
| */ |
| private static boolean isVolatile(JsExpression e, JsFunction context) { |
| return isVolatile(Collections.singletonList(e), context); |
| } |
| |
| /** |
| * Indicates if a list of expressions would create side effects or possibly be |
| * affected by side effects when evaluated within a particular function |
| * context. |
| */ |
| private static boolean isVolatile(List<JsExpression> list, JsFunction context) { |
| return hasSideEffects(list) || affectedBySideEffects(list, context); |
| } |
| |
| /** |
| * Transforms any <code>foo.call(this)</code> into <code>this.foo()</code> to |
| * be compatible with our inlining algorithm. |
| */ |
| private static JsInvocation tryToUnravelExplicitCall(JsInvocation x) { |
| if (!(x.getQualifier() instanceof JsNameRef)) { |
| return x; |
| } |
| JsNameRef ref = (JsNameRef) x.getQualifier(); |
| if (ref.getName().isObfuscatable() || !"call".equals(ref.getIdent())) { |
| return x; |
| } |
| List<JsExpression> oldArgs = x.getArguments(); |
| if (oldArgs.size() < 1) { |
| return x; |
| } |
| |
| JsNameRef oldTarget = (JsNameRef) ref.getQualifier(); |
| JsNameRef newTarget = new JsNameRef(oldTarget.getSourceInfo(), |
| oldTarget.getName()); |
| newTarget.setQualifier(oldArgs.get(0)); |
| JsInvocation newCall = new JsInvocation(x.getSourceInfo()); |
| newCall.setQualifier(newTarget); |
| // Don't have to clone because the returned invocation is transient. |
| newCall.getArguments().addAll(oldArgs.subList(1, oldArgs.size())); |
| return newCall; |
| } |
| |
| /** |
| * Utility class. |
| */ |
| private JsInliner() { |
| } |
| } |
