// 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(turbofan): 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