dart2js cps: More interceptor optimizations and fixes.

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

 // Copyright (c) 2015, 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.
 
 library dart2js.cps_ir.share_interceptors;
 
 import 'optimizers.dart';
 import 'cps_ir_nodes.dart';
 import 'loop_hierarchy.dart';
+import 'cps_fragment.dart';
 import '../constants/values.dart';
+import '../elements/elements.dart';
+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, Primitive> interceptorFor =
-      <Primitive, Primitive>{};
+  final Map<Primitive, Interceptor> interceptorFor = <Primitive, Interceptor>{};
 
-  /// A primitive currently in scope holding a given interceptor constant.
-  final Map<ConstantValue, Primitive> sharedConstantFor =
-      <ConstantValue, Primitive>{};
+  /// Interceptors that have been hoisted out of a given loop.
+  final Map<Continuation, List<Interceptor>> loopHoistedInterceptors =
+      <Continuation, List<Interceptor>>{};
 
-  /// Interceptors to be hoisted out of the given loop.
-  final Map<Continuation, List<Primitive>> loopHoistedInterceptors =
-      <Continuation, List<Primitive>>{};
-
+  JavaScriptBackend backend;
   LoopHierarchy loopHierarchy;
   Continuation currentLoopHeader;
 
+  ShareInterceptors(this.backend);
+
   void rewrite(FunctionDefinition node) {
     loopHierarchy = new LoopHierarchy(node);
     visit(node.body);
+    new ShareConstants().visit(node);
   }
 
   @override
   Expression traverseContinuation(Continuation cont) {
     Continuation oldLoopHeader = currentLoopHeader;
-    pushAction(() {
-      currentLoopHeader = oldLoopHeader;
-    });
     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<Primitive> hoisted = loopHoistedInterceptors[cont];
+        List<Interceptor> hoisted = loopHoistedInterceptors[cont];
         if (hoisted != null) {
-          for (Primitive interceptor in hoisted) {
-            if (interceptor is Interceptor) {
-              Primitive input = interceptor.input.definition;
-              assert(interceptorFor[input] == interceptor);
-              interceptorFor.remove(input);
-            } else if (interceptor is Constant) {
-              assert(sharedConstantFor[interceptor.value] == interceptor);
-              sharedConstantFor.remove(interceptor.value);
-            } else {
-              throw "Unexpected interceptor: $interceptor";
-            }
+          for (Interceptor interceptor in hoisted) {
+            Primitive input = interceptor.input.definition;
+            assert(interceptorFor[input] == interceptor);
+            interceptorFor.remove(input);
+            constifyInterceptor(interceptor);
           }
         }
       });
     }
+    pushAction(() {
+      currentLoopHeader = oldLoopHeader;
+    });
     return cont.body;
   }
 
+  /// If only one method table can be returned by the given interceptor,
+  /// returns a constant for that method table.
+  InterceptorConstantValue getInterceptorConstant(Interceptor node) {
+    if (node.interceptedClasses.length == 1 &&
+        node.isInterceptedClassAlwaysExact) {
+      ClassElement interceptorClass = node.interceptedClasses.single;
+      return new InterceptorConstantValue(interceptorClass.rawType);
+    }
+    return null;
+  }
+
+  bool hasNoFalsyValues(ClassElement class_) {
+    return class_ != backend.jsInterceptorClass &&
+       class_ != backend.jsNullClass &&
+       class_ != backend.jsBoolClass &&
+       class_ != backend.jsStringClass &&
+       !class_.isSubclassOf(backend.jsNumberClass);
+  }
+
+  Continuation getCurrentOuterLoop({Continuation scope}) {
+    Continuation inner = null, outer = currentLoopHeader;
+    while (outer != scope) {
+      inner = outer;
+      outer = loopHierarchy.getEnclosingLoop(outer);
+    }
+    return inner;
+  }
+
+  /// Binds the given constant in a primitive, in scope of the [useSite].
+  ///
+  /// The constant will be hoisted out of loops, and shared with other requests
+  /// for the same constant as long as it is in scope.
+  Primitive makeConstantFor(ConstantValue constant,
+                            {Expression useSite,
+                             TypeMask type,
+                             SourceInformation sourceInformation,
+                             Entity hint}) {
+    Constant prim =
+        new Constant(constant, sourceInformation: sourceInformation);
+    prim.hint = hint;
+    prim.type = type;
+    LetPrim letPrim = new LetPrim(prim);
+    Continuation loop = getCurrentOuterLoop();
+    if (loop != null) {
+      LetCont loopBinding = loop.parent;
+      letPrim.insertAbove(loopBinding);
+    } else {
+      letPrim.insertAbove(useSite);
+    }
+    return prim;
+  }
+
+  void constifyInterceptor(Interceptor interceptor) {
+    LetPrim let = interceptor.parent;
+    InterceptorConstantValue constant = getInterceptorConstant(interceptor);
+
+    if (constant == null) return;
+
+    if (interceptor.isAlwaysIntercepted) {
+      Primitive constantPrim = makeConstantFor(constant,
+          useSite: let,
+          type: interceptor.type,
+          sourceInformation: interceptor.sourceInformation);
+      constantPrim.useElementAsHint(interceptor.hint);
+      constantPrim.substituteFor(interceptor);
+      interceptor.destroy();
+      let.remove();
+    } else if (interceptor.isAlwaysNullOrIntercepted) {
+      Primitive input = interceptor.input.definition;
+      Primitive constantPrim = makeConstantFor(constant,
+          useSite: let,
+          type: interceptor.type.nonNullable(),
+          sourceInformation: interceptor.sourceInformation);
+      CpsFragment cps = new CpsFragment(interceptor.sourceInformation);
+      Parameter param = new Parameter(interceptor.hint);
+      Continuation cont = cps.letCont(<Parameter>[param]);
+      if (interceptor.interceptedClasses.every(hasNoFalsyValues)) {
+        // If null is the only falsy value, compile as "x && CONST".
+        cps.ifFalsy(input).invokeContinuation(cont, [input]);
+      } else {
+        // If there are other falsy values compile as "x == null ? x : CONST".
+        Primitive condition = cps.applyBuiltin(
+            BuiltinOperator.LooseEq,
+            [input, cps.makeNull()]);
+        cps.ifTruthy(condition).invokeContinuation(cont, [input]);
+      }
+      cps.invokeContinuation(cont, [constantPrim]);
+      cps.context = cont;
+      cps.insertAbove(let);
+      param.substituteFor(interceptor);
+      interceptor.destroy();
+      let.remove();
+    }
+  }
+
   @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.
-    Primitive existing = interceptorFor[input];
+    Interceptor existing = interceptorFor[input];
     if (existing != null) {
-      if (existing is Interceptor) {
-        existing.interceptedClasses.addAll(interceptor.interceptedClasses);
-      }
+      existing.interceptedClasses.addAll(interceptor.interceptedClasses);
+      existing.flags |= interceptor.flags;
       existing.substituteFor(interceptor);
       interceptor.destroy();
       node.remove();
       return next;
     }
 
-    // There is no interceptor obtained from this particular input, but
-    // there might one obtained from another input that is known to
-    // have the same result, so try to reuse that.
-    InterceptorConstantValue constant = interceptor.constantValue;
-    if (constant != null) {
-      existing = sharedConstantFor[constant];
-      if (existing != null) {
-        existing.substituteFor(interceptor);
-        interceptor.destroy();
-        node.remove();
-        return next;
-      }
+    // Put this interceptor in the environment.
+    interceptorFor[input] = interceptor;
 
-      // The interceptor could not be shared. Replace it with a constant.
-      Constant constantPrim = new Constant(constant);
-      node.primitive = constantPrim;
-      constantPrim.parent = node;
-      constantPrim.hint = interceptor.hint;
-      constantPrim.type = interceptor.type;
-      constantPrim.substituteFor(interceptor);
-      interceptor.destroy();
-      sharedConstantFor[constant] = constantPrim;
+    // 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, () => <Primitive>[])
+          .add(interceptor);
     } else {
-      interceptorFor[input] = interceptor;
+      // 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);
+      });
     }
 
-    // Determine the outermost loop where the input to the interceptor call
-    // is available.  Constant interceptors take no input and can thus be
-    // hoisted all way to the top-level.
-    Continuation referencedLoop = constant != null
-        ? null
-        : lowestCommonAncestor(loopHeaderFor[input], currentLoopHeader);
-    if (referencedLoop != currentLoopHeader) {
-      // [referencedLoop] contains the binding for [input], so we cannot hoist
-      // the interceptor outside that loop.  Find the loop nested one level
-      // inside referencedLoop, and hoist the interceptor just outside that one.
-      Continuation loop = currentLoopHeader;
-      Continuation enclosing = loopHierarchy.getEnclosingLoop(loop);
-      while (enclosing != referencedLoop) {
-        assert(loop != null);
-        loop = enclosing;
-        enclosing = loopHierarchy.getEnclosingLoop(loop);
-      }
-      assert(loop != null);
-
-      // Move the LetPrim above the loop binding.
-      LetCont loopBinding = loop.parent;
-      node.remove();
-      node.insertAbove(loopBinding);
-
-      // A different loop now contains the interceptor.
-      loopHeaderFor[node.primitive] = enclosing;
-
-      // Register the interceptor as hoisted to that loop, so it will be
-      // removed from the environment when it falls out of scope.
-      loopHoistedInterceptors
-          .putIfAbsent(loop, () => <Primitive>[])
-          .add(node.primitive);
-    } else if (constant != null) {
-      // The LetPrim was not hoisted. Remove the bound interceptor from the
-      // environment when leaving the LetPrim body.
-      pushAction(() {
-        assert(sharedConstantFor[constant] == node.primitive);
-        sharedConstantFor.remove(constant);
-      });
-    } else {
-      pushAction(() {
-        assert(interceptorFor[input] == node.primitive);
-        interceptorFor.remove(input);
-      });
-    }
     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];
   }
 }
+
+class ShareConstants extends TrampolineRecursiveVisitor {
+  Map<ConstantValue, Constant> sharedConstantFor = <ConstantValue, Constant>{};
+
+  Expression traverseLetPrim(LetPrim node) {
+    Expression next = node.body;
+    if (node.primitive is Constant && shouldShareConstant(node.primitive)) {
+      Constant prim = node.primitive;
+      Constant existing = sharedConstantFor[prim.value];
+      if (existing != null) {
+        existing.substituteFor(prim);
+        existing.useElementAsHint(prim.hint);

[sra1, 2015/10/28 02:31:52]

Should we really keep the dominating hint in the case of a conflict?
In the following, neither x_ nor y_ are good names:

var x_ = C.JSNumber_methods, y_ = C.JSNumber_methods;
x_.toInt$0(x)
y_.toInt$0(y)
->
var x_ = C.JSNumber_methods;
x_.toInt$0(x);
x_.toInt$0(y);

In this case we should probably make a hint based on the class, e.g. JSNumber_
or num_

These comments are FYI. We can address this later. I think some hints could be
better chosen in a specific pass.

[asgerf, 2015/10/28 10:06:31]

I agree, the names usually aren't that great, and sometimes downright confusing.

+        prim.destroy();
+        node.remove();
+        return next;
+      }
+      sharedConstantFor[prim.value] = prim;
+      pushAction(() {
+        assert(sharedConstantFor[prim.value] == prim);
+        sharedConstantFor.remove(prim.value);
+      });
+    }
+    return next;
+  }
+
+  bool shouldShareConstant(Constant constant) {
+    return constant.value.isInterceptor;
+  }
+}