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.
 
+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;
   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);
 
+  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();
   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) {
+    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);
     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 179 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();
   }
 
+  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) {
       constantHandler.compileWorkItem(work);
       return null;
     } else {
       String code = backend.codegen(work);
       codegenWorld.addGeneratedCode(work, code);
       return code;
     }
@@ skipping 79 matching lines @@
       // 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();
+    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]) {
     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);
   }
 }