dart2js cps: Fix performance issues in optimization passes.

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

 // Copyright (c) 2014, 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.
 
 import 'optimizers.dart';
 
 import '../constants/constant_system.dart';
 import '../resolution/operators.dart';
 import '../constants/values.dart';
 import '../dart_types.dart' as types;
@@ skipping 537 matching lines @@
  */
 class TransformingVisitor extends LeafVisitor {
   final TypePropagationVisitor analyzer;
   final Map<Expression, ConstantValue> replacements;
   final ConstantPropagationLattice lattice;
   final dart2js.Compiler compiler;
 
   JavaScriptBackend get backend => compiler.backend;
   TypeMaskSystem get typeSystem => lattice.typeSystem;
   types.DartTypes get dartTypes => lattice.dartTypes;
-  Set<Node> get reachable => analyzer.reachableNodes;
   Map<Node, AbstractValue> get values => analyzer.values;
 
   final dart2js.InternalErrorFunction internalError;
 
   final List<Node> stack = <Node>[];
 
   TransformingVisitor(this.compiler,
                       this.lattice,
                       this.analyzer,
                       this.replacements,
@@ skipping 875 matching lines @@
       case AbstractBool.True:
         // Cast always succeeds, replace it with InvokeContinuation.
         InvokeContinuation invoke =
             new InvokeContinuation(cont, <Primitive>[node.value.definition]);
         replaceSubtree(node, invoke);
         push(invoke);
         return;
 
       case AbstractBool.False:
         // Cast always fails, remove unreachable continuation body.
-        assert(!reachable.contains(cont));
         replaceSubtree(cont.body, new Unreachable());
         break;
     }
   }
 
   /// Specialize calls to internal static methods.
   ///
   /// Returns true if the call was replaced.
   bool specializeInternalMethodCall(InvokeStatic node) {
     // TODO(asgerf): This is written to easily scale to more cases,
@@ skipping 161 matching lines @@
   // The node worklist stores nodes that are both reachable and need to be
   // processed, but have not been processed yet. Using a worklist avoids deep
   // recursion.
   // The node worklist and the reachable set operate in concert: nodes are
   // only ever added to the worklist when they have not yet been marked as
   // reachable, and adding a node to the worklist is always followed by marking
   // it reachable.
   // TODO(jgruber): Storing reachability per-edge instead of per-node would
   // allow for further optimizations.
   final List<Node> nodeWorklist = <Node>[];
-  final Set<Node> reachableNodes = new Set<Node>();
+  final Set<Continuation> reachableContinuations = new Set<Continuation>();
 
   // The definition workset stores all definitions which need to be reprocessed
   // since their lattice value has changed.
-  final Set<Definition> defWorkset = new Set<Definition>();
+  final List<Definition> defWorklist = <Definition>[];
 
   final ConstantPropagationLattice lattice;
   final dart2js.InternalErrorFunction internalError;
 
   TypeMaskSystem get typeSystem => lattice.typeSystem;
 
   AbstractValue get nothing => lattice.nothing;
 
   AbstractValue nonConstant([TypeMask type]) => lattice.nonConstant(type);
 
   AbstractValue constantValue(ConstantValue constant, [TypeMask type]) {
     return lattice.constant(constant, type);
   }
 
   // Stores the current lattice value for primitives and mutable variables.
   // Access through [getValue] and [setValue].
   final Map<Definition, AbstractValue> values;
 
   /// Expressions that invoke their call continuation with a constant value
   /// and without any side effects. These can be replaced by the constant.
   final Map<Expression, ConstantValue> replacements;
 
   TypePropagationVisitor(this.lattice,
                          this.values,
                          this.replacements,
                          this.internalError);
 
   void analyze(FunctionDefinition root) {
-    reachableNodes.clear();
+    reachableContinuations.clear();
 
     // Initially, only the root node is reachable.
-    setReachable(root);
+    push(root);
 
     iterateWorklist();
   }
 
   void reanalyzeSubtree(Node node) {
-    new ResetAnalysisInfo(reachableNodes, values).visit(node);
-    setReachable(node);
+    new ResetAnalysisInfo(reachableContinuations, values).visit(node);
+    push(node);
     iterateWorklist();
   }
 
   void iterateWorklist() {
     while (true) {
       if (nodeWorklist.isNotEmpty) {
         // Process a new reachable expression.
         Node node = nodeWorklist.removeLast();
         visit(node);
-      } else if (defWorkset.isNotEmpty) {
+      } else if (defWorklist.isNotEmpty) {
         // Process all usages of a changed definition.
-        Definition def = defWorkset.first;
-        defWorkset.remove(def);
+        Definition def = defWorklist.removeLast();
 
         // Visit all uses of this definition. This might add new entries to
         // [nodeWorklist], for example by visiting a newly-constant usage within
         // a branch node.
         for (Reference ref = def.firstRef; ref != null; ref = ref.next) {
           visit(ref.parent);
         }
       } else {
         break;  // Both worklists empty.
       }
     }
   }
 
+  /// Adds [node] to the worklist.
+  void push(Node node) {
+    nodeWorklist.add(node);
+  }
+
   /// If the passed node is not yet reachable, mark it reachable and add it
   /// to the work list.
-  void setReachable(Node node) {
-    if (!reachableNodes.contains(node)) {
-      reachableNodes.add(node);
-      nodeWorklist.add(node);
+  void setReachable(Continuation cont) {
+    if (reachableContinuations.add(cont)) {
+      push(cont);
     }
   }
 
   /// Returns the lattice value corresponding to [node], defaulting to nothing.
   ///
   /// Never returns null.
   AbstractValue getValue(Definition node) {
     AbstractValue value = values[node];
     return (value == null) ? nothing : value;
   }
 
   /// Joins the passed lattice [updateValue] to the current value of [node],
   /// and adds it to the definition work set if it has changed and [node] is
   /// a definition.
   void setValue(Definition node, AbstractValue updateValue) {
     AbstractValue oldValue = getValue(node);
     AbstractValue newValue = lattice.join(oldValue, updateValue);
     if (oldValue == newValue) {
       return;
     }
 
     // Values may only move in the direction NOTHING -> CONSTANT -> NONCONST.
     assert(newValue.kind >= oldValue.kind);
 
     values[node] = newValue;
-    defWorkset.add(node);
+    defWorklist.add(node);
   }
 
   // -------------------------- Visitor overrides ------------------------------
   void visit(Node node) { node.accept(this); }
 
   void visitFunctionDefinition(FunctionDefinition node) {
     if (node.thisParameter != null) {
       setValue(node.thisParameter,
                nonConstant(typeSystem.getReceiverType(node.element)));
     }
     node.parameters.forEach(visit);
-    setReachable(node.body);
+    push(node.body);
   }
 
   void visitLetPrim(LetPrim node) {
     visit(node.primitive); // No reason to delay visits to primitives.
-    setReachable(node.body);
+    push(node.body);
   }
 
   void visitLetCont(LetCont node) {
     // The continuation is only marked as reachable on use.
-    setReachable(node.body);
+    push(node.body);
   }
 
   void visitLetHandler(LetHandler node) {
-    setReachable(node.body);
+    push(node.body);
     // The handler is assumed to be reachable (we could instead treat it as
     // unreachable unless we find something reachable that might throw in the
     // body --- it's not clear if we want to do that here or in some other
     // pass).  The handler parameters are assumed to be unknown.
     //
     // TODO(kmillikin): we should set the type of the exception and stack
     // trace here.  The way we do that depends on how we handle 'on T' catch
     // clauses.
     setReachable(node.handler);
     for (Parameter param in node.handler.parameters) {
       setValue(param, nonConstant());
     }
   }
 
   void visitLetMutable(LetMutable node) {
     setValue(node.variable, getValue(node.value.definition));
-    setReachable(node.body);
+    push(node.body);
   }
 
   void visitInvokeStatic(InvokeStatic node) {
     Continuation cont = node.continuation.definition;
     setReachable(cont);
 
     assert(cont.parameters.length == 1);
     Parameter returnValue = cont.parameters[0];
 
     /// Sets the value of the target continuation parameter, and possibly
@@ skipping 295 matching lines @@
     ConstantValue value = node.value;
     if (value.isDummy || !value.isConstant) {
       // TODO(asgerf): Explain how this happens and why we don't want them.
       setValue(node, nonConstant(typeSystem.getTypeOf(value)));
     } else {
       setValue(node, constantValue(value, typeSystem.getTypeOf(value)));
     }
   }
 
   void visitCreateFunction(CreateFunction node) {
-    setReachable(node.definition);
-    ConstantValue constant =
-        new FunctionConstantValue(node.definition.element);
-    setValue(node, constantValue(constant, typeSystem.functionType));
+    throw 'CreateFunction is not used';
   }
 
   void visitGetMutable(GetMutable node) {
     setValue(node, getValue(node.variable.definition));
   }
 
   void visitMutableVariable(MutableVariable node) {
     // [MutableVariable]s are bound either as parameters to
     // [FunctionDefinition]s, by [LetMutable].
     if (node.parent is FunctionDefinition) {
@@ skipping 26 matching lines @@
       // some other abstract value than non-constant.
     } else {
       internalError(node.hint, "Unexpected parent of Parameter: ${node.parent}");
     }
   }
 
   void visitContinuation(Continuation node) {
     node.parameters.forEach(visit);
 
     if (node.body != null) {
-      setReachable(node.body);
+      push(node.body);
     }
   }
 
   void visitGetStatic(GetStatic node) {
     if (node.element.isFunction) {
       setValue(node, nonConstant(typeSystem.functionType));
     } else {
       setValue(node, nonConstant(typeSystem.getFieldType(node.element)));
     }
   }
 
   void visitSetStatic(SetStatic node) {}
 
   void visitGetLazyStatic(GetLazyStatic node) {
     Continuation cont = node.continuation.definition;
     setReachable(cont);
 
     assert(cont.parameters.length == 1);
     Parameter returnValue = cont.parameters[0];
     setValue(returnValue, nonConstant(typeSystem.getFieldType(node.element)));
   }
 
   void visitIsTrue(IsTrue node) {
     Branch branch = node.parent;
     visitBranch(branch);
   }
 
   void visitInterceptor(Interceptor node) {
-    setReachable(node.input.definition);
+    push(node.input.definition);
     AbstractValue value = getValue(node.input.definition);
     if (!value.isNothing) {
       setValue(node, nonConstant(typeSystem.nonNullType));
     }
   }
 
   void visitGetField(GetField node) {
     setValue(node, nonConstant(typeSystem.getFieldType(node.field)));
   }
 
@@ skipping 142 matching lines @@
   String get name => 'current';
 }
 
 /// Suggested name for the original length of a list, for use in checks
 /// for concurrent modification.
 class OriginalLengthEntity extends Entity {
   String get name => 'length';
 }
 
 class ResetAnalysisInfo extends RecursiveVisitor {
-  Set<Node> reachableNodes;
+  Set<Continuation> reachableContinuations;
   Map<Definition, AbstractValue> values;
 
-  ResetAnalysisInfo(this.reachableNodes, this.values);
+  ResetAnalysisInfo(this.reachableContinuations, this.values);
 
-  visit(Node node) {
-    reachableNodes.remove(node);
-    if (node is Definition) values.remove(node);
-    node.accept(this);
+  processContinuation(Continuation cont) {
+    reachableContinuations.remove(cont);
+    cont.parameters.forEach(values.remove);
+  }
+
+  processLetPrim(LetPrim node) {
+    values.remove(node.primitive);
+  }
+
+  processLetMutable(LetMutable node) {
+    values.remove(node.variable);
   }
 }