Author: [email protected]
Date: Mon Jun 22 10:19:32 2009
New Revision: 5597
Modified:
trunk/dev/core/src/com/google/gwt/dev/js/JsInliner.java
trunk/dev/core/test/com/google/gwt/dev/js/JsInlinerTest.java
Log:
Fix JsInliner for mutually-recursive functions.
Patch by: bobv
Review by: spoon
Modified: trunk/dev/core/src/com/google/gwt/dev/js/JsInliner.java
==============================================================================
--- trunk/dev/core/src/com/google/gwt/dev/js/JsInliner.java (original)
+++ trunk/dev/core/src/com/google/gwt/dev/js/JsInliner.java Mon Jun 22
10:19:32 2009
@@ -722,6 +722,14 @@
*/
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>>();
@@ -859,13 +867,13 @@
* when trying operate on references to external functions, or
functions
* as arguments to another function.
*/
- JsFunction f = isFunction(x.getQualifier());
- if (f == null) {
+ JsFunction invokedFunction = isFunction(x.getQualifier());
+ if (invokedFunction == null) {
return;
}
// Don't inline blacklisted functions
- if (blacklist.contains(f)) {
+ if (blacklist.contains(invokedFunction)) {
return;
}
@@ -873,14 +881,130 @@
* The current function has been mutated so as to be self-recursive.
Ban
* it from any future inlining to prevent infinite expansion.
*/
- if (f == callerFunction) {
- blacklist.add(f);
+ 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);
+ 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(JsProgramFragment x, JsContext<JsProgramFragment>
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<JsStatement> 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<JsExpression> 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(JsProgramFragment x, JsContext<JsProgramFragment>
ctx) {
+ programFunction = new JsFunction(program.getSourceInfo(),
+ program.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().makeChild(
+ InliningVisitor.class, "Synthetic locals");
+ 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 (f.getBody() != null) {
- statements = new
ArrayList<JsStatement>(f.getBody().getStatements());
+ if (invokedFunction.getBody() != null) {
+ statements = new ArrayList<JsStatement>(
+ invokedFunction.getBody().getStatements());
} else {
/*
* Will see this with certain classes whose clinits are folded
into the
@@ -908,7 +1032,7 @@
* TODO(bobv): maybe it could still be inlined with smart
* transformation?
*/
- return;
+ return x;
}
/*
@@ -922,7 +1046,7 @@
JsExpression h = hoistedExpression(program, statement,
localVariableNames);
if (h == null) {
- return;
+ return x;
}
if (isReturnStatement(statement)) {
@@ -963,12 +1087,13 @@
}
// Confirm that the expression conforms to the desired heuristics
- if (!isInlinable(program, callerFunction, f, x.getArguments(), op)) {
- return;
+ if (!isInlinable(program, callerFunction, invokedFunction,
+ x.getArguments(), op)) {
+ return x;
}
// Perform the name replacement
- NameRefReplacerVisitor v = new NameRefReplacerVisitor(x, f);
+ NameRefReplacerVisitor v = new NameRefReplacerVisitor(x,
invokedFunction);
for (ListIterator<JsName> nameIterator =
localVariableNames.listIterator(); nameIterator.hasNext();) {
JsName name = nameIterator.next();
@@ -978,7 +1103,7 @@
* function so we'll use a counter for disambiguation.
*/
String ident;
- String base = f.getName() + "_" + name.getIdent();
+ String base = invokedFunction.getName() + "_" + name.getIdent();
JsScope scope = callerFunction.getScope();
HashMap<String, Integer> startIdent =
startIdentForScope.get(scope);
if (startIdent == null) {
@@ -1009,13 +1134,14 @@
int originalComplexity = complexity(x);
int inlinedComplexity = complexity(op);
double ratio = ((double) inlinedComplexity) / originalComplexity;
- if (ratio > MAX_COMPLEXITY_INCREASE && isInvokedMoreThanOnce(f)) {
- return;
+ 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;
+ return x;
}
// We've committed to the inlining, ensure the vars are created
@@ -1024,92 +1150,7 @@
// update invocation counts according to this inlining
invocationCountingVisitor.removeCountsFor(x);
invocationCountingVisitor.accept(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);
- }
-
- @Override
- public void endVisit(JsProgramFragment x, JsContext<JsProgramFragment>
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<JsStatement> 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<JsExpression> 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(JsProgramFragment x, JsContext<JsProgramFragment>
ctx) {
- programFunction = new JsFunction(program.getSourceInfo(),
- program.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().makeChild(
- InliningVisitor.class, "Synthetic locals");
- 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;
+ return op;
}
}
Modified: trunk/dev/core/test/com/google/gwt/dev/js/JsInlinerTest.java
==============================================================================
--- trunk/dev/core/test/com/google/gwt/dev/js/JsInlinerTest.java
(original)
+++ trunk/dev/core/test/com/google/gwt/dev/js/JsInlinerTest.java Mon Jun
22
10:19:32 2009
@@ -27,27 +27,50 @@
*/
public class JsInlinerTest extends OptimizerTestBase {
+ private static class FixStaticRefsVisitor extends JsModVisitor {
+ public static void exec(JsProgram program) {
+ (new FixStaticRefsVisitor()).accept(program);
+ }
+
+ @Override
+ public void endVisit(JsFunction x, JsContext<JsExpression> ctx) {
+ JsName name = x.getName();
+ name.setStaticRef(x);
+ }
+ }
+
+ /**
+ * A test for mutually-recursive functions. Setup:
+ *
+ * <pre>
+ * a -> b, c
+ * b -> a, c
+ * c -> a, c
+ * </pre>
+ */
+ public void testMutualRecursion() throws Exception {
+ String input = "function a1() { return ex ? b1() : c1() }"
+ + "function b1() { return ex2 ? a1(): c1(); }"
+ + "function c1() { return ex2? a1():c1(); } c1()";
+ String expected = "function a1() { return ex ? (ex2 ? a1() : c1()) :
c1() }"
+ + "function c1() { return ex2 ? a1() :c1(); } c1()";
+ compare(expected, input);
+ }
+
public void testSelfRecursion() throws Exception {
String input = "function a1() { return blah && b1() }"
+ "function b1() { return bar && a1()}" + "function c() { a1() }
c()";
- input = optimize(input, JsSymbolResolver.class,
FixStaticRefsVisitor.class,
- JsInliner.class, JsUnusedFunctionRemover.class);
String expected = "function a1() { return blah && bar && a1() }"
+ "function c() { a1() } c()";
- expected = optimize(expected);
- assertEquals(expected, input);
- }
- private static class FixStaticRefsVisitor extends JsModVisitor {
- @Override
- public void endVisit(JsFunction x, JsContext<JsExpression> ctx) {
- JsName name = x.getName();
- name.setStaticRef(x);
- }
+ compare(expected, input);
+ }
- public static void exec(JsProgram program) {
- (new FixStaticRefsVisitor()).accept(program);
- }
+ private void compare(String expected, String input) throws Exception {
+ input = optimize(input, JsSymbolResolver.class,
FixStaticRefsVisitor.class,
+ JsInliner.class, JsUnusedFunctionRemover.class);
+ expected = optimize(expected);
+ assertEquals(expected, input);
}
}
--~--~---------~--~----~------------~-------~--~----~
http://groups.google.com/group/Google-Web-Toolkit-Contributors
-~----------~----~----~----~------~----~------~--~---
