Support local variables in dart2dart.

sdk/lib/_internal/compiler/implementation/ir/ir_builder.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_builder;
 
 import 'ir_nodes.dart' as ir;
 import '../elements/elements.dart';
 import '../dart2jslib.dart';
 import '../dart_types.dart';
@@ skipping 132 matching lines @@
     }
     return element.getCompilationUnit().script.file;
   }
 }
 
 /**
  * A tree visitor that builds [IrNodes]. The visit methods add statements using
  * to the [builder] and return the last added statement for trees that represent
  * an expression.
  */
-class IrBuilder extends ResolvedVisitor<ir.Definition> {
+class IrBuilder extends ResolvedVisitor<ir.Primitive> {
   final SourceFile sourceFile;
-  ir.Continuation returnContinuation = null;
-  List<ir.Parameter> parameters = <ir.Parameter>[];
+  final ir.Continuation returnContinuation;
+  final List<ir.Parameter> parameters;
 
   // The IR builder maintains a context, which is an expression with a hole in
   // it.  The hole represents the focus where new expressions can be added.
   // The context is implemented by 'root' which is the root of the expression
   // and 'current' which is the expression that immediately contains the hole.
   // Not all expressions have a hole (e.g., invocations, which always occur in
   // tail position, do not have a hole).  Expressions with a hole have a plug
   // method.
   //
   // Conceptually, visiting a statement takes a context as input and returns
   // either a new context or else an expression without a hole if all
   // control-flow paths through the statement have exited.  An expression
   // without a hole is represented by a (root, current) pair where root is the
   // expression and current is null.
   //
   // Conceptually again, visiting an expression takes a context as input and
   // returns either a pair of a new context and a definition denoting
   // the expression's value, or else an expression without a hole if all
   // control-flow paths through the expression have exited.
   //
-  // We do not pass and return contexts, rather we use the current context
-  // (root, current) as the visitor state and mutate current.  Visiting a
-  // statement returns null; visiting an expression optionally returns the
-  // definition denoting its value.
+  // We do not pass contexts as arguments or return them.  Rather we use the
+  // current context (root, current) as the visitor state and mutate current.
+  // Visiting a statement returns null; visiting an expression returns the
+  // primitive denoting its value.
+
   ir.Expression root = null;
   ir.Expression current = null;
 
-  Map<Element, int> variableIndex = <Element, int>{};
-  List<ir.Definition> assignedVars = <ir.Definition>[];
+  // In SSA terms, join-point continuation parameters are the phis and the
+  // continuation invocation arguments are the corresponding phi inputs.  To
+  // support name introduction and renaming for source level variables, we use
+  // nested (delimited) visitors for constructing subparts of the IR that will
+  // need renaming.  Each source variable is assigned an index.
+  //
+  // Each nested visitor maintains a list of free variable uses in the body.
+  // These are implemented as a list of parameters, each with their own use
+  // list of references.  When the delimited subexpression is plugged into the
+  // surrounding context, the free occurrences can be captured or become free
+  // occurrences in the next outer delimited subexpression.
+  //
+  // Each nested visitor maintains a list that maps indexes of variables
+  // assigned in the delimited subexpression to their reaching definition ---
+  // that is, the definition in effect at the hole in 'current'.  These are
+  // used to determine if a join-point continuation needs to be passed
+  // arguments, and what the arguments are.
+  final Map<Element, int> variableIndex;
+  final List<ir.Parameter> freeVars;
+  final List<ir.Primitive> assignedVars;
 
+  /// Construct a top-level visitor.
   IrBuilder(TreeElements elements, Compiler compiler, this.sourceFile)
-      : super(elements, compiler);
+      : returnContinuation = new ir.Continuation.retrn(),
+        parameters = <ir.Parameter>[],
+        variableIndex = <Element, int>{},
+        freeVars = null,
+        assignedVars = <ir.Primitive>[],
+        super(elements, compiler);
+
+  /// Construct a delimited visitor.
+  IrBuilder.delimited(IrBuilder parent)
+      : sourceFile = parent.sourceFile,
+        returnContinuation = parent.returnContinuation,
+        parameters = parent.parameters,
+        variableIndex = parent.variableIndex,
+        freeVars = new List<ir.Parameter>.generate(
+            parent.assignedVars.length, (_) => new ir.Parameter(null),
+            growable: false),
+        assignedVars = new List<ir.Primitive>.generate(
+            parent.assignedVars.length, (_) => null),
+        super(parent.elements, parent.compiler);
 
   /**
    * Builds the [ir.FunctionDefinition] for a function element. In case the
    * function uses features that cannot be expressed in the IR, this function
    * returns `null`.
    */
   ir.FunctionDefinition buildFunction(FunctionElement functionElement) {
     return nullIfGiveup(() => buildFunctionInternal(functionElement));
   }
 
   ir.FunctionDefinition buildFunctionInternal(FunctionElement element) {
     assert(invariant(element, element.isImplementation));
     ast.FunctionExpression function = element.parseNode(compiler);
     assert(function != null);
     assert(!function.modifiers.isExternal());
     assert(elements[function] != null);
 
-    returnContinuation = new ir.Continuation.retrn();
     root = current = null;
 
     FunctionSignature signature = element.functionSignature;
     signature.orderedForEachParameter((parameterElement) {
       ir.Parameter parameter = new ir.Parameter(parameterElement);
       parameters.add(parameter);
       variableIndex[parameterElement] = assignedVars.length;
       assignedVars.add(parameter);
     });
 
     visit(function.body);
     ensureReturn(function);
     return new ir.FunctionDefinition(returnContinuation, parameters, root);
   }
 
   ConstantSystem get constantSystem => compiler.backend.constantSystem;
 
   bool get isOpen => root == null || current != null;
 
   // Plug an expression into the 'hole' in the context being accumulated.  The
   // empty context (just a hole) is represented by root (and current) being
   // null.  Since the hole in the current context is filled by this function,
   // the new hole must be in the newly added expression---which becomes the
   // new value of current.
   void add(ir.Expression expr) {
+    assert(isOpen);
     if (root == null) {
       root = current = expr;
-    } else if (current != null) {
+    } else {
       current = current.plug(expr);
     }
   }
 
   /**
    * Add an explicit `return null` for functions that don't have a return
    * statement on each branch. This includes functions with an empty body,
    * such as `foo(){ }`.
    */
   void ensureReturn(ast.FunctionExpression node) {
     if (!isOpen) return;
     ir.Constant constant = new ir.Constant(constantSystem.createNull());
     add(new ir.LetPrim(constant));
-    add(new ir.InvokeContinuation(returnContinuation, constant));
+    add(new ir.InvokeContinuation(returnContinuation, [constant]));
     current = null;
   }
 
-  ir.Definition visit(ast.Node node) => node.accept(this);
+  ir.Primitive visit(ast.Node node) => node.accept(this);
 
   // ==== Statements ====
   // Build(Block(stamements), C) = C'
   //   where C' = statements.fold(Build, C)
-  ir.Definition visitBlock(ast.Block node) {
+  ir.Primitive visitBlock(ast.Block node) {
     assert(isOpen);
     for (ast.Node n in node.statements.nodes) {
       visit(n);
       if (!isOpen) return null;
     }
     return null;
   }
 
   // Build(EmptyStatement, C) = C
-  ir.Definition visitEmptyStatement(ast.EmptyStatement node) {
+  ir.Primitive visitEmptyStatement(ast.EmptyStatement node) {
     assert(isOpen);
     return null;
   }
 
   // Build(ExpressionStatement(e), C) = C'
   //   where (C', _) = Build(e, C)
-  ir.Definition visitExpressionStatement(ast.ExpressionStatement node) {
+  ir.Primitive visitExpressionStatement(ast.ExpressionStatement node) {
     assert(isOpen);
     visit(node.expression);
     return null;
   }
 
-  ir.Definition visitIf(ast.If node) {
+  ir.Primitive visitIf(ast.If node) {
     assert(isOpen);
-    return giveup();
+    ir.Primitive condition = visit(node.condition);
+
+    // The then and else parts are delimited.
+    IrBuilder thenBuilder = new IrBuilder.delimited(this);
+    thenBuilder.visit(node.thenPart);
+    IrBuilder elseBuilder = new IrBuilder.delimited(this);
+    if (node.hasElsePart) elseBuilder.visit(node.elsePart);
+
+    // The free variables in the then and else parts are uses of definitions
+    // from an outer builder.  Capture them or propagate them outward.  The
+    // assigned variables in the then and else parts are arguments to the join
+    // point continuation if any.
+
+    // FreeVars is initially the length of assignedVars of the parent, and it
+    // does not grow.  AssignedVars can grow.
+    assert(assignedVars.length == thenBuilder.freeVars.length);
+    assert(assignedVars.length == elseBuilder.freeVars.length);
+    assert(assignedVars.length <= thenBuilder.assignedVars.length);
+    assert(assignedVars.length <= elseBuilder.assignedVars.length);
+    List<ir.Parameter> parameters = <ir.Parameter>[];
+    List<ir.Primitive> thenArguments = <ir.Primitive>[];
+    List<ir.Primitive> elseArguments = <ir.Primitive>[];
+    for (int i = 0; i < assignedVars.length; ++i) {
+      // These are the last assignments, if any, in the then and else
+      // continuations respectively (if they can reach the join point).  If a
+      // variable is assigned in either branch reaching the join point, it has
+      // different values that must be passed as an argument to the join point
+      // continuation.
+      ir.Definition thenAssignment =
+          thenBuilder.isOpen ? thenBuilder.assignedVars[i] : null;
+      ir.Definition elseAssignment =
+          elseBuilder.isOpen ? elseBuilder.assignedVars[i] : null;
+      if (thenAssignment != null || elseAssignment != null) {
+        // In the case that not both then and else parts can reach the join
+        // point, there will still be a join-point continuation possibly with
+        // arguments passed to it.  Such singly-used continuations should be
+        // eliminated by shrinking conversions (because they can arise
+        // otherwise as the result of optimization).
+        ir.Parameter parameter = new ir.Parameter(null);
+        parameters.add(parameter);
+        thenArguments.add(thenAssignment == null
+                              ? thenBuilder.freeVars[i]
+                              : thenAssignment);
+        elseArguments.add(elseAssignment == null
+                              ? elseBuilder.freeVars[i]
+                              : elseAssignment);
+      }
+    }
+
+    // Create a then and else continuations and a join continuation if
+    // necessary.  Jump to the join continuation from the exits of the then
+    // and else continuations.
+    ir.Continuation joinContinuation;
+    ir.Continuation thenContinuation = new ir.Continuation([]);
+    ir.Continuation elseContinuation = new ir.Continuation([]);
+    if (thenBuilder.isOpen || elseBuilder.isOpen) {
+      joinContinuation = new ir.Continuation(parameters);
+      if (thenBuilder.isOpen) {
+        thenBuilder.add(
+            new ir.InvokeContinuation(joinContinuation, thenArguments));
+      }
+      if (elseBuilder.isOpen) {
+        elseBuilder.add(
+            new ir.InvokeContinuation(joinContinuation, elseArguments));
+      }
+    }
+    thenContinuation.body = thenBuilder.root;
+    elseContinuation.body = elseBuilder.root;
+
+    // Capture free occurrences in the then and else bodies.  This is done
+    // after creating invocations of the join continuation so free join
+    // continuation arguments are properly captured.
+    //
+    // Also add join continuation parameters as assignments for the join body.
+    // This is done last because the assigned variables are updated in place.
+    int parameterIndex = 0;
+    for (int i = 0; i < assignedVars.length; ++i) {
+      // This is the definition that reaches the then and else continuations.
+      // All free uses in either continuation are uses of this definition.
+      ir.Definition reachingDefinition =
+          assignedVars[i] == null ? freeVars[i] : assignedVars[i];
+      reachingDefinition
+          ..substituteFor(thenBuilder.freeVars[i])
+          ..substituteFor(elseBuilder.freeVars[i]);
+
+      if ((thenBuilder.isOpen && thenBuilder.assignedVars[i] != null) ||
+          (elseBuilder.isOpen && elseBuilder.assignedVars[i] != null)) {
+        assignedVars[i] = parameters[parameterIndex++];
+      }
+    }
+
+    ir.Expression branch =
+        new ir.LetCont(thenContinuation,
+            new ir.LetCont(elseContinuation,
+                new ir.Branch(new ir.IsTrue(condition),
+                              thenContinuation,
+                              elseContinuation)));
+    if (joinContinuation == null) {
+      add(branch);
+      current = null;
+    } else {
+      add(new ir.LetCont(joinContinuation, branch));
+    }
+    return null;
   }
 
-  ir.Definition visitVariableDefinitions(ast.VariableDefinitions node) {
+  ir.Primitive visitVariableDefinitions(ast.VariableDefinitions node) {
     assert(isOpen);
     for (ast.Node definition in node.definitions.nodes) {
       Element element = elements[definition];
       // Definitions are either SendSets if there is an initializer, or
       // Identifiers if there is no initializer.
       if (definition is ast.SendSet) {
         assert(!definition.arguments.isEmpty);
         assert(definition.arguments.tail.isEmpty);
-        ir.Definition initialValue = visit(definition.arguments.head);
-        // Do not continue adding instructions if the initializer throws.
-        if (!isOpen) return null;
+        ir.Primitive initialValue = visit(definition.arguments.head);
         variableIndex[element] = assignedVars.length;
         assignedVars.add(initialValue);
       } else {
         assert(definition is ast.Identifier);
         // The initial value is null.
         // TODO(kmillikin): Consider pooling constants.
         ir.Constant constant = new ir.Constant(constantSystem.createNull());
         add(new ir.LetPrim(constant));
         variableIndex[element] = assignedVars.length;
         assignedVars.add(constant);
       }
     }
     return null;
   }
 
   // Build(Return(e), C) = C'[InvokeContinuation(return, x)]
   //   where (C', x) = Build(e, C)
   //
   // Return without a subexpression is translated as if it were return null.
-  ir.Definition visitReturn(ast.Return node) {
+  ir.Primitive visitReturn(ast.Return node) {
     assert(isOpen);
     // TODO(lry): support native returns.
     if (node.beginToken.value == 'native') return giveup();
-    ir.Definition value;
+    ir.Primitive value;
     if (node.expression == null) {
       value = new ir.Constant(constantSystem.createNull());
       add(new ir.LetPrim(value));
     } else {
       value = visit(node.expression);
-      if (!isOpen) return null;
     }
-    add(new ir.InvokeContinuation(returnContinuation, value));
+    add(new ir.InvokeContinuation(returnContinuation, [value]));
     current = null;
     return null;
   }
 
   // ==== Expressions ====
   // For all simple literals:
   // Build(Literal(c), C) = C[let val x = Constant(c) in [], x]
-  ir.Definition visitLiteralBool(ast.LiteralBool node) {
+  ir.Primitive visitLiteralBool(ast.LiteralBool node) {
     assert(isOpen);
     ir.Constant constant =
         new ir.Constant(constantSystem.createBool(node.value));
     add(new ir.LetPrim(constant));
     return constant;
   }
 
-  ir.Definition visitLiteralDouble(ast.LiteralDouble node) {
+  ir.Primitive visitLiteralDouble(ast.LiteralDouble node) {
     assert(isOpen);
     ir.Constant constant =
         new ir.Constant(constantSystem.createDouble(node.value));
     add(new ir.LetPrim(constant));
     return constant;
   }
 
-  ir.Definition visitLiteralInt(ast.LiteralInt node) {
+  ir.Primitive visitLiteralInt(ast.LiteralInt node) {
     assert(isOpen);
     ir.Constant constant =
         new ir.Constant(constantSystem.createInt(node.value));
     add(new ir.LetPrim(constant));
     return constant;
   }
 
 
-  ir.Definition visitLiteralNull(ast.LiteralNull node) {
+  ir.Primitive visitLiteralNull(ast.LiteralNull node) {
     assert(isOpen);
     ir.Constant constant = new ir.Constant(constantSystem.createNull());
     add(new ir.LetPrim(constant));
     return constant;
   }
 
   // TODO(kmillikin): other literals.  Strings require quoting and escaping
   // in the Dart backend.
   //   LiteralString
   //   LiteralList
   //   LiteralMap
   //   LiteralMapEntry
   //   LiteralSymbol
 
-  ir.Definition visitParenthesizedExpression(
+  ir.Primitive visitParenthesizedExpression(
       ast.ParenthesizedExpression node) {
+    assert(isOpen);
     return visit(node.expression);
   }
 
   // ==== Sends ====
-  ir.Definition visitAssert(ast.Send node) {
+  ir.Primitive visitAssert(ast.Send node) {
+    assert(isOpen);
     return giveup();
   }
 
-  ir.Definition visitClosureSend(ast.Send node) {
+  ir.Primitive visitClosureSend(ast.Send node) {
+    assert(isOpen);
     return giveup();
   }
 
-  ir.Definition visitDynamicSend(ast.Send node) {
+  ir.Primitive visitDynamicSend(ast.Send node) {
+    assert(isOpen);
     return giveup();
   }
 
-  ir.Definition visitGetterSend(ast.Send node) {
+  ir.Primitive visitGetterSend(ast.Send node) {
+    assert(isOpen);
     Element element = elements[node];
     if (!Elements.isLocal(element)) return giveup();
-    return assignedVars[variableIndex[element]];
+    int index = variableIndex[element];
+    ir.Primitive value = assignedVars[index];
+    return value == null ? freeVars[index] : value;
   }
 
-  ir.Definition visitOperatorSend(ast.Send node) {
+  ir.Primitive visitOperatorSend(ast.Send node) {
+    assert(isOpen);
     return giveup();
   }
 
   // Build(StaticSend(f, arguments), C) = C[C'[InvokeStatic(f, xs)]]
   //   where (C', xs) = arguments.fold(Build, C)
-  ir.Definition visitStaticSend(ast.Send node) {
+  ir.Primitive visitStaticSend(ast.Send node) {
     assert(isOpen);
     Element element = elements[node];
     // TODO(lry): support static fields. (separate IR instruction?)
     if (element.isField() || element.isGetter()) return giveup();
     // TODO(kmillikin): support static setters.
     if (element.isSetter()) return giveup();
     // TODO(lry): support constructors / factory calls.
     if (element.isConstructor()) return giveup();
     // TODO(lry): support foreign functions.
     if (element.isForeign(compiler)) return giveup();
     // TODO(lry): for elements that could not be resolved emit code to throw a
     // [NoSuchMethodError].
     if (element.isErroneous()) return giveup();
     // TODO(lry): generate IR for object identicality.
     if (element == compiler.identicalFunction) giveup();
 
     Selector selector = elements.getSelector(node);
     // TODO(lry): support named arguments
     if (selector.namedArgumentCount != 0) return giveup();
 
     // TODO(kmillikin): support a receiver: A.m().
     if (node.receiver != null) return giveup();
 
     List arguments = [];
     // TODO(lry): support default arguments, need support for locals.
     bool succeeded = selector.addArgumentsToList(
-        node.arguments, arguments, element.implementation,
-        // Guard against visiting arguments after an argument expression throws.
-        (node) => isOpen ? visit(node) : null,
-        (node) => giveup(),
-        compiler);
+        node.arguments, arguments, element.implementation, visit,
+        (node) => giveup(), compiler);
     if (!succeeded) {
       // TODO(lry): generate code to throw a [WrongArgumentCountError].
       return giveup();
     }
-    if (!isOpen) return null;
     ir.Parameter v = new ir.Parameter(null);
     ir.Continuation k = new ir.Continuation([v]);
     ir.Expression invoke =
         new ir.InvokeStatic(element, selector, k, arguments);
     add(new ir.LetCont(k, invoke));
     return v;
   }
 
-  ir.Definition visitSuperSend(ast.Send node) {
+  ir.Primitive visitSuperSend(ast.Send node) {
+    assert(isOpen);
     return giveup();
   }
 
-  ir.Definition visitTypeReferenceSend(ast.Send node) {
+  ir.Primitive visitTypeReferenceSend(ast.Send node) {
+    assert(isOpen);
     return giveup();
   }
 
-  ir.Definition visitSendSet(ast.SendSet node) {
+  ir.Primitive visitSendSet(ast.SendSet node) {
+    assert(isOpen);
     Element element = elements[node];
     if (!Elements.isLocal(element)) return giveup();
     if (node.assignmentOperator.source != '=') return giveup();
     // Exactly one argument expected for a simple assignment.
     assert(!node.arguments.isEmpty);
     assert(node.arguments.tail.isEmpty);
-    ir.Definition result = visit(node.arguments.head);
+    ir.Primitive result = visit(node.arguments.head);
     assignedVars[variableIndex[element]] = result;
     return result;
   }
 
   static final String ABORT_IRNODE_BUILDER = "IrNode builder aborted";
 
-  ir.Definition giveup() => throw ABORT_IRNODE_BUILDER;
+  ir.Primitive giveup() => throw ABORT_IRNODE_BUILDER;
 
   ir.FunctionDefinition nullIfGiveup(ir.FunctionDefinition action()) {
     try {
       return action();
     } catch(e) {
       if (e == ABORT_IRNODE_BUILDER) return null;
       rethrow;
     }
   }
 
   void internalError(String reason, {ast.Node node}) {
     giveup();
   }
 }
 
 // Verify that types are ones that can be reconstructed by the type emitter.
 class SupportedTypeVerifier extends DartTypeVisitor<bool, Null> {
   bool visit(DartType type, Null _) => type.accept(this, null);
 
   bool visitType(DartType type, Null _) => false;
 
   bool visitVoidType(VoidType type, Null _) => true;
 
   // Currently, InterfaceType and TypedefType are supported so long as they
   // do not have type parameters.  They are subclasses of GenericType.
   bool visitGenericType(GenericType type, Null _) => !type.isGeneric;
 }