Improve null-check elimination and change backward traversal strategy.

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

 // Copyright (c) 2013, 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.ir_nodes;
 
 import 'dart:collection';
 import 'cps_fragment.dart' show CpsFragment;
 import '../constants/values.dart' as values;
 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
 import '../elements/elements.dart';
@@ skipping 46 matching lines @@
 abstract class Expression extends Node {
   InteriorNode get parent; // Only InteriorNodes may contain expressions.
 
   Expression plug(Expression expr) => throw 'impossible';
 
   /// The next expression in the basic block.
   ///
   /// For [InteriorExpression]s this is the body, for [CallExpressions] it is
   /// the body of the continuation, and for [TailExpressions] it is `null`.
   Expression get next;
+
+  accept(BlockVisitor visitor);
 }
 
 /// Represents a node with a child node, which can be accessed through the
 /// `body` member. A typical usage is when removing a node from the CPS graph:
 ///
 ///     Node child          = node.body;
 ///     InteriorNode parent = node.parent;
 ///
 ///     child.parent = parent;
 ///     parent.body  = child;
 abstract class InteriorNode extends Node {
   Expression get body;
   void set body(Expression body);
+
+  accept(BlockVisitor visitor);
 }
 
 /// An expression that creates new bindings and continues evaluation in
 /// a subexpression.
 ///
 /// The interior expressions are [LetPrim], [LetCont], [LetHandler], and
 /// [LetMutable].
 abstract class InteriorExpression extends Expression implements InteriorNode {
   Expression get next => body;
 
@@ skipping 273 matching lines @@
   Primitive primitive;
   Expression body;
 
   LetPrim(this.primitive, [this.body = null]);
 
   Expression plug(Expression expr) {
     assert(body == null);
     return body = expr;
   }
 
-  accept(Visitor visitor) => visitor.visitLetPrim(this);
+  accept(BlockVisitor visitor) => visitor.visitLetPrim(this);
 
   void setParentPointers() {
     primitive.parent = this;
     if (body != null) body.parent = this;
   }
 }
 
 /// Binding continuations.
 ///
 /// let cont k0(v0 ...) = E0
@@ skipping 19 matching lines @@
 
   LetCont.many(this.continuations, this.body);
 
   Expression plug(Expression expr) {
     assert(continuations != null &&
            continuations.isNotEmpty &&
            continuations.first.body == null);
     return continuations.first.body = expr;
   }
 
-  accept(Visitor visitor) => visitor.visitLetCont(this);
+  accept(BlockVisitor visitor) => visitor.visitLetCont(this);
 
   void setParentPointers() {
     _setParentsOnNodes(continuations, this);
     if (body != null) body.parent = this;
   }
 }
 
 // Binding an exception handler.
 //
 // let handler h(v0, v1) = E0 in E1
 //
 // The handler is a two-argument (exception, stack trace) continuation which
 // is implicitly the error continuation of all the code in its body E1.
 // [LetHandler] differs from a [LetCont] binding in that it (1) has the
 // runtime semantics of pushing/popping a handler from the dynamic exception
 // handler stack and (2) it does not have any explicit invocations.
 class LetHandler extends InteriorExpression {
   Continuation handler;
   Expression body;
 
   LetHandler(this.handler, this.body);
 
-  accept(Visitor visitor) => visitor.visitLetHandler(this);
+  accept(BlockVisitor visitor) => visitor.visitLetHandler(this);
 
   void setParentPointers() {
     handler.parent = this;
     if (body != null) body.parent = this;
   }
 }
 
 /// Binding mutable variables.
 ///
 /// let mutable v = P in E
 ///
 /// [MutableVariable]s can be seen as ref cells that are not first-class
 /// values.  They are therefore not [Primitive]s and not bound by [LetPrim]
 /// to prevent unrestricted use of references to them.  During one-pass
 /// construction, a [LetMutable] with an empty body is use to represent the
 /// one-hole context 'let mutable v = P in []'.
 class LetMutable extends InteriorExpression {
   final MutableVariable variable;
   final Reference<Primitive> value;
   Expression body;
 
   LetMutable(this.variable, Primitive value)
       : this.value = new Reference<Primitive>(value);
 
   Expression plug(Expression expr) {
     return body = expr;
   }
 
-  accept(Visitor visitor) => visitor.visitLetMutable(this);
+  accept(BlockVisitor visitor) => visitor.visitLetMutable(this);
 
   void setParentPointers() {
     variable.parent = this;
     value.parent = this;
     if (body != null) body.parent = this;
   }
 }
 
 enum CallingConvention {
   /// JS receiver is the Dart receiver, there are no extra arguments.
@@ skipping 569 matching lines @@
 
 /// Throw a value.
 ///
 /// Throw is an expression, i.e., it always occurs in tail position with
 /// respect to a body or expression.
 class Throw extends TailExpression {
   Reference<Primitive> value;
 
   Throw(Primitive value) : value = new Reference<Primitive>(value);
 
-  accept(Visitor visitor) => visitor.visitThrow(this);
+  accept(BlockVisitor visitor) => visitor.visitThrow(this);
 
   void setParentPointers() {
     value.parent = this;
   }
 }
 
 /// Rethrow
 ///
 /// Rethrow can only occur inside a continuation bound by [LetHandler].  It
 /// implicitly throws the exception parameter of the enclosing handler with
 /// the same stack trace as the enclosing handler.
 class Rethrow extends TailExpression {
-  accept(Visitor visitor) => visitor.visitRethrow(this);
+  accept(BlockVisitor visitor) => visitor.visitRethrow(this);
   void setParentPointers() {}
 }
 
 /// An expression that is known to be unreachable.
 ///
 /// This can be placed as the body of a call continuation, when the caller is
 /// known never to invoke it, e.g. because the calling expression always throws.
 class Unreachable extends TailExpression {
-  accept(Visitor visitor) => visitor.visitUnreachable(this);
+  accept(BlockVisitor visitor) => visitor.visitUnreachable(this);
   void setParentPointers() {}
 }
 
 /// Gets the value from a [MutableVariable].
 ///
 /// [MutableVariable]s can be seen as ref cells that are not first-class
 /// values.  A [LetPrim] with a [GetMutable] can then be seen as:
 ///
 ///   let prim p = ![variable] in [body]
 ///
@@ skipping 68 matching lines @@
   /// in later.
   ///
   /// Used as a placeholder for a jump whose target is not yet created
   /// (e.g., in the translation of break and continue).
   InvokeContinuation.uninitialized({this.isRecursive: false,
                                     this.isEscapingTry: false})
       : continuation = null,
         arguments = null,
         sourceInformation = null;
 
-  accept(Visitor visitor) => visitor.visitInvokeContinuation(this);
+  accept(BlockVisitor visitor) => visitor.visitInvokeContinuation(this);
 
   void setParentPointers() {
     if (continuation != null) continuation.parent = this;
     if (arguments != null) _setParentsOnList(arguments, this);
   }
 }
 
 /// Choose between a pair of continuations based on a condition value.
 ///
 /// The two continuations must not declare any parameters.
@@ skipping 18 matching lines @@
         isStrictCheck = true;
 
   Branch.loose(Primitive condition,
                Continuation trueCont,
                Continuation falseCont)
       : this.condition = new Reference<Primitive>(condition),
         trueContinuation = new Reference<Continuation>(trueCont),
         falseContinuation = new Reference<Continuation>(falseCont),
         this.isStrictCheck = false;
 
-  accept(Visitor visitor) => visitor.visitBranch(this);
+  accept(BlockVisitor visitor) => visitor.visitBranch(this);
 
   void setParentPointers() {
     condition.parent = this;
     trueContinuation.parent = this;
     falseContinuation.parent = this;
   }
 }
 
 /// Directly assigns to a field on a given object.
 class SetField extends Primitive {
@@ skipping 473 matching lines @@
   bool isRecursive;
 
   bool get isReturnContinuation => body == null;
 
   Continuation(this.parameters, {this.isRecursive: false});
 
   Continuation.retrn()
     : parameters = <Parameter>[new Parameter(null)],
       isRecursive = false;
 
-  accept(Visitor visitor) => visitor.visitContinuation(this);
+  accept(BlockVisitor visitor) => visitor.visitContinuation(this);
 
   void setParentPointers() {
     _setParentsOnNodes(parameters, this);
     if (body != null) body.parent = this;
   }
 }
 
 /// Common interface for [Primitive] and [MutableVariable].
 abstract class Variable<T extends Variable<T>> extends Definition<T> {
   /// Type of value held in the variable.
@@ skipping 34 matching lines @@
   final List<Parameter> parameters;
   final Continuation returnContinuation;
   Expression body;
 
   FunctionDefinition(this.element,
       this.thisParameter,
       this.parameters,
       this.returnContinuation,
       this.body);
 
-  accept(Visitor visitor) => visitor.visitFunctionDefinition(this);
+  accept(BlockVisitor visitor) => visitor.visitFunctionDefinition(this);
 
   void setParentPointers() {
     if (thisParameter != null) thisParameter.parent = this;
     _setParentsOnNodes(parameters, this);
     returnContinuation.parent = this;
     if (body != null) body.parent = this;
   }
 }
 
 /// Converts the internal representation of a type to a Dart object of type
@@ skipping 121 matching lines @@
     node.parent = parent;
   }
 }
 
 void _setParentsOnList(List<Reference> nodes, Node parent) {
   for (Reference node in nodes) {
     node.parent = parent;
   }
 }
 
-abstract class Visitor<T> {
+/// Visitor for block-level traversals that do not need to dispatch on
+/// primitives.
+abstract class BlockVisitor<T> {
+  const BlockVisitor();
+
+  T visit(Node node) => node.accept(this);
+
+  // Block headers.
+  T visitFunctionDefinition(FunctionDefinition node) => null;
+  T visitContinuation(Continuation node) => null;
+
+  // Interior expressions.
+  T visitLetPrim(LetPrim node) => null;
+  T visitLetCont(LetCont node) => null;
+  T visitLetHandler(LetHandler node) => null;
+  T visitLetMutable(LetMutable node) => null;
+
+  // Tail expressions.
+  T visitInvokeContinuation(InvokeContinuation node) => null;
+  T visitThrow(Throw node) => null;
+  T visitRethrow(Rethrow node) => null;
+  T visitBranch(Branch node) => null;
+  T visitUnreachable(Unreachable node) => null;
+
+  /// Visits block-level nodes in lexical post-order (not post-dominator order).
+  ///
+  /// Continuations and function definitions are considered "block headers".
+  /// The block itself is the sequence of interior expressions in the body,
+  /// terminated by a tail expression.
+  ///
+  /// Each block is visited starting with its tail expression, then every
+  /// interior expression from bottom to top, and finally the block header
+  /// is visited.
+  ///
+  /// Blocks are visited in post-order, so the body of a continuation is always
+  /// processed before its non-recursive invocation sites.
+  ///
+  /// The IR may be transformed during the traversal, but only the original
+  /// nodes will be visited.
+  static void traverseInPostOrder(FunctionDefinition root, BlockVisitor v) {
+    List<Continuation> stack = <Continuation>[];
+    List<Node> nodes = <Node>[];
+    void walkBlock(InteriorNode block) {
+      nodes.add(block);
+      Expression node = block.body;
+      nodes.add(node);
+      while (node.next != null) {
+        if (node is LetCont) {
+          stack.addAll(node.continuations);
+        } else if (node is LetHandler) {
+          stack.add(node.handler);
+        }
+        node = node.next;
+        nodes.add(node);
+      }
+    }
+    walkBlock(root);
+    while (stack.isNotEmpty) {
+      walkBlock(stack.removeLast());
+    }
+    nodes.reversed.forEach(v.visit);
+  }
+}
+
+abstract class Visitor<T> implements BlockVisitor<T> {
   const Visitor();
 
   T visit(Node node);
 
-  // Concrete classes.
-  T visitFunctionDefinition(FunctionDefinition node);
-
-  // Expressions.
-  T visitLetPrim(LetPrim node);
-  T visitLetCont(LetCont node);
-  T visitLetHandler(LetHandler node);
-  T visitLetMutable(LetMutable node);
-  T visitInvokeContinuation(InvokeContinuation node);
-  T visitThrow(Throw node);
-  T visitRethrow(Rethrow node);
-  T visitBranch(Branch node);
-  T visitUnreachable(Unreachable node);
-
   // Definitions.
   T visitInvokeStatic(InvokeStatic node);
   T visitInvokeMethod(InvokeMethod node);
   T visitInvokeMethodDirectly(InvokeMethodDirectly node);
   T visitInvokeConstructor(InvokeConstructor node);
   T visitTypeCast(TypeCast node);
   T visitSetMutable(SetMutable node);
   T visitSetStatic(SetStatic node);
   T visitSetField(SetField node);
   T visitGetLazyStatic(GetLazyStatic node);
   T visitAwait(Await node);
   T visitYield(Yield node);
   T visitLiteralList(LiteralList node);
   T visitLiteralMap(LiteralMap node);
   T visitConstant(Constant node);
   T visitGetMutable(GetMutable node);
   T visitParameter(Parameter node);
-  T visitContinuation(Continuation node);
   T visitMutableVariable(MutableVariable node);
   T visitGetStatic(GetStatic node);
   T visitInterceptor(Interceptor node);
   T visitCreateInstance(CreateInstance node);
   T visitGetField(GetField node);
   T visitCreateBox(CreateBox node);
   T visitReifyRuntimeType(ReifyRuntimeType node);
   T visitReadTypeVariable(ReadTypeVariable node);
   T visitTypeExpression(TypeExpression node);
   T visitCreateInvocationMirror(CreateInvocationMirror node);
   T visitTypeTest(TypeTest node);
   T visitTypeTestViaFlag(TypeTestViaFlag node);
   T visitApplyBuiltinOperator(ApplyBuiltinOperator node);
   T visitApplyBuiltinMethod(ApplyBuiltinMethod node);
   T visitGetLength(GetLength node);
   T visitGetIndex(GetIndex node);
   T visitSetIndex(SetIndex node);
   T visitRefinement(Refinement node);
   T visitBoundsCheck(BoundsCheck node);
   T visitNullCheck(NullCheck node);
-
-  // Support for literal foreign code.
   T visitForeignCode(ForeignCode node);
 }
 
 /// Recursively visits all children of a CPS term.
 ///
 /// The user of the class is responsible for avoiding stack overflows from
 /// deep recursion, e.g. by overriding methods to cut off recursion at certain
 /// points.
 ///
 /// All recursive invocations occur through the [visit] method, which the
@@ skipping 823 matching lines @@
     plug(new Branch.loose(_definitions.getCopy(node.condition),
         _copies[node.trueContinuation.definition],
         _copies[node.falseContinuation.definition])
       ..isStrictCheck = node.isStrictCheck);
   }
 
   visitUnreachable(Unreachable node) {
     plug(new Unreachable());
   }
 }