| // 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 |