graph-reducer.cc

// Copyright 2014 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 <functional>
#include <limits>

#include "src/compiler/graph.h"
#include "src/compiler/graph-reducer.h"
#include "src/compiler/node.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/verifier.h"

namespace v8 {
namespace internal {
namespace compiler {

enum class GraphReducer::State : uint8_t {
  kUnvisited,
  kRevisit,
  kOnStack,
  kVisited
};


void Reducer::Finalize() {}

GraphReducer::GraphReducer(Zone* zone, Graph* graph, Node* dead)
    : graph_(graph),
      dead_(dead),
      state_(graph, 4),
      reducers_(zone),
      revisit_(zone),
      stack_(zone) {
  if (dead != nullptr) {
    NodeProperties::SetType(dead_, Type::None());
  }
}

GraphReducer::~GraphReducer() {}


void GraphReducer::AddReducer(Reducer* reducer) {
  reducers_.push_back(reducer);
}


void GraphReducer::ReduceNode(Node* node) {
  DCHECK(stack_.empty());
  DCHECK(revisit_.empty());
  Push(node);
  for (;;) {
    if (!stack_.empty()) {
      // Process the node on the top of the stack, potentially pushing more or
      // popping the node off the stack.
      ReduceTop();
    } else if (!revisit_.empty()) {
      // If the stack becomes empty, revisit any nodes in the revisit queue.
      Node* const node = revisit_.front();
      revisit_.pop();
      if (state_.Get(node) == State::kRevisit) {
        // state can change while in queue.
        Push(node);
      }
    } else {
      // Run all finalizers.
      for (Reducer* const reducer : reducers_) reducer->Finalize();

      // Check if we have new nodes to revisit.
      if (revisit_.empty()) break;
    }
  }
  DCHECK(revisit_.empty());
  DCHECK(stack_.empty());
}


void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }


Reduction GraphReducer::Reduce(Node* const node) {
  auto skip = reducers_.end();
  for (auto i = reducers_.begin(); i != reducers_.end();) {
    if (i != skip) {
      Reduction reduction = (*i)->Reduce(node);
      if (!reduction.Changed()) {
        // No change from this reducer.
      } else if (reduction.replacement() == node) {
        // {replacement} == {node} represents an in-place reduction. Rerun
        // all the other reducers for this node, as now there may be more
        // opportunities for reduction.
        if (FLAG_trace_turbo_reduction) {
          OFStream os(stdout);
          os << "- In-place update of " << *node << " by reducer "
             << (*i)->reducer_name() << std::endl;
        }
        skip = i;
        i = reducers_.begin();
        continue;
      } else {
        // {node} was replaced by another node.
        if (FLAG_trace_turbo_reduction) {
          OFStream os(stdout);
          os << "- Replacement of " << *node << " with "
             << *(reduction.replacement()) << " by reducer "
             << (*i)->reducer_name() << std::endl;
        }
        return reduction;
      }
    }
    ++i;
  }
  if (skip == reducers_.end()) {
    // No change from any reducer.
    return Reducer::NoChange();
  }
  // At least one reducer did some in-place reduction.
  return Reducer::Changed(node);
}


void GraphReducer::ReduceTop() {
  NodeState& entry = stack_.top();
  Node* node = entry.node;
  DCHECK_EQ(State::kOnStack, state_.Get(node));

  if (node->IsDead()) return Pop();  // Node was killed while on stack.

  Node::Inputs node_inputs = node->inputs();

  // Recurse on an input if necessary.
  int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
  for (int i = start; i < node_inputs.count(); ++i) {
    Node* input = node_inputs[i];
    if (input != node && Recurse(input)) {
      entry.input_index = i + 1;
      return;
    }
  }
  for (int i = 0; i < start; ++i) {
    Node* input = node_inputs[i];
    if (input != node && Recurse(input)) {
      entry.input_index = i + 1;
      return;
    }
  }

  // Remember the max node id before reduction.
  NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);

  // All inputs should be visited or on stack. Apply reductions to node.
  Reduction reduction = Reduce(node);

  // If there was no reduction, pop {node} and continue.
  if (!reduction.Changed()) return Pop();

  // Check if the reduction is an in-place update of the {node}.
  Node* const replacement = reduction.replacement();
  if (replacement == node) {
    // In-place update of {node}, may need to recurse on an input.
    Node::Inputs node_inputs = node->inputs();
    for (int i = 0; i < node_inputs.count(); ++i) {
      Node* input = node_inputs[i];
      if (input != node && Recurse(input)) {
        entry.input_index = i + 1;
        return;
      }
    }
  }

  // After reducing the node, pop it off the stack.
  Pop();

  // Check if we have a new replacement.
  if (replacement != node) {
    Replace(node, replacement, max_id);
  } else {
    // Revisit all uses of the node.
    for (Node* const user : node->uses()) {
      // Don't revisit this node if it refers to itself.
      if (user != node) Revisit(user);
    }
  }
}


void GraphReducer::Replace(Node* node, Node* replacement) {
  Replace(node, replacement, std::numeric_limits<NodeId>::max());
}


void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
  if (node == graph()->start()) graph()->SetStart(replacement);
  if (node == graph()->end()) graph()->SetEnd(replacement);
  if (replacement->id() <= max_id) {
    // {replacement} is an old node, so unlink {node} and assume that
    // {replacement} was already reduced and finish.
    for (Edge edge : node->use_edges()) {
      Node* const user = edge.from();
      Verifier::VerifyEdgeInputReplacement(edge, replacement);
      edge.UpdateTo(replacement);
      // Don't revisit this node if it refers to itself.
      if (user != node) Revisit(user);
    }
    node->Kill();
  } else {
    // Replace all old uses of {node} with {replacement}, but allow new nodes
    // created by this reduction to use {node}.
    for (Edge edge : node->use_edges()) {
      Node* const user = edge.from();
      if (user->id() <= max_id) {
        edge.UpdateTo(replacement);
        // Don't revisit this node if it refers to itself.
        if (user != node) Revisit(user);
      }
    }
    // Unlink {node} if it's no longer used.
    if (node->uses().empty()) node->Kill();

    // If there was a replacement, reduce it after popping {node}.
    Recurse(replacement);
  }
}


void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
                                    Node* control) {
  if (effect == nullptr && node->op()->EffectInputCount() > 0) {
    effect = NodeProperties::GetEffectInput(node);
  }
  if (control == nullptr && node->op()->ControlInputCount() > 0) {
    control = NodeProperties::GetControlInput(node);
  }

  // Requires distinguishing between value, effect and control edges.
  for (Edge edge : node->use_edges()) {
    Node* const user = edge.from();
    DCHECK(!user->IsDead());
    if (NodeProperties::IsControlEdge(edge)) {
      if (user->opcode() == IrOpcode::kIfSuccess) {
        Replace(user, control);
      } else if (user->opcode() == IrOpcode::kIfException) {
        DCHECK_NOT_NULL(dead_);
        edge.UpdateTo(dead_);
        Revisit(user);
      } else {
        DCHECK_NOT_NULL(control);
        edge.UpdateTo(control);
        Revisit(user);
      }
    } else if (NodeProperties::IsEffectEdge(edge)) {
      DCHECK_NOT_NULL(effect);
      edge.UpdateTo(effect);
      Revisit(user);
    } else {
      DCHECK_NOT_NULL(value);
      edge.UpdateTo(value);
      Revisit(user);
    }
  }
}


void GraphReducer::Pop() {
  Node* node = stack_.top().node;
  state_.Set(node, State::kVisited);
  stack_.pop();
}


void GraphReducer::Push(Node* const node) {
  DCHECK_NE(State::kOnStack, state_.Get(node));
  state_.Set(node, State::kOnStack);
  stack_.push({node, 0});
}


bool GraphReducer::Recurse(Node* node) {
  if (state_.Get(node) > State::kRevisit) return false;
  Push(node);
  return true;
}


void GraphReducer::Revisit(Node* node) {
  if (state_.Get(node) == State::kVisited) {
    state_.Set(node, State::kRevisit);
    revisit_.push(node);
  }
}

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