Better tracking of provided types at call sites

lib/compiler/implementation/js_backend/backend.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.
 
 typedef void Recompile(Element element);
 
 class ReturnInfo {
   HType returnType;
   List<Element> compiledFunctions;
 
@@ skipping 17 matching lines @@
         compiledFunctions.forEach(recompile);
       }
       compiledFunctions.clear();
     }
   }
 
   addCompiledFunction(FunctionElement function) =>
       compiledFunctions.add(function);
 }
 
+class OptionalParameterTypes {
+  final List<SourceString> names;
+  final List<HType> types;
+
+  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];
+
+  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);
-  const HTypeList.allUnknown() : types = null;
+  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.fromInvocation(HInvoke node, HTypeMap types) {
+  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) {
         allUnknown = false;
         break;
       }
     }
     if (allUnknown) return HTypeList.ALL_UNKNOWN;
 
     HTypeList 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;
   }
 
+  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];
 
   HTypeList union(HTypeList other) {
     if (allUnknown) return this;
     if (other.allUnknown) return other;
     if (length != other.length) return HTypeList.ALL_UNKNOWN;
     bool onlyUnknown = true;
     HTypeList result = this;
     for (int i = 0; i < length; i++) {
@@ skipping 36 matching lines @@
         result.types.setRange(0, i, this.types);
       }
       if (result != this) {
         result.types[i] = newType;
       }
       if (result[i] != HType.UNKNOWN) onlyUnknown = false;
     }
     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";
 }
 
 class ArgumentTypesRegistry {
   final JavaScriptBackend backend;
   final Map<Element, HTypeList> staticTypeMap;
   final Set<Element> optimizedStaticFunctions;
   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>(),
         optimizedStaticFunctions = new Set<Element>(),
         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);
       if (newTypes === oldTypes) return;
       staticTypeMap[element] = newTypes;
       if (optimizedStaticFunctions.contains(element)) {
         backend.scheduleForRecompilation(element);
       }
     }
   }
@@ skipping 17 matching lines @@
     // TODO(sgjesse): These checks should use the codegenWorld and keep track
     // of changes to this information.
     Element element = node.element;
     Universe resolverWorld = compiler.resolverWorld;
     if (element != null &&
         (resolverWorld.hasFieldGetter(element, compiler) ||
             resolverWorld.hasInvokedGetter(element, compiler))) {
       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 {
       HTypeList oldTypes = selectorTypeMap[selector];
       HTypeList newTypes = oldTypes.unionWithInvoke(node, types);
       if (newTypes === oldTypes) return;
       selectorTypeMap[selector] = newTypes;
     }
 
     // If we're not compiling, we don't have to do anything.
     if (compiler.phase != Compiler.PHASE_COMPILING) return;
 
     // Run through all optimized functions and figure out if they need
     // to be recompiled because of this new invocation.
     optimizedFunctions.filterBySelector(selector).forEach((Element element) {
       // 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;
           }
         }
       }
       if (recompile) backend.scheduleForRecompilation(element);
     });
   }
 
-  HTypeList parameterTypes(element) {
+  HTypeList parameterTypes(FunctionElement element,
+                           OptionalParameterTypes defaultValueTypes) {
     // Handle static functions separately.
     if (Elements.isStaticOrTopLevelFunction(element)) {
       HTypeList types = staticTypeMap[element];
       if (types !== null) {
         if (!optimizedStaticFunctions.contains(element)) {
           optimizedStaticFunctions.add(element);
         }
         return types;
       } else {
         return HTypeList.ALL_UNKNOWN;
       }
     }
 
+
     // 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;
       }
     });
     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);
       } else {
         optimizedStaticFunctions.add(element);
       }
     }
 
     // TODO(kasperl): What kind of non-members do we get here?
     if (!element.isMember()) return;
 
     if (parameterTypes.allUnknown) {
       optimizedFunctions.remove(element);
       optimizedTypes.remove(element);
+      optimizedDefaultValueTypes.remove(element);
     } else {
       optimizedFunctions.add(element);
       optimizedTypes[element] = parameterTypes;
+      optimizedDefaultValueTypes[element] = defaultValueTypes;
     }
   }
 }
 
 class JavaScriptItemCompilationContext extends ItemCompilationContext {
   final HTypeMap types;
 
   JavaScriptItemCompilationContext() : types = new HTypeMap();
 }
 
@@ skipping 201 matching lines @@
    */
   void registerNonCallStaticUse(HStatic node) {
     argumentTypes.registerNonCallStaticUse(node);
   }
 
   /**
    * Retrieve the types of the parameters used for calling the [element]
    * 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) {
     ReturnInfo info = returnInfo[element];
     if (info != null) {
       info.update(returnType, scheduleForRecompilation);
     } else {
       returnInfo[element] = new ReturnInfo(returnType);
     }
   }
@@ skipping 47 matching lines @@
           return const SourceString('listSuperTypeCheck');
         }
       } else if (nativeCheck) {
         return const SourceString('callTypeCheck');
       } else {
         return const SourceString('propertyTypeCheck');
       }
     }
   }
 }