Implement a "dependent optimizations" framework. - This framework is used for speeding up optimizations by running optimizers on just modified fields and methods. - Use the framework to speedup MethodInliner (both inner loop and outer loop). - Add unit tests for MethodInliner. Change-Id: Ieb38b77294a2004ee03047f6f6aac41164395329
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 66559a9..6b9497a 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java +++ b/dev/core/src/com/google/gwt/dev/jjs/JavaToJavaScriptCompiler.java
@@ -80,6 +80,7 @@ import com.google.gwt.dev.jjs.impl.MethodCallSpecializer; import com.google.gwt.dev.jjs.impl.MethodCallTightener; import com.google.gwt.dev.jjs.impl.MethodInliner; +import com.google.gwt.dev.jjs.impl.OptimizerContext; import com.google.gwt.dev.jjs.impl.OptimizerStats; import com.google.gwt.dev.jjs.impl.Pruner; import com.google.gwt.dev.jjs.impl.RecordRebinds; @@ -357,7 +358,6 @@ addSyntheticArtifacts(unifiedAst, permutation, startTimeMs, permutationId, jjsmap, dependenciesAndRecorder, internedLiteralByVariableName, isSourceMapsEnabled, jsFragments, sizeBreakdowns, sourceInfoMaps, permutationResult); - return permutationResult; } catch (Throwable e) { throw CompilationProblemReporter.logAndTranslateException(logger, e); @@ -1132,7 +1132,8 @@ * compiles, so let's avoid doing potentially superlinear optimizations on the unified * AST. */ - optimizeJavaOneTime("Early Optimization", jprogram.getNodeCount()); + optimizeJavaOneTime("Early Optimization", jprogram.getNodeCount(), + new OptimizerContext(jprogram)); } } } @@ -1450,6 +1451,7 @@ boolean atMaxLevel = options.getOptimizationLevel() == OptionOptimize.OPTIMIZE_LEVEL_MAX; int passLimit = atMaxLevel ? MAX_PASSES : options.getOptimizationLevel(); float minChangeRate = atMaxLevel ? FIXED_POINT_CHANGE_RATE : EFFICIENT_CHANGE_RATE; + OptimizerContext optimizerCtx = new OptimizerContext(jprogram); while (true) { passCount++; if (passCount > passLimit) { @@ -1460,7 +1462,7 @@ throw new InterruptedException(); } AstDumper.maybeDumpAST(jprogram); - OptimizerStats stats = optimizeJavaOneTime("Pass " + passCount, nodeCount); + OptimizerStats stats = optimizeJavaOneTime("Pass " + passCount, nodeCount, optimizerCtx); allOptimizerStats.add(stats); lastNodeCount = nodeCount; nodeCount = jprogram.getNodeCount(); @@ -1493,23 +1495,24 @@ } } - private OptimizerStats optimizeJavaOneTime(String passName, int numNodes) { + private OptimizerStats optimizeJavaOneTime(String passName, int numNodes, + OptimizerContext optimizerCtx) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "phase", "loop"); // Clinits might have become empty become empty. jprogram.typeOracle.recomputeAfterOptimizations(jprogram.getDeclaredTypes()); OptimizerStats stats = new OptimizerStats(passName); - stats.add(Pruner.exec(jprogram, true).recordVisits(numNodes)); - stats.add(Finalizer.exec(jprogram).recordVisits(numNodes)); - stats.add(MakeCallsStatic.exec(jprogram, options.shouldAddRuntimeChecks()) + stats.add(Pruner.exec(jprogram, true, optimizerCtx).recordVisits(numNodes)); + stats.add(Finalizer.exec(jprogram, optimizerCtx).recordVisits(numNodes)); + stats.add(MakeCallsStatic.exec(jprogram, options.shouldAddRuntimeChecks(), optimizerCtx) .recordVisits(numNodes)); - stats.add(TypeTightener.exec(jprogram).recordVisits(numNodes)); - stats.add(MethodCallTightener.exec(jprogram).recordVisits(numNodes)); + stats.add(TypeTightener.exec(jprogram, optimizerCtx).recordVisits(numNodes)); + stats.add(MethodCallTightener.exec(jprogram, optimizerCtx).recordVisits(numNodes)); // Note: Specialization should be done before inlining. - stats.add(MethodCallSpecializer.exec(jprogram).recordVisits(numNodes)); - stats.add(DeadCodeElimination.exec(jprogram).recordVisits(numNodes)); - stats.add(MethodInliner.exec(jprogram).recordVisits(numNodes)); + stats.add(MethodCallSpecializer.exec(jprogram, optimizerCtx).recordVisits(numNodes)); + stats.add(DeadCodeElimination.exec(jprogram, optimizerCtx).recordVisits(numNodes)); + stats.add(MethodInliner.exec(jprogram, optimizerCtx).recordVisits(numNodes)); if (options.shouldInlineLiteralParameters()) { - stats.add(SameParameterValueOptimizer.exec(jprogram).recordVisits(numNodes)); + stats.add(SameParameterValueOptimizer.exec(jprogram, optimizerCtx).recordVisits(numNodes)); } if (options.shouldOrdinalizeEnums()) { stats.add(EnumOrdinalizer.exec(jprogram).recordVisits(numNodes));
diff --git a/dev/core/src/com/google/gwt/dev/jjs/ast/JModVisitor.java b/dev/core/src/com/google/gwt/dev/jjs/ast/JModVisitor.java index 7339446..a4c48a4 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/ast/JModVisitor.java +++ b/dev/core/src/com/google/gwt/dev/jjs/ast/JModVisitor.java
@@ -53,14 +53,14 @@ public void insertAfter(JNode node) { checkRemoved(); list.add(index + 1, (T) node); - ++numVisitorChanges; + madeChanges(); } @Override public void insertBefore(JNode node) { checkRemoved(); list.add(index++, (T) node); - ++numVisitorChanges; + madeChanges(); } @Override @@ -73,7 +73,7 @@ checkState(); list.remove(index--); removed = true; - ++numVisitorChanges; + madeChanges(); } @Override @@ -82,7 +82,7 @@ checkReplacement(list.get(index), node); list.set(index, (T) node); replaced = true; - ++numVisitorChanges; + madeChanges(); } /** @@ -141,14 +141,14 @@ public void insertAfter(JNode node) { checkRemoved(); list = Lists.add(list, index + 1, (T) node); - ++numVisitorChanges; + madeChanges(); } @Override public void insertBefore(JNode node) { checkRemoved(); list = Lists.add(list, index++, (T) node); - ++numVisitorChanges; + madeChanges(); } @Override @@ -161,7 +161,7 @@ checkState(); list = Lists.remove(list, index--); removed = true; - ++numVisitorChanges; + madeChanges(); } @Override @@ -170,7 +170,7 @@ checkReplacement(list.get(index), node); list = Lists.set(list, index, (T) node); replaced = true; - ++numVisitorChanges; + madeChanges(); } /** @@ -252,9 +252,8 @@ if (!canRemove) { throw new UnsupportedOperationException("Can't remove " + node); } - this.node = null; - ++numVisitorChanges; + madeChanges(); } @Override @@ -265,7 +264,7 @@ checkReplacement(this.node, node); this.node = node; replaced = true; - ++numVisitorChanges; + madeChanges(); } } @@ -380,4 +379,5 @@ protected void traverse(JNode node, Context context) { node.traverse(this, context); } + }
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/CallGraph.java b/dev/core/src/com/google/gwt/dev/jjs/impl/CallGraph.java new file mode 100644 index 0000000..07ae11f --- /dev/null +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/CallGraph.java
@@ -0,0 +1,113 @@ +/* + * Copyright 2014 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.JMethod; +import com.google.gwt.dev.jjs.ast.JMethodCall; +import com.google.gwt.dev.jjs.ast.JProgram; +import com.google.gwt.dev.jjs.ast.JVisitor; +import com.google.gwt.thirdparty.guava.common.collect.HashMultimap; +import com.google.gwt.thirdparty.guava.common.collect.Multimap; +import com.google.gwt.thirdparty.guava.common.collect.Sets; + +import java.util.Set; + +/** + * Call graph, which records {callee->callers} and {caller->callees} pairs. + */ +public class CallGraph { + + /** + * Visitor used to build call graph. + */ + private class BuildCallGraphVisitor extends JVisitor { + + // TODO(leafwang): This call graph does not take into account overloads nor calls that happen + // in JSNI methods. + + private JMethod currentMethod; + + @Override + public void endVisit(JMethod x, Context ctx) { + assert (currentMethod == x); + currentMethod = null; + } + + @Override + public void endVisit(JMethodCall x, Context ctx) { + JMethod calleeMethod = x.getTarget(); + assert (currentMethod != null); + calleeCallersPairs.put(calleeMethod, currentMethod); + callerCalleesPairs.put(currentMethod, calleeMethod); + } + + @Override + public boolean visit(JMethod x, Context ctx) { + assert (currentMethod == null); + currentMethod = x; + return true; + } + } + + private Multimap<JMethod, JMethod> calleeCallersPairs = HashMultimap.create(); + private Multimap<JMethod, JMethod> callerCalleesPairs = HashMultimap.create(); + + /** + * Build the call graph of a JProgram. + */ + public void buildCallGraph(JProgram program) { + resetCallGraph(); + BuildCallGraphVisitor buildCallGraphVisitor = new BuildCallGraphVisitor(); + buildCallGraphVisitor.accept(program); + } + + public void resetCallGraph() { + calleeCallersPairs.clear(); + callerCalleesPairs.clear(); + } + + /** + * Update call graph of a JMethod. + */ + public void updateCallGraphOfMethod(JMethod method) { + removeMethod(method); + BuildCallGraphVisitor callSiteVisitor = new BuildCallGraphVisitor(); + callSiteVisitor.currentMethod = method; + callSiteVisitor.accept(method.getBody()); + } + + /** + * For removing a method, remove the {caller->callees} and {callee->callers} pairs that are + * related to the method. + */ + public void removeMethod(JMethod method) { + for (JMethod calleeMethod : callerCalleesPairs.get(method)) { + calleeCallersPairs.remove(calleeMethod, method); + } + callerCalleesPairs.removeAll(method); + } + + /** + * Return all the callers of a set of callee methods. + */ + public Set<JMethod> getCallers(Set<JMethod> calleeMethods) { + assert (calleeMethods != null); + Set<JMethod> callerMethods = Sets.newLinkedHashSet(); + for (JMethod calleeMethod : calleeMethods) { + callerMethods.addAll(calleeCallersPairs.get(calleeMethod)); + } + return callerMethods; + } +}
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 588a75b..cf68a5d 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
@@ -47,7 +47,6 @@ import com.google.gwt.dev.jjs.ast.JLongLiteral; 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.JNewInstance; import com.google.gwt.dev.jjs.ast.JNode; import com.google.gwt.dev.jjs.ast.JParameterRef; @@ -110,8 +109,11 @@ * {@link #cast(JExpression, SourceInfo, JType, JExpression) simplifyCast}, so * that more simplifications can be made on a single pass through a tree. */ - public class DeadCodeVisitor extends JModVisitor { - private JMethod currentMethod = null; + public class DeadCodeVisitor extends JChangeTrackingVisitor { + + public DeadCodeVisitor(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } /** * Expressions whose result does not matter. A parent node should add any @@ -421,7 +423,7 @@ */ @Override public void endVisit(JIfStatement x, Context ctx) { - maybeReplaceMe(x, Simplifier.ifStatement(x, currentMethod), ctx); + maybeReplaceMe(x, Simplifier.ifStatement(x, getCurrentMethod()), ctx); } /** @@ -444,11 +446,6 @@ } } - @Override - public void endVisit(JMethod x, Context ctx) { - currentMethod = null; - } - /** * Resolve method calls that can be computed statically. */ @@ -756,12 +753,6 @@ } @Override - public boolean visit(JMethod x, Context ctx) { - currentMethod = x; - return true; - } - - @Override public boolean visit(JMethodCall x, Context ctx) { JMethod target = x.getTarget(); if (target.isStatic() && x.getInstance() != null) { @@ -1980,12 +1971,34 @@ public static final String NAME = DeadCodeElimination.class.getSimpleName(); + // TODO(leafwang): remove this entry point when it is no longer needed. public static OptimizerStats exec(JProgram program) { - return new DeadCodeElimination(program).execImpl(program); + return new DeadCodeElimination(program).execImpl(program, new OptimizerContext(program)); } + // TODO(leafwang): remove this entry point when it is no longer needed. public static OptimizerStats exec(JProgram program, JNode node) { - return new DeadCodeElimination(program).execImpl(node); + return new DeadCodeElimination(program).execImpl(node, new OptimizerContext(program)); + } + + public static OptimizerStats exec(JProgram program, OptimizerContext optimizerCtx) { + OptimizerStats stats = new DeadCodeElimination(program).execImpl(program, optimizerCtx); + optimizerCtx.incOptimizationStep(); + return stats; + } + + /** + * Apply DeadCodeElimination on a set of methods, mark the modifications in a single step. + */ + public static OptimizerStats exec(JProgram program, Set<JMethod> methods, + OptimizerContext optimizerCtx) { + OptimizerStats stats = new OptimizerStats(NAME); + for (JMethod method : methods) { + OptimizerStats innerStats = new DeadCodeElimination(program).execImpl(method, optimizerCtx); + stats.recordModified(innerStats.getNumMods()); + } + optimizerCtx.incOptimizationStep(); + return stats; } private final JProgram program; @@ -2006,11 +2019,11 @@ typeClassMap.put(program.getTypePrimitiveShort(), short.class); } - private OptimizerStats execImpl(JNode node) { + private OptimizerStats execImpl(JNode node, OptimizerContext optimizerCtx) { OptimizerStats stats = new OptimizerStats(NAME); Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - DeadCodeVisitor deadCodeVisitor = new DeadCodeVisitor(); + DeadCodeVisitor deadCodeVisitor = new DeadCodeVisitor(optimizerCtx); deadCodeVisitor.accept(node); stats.recordModified(deadCodeVisitor.getNumMods()); optimizeEvent.end("didChange", "" + stats.didChange());
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/Finalizer.java b/dev/core/src/com/google/gwt/dev/jjs/impl/Finalizer.java index 1494364..c09c475 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/Finalizer.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/Finalizer.java
@@ -27,7 +27,6 @@ import com.google.gwt.dev.jjs.ast.JLocal; import com.google.gwt.dev.jjs.ast.JMethod; import com.google.gwt.dev.jjs.ast.JMethodBody; -import com.google.gwt.dev.jjs.ast.JModVisitor; import com.google.gwt.dev.jjs.ast.JParameter; import com.google.gwt.dev.jjs.ast.JPostfixOperation; import com.google.gwt.dev.jjs.ast.JPrefixOperation; @@ -59,7 +58,11 @@ * program. But if it wasn't implemented, then the enclosing class should have * come up as not instantiated and been culled. So I think it's not possible. */ - private class FinalizeVisitor extends JModVisitor { + private class FinalizeVisitor extends JChangeTrackingVisitor { + + public FinalizeVisitor(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } @Override public void endVisit(JClassType x, Context ctx) { @@ -74,7 +77,7 @@ } @Override - public void endVisit(JField x, Context ctx) { + public void exitField(JField x, Context ctx) { if (!x.isVolatile()) { maybeFinalize(x); } @@ -86,7 +89,7 @@ } @Override - public void endVisit(JMethod x, Context ctx) { + public void exitMethod(JMethod x, Context ctx) { if (!x.isFinal() && !isOverridden.contains(x)) { setFinal(x); } @@ -208,9 +211,18 @@ private static final String NAME = Finalizer.class.getSimpleName(); + // TODO(leafwang): remove this entry point when it is no longer needed. public static OptimizerStats exec(JProgram program) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new Finalizer().execImpl(program); + OptimizerStats stats = new Finalizer().execImpl(program, new OptimizerContext(program)); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } + + public static OptimizerStats exec(JProgram program, OptimizerContext optimizerCtx) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = new Finalizer().execImpl(program, optimizerCtx); + optimizerCtx.incOptimizationStep(); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } @@ -221,14 +233,11 @@ private final Set<JClassType> isSubclassed = new HashSet<JClassType>(); - private Finalizer() { - } - - private OptimizerStats execImpl(JProgram program) { + private OptimizerStats execImpl(JProgram program, OptimizerContext optimizerCtx) { MarkVisitor marker = new MarkVisitor(); marker.accept(program); - FinalizeVisitor finalizer = new FinalizeVisitor(); + FinalizeVisitor finalizer = new FinalizeVisitor(optimizerCtx); finalizer.accept(program); return new OptimizerStats(NAME).recordModified(finalizer.getNumMods());
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/JChangeTrackingVisitor.java b/dev/core/src/com/google/gwt/dev/jjs/impl/JChangeTrackingVisitor.java new file mode 100644 index 0000000..91caad0 --- /dev/null +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/JChangeTrackingVisitor.java
@@ -0,0 +1,110 @@ +/* + * Copyright 2014 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.JField; +import com.google.gwt.dev.jjs.ast.JMethod; +import com.google.gwt.dev.jjs.ast.JModVisitor; + +/** + * A visitor for optimizing an AST. + */ +public abstract class JChangeTrackingVisitor extends JModVisitor { + + private JField currentField; + private JMethod currentMethod; + private final OptimizerContext optimizerCtx; + private boolean fieldModified = false; + private boolean methodModified = false; + + public JChangeTrackingVisitor(OptimizerContext optimizerCtx) { + this.optimizerCtx = optimizerCtx; + } + + public boolean enterField(JField f, Context ctx) { + return true; + } + + public boolean enterMethod(JMethod x, Context ctx) { + return true; + } + + public JField getCurrentField() { + return currentField; + } + + public JMethod getCurrentMethod() { + return currentMethod; + } + + public void exitField(JField f, Context ctx) { + return; + } + + public void exitMethod(JMethod x, Context ctx) { + return; + } + + @Override + public final void endVisit(JField x, Context ctx) { + exitField(x, ctx); + if (fieldModified) { + optimizerCtx.markModifiedField(x); + } + currentField = null; + } + + @Override + public final void endVisit(JMethod x, Context ctx) { + exitMethod(x, ctx); + if (methodModified) { + optimizerCtx.markModifiedMethod(x); + } + currentMethod = null; + } + + @Override + public final boolean visit(JField x, Context ctx) { + currentField = x; + fieldModified = false; + return enterField(x, ctx); + } + + @Override + public final boolean visit(JMethod x, Context ctx) { + currentMethod = x; + methodModified = false; + return enterMethod(x, ctx); + } + + @Override + protected void madeChanges() { + super.madeChanges(); + if (currentMethod != null) { + methodModified = true; + } + if (currentField != null) { + fieldModified = true; + } + } + + public void fieldWasRemoved(JField field) { + optimizerCtx.removeField(field); + } + + public void methodWasRemoved(JMethod method) { + optimizerCtx.removeMethod(method); + } +}
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/MakeCallsStatic.java b/dev/core/src/com/google/gwt/dev/jjs/impl/MakeCallsStatic.java index 5945ddf..b9d7372 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/MakeCallsStatic.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/MakeCallsStatic.java
@@ -27,7 +27,6 @@ import com.google.gwt.dev.jjs.ast.JMethod.Specialization; import com.google.gwt.dev.jjs.ast.JMethodBody; import com.google.gwt.dev.jjs.ast.JMethodCall; -import com.google.gwt.dev.jjs.ast.JModVisitor; import com.google.gwt.dev.jjs.ast.JParameter; import com.google.gwt.dev.jjs.ast.JParameterRef; import com.google.gwt.dev.jjs.ast.JProgram; @@ -105,12 +104,14 @@ * thisRefs must be replaced with paramRefs to the synthetic this param. * ParameterRefs also need to be targeted to the params in the new method. */ - private class RewriteMethodBody extends JModVisitor { + private class RewriteMethodBody extends JChangeTrackingVisitor { private final JParameter thisParam; private final Map<JParameter, JParameter> varMap; - public RewriteMethodBody(JParameter thisParam, Map<JParameter, JParameter> varMap) { + public RewriteMethodBody(JParameter thisParam, Map<JParameter, JParameter> varMap, + OptimizerContext optimizerCtx) { + super(optimizerCtx); this.thisParam = thisParam; this.varMap = varMap; } @@ -130,9 +131,16 @@ } private final JProgram program; + private final OptimizerContext optimizerCtx; + + private CreateStaticImplsVisitor(JProgram program, OptimizerContext optimizerCtx) { + this.program = program; + this.optimizerCtx = optimizerCtx; + } CreateStaticImplsVisitor(JProgram program) { this.program = program; + this.optimizerCtx = null; } @Override @@ -217,13 +225,18 @@ // Accept the body to avoid the recursion blocker. rewriter.accept(jsFunc.getBody()); } else { - RewriteMethodBody rewriter = new RewriteMethodBody(thisParam, varMap); + RewriteMethodBody rewriter = new RewriteMethodBody(thisParam, varMap, optimizerCtx); rewriter.accept(movedBody); } // Add the new method as a static impl of the old method program.putStaticImpl(x, newMethod); enclosingType.getMethods().add(myIndexInClass + 1, newMethod); + + if (optimizerCtx != null) { + optimizerCtx.markModifiedMethod(x); + optimizerCtx.markModifiedMethod(newMethod); + } return false; } } @@ -299,10 +312,15 @@ * CreateStaticMethodVisitor, go and rewrite the call sites to call the static * method instead. */ - private class RewriteCallSites extends JModVisitor { + private class RewriteCallSites extends JChangeTrackingVisitor { + private boolean currentMethodIsInitiallyLive; private ControlFlowAnalyzer initiallyLive; + public RewriteCallSites(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } + /** * In cases where callers are directly referencing (effectively) final * instance methods, rewrite the call site to reference the newly-generated @@ -332,7 +350,7 @@ } @Override - public boolean visit(JMethod x, Context ctx) { + public boolean enterMethod(JMethod x, Context ctx) { currentMethodIsInitiallyLive = initiallyLive.getLiveFieldsAndMethods().contains(x); return true; } @@ -420,14 +438,23 @@ private static final String NAME = MakeCallsStatic.class.getSimpleName(); - public static OptimizerStats exec(JProgram program, boolean addRuntimeChecks) { + public static OptimizerStats exec(JProgram program, boolean addRuntimeChecks, + OptimizerContext optimizerCtx) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new MakeCallsStatic(program, addRuntimeChecks).execImpl(); + OptimizerStats stats = new MakeCallsStatic(program, addRuntimeChecks).execImpl(optimizerCtx); + optimizerCtx.incOptimizationStep(); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } - + // TODO(leafwang): remove this entry point when it is no longer needed. + public static OptimizerStats exec(JProgram program, boolean addRuntimeChecks) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = + new MakeCallsStatic(program, addRuntimeChecks).execImpl(new OptimizerContext(program)); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } protected Set<JMethod> toBeMadeStatic = new HashSet<JMethod>(); @@ -439,12 +466,12 @@ this.converter = new StaticCallConverter(program, addRuntimeChecks); } - private OptimizerStats execImpl() { + private OptimizerStats execImpl(OptimizerContext optimizerCtx) { OptimizerStats stats = new OptimizerStats(NAME); FindStaticDispatchSitesVisitor finder = new FindStaticDispatchSitesVisitor(); finder.accept(program); - CreateStaticImplsVisitor creator = new CreateStaticImplsVisitor(program); + CreateStaticImplsVisitor creator = new CreateStaticImplsVisitor(program, optimizerCtx); for (JMethod method : toBeMadeStatic) { creator.accept(method); } @@ -468,7 +495,7 @@ * optimizations can unlock devirtualizations even if no more static impls * are created. */ - RewriteCallSites rewriter = new RewriteCallSites(); + RewriteCallSites rewriter = new RewriteCallSites(optimizerCtx); rewriter.accept(program); stats.recordModified(rewriter.getNumMods()); assert (rewriter.didChange() || toBeMadeStatic.isEmpty());
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallSpecializer.java b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallSpecializer.java index 661e42b..1e5b005 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallSpecializer.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallSpecializer.java
@@ -18,7 +18,6 @@ import com.google.gwt.dev.jjs.ast.Context; 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.JNullType; import com.google.gwt.dev.jjs.ast.JProgram; import com.google.gwt.dev.jjs.ast.JType; @@ -36,7 +35,11 @@ */ public class MethodCallSpecializer { - private class MethodCallSpecializingVisitor extends JModVisitor { + private class MethodCallSpecializingVisitor extends JChangeTrackingVisitor { + + public MethodCallSpecializingVisitor(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } @Override public void endVisit(JMethodCall x, Context ctx) { @@ -83,9 +86,18 @@ public static final String NAME = MethodCallSpecializer.class.getSimpleName(); + // TODO(leafwang): remove this entry point when it is no longer needed. public static OptimizerStats exec(JProgram program) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new MethodCallSpecializer(program).execImpl(); + OptimizerStats stats = new MethodCallSpecializer(program).execImpl(new OptimizerContext(program)); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } + + public static OptimizerStats exec(JProgram program, OptimizerContext optimizerCtx) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = new MethodCallSpecializer(program).execImpl(optimizerCtx); + optimizerCtx.incOptimizationStep(); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } @@ -96,10 +108,9 @@ this.program = program; } - private OptimizerStats execImpl() { - MethodCallSpecializingVisitor specializer = - new MethodCallSpecializingVisitor(); + private OptimizerStats execImpl(OptimizerContext optimizerCtx) { + MethodCallSpecializingVisitor specializer = new MethodCallSpecializingVisitor(optimizerCtx); specializer.accept(program); return new OptimizerStats(NAME).recordModified(specializer.getNumMods()); } -} \ No newline at end of file +}
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java index fce0df8..d72d0da 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/MethodCallTightener.java
@@ -19,7 +19,6 @@ import com.google.gwt.dev.jjs.ast.JClassType; 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.JNewInstance; import com.google.gwt.dev.jjs.ast.JProgram; import com.google.gwt.dev.jjs.ast.JRunAsync; @@ -52,7 +51,11 @@ * Updates polymorphic method calls to tighter bindings based on the type of * the qualifier. */ - public class MethodCallTighteningVisitor extends JModVisitor { + public class MethodCallTighteningVisitor extends JChangeTrackingVisitor { + + public MethodCallTighteningVisitor(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } @Override public void endVisit(JMethodCall x, Context ctx) { @@ -114,9 +117,18 @@ public static final String NAME = MethodCallTightener.class.getSimpleName(); + // TODO(leafwang): remove this entry point when it is no longer needed. public static OptimizerStats exec(JProgram program) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new MethodCallTightener(program).execImpl(); + OptimizerStats stats = new MethodCallTightener(program).execImpl(new OptimizerContext(program)); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } + + public static OptimizerStats exec(JProgram program, OptimizerContext optimizerCtx) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = new MethodCallTightener(program).execImpl(optimizerCtx); + optimizerCtx.incOptimizationStep(); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } @@ -127,9 +139,9 @@ this.program = program; } - private OptimizerStats execImpl() { - MethodCallTighteningVisitor tightener = new MethodCallTighteningVisitor(); + private OptimizerStats execImpl(OptimizerContext optimizerCtx) { + MethodCallTighteningVisitor tightener = new MethodCallTighteningVisitor(optimizerCtx); tightener.accept(program); return new OptimizerStats(NAME).recordModified(tightener.getNumMods()); } -} \ No newline at end of file +}
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 de4aca5..84d6d33 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
@@ -44,7 +44,6 @@ import com.google.gwt.thirdparty.guava.common.collect.Lists; import com.google.gwt.thirdparty.guava.common.collect.Sets; -import java.util.LinkedHashSet; import java.util.List; import java.util.Set; @@ -78,8 +77,11 @@ /** * Method inlining visitor. */ - private class InliningVisitor extends JModVisitor { - protected final Set<JMethod> modifiedMethods = new LinkedHashSet<JMethod>(); + private class InliningVisitor extends JChangeTrackingVisitor { + + public InliningVisitor(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } /** * Resets with each new visitor, which is good since things that couldn't be @@ -94,15 +96,10 @@ } @Override - public void endVisit(JMethod x, Context ctx) { - currentMethod = null; - } - - @Override public void endVisit(JMethodCall x, Context ctx) { JMethod method = x.getTarget(); - if (currentMethod == method) { + if (getCurrentMethod() == method) { // Never try to inline a recursive call! return; } @@ -180,8 +177,7 @@ } @Override - public boolean visit(JMethod x, Context ctx) { - currentMethod = x; + public boolean enterMethod(JMethod x, Context ctx) { if (program.getStaticImpl(x) != null) { /* * Never inline a static impl into the calling instance method. We used @@ -209,7 +205,7 @@ private JMethodCall createClinitCall(JMethodCall x) { JDeclaredType targetType = x.getTarget().getEnclosingType().getClinitTarget(); - if (!currentMethod.getEnclosingType().checkClinitTo(targetType)) { + if (!getCurrentMethod().getEnclosingType().checkClinitTo(targetType)) { // Access from this class to the target class won't trigger a clinit return null; } @@ -295,15 +291,6 @@ } /** - * Replace the current expression with a given replacement and mark the - * method as modified. - */ - private void replaceMeAndRecordModification(Context ctx, JExpression replacement) { - ctx.replaceMe(replacement); - modifiedMethods.add(currentMethod); - } - - /** * Inline a call to an expression. Returns {@code InlineResult.BLACKLIST} if the method is * deemed not inlineable regardless of call site; {@code InlineResult.DO_NOT_BLACKLIST} * otherwise. @@ -368,8 +355,7 @@ if (orderVisitor.checkResults() == SideEffectCheck.NO_REFERENCES) { List<JExpression> expressions = expressionsIncludingArgs(x); expressions.addAll(bodyAsExpressionList); - replaceMeAndRecordModification(ctx, - JjsUtils.createOptimizedMultiExpression(ignoringReturn, expressions)); + ctx.replaceMe(JjsUtils.createOptimizedMultiExpression(ignoringReturn, expressions)); return InlineResult.DO_NOT_BLACKLIST; } @@ -403,7 +389,7 @@ replacer.accept(bodyAsExpressionList); bodyAsExpressionList.add(0, x.getInstance()); bodyAsExpressionList.add(1, createClinitCall(x)); - replaceMeAndRecordModification(ctx, JjsUtils.createOptimizedMultiExpression(ignoringReturn, + ctx.replaceMe(JjsUtils.createOptimizedMultiExpression(ignoringReturn, bodyAsExpressionList)); return InlineResult.DO_NOT_BLACKLIST; } @@ -543,14 +529,20 @@ public static String NAME = MethodInliner.class.getSimpleName(); - public static OptimizerStats exec(JProgram program) { + public static OptimizerStats exec(JProgram program, OptimizerContext optimizerCtx) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new MethodInliner(program).execImpl(); + OptimizerStats stats = new MethodInliner(program).execImpl(optimizerCtx); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } - private JMethod currentMethod; + // TODO(leafwang): remove this entry point when it is no longer needed. + public static OptimizerStats exec(JProgram program) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = new MethodInliner(program).execImpl(new OptimizerContext(program)); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } private final JProgram program; @@ -558,26 +550,52 @@ this.program = program; } - private OptimizerStats execImpl() { + private OptimizerStats execImpl(OptimizerContext optimizerCtx) { OptimizerStats stats = new OptimizerStats(NAME); + int lastStep = optimizerCtx.getLastStepFor(NAME); while (true) { - InliningVisitor inliner = new InliningVisitor(); - inliner.accept(program); + InliningVisitor inliner = new InliningVisitor(optimizerCtx); + + // TODO(leafwang): generalize this part to avoid explicitly implementing this loop in each + // Visitor. + Set<JMethod> modifiedMethods = optimizerCtx.getModifiedMethodsSince(lastStep); + Set<JMethod> affectedMethods = affectedMethods(modifiedMethods, optimizerCtx); + for (JMethod method : affectedMethods) { + inliner.accept(method); + } + stats.recordModified(inliner.getNumMods()); + lastStep = optimizerCtx.getOptimizationStep(); + optimizerCtx.incOptimizationStep(); + if (!inliner.didChange()) { break; } // Run a cleanup on the methods we just modified - for (JMethod method : inliner.modifiedMethods) { - OptimizerStats innerStats = DeadCodeElimination.exec(program, method); - stats.recordModified(innerStats.getNumMods()); - } + OptimizerStats dceStats = DeadCodeElimination.exec(program, + optimizerCtx.getModifiedMethodsAt(lastStep), optimizerCtx); + stats.recordModified(dceStats.getNumMods()); } + optimizerCtx.setLastStepFor(NAME, optimizerCtx.getOptimizationStep()); return stats; } /** + * Return the set of methods affected (because they are or callers of) by the modifications to the + * given set functions. + */ + private Set<JMethod> affectedMethods(Set<JMethod> modifiedMethods, OptimizerContext optimizerCtx) { + Set<JMethod> affectedMethods = Sets.newLinkedHashSet(); + if (modifiedMethods == null || modifiedMethods.size() == 0) { + return affectedMethods; + } + affectedMethods.addAll(modifiedMethods); + affectedMethods.addAll(optimizerCtx.getCallers(modifiedMethods)); + return affectedMethods; + } + + /** * Insert an implicit cast if the types differ; it might get optimized out * later, but in some cases it will force correct math evaluation. */
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/OptimizerContext.java b/dev/core/src/com/google/gwt/dev/jjs/impl/OptimizerContext.java new file mode 100644 index 0000000..5920c6d --- /dev/null +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/OptimizerContext.java
@@ -0,0 +1,187 @@ +/* + * Copyright 2014 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.JDeclaredType; +import com.google.gwt.dev.jjs.ast.JField; +import com.google.gwt.dev.jjs.ast.JMethod; +import com.google.gwt.dev.jjs.ast.JProgram; +import com.google.gwt.thirdparty.guava.common.collect.HashMultiset; +import com.google.gwt.thirdparty.guava.common.collect.Lists; +import com.google.gwt.thirdparty.guava.common.collect.Multiset; +import com.google.gwt.thirdparty.guava.common.collect.Sets; + +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; + +/** + * Maintains dependence and modification information for AST optimizers. + * <p> + * Is updated incrementally. + */ +public class OptimizerContext { + private int optimizationStep = -1; + + private CallGraph callGraph = new CallGraph(); + + // TODO(leafwang): add other dependencies here + + /** + * A mapping from methods to the numbers of the most recent step in which they were modified. + */ + private Multiset<JMethod> modificationStepByMethod = HashMultiset.create(); + + /** + * A list of modified methods in each step. + */ + private List<Set<JMethod>> methodsByModificationStep = Lists.newArrayList(); + + /** + * A mapping from methods to the numbers of the most recent step in which they were modified. + */ + private Multiset<JField> modificationStepByField = HashMultiset.create(); + + /** + * A list of modified fields in each step. + */ + private List<Set<JField>> fieldsByModificationStep = Lists.newArrayList(); + + /** + * A mapping from optimizers to their last modification step. + */ + private Multiset<String> lastStepForOptimizer = HashMultiset.create(); + + public OptimizerContext(JProgram program) { + incOptimizationStep(); + initializeModifications(program); + buildCallGraph(program); + incOptimizationStep(); + } + + /** + * Add modified field to the modification information. + */ + public void markModifiedField(JField modifiedField) { + fieldsByModificationStep.get(modificationStepByField.count(modifiedField)).remove( + modifiedField); + fieldsByModificationStep.get(optimizationStep).add(modifiedField); + modificationStepByField.setCount(modifiedField, optimizationStep); + + // TODO(leafwang): update related dependence information here. + } + + /** + * Add modified method to both the modification and dependence information. + */ + public void markModifiedMethod(JMethod modifiedMethod) { + methodsByModificationStep.get(modificationStepByMethod.count(modifiedMethod)).remove( + modifiedMethod); + methodsByModificationStep.get(optimizationStep).add(modifiedMethod); + modificationStepByMethod.setCount(modifiedMethod, optimizationStep); + callGraph.updateCallGraphOfMethod(modifiedMethod); + } + + public Set<JMethod> getCallers(Set<JMethod> calleeMethods) { + return callGraph.getCallers(calleeMethods); + } + + /** + * Return the last modification step for a given optimizer. + */ + public int getLastStepFor(String optimizerName) { + return lastStepForOptimizer.count(optimizerName); + } + + /** + * Return all the effective modified fields since a given step. + */ + public Set<JField> getModifiedFieldsSince(int stepSince) { + Set<JField> result = Sets.newLinkedHashSet(); + for (int i = stepSince; i <= optimizationStep; i++) { + result.addAll(fieldsByModificationStep.get(i)); + } + return result; + } + + /** + * Return all the modified methods at a given step. + */ + public Set<JMethod> getModifiedMethodsAt(int step) { + assert (step >= 0 && step <= optimizationStep); + return new LinkedHashSet<JMethod>(methodsByModificationStep.get(step)); + } + + /** + * Return all the effective modified methods since a given step. + */ + public Set<JMethod> getModifiedMethodsSince(int stepSince) { + Set<JMethod> result = Sets.newLinkedHashSet(); + for (int i = stepSince; i <= optimizationStep; i++) { + result.addAll(methodsByModificationStep.get(i)); + } + return result; + } + + /** + * Return the current optimization step number. + */ + public int getOptimizationStep() { + return optimizationStep; + } + + /** + * Increase the optimization step by 1, create a new set to record modifications in this step. + */ + public void incOptimizationStep() { + methodsByModificationStep.add(new LinkedHashSet<JMethod>()); + fieldsByModificationStep.add(new LinkedHashSet<JField>()); + optimizationStep++; + } + + /** + * Remove field from the modification information. + */ + public void removeField(JField field) { + fieldsByModificationStep.get(modificationStepByField.count(field)).remove(field); + modificationStepByField.remove(field); + } + + /** + * Remove method from both the dependence and modification information. + */ + public void removeMethod(JMethod method) { + methodsByModificationStep.get(modificationStepByMethod.count(method)).remove(method); + modificationStepByMethod.remove(method); + callGraph.removeMethod(method); + } + + /** + * Set the last modification step of a given optimizer. + */ + public void setLastStepFor(String optimizerName, int step) { + lastStepForOptimizer.setCount(optimizerName, step); + } + + private void buildCallGraph(JProgram program) { + callGraph.buildCallGraph(program); + } + + private void initializeModifications(JProgram program) { + for (JDeclaredType type : program.getModuleDeclaredTypes()) { + fieldsByModificationStep.get(0).addAll(type.getFields()); + methodsByModificationStep.get(0).addAll(type.getMethods()); + } + } +}
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/Pruner.java b/dev/core/src/com/google/gwt/dev/jjs/impl/Pruner.java index 0880fe5..8f41e26 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/Pruner.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/Pruner.java
@@ -35,7 +35,6 @@ import com.google.gwt.dev.jjs.ast.JMethod; import com.google.gwt.dev.jjs.ast.JMethodBody; import com.google.gwt.dev.jjs.ast.JMethodCall; -import com.google.gwt.dev.jjs.ast.JModVisitor; import com.google.gwt.dev.jjs.ast.JNameOf; import com.google.gwt.dev.jjs.ast.JNewInstance; import com.google.gwt.dev.jjs.ast.JNode; @@ -89,7 +88,7 @@ * references to pruned variables and methods by references to the null field * and null method, and drop assignments to pruned variables. */ - private class CleanupRefsVisitor extends JModVisitor { + private class CleanupRefsVisitor extends JChangeTrackingVisitor { private final Stack<JExpression> lValues = new Stack<JExpression>(); private final Map<JMethod, ArrayList<JParameter>> methodToOriginalParamsMap; private final Set<? extends JNode> referencedNonTypes; @@ -99,7 +98,8 @@ } public CleanupRefsVisitor(Set<? extends JNode> referencedNodes, - Map<JMethod, ArrayList<JParameter>> methodToOriginalParamsMap) { + Map<JMethod, ArrayList<JParameter>> methodToOriginalParamsMap, OptimizerContext optimizerCtx) { + super(optimizerCtx); this.referencedNonTypes = referencedNodes; this.methodToOriginalParamsMap = methodToOriginalParamsMap; } @@ -151,7 +151,7 @@ } @Override - public void endVisit(JMethod x, Context ctx) { + public void exitMethod(JMethod x, Context ctx) { JType type = x.getType(); if (type instanceof JReferenceType && !program.typeOracle.isInstantiatedType((JReferenceType) type)) { @@ -336,14 +336,15 @@ * Remove any unreferenced classes and interfaces from JProgram. Remove any * unreferenced methods and fields from their containing classes. */ - private class PruneVisitor extends JModVisitor { + private class PruneVisitor extends JChangeTrackingVisitor { private final Map<JMethod, ArrayList<JParameter>> methodToOriginalParamsMap = new HashMap<JMethod, ArrayList<JParameter>>(); private final Set<? extends JNode> referencedNonTypes; private final Set<? extends JReferenceType> referencedTypes; public PruneVisitor(Set<? extends JReferenceType> referencedTypes, - Set<? extends JNode> referencedNodes) { + Set<? extends JNode> referencedNodes, OptimizerContext optimizerCtx) { + super(optimizerCtx); this.referencedTypes = referencedTypes; this.referencedNonTypes = referencedNodes; } @@ -358,6 +359,7 @@ for (int i = 0; i < type.getFields().size(); ++i) { JField field = type.getFields().get(i); if (!referencedNonTypes.contains(field)) { + fieldWasRemoved(field); type.removeField(i); madeChanges(); --i; @@ -369,7 +371,9 @@ if (!referencedNonTypes.contains(method)) { // Never prune clinit directly out of the class. if (i > 0) { + methodWasRemoved(method); type.removeMethod(i); + methodWasRemoved(program.getStaticImpl(method)); program.removeStaticImplMapping(method); madeChanges(); --i; @@ -391,6 +395,7 @@ JField field = type.getFields().get(i); // all interface fields are static and final if (!isReferenced || !referencedNonTypes.contains(field)) { + fieldWasRemoved(field); type.removeField(i); madeChanges(); --i; @@ -402,6 +407,7 @@ JMethod method = type.getMethods().get(i); // all other interface methods are instance and abstract if (!isInstantiated || !referencedNonTypes.contains(method)) { + methodWasRemoved(method); type.removeMethod(i); assert program.instanceMethodForStaticImpl(method) == null; madeChanges(); @@ -413,7 +419,7 @@ } @Override - public boolean visit(JMethod x, Context ctx) { + public boolean enterMethod(JMethod x, Context ctx) { if (!x.canBePolymorphic()) { /* * Don't prune parameters on unreferenced methods. The methods might not @@ -498,9 +504,19 @@ private static final String NAME = Pruner.class.getSimpleName(); + public static OptimizerStats exec(JProgram program, boolean noSpecialTypes, + OptimizerContext optimizerCtx) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = new Pruner(program, noSpecialTypes).execImpl(optimizerCtx); + optimizerCtx.incOptimizationStep(); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } + + // TODO(leafwang): remove this entry point when it is no longer needed. public static OptimizerStats exec(JProgram program, boolean noSpecialTypes) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new Pruner(program, noSpecialTypes).execImpl(); + OptimizerStats stats = new Pruner(program, noSpecialTypes).execImpl(new OptimizerContext(program)); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } @@ -612,7 +628,7 @@ this.saveCodeGenTypes = saveCodeGenTypes; } - private OptimizerStats execImpl() { + private OptimizerStats execImpl(OptimizerContext optimizerCtx) { OptimizerStats stats = new OptimizerStats(NAME); ControlFlowAnalyzer livenessAnalyzer = new ControlFlowAnalyzer(program); @@ -640,15 +656,16 @@ PruneVisitor pruner = new PruneVisitor(livenessAnalyzer.getReferencedTypes(), livenessAnalyzer - .getLiveFieldsAndMethods()); + .getLiveFieldsAndMethods(), optimizerCtx); pruner.accept(program); stats.recordModified(pruner.getNumMods()); + if (!pruner.didChange()) { return stats; } CleanupRefsVisitor cleaner = new CleanupRefsVisitor(livenessAnalyzer.getLiveFieldsAndMethods(), pruner - .getMethodToOriginalParamsMap()); + .getMethodToOriginalParamsMap(), optimizerCtx); cleaner.accept(program.getDeclaredTypes()); return stats; }
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java b/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java index 97e8394..fcd27be 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java
@@ -21,7 +21,6 @@ import com.google.gwt.dev.jjs.ast.JExpression; 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.JParameter; import com.google.gwt.dev.jjs.ast.JParameterRef; @@ -163,12 +162,14 @@ /** * Substitute all parameter references with expression. */ - private class SubstituteParameterVisitor extends JModVisitor { + private class SubstituteParameterVisitor extends JChangeTrackingVisitor { private final CloneExpressionVisitor cloner; private final JExpression expression; private final JParameter parameter; - public SubstituteParameterVisitor(JParameter parameter, JExpression expression) { + public SubstituteParameterVisitor(JParameter parameter, JExpression expression, + OptimizerContext optimizerCtx) { + super(optimizerCtx); this.parameter = parameter; this.expression = expression; cloner = new CloneExpressionVisitor(); @@ -186,7 +187,16 @@ public static OptimizerStats exec(JProgram program) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new SameParameterValueOptimizer(program).execImpl(program); + OptimizerStats stats = + new SameParameterValueOptimizer(program).execImpl(program, new OptimizerContext(program)); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } + + public static OptimizerStats exec(JProgram program, OptimizerContext optimizerCtx) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = new SameParameterValueOptimizer(program).execImpl(program, optimizerCtx); + optimizerCtx.incOptimizationStep(); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } @@ -215,7 +225,7 @@ this.program = program; } - private OptimizerStats execImpl(JNode node) { + private OptimizerStats execImpl(JNode node, OptimizerContext optimizerCtx) { OptimizerStats stats = new OptimizerStats(NAME); AnalysisVisitor analysisVisitor = new AnalysisVisitor(); analysisVisitor.accept(node); @@ -228,7 +238,7 @@ if (valueLiteral != null) { SubstituteParameterVisitor substituteParameterVisitor = new SubstituteParameterVisitor(parameter, Simplifier.cast(parameter.getType(), - valueLiteral)); + valueLiteral), optimizerCtx); substituteParameterVisitor.accept(parameter.getEnclosingMethod()); stats.recordModified(substituteParameterVisitor.getNumMods()); }
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/TypeTightener.java b/dev/core/src/com/google/gwt/dev/jjs/impl/TypeTightener.java index 7ba0e69..a531e5b 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/TypeTightener.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/TypeTightener.java
@@ -35,7 +35,6 @@ import com.google.gwt.dev.jjs.ast.JLocal; 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.JNewInstance; import com.google.gwt.dev.jjs.ast.JNullType; import com.google.gwt.dev.jjs.ast.JParameter; @@ -125,7 +124,11 @@ /** * Replaces dangling null references with dummy calls. */ - public class FixDanglingRefsVisitor extends JModVisitor { + public class FixDanglingRefsVisitor extends JChangeTrackingVisitor { + + public FixDanglingRefsVisitor(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } @Override public void endVisit(JFieldRef x, Context ctx) { @@ -370,7 +373,11 @@ * * Also optimize dynamic casts and instanceof operations where possible. */ - public class TightenTypesVisitor extends JModVisitor { + public class TightenTypesVisitor extends JChangeTrackingVisitor { + + public TightenTypesVisitor(OptimizerContext optimizerCtx) { + super(optimizerCtx); + } /** * Tries to determine a specific concrete type for the cast, then either @@ -443,7 +450,7 @@ } @Override - public void endVisit(JField x, Context ctx) { + public void exitField(JField x, Context ctx) { if (!x.isVolatile()) { tighten(x); } @@ -523,7 +530,7 @@ * Tighten based on return types and overrides. */ @Override - public void endVisit(JMethod x, Context ctx) { + public void exitMethod(JMethod x, Context ctx) { if (!(x.getType() instanceof JReferenceType)) { return; } @@ -650,7 +657,7 @@ } @Override - public boolean visit(JMethod x, Context ctx) { + public boolean enterMethod(JMethod x, Context ctx) { /* * Explicitly NOT visiting native methods since we can't infer further * type information. @@ -781,9 +788,18 @@ private static final String NAME = TypeTightener.class.getSimpleName(); + public static OptimizerStats exec(JProgram program, OptimizerContext optimizerCtx) { + Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); + OptimizerStats stats = new TypeTightener(program).execImpl(optimizerCtx); + optimizerCtx.incOptimizationStep(); + optimizeEvent.end("didChange", "" + stats.didChange()); + return stats; + } + + // TODO(leafwang): remove this entry point when it is no longer needed. public static OptimizerStats exec(JProgram program) { Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); - OptimizerStats stats = new TypeTightener(program).execImpl(); + OptimizerStats stats = new TypeTightener(program).execImpl(new OptimizerContext(program)); optimizeEvent.end("didChange", "" + stats.didChange()); return stats; } @@ -864,7 +880,7 @@ typeNull = program.getTypeNull(); } - private OptimizerStats execImpl() { + private OptimizerStats execImpl(OptimizerContext optimizerCtx) { OptimizerStats stats = new OptimizerStats(NAME); RecordVisitor recorder = new RecordVisitor(); recorder.record(program); @@ -879,7 +895,7 @@ * output. */ while (true) { - TightenTypesVisitor tightener = new TightenTypesVisitor(); + TightenTypesVisitor tightener = new TightenTypesVisitor(optimizerCtx); tightener.accept(program); stats.recordModified(tightener.getNumMods()); if (!tightener.didChange()) { @@ -888,7 +904,7 @@ } if (stats.didChange()) { - FixDanglingRefsVisitor fixer = new FixDanglingRefsVisitor(); + FixDanglingRefsVisitor fixer = new FixDanglingRefsVisitor(optimizerCtx); fixer.accept(program); }
diff --git a/dev/core/test/com/google/gwt/dev/jjs/impl/MethodInlinerTest.java b/dev/core/test/com/google/gwt/dev/jjs/impl/MethodInlinerTest.java new file mode 100644 index 0000000..be21d82 --- /dev/null +++ b/dev/core/test/com/google/gwt/dev/jjs/impl/MethodInlinerTest.java
@@ -0,0 +1,165 @@ +/* + * Copyright 2014 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.JMethod; +import com.google.gwt.dev.jjs.ast.JProgram; + +/** + * Test for {@link MethodInliner}. + */ +public class MethodInlinerTest extends OptimizerTestBase { + @Override + protected void setUp() throws Exception { + super.setUp(); + } + + public void testNoMethodCall() throws Exception { + addSnippetClassDecl("static int fun1(int a) { return a; }"); + addSnippetClassDecl("static int fun2(int a, int b) { return a + b; }"); + Result result = optimize("void", ""); + assertEquals("static int fun1(int a){\n" + " return a;\n}", + result.findMethod("fun1").toSource()); + assertEquals("static int fun2(int a, int b){\n" + " return a + b;\n}", + result.findMethod("fun2").toSource()); + } + + public void testSimple() throws Exception { + addSnippetClassDecl("static int fun1(int a) { return a; }"); + addSnippetClassDecl("static int fun2(int a, int b) { return a + b; }"); + addSnippetClassDecl("static int fun3(int a) { return 1 + fun1(a); }"); + addSnippetClassDecl("static int fun4() {", " int a = 1;", " int b = 2;", + " return fun1(a) + fun2(a, b); }"); + Result result = optimize("int", "return fun3(1) + fun4();"); + + // one method call in caller + assertEquals("static int fun3(int a){\n" + " return 1 + a;\n" + "}", + result.findMethod("fun3").toSource()); + + // two method calls in caller + assertEquals( + "static int fun4(){\n" + " int a = 1;\n" + " int b = 2;\n" + " return a + a + b;\n}", + result.findMethod("fun4").toSource()); + } + + public void testLargerMethodBody() throws Exception { + addSnippetClassDecl("static void fun0(int a) { int b = a; b++; assert(b>0); }"); + addSnippetClassDecl("static int fun1(int a) { fun0(a); return 2 + a; }"); + addSnippetClassDecl("static int fun2(int a) { return 1 + fun1(a); }"); + addSnippetClassDecl("static int fun3() {", " int a = 1;", " int b = 2;", " a = a + fun1(a);", + " return a + fun1(b); }"); + Result result = optimize("int", "return fun2(1);"); + assertEquals( + "static int fun1(int a){\n" + " EntryPoint.fun0(a);\n" + " return 2 + a;\n" + "}", + result.findMethod("fun1").toSource()); + // one method call in caller + assertEquals("static int fun2(int a){\n" + " return (EntryPoint.fun0(a), 1 + 2 + a);\n}", + result.findMethod("fun2").toSource()); + + // two method calls in caller + assertEquals("static int fun3(){\n" + " int a = 1;\n" + " int b = 2;\n" + + " a = a + ((EntryPoint.fun0(a), 2 + a));\n" + + " return a + ((EntryPoint.fun0(b), 2 + b));\n}", result.findMethod("fun3").toSource()); + } + + public void testMoreCallSequences() throws Exception { + addSnippetClassDecl("static int fun1(int a) { return a; }"); + addSnippetClassDecl("static int fun2(int a) { return fun1(a)+1; }"); + addSnippetClassDecl("static int fun3(int a) { return fun2(a) + 2; }"); + addSnippetClassDecl("static int fun4(int a) { return fun3(a) + 3; }"); + Result result = optimize("int", "return fun4(1);"); + assertEquals("static int fun2(int a){\n" + " return a + 1;\n}", + result.findMethod("fun2").toSource()); + assertEquals("static int fun3(int a){\n" + " return a + 1 + 2;\n}", + result.findMethod("fun3").toSource()); + assertEquals("static int fun4(int a){\n" + " return a + 1 + 2 + 3;\n}", + result.findMethod("fun4").toSource()); + } + + public void testDeadCodeElimination_notInlinable() throws Exception { + // fun1 cannot be inlined + addSnippetClassDecl("static boolean test1(int a)" + "{ return a>1; }"); + addSnippetClassDecl("static int fun1(int a)" + "{ if (test1(a)) { return a; }" + + "else {switch(a) { case 1: a++; break; default: a=a+2; break; }; return a; }" + "}"); + addSnippetClassDecl("static int fun2(int a)" + "{return fun1(a);}"); + Result result = optimize("int", "return fun2(0);"); + assertEquals("static int fun1(int a){\n" + " if (a > 1) {\n" + " return a;\n" + + " } else {\n" + " switch (a) {\n" + " case 1: \n" + " ++a;\n" + + " break;\n" + " default: \n" + " a = a + 2;\n" + " }\n" + + " return a;\n" + " }\n" + "}", result.findMethod("fun1").toSource()); + assertEquals("static int fun2(int a){\n" + " return EntryPoint.fun1(a);\n" + "}", + result.findMethod("fun2").toSource()); + } + + public void testDeadCodeElimination_delayedInline() throws Exception { + // same fun1() and fun2() as the previous test, but different test1(); + // fun1 can be inlined after inling test1 and DeadCodeElimination + addSnippetClassDecl("static boolean test1(int a)" + "{ return true; }"); + addSnippetClassDecl("static int fun1(int a)" + "{ if (test1(a)) { return a; }" + + "else {switch(a) { case 1: a++; break; default: a=a+2; break; }; return a; }" + "}"); + addSnippetClassDecl("static int fun2(int a)" + "{return fun1(a);}"); + Result result = optimize("int", "return fun2(0);"); + assertEquals("static int fun1(int a){\n" + " return a;\n}", + result.findMethod("fun1").toSource()); + assertEquals("static int fun2(int a){\n" + " return a;\n}", + result.findMethod("fun2").toSource()); + } + + public void testRecursion1() throws Exception { + // one recursive function, and one call to the function + addSnippetClassDecl("static int fun1(int a) { return a<=0 ? a : fun1(a-1)+a; }"); + addSnippetClassDecl("static int fun2(int b) { return b + fun1(b); }"); + Result result = optimize("int", "return fun2(5);"); + assertEquals( + "static int fun1(int a){\n" + " return a <= 0 ? a : EntryPoint.fun1(a - 1) + a;\n" + "}", + result.findMethod("fun1").toSource()); + // never inline a recursive function + assertEquals("static int fun2(int b){\n" + " return b + EntryPoint.fun1(b);\n" + "}", + result.findMethod("fun2").toSource()); + } + + public void testRecursion2() throws Exception { + // one call inside a recursive function + addSnippetClassDecl("static int fun1(int a) { return a + 1; }"); + addSnippetClassDecl("static int fun2(int b) { return b<=0 ? fun1(b) : fun2(b-1)+b; }"); + Result result = optimize("int", "return fun2(5);"); + // recursive function can inline other functions + assertEquals("static int fun2(int b){\n" + + " return b <= 0 ? b + 1 : EntryPoint.fun2(b - 1) + b;\n" + "}", + result.findMethod("fun2").toSource()); + } + + public void testRecursion3() throws Exception { + // nested recursive call + addSnippetClassDecl("static int fun1(int a) { return a<=0 ? a : fun2(a-1)+a; }"); + addSnippetClassDecl("static int fun2(int a) { return a<=0 ? a : fun1(a-1)+a; }"); + Result result = optimize("int", "return fun1(0);"); + assertEquals("static int fun1(int a){\n" + + " return a <= 0 ? a : (a - 1 <= 0 ? a - 1 : EntryPoint.fun1(a - 1 - 1) + a - 1) + a;\n" + + "}", result.findMethod("fun1").toSource()); + assertEquals( + "static int fun2(int a){\n" + " return a <= 0 ? a : EntryPoint.fun1(a - 1) + a;\n" + "}", + result.findMethod("fun2").toSource()); + } + + @Override + protected boolean optimizeMethod(JProgram program, JMethod method) { + program.addEntryMethod(findMainMethod(program)); + boolean didChange = false; + while (MethodInliner.exec(program).didChange()) { + didChange = true; + } + return didChange; + } +}