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

// 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;

  /**
   * 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)
    : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(),
      liveIntervals = new Map<HInstruction, LiveInterval>();

  void visitGraph(HGraph graph) {
    visitPostDominatorTree(graph);
    if (!liveInstructions[graph.entry].isEmpty) {
      compiler.internalError('LiveIntervalBuilder',
          node: compiler.currentElement.parseNode(compiler));
    }
  }

  void markInputsAsLiveInEnvironment(HInstruction instruction,
                                     LiveEnvironment environment) {
    for (int i = 0, len = instruction.inputs.length; i < len; i++) {
      markAsLiveInEnvironment(instruction.inputs[i], environment);
    }
  }

  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 = check.nonCheck();
        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 = check.nonCheck();
      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);

    // 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;
  /**
   * Name that is used in bailout code. We make sure this name is not being used
   * anywhere by reserving it when we allocate names for instructions.
   */
  final String stateName;

  String getSwapTemp() {
    allUsedNames.add(swapTemp);
    return swapTemp;
  }

  VariableNames()
    : ownName = new Map<HInstruction, String>(),
      copyHandlers = new Map<HBasicBlock, CopyHandler>(),
      allUsedNames = new Set<String>(),
      swapTemp = computeFreshWithPrefix("t"),
      stateName = computeFreshWithPrefix("state");

  int get numberOfVariables => allUsedNames.length;

  /** Returns a fresh variable with the given prefix. */
  static String computeFreshWithPrefix(String prefix) {
    String name = '${prefix}0';
    int i = 1;
    return name;
  }

  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);
    // [VariableNames.stateName] is being used throughout a bailout function.
    // Whenever a bailout-target is reached we set the state-variable to 0. We
    // must therefore not have any local variable that could clash with the
    // state variable.
    // Therefore we make sure no one uses it at any time.
    usedNames.add(names.stateName);

    // 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.slowToString());
    } 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.slowToString());
      } 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];
      if (!needsName(input)) {
        names.addAssignment(predecessor, input, phi);
      } else {
        names.addCopy(predecessor, input, phi);
      }
    }

    namer.allocateName(phi);
  }
}