Revision: 10203
Author: sco...@google.com
Date: Mon May 23 09:42:46 2011
Log: Pruner runs only once.
I know this feels a little hacky, but I tracked down most of the sources of
Pruner jitter that's causing it to run more than once.
1) Instance fields needed to be treated like method and put into limbo
until their enclosing type is instantiable. This shouldn't be too
controversial.
2) A big source of jitter is the fact that CleanupRefsVisitor removes
non-side-effect causing arguments when the invoked parameter is pruned.
Essentially, I am doing the same conceptual thing for arguments to methods
as we are for methods and fields-- unless the argument expressions have
side effects, they are not considered rescued until the target parameter is
rescued.
http://gwt-code-reviews.appspot.com/1436802/
http://code.google.com/p/google-web-toolkit/source/detail?r=10203
Modified:
/trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ControlFlowAnalyzer.java
/trunk/dev/core/src/com/google/gwt/dev/jjs/impl/Pruner.java
/trunk/dev/core/test/com/google/gwt/dev/jjs/impl/PrunerTest.java
=======================================
---
/trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ControlFlowAnalyzer.java
Thu May 5 06:03:58 2011
+++
/trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ControlFlowAnalyzer.java
Mon May 23 09:42:46 2011
@@ -55,6 +55,7 @@
import com.google.gwt.dev.js.ast.JsName;
import com.google.gwt.dev.js.ast.JsNameRef;
import com.google.gwt.dev.js.ast.JsVisitor;
+import com.google.gwt.dev.util.collect.Lists;
import java.util.ArrayList;
import java.util.HashMap;
@@ -81,8 +82,8 @@
/**
* Marks as "referenced" any types, methods, and fields that are
reachable.
- * Also marks as "instantiable" any the classes and interfaces that can
- * possibly be instantiated.
+ * Also marks as "instantiable" any classes and interfaces that can
possibly
+ * be instantiated.
*
* TODO(later): make RescueVisitor use less stack?
*/
@@ -229,8 +230,7 @@
rescue(intfType, false, isInstantiated);
}
- rescueMethodsIfInstantiable(type);
-
+ rescueMembersIfInstantiable(type);
return false;
}
@@ -271,14 +271,23 @@
public boolean visit(JFieldRef ref, Context ctx) {
JField target = ref.getField();
- // JLS 12.4.1: references to static, non-final, or
- // non-compile-time-constant fields rescue the enclosing class.
- // JDT already folds in compile-time constants as literals, so we
must
- // rescue the enclosing types for any static fields that make it
here.
+ /*
+ * JLS 12.4.1: references to static, non-final, or
+ * non-compile-time-constant fields rescue the enclosing class. JDT
+ * already folds in compile-time constants as literals, so we must
rescue
+ * the enclosing types for any static fields that make it here.
+ */
if (target.isStatic()) {
rescue(target.getEnclosingType(), true, false);
}
- rescue(target);
+ if (target.isStatic() ||
instantiatedTypes.contains(target.getEnclosingType())) {
+ rescue(target);
+ } else {
+ // It's a field whose class is not instantiable
+ if (!liveFieldsAndMethods.contains(target)) {
+ membersToRescueIfTypeIsInstantiated.add(target);
+ }
+ }
return true;
}
@@ -306,7 +315,7 @@
accept(it);
}
- rescueMethodsIfInstantiable(type);
+ rescueMembersIfInstantiable(type);
return false;
}
@@ -363,11 +372,21 @@
} else {
// It's a virtual method whose class is not instantiable
if (!liveFieldsAndMethods.contains(method)) {
- methodsLiveExceptForInstantiability.add(method);
+ membersToRescueIfTypeIsInstantiated.add(method);
}
}
- return true;
+ if (argsToRescueIfParameterRead == null || method.canBePolymorphic()
+ || call instanceof JsniMethodRef) {
+ return true;
+ }
+
+ if (program.staticImplFor(method) != null) {
+ // CleanUpRefsVisitor does not prune these params, must rescue.
+ return true;
+ }
+
+ return rescueArgumentsIfParametersCanBeRead(call, method);
}
@Override
@@ -524,7 +543,7 @@
if (method != null) {
if (!liveFieldsAndMethods.contains(method)) {
liveFieldsAndMethods.add(method);
- methodsLiveExceptForInstantiability.remove(method);
+ membersToRescueIfTypeIsInstantiated.remove(method);
if (dependencyRecorder != null) {
curMethodStack.add(method);
dependencyRecorder.methodIsLiveBecause(method, curMethodStack);
@@ -589,6 +608,7 @@
private void rescue(JVariable var) {
if (var != null) {
if (liveFieldsAndMethods.add(var)) {
+ membersToRescueIfTypeIsInstantiated.remove(var);
if (isStaticFieldInitializedToLiteral(var)) {
/*
* Rescue literal initializers when the field is rescued, not
when
@@ -619,6 +639,13 @@
accept(field.getInitializer());
referencedTypes.add(field.getEnclosingType());
liveFieldsAndMethods.add(field.getEnclosingType().getMethods().get(0));
+ } else if (argsToRescueIfParameterRead != null && var instanceof
JParameter) {
+ List<JExpression> list =
argsToRescueIfParameterRead.remove(var);
+ if (list != null) {
+ for (JExpression arg : list) {
+ this.accept(arg);
+ }
+ }
}
}
}
@@ -627,6 +654,43 @@
private void rescueAndInstantiate(JClassType type) {
rescue(type, true, true);
}
+
+ /**
+ * The code is very tightly tied to the behavior of
+ * Pruner.CleanupRefsVisitor. CleanUpRefsVisitor will prune unread
+ * parameters, and also prune any matching arguments that don't have
side
+ * effects. We want to make control flow congruent to pruning, to
avoid the
+ * need to iterate over Pruner until reaching a stable point, so we
avoid
+ * actually rescuing such arguments until/unless the parameter is read.
+ */
+ private boolean rescueArgumentsIfParametersCanBeRead(JMethodCall call,
JMethod method) {
+ if (call.getInstance() != null) {
+ // Explicitly visit instance since we're returning false below.
+ this.accept(call.getInstance());
+ }
+ List<JExpression> args = call.getArgs();
+ List<JParameter> params = method.getParams();
+ int i = 0;
+ for (int c = params.size(); i < c; ++i) {
+ JExpression arg = args.get(i);
+ JParameter param = params.get(i);
+ if (arg.hasSideEffects() || liveFieldsAndMethods.contains(param)) {
+ this.accept(arg);
+ continue;
+ }
+ List<JExpression> list = argsToRescueIfParameterRead.get(param);
+ if (list == null) {
+ argsToRescueIfParameterRead.put(param, Lists.create(arg));
+ } else {
+ argsToRescueIfParameterRead.put(param, Lists.add(list, arg));
+ }
+ }
+ // Visit any "extra" arguments that exceed the param list.
+ for (int c = args.size(); i < c; ++i) {
+ this.accept(args.get(i));
+ }
+ return false;
+ }
/**
* Handle special rescues needed implicitly to support concat.
@@ -672,16 +736,24 @@
* If the type is instantiable, rescue any of its virtual methods that
a
* previously seen method call could call.
*/
- private void rescueMethodsIfInstantiable(JDeclaredType type) {
+ private void rescueMembersIfInstantiable(JDeclaredType type) {
if (instantiatedTypes.contains(type)) {
for (JMethod method : type.getMethods()) {
if (!method.isStatic()) {
- if (methodsLiveExceptForInstantiability.contains(method)) {
+ if (membersToRescueIfTypeIsInstantiated.contains(method)) {
rescue(method);
continue;
}
}
}
+ for (JField field : type.getFields()) {
+ if (!field.isStatic()) {
+ if (membersToRescueIfTypeIsInstantiated.contains(field)) {
+ rescue(field);
+ continue;
+ }
+ }
+ }
}
}
@@ -703,13 +775,21 @@
rescue(overrider);
} else {
// The enclosing class is not yet alive, put override in
limbo.
- methodsLiveExceptForInstantiability.add(overrider);
+ membersToRescueIfTypeIsInstantiated.add(overrider);
}
}
}
}
}
}
+
+ /**
+ * These are arguments that have not yet been rescued on account of the
+ * associated parameter not having been read yet. If the parameter
becomes
+ * read, we will need to rescue the associated arguments. See comments in
+ * {@link #rescueArgumentsIfParametersCanBeRead}.
+ */
+ private Map<JParameter, List<JExpression>> argsToRescueIfParameterRead;
private final JDeclaredType baseArrayType;
private DependencyRecorder dependencyRecorder;
@@ -720,12 +800,12 @@
private Set<String> liveStrings = new HashSet<String>();
/**
- * Schrodinger's methods... aka "limbo". :) These are instance methods
that
- * seem to be reachable, only their enclosing type is uninstantiable. We
place
- * these methods into purgatory until/unless the enclosing type is found
to be
- * instantiable.
+ * Schrodinger's members... aka "limbo". :) These are instance methods
and
+ * fields that seem to be reachable, only their enclosing type is
+ * uninstantiable. We place these methods into purgatory until/unless the
+ * enclosing type is found to be instantiable.
*/
- private Set<JMethod> methodsLiveExceptForInstantiability = new
HashSet<JMethod>();
+ private Set<JNode> membersToRescueIfTypeIsInstantiated = new
HashSet<JNode>();
/**
* A precomputed map of all instance methods onto a set of methods that
@@ -748,8 +828,12 @@
referencedTypes = new HashSet<JReferenceType>(cfa.referencedTypes);
stringValueOfChar = cfa.stringValueOfChar;
liveStrings = new HashSet<String>(cfa.liveStrings);
- methodsLiveExceptForInstantiability =
- new HashSet<JMethod>(cfa.methodsLiveExceptForInstantiability);
+ membersToRescueIfTypeIsInstantiated =
+ new HashSet<JNode>(cfa.membersToRescueIfTypeIsInstantiated);
+ if (cfa.argsToRescueIfParameterRead != null) {
+ argsToRescueIfParameterRead =
+ new HashMap<JParameter,
List<JExpression>>(cfa.argsToRescueIfParameterRead);
+ }
methodsThatOverrideMe = cfa.methodsThatOverrideMe;
}
@@ -802,6 +886,11 @@
}
this.dependencyRecorder = dr;
}
+
+ public void setForPruning() {
+ assert argsToRescueIfParameterRead == null;
+ argsToRescueIfParameterRead = new HashMap<JParameter,
List<JExpression>>();
+ }
/**
* Traverse all code executed by <code>expr</code>.
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/Pruner.java Tue May 10
05:59:20 2011
+++ /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/Pruner.java Mon May 23
09:42:46 2011
@@ -344,12 +344,9 @@
@Override
public boolean visit(JClassType type, Context ctx) {
assert (referencedTypes.contains(type));
- boolean isInstantiated = program.typeOracle.isInstantiatedType(type);
-
for (int i = 0; i < type.getFields().size(); ++i) {
JField field = type.getFields().get(i);
- if (!referencedNonTypes.contains(field)
- || pruneViaNoninstantiability(isInstantiated, field)) {
+ if (!referencedNonTypes.contains(field)) {
type.removeField(i);
madeChanges();
--i;
@@ -358,8 +355,7 @@
for (int i = 0; i < type.getMethods().size(); ++i) {
JMethod method = type.getMethods().get(i);
- if (!referencedNonTypes.contains(method)
- || pruneViaNoninstantiability(isInstantiated, method)) {
+ if (!referencedNonTypes.contains(method)) {
// Never prune clinit directly out of the class.
if (i > 0) {
type.removeMethod(i);
@@ -423,15 +419,14 @@
* We cannot prune parameters from staticImpls that still have a
live
* instance method, because doing so would screw up any subsequent
* devirtualizations. If the instance method has been pruned, then
it's
- * okay. Also, it's okay on the final pass since no more
- * devirtualizations will occur.
+ * okay. Also, it's okay on the final pass (saveCodeTypes == false)
+ * since no more devirtualizations will occur.
*
* TODO: prune params; MakeCallsStatic smarter to account for it.
*/
JMethod staticImplFor = program.staticImplFor(x);
// Unless the instance method has already been pruned, of course.
- if (saveCodeGenTypes && staticImplFor != null
- &&
staticImplFor.getEnclosingType().getMethods().contains(staticImplFor)) {
+ if (saveCodeGenTypes && staticImplFor != null &&
referencedNonTypes.contains(staticImplFor)) {
// instance method is still live
return true;
}
@@ -485,10 +480,6 @@
}
return false;
}
-
- private boolean pruneViaNoninstantiability(boolean isInstantiated,
CanBeStatic it) {
- return (!isInstantiated && !it.isStatic());
- }
}
private static final String NAME = Pruner.class.getSimpleName();
@@ -576,7 +567,11 @@
new JMethodCall(x.getSourceInfo(), instance,
program.getNullMethod(),
primitiveTypeOrNullType(program, x.getType()));
// Retain the original arguments, they will be evaluated for side
effects.
- newCall.addArgs(args);
+ for (JExpression arg : args) {
+ if (arg.hasSideEffects()) {
+ newCall.addArg(arg);
+ }
+ }
return newCall;
}
@@ -591,6 +586,7 @@
}
private final JProgram program;
+
private final boolean saveCodeGenTypes;
private Pruner(JProgram program, boolean saveCodeGenTypes) {
@@ -601,38 +597,35 @@
private OptimizerStats execImpl() {
OptimizerStats stats = new OptimizerStats(NAME);
- // TODO(zundel): see if this loop can be removed and all work done in
one
- // pass of the optimizer to improve performance.
- while (true) {
- ControlFlowAnalyzer livenessAnalyzer = new
ControlFlowAnalyzer(program);
- if (saveCodeGenTypes) {
- /*
- * SPECIAL: Some classes contain methods used by code generation
later.
- * Unless those transforms have already been performed, we must
rescue
- * all contained methods for later user.
- */
- traverseFromCodeGenTypes(livenessAnalyzer);
- }
- for (JMethod method : program.getAllEntryMethods()) {
- livenessAnalyzer.traverseFrom(method);
- }
- livenessAnalyzer.traverseFromLeftoversFragmentHasLoaded();
-
-
program.typeOracle.setInstantiatedTypes(livenessAnalyzer.getInstantiatedTypes());
-
- PruneVisitor pruner =
- new PruneVisitor(livenessAnalyzer.getReferencedTypes(),
livenessAnalyzer
- .getLiveFieldsAndMethods());
- pruner.accept(program);
- stats.recordModified(pruner.getNumMods());
- if (!pruner.didChange()) {
- break;
- }
- CleanupRefsVisitor cleaner =
- new
CleanupRefsVisitor(livenessAnalyzer.getLiveFieldsAndMethods(), pruner
- .getMethodToOriginalParamsMap());
- cleaner.accept(program.getDeclaredTypes());
- }
+ ControlFlowAnalyzer livenessAnalyzer = new
ControlFlowAnalyzer(program);
+ livenessAnalyzer.setForPruning();
+ if (saveCodeGenTypes) {
+ /*
+ * SPECIAL: Some classes contain methods used by code generation
later.
+ * Unless those transforms have already been performed, we must
rescue all
+ * contained methods for later user.
+ */
+ traverseFromCodeGenTypes(livenessAnalyzer);
+ }
+ for (JMethod method : program.getAllEntryMethods()) {
+ livenessAnalyzer.traverseFrom(method);
+ }
+ livenessAnalyzer.traverseFromLeftoversFragmentHasLoaded();
+
+
program.typeOracle.setInstantiatedTypes(livenessAnalyzer.getInstantiatedTypes());
+
+ PruneVisitor pruner =
+ new PruneVisitor(livenessAnalyzer.getReferencedTypes(),
livenessAnalyzer
+ .getLiveFieldsAndMethods());
+ pruner.accept(program);
+ stats.recordModified(pruner.getNumMods());
+ if (!pruner.didChange()) {
+ return stats;
+ }
+ CleanupRefsVisitor cleaner =
+ new CleanupRefsVisitor(livenessAnalyzer.getLiveFieldsAndMethods(),
pruner
+ .getMethodToOriginalParamsMap());
+ cleaner.accept(program.getDeclaredTypes());
return stats;
}
=======================================
--- /trunk/dev/core/test/com/google/gwt/dev/jjs/impl/PrunerTest.java Fri
Mar 11 09:50:44 2011
+++ /trunk/dev/core/test/com/google/gwt/dev/jjs/impl/PrunerTest.java Mon
May 23 09:42:46 2011
@@ -139,10 +139,15 @@
"}",
result.findClass("EntryPoint$UsedInterface").toSource());
}
-
+
@Override
protected boolean optimizeMethod(JProgram program, JMethod method) {
program.addEntryMethod(findMainMethod(program));
- return Pruner.exec(program, true).didChange();
+ boolean didChange = false;
+ // TODO(jbrosenberg): remove loop when Pruner/CFA interaction is
perfect.
+ while (Pruner.exec(program, true).didChange()) {
+ didChange = true;
+ }
+ return didChange;
}
}
--
http://groups.google.com/group/Google-Web-Toolkit-Contributors
