Better tracking of provided types at call sites

lib/compiler/implementation/js_backend/backend.dart

Index: lib/compiler/implementation/js_backend/backend.dart
diff --git a/lib/compiler/implementation/js_backend/backend.dart b/lib/compiler/implementation/js_backend/backend.dart
index c96cd0eba00473d7d7754bf000249b85ac1b3e01..1979b0048a62d47c20275eb38dd87c125afbfdfd 100644
--- a/lib/compiler/implementation/js_backend/backend.dart
+++ b/lib/compiler/implementation/js_backend/backend.dart
@@ -35,13 +35,40 @@ class ReturnInfo {
       compiledFunctions.add(function);
 }
 
-class HTypeList {
+class OptionalParameterTypes {
+  final List<SourceString> names;
   final List<HType> types;
 
-  HTypeList(int length) : types = new List<HType>(length);
-  const HTypeList.allUnknown() : types = null;
+  OptionalParameterTypes(int optionalArgumentsCount)
+      : names = new List<SourceString>(optionalArgumentsCount),
+        types = new List<HType>(optionalArgumentsCount);
+
+  int get length => names.length;
+  SourceString name(int index) => names[index];
+  HType type(int index) => types[index];
 
-  factory HTypeList.fromInvocation(HInvoke node, HTypeMap types) {
+  void insert(int index, SourceString name, HType type) {

[kasperl, 2012/09/04 09:18:45]

Insert makes it sound like you're growing the list -- maybe change to update?

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

+    names[index] = name;
+    types[index] = type;
+  }
+
+  String toString() => "OptionalParameterTypes($names, $types)";
+}
+
+class HTypeList {
+  final List<HType> types;
+  final List<SourceString> namedArguments;
+
+  HTypeList(int length)
+      : types = new List<HType>(length),
+        namedArguments = null;
+  HTypeList.withNamedArguments(int length, this.namedArguments)
+      : types = new List<HType>(length);
+  const HTypeList.allUnknown()
+      : types = null,
+        namedArguments = null;
+
+  factory HTypeList.fromStaticInvocation(HInvokeStatic node, HTypeMap types) {
     bool allUnknown = true;
     for (int i = 1; i < node.inputs.length; i++) {
       if (types[node.inputs[i]] != HType.UNKNOWN) {
@@ -58,9 +85,27 @@ class HTypeList {
     return result;
   }
 
+  factory HTypeList.fromDynamicInvocation(HInvokeDynamic node,
+                                          Selector selector,
+                                          HTypeMap types) {
+    HTypeList result;
+    if (selector.namedArgumentCount > 0) {
+      result =
+          new HTypeList.withNamedArguments(
+              node.inputs.length - 1, selector.namedArguments);

[kasperl, 2012/09/04 09:18:45]

Maybe cache node.inputs.length - 1 in a local to make this more readable?

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

+    } else {
+      result = new HTypeList(node.inputs.length - 1);
+    }
+    for (int i = 0; i < result.types.length; i++) {
+      result.types[i] = types[node.inputs[i + 1]];
+    }
+    return result;
+  }
+
   static const HTypeList ALL_UNKNOWN = const HTypeList.allUnknown();
 
   bool get allUnknown => types === null;
+  bool get hasNamedArguments => namedArguments != null;
   int get length => types.length;
   HType operator[](int index) => types[index];
 
@@ -117,6 +162,56 @@ class HTypeList {
     return onlyUnknown ? HTypeList.ALL_UNKNOWN : result;
   }
 
+  HTypeList unionWithOptionalParameters(

[kasperl, 2012/09/04 09:18:45]

This is fairly complicated. Can you add unit tests for this function or would
that be too painful?

[Søren Gjesse, 2012/09/04 14:55:07]

I tried to do it in tests/compiler/dart2js/backend_htype_list_test.dart.

+      Selector selector,
+      FunctionSignature signature,
+      OptionalParameterTypes defaultValueTypes) {
+    assert(allUnknown || selector.argumentCount == this.length);
+    // Create a new HTypeList for holding types for all parameters.
+    HTypeList result = new HTypeList(signature.parameterCount);
+
+    // First fill in the type of the positional arguments.
+    int nextTypeIndex = -1;
+    if (allUnknown) {
+      for (int i = 0; i < selector.positionalArgumentCount; i++) {
+        result.types[i] = HType.UNKNOWN;
+      }
+    } else {
+      result.types.setRange(0, selector.positionalArgumentCount, this.types);
+      nextTypeIndex = selector.positionalArgumentCount;
+    }
+    int next = selector.positionalArgumentCount;  // Next parameter of interest.
+    int index = signature.requiredParameterCount;  // Current parameter.
+    signature.forEachOptionalParameter((Element element) {
+      // If some optional parameters where passed positional these have

[kasperl, 2012/09/04 09:18:45]

positional -> positionally

[kasperl, 2012/09/04 09:18:45]

where -> were

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

+      // already been filled.
+      int positionalArgumentCount = selector.positionalArgumentCount;

[kasperl, 2012/09/04 09:18:45]

This local isn't used.

[Søren Gjesse, 2012/09/04 14:55:07]

Removed.

+      if (index == next) {
+        assert(result.types[index] === null);
+        HType type = null;
+        if (selector.namedArgumentCount > 0 && hasNamedArguments) {
+          for (int i = 0; i < namedArguments.length; i++) {

[kasperl, 2012/09/04 09:18:45]

Could you use namedArguments.indexOf here? Maybe you don't even have to check
for namedArgumentCount > 0 and you can just do something like:

   if (hasNamedArguments &&
       selector.namedArguments.indexOf(element.name) >= 0)

Maybe you wouldn't need the break and the type === null check in that case (an
else would do).

[Søren Gjesse, 2012/09/04 14:55:07]

Nice simplification. Done.

+            if (namedArguments[i] == element.name) {
+              type = types[nextTypeIndex++];
+              break;
+            }
+          }
+        }
+        if (type === null) {
+          for (int i = 0; i < defaultValueTypes.length; i++) {

[kasperl, 2012/09/04 09:18:45]

Maybe add indexOf to OptionalParameterTypes?

[Søren Gjesse, 2012/09/04 14:55:07]

Added typeFor(SourceString name) instead.

+            if (defaultValueTypes.name(i) == element.name) {
+              type = defaultValueTypes.type(i);

[kasperl, 2012/09/04 09:18:45]

If you end up not going for indexOf, you should probably add a break here.

[Søren Gjesse, 2012/09/04 14:55:07]

See above.

+            }
+          }
+        }
+        result.types[index] = type;
+        next++;
+      }
+      index++;
+    });
+    return result;
+  }
+
   String toString() =>
       allUnknown ? "HTypeList.ALL_UNKNOWN" : "HTypeList $types";
 }
@@ -128,6 +223,7 @@ class ArgumentTypesRegistry {
   final SelectorMap<HTypeList> selectorTypeMap;
   final FunctionSet optimizedFunctions;
   final Map<Element, HTypeList> optimizedTypes;
+  final Map<Element, OptionalParameterTypes> optimizedDefaultValueTypes;
 
   ArgumentTypesRegistry(JavaScriptBackend backend)
       : staticTypeMap = new Map<Element, HTypeList>(),
@@ -135,21 +231,17 @@ class ArgumentTypesRegistry {
         selectorTypeMap = new SelectorMap<HTypeList>(backend.compiler),
         optimizedFunctions = new FunctionSet(backend.compiler),
         optimizedTypes = new Map<Element, HTypeList>(),
+        optimizedDefaultValueTypes =
+            new Map<Element, OptionalParameterTypes>(),
         this.backend = backend;
 
   Compiler get compiler => backend.compiler;
 
-  // Gather the type information provided. If the types contains no
-  // useful information there is no need to actually store them.
-  HTypeList computeProvidedTypes(HInvoke node, HTypeMap types) {
-    return new HTypeList.fromInvocation(node, types);
-  }
-
   void registerStaticInvocation(HInvokeStatic node, HTypeMap types) {
     Element element = node.element;
     HTypeList oldTypes = staticTypeMap[element];
     if (oldTypes == null) {
-      staticTypeMap[element] = computeProvidedTypes(node, types);
+      staticTypeMap[element] = new HTypeList.fromStaticInvocation(node, types);
     } else {
       if (oldTypes.allUnknown) return;
       HTypeList newTypes = oldTypes.unionWithInvoke(node, types);
@@ -187,11 +279,8 @@ class ArgumentTypesRegistry {
       return;
     }
 
-    // TODO(kasperl): For now, we're only dealing with non-named arguments.
-    // We should generalize this.
-    HTypeList providedTypes = selector.namedArguments.isEmpty()
-        ? computeProvidedTypes(node, types)
-        : HTypeList.ALL_UNKNOWN;
+    HTypeList providedTypes =
+        new HTypeList.fromDynamicInvocation(node, selector, types);
     if (!selectorTypeMap.containsKey(selector)) {
       selectorTypeMap[selector] = providedTypes;
     } else {
@@ -210,17 +299,15 @@ class ArgumentTypesRegistry {
       // TODO(kasperl): Maybe check if the element is already marked for
       // recompilation? Could be pretty cheap compared to computing
       // union types.
-      HTypeList newTypes = parameterTypes(element);
+      HTypeList newTypes =
+          parameterTypes(element, optimizedDefaultValueTypes[element]);
       bool recompile = false;
       if (newTypes.allUnknown) {
         recompile = true;
       } else {
         HTypeList oldTypes = optimizedTypes[element];
-        if (newTypes.length != oldTypes.length) {
-          // TODO(kasperl): This can be improved. If the newTypes aren't in
-          // conflict we can avoid the recompilation.
-          recompile = true;
-        } else for (int i = 0; i < oldTypes.length; i++) {
+        assert(newTypes.length == oldTypes.length);

[kasperl, 2012/09/04 09:18:45]

This is great!

[Søren Gjesse, 2012/09/04 14:55:07]

Thanks.

+        for (int i = 0; i < oldTypes.length; i++) {
           if (newTypes[i] != oldTypes[i]) {
             recompile = true;
             break;
@@ -231,7 +318,8 @@ class ArgumentTypesRegistry {
     });
   }
 
-  HTypeList parameterTypes(element) {
+  HTypeList parameterTypes(FunctionElement element,
+                           OptionalParameterTypes defaultValueTypes) {
     // Handle static functions separately.
     if (Elements.isStaticOrTopLevelFunction(element)) {
       HTypeList types = staticTypeMap[element];
@@ -245,19 +333,25 @@ class ArgumentTypesRegistry {
       }
     }
 
+
     // TODO(kasperl): What kind of non-members do we get here?
     if (!element.isMember()) return HTypeList.ALL_UNKNOWN;
+    if (element.isGetter()) return HTypeList.ALL_UNKNOWN;

[kasperl, 2012/09/04 09:18:45]

Add a comment that explains why getters should lead to ALL_UNKNOWN.

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

 
     FunctionSignature signature = element.computeSignature(compiler);
     HTypeList found = null;
     selectorTypeMap.visitMatching(element,
         (Selector selector, HTypeList types) {
-      if (selector.argumentCount != signature.parameterCount) {
-        found = HTypeList.ALL_UNKNOWN;
-        return false;
-      } else if (found === null) {
+      if (selector.argumentCount != signature.parameterCount ||
+          selector.namedArgumentCount > 0) {
+        types = types.unionWithOptionalParameters(selector,
+                                                 signature,

[kasperl, 2012/09/04 09:18:45]

Indentation is slightly off.

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

+                                                 defaultValueTypes);
+      }
+      assert(types.allUnknown || types.length == signature.parameterCount);
+      if (found === null) {
         found = types;
-        return true;
+        return !found.allUnknown;

[kasperl, 2012/09/04 09:18:45]

This should be shareable now. Something like:

   found = (found === null) ? types : found.union(types);
   return !found.allUnknown;

[Søren Gjesse, 2012/09/04 14:55:07]

Done.

       } else {
         found = found.union(types);
         return !found.allUnknown;
@@ -266,7 +360,9 @@ class ArgumentTypesRegistry {
     return found !== null ? found : HTypeList.ALL_UNKNOWN;
   }
 
-  void registerOptimization(Element element, HTypeList parameterTypes) {
+  void registerOptimization(Element element,
+                            HTypeList parameterTypes,
+                            OptionalParameterTypes defaultValueTypes) {
     if (Elements.isStaticOrTopLevelFunction(element)) {
       if (parameterTypes.allUnknown) {
         optimizedStaticFunctions.remove(element);
@@ -281,9 +377,11 @@ class ArgumentTypesRegistry {
     if (parameterTypes.allUnknown) {
       optimizedFunctions.remove(element);
       optimizedTypes.remove(element);
+      optimizedDefaultValueTypes.remove(element);
     } else {
       optimizedFunctions.add(element);
       optimizedTypes[element] = parameterTypes;
+      optimizedDefaultValueTypes[element] = defaultValueTypes;
     }
   }
 }
@@ -505,18 +603,25 @@ class JavaScriptBackend extends Backend {
    * function. The types are optimistic in the sense as they are based on the
    * possible invocations of the function seen so far.
    */
-  HTypeList optimisticParameterTypes(FunctionElement element) {
-    return argumentTypes.parameterTypes(element);
+  HTypeList optimisticParameterTypes(
+      FunctionElement element,
+      OptionalParameterTypes defaultValueTypes) {
+    return argumentTypes.parameterTypes(element, defaultValueTypes);
   }
 
   /**
    * Register that the function [element] has been optimized under the
    * assumptions that the types [parameterType] will be used for calling it.
-   * If this assumption fail the function will be scheduled for recompilation.
+   * The passed [defaultValueTypes] holds the types of default values for
+   * the optional parameters. If this assumption fail the function will be
+   * scheduled for recompilation.
    */
   registerParameterTypesOptimization(
-      FunctionElement element, HTypeList parameterTypes) {
-    argumentTypes.registerOptimization(element, parameterTypes);
+      FunctionElement element,
+      HTypeList parameterTypes,

[kasperl, 2012/09/04 09:18:45]

I wonder if we should have an abstraction over all the parameter types -- and
not have two separate parts?

[Søren Gjesse, 2012/09/04 14:55:07]

That might be - I will look at that as a separate change.

+      OptionalParameterTypes defaultValueTypes) {
+    argumentTypes.registerOptimization(
+        element, parameterTypes, defaultValueTypes);
   }
 
   void registerReturnType(FunctionElement element, HType returnType) {