// 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/dead-code-elimination.h"

#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
#include "src/compiler/js-operator.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/operator-properties.h"

namespace v8 {
namespace internal {
namespace compiler {

DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
                                         CommonOperatorBuilder* common,
                                         Zone* temp_zone)
    : AdvancedReducer(editor),
      graph_(graph),
      common_(common),
      dead_(graph->NewNode(common->Dead())),
      zone_(temp_zone) {
  NodeProperties::SetType(dead_, Type::None());
}

namespace {

// True if we can guarantee that {node} will never actually produce a value or
// effect.
bool NoReturn(Node* node) {
  return node->opcode() == IrOpcode::kDead ||
         node->opcode() == IrOpcode::kUnreachable ||
         node->opcode() == IrOpcode::kDeadValue ||
         NodeProperties::GetTypeOrAny(node).IsNone();
}

Node* FindDeadInput(Node* node) {
  for (Node* input : node->inputs()) {
    if (NoReturn(input)) return input;
  }
  return nullptr;
}

}  // namespace

Reduction DeadCodeElimination::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;
  switch (node->opcode()) {
    case IrOpcode::kEnd:
      return ReduceEnd(node);
    case IrOpcode::kLoop:
    case IrOpcode::kMerge:
      return ReduceLoopOrMerge(node);
    case IrOpcode::kLoopExit:
      return ReduceLoopExit(node);
    case IrOpcode::kUnreachable:
    case IrOpcode::kIfException:
      return ReduceUnreachableOrIfException(node);
    case IrOpcode::kPhi:
      return ReducePhi(node);
    case IrOpcode::kEffectPhi:
      return PropagateDeadControl(node);
    case IrOpcode::kDeoptimize:
    case IrOpcode::kReturn:
    case IrOpcode::kTerminate:
      return ReduceDeoptimizeOrReturnOrTerminate(node);
    case IrOpcode::kThrow:
      return PropagateDeadControl(node);
    case IrOpcode::kBranch:
    case IrOpcode::kSwitch:
      return ReduceBranchOrSwitch(node);
    default:
      return ReduceNode(node);
  }
  UNREACHABLE();
}

Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
  DCHECK_EQ(1, node->op()->ControlInputCount());
  Node* control = NodeProperties::GetControlInput(node);
  if (control->opcode() == IrOpcode::kDead) return Replace(control);
  return NoChange();
}

Reduction DeadCodeElimination::ReduceEnd(Node* node) {
  DCHECK_EQ(IrOpcode::kEnd, node->opcode());
  Node::Inputs inputs = node->inputs();
  DCHECK_LE(1, inputs.count());
  int live_input_count = 0;
  for (int i = 0; i < inputs.count(); ++i) {
    Node* const input = inputs[i];
    // Skip dead inputs.
    if (input->opcode() == IrOpcode::kDead) continue;
    // Compact live inputs.
    if (i != live_input_count) node->ReplaceInput(live_input_count, input);
    ++live_input_count;
  }
  if (live_input_count == 0) {
    return Replace(dead());
  } else if (live_input_count < inputs.count()) {
    node->TrimInputCount(live_input_count);
    NodeProperties::ChangeOp(node, common()->End(live_input_count));
    return Changed(node);
  }
  DCHECK_EQ(inputs.count(), live_input_count);
  return NoChange();
}


Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
  DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
  Node::Inputs inputs = node->inputs();
  DCHECK_LE(1, inputs.count());
  // Count the number of live inputs to {node} and compact them on the fly, also
  // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
  // same time.  We consider {Loop}s dead even if only the first control input
  // is dead.
  int live_input_count = 0;
  if (node->opcode() != IrOpcode::kLoop ||
      node->InputAt(0)->opcode() != IrOpcode::kDead) {
    for (int i = 0; i < inputs.count(); ++i) {
      Node* const input = inputs[i];
      // Skip dead inputs.
      if (input->opcode() == IrOpcode::kDead) continue;
      // Compact live inputs.
      if (live_input_count != i) {
        node->ReplaceInput(live_input_count, input);
        for (Node* const use : node->uses()) {
          if (NodeProperties::IsPhi(use)) {
            DCHECK_EQ(inputs.count() + 1, use->InputCount());
            use->ReplaceInput(live_input_count, use->InputAt(i));
          }
        }
      }
      ++live_input_count;
    }
  }
  if (live_input_count == 0) {
    return Replace(dead());
  } else if (live_input_count == 1) {
    NodeVector loop_exits(zone_);
    // Due to compaction above, the live input is at offset 0.
    for (Node* const use : node->uses()) {
      if (NodeProperties::IsPhi(use)) {
        Replace(use, use->InputAt(0));
      } else if (use->opcode() == IrOpcode::kLoopExit &&
                 use->InputAt(1) == node) {
        // Remember the loop exits so that we can mark their loop input dead.
        // This has to be done after the use list iteration so that we do
        // not mutate the use list while it is being iterated.
        loop_exits.push_back(use);
      } else if (use->opcode() == IrOpcode::kTerminate) {
        DCHECK_EQ(IrOpcode::kLoop, node->opcode());
        Replace(use, dead());
      }
    }
    for (Node* loop_exit : loop_exits) {
      loop_exit->ReplaceInput(1, dead());
      Revisit(loop_exit);
    }
    return Replace(node->InputAt(0));
  }
  DCHECK_LE(2, live_input_count);
  DCHECK_LE(live_input_count, inputs.count());
  // Trim input count for the {Merge} or {Loop} node.
  if (live_input_count < inputs.count()) {
    // Trim input counts for all phi uses and revisit them.
    for (Node* const use : node->uses()) {
      if (NodeProperties::IsPhi(use)) {
        use->ReplaceInput(live_input_count, node);
        TrimMergeOrPhi(use, live_input_count);
        Revisit(use);
      }
    }
    TrimMergeOrPhi(node, live_input_count);
    return Changed(node);
  }
  return NoChange();
}

Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
  DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
  for (Node* const use : node->uses()) {
    if (use->opcode() == IrOpcode::kLoopExitValue ||
        use->opcode() == IrOpcode::kLoopExitEffect) {
      Replace(use, use->InputAt(0));
    }
  }
  Node* control = NodeProperties::GetControlInput(node, 0);
  Replace(node, control);
  return Replace(control);
}

Reduction DeadCodeElimination::ReduceNode(Node* node) {
  DCHECK(!IrOpcode::IsGraphTerminator(node->opcode()));
  int const effect_input_count = node->op()->EffectInputCount();
  int const control_input_count = node->op()->ControlInputCount();
  DCHECK_LE(control_input_count, 1);
  if (control_input_count == 1) {
    Reduction reduction = PropagateDeadControl(node);
    if (reduction.Changed()) return reduction;
  }
  if (effect_input_count == 0 &&
      (control_input_count == 0 || node->op()->ControlOutputCount() == 0)) {
    return ReducePureNode(node);
  }
  if (effect_input_count > 0) {
    return ReduceEffectNode(node);
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReducePhi(Node* node) {
  DCHECK_EQ(IrOpcode::kPhi, node->opcode());
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
  MachineRepresentation rep = PhiRepresentationOf(node->op());
  if (rep == MachineRepresentation::kNone ||
      NodeProperties::GetTypeOrAny(node).IsNone()) {
    return Replace(DeadValue(node, rep));
  }
  int input_count = node->op()->ValueInputCount();
  for (int i = 0; i < input_count; ++i) {
    Node* input = NodeProperties::GetValueInput(node, i);
    if (input->opcode() == IrOpcode::kDeadValue &&
        DeadValueRepresentationOf(input->op()) != rep) {
      NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i);
    }
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReducePureNode(Node* node) {
  DCHECK_EQ(0, node->op()->EffectInputCount());
  if (node->opcode() == IrOpcode::kDeadValue) return NoChange();
  if (Node* input = FindDeadInput(node)) {
    return Replace(DeadValue(input));
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kUnreachable ||
         node->opcode() == IrOpcode::kIfException);
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
  Node* effect = NodeProperties::GetEffectInput(node, 0);
  if (effect->opcode() == IrOpcode::kDead) {
    return Replace(effect);
  }
  if (effect->opcode() == IrOpcode::kUnreachable) {
    return Replace(effect);
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
  DCHECK_EQ(1, node->op()->EffectInputCount());
  Node* effect = NodeProperties::GetEffectInput(node, 0);
  if (effect->opcode() == IrOpcode::kDead) {
    return Replace(effect);
  }
  if (Node* input = FindDeadInput(node)) {
    if (effect->opcode() == IrOpcode::kUnreachable) {
      RelaxEffectsAndControls(node);
      return Replace(DeadValue(input));
    }

    Node* control = node->op()->ControlInputCount() == 1
                        ? NodeProperties::GetControlInput(node, 0)
                        : graph()->start();
    Node* unreachable =
        graph()->NewNode(common()->Unreachable(), effect, control);
    NodeProperties::SetType(unreachable, Type::None());
    ReplaceWithValue(node, DeadValue(input), node, control);
    return Replace(unreachable);
  }

  return NoChange();
}

Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminate(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
         node->opcode() == IrOpcode::kReturn ||
         node->opcode() == IrOpcode::kTerminate);
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
  if (FindDeadInput(node) != nullptr) {
    Node* effect = NodeProperties::GetEffectInput(node, 0);
    Node* control = NodeProperties::GetControlInput(node, 0);
    if (effect->opcode() != IrOpcode::kUnreachable) {
      effect = graph()->NewNode(common()->Unreachable(), effect, control);
      NodeProperties::SetType(effect, Type::None());
    }
    node->TrimInputCount(2);
    node->ReplaceInput(0, effect);
    node->ReplaceInput(1, control);
    NodeProperties::ChangeOp(node, common()->Throw());
    return Changed(node);
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
  Node* control = NodeProperties::GetControlInput(node, 0);
  Node* loop = NodeProperties::GetControlInput(node, 1);
  if (control->opcode() == IrOpcode::kDead ||
      loop->opcode() == IrOpcode::kDead) {
    return RemoveLoopExit(node);
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kBranch ||
         node->opcode() == IrOpcode::kSwitch);
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
  Node* condition = NodeProperties::GetValueInput(node, 0);
  if (condition->opcode() == IrOpcode::kDeadValue) {
    // Branches or switches on {DeadValue} must originate from unreachable code
    // and cannot matter. Due to schedule freedom between the effect and the
    // control chain, they might still appear in reachable code. Remove them by
    // always choosing the first projection.
    size_t const projection_cnt = node->op()->ControlOutputCount();
    Node** projections = zone_->NewArray<Node*>(projection_cnt);
    NodeProperties::CollectControlProjections(node, projections,
                                              projection_cnt);
    Replace(projections[0], NodeProperties::GetControlInput(node));
    return Replace(dead());
  }
  return NoChange();
}

void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
  const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
  node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
  NodeProperties::ChangeOp(node, op);
}

Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) {
  if (node->opcode() == IrOpcode::kDeadValue) {
    if (rep == DeadValueRepresentationOf(node->op())) return node;
    node = NodeProperties::GetValueInput(node, 0);
  }
  Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node);
  NodeProperties::SetType(dead_value, Type::None());
  return dead_value;
}

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