dart2js cps: Maintain parent pointers instead of recomputing them.

pkg/compiler/lib/src/cps_ir/shrinking_reductions.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.
 
 library dart2js.cps_ir.shrinking_reductions;
 
 import 'cps_ir_nodes.dart';
 import 'optimizers.dart';
 
 /**
  * [ShrinkingReducer] applies shrinking reductions to CPS terms as described
  * in 'Compiling with Continuations, Continued' by Andrew Kennedy.
  */
 class ShrinkingReducer extends Pass {
   String get passName => 'Shrinking reductions';
 
   List<_ReductionTask> _worklist;
 
   static final _DeletedNode _DELETED = new _DeletedNode();
 
   /// Applies shrinking reductions to root, mutating root in the process.
   @override
   void rewrite(FunctionDefinition root) {
     _worklist = new List<_ReductionTask>();
     _RedexVisitor redexVisitor = new _RedexVisitor(_worklist);
 
-    // Set all parent pointers.
-    new ParentVisitor().visit(root);
-
     // Sweep over the term, collecting redexes into the worklist.
     redexVisitor.visit(root);
 
     // Process the worklist.
     while (_worklist.isNotEmpty) {
       _ReductionTask task = _worklist.removeLast();
       _processTask(task);
     }
   }
 
   /// Removes the given node from the CPS graph, replacing it with its body
   /// and marking it as deleted. The node's parent must be a [[InteriorNode]].
   void _removeNode(InteriorNode node) {
     Node body           = node.body;
     InteriorNode parent = node.parent;
     assert(parent.body == node);
 
     body.parent = parent;
     parent.body = body;
     node.parent = _DELETED;
   }
 
   /// Remove a given continuation from the CPS graph.  The LetCont itself is
   /// removed if the given continuation is the only binding.
   void _removeContinuation(Continuation cont) {
     LetCont parent = cont.parent;
     if (parent.continuations.length == 1) {
-      assert(cont.parent_index == 0);
       _removeNode(parent);
     } else {
-      List<Continuation> continuations = parent.continuations;
-      for (int i = cont.parent_index; i < continuations.length - 1; ++i) {
-        Continuation current = continuations[i + 1];
-        continuations[i] = current;
-        current.parent_index = i;
-      }
-      continuations.removeLast();

[asgerf, 2015/10/01 10:54:46]

The array shift kind of defeats the purpose of the parent index. Or at least,
the performance issue it tries to fix is still there.

This could also be fixed by moving the last continuation into the free slot,
assuming it's ok to change the order.

But performance-wise not much has changed anyway, so I'd rather just revisit
later if it becomes an issue.

+      parent.continuations.remove(cont);
     }
     cont.parent = _DELETED;
   }
 
   void _processTask(_ReductionTask task) {
     // Skip tasks for deleted nodes.
     if (task.node.parent == _DELETED) {
       return;
     }
 
@@ skipping 120 matching lines @@
     // let cont k0(v0) = /* v0 is not used */ in
     //   call foo () k0
     //
     // Where the dead parameter reduction is no longer valid because we do not
     // allow removing the paramter of call continuations.  We disallow such eta
     // reductions in [_isEtaCont].
     assert(_isDeadParameter(task.node));
 
     Parameter parameter = task.node;
     Continuation continuation = parameter.parent;
-    int index = parameter.parentIndex;
+    int index = continuation.parameters.indexOf(parameter);
+    assert(index != -1);
 
     // Remove the index'th argument from each invocation.
     Reference<Continuation> current = continuation.firstRef;
     while (current != null) {
       InvokeContinuation invoke = current.parent;
       Reference<Primitive> argument = invoke.arguments[index];
       argument.unlink();
       // Removing an argument can create a dead parameter or dead value redex.
       if (argument.definition is Parameter) {
         if (_isDeadParameter(argument.definition)) {
           _worklist.add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER,
                                            argument.definition));
         }
       } else {
         Node parent = argument.definition.parent;
         if (parent is LetPrim) {
           if (_isDeadVal(parent)) {
             _worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, parent));
           }
         }
       }
       invoke.arguments.removeAt(index);
       current = current.next;
     }
-    // Copy the parameters above index down.
-    List<Parameter> parameters = continuation.parameters;
-    for (int i = index; i < parameters.length - 1; ++i) {
-      Parameter p = parameters[i + 1];
-      parameters[i] = p;
-      p.parentIndex = i;
-    }
-    parameters.removeLast();

[asgerf, 2015/10/01 10:54:46]

Same as above.

+    continuation.parameters.removeAt(index);
 
     // Removing an unused parameter can create an eta-redex.
     if (_isEtaCont(continuation)) {
       _worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, continuation));
     }
   }
 }
 
 /// Returns true iff the bound primitive is unused, and has no effects
 /// preventing it from being eliminated.
@@ skipping 141 matching lines @@
   while (current != null) {
     if (current.parent is! InvokeContinuation) return false;
     InvokeContinuation invoke = current.parent;
     if (invoke.continuation.definition != continuation) return false;
     current = current.next;
   }
   return true;
 }
 
 /// Traverses a term and adds any found redexes to the worklist.
-class _RedexVisitor extends RecursiveVisitor {
+class _RedexVisitor extends TrampolineRecursiveVisitor {
   final List<_ReductionTask> worklist;
 
   _RedexVisitor(this.worklist);
 
   void processLetPrim(LetPrim node) {
     if (_isDeadVal(node)) {
       worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, node));
     }
   }
 
@@ skipping 25 matching lines @@
     }
   }
 }
 
 /// Traverses a deleted CPS term, marking nodes that might participate in a
 /// redex as deleted and adding newly created redexes to the worklist.
 ///
 /// Deleted nodes that might participate in a reduction task are marked so that
 /// any corresponding tasks can be skipped.  Nodes are marked so by setting
 /// their parent to the deleted sentinel.
-class _RemovalVisitor extends RecursiveVisitor {
+class _RemovalVisitor extends TrampolineRecursiveVisitor {
   final List<_ReductionTask> worklist;
 
   _RemovalVisitor(this.worklist);
 
   void processLetPrim(LetPrim node) {
     node.parent = ShrinkingReducer._DELETED;
   }
 
   void processContinuation(Continuation node) {
     node.parent = ShrinkingReducer._DELETED;
@@ skipping 25 matching lines @@
         if (_isDeadCont(cont)) {
           worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, cont));
         } else if (_isBetaContLin(cont)) {
           worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, cont));
         }
       }
     }
   }
 }
 
-/// Traverses the CPS term and sets node.parent for each visited node.
-class ParentVisitor extends RecursiveVisitor {
-  processFunctionDefinition(FunctionDefinition node) {
-    node.body.parent = node;
-    if (node.thisParameter != null) node.thisParameter.parent = node;
-    int index = 0;
-    node.parameters.forEach((Definition parameter) {
-      parameter.parent = node;
-      if (parameter is Parameter) parameter.parentIndex = index++;
-    });
-    node.returnContinuation.parent = node;
-    node.body.parent = node;
-  }
 
-  processLetPrim(LetPrim node) {
-    node.primitive.parent = node;
-    node.body.parent = node;
-  }
-
-  processLetCont(LetCont node) {
-    int index = 0;
-    node.continuations.forEach((Continuation continuation) {
-      continuation.parent = node;
-      continuation.parent_index = index++;
-    });
-    node.body.parent = node;
-  }
-
-  processLetHandler(LetHandler node) {
-    node.handler.parent = node;
-    node.body.parent = node;
-  }
-
-  processLetMutable(LetMutable node) {
-    node.variable.parent = node;
-    node.value.parent = node;
-    node.body.parent = node;
-  }
-
-  processInvokeStatic(InvokeStatic node) {
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-    node.continuation.parent = node;
-  }
-
-  processInvokeContinuation(InvokeContinuation node) {
-    node.continuation.parent = node;
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processInvokeMethod(InvokeMethod node) {
-    node.receiver.parent = node;
-    node.continuation.parent = node;
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processInvokeMethodDirectly(InvokeMethodDirectly node) {
-    node.receiver.parent = node;
-    node.continuation.parent = node;
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processInvokeConstructor(InvokeConstructor node) {
-    node.continuation.parent = node;
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processBranch(Branch node) {
-    node.condition.parent = node;
-    node.trueContinuation.parent = node;
-    node.falseContinuation.parent = node;
-  }
-
-  processTypeCast(TypeCast node) {
-    node.typeArguments.forEach((Reference ref) => ref.parent = node);
-    node.continuation.parent = node;
-    node.value.parent = node;
-  }
-
-  processTypeTest(TypeTest node) {
-    node.typeArguments.forEach((Reference ref) => ref.parent = node);
-    node.value.parent = node;
-  }
-
-  processSetMutable(SetMutable node) {
-    node.variable.parent = node;
-    node.value.parent = node;
-  }
-
-  processThrow(Throw node) {
-    node.value.parent = node;
-  }
-
-  processGetLazyStatic(GetLazyStatic node) {
-    node.continuation.parent = node;
-  }
-
-  processLiteralList(LiteralList node) {
-    node.values.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processLiteralMap(LiteralMap node) {
-    node.entries.forEach((LiteralMapEntry entry) {
-      entry.key.parent = node;
-      entry.value.parent = node;
-    });
-  }
-
-  processCreateFunction(CreateFunction node) {
-    node.definition.parent = node;
-  }
-
-  processContinuation(Continuation node) {
-    if (node.body != null) node.body.parent = node;
-    int index = 0;
-    node.parameters.forEach((Parameter parameter) {
-      parameter.parent = node;
-      parameter.parentIndex = index++;
-    });
-  }
-
-  processInterceptor(Interceptor node) {
-    node.input.parent = node;
-  }
-
-  processSetField(SetField node) {
-    node.object.parent = node;
-    node.value.parent = node;
-  }
-
-  processGetField(GetField node) {
-    node.object.parent = node;
-  }
-
-  processGetStatic(GetStatic node) {
-  }
-
-  processSetStatic(SetStatic node) {
-    node.value.parent = node;
-  }
-
-  processGetMutable(GetMutable node) {
-    node.variable.parent = node;
-  }
-
-  processCreateInstance(CreateInstance node) {
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-    node.typeInformation.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processCreateBox(CreateBox node) {
-  }
-
-  processReifyRuntimeType(ReifyRuntimeType node) {
-    node.value.parent = node;
-  }
-
-  processReadTypeVariable(ReadTypeVariable node) {
-    node.target.parent = node;
-  }
-
-  processTypeExpression(TypeExpression node) {
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processCreateInvocationMirror(CreateInvocationMirror node) {
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processApplyBuiltinOperator(ApplyBuiltinOperator node) {
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processApplyBuiltinMethod(ApplyBuiltinMethod node) {
-    node.receiver.parent = node;
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processForeignCode(ForeignCode node) {
-    if (node.continuation != null) {
-      node.continuation.parent = node;
-    }
-    node.arguments.forEach((Reference ref) => ref.parent = node);
-  }
-
-  processGetLength(GetLength node) {
-    node.object.parent = node;
-  }
-
-  processGetIndex(GetIndex node) {
-    node.object.parent = node;
-    node.index.parent = node;
-  }
-
-  processSetIndex(SetIndex node) {
-    node.object.parent = node;
-    node.index.parent = node;
-    node.value.parent = node;
-  }
-
-  processAwait(Await node) {
-    node.continuation.parent = node;
-    node.input.parent = node;
-  }
-
-  processRefinement(Refinement node) {
-    node.value.parent = node;
-  }
-
-  processYield(Yield node) {
-    node.continuation.parent = node;
-    node.input.parent = node;
-  }
-}
 
 class _ReductionKind {
   final String name;
   final int hashCode;
 
   const _ReductionKind(this.name, this.hashCode);
 
   static const _ReductionKind DEAD_VAL = const _ReductionKind('dead-val', 0);
   static const _ReductionKind DEAD_CONT = const _ReductionKind('dead-cont', 1);
   static const _ReductionKind BETA_CONT_LIN =
@@ skipping 23 matching lines @@
   bool operator==(_ReductionTask that) {
     return (that.kind == this.kind && that.node == this.node);
   }
 
   String toString() => "$kind: $node";
 }
 
 /// A dummy class used solely to mark nodes as deleted once they are removed
 /// from a term.
 class _DeletedNode extends Node {
-  accept(_) => null;
+  accept(_) {}
+  setParentPointers() {}
 }