blob: 8631810ebd3222432f21a7001423157618ffad02 [file] [log] [blame]
// 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