Change the type inference for fields in dart2js

lib/compiler/implementation/ssa/optimize.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.
 
 abstract class OptimizationPhase {
   String get name;
   void visitGraph(HGraph graph);
 }
 
 class SsaOptimizerTask extends CompilerTask {
@@ skipping 29 matching lines @@
           new SsaCheckInserter(backend, types, context.boundsChecked),
           new SsaConstantFolder(constantSystem, backend, work, types),
           new SsaRedundantPhiEliminator(),
           new SsaDeadPhiEliminator(),
           new SsaGlobalValueNumberer(compiler, types),
           new SsaCodeMotion(),
           // Previous optimizations may have generated new
           // opportunities for constant folding.
           new SsaConstantFolder(constantSystem, backend, work, types),
           new SsaDeadCodeEliminator(types),
-          new SsaRegisterRecompilationCandidates(backend, work, types)];
+          new SsaConstructionFieldTypes(backend, work, types)];

[ngeoffray, 2012/09/24 08:15:49]

This will also be run by the speculative optimization. Please fix it or
otherwise we could start optimizing on speculative types (I think you check for
it in the optimization phase, but it's very error prone). 

[Søren Gjesse, 2012/09/24 15:06:50]

Done.

       runPhases(graph, phases);
     });
   }
 
   bool trySpeculativeOptimizations(WorkItem work, HGraph graph) {
     if (work.element.isField()) {
       // Lazy initializers may not have bailout methods.
       return false;
     }
     JavaScriptItemCompilationContext context = work.compilationContext;
     HTypeMap types = context.types;
     return measure(() {
       // Run the phases that will generate type guards.
       List<OptimizationPhase> phases = <OptimizationPhase>[
-          new SsaRecompilationFieldTypePropagator(backend, work, types),
           new SsaSpeculativeTypePropagator(compiler, types),
           new SsaTypeGuardInserter(compiler, work, types),
           new SsaEnvironmentBuilder(compiler),
           // Change the propagated types back to what they were before we
           // speculatively propagated, so that we can generate the bailout
           // version.
           // Note that we do this even if there were no guards inserted. If a
           // guard is not beneficial enough we don't emit one, but there might
           // still be speculative types on the instructions.
           new SsaTypePropagator(compiler, types),
@@ skipping 529 matching lines @@
     Modifiers modifiers = field.modifiers;
     bool isFinalOrConst = false;
     if (modifiers != null) {
       isFinalOrConst = modifiers.isFinal() || modifiers.isConst();
     }
     if (!compiler.resolverWorld.hasInvokedSetter(field, compiler)) {
       // If no setter is ever used for this field it is only initialized in the
       // initializer list.
       isFinalOrConst = true;
     }
-    if (!isFinalOrConst &&
-        !compiler.codegenWorld.hasInvokedSetter(field, compiler) &&
-        !compiler.codegenWorld.hasFieldSetter(field, compiler)) {
-      switch (compiler.phase) {
-        case Compiler.PHASE_COMPILING:
-          compiler.enqueuer.codegen.registerRecompilationCandidate(
-              work.element);
-          break;
-        case Compiler.PHASE_RECOMPILING:
-          // If field is not final or const but no setters are used then the
-          // field might be considered final anyway as it will be either
-          // un-initialized or initialized in the constructor initializer list.
-          isFinalOrConst = true;
-          break;
+    HFieldGet result = new HFieldGet(
+        field, node.inputs[0], isAssignable: !isFinalOrConst);
+    if (work.element.isMember()) {

[ngeoffray, 2012/09/24 08:15:49]

Why this check?

[Søren Gjesse, 2012/09/24 15:06:50]

Because I did not add support for static or top level functions in the field
types registry. This has now been added and this check removed.

+      HType type = backend.optimisticFieldType(field);
+      if (type != null) {
+        result.guaranteedType = type;
+        backend.registerFieldTypesOptimization(
+            work.element, field, result.guaranteedType);
       }
     }
-    return new HFieldGet(field, node.inputs[0], isAssignable: !isFinalOrConst);
+    return result;
   }
 
   HInstruction visitInvokeDynamicSetter(HInvokeDynamicSetter node) {
     Element field =
         findConcreteFieldForDynamicAccess(node.receiver, node.selector);
     if (field === null) return node;
     HInstruction value = node.inputs[1];
     if (compiler.enableTypeAssertions) {
       HInstruction other = value.convertType(
           compiler, field, HTypeConversion.CHECKED_MODE_CHECK);
@@ skipping 571 matching lines @@
 
     for (HIf ifUser in notIfUsers) {
       changeUsesDominatedBy(ifUser.elseBlock, input, convertedType);
       // TODO(ngeoffray): Also change uses for the then block on a HType
       // that knows it is not of a specific Type.
     }
   }
 }
 
 
-// Base class for the handling of recompilation based on inferred
-// field types.
-class BaseRecompilationVisitor extends HBaseVisitor {
+// Analyze the constructors to see if some fields will always have a specific
+// type after construction. If this is the case we can ignore the type given
+// by the field initializer. This is especially useful when the field
+// initializer is initializing the field to null.
+class SsaConstructionFieldTypes
+    extends HBaseVisitor implements OptimizationPhase {
   final JavaScriptBackend backend;
   final WorkItem work;
   final HTypeMap types;
-  Compiler get compiler => backend.compiler;
+  final String name = "SsaConstructionFieldTypes";
+  final Set<Element> allSetters;
+  final Map<HBasicBlock, Map<Element, HType>> blockFieldSetters;
+  bool thisExposed = false;
+  HGraph currentGraph;
+  Map<Element, HType> currentFieldSetters;
 
-  BaseRecompilationVisitor(this.backend, this.work, this.types);
+  SsaConstructionFieldTypes(JavaScriptBackend this.backend,
+         WorkItem this.work,
+         HTypeMap this.types)
+      : allSetters = new Set<Element>(),
+        blockFieldSetters = new Map<HBasicBlock, Map<Element, HType>>();
 
-  abstract void handleFieldGet(HFieldGet node, HType type);
-  abstract void handleFieldNumberOperation(HFieldGet field, HType type);
+  void visitGraph(HGraph graph) {
+    currentGraph = graph;
+    if (!work.element.isGenerativeConstructorBody() &&
+        !work.element.isGenerativeConstructor()) return;
+    visitDominatorTree(graph);
+  }
 
-  // Checks if the binary invocation operates on a field and a
-  // constant number. If it does [handleFieldNumberOperation] is
-  // called with the field and the type inferred for the field so far.
-  void checkFieldNumberOperation(HInvokeBinary node) {
-    // Determine if one of the operands is an HFieldGet.
-    HFieldGet field;
-    HInstruction other;
-    if (node.left is HFieldGet) {
-      field = node.left;
-      other = node.right;
-    } else if (node.right is HFieldGet) {
-      field = node.right;
-      other = node.left;
+  visitBasicBlock(HBasicBlock block) {
+    if (block.predecessors.length == 0) {
+      // Create a new empty map for the first block.
+      currentFieldSetters = new Map<Element, HType>();
+    } else {
+      // Build a map which unions the fields from all predecessors.

[ngeoffray, 2012/09/24 08:15:49]

It's a union of the types but an intersection of the fields.

[Søren Gjesse, 2012/09/24 15:06:50]

Updated comments.

+      currentFieldSetters =
+          new Map.from(blockFieldSetters[block.predecessors[0]]);
+      // Loop headers are the only nodes with back edges.

[ngeoffray, 2012/09/24 08:15:49]

Please also assert that they only have 2 predecessors.

[Søren Gjesse, 2012/09/24 15:06:50]

Done.

+      if (!block.isLoopHeader()) {
+        for (int i = 1; i < block.predecessors.length; i++) {
+          Map<Element, HType> predecessorsFieldSetters =
+              blockFieldSetters[block.predecessors[i]];
+          Map<Element, HType> newFieldSetters = new Map<Element, HType>();
+          predecessorsFieldSetters.forEach((Element element, HType type) {
+            HType currentType = currentFieldSetters[element];
+            if (currentType != null) {
+              newFieldSetters[element] = currentType.union(type);
+            } else {
+              newFieldSetters[element] = type;
+            }
+          });
+          currentFieldSetters = newFieldSetters;
+        }
+      }
     }
-    // Try to optimize the case where a field which is known to always
-    // be an integer is compared with a constant number.
-    if (other != null &&
-        other.isConstantNumber() &&
-        field.element != null &&
-        field.element.isMember()) {
-      // Calculate the field type from the information available.  If
-      // we have type information for the field and it contains NUMBER
-      // we use it as a candidate for recompilation.
-      Element fieldElement = field.element;
-      HType fieldSettersType = backend.fieldSettersTypeSoFar(fieldElement);
-      HType initializersType = backend.typeFromInitializersSoFar(fieldElement);
-      HType fieldType = fieldSettersType.union(initializersType);
-      HType type = HType.NUMBER.union(fieldType);
-      if (type == HType.NUMBER) {
-        handleFieldNumberOperation(field, fieldType);
-      }
+    block.forEachInstruction(
+        (HInstruction instruction) => instruction.accept(this));
+    assert(currentFieldSetters != null);
+    blockFieldSetters[block] = currentFieldSetters;
+  }
+
+  visitInstruction(HInstruction instruction) {
+    // Instruction not explicitly handled keeps the current inferred types.

[ngeoffray, 2012/09/24 08:15:49]

Kasper suggested to do the other way around and have a white-list of
instructions instead, and I agree it feels safer. So I'd prefer if you'd check
that instruction uses 'this' and mark thisExposed if yes. You could construct a
set of all users of this before visiting the graph, and the check would be
cheap.

[Søren Gjesse, 2012/09/24 15:06:50]

Done.

+  }
+
+  visitForeignNew(HForeignNew node) {
+    // The HForeignNew instruction is used in the generative constructor to
+    // initialize all fields in newly created objects. The fields are
+    // initialized to the value present in the initializer list or set to null
+    // if not otherwise initialized.
+    int j = 0;
+    node.element.forEachInstanceField(
+      includeBackendMembers: true,
+      includeSuperMembers: true,
+      f: (ClassElement enclosingClass, Element element) {
+        backend.registerFieldInitializer(element, types[node.inputs[j]]);
+        j++;
+      });
+  }
+
+  visitInvoke(HInvoke node) {
+    for (int i = 0; i < node.inputs.length && !thisExposed; i++) {
+      if (node.inputs[i] is HThis) thisExposed = true;
     }
   }
 
-  void visitFieldGet(HFieldGet node) {
-    if (!node.element.isInstanceMember()) return;
+  visitFieldSet(HFieldSet node) {
     Element field = node.element;
-    if (field != null) {
-      HType type = backend.optimisticFieldTypeAfterConstruction(field);
-      if (!type.isUnknown()) {
-        // Allow handling even if we haven't seen any types for this
-        // field yet. There might still be only one setter in an
-        // initializer list or constructor body and recompilation
-        // can therefore pay off.
-        handleFieldGet(node, type);
-      }
+    assert(field.isMember());

[ngeoffray, 2012/09/24 08:15:49]

Why this assert? 

[Søren Gjesse, 2012/09/24 15:06:50]

Good question - removed.

+    HInstruction value = node.value;
+    HType type = types[value];
+    allSetters.add(field);
+    if (work.element.getEnclosingClass() === field.getEnclosingClass() &&
+        value.hasGuaranteedType()) {
+      currentFieldSetters[field] = type;
     }
   }
 
-  HInstruction visitEquals(HEquals node) {
-    checkFieldNumberOperation(node);
-  }
+  visitExit(HExit node) {
+    // If this has been exposed then we cannot say anything about types after
+    // construction.
+    if (thisExposed) return;
 
-  HInstruction visitBinaryArithmetic(HBinaryArithmetic node) {
-    checkFieldNumberOperation(node);
+    // Register the known field types.
+    currentFieldSetters.forEach((Element element, HType type) {
+      backend.registerFieldConstructor(element, type);
+      allSetters.remove(element);
+    });
+    allSetters.forEach((Element element) {
+      backend.registerFieldConstructor(element, HType.UNKNOWN);

[ngeoffray, 2012/09/24 08:15:49]

Why do you have to say they're unknown?

[Søren Gjesse, 2012/09/24 15:06:50]

Because I just know that these fields have been set to something somewhere in
the constructor, but not on all control patch. Ideally this should be unioned
with the field initializer type for this field, but then we should have a flag
here to indicate that the field might be set in the constructor together with
the type.

+    });
   }
 }
-
-
-// Visitor that registers candidates for recompilation.
-class SsaRegisterRecompilationCandidates
-    extends BaseRecompilationVisitor implements OptimizationPhase {
-  final String name = "SsaRegisterRecompileCandidates";
-  HGraph graph;
-
-  SsaRegisterRecompilationCandidates(JavaScriptBackend backend,
-                                     WorkItem work,
-                                     HTypeMap types)
-      : super(backend, work, types);
-
-  void visitGraph(HGraph visitee) {
-    graph = visitee;
-    if (compiler.phase == Compiler.PHASE_COMPILING) {
-      visitDominatorTree(visitee);
-    }
-  }
-
-  void handleFieldGet(HFieldGet node, HType type) {
-    assert(compiler.phase == Compiler.PHASE_COMPILING);
-    compiler.enqueuer.codegen.registerRecompilationCandidate(
-        work.element);
-  }
-
-  void handleFieldNumberOperation(HFieldGet node, HType type) {
-    assert(compiler.phase == Compiler.PHASE_COMPILING);
-    compiler.enqueuer.codegen.registerRecompilationCandidate(
-        work.element);
-  }
-}
-
-
-// Visitor that sets the known or suspected type of fields during
-// recompilation.
-class SsaRecompilationFieldTypePropagator
-    extends BaseRecompilationVisitor implements OptimizationPhase {
-  final String name = "SsaRecompilationFieldTypePropagator";
-  HGraph graph;
-
-  SsaRecompilationFieldTypePropagator(JavaScriptBackend backend,
-                                      WorkItem work,
-                                      HTypeMap types)
-      : super(backend, work, types);
-
-  void visitGraph(HGraph visitee) {
-    graph = visitee;
-    if (compiler.phase == Compiler.PHASE_RECOMPILING) {
-      visitDominatorTree(visitee);
-    }
-  }
-
-  void handleFieldGet(HFieldGet field, HType type) {
-    assert(compiler.phase == Compiler.PHASE_RECOMPILING);
-    if (!type.isConflicting()) {
-      // If there are no invoked setters with this name, the union of
-      // the types of the initializers and the setters is guaranteed
-      // otherwise it is only speculative.
-      Element element = field.element;
-      assert(!element.isGenerativeConstructorBody());
-      if (!compiler.codegenWorld.hasInvokedSetter(element, compiler)) {
-        field.guaranteedType =
-            type.union(backend.fieldSettersTypeSoFar(element));
-      } else {
-        types[field] = type.union(backend.fieldSettersTypeSoFar(element));
-      }
-    }
-  }
-
-  void handleFieldNumberOperation(HFieldGet field, HType type) {
-    assert(compiler.phase == Compiler.PHASE_RECOMPILING);
-    if (compiler.codegenWorld.hasInvokedSetter(field.element, compiler)) {
-      // If there are invoked setters we don't know for sure
-      // that the field will hold a value of the calculated
-      // type, but the fact that the class itself sticks to
-      // this type for the field is still a strong signal
-      // indicating the expected type of the field.
-      types[field] = type;
-    } else {
-      // If there are no invoked setters we know the type of
-      // this field for sure.
-      field.guaranteedType = type;
-    }
-  }
-}