deps/v8/src/regexp/regexp-bytecode-analysis.h - main - githubmirror/node

deps/v8/src/regexp/regexp-bytecode-analysis.h
117 строк4 KB
Michaël Zasso
deps: update V8 to 14.6.202.33
24 апр 2026, 19:01
24 апр 2026, 19:01f1e0b83
// Copyright 2026 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_REGEXP_REGEXP_BYTECODE_ANALYSIS_H_
#define V8_REGEXP_REGEXP_BYTECODE_ANALYSIS_H_

#include "src/common/globals.h"
#include "src/handles/handles.h"
#include "src/objects/trusted-object.h"
#include "src/utils/bit-vector.h"
#include "src/zone/zone-containers.h"
#include "src/zone/zone.h"

namespace v8 {
namespace internal {

class TrustedByteArray;

class RegExpBytecodeAnalysis : public ZoneObject {
 public:
  RegExpBytecodeAnalysis(Isolate* isolate, Zone* zone,
                         DirectHandle<TrustedByteArray> bytecode);

  // Runs the analysis.
  void Analyze();

  void PrintBlock(int block_id);

  // Queries
  bool IsLoopHeader(int block_id) const;
  bool IsBackEdge(int bytecode_offset) const;

  bool UsesCurrentChar(int block_id) const;
  bool LoadsCurrentChar(int block_id) const;

  int GetBlockId(int bytecode_offset) const;
  int GetEbbId(int bytecode_offset) const;
  int BlockStart(int block_id) const;
  int BlockEnd(int block_id) const;

 private:
  struct LoopInfo {
    int header_block_id;
    BitVector members;
    // Pairs of (source_block_id, target_block_id).
    ZoneVector<std::pair<int, int>> exits;

    LoopInfo(int header_id, int num_blocks, Zone* zone)
        : header_block_id(header_id), members(num_blocks, zone), exits(zone) {}
  };

  void FindBasicBlocks();
  void AnalyzeControlFlow();
  void ComputeLoops(const ZoneVector<std::pair<int, int>>& back_edges);
  void AnalyzeDataFlow();

  // Helper to iterate successors of a block.
  template <typename Callback>
  void ForEachSuccessor(int block_id, Callback callback,
                        bool include_backtrack);

  int block_count() const {
    return static_cast<int>(block_starts_.size()) - kSlotAtLength;
  }

  Zone* zone_;
  Handle<TrustedByteArray> bytecode_;
  int length_;

  // Some arrays are sized so they are safe to access at index
  // `bytecode_array.length`.
  static constexpr int kSlotAtLength = 1;

  // TODO(jgruber): For all bytecode_offset-indexed data structures: reduce
  // overhead by only considering kBytecodeAlignment. We could also merge block
  // information (such as the ebb id) into a BlockInfo struct.

  // Enable backwards walks. Index: bytecode_offset.
  ZoneVector<uint8_t> offset_to_prev_bytecode_;

  // Backtrack bytecodes may jump to any backtrack target. We collect all
  // PushBacktrack targets in the first pass.
  ZoneVector<uint32_t> backtrack_targets_;

  // Block boundaries. Index: block_id.
  // Block[i] range is [ block_starts_[i], block_starts_[i+1] )
  // The last entry in block_starts_ is equal to length_, serving as the
  // end of the last block.
  ZoneVector<int> block_starts_;

  // Which block a bytecode belongs to. Index: bytecode_offset.
  ZoneVector<int32_t> offset_to_block_id_;

  // Extended basic blocks (single entry, multiple exits).
  // Which EBB a bytecode belongs to. Index: bytecode_offset.
  ZoneVector<int32_t> offset_to_ebb_id_;

  // Predecessors for each block. Index: block_id.
  ZoneVector<ZoneSet<int>> predecessors_;

  // Loops found in the graph.
  ZoneVector<LoopInfo> loops_;

  // Analysis Results
  BitVector is_loop_header_;      // Index: block_id.
  BitVector is_back_edge_;        // Index: bytecode_offset.
  BitVector uses_current_char_;   // Index: block_id.
  BitVector loads_current_char_;  // Index: block_id.

  DisallowGarbageCollection no_gc_;
};

}  // namespace internal
}  // namespace v8

#endif  // V8_REGEXP_REGEXP_BYTECODE_ANALYSIS_H_