Optimize redundant 'switch' statements Fix bug caused by using short idents when matching case bodies Review at http://gwt-code-reviews.appspot.com/1311801 Review by: scottb@google.com git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@9585 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java b/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java index e795adb..7aeb7f4 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java +++ b/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java
@@ -107,6 +107,7 @@ import com.google.gwt.dev.js.EvalFunctionsAtTopScope; import com.google.gwt.dev.js.JsBreakUpLargeVarStatements; import com.google.gwt.dev.js.JsCoerceIntShift; +import com.google.gwt.dev.js.JsDuplicateCaseFolder; import com.google.gwt.dev.js.JsDuplicateFunctionRemover; import com.google.gwt.dev.js.JsIEBlockSizeVisitor; import com.google.gwt.dev.js.JsInliner; @@ -322,6 +323,11 @@ // (9) Optimize the JS AST. if (optimizationLevel > OptionOptimize.OPTIMIZE_LEVEL_DRAFT) { optimizeJs(options, jsProgram); + + /* + * Coalesce redundant labels in switch statements. + */ + JsDuplicateCaseFolder.exec(jsProgram); } /* @@ -572,7 +578,7 @@ Memory.maybeDumpMemory("AstOnly"); AstDumper.maybeDumpAST(jprogram); - + // See if we should run the EnumNameObfuscator if (module != null) { ConfigurationProperty enumNameObfuscationProp = (ConfigurationProperty) module.getProperties().find( @@ -822,12 +828,12 @@ // remove same parameters value stats.add(SameParameterValueOptimizer.exec(jprogram).recordVisits( numNodes)); - + /* * enum ordinalization * TODO(jbrosenberg): graduate this out of the 'isAggressivelyOptimize' * block, over time. - */ + */ stats.add(EnumOrdinalizer.exec(jprogram).recordVisits(numNodes)); }
diff --git a/dev/core/src/com/google/gwt/dev/js/JsDuplicateCaseFolder.java b/dev/core/src/com/google/gwt/dev/js/JsDuplicateCaseFolder.java new file mode 100644 index 0000000..397894d --- /dev/null +++ b/dev/core/src/com/google/gwt/dev/js/JsDuplicateCaseFolder.java
@@ -0,0 +1,174 @@ +/* + * Copyright 2011 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.js.ast.JsBlock; +import com.google.gwt.dev.js.ast.JsContext; +import com.google.gwt.dev.js.ast.JsModVisitor; +import com.google.gwt.dev.js.ast.JsProgram; +import com.google.gwt.dev.js.ast.JsStatement; +import com.google.gwt.dev.js.ast.JsSwitch; +import com.google.gwt.dev.js.ast.JsSwitchMember; + +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; + +/** + * Combine case labels with identical bodies. Case bodies that may fall through + * to the following case label and case bodies following a possible fallthrough + * are left undisturbed. + * + * For example, consider the following input: + * + * <pre> + * switch (x) { + * case 0: y = 17; break; + * case 1: if (z == 0) { y = 18; break; } else { y = 19 } // fallthrough else + * case 2: return 22; + * case 3: if (z == 0) { y = 18; break; } else { y = 19 } // fallthrough else + * case 4: y = 17; break; + * case 5: y = 17; break; + * case 6: return 22; + * } + * </pre> + * + * This will be transformed into: + * + * <pre> + * switch (x) { + * case 0: y = 17; break; + * case 1: if (z == 0) { y = 18; break; } else { y = 19 } + * case 6: case 2: return 22; + * case 3: if (z == 0) { y = 18; break; } else { y = 19 } + * case 5: case 4: y = 17; break; + * } + * + * <pre> + * + * Cases (2, 6) and (4, 5) have been coalesced. Note that case 0 has not been + * combined with cases 4 and 5 since case 4 cannot be moved due to the potential + * fallthrough from case 3, and we currently only coalesce a given cases with a + * preceding case and so cannot move case 0 downward. + * + * Although this pattern is unlikely to occur frequently in hand-written code, + * it can account for a significant amount of space in generated code. + */ +public class JsDuplicateCaseFolder { + + private class DuplicateCaseFolder extends JsModVisitor { + + public DuplicateCaseFolder() { + } + + @Override + public boolean visit(JsSwitch x, JsContext<JsStatement> ctx) { + boolean modified = false; + + // A map from case body source code to the original case label + // in which they appeared + Map<String, JsSwitchMember> seen = new HashMap<String, JsSwitchMember>(); + + // Original list of members + List<JsSwitchMember> cases = x.getCases(); + // Coalesced list of members + List<JsSwitchMember> newCases = new LinkedList<JsSwitchMember>(); + + // Keep track of whether the previous case can fall through + // to the current case + boolean hasPreviousFallthrough = false; + + // Iterate over members and locate ones with bodies identical to + // previous members + for (JsSwitchMember member : cases) { + List<JsStatement> stmts = member.getStmts(); + + // Don't rewrite any cases that might fall through + if (!unconditionalControlBreak(stmts)) { + hasPreviousFallthrough = true; + // copy the case into the output + newCases.add(member); + continue; + } + + String body = toSource(stmts); + JsSwitchMember previousCase = seen.get(body); + if (previousCase == null || hasPreviousFallthrough) { + // Don't coalesce a case that can be reached via fallthrough + // from the previous case + newCases.add(member); + seen.put(body, member); + } else { + // Locate the position of the case that this case is to be + // coalesced with. Note: linear search in output list + int index = newCases.indexOf(previousCase); + + // Empty the case body and insert the case label into the output + member.getStmts().clear(); + newCases.add(index, member); + modified = true; + } + + hasPreviousFallthrough = false; + } + + // Rewrite the AST if any cases have changed + if (modified) { + didChange = true; + cases.clear(); + cases.addAll(newCases); + } + + return true; + } + + private String toSource(List<JsStatement> stmts) { + StringBuilder sb = new StringBuilder(); + for (JsStatement stmt : stmts) { + sb.append(stmt.toSource(true)); + sb.append("\n"); // separate statements + } + return sb.toString(); + } + + /** + * See {@link JsStatement#unconditionalControlBreak()}. + */ + private boolean unconditionalControlBreak(List<JsStatement> stmts) { + for (JsStatement stmt : stmts) { + if (stmt.unconditionalControlBreak()) { + return true; + } + } + return false; + } + } + + // Needed for OptimizerTestBase + public static boolean exec(JsProgram program) { + return new JsDuplicateCaseFolder().execImpl(program.getFragmentBlock(0)); + } + + public JsDuplicateCaseFolder() { + } + + private boolean execImpl(JsBlock fragment) { + DuplicateCaseFolder dcf = new DuplicateCaseFolder(); + dcf.accept(fragment); + return dcf.didChange(); + } +}
diff --git a/dev/core/src/com/google/gwt/dev/js/JsSourceGenerationVisitor.java b/dev/core/src/com/google/gwt/dev/js/JsSourceGenerationVisitor.java index 1a0ff06..5eea334 100644 --- a/dev/core/src/com/google/gwt/dev/js/JsSourceGenerationVisitor.java +++ b/dev/core/src/com/google/gwt/dev/js/JsSourceGenerationVisitor.java
@@ -27,9 +27,21 @@ */ public class JsSourceGenerationVisitor extends JsToStringGenerationVisitor { + /** + * Generate the output source code using short identifiers. + */ public JsSourceGenerationVisitor(TextOutput out) { super(out); } + + /** + * Generate the output source code using short or long identifiers. + * + * @param useLongIdents if true, emit all identifiers in long form + */ + public JsSourceGenerationVisitor(TextOutput out, boolean useLongIdents) { + super(out, useLongIdents); + } @Override public boolean visit(JsProgram x, JsContext<JsProgram> ctx) {
diff --git a/dev/core/src/com/google/gwt/dev/js/JsToStringGenerationVisitor.java b/dev/core/src/com/google/gwt/dev/js/JsToStringGenerationVisitor.java index a363f88..a8d1e1e 100644 --- a/dev/core/src/com/google/gwt/dev/js/JsToStringGenerationVisitor.java +++ b/dev/core/src/com/google/gwt/dev/js/JsToStringGenerationVisitor.java
@@ -263,13 +263,27 @@ */ private Set<JsBlock> globalBlocks = new HashSet<JsBlock>(); private final TextOutput p; + private final boolean useLongIdents; private ArrayList<Integer> statementEnds = new ArrayList<Integer>(); private ArrayList<Integer> statementStarts = new ArrayList<Integer>(); + /** + * Generate the output string using short identifiers. + */ public JsToStringGenerationVisitor(TextOutput out) { + this(out, false); + } + + /** + * Generate the output string using short or long identifiers. + * + * @param useLongIdents if true, emit all identifiers in long form + */ + JsToStringGenerationVisitor(TextOutput out, boolean useLongIdents) { this.p = out; + this.useLongIdents = useLongIdents; } public StatementRanges getStatementRanges() { @@ -682,7 +696,12 @@ @Override public boolean visit(JsNameOf x, JsContext<JsExpression> ctx) { - printStringLiteral(x.getName().getShortIdent()); + if (useLongIdents) { + printStringLiteral(x.getName().getIdent()); + } else { + printStringLiteral(x.getName().getShortIdent()); + } + return false; } @@ -1142,7 +1161,11 @@ } private void _nameDef(JsName name) { - p.print(name.getShortIdent()); + if (useLongIdents) { + p.print(name.getIdent()); + } else { + p.print(name.getShortIdent()); + } } private void _nameOf(HasName hasName) { @@ -1150,7 +1173,11 @@ } private void _nameRef(JsNameRef nameRef) { - p.print(nameRef.getShortIdent()); + if (useLongIdents) { + p.print(nameRef.getIdent()); + } else { + p.print(nameRef.getShortIdent()); + } } private boolean _nestedPop(JsStatement statement) {
diff --git a/dev/core/src/com/google/gwt/dev/js/ast/JsBlock.java b/dev/core/src/com/google/gwt/dev/js/ast/JsBlock.java index a4a06c8..0cbf91c 100644 --- a/dev/core/src/com/google/gwt/dev/js/ast/JsBlock.java +++ b/dev/core/src/com/google/gwt/dev/js/ast/JsBlock.java
@@ -45,4 +45,14 @@ } v.endVisit(this, ctx); } + + @Override + public boolean unconditionalControlBreak() { + for (JsStatement stmt : stmts) { + if (stmt.unconditionalControlBreak()) { + return true; + } + } + return false; + } }
diff --git a/dev/core/src/com/google/gwt/dev/js/ast/JsBreak.java b/dev/core/src/com/google/gwt/dev/js/ast/JsBreak.java index 5c2fb73..5c63bde 100644 --- a/dev/core/src/com/google/gwt/dev/js/ast/JsBreak.java +++ b/dev/core/src/com/google/gwt/dev/js/ast/JsBreak.java
@@ -48,6 +48,6 @@ @Override public boolean unconditionalControlBreak() { - return true; + return label == null; } }
diff --git a/dev/core/src/com/google/gwt/dev/js/ast/JsIf.java b/dev/core/src/com/google/gwt/dev/js/ast/JsIf.java index 2440155..b1b9d3d 100644 --- a/dev/core/src/com/google/gwt/dev/js/ast/JsIf.java +++ b/dev/core/src/com/google/gwt/dev/js/ast/JsIf.java
@@ -74,4 +74,17 @@ } v.endVisit(this, ctx); } + + @Override + public boolean unconditionalControlBreak() { + boolean thenBreaks = thenStmt != null + && thenStmt.unconditionalControlBreak(); + boolean elseBreaks = elseStmt != null + && elseStmt.unconditionalControlBreak(); + if (thenBreaks && elseBreaks) { + // both branches have an unconditional break + return true; + } + return false; + } }
diff --git a/dev/core/src/com/google/gwt/dev/js/ast/JsNode.java b/dev/core/src/com/google/gwt/dev/js/ast/JsNode.java index f370ee4..1f4add6 100644 --- a/dev/core/src/com/google/gwt/dev/js/ast/JsNode.java +++ b/dev/core/src/com/google/gwt/dev/js/ast/JsNode.java
@@ -42,10 +42,23 @@ return sourceInfo; } + /** + * Returns a source code representation of the node using short identifiers. + */ // Causes source generation to delegate to the one visitor public final String toSource() { + return toSource(false); + } + + /** + * Returns a source code representation of the node using short or long + * identifiers. + * + * @param useLongIdents if true, emit all identifiers in long form + */ + public final String toSource(boolean useLongIdents) { DefaultTextOutput out = new DefaultTextOutput(false); - JsSourceGenerationVisitor v = new JsSourceGenerationVisitor(out); + JsSourceGenerationVisitor v = new JsSourceGenerationVisitor(out, useLongIdents); v.accept(this); return out.toString(); }
diff --git a/dev/core/test/com/google/gwt/dev/js/JsDuplicateCaseFolderTest.java b/dev/core/test/com/google/gwt/dev/js/JsDuplicateCaseFolderTest.java new file mode 100644 index 0000000..aec66fd --- /dev/null +++ b/dev/core/test/com/google/gwt/dev/js/JsDuplicateCaseFolderTest.java
@@ -0,0 +1,95 @@ +/* + * Copyright 2011 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; + +/** + * Tests the JsDuplicateCaseFolder optimizer. + */ +public class JsDuplicateCaseFolderTest extends OptimizerTestBase { + + public void test1() throws Exception { + String input = "function a(x){switch(x){case 0:return 17;case 12:case 1:return 18;case 2:return 17;case 3:return 18;}}"; + String expected = "function a(x){switch(x){case 2:case 0:return 17;case 12:case 3:case 1:return 18;}}\n"; + check(expected, input); + } + + public void test1b() throws Exception { + String input = "function a(x){switch(x){case 0:return 17;case 12:case 1:return 18;default:return 17;case 3:return 18;}}"; + String expected = "function a(x){switch(x){default:case 0:return 17;case 12:case 3:case 1:return 18;}}\n"; + check(expected, input); + } + + public void test2() throws Exception { + // Don't coalesces cases 0 and 2 since 2 can be reached via fallthrough from 1 + String input = "function a(x){var y;switch(x){case 0:return 17;case 1:y=18;case 2:return 17;case 3:y=18;}return y}"; + String expected = "function a(x){var y;switch(x){case 0:return 17;case 1:y=18;case 2:return 17;case 3:y=18;}return y}\n"; + check(expected, input); + } + + public void test3() throws Exception { + // cases 1 and 3 can fall through, don't coalesce + String input = "function a(x){var y;switch(x){case 0:return 17;case 1:y=18;break;case 2:return 17;case 3:y=18;break;}return y}"; + String expected = "function a(x){var y;switch(x){case 2:case 0:return 17;case 3:case 1:y=18;break;}return y}\n"; + check(expected, input); + } + + public void test4() throws Exception { + // cases 1 and 3 may be coalesced + String input = "function a(x,z){var y;switch(x){case 0:return 17;case 1:if (z==0){y=18;break}else{y=19;break}case 2:return 17;case 3:if(z==0){y=18;break}else{y=19;break}}return y}"; + String expected = "function a(x,z){var y;switch(x){case 2:case 0:return 17;case 3:case 1:if(z==0){y=18;break}else{y=19;break}}return y}\n"; + check(expected, input); + } + + public void test4b() throws Exception { + // cases 1 and 3 may be coalesced + // ensure additional fallthroughs are handled correctly + String input = "function a(x,z){var y;switch(x){case 0:case 22:return 17;case 100:case 1:if (z==0){y=18;break}else{y=19;return 20}case 2:return 17;case 200:case 3:if(z==0){y=18;break}else{y=19;return 20}}return y}"; + String expected = "function a(x,z){var y;switch(x){case 0:case 2:case 22:return 17;case 100:case 1:if(z==0){y=18;break}else{y=19;return 20}case 200:case 3:if(z==0){y=18;break}else{y=19;return 20}}return y}\n"; + check(expected, input); + } + + public void test5() throws Exception { + // cases 1 and 3 can fall through due to no else clause, don't coalesce + String input = "function a(x,z){var y;switch(x){case 0:return 17;case 1:if (z==0){y=18;break}else{y=19}case 2:return 17;case 3:if(z==0){y=18;break}else{y=19}}return y}"; + String expected = "function a(x,z){var y;switch(x){case 0:return 17;case 1:if(z==0){y=18;break}else{y=19}case 2:return 17;case 3:if(z==0){y=18;break}else{y=19}}return y}\n"; + check(expected, input); + } + + public void test6() throws Exception { + // cases 1 and 3 can fall through due to no else clause, don't coalesce + String input = "function a(x,z){var y;switch(x){case 0:y=17;break;case 1:if(z==0){y=18;break}else{y=19}case 2:return 22;case 3:if(z==0){y=18;break}else{y=19}case 4:y=17;break;case 5:y=17;break;case 6:return 22;}return y}"; + String expected = "function a(x,z){var y;switch(x){case 0:y=17;break;case 1:if(z==0){y=18;break}else{y=19}case 6:case 2:return 22;case 3:if(z==0){y=18;break}else{y=19}case 5:case 4:y=17;break;}return y}\n"; + check(expected, input); + } + + public void test6b() throws Exception { + // cases 1 and 3 can fall through due to no else clause, don't coalesce + String input = "function a(x,z){var y;switch(x){case 0:y=17;break;case 1:if(z==0){y=18;break}else{y=19}default:return 22;case 3:if(z==0){y=18;break}else{y=19}case 4:y=17;break;case 5:y=17;break;case 6:return 22;}return y}"; + String expected = "function a(x,z){var y;switch(x){case 0:y=17;break;case 1:if(z==0){y=18;break}else{y=19}case 6:default:return 22;case 3:if(z==0){y=18;break}else{y=19}case 5:case 4:y=17;break;}return y}\n"; + check(expected, input); + } + + private void check(String expected, String input) throws Exception { + // Pass the expected code through the parser to normalize it + expected = super.optimize(expected, new Class[0]); + String output = optimize(input); + assertEquals(expected, output); + } + + private String optimize(String js) throws Exception { + return optimize(js, JsDuplicateCaseFolder.class); + } +}