cps-ir: Merge variables based on set-based liveness and graph coloring.

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.
 
 // 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 '../constants/expressions.dart';
 import '../constants/values.dart' as values show ConstantValue;
@@ skipping 47 matching lines @@
 /// 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<Primitive> {
   /// The [VariableElement] or [ParameterElement] from which the primitive
   /// binding originated.
   Entity 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(Entity hint) {
     if (this.hint == null) {
       this.hint = hint;
     }
   }
 }
 
@@ skipping 910 matching lines @@
     node.parameters.forEach(visit);
     if (!node.isAbstract) {
       visit(node.body);
     }
   }
 
   processConstructorDefinition(ConstructorDefinition node) {}
   visitConstructorDefinition(ConstructorDefinition node) {
     processConstructorDefinition(node);
     node.parameters.forEach(visit);
-    node.initializers.forEach(visit);
-    visit(node.body);
+    if (!node.isAbstract) {
+      node.initializers.forEach(visit);
+      visit(node.body);
+    }
   }
 
   processFieldInitializer(FieldInitializer node) {}
   visitFieldInitializer(FieldInitializer node) {
     processFieldInitializer(node);
     visit(node.body);
   }
 
   processSuperInitializer(SuperInitializer node) {}
   visitSuperInitializer(SuperInitializer node) {
@@ skipping 212 matching lines @@
     processReifyRuntimeType(node);
     processReference(node.value);
   }
 
   processReadTypeVariable(ReadTypeVariable node) {}
   visitReadTypeVariable(ReadTypeVariable node) {
     processReadTypeVariable(node);
     processReference(node.target);
   }
 }
-
-/// 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 implements Visitor {
-  final dart2js.InternalErrorFunction internalError;
-
-  /// Separate register spaces for each source-level variable/parameter.
-  /// Note that null is used as key for primitives without hints.
-  final Map<Local, RegisterArray> elementRegisters = <Local, RegisterArray>{};
-
-  RegisterAllocator(this.internalError);
-
-  RegisterArray getRegisterArray(Local local) {
-    RegisterArray registers = elementRegisters[local];
-    if (registers == null) {
-      registers = new RegisterArray();
-      elementRegisters[local] = 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 visit(Node node) => node.accept(this);
-
-  void visitReference(Reference reference) {
-    allocate(reference.definition);
-  }
-
-  void visitFieldDefinition(FieldDefinition node) {
-    if (node.hasInitializer) {
-      visit(node.body);
-    }
-  }
-
-  void visitRunnableBody(RunnableBody node) {
-    visit(node.body);
-  }
-
-  void visitFunctionDefinition(FunctionDefinition node) {
-    if (!node.isAbstract) {
-      visit(node.body);
-    }
-    // Assign indices to unused parameters.
-    for (Definition param in node.parameters) {
-      if (param is Primitive) {
-        allocate(param);
-      }
-    }
-  }
-
-  void visitConstructorDefinition(ConstructorDefinition node) {
-    if (!node.isAbstract) {
-      node.initializers.forEach(visit);
-      visit(node.body);
-    }
-    // Assign indices to unused parameters.
-    for (Definition param in node.parameters) {
-      if (param is Primitive) {
-        allocate(param);
-      }
-    }
-  }
-
-  void visitFieldInitializer(FieldInitializer node) {
-    visit(node.body.body);
-  }
-
-  void visitSuperInitializer(SuperInitializer node) {
-    node.arguments.forEach(visit);
-  }
-
-  void visitLetPrim(LetPrim node) {
-    visit(node.body);
-    release(node.primitive);
-    visit(node.primitive);
-  }
-
-  void visitLetCont(LetCont node) {
-    node.continuations.forEach(visit);
-    visit(node.body);
-  }
-
-  void visitLetHandler(LetHandler node) {
-    visit(node.handler);
-    // Handler parameters that were not used in the handler body will not have
-    // had register indexes assigned.  Assign them here, otherwise they will
-    // be eliminated later and they should not be (i.e., a catch clause that
-    // does not use the exception parameter should not have the exception
-    // parameter eliminated, because it would not be well-formed anymore).
-    // In any case release the parameter indexes because the parameters are
-    // not live in the try block.
-    node.handler.parameters.forEach((Parameter parameter) {
-      allocate(parameter);
-      release(parameter);
-    });
-    visit(node.body);
-  }
-
-  void visitLetMutable(LetMutable node) {
-    visit(node.body);
-    visitReference(node.value);
-  }
-
-  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 visitInvokeMethodDirectly(InvokeMethodDirectly node) {
-    visitReference(node.receiver);
-    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 (LiteralMapEntry entry in node.entries) {
-      visitReference(entry.key);
-      visitReference(entry.value);
-    }
-  }
-
-  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(internalError).visit(node.definition);
-  }
-
-  void visitGetMutableVariable(GetMutableVariable node) {
-  }
-
-  void visitSetMutableVariable(SetMutableVariable node) {
-    visit(node.body);
-    visitReference(node.value);
-  }
-
-  void visitDeclareFunction(DeclareFunction node) {
-    new RegisterAllocator(internalError).visit(node.definition);
-    visit(node.body);
-  }
-
-  void visitParameter(Parameter node) {
-    // Parameters are handled differently depending on whether they are
-    // function parameters, continuation parameters, exception handler
-    // parameters, etc.  Thus we do not call visitParameter directly and
-    // handle them explicitly in their parent IR node.
-    internalError(dart2js.CURRENT_ELEMENT_SPANNABLE,
-                  'tried to allocate a parameter');
-  }
-
-  void visitMutableVariable(MutableVariable node) {}
-
-  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);
-  }
-
-  // JavaScript specific nodes.
-
-  void visitSetField(SetField node) {
-    visit(node.body);
-    visitReference(node.value);
-    visitReference(node.object);
-  }
-
-  void visitGetField(GetField node) {
-    visitReference(node.object);
-  }
-
-  void visitCreateBox(CreateBox node) {
-  }
-
-  void visitCreateInstance(CreateInstance node) {
-    node.arguments.forEach(visitReference);
-  }
-
-  void visitIdentical(Identical node) {
-    visitReference(node.left);
-    visitReference(node.right);
-  }
-
-  void visitInterceptor(Interceptor node) {
-    visitReference(node.input);
-  }
-
-  void visitReifyRuntimeType(ReifyRuntimeType node) {
-    visitReference(node.value);
-  }
-
-  void visitReadTypeVariable(ReadTypeVariable node) {
-    visitReference(node.target);
-  }
-}