| // 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 "src/compiler/common-operator.h" |
| #include "src/compiler/control-reducer.h" |
| #include "src/compiler/graph.h" |
| #include "src/compiler/js-graph.h" |
| #include "src/compiler/node-matchers.h" |
| #include "src/compiler/node-properties-inl.h" |
| #include "src/zone-containers.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| enum VisitState { kUnvisited, kOnStack, kRevisit, kVisited }; |
| |
| #define TRACE(x) \ |
| if (FLAG_trace_turbo) PrintF x |
| |
| class ControlReducerImpl { |
| public: |
| ControlReducerImpl(Zone* zone, JSGraph* jsgraph, |
| CommonOperatorBuilder* common) |
| : zone_(zone), |
| jsgraph_(jsgraph), |
| common_(common), |
| state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_), |
| stack_(zone_), |
| revisit_(zone_), |
| dead_(NULL) {} |
| |
| Zone* zone_; |
| JSGraph* jsgraph_; |
| CommonOperatorBuilder* common_; |
| ZoneVector<VisitState> state_; |
| ZoneDeque<Node*> stack_; |
| ZoneDeque<Node*> revisit_; |
| Node* dead_; |
| |
| void Trim() { |
| // Mark all nodes reachable from end. |
| NodeVector nodes(zone_); |
| state_.assign(jsgraph_->graph()->NodeCount(), kUnvisited); |
| Push(jsgraph_->graph()->end()); |
| while (!stack_.empty()) { |
| Node* node = stack_[stack_.size() - 1]; |
| stack_.pop_back(); |
| state_[node->id()] = kVisited; |
| nodes.push_back(node); |
| for (InputIter i = node->inputs().begin(); i != node->inputs().end(); |
| ++i) { |
| Recurse(*i); // pushes node onto the stack if necessary. |
| } |
| } |
| // Process cached nodes in the JSGraph too. |
| jsgraph_->GetCachedNodes(&nodes); |
| // Remove dead->live edges. |
| for (size_t j = 0; j < nodes.size(); j++) { |
| Node* node = nodes[j]; |
| for (UseIter i = node->uses().begin(); i != node->uses().end();) { |
| size_t id = static_cast<size_t>((*i)->id()); |
| if (state_[id] != kVisited) { |
| TRACE(("DeadLink: #%d:%s(%d) -> #%d:%s\n", (*i)->id(), |
| (*i)->op()->mnemonic(), i.index(), node->id(), |
| node->op()->mnemonic())); |
| i.UpdateToAndIncrement(NULL); |
| } else { |
| ++i; |
| } |
| } |
| } |
| #if DEBUG |
| // Verify that no inputs to live nodes are NULL. |
| for (size_t j = 0; j < nodes.size(); j++) { |
| Node* node = nodes[j]; |
| for (InputIter i = node->inputs().begin(); i != node->inputs().end(); |
| ++i) { |
| CHECK_NE(NULL, *i); |
| } |
| for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) { |
| size_t id = static_cast<size_t>((*i)->id()); |
| CHECK_EQ(kVisited, state_[id]); |
| } |
| } |
| #endif |
| } |
| |
| // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}. |
| bool Recurse(Node* node) { |
| size_t id = static_cast<size_t>(node->id()); |
| if (id < state_.size()) { |
| if (state_[id] != kRevisit && state_[id] != kUnvisited) return false; |
| } else { |
| state_.resize((3 * id) / 2, kUnvisited); |
| } |
| Push(node); |
| return true; |
| } |
| |
| void Push(Node* node) { |
| state_[node->id()] = kOnStack; |
| stack_.push_back(node); |
| } |
| }; |
| |
| void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph, |
| CommonOperatorBuilder* common) { |
| ControlReducerImpl impl(zone, jsgraph, NULL); |
| // Only trim the graph for now. Control reduction can reduce non-terminating |
| // loops to graphs that are unschedulable at the moment. |
| impl.Trim(); |
| } |
| |
| |
| void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) { |
| ControlReducerImpl impl(zone, jsgraph, NULL); |
| impl.Trim(); |
| } |
| } |
| } |
| } // namespace v8::internal::compiler |