RFC: Resolution based tree-shaking.

dart/lib/compiler/implementation/compiler.dart

Index: dart/lib/compiler/implementation/compiler.dart
diff --git a/dart/lib/compiler/implementation/compiler.dart b/dart/lib/compiler/implementation/compiler.dart
index 2b4679c73003466009e44e4fbf641bcc0d964b2b..fd4912d2e9dc9b99b457c55ec6d49bee8b187809 100644
--- a/dart/lib/compiler/implementation/compiler.dart
+++ b/dart/lib/compiler/implementation/compiler.dart
@@ -2,6 +2,8 @@
 // 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.
 
+final bool REPORT_EXCESS_RESOLUTION = false;

[ahe, 2012/06/12 06:22:49]

Document this.

[ahe, 2012/06/12 10:56:11]

Done.

+
 class WorkItem {
   final Element element;
   TreeElements resolutionTree;
@@ -15,8 +17,8 @@ class WorkItem {
   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);
   }
 }
 
@@ -25,6 +27,7 @@ class Backend {
 
   Backend(this.compiler);
 
+  abstract void enqueueHelpers(Enqueuer world);

[ahe, 2012/06/12 06:22:49]

Implement in dart backend.

[ahe, 2012/06/12 10:56:11]

Done.

   abstract String codegen(WorkItem work);
   abstract void processNativeClasses(world, libraries);
   abstract void assembleProgram();
@@ -49,6 +52,21 @@ class JavaScriptBackend extends Backend {
     generator = new SsaCodeGeneratorTask(this);
   }
 
+  void enqueueHelpers(Enqueuer world) {
+    for (var lib in [compiler.jsHelperLibrary, compiler.interceptorsLibrary]) {

[kasperl, 2012/06/12 05:50:12]

Add a comment that explains that this enqueues all functions in the two
libraries -- or add a helper function ala enqueueAllToplevelFunctionsFrom(lib)?

[ahe, 2012/06/12 10:56:11]

Done.

+      for (Element e in lib.elements.getValues()) {
+        if (e.isFunction()) {
+          world.addToWorkList(e);
+        }
+      }
+    }
+    for (var helper in [const SourceString('Closure'),
+                        const SourceString('ConstantMap'),
+                        const SourceString('ConstantProtoMap')]) {
+      world.registerInstantiatedClass(compiler.findHelper(helper));
+    }
+  }
+
   String codegen(WorkItem work) {
     HGraph graph = builder.build(work);
     optimizer.optimize(work, graph);
@@ -248,15 +266,25 @@ class Compiler implements DiagnosticListener {
   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));
   }
 
@@ -366,50 +394,112 @@ class Compiler implements DiagnosticListener {
     // 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();
   }
 
+  checkQueues() {

[kasperl, 2012/06/12 05:50:12]

Add a high level comment that explains the purpose of this method.

[ahe, 2012/06/12 10:56:11]

Done.

+    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 resolved) {
+      if (e.isClass() ||
+          e.isField() ||
+          e.isTypeVariable() ||
+          e.isTypedef() ||
+          e.kind === ElementKind.ABSTRACT_FIELD) {
+        resolved.remove(e);

[sra1, 2012/06/12 02:25:20]

I'm not sure it is safe to remove elements from a set while iterating over the
set.

[ahe, 2012/06/12 06:22:49]

I thought about that when writing the code. Nothing seemed to break, so I
assumed it was safe. The documentation of Set.remove does not mention that it
isn't safe. I'll change the code, assuming that it isn't safe and file a bug to
update the documentation of Set.remove. 

[ahe, 2012/06/12 10:56:11]

Done.

+      }
+      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) {

[ahe, 2012/06/12 06:22:49]

Clean up these and the following special cases.

[ahe, 2012/06/12 10:56:11]

That doesn't work :-(

+      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);

[kasperl, 2012/06/12 05:50:12]

I think I would use two separate variables for this by calling the first one
'cached' and the other one 'elements'. It feels a bit simpler that way.

[ahe, 2012/06/12 10:56:11]

I don't see the benefit.

     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);

[kasperl, 2012/06/12 05:50:12]

Consider a cached/result split here too.

[ahe, 2012/06/12 10:56:11]

Done. Well, I considered it :-)

+    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;
     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) {
@@ -509,11 +599,16 @@ class Compiler implements DiagnosticListener {
       element = currentElement;
     }
     Token position = element.position();
+    Uri uri = element.getCompilationUnit().script.uri;
     if (position === null) {
-      Uri uri = element.getCompilationUnit().script.uri;
       return new SourceSpan(uri, 0, 0);
+    } else {
+      return SourceSpan.withOffsets(

[ahe, 2012/06/12 06:22:49]

This inlines part of spanFromTokens to define the uri. Consider an optional
argument.

[ahe, 2012/06/12 10:56:11]

Done.

+          position, position,
+          (beginOffset, endOffset) {

[kasperl, 2012/06/12 05:50:12]

Maybe pull out this closure into a named function declaration instead so its
purpose becomes more obvious?

[ahe, 2012/06/12 10:56:11]

Done.

+            return new SourceSpan(uri, beginOffset, endOffset);
+          });
     }
-    return spanFromTokens(position, position);
   }
 
   Script readScript(Uri uri, [ScriptTag node]) {