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

/**
 * Instead of emitting each SSA instruction with a temporary variable
 * mark instructions that can be emitted at their use-site.
 * For example, in:
 *   t0 = 4;
 *   t1 = 3;
 *   t2 = add(t0, t1);
 * t0 and t1 would be marked and the resulting code would then be:
 *   t2 = add(4, 3);
 */
class SsaInstructionMerger extends HBaseVisitor {
  /**
   * List of [HInstruction] that the instruction merger expects in
   * order when visiting the inputs of an instruction.
   */
  List<HInstruction> expectedInputs;
  /**
   * Set of pure [HInstruction] that the instruction merger expects to
   * find. The order of pure instructions do not matter, as they will
   * not be affected by side effects.
   */
  Set<HInstruction> pureInputs;
  Set<HInstruction> generateAtUseSite;

  void markAsGenerateAtUseSite(HInstruction instruction) {
    assert(!instruction.isJsStatement());
    generateAtUseSite.add(instruction);
  }

  SsaInstructionMerger(this.generateAtUseSite);

  void visitGraph(HGraph graph) {
    visitDominatorTree(graph);
  }

  void analyzeInputs(HInstruction user, int start) {
    List<HInstruction> inputs = user.inputs;
    for (int i = start; i < inputs.length; i++) {
      HInstruction input = inputs[i];
      if (!generateAtUseSite.contains(input)
          && !input.isCodeMotionInvariant()
          && input.usedBy.length == 1
          && input is !HPhi
          && input is !HLocalValue
          && !input.isJsStatement()) {
        if (input.isPure()) {
          // Only consider a pure input if it is in the same loop.
          // Otherwise, we might move GVN'ed instruction back into the
          // loop.
          if (user.hasSameLoopHeaderAs(input)) {
            // Move it closer to [user], so that instructions in
            // between do not prevent making it generate at use site.
            input.moveBefore(user);
            pureInputs.add(input);
            // Previous computations done on [input] are now invalid
            // because we moved [input] to another place. So all
            // non code motion invariant instructions need
            // to be removed from the [generateAtUseSite] set.
            input.inputs.forEach((instruction) {
              if (!instruction.isCodeMotionInvariant()) {
                generateAtUseSite.remove(instruction);
              }
            });
            // Visit the pure input now so that the expected inputs
            // are after the expected inputs of [user].
            input.accept(this);
          }
        } else {
          expectedInputs.add(input);
        }
      }
    }
  }

  void visitInstruction(HInstruction instruction) {
    // A code motion invariant instruction is dealt before visiting it.
    assert(!instruction.isCodeMotionInvariant());
    analyzeInputs(instruction, 0);
  }

  // The codegen might use the input multiple times, so it must not be
  // set generate at use site.
  void visitIs(HIs instruction) {}

  // A bounds check method must not have its first input generated at use site,
  // because it's using it twice.
  void visitBoundsCheck(HBoundsCheck instruction) {
    analyzeInputs(instruction, 1);
  }

  // A type guard should not generate its input at use site, otherwise
  // they would not be alive.
  void visitTypeGuard(HTypeGuard instruction) {}

  // An identity operation must only have its inputs generated at use site if
  // does not require an expression with multiple uses (because of null /
  // undefined).
  void visitIdentity(HIdentity instruction) {
    HInstruction left = instruction.left;
    HInstruction right = instruction.right;
    if (singleIdentityComparison(left, right) != null) {
      super.visitIdentity(instruction);
    }
    // Do nothing.
  }

  void visitTypeConversion(HTypeConversion instruction) {
    if (!instruction.isChecked) {
      markAsGenerateAtUseSite(instruction);
    } else if (!instruction.isArgumentTypeCheck
               && !instruction.isReceiverTypeCheck) {
      assert(instruction.isCheckedModeCheck || instruction.isCastTypeCheck);
      // Checked mode checks and cast checks compile to code that
      // only use their input once, so we can safely visit them
      // and try to merge the input.
      visitInstruction(instruction);
    }
  }

  void tryGenerateAtUseSite(HInstruction instruction) {
    if (instruction.isControlFlow()) return;
    markAsGenerateAtUseSite(instruction);
  }

  bool isBlockSinglePredecessor(HBasicBlock block) {
    return block.successors.length == 1
        && block.successors[0].predecessors.length == 1;
  }

  void visitBasicBlock(HBasicBlock block) {
    // Compensate from not merging blocks: if the block is the
    // single predecessor of its single successor, let the successor
    // visit it.
    if (isBlockSinglePredecessor(block)) return;

    tryMergingExpressions(block);
  }

  void tryMergingExpressions(HBasicBlock block) {
    // Visit each instruction of the basic block in last-to-first order.
    // Keep a list of expected inputs of the current "expression" being
    // merged. If instructions occur in the expected order, they are
    // included in the expression.

    // The expectedInputs list holds non-trivial instructions that may
    // be generated at their use site, if they occur in the correct order.
    if (expectedInputs == null) expectedInputs = new List<HInstruction>();
    if (pureInputs == null) pureInputs = new Set<HInstruction>();

    // Pop instructions from expectedInputs until instruction is found.
    // Return true if it is found, or false if not.
    bool findInInputsAndPopNonMatching(HInstruction instruction) {
      assert(!instruction.isPure());
      while (!expectedInputs.isEmpty) {
        HInstruction nextInput = expectedInputs.removeLast();
        assert(!generateAtUseSite.contains(nextInput));
        assert(nextInput.usedBy.length == 1);
        if (identical(nextInput, instruction)) {
          return true;
        }
      }
      return false;
    }

    block.last.accept(this);
    for (HInstruction instruction = block.last.previous;
         instruction != null;
         instruction = instruction.previous) {
      if (generateAtUseSite.contains(instruction)) {
        continue;
      }
      if (instruction.isCodeMotionInvariant()) {
        markAsGenerateAtUseSite(instruction);
        continue;
      }
      if (instruction.isJsStatement()) {
        expectedInputs.clear();
      }
      if (instruction.isPure()) {
        if (pureInputs.contains(instruction)) {
          tryGenerateAtUseSite(instruction);
        } else {
          // If the input is not in the [pureInputs] set, it has not
          // been visited.
          instruction.accept(this);
        }
      } else {
        if (findInInputsAndPopNonMatching(instruction)) {
          // The current instruction is the next non-trivial
          // expected input.
          tryGenerateAtUseSite(instruction);
        } else {
          assert(expectedInputs.isEmpty);
        }
        instruction.accept(this);
      }
    }

    if (block.predecessors.length == 1
        && isBlockSinglePredecessor(block.predecessors[0])) {
      assert(block.phis.isEmpty);
      tryMergingExpressions(block.predecessors[0]);
    } else {
      expectedInputs = null;
      pureInputs = null;
    }
  }
}

/**
 *  Detect control flow arising from short-circuit logical and
 *  conditional operators, and prepare the program to be generated
 *  using these operators instead of nested ifs and boolean variables.
 */
class SsaConditionMerger extends HGraphVisitor {
  Set<HInstruction> generateAtUseSite;
  Set<HInstruction> controlFlowOperators;

  void markAsGenerateAtUseSite(HInstruction instruction) {
    assert(!instruction.isJsStatement());
    generateAtUseSite.add(instruction);
  }

  SsaConditionMerger(this.generateAtUseSite, this.controlFlowOperators);

  void visitGraph(HGraph graph) {
    visitPostDominatorTree(graph);
  }

  /**
   * Check if a block has at least one statement other than
   * [instruction].
   */
  bool hasAnyStatement(HBasicBlock block, HInstruction instruction) {
    // If [instruction] is not in [block], then if the block is not
    // empty, we know there will be a statement to emit.
    if (!identical(instruction.block, block)) return !identical(block.last, block.first);

    // If [instruction] is not the last instruction of the block
    // before the control flow instruction, or the last instruction,
    // then we will have to emit a statement for that last instruction.
    if (instruction != block.last
        && !identical(instruction, block.last.previous)) return true;

    // If one of the instructions in the block until [instruction] is
    // not generated at use site, then we will have to emit a
    // statement for it.
    // TODO(ngeoffray): we could generate a comma separated
    // list of expressions.
    for (HInstruction temp = block.first;
         !identical(temp, instruction);
         temp = temp.next) {
      if (!generateAtUseSite.contains(temp)) return true;
    }

    return false;
  }

  bool isSafeToGenerateAtUseSite(HInstruction user, HInstruction input) {
    // A [HForeign] instruction uses operators and if we generate
    // [input] at use site, the precedence might be wrong.
    if (user is HForeign) return false;
    // A [HCheck] instruction with control flow uses its input
    // multiple times, so we avoid generating it at use site.
    if (user is HCheck && user.isControlFlow()) return false;
    // A [HIs] instruction uses its input multiple times, so we
    // avoid generating it at use site.
    if (user is HIs) return false;
    return true;
  }

  void visitBasicBlock(HBasicBlock block) {
    if (block.last is !HIf) return;
    HIf startIf = block.last;
    HBasicBlock end = startIf.joinBlock;

    // We check that the structure is the following:
    //         If
    //       /    \
    //      /      \
    //   1 expr    goto
    //    goto     /
    //      \     /
    //       \   /
    // phi(expr, true|false)
    //
    // and the same for nested nodes:
    //
    //            If
    //          /    \
    //         /      \
    //      1 expr1    \
    //       If         \
    //      /  \         \
    //     /    \         goto
    //  1 expr2            |
    //    goto    goto     |
    //      \     /        |
    //       \   /         |
    //   phi1(expr2, true|false)
    //          \          |
    //           \         |
    //             phi(phi1, true|false)

    if (end == null) return;
    if (end.phis.isEmpty) return;
    if (!identical(end.phis.first, end.phis.last)) return;
    HBasicBlock elseBlock = startIf.elseBlock;

    if (!identical(end.predecessors[1], elseBlock)) return;
    HPhi phi = end.phis.first;
    HInstruction thenInput = phi.inputs[0];
    HInstruction elseInput = phi.inputs[1];
    if (thenInput.isJsStatement() || elseInput.isJsStatement()) return;

    if (hasAnyStatement(elseBlock, elseInput)) return;
    assert(elseBlock.successors.length == 1);
    assert(end.predecessors.length == 2);

    HBasicBlock thenBlock = startIf.thenBlock;
    // Skip trivial goto blocks.
    while (thenBlock.successors[0] != end && thenBlock.first is HGoto) {
      thenBlock = thenBlock.successors[0];
    }

    // If the [thenBlock] is already a control flow operation, and does not
    // have any statement and its join block is [end], we can emit a
    // sequence of control flow operation.
    if (controlFlowOperators.contains(thenBlock.last)) {
      HIf otherIf = thenBlock.last;
      if (!identical(otherIf.joinBlock, end)) {
        // This could be a join block that just feeds into our join block.
        HBasicBlock otherJoin = otherIf.joinBlock;
        if (otherJoin.first != otherJoin.last) return;
        if (otherJoin.successors.length != 1) return;
        if (otherJoin.successors[0] != end) return;
        if (otherJoin.phis.isEmpty) return;
        if (!identical(otherJoin.phis.first, otherJoin.phis.last)) return;
        HPhi otherPhi = otherJoin.phis.first;
        if (thenInput != otherPhi) return;
        if (elseInput != otherPhi.inputs[1]) return;
      }
      if (hasAnyStatement(thenBlock, otherIf)) return;
    } else {
      if (!identical(end.predecessors[0], thenBlock)) return;
      if (hasAnyStatement(thenBlock, thenInput)) return;
      assert(thenBlock.successors.length == 1);
    }

    // From now on, we have recognized a control flow operation built from
    // the builder. Mark the if instruction as such.
    controlFlowOperators.add(startIf);

    // Find the next non-HGoto instruction following the phi.
    HInstruction nextInstruction = phi.block.first;
    while (nextInstruction is HGoto) {
      nextInstruction = nextInstruction.block.successors[0].first;
    }

    // If the operation is only used by the first instruction
    // of its block and is safe to be generated at use site, mark it
    // so.
    if (phi.usedBy.length == 1
        && phi.usedBy[0] == nextInstruction
        && isSafeToGenerateAtUseSite(phi.usedBy[0], phi)) {
      markAsGenerateAtUseSite(phi);
    }

    if (identical(elseInput.block, elseBlock)) {
      assert(elseInput.usedBy.length == 1);
      markAsGenerateAtUseSite(elseInput);
    }

    // If [thenInput] is defined in the first predecessor, then it is only used
    // by [phi] and can be generated at use site.
    if (identical(thenInput.block, end.predecessors[0])) {
      assert(thenInput.usedBy.length == 1);
      markAsGenerateAtUseSite(thenInput);
    }
  }
}