// Copyright 2016 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/redundancy-elimination.h"

#include "src/compiler/node-properties.h"

namespace v8 {
namespace internal {
namespace compiler {

RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
    : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}

RedundancyElimination::~RedundancyElimination() {}

Reduction RedundancyElimination::Reduce(Node* node) {
  if (node_checks_.Get(node)) return NoChange();
  switch (node->opcode()) {
    case IrOpcode::kCheckBounds:
    case IrOpcode::kCheckFloat64Hole:
    case IrOpcode::kCheckHeapObject:
    case IrOpcode::kCheckIf:
    case IrOpcode::kCheckInternalizedString:
    case IrOpcode::kCheckNumber:
    case IrOpcode::kCheckReceiver:
    case IrOpcode::kCheckSmi:
    case IrOpcode::kCheckString:
    case IrOpcode::kCheckSeqString:
    case IrOpcode::kCheckTaggedHole:
    case IrOpcode::kCheckedFloat64ToInt32:
    case IrOpcode::kCheckedInt32Add:
    case IrOpcode::kCheckedInt32Sub:
    case IrOpcode::kCheckedInt32Div:
    case IrOpcode::kCheckedInt32Mod:
    case IrOpcode::kCheckedInt32Mul:
    case IrOpcode::kCheckedTaggedToFloat64:
    case IrOpcode::kCheckedTaggedSignedToInt32:
    case IrOpcode::kCheckedTaggedToInt32:
    case IrOpcode::kCheckedUint32ToInt32:
      return ReduceCheckNode(node);
    case IrOpcode::kSpeculativeNumberAdd:
    case IrOpcode::kSpeculativeNumberSubtract:
      // For increments and decrements by a constant, try to learn from the last
      // bounds check.
      return TryReuseBoundsCheckForFirstInput(node);
    case IrOpcode::kEffectPhi:
      return ReduceEffectPhi(node);
    case IrOpcode::kDead:
      break;
    case IrOpcode::kStart:
      return ReduceStart(node);
    default:
      return ReduceOtherNode(node);
  }
  return NoChange();
}

// static
RedundancyElimination::EffectPathChecks*
RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
                                              EffectPathChecks const* checks) {
  return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
}

// static
RedundancyElimination::EffectPathChecks const*
RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
  return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
}

bool RedundancyElimination::EffectPathChecks::Equals(
    EffectPathChecks const* that) const {
  if (this->size_ != that->size_) return false;
  Check* this_head = this->head_;
  Check* that_head = that->head_;
  while (this_head != that_head) {
    if (this_head->node != that_head->node) return false;
    this_head = this_head->next;
    that_head = that_head->next;
  }
  return true;
}

void RedundancyElimination::EffectPathChecks::Merge(
    EffectPathChecks const* that) {
  // Change the current check list to a longest common tail of this check
  // list and the other list.

  // First, we throw away the prefix of the longer list, so that
  // we have lists of the same length.
  Check* that_head = that->head_;
  size_t that_size = that->size_;
  while (that_size > size_) {
    that_head = that_head->next;
    that_size--;
  }
  while (size_ > that_size) {
    head_ = head_->next;
    size_--;
  }

  // Then we go through both lists in lock-step until we find
  // the common tail.
  while (head_ != that_head) {
    DCHECK_LT(0u, size_);
    DCHECK_NOT_NULL(head_);
    size_--;
    head_ = head_->next;
    that_head = that_head->next;
  }
}

RedundancyElimination::EffectPathChecks const*
RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
                                                  Node* node) const {
  Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
  return new (zone->New(sizeof(EffectPathChecks)))
      EffectPathChecks(head, size_ + 1);
}

namespace {

bool IsCompatibleCheck(Node const* a, Node const* b) {
  if (a->op() != b->op()) {
    if (a->opcode() == IrOpcode::kCheckInternalizedString &&
        b->opcode() == IrOpcode::kCheckString) {
      // CheckInternalizedString(node) implies CheckString(node)
    } else {
      return false;
    }
  }
  for (int i = a->op()->ValueInputCount(); --i >= 0;) {
    if (a->InputAt(i) != b->InputAt(i)) return false;
  }
  return true;
}

}  // namespace

Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
  for (Check const* check = head_; check != nullptr; check = check->next) {
    if (IsCompatibleCheck(check->node, node)) {
      DCHECK(!check->node->IsDead());
      return check->node;
    }
  }
  return nullptr;
}

Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
    Node* node) const {
  for (Check const* check = head_; check != nullptr; check = check->next) {
    if (check->node->opcode() == IrOpcode::kCheckBounds &&
        check->node->InputAt(0) == node) {
      return check->node;
    }
  }
  return nullptr;
}

RedundancyElimination::EffectPathChecks const*
RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
  size_t const id = node->id();
  if (id < info_for_node_.size()) return info_for_node_[id];
  return nullptr;
}

void RedundancyElimination::PathChecksForEffectNodes::Set(
    Node* node, EffectPathChecks const* checks) {
  size_t const id = node->id();
  if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
  info_for_node_[id] = checks;
}

Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
  Node* const effect = NodeProperties::GetEffectInput(node);
  EffectPathChecks const* checks = node_checks_.Get(effect);
  // If we do not know anything about the predecessor, do not propagate just yet
  // because we will have to recompute anyway once we compute the predecessor.
  if (checks == nullptr) return NoChange();
  // See if we have another check that dominates us.
  if (Node* check = checks->LookupCheck(node)) {
    ReplaceWithValue(node, check);
    return Replace(check);
  }

  // Learn from this check.
  return UpdateChecks(node, checks->AddCheck(zone(), node));
}

Reduction RedundancyElimination::TryReuseBoundsCheckForFirstInput(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
         node->opcode() == IrOpcode::kSpeculativeNumberSubtract);

  DCHECK_EQ(1, node->op()->EffectInputCount());
  DCHECK_EQ(1, node->op()->EffectOutputCount());

  Node* const effect = NodeProperties::GetEffectInput(node);
  EffectPathChecks const* checks = node_checks_.Get(effect);

  // If we do not know anything about the predecessor, do not propagate just yet
  // because we will have to recompute anyway once we compute the predecessor.
  if (checks == nullptr) return NoChange();

  Node* left = node->InputAt(0);
  Node* right = node->InputAt(1);
  // Only use bounds checks for increments/decrements by a constant.
  if (right->opcode() == IrOpcode::kNumberConstant) {
    if (Node* bounds_check = checks->LookupBoundsCheckFor(left)) {
      // Only use the bounds checked type if it is better.
      if (NodeProperties::GetType(bounds_check)
              ->Is(NodeProperties::GetType(left))) {
        node->ReplaceInput(0, bounds_check);
      }
    }
  }

  return UpdateChecks(node, checks);
}

Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
  Node* const control = NodeProperties::GetControlInput(node);
  if (control->opcode() == IrOpcode::kLoop) {
    // Here we rely on having only reducible loops:
    // The loop entry edge always dominates the header, so we can just use
    // the information from the loop entry edge.
    return TakeChecksFromFirstEffect(node);
  }
  DCHECK_EQ(IrOpcode::kMerge, control->opcode());

  // Shortcut for the case when we do not know anything about some input.
  int const input_count = node->op()->EffectInputCount();
  for (int i = 0; i < input_count; ++i) {
    Node* const effect = NodeProperties::GetEffectInput(node, i);
    if (node_checks_.Get(effect) == nullptr) return NoChange();
  }

  // Make a copy of the first input's checks and merge with the checks
  // from other inputs.
  EffectPathChecks* checks = EffectPathChecks::Copy(
      zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
  for (int i = 1; i < input_count; ++i) {
    Node* const input = NodeProperties::GetEffectInput(node, i);
    checks->Merge(node_checks_.Get(input));
  }
  return UpdateChecks(node, checks);
}

Reduction RedundancyElimination::ReduceStart(Node* node) {
  return UpdateChecks(node, EffectPathChecks::Empty(zone()));
}

Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
  if (node->op()->EffectInputCount() == 1) {
    if (node->op()->EffectOutputCount() == 1) {
      return TakeChecksFromFirstEffect(node);
    } else {
      // Effect terminators should be handled specially.
      return NoChange();
    }
  }
  DCHECK_EQ(0, node->op()->EffectInputCount());
  DCHECK_EQ(0, node->op()->EffectOutputCount());
  return NoChange();
}

Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
  DCHECK_EQ(1, node->op()->EffectOutputCount());
  Node* const effect = NodeProperties::GetEffectInput(node);
  EffectPathChecks const* checks = node_checks_.Get(effect);
  // If we do not know anything about the predecessor, do not propagate just yet
  // because we will have to recompute anyway once we compute the predecessor.
  if (checks == nullptr) return NoChange();
  // We just propagate the information from the effect input (ideally,
  // we would only revisit effect uses if there is change).
  return UpdateChecks(node, checks);
}

Reduction RedundancyElimination::UpdateChecks(Node* node,
                                              EffectPathChecks const* checks) {
  EffectPathChecks const* original = node_checks_.Get(node);
  // Only signal that the {node} has Changed, if the information about {checks}
  // has changed wrt. the {original}.
  if (checks != original) {
    if (original == nullptr || !checks->Equals(original)) {
      node_checks_.Set(node, checks);
      return Changed(node);
    }
  }
  return NoChange();
}

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