Revision: 9565
Author: r...@google.com
Date: Tue Jan 18 10:26:55 2011
Log: Optimize redundant 'switch' statements
Review at http://gwt-code-reviews.appspot.com/1286801
Review by: sco...@google.com
http://code.google.com/p/google-web-toolkit/source/detail?r=9565
Added:
/trunk/dev/core/src/com/google/gwt/dev/js/JsDuplicateCaseFolder.java
/trunk/dev/core/test/com/google/gwt/dev/js/JsDuplicateCaseFolderTest.java
Modified:
/trunk/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java
/trunk/dev/core/src/com/google/gwt/dev/js/ast/JsBlock.java
/trunk/dev/core/src/com/google/gwt/dev/js/ast/JsBreak.java
/trunk/dev/core/src/com/google/gwt/dev/js/ast/JsIf.java
=======================================
--- /dev/null
+++ /trunk/dev/core/src/com/google/gwt/dev/js/JsDuplicateCaseFolder.java
Tue Jan 18 10:26:55 2011
@@ -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());
+ 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();
+ }
+}
=======================================
--- /dev/null
+++
/trunk/dev/core/test/com/google/gwt/dev/js/JsDuplicateCaseFolderTest.java
Tue Jan 18 10:26:55 2011
@@ -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 optimizer 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);
+ }
+}
=======================================
---
/trunk/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java
Mon Nov 22 12:01:32 2010
+++
/trunk/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java
Tue Jan 18 10:26:55 2011
@@ -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));
}
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/js/ast/JsBlock.java Fri Sep 26
08:20:00 2008
+++ /trunk/dev/core/src/com/google/gwt/dev/js/ast/JsBlock.java Tue Jan 18
10:26:55 2011
@@ -45,4 +45,14 @@
}
v.endVisit(this, ctx);
}
-}
+
+ @Override
+ public boolean unconditionalControlBreak() {
+ for (JsStatement stmt : stmts) {
+ if (stmt.unconditionalControlBreak()) {
+ return true;
+ }
+ }
+ return false;
+ }
+}
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/js/ast/JsBreak.java Wed Aug 11
09:22:23 2010
+++ /trunk/dev/core/src/com/google/gwt/dev/js/ast/JsBreak.java Tue Jan 18
10:26:55 2011
@@ -48,6 +48,6 @@
@Override
public boolean unconditionalControlBreak() {
- return true;
+ return label == null;
}
}
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/js/ast/JsIf.java Fri Sep 26
08:20:00 2008
+++ /trunk/dev/core/src/com/google/gwt/dev/js/ast/JsIf.java Tue Jan 18
10:26:55 2011
@@ -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;
+ }
+}
--
http://groups.google.com/group/Google-Web-Toolkit-Contributors
