// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/control-flow-optimizer.h"

#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
#include "src/compiler/node-matchers.h"
#include "src/compiler/node-properties.h"

namespace v8 {
namespace internal {
namespace compiler {

ControlFlowOptimizer::ControlFlowOptimizer(Graph* graph,
                                           CommonOperatorBuilder* common,
                                           MachineOperatorBuilder* machine,
                                           Zone* zone)
    : graph_(graph),
      common_(common),
      machine_(machine),
      queue_(zone),
      queued_(graph, 2),
      zone_(zone) {}


void ControlFlowOptimizer::Optimize() {
  Enqueue(graph()->start());
  while (!queue_.empty()) {
    Node* node = queue_.front();
    queue_.pop();
    if (node->IsDead()) continue;
    switch (node->opcode()) {
      case IrOpcode::kBranch:
        VisitBranch(node);
        break;
      default:
        VisitNode(node);
        break;
    }
  }
}


void ControlFlowOptimizer::Enqueue(Node* node) {
  DCHECK_NOT_NULL(node);
  if (node->IsDead() || queued_.Get(node)) return;
  queued_.Set(node, true);
  queue_.push(node);
}


void ControlFlowOptimizer::VisitNode(Node* node) {
  for (Edge edge : node->use_edges()) {
    if (NodeProperties::IsControlEdge(edge)) {
      Enqueue(edge.from());
    }
  }
}


void ControlFlowOptimizer::VisitBranch(Node* node) {
  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  if (TryBuildSwitch(node)) return;
  if (TryCloneBranch(node)) return;
  VisitNode(node);
}


bool ControlFlowOptimizer::TryCloneBranch(Node* node) {
  DCHECK_EQ(IrOpcode::kBranch, node->opcode());

  // This optimization is a special case of (super)block cloning. It takes an
  // input graph as shown below and clones the Branch node for every predecessor
  // to the Merge, essentially removing the Merge completely. This avoids
  // materializing the bit for the Phi and may offer potential for further
  // branch folding optimizations (i.e. because one or more inputs to the Phi is
  // a constant). Note that there may be more Phi nodes hanging off the Merge,
  // but we can only a certain subset of them currently (actually only Phi and
  // EffectPhi nodes whose uses have either the IfTrue or IfFalse as control
  // input).

  //   Control1 ... ControlN
  //      ^            ^
  //      |            |   Cond1 ... CondN
  //      +----+  +----+     ^         ^
  //           |  |          |         |
  //           |  |     +----+         |
  //          Merge<--+ | +------------+
  //            ^      \|/
  //            |      Phi
  //            |       |
  //          Branch----+
  //            ^
  //            |
  //      +-----+-----+
  //      |           |
  //    IfTrue     IfFalse
  //      ^           ^
  //      |           |

  // The resulting graph (modulo the Phi and EffectPhi nodes) looks like this:

  // Control1 Cond1 ... ControlN CondN
  //    ^      ^           ^      ^
  //    \      /           \      /
  //     Branch     ...     Branch
  //       ^                  ^
  //       |                  |
  //   +---+---+          +---+----+
  //   |       |          |        |
  // IfTrue IfFalse ... IfTrue  IfFalse
  //   ^       ^          ^        ^
  //   |       |          |        |
  //   +--+ +-------------+        |
  //      | |  +--------------+ +--+
  //      | |                 | |
  //     Merge               Merge
  //       ^                   ^
  //       |                   |

  Node* branch = node;
  Node* cond = NodeProperties::GetValueInput(branch, 0);
  if (!cond->OwnedBy(branch) || cond->opcode() != IrOpcode::kPhi) return false;
  Node* merge = NodeProperties::GetControlInput(branch);
  if (merge->opcode() != IrOpcode::kMerge ||
      NodeProperties::GetControlInput(cond) != merge) {
    return false;
  }
  // Grab the IfTrue/IfFalse projections of the Branch.
  BranchMatcher matcher(branch);
  // Check/collect other Phi/EffectPhi nodes hanging off the Merge.
  NodeVector phis(zone());
  for (Node* const use : merge->uses()) {
    if (use == branch || use == cond) continue;
    // We cannot currently deal with non-Phi/EffectPhi nodes hanging off the
    // Merge. Ideally, we would just clone the nodes (and everything that
    // depends on it to some distant join point), but that requires knowledge
    // about dominance/post-dominance.
    if (!NodeProperties::IsPhi(use)) return false;
    for (Edge edge : use->use_edges()) {
      // Right now we can only handle Phi/EffectPhi nodes whose uses are
      // directly control-dependend on either the IfTrue or the IfFalse
      // successor, because we know exactly how to update those uses.
      // TODO(turbofan): Generalize this to all Phi/EffectPhi nodes using
      // dominance/post-dominance on the sea of nodes.
      if (edge.from()->op()->ControlInputCount() != 1) return false;
      Node* control = NodeProperties::GetControlInput(edge.from());
      if (NodeProperties::IsPhi(edge.from())) {
        control = NodeProperties::GetControlInput(control, edge.index());
      }
      if (control != matcher.IfTrue() && control != matcher.IfFalse())
        return false;
    }
    phis.push_back(use);
  }
  BranchHint const hint = BranchHintOf(branch->op());
  int const input_count = merge->op()->ControlInputCount();
  DCHECK_LE(1, input_count);
  Node** const inputs = zone()->NewArray<Node*>(2 * input_count);
  Node** const merge_true_inputs = &inputs[0];
  Node** const merge_false_inputs = &inputs[input_count];
  for (int index = 0; index < input_count; ++index) {
    Node* cond1 = NodeProperties::GetValueInput(cond, index);
    Node* control1 = NodeProperties::GetControlInput(merge, index);
    Node* branch1 = graph()->NewNode(common()->Branch(hint), cond1, control1);
    merge_true_inputs[index] = graph()->NewNode(common()->IfTrue(), branch1);
    merge_false_inputs[index] = graph()->NewNode(common()->IfFalse(), branch1);
    Enqueue(branch1);
  }
  Node* const merge_true = graph()->NewNode(common()->Merge(input_count),
                                            input_count, merge_true_inputs);
  Node* const merge_false = graph()->NewNode(common()->Merge(input_count),
                                             input_count, merge_false_inputs);
  for (Node* const phi : phis) {
    for (int index = 0; index < input_count; ++index) {
      inputs[index] = phi->InputAt(index);
    }
    inputs[input_count] = merge_true;
    Node* phi_true = graph()->NewNode(phi->op(), input_count + 1, inputs);
    inputs[input_count] = merge_false;
    Node* phi_false = graph()->NewNode(phi->op(), input_count + 1, inputs);
    for (Edge edge : phi->use_edges()) {
      Node* control = NodeProperties::GetControlInput(edge.from());
      if (NodeProperties::IsPhi(edge.from())) {
        control = NodeProperties::GetControlInput(control, edge.index());
      }
      DCHECK(control == matcher.IfTrue() || control == matcher.IfFalse());
      edge.UpdateTo((control == matcher.IfTrue()) ? phi_true : phi_false);
    }
    phi->Kill();
  }
  // Fix up IfTrue and IfFalse and kill all dead nodes.
  matcher.IfFalse()->ReplaceUses(merge_false);
  matcher.IfTrue()->ReplaceUses(merge_true);
  matcher.IfFalse()->Kill();
  matcher.IfTrue()->Kill();
  branch->Kill();
  cond->Kill();
  merge->Kill();
  return true;
}


bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
  DCHECK_EQ(IrOpcode::kBranch, node->opcode());

  Node* branch = node;
  if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
  Node* cond = NodeProperties::GetValueInput(branch, 0);
  if (cond->opcode() != IrOpcode::kWord32Equal) return false;
  Int32BinopMatcher m(cond);
  Node* index = m.left().node();
  if (!m.right().HasValue()) return false;
  int32_t value = m.right().Value();
  ZoneSet<int32_t> values(zone());
  values.insert(value);

  Node* if_false;
  Node* if_true;
  while (true) {
    BranchMatcher matcher(branch);
    DCHECK(matcher.Matched());

    if_true = matcher.IfTrue();
    if_false = matcher.IfFalse();

    auto it = if_false->uses().begin();
    if (it == if_false->uses().end()) break;
    Node* branch1 = *it++;
    if (branch1->opcode() != IrOpcode::kBranch) break;
    if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
    if (it != if_false->uses().end()) break;
    Node* cond1 = branch1->InputAt(0);
    if (cond1->opcode() != IrOpcode::kWord32Equal) break;
    Int32BinopMatcher m1(cond1);
    if (m1.left().node() != index) break;
    if (!m1.right().HasValue()) break;
    int32_t value1 = m1.right().Value();
    if (values.find(value1) != values.end()) break;
    DCHECK_NE(value, value1);

    if (branch != node) {
      branch->NullAllInputs();
      if_true->ReplaceInput(0, node);
    }
    NodeProperties::ChangeOp(if_true, common()->IfValue(value));
    if_false->NullAllInputs();
    Enqueue(if_true);

    branch = branch1;
    value = value1;
    values.insert(value);
  }

  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
  if (branch == node) {
    DCHECK_EQ(1u, values.size());
    return false;
  }
  DCHECK_LT(1u, values.size());
  node->ReplaceInput(0, index);
  NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
  if_true->ReplaceInput(0, node);
  NodeProperties::ChangeOp(if_true, common()->IfValue(value));
  Enqueue(if_true);
  if_false->ReplaceInput(0, node);
  NodeProperties::ChangeOp(if_false, common()->IfDefault());
  Enqueue(if_false);
  branch->NullAllInputs();
  return true;
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8