| // 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. |
| |
| // IrNodes are kept in a separate library to have precise control over their |
| // dependencies on other parts of the system. |
| library dart2js.ir_nodes; |
| |
| import '../dart2jslib.dart' as dart2js show Constant, ConstructedConstant, |
| StringConstant, ListConstant, MapConstant; |
| import '../elements/elements.dart'; |
| import '../universe/universe.dart' show Selector, SelectorKind; |
| import '../dart_types.dart' show DartType, GenericType; |
| import 'const_expression.dart'; |
| import '../helpers/helpers.dart'; |
| |
| abstract class Node { |
| static int hashCount = 0; |
| final int hashCode = hashCount = (hashCount + 1) & 0x3fffffff; |
| |
| accept(Visitor visitor); |
| } |
| |
| abstract class Expression extends Node { |
| Expression plug(Expression expr) => throw 'impossible'; |
| } |
| |
| /// The base class of things that variables can refer to: primitives, |
| /// continuations, function and continuation parameters, etc. |
| abstract class Definition extends Node { |
| // The head of a linked-list of occurrences, in no particular order. |
| Reference firstRef = null; |
| |
| bool get hasAtMostOneUse => firstRef == null || firstRef.nextRef == null; |
| bool get hasExactlyOneUse => firstRef != null && firstRef.nextRef == null; |
| bool get hasAtLeastOneUse => firstRef != null; |
| bool get hasMultipleUses => !hasAtMostOneUse; |
| |
| void substituteFor(Definition other) { |
| if (other.firstRef == null) return; |
| Reference previous, current = other.firstRef; |
| do { |
| current.definition = this; |
| previous = current; |
| current = current.nextRef; |
| } while (current != null); |
| previous.nextRef = firstRef; |
| firstRef = other.firstRef; |
| } |
| } |
| |
| /// An expression that cannot throw or diverge and has no side-effects. |
| /// All primitives are named using the identity of the [Primitive] object. |
| /// |
| /// Primitives may allocate objects, this is not considered side-effect here. |
| /// |
| /// Although primitives may not mutate state, they may depend on state. |
| abstract class Primitive extends Definition { |
| /// The [VariableElement] or [ParameterElement] from which the primitive |
| /// binding originated. |
| Element hint; |
| |
| /// Register in which the variable binding this primitive can be allocated. |
| /// Separate register spaces are used for primitives with different [element]. |
| /// Assigned by [RegisterAllocator], is null before that phase. |
| int registerIndex; |
| |
| /// Use the given element as a hint for naming this primitive. |
| /// |
| /// Has no effect if this primitive already has a non-null [element]. |
| void useElementAsHint(Element hint) { |
| if (this.hint == null) { |
| this.hint = hint; |
| } |
| } |
| } |
| |
| /// Operands to invocations and primitives are always variables. They point to |
| /// their definition and are linked into a list of occurrences. |
| class Reference { |
| Definition definition; |
| Reference nextRef = null; |
| |
| Reference(this.definition) { |
| nextRef = definition.firstRef; |
| definition.firstRef = this; |
| } |
| } |
| |
| /// Binding a value (primitive or constant): 'let val x = V in E'. The bound |
| /// value is in scope in the body. |
| /// During one-pass construction a LetVal with an empty body is used to |
| /// represent one-level context 'let val x = V in []'. |
| class LetPrim extends Expression { |
| final Primitive primitive; |
| Expression body = null; |
| |
| LetPrim(this.primitive); |
| |
| Expression plug(Expression expr) { |
| assert(body == null); |
| return body = expr; |
| } |
| |
| accept(Visitor visitor) => visitor.visitLetPrim(this); |
| } |
| |
| |
| /// Binding a continuation: 'let cont k(v) = E in E'. The bound continuation |
| /// is in scope in the body and the continuation parameter is in scope in the |
| /// continuation body. |
| /// During one-pass construction a LetCont with an empty continuation body is |
| /// used to represent the one-level context 'let cont k(v) = [] in E'. |
| class LetCont extends Expression { |
| final Continuation continuation; |
| final Expression body; |
| |
| LetCont(this.continuation, this.body); |
| |
| Expression plug(Expression expr) { |
| assert(continuation.body == null); |
| return continuation.body = expr; |
| } |
| |
| accept(Visitor visitor) => visitor.visitLetCont(this); |
| } |
| |
| abstract class Invoke { |
| Selector get selector; |
| List<Reference> get arguments; |
| } |
| |
| /// Invoke a static function or static field getter/setter. |
| class InvokeStatic extends Expression implements Invoke { |
| /// [FunctionElement] or [FieldElement]. |
| final Entity target; |
| |
| /** |
| * The selector encodes how the function is invoked: number of positional |
| * arguments, names used in named arguments. This information is required |
| * to build the [StaticCallSiteTypeInformation] for the inference graph. |
| */ |
| final Selector selector; |
| |
| final Reference continuation; |
| final List<Reference> arguments; |
| |
| InvokeStatic(this.target, this.selector, Continuation cont, |
| List<Definition> args) |
| : continuation = new Reference(cont), |
| arguments = _referenceList(args) { |
| assert(target is ErroneousElement || selector.name == target.name); |
| } |
| |
| accept(Visitor visitor) => visitor.visitInvokeStatic(this); |
| } |
| |
| /// Invoke a method, operator, getter, setter, or index getter/setter. |
| /// Converting a method to a function object is treated as a getter invocation. |
| class InvokeMethod extends Expression implements Invoke { |
| final Reference receiver; |
| final Selector selector; |
| final Reference continuation; |
| final List<Reference> arguments; |
| |
| InvokeMethod(Definition receiver, |
| this.selector, |
| Continuation cont, |
| List<Definition> args) |
| : receiver = new Reference(receiver), |
| continuation = new Reference(cont), |
| arguments = _referenceList(args) { |
| assert(selector != null); |
| assert(selector.kind == SelectorKind.CALL || |
| selector.kind == SelectorKind.OPERATOR || |
| (selector.kind == SelectorKind.GETTER && arguments.isEmpty) || |
| (selector.kind == SelectorKind.SETTER && arguments.length == 1) || |
| (selector.kind == SelectorKind.INDEX && arguments.length == 1) || |
| (selector.kind == SelectorKind.INDEX && arguments.length == 2)); |
| } |
| |
| accept(Visitor visitor) => visitor.visitInvokeMethod(this); |
| } |
| |
| /// Invoke a method, operator, getter, setter, or index getter/setter from the |
| /// super class in tail position. |
| class InvokeSuperMethod extends Expression implements Invoke { |
| final Selector selector; |
| final Reference continuation; |
| final List<Reference> arguments; |
| |
| InvokeSuperMethod(this.selector, |
| Continuation cont, |
| List<Definition> args) |
| : continuation = new Reference(cont), |
| arguments = _referenceList(args) { |
| assert(selector != null); |
| assert(selector.kind == SelectorKind.CALL || |
| selector.kind == SelectorKind.OPERATOR || |
| (selector.kind == SelectorKind.GETTER && arguments.isEmpty) || |
| (selector.kind == SelectorKind.SETTER && arguments.length == 1) || |
| (selector.kind == SelectorKind.INDEX && arguments.length == 1) || |
| (selector.kind == SelectorKind.INDEX && arguments.length == 2)); |
| } |
| |
| accept(Visitor visitor) => visitor.visitInvokeSuperMethod(this); |
| } |
| |
| /// Non-const call to a constructor. The [target] may be a generative |
| /// constructor, factory, or redirecting factory. |
| class InvokeConstructor extends Expression implements Invoke { |
| final DartType type; |
| final FunctionElement target; |
| final Reference continuation; |
| final List<Reference> arguments; |
| final Selector selector; |
| |
| /// The class being instantiated. This is the same as `target.enclosingClass` |
| /// and `type.element`. |
| ClassElement get targetClass => target.enclosingElement; |
| |
| /// True if this is an invocation of a factory constructor. |
| bool get isFactory => target.isFactoryConstructor; |
| |
| InvokeConstructor(this.type, |
| this.target, |
| this.selector, |
| Continuation cont, |
| List<Definition> args) |
| : continuation = new Reference(cont), |
| arguments = _referenceList(args) { |
| assert(target.isErroneous || target.isConstructor); |
| assert(target.isErroneous || type.isDynamic || |
| type.element == target.enclosingElement); |
| } |
| |
| accept(Visitor visitor) => visitor.visitInvokeConstructor(this); |
| } |
| |
| /// "as" casts and "is" checks. |
| // We might want to turn "is"-checks into a [Primitive] as it can never diverge. |
| // But then we need to special-case for is-checks with an erroneous .type as |
| // these will throw. |
| class TypeOperator extends Expression { |
| final Reference receiver; |
| final DartType type; |
| final Reference continuation; |
| final String operator; |
| |
| TypeOperator(this.operator, |
| Primitive receiver, |
| this.type, |
| Continuation cont) |
| : this.receiver = new Reference(receiver), |
| this.continuation = new Reference(cont) { |
| assert(operator == "is" || operator == "as"); |
| } |
| |
| accept(Visitor visitor) => visitor.visitTypeOperator(this); |
| } |
| |
| /// Invoke [toString] on each argument and concatenate the results. |
| class ConcatenateStrings extends Expression { |
| final Reference continuation; |
| final List<Reference> arguments; |
| |
| ConcatenateStrings(Continuation cont, List<Definition> args) |
| : continuation = new Reference(cont), |
| arguments = _referenceList(args); |
| |
| accept(Visitor visitor) => visitor.visitConcatenateStrings(this); |
| } |
| |
| /// Gets the value from a closure variable. The identity of the variable is |
| /// determined by a [Local]. |
| /// |
| /// Closure variables can be seen as ref cells that are not first-class values. |
| /// A [LetPrim] with a [GetClosureVariable] can then be seen as: |
| /// |
| /// let prim p = ![variable] in [body] |
| /// |
| class GetClosureVariable extends Primitive { |
| final Local variable; |
| |
| GetClosureVariable(this.variable) { |
| assert(variable != null); |
| } |
| |
| accept(Visitor visitor) => visitor.visitGetClosureVariable(this); |
| } |
| |
| /// Assign or declare a closure variable. The identity of the variable is |
| /// determined by a [Local]. |
| /// |
| /// Closure variables can be seen as ref cells that are not first-class values. |
| /// If [isDeclaration], this can seen as a let binding: |
| /// |
| /// let [variable] = ref [value] in [body] |
| /// |
| /// And otherwise, it can be seen as a dereferencing assignment: |
| /// |
| /// { ![variable] := [value]; [body] } |
| /// |
| /// Closure variables without a declaring [SetClosureVariable] are implicitly |
| /// declared at the entry to the [variable]'s enclosing function. |
| class SetClosureVariable extends Expression { |
| final Local variable; |
| final Reference value; |
| Expression body; |
| |
| /// If true, this declares a new copy of the closure variable. If so, all |
| /// uses of the closure variable must occur in the [body]. |
| /// |
| /// There can be at most one declaration per closure variable. If there is no |
| /// declaration, only one copy exists (per function execution). It is best to |
| /// avoid declaring closure variables if it is not necessary. |
| final bool isDeclaration; |
| |
| SetClosureVariable(this.variable, Primitive value, |
| {this.isDeclaration : false }) |
| : this.value = new Reference(value) { |
| assert(variable != null); |
| } |
| |
| accept(Visitor visitor) => visitor.visitSetClosureVariable(this); |
| |
| Expression plug(Expression expr) { |
| assert(body == null); |
| return body = expr; |
| } |
| } |
| |
| /// Create a potentially recursive function and store it in a closure variable. |
| /// The function can access itself using [GetClosureVariable] on [variable]. |
| /// There must not exist a [SetClosureVariable] to [variable]. |
| /// |
| /// This can be seen as a let rec binding: |
| /// |
| /// let rec [variable] = [definition] in [body] |
| /// |
| class DeclareFunction extends Expression { |
| final Local variable; |
| final FunctionDefinition definition; |
| Expression body; |
| |
| DeclareFunction(this.variable, this.definition); |
| |
| Expression plug(Expression expr) { |
| assert(body == null); |
| return body = expr; |
| } |
| |
| accept(Visitor visitor) => visitor.visitDeclareFunction(this); |
| } |
| |
| /// Invoke a continuation in tail position. |
| class InvokeContinuation extends Expression { |
| final Reference continuation; |
| final List<Reference> arguments; |
| |
| // An invocation of a continuation is recursive if it occurs in the body of |
| // the continuation itself. |
| bool isRecursive; |
| |
| InvokeContinuation(Continuation cont, List<Definition> args, |
| {recursive: false}) |
| : continuation = new Reference(cont), |
| arguments = _referenceList(args), |
| isRecursive = recursive { |
| assert(cont.parameters == null || |
| cont.parameters.length == args.length); |
| if (recursive) cont.isRecursive = true; |
| } |
| |
| accept(Visitor visitor) => visitor.visitInvokeContinuation(this); |
| } |
| |
| /// The base class of things which can be tested and branched on. |
| abstract class Condition extends Node { |
| } |
| |
| class IsTrue extends Condition { |
| final Reference value; |
| |
| IsTrue(Definition val) : value = new Reference(val); |
| |
| accept(Visitor visitor) => visitor.visitIsTrue(this); |
| } |
| |
| /// Choose between a pair of continuations based on a condition value. |
| class Branch extends Expression { |
| final Condition condition; |
| final Reference trueContinuation; |
| final Reference falseContinuation; |
| |
| Branch(this.condition, Continuation trueCont, Continuation falseCont) |
| : trueContinuation = new Reference(trueCont), |
| falseContinuation = new Reference(falseCont); |
| |
| accept(Visitor visitor) => visitor.visitBranch(this); |
| } |
| |
| class Constant extends Primitive { |
| final ConstExp expression; |
| final dart2js.Constant value; |
| |
| Constant(this.expression, this.value); |
| |
| accept(Visitor visitor) => visitor.visitConstant(this); |
| } |
| |
| class This extends Primitive { |
| This(); |
| |
| accept(Visitor visitor) => visitor.visitThis(this); |
| } |
| |
| /// Reify the given type variable as a [Type]. |
| /// This depends on the current binding of 'this'. |
| class ReifyTypeVar extends Primitive { |
| final TypeVariableElement typeVariable; |
| |
| ReifyTypeVar(this.typeVariable); |
| |
| dart2js.Constant get constant => null; |
| |
| accept(Visitor visitor) => visitor.visitReifyTypeVar(this); |
| } |
| |
| class LiteralList extends Primitive { |
| /// The List type being created; this is not the type argument. |
| final GenericType type; |
| final List<Reference> values; |
| |
| LiteralList(this.type, List<Primitive> values) |
| : this.values = _referenceList(values); |
| |
| accept(Visitor visitor) => visitor.visitLiteralList(this); |
| } |
| |
| class LiteralMap extends Primitive { |
| final GenericType type; |
| final List<Reference> keys; |
| final List<Reference> values; |
| |
| LiteralMap(this.type, List<Primitive> keys, List<Primitive> values) |
| : this.keys = _referenceList(keys), |
| this.values = _referenceList(values); |
| |
| accept(Visitor visitor) => visitor.visitLiteralMap(this); |
| } |
| |
| /// Create a non-recursive function. |
| class CreateFunction extends Primitive { |
| final FunctionDefinition definition; |
| |
| CreateFunction(this.definition); |
| |
| accept(Visitor visitor) => visitor.visitCreateFunction(this); |
| } |
| |
| class Parameter extends Primitive { |
| Parameter(Element element) { |
| super.hint = element; |
| } |
| |
| accept(Visitor visitor) => visitor.visitParameter(this); |
| } |
| |
| /// Continuations are normally bound by 'let cont'. A continuation with no |
| /// parameter (or body) is used to represent a function's return continuation. |
| /// The return continuation is bound by the Function, not by 'let cont'. |
| class Continuation extends Definition { |
| final List<Parameter> parameters; |
| Expression body = null; |
| |
| // A continuation is recursive if it has any recursive invocations. |
| bool isRecursive = false; |
| |
| Continuation(this.parameters); |
| |
| Continuation.retrn() : parameters = null; |
| |
| accept(Visitor visitor) => visitor.visitContinuation(this); |
| } |
| |
| /// A function definition, consisting of parameters and a body. The parameters |
| /// include a distinguished continuation parameter. |
| class FunctionDefinition extends Node { |
| final FunctionElement element; |
| final Continuation returnContinuation; |
| final List<Parameter> parameters; |
| final Expression body; |
| final List<ConstDeclaration> localConstants; |
| |
| /// Values for optional parameters. |
| final List<ConstExp> defaultParameterValues; |
| |
| FunctionDefinition(this.element, this.returnContinuation, |
| this.parameters, this.body, this.localConstants, |
| this.defaultParameterValues); |
| |
| accept(Visitor visitor) => visitor.visitFunctionDefinition(this); |
| } |
| |
| List<Reference> _referenceList(List<Definition> definitions) { |
| return definitions.map((e) => new Reference(e)).toList(); |
| } |
| |
| abstract class Visitor<T> { |
| T visit(Node node) => node.accept(this); |
| // Abstract classes. |
| T visitNode(Node node) => null; |
| T visitExpression(Expression node) => visitNode(node); |
| T visitDefinition(Definition node) => visitNode(node); |
| T visitPrimitive(Primitive node) => visitDefinition(node); |
| T visitCondition(Condition node) => visitNode(node); |
| |
| // Concrete classes. |
| T visitFunctionDefinition(FunctionDefinition node) => visitNode(node); |
| |
| // Expressions. |
| T visitLetPrim(LetPrim node) => visitExpression(node); |
| T visitLetCont(LetCont node) => visitExpression(node); |
| T visitInvokeStatic(InvokeStatic node) => visitExpression(node); |
| T visitInvokeContinuation(InvokeContinuation node) => visitExpression(node); |
| T visitInvokeMethod(InvokeMethod node) => visitExpression(node); |
| T visitInvokeSuperMethod(InvokeSuperMethod node) => visitExpression(node); |
| T visitInvokeConstructor(InvokeConstructor node) => visitExpression(node); |
| T visitConcatenateStrings(ConcatenateStrings node) => visitExpression(node); |
| T visitBranch(Branch node) => visitExpression(node); |
| T visitTypeOperator(TypeOperator node) => visitExpression(node); |
| T visitSetClosureVariable(SetClosureVariable node) => visitExpression(node); |
| T visitDeclareFunction(DeclareFunction node) => visitExpression(node); |
| |
| // Definitions. |
| T visitLiteralList(LiteralList node) => visitPrimitive(node); |
| T visitLiteralMap(LiteralMap node) => visitPrimitive(node); |
| T visitConstant(Constant node) => visitPrimitive(node); |
| T visitThis(This node) => visitPrimitive(node); |
| T visitReifyTypeVar(ReifyTypeVar node) => visitPrimitive(node); |
| T visitCreateFunction(CreateFunction node) => visitPrimitive(node); |
| T visitGetClosureVariable(GetClosureVariable node) => visitPrimitive(node); |
| T visitParameter(Parameter node) => visitPrimitive(node); |
| T visitContinuation(Continuation node) => visitDefinition(node); |
| |
| // Conditions. |
| T visitIsTrue(IsTrue node) => visitCondition(node); |
| } |
| |
| abstract class RecursiveVisitor extends Visitor { |
| // Ensures that RecursiveVisitor contains overrides for all relevant nodes. |
| // As a rule of thumb, nodes with structure to traverse should be overridden |
| // with the appropriate visits in this class (for example, visitLetCont), |
| // while leaving other nodes for subclasses (i.e., visitLiteralList). |
| visitNode(Node node) { |
| throw "RecursiveVisitor is stale, add missing visit overrides"; |
| } |
| |
| visitFunctionDefinition(FunctionDefinition node) { |
| visit(node.body); |
| } |
| |
| // Expressions. |
| |
| visitLetPrim(LetPrim node) { |
| visit(node.primitive); |
| visit(node.body); |
| } |
| |
| visitLetCont(LetCont node) { |
| visit(node.continuation.body); |
| visit(node.body); |
| } |
| |
| visitInvokeStatic(InvokeStatic node) => null; |
| visitInvokeContinuation(InvokeContinuation node) => null; |
| visitInvokeMethod(InvokeMethod node) => null; |
| visitInvokeSuperMethod(InvokeSuperMethod node) => null; |
| visitInvokeConstructor(InvokeConstructor node) => null; |
| visitConcatenateStrings(ConcatenateStrings node) => null; |
| |
| visitBranch(Branch node) { |
| visit(node.condition); |
| } |
| |
| visitTypeOperator(TypeOperator node) => null; |
| |
| visitSetClosureVariable(SetClosureVariable node) { |
| visit(node.body); |
| } |
| |
| visitDeclareFunction(DeclareFunction node) { |
| visit(node.definition); |
| visit(node.body); |
| } |
| |
| // Definitions. |
| |
| visitLiteralList(LiteralList node) => null; |
| visitLiteralMap(LiteralMap node) => null; |
| visitConstant(Constant node) => null; |
| visitThis(This node) => null; |
| visitReifyTypeVar(ReifyTypeVar node) => null; |
| |
| visitCreateFunction(CreateFunction node) { |
| visit(node.definition); |
| } |
| |
| visitGetClosureVariable(GetClosureVariable node) => null; |
| visitParameter(Parameter node) => null; |
| visitContinuation(Continuation node) => null; |
| |
| // Conditions. |
| |
| visitIsTrue(IsTrue node) => null; |
| } |
| |
| /// Keeps track of currently unused register indices. |
| class RegisterArray { |
| int nextIndex = 0; |
| final List<int> freeStack = <int>[]; |
| |
| /// Returns an index that is currently unused. |
| int makeIndex() { |
| if (freeStack.isEmpty) { |
| return nextIndex++; |
| } else { |
| return freeStack.removeLast(); |
| } |
| } |
| |
| void releaseIndex(int index) { |
| freeStack.add(index); |
| } |
| } |
| |
| /// Assigns indices to each primitive in the IR such that primitives that are |
| /// live simultaneously never get assigned the same index. |
| /// This information is used by the dart tree builder to generate fewer |
| /// redundant variables. |
| /// Currently, the liveness analysis is very simple and is often inadequate |
| /// for removing all of the redundant variables. |
| class RegisterAllocator extends Visitor { |
| /// Separate register spaces for each source-level variable/parameter. |
| /// Note that null is used as key for primitives without elements. |
| final Map<Element, RegisterArray> elementRegisters = |
| <Element, RegisterArray>{}; |
| |
| RegisterArray getRegisterArray(Element element) { |
| RegisterArray registers = elementRegisters[element]; |
| if (registers == null) { |
| registers = new RegisterArray(); |
| elementRegisters[element] = registers; |
| } |
| return registers; |
| } |
| |
| void allocate(Primitive primitive) { |
| if (primitive.registerIndex == null) { |
| primitive.registerIndex = getRegisterArray(primitive.hint).makeIndex(); |
| } |
| } |
| |
| void release(Primitive primitive) { |
| // Do not share indices for temporaries as this may obstruct inlining. |
| if (primitive.hint == null) return; |
| if (primitive.registerIndex != null) { |
| getRegisterArray(primitive.hint).releaseIndex(primitive.registerIndex); |
| } |
| } |
| |
| void visitReference(Reference reference) { |
| allocate(reference.definition); |
| } |
| |
| void visitFunctionDefinition(FunctionDefinition node) { |
| visit(node.body); |
| node.parameters.forEach(allocate); // Assign indices to unused parameters. |
| elementRegisters.clear(); |
| } |
| |
| void visitLetPrim(LetPrim node) { |
| visit(node.body); |
| release(node.primitive); |
| visit(node.primitive); |
| } |
| |
| void visitLetCont(LetCont node) { |
| visit(node.continuation); |
| visit(node.body); |
| } |
| |
| void visitInvokeStatic(InvokeStatic node) { |
| node.arguments.forEach(visitReference); |
| } |
| |
| void visitInvokeContinuation(InvokeContinuation node) { |
| node.arguments.forEach(visitReference); |
| } |
| |
| void visitInvokeMethod(InvokeMethod node) { |
| visitReference(node.receiver); |
| node.arguments.forEach(visitReference); |
| } |
| |
| void visitInvokeSuperMethod(InvokeSuperMethod node) { |
| node.arguments.forEach(visitReference); |
| } |
| |
| void visitInvokeConstructor(InvokeConstructor node) { |
| node.arguments.forEach(visitReference); |
| } |
| |
| void visitConcatenateStrings(ConcatenateStrings node) { |
| node.arguments.forEach(visitReference); |
| } |
| |
| void visitBranch(Branch node) { |
| visit(node.condition); |
| } |
| |
| void visitLiteralList(LiteralList node) { |
| node.values.forEach(visitReference); |
| } |
| |
| void visitLiteralMap(LiteralMap node) { |
| for (int i = 0; i < node.keys.length; ++i) { |
| visitReference(node.keys[i]); |
| visitReference(node.values[i]); |
| } |
| } |
| |
| void visitTypeOperator(TypeOperator node) { |
| visitReference(node.receiver); |
| } |
| |
| void visitConstant(Constant node) { |
| } |
| |
| void visitThis(This node) { |
| } |
| |
| void visitReifyTypeVar(ReifyTypeVar node) { |
| } |
| |
| void visitCreateFunction(CreateFunction node) { |
| new RegisterAllocator().visit(node.definition); |
| } |
| |
| void visitGetClosureVariable(GetClosureVariable node) { |
| } |
| |
| void visitSetClosureVariable(SetClosureVariable node) { |
| visit(node.body); |
| visitReference(node.value); |
| } |
| |
| void visitDeclareFunction(DeclareFunction node) { |
| new RegisterAllocator().visit(node.definition); |
| visit(node.body); |
| } |
| |
| void visitParameter(Parameter node) { |
| throw "Parameters should not be visited by RegisterAllocator"; |
| } |
| |
| void visitContinuation(Continuation node) { |
| visit(node.body); |
| |
| // Arguments get allocated left-to-right, so we release parameters |
| // right-to-left. This increases the likelihood that arguments can be |
| // transferred without intermediate assignments. |
| for (int i = node.parameters.length - 1; i >= 0; --i) { |
| release(node.parameters[i]); |
| } |
| } |
| |
| void visitIsTrue(IsTrue node) { |
| visitReference(node.value); |
| } |
| |
| } |
| |
| /// Eliminate redundant phis from the given [FunctionDefinition]. |
| /// |
| /// Phis in this case are [Continuations] together with corresponding |
| /// [InvokeContinuation]s. A [Continuation] parameter at position i is redundant |
| /// if for all [InvokeContinuation]s, the parameter at position i is identical |
| /// (except for feedback). Redundant parameters are removed from the |
| /// continuation signature, all invocations, and replaced within the |
| /// continuation body. |
| class RedundantPhiEliminator extends RecursiveVisitor { |
| final Map<Continuation, List<InvokeContinuation>> cont2invokes = |
| <Continuation, List<InvokeContinuation>>{}; |
| // For each reference r used in a continuation invocation i, stores the |
| // corresponding continuation i.continuation. If required by other passes, |
| // we could consider adding parent pointers to references instead. |
| final Map<Reference, Continuation> ref2cont = <Reference, Continuation>{}; |
| final Set<Continuation> workSet = new Set<Continuation>(); |
| |
| void rewrite(final FunctionDefinition root) { |
| // Traverse the tree once to build the work set. |
| visit(root); |
| workSet.addAll(cont2invokes.keys); |
| |
| // Process each continuation one-by-one. |
| while (workSet.isNotEmpty) { |
| Continuation cont = workSet.first; |
| workSet.remove(cont); |
| |
| if (cont.body == null) { |
| continue; // Skip function return continuations. |
| } |
| |
| List<InvokeContinuation> invokes = cont2invokes[cont]; |
| assert(invokes != null); |
| |
| _processContinuation(cont, invokes); |
| } |
| } |
| |
| /// Called for each continuation on the work set, together with its |
| /// invocations. |
| void _processContinuation(Continuation cont, |
| List<InvokeContinuation> invokes) { |
| /// Returns the unique definition of parameter i if it exists and null |
| /// otherwise. A definition is unique if it is the only value used to |
| /// invoke the continuation, excluding feedback. |
| Definition uniqueDefinitionOf(int i) { |
| Definition value = null; |
| for (InvokeContinuation invoke in invokes) { |
| Definition def = invoke.arguments[i].definition; |
| |
| if (cont.parameters[i] == def) { |
| // Invocation param == param in LetCont (i.e. a recursive call). |
| continue; |
| } else if (value == null) { |
| value = def; // Set initial comparison value. |
| } else if (value != def) { |
| return null; // Differing invocation arguments. |
| } |
| } |
| |
| return value; |
| } |
| |
| // Check if individual parameters are always called with a unique |
| // definition, and remove them if that is the case. During each iteration, |
| // we read the current parameter/argument from index `src` and copy it |
| // to index `dst`. |
| int dst = 0; |
| for (int src = 0; src < cont.parameters.length; src++) { |
| // Is the current phi redundant? |
| Definition uniqueDefinition = uniqueDefinitionOf(src); |
| if (uniqueDefinition == null) { |
| // Reorganize parameters and arguments in case of deletions. |
| cont.parameters[dst] = cont.parameters[src]; |
| for (InvokeContinuation invoke in invokes) { |
| invoke.arguments[dst] = invoke.arguments[src]; |
| } |
| |
| dst++; |
| continue; |
| } |
| |
| Definition oldDefinition = cont.parameters[src]; |
| |
| // Add continuations of about-to-be modified invokes to worklist since |
| // we might introduce new optimization opportunities. |
| for (Reference ref = oldDefinition.firstRef; ref != null; |
| ref = ref.nextRef) { |
| Continuation thatCont = ref2cont[ref]; |
| // thatCont is null if ref does not belong to a continuation invocation. |
| if (thatCont != null && thatCont != cont) { |
| workSet.add(thatCont); |
| } |
| } |
| |
| // Replace individual parameters: |
| // * In the continuation body, replace occurrence of param with value, |
| // * and implicitly remove param from continuation signature and |
| // invocations by not incrementing `dst`. |
| uniqueDefinition.substituteFor(oldDefinition); |
| } |
| |
| // Remove trailing items from parameter and argument lists. |
| cont.parameters.length = dst; |
| for (InvokeContinuation invoke in invokes) { |
| invoke.arguments.length = dst; |
| } |
| } |
| |
| void visitInvokeContinuation(InvokeContinuation node) { |
| // Update the continuation map. |
| Continuation cont = node.continuation.definition; |
| assert(cont != null); |
| cont2invokes.putIfAbsent(cont, () => <InvokeContinuation>[]) |
| .add(node); |
| |
| // And the reference map. |
| node.arguments.forEach((Reference ref) { |
| assert(!ref2cont.containsKey(ref)); |
| ref2cont[ref] = node.continuation.definition; |
| }); |
| } |
| } |