// Copyright 2014 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/common-operator.h"
#include "src/compiler/control-reducer.h"
#include "src/compiler/graph.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/node-matchers.h"
#include "src/compiler/node-properties-inl.h"
#include "src/zone-containers.h"

namespace v8 {
namespace internal {
namespace compiler {

enum VisitState { kUnvisited = 0, kOnStack = 1, kRevisit = 2, kVisited = 3 };
enum Decision { kFalse, kUnknown, kTrue };

class ReachabilityMarker : public NodeMarker<uint8_t> {
 public:
  explicit ReachabilityMarker(Graph* graph) : NodeMarker<uint8_t>(graph, 8) {}
  bool SetReachableFromEnd(Node* node) {
    uint8_t before = Get(node);
    Set(node, before | kFromEnd);
    return before & kFromEnd;
  }
  bool IsReachableFromEnd(Node* node) { return Get(node) & kFromEnd; }
  bool SetReachableFromStart(Node* node) {
    uint8_t before = Get(node);
    Set(node, before | kFromStart);
    return before & kFromStart;
  }
  bool IsReachableFromStart(Node* node) { return Get(node) & kFromStart; }
  void Push(Node* node) { Set(node, Get(node) | kFwStack); }
  void Pop(Node* node) { Set(node, Get(node) & ~kFwStack); }
  bool IsOnStack(Node* node) { return Get(node) & kFwStack; }

 private:
  enum Bit { kFromEnd = 1, kFromStart = 2, kFwStack = 4 };
};


#define TRACE(x) \
  if (FLAG_trace_turbo_reduction) PrintF x

class ControlReducerImpl {
 public:
  ControlReducerImpl(Zone* zone, JSGraph* jsgraph,
                     CommonOperatorBuilder* common)
      : zone_(zone),
        jsgraph_(jsgraph),
        common_(common),
        state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_),
        stack_(zone_),
        revisit_(zone_),
        dead_(NULL) {}

  Zone* zone_;
  JSGraph* jsgraph_;
  CommonOperatorBuilder* common_;
  ZoneVector<VisitState> state_;
  ZoneDeque<Node*> stack_;
  ZoneDeque<Node*> revisit_;
  Node* dead_;

  void Reduce() {
    Push(graph()->end());
    do {
      // Process the node on the top of the stack, potentially pushing more
      // or popping the node off the stack.
      ReduceTop();
      // If the stack becomes empty, revisit any nodes in the revisit queue.
      // If no nodes in the revisit queue, try removing dead loops.
      // If no dead loops, then finish.
    } while (!stack_.empty() || TryRevisit() || RepairAndRemoveLoops());
  }

  bool TryRevisit() {
    while (!revisit_.empty()) {
      Node* n = revisit_.back();
      revisit_.pop_back();
      if (state_[n->id()] == kRevisit) {  // state can change while in queue.
        Push(n);
        return true;
      }
    }
    return false;
  }

  // Repair the graph after the possible creation of non-terminating or dead
  // loops. Removing dead loops can produce more opportunities for reduction.
  bool RepairAndRemoveLoops() {
    // TODO(turbofan): we can skip this if the graph has no loops, but
    // we have to be careful about proper loop detection during reduction.

    // Gather all nodes backwards-reachable from end (through inputs).
    ReachabilityMarker marked(graph());
    NodeVector nodes(zone_);
    AddNodesReachableFromEnd(marked, nodes);

    // Walk forward through control nodes, looking for back edges to nodes
    // that are not connected to end. Those are non-terminating loops (NTLs).
    Node* start = graph()->start();
    marked.Push(start);
    marked.SetReachableFromStart(start);

    // We use a stack of (Node, UseIter) pairs to avoid O(n^2) traversal.
    typedef std::pair<Node*, UseIter> FwIter;
    ZoneVector<FwIter> fw_stack(zone_);
    fw_stack.push_back(FwIter(start, start->uses().begin()));

    while (!fw_stack.empty()) {
      Node* node = fw_stack.back().first;
      TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic()));
      bool pop = true;
      while (fw_stack.back().second != node->uses().end()) {
        Node* succ = *(fw_stack.back().second);
        if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) {
          // {succ} is on stack and not reachable from end.
          Node* added = ConnectNTL(succ);
          nodes.push_back(added);
          marked.SetReachableFromEnd(added);
          AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);

          // Reset the use iterators for the entire stack.
          for (size_t i = 0; i < fw_stack.size(); i++) {
            FwIter& iter = fw_stack[i];
            fw_stack[i] = FwIter(iter.first, iter.first->uses().begin());
          }
          pop = false;  // restart traversing successors of this node.
          break;
        }
        if (IrOpcode::IsControlOpcode(succ->opcode()) &&
            !marked.IsReachableFromStart(succ)) {
          // {succ} is a control node and not yet reached from start.
          marked.Push(succ);
          marked.SetReachableFromStart(succ);
          fw_stack.push_back(FwIter(succ, succ->uses().begin()));
          pop = false;  // "recurse" into successor control node.
          break;
        }
        ++fw_stack.back().second;
      }
      if (pop) {
        marked.Pop(node);
        fw_stack.pop_back();
      }
    }

    // Trim references from dead nodes to live nodes first.
    jsgraph_->GetCachedNodes(&nodes);
    TrimNodes(marked, nodes);

    // Any control nodes not reachable from start are dead, even loops.
    for (size_t i = 0; i < nodes.size(); i++) {
      Node* node = nodes[i];
      if (IrOpcode::IsControlOpcode(node->opcode()) &&
          !marked.IsReachableFromStart(node)) {
        ReplaceNode(node, dead());  // uses will be added to revisit queue.
      }
    }
    return TryRevisit();  // try to push a node onto the stack.
  }

  // Connect {loop}, the header of a non-terminating loop, to the end node.
  Node* ConnectNTL(Node* loop) {
    TRACE(("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic()));

    if (loop->opcode() != IrOpcode::kTerminate) {
      // Insert a {Terminate} node if the loop has effects.
      ZoneDeque<Node*> effects(zone_);
      for (Node* const use : loop->uses()) {
        if (use->opcode() == IrOpcode::kEffectPhi) effects.push_back(use);
      }
      int count = static_cast<int>(effects.size());
      if (count > 0) {
        Node** inputs = zone_->NewArray<Node*>(1 + count);
        for (int i = 0; i < count; i++) inputs[i] = effects[i];
        inputs[count] = loop;
        loop = graph()->NewNode(common_->Terminate(count), 1 + count, inputs);
        TRACE(("AddTerminate: #%d:%s[%d]\n", loop->id(), loop->op()->mnemonic(),
               count));
      }
    }

    Node* to_add = loop;
    Node* end = graph()->end();
    CHECK_EQ(IrOpcode::kEnd, end->opcode());
    Node* merge = end->InputAt(0);
    if (merge == NULL || merge->opcode() == IrOpcode::kDead) {
      // The end node died; just connect end to {loop}.
      end->ReplaceInput(0, loop);
    } else if (merge->opcode() != IrOpcode::kMerge) {
      // Introduce a final merge node for {end->InputAt(0)} and {loop}.
      merge = graph()->NewNode(common_->Merge(2), merge, loop);
      end->ReplaceInput(0, merge);
      to_add = merge;
      // Mark the node as visited so that we can revisit later.
      EnsureStateSize(merge->id());
      state_[merge->id()] = kVisited;
    } else {
      // Append a new input to the final merge at the end.
      merge->AppendInput(graph()->zone(), loop);
      merge->set_op(common_->Merge(merge->InputCount()));
    }
    return to_add;
  }

  void AddNodesReachableFromEnd(ReachabilityMarker& marked, NodeVector& nodes) {
    Node* end = graph()->end();
    marked.SetReachableFromEnd(end);
    if (!end->IsDead()) {
      nodes.push_back(end);
      AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
    }
  }

  void AddBackwardsReachableNodes(ReachabilityMarker& marked, NodeVector& nodes,
                                  size_t cursor) {
    while (cursor < nodes.size()) {
      Node* node = nodes[cursor++];
      for (Node* const input : node->inputs()) {
        if (!marked.SetReachableFromEnd(input)) {
          nodes.push_back(input);
        }
      }
    }
  }

  void Trim() {
    // Gather all nodes backwards-reachable from end through inputs.
    ReachabilityMarker marked(graph());
    NodeVector nodes(zone_);
    AddNodesReachableFromEnd(marked, nodes);

    // Process cached nodes in the JSGraph too.
    jsgraph_->GetCachedNodes(&nodes);
    TrimNodes(marked, nodes);
  }

  void TrimNodes(ReachabilityMarker& marked, NodeVector& nodes) {
    // Remove dead->live edges.
    for (size_t j = 0; j < nodes.size(); j++) {
      Node* node = nodes[j];
      for (Edge edge : node->use_edges()) {
        Node* use = edge.from();
        if (!marked.IsReachableFromEnd(use)) {
          TRACE(("DeadLink: #%d:%s(%d) -> #%d:%s\n", use->id(),
                 use->op()->mnemonic(), edge.index(), node->id(),
                 node->op()->mnemonic()));
          edge.UpdateTo(NULL);
        }
      }
    }
#if DEBUG
    // Verify that no inputs to live nodes are NULL.
    for (size_t j = 0; j < nodes.size(); j++) {
      Node* node = nodes[j];
      for (Node* const input : node->inputs()) {
        CHECK_NE(NULL, input);
      }
      for (Node* const use : node->uses()) {
        CHECK(marked.IsReachableFromEnd(use));
      }
    }
#endif
  }

  // Reduce the node on the top of the stack.
  // If an input {i} is not yet visited or needs to be revisited, push {i} onto
  // the stack and return. Otherwise, all inputs are visited, so apply
  // reductions for {node} and pop it off the stack.
  void ReduceTop() {
    size_t height = stack_.size();
    Node* node = stack_.back();

    if (node->IsDead()) return Pop();  // Node was killed while on stack.

    TRACE(("ControlReduce: #%d:%s\n", node->id(), node->op()->mnemonic()));

    // Recurse on an input if necessary.
    for (Node* const input : node->inputs()) {
      if (Recurse(input)) return;
    }

    // All inputs should be visited or on stack. Apply reductions to node.
    Node* replacement = ReduceNode(node);
    if (replacement != node) ReplaceNode(node, replacement);

    // After reducing the node, pop it off the stack.
    CHECK_EQ(static_cast<int>(height), static_cast<int>(stack_.size()));
    Pop();

    // If there was a replacement, reduce it after popping {node}.
    if (replacement != node) Recurse(replacement);
  }

  void EnsureStateSize(size_t id) {
    if (id >= state_.size()) {
      state_.resize((3 * id) / 2, kUnvisited);
    }
  }

  // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}.
  bool Recurse(Node* node) {
    size_t id = static_cast<size_t>(node->id());
    EnsureStateSize(id);
    if (state_[id] != kRevisit && state_[id] != kUnvisited) return false;
    Push(node);
    return true;
  }

  void Push(Node* node) {
    state_[node->id()] = kOnStack;
    stack_.push_back(node);
  }

  void Pop() {
    int pos = static_cast<int>(stack_.size()) - 1;
    DCHECK_GE(pos, 0);
    DCHECK_EQ(kOnStack, state_[stack_[pos]->id()]);
    state_[stack_[pos]->id()] = kVisited;
    stack_.pop_back();
  }

  // Queue a node to be revisited if it has been visited once already.
  void Revisit(Node* node) {
    size_t id = static_cast<size_t>(node->id());
    if (id < state_.size() && state_[id] == kVisited) {
      TRACE(("  Revisit #%d:%s\n", node->id(), node->op()->mnemonic()));
      state_[id] = kRevisit;
      revisit_.push_back(node);
    }
  }

  Node* dead() {
    if (dead_ == NULL) dead_ = graph()->NewNode(common_->Dead());
    return dead_;
  }

  //===========================================================================
  // Reducer implementation: perform reductions on a node.
  //===========================================================================
  Node* ReduceNode(Node* node) {
    if (node->op()->ControlInputCount() == 1) {
      // If a node has only one control input and it is dead, replace with dead.
      Node* control = NodeProperties::GetControlInput(node);
      if (control->opcode() == IrOpcode::kDead) {
        TRACE(("ControlDead: #%d:%s\n", node->id(), node->op()->mnemonic()));
        return control;
      }
    }

    // Reduce branches, phis, and merges.
    switch (node->opcode()) {
      case IrOpcode::kBranch:
        return ReduceBranch(node);
      case IrOpcode::kLoop:
      case IrOpcode::kMerge:
        return ReduceMerge(node);
      case IrOpcode::kSelect:
        return ReduceSelect(node);
      case IrOpcode::kPhi:
      case IrOpcode::kEffectPhi:
        return ReducePhi(node);
      default:
        return node;
    }
  }

  // Try to statically fold a condition.
  Decision DecideCondition(Node* cond) {
    switch (cond->opcode()) {
      case IrOpcode::kInt32Constant:
        return Int32Matcher(cond).Is(0) ? kFalse : kTrue;
      case IrOpcode::kInt64Constant:
        return Int64Matcher(cond).Is(0) ? kFalse : kTrue;
      case IrOpcode::kNumberConstant:
        return NumberMatcher(cond).Is(0) ? kFalse : kTrue;
      case IrOpcode::kHeapConstant: {
        Handle<Object> object =
            HeapObjectMatcher<Object>(cond).Value().handle();
        if (object->IsTrue()) return kTrue;
        if (object->IsFalse()) return kFalse;
        // TODO(turbofan): decide more conditions for heap constants.
        break;
      }
      default:
        break;
    }
    return kUnknown;
  }

  // Reduce redundant selects.
  Node* ReduceSelect(Node* const node) {
    Node* const tvalue = node->InputAt(1);
    Node* const fvalue = node->InputAt(2);
    if (tvalue == fvalue) return tvalue;
    Decision result = DecideCondition(node->InputAt(0));
    if (result == kTrue) return tvalue;
    if (result == kFalse) return fvalue;
    return node;
  }

  // Reduce redundant phis.
  Node* ReducePhi(Node* node) {
    int n = node->InputCount();
    if (n <= 1) return dead();            // No non-control inputs.
    if (n == 2) return node->InputAt(0);  // Only one non-control input.

    // Never remove an effect phi from a (potentially non-terminating) loop.
    // Otherwise, we might end up eliminating effect nodes, such as calls,
    // before the loop.
    if (node->opcode() == IrOpcode::kEffectPhi &&
        NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) {
      return node;
    }

    Node* replacement = NULL;
    Node::Inputs inputs = node->inputs();
    for (InputIter it = inputs.begin(); n > 1; --n, ++it) {
      Node* input = *it;
      if (input->opcode() == IrOpcode::kDead) continue;  // ignore dead inputs.
      if (input != node && input != replacement) {       // non-redundant input.
        if (replacement != NULL) return node;
        replacement = input;
      }
    }
    return replacement == NULL ? dead() : replacement;
  }

  // Reduce merges by trimming away dead inputs from the merge and phis.
  Node* ReduceMerge(Node* node) {
    // Count the number of live inputs.
    int live = 0;
    int index = 0;
    int live_index = 0;
    for (Node* const input : node->inputs()) {
      if (input->opcode() != IrOpcode::kDead) {
        live++;
        live_index = index;
      }
      index++;
    }

    if (live > 1 && live == node->InputCount()) return node;  // nothing to do.

    TRACE(("ReduceMerge: #%d:%s (%d live)\n", node->id(),
           node->op()->mnemonic(), live));

    if (live == 0) return dead();  // no remaining inputs.

    // Gather phis and effect phis to be edited.
    ZoneVector<Node*> phis(zone_);
    for (Node* const use : node->uses()) {
      if (use->opcode() == IrOpcode::kPhi ||
          use->opcode() == IrOpcode::kEffectPhi) {
        phis.push_back(use);
      }
    }

    if (live == 1) {
      // All phis are redundant. Replace them with their live input.
      for (Node* const phi : phis) ReplaceNode(phi, phi->InputAt(live_index));
      // The merge itself is redundant.
      return node->InputAt(live_index);
    }

    // Edit phis in place, removing dead inputs and revisiting them.
    for (Node* const phi : phis) {
      TRACE(("  PhiInMerge: #%d:%s (%d live)\n", phi->id(),
             phi->op()->mnemonic(), live));
      RemoveDeadInputs(node, phi);
      Revisit(phi);
    }
    // Edit the merge in place, removing dead inputs.
    RemoveDeadInputs(node, node);
    return node;
  }

  // Reduce branches if they have constant inputs.
  Node* ReduceBranch(Node* node) {
    Decision result = DecideCondition(node->InputAt(0));
    if (result == kUnknown) return node;

    TRACE(("BranchReduce: #%d:%s = %s\n", node->id(), node->op()->mnemonic(),
           (result == kTrue) ? "true" : "false"));

    // Replace IfTrue and IfFalse projections from this branch.
    Node* control = NodeProperties::GetControlInput(node);
    for (Edge edge : node->use_edges()) {
      Node* use = edge.from();
      if (use->opcode() == IrOpcode::kIfTrue) {
        TRACE(("  IfTrue: #%d:%s\n", use->id(), use->op()->mnemonic()));
        edge.UpdateTo(NULL);
        ReplaceNode(use, (result == kTrue) ? control : dead());
      } else if (use->opcode() == IrOpcode::kIfFalse) {
        TRACE(("  IfFalse: #%d:%s\n", use->id(), use->op()->mnemonic()));
        edge.UpdateTo(NULL);
        ReplaceNode(use, (result == kTrue) ? dead() : control);
      }
    }
    return control;
  }

  // Remove inputs to {node} corresponding to the dead inputs to {merge}
  // and compact the remaining inputs, updating the operator.
  void RemoveDeadInputs(Node* merge, Node* node) {
    int pos = 0;
    for (int i = 0; i < node->InputCount(); i++) {
      // skip dead inputs.
      if (i < merge->InputCount() &&
          merge->InputAt(i)->opcode() == IrOpcode::kDead)
        continue;
      // compact live inputs.
      if (pos != i) node->ReplaceInput(pos, node->InputAt(i));
      pos++;
    }
    node->TrimInputCount(pos);
    if (node->opcode() == IrOpcode::kPhi) {
      node->set_op(common_->Phi(OpParameter<MachineType>(node->op()), pos - 1));
    } else if (node->opcode() == IrOpcode::kEffectPhi) {
      node->set_op(common_->EffectPhi(pos - 1));
    } else if (node->opcode() == IrOpcode::kMerge) {
      node->set_op(common_->Merge(pos));
    } else if (node->opcode() == IrOpcode::kLoop) {
      node->set_op(common_->Loop(pos));
    } else {
      UNREACHABLE();
    }
  }

  // Replace uses of {node} with {replacement} and revisit the uses.
  void ReplaceNode(Node* node, Node* replacement) {
    if (node == replacement) return;
    TRACE(("  Replace: #%d:%s with #%d:%s\n", node->id(),
           node->op()->mnemonic(), replacement->id(),
           replacement->op()->mnemonic()));
    for (Node* const use : node->uses()) {
      // Don't revisit this node if it refers to itself.
      if (use != node) Revisit(use);
    }
    node->ReplaceUses(replacement);
    node->Kill();
  }

  Graph* graph() { return jsgraph_->graph(); }
};


void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph,
                                 CommonOperatorBuilder* common) {
  ControlReducerImpl impl(zone, jsgraph, common);
  impl.Reduce();
}


void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) {
  ControlReducerImpl impl(zone, jsgraph, NULL);
  impl.Trim();
}


Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph,
                                          CommonOperatorBuilder* common,
                                          Node* node) {
  Zone zone(jsgraph->graph()->zone()->isolate());
  ControlReducerImpl impl(&zone, jsgraph, common);
  return impl.ReducePhi(node);
}


Node* ControlReducer::ReduceMergeForTesting(JSGraph* jsgraph,
                                            CommonOperatorBuilder* common,
                                            Node* node) {
  Zone zone(jsgraph->graph()->zone()->isolate());
  ControlReducerImpl impl(&zone, jsgraph, common);
  return impl.ReduceMerge(node);
}


Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph,
                                             CommonOperatorBuilder* common,
                                             Node* node) {
  Zone zone(jsgraph->graph()->zone()->isolate());
  ControlReducerImpl impl(&zone, jsgraph, common);
  return impl.ReduceBranch(node);
}
}
}
}  // namespace v8::internal::compiler