maglev-graph-processor.h

Go to the documentation of this file.

// Copyright 2022 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.
 
#ifndef V8_MAGLEV_MAGLEV_GRAPH_PROCESSOR_H_
#define V8_MAGLEV_MAGLEV_GRAPH_PROCESSOR_H_
 
#include "src/base/macros.h"
#include "src/compiler/bytecode-analysis.h"
#include "src/maglev/maglev-basic-block.h"
#include "src/maglev/maglev-compilation-info.h"
#include "src/maglev/maglev-graph.h"
#include "src/maglev/maglev-interpreter-frame-state.h"
#include "src/maglev/maglev-ir.h"
 
namespace v8 {
namespace internal {
namespace maglev {
 
// The GraphProcessor takes a NodeProcessor, and applies it to each Node in the
// Graph by calling NodeProcessor::Process on each Node.
//
// The GraphProcessor also keeps track of the current ProcessingState, and
// passes this to the Process method.
//
// It expects a NodeProcessor class with:
//
//   // A function that processes the graph before the nodes are walked.
//   void PreProcessGraph(Graph* graph);
//
//   // A function that processes the graph after the nodes are walked.
//   void PostProcessGraph(Graph* graph);
//
//   // A function that processes each basic block before its nodes are walked.
//   BlockProcessResult PreProcessBasicBlock(BasicBlock* block);
//
//   // Process methods for each Node type. The GraphProcessor switches over
//   // the Node's opcode, casts it to the appropriate FooNode, and dispatches
//   // to NodeProcessor::Process. It's then up to the NodeProcessor to provide
//   // either distinct Process methods per Node type, or using templates or
//   // overloading as appropriate to group node processing.
//   void Process(FooNode* node, const ProcessingState& state) {}
//
template <typename NodeProcessor, bool visit_identity_nodes = false>
class GraphProcessor;
 
enum class BlockProcessResult {
  kContinue,  // Process exited normally.
  kSkip,      // Skip processing this block (no MultiProcessor support).
};
 
enum class ProcessResult {
  kContinue,   // Process exited normally, and the following processors will be
               // called on the node.
  kRemove,     // Remove the current node from the graph (and do not call the
               // following processors).
  kHoist,      // Hoist the current instruction to the parent basic block
               // and reset the current instruction to the beginning of the
               // block. Parent block must be dominating.
  kAbort,      // Stop processing now, do not process subsequent nodes/blocks.
               // Should not be used when processing Constants.
  kSkipBlock,  // Stop processing this block and skip the remaining nodes (no
               // MultiProcessor support).
};
 
class ProcessingState {
 public:
  explicit ProcessingState(BlockConstIterator block_it,
                           NodeIterator* node_it = nullptr)
      : block_it_(block_it), node_it_(node_it) {}
 
  // Disallow copies, since the underlying frame states stay mutable.
  ProcessingState(const ProcessingState&) = delete;
  ProcessingState& operator=(const ProcessingState&) = delete;
 
  BasicBlock* block() const { return *block_it_; }
  BasicBlock* next_block() const { return *(block_it_ + 1); }
 
  NodeIterator* node_it() const {
    DCHECK_NOT_NULL(node_it_);
    return node_it_;
  }
 
 private:
  BlockConstIterator block_it_;
  NodeIterator* node_it_;
};
 
template <typename NodeProcessor, bool visit_identity_nodes>
class GraphProcessor {
 public:
  template <typename... Args>
  explicit GraphProcessor(Args&&... args)
      : node_processor_(std::forward<Args>(args)...) {}
 
  void ProcessGraph(Graph* graph) {
    graph_ = graph;
 
    node_processor_.PreProcessGraph(graph);
 
    auto process_constants = [&](auto& map) {
      for (auto it = map.begin(); it != map.end();) {
        ProcessResult result =
            node_processor_.Process(it->second, GetCurrentState());
        switch (result) {
          [[likely]] case ProcessResult::kContinue:
            ++it;
            break;
          case ProcessResult::kRemove:
            it = map.erase(it);
            break;
          case ProcessResult::kHoist:
          case ProcessResult::kAbort:
          case ProcessResult::kSkipBlock:
            UNREACHABLE();
        }
      }
    };
    process_constants(graph->constants());
    process_constants(graph->root());
    process_constants(graph->smi());
    process_constants(graph->tagged_index());
    process_constants(graph->int32());
    process_constants(graph->uint32());
    process_constants(graph->float64());
    process_constants(graph->external_references());
    process_constants(graph->trusted_constants());
 
    for (block_it_ = graph->begin(); block_it_ != graph->end(); ++block_it_) {
      BasicBlock* block = *block_it_;
 
      BlockProcessResult preprocess_result =
          node_processor_.PreProcessBasicBlock(block);
      switch (preprocess_result) {
        [[likely]] case BlockProcessResult::kContinue:
          break;
        case BlockProcessResult::kSkip:
          continue;
      }
 
      if (block->has_phi()) {
        auto& phis = *block->phis();
        for (auto it = phis.begin(); it != phis.end();) {
          Phi* phi = *it;
          ProcessResult result =
              node_processor_.Process(phi, GetCurrentState());
          switch (result) {
            [[likely]] case ProcessResult::kContinue:
              ++it;
              break;
            case ProcessResult::kRemove:
              it = phis.RemoveAt(it);
              break;
            case ProcessResult::kAbort:
              return;
            case ProcessResult::kSkipBlock:
              goto skip_block;
            case ProcessResult::kHoist:
              UNREACHABLE();
          }
        }
      }
 
      node_processor_.PostPhiProcessing();
 
      for (node_it_ = block->nodes().begin(); node_it_ != block->nodes().end();
           ++node_it_) {
        Node* node = *node_it_;
        if (node == nullptr) continue;
        ProcessResult result = ProcessNodeBase(node, GetCurrentState());
        switch (result) {
          [[likely]] case ProcessResult::kContinue:
            break;
          case ProcessResult::kRemove:
            *node_it_ = nullptr;
            break;
          case ProcessResult::kHoist: {
            DCHECK(block->predecessor_count() == 1 ||
                   (block->predecessor_count() == 2 && block->is_loop()));
            BasicBlock* target = block->predecessor_at(0);
            DCHECK(target->successors().size() == 1);
            Node* cur = *node_it_;
            cur->set_owner(target);
            *node_it_ = nullptr;
            target->nodes().push_back(cur);
            node_it_ = block->nodes().begin();
            break;
          }
          case ProcessResult::kAbort:
            return;
          case ProcessResult::kSkipBlock:
            goto skip_block;
        }
      }
 
      {
        ProcessResult control_result =
            ProcessNodeBase(block->control_node(), GetCurrentState());
        switch (control_result) {
          [[likely]] case ProcessResult::kContinue:
          case ProcessResult::kSkipBlock:
            break;
          case ProcessResult::kAbort:
            return;
          case ProcessResult::kRemove:
          case ProcessResult::kHoist:
            UNREACHABLE();
        }
      }
    skip_block:
      node_processor_.PostProcessBasicBlock(block);
      continue;
    }
 
    node_processor_.PostProcessGraph(graph);
  }
 
  NodeProcessor& node_processor() { return node_processor_; }
  const NodeProcessor& node_processor() const { return node_processor_; }
 
 private:
  ProcessingState GetCurrentState() {
    return ProcessingState(block_it_, &node_it_);
  }
 
  ProcessResult ProcessNodeBase(NodeBase* node, const ProcessingState& state) {
    switch (node->opcode()) {
#define CASE(OPCODE)                                        \
  case Opcode::k##OPCODE:                                   \
    if constexpr (!visit_identity_nodes &&                  \
                  Opcode::k##OPCODE == Opcode::kIdentity) { \
      return ProcessResult::kContinue;                      \
    }                                                       \
    PreProcess(node->Cast<OPCODE>(), state);                \
    return node_processor_.Process(node->Cast<OPCODE>(), state);
 
      NODE_BASE_LIST(CASE)
#undef CASE
    }
  }
 
  void PreProcess(NodeBase* node, const ProcessingState& state) {}
 
  NodeProcessor node_processor_;
  Graph* graph_;
  BlockConstIterator block_it_;
  NodeIterator node_it_;
};
 
// A NodeProcessor that wraps multiple NodeProcessors, and forwards to each of
// them iteratively.
template <typename... Processors>
class NodeMultiProcessor;
 
template <>
class NodeMultiProcessor<> {
 public:
  void PreProcessGraph(Graph* graph) {}
  void PostProcessGraph(Graph* graph) {}
  BlockProcessResult PreProcessBasicBlock(BasicBlock* block) {
    return BlockProcessResult::kContinue;
  }
  void PostProcessBasicBlock(BasicBlock* block) {}
  V8_INLINE ProcessResult Process(NodeBase* node,
                                  const ProcessingState& state) {
    return ProcessResult::kContinue;
  }
  void PostPhiProcessing() {}
};
 
template <typename Processor, typename... Processors>
class NodeMultiProcessor<Processor, Processors...>
    : NodeMultiProcessor<Processors...> {
  using Base = NodeMultiProcessor<Processors...>;
 
 public:
  template <typename... Args>
  explicit NodeMultiProcessor(Processor&& processor, Args&&... processors)
      : Base(std::forward<Args>(processors)...),
        processor_(std::forward<Processor>(processor)) {}
  template <typename... Args>
  explicit NodeMultiProcessor(Args&&... processors)
      : Base(std::forward<Args>(processors)...) {}
 
  template <typename Node>
  ProcessResult Process(Node* node, const ProcessingState& state) {
    auto res = processor_.Process(node, state);
    switch (res) {
      [[likely]] case ProcessResult::kContinue:
        return Base::Process(node, state);
      case ProcessResult::kAbort:
      case ProcessResult::kRemove:
        return res;
      case ProcessResult::kHoist:
      case ProcessResult::kSkipBlock:
        // TODO(olivf): How to combine these with multiple processors depends on
        // the needs of the actual processors. Implement once needed.
        UNREACHABLE();
    }
  }
  void PreProcessGraph(Graph* graph) {
    processor_.PreProcessGraph(graph);
    Base::PreProcessGraph(graph);
  }
  void PostProcessGraph(Graph* graph) {
    // Post process in reverse order because that kind of makes sense.
    Base::PostProcessGraph(graph);
    processor_.PostProcessGraph(graph);
  }
  void PostProcessBasicBlock(BasicBlock* block) {
    Base::PostProcessBasicBlock(block);
    processor_.PostProcessBasicBlock(block);
  }
  BlockProcessResult PreProcessBasicBlock(BasicBlock* block) {
    BlockProcessResult res = processor_.PreProcessBasicBlock(block);
    switch (res) {
      [[likely]] case BlockProcessResult::kContinue:
        return Base::PreProcessBasicBlock(block);
      case BlockProcessResult::kSkip:
        // TODO(olivf): How to combine this with multiple processors depends on
        // the needs of the actual processors. Implement once needed.
        UNREACHABLE();
    }
  }
  void PostPhiProcessing() {
    processor_.PostPhiProcessing();
    Base::PostPhiProcessing();
  }
 
 private:
  Processor processor_;
};
 
template <typename... Processors>
using GraphMultiProcessor = GraphProcessor<NodeMultiProcessor<Processors...>>;
 
}  // namespace maglev
}  // namespace internal
}  // namespace v8
 
#endif  // V8_MAGLEV_MAGLEV_GRAPH_PROCESSOR_H_