Move dart2js from sdk/lib/_internal/compiler to pkg/compiler

sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart

Index: sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart
diff --git a/sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart b/sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart
deleted file mode 100644
index bd95f58b00f2735768f5dfbd517aa42d437fde5e..0000000000000000000000000000000000000000
--- a/sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart
+++ /dev/null
@@ -1,716 +0,0 @@
-// Copyright (c) 2012, 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.
-
-part of ssa;
-
-/**
- * The [LiveRange] class covers a range where an instruction is live.
- */
-class LiveRange {
-  final int start;
-  // [end] is not final because it can be updated due to loops.
-  int end;
-  LiveRange(this.start, this.end) {
-    assert(start <= end);
-  }
-
-  String toString() => '[$start $end[';
-}
-
-/**
- * The [LiveInterval] class contains the list of ranges where an
- * instruction is live.
- */
-class LiveInterval {
-  /**
-   * The id where the instruction is defined.
-   */
-  int start;
-  final List<LiveRange> ranges;
-  LiveInterval() : ranges = <LiveRange>[];
-
-  // We want [HCheck] instructions to have the same name as the
-  // instruction it checks, so both instructions should share the same
-  // live ranges.
-  LiveInterval.forCheck(this.start, LiveInterval checkedInterval)
-      : ranges = checkedInterval.ranges;
-
-  /**
-   * Update all ranges that are contained in [from, to[ to
-   * die at [to].
-   */
-  void loopUpdate(int from, int to) {
-    for (LiveRange range in ranges) {
-      if (from <= range.start && range.end < to) {
-        range.end = to;
-      }
-    }
-  }
-
-  /**
-   * Add a new range to this interval.
-   */
-  void add(LiveRange interval) {
-    ranges.add(interval);
-  }
-
-  /**
-   * Returns true if one of the ranges of this interval dies at [at].
-   */
-  bool diesAt(int at) {
-    for (LiveRange range in ranges) {
-      if (range.end == at) return true;
-    }
-    return false;
-  }
-
-  String toString() {
-    List<String> res = new List<String>();
-    for (final interval in ranges) res.add(interval.toString());
-    return '(${res.join(", ")})';
-  }
-}
-
-/**
- * The [LiveEnvironment] class contains the liveIn set of a basic
- * block. A liveIn set of a block contains the instructions that are
- * live when entering that block.
- */
-class LiveEnvironment {
-  /**
-   * The instruction id where the basic block starts. See
-   * [SsaLiveIntervalBuilder.instructionId].
-   */
-  int startId;
-
-  /**
-   * The instruction id where the basic block ends.
-   */
-  final int endId;
-
-  /**
-   * Loop markers that will be updated once the loop header is
-   * visited. The liveIn set of the loop header will be merged into this
-   * environment. [loopMarkers] is a mapping from block header to the
-   * end instruction id of the loop exit block.
-   */
-  final Map<HBasicBlock, int> loopMarkers;
-
-  /**
-   * The instructions that are live in this basic block. The values of
-   * the map contain the instruction ids where the instructions die.
-   * It will be used when adding a range to the live interval of an
-   * instruction.
-   */
-  final Map<HInstruction, int> liveInstructions;
-
-  /**
-   * Map containing the live intervals of instructions.
-   */
-  final Map<HInstruction, LiveInterval> liveIntervals;
-
-  LiveEnvironment(this.liveIntervals, this.endId)
-    : liveInstructions = new Map<HInstruction, int>(),
-      loopMarkers = new Map<HBasicBlock, int>();
-
-  /**
-   * Remove an instruction from the liveIn set. This method also
-   * updates the live interval of [instruction] to contain the new
-   * range: [id, / id contained in [liveInstructions] /].
-   */
-  void remove(HInstruction instruction, int id) {
-    LiveInterval interval = liveIntervals.putIfAbsent(
-        instruction, () => new LiveInterval());
-    int lastId = liveInstructions[instruction];
-    // If [lastId] is null, then this instruction is not being used.
-    interval.add(new LiveRange(id, lastId == null ? id : lastId));
-    // The instruction is defined at [id].
-    interval.start = id;
-    liveInstructions.remove(instruction);
-  }
-
-  /**
-   * Add [instruction] to the liveIn set. If the instruction is not
-   * already in the set, we save the id where it dies.
-   */
-  void add(HInstruction instruction, int userId) {
-    // Note that we are visiting the graph in post-dominator order, so
-    // the first time we see a variable is when it dies.
-    liveInstructions.putIfAbsent(instruction, () => userId);
-  }
-
-  /**
-   * Merge this environment with [other]. Update the end id of
-   * instructions in case they are different between this and [other].
-   */
-  void mergeWith(LiveEnvironment other) {
-    other.liveInstructions.forEach((HInstruction instruction, int existingId) {
-      // If both environments have the same instruction id of where
-      // [instruction] dies, there is no need to update the live
-      // interval of [instruction]. For example the if block and the
-      // else block have the same end id for an instruction that is
-      // being used in the join block and defined before the if/else.
-      if (existingId == endId) return;
-      LiveInterval range = liveIntervals.putIfAbsent(
-          instruction, () => new LiveInterval());
-      range.add(new LiveRange(other.startId, existingId));
-      liveInstructions[instruction] = endId;
-    });
-    other.loopMarkers.forEach((k, v) { loopMarkers[k] = v; });
-  }
-
-  void addLoopMarker(HBasicBlock header, int id) {
-    assert(!loopMarkers.containsKey(header));
-    loopMarkers[header] = id;
-  }
-
-  void removeLoopMarker(HBasicBlock header) {
-    assert(loopMarkers.containsKey(header));
-    loopMarkers.remove(header);
-  }
-
-  bool get isEmpty => liveInstructions.isEmpty && loopMarkers.isEmpty;
-  bool contains(HInstruction instruction) =>
-      liveInstructions.containsKey(instruction);
-  String toString() => liveInstructions.toString();
-}
-
-/**
- * Builds the live intervals of each instruction. The algorithm visits
- * the graph post-dominator tree to find the last uses of an
- * instruction, and computes the liveIns of each basic block.
- */
-class SsaLiveIntervalBuilder extends HBaseVisitor {
-  final Compiler compiler;
-  final Set<HInstruction> generateAtUseSite;
-  final Set<HInstruction> controlFlowOperators;
-
-  /**
-   * A counter to assign start and end ids to live ranges. The initial
-   * value is not relevant. Note that instructionId goes downward to ease
-   * reasoning about live ranges (the first instruction of a graph has
-   * the lowest id).
-   */
-  int instructionId = 0;
-
-  /**
-   * The liveIns of basic blocks.
-   */
-  final Map<HBasicBlock, LiveEnvironment> liveInstructions;
-
-  /**
-   * The live intervals of instructions.
-   */
-  final Map<HInstruction, LiveInterval> liveIntervals;
-
-  SsaLiveIntervalBuilder(
-      this.compiler, this.generateAtUseSite, this.controlFlowOperators)
-    : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(),
-      liveIntervals = new Map<HInstruction, LiveInterval>();
-
-  void visitGraph(HGraph graph) {
-    visitPostDominatorTree(graph);
-    if (!liveInstructions[graph.entry].isEmpty) {
-      compiler.internalError(CURRENT_ELEMENT_SPANNABLE, 'LiveIntervalBuilder.');
-    }
-  }
-
-  void markInputsAsLiveInEnvironment(HInstruction instruction,
-                                     LiveEnvironment environment) {
-    for (int i = 0, len = instruction.inputs.length; i < len; i++) {
-      markAsLiveInEnvironment(instruction.inputs[i], environment);
-    }
-  }
-
-  // Returns the non-HCheck instruction, or the last [HCheck] in the
-  // check chain that is not generate at use site.
-  //
-  // For example:
-  //
-  //     t1 = GeneratedAtUseSite instruction
-  //     t2 = check(t1)
-  //     t3 = check(t2)
-  //     t4 = use(t3)
-  //     t5 = use(t3)
-  //     t6 = use(t2)
-  //
-  // The t1 is generate-at-use site, and the live-range must thus be on t2 and
-  // not on the checked instruction t1.
-  // When looking for the checkedInstructionOrNonGenerateAtUseSite of t3 we must
-  // return t2.
-  HInstruction checkedInstructionOrNonGenerateAtUseSite(HCheck check) {
-    var checked = check.checkedInput;
-    while (checked is HCheck) {
-      HInstruction next = checked.checkedInput;
-      if (generateAtUseSite.contains(next)) break;
-      checked = next;
-    }
-    return checked;
-  }
-
-  void markAsLiveInEnvironment(HInstruction instruction,
-                               LiveEnvironment environment) {
-    if (generateAtUseSite.contains(instruction)) {
-      markInputsAsLiveInEnvironment(instruction, environment);
-    } else {
-      environment.add(instruction, instructionId);
-      // Special case the HCheck instruction to mark the actual
-      // checked instruction live. The checked instruction and the
-      // [HCheck] will share the same live ranges.
-      if (instruction is HCheck) {
-        HCheck check = instruction;
-        HInstruction checked = checkedInstructionOrNonGenerateAtUseSite(check);
-        if (!generateAtUseSite.contains(checked)) {
-          environment.add(checked, instructionId);
-        }
-      }
-    }
-  }
-
-  void removeFromEnvironment(HInstruction instruction,
-                             LiveEnvironment environment) {
-    environment.remove(instruction, instructionId);
-    // Special case the HCheck instruction to have the same live
-    // interval as the instruction it is checking.
-    if (instruction is HCheck) {
-      HCheck check = instruction;
-      HInstruction checked = checkedInstructionOrNonGenerateAtUseSite(check);
-      if (!generateAtUseSite.contains(checked)) {
-        liveIntervals.putIfAbsent(checked, () => new LiveInterval());
-        // Unconditionally force the live ranges of the HCheck to
-        // be the live ranges of the instruction it is checking.
-        liveIntervals[instruction] =
-            new LiveInterval.forCheck(instructionId, liveIntervals[checked]);
-      }
-    }
-  }
-
-  void visitBasicBlock(HBasicBlock block) {
-    LiveEnvironment environment =
-        new LiveEnvironment(liveIntervals, instructionId);
-
-    // If the control flow instruction in this block will actually be
-    // inlined in the codegen in the join block, we need to make
-    // whatever is used by that control flow instruction as live in
-    // the join block.
-    if (controlFlowOperators.contains(block.last)) {
-      HIf ifInstruction = block.last;
-      HBasicBlock joinBlock = ifInstruction.joinBlock;
-      if (generateAtUseSite.contains(joinBlock.phis.first)) {
-        markInputsAsLiveInEnvironment(
-            ifInstruction, liveInstructions[joinBlock]);
-      }
-    }
-
-    // Add to the environment the liveIn of its successor, as well as
-    // the inputs of the phis of the successor that flow from this block.
-    for (int i = 0; i < block.successors.length; i++) {
-      HBasicBlock successor = block.successors[i];
-      LiveEnvironment successorEnv = liveInstructions[successor];
-      if (successorEnv != null) {
-        environment.mergeWith(successorEnv);
-      } else {
-        environment.addLoopMarker(successor, instructionId);
-      }
-
-      int index = successor.predecessors.indexOf(block);
-      for (HPhi phi = successor.phis.first; phi != null; phi = phi.next) {
-        markAsLiveInEnvironment(phi.inputs[index], environment);
-      }
-    }
-
-    // Iterate over all instructions to remove an instruction from the
-    // environment and add its inputs.
-    HInstruction instruction = block.last;
-    while (instruction != null) {
-      if (!generateAtUseSite.contains(instruction)) {
-        removeFromEnvironment(instruction, environment);
-        markInputsAsLiveInEnvironment(instruction, environment);
-      }
-      instructionId--;
-      instruction = instruction.previous;
-    }
-
-    // We just remove the phis from the environment. The inputs of the
-    // phis will be put in the environment of the predecessors.
-    for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
-      if (!generateAtUseSite.contains(phi)) {
-        environment.remove(phi, instructionId);
-      }
-    }
-
-    // Save the liveInstructions of that block.
-    environment.startId = instructionId + 1;
-    liveInstructions[block] = environment;
-
-    // If the block is a loop header, we can remove the loop marker,
-    // because it will just recompute the loop phis.
-    // We also check if this loop header has any back edges. If not,
-    // we know there is no loop marker for it.
-    if (block.isLoopHeader() && block.predecessors.length > 1) {
-      updateLoopMarker(block);
-    }
-  }
-
-  void updateLoopMarker(HBasicBlock header) {
-    LiveEnvironment env = liveInstructions[header];
-    int lastId = env.loopMarkers[header];
-    // Update all instructions that are liveIns in [header] to have a
-    // range that covers the loop.
-    env.liveInstructions.forEach((HInstruction instruction, int id) {
-      LiveInterval range = env.liveIntervals.putIfAbsent(
-          instruction, () => new LiveInterval());
-      range.loopUpdate(env.startId, lastId);
-      env.liveInstructions[instruction] = lastId;
-    });
-
-    env.removeLoopMarker(header);
-
-    // Update all liveIns set to contain the liveIns of [header].
-    liveInstructions.forEach((HBasicBlock block, LiveEnvironment other) {
-      if (other.loopMarkers.containsKey(header)) {
-        env.liveInstructions.forEach((HInstruction instruction, int id) {
-          other.liveInstructions[instruction] = id;
-        });
-        other.removeLoopMarker(header);
-        env.loopMarkers.forEach((k, v) { other.loopMarkers[k] = v; });
-      }
-    });
-  }
-}
-
-/**
- * Represents a copy from one instruction to another. The codegen
- * also uses this class to represent a copy from one variable to
- * another.
- */
-class Copy {
-  final source;
-  final destination;
-  Copy(this.source, this.destination);
-  String toString() => '$destination <- $source';
-}
-
-/**
- * A copy handler contains the copies that a basic block needs to do
- * after executing all its instructions.
- */
-class CopyHandler {
-  /**
-   * The copies from an instruction to a phi of the successor.
-   */
-  final List<Copy> copies;
-
-  /**
-   * Assignments from an instruction that does not need a name (e.g. a
-   * constant) to the phi of a successor.
-   */
-  final List<Copy> assignments;
-
-  CopyHandler()
-    : copies = new List<Copy>(),
-      assignments = new List<Copy>();
-
-  void addCopy(HInstruction source, HInstruction destination) {
-    copies.add(new Copy(source, destination));
-  }
-
-  void addAssignment(HInstruction source, HInstruction destination) {
-    assignments.add(new Copy(source, destination));
-  }
-
-  String toString() => 'Copies: $copies, assignments: $assignments';
-  bool get isEmpty => copies.isEmpty && assignments.isEmpty;
-}
-
-/**
- * Contains the mapping between instructions and their names for code
- * generation, as well as the [CopyHandler] for each basic block.
- */
-class VariableNames {
-  final Map<HInstruction, String> ownName;
-  final Map<HBasicBlock, CopyHandler> copyHandlers;
-
-  // Used to control heuristic that determines how local variables are declared.
-  final Set<String> allUsedNames;
-  /**
-   * Name that is used as a temporary to break cycles in
-   * parallel copies. We make sure this name is not being used
-   * anywhere by reserving it when we allocate names for instructions.
-   */
-  final String swapTemp;
-
-  String getSwapTemp() {
-    allUsedNames.add(swapTemp);
-    return swapTemp;
-  }
-
-  VariableNames()
-    : ownName = new Map<HInstruction, String>(),
-      copyHandlers = new Map<HBasicBlock, CopyHandler>(),
-      allUsedNames = new Set<String>(),
-      swapTemp = 't0';
-
-  int get numberOfVariables => allUsedNames.length;
-
-  String getName(HInstruction instruction) {
-    return ownName[instruction];
-  }
-
-  CopyHandler getCopyHandler(HBasicBlock block) {
-    return copyHandlers[block];
-  }
-
-  void addNameUsed(String name) {
-    allUsedNames.add(name);
-  }
-
-  bool hasName(HInstruction instruction) => ownName.containsKey(instruction);
-
-  void addCopy(HBasicBlock block, HInstruction source, HPhi destination) {
-    CopyHandler handler =
-        copyHandlers.putIfAbsent(block, () => new CopyHandler());
-    handler.addCopy(source, destination);
-  }
-
-  void addAssignment(HBasicBlock block, HInstruction source, HPhi destination) {
-    CopyHandler handler =
-        copyHandlers.putIfAbsent(block, () => new CopyHandler());
-    handler.addAssignment(source, destination);
-  }
-}
-
-/**
- * Allocates variable names for instructions, making sure they don't collide.
- */
-class VariableNamer {
-  final VariableNames names;
-  final Compiler compiler;
-  final Set<String> usedNames;
-  final List<String> freeTemporaryNames;
-  int temporaryIndex = 0;
-  static final RegExp regexp = new RegExp('t[0-9]+');
-
-  VariableNamer(LiveEnvironment environment,
-                this.names,
-                this.compiler)
-    : usedNames = new Set<String>(),
-      freeTemporaryNames = new List<String>() {
-    // [VariableNames.swapTemp] is used when there is a cycle in a copy handler.
-    // Therefore we make sure no one uses it.
-    usedNames.add(names.swapTemp);
-
-    // All liveIns instructions must have a name at this point, so we
-    // add them to the list of used names.
-    environment.liveInstructions.forEach((HInstruction instruction, int index) {
-      String name = names.getName(instruction);
-      if (name != null) {
-        usedNames.add(name);
-        names.addNameUsed(name);
-      }
-    });
-  }
-
-  String allocateWithHint(String originalName) {
-    int i = 0;
-    JavaScriptBackend backend = compiler.backend;
-    String name = backend.namer.safeVariableName(originalName);
-    while (usedNames.contains(name)) {
-      name = backend.namer.safeVariableName('$originalName${i++}');
-    }
-    return name;
-  }
-
-  String allocateTemporary() {
-    while (!freeTemporaryNames.isEmpty) {
-      String name = freeTemporaryNames.removeLast();
-      if (!usedNames.contains(name)) return name;
-    }
-    String name = 't${temporaryIndex++}';
-    while (usedNames.contains(name)) name = 't${temporaryIndex++}';
-    return name;
-  }
-
-  HPhi firstPhiUserWithElement(HInstruction instruction) {
-    for (HInstruction user in instruction.usedBy) {
-      if (user is HPhi && user.sourceElement != null) {
-        return user;
-      }
-    }
-    return null;
-  }
-
-  String allocateName(HInstruction instruction) {
-    String name;
-    if (instruction is HCheck) {
-      // Special case this instruction to use the name of its
-      // input if it has one.
-      var temp = instruction;
-      do {
-        temp = temp.checkedInput;
-        name = names.ownName[temp];
-      } while (name == null && temp is HCheck);
-      if (name != null) return addAllocatedName(instruction, name);
-    }
-
-    if (instruction.sourceElement != null) {
-      name = allocateWithHint(instruction.sourceElement.name);
-    } else {
-      // We could not find an element for the instruction. If the
-      // instruction is used by a phi, try to use the name of the phi.
-      // Otherwise, just allocate a temporary name.
-      HPhi phi = firstPhiUserWithElement(instruction);
-      if (phi != null) {
-        name = allocateWithHint(phi.sourceElement.name);
-      } else {
-        name = allocateTemporary();
-      }
-    }
-    return addAllocatedName(instruction, name);
-  }
-
-  String addAllocatedName(HInstruction instruction, String name) {
-    usedNames.add(name);
-    names.addNameUsed(name);
-    names.ownName[instruction] = name;
-    return name;
-  }
-
-  /**
-   * Frees [instruction]'s name so it can be used for other instructions.
-   */
-  void freeName(HInstruction instruction) {
-    String ownName = names.ownName[instruction];
-    if (ownName != null) {
-      // We check if we have already looked for temporary names
-      // because if we haven't, chances are the temporary we allocate
-      // in this block can match a phi with the same name in the
-      // successor block.
-      if (temporaryIndex != 0 && regexp.hasMatch(ownName)) {
-        freeTemporaryNames.add(ownName);
-      }
-      usedNames.remove(ownName);
-    }
-  }
-}
-
-/**
- * Visits all blocks in the graph, sets names to instructions, and
- * creates the [CopyHandler] for each block. This class needs to have
- * the liveIns set as well as all the live intervals of instructions.
- * It visits the graph in dominator order, so that at each entry of a
- * block, the instructions in its liveIns set have names.
- *
- * When visiting a block, it goes through all instructions. For each
- * instruction, it frees the names of the inputs that die at that
- * instruction, and allocates a name to the instruction. For each phi,
- * it adds a copy to the CopyHandler of the corresponding predecessor.
- */
-class SsaVariableAllocator extends HBaseVisitor {
-
-  final Compiler compiler;
-  final Map<HBasicBlock, LiveEnvironment> liveInstructions;
-  final Map<HInstruction, LiveInterval> liveIntervals;
-  final Set<HInstruction> generateAtUseSite;
-
-  final VariableNames names;
-
-  SsaVariableAllocator(this.compiler,
-                       this.liveInstructions,
-                       this.liveIntervals,
-                       this.generateAtUseSite)
-    : this.names = new VariableNames();
-
-  void visitGraph(HGraph graph) {
-    visitDominatorTree(graph);
-  }
-
-  void visitBasicBlock(HBasicBlock block) {
-    VariableNamer namer = new VariableNamer(
-        liveInstructions[block], names, compiler);
-
-    block.forEachPhi((HPhi phi) {
-      handlePhi(phi, namer);
-    });
-
-    block.forEachInstruction((HInstruction instruction) {
-      handleInstruction(instruction, namer);
-    });
-  }
-
-  /**
-   * Returns whether [instruction] needs a name. Instructions that
-   * have no users or that are generated at use site do not need a name.
-   */
-  bool needsName(instruction) {
-    if (instruction is HThis) return false;
-    if (instruction is HParameterValue) return true;
-    if (instruction.usedBy.isEmpty) return false;
-    if (generateAtUseSite.contains(instruction)) return false;
-    return !instruction.nonCheck().isCodeMotionInvariant();
-  }
-
-  /**
-   * Returns whether [instruction] dies at the instruction [at].
-   */
-  bool diesAt(HInstruction instruction, HInstruction at) {
-    LiveInterval atInterval = liveIntervals[at];
-    LiveInterval instructionInterval = liveIntervals[instruction];
-    int start = atInterval.start;
-    return instructionInterval.diesAt(start);
-  }
-
-  void freeUsedNamesAt(HInstruction instruction,
-                       HInstruction at,
-                       VariableNamer namer) {
-    if (needsName(instruction)) {
-      if (diesAt(instruction, at)) {
-        namer.freeName(instruction);
-      }
-    } else if (generateAtUseSite.contains(instruction)) {
-      // If the instruction is generated at use site, then all its
-      // inputs may also die at [at].
-      for (int i = 0, len = instruction.inputs.length; i < len; i++) {
-        HInstruction input = instruction.inputs[i];
-        freeUsedNamesAt(input, at, namer);
-      }
-    }
-  }
-
-  void handleInstruction(HInstruction instruction, VariableNamer namer) {
-    if (generateAtUseSite.contains(instruction)) {
-      assert(!liveIntervals.containsKey(instruction));
-      return;
-    }
-
-    for (int i = 0, len = instruction.inputs.length; i < len; i++) {
-      HInstruction input = instruction.inputs[i];
-      freeUsedNamesAt(input, instruction, namer);
-    }
-
-    if (needsName(instruction)) {
-      namer.allocateName(instruction);
-    }
-  }
-
-  void handlePhi(HPhi phi, VariableNamer namer) {
-    if (!needsName(phi)) return;
-
-    for (int i = 0; i < phi.inputs.length; i++) {
-      HInstruction input = phi.inputs[i];
-      HBasicBlock predecessor = phi.block.predecessors[i];
-      // A [HTypeKnown] instruction never has a name, but its checked
-      // input might, therefore we need to do a copy instead of an
-      // assignment.
-      while (input is HTypeKnown) input = input.inputs[0];
-      if (!needsName(input)) {
-        names.addAssignment(predecessor, input, phi);
-      } else {
-        names.addCopy(predecessor, input, phi);
-      }
-    }
-
-    namer.allocateName(phi);
-  }
-}