control-equivalence.cc

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