Compiler now inlines many more types of methods in the Java AST. Includes new tests to check for inlining bugs.
Issue: #1787
Patch by: mmastrac, scottb
Review by: scottb, mmastrac
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@1507 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/CloneExpressionVisitor.java b/dev/core/src/com/google/gwt/dev/jjs/impl/CloneExpressionVisitor.java
new file mode 100644
index 0000000..4d815eb
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/jjs/impl/CloneExpressionVisitor.java
@@ -0,0 +1,270 @@
+/*
+ * Copyright 2007 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.jjs.impl;
+
+import com.google.gwt.dev.jjs.InternalCompilerException;
+import com.google.gwt.dev.jjs.ast.Context;
+import com.google.gwt.dev.jjs.ast.JAbsentArrayDimension;
+import com.google.gwt.dev.jjs.ast.JArrayRef;
+import com.google.gwt.dev.jjs.ast.JBinaryOperation;
+import com.google.gwt.dev.jjs.ast.JBooleanLiteral;
+import com.google.gwt.dev.jjs.ast.JCastOperation;
+import com.google.gwt.dev.jjs.ast.JCharLiteral;
+import com.google.gwt.dev.jjs.ast.JClassLiteral;
+import com.google.gwt.dev.jjs.ast.JConditional;
+import com.google.gwt.dev.jjs.ast.JDoubleLiteral;
+import com.google.gwt.dev.jjs.ast.JExpression;
+import com.google.gwt.dev.jjs.ast.JFieldRef;
+import com.google.gwt.dev.jjs.ast.JFloatLiteral;
+import com.google.gwt.dev.jjs.ast.JInstanceOf;
+import com.google.gwt.dev.jjs.ast.JIntLiteral;
+import com.google.gwt.dev.jjs.ast.JLocalRef;
+import com.google.gwt.dev.jjs.ast.JLongLiteral;
+import com.google.gwt.dev.jjs.ast.JMethodCall;
+import com.google.gwt.dev.jjs.ast.JNewArray;
+import com.google.gwt.dev.jjs.ast.JNewInstance;
+import com.google.gwt.dev.jjs.ast.JNullLiteral;
+import com.google.gwt.dev.jjs.ast.JParameterRef;
+import com.google.gwt.dev.jjs.ast.JPostfixOperation;
+import com.google.gwt.dev.jjs.ast.JPrefixOperation;
+import com.google.gwt.dev.jjs.ast.JProgram;
+import com.google.gwt.dev.jjs.ast.JStringLiteral;
+import com.google.gwt.dev.jjs.ast.JThisRef;
+import com.google.gwt.dev.jjs.ast.JVisitor;
+import com.google.gwt.dev.jjs.ast.js.JClassSeed;
+import com.google.gwt.dev.jjs.ast.js.JMultiExpression;
+
+import java.util.ArrayList;
+
+/**
+ * A general purpose expression cloner.
+ */
+public class CloneExpressionVisitor extends JVisitor {
+ private JExpression expression;
+ private JProgram program;
+
+ public CloneExpressionVisitor(JProgram program) {
+ this.program = program;
+ }
+
+ public JExpression cloneExpression(JExpression expr) {
+ if (expr == null) {
+ return null;
+ }
+
+ this.accept(expr);
+
+ if (expression == null) {
+ throw new InternalCompilerException(expr, "Unable to clone expression",
+ null);
+ }
+
+ return expression;
+ }
+
+ @Override
+ public boolean visit(JAbsentArrayDimension x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JArrayRef x, Context ctx) {
+ expression = new JArrayRef(program, x.getSourceInfo(),
+ cloneExpression(x.getInstance()), cloneExpression(x.getIndexExpr()));
+ return false;
+ }
+
+ @Override
+ public boolean visit(JBinaryOperation x, Context ctx) {
+ expression = new JBinaryOperation(program, x.getSourceInfo(), x.getType(),
+ x.getOp(), cloneExpression(x.getLhs()), cloneExpression(x.getRhs()));
+ return false;
+ }
+
+ @Override
+ public boolean visit(JBooleanLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JCastOperation x, Context ctx) {
+ expression = new JCastOperation(program, x.getSourceInfo(),
+ x.getCastType(), cloneExpression(x.getExpr()));
+ return false;
+ }
+
+ @Override
+ public boolean visit(JCharLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JClassLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JClassSeed x, Context ctx) {
+ expression = new JClassSeed(program, x.getRefType());
+ return false;
+ }
+
+ @Override
+ public boolean visit(JConditional x, Context ctx) {
+ expression = new JConditional(program, x.getSourceInfo(), x.getType(),
+ cloneExpression(x.getIfTest()), cloneExpression(x.getThenExpr()),
+ cloneExpression(x.getElseExpr()));
+ return false;
+ }
+
+ @Override
+ public boolean visit(JDoubleLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JFieldRef x, Context ctx) {
+ expression = new JFieldRef(program, x.getSourceInfo(),
+ cloneExpression(x.getInstance()), x.getField(), x.getEnclosingType());
+ return false;
+ }
+
+ @Override
+ public boolean visit(JFloatLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JInstanceOf x, Context ctx) {
+ expression = new JInstanceOf(program, x.getSourceInfo(), x.getTestType(),
+ cloneExpression(x.getExpr()));
+ return false;
+ }
+
+ @Override
+ public boolean visit(JIntLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JLocalRef x, Context ctx) {
+ expression = new JLocalRef(program, x.getSourceInfo(), x.getLocal());
+ return false;
+ }
+
+ @Override
+ public boolean visit(JLongLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JMethodCall x, Context ctx) {
+ JMethodCall newMethodCall = new JMethodCall(program, x.getSourceInfo(),
+ cloneExpression(x.getInstance()), x.getTarget());
+
+ for (JExpression arg : x.getArgs()) {
+ newMethodCall.getArgs().add(cloneExpression(arg));
+ }
+
+ expression = newMethodCall;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JMultiExpression x, Context ctx) {
+ JMultiExpression multi = new JMultiExpression(program, x.getSourceInfo());
+ for (JExpression expr : x.exprs) {
+ multi.exprs.add(cloneExpression(expr));
+ }
+
+ expression = multi;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JNewArray x, Context ctx) {
+ JNewArray newArray = new JNewArray(program, x.getSourceInfo(),
+ x.getArrayType());
+
+ if (x.dims != null) {
+ newArray.dims = new ArrayList<JExpression>();
+ for (JExpression dim : x.dims) {
+ newArray.dims.add(cloneExpression(dim));
+ }
+ }
+ if (x.initializers != null) {
+ newArray.initializers = new ArrayList<JExpression>();
+ for (JExpression initializer : x.initializers) {
+ newArray.initializers.add(cloneExpression(initializer));
+ }
+ }
+
+ expression = newArray;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JNewInstance x, Context ctx) {
+ expression = new JNewInstance(program, x.getSourceInfo(), x.getClassType());
+ return false;
+ }
+
+ @Override
+ public boolean visit(JNullLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JParameterRef x, Context ctx) {
+ expression = new JParameterRef(program, x.getSourceInfo(), x.getParameter());
+ return false;
+ }
+
+ @Override
+ public boolean visit(JPostfixOperation x, Context ctx) {
+ expression = new JPostfixOperation(program, x.getSourceInfo(), x.getOp(),
+ cloneExpression(x.getArg()));
+ return false;
+ }
+
+ @Override
+ public boolean visit(JPrefixOperation x, Context ctx) {
+ expression = new JPrefixOperation(program, x.getSourceInfo(), x.getOp(),
+ cloneExpression(x.getArg()));
+ return false;
+ }
+
+ @Override
+ public boolean visit(JStringLiteral x, Context ctx) {
+ expression = x;
+ return false;
+ }
+
+ @Override
+ public boolean visit(JThisRef x, Context ctx) {
+ expression = program.getExprThisRef(x.getSourceInfo(), x.getClassType());
+ return false;
+ }
+}
\ No newline at end of file
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/DeadCodeElimination.java b/dev/core/src/com/google/gwt/dev/jjs/impl/DeadCodeElimination.java
index 0f084e2..27268b3 100644
--- a/dev/core/src/com/google/gwt/dev/jjs/impl/DeadCodeElimination.java
+++ b/dev/core/src/com/google/gwt/dev/jjs/impl/DeadCodeElimination.java
@@ -38,6 +38,7 @@
import com.google.gwt.dev.jjs.ast.JMethod;
import com.google.gwt.dev.jjs.ast.JMethodCall;
import com.google.gwt.dev.jjs.ast.JModVisitor;
+import com.google.gwt.dev.jjs.ast.JNode;
import com.google.gwt.dev.jjs.ast.JPrefixOperation;
import com.google.gwt.dev.jjs.ast.JProgram;
import com.google.gwt.dev.jjs.ast.JReferenceType;
@@ -70,6 +71,11 @@
public class DeadCodeVisitor extends JModVisitor {
/**
+ * An expression whose result does not matter.
+ */
+ private JExpression ignoringExpressionOutput;
+
+ /**
* Short circuit binary operations.
*/
@Override
@@ -294,7 +300,11 @@
*/
@Override
public void endVisit(JMultiExpression x, Context ctx) {
- for (int i = 0; i < x.exprs.size() - 1; i++) {
+ /*
+ * If we're ignoring the output of this expression, we don't need to
+ * maintain the final multi value.
+ */
+ for (int i = 0; i < numRemovableExpressions(x); i++) {
JExpression expr = x.exprs.get(i);
if (!expr.hasSideEffects()) {
x.exprs.remove(i);
@@ -302,6 +312,14 @@
continue;
}
+ // Remove nested JMultiExpressions
+ if (expr instanceof JMultiExpression) {
+ x.exprs.remove(i);
+ x.exprs.addAll(i, ((JMultiExpression) expr).exprs);
+ i--;
+ continue;
+ }
+
if (expr instanceof JFieldRef) {
JFieldRef fieldRef = (JFieldRef) expr;
JExpression instance = fieldRef.getInstance();
@@ -449,6 +467,12 @@
}
}
+ @Override
+ public boolean visit(JExpressionStatement x, Context ctx) {
+ ignoringExpressionOutput = x.getExpr();
+ return true;
+ }
+
private boolean hasNoDefaultCase(JSwitchStatement x) {
JBlock body = x.getBody();
boolean inDefault = false;
@@ -498,6 +522,16 @@
return typeClassMap.get(type);
}
+ private int numRemovableExpressions(JMultiExpression x) {
+ if (x == ignoringExpressionOutput) {
+ // All expressions can be removed.
+ return x.exprs.size();
+ } else {
+ // The last expression cannot be removed.
+ return x.exprs.size() - 1;
+ }
+ }
+
/**
* Removes any break statements that appear one after another.
*/
@@ -737,7 +771,11 @@
}
public static boolean exec(JProgram program) {
- return new DeadCodeElimination(program).execImpl();
+ return new DeadCodeElimination(program).execImpl(program);
+ }
+
+ public static boolean exec(JProgram program, JNode node) {
+ return new DeadCodeElimination(program).execImpl(node);
}
private final JProgram program;
@@ -758,11 +796,11 @@
typeClassMap.put(program.getTypePrimitiveShort(), short.class);
}
- private boolean execImpl() {
+ private boolean execImpl(JNode node) {
boolean madeChanges = false;
while (true) {
DeadCodeVisitor deadCodeVisitor = new DeadCodeVisitor();
- deadCodeVisitor.accept(program);
+ deadCodeVisitor.accept(node);
if (!deadCodeVisitor.didChange()) {
break;
}
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/ExpressionAnalyzer.java b/dev/core/src/com/google/gwt/dev/jjs/impl/ExpressionAnalyzer.java
new file mode 100644
index 0000000..8450eb2
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/jjs/impl/ExpressionAnalyzer.java
@@ -0,0 +1,285 @@
+/*
+ * Copyright 2007 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.jjs.impl;
+
+import com.google.gwt.dev.jjs.ast.Context;
+import com.google.gwt.dev.jjs.ast.JArrayRef;
+import com.google.gwt.dev.jjs.ast.JBinaryOperation;
+import com.google.gwt.dev.jjs.ast.JBinaryOperator;
+import com.google.gwt.dev.jjs.ast.JCastOperation;
+import com.google.gwt.dev.jjs.ast.JConditional;
+import com.google.gwt.dev.jjs.ast.JExpression;
+import com.google.gwt.dev.jjs.ast.JFieldRef;
+import com.google.gwt.dev.jjs.ast.JIntLiteral;
+import com.google.gwt.dev.jjs.ast.JLocalRef;
+import com.google.gwt.dev.jjs.ast.JMethodCall;
+import com.google.gwt.dev.jjs.ast.JNewArray;
+import com.google.gwt.dev.jjs.ast.JNewInstance;
+import com.google.gwt.dev.jjs.ast.JParameterRef;
+import com.google.gwt.dev.jjs.ast.JPostfixOperation;
+import com.google.gwt.dev.jjs.ast.JPrefixOperation;
+import com.google.gwt.dev.jjs.ast.JThisRef;
+import com.google.gwt.dev.jjs.ast.JVisitor;
+
+/**
+ * Analyzes an expression and make a number of static analysis flags available
+ * based on the information available solely through the expression.
+ *
+ * TODO: make this even smarter when we have real null analysis.
+ */
+public class ExpressionAnalyzer extends JVisitor {
+ private boolean accessesField;
+ private boolean accessesLocal;
+ private boolean accessesParameter;
+ private boolean assignmentToField;
+ private boolean assignmentToLocal;
+ private boolean assignmentToParameter;
+ private boolean canThrowException;
+ private boolean createsObject;
+ private int inConditional;
+
+ /**
+ * Does this expression read or write fields within the scope of the
+ * expression?
+ */
+ public boolean accessesField() {
+ return accessesField;
+ }
+
+ /**
+ * Does this expression read or write locals within the scope of the
+ * expression?
+ */
+ public boolean accessesLocal() {
+ return accessesLocal;
+ }
+
+ /**
+ * Does this expression read or write parameters within the scope of the
+ * expression?
+ */
+ public boolean accessesParameter() {
+ return accessesParameter;
+ }
+
+ public boolean canThrowException() {
+ return canThrowException;
+ }
+
+ public boolean createsObject() {
+ return createsObject;
+ }
+
+ @Override
+ public void endVisit(JArrayRef x, Context ctx) {
+ /*
+ * In Java, array references can throw IndexOutOfBoundsExceptions, but this
+ * isn't the case for current GWT generated code. If we add a strict array
+ * bounds check later, this flag would need to reflect it.
+ */
+
+ // If JArrayRef is null, this can throw a NullPointerException.
+ canThrowException = true;
+ }
+
+ @Override
+ public void endVisit(JBinaryOperation x, Context ctx) {
+ if (x.isAssignment()) {
+ JExpression lhs = x.getLhs();
+ if (lhs instanceof JArrayRef) {
+ // Array store operations can throw ArrayStoreExceptions
+ canThrowException = true;
+ } else {
+ analyzeStore(lhs);
+ }
+ }
+ }
+
+ @Override
+ public void endVisit(JCastOperation x, Context ctx) {
+ // Can throw ClassCastException
+ canThrowException = true;
+ }
+
+ @Override
+ public void endVisit(JFieldRef x, Context ctx) {
+ accessesField = true;
+
+ JExpression instance = x.getInstance();
+
+ // Field references using this are always safe
+ if (instance instanceof JThisRef) {
+ return;
+ }
+
+ /*
+ * We don't have enough information at this point to determine that a field
+ * reference is guaranteed to be safe.
+ *
+ * If a field reference is static, it can throw exceptions via a clinit().
+ *
+ * If a field is not static and isn't accessed using "this", the instance
+ * expression may be null.
+ */
+ canThrowException = true;
+ }
+
+ @Override
+ public void endVisit(JLocalRef x, Context ctx) {
+ accessesLocal = true;
+ }
+
+ @Override
+ public void endVisit(JMethodCall x, Context ctx) {
+ /*
+ * We can't assume anything about method calls right now, except that it
+ * can't assign to one of our locals or one of our parameters. It's possible
+ * that it could read from a field, assign to a field or throw an exception
+ * that we can't see.
+ */
+ assignmentToField = true;
+ accessesField = true;
+ canThrowException = true;
+ }
+
+ @Override
+ public void endVisit(JNewArray x, Context ctx) {
+ /*
+ * If no array bounds, the new array is being automatically initialized. If
+ * there are side-effects, they'll show up when we visit the initializers.
+ */
+ if (x.dims == null) {
+ return;
+ }
+
+ /*
+ * Can throw NegativeArraySizeException if we initialize an array with
+ * negative dimensions.
+ */
+ for (JExpression expression : x.dims) {
+ if (expression instanceof JIntLiteral) {
+ int value = ((JIntLiteral) expression).getValue();
+ if (value >= 0) {
+ continue;
+ }
+ }
+ canThrowException = true;
+ }
+ }
+
+ @Override
+ public void endVisit(JNewInstance x, Context ctx) {
+ /*
+ * Due to implementation details, a new instance operation has no other
+ * possible side-effects.
+ */
+ createsObject = true;
+ }
+
+ @Override
+ public void endVisit(JParameterRef x, Context ctx) {
+ accessesParameter = true;
+ }
+
+ @Override
+ public void endVisit(JPostfixOperation x, Context ctx) {
+ // Unary operations that are modifying cause assignment side-effects.
+ if (x.getOp().isModifying()) {
+ analyzeStore(x.getArg());
+ }
+ }
+
+ @Override
+ public void endVisit(JPrefixOperation x, Context ctx) {
+ // Unary operations that are modifying cause assignment side-effects.
+ if (x.getOp().isModifying()) {
+ analyzeStore(x.getArg());
+ }
+ }
+
+ /**
+ * Does this expression make assignments to variables within the scope of the
+ * expression?
+ */
+ public boolean hasAssignment() {
+ return assignmentToField || assignmentToLocal || assignmentToParameter;
+ }
+
+ /**
+ * Does this expression make assignments to fields within the scope of the
+ * expression?
+ */
+ public boolean hasAssignmentToField() {
+ return assignmentToField;
+ }
+
+ /**
+ * Does this expression make assignments to locals within the scope of the
+ * expression?
+ */
+ public boolean hasAssignmentToLocal() {
+ return assignmentToLocal;
+ }
+
+ /**
+ * Does this expression make assignments to parameters within the scope of the
+ * expression?
+ */
+ public boolean hasAssignmentToParameter() {
+ return assignmentToParameter;
+ }
+
+ @Override
+ public boolean visit(JBinaryOperation x, Context ctx) {
+ if (x.getOp() == JBinaryOperator.AND || x.getOp() == JBinaryOperator.OR) {
+ accept(x.getLhs());
+ inConditional++;
+ accept(x.getRhs());
+ inConditional--;
+ return false;
+ }
+ return true;
+ }
+
+ @Override
+ public boolean visit(JConditional x, Context ctx) {
+ accept(x.getIfTest());
+ inConditional++;
+ accept(x.getThenExpr());
+ accept(x.getElseExpr());
+ inConditional--;
+
+ return false;
+ }
+
+ /**
+ * Determined if the current expression conditionally executes, based on its
+ * parent expressions.
+ */
+ protected boolean isInConditional() {
+ return inConditional > 0;
+ }
+
+ private void analyzeStore(JExpression expr) {
+ if (expr instanceof JFieldRef) {
+ assignmentToField = true;
+ } else if (expr instanceof JParameterRef) {
+ assignmentToParameter = true;
+ } else if (expr instanceof JLocalRef) {
+ assignmentToLocal = true;
+ }
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodInliner.java b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodInliner.java
index 24158dd..941ac34 100644
--- a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodInliner.java
+++ b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodInliner.java
@@ -15,14 +15,11 @@
*/
package com.google.gwt.dev.jjs.impl;
-import com.google.gwt.dev.jjs.SourceInfo;
+import com.google.gwt.dev.jjs.InternalCompilerException;
import com.google.gwt.dev.jjs.ast.Context;
-import com.google.gwt.dev.jjs.ast.JBlock;
import com.google.gwt.dev.jjs.ast.JExpression;
import com.google.gwt.dev.jjs.ast.JExpressionStatement;
-import com.google.gwt.dev.jjs.ast.JField;
-import com.google.gwt.dev.jjs.ast.JFieldRef;
-import com.google.gwt.dev.jjs.ast.JLiteral;
+import com.google.gwt.dev.jjs.ast.JLocalRef;
import com.google.gwt.dev.jjs.ast.JMethod;
import com.google.gwt.dev.jjs.ast.JMethodBody;
import com.google.gwt.dev.jjs.ast.JMethodCall;
@@ -33,73 +30,84 @@
import com.google.gwt.dev.jjs.ast.JReferenceType;
import com.google.gwt.dev.jjs.ast.JReturnStatement;
import com.google.gwt.dev.jjs.ast.JStatement;
-import com.google.gwt.dev.jjs.ast.JVisitor;
+import com.google.gwt.dev.jjs.ast.JThisRef;
import com.google.gwt.dev.jjs.ast.js.JMultiExpression;
import java.util.ArrayList;
import java.util.HashSet;
-import java.util.Iterator;
import java.util.List;
import java.util.Set;
/**
- * Inline methods that can be inlined.
+ * Inline methods that can be inlined. The current implementation limits the
+ * methods that can be inlined to those that are composed of at most two
+ * top-level expressions.
*
- * TODO(later): more aggressive inlining
+ * Future improvements will allow more complex methods to be inlined based on
+ * the number of call sites, as well as adding support for more complex target
+ * method expressions.
*/
public class MethodInliner {
/**
- * Flattens <code>JMultiExpressions</code> where possible.
- *
- * TODO: make this a JModVisitor
+ * Clones an expression, ensuring no local or this refs.
*/
- public class FlattenMultiVisitor extends JVisitor {
+ private class CloneCalleeExpressionVisitor extends CloneExpressionVisitor {
- private boolean didChange = false;
-
- @Override
- public boolean didChange() {
- return didChange;
+ public CloneCalleeExpressionVisitor() {
+ super(program);
}
@Override
- public void endVisit(JMultiExpression x, Context ctx) {
- ArrayList<JExpression> exprs = x.exprs;
+ public boolean visit(JLocalRef x, Context ctx) {
+ throw new InternalCompilerException(
+ "Unable to clone a local reference in a function being inlined");
+ }
- /*
- * Add the contents of all nested multis into the top multi, in place. We
- * are in fact iterating over nodes we've just added, but that should be
- * okay as the children will already be flattened.
- */
- for (int i = 0; i < exprs.size(); ++i) {
- JExpression expr = exprs.get(i);
- if (expr instanceof JMultiExpression) {
- JMultiExpression sub = (JMultiExpression) expr;
- exprs.addAll(i + 1, sub.exprs);
- didChange = true;
- }
- }
-
- // now remove the old multis
- for (Iterator<JExpression> it = exprs.iterator(); it.hasNext();) {
- JExpression expr = it.next();
- if (expr instanceof JMultiExpression) {
- it.remove();
- didChange = true;
- }
- }
+ @Override
+ public boolean visit(JThisRef x, Context ctx) {
+ throw new InternalCompilerException("Should not encounter a JThisRef "
+ + "within a static method");
}
}
+
+ /**
+ * Replace parameters inside an inlined expression with arguments to the
+ * inlined method.
+ */
+ private class ParameterReplacer extends JModVisitor {
+ private final JMethodCall methodCall;
+
+ public ParameterReplacer(JMethodCall methodCall) {
+ this.methodCall = methodCall;
+ }
+
+ @Override
+ public void endVisit(JParameterRef x, Context ctx) {
+ int paramIndex = methodCall.getTarget().params.indexOf(x.getParameter());
+ assert paramIndex != -1;
+
+ // Replace with a cloned call argument.
+ CloneExpressionVisitor cloner = new CloneExpressionVisitor(program);
+ JExpression arg = methodCall.getArgs().get(paramIndex);
+ JExpression clone = cloner.cloneExpression(arg);
+ ctx.replaceMe(clone);
+ }
+ }
+
/**
* Method inlining visitor.
*/
- public class InliningVisitor extends JModVisitor {
+ private class InliningVisitor extends JModVisitor {
+
+ protected final Set<JMethod> modifiedMethods = new HashSet<JMethod>();
+
/**
* Resets with each new visitor, which is good since things that couldn't be
- * inlined before might become inlineable.
+ * inlined before might become inlinable.
*/
- Set<JMethod> cannotInline = new HashSet<JMethod>();
+ private final Set<JMethod> cannotInline = new HashSet<JMethod>();
+ private JExpression ignoringReturnValueFor;
@Override
public void endVisit(JMethod x, Context ctx) {
@@ -110,8 +118,8 @@
public void endVisit(JMethodCall x, Context ctx) {
JMethod method = x.getTarget();
- // The method call must be known statically.
- if (!method.isStatic() || method.isNative()) {
+ if (currentMethod == method) {
+ // Never try to inline a recursive call!
return;
}
@@ -119,289 +127,332 @@
return;
}
- JMethodBody body = (JMethodBody) method.getBody();
- List<JStatement> stmts = body.getStatements();
boolean possibleToInline = false;
- // clinit() calls cannot be inlined unless they are empty
- if (method.getEnclosingType() != null
- && method.getEnclosingType().methods.get(0) == method
- && !stmts.isEmpty()) {
- return;
- }
+ if (method.isStatic() && !method.isNative()) {
+ JMethodBody body = (JMethodBody) method.getBody();
+ List<JStatement> stmts = body.getStatements();
- if (stmts.isEmpty()) {
- tryInlineEmptyMethodCall(x, ctx);
- possibleToInline = true;
- } else if (stmts.size() == 1) {
- JStatement stmt = stmts.get(0);
- if (stmt instanceof JReturnStatement) {
- possibleToInline = tryInlineExpression(x, ctx,
- ((JReturnStatement) stmt).getExpr());
- } else if (stmt instanceof JExpressionStatement) {
- possibleToInline = tryInlineExpression(x, ctx,
- ((JExpressionStatement) stmt).getExpr());
+ if (method.getEnclosingType() != null
+ && method.getEnclosingType().methods.get(0) == method
+ && !stmts.isEmpty()) {
+ // clinit() calls cannot be inlined unless they are empty
+ possibleToInline = false;
+ } else {
+ JMultiExpression multi = createMultiExpressionFromBody(body,
+ ignoringReturnValueFor == x);
+ if (multi != null) {
+ possibleToInline = tryInlineExpression(x, ctx, multi);
+ }
}
}
+ // If it will never be possible to inline the method, add it to a
+ // blacklist
if (!possibleToInline) {
cannotInline.add(method);
}
}
@Override
+ public boolean visit(JExpressionStatement x, Context ctx) {
+ ignoringReturnValueFor = x.getExpr();
+ return true;
+ }
+
+ @Override
public boolean visit(JMethod x, Context ctx) {
currentMethod = x;
return true;
}
- /**
- * This complicated method has a simple purpose: see if the expression part
- * of a return statement is inlinable. The trickiness comes from the fact
- * that we'd like to be able to do this recursively in certain cases. For
- * example, the accessor method
- *
- * <pre>
- * $getFoo(this$static) {
- * return this$static.foo
- * }
- * </pre>
- *
- * should be inlinable, but we have to first examine the field reference and
- * then recursively determine that the qualifier is inlinable.
- */
- private JExpression canInlineExpression(SourceInfo info,
- JExpression targetExpr, List<JParameter> params,
- ArrayList<JExpression> args, int[] magicArg) {
- if (targetExpr instanceof JLiteral) {
- // just reference the same JLiteral
- /*
- * hackish: pretend there is an arg that is returned which comes after
- * all the real args; this allows the evaluation order check in
- * tryInlineSimpleMethodCall to succeed
- */
- magicArg[0] = args.size();
- return targetExpr;
- } else if (targetExpr instanceof JParameterRef) {
- // translate the param ref into the appropriate arg
- int i = params.indexOf(((JParameterRef) targetExpr).getTarget());
- assert (i >= 0);
- magicArg[0] = i;
- return args.get(i);
- } else if (targetExpr instanceof JFieldRef) {
- JFieldRef oldFieldRef = (JFieldRef) targetExpr;
- JField field = oldFieldRef.getField();
- JExpression instance = oldFieldRef.getInstance();
- if (instance != null) {
- // If an instance field, we have to be able to inline the qualifier
- instance = canInlineExpression(info, instance, params, args, magicArg);
- if (instance == null) {
- return null;
- }
- }
- JFieldRef newFieldRef = new JFieldRef(program, info, instance, field,
- currentMethod.getEnclosingType());
- return newFieldRef;
- } else {
- /*
- * For now, only inline REALLY trivial stuff since we have no way of
- * cloning arbitrary expressions.
- */
- return null;
- }
- }
-
- /**
- * Returns <code>true</code> if inlining the target expression would
- * eliminate a necessary clinit.
- */
- private boolean checkClinitViolation(JMethodCall x,
- JExpression resultExpression) {
+ private JMethodCall createClinitCall(JMethodCall x) {
JReferenceType targetEnclosingType = x.getTarget().getEnclosingType();
if (!program.typeOracle.checkClinit(currentMethod.getEnclosingType(),
targetEnclosingType)) {
// Access from this class to the target class won't trigger a clinit
- return false;
+ return null;
}
if (program.isStaticImpl(x.getTarget())) {
// No clinit needed; target is really an instance method.
+ return null;
+ }
+ if (x.getTarget() == x.getTarget().getEnclosingType().methods.get(0)) {
+ // This is a clinit call, doesn't need another clinit
+ return null;
+ }
+
+ JMethod clinit = targetEnclosingType.methods.get(0);
+
+ // If the clinit is a non-native, empty body we can optimize it out here
+ if (!clinit.isNative()
+ && (((JMethodBody) clinit.getBody())).getStatements().size() == 0) {
+ return null;
+ }
+
+ return new JMethodCall(program, x.getSourceInfo(), null, clinit);
+ }
+
+ /**
+ * Creates a multi expression for evaluating a method call instance and
+ * possible clinit. This is a precursor for inlining the remainder of a
+ * method.
+ */
+ private JMultiExpression createMultiExpressionForInstanceAndClinit(
+ JMethodCall x) {
+ JMultiExpression multi = new JMultiExpression(program, x.getSourceInfo());
+
+ // Any instance expression goes first (this can happen even with statics).
+ if (x.getInstance() != null) {
+ multi.exprs.add(x.getInstance());
+ }
+
+ // If we need a clinit call, add it first
+ JMethodCall clinit = createClinitCall(x);
+ if (clinit != null) {
+ multi.exprs.add(clinit);
+ }
+ return multi;
+ }
+
+ /**
+ * Creates a JMultiExpression from a set of JExpressionStatements,
+ * optionally terminated by a JReturnStatement. If the method doesn't match
+ * this pattern, it returns <code>null</code>.
+ *
+ * If a method has a non-void return statement and can be represented as a
+ * multi-expression, the output of the multi-expression will be the return
+ * expression of the method. If the method is void, the output of the
+ * multi-expression should be considered undefined.
+ */
+ private JMultiExpression createMultiExpressionFromBody(JMethodBody body,
+ boolean ignoringReturnValue) {
+ JMultiExpression multi = new JMultiExpression(program,
+ body.getSourceInfo());
+ CloneCalleeExpressionVisitor cloner = new CloneCalleeExpressionVisitor();
+
+ for (JStatement stmt : body.getStatements()) {
+ if (stmt instanceof JExpressionStatement) {
+ JExpressionStatement exprStmt = (JExpressionStatement) stmt;
+ JExpression expr = exprStmt.getExpr();
+ JExpression clone = cloner.cloneExpression(expr);
+ multi.exprs.add(clone);
+ } else if (stmt instanceof JReturnStatement) {
+ JReturnStatement returnStatement = (JReturnStatement) stmt;
+ JExpression expr = returnStatement.getExpr();
+ if (expr != null) {
+ if (!ignoringReturnValue || expr.hasSideEffects()) {
+ JExpression clone = cloner.cloneExpression(expr);
+ multi.exprs.add(clone);
+ }
+ }
+ // We hit an unconditional return; no need to evaluate anything else.
+ break;
+ } else {
+ // Any other kind of statement won't be inlinable.
+ return null;
+ }
+ }
+
+ return multi;
+ }
+
+ /**
+ * Creates a multi expression for evaluating a method call instance,
+ * possible clinit, and all arguments. This is a precursor for inlining the
+ * remainder of a method that does not reference any parameters.
+ */
+ private JMultiExpression createMultiExpressionIncludingArgs(JMethodCall x) {
+ JMultiExpression multi = createMultiExpressionForInstanceAndClinit(x);
+
+ for (int i = 0, c = x.getArgs().size(); i < c; ++i) {
+ JExpression arg = x.getArgs().get(i);
+ ExpressionAnalyzer analyzer = new ExpressionAnalyzer();
+ analyzer.accept(arg);
+
+ if (analyzer.hasAssignment() || analyzer.canThrowException()) {
+ multi.exprs.add(arg);
+ }
+ }
+ return multi;
+ }
+
+ /**
+ * Replace the current expression with a given multi-expression and mark the
+ * method as modified. The dead-code elimination pass will optimize this if
+ * necessary.
+ */
+ private void replaceWithMulti(Context ctx, JMultiExpression multi) {
+ ctx.replaceMe(multi);
+ modifiedMethods.add(currentMethod);
+ }
+
+ /**
+ * Inline a call to an expression.
+ */
+ private boolean tryInlineExpression(JMethodCall x, Context ctx,
+ JMultiExpression targetExpr) {
+ List<JParameter> params = x.getTarget().params;
+ ArrayList<JExpression> args = x.getArgs();
+
+ /*
+ * Limit inlined methods to multiexpressions of length 2 for now. This
+ * handles the simple { return JVariableRef; } or { expression; return
+ * something; } cases.
+ *
+ * TODO: add an expression complexity analyzer.
+ */
+ if (targetExpr.exprs.size() > 2) {
+ return false;
+ }
+
+ // Do not inline anything that modifies one of its params.
+ ExpressionAnalyzer targetAnalyzer = new ExpressionAnalyzer();
+ targetAnalyzer.accept(targetExpr);
+ if (targetAnalyzer.hasAssignmentToParameter()) {
return false;
}
/*
- * Potential clinit violation! We can only allow this if the result is
- * itself a static field ref into the target class, which would trigger
- * the clinit itself.
+ * After this point, it's possible that the method might be inlinable at
+ * some call sites, depending on its arguments. From here on return 'true'
+ * as the method might be inlinable elsewhere.
*/
- // resultExpression might be null, which behaves correctly here.
- if (!(resultExpression instanceof JFieldRef)) {
- return true;
- }
- JFieldRef fieldRefResult = (JFieldRef) resultExpression;
- JField fieldResult = fieldRefResult.getField();
- if (!fieldResult.isStatic()) {
- // A nonstatic field reference won't trigger the clinit we need.
- return true;
- }
- if (fieldResult.getEnclosingType() != targetEnclosingType) {
- // We have a static field reference, but it's to the wrong class (not
- // the class whose clinit we must trigger).
- return true;
- }
- // The correct cross-class static field reference will trigger the clinit.
- return false;
- }
-
- /**
- * Inlines a call to an empty method.
- */
- private void tryInlineEmptyMethodCall(JMethodCall x, Context ctx) {
- if (checkClinitViolation(x, null)) {
- return;
- }
- JMultiExpression multi = new JMultiExpression(program, x.getSourceInfo());
- JExpression instance = x.getInstance();
- if (instance != null && instance.hasSideEffects()) {
- multi.exprs.add(x.getInstance());
- }
- for (int i = 0, c = x.getArgs().size(); i < c; ++i) {
- if (x.getArgs().get(i).hasSideEffects()) {
- multi.exprs.add(x.getArgs().get(i));
- }
- }
- ctx.replaceMe(multi);
- }
-
- /**
- * Inline a call to a method that contains only a return statement.
- */
- private boolean tryInlineExpression(JMethodCall x, Context ctx,
- JExpression targetExpr) {
- List<JParameter> params = x.getTarget().params;
- ArrayList<JExpression> args = x.getArgs();
-
- // the expression returned by the inlined method, if any
- JExpression resultExpression;
- // the argument that is returned by the inlined method, if any
- int magicArg[] = new int[1];
-
- resultExpression = canInlineExpression(x.getSourceInfo(), targetExpr,
- params, args, magicArg);
-
- if (resultExpression == null) {
- return false; // cannot inline
- }
-
- // The expression is inlinable.
-
- if (checkClinitViolation(x, resultExpression)) {
- /*
- * Inlining here would cause a clinit to not fire, so we can't. But
- * return true, because this method could still be inlined from within
- * the same class.
- */
+ /*
+ * There are a different number of parameters than args - this is likely a
+ * result of parameter pruning. Don't consider this call site a candidate.
+ *
+ * TODO: would this be possible in the trivial delegation case?
+ */
+ if (params.size() != args.size()) {
return true;
}
- // the argument that is returned by the inlined method
- int iMagicArg = magicArg[0];
+ // Run the order check. This verifies that all the parameters are
+ // referenced once and only once, not within a conditionally-executing
+ // expression and before any tricky target expressions, such as:
+ // - assignments to any variable
+ // - expressions that throw exceptions
+ // - field references
- JMultiExpression multi = new JMultiExpression(program, x.getSourceInfo());
+ /*
+ * Ensure correct evaluation order or params relative to each other and to
+ * other expressions.
+ */
+ OrderVisitor orderVisitor = new OrderVisitor(x.getTarget().params);
+ orderVisitor.accept(targetExpr);
- // Evaluate the instance argument (we can have one even with static calls)
- JExpression instance = x.getInstance();
- if (instance != null && instance.hasSideEffects()) {
- multi.exprs.add(x.getInstance());
+ /*
+ * A method that doesn't touch any parameters is trivially inlinable (this
+ * covers the empty method case)
+ */
+ if (orderVisitor.checkResults() == SideEffectCheck.NO_REFERENCES) {
+ JMultiExpression multi = createMultiExpressionIncludingArgs(x);
+ multi.exprs.add(targetExpr);
+ replaceWithMulti(ctx, multi);
+ return true;
}
- // Now evaluate any side-effect args that aren't the magic arg.
- for (int i = 0; i < params.size(); ++i) {
- if (args.get(i).hasSideEffects()) {
- if (i < iMagicArg) {
- // evaluate this arg inside of the multi
- multi.exprs.add(args.get(i));
- } else if (i == iMagicArg) {
- // skip this arg, we'll do it below as the final one
- } else {
- assert (i > iMagicArg);
+ /*
+ * We can still inline in the case where all of the actual arguments are
+ * "safe". They must have no side effects, and also have values which
+ * could not be affected by the execution of any code within the callee.
+ */
+ if (orderVisitor.checkResults() == SideEffectCheck.FAILS) {
+ for (JExpression arg : x.getArgs()) {
+ ExpressionAnalyzer argAnalyzer = new ExpressionAnalyzer();
+ argAnalyzer.accept(arg);
+
+ if (argAnalyzer.hasAssignment() || argAnalyzer.accessesField()
+ || argAnalyzer.createsObject() || argAnalyzer.canThrowException()) {
+
/*
- * ABORT ABORT ABORT! This would cause an out-of-order evalutation.
- * Due to the way we construct multis, the magic arg must come last.
- * However, we've encountered a case where an argument coming after
- * the magic arg must be evaluated. Just bail.
- *
- * However, we return true because this call might be inlinable at
- * other call sites.
+ * This argument evaluation could affect or be affected by the
+ * callee so we cannot inline here.
*/
return true;
}
}
}
- // add in the result expression as the last item in the multi
- multi.exprs.add(resultExpression);
- ctx.replaceMe(multi);
+ // We're safe to inline.
+ JMultiExpression multi = createMultiExpressionForInstanceAndClinit(x);
+
+ // Replace all params in the target expression with the actual arguments.
+ new ParameterReplacer(x).accept(targetExpr);
+
+ multi.exprs.add(targetExpr);
+ replaceWithMulti(ctx, multi);
return true;
}
}
/**
- * Reduces <code>JMultiExpression</code> where possible.
+ * Verifies that all the parameters are referenced once and only once, not
+ * within a conditionally-executing expression, and any before trouble some
+ * expressions evaluate. Examples of troublesome expressions include:
+ *
+ * <ul>
+ * <li>assignments to any variable</li>
+ * <li>expressions that throw exceptions</li>
+ * <li>field references</li>
+ * </ul>
*/
- public class ReduceMultiVisitor extends JModVisitor {
+ private class OrderVisitor extends ExpressionAnalyzer {
+ private int currentIndex = 0;
+ private final List<JParameter> parameters;
+ private boolean succeeded = true;
- @Override
- public void endVisit(JBlock x, Context ctx) {
- for (Iterator<JStatement> it = x.statements.iterator(); it.hasNext();) {
- JStatement stmt = it.next();
- // If we're a JExprStmt with no side effects, just remove me
- if (stmt instanceof JExpressionStatement) {
- JExpression expr = ((JExpressionStatement) stmt).getExpr();
- if (!expr.hasSideEffects()) {
- it.remove();
- didChange = true;
- }
- }
+ public OrderVisitor(List<JParameter> parameters) {
+ this.parameters = parameters;
+ }
+
+ public SideEffectCheck checkResults() {
+ if (succeeded && currentIndex == parameters.size()) {
+ return SideEffectCheck.CORRECT_ORDER;
}
+
+ if (succeeded && currentIndex == 0) {
+ return SideEffectCheck.NO_REFERENCES;
+ }
+
+ return SideEffectCheck.FAILS;
}
@Override
- public void endVisit(JMultiExpression x, Context ctx) {
- ArrayList<JExpression> exprs = x.exprs;
+ public void endVisit(JParameterRef x, Context ctx) {
+ JParameter param = x.getParameter();
- final int c = exprs.size();
- if (c == 0) {
- return;
+ // If the expression has side-effects before a parameter reference, fail
+ if (hasAssignment() || accessesField() || canThrowException()) {
+ succeeded = false;
}
- int countSideEffectsBeforeLast = 0;
- for (int i = 0; i < c - 1; ++i) {
- JExpression expr = exprs.get(i);
- if (expr.hasSideEffects()) {
- ++countSideEffectsBeforeLast;
- }
+ // If this parameter reference won't always execute, fail
+ if (isInConditional()) {
+ succeeded = false;
}
- if (countSideEffectsBeforeLast == 0) {
- ctx.replaceMe(x.exprs.get(c - 1));
+ // Ensure this parameter is evaluated in the correct order relative to
+ // other parameters.
+ if (parameters.indexOf(param) == currentIndex) {
+ currentIndex++;
} else {
- JMultiExpression newMulti = new JMultiExpression(program,
- x.getSourceInfo());
- for (int i = 0; i < c - 1; ++i) {
- JExpression expr = exprs.get(i);
- if (expr.hasSideEffects()) {
- newMulti.exprs.add(expr);
- }
- }
- newMulti.exprs.add(x.exprs.get(c - 1));
- if (newMulti.exprs.size() < x.exprs.size()) {
- ctx.replaceMe(newMulti);
- }
+ succeeded = false;
}
+
+ super.endVisit(x, ctx);
}
}
+ /**
+ * Results of a side-effect and order check.
+ */
+ private enum SideEffectCheck {
+ CORRECT_ORDER, FAILS, NO_REFERENCES
+ }
+
public static boolean exec(JProgram program) {
return new MethodInliner(program).execImpl();
}
@@ -423,13 +474,11 @@
}
madeChanges = true;
- FlattenMultiVisitor flattener = new FlattenMultiVisitor();
- flattener.accept(program);
-
- ReduceMultiVisitor reducer = new ReduceMultiVisitor();
- reducer.accept(program);
+ // Run a cleanup on the methods we just modified
+ for (JMethod method : inliner.modifiedMethods) {
+ DeadCodeElimination.exec(program, method);
+ }
}
return madeChanges;
}
-
}
diff --git a/user/test/com/google/gwt/dev/jjs/test/MethodCallTest.java b/user/test/com/google/gwt/dev/jjs/test/MethodCallTest.java
index 70f7a43..d7a84d3 100644
--- a/user/test/com/google/gwt/dev/jjs/test/MethodCallTest.java
+++ b/user/test/com/google/gwt/dev/jjs/test/MethodCallTest.java
@@ -18,7 +18,7 @@
import com.google.gwt.junit.client.GWTTestCase;
/**
- * TODO: document me.
+ * Tests method invocations including potential inlining bugs.
*/
public class MethodCallTest extends GWTTestCase {
@@ -140,6 +140,18 @@
assertEquals(10, result);
}
+ public void testAssignsToParam() {
+ value = 10;
+ int result = assignsToParam(value);
+ assertEquals(10, value);
+ assertEquals(11, result);
+
+ int localValue = 20;
+ result = assignsToParam(localValue);
+ assertEquals(20, localValue);
+ assertEquals(21, result);
+ }
+
public void testManyArgs() {
assertEquals(32385, manyArgs(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
@@ -160,6 +172,15 @@
243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254));
}
+ /**
+ * Ensure that we correctly inline a method that ignores its parameters.
+ */
+ public void testNoParameterRefs() {
+ int value = 100;
+ assertEquals(1, ignoreParams(value++, value++));
+ assertEquals(102, value);
+ }
+
public void testRecursion() {
assertEquals(20100, recursiveSum(200));
}
@@ -293,6 +314,10 @@
return value + i;
}
+ private int assignsToParam(int x) {
+ return ++x;
+ }
+
private int checkOrder(int x, int y) {
return y * 1000 + x;
}
@@ -313,6 +338,10 @@
return (value *= 2) + i;
}
+ private int ignoreParams(int i, int j) {
+ return 1;
+ }
+
private int recursiveSum(int x) {
if (x == 0) {
return 0;
