// 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/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_(true) {}


Reduction EscapeAnalysisReducer::Reduce(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 (int i = 0; i < node->InputCount(); i++) {
        Node* input = node->InputAt(i);
        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::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 (Node* rep = escape_analysis()->GetReplacement(node)) {
    counters()->turbo_escape_loads_replaced()->Increment();
    TRACE("Replaced #%d (%s) with #%d (%s)\n", node->id(),
          node->op()->mnemonic(), rep->id(), rep->op()->mnemonic());
    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(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);
    counters()->turbo_escape_allocs_replaced()->Increment();
    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 = NodeProperties::GetValueInput(node, 0);
  Node* right = 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());
      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 = 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, 0);
    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, 0, 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 = 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 (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;
}


Counters* EscapeAnalysisReducer::counters() const {
  return jsgraph_->isolate()->counters();
}


class EscapeAnalysisVerifier final : public AdvancedReducer {
 public:
  EscapeAnalysisVerifier(Editor* editor, EscapeAnalysis* escape_analysis)
      : AdvancedReducer(editor), escape_analysis_(escape_analysis) {}

  Reduction Reduce(Node* node) final {
    switch (node->opcode()) {
      case IrOpcode::kAllocate:
        CHECK(!escape_analysis_->IsVirtual(node));
        break;
      default:
        break;
    }
    return NoChange();
  }

 private:
  EscapeAnalysis* escape_analysis_;
};

void EscapeAnalysisReducer::VerifyReplacement() const {
#ifdef DEBUG
  GraphReducer graph_reducer(zone(), jsgraph()->graph());
  EscapeAnalysisVerifier verifier(&graph_reducer, escape_analysis());
  graph_reducer.AddReducer(&verifier);
  graph_reducer.ReduceGraph();
#endif  // DEBUG
}

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