deps/v8/src/maglev/maglev-graph-processor.h - main - githubmirror/node

deps/v8/src/maglev/maglev-graph-processor.h
506 строк16 KB
Michaël Zasso
deps: update V8 to 14.6.202.33
24 апр 2026, 19:01
24 апр 2026, 19:01f1e0b83
// 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>
class GraphProcessor;
template <typename NodeProcessor>
class GraphBackwardProcessor;

enum class BlockProcessResult {
  kContinue,  // Process exited normally.
  kSkip,      // Skip processing this blockand and do not call the following
              // processors.
};

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).
  kRevisit,   // Process this node again. Note that the node is allowed to have
              // changed.
  kTruncateBlock,  // Remove all nodes from this point from the basic block
                   // (including the current node) 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:
  static constexpr int kNoNodeIndex = -1;

  explicit ProcessingState(BlockConstIterator block_end,
                           BlockConstIterator block_it,
                           int node_index = kNoNodeIndex)
      : block_end_(block_end), block_it_(block_it), node_index_(node_index) {
    DCHECK_IMPLIES(node_index != kNoNodeIndex, node_index >= 0);
  }

  // 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 {
    BlockConstIterator next_block_it = block_it_ + 1;
    if (next_block_it == block_end_) return nullptr;
    return *next_block_it;
  }

  int node_index() const {
    DCHECK_GE(node_index_, 0);
    return node_index_;
  }

 private:
  BlockConstIterator block_end_;
  BlockConstIterator block_it_;
  const int node_index_;  // Index inside the basic block.
};

template <typename NodeProcessor>
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(0));
        switch (result) {
          [[likely]] case ProcessResult::kContinue:
            ++it;
            break;
          case ProcessResult::kRevisit:
            break;
          case ProcessResult::kRemove:
            it = map.erase(it);
            break;
          case ProcessResult::kTruncateBlock:
          case ProcessResult::kHoist:
          case ProcessResult::kAbort:
          case ProcessResult::kSkipBlock:
            UNREACHABLE();
        }
      }
    };
    // LINT.IfChange(maglev_constant_nodes)
    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->intptr());
    process_constants(graph->float64());
    process_constants(graph->holey_float64());
    process_constants(graph->heap_number());
    process_constants(graph->trusted_constants());
    // LINT.ThenChange()

    for (block_it_ = graph->begin(); block_it_ != graph->end(); ++block_it_) {
      bool process_control_block = true;
      BasicBlock* block = *block_it_;
      if (V8_UNLIKELY(block->is_dead())) continue;

      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::kRevisit:
              break;
            case ProcessResult::kRemove:
              it = phis.RemoveAt(it);
              break;
            case ProcessResult::kAbort:
              return;
            case ProcessResult::kSkipBlock:
              goto skip_block;
            case ProcessResult::kTruncateBlock:
            case ProcessResult::kHoist:
              UNREACHABLE();
          }
        }
      }

      node_processor_.PostPhiProcessing();

      for (node_it_ = block->nodes().begin();
           node_it_ != block->nodes().end();) {
        Node* node = *node_it_;
        if (node == nullptr) {
          ++node_it_;
          continue;
        }
        ProcessResult result = ProcessNodeBase(
            node, GetCurrentState(node_it_ - block->nodes().begin()));
        switch (result) {
          [[likely]] case ProcessResult::kContinue:
            ++node_it_;
            break;
          case ProcessResult::kRevisit:
            break;
          case ProcessResult::kRemove:
            *node_it_ = nullptr;
            ++node_it_;
            break;
          case ProcessResult::kTruncateBlock:
            block->nodes().resize(node_it_ - block->nodes().begin());
            node_it_ = block->nodes().end();
            graph_->set_may_have_unreachable_blocks(true);
            break;
          case ProcessResult::kHoist: {
            DCHECK(block->predecessor_count() == 1 ||
                   (block->predecessor_count() == 2 && block->is_loop()));
            BasicBlock* target = block->predecessor_at(0);
            DCHECK_EQ(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;
        }
      }

      while (process_control_block) {
        ProcessResult control_result =
            ProcessNodeBase(block->control_node(), GetCurrentState());
        process_control_block = false;
        switch (control_result) {
          [[likely]] case ProcessResult::kContinue:
            break;
          case ProcessResult::kRevisit:
            process_control_block = true;
            break;
          case ProcessResult::kSkipBlock:
            break;
          case ProcessResult::kAbort:
            return;
          case ProcessResult::kRemove:
          case ProcessResult::kTruncateBlock:
          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(
      size_t node_index = ProcessingState::kNoNodeIndex) {
    return ProcessingState(graph_->end(), block_it_,
                           static_cast<int>(node_index));
  }

  ProcessResult ProcessNodeBase(NodeBase* node, const ProcessingState& state) {
    switch (node->opcode()) {
#define CASE(OPCODE)                                        \
  case Opcode::k##OPCODE:                                   \
    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_;
};

template <typename NodeProcessor>
class GraphBackwardProcessor {
 public:
  template <typename... Args>
  explicit GraphBackwardProcessor(Args&&... args)
      : node_processor_(std::forward<Args>(args)...) {}

  void ProcessGraph(Graph* graph) {
    node_processor_.PreProcessGraph(graph);

    for (BasicBlock* block : base::Reversed(graph->blocks())) {
      {
        ProcessResult control_result = ProcessNodeBase(block->control_node());
        switch (control_result) {
          [[likely]] case ProcessResult::kContinue:
            break;
          case ProcessResult::kAbort:
            return;
          case ProcessResult::kRevisit:
          case ProcessResult::kRemove:
          case ProcessResult::kTruncateBlock:
          case ProcessResult::kHoist:
          case ProcessResult::kSkipBlock:
            UNREACHABLE();
        }
      }

      for (Node* node : base::Reversed(block->nodes())) {
        if (node == nullptr) continue;
        ProcessResult result = ProcessNodeBase(node);
        switch (result) {
          [[likely]] case ProcessResult::kContinue:
            break;
          case ProcessResult::kAbort:
            return;
          case ProcessResult::kRevisit:
          case ProcessResult::kRemove:
          case ProcessResult::kTruncateBlock:
          case ProcessResult::kHoist:
          case ProcessResult::kSkipBlock:
            UNREACHABLE();
        }
      }

      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);
          switch (result) {
            [[likely]] case ProcessResult::kContinue:
              ++it;
              break;
            case ProcessResult::kRemove:
              it = phis.RemoveAt(it);
              break;
            case ProcessResult::kAbort:
              return;
            case ProcessResult::kTruncateBlock:
            case ProcessResult::kRevisit:
            case ProcessResult::kSkipBlock:
            case ProcessResult::kHoist:
              UNREACHABLE();
          }
        }
      }

      node_processor_.PostProcessBasicBlock(block);
    }

    auto process_constants = [&](auto& map) {
      for (auto it = map.begin(); it != map.end();) {
        ProcessResult result = node_processor_.Process(it->second);
        switch (result) {
          [[likely]] case ProcessResult::kContinue:
            ++it;
            break;
          case ProcessResult::kRemove:
            it = map.erase(it);
            break;
          case ProcessResult::kRevisit:
          case ProcessResult::kHoist:
          case ProcessResult::kAbort:
          case ProcessResult::kTruncateBlock:
          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->intptr());
    process_constants(graph->float64());
    process_constants(graph->heap_number());
    process_constants(graph->trusted_constants());

    node_processor_.PostProcessGraph(graph);
  }

 private:
  ProcessResult ProcessNodeBase(NodeBase* node) {
    switch (node->opcode()) {
#define CASE(OPCODE)      \
  case Opcode::k##OPCODE: \
    return node_processor_.Process(node->Cast<OPCODE>());
      NODE_BASE_LIST(CASE)
#undef CASE
    }
  }

  NodeProcessor node_processor_;
};

// 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::kRevisit:
      case ProcessResult::kAbort:
      case ProcessResult::kRemove:
        return res;
      case ProcessResult::kTruncateBlock:
        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:
        return res;
    }
  }
  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_