RFC: Resolution based tree-shaking.

dart/lib/compiler/implementation/compiler.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
+
+/**
+ * If true, print a warning for each method that was resolved, but not
+ * compiled.
+ */
+final bool REPORT_EXCESS_RESOLUTION = false;
+
 class WorkItem {
   final Element element;
   TreeElements resolutionTree;
   bool allowSpeculativeOptimization = true;
   List<HTypeGuard> guards = const <HTypeGuard>[];
 
   WorkItem(this.element, this.resolutionTree);
 
   bool isAnalyzed() => resolutionTree !== null;
 
   String run(Compiler compiler, Enqueuer world) {
     String code = world.universe.generatedCode[element];
     if (code !== null) return code;
-    if (!isAnalyzed()) compiler.analyze(this);
-    return compiler.codegen(this);
+    resolutionTree = compiler.analyze(this, world);
+    return compiler.codegen(this, world);
   }
 }
 
 class Backend {
   final Compiler compiler;
 
   Backend(this.compiler);
 
+  void enqueueAllTopLevelFunctions(LibraryElement lib, Enqueuer world) {
+    lib.forEachExport((Element e) {
+      if (e.isFunction()) world.addToWorkList(e);
+    });
+  }
+
+  abstract void enqueueHelpers(Enqueuer world);
   abstract String codegen(WorkItem work);
   abstract void processNativeClasses(world, libraries);
   abstract void assembleProgram();
   abstract List<CompilerTask> get tasks();
 }
 
 class JavaScriptBackend extends Backend {
   SsaBuilderTask builder;
   SsaOptimizerTask optimizer;
   SsaCodeGeneratorTask generator;
   CodeEmitterTask emitter;
 
   List<CompilerTask> get tasks() {
     return <CompilerTask>[builder, optimizer, generator, emitter];
   }
 
   JavaScriptBackend(Compiler compiler)
       : emitter = new CodeEmitterTask(compiler),
         super(compiler) {
     builder = new SsaBuilderTask(this);
     optimizer = new SsaOptimizerTask(this);
     generator = new SsaCodeGeneratorTask(this);
   }
 
+  void enqueueHelpers(Enqueuer world) {
+    enqueueAllTopLevelFunctions(compiler.jsHelperLibrary, world);
+    enqueueAllTopLevelFunctions(compiler.interceptorsLibrary, world);
+    for (var helper in [const SourceString('Closure'),
+                        const SourceString('ConstantMap'),
+                        const SourceString('ConstantProtoMap')]) {
+      var e = compiler.findHelper(helper);
+      if (e !== null) world.registerInstantiatedClass(e);
+    }
+  }
+
   String codegen(WorkItem work) {
     HGraph graph = builder.build(work);
     optimizer.optimize(work, graph);
     if (work.allowSpeculativeOptimization
         && optimizer.trySpeculativeOptimizations(work, graph)) {
       String code = generator.generateBailoutMethod(work, graph);
       compiler.codegenWorld.addBailoutCode(work, code);
       optimizer.prepareForSpeculativeOptimizations(work, graph);
       optimizer.optimize(work, graph);
     }
@@ skipping 136 matching lines @@
     reportDiagnostic(spanFromElement(element),
                      MessageKind.COMPILER_CRASHED.error().toString(),
                      false);
     // TODO(ahe): Obtain the build ID.
     var buildId = 'build number could not be determined';
     print(MessageKind.PLEASE_REPORT_THE_CRASH.message([buildId]));
   }
 
   void cancel([String reason, Node node, Token token,
                HInstruction instruction, Element element]) {
+    assembledCode = null; // Compilation failed. Make sure that we
+                          // don't return a bogus result.
     SourceSpan span = const SourceSpan(null, null, null);
     if (node !== null) {
       span = spanFromNode(node);
     } else if (token !== null) {
       span = spanFromTokens(token, token);
     } else if (instruction !== null) {
       span = spanFromElement(currentElement);
     } else if (element !== null) {
       span = spanFromElement(element);
     } else {
@@ skipping 23 matching lines @@
       return false;
     }
     tracer.close();
     log('compilation succeeded');
     return true;
   }
 
   void enableNoSuchMethod(Element element) {
     // TODO(ahe): Move this method to Enqueuer.
     if (enabledNoSuchMethod) return;
-    if (element.enclosingElement == objectClass) return;
+    if (element.enclosingElement === objectClass) {
+      enqueuer.resolution.registerDynamicInvocationOf(element);
+      return;
+    }
     enabledNoSuchMethod = true;
+    enqueuer.resolution.registerInvocation(NO_SUCH_METHOD,
+                                           Selector.INVOCATION_2);
     enqueuer.codegen.registerInvocation(NO_SUCH_METHOD,
-                                        new Selector.invocation(2));
+                                        Selector.INVOCATION_2);
   }
 
   void enableIsolateSupport(LibraryElement element) {
     // TODO(ahe): Move this method to Enqueuer.
     isolateLibrary = element;
+    enqueuer.resolution.addToWorkList(element.find(START_ROOT_ISOLATE));
+    enqueuer.resolution.addToWorkList(
+        element.find(const SourceString('_currentIsolate')));
+    enqueuer.resolution.addToWorkList(
+        element.find(const SourceString('_callInIsolate')));
     enqueuer.codegen.addToWorkList(element.find(START_ROOT_ISOLATE));
   }
 
   bool hasIsolateSupport() => isolateLibrary !== null;
 
   void onLibraryLoaded(LibraryElement library, Uri uri) {
     if (uri.toString() == 'dart:isolate') {
       enableIsolateSupport(library);
     }
     if (dynamicClass !== null) {
@@ skipping 89 matching lines @@
       FunctionSignature parameters = mainMethod.computeSignature(this);
       parameters.forEachParameter((Element parameter) {
         reportFatalError('main cannot have parameters', parameter);
       });
     }
 
     // TODO(ahe): Remove this line. Eventually, enqueuer.resolution
     // should know this.
     world.populate(this, libraries.getValues());
 
-    // Not yet ready to process the enqueuer.resolution queue...
-    // processQueue(enqueuer.resolution);
+    log('Resolving...');
+    backend.enqueueHelpers(enqueuer.resolution);
+    processQueue(enqueuer.resolution, main);
+    log('Resolved ${enqueuer.resolution.resolvedElements.length} elements.');
+
+    log('Compiling...');
     processQueue(enqueuer.codegen, main);
+    log('Compiled ${codegenWorld.generatedCode.length} methods.');
 
     backend.assembleProgram();
-    if (!enqueuer.codegen.queue.isEmpty()) {
-      internalErrorOnElement(enqueuer.codegen.queue.first().element,
-                             "work list is not empty");
-    }
+
+    checkQueues();
   }
 
   processQueue(Enqueuer world, Element main) {
     backend.processNativeClasses(world, libraries.getValues());
     world.addToWorkList(main);
     codegenProgress.reset();
-    while (!world.queue.isEmpty()) {
-      WorkItem work = world.queue.removeLast();
+    world.forEach((WorkItem work) {
       withCurrentElement(work.element, () => work.run(this, world));
-    }
+    });
     world.queueIsClosed = true;
     assert(world.checkNoEnqueuedInvokedInstanceMethods());
     world.registerFieldClosureInvocations();
   }
 
+  /**
+   * Perform various checks of the queues. This includes checking that
+   * the queues are empty (nothing was added after we stopped
+   * processing the quese). Also compute the number of methods that

[ngeoffray, 2012/06/12 12:44:14]

quese -> queues

[ahe, 2012/06/12 18:47:13]

Done.

+   * were resolved, but not compiled (aka excess resolution).
+   */
+  checkQueues() {
+    for (var world in [enqueuer.resolution, enqueuer.codegen]) {
+      world.forEach((WorkItem work) {
+        internalErrorOnElement(work.element, "Work list is not empty.");
+      });
+    }
+    var resolved = new Set.from(enqueuer.resolution.resolvedElements.getKeys());
+    for (Element e in codegenWorld.generatedCode.getKeys()) {
+      resolved.remove(e);
+    }
+    for (Element e in new Set.from(resolved)) {
+      if (e.isClass() ||
+          e.isField() ||
+          e.isTypeVariable() ||
+          e.isTypedef() ||
+          e.kind === ElementKind.ABSTRACT_FIELD) {
+        resolved.remove(e);
+      }
+      if (e.kind === ElementKind.GENERATIVE_CONSTRUCTOR) {
+        if (e.enclosingElement.isInterface()) {
+          resolved.remove(e);
+        }
+        resolved.remove(e);
+
+      }
+      if (e.getLibrary() === jsHelperLibrary) {
+        resolved.remove(e);
+      }
+      if (e.getLibrary() === interceptorsLibrary) {
+        resolved.remove(e);
+      }
+    }
+    log('Excess resolution work: ${resolved.length}.');
+    if (!REPORT_EXCESS_RESOLUTION) return;
+    for (Element e in resolved) {
+      SourceSpan span = spanFromElement(e);
+      reportDiagnostic(span, 'Warning: $e resolved but not compiled.', false);
+    }
+  }
+
   TreeElements analyzeElement(Element element) {
+    TreeElements elements = enqueuer.resolution.getCachedElements(element);
+    if (elements !== null) return elements;
+    if (element is AbstractFieldElement) {

[ngeoffray, 2012/06/12 12:44:14]

Maybe add this check together with the allowed check line 486.

[ahe, 2012/06/12 18:47:13]

Done.

+      return null;
+    }
+    final int allowed = ElementCategory.VARIABLE | ElementCategory.FUNCTION
+                        | ElementCategory.FACTORY;
+    if (!element.isAccessor() && (element.kind.category & allowed) == 0) {
+      return null;
+    }
     assert(parser !== null);
     Node tree = parser.parse(element);
     validator.validate(tree);
     unparseValidator.check(element);
-    TreeElements elements = resolver.resolve(element);
+    elements = resolver.resolve(element);
     checker.check(tree, elements);
     return elements;
   }
 
-  TreeElements analyze(WorkItem work) {
-    work.resolutionTree = analyzeElement(work.element);
-    return work.resolutionTree;
+  TreeElements analyze(WorkItem work, Enqueuer world) {
+    if (work.isAnalyzed()) return work.resolutionTree;
+    Element element = work.element;
+    TreeElements result = world.getCachedElements(element);
+    if (result !== null) return result;
+    if (world !== enqueuer.resolution) {
+      internalErrorOnElement(element,
+                             'Internal error: unresolved element: $element.');
+    }
+    result = analyzeElement(element);
+    enqueuer.resolution.resolvedElements[element] = result;
+    return result;
   }
 
-  String codegen(WorkItem work) {
+  String codegen(WorkItem work, Enqueuer world) {
+    if (world !== enqueuer.codegen) return null;

[ngeoffray, 2012/06/12 12:44:14]

Can we actually prevent this situation? Or is that too cumbersome?

[ahe, 2012/06/12 18:47:13]

I'm not sure I understand your question.

[ngeoffray, 2012/06/13 07:31:57]

It does not feel right that the resolver queue ends up being mixed with the
codegen method in compiler. But that's probably because of how the pipeline is
structured.

[ahe, 2012/06/13 08:20:41]

I have some ideas for cleaning this up. If enqueuer.codegen and
enqueuer.resolution were slightly different classes (or initialized
differently), then we could probably change WorkItem.run, analyze, and codegen
to be simpler.

     if (codegenProgress.elapsedInMs() > 500) {
       // TODO(ahe): Add structured diagnostics to the compiler API and
       // use it to separate this from the --verbose option.
-      log('compiled ${codegenWorld.generatedCode.length} methods');
+      log('Compiled ${codegenWorld.generatedCode.length} methods.');
       codegenProgress.reset();
     }
     if (work.element.kind.category == ElementCategory.VARIABLE) {
       constantHandler.compileWorkItem(work);
       return null;
     } else {
       String code = backend.codegen(work);
       codegenWorld.addGeneratedCode(work, code);
       return code;
     }
@@ skipping 49 matching lines @@
   }
 
   reportError(Node node, var message) {
     SourceSpan span = spanFromNode(node);
     reportDiagnostic(span, "${red('error:')} $message", true);
     throw new CompilerCancelledException(message.toString());
   }
 
   abstract void reportDiagnostic(SourceSpan span, String message, bool fatal);
 
-  SourceSpan spanFromTokens(Token begin, Token end) {
+  SourceSpan spanFromTokens(Token begin, Token end, [Uri uri]) {
     if (begin === null || end === null) {
       // TODO(ahe): We can almost always do better. Often it is only
       // end that is null. Otherwise, we probably know the current
       // URI.
-      throw 'cannot find tokens to produce error message';
+      throw 'Cannot find tokens to produce error message.';
     }
-    Uri uri = currentElement.getCompilationUnit().script.uri;
+    if (uri === null) {
+      uri = currentElement.getCompilationUnit().script.uri;
+    }
     return SourceSpan.withOffsets(begin, end, (beginOffset, endOffset) =>
         new SourceSpan(uri, beginOffset, endOffset));
   }
 
   SourceSpan spanFromNode(Node node) {
     return spanFromTokens(node.getBeginToken(), node.getEndToken());
   }
 
   SourceSpan spanFromElement(Element element) {
     if (element.position() === null) {
       // Sometimes, the backend fakes up elements that have no
       // position. So we use the enclosing element instead. It is
       // not a good error location, but cancel really is "internal
       // error" or "not implemented yet", so the vicinity is good
       // enough for now.
       element = element.enclosingElement;
       // TODO(ahe): I plan to overhaul this infrastructure anyways.
     }
     if (element === null) {
       element = currentElement;
     }
     Token position = element.position();
-    if (position === null) {
-      Uri uri = element.getCompilationUnit().script.uri;
-      return new SourceSpan(uri, 0, 0);
-    }
-    return spanFromTokens(position, position);
+    Uri uri = element.getCompilationUnit().script.uri;
+    return (position === null)
+        ? new SourceSpan(uri, 0, 0)
+        : spanFromTokens(position, position, uri);
   }
 
   Script readScript(Uri uri, [ScriptTag node]) {
     unimplemented('Compiler.readScript');
   }
 
   String get legDirectory() {
     unimplemented('Compiler.legDirectory');
   }
 
@@ skipping 68 matching lines @@
     // invariant that endOffset > beginOffset, but for EOF the
     // charoffset of the next token may be [beginOffset]. This can
     // also happen for synthetized tokens that are produced during
     // error handling.
     final endOffset =
       Math.max((end.next !== null) ? end.next.charOffset : 0, beginOffset + 1);
     assert(endOffset > beginOffset);
     return f(beginOffset, endOffset);
   }
 }