dart2js cps: Global value numbering and loop-invariant code motion.

pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart

Index: pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart
diff --git a/pkg/compiler/lib/src/cps_ir/share_interceptors.dart b/pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart
similarity index 59%
rename from pkg/compiler/lib/src/cps_ir/share_interceptors.dart
rename to pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart
index 1fbbba31f6bccaa13d320a52eca9eb96303c4e6c..4fbe3070ed2ef8b35aa2015dce163955e232903d 100644
--- a/pkg/compiler/lib/src/cps_ir/share_interceptors.dart
+++ b/pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart
@@ -2,7 +2,7 @@
 // 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.
 
-library dart2js.cps_ir.share_interceptors;
+library dart2js.cps_ir.optimize_interceptors;
 
 import 'optimizers.dart';
 import 'cps_ir_nodes.dart';
@@ -15,35 +15,25 @@ import '../js_backend/js_backend.dart' show JavaScriptBackend;
 import '../types/types.dart' show TypeMask;
 import '../io/source_information.dart' show SourceInformation;
 
-/// Removes redundant `getInterceptor` calls.
-///
-/// The pass performs three optimizations for interceptors:
-///- pull interceptors out of loops
-///- replace interceptors with constants
-///- share interceptors when one is in scope of the other
-class ShareInterceptors extends TrampolineRecursiveVisitor implements Pass {
-  String get passName => 'Share interceptors';
-
-  /// The innermost loop containing a given primitive.
-  final Map<Primitive, Continuation> loopHeaderFor =
-      <Primitive, Continuation>{};
-
-  /// An interceptor currently in scope for a given primitive.
-  final Map<Primitive, Interceptor> interceptorFor = <Primitive, Interceptor>{};
-
-  /// Interceptors that have been hoisted out of a given loop.
-  final Map<Continuation, List<Interceptor>> loopHoistedInterceptors =
-      <Continuation, List<Interceptor>>{};
+/// Replaces `getInterceptor` calls with interceptor constants when possible,
+/// or with "almost constant" expressions like "x && CONST" when the input
+/// is either null or has a known interceptor.
+//
+//  TODO(asgerf): Compute intercepted classes in this pass.
+class OptimizeInterceptors extends TrampolineRecursiveVisitor implements Pass {
+  String get passName => 'Optimize interceptors';
 
   JavaScriptBackend backend;
   LoopHierarchy loopHierarchy;
   Continuation currentLoopHeader;
 
-  ShareInterceptors(this.backend);
+  OptimizeInterceptors(this.backend);
 
   BackendHelpers get helpers => backend.helpers;
 
   void rewrite(FunctionDefinition node) {
+    // TODO(asgerf): Computing the LoopHierarchy here may be overkill when all
+    //               we want is to hoist constants out of loops.
     loopHierarchy = new LoopHierarchy(node);
     visit(node.body);
     new ShareConstants().visit(node);
@@ -53,25 +43,6 @@ class ShareInterceptors extends TrampolineRecursiveVisitor implements Pass {
   Expression traverseContinuation(Continuation cont) {
     Continuation oldLoopHeader = currentLoopHeader;
     currentLoopHeader = loopHierarchy.getLoopHeader(cont);
-    for (Parameter param in cont.parameters) {
-      loopHeaderFor[param] = currentLoopHeader;
-    }
-    if (cont.isRecursive) {
-      pushAction(() {
-        // After the loop body has been processed, all interceptors hoisted
-        // to this loop fall out of scope and should be removed from the
-        // environment.
-        List<Interceptor> hoisted = loopHoistedInterceptors[cont];
-        if (hoisted != null) {
-          for (Interceptor interceptor in hoisted) {
-            Primitive input = interceptor.input.definition;
-            assert(interceptorFor[input] == interceptor);
-            interceptorFor.remove(input);
-            constifyInterceptor(interceptor);
-          }
-        }
-      });
-    }
     pushAction(() {
       currentLoopHeader = oldLoopHeader;
     });
@@ -175,79 +146,20 @@ class ShareInterceptors extends TrampolineRecursiveVisitor implements Pass {
 
   @override
   Expression traverseLetPrim(LetPrim node) {
-    loopHeaderFor[node.primitive] = currentLoopHeader;
     Expression next = node.body;
-    if (node.primitive is! Interceptor) {
-      return next;
-    }
-    Interceptor interceptor = node.primitive;
-    Primitive input = interceptor.input.definition;
-
-    // Try to reuse an existing interceptor for the same input.
-    Interceptor existing = interceptorFor[input];
-    if (existing != null) {
-      existing.interceptedClasses.addAll(interceptor.interceptedClasses);
-      existing.flags |= interceptor.flags;
-      existing.substituteFor(interceptor);
-      interceptor.destroy();
-      node.remove();
-      return next;
-    }
-
-    // Put this interceptor in the environment.
-    interceptorFor[input] = interceptor;
-
-    // Determine how far the interceptor can be lifted. The outermost loop
-    // that contains the input binding should also contain the interceptor
-    // binding.
-    Continuation referencedLoop =
-        lowestCommonAncestor(loopHeaderFor[input], currentLoopHeader);
-    if (referencedLoop != currentLoopHeader) {
-      Continuation hoistTarget = getCurrentOuterLoop(scope: referencedLoop);
-      LetCont loopBinding = hoistTarget.parent;
-      node.remove();
-      node.insertAbove(loopBinding);
-      // Remove the interceptor from the environment after processing the loop.
-      loopHoistedInterceptors
-          .putIfAbsent(hoistTarget, () => <Interceptor>[])
-          .add(interceptor);
-    } else {
-      // Remove the interceptor from the environment when it falls out of scope.
-      pushAction(() {
-        assert(interceptorFor[input] == interceptor);
-        interceptorFor.remove(input);
-
-        // Now that the final set of intercepted classes has been seen, try to
-        // replace it with a constant.
-        constifyInterceptor(interceptor);
-      });
+    if (node.primitive is Interceptor) {
+      constifyInterceptor(node.primitive);
     }
-
     return next;
   }
-
-  /// Returns the the innermost loop that effectively encloses both
-  /// c1 and c2 (or `null` if there is no such loop).
-  Continuation lowestCommonAncestor(Continuation c1, Continuation c2) {
-    int d1 = getDepth(c1), d2 = getDepth(c2);
-    while (c1 != c2) {
-      if (d1 <= d2) {
-        c2 = loopHierarchy.getEnclosingLoop(c2);
-        d2 = getDepth(c2);
-      } else {
-        c1 = loopHierarchy.getEnclosingLoop(c1);
-        d1 = getDepth(c1);
-      }
-    }
-    return c1;
-  }
-
-  int getDepth(Continuation loop) {
-    if (loop == null) return -1;
-    return loopHierarchy.loopDepth[loop];
-  }
 }
 
+/// Shares interceptor constants when one is in scope of another.
+///
+/// Interceptor optimization runs after GVN, hence this clean-up step is needed.
+///
+/// TODO(asgerf): Handle in seperate constant optimization pass? With some other

[sra1, 2015/11/17 05:41:14]

separate

[asgerf, 2015/11/17 12:43:43]

Done.

+///   constant-related optimizations, like cloning small constants at use-site.
 class ShareConstants extends TrampolineRecursiveVisitor {
   Map<ConstantValue, Constant> sharedConstantFor = <ConstantValue, Constant>{};