// 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/js-graph.h"
#include "src/compiler/node-matchers.h"
#include "src/compiler/node-properties.h"

namespace v8 {
namespace internal {
namespace compiler {

ControlFlowOptimizer::ControlFlowOptimizer(JSGraph* jsgraph, Zone* zone)
    : jsgraph_(jsgraph),
      queue_(zone),
      queued_(jsgraph->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 (Node* use : node->uses()) {
    if (NodeProperties::IsControl(use)) Enqueue(use);
  }
}


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

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

  Node* if_false;
  Node* if_true;
  while (true) {
    // TODO(turbofan): use NodeProperties::CollectSuccessorProjections() here
    // once available.
    auto it = branch->uses().begin();
    DCHECK(it != branch->uses().end());
    if_true = *it++;
    DCHECK(it != branch->uses().end());
    if_false = *it++;
    DCHECK(it == branch->uses().end());
    if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
    DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
    DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());

    it = if_false->uses().begin();
    if (it == if_false->uses().end()) break;
    Node* branch1 = *it++;
    if (branch1->opcode() != IrOpcode::kBranch) 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->RemoveAllInputs();
      if_true->ReplaceInput(0, node);
    }
    if_true->set_op(common()->IfValue(value));
    if_false->RemoveAllInputs();
    Enqueue(if_true);

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

  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
  DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
  DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
  if (branch == node) {
    DCHECK_EQ(1u, values.size());
    Enqueue(if_true);
    Enqueue(if_false);
  } else {
    DCHECK_LT(1u, values.size());
    node->set_op(common()->Switch(values.size() + 1));
    node->ReplaceInput(0, index);
    if_true->set_op(common()->IfValue(value));
    if_true->ReplaceInput(0, node);
    Enqueue(if_true);
    if_false->set_op(common()->IfDefault());
    if_false->ReplaceInput(0, node);
    Enqueue(if_false);
    branch->RemoveAllInputs();
  }
}


CommonOperatorBuilder* ControlFlowOptimizer::common() const {
  return jsgraph()->common();
}


Graph* ControlFlowOptimizer::graph() const { return jsgraph()->graph(); }


MachineOperatorBuilder* ControlFlowOptimizer::machine() const {
  return jsgraph()->machine();
}

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