| // 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/control-equivalence.h" |
| #include "src/compiler/node-properties.h" |
| |
| #define TRACE(...) \ |
| do { \ |
| if (FLAG_trace_turbo_ceq) PrintF(__VA_ARGS__); \ |
| } while (false) |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| void ControlEquivalence::Run(Node* exit) { |
| if (!Participates(exit) || GetClass(exit) == kInvalidClass) { |
| DetermineParticipation(exit); |
| RunUndirectedDFS(exit); |
| } |
| } |
| |
| |
| // static |
| STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass; |
| |
| |
| void ControlEquivalence::VisitPre(Node* node) { |
| TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic()); |
| } |
| |
| |
| void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) { |
| TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic()); |
| BracketList& blist = GetBracketList(node); |
| |
| // Remove brackets pointing to this node [line:19]. |
| BracketListDelete(blist, node, direction); |
| |
| // Potentially introduce artificial dependency from start to end. |
| if (blist.empty()) { |
| DCHECK_EQ(kInputDirection, direction); |
| VisitBackedge(node, graph_->end(), kInputDirection); |
| } |
| |
| // Potentially start a new equivalence class [line:37]. |
| BracketListTRACE(blist); |
| Bracket* recent = &blist.back(); |
| if (recent->recent_size != blist.size()) { |
| recent->recent_size = blist.size(); |
| recent->recent_class = NewClassNumber(); |
| } |
| |
| // Assign equivalence class to node. |
| SetClass(node, recent->recent_class); |
| TRACE(" Assigned class number is %zu\n", GetClass(node)); |
| } |
| |
| |
| void ControlEquivalence::VisitPost(Node* node, Node* parent_node, |
| DFSDirection direction) { |
| TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic()); |
| BracketList& blist = GetBracketList(node); |
| |
| // Remove brackets pointing to this node [line:19]. |
| BracketListDelete(blist, node, direction); |
| |
| // Propagate bracket list up the DFS tree [line:13]. |
| if (parent_node != nullptr) { |
| BracketList& parent_blist = GetBracketList(parent_node); |
| parent_blist.splice(parent_blist.end(), blist); |
| } |
| } |
| |
| |
| void ControlEquivalence::VisitBackedge(Node* from, Node* to, |
| DFSDirection direction) { |
| TRACE("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(), |
| from->op()->mnemonic(), to->id(), to->op()->mnemonic()); |
| |
| // Push backedge onto the bracket list [line:25]. |
| Bracket bracket = {direction, kInvalidClass, 0, from, to}; |
| GetBracketList(from).push_back(bracket); |
| } |
| |
| |
| void ControlEquivalence::RunUndirectedDFS(Node* exit) { |
| ZoneStack<DFSStackEntry> stack(zone_); |
| DFSPush(stack, exit, nullptr, kInputDirection); |
| VisitPre(exit); |
| |
| while (!stack.empty()) { // Undirected depth-first backwards traversal. |
| DFSStackEntry& entry = stack.top(); |
| Node* node = entry.node; |
| |
| if (entry.direction == kInputDirection) { |
| if (entry.input != node->input_edges().end()) { |
| Edge edge = *entry.input; |
| Node* input = edge.to(); |
| ++(entry.input); |
| if (NodeProperties::IsControlEdge(edge)) { |
| // Visit next control input. |
| if (!Participates(input)) continue; |
| if (GetData(input)->visited) continue; |
| if (GetData(input)->on_stack) { |
| // Found backedge if input is on stack. |
| if (input != entry.parent_node) { |
| VisitBackedge(node, input, kInputDirection); |
| } |
| } else { |
| // Push input onto stack. |
| DFSPush(stack, input, node, kInputDirection); |
| VisitPre(input); |
| } |
| } |
| continue; |
| } |
| if (entry.use != node->use_edges().end()) { |
| // Switch direction to uses. |
| entry.direction = kUseDirection; |
| VisitMid(node, kInputDirection); |
| continue; |
| } |
| } |
| |
| if (entry.direction == kUseDirection) { |
| if (entry.use != node->use_edges().end()) { |
| Edge edge = *entry.use; |
| Node* use = edge.from(); |
| ++(entry.use); |
| if (NodeProperties::IsControlEdge(edge)) { |
| // Visit next control use. |
| if (!Participates(use)) continue; |
| if (GetData(use)->visited) continue; |
| if (GetData(use)->on_stack) { |
| // Found backedge if use is on stack. |
| if (use != entry.parent_node) { |
| VisitBackedge(node, use, kUseDirection); |
| } |
| } else { |
| // Push use onto stack. |
| DFSPush(stack, use, node, kUseDirection); |
| VisitPre(use); |
| } |
| } |
| continue; |
| } |
| if (entry.input != node->input_edges().end()) { |
| // Switch direction to inputs. |
| entry.direction = kInputDirection; |
| VisitMid(node, kUseDirection); |
| continue; |
| } |
| } |
| |
| // Pop node from stack when done with all inputs and uses. |
| DCHECK(entry.input == node->input_edges().end()); |
| DCHECK(entry.use == node->use_edges().end()); |
| DFSPop(stack, node); |
| VisitPost(node, entry.parent_node, entry.direction); |
| } |
| } |
| |
| void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, |
| Node* node) { |
| if (!Participates(node)) { |
| AllocateData(node); |
| queue.push(node); |
| } |
| } |
| |
| |
| void ControlEquivalence::DetermineParticipation(Node* exit) { |
| ZoneQueue<Node*> queue(zone_); |
| DetermineParticipationEnqueue(queue, exit); |
| while (!queue.empty()) { // Breadth-first backwards traversal. |
| Node* node = queue.front(); |
| queue.pop(); |
| int max = NodeProperties::PastControlIndex(node); |
| for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { |
| DetermineParticipationEnqueue(queue, node->InputAt(i)); |
| } |
| } |
| } |
| |
| |
| void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from, |
| DFSDirection dir) { |
| DCHECK(Participates(node)); |
| DCHECK(!GetData(node)->visited); |
| GetData(node)->on_stack = true; |
| Node::InputEdges::iterator input = node->input_edges().begin(); |
| Node::UseEdges::iterator use = node->use_edges().begin(); |
| stack.push({dir, input, use, from, node}); |
| } |
| |
| |
| void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) { |
| DCHECK_EQ(stack.top().node, node); |
| GetData(node)->on_stack = false; |
| GetData(node)->visited = true; |
| stack.pop(); |
| } |
| |
| |
| void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to, |
| DFSDirection direction) { |
| // TODO(mstarzinger): Optimize this to avoid linear search. |
| for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) { |
| if (i->to == to && i->direction != direction) { |
| TRACE(" BList erased: {%d->%d}\n", i->from->id(), i->to->id()); |
| i = blist.erase(i); |
| } else { |
| ++i; |
| } |
| } |
| } |
| |
| |
| void ControlEquivalence::BracketListTRACE(BracketList& blist) { |
| if (FLAG_trace_turbo_ceq) { |
| TRACE(" BList: "); |
| for (Bracket bracket : blist) { |
| TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id()); |
| } |
| TRACE("\n"); |
| } |
| } |
| |
| #undef TRACE |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |