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

#include "src/compiler/all-nodes.h"
#include "src/compiler/js-graph.h"
#include "src/counters.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,
                                             EscapeAnalysis* escape_analysis,
                                             Zone* zone)
    : AdvancedReducer(editor),
      jsgraph_(jsgraph),
      escape_analysis_(escape_analysis),
      zone_(zone),
      fully_reduced_(static_cast<int>(jsgraph->graph()->NodeCount() * 2), zone),
      exists_virtual_allocate_(escape_analysis->ExistsVirtualAllocate()) {}

Reduction EscapeAnalysisReducer::ReduceNode(Node* node) {
  if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
      fully_reduced_.Contains(node->id())) {
    return NoChange();
  }

  switch (node->opcode()) {
    case IrOpcode::kLoadField:
    case IrOpcode::kLoadElement:
      return ReduceLoad(node);
    case IrOpcode::kStoreField:
    case IrOpcode::kStoreElement:
      return ReduceStore(node);
    case IrOpcode::kAllocate:
      return ReduceAllocate(node);
    case IrOpcode::kFinishRegion:
      return ReduceFinishRegion(node);
    case IrOpcode::kReferenceEqual:
      return ReduceReferenceEqual(node);
    case IrOpcode::kObjectIsSmi:
      return ReduceObjectIsSmi(node);
    // FrameStates and Value nodes are preprocessed here,
    // and visited via ReduceFrameStateUses from their user nodes.
    case IrOpcode::kFrameState:
    case IrOpcode::kStateValues: {
      if (node->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
          fully_reduced_.Contains(node->id())) {
        break;
      }
      bool depends_on_object_state = false;
      for (Node* input : node->inputs()) {
        switch (input->opcode()) {
          case IrOpcode::kAllocate:
          case IrOpcode::kFinishRegion:
            depends_on_object_state =
                depends_on_object_state || escape_analysis()->IsVirtual(input);
            break;
          case IrOpcode::kFrameState:
          case IrOpcode::kStateValues:
            depends_on_object_state =
                depends_on_object_state ||
                input->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
                !fully_reduced_.Contains(input->id());
            break;
          default:
            break;
        }
      }
      if (!depends_on_object_state) {
        fully_reduced_.Add(node->id());
      }
      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 (exists_virtual_allocate_ && node->op()->EffectInputCount() > 0) {
        return ReduceFrameStateUses(node);
      }
      break;
  }
  return NoChange();
}

Reduction EscapeAnalysisReducer::Reduce(Node* node) {
  Reduction reduction = ReduceNode(node);
  if (reduction.Changed() && node != reduction.replacement()) {
    escape_analysis()->SetReplacement(node, reduction.replacement());
  }
  return reduction;
}

namespace {

Node* MaybeGuard(JSGraph* jsgraph, Zone* zone, Node* original,
                 Node* replacement) {
  // We might need to guard the replacement if the type of the {replacement}
  // node is not in a sub-type relation to the type of the the {original} node.
  Type* const replacement_type = NodeProperties::GetType(replacement);
  Type* const original_type = NodeProperties::GetType(original);
  if (!replacement_type->Is(original_type)) {
    Node* const control = NodeProperties::GetControlInput(original);
    replacement = jsgraph->graph()->NewNode(
        jsgraph->common()->TypeGuard(original_type), replacement, control);
    NodeProperties::SetType(replacement, original_type);
  }
  return replacement;
}

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

}  // namespace

Reduction EscapeAnalysisReducer::ReduceLoad(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kLoadField ||
         node->opcode() == IrOpcode::kLoadElement);
  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    fully_reduced_.Add(node->id());
  }
  if (escape_analysis()->IsVirtual(
          SkipTypeGuards(NodeProperties::GetValueInput(node, 0)))) {
    if (Node* rep = escape_analysis()->GetReplacement(node)) {
      TRACE("Replaced #%d (%s) with #%d (%s)\n", node->id(),
            node->op()->mnemonic(), rep->id(), rep->op()->mnemonic());
      rep = MaybeGuard(jsgraph(), zone(), node, rep);
      ReplaceWithValue(node, rep);
      return Replace(rep);
    }
  }
  return NoChange();
}


Reduction EscapeAnalysisReducer::ReduceStore(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kStoreField ||
         node->opcode() == IrOpcode::kStoreElement);
  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    fully_reduced_.Add(node->id());
  }
  if (escape_analysis()->IsVirtual(
          SkipTypeGuards(NodeProperties::GetValueInput(node, 0)))) {
    TRACE("Removed #%d (%s) from effect chain\n", node->id(),
          node->op()->mnemonic());
    RelaxEffectsAndControls(node);
    return Changed(node);
  }
  return NoChange();
}


Reduction EscapeAnalysisReducer::ReduceAllocate(Node* node) {
  DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    fully_reduced_.Add(node->id());
  }
  if (escape_analysis()->IsVirtual(node)) {
    RelaxEffectsAndControls(node);
    TRACE("Removed allocate #%d from effect chain\n", node->id());
    return Changed(node);
  }
  return NoChange();
}


Reduction EscapeAnalysisReducer::ReduceFinishRegion(Node* node) {
  DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
  Node* effect = NodeProperties::GetEffectInput(node, 0);
  if (effect->opcode() == IrOpcode::kBeginRegion) {
    // We only add it now to remove empty Begin/Finish region pairs
    // in the process.
    if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
      fully_reduced_.Add(node->id());
    }
    RelaxEffectsAndControls(effect);
    RelaxEffectsAndControls(node);
#ifdef DEBUG
    if (FLAG_trace_turbo_escape) {
      PrintF("Removed region #%d / #%d from effect chain,", effect->id(),
             node->id());
      PrintF(" %d user(s) of #%d remain(s):", node->UseCount(), node->id());
      for (Edge edge : node->use_edges()) {
        PrintF(" #%d", edge.from()->id());
      }
      PrintF("\n");
    }
#endif  // DEBUG
    return Changed(node);
  }
  return NoChange();
}


Reduction EscapeAnalysisReducer::ReduceReferenceEqual(Node* node) {
  DCHECK_EQ(node->opcode(), IrOpcode::kReferenceEqual);
  Node* left = SkipTypeGuards(NodeProperties::GetValueInput(node, 0));
  Node* right = SkipTypeGuards(NodeProperties::GetValueInput(node, 1));
  if (escape_analysis()->IsVirtual(left)) {
    if (escape_analysis()->IsVirtual(right) &&
        escape_analysis()->CompareVirtualObjects(left, right)) {
      ReplaceWithValue(node, jsgraph()->TrueConstant());
      TRACE("Replaced ref eq #%d with true\n", node->id());
      return Replace(jsgraph()->TrueConstant());
    }
    // Right-hand side is not a virtual object, or a different one.
    ReplaceWithValue(node, jsgraph()->FalseConstant());
    TRACE("Replaced ref eq #%d with false\n", node->id());
    return Replace(jsgraph()->FalseConstant());
  } else if (escape_analysis()->IsVirtual(right)) {
    // Left-hand side is not a virtual object.
    ReplaceWithValue(node, jsgraph()->FalseConstant());
    TRACE("Replaced ref eq #%d with false\n", node->id());
    return Replace(jsgraph()->FalseConstant());
  }
  return NoChange();
}


Reduction EscapeAnalysisReducer::ReduceObjectIsSmi(Node* node) {
  DCHECK_EQ(node->opcode(), IrOpcode::kObjectIsSmi);
  Node* input = SkipTypeGuards(NodeProperties::GetValueInput(node, 0));
  if (escape_analysis()->IsVirtual(input)) {
    ReplaceWithValue(node, jsgraph()->FalseConstant());
    TRACE("Replaced ObjectIsSmi #%d with false\n", node->id());
    return Replace(jsgraph()->FalseConstant());
  }
  return NoChange();
}


Reduction EscapeAnalysisReducer::ReduceFrameStateUses(Node* node) {
  DCHECK_GE(node->op()->EffectInputCount(), 1);
  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    fully_reduced_.Add(node->id());
  }
  bool changed = false;
  for (int i = 0; i < node->InputCount(); ++i) {
    Node* input = node->InputAt(i);
    if (input->opcode() == IrOpcode::kFrameState) {
      if (Node* ret = ReduceDeoptState(input, node, false)) {
        node->ReplaceInput(i, ret);
        changed = true;
      }
    }
  }
  if (changed) {
    return Changed(node);
  }
  return NoChange();
}


// Returns the clone if it duplicated the node, and null otherwise.
Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
                                              bool multiple_users) {
  DCHECK(node->opcode() == IrOpcode::kFrameState ||
         node->opcode() == IrOpcode::kStateValues);
  if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
      fully_reduced_.Contains(node->id())) {
    return nullptr;
  }
  TRACE("Reducing %s %d\n", node->op()->mnemonic(), node->id());
  Node* clone = nullptr;
  bool node_multiused = node->UseCount() > 1;
  bool multiple_users_rec = multiple_users || node_multiused;
  for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
    Node* input = NodeProperties::GetValueInput(node, i);
    if (input->opcode() == IrOpcode::kStateValues) {
      if (Node* ret = ReduceDeoptState(input, effect, multiple_users_rec)) {
        if (node_multiused || (multiple_users && !clone)) {
          TRACE("  Cloning #%d", node->id());
          node = clone = jsgraph()->graph()->CloneNode(node);
          TRACE(" to #%d\n", node->id());
          node_multiused = false;
        }
        NodeProperties::ReplaceValueInput(node, ret, i);
      }
    } else {
      if (Node* ret = ReduceStateValueInput(node, i, effect, node_multiused,
                                            clone, multiple_users)) {
        DCHECK_NULL(clone);
        node_multiused = false;  // Don't clone anymore.
        node = clone = ret;
      }
    }
  }
  if (node->opcode() == IrOpcode::kFrameState) {
    Node* outer_frame_state = NodeProperties::GetFrameStateInput(node);
    if (outer_frame_state->opcode() == IrOpcode::kFrameState) {
      if (Node* ret =
              ReduceDeoptState(outer_frame_state, effect, multiple_users_rec)) {
        if (node_multiused || (multiple_users && !clone)) {
          TRACE("    Cloning #%d", node->id());
          node = clone = jsgraph()->graph()->CloneNode(node);
          TRACE(" to #%d\n", node->id());
        }
        NodeProperties::ReplaceFrameStateInput(node, ret);
      }
    }
  }
  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    fully_reduced_.Add(node->id());
  }
  return clone;
}


// Returns the clone if it duplicated the node, and null otherwise.
Node* EscapeAnalysisReducer::ReduceStateValueInput(Node* node, int node_index,
                                                   Node* effect,
                                                   bool node_multiused,
                                                   bool already_cloned,
                                                   bool multiple_users) {
  Node* input = SkipTypeGuards(NodeProperties::GetValueInput(node, node_index));
  if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
      fully_reduced_.Contains(node->id())) {
    return nullptr;
  }
  TRACE("Reducing State Input #%d (%s)\n", input->id(),
        input->op()->mnemonic());
  Node* clone = nullptr;
  if (input->opcode() == IrOpcode::kFinishRegion ||
      input->opcode() == IrOpcode::kAllocate) {
    if (escape_analysis()->IsVirtual(input)) {
      if (escape_analysis()->IsCyclicObjectState(effect, input)) {
        // TODO(mstarzinger): Represent cyclic object states differently to
        // ensure the scheduler can properly handle such object states.
        compilation_failed_ = true;
        return nullptr;
      }
      if (Node* object_state =
              escape_analysis()->GetOrCreateObjectState(effect, input)) {
        if (node_multiused || (multiple_users && !already_cloned)) {
          TRACE("Cloning #%d", node->id());
          node = clone = jsgraph()->graph()->CloneNode(node);
          TRACE(" to #%d\n", node->id());
          node_multiused = false;
          already_cloned = true;
        }
        NodeProperties::ReplaceValueInput(node, object_state, node_index);
        TRACE("Replaced state #%d input #%d with object state #%d\n",
              node->id(), input->id(), object_state->id());
      } else {
        TRACE("No object state replacement for #%d at effect #%d available.\n",
              input->id(), effect->id());
        UNREACHABLE();
      }
    }
  }
  return clone;
}


void EscapeAnalysisReducer::VerifyReplacement() const {
#ifdef DEBUG
  AllNodes all(zone(), jsgraph()->graph());
  for (Node* node : all.reachable) {
    if (node->opcode() == IrOpcode::kAllocate) {
      CHECK(!escape_analysis_->IsVirtual(node));
    }
  }
#endif  // DEBUG
}

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