| /* |
| * Copyright 2008 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.core.ext.TreeLogger; |
| import com.google.gwt.core.ext.UnableToCompleteException; |
| import com.google.gwt.dev.cfg.ConfigurationProperty; |
| import com.google.gwt.dev.cfg.Properties; |
| import com.google.gwt.dev.cfg.Property; |
| import com.google.gwt.dev.jjs.InternalCompilerException; |
| import com.google.gwt.dev.jjs.ast.Context; |
| import com.google.gwt.dev.jjs.ast.JArrayType; |
| import com.google.gwt.dev.jjs.ast.JClassLiteral; |
| import com.google.gwt.dev.jjs.ast.JDeclaredType; |
| import com.google.gwt.dev.jjs.ast.JExpression; |
| import com.google.gwt.dev.jjs.ast.JField; |
| import com.google.gwt.dev.jjs.ast.JIntLiteral; |
| import com.google.gwt.dev.jjs.ast.JMethod; |
| import com.google.gwt.dev.jjs.ast.JMethodCall; |
| import com.google.gwt.dev.jjs.ast.JNewArray; |
| import com.google.gwt.dev.jjs.ast.JNode; |
| import com.google.gwt.dev.jjs.ast.JPrimitiveType; |
| import com.google.gwt.dev.jjs.ast.JProgram; |
| import com.google.gwt.dev.jjs.ast.JReferenceType; |
| import com.google.gwt.dev.jjs.ast.JRunAsync; |
| import com.google.gwt.dev.jjs.ast.JStringLiteral; |
| import com.google.gwt.dev.jjs.ast.JVisitor; |
| import com.google.gwt.dev.jjs.impl.ControlFlowAnalyzer.DependencyRecorder; |
| import com.google.gwt.dev.jjs.impl.FragmentExtractor.CfaLivenessPredicate; |
| import com.google.gwt.dev.jjs.impl.FragmentExtractor.LivenessPredicate; |
| import com.google.gwt.dev.jjs.impl.FragmentExtractor.NothingAlivePredicate; |
| import com.google.gwt.dev.jjs.impl.FragmentExtractor.StatementLogger; |
| import com.google.gwt.dev.js.ast.JsBlock; |
| import com.google.gwt.dev.js.ast.JsExprStmt; |
| import com.google.gwt.dev.js.ast.JsExpression; |
| import com.google.gwt.dev.js.ast.JsFunction; |
| import com.google.gwt.dev.js.ast.JsProgram; |
| import com.google.gwt.dev.js.ast.JsStatement; |
| import com.google.gwt.dev.js.ast.JsVars; |
| import com.google.gwt.dev.js.ast.JsVars.JsVar; |
| import com.google.gwt.dev.util.JsniRef; |
| import com.google.gwt.dev.util.collect.HashMap; |
| import com.google.gwt.dev.util.collect.HashSet; |
| import com.google.gwt.dev.util.collect.Lists; |
| import com.google.gwt.dev.util.log.speedtracer.CompilerEventType; |
| import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger; |
| import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event; |
| |
| import java.util.ArrayList; |
| import java.util.LinkedHashSet; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Queue; |
| import java.util.Set; |
| import java.util.concurrent.ArrayBlockingQueue; |
| |
| /** |
| * <p> |
| * Divides the code in a {@link JsProgram} into multiple fragments. The initial |
| * fragment is sufficient to run all of the program's functionality except for |
| * anything called in a callback supplied to |
| * {@link com.google.gwt.core.client.GWT#runAsync(com.google.gwt.core.client.RunAsyncCallback) |
| * GWT.runAsync()}. The remaining code should be downloadable via |
| * {@link com.google.gwt.core.client.impl.AsyncFragmentLoader#inject(int)}. |
| * </p> |
| * |
| * <p> |
| * The precise way the program is fragmented is an implementation detail that is |
| * subject to change. Whenever the fragment strategy changes, |
| * <code>AsyncFragmentLoader</code> must be updated in tandem. That said, the |
| * current fragmentation strategy is to create an initial fragment, a leftovers |
| * fragment, and one fragment per split point. Additionally, the splitter |
| * computes an initial load sequence. All runAsync calls in the initial load |
| * sequence are reached before any call not in the sequence. Further, any call |
| * in the sequence is reached before any call later in the sequence. |
| * </p> |
| * |
| * <p> |
| * The fragment for a split point contains different things depending on whether |
| * it is in the initial load sequence or not. If it's in the initial load |
| * sequence, then the fragment includes the code newly live once that split |
| * point is crossed, that wasn't already live for the set of split points |
| * earlier in the sequence. For a split point not in the initial load sequence, |
| * the fragment contains only code exclusive to that split point, that is, code |
| * that cannot be reached except via that split point. All other code goes into |
| * the leftovers fragment. |
| * </p> |
| */ |
| public class CodeSplitter { |
| /** |
| * A dependency recorder that can record multiple dependency graphs. It has |
| * methods for starting and finishing new dependency graphs. |
| */ |
| public interface MultipleDependencyGraphRecorder extends DependencyRecorder { |
| /** |
| * Stop recording dependencies. |
| */ |
| void close(); |
| |
| /** |
| * Stop recording the current dependency graph. |
| */ |
| void endDependencyGraph(); |
| |
| void open(); |
| |
| /** |
| * Start a new dependency graph. It can be an extension of a previously |
| * recorded dependency graph, in which case the dependencies in the previous |
| * graph will not be repeated. |
| */ |
| void startDependencyGraph(String name, String extnds); |
| } |
| |
| /** |
| * A statement logger that immediately prints out everything live that it |
| * sees. |
| */ |
| private class EchoStatementLogger implements StatementLogger { |
| public void logStatement(JsStatement stat, boolean isIncluded) { |
| if (isIncluded) { |
| if (stat instanceof JsExprStmt) { |
| JsExpression expr = ((JsExprStmt) stat).getExpression(); |
| if (expr instanceof JsFunction) { |
| JsFunction func = (JsFunction) expr; |
| if (func.getName() != null) { |
| JMethod method = map.nameToMethod(func.getName()); |
| if (method != null) { |
| System.out.println(fullNameString(method)); |
| } |
| } |
| } |
| } |
| |
| if (stat instanceof JsVars) { |
| JsVars vars = (JsVars) stat; |
| for (JsVar var : vars) { |
| JField field = map.nameToField(var.getName()); |
| if (field != null) { |
| System.out.println(fullNameString(field)); |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * A map from program atoms to the split point, if any, that they are |
| * exclusive to. Atoms not exclusive to any split point are either mapped to 0 |
| * or left out of the map entirely. Note that the map is incomplete; any entry |
| * not included has not been proven to be exclusive. Also, note that the |
| * initial load sequence is assumed to already be loaded. |
| */ |
| private static class ExclusivityMap { |
| public Map<JField, Integer> fields = new HashMap<JField, Integer>(); |
| public Map<JMethod, Integer> methods = new HashMap<JMethod, Integer>(); |
| public Map<String, Integer> strings = new HashMap<String, Integer>(); |
| public Map<JDeclaredType, Integer> types = new HashMap<JDeclaredType, Integer>(); |
| } |
| |
| /** |
| * A liveness predicate that is based on an exclusivity map. |
| */ |
| private static class ExclusivityMapLivenessPredicate implements LivenessPredicate { |
| private final int fragment; |
| private final ExclusivityMap fragmentMap; |
| |
| public ExclusivityMapLivenessPredicate(ExclusivityMap fragmentMap, int fragment) { |
| this.fragmentMap = fragmentMap; |
| this.fragment = fragment; |
| } |
| |
| public boolean isLive(JDeclaredType type) { |
| return checkMap(fragmentMap.types, type); |
| } |
| |
| public boolean isLive(JField field) { |
| return checkMap(fragmentMap.fields, field); |
| } |
| |
| public boolean isLive(JMethod method) { |
| return checkMap(fragmentMap.methods, method); |
| } |
| |
| public boolean isLive(String literal) { |
| return checkMap(fragmentMap.strings, literal); |
| } |
| |
| public boolean miscellaneousStatementsAreLive() { |
| return true; |
| } |
| |
| private <T> boolean checkMap(Map<T, Integer> map, T x) { |
| Integer entryForX = map.get(x); |
| if (entryForX == null) { |
| // unrecognized items are always live |
| return true; |
| } else { |
| return (fragment == entryForX) || (entryForX == 0); |
| } |
| } |
| } |
| |
| /** |
| * A {@link MultipleDependencyGraphRecorder} that does nothing. |
| */ |
| public static final MultipleDependencyGraphRecorder NULL_RECORDER = |
| new MultipleDependencyGraphRecorder() { |
| public void close() { |
| } |
| |
| public void endDependencyGraph() { |
| } |
| |
| public void methodIsLiveBecause(JMethod liveMethod, ArrayList<JMethod> dependencyChain) { |
| } |
| |
| public void open() { |
| } |
| |
| public void startDependencyGraph(String name, String extnds) { |
| } |
| }; |
| |
| private static final String PROP_INITIAL_SEQUENCE = "compiler.splitpoint.initial.sequence"; |
| |
| /** |
| * A Java property that causes the fragment map to be logged. |
| */ |
| private static String PROP_LOG_FRAGMENT_MAP = "gwt.jjs.logFragmentMap"; |
| |
| public static ControlFlowAnalyzer computeInitiallyLive(JProgram jprogram) { |
| return computeInitiallyLive(jprogram, NULL_RECORDER); |
| } |
| |
| public static void exec(TreeLogger logger, JProgram jprogram, JsProgram jsprogram, |
| JavaToJavaScriptMap map, MultipleDependencyGraphRecorder dependencyRecorder) { |
| if (jprogram.getRunAsyncs().size() == 0) { |
| // Don't do anything if there is no call to runAsync |
| return; |
| } |
| Event codeSplitterEvent = SpeedTracerLogger.start(CompilerEventType.CODE_SPLITTER); |
| dependencyRecorder.open(); |
| new CodeSplitter(logger, jprogram, jsprogram, map, dependencyRecorder).execImpl(); |
| dependencyRecorder.close(); |
| codeSplitterEvent.end(); |
| } |
| |
| /** |
| * Find a split point as designated in the {@link #PROP_INITIAL_SEQUENCE} |
| * configuration property. |
| */ |
| public static int findSplitPoint(String refString, JProgram program, TreeLogger branch) |
| throws UnableToCompleteException { |
| Event codeSplitterEvent = |
| SpeedTracerLogger.start(CompilerEventType.CODE_SPLITTER, "phase", "findSplitPoint"); |
| Map<String, List<Integer>> nameToSplitPoint = reverseByName(program.getRunAsyncs()); |
| |
| if (refString.startsWith("@")) { |
| JsniRef jsniRef = JsniRef.parse(refString); |
| if (jsniRef == null) { |
| branch.log(TreeLogger.ERROR, "Badly formatted JSNI reference in " + PROP_INITIAL_SEQUENCE |
| + ": " + refString); |
| throw new UnableToCompleteException(); |
| } |
| final String lookupErrorHolder[] = new String[1]; |
| JNode referent = |
| JsniRefLookup.findJsniRefTarget(jsniRef, program, new JsniRefLookup.ErrorReporter() { |
| public void reportError(String error) { |
| lookupErrorHolder[0] = error; |
| } |
| }); |
| if (referent == null) { |
| TreeLogger resolveLogger = |
| branch.branch(TreeLogger.ERROR, "Could not resolve JSNI reference: " + jsniRef); |
| resolveLogger.log(TreeLogger.ERROR, lookupErrorHolder[0]); |
| throw new UnableToCompleteException(); |
| } |
| |
| if (!(referent instanceof JMethod)) { |
| branch.log(TreeLogger.ERROR, "Not a method: " + referent); |
| throw new UnableToCompleteException(); |
| } |
| |
| JMethod method = (JMethod) referent; |
| String canonicalName = ReplaceRunAsyncs.getImplicitName(method); |
| List<Integer> splitPoints = nameToSplitPoint.get(canonicalName); |
| if (splitPoints == null) { |
| branch.log(TreeLogger.ERROR, "Method does not enclose a runAsync call: " + jsniRef); |
| throw new UnableToCompleteException(); |
| } |
| if (splitPoints.size() > 1) { |
| branch.log(TreeLogger.ERROR, "Method includes multiple runAsync calls, " |
| + "so it's ambiguous which one is meant: " + jsniRef); |
| throw new UnableToCompleteException(); |
| } |
| |
| return splitPoints.get(0); |
| } |
| |
| // Assume it's a raw class name |
| List<Integer> splitPoints = nameToSplitPoint.get(refString); |
| if (splitPoints == null || splitPoints.size() == 0) { |
| branch.log(TreeLogger.ERROR, "No runAsync call is labelled with class " + refString); |
| throw new UnableToCompleteException(); |
| } |
| if (splitPoints.size() > 1) { |
| branch.log(TreeLogger.ERROR, "More than one runAsync call is labelled with class " |
| + refString); |
| throw new UnableToCompleteException(); |
| } |
| int result = splitPoints.get(0); |
| codeSplitterEvent.end(); |
| return result; |
| } |
| |
| public static int getExclusiveFragmentNumber(int splitPoint) { |
| return splitPoint; |
| } |
| |
| public static int getLeftoversFragmentNumber(int numSplitPoints) { |
| return numSplitPoints + 1; |
| } |
| |
| /** |
| * Infer the number of split points for a given number of code fragments. |
| */ |
| public static int numSplitPointsForFragments(int codeFragments) { |
| assert (codeFragments != 2); |
| |
| if (codeFragments == 1) { |
| return 0; |
| } |
| |
| return codeFragments - 2; |
| } |
| |
| /** |
| * Choose an initial load sequence of split points for the specified program. |
| * Do so by identifying split points whose code always load first, before any |
| * other split points. As a side effect, modifies |
| * {@link com.google.gwt.core.client.impl.AsyncFragmentLoader#initialLoadSequence} |
| * in the program being compiled. |
| * |
| * @throws UnableToCompleteException If the module specifies a bad load order |
| */ |
| public static void pickInitialLoadSequence(TreeLogger logger, JProgram program, |
| Properties properties) throws UnableToCompleteException { |
| Event codeSplitterEvent = |
| SpeedTracerLogger |
| .start(CompilerEventType.CODE_SPLITTER, "phase", "pickInitialLoadSequence"); |
| TreeLogger branch = |
| logger.branch(TreeLogger.TRACE, "Looking up initial load sequence for split points"); |
| LinkedHashSet<Integer> initialLoadSequence = new LinkedHashSet<Integer>(); |
| |
| ConfigurationProperty prop; |
| { |
| Property p = properties.find(PROP_INITIAL_SEQUENCE); |
| if (p == null) { |
| throw new InternalCompilerException("Could not find configuration property " |
| + PROP_INITIAL_SEQUENCE); |
| } |
| if (!(p instanceof ConfigurationProperty)) { |
| throw new InternalCompilerException(PROP_INITIAL_SEQUENCE |
| + " is not a configuration property"); |
| } |
| prop = (ConfigurationProperty) p; |
| } |
| |
| for (String refString : prop.getValues()) { |
| int splitPoint = findSplitPoint(refString, program, branch); |
| if (initialLoadSequence.contains(splitPoint)) { |
| branch.log(TreeLogger.ERROR, "Split point specified more than once: " + refString); |
| } |
| initialLoadSequence.add(splitPoint); |
| } |
| |
| logInitialLoadSequence(logger, initialLoadSequence); |
| installInitialLoadSequenceField(program, initialLoadSequence); |
| program.setSplitPointInitialSequence(new ArrayList<Integer>(initialLoadSequence)); |
| codeSplitterEvent.end(); |
| } |
| |
| /** |
| * <p> |
| * Computes the "maximum total script size" for one permutation. The total |
| * script size for one sequence of split points reached is the sum of the |
| * scripts that are downloaded for that sequence. The maximum total script |
| * size is the maximum such size for all possible sequences of split points. |
| * </p> |
| * |
| * @param jsLengths The lengths of the fragments for the compilation of one |
| * permutation |
| */ |
| public static int totalScriptSize(int[] jsLengths) { |
| /* |
| * The total script size is currently simple: it's the sum of all the |
| * individual script files. |
| */ |
| |
| int maxTotalSize; |
| int numSplitPoints = numSplitPointsForFragments(jsLengths.length); |
| if (numSplitPoints == 0) { |
| maxTotalSize = jsLengths[0]; |
| } else { |
| // Add up the initial and exclusive fragments |
| maxTotalSize = jsLengths[0]; |
| for (int sp = 1; sp <= numSplitPoints; sp++) { |
| int excl = getExclusiveFragmentNumber(sp); |
| maxTotalSize += jsLengths[excl]; |
| } |
| |
| // Add the leftovers |
| maxTotalSize += jsLengths[getLeftoversFragmentNumber(numSplitPoints)]; |
| } |
| return maxTotalSize; |
| } |
| |
| private static Map<JField, JClassLiteral> buildFieldToClassLiteralMap(JProgram jprogram) { |
| final Map<JField, JClassLiteral> map = new HashMap<JField, JClassLiteral>(); |
| class BuildFieldToLiteralVisitor extends JVisitor { |
| @Override |
| public void endVisit(JClassLiteral lit, Context ctx) { |
| map.put(lit.getField(), lit); |
| } |
| } |
| (new BuildFieldToLiteralVisitor()).accept(jprogram); |
| return map; |
| } |
| |
| /** |
| * Compute the set of initially live code for this program. Such code must be |
| * included in the initial download of the program. |
| */ |
| private static ControlFlowAnalyzer computeInitiallyLive(JProgram jprogram, |
| MultipleDependencyGraphRecorder dependencyRecorder) { |
| dependencyRecorder.startDependencyGraph("initial", null); |
| |
| ControlFlowAnalyzer cfa = new ControlFlowAnalyzer(jprogram); |
| cfa.setDependencyRecorder(dependencyRecorder); |
| cfa.traverseEntryMethods(); |
| traverseClassArray(jprogram, cfa); |
| |
| dependencyRecorder.endDependencyGraph(); |
| return cfa; |
| } |
| |
| /** |
| * Extract the types from a set that happen to be declared types. |
| */ |
| private static Set<JDeclaredType> declaredTypesIn(Set<JReferenceType> types) { |
| Set<JDeclaredType> result = new HashSet<JDeclaredType>(); |
| for (JReferenceType type : types) { |
| if (type instanceof JDeclaredType) { |
| result.add((JDeclaredType) type); |
| } |
| } |
| return result; |
| } |
| |
| private static String fullNameString(JField field) { |
| return field.getEnclosingType().getName() + "." + field.getName(); |
| } |
| |
| private static String fullNameString(JMethod method) { |
| return method.getEnclosingType().getName() + "." + JProgram.getJsniSig(method); |
| } |
| |
| private static <T> int getOrZero(Map<T, Integer> map, T key) { |
| Integer value = map.get(key); |
| return (value == null) ? 0 : value; |
| } |
| |
| /** |
| * Installs the initial load sequence into AsyncFragmentLoader.BROWSER_LOADER. |
| * The initializer looks like this: |
| * |
| * <pre> |
| * AsyncFragmentLoader BROWSER_LOADER = makeBrowserLoader(1, new int[]{}); |
| * </pre> |
| * |
| * The second argument (<code>new int[]</code>) gets replaced by an array |
| * corresponding to <code>initialLoadSequence</code>. |
| */ |
| private static void installInitialLoadSequenceField(JProgram program, |
| LinkedHashSet<Integer> initialLoadSequence) { |
| // Arg 1 is initialized in the source as "new int[]{}". |
| JMethodCall call = ReplaceRunAsyncs.getBrowserLoaderConstructor(program); |
| JExpression arg1 = call.getArgs().get(1); |
| assert arg1 instanceof JNewArray; |
| JArrayType arrayType = program.getTypeArray(JPrimitiveType.INT); |
| assert ((JNewArray) arg1).getArrayType() == arrayType; |
| List<JExpression> initializers = new ArrayList<JExpression>(initialLoadSequence.size()); |
| for (int sp : initialLoadSequence) { |
| initializers.add(JIntLiteral.get(sp)); |
| } |
| JNewArray newArray = |
| JNewArray.createInitializers(arg1.getSourceInfo(), arrayType, Lists |
| .normalizeUnmodifiable(initializers)); |
| call.setArg(1, newArray); |
| } |
| |
| private static <T> T last(T[] array) { |
| return array[array.length - 1]; |
| } |
| |
| private static void logInitialLoadSequence(TreeLogger logger, |
| LinkedHashSet<Integer> initialLoadSequence) { |
| if (!logger.isLoggable(TreeLogger.TRACE)) { |
| return; |
| } |
| |
| StringBuffer message = new StringBuffer(); |
| message.append("Initial load sequence of split points: "); |
| if (initialLoadSequence.isEmpty()) { |
| message.append("(none)"); |
| } else { |
| boolean first = true; |
| for (int sp : initialLoadSequence) { |
| if (first) { |
| first = false; |
| } else { |
| message.append(", "); |
| } |
| message.append(sp); |
| } |
| } |
| |
| logger.log(TreeLogger.TRACE, message.toString()); |
| } |
| |
| private static Map<String, List<Integer>> reverseByName(List<JRunAsync> runAsyncs) { |
| Map<String, List<Integer>> revmap = new HashMap<String, List<Integer>>(); |
| for (JRunAsync replacement : runAsyncs) { |
| String name = replacement.getName(); |
| if (name != null) { |
| List<Integer> list = revmap.get(name); |
| if (list == null) { |
| list = new ArrayList<Integer>(); |
| revmap.put(name, list); |
| } |
| list.add(replacement.getSplitPoint()); |
| } |
| } |
| return revmap; |
| } |
| |
| /** |
| * Any instance method in the magic Array class must be in the initial |
| * download. The methods of that class are copied to a separate object the |
| * first time class Array is touched, and any methods added later won't be |
| * part of the copy. |
| */ |
| private static void traverseClassArray(JProgram jprogram, ControlFlowAnalyzer cfa) { |
| JDeclaredType typeArray = jprogram.getFromTypeMap("com.google.gwt.lang.Array"); |
| if (typeArray == null) { |
| // It was pruned; nothing to do |
| return; |
| } |
| |
| cfa.traverseFromInstantiationOf(typeArray); |
| for (JMethod method : typeArray.getMethods()) { |
| if (method.needsVtable()) { |
| cfa.traverseFrom(method); |
| } |
| } |
| } |
| |
| private static <T> Set<T> union(Set<? extends T> set1, Set<? extends T> set2) { |
| Set<T> union = new HashSet<T>(); |
| union.addAll(set1); |
| union.addAll(set2); |
| return union; |
| } |
| |
| private static <T> void updateMap(int entry, Map<T, Integer> map, Set<?> liveWithoutEntry, |
| Iterable<T> all) { |
| for (T each : all) { |
| if (!liveWithoutEntry.contains(each)) { |
| /* |
| * Note that it is fine to overwrite a preexisting entry in the map. If |
| * an atom is dead until split point i has been reached, and is also |
| * dead until entry j has been reached, then it is dead until both have |
| * been reached. Thus, it can be downloaded along with either i's or j's |
| * code. |
| */ |
| map.put(each, entry); |
| } |
| } |
| } |
| |
| private final MultipleDependencyGraphRecorder dependencyRecorder; |
| private final Map<JField, JClassLiteral> fieldToLiteralOfClass; |
| private final FragmentExtractor fragmentExtractor; |
| private final LinkedHashSet<Integer> initialLoadSequence; |
| |
| /** |
| * Code that is initially live when the program first downloads. |
| */ |
| private final ControlFlowAnalyzer initiallyLive; |
| private final JProgram jprogram; |
| private final JsProgram jsprogram; |
| |
| /** |
| * Computed during {@link #execImpl()}, so that intermediate steps of it can |
| * be used as they are created. |
| */ |
| private ControlFlowAnalyzer liveAfterInitialSequence; |
| private final TreeLogger logger; |
| private final boolean logging; |
| private final JavaToJavaScriptMap map; |
| private final Set<JMethod> methodsInJavaScript; |
| private final int numEntries; |
| |
| private CodeSplitter(TreeLogger logger, JProgram jprogram, JsProgram jsprogram, |
| JavaToJavaScriptMap map, MultipleDependencyGraphRecorder dependencyRecorder) { |
| this.logger = logger.branch(TreeLogger.TRACE, "Splitting JavaScript for incremental download"); |
| this.jprogram = jprogram; |
| this.jsprogram = jsprogram; |
| this.map = map; |
| this.dependencyRecorder = dependencyRecorder; |
| this.initialLoadSequence = new LinkedHashSet<Integer>(jprogram.getSplitPointInitialSequence()); |
| |
| numEntries = jprogram.getRunAsyncs().size() + 1; |
| logging = Boolean.getBoolean(PROP_LOG_FRAGMENT_MAP); |
| fieldToLiteralOfClass = buildFieldToClassLiteralMap(jprogram); |
| fragmentExtractor = new FragmentExtractor(jprogram, jsprogram, map); |
| |
| initiallyLive = computeInitiallyLive(jprogram, dependencyRecorder); |
| |
| methodsInJavaScript = fragmentExtractor.findAllMethodsInJavaScript(); |
| } |
| |
| /** |
| * Create a new fragment and add it to the table of fragments. |
| * |
| * @param splitPoint The split point to associate this code with |
| * @param alreadyLoaded The code that should be assumed to have already been |
| * loaded |
| * @param liveNow The code that is assumed live once this fragment loads; |
| * anything in here but not in <code>alreadyLoaded</code> will be |
| * included in the created fragment |
| * @param stmtsToAppend Additional statements to append to the end of the new |
| * fragment |
| * @param fragmentStats The list of fragments to append to |
| */ |
| private void addFragment(int splitPoint, LivenessPredicate alreadyLoaded, |
| LivenessPredicate liveNow, List<JsStatement> stmtsToAppend, |
| Map<Integer, List<JsStatement>> fragmentStats) { |
| if (logging) { |
| System.out.println(); |
| System.out.println("==== Fragment " + fragmentStats.size() + " ===="); |
| fragmentExtractor.setStatementLogger(new EchoStatementLogger()); |
| } |
| List<JsStatement> stats = fragmentExtractor.extractStatements(liveNow, alreadyLoaded); |
| stats.addAll(stmtsToAppend); |
| fragmentStats.put(splitPoint, stats); |
| } |
| |
| /** |
| * For each split point other than those in the initial load sequence, compute |
| * a CFA that traces every other split point. For those that are in the |
| * initial load sequence, add a <code>null</code> to the list. |
| */ |
| private List<ControlFlowAnalyzer> computeAllButOneCfas() { |
| String dependencyGraphNameAfterInitialSequence = dependencyGraphNameAfterInitialSequence(); |
| |
| List<ControlFlowAnalyzer> allButOnes = new ArrayList<ControlFlowAnalyzer>(); |
| for (JRunAsync runAsync : jprogram.getRunAsyncs()) { |
| int splitPoint = runAsync.getSplitPoint(); |
| if (isInitial(splitPoint)) { |
| allButOnes.add(null); |
| continue; |
| } |
| dependencyRecorder.startDependencyGraph("sp" + splitPoint, |
| dependencyGraphNameAfterInitialSequence); |
| ControlFlowAnalyzer cfa = new ControlFlowAnalyzer(liveAfterInitialSequence); |
| cfa.setDependencyRecorder(dependencyRecorder); |
| for (JRunAsync otherRunAsync : jprogram.getRunAsyncs()) { |
| if (isInitial(otherRunAsync.getSplitPoint())) { |
| continue; |
| } |
| if (otherRunAsync == runAsync) { |
| continue; |
| } |
| cfa.traverseFromRunAsync(otherRunAsync); |
| } |
| dependencyRecorder.endDependencyGraph(); |
| allButOnes.add(cfa); |
| } |
| |
| return allButOnes; |
| } |
| |
| /** |
| * Compute a CFA that covers the entire live code of the program. |
| */ |
| private ControlFlowAnalyzer computeCompleteCfa() { |
| dependencyRecorder.startDependencyGraph("total", null); |
| ControlFlowAnalyzer everything = new ControlFlowAnalyzer(jprogram); |
| everything.setDependencyRecorder(dependencyRecorder); |
| everything.traverseEverything(); |
| dependencyRecorder.endDependencyGraph(); |
| return everything; |
| } |
| |
| /** |
| * The name of the dependency graph that corresponds to |
| * {@link #liveAfterInitialSequence}. |
| */ |
| private String dependencyGraphNameAfterInitialSequence() { |
| if (initialLoadSequence.isEmpty()) { |
| return "initial"; |
| } else { |
| return "sp" + last(initialLoadSequence.toArray()); |
| } |
| } |
| |
| /** |
| * Map each program atom as exclusive to some split point, whenever possible. |
| * Also fixes up load order problems that could result from splitting code |
| * based on this assumption. |
| */ |
| private ExclusivityMap determineExclusivity() { |
| ExclusivityMap fragmentMap = new ExclusivityMap(); |
| |
| mapExclusiveAtoms(fragmentMap); |
| fixUpLoadOrderDependencies(fragmentMap); |
| |
| return fragmentMap; |
| } |
| |
| private void execImpl() { |
| Map<Integer, List<JsStatement>> fragmentStats = new HashMap<Integer, List<JsStatement>>(); |
| |
| { |
| /* |
| * Compute the base fragment. It includes everything that is live when the |
| * program starts. |
| */ |
| LivenessPredicate alreadyLoaded = new NothingAlivePredicate(); |
| LivenessPredicate liveNow = new CfaLivenessPredicate(initiallyLive); |
| List<JsStatement> noStats = new ArrayList<JsStatement>(); |
| addFragment(0, alreadyLoaded, liveNow, noStats, fragmentStats); |
| } |
| |
| /* |
| * Compute the base fragments, for split points in the initial load |
| * sequence. |
| */ |
| liveAfterInitialSequence = new ControlFlowAnalyzer(initiallyLive); |
| String extendsCfa = "initial"; |
| for (int sp : initialLoadSequence) { |
| LivenessPredicate alreadyLoaded = new CfaLivenessPredicate(liveAfterInitialSequence); |
| String depGraphName = "sp" + sp; |
| dependencyRecorder.startDependencyGraph(depGraphName, extendsCfa); |
| extendsCfa = depGraphName; |
| |
| ControlFlowAnalyzer liveAfterSp = new ControlFlowAnalyzer(liveAfterInitialSequence); |
| JRunAsync runAsync = jprogram.getRunAsyncs().get(sp - 1); |
| assert runAsync.getSplitPoint() == sp; |
| liveAfterSp.traverseFromRunAsync(runAsync); |
| dependencyRecorder.endDependencyGraph(); |
| |
| LivenessPredicate liveNow = new CfaLivenessPredicate(liveAfterSp); |
| |
| List<JsStatement> statsToAppend = fragmentExtractor.createOnLoadedCall(sp); |
| |
| addFragment(sp, alreadyLoaded, liveNow, statsToAppend, fragmentStats); |
| |
| liveAfterInitialSequence = liveAfterSp; |
| } |
| |
| ExclusivityMap fragmentMap = determineExclusivity(); |
| |
| /* |
| * Compute the exclusively live fragments. Each includes everything |
| * exclusively live after entry point i. |
| */ |
| for (JRunAsync runAsync : jprogram.getRunAsyncs()) { |
| int i = runAsync.getSplitPoint(); |
| if (isInitial(i)) { |
| continue; |
| } |
| LivenessPredicate alreadyLoaded = new ExclusivityMapLivenessPredicate(fragmentMap, 0); |
| LivenessPredicate liveNow = new ExclusivityMapLivenessPredicate(fragmentMap, i); |
| List<JsStatement> statsToAppend = fragmentExtractor.createOnLoadedCall(i); |
| addFragment(i, alreadyLoaded, liveNow, statsToAppend, fragmentStats); |
| } |
| |
| /* |
| * Compute the leftovers fragment. |
| */ |
| { |
| LivenessPredicate alreadyLoaded = new CfaLivenessPredicate(liveAfterInitialSequence); |
| LivenessPredicate liveNow = new ExclusivityMapLivenessPredicate(fragmentMap, 0); |
| List<JsStatement> statsToAppend = fragmentExtractor.createOnLoadedCall(numEntries); |
| addFragment(numEntries, alreadyLoaded, liveNow, statsToAppend, fragmentStats); |
| } |
| |
| // now install the new statements in the program fragments |
| jsprogram.setFragmentCount(fragmentStats.size()); |
| for (int i = 0; i < fragmentStats.size(); i++) { |
| JsBlock fragBlock = jsprogram.getFragmentBlock(i); |
| fragBlock.getStatements().clear(); |
| fragBlock.getStatements().addAll(fragmentStats.get(i)); |
| } |
| } |
| |
| /** |
| * <p> |
| * Patch up the fragment map to satisfy load-order dependencies, as described |
| * in the comment of {@link LivenessPredicate}. Load-order dependencies can be |
| * violated when an atom is mapped to 0 as a leftover, but it has some |
| * load-order dependency on an atom that was put in an exclusive fragment. |
| * </p> |
| * |
| * <p> |
| * In general, it might be possible to split things better by considering load |
| * order dependencies when building the fragment map. However, fixing them |
| * after the fact makes CodeSplitter simpler. In practice, for programs tried |
| * so far, there are very few load order dependency fixups that actually |
| * happen, so it seems better to keep the compiler simpler. |
| * </p> |
| */ |
| private void fixUpLoadOrderDependencies(ExclusivityMap fragmentMap) { |
| fixUpLoadOrderDependenciesForMethods(fragmentMap); |
| fixUpLoadOrderDependenciesForTypes(fragmentMap); |
| fixUpLoadOrderDependenciesForClassLiterals(fragmentMap); |
| fixUpLoadOrderDependenciesForFieldsInitializedToStrings(fragmentMap); |
| } |
| |
| private void fixUpLoadOrderDependenciesForClassLiterals(ExclusivityMap fragmentMap) { |
| int numClassLitStrings = 0; |
| int numFixups = 0; |
| for (JField field : fragmentMap.fields.keySet()) { |
| JClassLiteral classLit = fieldToLiteralOfClass.get(field); |
| if (classLit != null) { |
| int classLitFrag = fragmentMap.fields.get(field); |
| for (String string : stringsIn(field.getInitializer())) { |
| numClassLitStrings++; |
| int stringFrag = getOrZero(fragmentMap.strings, string); |
| if (stringFrag != classLitFrag && stringFrag != 0) { |
| numFixups++; |
| fragmentMap.strings.put(string, 0); |
| } |
| } |
| } |
| } |
| if (logger.isLoggable(TreeLogger.DEBUG)) { |
| logger.log(TreeLogger.DEBUG, "Fixed up load-order dependencies by moving " + numFixups |
| + " strings in class literal constructors to fragment 0, out of " + numClassLitStrings); |
| } |
| } |
| |
| private void fixUpLoadOrderDependenciesForFieldsInitializedToStrings(ExclusivityMap fragmentMap) { |
| int numFixups = 0; |
| int numFieldStrings = 0; |
| |
| for (JField field : fragmentMap.fields.keySet()) { |
| if (field.getInitializer() instanceof JStringLiteral) { |
| numFieldStrings++; |
| |
| String string = ((JStringLiteral) field.getInitializer()).getValue(); |
| int fieldFrag = getOrZero(fragmentMap.fields, field); |
| int stringFrag = getOrZero(fragmentMap.strings, string); |
| if (fieldFrag != stringFrag && stringFrag != 0) { |
| numFixups++; |
| fragmentMap.strings.put(string, 0); |
| } |
| } |
| } |
| |
| if (logger.isLoggable(TreeLogger.DEBUG)) { |
| logger.log(TreeLogger.DEBUG, "Fixed up load-order dependencies by moving " + numFixups |
| + " strings used to initialize fields to fragment 0, out of " + +numFieldStrings); |
| } |
| } |
| |
| private void fixUpLoadOrderDependenciesForMethods(ExclusivityMap fragmentMap) { |
| int numFixups = 0; |
| |
| for (JDeclaredType type : jprogram.getDeclaredTypes()) { |
| int typeFrag = getOrZero(fragmentMap.types, type); |
| |
| if (typeFrag != 0) { |
| /* |
| * If the type is in an exclusive fragment, all its instance methods |
| * must be in the same one. |
| */ |
| for (JMethod method : type.getMethods()) { |
| if (method.needsVtable() && methodsInJavaScript.contains(method)) { |
| int methodFrag = getOrZero(fragmentMap.methods, method); |
| if (methodFrag != typeFrag) { |
| fragmentMap.types.put(type, 0); |
| numFixups++; |
| break; |
| } |
| } |
| } |
| } |
| } |
| |
| if (logger.isLoggable(TreeLogger.DEBUG)) { |
| logger.log(TreeLogger.DEBUG, |
| "Fixed up load-order dependencies for instance methods by moving " + numFixups |
| + " types to fragment 0, out of " + jprogram.getDeclaredTypes().size()); |
| } |
| } |
| |
| private void fixUpLoadOrderDependenciesForTypes(ExclusivityMap fragmentMap) { |
| int numFixups = 0; |
| Queue<JDeclaredType> typesToCheck = |
| new ArrayBlockingQueue<JDeclaredType>(jprogram.getDeclaredTypes().size()); |
| typesToCheck.addAll(jprogram.getDeclaredTypes()); |
| |
| while (!typesToCheck.isEmpty()) { |
| JDeclaredType type = typesToCheck.remove(); |
| if (type.getSuperClass() != null) { |
| int typeFrag = getOrZero(fragmentMap.types, type); |
| int supertypeFrag = getOrZero(fragmentMap.types, type.getSuperClass()); |
| if (typeFrag != supertypeFrag && supertypeFrag != 0) { |
| numFixups++; |
| fragmentMap.types.put(type.getSuperClass(), 0); |
| typesToCheck.add(type.getSuperClass()); |
| } |
| } |
| } |
| |
| if (logger.isLoggable(TreeLogger.DEBUG)) { |
| logger.log(TreeLogger.DEBUG, "Fixed up load-order dependencies on supertypes by moving " |
| + numFixups + " types to fragment 0, out of " + jprogram.getDeclaredTypes().size()); |
| } |
| } |
| |
| private boolean isInitial(int entry) { |
| return initialLoadSequence.contains(entry); |
| } |
| |
| /** |
| * Map atoms to exclusive fragments. Do this by trying to find code atoms that |
| * are only needed by a single split point. Such code can be moved to the |
| * exclusively live fragment associated with that split point. |
| */ |
| private void mapExclusiveAtoms(ExclusivityMap fragmentMap) { |
| List<ControlFlowAnalyzer> allButOnes = computeAllButOneCfas(); |
| |
| ControlFlowAnalyzer everything = computeCompleteCfa(); |
| |
| Set<JField> allFields = new HashSet<JField>(); |
| Set<JMethod> allMethods = new HashSet<JMethod>(); |
| |
| for (JNode node : everything.getLiveFieldsAndMethods()) { |
| if (node instanceof JField) { |
| allFields.add((JField) node); |
| } |
| if (node instanceof JMethod) { |
| allMethods.add((JMethod) node); |
| } |
| } |
| allFields.addAll(everything.getFieldsWritten()); |
| |
| for (JRunAsync runAsync : jprogram.getRunAsyncs()) { |
| int splitPoint = runAsync.getSplitPoint(); |
| if (isInitial(splitPoint)) { |
| continue; |
| } |
| ControlFlowAnalyzer allButOne = allButOnes.get(splitPoint - 1); |
| Set<JNode> allLiveNodes = |
| union(allButOne.getLiveFieldsAndMethods(), allButOne.getFieldsWritten()); |
| updateMap(splitPoint, fragmentMap.fields, allLiveNodes, allFields); |
| updateMap(splitPoint, fragmentMap.methods, allButOne.getLiveFieldsAndMethods(), allMethods); |
| updateMap(splitPoint, fragmentMap.strings, allButOne.getLiveStrings(), everything |
| .getLiveStrings()); |
| updateMap(splitPoint, fragmentMap.types, declaredTypesIn(allButOne.getInstantiatedTypes()), |
| declaredTypesIn(everything.getInstantiatedTypes())); |
| } |
| } |
| |
| /** |
| * Traverse <code>exp</code> and find all string literals within it. |
| */ |
| private Set<String> stringsIn(JExpression exp) { |
| final Set<String> strings = new HashSet<String>(); |
| class StringFinder extends JVisitor { |
| @Override |
| public void endVisit(JStringLiteral stringLiteral, Context ctx) { |
| strings.add(stringLiteral.getValue()); |
| } |
| } |
| (new StringFinder()).accept(exp); |
| return strings; |
| } |
| } |
