// Copyright 2017 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/escape-analysis-reducer.h"

#include "src/compiler/all-nodes.h"
#include "src/compiler/simplified-operator.h"
#include "src/compiler/type-cache.h"
#include "src/execution/frame-constants.h"

namespace v8 {
namespace internal {
namespace compiler {

#ifdef DEBUG
#define TRACE(...)                                    \
  do {                                                \
    if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
  } while (false)
#else
#define TRACE(...)
#endif  // DEBUG

EscapeAnalysisReducer::EscapeAnalysisReducer(
    Editor* editor, JSGraph* jsgraph, EscapeAnalysisResult analysis_result,
    Zone* zone)
    : AdvancedReducer(editor),
      jsgraph_(jsgraph),
      analysis_result_(analysis_result),
      object_id_cache_(zone),
      node_cache_(jsgraph->graph(), zone),
      arguments_elements_(zone),
      zone_(zone) {}

Reduction EscapeAnalysisReducer::ReplaceNode(Node* original,
                                             Node* replacement) {
  const VirtualObject* vobject =
      analysis_result().GetVirtualObject(replacement);
  if (replacement->opcode() == IrOpcode::kDead ||
      (vobject && !vobject->HasEscaped())) {
    RelaxEffectsAndControls(original);
    return Replace(replacement);
  }
  Type const replacement_type = NodeProperties::GetType(replacement);
  Type const original_type = NodeProperties::GetType(original);
  if (replacement_type.Is(original_type)) {
    RelaxEffectsAndControls(original);
    return Replace(replacement);
  }

  // We need to guard the replacement if we would widen the type otherwise.
  DCHECK_EQ(1, original->op()->EffectOutputCount());
  DCHECK_EQ(1, original->op()->EffectInputCount());
  DCHECK_EQ(1, original->op()->ControlInputCount());
  Node* effect = NodeProperties::GetEffectInput(original);
  Node* control = NodeProperties::GetControlInput(original);
  original->TrimInputCount(0);
  original->AppendInput(jsgraph()->zone(), replacement);
  original->AppendInput(jsgraph()->zone(), effect);
  original->AppendInput(jsgraph()->zone(), control);
  NodeProperties::SetType(
      original,
      Type::Intersect(original_type, replacement_type, jsgraph()->zone()));
  NodeProperties::ChangeOp(original,
                           jsgraph()->common()->TypeGuard(original_type));
  ReplaceWithValue(original, original, original, control);
  return NoChange();
}

namespace {

Node* SkipTypeGuards(Node* node) {
  while (node->opcode() == IrOpcode::kTypeGuard) {
    node = NodeProperties::GetValueInput(node, 0);
  }
  return node;
}

}  // namespace

Node* EscapeAnalysisReducer::ObjectIdNode(const VirtualObject* vobject) {
  VirtualObject::Id id = vobject->id();
  if (id >= object_id_cache_.size()) object_id_cache_.resize(id + 1);
  if (!object_id_cache_[id]) {
    Node* node = jsgraph()->graph()->NewNode(jsgraph()->common()->ObjectId(id));
    NodeProperties::SetType(node, Type::Object());
    object_id_cache_[id] = node;
  }
  return object_id_cache_[id];
}

Reduction EscapeAnalysisReducer::Reduce(Node* node) {
  if (Node* replacement = analysis_result().GetReplacementOf(node)) {
    DCHECK(node->opcode() != IrOpcode::kAllocate &&
           node->opcode() != IrOpcode::kFinishRegion);
    DCHECK_NE(replacement, node);
    return ReplaceNode(node, replacement);
  }

  switch (node->opcode()) {
    case IrOpcode::kAllocate:
    case IrOpcode::kTypeGuard: {
      const VirtualObject* vobject = analysis_result().GetVirtualObject(node);
      if (vobject && !vobject->HasEscaped()) {
        RelaxEffectsAndControls(node);
      }
      return NoChange();
    }
    case IrOpcode::kFinishRegion: {
      Node* effect = NodeProperties::GetEffectInput(node, 0);
      if (effect->opcode() == IrOpcode::kBeginRegion) {
        RelaxEffectsAndControls(effect);
        RelaxEffectsAndControls(node);
      }
      return NoChange();
    }
    case IrOpcode::kNewArgumentsElements:
      arguments_elements_.insert(node);
      return NoChange();
    default: {
      // TODO(sigurds): Change this to GetFrameStateInputCount once
      // it is working. For now we use EffectInputCount > 0 to determine
      // whether a node might have a frame state input.
      if (node->op()->EffectInputCount() > 0) {
        ReduceFrameStateInputs(node);
      }
      return NoChange();
    }
  }
}

// While doing DFS on the FrameState tree, we have to recognize duplicate
// occurrences of virtual objects.
class Deduplicator {
 public:
  explicit Deduplicator(Zone* zone) : is_duplicate_(zone) {}
  bool SeenBefore(const VirtualObject* vobject) {
    VirtualObject::Id id = vobject->id();
    if (id >= is_duplicate_.size()) {
      is_duplicate_.resize(id + 1);
    }
    bool is_duplicate = is_duplicate_[id];
    is_duplicate_[id] = true;
    return is_duplicate;
  }

 private:
  ZoneVector<bool> is_duplicate_;
};

void EscapeAnalysisReducer::ReduceFrameStateInputs(Node* node) {
  DCHECK_GE(node->op()->EffectInputCount(), 1);
  for (int i = 0; i < node->InputCount(); ++i) {
    Node* input = node->InputAt(i);
    if (input->opcode() == IrOpcode::kFrameState) {
      Deduplicator deduplicator(zone());
      if (Node* ret = ReduceDeoptState(input, node, &deduplicator)) {
        node->ReplaceInput(i, ret);
      }
    }
  }
}

Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
                                              Deduplicator* deduplicator) {
  if (node->opcode() == IrOpcode::kFrameState) {
    NodeHashCache::Constructor new_node(&node_cache_, node);
    // This input order is important to match the DFS traversal used in the
    // instruction selector. Otherwise, the instruction selector might find a
    // duplicate node before the original one.
    for (int input_id : {kFrameStateOuterStateInput, kFrameStateFunctionInput,
                         kFrameStateParametersInput, kFrameStateContextInput,
                         kFrameStateLocalsInput, kFrameStateStackInput}) {
      Node* input = node->InputAt(input_id);
      new_node.ReplaceInput(ReduceDeoptState(input, effect, deduplicator),
                            input_id);
    }
    return new_node.Get();
  } else if (node->opcode() == IrOpcode::kStateValues) {
    NodeHashCache::Constructor new_node(&node_cache_, node);
    for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
      Node* input = NodeProperties::GetValueInput(node, i);
      new_node.ReplaceValueInput(ReduceDeoptState(input, effect, deduplicator),
                                 i);
    }
    return new_node.Get();
  } else if (const VirtualObject* vobject =
                 analysis_result().GetVirtualObject(SkipTypeGuards(node))) {
    if (vobject->HasEscaped()) return node;
    if (deduplicator->SeenBefore(vobject)) {
      return ObjectIdNode(vobject);
    } else {
      std::vector<Node*> inputs;
      for (int offset = 0; offset < vobject->size(); offset += kTaggedSize) {
        Node* field =
            analysis_result().GetVirtualObjectField(vobject, offset, effect);
        CHECK_NOT_NULL(field);
        if (field != jsgraph()->Dead()) {
          inputs.push_back(ReduceDeoptState(field, effect, deduplicator));
        }
      }
      int num_inputs = static_cast<int>(inputs.size());
      NodeHashCache::Constructor new_node(
          &node_cache_,
          jsgraph()->common()->ObjectState(vobject->id(), num_inputs),
          num_inputs, &inputs.front(), NodeProperties::GetType(node));
      return new_node.Get();
    }
  } else {
    return node;
  }
}

void EscapeAnalysisReducer::VerifyReplacement() const {
  AllNodes all(zone(), jsgraph()->graph());
  for (Node* node : all.reachable) {
    if (node->opcode() == IrOpcode::kAllocate) {
      if (const VirtualObject* vobject =
              analysis_result().GetVirtualObject(node)) {
        if (!vobject->HasEscaped()) {
          FATAL("Escape analysis failed to remove node %s#%d\n",
                node->op()->mnemonic(), node->id());
        }
      }
    }
  }
}

void EscapeAnalysisReducer::Finalize() {
  for (Node* node : arguments_elements_) {
    int mapped_count = NewArgumentsElementsMappedCountOf(node->op());

    Node* arguments_frame = NodeProperties::GetValueInput(node, 0);
    if (arguments_frame->opcode() != IrOpcode::kArgumentsFrame) continue;
    Node* arguments_length = NodeProperties::GetValueInput(node, 1);
    if (arguments_length->opcode() != IrOpcode::kArgumentsLength) continue;

    // If mapped arguments are specified, then their number is always equal to
    // the number of formal parameters. This allows to use just the three-value
    // {ArgumentsStateType} enum because the deoptimizer can reconstruct the
    // value of {mapped_count} from the number of formal parameters.
    DCHECK_IMPLIES(
        mapped_count != 0,
        mapped_count == FormalParameterCountOf(arguments_length->op()));
    ArgumentsStateType type = IsRestLengthOf(arguments_length->op())
                                  ? ArgumentsStateType::kRestParameter
                                  : (mapped_count == 0)
                                        ? ArgumentsStateType::kUnmappedArguments
                                        : ArgumentsStateType::kMappedArguments;

    Node* arguments_length_state = nullptr;
    for (Edge edge : arguments_length->use_edges()) {
      Node* use = edge.from();
      switch (use->opcode()) {
        case IrOpcode::kObjectState:
        case IrOpcode::kTypedObjectState:
        case IrOpcode::kStateValues:
        case IrOpcode::kTypedStateValues:
          if (!arguments_length_state) {
            arguments_length_state = jsgraph()->graph()->NewNode(
                jsgraph()->common()->ArgumentsLengthState(type));
            NodeProperties::SetType(arguments_length_state,
                                    Type::OtherInternal());
          }
          edge.UpdateTo(arguments_length_state);
          break;
        default:
          break;
      }
    }

    bool escaping_use = false;
    ZoneVector<Node*> loads(zone());
    for (Edge edge : node->use_edges()) {
      Node* use = edge.from();
      if (!NodeProperties::IsValueEdge(edge)) continue;
      if (use->use_edges().empty()) {
        // A node without uses is dead, so we don't have to care about it.
        continue;
      }
      switch (use->opcode()) {
        case IrOpcode::kStateValues:
        case IrOpcode::kTypedStateValues:
        case IrOpcode::kObjectState:
        case IrOpcode::kTypedObjectState:
          break;
        case IrOpcode::kLoadElement:
          if (mapped_count == 0) {
            loads.push_back(use);
          } else {
            escaping_use = true;
          }
          break;
        case IrOpcode::kLoadField:
          if (FieldAccessOf(use->op()).offset == FixedArray::kLengthOffset) {
            loads.push_back(use);
          } else {
            escaping_use = true;
          }
          break;
        default:
          // If the arguments elements node node is used by an unhandled node,
          // then we cannot remove this allocation.
          escaping_use = true;
          break;
      }
      if (escaping_use) break;
    }
    if (!escaping_use) {
      Node* arguments_elements_state = jsgraph()->graph()->NewNode(
          jsgraph()->common()->ArgumentsElementsState(type));
      NodeProperties::SetType(arguments_elements_state, Type::OtherInternal());
      ReplaceWithValue(node, arguments_elements_state);

      for (Node* load : loads) {
        switch (load->opcode()) {
          case IrOpcode::kLoadElement: {
            Node* index = NodeProperties::GetValueInput(load, 1);
            // {offset} is a reverted index starting from 1. The base address is
            // adapted to allow offsets starting from 1.
            Node* offset = jsgraph()->graph()->NewNode(
                jsgraph()->simplified()->NumberSubtract(), arguments_length,
                index);
            NodeProperties::SetType(offset,
                                    TypeCache::Get()->kArgumentsLengthType);
            NodeProperties::ReplaceValueInput(load, arguments_frame, 0);
            NodeProperties::ReplaceValueInput(load, offset, 1);
            NodeProperties::ChangeOp(
                load, jsgraph()->simplified()->LoadStackArgument());
            break;
          }
          case IrOpcode::kLoadField: {
            DCHECK_EQ(FieldAccessOf(load->op()).offset,
                      FixedArray::kLengthOffset);
            Node* length = NodeProperties::GetValueInput(node, 1);
            ReplaceWithValue(load, length);
            break;
          }
          default:
            UNREACHABLE();
        }
      }
    }
  }
}

Node* NodeHashCache::Query(Node* node) {
  auto it = cache_.find(node);
  if (it != cache_.end()) {
    return *it;
  } else {
    return nullptr;
  }
}

NodeHashCache::Constructor::Constructor(NodeHashCache* cache,
                                        const Operator* op, int input_count,
                                        Node** inputs, Type type)
    : node_cache_(cache), from_(nullptr) {
  if (node_cache_->temp_nodes_.size() > 0) {
    tmp_ = node_cache_->temp_nodes_.back();
    node_cache_->temp_nodes_.pop_back();
    int tmp_input_count = tmp_->InputCount();
    if (input_count <= tmp_input_count) {
      tmp_->TrimInputCount(input_count);
    }
    for (int i = 0; i < input_count; ++i) {
      if (i < tmp_input_count) {
        tmp_->ReplaceInput(i, inputs[i]);
      } else {
        tmp_->AppendInput(node_cache_->graph_->zone(), inputs[i]);
      }
    }
    NodeProperties::ChangeOp(tmp_, op);
  } else {
    tmp_ = node_cache_->graph_->NewNode(op, input_count, inputs);
  }
  NodeProperties::SetType(tmp_, type);
}

Node* NodeHashCache::Constructor::Get() {
  DCHECK(tmp_ || from_);
  Node* node;
  if (!tmp_) {
    node = node_cache_->Query(from_);
    if (!node) node = from_;
  } else {
    node = node_cache_->Query(tmp_);
    if (node) {
      node_cache_->temp_nodes_.push_back(tmp_);
    } else {
      node = tmp_;
      node_cache_->Insert(node);
    }
  }
  tmp_ = from_ = nullptr;
  return node;
}

Node* NodeHashCache::Constructor::MutableNode() {
  DCHECK(tmp_ || from_);
  if (!tmp_) {
    if (node_cache_->temp_nodes_.empty()) {
      tmp_ = node_cache_->graph_->CloneNode(from_);
    } else {
      tmp_ = node_cache_->temp_nodes_.back();
      node_cache_->temp_nodes_.pop_back();
      int from_input_count = from_->InputCount();
      int tmp_input_count = tmp_->InputCount();
      if (from_input_count <= tmp_input_count) {
        tmp_->TrimInputCount(from_input_count);
      }
      for (int i = 0; i < from_input_count; ++i) {
        if (i < tmp_input_count) {
          tmp_->ReplaceInput(i, from_->InputAt(i));
        } else {
          tmp_->AppendInput(node_cache_->graph_->zone(), from_->InputAt(i));
        }
      }
      NodeProperties::SetType(tmp_, NodeProperties::GetType(from_));
      NodeProperties::ChangeOp(tmp_, from_->op());
    }
  }
  return tmp_;
}

#undef TRACE

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