Move frog/leg to lib/compiler/implementation.

frog/leg/ssa/bailout.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.
-
-class BailoutInfo {
-  int instructionId;
-  int bailoutId;
-  BailoutInfo(this.instructionId, this.bailoutId);
-}
-
-/**
- * Keeps track of the execution environment for instructions. An
- * execution environment contains the SSA instructions that are live.
- */
-class Environment {
-  final Set<HInstruction> lives;
-  final Set<HBasicBlock> loopMarkers;
-  Environment() : lives = new Set<HInstruction>(),
-                  loopMarkers = new Set<HBasicBlock>();
-  Environment.from(Environment other)
-    : lives = new Set<HInstruction>.from(other.lives),
-      loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
-
-  Environment.forLoopBody(Environment other)
-    : lives = new Set<HInstruction>(),
-      loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
-
-  void remove(HInstruction instruction) {
-    lives.remove(instruction);
-  }
-
-  void add(HInstruction instruction) {
-    if (!instruction.isCodeMotionInvariant()) {
-      lives.add(instruction);
-    } else {
-      for (int i = 0, len = instruction.inputs.length; i < len; i++) {
-        add(instruction.inputs[i]);
-      }
-    }
-  }
-
-  void addLoopMarker(HBasicBlock block) {
-    loopMarkers.add(block);
-  }
-
-  void removeLoopMarker(HBasicBlock block) {
-    loopMarkers.remove(block);
-  }
-
-  void addAll(Environment other) {
-    lives.addAll(other.lives);
-    loopMarkers.addAll(other.loopMarkers);
-  }
-
-  List<HInstruction> buildAndSetLast(HInstruction instruction) {
-    remove(instruction);
-    List<HInstruction> result = new List<HInstruction>.from(lives);
-    result.addLast(instruction);
-    add(instruction);
-    return result;
-  }
-
-  bool isEmpty() => lives.isEmpty();
-  bool contains(HInstruction instruction) => lives.contains(instruction);
-  bool containsLoopMarker(HBasicBlock block) => loopMarkers.contains(block);
-  void clear() => lives.clear();
-}
-
-/**
- * Computes the environment for each SSA instruction: visits the graph
- * in post-dominator order. Removes an instruction from the environment
- * and adds its inputs to the environment at the instruction's
- * definition.
- *
- * At the end of the computation, insert type guards in the graph.
- */
-class SsaTypeGuardBuilder extends HBaseVisitor implements OptimizationPhase {
-  final Compiler compiler;
-  final WorkItem work;
-  final String name = 'SsaTypeGuardBuilder';
-  Environment environment;
-  SubGraph subGraph;
-
-  final Map<HInstruction, Environment> capturedEnvironments;
-
-  SsaTypeGuardBuilder(Compiler this.compiler, WorkItem this.work)
-    : capturedEnvironments = new Map<HInstruction, Environment>();
-
-
-  void visitGraph(HGraph graph) {
-    subGraph = new SubGraph(graph.entry, graph.exit);
-    environment = new Environment();
-    visitBasicBlock(graph.entry);
-    if (!environment.isEmpty()) {
-      compiler.internalError('Bailout environment computation',
-          node: compiler.currentElement.parseNode(compiler));
-    }
-    insertCapturedEnvironments();
-  }
-
-  void maybeCaptureEnvironment(HInstruction instruction) {
-    if (shouldCaptureEnvironment(instruction)) {
-      capturedEnvironments[instruction] = new Environment.from(environment);
-    }
-  }
-
-  void visitSubGraph(SubGraph newSubGraph) {
-    SubGraph oldSubGraph = subGraph;
-    subGraph = newSubGraph;
-    visitBasicBlock(subGraph.start);
-    subGraph = oldSubGraph;
-  }
-
-  void visitBasicBlock(HBasicBlock block) {
-    if (!subGraph.contains(block)) return;
-    block.last.accept(this);
-
-    HInstruction instruction = block.last.previous;
-    while (instruction != null) {
-      HInstruction previous = instruction.previous;
-      instruction.accept(this);
-      instruction = previous;
-    }
-
-    for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
-      phi.accept(this);
-    }
-
-    if (block.isLoopHeader()) {
-      // If the block is a loop header, we need to change every uses
-      // of its loop marker to the current set of live instructions.
-      // For example with the following loop (read the example in
-      // reverse):
-      //
-      // while (true) { <-- (4) update the marker with the environment
-      //   use(x);      <-- (3) environment = {x}
-      //   bailout;     <-- (2) has the marker when computed
-      // }              <-- (1) create a loop marker
-      //
-      // The bailout instruction first captures the marker, but it
-      // will be replaced by the live environment at the loop entry,
-      // in this case {x}.
-      environment.removeLoopMarker(block);
-      capturedEnvironments.forEach((instruction, env) {
-        if (env.containsLoopMarker(block)) {
-          env.removeLoopMarker(block);
-          env.addAll(environment);
-        }
-      });
-    }
-  }
-
-  void visitPhi(HPhi phi) {
-    maybeCaptureEnvironment(phi);
-    environment.remove(phi);
-    // If the block is a loop header, we insert the incoming values of
-    // the phis, and remove the loop values.
-    // If the block is not a loop header, the phi will be handled by
-    // the control flow instruction.
-    if (phi.block.isLoopHeader()) {
-      environment.add(phi.inputs[0]);
-      for (int i = 1, len = phi.inputs.length; i < len; i++) {
-        environment.remove(phi.inputs[i]);
-      }
-    }
-  }
-
-  void visitInstruction(HInstruction instruction) {
-    maybeCaptureEnvironment(instruction);
-    environment.remove(instruction);
-    for (int i = 0, len = instruction.inputs.length; i < len; i++) {
-      environment.add(instruction.inputs[i]);
-    }
-  }
-
-  void visitIf(HIf instruction) {
-    HIfBlockInformation info = instruction.blockInformation;
-    HBasicBlock joinBlock = info.joinBlock;
-
-    if (joinBlock != null) {
-      visitBasicBlock(joinBlock);
-    }
-    Environment thenEnvironment = new Environment.from(environment);
-    Environment elseEnvironment = environment;
-
-    if (joinBlock != null) {
-      for (HPhi phi = joinBlock.phis.first; phi != null; phi = phi.next) {
-        if (joinBlock.predecessors[0] == instruction.block) {
-          // We're dealing with an 'if' without an else branch.
-          thenEnvironment.add(phi.inputs[1]);
-          elseEnvironment.add(phi.inputs[0]);
-        } else {
-          thenEnvironment.add(phi.inputs[0]);
-          elseEnvironment.add(phi.inputs[1]);
-        }
-      }
-    }
-
-    if (instruction.hasElse) {
-      environment = elseEnvironment;
-      visitSubGraph(info.elseGraph);
-      elseEnvironment = environment;
-    }
-
-    environment = thenEnvironment;
-    visitSubGraph(info.thenGraph);
-    environment.addAll(elseEnvironment);
-  }
-
-  void visitGoto(HGoto goto) {
-    HBasicBlock block = goto.block;
-    if (block.successors[0].dominator != block) return;
-    visitBasicBlock(block.successors[0]);
-  }
-
-  void visitBreak(HBreak breakInstruction) {
-    compiler.unimplemented("SsaEnvironmentBuilder.visitBreak");
-  }
-
-  void visitLoopBranch(HLoopBranch branch) {
-    HBasicBlock block = branch.block;
-
-    // Visit the code after the loop.
-    visitBasicBlock(block.successors[1]);
-
-    Environment joinEnvironment = environment;
-
-    // When visiting the loop body, we don't require the live
-    // instructions after the loop body to be in the environment. They
-    // will be either recomputed in the loop header, or inserted
-    // with the loop marker. We still need to transfer existing loop
-    // markers from the current environment, because they must be live
-    // for this loop body.
-    environment = new Environment.forLoopBody(environment);
-
-    // Put the loop phis in the environment.
-    HBasicBlock header = block.isLoopHeader() ? block : block.parentLoopHeader;
-    for (HPhi phi = header.phis.first; phi != null; phi = phi.next) {
-      for (int i = 1, len = phi.inputs.length; i < len; i++) {
-        environment.add(phi.inputs[i]);
-      }
-    }
-
-    // Add the loop marker
-    environment.addLoopMarker(header);
-
-    if (!branch.isDoWhile()) {
-      assert(block.successors[0] == block.dominatedBlocks[0]);
-      visitBasicBlock(block.successors[0]);
-    }
-
-    // We merge the environment required by the code after the loop,
-    // and the code inside the loop.
-    environment.addAll(joinEnvironment);
-  }
-
-  // Deal with all kinds of control flow instructions. In case we add
-  // a new one, we will hit an internal error.
-  void visitExit(HExit exit) {}
-
-  void visitReturn(HReturn instruction) {
-    environment.clear();
-    visitInstruction(instruction);
-  }
-
-  void visitThrow(HThrow instruction) {
-    environment.clear();
-    visitInstruction(instruction);
-  }
-
-  void visitControlFlow(HControlFlow instruction) {
-    compiler.internalError('Control flow instructions already dealt with.',
-                           instruction: instruction);
-  }
-
-  bool shouldCaptureEnvironment(HInstruction instruction) {
-    return instruction.type.isKnown() && !instruction.hasExpectedType();
-  }
-
-  void insertCapturedEnvironments() {
-    work.guards = <HTypeGuard>[];
-    int state = 1;
-    capturedEnvironments.forEach((HInstruction instruction, Environment env) {
-      List<HInstruction> inputs = env.buildAndSetLast(instruction);
-      HTypeGuard guard = new HTypeGuard(state++, inputs);
-      work.guards.add(guard);
-      instruction.block.rewrite(instruction, guard);
-      HInstruction insertionPoint = (instruction is HPhi)
-          ? instruction.block.first
-          : instruction.next;
-      insertionPoint.block.addBefore(insertionPoint, guard);
-    });
-  }
-}
-
-/**
- * Propagates bailout information to blocks that need it. This visitor
- * is run before codegen, to know which blocks have to deal with
- * bailouts.
- */
-class SsaBailoutPropagator extends HBaseVisitor {
-  final Compiler compiler;
-  final List<HBasicBlock> blocks;
-
-  SsaBailoutPropagator(Compiler this.compiler) : blocks = <HBasicBlock>[];
-
-  void visitGraph(HGraph graph) {
-    blocks.addLast(graph.entry);
-    visitBasicBlock(graph.entry);
-  }
-
-  void visitBasicBlock(HBasicBlock block) {
-    if (block.isLoopHeader()) blocks.addLast(block);
-    HInstruction instruction = block.first;
-    while (instruction != null) {
-      instruction.accept(this);
-      instruction = instruction.next;
-    }
-  }
-
-  void enterBlock(HBasicBlock block) {
-    if (block == null) return;
-    blocks.addLast(block);
-    visitBasicBlock(block);
-    blocks.removeLast();
-  }
-
-  void visitIf(HIf instruction) {
-    enterBlock(instruction.thenBlock);
-    enterBlock(instruction.elseBlock);
-    enterBlock(instruction.joinBlock);
-  }
-
-  void visitGoto(HGoto goto) {
-    HBasicBlock block = goto.block;
-    if (block.successors[0].dominator != block) return;
-    visitBasicBlock(block.successors[0]);
-  }
-
-  void visitLoopBranch(HLoopBranch branch) {
-    HBasicBlock branchBlock = branch.block;
-    if (!branch.isDoWhile()) {
-      // Not a do while loop. We visit the body of the loop.
-      visitBasicBlock(branchBlock.dominatedBlocks[0]);
-    }
-    blocks.removeLast();
-    visitBasicBlock(branchBlock.successors[1]);
-  }
-
-  // Deal with all kinds of control flow instructions. In case we add
-  // a new one, we will hit an internal error.
-  void visitExit(HExit exit) {}
-  void visitReturn(HReturn instruction) {}
-  void visitThrow(HThrow instruction) {}
-
-  void visitControlFlow(HControlFlow instruction) {
-    compiler.internalError('Control flow instructions already dealt with.',
-                           instruction: instruction);
-  }
-
-  visitTypeGuard(HTypeGuard guard) {
-    blocks.forEach((HBasicBlock block) {
-      block.guards.add(guard);
-    });
-  }
-}