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

abstract class HVisitor<R> {
  R visitAdd(HAdd node);
  R visitBailoutTarget(HBailoutTarget node);
  R visitBitAnd(HBitAnd node);
  R visitBitNot(HBitNot node);
  R visitBitOr(HBitOr node);
  R visitBitXor(HBitXor node);
  R visitBoolify(HBoolify node);
  R visitBoundsCheck(HBoundsCheck node);
  R visitBreak(HBreak node);
  R visitConstant(HConstant node);
  R visitContinue(HContinue node);
  R visitDivide(HDivide node);
  R visitEquals(HEquals node);
  R visitExit(HExit node);
  R visitExitTry(HExitTry node);
  R visitFieldGet(HFieldGet node);
  R visitFieldSet(HFieldSet node);
  R visitForeign(HForeign node);
  R visitForeignNew(HForeignNew node);
  R visitGoto(HGoto node);
  R visitGreater(HGreater node);
  R visitGreaterEqual(HGreaterEqual node);
  R visitIdentity(HIdentity node);
  R visitIf(HIf node);
  R visitIndex(HIndex node);
  R visitIndexAssign(HIndexAssign node);
  R visitIntegerCheck(HIntegerCheck node);
  R visitInterceptor(HInterceptor node);
  R visitInvokeClosure(HInvokeClosure node);
  R visitInvokeDynamicGetter(HInvokeDynamicGetter node);
  R visitInvokeDynamicMethod(HInvokeDynamicMethod node);
  R visitInvokeDynamicSetter(HInvokeDynamicSetter node);
  R visitInvokeStatic(HInvokeStatic node);
  R visitInvokeSuper(HInvokeSuper node);
  R visitIs(HIs node);
  R visitLazyStatic(HLazyStatic node);
  R visitLess(HLess node);
  R visitLessEqual(HLessEqual node);
  R visitLiteralList(HLiteralList node);
  R visitLocalGet(HLocalGet node);
  R visitLocalSet(HLocalSet node);
  R visitLocalValue(HLocalValue node);
  R visitLoopBranch(HLoopBranch node);
  R visitModulo(HModulo node);
  R visitMultiply(HMultiply node);
  R visitNegate(HNegate node);
  R visitNot(HNot node);
  R visitParameterValue(HParameterValue node);
  R visitPhi(HPhi node);
  R visitRangeConversion(HRangeConversion node);
  R visitReturn(HReturn node);
  R visitShiftLeft(HShiftLeft node);
  R visitShiftRight(HShiftRight node);
  R visitStatic(HStatic node);
  R visitStaticStore(HStaticStore node);
  R visitStringConcat(HStringConcat node);
  R visitSubtract(HSubtract node);
  R visitSwitch(HSwitch node);
  R visitThis(HThis node);
  R visitThrow(HThrow node);
  R visitTruncatingDivide(HTruncatingDivide node);
  R visitTry(HTry node);
  R visitTypeGuard(HTypeGuard node);
  R visitTypeConversion(HTypeConversion node);
}

abstract class HGraphVisitor {
  visitDominatorTree(HGraph graph) {
    void visitBasicBlockAndSuccessors(HBasicBlock block) {
      visitBasicBlock(block);
      List dominated = block.dominatedBlocks;
      for (int i = 0; i < dominated.length; i++) {
        visitBasicBlockAndSuccessors(dominated[i]);
      }
    }

    visitBasicBlockAndSuccessors(graph.entry);
  }

  visitPostDominatorTree(HGraph graph) {
    void visitBasicBlockAndSuccessors(HBasicBlock block) {
      List dominated = block.dominatedBlocks;
      for (int i = dominated.length - 1; i >= 0; i--) {
        visitBasicBlockAndSuccessors(dominated[i]);
      }
      visitBasicBlock(block);
    }

    visitBasicBlockAndSuccessors(graph.entry);
  }

  visitBasicBlock(HBasicBlock block);
}

abstract class HInstructionVisitor extends HGraphVisitor {
  HBasicBlock currentBlock;

  visitInstruction(HInstruction node);

  visitBasicBlock(HBasicBlock node) {
    void visitInstructionList(HInstructionList list) {
      HInstruction instruction = list.first;
      while (instruction != null) {
        visitInstruction(instruction);
        instruction = instruction.next;
        assert(instruction != list.first);
      }
    }

    currentBlock = node;
    visitInstructionList(node);
  }
}

class HGraph {
  HBasicBlock entry;
  HBasicBlock exit;
  bool isRecursiveMethod = false;
  bool calledInLoop = false;
  final List<HBasicBlock> blocks;

  // We canonicalize all constants used within a graph so we do not
  // have to worry about them for global value numbering.
  Map<Constant, HConstant> constants;

  HGraph()
      : blocks = new List<HBasicBlock>(),
        constants = new Map<Constant, HConstant>() {
    entry = addNewBlock();
    // The exit block will be added later, so it has an id that is
    // after all others in the system.
    exit = new HBasicBlock();
  }

  void addBlock(HBasicBlock block) {
    int id = blocks.length;
    block.id = id;
    blocks.add(block);
    assert(identical(blocks[id], block));
  }

  HBasicBlock addNewBlock() {
    HBasicBlock result = new HBasicBlock();
    addBlock(result);
    return result;
  }

  HBasicBlock addNewLoopHeaderBlock(TargetElement target,
                                    List<LabelElement> labels) {
    HBasicBlock result = addNewBlock();
    result.loopInformation =
        new HLoopInformation(result, target, labels);
    return result;
  }

  static HType mapConstantTypeToSsaType(Constant constant) {
    if (constant.isNull()) return HType.NULL;
    if (constant.isBool()) return HType.BOOLEAN;
    if (constant.isInt()) return HType.INTEGER;
    if (constant.isDouble()) return HType.DOUBLE;
    if (constant.isString()) return HType.STRING;
    if (constant.isList()) return HType.READABLE_ARRAY;
    if (constant.isFunction()) return HType.UNKNOWN;
    if (constant.isSentinel()) return HType.UNKNOWN;
    ObjectConstant objectConstant = constant;
    return new HBoundedType.exact(objectConstant.type);
  }

  HConstant addConstant(Constant constant) {
    HConstant result = constants[constant];
    if (result == null) {
      HType type = mapConstantTypeToSsaType(constant);
      result = new HConstant.internal(constant, type);
      entry.addAtExit(result);
      constants[constant] = result;
    }
    return result;
  }

  HConstant addConstantInt(int i, ConstantSystem constantSystem) {
    return addConstant(constantSystem.createInt(i));
  }

  HConstant addConstantDouble(double d, ConstantSystem constantSystem) {
    return addConstant(constantSystem.createDouble(d));
  }

  HConstant addConstantString(DartString str,
                              Node diagnosticNode,
                              ConstantSystem constantSystem) {
    return addConstant(constantSystem.createString(str, diagnosticNode));
  }

  HConstant addConstantBool(bool value, ConstantSystem constantSystem) {
    return addConstant(constantSystem.createBool(value));
  }

  HConstant addConstantNull(ConstantSystem constantSystem) {
    return addConstant(constantSystem.createNull());
  }

  void finalize() {
    addBlock(exit);
    exit.open();
    exit.close(new HExit());
    assignDominators();
  }

  void assignDominators() {
    // Run through the blocks in order of increasing ids so we are
    // guaranteed that we have computed dominators for all blocks
    // higher up in the dominator tree.
    for (int i = 0, length = blocks.length; i < length; i++) {
      HBasicBlock block = blocks[i];
      List<HBasicBlock> predecessors = block.predecessors;
      if (block.isLoopHeader()) {
        block.assignCommonDominator(predecessors[0]);
      } else {
        for (int j = predecessors.length - 1; j >= 0; j--) {
          block.assignCommonDominator(predecessors[j]);
        }
      }
    }
  }

  bool isValid() {
    HValidator validator = new HValidator();
    validator.visitGraph(this);
    return validator.isValid;
  }
}

class HBaseVisitor extends HGraphVisitor implements HVisitor {
  HBasicBlock currentBlock;

  visitBasicBlock(HBasicBlock node) {
    currentBlock = node;

    HInstruction instruction = node.first;
    while (instruction != null) {
      instruction.accept(this);
      instruction = instruction.next;
    }
  }

  visitInstruction(HInstruction instruction) {}

  visitBinaryArithmetic(HBinaryArithmetic node) => visitInvokeBinary(node);
  visitBinaryBitOp(HBinaryBitOp node) => visitBinaryArithmetic(node);
  visitInvoke(HInvoke node) => visitInstruction(node);
  visitInvokeBinary(HInvokeBinary node) => visitInvokeStatic(node);
  visitInvokeDynamic(HInvokeDynamic node) => visitInvoke(node);
  visitInvokeDynamicField(HInvokeDynamicField node) => visitInvokeDynamic(node);
  visitInvokeUnary(HInvokeUnary node) => visitInvokeStatic(node);
  visitConditionalBranch(HConditionalBranch node) => visitControlFlow(node);
  visitControlFlow(HControlFlow node) => visitInstruction(node);
  visitFieldAccess(HFieldAccess node) => visitInstruction(node);
  visitRelational(HRelational node) => visitInvokeBinary(node);

  visitAdd(HAdd node) => visitBinaryArithmetic(node);
  visitBailoutTarget(HBailoutTarget node) => visitInstruction(node);
  visitBitAnd(HBitAnd node) => visitBinaryBitOp(node);
  visitBitNot(HBitNot node) => visitInvokeUnary(node);
  visitBitOr(HBitOr node) => visitBinaryBitOp(node);
  visitBitXor(HBitXor node) => visitBinaryBitOp(node);
  visitBoolify(HBoolify node) => visitInstruction(node);
  visitBoundsCheck(HBoundsCheck node) => visitCheck(node);
  visitBreak(HBreak node) => visitJump(node);
  visitContinue(HContinue node) => visitJump(node);
  visitCheck(HCheck node) => visitInstruction(node);
  visitConstant(HConstant node) => visitInstruction(node);
  visitDivide(HDivide node) => visitBinaryArithmetic(node);
  visitEquals(HEquals node) => visitRelational(node);
  visitExit(HExit node) => visitControlFlow(node);
  visitExitTry(HExitTry node) => visitControlFlow(node);
  visitFieldGet(HFieldGet node) => visitFieldAccess(node);
  visitFieldSet(HFieldSet node) => visitFieldAccess(node);
  visitForeign(HForeign node) => visitInstruction(node);
  visitForeignNew(HForeignNew node) => visitForeign(node);
  visitGoto(HGoto node) => visitControlFlow(node);
  visitGreater(HGreater node) => visitRelational(node);
  visitGreaterEqual(HGreaterEqual node) => visitRelational(node);
  visitIdentity(HIdentity node) => visitRelational(node);
  visitIf(HIf node) => visitConditionalBranch(node);
  visitIndex(HIndex node) => visitInvokeStatic(node);
  visitIndexAssign(HIndexAssign node) => visitInvokeStatic(node);
  visitIntegerCheck(HIntegerCheck node) => visitCheck(node);
  visitInterceptor(HInterceptor node) => visitInstruction(node);
  visitInvokeClosure(HInvokeClosure node)
      => visitInvokeDynamic(node);
  visitInvokeDynamicMethod(HInvokeDynamicMethod node)
      => visitInvokeDynamic(node);
  visitInvokeDynamicGetter(HInvokeDynamicGetter node)
      => visitInvokeDynamicField(node);
  visitInvokeDynamicSetter(HInvokeDynamicSetter node)
      => visitInvokeDynamicField(node);
  visitInvokeStatic(HInvokeStatic node) => visitInvoke(node);
  visitInvokeSuper(HInvokeSuper node) => visitInvoke(node);
  visitJump(HJump node) => visitControlFlow(node);
  visitLazyStatic(HLazyStatic node) => visitStatic(node);
  visitLess(HLess node) => visitRelational(node);
  visitLessEqual(HLessEqual node) => visitRelational(node);
  visitLiteralList(HLiteralList node) => visitInstruction(node);
  visitLocalGet(HLocalGet node) => visitFieldGet(node);
  visitLocalSet(HLocalSet node) => visitFieldSet(node);
  visitLocalValue(HLocalValue node) => visitInstruction(node);
  visitLoopBranch(HLoopBranch node) => visitConditionalBranch(node);
  visitModulo(HModulo node) => visitBinaryArithmetic(node);
  visitNegate(HNegate node) => visitInvokeUnary(node);
  visitNot(HNot node) => visitInstruction(node);
  visitPhi(HPhi node) => visitInstruction(node);
  visitMultiply(HMultiply node) => visitBinaryArithmetic(node);
  visitParameterValue(HParameterValue node) => visitLocalValue(node);
  visitRangeConversion(HRangeConversion node) => visitCheck(node);
  visitReturn(HReturn node) => visitControlFlow(node);
  visitShiftRight(HShiftRight node) => visitBinaryBitOp(node);
  visitShiftLeft(HShiftLeft node) => visitBinaryBitOp(node);
  visitSubtract(HSubtract node) => visitBinaryArithmetic(node);
  visitSwitch(HSwitch node) => visitControlFlow(node);
  visitStatic(HStatic node) => visitInstruction(node);
  visitStaticStore(HStaticStore node) => visitInstruction(node);
  visitStringConcat(HStringConcat node) => visitInstruction(node);
  visitThis(HThis node) => visitParameterValue(node);
  visitThrow(HThrow node) => visitControlFlow(node);
  visitTry(HTry node) => visitControlFlow(node);
  visitTruncatingDivide(HTruncatingDivide node) => visitBinaryArithmetic(node);
  visitTypeGuard(HTypeGuard node) => visitCheck(node);
  visitIs(HIs node) => visitInstruction(node);
  visitTypeConversion(HTypeConversion node) => visitCheck(node);
}

class SubGraph {
  // The first and last block of the sub-graph.
  final HBasicBlock start;
  final HBasicBlock end;

  const SubGraph(this.start, this.end);

  bool contains(HBasicBlock block) {
    assert(start != null);
    assert(end != null);
    assert(block != null);
    return start.id <= block.id && block.id <= end.id;
  }
}

class SubExpression extends SubGraph {
  const SubExpression(HBasicBlock start, HBasicBlock end)
      : super(start, end);

  /** Find the condition expression if this sub-expression is a condition. */
  HInstruction get conditionExpression {
    HInstruction last = end.last;
    if (last is HConditionalBranch || last is HSwitch) return last.inputs[0];
    return null;
  }
}

class HInstructionList {
  HInstruction first = null;
  HInstruction last = null;

  bool get isEmpty {
    return first == null;
  }

  void addAfter(HInstruction cursor, HInstruction instruction) {
    if (cursor == null) {
      assert(isEmpty);
      first = last = instruction;
    } else if (identical(cursor, last)) {
      last.next = instruction;
      instruction.previous = last;
      last = instruction;
    } else {
      instruction.previous = cursor;
      instruction.next = cursor.next;
      cursor.next.previous = instruction;
      cursor.next = instruction;
    }
  }

  void addBefore(HInstruction cursor, HInstruction instruction) {
    if (cursor == null) {
      assert(isEmpty);
      first = last = instruction;
    } else if (identical(cursor, first)) {
      first.previous = instruction;
      instruction.next = first;
      first = instruction;
    } else {
      instruction.next = cursor;
      instruction.previous = cursor.previous;
      cursor.previous.next = instruction;
      cursor.previous = instruction;
    }
  }

  void detach(HInstruction instruction) {
    assert(contains(instruction));
    assert(instruction.isInBasicBlock());
    if (instruction.previous == null) {
      first = instruction.next;
    } else {
      instruction.previous.next = instruction.next;
    }
    if (instruction.next == null) {
      last = instruction.previous;
    } else {
      instruction.next.previous = instruction.previous;
    }
    instruction.previous = null;
    instruction.next = null;
  }

  void remove(HInstruction instruction) {
    assert(instruction.usedBy.isEmpty);
    detach(instruction);
  }

  /** Linear search for [instruction]. */
  bool contains(HInstruction instruction) {
    HInstruction cursor = first;
    while (cursor != null) {
      if (identical(cursor, instruction)) return true;
      cursor = cursor.next;
    }
    return false;
  }
}

class HBasicBlock extends HInstructionList {
  // The [id] must be such that any successor's id is greater than
  // this [id]. The exception are back-edges.
  int id;

  static const int STATUS_NEW = 0;
  static const int STATUS_OPEN = 1;
  static const int STATUS_CLOSED = 2;
  int status = STATUS_NEW;

  HInstructionList phis;

  HLoopInformation loopInformation = null;
  HBlockFlow blockFlow = null;
  HBasicBlock parentLoopHeader = null;
  List<HBailoutTarget> bailoutTargets;

  final List<HBasicBlock> predecessors;
  List<HBasicBlock> successors;

  HBasicBlock dominator = null;
  final List<HBasicBlock> dominatedBlocks;

  HBasicBlock() : this.withId(null);
  HBasicBlock.withId(this.id)
      : phis = new HInstructionList(),
        predecessors = <HBasicBlock>[],
        successors = const <HBasicBlock>[],
        dominatedBlocks = <HBasicBlock>[],
        bailoutTargets = <HBailoutTarget>[];

  int get hashCode => id;

  bool isNew() => status == STATUS_NEW;
  bool isOpen() => status == STATUS_OPEN;
  bool isClosed() => status == STATUS_CLOSED;

  bool isLoopHeader() {
    return loopInformation != null;
  }

  void setBlockFlow(HBlockInformation blockInfo, HBasicBlock continuation) {
    blockFlow = new HBlockFlow(blockInfo, continuation);
  }

  bool isLabeledBlock() =>
    blockFlow != null &&
    blockFlow.body is HLabeledBlockInformation;

  HBasicBlock get enclosingLoopHeader {
    if (isLoopHeader()) return this;
    return parentLoopHeader;
  }

  bool hasBailoutTargets() => !bailoutTargets.isEmpty;

  void open() {
    assert(isNew());
    status = STATUS_OPEN;
  }

  void close(HControlFlow end) {
    assert(isOpen());
    addAfter(last, end);
    status = STATUS_CLOSED;
  }

  void addAtEntry(HInstruction instruction) {
    assert(instruction is !HPhi);
    super.addBefore(first, instruction);
    instruction.notifyAddedToBlock(this);
  }

  void addAtExit(HInstruction instruction) {
    assert(isClosed());
    assert(last is HControlFlow);
    assert(instruction is !HPhi);
    super.addBefore(last, instruction);
    instruction.notifyAddedToBlock(this);
  }

  void moveAtExit(HInstruction instruction) {
    assert(instruction is !HPhi);
    assert(instruction.isInBasicBlock());
    assert(isClosed());
    assert(last is HControlFlow);
    super.addBefore(last, instruction);
    instruction.block = this;
    assert(isValid());
  }

  void add(HInstruction instruction) {
    assert(instruction is !HControlFlow);
    assert(instruction is !HPhi);
    super.addAfter(last, instruction);
    instruction.notifyAddedToBlock(this);
  }

  void addPhi(HPhi phi) {
    phis.addAfter(phis.last, phi);
    phi.notifyAddedToBlock(this);
  }

  void removePhi(HPhi phi) {
    phis.remove(phi);
    assert(phi.block == this);
    phi.notifyRemovedFromBlock();
  }

  void addAfter(HInstruction cursor, HInstruction instruction) {
    assert(cursor is !HPhi);
    assert(instruction is !HPhi);
    assert(isOpen() || isClosed());
    super.addAfter(cursor, instruction);
    instruction.notifyAddedToBlock(this);
  }

  void addBefore(HInstruction cursor, HInstruction instruction) {
    assert(cursor is !HPhi);
    assert(instruction is !HPhi);
    assert(isOpen() || isClosed());
    super.addBefore(cursor, instruction);
    instruction.notifyAddedToBlock(this);
  }

  void remove(HInstruction instruction) {
    assert(isOpen() || isClosed());
    assert(instruction is !HPhi);
    super.remove(instruction);
    assert(instruction.block == this);
    instruction.notifyRemovedFromBlock();
  }

  void addSuccessor(HBasicBlock block) {
    if (successors.isEmpty) {
      successors = [block];
    } else {
      successors.add(block);
    }
    block.predecessors.add(this);
  }

  void postProcessLoopHeader() {
    assert(isLoopHeader());
    // Only the first entry into the loop is from outside the
    // loop. All other entries must be back edges.
    for (int i = 1, length = predecessors.length; i < length; i++) {
      loopInformation.addBackEdge(predecessors[i]);
    }
  }

  /**
   * Rewrites all uses of the [from] instruction to using the [to]
   * instruction instead.
   */
  void rewrite(HInstruction from, HInstruction to) {
    for (HInstruction use in from.usedBy) {
      use.rewriteInput(from, to);
    }
    to.usedBy.addAll(from.usedBy);
    from.usedBy.clear();
  }

  /**
   * Rewrites all uses of the [from] instruction to using either the
   * [to] instruction, or a [HCheck] instruction that has better type
   * information on [to], and that dominates the user.
   */
  void rewriteWithBetterUser(HInstruction from, HInstruction to) {
    Link<HCheck> better = const Link<HCheck>();
    for (HInstruction user in to.usedBy) {
      if (user is HCheck && identical((user as HCheck).checkedInput, to)) {
        better = better.prepend(user);
      }
    }

    if (better.isEmpty) return rewrite(from, to);

    L1: for (HInstruction user in from.usedBy) {
      for (HCheck check in better) {
        if (check.dominates(user)) {
          user.rewriteInput(from, check);
          check.usedBy.add(user);
          continue L1;
        }
      }
      user.rewriteInput(from, to);
      to.usedBy.add(user);
    }
    from.usedBy.clear();
  }

  bool isExitBlock() {
    return identical(first, last) && first is HExit;
  }

  void addDominatedBlock(HBasicBlock block) {
    assert(isClosed());
    assert(id != null && block.id != null);
    assert(dominatedBlocks.indexOf(block) < 0);
    // Keep the list of dominated blocks sorted such that if there are two
    // succeeding blocks in the list, the predecessor is before the successor.
    // Assume that we add the dominated blocks in the right order.
    int index = dominatedBlocks.length;
    while (index > 0 && dominatedBlocks[index - 1].id > block.id) {
      index--;
    }
    if (index == dominatedBlocks.length) {
      dominatedBlocks.add(block);
    } else {
      dominatedBlocks.insertRange(index, 1, block);
    }
    assert(block.dominator == null);
    block.dominator = this;
  }

  void removeDominatedBlock(HBasicBlock block) {
    assert(isClosed());
    assert(id != null && block.id != null);
    int index = dominatedBlocks.indexOf(block);
    assert(index >= 0);
    if (index == dominatedBlocks.length - 1) {
      dominatedBlocks.removeLast();
    } else {
      dominatedBlocks.removeRange(index, 1);
    }
    assert(identical(block.dominator, this));
    block.dominator = null;
  }

  void assignCommonDominator(HBasicBlock predecessor) {
    assert(isClosed());
    if (dominator == null) {
      // If this basic block doesn't have a dominator yet we use the
      // given predecessor as the dominator.
      predecessor.addDominatedBlock(this);
    } else if (predecessor.dominator != null) {
      // If the predecessor has a dominator and this basic block has a
      // dominator, we find a common parent in the dominator tree and
      // use that as the dominator.
      HBasicBlock block0 = dominator;
      HBasicBlock block1 = predecessor;
      while (!identical(block0, block1)) {
        if (block0.id > block1.id) {
          block0 = block0.dominator;
        } else {
          block1 = block1.dominator;
        }
        assert(block0 != null && block1 != null);
      }
      if (!identical(dominator, block0)) {
        dominator.removeDominatedBlock(this);
        block0.addDominatedBlock(this);
      }
    }
  }

  void forEachPhi(void f(HPhi phi)) {
    HPhi current = phis.first;
    while (current != null) {
      HInstruction saved = current.next;
      f(current);
      current = saved;
    }
  }

  void forEachInstruction(void f(HInstruction instruction)) {
    HInstruction current = first;
    while (current != null) {
      HInstruction saved = current.next;
      f(current);
      current = saved;
    }
  }

  bool isValid() {
    assert(isClosed());
    HValidator validator = new HValidator();
    validator.visitBasicBlock(this);
    return validator.isValid;
  }

  // TODO(ngeoffray): Cache the information if this method ends up
  // being hot.
  bool dominates(HBasicBlock other) {
    do {
      if (identical(this, other)) return true;
      other = other.dominator;
    } while (other != null && other.id >= id);
    return false;
  }
}


abstract class HInstruction implements Spannable {
  Element sourceElement;
  SourceFileLocation sourcePosition;

  final int id;
  static int idCounter;

  final List<HInstruction> inputs;
  final List<HInstruction> usedBy;

  HBasicBlock block;
  HInstruction previous = null;
  HInstruction next = null;
  int flags = 0;

  // Changes flags.
  static const int FLAG_CHANGES_INDEX = 0;
  static const int FLAG_CHANGES_INSTANCE_PROPERTY = FLAG_CHANGES_INDEX + 1;
  static const int FLAG_CHANGES_STATIC_PROPERTY
      = FLAG_CHANGES_INSTANCE_PROPERTY + 1;
  static const int FLAG_CHANGES_SOMETHING = FLAG_CHANGES_STATIC_PROPERTY + 1;
  static const int FLAG_CHANGES_COUNT = FLAG_CHANGES_SOMETHING + 1;

  // Depends flags (one for each changes flag).
  static const int FLAG_DEPENDS_ON_INDEX_STORE = FLAG_CHANGES_COUNT;
  static const int FLAG_DEPENDS_ON_INSTANCE_PROPERTY_STORE =
      FLAG_DEPENDS_ON_INDEX_STORE + 1;
  static const int FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE =
      FLAG_DEPENDS_ON_INSTANCE_PROPERTY_STORE + 1;
  static const int FLAG_DEPENDS_ON_SOMETHING =
      FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE + 1;

  // Other flags.
  static const int FLAG_USE_GVN = FLAG_DEPENDS_ON_SOMETHING + 1;

  // Type codes.
  static const int UNDEFINED_TYPECODE = -1;
  static const int BOOLIFY_TYPECODE = 0;
  static const int TYPE_GUARD_TYPECODE = 1;
  static const int BOUNDS_CHECK_TYPECODE = 2;
  static const int INTEGER_CHECK_TYPECODE = 3;
  static const int INTERCEPTOR_TYPECODE = 4;
  static const int ADD_TYPECODE = 5;
  static const int DIVIDE_TYPECODE = 6;
  static const int MODULO_TYPECODE = 7;
  static const int MULTIPLY_TYPECODE = 8;
  static const int SUBTRACT_TYPECODE = 9;
  static const int TRUNCATING_DIVIDE_TYPECODE = 10;
  static const int SHIFT_LEFT_TYPECODE = 11;
  static const int SHIFT_RIGHT_TYPECODE = 12;
  static const int BIT_OR_TYPECODE = 13;
  static const int BIT_AND_TYPECODE = 14;
  static const int BIT_XOR_TYPECODE = 15;
  static const int NEGATE_TYPECODE = 16;
  static const int BIT_NOT_TYPECODE = 17;
  static const int NOT_TYPECODE = 18;
  static const int EQUALS_TYPECODE = 19;
  static const int IDENTITY_TYPECODE = 20;
  static const int GREATER_TYPECODE = 21;
  static const int GREATER_EQUAL_TYPECODE = 22;
  static const int LESS_TYPECODE = 23;
  static const int LESS_EQUAL_TYPECODE = 24;
  static const int STATIC_TYPECODE = 25;
  static const int STATIC_STORE_TYPECODE = 26;
  static const int FIELD_GET_TYPECODE = 27;
  static const int TYPE_CONVERSION_TYPECODE = 28;
  static const int BAILOUT_TARGET_TYPECODE = 29;
  static const int INVOKE_STATIC_TYPECODE = 30;
  static const int INVOKE_DYNAMIC_GETTER_TYPECODE = 31;
  static const int INDEX_TYPECODE = 32;

  HInstruction(this.inputs)
      : id = idCounter++,
        usedBy = <HInstruction>[];

  int get hashCode => id;

  bool getFlag(int position) => (flags & (1 << position)) != 0;
  void setFlag(int position) { flags |= (1 << position); }
  void clearFlag(int position) { flags &= ~(1 << position); }

  static int computeDependsOnFlags(int flags) => flags << FLAG_CHANGES_COUNT;

  int getChangesFlags() => flags & ((1 << FLAG_CHANGES_COUNT) - 1);
  bool hasSideEffects(HTypeMap types) => getChangesFlags() != 0;
  void prepareGvn(HTypeMap types) { setAllSideEffects(); }

  void setAllSideEffects() { flags |= ((1 << FLAG_CHANGES_COUNT) - 1); }
  void clearAllSideEffects() { flags &= ~((1 << FLAG_CHANGES_COUNT) - 1); }

  bool dependsOnSomething() => getFlag(FLAG_DEPENDS_ON_SOMETHING);
  void setDependsOnSomething() { setFlag(FLAG_DEPENDS_ON_SOMETHING); }

  bool dependsOnStaticPropertyStore() {
    return getFlag(FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE);
  }
  void setDependsOnStaticPropertyStore() {
    setFlag(FLAG_DEPENDS_ON_STATIC_PROPERTY_STORE);
  }
  void setChangesStaticProperty() { setFlag(FLAG_CHANGES_STATIC_PROPERTY); }

  bool dependsOnIndexStore() => getFlag(FLAG_DEPENDS_ON_INDEX_STORE);
  void setDependsOnIndexStore() { setFlag(FLAG_DEPENDS_ON_INDEX_STORE); }
  void setChangesIndex() { setFlag(FLAG_CHANGES_INDEX); }

  bool dependsOnInstancePropertyStore() {
    return getFlag(FLAG_DEPENDS_ON_INSTANCE_PROPERTY_STORE);
  }
  void setDependsOnInstancePropertyStore() {
    setFlag(FLAG_DEPENDS_ON_INSTANCE_PROPERTY_STORE);
  }
  void setChangesInstanceProperty() { setFlag(FLAG_CHANGES_INSTANCE_PROPERTY); }

  bool useGvn() => getFlag(FLAG_USE_GVN);
  void setUseGvn() { setFlag(FLAG_USE_GVN); }
  // Does this node potentially affect control flow.
  bool isControlFlow() => false;

  // All isFunctions work on the propagated types.
  bool isArray(HTypeMap types) => types[this].isArray();
  bool isReadableArray(HTypeMap types) => types[this].isReadableArray();
  bool isMutableArray(HTypeMap types) => types[this].isMutableArray();
  bool isExtendableArray(HTypeMap types) => types[this].isExtendableArray();
  bool isFixedArray(HTypeMap types) => types[this].isFixedArray();
  bool isBoolean(HTypeMap types) => types[this].isBoolean();
  bool isInteger(HTypeMap types) => types[this].isInteger();
  bool isDouble(HTypeMap types) => types[this].isDouble();
  bool isNumber(HTypeMap types) => types[this].isNumber();
  bool isNumberOrNull(HTypeMap types) => types[this].isNumberOrNull();
  bool isString(HTypeMap types) => types[this].isString();
  bool isTypeUnknown(HTypeMap types) => types[this].isUnknown();
  bool isIndexablePrimitive(HTypeMap types)
      => types[this].isIndexablePrimitive();
  bool isPrimitive(HTypeMap types) => types[this].isPrimitive();
  bool canBePrimitive(HTypeMap types) => types[this].canBePrimitive();
  bool canBeNull(HTypeMap types) => types[this].canBeNull();

  /**
   * This is the type the instruction is guaranteed to have. It does not
   * take any propagation into account.
   */
  HType guaranteedType = HType.UNKNOWN;
  bool hasGuaranteedType() => !guaranteedType.isUnknown();

  /**
   * Some instructions have a good idea of their return type, but cannot
   * guarantee the type. The computed does not need to be more specialized
   * than the provided type for [this].
   *
   * Examples: the likely type of [:x == y:] is a boolean. In most cases this
   * cannot be guaranteed, but when merging types we still want to use this
   * information.
   *
   * Similarily the [HAdd] instruction is likely a number. Note that, even if
   * the incoming type is already set to integer, the likely type might still
   * just return the number type.
   */
  HType computeLikelyType(HTypeMap types, Compiler compiler) => types[this];

  /**
   * Compute the type of the instruction by propagating the input types through
   * the instruction.
   *
   * By default just copy the guaranteed type.
   */
  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    return guaranteedType;
  }

  /**
   * Compute the desired type for the the given [input]. Aside from using
   * other inputs to compute the desired type one should also use
   * the given [types] which, during the invocation of this method,
   * represents the desired type of [this].
   */
  HType computeDesiredTypeForInput(HInstruction input,
                                   HTypeMap types,
                                   Compiler compiler) {
    return HType.UNKNOWN;
  }

  bool isInBasicBlock() => block != null;

  String inputsToString() {
    void addAsCommaSeparated(StringBuffer buffer, List<HInstruction> list) {
      for (int i = 0; i < list.length; i++) {
        if (i != 0) buffer.add(', ');
        buffer.add("@${list[i].id}");
      }
    }

    StringBuffer buffer = new StringBuffer();
    buffer.add('(');
    addAsCommaSeparated(buffer, inputs);
    buffer.add(') - used at [');
    addAsCommaSeparated(buffer, usedBy);
    buffer.add(']');
    return buffer.toString();
  }

  bool gvnEquals(HInstruction other) {
    assert(useGvn() && other.useGvn());
    // Check that the type and the flags match.
    bool hasSameType = typeEquals(other);
    assert(hasSameType == (typeCode() == other.typeCode()));
    if (!hasSameType) return false;
    if (flags != other.flags) return false;
    // Check that the inputs match.
    final int inputsLength = inputs.length;
    final List<HInstruction> otherInputs = other.inputs;
    if (inputsLength != otherInputs.length) return false;
    for (int i = 0; i < inputsLength; i++) {
      if (!identical(inputs[i], otherInputs[i])) return false;
    }
    // Check that the data in the instruction matches.
    return dataEquals(other);
  }

  int gvnHashCode() {
    int result = typeCode();
    int length = inputs.length;
    for (int i = 0; i < length; i++) {
      result = (result * 19) + (inputs[i].id) + (result >> 7);
    }
    return result;
  }

  // These methods should be overwritten by instructions that
  // participate in global value numbering.
  int typeCode() => HInstruction.UNDEFINED_TYPECODE;
  bool typeEquals(HInstruction other) => false;
  bool dataEquals(HInstruction other) => false;

  accept(HVisitor visitor);

  void notifyAddedToBlock(HBasicBlock targetBlock) {
    assert(!isInBasicBlock());
    assert(block == null);
    // Add [this] to the inputs' uses.
    for (int i = 0; i < inputs.length; i++) {
      assert(inputs[i].isInBasicBlock());
      inputs[i].usedBy.add(this);
    }
    block = targetBlock;
    assert(isValid());
  }

  void notifyRemovedFromBlock() {
    assert(isInBasicBlock());
    assert(usedBy.isEmpty);

    // Remove [this] from the inputs' uses.
    for (int i = 0; i < inputs.length; i++) {
      inputs[i].removeUser(this);
    }
    this.block = null;
    assert(isValid());
  }

  void rewriteInput(HInstruction from, HInstruction to) {
    for (int i = 0; i < inputs.length; i++) {
      if (identical(inputs[i], from)) inputs[i] = to;
    }
  }

  /** Removes all occurrences of [user] from [usedBy]. */
  void removeUser(HInstruction user) {
    List<HInstruction> users = usedBy;
    int length = users.length;
    for (int i = 0; i < length; i++) {
      if (identical(users[i], user)) {
        users[i] = users[length - 1];
        length--;
      }
    }
    users.length = length;
  }

  // Change all uses of [oldInput] by [this] to [newInput]. Also
  // updates the [usedBy] of [oldInput] and [newInput].
  void changeUse(HInstruction oldInput, HInstruction newInput) {
    for (int i = 0; i < inputs.length; i++) {
      if (identical(inputs[i], oldInput)) {
        inputs[i] = newInput;
        newInput.usedBy.add(this);
      }
    }
    List<HInstruction> oldInputUsers = oldInput.usedBy;
    int i = 0;
    while (i < oldInputUsers.length) {
      if (oldInputUsers[i] == this) {
        oldInputUsers[i] = oldInputUsers[oldInput.usedBy.length - 1];
        oldInputUsers.length--;
      } else {
        i++;
      }
    }
  }

  // Compute the set of users of this instruction that is dominated by
  // [other]. If [other] is a user of [this], it is included in the
  // returned set.
  Set<HInstruction> dominatedUsers(HInstruction other) {
    // Keep track of all instructions that we have to deal with later
    // and count the number of them that are in the current block.
    Set<HInstruction> users = new Set<HInstruction>();
    int usersInCurrentBlock = 0;

    // Run through all the users and see if they are dominated or
    // potentially dominated by [other].
    HBasicBlock otherBlock = other.block;
    for (int i = 0, length = usedBy.length; i < length; i++) {
      HInstruction current = usedBy[i];
      if (otherBlock.dominates(current.block)) {
        if (identical(current.block, otherBlock)) usersInCurrentBlock++;
        users.add(current);
      }
    }

    // Run through all the phis in the same block as [other] and remove them
    // from the users set.
    if (usersInCurrentBlock > 0) {
      for (HPhi phi = otherBlock.phis.first; phi != null; phi = phi.next) {
        if (users.contains(phi)) {
          users.remove(phi);
          if (--usersInCurrentBlock == 0) break;
        }
      }
    }

    // Run through all the instructions before [other] and remove them
    // from the users set.
    if (usersInCurrentBlock > 0) {
      HInstruction current = otherBlock.first;
      while (!identical(current, other)) {
        if (users.contains(current)) {
          users.remove(current);
          if (--usersInCurrentBlock == 0) break;
        }
        current = current.next;
      }
    }

    return users;
  }

  bool isConstant() => false;
  bool isConstantBoolean() => false;
  bool isConstantNull() => false;
  bool isConstantNumber() => false;
  bool isConstantInteger() => false;
  bool isConstantString() => false;
  bool isConstantList() => false;
  bool isConstantMap() => false;
  bool isConstantFalse() => false;
  bool isConstantTrue() => false;
  bool isConstantSentinel() => false;

  bool isValid() {
    HValidator validator = new HValidator();
    validator.currentBlock = block;
    validator.visitInstruction(this);
    return validator.isValid;
  }

  /**
   * The code for computing a bailout environment, and the code
   * generation must agree on what does not need to be captured,
   * so should always be generated at use site.
   */
  bool isCodeMotionInvariant() => false;

  bool isJsStatement(HTypeMap types) => false;

  bool dominates(HInstruction other) {
    // An instruction does not dominates itself.
    if (this == other) return false;
    if (block != other.block) return block.dominates(other.block);

    HInstruction current = this.next;
    while (current != null) {
      if (current == other) return true;
      current = current.next;
    }
    return false;
  }


  HInstruction convertType(Compiler compiler, DartType type, int kind) {
    if (type == null) return this;
    if (identical(type.element, compiler.dynamicClass)) return this;
    if (identical(type.element, compiler.objectClass)) return this;

    // If the original can't be null, type conversion also can't produce null.
    bool canBeNull = this.guaranteedType.canBeNull();
    HType convertedType =
        new HType.fromBoundedType(type, compiler, canBeNull);

    // No need to convert if we know the instruction has
    // [convertedType] as a bound.
    if (this.guaranteedType == convertedType) {
      return this;
    }

    return new HTypeConversion(convertedType, this, kind);
  }
}

class HBoolify extends HInstruction {
  HBoolify(HInstruction value) : super(<HInstruction>[value]);
  void prepareGvn(HTypeMap types) {
    assert(!hasSideEffects(types));
    setUseGvn();
  }

  HType get guaranteedType => HType.BOOLEAN;

  accept(HVisitor visitor) => visitor.visitBoolify(this);
  int typeCode() => HInstruction.BOOLIFY_TYPECODE;
  bool typeEquals(other) => other is HBoolify;
  bool dataEquals(HInstruction other) => true;
}

/**
 * A [HCheck] instruction is an instruction that might do a dynamic
 * check at runtime on another instruction. To have proper instruction
 * dependencies in the graph, instructions that depend on the check
 * being done reference the [HCheck] instruction instead of the
 * instruction itself.
 */
abstract class HCheck extends HInstruction {
  HCheck(inputs) : super(inputs);
  HInstruction get checkedInput => inputs[0];
  bool isJsStatement(HTypeMap types) => true;
  void prepareGvn(HTypeMap types) {
    assert(!hasSideEffects(types));
    setUseGvn();
  }
}

class HBailoutTarget extends HInstruction {
  final int state;
  bool isEnabled = false;
  HBailoutTarget(this.state) : super(<HInstruction>[]);
  void prepareGvn(HTypeMap types) {
    assert(!hasSideEffects(types));
    setUseGvn();
  }

  bool isControlFlow() => true;
  bool isJsStatement(HTypeMap types) => isEnabled;

  accept(HVisitor visitor) => visitor.visitBailoutTarget(this);
  int typeCode() => HInstruction.BAILOUT_TARGET_TYPECODE;
  bool typeEquals(other) => other is HBailoutTarget;
  bool dataEquals(HBailoutTarget other) => other.state == state;
}

class HTypeGuard extends HCheck {
  final HType guardedType;
  bool isEnabled = false;

  HTypeGuard(this.guardedType, HInstruction guarded, HInstruction bailoutTarget)
      : super(<HInstruction>[guarded, bailoutTarget]);

  HInstruction get guarded => inputs[0];
  HInstruction get checkedInput => guarded;
  HBailoutTarget get bailoutTarget => inputs[1];
  int get state => bailoutTarget.state;

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    return isEnabled ? guardedType : types[guarded];
  }

  HType get guaranteedType => isEnabled ? guardedType : HType.UNKNOWN;

  bool isControlFlow() => true;

  bool isJsStatement(HTypeMap types) => isEnabled;

  accept(HVisitor visitor) => visitor.visitTypeGuard(this);
  int typeCode() => HInstruction.TYPE_GUARD_TYPECODE;
  bool typeEquals(other) => other is HTypeGuard;
  bool dataEquals(HTypeGuard other) => guardedType == other.guardedType;
}

class HBoundsCheck extends HCheck {
  static const int ALWAYS_FALSE = 0;
  static const int FULL_CHECK = 1;
  static const int ALWAYS_ABOVE_ZERO = 2;
  static const int ALWAYS_BELOW_LENGTH = 3;
  static const int ALWAYS_TRUE = 4;
  /**
   * Details which tests have been done statically during compilation.
   * Default is that all checks must be performed dynamically.
   */
  int staticChecks = FULL_CHECK;

  HBoundsCheck(length, index) : super(<HInstruction>[length, index]);

  HInstruction get length => inputs[1];
  HInstruction get index => inputs[0];
  bool isControlFlow() => true;

  HType get guaranteedType => HType.INTEGER;

  accept(HVisitor visitor) => visitor.visitBoundsCheck(this);
  int typeCode() => HInstruction.BOUNDS_CHECK_TYPECODE;
  bool typeEquals(other) => other is HBoundsCheck;
  bool dataEquals(HInstruction other) => true;
}

class HIntegerCheck extends HCheck {
  bool alwaysFalse = false;

  HIntegerCheck(value) : super(<HInstruction>[value]);

  HInstruction get value => inputs[0];
  bool isControlFlow() => true;

  HType get guaranteedType => HType.INTEGER;

  HType computeDesiredTypeForInput(HInstruction input,
                                   HTypeMap types,
                                   Compiler compiler) {
    // If the desired type of the input is already a number, we want
    // to specialize it to an integer.
    return input.isNumber(types)
      ? HType.INTEGER
      : super.computeDesiredTypeForInput(input, types, compiler);
  }

  accept(HVisitor visitor) => visitor.visitIntegerCheck(this);
  int typeCode() => HInstruction.INTEGER_CHECK_TYPECODE;
  bool typeEquals(other) => other is HIntegerCheck;
  bool dataEquals(HInstruction other) => true;
}

abstract class HConditionalBranch extends HControlFlow {
  HConditionalBranch(inputs) : super(inputs);
  HInstruction get condition => inputs[0];
  HBasicBlock get trueBranch => block.successors[0];
  HBasicBlock get falseBranch => block.successors[1];
}

abstract class HControlFlow extends HInstruction {
  HControlFlow(inputs) : super(inputs);
  void prepareGvn(HTypeMap types) {
    // Control flow does not have side-effects.
  }
  bool isControlFlow() => true;
  bool isJsStatement(HTypeMap types) => true;
}

abstract class HInvoke extends HInstruction {
  /**
    * The first argument must be the target: either an [HStatic] node, or
    * the receiver of a method-call. The remaining inputs are the arguments
    * to the invocation.
    */
  HInvoke(List<HInstruction> inputs) : super(inputs);
  static const int ARGUMENTS_OFFSET = 1;
}

abstract class HInvokeDynamic extends HInvoke {
  final Selector selector;
  Element element;

  HInvokeDynamic(this.selector, this.element, List<HInstruction> inputs)
    : super(inputs);
  toString() => 'invoke dynamic: $selector';
  HInstruction get receiver => inputs[0];

  bool get isInterceptorCall {
    // We know it's a selector call if it follows the interceptor
    // calling convention, which adds the actual receiver as a
    // parameter to the call.
    return inputs.length - 2 == selector.argumentCount;
  }
}

class HInvokeClosure extends HInvokeDynamic {
  HInvokeClosure(Selector selector, List<HInstruction> inputs)
    : super(selector, null, inputs);
  accept(HVisitor visitor) => visitor.visitInvokeClosure(this);
}

class HInvokeDynamicMethod extends HInvokeDynamic {
  HInvokeDynamicMethod(Selector selector, List<HInstruction> inputs)
    : super(selector, null, inputs);
  toString() => 'invoke dynamic method: $selector';
  accept(HVisitor visitor) => visitor.visitInvokeDynamicMethod(this);
}

abstract class HInvokeDynamicField extends HInvokeDynamic {
  final bool isSideEffectFree;
  HInvokeDynamicField(
      Selector selector, Element element, List<HInstruction> inputs,
      this.isSideEffectFree)
      : super(selector, element, inputs);
  toString() => 'invoke dynamic field: $selector';
}

class HInvokeDynamicGetter extends HInvokeDynamicField {
  HInvokeDynamicGetter(
      selector, element, receiver, isSideEffectFree)
    : super(selector, element, [receiver], isSideEffectFree);
  toString() => 'invoke dynamic getter: $selector';
  accept(HVisitor visitor) => visitor.visitInvokeDynamicGetter(this);

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    if (isSideEffectFree) {
      setUseGvn();
      setDependsOnInstancePropertyStore();
    } else {
      setAllSideEffects();
    }
  }

  int typeCode() => HInstruction.INVOKE_DYNAMIC_GETTER_TYPECODE;
  bool typeEquals(other) => other is HInvokeDynamicGetter;
  bool dataEquals(HInvokeDynamicGetter other) => selector == other.selector;
}

class HInvokeDynamicSetter extends HInvokeDynamicField {
  HInvokeDynamicSetter(selector, element, receiver, value, isSideEffectFree)
    : super(selector, element, [receiver, value], isSideEffectFree);
  toString() => 'invoke dynamic setter: $selector';
  accept(HVisitor visitor) => visitor.visitInvokeDynamicSetter(this);

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    if (isSideEffectFree) {
      setChangesInstanceProperty();
    } else {
      setAllSideEffects();
    }
  }
}

class HInvokeStatic extends HInvoke {
  /** The first input must be the target. */
  HInvokeStatic(inputs, [HType knownType = HType.UNKNOWN]) : super(inputs) {
    guaranteedType = knownType;
  }

  toString() => 'invoke static: ${element.name}';
  accept(HVisitor visitor) => visitor.visitInvokeStatic(this);
  int typeCode() => HInstruction.INVOKE_STATIC_TYPECODE;
  Element get element => target.element;
  HStatic get target => inputs[0];

  HType computeDesiredTypeForInput(HInstruction input,
                                   HTypeMap types,
                                   Compiler compiler) {
    // TODO(floitsch): we want the target to be a function.
    if (input == target) return HType.UNKNOWN;
    return computeDesiredTypeForNonTargetInput(input, types, compiler);
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    return HType.UNKNOWN;
  }
}

class HInvokeSuper extends HInvokeStatic {
  final bool isSetter;
  HInvokeSuper(inputs, {this.isSetter: false}) : super(inputs);
  toString() => 'invoke super: ${element.name}';
  accept(HVisitor visitor) => visitor.visitInvokeSuper(this);

  HInstruction get value {
    assert(isSetter);
    // Index 0: the element, index 1: 'this'.
    return inputs[2];
  }
}

abstract class HFieldAccess extends HInstruction {
  final Element element;

  HFieldAccess(Element element, List<HInstruction> inputs)
      : this.element = element,
        super(inputs);
}

class HFieldGet extends HFieldAccess {
  final bool isAssignable;

  HFieldGet(Element element, HInstruction receiver, {bool isAssignable})
      : this.isAssignable = (isAssignable != null)
            ? isAssignable
            : element.isAssignable(),
        super(element, <HInstruction>[receiver]);

  HInstruction get receiver => inputs[0];

  accept(HVisitor visitor) => visitor.visitFieldGet(this);

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    setUseGvn();
    if (isAssignable) {
      setDependsOnInstancePropertyStore();
    }
  }

  int typeCode() => HInstruction.FIELD_GET_TYPECODE;
  bool typeEquals(other) => other is HFieldGet;
  bool dataEquals(HFieldGet other) => element == other.element;
  String toString() => "FieldGet $element";
}

class HFieldSet extends HFieldAccess {
  HFieldSet(Element element,
            HInstruction receiver,
            HInstruction value)
      : super(element, <HInstruction>[receiver, value]);

  HInstruction get receiver => inputs[0];
  HInstruction get value => inputs[1];
  accept(HVisitor visitor) => visitor.visitFieldSet(this);

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    setChangesInstanceProperty();
  }

  bool isJsStatement(HTypeMap types) => true;
  String toString() => "FieldSet $element";
}

class HLocalGet extends HFieldGet {
  HLocalGet(Element element, HLocalValue local) : super(element, local);

  accept(HVisitor visitor) => visitor.visitLocalGet(this);

  HLocalValue get local => inputs[0];

  void prepareGvn(HTypeMap types) {
    // No need to use GVN for a [HLocalGet], it is just a local
    // access.
    clearAllSideEffects();
  }
}

class HLocalSet extends HFieldSet {
  HLocalSet(Element element, HLocalValue local, HInstruction value)
      : super(element, local, value);

  accept(HVisitor visitor) => visitor.visitLocalSet(this);

  HLocalValue get local => inputs[0];
}

class HForeign extends HInstruction {
  final DartString code;
  final HType foreignType;
  final bool _isStatement;

  HForeign(this.code, DartString declaredType, List<HInstruction> inputs)
      : foreignType = computeTypeFromDeclaredType(declaredType),
        _isStatement = false,
        super(inputs);
  HForeign.statement(this.code, List<HInstruction> inputs)
      : foreignType = HType.UNKNOWN,
        _isStatement = true,
        super(inputs);
  accept(HVisitor visitor) => visitor.visitForeign(this);

  static HType computeTypeFromDeclaredType(DartString declaredType) {
    if (declaredType.slowToString() == 'bool') return HType.BOOLEAN;
    if (declaredType.slowToString() == 'int') return HType.INTEGER;
    if (declaredType.slowToString() == 'double') return HType.DOUBLE;
    if (declaredType.slowToString() == 'num') return HType.NUMBER;
    if (declaredType.slowToString() == 'String') return HType.STRING;
    if (declaredType.slowToString() == 'JSArray') return HType.READABLE_ARRAY;
    return HType.UNKNOWN;
  }

  HType get guaranteedType => foreignType;

  bool isJsStatement(HTypeMap types) => _isStatement;
}

class HForeignNew extends HForeign {
  ClassElement element;
  HForeignNew(this.element, List<HInstruction> inputs)
      : super(const LiteralDartString("new"),
              const LiteralDartString("Object"), inputs);
  accept(HVisitor visitor) => visitor.visitForeignNew(this);
}

abstract class HInvokeBinary extends HInvokeStatic {
  HInvokeBinary(HStatic target, HInstruction left, HInstruction right)
      : super(<HInstruction>[target, left, right]);

  HInstruction get left => inputs[1];
  HInstruction get right => inputs[2];

  BinaryOperation operation(ConstantSystem constantSystem);
  isBuiltin(HTypeMap types);
}

abstract class HBinaryArithmetic extends HInvokeBinary {
  HBinaryArithmetic(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    // An arithmetic expression can take part in global value
    // numbering and do not have any side-effects if we know that all
    // inputs are numbers.
    if (isBuiltin(types)) {
      setUseGvn();
    } else {
      setAllSideEffects();
    }
  }

  bool isBuiltin(HTypeMap types)
      => left.isNumber(types) && right.isNumber(types);

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    if (left.isInteger(types) && right.isInteger(types)) return HType.INTEGER;
    if (left.isNumber(types)) {
      if (left.isDouble(types) || right.isDouble(types)) return HType.DOUBLE;
      return HType.NUMBER;
    }
    return HType.UNKNOWN;
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    HType propagatedType = types[this];
    // If the desired output type should be an integer we want to get two
    // integers as arguments.
    if (propagatedType.isInteger()) return HType.INTEGER;
    // If the outgoing type should be a number we can get that if both inputs
    // are numbers. If we don't know the outgoing type we try to make it a
    // number.
    if (propagatedType.isUnknown() || propagatedType.isNumber()) {
      return HType.NUMBER;
    }
    // Even if the desired outgoing type is not a number we still want the
    // second argument to be a number if the first one is a number. This will
    // not help for the outgoing type, but at least the binary arithmetic
    // operation will not have type problems.
    // TODO(floitsch): normally we shouldn't request a number, but simply
    // throw an ArgumentError if it isn't. This would be similar
    // to the array case.
    if (input == right && left.isNumber(types)) return HType.NUMBER;
    return HType.UNKNOWN;
  }

  HType computeLikelyType(HTypeMap types, Compiler compiler) {
    if (left.isTypeUnknown(types)) return HType.NUMBER;
    return HType.UNKNOWN;
  }

  BinaryOperation operation(ConstantSystem constantSystem);
}

class HAdd extends HBinaryArithmetic {
  HAdd(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitAdd(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.add;
  int typeCode() => HInstruction.ADD_TYPECODE;
  bool typeEquals(other) => other is HAdd;
  bool dataEquals(HInstruction other) => true;
}

class HDivide extends HBinaryArithmetic {
  HDivide(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitDivide(this);

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    if (left.isNumber(types)) return HType.DOUBLE;
    return HType.UNKNOWN;
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    // A division can never return an integer. So don't ask for integer inputs.
    if (isInteger(types)) return HType.UNKNOWN;
    return super.computeDesiredTypeForNonTargetInput(input, types, compiler);
  }

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.divide;
  int typeCode() => HInstruction.DIVIDE_TYPECODE;
  bool typeEquals(other) => other is HDivide;
  bool dataEquals(HInstruction other) => true;
}

class HModulo extends HBinaryArithmetic {
  HModulo(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitModulo(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.modulo;
  int typeCode() => HInstruction.MODULO_TYPECODE;
  bool typeEquals(other) => other is HModulo;
  bool dataEquals(HInstruction other) => true;
}

class HMultiply extends HBinaryArithmetic {
  HMultiply(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitMultiply(this);

  BinaryOperation operation(ConstantSystem operations)
      => operations.multiply;
  int typeCode() => HInstruction.MULTIPLY_TYPECODE;
  bool typeEquals(other) => other is HMultiply;
  bool dataEquals(HInstruction other) => true;
}

class HSubtract extends HBinaryArithmetic {
  HSubtract(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitSubtract(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.subtract;
  int typeCode() => HInstruction.SUBTRACT_TYPECODE;
  bool typeEquals(other) => other is HSubtract;
  bool dataEquals(HInstruction other) => true;
}

/**
 * An [HSwitch] instruction has one input for the incoming
 * value, and one input per constant that it can switch on.
 * Its block has one successor per constant, and one for the default.
 */
class HSwitch extends HControlFlow {
  HSwitch(List<HInstruction> inputs) : super(inputs);

  HConstant constant(int index) => inputs[index + 1];
  HInstruction get expression => inputs[0];

  /**
   * Provides the target to jump to if none of the constants match
   * the expression. If the switch had no default case, this is the
   * following join-block.
   */
  HBasicBlock get defaultTarget => block.successors.last;

  accept(HVisitor visitor) => visitor.visitSwitch(this);

  String toString() => "HSwitch cases = $inputs";
}

class HTruncatingDivide extends HBinaryArithmetic {
  HTruncatingDivide(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitTruncatingDivide(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.truncatingDivide;
  int typeCode() => HInstruction.TRUNCATING_DIVIDE_TYPECODE;
  bool typeEquals(other) => other is HTruncatingDivide;
  bool dataEquals(HInstruction other) => true;
}


// TODO(floitsch): Should HBinaryArithmetic really be the super class of
// HBinaryBitOp?
abstract class HBinaryBitOp extends HBinaryArithmetic {
  HBinaryBitOp(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    // All bitwise operations on primitive types either produce an
    // integer or throw an error.
    if (left.isPrimitive(types)) return HType.INTEGER;
    return HType.UNKNOWN;
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    HType propagatedType = types[this];
    // If the outgoing type should be a number we can get that only if both
    // inputs are integers. If we don't know the outgoing type we try to make
    // it an integer.
    if (propagatedType.isUnknown() || propagatedType.isNumber()) {
      return HType.INTEGER;
    }
    return HType.UNKNOWN;
  }

  HType computeLikelyType(HTypeMap types, Compiler compiler) {
    if (left.isTypeUnknown(types)) return HType.INTEGER;
    return HType.UNKNOWN;
  }
}

class HShiftLeft extends HBinaryBitOp {
  HShiftLeft(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitShiftLeft(this);

  // Shift left cannot be mapped to the native operator unless the
  // shift count is guaranteed to be an integer in the [0,31] range.
  bool isBuiltin(HTypeMap types) {
    if (!left.isNumber(types) || !right.isConstantInteger()) return false;
    HConstant rightConstant = right;
    IntConstant intConstant = rightConstant.constant;
    int count = intConstant.value;
    return count >= 0 && count <= 31;
  }

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.shiftLeft;
  int typeCode() => HInstruction.SHIFT_LEFT_TYPECODE;
  bool typeEquals(other) => other is HShiftLeft;
  bool dataEquals(HInstruction other) => true;
}

class HShiftRight extends HBinaryBitOp {
  HShiftRight(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitShiftRight(this);

  // Shift right cannot be mapped to the native operator easily.
  bool isBuiltin(HTypeMap types) => false;

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.shiftRight;
  int typeCode() => HInstruction.SHIFT_RIGHT_TYPECODE;
  bool typeEquals(other) => other is HShiftRight;
  bool dataEquals(HInstruction other) => true;
}

class HBitOr extends HBinaryBitOp {
  HBitOr(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitBitOr(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.bitOr;
  int typeCode() => HInstruction.BIT_OR_TYPECODE;
  bool typeEquals(other) => other is HBitOr;
  bool dataEquals(HInstruction other) => true;
}

class HBitAnd extends HBinaryBitOp {
  HBitAnd(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitBitAnd(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.bitAnd;
  int typeCode() => HInstruction.BIT_AND_TYPECODE;
  bool typeEquals(other) => other is HBitAnd;
  bool dataEquals(HInstruction other) => true;
}

class HBitXor extends HBinaryBitOp {
  HBitXor(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitBitXor(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.bitXor;
  int typeCode() => HInstruction.BIT_XOR_TYPECODE;
  bool typeEquals(other) => other is HBitXor;
  bool dataEquals(HInstruction other) => true;
}

abstract class HInvokeUnary extends HInvokeStatic {
  HInvokeUnary(HStatic target, HInstruction input)
      : super(<HInstruction>[target, input]);

  HInstruction get operand => inputs[1];

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    // A unary arithmetic expression can take part in global value
    // numbering and does not have any side-effects if its input is a
    // number.
    if (isBuiltin(types)) {
      setUseGvn();
    } else {
      setAllSideEffects();
    }
  }

  bool isBuiltin(HTypeMap types) => operand.isNumber(types);

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    HType operandType = types[operand];
    if (operandType.isNumber()) return operandType;
    return HType.UNKNOWN;
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    HType propagatedType = types[this];
    // If the outgoing type should be a number (integer, double or both) we
    // want the outgoing type to be the input too.
    // If we don't know the outgoing type we try to make it a number.
    if (propagatedType.isNumber()) return propagatedType;
    if (propagatedType.isUnknown()) return HType.NUMBER;
    return HType.UNKNOWN;
  }

  HType computeLikelyType(HTypeMap types, Compiler compiler) => HType.NUMBER;

  UnaryOperation operation(ConstantSystem constantSystem);
}

class HNegate extends HInvokeUnary {
  HNegate(HStatic target, HInstruction input) : super(target, input);
  accept(HVisitor visitor) => visitor.visitNegate(this);

  UnaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.negate;
  int typeCode() => HInstruction.NEGATE_TYPECODE;
  bool typeEquals(other) => other is HNegate;
  bool dataEquals(HInstruction other) => true;
}

class HBitNot extends HInvokeUnary {
  HBitNot(HStatic target, HInstruction input) : super(target, input);
  accept(HVisitor visitor) => visitor.visitBitNot(this);

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    // All bitwise operations on primitive types either produce an
    // integer or throw an error.
    if (operand.isPrimitive(types)) return HType.INTEGER;
    return HType.UNKNOWN;
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    HType propagatedType = types[this];
    // Bit operations only work on integers. If there is no desired output
    // type or if it as a number we want to get an integer as input.
    if (propagatedType.isUnknown() || propagatedType.isNumber()) {
      return HType.INTEGER;
    }
    return HType.UNKNOWN;
  }

  UnaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.bitNot;
  int typeCode() => HInstruction.BIT_NOT_TYPECODE;
  bool typeEquals(other) => other is HBitNot;
  bool dataEquals(HInstruction other) => true;
}

class HExit extends HControlFlow {
  HExit() : super(const <HInstruction>[]);
  toString() => 'exit';
  accept(HVisitor visitor) => visitor.visitExit(this);
}

class HGoto extends HControlFlow {
  HGoto() : super(const <HInstruction>[]);
  toString() => 'goto';
  accept(HVisitor visitor) => visitor.visitGoto(this);
}

abstract class HJump extends HControlFlow {
  final TargetElement target;
  final LabelElement label;
  HJump(this.target) : label = null, super(const <HInstruction>[]);
  HJump.toLabel(LabelElement label)
      : label = label, target = label.target, super(const <HInstruction>[]);
}

class HBreak extends HJump {
  HBreak(TargetElement target) : super(target);
  HBreak.toLabel(LabelElement label) : super.toLabel(label);
  toString() => (label != null) ? 'break ${label.labelName}' : 'break';
  accept(HVisitor visitor) => visitor.visitBreak(this);
}

class HContinue extends HJump {
  HContinue(TargetElement target) : super(target);
  HContinue.toLabel(LabelElement label) : super.toLabel(label);
  toString() => (label != null) ? 'continue ${label.labelName}' : 'continue';
  accept(HVisitor visitor) => visitor.visitContinue(this);
}

class HTry extends HControlFlow {
  HParameterValue exception;
  HBasicBlock catchBlock;
  HBasicBlock finallyBlock;
  HTry() : super(const <HInstruction>[]);
  toString() => 'try';
  accept(HVisitor visitor) => visitor.visitTry(this);
  HBasicBlock get joinBlock => this.block.successors.last;
}

// An [HExitTry] control flow node is used when the body of a try or
// the body of a catch contains a return, break or continue. To build
// the control flow graph, we explicitely mark the body that
// leads to one of this instruction a predecessor of catch and
// finally.
class HExitTry extends HControlFlow {
  HExitTry() : super(const <HInstruction>[]);
  toString() => 'exit try';
  accept(HVisitor visitor) => visitor.visitExitTry(this);
  HBasicBlock get bodyTrySuccessor => block.successors[0];
}

class HIf extends HConditionalBranch {
  HBlockFlow blockInformation = null;
  HIf(HInstruction condition) : super(<HInstruction>[condition]);
  toString() => 'if';
  accept(HVisitor visitor) => visitor.visitIf(this);

  HBasicBlock get thenBlock {
    assert(identical(block.dominatedBlocks[0], block.successors[0]));
    return block.successors[0];
  }

  HBasicBlock get elseBlock {
    assert(identical(block.dominatedBlocks[1], block.successors[1]));
    return block.successors[1];
  }

  HBasicBlock get joinBlock => blockInformation.continuation;
}

class HLoopBranch extends HConditionalBranch {
  static const int CONDITION_FIRST_LOOP = 0;
  static const int DO_WHILE_LOOP = 1;

  final int kind;
  HLoopBranch(HInstruction condition, [this.kind = CONDITION_FIRST_LOOP])
      : super(<HInstruction>[condition]);
  toString() => 'loop-branch';
  accept(HVisitor visitor) => visitor.visitLoopBranch(this);

  bool isDoWhile() {
    return identical(kind, DO_WHILE_LOOP);
  }
}

class HConstant extends HInstruction {
  final Constant constant;
  final HType constantType;
  HConstant.internal(this.constant, HType this.constantType)
      : super(<HInstruction>[]);

  void prepareGvn(HTypeMap types) {
    assert(!hasSideEffects(types));
  }

  toString() => 'literal: $constant';
  accept(HVisitor visitor) => visitor.visitConstant(this);

  HType get guaranteedType => constantType;

  bool isConstant() => true;
  bool isConstantBoolean() => constant.isBool();
  bool isConstantNull() => constant.isNull();
  bool isConstantNumber() => constant.isNum();
  bool isConstantInteger() => constant.isInt();
  bool isConstantString() => constant.isString();
  bool isConstantList() => constant.isList();
  bool isConstantMap() => constant.isMap();
  bool isConstantFalse() => constant.isFalse();
  bool isConstantTrue() => constant.isTrue();
  bool isConstantSentinel() => constant.isSentinel();

  // Maybe avoid this if the literal is big?
  bool isCodeMotionInvariant() => true;
}

class HNot extends HInstruction {
  HNot(HInstruction value) : super(<HInstruction>[value]);
  void prepareGvn(HTypeMap types) {
    assert(!hasSideEffects(types));
    setUseGvn();
  }

  HType get guaranteedType => HType.BOOLEAN;

  // 'Not' only works on booleans. That's what we want as input.
  HType computeDesiredTypeForInput(HInstruction input,
                                   HTypeMap types,
                                   Compiler compiler) {
    return HType.BOOLEAN;
  }

  accept(HVisitor visitor) => visitor.visitNot(this);
  int typeCode() => HInstruction.NOT_TYPECODE;
  bool typeEquals(other) => other is HNot;
  bool dataEquals(HInstruction other) => true;
}

/**
  * An [HLocalValue] represents a local. Unlike [HParameterValue]s its
  * first use must be in an HLocalSet. That is, [HParameterValue]s have a
  * value from the start, whereas [HLocalValue]s need to be initialized first.
  */
class HLocalValue extends HInstruction {
  HLocalValue(Element element) : super(<HInstruction>[]) {
    sourceElement = element;
  }

  void prepareGvn(HTypeMap types) {
    assert(!hasSideEffects(types));
  }
  toString() => 'local ${sourceElement.name}';
  accept(HVisitor visitor) => visitor.visitLocalValue(this);
  bool isCodeMotionInvariant() => true;
}

class HParameterValue extends HLocalValue {
  HParameterValue(Element element) : super(element);

  toString() => 'parameter ${sourceElement.name.slowToString()}';
  accept(HVisitor visitor) => visitor.visitParameterValue(this);
}

class HThis extends HParameterValue {
  HThis(Element element, [HType type = HType.UNKNOWN]) : super(element) {
    guaranteedType = type;
  }
  toString() => 'this';
  accept(HVisitor visitor) => visitor.visitThis(this);
}

class HPhi extends HInstruction {
  static const IS_NOT_LOGICAL_OPERATOR = 0;
  static const IS_AND = 1;
  static const IS_OR = 2;

  int logicalOperatorType = IS_NOT_LOGICAL_OPERATOR;

  // The order of the [inputs] must correspond to the order of the
  // predecessor-edges. That is if an input comes from the first predecessor
  // of the surrounding block, then the input must be the first in the [HPhi].
  HPhi(Element element, List<HInstruction> inputs) : super(inputs) {
    sourceElement = element;
  }
  HPhi.noInputs(Element element) : this(element, <HInstruction>[]);
  HPhi.singleInput(Element element, HInstruction input)
      : this(element, <HInstruction>[input]);
  HPhi.manyInputs(Element element, List<HInstruction> inputs)
      : this(element, inputs);

  void addInput(HInstruction input) {
    assert(isInBasicBlock());
    inputs.add(input);
    input.usedBy.add(this);
  }

  // Compute the (shared) type of the inputs if any. If all inputs
  // have the same known type return it. If any two inputs have
  // different known types, we'll return a conflict -- otherwise we'll
  // simply return an unknown type.
  HType computeInputsType(bool ignoreUnknowns,
                          HTypeMap types,
                          Compiler compiler) {
    HType candidateType = HType.CONFLICTING;
    for (int i = 0, length = inputs.length; i < length; i++) {
      HType inputType = types[inputs[i]];
      if (ignoreUnknowns && inputType.isUnknown()) continue;
      // Phis need to combine the incoming types using the union operation.
      // For example, if one incoming edge has type integer and the other has
      // type double, then the phi is either an integer or double and thus has
      // type number.
      candidateType = candidateType.union(inputType, compiler);
      if (candidateType.isUnknown()) return HType.UNKNOWN;
    }
    return candidateType;
  }

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    HType inputsType = computeInputsType(false, types, compiler);
    if (inputsType.isConflicting()) return HType.UNKNOWN;
    return inputsType;
  }

  HType computeDesiredTypeForInput(HInstruction input,
                                   HTypeMap types,
                                   Compiler compiler) {
    HType propagatedType = types[this];
    // Best case scenario for a phi is, when all inputs have the same type. If
    // there is no desired outgoing type we therefore try to unify the input
    // types (which is basically the [likelyType]).
    if (propagatedType.isUnknown()) return computeLikelyType(types, compiler);
    // When the desired outgoing type is conflicting we don't need to give any
    // requirements on the inputs.
    if (propagatedType.isConflicting()) return HType.UNKNOWN;
    // Otherwise the input type must match the desired outgoing type.
    return propagatedType;
  }

  HType computeLikelyType(HTypeMap types, Compiler compiler) {
    HType agreedType = computeInputsType(true, types, compiler);
    if (agreedType.isConflicting()) return HType.UNKNOWN;
    // Don't be too restrictive. If the agreed type is integer or double just
    // say that the likely type is number. If more is expected the type will be
    // propagated back.
    if (agreedType.isNumber()) return HType.NUMBER;
    return agreedType;
  }

  bool isLogicalOperator() => logicalOperatorType != IS_NOT_LOGICAL_OPERATOR;

  String logicalOperator() {
    assert(isLogicalOperator());
    if (logicalOperatorType == IS_AND) return "&&";
    assert(logicalOperatorType == IS_OR);
    return "||";
  }

  toString() => 'phi';
  accept(HVisitor visitor) => visitor.visitPhi(this);
}

abstract class HRelational extends HInvokeBinary {
  bool usesBoolifiedInterceptor = false;
  HRelational(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    // Relational expressions can take part in global value numbering
    // and do not have any side-effects if we know all the inputs are
    // numbers. This can be improved for at least equality.
    if (isBuiltin(types)) {
      setUseGvn();
    } else {
      setAllSideEffects();
    }
  }

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    if (left.isNumber(types) || usesBoolifiedInterceptor) return HType.BOOLEAN;
    return HType.UNKNOWN;
  }

  HType get guaranteedType {
    if (usesBoolifiedInterceptor) return HType.BOOLEAN;
    return HType.UNKNOWN;
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    HType propagatedType = types[this];
    // For all relational operations exept HEquals, we expect to get numbers
    // only. With numbers the outgoing type is a boolean. If something else
    // is desired, then numbers are incorrect, though.
    if (propagatedType.isUnknown() || propagatedType.isBoolean()) {
      if (left.isTypeUnknown(types) || left.isNumber(types)) {
        return HType.NUMBER;
      }
    }
    return HType.UNKNOWN;
  }

  HType computeLikelyType(HTypeMap types, Compiler compiler) => HType.BOOLEAN;

  bool isBuiltin(HTypeMap types)
      => left.isNumber(types) && right.isNumber(types);
}

class HEquals extends HRelational {
  HEquals(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitEquals(this);

  bool isBuiltin(HTypeMap types) {
    // All primitive types have 'identical' semantics.
    // Note that this includes all constants except the user-constructed
    // objects.
    return types[left].isPrimitiveOrNull() || right.isConstantNull();
  }

  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler) {
    if (isBuiltin(types) || usesBoolifiedInterceptor) return HType.BOOLEAN;
    return HType.UNKNOWN;
  }

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    HType propagatedType = types[this];
    if (input == left && types[right].isUseful()) {
      // All our useful types have 'identical' semantics. But we don't want to
      // speculatively test for all possible types. Therefore we try to match
      // the two types. That is, if we see x == 3, then we speculatively test
      // if x is a number and bailout if it isn't.
      // If right is a number we don't need more than a number (no need to match
      // the exact type of right).
      if (right.isNumber(types)) return HType.NUMBER;
      // String equality testing is much more common than array equality
      // testing.
      if (right.isIndexablePrimitive(types)) return HType.STRING;
      return types[right];
    }
    // String equality testing is much more common than array equality testing.
    if (input == left && left.isIndexablePrimitive(types)) {
      return HType.READABLE_ARRAY;
    }
    // String equality testing is much more common than array equality testing.
    if (input == right && right.isIndexablePrimitive(types)) {
      return HType.STRING;
    }
    return HType.UNKNOWN;
  }

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.equal;
  int typeCode() => HInstruction.EQUALS_TYPECODE;
  bool typeEquals(other) => other is HEquals;
  bool dataEquals(HInstruction other) => true;
}

class HIdentity extends HRelational {
  HIdentity(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitIdentity(this);

  bool isBuiltin(HTypeMap types) => true;

  HType get guaranteedType => HType.BOOLEAN;
  HType computeTypeFromInputTypes(HTypeMap types, Compiler compiler)
      => HType.BOOLEAN;
  // Note that the identity operator really does not care for its input types.
  HType computeDesiredTypeForInput(HInstruction input,
                                   HTypeMap types,
                                   Compiler compiler) {
    return HType.UNKNOWN;
  }

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.identity;
  int typeCode() => HInstruction.IDENTITY_TYPECODE;
  bool typeEquals(other) => other is HIdentity;
  bool dataEquals(HInstruction other) => true;
}

class HGreater extends HRelational {
  HGreater(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitGreater(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.greater;
  int typeCode() => HInstruction.GREATER_TYPECODE;
  bool typeEquals(other) => other is HGreater;
  bool dataEquals(HInstruction other) => true;
}

class HGreaterEqual extends HRelational {
  HGreaterEqual(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitGreaterEqual(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.greaterEqual;
  int typeCode() => HInstruction.GREATER_EQUAL_TYPECODE;
  bool typeEquals(other) => other is HGreaterEqual;
  bool dataEquals(HInstruction other) => true;
}

class HLess extends HRelational {
  HLess(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitLess(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.less;
  int typeCode() => HInstruction.LESS_TYPECODE;
  bool typeEquals(other) => other is HLess;
  bool dataEquals(HInstruction other) => true;
}

class HLessEqual extends HRelational {
  HLessEqual(HStatic target, HInstruction left, HInstruction right)
      : super(target, left, right);
  accept(HVisitor visitor) => visitor.visitLessEqual(this);

  BinaryOperation operation(ConstantSystem constantSystem)
      => constantSystem.lessEqual;
  int typeCode() => HInstruction.LESS_EQUAL_TYPECODE;
  bool typeEquals(other) => other is HLessEqual;
  bool dataEquals(HInstruction other) => true;
}

class HReturn extends HControlFlow {
  HReturn(value) : super(<HInstruction>[value]);
  toString() => 'return';
  accept(HVisitor visitor) => visitor.visitReturn(this);
}

class HThrow extends HControlFlow {
  final bool isRethrow;
  HThrow(value, {this.isRethrow: false}) : super(<HInstruction>[value]);
  toString() => 'throw';
  accept(HVisitor visitor) => visitor.visitThrow(this);
}

class HStatic extends HInstruction {
  final Element element;
  HStatic(this.element) : super(<HInstruction>[]) {
    assert(element != null);
    assert(invariant(this, element.isDeclaration));
  }

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    if (element.isAssignable()) {
      setDependsOnStaticPropertyStore();
    }
    setUseGvn();
  }
  toString() => 'static ${element.name}';
  accept(HVisitor visitor) => visitor.visitStatic(this);

  int gvnHashCode() => super.gvnHashCode() ^ element.hashCode;
  int typeCode() => HInstruction.STATIC_TYPECODE;
  bool typeEquals(other) => other is HStatic;
  bool dataEquals(HStatic other) => element == other.element;
  bool isCodeMotionInvariant() => !element.isAssignable();
}

class HInterceptor extends HInstruction {
  Set<ClassElement> interceptedClasses;
  HInterceptor(this.interceptedClasses, HInstruction receiver)
      : super(<HInstruction>[receiver]);
  String toString() => 'interceptor on $interceptedClasses';
  accept(HVisitor visitor) => visitor.visitInterceptor(this);
  HInstruction get receiver => inputs[0];

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    setUseGvn();
  }

  int typeCode() => HInstruction.INTERCEPTOR_TYPECODE;
  bool typeEquals(other) => other is HInterceptor;
  bool dataEquals(HInterceptor other) {
    return interceptedClasses == other.interceptedClasses
        || (interceptedClasses.length == other.interceptedClasses.length
            && interceptedClasses.containsAll(other.interceptedClasses));
  }
}

/** An [HLazyStatic] is a static that is initialized lazily at first read. */
class HLazyStatic extends HStatic {
  HLazyStatic(Element element) : super(element);

  void prepareGvn(HTypeMap types) {
    // TODO(4931): The first access has side-effects, but we afterwards we
    // should be able to GVN.
    setAllSideEffects();
  }

  toString() => 'lazy static ${element.name}';
  accept(HVisitor visitor) => visitor.visitLazyStatic(this);

  int typeCode() => 30;
  // TODO(4931): can we do better here?
  bool isCodeMotionInvariant() => false;
}

class HStaticStore extends HInstruction {
  Element element;
  HStaticStore(this.element, HInstruction value) : super(<HInstruction>[value]);
  toString() => 'static store ${element.name}';
  accept(HVisitor visitor) => visitor.visitStaticStore(this);

  int typeCode() => HInstruction.STATIC_STORE_TYPECODE;
  bool typeEquals(other) => other is HStaticStore;
  bool dataEquals(HStaticStore other) => element == other.element;
  bool isJsStatement(HTypeMap types) => true;

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    setChangesStaticProperty();
  }
}

class HLiteralList extends HInstruction {
  HLiteralList(inputs) : super(inputs);
  toString() => 'literal list';
  accept(HVisitor visitor) => visitor.visitLiteralList(this);

  HType get guaranteedType => HType.EXTENDABLE_ARRAY;

  void prepareGvn(HTypeMap types) {
    assert(!hasSideEffects(types));
  }
}

class HIndex extends HInvokeStatic {
  HIndex(HStatic target, HInstruction receiver, HInstruction index)
      : super(<HInstruction>[target, receiver, index]);
  toString() => 'index operator';
  accept(HVisitor visitor) => visitor.visitIndex(this);

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    if (isBuiltin(types)) {
      setDependsOnIndexStore();
      setUseGvn();
    } else {
      setAllSideEffects();
    }
  }

  HInstruction get receiver => inputs[1];
  HInstruction get index => inputs[2];

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    if (input == receiver &&
        (index.isTypeUnknown(types) || index.isNumber(types))) {
      return HType.INDEXABLE_PRIMITIVE;
    }
    // The index should be an int when the receiver is a string or array.
    // However it turns out that inserting an integer check in the optimized
    // version is cheaper than having another bailout case. This is true,
    // because the integer check will simply throw if it fails.
    return HType.UNKNOWN;
  }

  bool isBuiltin(HTypeMap types)
      => receiver.isIndexablePrimitive(types) && index.isInteger(types);

  int typeCode() => HInstruction.INDEX_TYPECODE;
  bool typeEquals(HInstruction other) => other is HIndex;
  bool dataEquals(HIndex other) => true;
}

class HIndexAssign extends HInvokeStatic {
  HIndexAssign(HStatic target,
               HInstruction receiver,
               HInstruction index,
               HInstruction value)
      : super(<HInstruction>[target, receiver, index, value]);
  toString() => 'index assign operator';
  accept(HVisitor visitor) => visitor.visitIndexAssign(this);

  HInstruction get receiver => inputs[1];
  HInstruction get index => inputs[2];
  HInstruction get value => inputs[3];

  void prepareGvn(HTypeMap types) {
    clearAllSideEffects();
    if (isBuiltin(types)) {
      setChangesIndex();
    } else {
      setAllSideEffects();
    }
  }

  // Note, that we don't have a computeTypeFromInputTypes, since [HIndexAssign]
  // is never used as input.

  HType computeDesiredTypeForNonTargetInput(HInstruction input,
                                            HTypeMap types,
                                            Compiler compiler) {
    if (input == receiver &&
        (index.isTypeUnknown(types) || index.isNumber(types))) {
      return HType.MUTABLE_ARRAY;
    }
    // The index should be an int when the receiver is a string or array.
    // However it turns out that inserting an integer check in the optimized
    // version is cheaper than having another bailout case. This is true,
    // because the integer check will simply throw if it fails.
    return HType.UNKNOWN;
  }

  bool isBuiltin(HTypeMap types)
      => receiver.isMutableArray(types) && index.isInteger(types);
  bool isJsStatement(HTypeMap types) => !isBuiltin(types);
}

class HIs extends HInstruction {
  final DartType typeExpression;
  final bool nullOk;

  HIs.withTypeInfoCall(this.typeExpression, HInstruction expression,
                       HInstruction typeInfo, [this.nullOk = false])
    : super(<HInstruction>[expression, typeInfo]);

  HIs(this.typeExpression, HInstruction expression, {this.nullOk: false})
     : super(<HInstruction>[expression]);

  HInstruction get expression => inputs[0];

  HInstruction get typeInfoCall => inputs[1];

  bool hasTypeInfo() => inputs.length == 2;

  HType get guaranteedType => HType.BOOLEAN;

  accept(HVisitor visitor) => visitor.visitIs(this);

  toString() => "$expression is $typeExpression";
}

class HTypeConversion extends HCheck {
  HType type;
  final int kind;

  static const int NO_CHECK = 0;
  static const int CHECKED_MODE_CHECK = 1;
  static const int ARGUMENT_TYPE_CHECK = 2;
  static const int CAST_TYPE_CHECK = 3;
  static const int BOOLEAN_CONVERSION_CHECK = 4;

  HTypeConversion(this.type, HInstruction input, [this.kind = NO_CHECK])
      : super(<HInstruction>[input]) {
    sourceElement = input.sourceElement;
  }
  HTypeConversion.checkedModeCheck(HType type, HInstruction input)
      : this(type, input, CHECKED_MODE_CHECK);
  HTypeConversion.argumentTypeCheck(HType type, HInstruction input)
      : this(type, input, ARGUMENT_TYPE_CHECK);
  HTypeConversion.castCheck(HType type, HInstruction input)
      : this(type, input, CAST_TYPE_CHECK);


  bool get isChecked => kind != NO_CHECK;
  bool get isCheckedModeCheck {
    return kind == CHECKED_MODE_CHECK || kind == BOOLEAN_CONVERSION_CHECK;
  }
  bool get isArgumentTypeCheck => kind == ARGUMENT_TYPE_CHECK;
  bool get isCastTypeCheck => kind == CAST_TYPE_CHECK;
  bool get isBooleanConversionCheck => kind == BOOLEAN_CONVERSION_CHECK;

  HType get guaranteedType => type;

  accept(HVisitor visitor) => visitor.visitTypeConversion(this);

  bool isJsStatement(HTypeMap types) => kind == ARGUMENT_TYPE_CHECK;
  bool isControlFlow() => kind == ARGUMENT_TYPE_CHECK;

  int typeCode() => HInstruction.TYPE_CONVERSION_TYPECODE;
  bool typeEquals(HInstruction other) => other is HTypeConversion;
  bool dataEquals(HTypeConversion other) {
    return type == other.type && kind == other.kind;
  }
}

class HRangeConversion extends HCheck {
  HRangeConversion(HInstruction input) : super(<HInstruction>[input]) {
    sourceElement = input.sourceElement;
  }
  accept(HVisitor visitor) => visitor.visitRangeConversion(this);

  // We currently only do range analysis for integers.
  HType get guaranteedType => HType.INTEGER;
}

class HStringConcat extends HInstruction {
  final Node node;
  HStringConcat(HInstruction left, HInstruction right, this.node)
      : super(<HInstruction>[left, right]);
  HType get guaranteedType => HType.STRING;

  HInstruction get left => inputs[0];
  HInstruction get right => inputs[1];

  accept(HVisitor visitor) => visitor.visitStringConcat(this);
  toString() => "string concat";
}

/** Non-block-based (aka. traditional) loop information. */
class HLoopInformation {
  final HBasicBlock header;
  final List<HBasicBlock> blocks;
  final List<HBasicBlock> backEdges;
  final List<LabelElement> labels;
  final TargetElement target;

  /** Corresponding block information for the loop. */
  HLoopBlockInformation loopBlockInformation;

  HLoopInformation(this.header, this.target, this.labels)
      : blocks = new List<HBasicBlock>(),
        backEdges = new List<HBasicBlock>();

  void addBackEdge(HBasicBlock predecessor) {
    backEdges.add(predecessor);
    addBlock(predecessor);
  }

  // Adds a block and transitively all its predecessors in the loop as
  // loop blocks.
  void addBlock(HBasicBlock block) {
    if (identical(block, header)) return;
    HBasicBlock parentHeader = block.parentLoopHeader;
    if (identical(parentHeader, header)) {
      // Nothing to do in this case.
    } else if (parentHeader != null) {
      addBlock(parentHeader);
    } else {
      block.parentLoopHeader = header;
      blocks.add(block);
      for (int i = 0, length = block.predecessors.length; i < length; i++) {
        addBlock(block.predecessors[i]);
      }
    }
  }

  HBasicBlock getLastBackEdge() {
    int maxId = -1;
    HBasicBlock result = null;
    for (int i = 0, length = backEdges.length; i < length; i++) {
      HBasicBlock current = backEdges[i];
      if (current.id > maxId) {
        maxId = current.id;
        result = current;
      }
    }
    return result;
  }
}


/**
 * Embedding of a [HBlockInformation] for block-structure based traversal
 * in a dominator based flow traversal by attaching it to a basic block.
 * To go back to dominator-based traversal, a [HSubGraphBlockInformation]
 * structure can be added in the block structure.
 */
class HBlockFlow {
  final HBlockInformation body;
  final HBasicBlock continuation;
  HBlockFlow(this.body, this.continuation);
}


/**
 * Information about a syntactic-like structure.
 */
abstract class HBlockInformation {
  HBasicBlock get start;
  HBasicBlock get end;
  bool accept(HBlockInformationVisitor visitor);
}


/**
 * Information about a statement-like structure.
 */
abstract class HStatementInformation extends HBlockInformation {
  bool accept(HStatementInformationVisitor visitor);
}


/**
 * Information about an expression-like structure.
 */
abstract class HExpressionInformation extends HBlockInformation {
  bool accept(HExpressionInformationVisitor visitor);
  HInstruction get conditionExpression;
}


abstract class HStatementInformationVisitor {
  bool visitLabeledBlockInfo(HLabeledBlockInformation info);
  bool visitLoopInfo(HLoopBlockInformation info);
  bool visitIfInfo(HIfBlockInformation info);
  bool visitTryInfo(HTryBlockInformation info);
  bool visitSwitchInfo(HSwitchBlockInformation info);
  bool visitSequenceInfo(HStatementSequenceInformation info);
  // Pseudo-structure embedding a dominator-based traversal into
  // the block-structure traversal. This will eventually go away.
  bool visitSubGraphInfo(HSubGraphBlockInformation info);
}


abstract class HExpressionInformationVisitor {
  bool visitAndOrInfo(HAndOrBlockInformation info);
  bool visitSubExpressionInfo(HSubExpressionBlockInformation info);
}


abstract class HBlockInformationVisitor
    implements HStatementInformationVisitor, HExpressionInformationVisitor {
}


/**
 * Generic class wrapping a [SubGraph] as a block-information until
 * all structures are handled properly.
 */
class HSubGraphBlockInformation implements HStatementInformation {
  final SubGraph subGraph;
  HSubGraphBlockInformation(this.subGraph);

  HBasicBlock get start => subGraph.start;
  HBasicBlock get end => subGraph.end;

  bool accept(HStatementInformationVisitor visitor) =>
    visitor.visitSubGraphInfo(this);
}


/**
 * Generic class wrapping a [SubExpression] as a block-information until
 * expressions structures are handled properly.
 */
class HSubExpressionBlockInformation implements HExpressionInformation {
  final SubExpression subExpression;
  HSubExpressionBlockInformation(this.subExpression);

  HBasicBlock get start => subExpression.start;
  HBasicBlock get end => subExpression.end;

  HInstruction get conditionExpression => subExpression.conditionExpression;

  bool accept(HExpressionInformationVisitor visitor) =>
    visitor.visitSubExpressionInfo(this);
}


/** A sequence of separate statements. */
class HStatementSequenceInformation implements HStatementInformation {
  final List<HStatementInformation> statements;
  HStatementSequenceInformation(this.statements);

  HBasicBlock get start => statements[0].start;
  HBasicBlock get end => statements.last.end;

  bool accept(HStatementInformationVisitor visitor) =>
    visitor.visitSequenceInfo(this);
}


class HLabeledBlockInformation implements HStatementInformation {
  final HStatementInformation body;
  final List<LabelElement> labels;
  final TargetElement target;
  final bool isContinue;

  HLabeledBlockInformation(this.body,
                           List<LabelElement> labels,
                           {this.isContinue: false}) :
      this.labels = labels, this.target = labels[0].target;

  HLabeledBlockInformation.implicit(this.body,
                                    this.target,
                                    {this.isContinue: false})
      : this.labels = const<LabelElement>[];

  HBasicBlock get start => body.start;
  HBasicBlock get end => body.end;

  bool accept(HStatementInformationVisitor visitor) =>
    visitor.visitLabeledBlockInfo(this);
}

class LoopTypeVisitor extends Visitor {
  const LoopTypeVisitor();
  int visitNode(Node node) => HLoopBlockInformation.NOT_A_LOOP;
  int visitWhile(While node) => HLoopBlockInformation.WHILE_LOOP;
  int visitFor(For node) => HLoopBlockInformation.FOR_LOOP;
  int visitDoWhile(DoWhile node) => HLoopBlockInformation.DO_WHILE_LOOP;
  int visitForIn(ForIn node) => HLoopBlockInformation.FOR_IN_LOOP;
}

class HLoopBlockInformation implements HStatementInformation {
  static const int WHILE_LOOP = 0;
  static const int FOR_LOOP = 1;
  static const int DO_WHILE_LOOP = 2;
  static const int FOR_IN_LOOP = 3;
  static const int NOT_A_LOOP = -1;

  final int kind;
  final HExpressionInformation initializer;
  final HExpressionInformation condition;
  final HStatementInformation body;
  final HExpressionInformation updates;
  final TargetElement target;
  final List<LabelElement> labels;
  final SourceFileLocation sourcePosition;
  final SourceFileLocation endSourcePosition;

  HLoopBlockInformation(this.kind,
                        this.initializer,
                        this.condition,
                        this.body,
                        this.updates,
                        this.target,
                        this.labels,
                        this.sourcePosition,
                        this.endSourcePosition);

  HBasicBlock get start {
    if (initializer != null) return initializer.start;
    if (kind == DO_WHILE_LOOP) {
      return body.start;
    }
    return condition.start;
  }

  HBasicBlock get loopHeader {
    return kind == DO_WHILE_LOOP ? body.start : condition.start;
  }

  HBasicBlock get end {
    if (updates != null) return updates.end;
    if (kind == DO_WHILE_LOOP && condition != null) {
      return condition.end;
    }
    return body.end;
  }

  static int loopType(Node node) {
    return node.accept(const LoopTypeVisitor());
  }

  bool accept(HStatementInformationVisitor visitor) =>
    visitor.visitLoopInfo(this);
}

class HIfBlockInformation implements HStatementInformation {
  final HExpressionInformation condition;
  final HStatementInformation thenGraph;
  final HStatementInformation elseGraph;
  HIfBlockInformation(this.condition,
                      this.thenGraph,
                      this.elseGraph);

  HBasicBlock get start => condition.start;
  HBasicBlock get end => elseGraph == null ? thenGraph.end : elseGraph.end;

  bool accept(HStatementInformationVisitor visitor) =>
    visitor.visitIfInfo(this);
}

class HAndOrBlockInformation implements HExpressionInformation {
  final bool isAnd;
  final HExpressionInformation left;
  final HExpressionInformation right;
  HAndOrBlockInformation(this.isAnd,
                         this.left,
                         this.right);

  HBasicBlock get start => left.start;
  HBasicBlock get end => right.end;

  // We don't currently use HAndOrBlockInformation.
  HInstruction get conditionExpression {
    return null;
  }
  bool accept(HExpressionInformationVisitor visitor) =>
    visitor.visitAndOrInfo(this);
}

class HTryBlockInformation implements HStatementInformation {
  final HStatementInformation body;
  final HParameterValue catchVariable;
  final HStatementInformation catchBlock;
  final HStatementInformation finallyBlock;
  HTryBlockInformation(this.body,
                       this.catchVariable,
                       this.catchBlock,
                       this.finallyBlock);

  HBasicBlock get start => body.start;
  HBasicBlock get end =>
      finallyBlock == null ? catchBlock.end : finallyBlock.end;

  bool accept(HStatementInformationVisitor visitor) =>
    visitor.visitTryInfo(this);
}


class HSwitchBlockInformation implements HStatementInformation {
  final HExpressionInformation expression;
  final List<List<Constant>> matchExpressions;
  final List<HStatementInformation> statements;
  // If the switch has a default, it's the last statement block, which
  // may or may not have other expresions.
  final bool hasDefault;
  final TargetElement target;
  final List<LabelElement> labels;

  HSwitchBlockInformation(this.expression,
                          this.matchExpressions,
                          this.statements,
                          this.hasDefault,
                          this.target,
                          this.labels);

  HBasicBlock get start => expression.start;
  HBasicBlock get end {
    // We don't create a switch block if there are no cases.
    assert(!statements.isEmpty);
    return statements.last.end;
  }

  bool accept(HStatementInformationVisitor visitor) =>
      visitor.visitSwitchInfo(this);
}