diff --git a/js/src/irregexp/imported/regexp-ast.h b/js/src/irregexp/imported/regexp-ast.h --- a/js/src/irregexp/imported/regexp-ast.h +++ b/js/src/irregexp/imported/regexp-ast.h @@ -178,24 +178,25 @@ } inline bool operator!=(const CharacterRange& lhs, const CharacterRange& rhs) { return !operator==(lhs, rhs); } -#define DECL_BOILERPLATE(Name) \ - void* Accept(RegExpVisitor* visitor, void* data) override; \ - RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) \ - override; \ - RegExp##Name* As##Name() override; \ +#define DECL_BOILERPLATE(Name) \ + void* Accept(RegExpVisitor* visitor, void* data) override; \ + RegExpNode* ToNodeImpl(RegExpCompiler* compiler, RegExpNode* on_success) \ + override; \ + RegExp##Name* As##Name() override; \ bool Is##Name() override class RegExpTree : public ZoneObject { public: static const int kInfinity = kMaxInt; virtual ~RegExpTree() = default; virtual void* Accept(RegExpVisitor* visitor, void* data) = 0; - virtual RegExpNode* ToNode(RegExpCompiler* compiler, - RegExpNode* on_success) = 0; + RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success); + virtual RegExpNode* ToNodeImpl(RegExpCompiler* compiler, + RegExpNode* on_success) = 0; virtual bool IsTextElement() { return false; } virtual bool IsAnchoredAtStart() { return false; } virtual bool IsAnchoredAtEnd() { return false; } virtual int min_match() = 0; virtual int max_match() = 0; @@ -531,10 +532,13 @@ elements_.Add(elm, zone); length_ += elm.length(); } ZoneList* elements() { return &elements_; } + bool StartsWithAtom() const; + RegExpAtom* FirstAtom() const; + private: ZoneList elements_; int length_ = 0; }; diff --git a/js/src/irregexp/imported/regexp-ast.cc b/js/src/irregexp/imported/regexp-ast.cc --- a/js/src/irregexp/imported/regexp-ast.cc +++ b/js/src/irregexp/imported/regexp-ast.cc @@ -437,7 +437,14 @@ return zone->template New( RegExpClassSetExpression::OperationType::kUnion, is_negated, false, operands); } +bool RegExpText::StartsWithAtom() const { + if (elements_.length() == 0) return false; + return elements_.at(0).text_type() == TextElement::ATOM; +} + +RegExpAtom* RegExpText::FirstAtom() const { return elements_.at(0).atom(); } + } // namespace internal } // namespace v8 diff --git a/js/src/irregexp/imported/regexp-bytecode-generator-inl.h b/js/src/irregexp/imported/regexp-bytecode-generator-inl.h --- a/js/src/irregexp/imported/regexp-bytecode-generator-inl.h +++ b/js/src/irregexp/imported/regexp-bytecode-generator-inl.h @@ -4,52 +4,73 @@ #ifndef V8_REGEXP_REGEXP_BYTECODE_GENERATOR_INL_H_ #define V8_REGEXP_REGEXP_BYTECODE_GENERATOR_INL_H_ #include "irregexp/imported/regexp-bytecode-generator.h" +// Include the non-inl header before the rest of the headers. -#include "irregexp/imported/regexp-bytecodes.h" +#include "irregexp/imported/regexp-bytecodes-inl.h" namespace v8 { namespace internal { -void RegExpBytecodeGenerator::Emit(uint32_t byte, uint32_t twenty_four_bits) { - DCHECK(is_uint24(twenty_four_bits)); - Emit32((twenty_four_bits << BYTECODE_SHIFT) | byte); +template +void RegExpBytecodeGenerator::Emit(T value, int offset) { + const int new_pc_within_bc = pc_ + offset; + DCHECK(base::IsInRange(new_pc_within_bc, pc_within_bc_, end_of_bc_)); + DCHECK_LE(new_pc_within_bc + sizeof(T), buffer_.size()); + DCHECK_LE(new_pc_within_bc + sizeof(T), end_of_bc_); + DCHECK(IsAligned(new_pc_within_bc, sizeof(T))); + EMIT_PADDING(offset); + *reinterpret_cast(buffer_.data() + new_pc_within_bc) = value; +#ifdef DEBUG + pc_within_bc_ = new_pc_within_bc + sizeof(T); +#endif } -void RegExpBytecodeGenerator::Emit(uint32_t byte, int32_t twenty_four_bits) { - DCHECK(is_int24(twenty_four_bits)); - Emit32((static_cast(twenty_four_bits) << BYTECODE_SHIFT) | byte); +void RegExpBytecodeGenerator::EmitBytecode(RegExpBytecode bc, + uint32_t packed_arg) { + DCHECK_EQ(pc_, end_of_bc_); + DCHECK_EQ(pc_within_bc_, end_of_bc_); + uint32_t word = (packed_arg << BYTECODE_SHIFT) | RegExpBytecodes::ToByte(bc); +#ifdef DEBUG + end_of_bc_ = pc_ + RegExpBytecodes::Size(bc); + pc_within_bc_ = pc_; +#endif + Emit(word, 0); } -void RegExpBytecodeGenerator::Emit16(uint32_t word) { - DCHECK(pc_ <= static_cast(buffer_.size())); - if (pc_ + 1 >= static_cast(buffer_.size())) { +void RegExpBytecodeGenerator::EnsureCapacity(size_t size) { + if (V8_UNLIKELY(pc_ + size > buffer_.size())) { ExpandBuffer(); } - *reinterpret_cast(buffer_.data() + pc_) = word; - pc_ += 2; +} + +void RegExpBytecodeGenerator::ResetPc(int new_pc) { + // Resetting is only allowed at the beginning of a bytecode. + DCHECK_EQ(pc_, pc_within_bc_); + DCHECK_LE(new_pc, pc_); + pc_ = new_pc; +#ifdef DEBUG + pc_within_bc_ = pc_; + end_of_bc_ = pc_; +#endif } -void RegExpBytecodeGenerator::Emit8(uint32_t word) { - DCHECK(pc_ <= static_cast(buffer_.size())); - if (pc_ == static_cast(buffer_.size())) { - ExpandBuffer(); +#ifdef DEBUG +void RegExpBytecodeGenerator::EmitPadding(int offset) { + const int padding_to = pc_ + offset; + DCHECK_LE(padding_to, buffer_.size()); + DCHECK_LE(padding_to, end_of_bc_); + DCHECK_GE(padding_to, pc_within_bc_); + static constexpr uint8_t kPaddingByte = 0x0; + for (int i = pc_within_bc_; i < padding_to; ++i) { + buffer_[i] = kPaddingByte; } - *reinterpret_cast(buffer_.data() + pc_) = word; - pc_ += 1; + pc_within_bc_ = padding_to; } - -void RegExpBytecodeGenerator::Emit32(uint32_t word) { - DCHECK(pc_ <= static_cast(buffer_.size())); - if (pc_ + 3 >= static_cast(buffer_.size())) { - ExpandBuffer(); - } - *reinterpret_cast(buffer_.data() + pc_) = word; - pc_ += 4; -} +#endif } // namespace internal } // namespace v8 #endif // V8_REGEXP_REGEXP_BYTECODE_GENERATOR_INL_H_ diff --git a/js/src/irregexp/imported/regexp-bytecode-generator.h b/js/src/irregexp/imported/regexp-bytecode-generator.h --- a/js/src/irregexp/imported/regexp-bytecode-generator.h +++ b/js/src/irregexp/imported/regexp-bytecode-generator.h @@ -3,10 +3,11 @@ // found in the LICENSE file. #ifndef V8_REGEXP_REGEXP_BYTECODE_GENERATOR_H_ #define V8_REGEXP_REGEXP_BYTECODE_GENERATOR_H_ +#include "irregexp/imported/regexp-bytecodes.h" #include "irregexp/imported/regexp-macro-assembler.h" namespace v8 { namespace internal { @@ -19,15 +20,12 @@ // for a detailed comment on the layout (globals.h). // // The assembler allocates and grows its own buffer, and buffer_size // determines the initial buffer size. The buffer is owned by the assembler // and deallocated upon destruction of the assembler. - RegExpBytecodeGenerator(Isolate* isolate, Zone* zone); + RegExpBytecodeGenerator(Isolate* isolate, Zone* zone, Mode mode); ~RegExpBytecodeGenerator() override; - // The byte-code interpreter checks on each push anyway. - int stack_limit_slack_slot_count() override { return 1; } - bool CanReadUnaligned() const override { return false; } void Bind(Label* label) override; void AdvanceCurrentPosition(int by) override; // Signed cp change. void PopCurrentPosition() override; void PushCurrentPosition() override; void Backtrack() override; @@ -36,27 +34,31 @@ bool Succeed() override; void Fail() override; void PopRegister(int register_index) override; void PushRegister(int register_index, StackCheckFlag check_stack_limit) override; - void AdvanceRegister(int reg, int by) override; // r[reg] += by. + void AdvanceRegister(int register_index, int by) override; // r[reg] += by. void SetCurrentPositionFromEnd(int by) override; void SetRegister(int register_index, int to) override; - void WriteCurrentPositionToRegister(int reg, int cp_offset) override; + void WriteCurrentPositionToRegister(int register_index, + int cp_offset) override; void ClearRegisters(int reg_from, int reg_to) override; void ReadCurrentPositionFromRegister(int reg) override; - void WriteStackPointerToRegister(int reg) override; - void ReadStackPointerFromRegister(int reg) override; + void WriteStackPointerToRegister(int register_index) override; + void ReadStackPointerFromRegister(int register_index) override; + void CheckPosition(int cp_offset, Label* on_outside_input) override; + void CheckSpecialClassRanges(StandardCharacterSet type, + Label* on_no_match) override; void LoadCurrentCharacterImpl(int cp_offset, Label* on_end_of_input, bool check_bounds, int characters, int eats_at_least) override; void CheckCharacter(unsigned c, Label* on_equal) override; void CheckCharacterAfterAnd(unsigned c, unsigned mask, Label* on_equal) override; void CheckCharacterGT(base::uc16 limit, Label* on_greater) override; void CheckCharacterLT(base::uc16 limit, Label* on_less) override; - void CheckGreedyLoop(Label* on_tos_equals_current_position) override; + void CheckFixedLengthLoop(Label* on_tos_equals_current_position) override; void CheckAtStart(int cp_offset, Label* on_at_start) override; void CheckNotAtStart(int cp_offset, Label* on_not_at_start) override; void CheckNotCharacter(unsigned c, Label* on_not_equal) override; void CheckNotCharacterAfterAnd(unsigned c, unsigned mask, Label* on_not_equal) override; @@ -82,46 +84,94 @@ Label* on_not_in_range) override { return false; } void CheckBitInTable(Handle table, Label* on_bit_set) override; void SkipUntilBitInTable(int cp_offset, Handle table, - Handle nibble_table, - int advance_by) override; + Handle nibble_table, int advance_by, + Label* on_match, Label* on_no_match) override; + void SkipUntilCharAnd(int cp_offset, int advance_by, unsigned character, + unsigned mask, int eats_at_least, Label* on_match, + Label* on_no_match) override; + void SkipUntilChar(int cp_offset, int advance_by, unsigned character, + Label* on_match, Label* on_no_match) override; + void SkipUntilCharPosChecked(int cp_offset, int advance_by, + unsigned character, int eats_at_least, + Label* on_match, Label* on_no_match) override; + void SkipUntilCharOrChar(int cp_offset, int advance_by, unsigned char1, + unsigned char2, Label* on_match, + Label* on_no_match) override; + void SkipUntilGtOrNotBitInTable(int cp_offset, int advance_by, + unsigned character, Handle table, + Label* on_match, Label* on_no_match) override; + void SkipUntilOneOfMasked(int cp_offset, int advance_by, unsigned both_chars, + unsigned both_mask, int max_offset, unsigned chars1, + unsigned mask1, unsigned chars2, unsigned mask2, + Label* on_match1, Label* on_match2, + Label* on_failure) override; + void SkipUntilOneOfMasked3(const SkipUntilOneOfMasked3Args& args) override; void CheckNotBackReference(int start_reg, bool read_backward, Label* on_no_match) override; void CheckNotBackReferenceIgnoreCase(int start_reg, bool read_backward, bool unicode, Label* on_no_match) override; - void IfRegisterLT(int register_index, int comparand, Label* if_lt) override; - void IfRegisterGE(int register_index, int comparand, Label* if_ge) override; - void IfRegisterEqPos(int register_index, Label* if_eq) override; + void IfRegisterLT(int register_index, int comparand, + Label* on_less_than) override; + void IfRegisterGE(int register_index, int comparand, + Label* on_greater_or_equal) override; + void IfRegisterEqPos(int register_index, Label* on_equal) override; + void RecordComment(std::string_view comment) override {} + MacroAssembler* masm() override { return nullptr; } IrregexpImplementation Implementation() override; DirectHandle GetCode(DirectHandle source, RegExpFlags flags) override; private: - void ExpandBuffer(); + // Code and bitmap emission. + template + void Emit(Args... args); + template + auto GetCheckedBasicOperandValue(T value); + template + void EmitOperand(T value, int offset); + template + void EmitPackedOperand(RegExpBytecode bc, T value); - // Code and bitmap emission. - inline void EmitOrLink(Label* label); - inline void Emit32(uint32_t x); - inline void Emit16(uint32_t x); - inline void Emit8(uint32_t x); - inline void Emit(uint32_t bc, uint32_t arg); - inline void Emit(uint32_t bc, int32_t arg); + template + inline void Emit(T value, int offset); + inline void EmitBytecode(RegExpBytecode bc, uint32_t packed_arg = 0); void EmitSkipTable(DirectHandle table); // Bytecode buffer. int length(); void Copy(uint8_t* a); + inline void EnsureCapacity(size_t size); + void ExpandBuffer(); + inline void ResetPc(int new_pc); +#ifdef DEBUG + // Emit padding from start (inclusive) to end (exclusive) + inline void EmitPadding(int offset); +#define EMIT_PADDING(offset) EmitPadding(offset) +#else +#define EMIT_PADDING(offset) ((void)0) +#endif // The buffer into which code and relocation info are generated. static constexpr int kInitialBufferSize = 1024; ZoneVector buffer_; - // The program counter. + // The program counter. Always points at the beginning of a bytecode while + // we generate the ByteArray. Points to the end when we are done. int pc_; +#ifdef DEBUG + // End of the bytecode we are currently emitting (exclusive). Absolute value + // greater than `pc_`. + int end_of_bc_; + // Position (absolute) within the current bytecode. This value is updated with + // every operand and is guaranteed to be between `pc_` and `end_of_bc_`. + int pc_within_bc_; +#endif + Label backtrack_; int advance_current_start_; int advance_current_offset_; int advance_current_end_; diff --git a/js/src/irregexp/imported/regexp-bytecode-generator.cc b/js/src/irregexp/imported/regexp-bytecode-generator.cc --- a/js/src/irregexp/imported/regexp-bytecode-generator.cc +++ b/js/src/irregexp/imported/regexp-bytecode-generator.cc @@ -2,35 +2,153 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "irregexp/imported/regexp-bytecode-generator.h" +#include + #include "irregexp/imported/regexp-bytecode-generator-inl.h" #include "irregexp/imported/regexp-bytecode-peephole.h" -#include "irregexp/imported/regexp-bytecodes.h" +#include "irregexp/imported/regexp-bytecodes-inl.h" #include "irregexp/imported/regexp-macro-assembler.h" namespace v8 { namespace internal { -RegExpBytecodeGenerator::RegExpBytecodeGenerator(Isolate* isolate, Zone* zone) - : RegExpMacroAssembler(isolate, zone), +RegExpBytecodeGenerator::RegExpBytecodeGenerator(Isolate* isolate, Zone* zone, + Mode mode) + : RegExpMacroAssembler(isolate, zone, mode), buffer_(kInitialBufferSize, zone), pc_(0), +#ifdef DEBUG + end_of_bc_(0), + pc_within_bc_(0), +#endif advance_current_end_(kInvalidPC), jump_edges_(zone), - isolate_(isolate) {} + isolate_(isolate) { +} RegExpBytecodeGenerator::~RegExpBytecodeGenerator() { if (backtrack_.is_linked()) backtrack_.Unuse(); } RegExpBytecodeGenerator::IrregexpImplementation RegExpBytecodeGenerator::Implementation() { return kBytecodeImplementation; } +template +void RegExpBytecodeGenerator::Emit(Args... args) { + using Operands = RegExpBytecodeOperands; + static_assert(sizeof...(Args) == Operands::kCountWithoutPadding, + "Wrong number of operands"); + + auto arguments_tuple = std::make_tuple(args...); + EnsureCapacity(Operands::kTotalSize); + if constexpr (Operands::kCount == 0) { + // No operands, just emit the bytecode. + EmitBytecode(bytecode); + } + Operands::ForEachOperandWithIndex([&]() { + constexpr RegExpBytecodeOperandType type = Operands::Type(op); + constexpr int offset = Operands::Offset(op); + auto value = std::get(arguments_tuple); + // Special treatment for the first operand, as it might get packed with the + // bytecode. + if constexpr (index == 0) { + if constexpr (offset == 1) { + EmitPackedOperand(bytecode, value); + } else { + EmitBytecode(bytecode); + EmitOperand(value, offset); + } + } else { + EmitOperand(value, offset); + } + }); + EMIT_PADDING(Operands::kTotalSize); + DCHECK_EQ(pc_within_bc_, end_of_bc_); + pc_ += Operands::kTotalSize; +} + +namespace { + +// Helper to get the underlying type of an enum, or the type itself if it isn't +// an enum. +template +struct get_underlying_or_self { + using type = T; +}; + +template + requires std::is_enum_v +struct get_underlying_or_self { + using type = std::underlying_type_t; +}; + +} // namespace + +template +auto RegExpBytecodeGenerator::GetCheckedBasicOperandValue(T value) { + static_assert(RegExpOperandTypeTraits::kIsBasic); + using Traits = RegExpOperandTypeTraits; + using EnumOrCType = Traits::kCType; + using CType = get_underlying_or_self::type; + if constexpr (std::is_enum_v) { + static_assert(std::is_same_v); + } else { + static_assert(std::is_convertible_v); + } + DCHECK_GE(value, Traits::kMinValue); + DCHECK_LE(value, Traits::kMaxValue); + return static_cast(value); +} + +template +void RegExpBytecodeGenerator::EmitOperand(T value, int offset) { + Emit(GetCheckedBasicOperandValue(value), offset); +} + +template +void RegExpBytecodeGenerator::EmitPackedOperand(RegExpBytecode bytecode, + T value) { + using Traits = RegExpOperandTypeTraits; + static_assert(Traits::kSize <= 2); + EmitBytecode(bytecode, GetCheckedBasicOperandValue(value)); +} + +template <> +void RegExpBytecodeGenerator::EmitOperand(Label* label, + int offset) { + const int current_pc = pc_ + offset; + if (label == nullptr) label = &backtrack_; + int pos = 0; + if (label->is_bound()) { + pos = label->pos(); + jump_edges_.emplace(current_pc, pos); + } else { + if (label->is_linked()) { + pos = label->pos(); + } + label->link_to(current_pc); + } + Emit(pos, offset); +} + +template <> +void RegExpBytecodeGenerator::EmitOperand( + Handle table, int offset) { + for (int i = 0; i < kTableSize; i += kBitsPerByte) { + uint8_t byte = 0; + for (int j = 0; j < kBitsPerByte; j++) { + if (table->get(i + j) != 0) byte |= 1 << j; + } + Emit(byte, offset + i / kBitsPerByte); + } +} + void RegExpBytecodeGenerator::Bind(Label* l) { advance_current_end_ = kInvalidPC; DCHECK(!l->is_bound()); if (l->is_linked()) { int pos = l->pos(); @@ -42,353 +160,345 @@ } } l->bind_to(pc_); } -void RegExpBytecodeGenerator::EmitOrLink(Label* l) { - if (l == nullptr) l = &backtrack_; - int pos = 0; - if (l->is_bound()) { - pos = l->pos(); - jump_edges_.emplace(pc_, pos); - } else { - if (l->is_linked()) { - pos = l->pos(); - } - l->link_to(pc_); - } - Emit32(pos); -} - void RegExpBytecodeGenerator::PopRegister(int register_index) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_POP_REGISTER, register_index); + Emit(register_index); } void RegExpBytecodeGenerator::PushRegister(int register_index, StackCheckFlag check_stack_limit) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_PUSH_REGISTER, register_index); + // TODO(433891213): check_stack_limit was previously emitted as 32-bit, + // which normally would cause issues on big-endian. However only the + // interpreter and peephole optimization still use the old bytecode format and + // - the interpreter ignores this operand anyways. + // - peephole optimization is not enabled on big-endian platforms. + // So this is not an issue. + Emit(register_index, check_stack_limit); } void RegExpBytecodeGenerator::WriteCurrentPositionToRegister(int register_index, int cp_offset) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_SET_REGISTER_TO_CP, register_index); - Emit32(cp_offset); // Current position offset. + Emit(register_index, + cp_offset); } void RegExpBytecodeGenerator::ClearRegisters(int reg_from, int reg_to) { - DCHECK(reg_from <= reg_to); - for (int reg = reg_from; reg <= reg_to; reg++) { - SetRegister(reg, -1); - } + DCHECK_LE(reg_from, reg_to); + Emit(reg_from, reg_to); } void RegExpBytecodeGenerator::ReadCurrentPositionFromRegister( int register_index) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_SET_CP_TO_REGISTER, register_index); + Emit(register_index); } void RegExpBytecodeGenerator::WriteStackPointerToRegister(int register_index) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_SET_REGISTER_TO_SP, register_index); + Emit(register_index); } void RegExpBytecodeGenerator::ReadStackPointerFromRegister(int register_index) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_SET_SP_TO_REGISTER, register_index); + Emit(register_index); } void RegExpBytecodeGenerator::SetCurrentPositionFromEnd(int by) { - DCHECK(is_uint24(by)); - Emit(BC_SET_CURRENT_POSITION_FROM_END, by); + Emit(by); } void RegExpBytecodeGenerator::SetRegister(int register_index, int to) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_SET_REGISTER, register_index); - Emit32(to); + Emit(register_index, to); } void RegExpBytecodeGenerator::AdvanceRegister(int register_index, int by) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_ADVANCE_REGISTER, register_index); - Emit32(by); + Emit(register_index, by); } -void RegExpBytecodeGenerator::PopCurrentPosition() { Emit(BC_POP_CP, 0); } +void RegExpBytecodeGenerator::PopCurrentPosition() { + Emit(); +} -void RegExpBytecodeGenerator::PushCurrentPosition() { Emit(BC_PUSH_CP, 0); } +void RegExpBytecodeGenerator::PushCurrentPosition() { + Emit(); +} void RegExpBytecodeGenerator::Backtrack() { int error_code = can_fallback() ? RegExp::RE_FALLBACK_TO_EXPERIMENTAL : RegExp::RE_FAILURE; - Emit(BC_POP_BT, error_code); + Emit(error_code); } -void RegExpBytecodeGenerator::GoTo(Label* l) { +void RegExpBytecodeGenerator::GoTo(Label* label) { if (advance_current_end_ == pc_) { // Combine advance current and goto. - pc_ = advance_current_start_; - Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_); - EmitOrLink(l); + // TODO(pthier): Let peephole-optimization handle this case instead. + ResetPc(advance_current_start_); + Emit(advance_current_offset_, label); advance_current_end_ = kInvalidPC; } else { // Regular goto. - Emit(BC_GOTO, 0); - EmitOrLink(l); + Emit(label); } } -void RegExpBytecodeGenerator::PushBacktrack(Label* l) { - Emit(BC_PUSH_BT, 0); - EmitOrLink(l); +void RegExpBytecodeGenerator::PushBacktrack(Label* label) { + Emit(label); } bool RegExpBytecodeGenerator::Succeed() { - Emit(BC_SUCCEED, 0); + Emit(); return false; // Restart matching for global regexp not supported. } -void RegExpBytecodeGenerator::Fail() { Emit(BC_FAIL, 0); } +void RegExpBytecodeGenerator::Fail() { Emit(); } void RegExpBytecodeGenerator::AdvanceCurrentPosition(int by) { - // TODO(chromium:1166138): Turn back into DCHECKs once the underlying issue - // is fixed. - CHECK_LE(kMinCPOffset, by); - CHECK_GE(kMaxCPOffset, by); advance_current_start_ = pc_; advance_current_offset_ = by; - Emit(BC_ADVANCE_CP, by); + Emit(by); advance_current_end_ = pc_; } -void RegExpBytecodeGenerator::CheckGreedyLoop( +void RegExpBytecodeGenerator::CheckFixedLengthLoop( Label* on_tos_equals_current_position) { - Emit(BC_CHECK_GREEDY, 0); - EmitOrLink(on_tos_equals_current_position); + Emit(on_tos_equals_current_position); +} + +void RegExpBytecodeGenerator::CheckPosition(int cp_offset, + Label* on_outside_input) { + Emit(cp_offset, on_outside_input); +} + +void RegExpBytecodeGenerator::CheckSpecialClassRanges(StandardCharacterSet type, + Label* on_no_match) { + DCHECK(CanOptimizeSpecialClassRanges(type)); + Emit(type, on_no_match); } void RegExpBytecodeGenerator::LoadCurrentCharacterImpl(int cp_offset, Label* on_failure, bool check_bounds, int characters, int eats_at_least) { DCHECK_GE(eats_at_least, characters); if (eats_at_least > characters && check_bounds) { - DCHECK(is_int24(cp_offset + eats_at_least)); - Emit(BC_CHECK_CURRENT_POSITION, cp_offset + eats_at_least); - EmitOrLink(on_failure); + Emit(cp_offset + eats_at_least - 1, + on_failure); check_bounds = false; // Load below doesn't need to check. } - DCHECK_LE(kMinCPOffset, cp_offset); - DCHECK_GE(kMaxCPOffset, cp_offset); - int bytecode; + CHECK(base::IsInRange(cp_offset, kMinCPOffset, kMaxCPOffset)); if (check_bounds) { if (characters == 4) { - bytecode = BC_LOAD_4_CURRENT_CHARS; + Emit(cp_offset, on_failure); } else if (characters == 2) { - bytecode = BC_LOAD_2_CURRENT_CHARS; + Emit(cp_offset, on_failure); } else { DCHECK_EQ(1, characters); - bytecode = BC_LOAD_CURRENT_CHAR; + Emit(cp_offset, on_failure); } } else { if (characters == 4) { - bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED; + Emit(cp_offset); } else if (characters == 2) { - bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED; + Emit(cp_offset); } else { DCHECK_EQ(1, characters); - bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED; + Emit(cp_offset); } } - Emit(bytecode, cp_offset); - if (check_bounds) EmitOrLink(on_failure); } void RegExpBytecodeGenerator::CheckCharacterLT(base::uc16 limit, Label* on_less) { - Emit(BC_CHECK_LT, limit); - EmitOrLink(on_less); + Emit(limit, on_less); } void RegExpBytecodeGenerator::CheckCharacterGT(base::uc16 limit, Label* on_greater) { - Emit(BC_CHECK_GT, limit); - EmitOrLink(on_greater); + Emit(limit, on_greater); } void RegExpBytecodeGenerator::CheckCharacter(uint32_t c, Label* on_equal) { if (c > MAX_FIRST_ARG) { - Emit(BC_CHECK_4_CHARS, 0); - Emit32(c); + Emit(c, on_equal); } else { - Emit(BC_CHECK_CHAR, c); + Emit(c, on_equal); } - EmitOrLink(on_equal); } void RegExpBytecodeGenerator::CheckAtStart(int cp_offset, Label* on_at_start) { - Emit(BC_CHECK_AT_START, cp_offset); - EmitOrLink(on_at_start); + Emit(cp_offset, on_at_start); } void RegExpBytecodeGenerator::CheckNotAtStart(int cp_offset, Label* on_not_at_start) { - Emit(BC_CHECK_NOT_AT_START, cp_offset); - EmitOrLink(on_not_at_start); + Emit(cp_offset, on_not_at_start); } void RegExpBytecodeGenerator::CheckNotCharacter(uint32_t c, Label* on_not_equal) { if (c > MAX_FIRST_ARG) { - Emit(BC_CHECK_NOT_4_CHARS, 0); - Emit32(c); + Emit(c, on_not_equal); } else { - Emit(BC_CHECK_NOT_CHAR, c); + Emit(c, on_not_equal); } - EmitOrLink(on_not_equal); } void RegExpBytecodeGenerator::CheckCharacterAfterAnd(uint32_t c, uint32_t mask, Label* on_equal) { + // TOOD(pthier): This is super hacky. We could still check for 4 characters + // (with the last 2 being 0 after masking them), but not emit AndCheck4Chars. + // This is rather confusing and should be changed. if (c > MAX_FIRST_ARG) { - Emit(BC_AND_CHECK_4_CHARS, 0); - Emit32(c); + Emit(c, mask, on_equal); } else { - Emit(BC_AND_CHECK_CHAR, c); + Emit(c, mask, on_equal); } - Emit32(mask); - EmitOrLink(on_equal); } void RegExpBytecodeGenerator::CheckNotCharacterAfterAnd(uint32_t c, uint32_t mask, Label* on_not_equal) { + // TOOD(pthier): This is super hacky. We could still check for 4 characters + // (with the last 2 being 0 after masking them), but not emit AndCheck4Chars. + // This is rather confusing and should be changed. if (c > MAX_FIRST_ARG) { - Emit(BC_AND_CHECK_NOT_4_CHARS, 0); - Emit32(c); + Emit(c, mask, on_not_equal); } else { - Emit(BC_AND_CHECK_NOT_CHAR, c); + Emit(c, mask, on_not_equal); } - Emit32(mask); - EmitOrLink(on_not_equal); } void RegExpBytecodeGenerator::CheckNotCharacterAfterMinusAnd( base::uc16 c, base::uc16 minus, base::uc16 mask, Label* on_not_equal) { - Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c); - Emit16(minus); - Emit16(mask); - EmitOrLink(on_not_equal); + Emit(c, minus, mask, + on_not_equal); } void RegExpBytecodeGenerator::CheckCharacterInRange(base::uc16 from, base::uc16 to, Label* on_in_range) { - Emit(BC_CHECK_CHAR_IN_RANGE, 0); - Emit16(from); - Emit16(to); - EmitOrLink(on_in_range); + Emit(from, to, on_in_range); } void RegExpBytecodeGenerator::CheckCharacterNotInRange(base::uc16 from, base::uc16 to, Label* on_not_in_range) { - Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0); - Emit16(from); - Emit16(to); - EmitOrLink(on_not_in_range); -} - -void RegExpBytecodeGenerator::EmitSkipTable(DirectHandle table) { - for (int i = 0; i < kTableSize; i += kBitsPerByte) { - int byte = 0; - for (int j = 0; j < kBitsPerByte; j++) { - if (table->get(i + j) != 0) byte |= 1 << j; - } - Emit8(byte); - } + Emit(from, to, on_not_in_range); } void RegExpBytecodeGenerator::CheckBitInTable(Handle table, Label* on_bit_set) { - Emit(BC_CHECK_BIT_IN_TABLE, 0); - EmitOrLink(on_bit_set); - EmitSkipTable(table); + Emit(on_bit_set, table); } void RegExpBytecodeGenerator::SkipUntilBitInTable( int cp_offset, Handle table, Handle nibble_table, - int advance_by) { - Label cont; - Emit(BC_SKIP_UNTIL_BIT_IN_TABLE, cp_offset); - Emit32(advance_by); - EmitSkipTable(table); - EmitOrLink(&cont); // goto_when_match - EmitOrLink(&cont); // goto_on_failure - Bind(&cont); + int advance_by, Label* on_match, Label* on_no_match) { + Emit(cp_offset, advance_by, table, + on_match, on_no_match); +} + +void RegExpBytecodeGenerator::SkipUntilCharAnd(int cp_offset, int advance_by, + unsigned character, + unsigned mask, int eats_at_least, + Label* on_match, + Label* on_no_match) { + Emit(cp_offset, advance_by, character, + mask, eats_at_least, on_match, + on_no_match); +} + +void RegExpBytecodeGenerator::SkipUntilChar(int cp_offset, int advance_by, + unsigned character, Label* on_match, + Label* on_no_match) { + // Only generated by peephole optimization. + UNREACHABLE(); +} + +void RegExpBytecodeGenerator::SkipUntilCharPosChecked( + int cp_offset, int advance_by, unsigned character, int eats_at_least, + Label* on_match, Label* on_no_match) { + // Only generated by peephole optimization. + UNREACHABLE(); +} + +void RegExpBytecodeGenerator::SkipUntilCharOrChar(int cp_offset, int advance_by, + unsigned char1, + unsigned char2, + Label* on_match, + Label* on_no_match) { + // Only generated by peephole optimization. + UNREACHABLE(); +} + +void RegExpBytecodeGenerator::SkipUntilGtOrNotBitInTable( + int cp_offset, int advance_by, unsigned character, Handle table, + Label* on_match, Label* on_no_match) { + // Only generated by peephole optimization. + UNREACHABLE(); +} + +void RegExpBytecodeGenerator::SkipUntilOneOfMasked( + int cp_offset, int advance_by, unsigned both_chars, unsigned both_mask, + int max_offset, unsigned chars1, unsigned mask1, unsigned chars2, + unsigned mask2, Label* on_match1, Label* on_match2, Label* on_failure) { + // Only generated by peephole optimization. + UNREACHABLE(); +} + +void RegExpBytecodeGenerator::SkipUntilOneOfMasked3( + const SkipUntilOneOfMasked3Args& args) { + // Only generated by peephole optimization. + UNREACHABLE(); } void RegExpBytecodeGenerator::CheckNotBackReference(int start_reg, bool read_backward, Label* on_not_equal) { - DCHECK_LE(0, start_reg); - DCHECK_GE(kMaxRegister, start_reg); - Emit(read_backward ? BC_CHECK_NOT_BACK_REF_BACKWARD : BC_CHECK_NOT_BACK_REF, - start_reg); - EmitOrLink(on_not_equal); + if (read_backward) { + Emit(start_reg, on_not_equal); + } else { + Emit(start_reg, on_not_equal); + } } void RegExpBytecodeGenerator::CheckNotBackReferenceIgnoreCase( int start_reg, bool read_backward, bool unicode, Label* on_not_equal) { - DCHECK_LE(0, start_reg); - DCHECK_GE(kMaxRegister, start_reg); - Emit(read_backward ? (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE_BACKWARD - : BC_CHECK_NOT_BACK_REF_NO_CASE_BACKWARD) - : (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE - : BC_CHECK_NOT_BACK_REF_NO_CASE), - start_reg); - EmitOrLink(on_not_equal); + if (read_backward) { + if (unicode) { + Emit(start_reg, + on_not_equal); + } else { + Emit(start_reg, + on_not_equal); + } + } else { + if (unicode) { + Emit(start_reg, + on_not_equal); + } else { + Emit(start_reg, on_not_equal); + } + } } void RegExpBytecodeGenerator::IfRegisterLT(int register_index, int comparand, Label* on_less_than) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_CHECK_REGISTER_LT, register_index); - Emit32(comparand); - EmitOrLink(on_less_than); + Emit(register_index, comparand, on_less_than); } void RegExpBytecodeGenerator::IfRegisterGE(int register_index, int comparand, Label* on_greater_or_equal) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_CHECK_REGISTER_GE, register_index); - Emit32(comparand); - EmitOrLink(on_greater_or_equal); + Emit(register_index, comparand, + on_greater_or_equal); } void RegExpBytecodeGenerator::IfRegisterEqPos(int register_index, - Label* on_eq) { - DCHECK_LE(0, register_index); - DCHECK_GE(kMaxRegister, register_index); - Emit(BC_CHECK_REGISTER_EQ_POS, register_index); - EmitOrLink(on_eq); + Label* on_equal) { + Emit(register_index, on_equal); } DirectHandle RegExpBytecodeGenerator::GetCode( DirectHandle source, RegExpFlags flags) { Bind(&backtrack_); diff --git a/js/src/irregexp/imported/regexp-bytecode-iterator-inl.h b/js/src/irregexp/imported/regexp-bytecode-iterator-inl.h new file mode 100644 --- /dev/null +++ b/js/src/irregexp/imported/regexp-bytecode-iterator-inl.h @@ -0,0 +1,52 @@ +// Copyright 2025 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_ITERATOR_INL_H_ +#define V8_REGEXP_REGEXP_BYTECODE_ITERATOR_INL_H_ + +#include "irregexp/imported/regexp-bytecode-iterator.h" +// Include the non-inl header before the rest of the headers. + +#include "irregexp/imported/regexp-bytecodes-inl.h" + +namespace v8 { +namespace internal { + +bool RegExpBytecodeIterator::done() const { return cursor_ >= end_; } + +void RegExpBytecodeIterator::advance() { + DCHECK(!done()); + cursor_ += current_size(); +} + +RegExpBytecode RegExpBytecodeIterator::current_bytecode() const { + DCHECK(!done()); + DCHECK_LE(cursor_ + sizeof(uint32_t), end_); + return RegExpBytecodes::FromPtr(cursor_); +} + +uint8_t RegExpBytecodeIterator::current_size() const { + DCHECK(!done()); + return RegExpBytecodes::Size(current_bytecode()); +} + +int RegExpBytecodeIterator::current_offset() const { + return static_cast(cursor_ - start_); +} + +uint8_t* RegExpBytecodeIterator::current_address() const { return cursor_; } + +void RegExpBytecodeIterator::reset() { cursor_ = start_; } + +template +void RegExpBytecodeIterator::ForEachBytecode(Func&& fun) { + for (; !done(); advance()) { + RegExpBytecodes::DispatchOnBytecode(current_bytecode(), fun); + } +} + +} // namespace internal +} // namespace v8 + +#endif // V8_REGEXP_REGEXP_BYTECODE_ITERATOR_INL_H_ diff --git a/js/src/irregexp/imported/regexp-bytecode-iterator.h b/js/src/irregexp/imported/regexp-bytecode-iterator.h new file mode 100644 --- /dev/null +++ b/js/src/irregexp/imported/regexp-bytecode-iterator.h @@ -0,0 +1,49 @@ +// Copyright 2025 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_ITERATOR_H_ +#define V8_REGEXP_REGEXP_BYTECODE_ITERATOR_H_ + +#include + +#include "irregexp/imported/regexp-bytecodes.h" + +namespace v8 { +namespace internal { + +class TrustedByteArray; + +class RegExpBytecodeIterator { + public: + explicit RegExpBytecodeIterator(DirectHandle bytecode); + ~RegExpBytecodeIterator(); + + inline bool done() const; + inline void advance(); + inline RegExpBytecode current_bytecode() const; + inline uint8_t current_size() const; + inline int current_offset() const; + inline uint8_t* current_address() const; + inline void reset(); + + // Calls |fun| templatized by RegExpBytecode for each bytecode in the + // Bytecode Array. + template + inline void ForEachBytecode(Func&& fun); + + static void UpdatePointersCallback(void* iterator); + + private: + void UpdatePointers(); + + DirectHandle bytecode_; + uint8_t* start_; + uint8_t* end_; + uint8_t* cursor_; +}; + +} // namespace internal +} // namespace v8 + +#endif // V8_REGEXP_REGEXP_BYTECODE_ITERATOR_H_ diff --git a/js/src/irregexp/imported/regexp-bytecode-iterator.cc b/js/src/irregexp/imported/regexp-bytecode-iterator.cc new file mode 100644 --- /dev/null +++ b/js/src/irregexp/imported/regexp-bytecode-iterator.cc @@ -0,0 +1,46 @@ +// Copyright 2025 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 "irregexp/imported/regexp-bytecode-iterator.h" + +#include "irregexp/imported/regexp-bytecode-iterator-inl.h" +#include "irregexp/imported/regexp-bytecodes-inl.h" + +namespace v8 { +namespace internal { + +RegExpBytecodeIterator::RegExpBytecodeIterator( + DirectHandle bytecode) + : bytecode_(bytecode), + start_(bytecode->begin()), + end_(bytecode->end()), + cursor_(start_) { + Isolate::Current()->main_thread_local_heap()->AddGCEpilogueCallback( + UpdatePointersCallback, this); +} + +RegExpBytecodeIterator::~RegExpBytecodeIterator() { + Isolate::Current()->main_thread_local_heap()->RemoveGCEpilogueCallback( + UpdatePointersCallback, this); +} + +// static +void RegExpBytecodeIterator::UpdatePointersCallback(void* iterator) { + reinterpret_cast(iterator)->UpdatePointers(); +} + +void RegExpBytecodeIterator::UpdatePointers() { + DisallowGarbageCollection no_gc; + uint8_t* start = bytecode_->begin(); + if (start != start_) { + start_ = start; + uint8_t* end = bytecode_->end(); + size_t distance_to_end = end_ - cursor_; + cursor_ = end - distance_to_end; + end_ = end; + } +} + +} // namespace internal +} // namespace v8 diff --git a/js/src/irregexp/imported/regexp-bytecode-peephole.cc b/js/src/irregexp/imported/regexp-bytecode-peephole.cc --- a/js/src/irregexp/imported/regexp-bytecode-peephole.cc +++ b/js/src/irregexp/imported/regexp-bytecode-peephole.cc @@ -2,32 +2,66 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "irregexp/imported/regexp-bytecode-peephole.h" +#include + +#include "irregexp/imported/regexp-bytecodes-inl.h" #include "irregexp/imported/regexp-bytecodes.h" namespace v8 { namespace internal { namespace { -struct BytecodeArgument { - int offset; - int length; +class BytecodeArgument { + public: + BytecodeArgument(int offset, int length) : offset_(offset), length_(length) {} - BytecodeArgument(int offset, int length) : offset(offset), length(length) {} + int offset() const { return offset_; } + int length() const { return length_; } + + private: + int offset_; + int length_; }; -struct BytecodeArgumentMapping : BytecodeArgument { - int new_length; +class BytecodeArgumentMapping : public BytecodeArgument { + public: + enum class Type : uint8_t { kDefault, kSpecial }; + enum class SpecialType : uint8_t { kOffsetAfterSequence }; BytecodeArgumentMapping(int offset, int length, int new_length) - : BytecodeArgument(offset, length), new_length(new_length) {} + : BytecodeArgument(offset, length), + type_(Type::kDefault), + value_{.new_length = new_length} {} + + explicit BytecodeArgumentMapping(SpecialType special_type) + : BytecodeArgument(-1, -1), + type_(Type::kSpecial), + value_{.special_type = special_type} {} + + Type type() const { return type_; } + int new_length() const { + DCHECK_EQ(type(), Type::kDefault); + return value_.new_length; + } + SpecialType special_type() const { + DCHECK_EQ(type(), Type::kSpecial); + return value_.special_type; + } + + private: + Type type_; + union { + int new_length; + SpecialType special_type; + } value_; }; -struct BytecodeArgumentCheck : BytecodeArgument { +struct BytecodeArgumentCheck : public BytecodeArgument { enum CheckType { kCheckAddress = 0, kCheckValue }; CheckType type; int check_offset; int check_length; @@ -44,20 +78,16 @@ }; // Trie-Node for storing bytecode sequences we want to optimize. class BytecodeSequenceNode { public: - // Dummy bytecode used when we need to store/return a bytecode but it's not a - // valid bytecode in the current context. - static constexpr int kDummyBytecode = -1; - - BytecodeSequenceNode(int bytecode, Zone* zone); + BytecodeSequenceNode(std::optional bytecode, Zone* zone); // Adds a new node as child of the current node if it isn't a child already. - BytecodeSequenceNode& FollowedBy(int bytecode); + BytecodeSequenceNode& FollowedBy(RegExpBytecode bytecode); // Marks the end of a sequence and sets optimized bytecode to replace all // bytecodes of the sequence with. - BytecodeSequenceNode& ReplaceWith(int bytecode); + BytecodeSequenceNode& ReplaceWith(RegExpBytecode bytecode); // Maps arguments of bytecodes in the sequence to the optimized bytecode. // Order of invocation determines order of arguments in the optimized // bytecode. // Invoking this method is only allowed on nodes that mark the end of a valid // sequence (i.e. after ReplaceWith()). @@ -71,10 +101,17 @@ // (= argument_byte_length if omitted). BytecodeSequenceNode& MapArgument(int bytecode_index_in_sequence, int argument_offset, int argument_byte_length, int new_argument_byte_length = 0); + // Emits the offset after the whole sequence. + // This should be used for every sequence that doesn't end in an unconditional + // jump. The offset isn't statically known, as bytecodes might be preserved + // after the sequence if they were jump targets from bytecodes outside the + // sequence. The emitted offset is after these potentially preserved + // bytecodes. + BytecodeSequenceNode& EmitOffsetAfterSequence(); // Adds a check to the sequence node making it only a valid sequence when the // argument of the current bytecode at the specified offset matches the offset // to check against. // argument_offset: Zero-based offset to the argument within the bytecode // (e.g. the first argument that's not packed with the bytecode has offset 4). @@ -113,16 +150,15 @@ // Returns whether this node marks the end of a valid sequence (i.e. can be // replaced with an optimized bytecode). bool IsSequence() const; // Returns the length of the sequence in bytes. int SequenceLength() const; - // Returns the optimized bytecode for the node or kDummyBytecode if it is not - // the end of a valid sequence. - int OptimizedBytecode() const; + // Returns the optimized bytecode for the node. + RegExpBytecode OptimizedBytecode() const; // Returns the child of the current node matching the given bytecode or // nullptr if no such child is found. - BytecodeSequenceNode* Find(int bytecode) const; + BytecodeSequenceNode* Find(RegExpBytecode bytecode) const; // Returns number of arguments mapped to the current node. // Invoking this method is only allowed on nodes that mark the end of a valid // sequence (i.e. if IsSequence()) size_t ArgumentSize() const; // Returns the argument-mapping of the argument at index. @@ -143,27 +179,23 @@ private: // Returns a node in the sequence specified by its index within the sequence. BytecodeSequenceNode& GetNodeByIndexInSequence(int index_in_sequence); Zone* zone() const; - int bytecode_; - int bytecode_replacement_; + std::optional bytecode_; + std::optional bytecode_replacement_; int index_in_sequence_; int start_offset_; BytecodeSequenceNode* parent_; - ZoneUnorderedMap children_; + ZoneUnorderedMap children_; ZoneVector* argument_mapping_; ZoneLinkedList* argument_check_; ZoneLinkedList* argument_ignored_; Zone* zone_; }; -// These definitions are here in order to please the linker, which in debug mode -// sometimes requires static constants to be defined in .cc files. -constexpr int BytecodeSequenceNode::kDummyBytecode; - class RegExpBytecodePeephole { public: RegExpBytecodePeephole(Zone* zone, size_t buffer_size, const ZoneUnorderedMap& jump_edges); @@ -178,11 +210,11 @@ private: // Sets up all sequences that are going to be used. void DefineStandardSequences(); // Starts a new bytecode sequence. - BytecodeSequenceNode& CreateSequence(int bytecode); + BytecodeSequenceNode& CreateSequence(RegExpBytecode bytecode); // Checks for optimization candidates at pc and emits optimized bytecode to // the internal buffer. Returns the length of replaced bytecodes in bytes. int TryOptimizeSequence(const uint8_t* bytecode, int bytecode_length, int start_pc); // Emits optimized bytecode to the internal buffer. start_pc points to the @@ -265,43 +297,43 @@ default: UNREACHABLE(); } } -BytecodeSequenceNode::BytecodeSequenceNode(int bytecode, Zone* zone) +BytecodeSequenceNode::BytecodeSequenceNode( + std::optional bytecode, Zone* zone) : bytecode_(bytecode), - bytecode_replacement_(kDummyBytecode), + bytecode_replacement_(std::nullopt), index_in_sequence_(0), start_offset_(0), parent_(nullptr), - children_(ZoneUnorderedMap(zone)), + children_(ZoneUnorderedMap(zone)), argument_mapping_(zone->New>(zone)), argument_check_(zone->New>(zone)), argument_ignored_(zone->New>(zone)), zone_(zone) {} -BytecodeSequenceNode& BytecodeSequenceNode::FollowedBy(int bytecode) { - DCHECK(0 <= bytecode && bytecode < kRegExpBytecodeCount); - +BytecodeSequenceNode& BytecodeSequenceNode::FollowedBy( + RegExpBytecode bytecode) { if (children_.find(bytecode) == children_.end()) { BytecodeSequenceNode* new_node = zone()->New(bytecode, zone()); // If node is not the first in the sequence, set offsets and parent. - if (bytecode_ != kDummyBytecode) { - new_node->start_offset_ = start_offset_ + RegExpBytecodeLength(bytecode_); + if (bytecode_.has_value()) { + new_node->start_offset_ = + start_offset_ + RegExpBytecodes::Size(bytecode_.value()); new_node->index_in_sequence_ = index_in_sequence_ + 1; new_node->parent_ = this; } children_[bytecode] = new_node; } return *children_[bytecode]; } -BytecodeSequenceNode& BytecodeSequenceNode::ReplaceWith(int bytecode) { - DCHECK(0 <= bytecode && bytecode < kRegExpBytecodeCount); - +BytecodeSequenceNode& BytecodeSequenceNode::ReplaceWith( + RegExpBytecode bytecode) { bytecode_replacement_ = bytecode; return *this; } @@ -311,11 +343,11 @@ DCHECK(IsSequence()); DCHECK_LE(bytecode_index_in_sequence, index_in_sequence_); BytecodeSequenceNode& ref_node = GetNodeByIndexInSequence(bytecode_index_in_sequence); - DCHECK_LT(argument_offset, RegExpBytecodeLength(ref_node.bytecode_)); + DCHECK_LT(argument_offset, RegExpBytecodes::Size(ref_node.bytecode_.value())); int absolute_offset = ref_node.start_offset_ + argument_offset; if (new_argument_byte_length == 0) { new_argument_byte_length = argument_byte_length; } @@ -324,13 +356,20 @@ absolute_offset, argument_byte_length, new_argument_byte_length}); return *this; } +BytecodeSequenceNode& BytecodeSequenceNode::EmitOffsetAfterSequence() { + DCHECK(IsSequence()); + argument_mapping_->push_back(BytecodeArgumentMapping{ + BytecodeArgumentMapping::SpecialType::kOffsetAfterSequence}); + return *this; +} + BytecodeSequenceNode& BytecodeSequenceNode::IfArgumentEqualsOffset( int argument_offset, int argument_byte_length, int check_byte_offset) { - DCHECK_LT(argument_offset, RegExpBytecodeLength(bytecode_)); + DCHECK_LT(argument_offset, RegExpBytecodes::Size(bytecode_.value())); DCHECK(argument_byte_length == 1 || argument_byte_length == 2 || argument_byte_length == 4); int absolute_offset = start_offset_ + argument_offset; @@ -342,17 +381,18 @@ BytecodeSequenceNode& BytecodeSequenceNode::IfArgumentEqualsValueAtOffset( int argument_offset, int argument_byte_length, int other_bytecode_index_in_sequence, int other_argument_offset, int other_argument_byte_length) { - DCHECK_LT(argument_offset, RegExpBytecodeLength(bytecode_)); + DCHECK_LT(argument_offset, RegExpBytecodes::Size(bytecode_.value())); DCHECK_LE(other_bytecode_index_in_sequence, index_in_sequence_); DCHECK_EQ(argument_byte_length, other_argument_byte_length); BytecodeSequenceNode& ref_node = GetNodeByIndexInSequence(other_bytecode_index_in_sequence); - DCHECK_LT(other_argument_offset, RegExpBytecodeLength(ref_node.bytecode_)); + DCHECK_LT(other_argument_offset, + RegExpBytecodes::Size(ref_node.bytecode_.value())); int absolute_offset = start_offset_ + argument_offset; int other_absolute_offset = ref_node.start_offset_ + other_argument_offset; argument_check_->push_back( @@ -368,11 +408,11 @@ DCHECK(IsSequence()); DCHECK_LE(bytecode_index_in_sequence, index_in_sequence_); BytecodeSequenceNode& ref_node = GetNodeByIndexInSequence(bytecode_index_in_sequence); - DCHECK_LT(argument_offset, RegExpBytecodeLength(ref_node.bytecode_)); + DCHECK_LT(argument_offset, RegExpBytecodes::Size(ref_node.bytecode_.value())); int absolute_offset = ref_node.start_offset_ + argument_offset; argument_ignored_->push_back( BytecodeArgument{absolute_offset, argument_byte_length}); @@ -382,12 +422,12 @@ bool BytecodeSequenceNode::CheckArguments(const uint8_t* bytecode, int pc) { bool is_valid = true; for (auto check_iter = argument_check_->begin(); check_iter != argument_check_->end() && is_valid; check_iter++) { - auto value = - GetArgumentValue(bytecode, pc + check_iter->offset, check_iter->length); + auto value = GetArgumentValue(bytecode, pc + check_iter->offset(), + check_iter->length()); if (check_iter->type == BytecodeArgumentCheck::kCheckAddress) { is_valid &= value == pc + check_iter->check_offset; } else if (check_iter->type == BytecodeArgumentCheck::kCheckValue) { auto other_value = GetArgumentValue( bytecode, pc + check_iter->check_offset, check_iter->check_length); @@ -398,22 +438,23 @@ } return is_valid; } bool BytecodeSequenceNode::IsSequence() const { - return bytecode_replacement_ != kDummyBytecode; + return bytecode_replacement_.has_value(); } int BytecodeSequenceNode::SequenceLength() const { - return start_offset_ + RegExpBytecodeLength(bytecode_); + return start_offset_ + RegExpBytecodes::Size(bytecode_.value()); } -int BytecodeSequenceNode::OptimizedBytecode() const { - return bytecode_replacement_; +RegExpBytecode BytecodeSequenceNode::OptimizedBytecode() const { + return bytecode_replacement_.value(); } -BytecodeSequenceNode* BytecodeSequenceNode::Find(int bytecode) const { +BytecodeSequenceNode* BytecodeSequenceNode::Find( + RegExpBytecode bytecode) const { auto found = children_.find(bytecode); if (found == children_.end()) return nullptr; return found->second; } @@ -465,12 +506,11 @@ RegExpBytecodePeephole::RegExpBytecodePeephole( Zone* zone, size_t buffer_size, const ZoneUnorderedMap& jump_edges) : optimized_bytecode_buffer_(zone), - sequences_(zone->New( - BytecodeSequenceNode::kDummyBytecode, zone)), + sequences_(zone->New(std::nullopt, zone)), jump_edges_(zone), jump_edges_mapped_(zone), jump_usage_counts_(zone), jump_source_fixups_(zone), jump_destination_fixups_(zone), @@ -490,126 +530,330 @@ DCHECK_LE(buffer_size, std::numeric_limits::max()); AddSentinelFixups(static_cast(buffer_size)); } void RegExpBytecodePeephole::DefineStandardSequences() { + using B = RegExpBytecode; + + // TODO(jgruber): These macros are porting crutches and will be removed asap. +#define OPERAND_OFFSET(BYTECODE, OPERAND) \ + RegExpBytecodeOperands::Offset( \ + RegExpBytecodeOperands::Operand::OPERAND) + // For size, we distinguish between the native type size, and the "packed" + // size, i.e. 3 if the operand is packed. + // TODO(jgruber): Remove this once unaligned packing is gone. +#define OPERAND_SIZE(BYTECODE, OPERAND) \ + RegExpBytecodeOperands::Size( \ + RegExpBytecodeOperands::Operand::OPERAND) +#define OPERAND_SIZE_PACKED(BYTECODE, OPERAND) \ + (OPERAND_OFFSET(BYTECODE, OPERAND) == 1 ? 3 : OPERAND_SIZE(BYTECODE, OPERAND)) + // Shorthands: + // "OS": Offset and size. + // "OSN": Offset, size, new_size. +#define OS(BYTECODE, OPERAND) \ + OPERAND_OFFSET(BYTECODE, OPERAND), OPERAND_SIZE(BYTECODE, OPERAND) +#define OS_PACKED(BYTECODE, OPERAND) \ + OPERAND_OFFSET(BYTECODE, OPERAND), OPERAND_SIZE_PACKED(BYTECODE, OPERAND) + // The first mapped operand currently preserves unaligned packing. + // TODO(jgruber): Remove this once unaligned packing is gone. +#define OSN_FIRST(BYTECODE, OPERAND) \ + OS_PACKED(BYTECODE, OPERAND), OPERAND_SIZE_PACKED(BYTECODE, OPERAND) +#define OSN(BYTECODE, OPERAND) \ + OS_PACKED(BYTECODE, OPERAND), OPERAND_SIZE(BYTECODE, OPERAND) + // Commonly used sequences can be found by creating regexp bytecode traces // (--trace-regexp-bytecodes) and using v8/tools/regexp-sequences.py. - CreateSequence(BC_LOAD_CURRENT_CHAR) - .FollowedBy(BC_CHECK_BIT_IN_TABLE) - .FollowedBy(BC_ADVANCE_CP_AND_GOTO) - // Sequence is only valid if the jump target of ADVANCE_CP_AND_GOTO is the + + CreateSequence(B::kLoadCurrentCharacter) + .FollowedBy(B::kCheckBitInTable) + .FollowedBy(B::kAdvanceCpAndGoto) + // Sequence is only valid if the jump target of AdvanceCpAndGoto is the // first bytecode in this sequence. - .IfArgumentEqualsOffset(4, 4, 0) - .ReplaceWith(BC_SKIP_UNTIL_BIT_IN_TABLE) - .MapArgument(0, 1, 3) // load offset - .MapArgument(2, 1, 3, 4) // advance by - .MapArgument(1, 8, 16) // bit table - .MapArgument(1, 4, 4) // goto when match - .MapArgument(0, 4, 4) // goto on failure - .IgnoreArgument(2, 4, 4); // loop jump + .IfArgumentEqualsOffset(OS(B::kAdvanceCpAndGoto, on_goto), 0) + .ReplaceWith(B::kSkipUntilBitInTable) + .MapArgument(0, OSN_FIRST(B::kLoadCurrentCharacter, cp_offset)) + // TODO(jgruber): Remove manual alignment once possible. + .MapArgument(2, OS_PACKED(B::kAdvanceCpAndGoto, by), 4) + .MapArgument(1, OSN(B::kCheckBitInTable, table)) + .MapArgument(1, OSN(B::kCheckBitInTable, on_bit_set)) + .MapArgument(0, OSN(B::kLoadCurrentCharacter, on_failure)) + .IgnoreArgument(2, OS(B::kAdvanceCpAndGoto, on_goto)); - CreateSequence(BC_CHECK_CURRENT_POSITION) - .FollowedBy(BC_LOAD_CURRENT_CHAR_UNCHECKED) - .FollowedBy(BC_CHECK_CHAR) - .FollowedBy(BC_ADVANCE_CP_AND_GOTO) - // Sequence is only valid if the jump target of ADVANCE_CP_AND_GOTO is the + CreateSequence(B::kCheckPosition) + .FollowedBy(B::kLoadCurrentCharacterUnchecked) + .FollowedBy(B::kCheckCharacter) + .FollowedBy(B::kAdvanceCpAndGoto) + // Sequence is only valid if the jump target of AdvanceCpAndGoto is the // first bytecode in this sequence. - .IfArgumentEqualsOffset(4, 4, 0) - .ReplaceWith(BC_SKIP_UNTIL_CHAR_POS_CHECKED) - .MapArgument(1, 1, 3) // load offset - .MapArgument(3, 1, 3, 2) // advance_by - .MapArgument(2, 1, 3, 2) // c - .MapArgument(0, 1, 3, 4) // eats at least - .MapArgument(2, 4, 4) // goto when match - .MapArgument(0, 4, 4) // goto on failure - .IgnoreArgument(3, 4, 4); // loop jump + .IfArgumentEqualsOffset(OS(B::kAdvanceCpAndGoto, on_goto), 0) + .ReplaceWith(B::kSkipUntilCharPosChecked) + .MapArgument(1, OSN_FIRST(B::kLoadCurrentCharacterUnchecked, cp_offset)) + .MapArgument(3, OSN(B::kAdvanceCpAndGoto, by)) + .MapArgument(2, OSN(B::kCheckCharacter, character)) + // eats at least + // TODO(jgruber): Remove manual alignment once possible. + .MapArgument(0, OS_PACKED(B::kCheckPosition, cp_offset), 4) + .MapArgument(2, OSN(B::kCheckCharacter, on_equal)) + .MapArgument(0, OSN(B::kCheckPosition, on_failure)) + .IgnoreArgument(3, OS(B::kAdvanceCpAndGoto, on_goto)); - CreateSequence(BC_CHECK_CURRENT_POSITION) - .FollowedBy(BC_LOAD_CURRENT_CHAR_UNCHECKED) - .FollowedBy(BC_AND_CHECK_CHAR) - .FollowedBy(BC_ADVANCE_CP_AND_GOTO) - // Sequence is only valid if the jump target of ADVANCE_CP_AND_GOTO is the + CreateSequence(B::kCheckPosition) + .FollowedBy(B::kLoadCurrentCharacterUnchecked) + .FollowedBy(B::kCheckCharacterAfterAnd) + .FollowedBy(B::kAdvanceCpAndGoto) + // Sequence is only valid if the jump target of AdvanceCpAndGoto is the // first bytecode in this sequence. - .IfArgumentEqualsOffset(4, 4, 0) - .ReplaceWith(BC_SKIP_UNTIL_CHAR_AND) - .MapArgument(1, 1, 3) // load offset - .MapArgument(3, 1, 3, 2) // advance_by - .MapArgument(2, 1, 3, 2) // c - .MapArgument(2, 4, 4) // mask - .MapArgument(0, 1, 3, 4) // eats at least - .MapArgument(2, 8, 4) // goto when match - .MapArgument(0, 4, 4) // goto on failure - .IgnoreArgument(3, 4, 4); // loop jump + .IfArgumentEqualsOffset(OS(B::kAdvanceCpAndGoto, on_goto), 0) + .ReplaceWith(B::kSkipUntilCharAnd) + .MapArgument(1, OSN_FIRST(B::kLoadCurrentCharacterUnchecked, cp_offset)) + .MapArgument(3, OSN(B::kAdvanceCpAndGoto, by)) + .MapArgument(2, OSN(B::kCheckCharacterAfterAnd, character)) + .MapArgument(2, OSN(B::kCheckCharacterAfterAnd, mask)) + // eats at least + // TODO(jgruber): Remove manual alignment once possible. + .MapArgument(0, OS_PACKED(B::kCheckPosition, cp_offset), 4) + .MapArgument(2, OSN(B::kCheckCharacterAfterAnd, on_equal)) + .MapArgument(0, OSN(B::kCheckPosition, on_failure)) + .IgnoreArgument(3, OS(B::kAdvanceCpAndGoto, on_goto)); // TODO(pthier): It might make sense for short sequences like this one to only // optimize them if the resulting optimization is not longer than the current // one. This could be the case if there are jumps inside the sequence and we // have to replicate parts of the sequence. A method to mark such sequences // might be useful. - CreateSequence(BC_LOAD_CURRENT_CHAR) - .FollowedBy(BC_CHECK_CHAR) - .FollowedBy(BC_ADVANCE_CP_AND_GOTO) - // Sequence is only valid if the jump target of ADVANCE_CP_AND_GOTO is the + CreateSequence(B::kLoadCurrentCharacter) + .FollowedBy(B::kCheckCharacter) + .FollowedBy(B::kAdvanceCpAndGoto) + // Sequence is only valid if the jump target of AdvanceCpAndGoto is the + // first bytecode in this sequence. + .IfArgumentEqualsOffset(OS(B::kAdvanceCpAndGoto, on_goto), 0) + .ReplaceWith(B::kSkipUntilChar) + .MapArgument(0, OSN_FIRST(B::kLoadCurrentCharacter, cp_offset)) + .MapArgument(2, OSN(B::kAdvanceCpAndGoto, by)) + .MapArgument(1, OSN(B::kCheckCharacter, character)) + .MapArgument(1, OSN(B::kCheckCharacter, on_equal)) + .MapArgument(0, OSN(B::kLoadCurrentCharacter, on_failure)) + .IgnoreArgument(2, OS(B::kAdvanceCpAndGoto, on_goto)); + + CreateSequence(B::kLoadCurrentCharacter) + .FollowedBy(B::kCheckCharacter) + .FollowedBy(B::kCheckCharacter) + // Sequence is only valid if the jump targets of both CheckCharacter + // bytecodes are equal. + .IfArgumentEqualsValueAtOffset(4, 4, 1, 4, 4) + .FollowedBy(B::kAdvanceCpAndGoto) + // Sequence is only valid if the jump target of AdvanceCpAndGoto is the // first bytecode in this sequence. .IfArgumentEqualsOffset(4, 4, 0) - .ReplaceWith(BC_SKIP_UNTIL_CHAR) - .MapArgument(0, 1, 3) // load offset - .MapArgument(2, 1, 3, 2) // advance by - .MapArgument(1, 1, 3, 2) // character - .MapArgument(1, 4, 4) // goto when match - .MapArgument(0, 4, 4) // goto on failure - .IgnoreArgument(2, 4, 4); // loop jump - - CreateSequence(BC_LOAD_CURRENT_CHAR) - .FollowedBy(BC_CHECK_CHAR) - .FollowedBy(BC_CHECK_CHAR) - // Sequence is only valid if the jump targets of both CHECK_CHAR bytecodes - // are equal. - .IfArgumentEqualsValueAtOffset(4, 4, 1, 4, 4) - .FollowedBy(BC_ADVANCE_CP_AND_GOTO) - // Sequence is only valid if the jump target of ADVANCE_CP_AND_GOTO is the - // first bytecode in this sequence. - .IfArgumentEqualsOffset(4, 4, 0) - .ReplaceWith(BC_SKIP_UNTIL_CHAR_OR_CHAR) + .ReplaceWith(B::kSkipUntilCharOrChar) .MapArgument(0, 1, 3) // load offset .MapArgument(3, 1, 3, 4) // advance by .MapArgument(1, 1, 3, 2) // character 1 .MapArgument(2, 1, 3, 2) // character 2 .MapArgument(1, 4, 4) // goto when match .MapArgument(0, 4, 4) // goto on failure .IgnoreArgument(2, 4, 4) // goto when match 2 .IgnoreArgument(3, 4, 4); // loop jump - CreateSequence(BC_LOAD_CURRENT_CHAR) - .FollowedBy(BC_CHECK_GT) - // Sequence is only valid if the jump target of CHECK_GT is the first - // bytecode AFTER the whole sequence. - .IfArgumentEqualsOffset(4, 4, 56) - .FollowedBy(BC_CHECK_BIT_IN_TABLE) - // Sequence is only valid if the jump target of CHECK_BIT_IN_TABLE is - // the ADVANCE_CP_AND_GOTO bytecode at the end of the sequence. - .IfArgumentEqualsOffset(4, 4, 48) - .FollowedBy(BC_GOTO) - // Sequence is only valid if the jump target of GOTO is the same as the - // jump target of CHECK_GT (i.e. both jump to the first bytecode AFTER the - // whole sequence. - .IfArgumentEqualsValueAtOffset(4, 4, 1, 4, 4) - .FollowedBy(BC_ADVANCE_CP_AND_GOTO) - // Sequence is only valid if the jump target of ADVANCE_CP_AND_GOTO is the + CreateSequence(B::kLoadCurrentCharacter) + .FollowedBy(B::kCheckCharacterGT) + // Sequence is only valid if the jump target of kCheckCharacterGT is the + // first bytecode AFTER the whole sequence. + .IfArgumentEqualsOffset(OS(B::kCheckCharacterGT, on_greater), 56) + .FollowedBy(B::kCheckBitInTable) + // Sequence is only valid if the jump target of kCheckBitInTable is + // the kAdvanceCpAndGoto bytecode at the end of the sequence. + .IfArgumentEqualsOffset(OS(B::kCheckBitInTable, on_bit_set), 48) + .FollowedBy(B::kGoTo) + // Sequence is only valid if the jump target of kGoTo is the same as the + // jump target of kCheckCharacterGT (i.e. both jump to the first bytecode + // AFTER the whole sequence. + .IfArgumentEqualsValueAtOffset(OS(B::kGoTo, label), 1, + OS(B::kCheckCharacterGT, on_greater)) + .FollowedBy(B::kAdvanceCpAndGoto) + // Sequence is only valid if the jump target of kAdvanceCpAndGoto is the // first bytecode in this sequence. - .IfArgumentEqualsOffset(4, 4, 0) - .ReplaceWith(BC_SKIP_UNTIL_GT_OR_NOT_BIT_IN_TABLE) - .MapArgument(0, 1, 3) // load offset - .MapArgument(4, 1, 3, 2) // advance by - .MapArgument(1, 1, 3, 2) // character - .MapArgument(2, 8, 16) // bit table - .MapArgument(1, 4, 4) // goto when match - .MapArgument(0, 4, 4) // goto on failure - .IgnoreArgument(2, 4, 4) // indirect loop jump - .IgnoreArgument(3, 4, 4) // jump out of loop - .IgnoreArgument(4, 4, 4); // loop jump + .IfArgumentEqualsOffset(OS(B::kAdvanceCpAndGoto, on_goto), 0) + .ReplaceWith(B::kSkipUntilGtOrNotBitInTable) + .MapArgument(0, OSN_FIRST(B::kLoadCurrentCharacter, cp_offset)) + .MapArgument(4, OSN(B::kAdvanceCpAndGoto, by)) + // TODO(jgruber): Remove manual alignment once possible. + .MapArgument(1, OS_PACKED(B::kCheckCharacterGT, limit), 2) + .MapArgument(2, OSN(B::kCheckBitInTable, table)) + .MapArgument(1, OSN(B::kCheckCharacterGT, on_greater)) // on_match + .MapArgument(0, OSN(B::kLoadCurrentCharacter, on_failure)) // on_no_match + .IgnoreArgument(2, OS(B::kCheckBitInTable, on_bit_set)) + .IgnoreArgument(3, OS(B::kGoTo, label)) + .IgnoreArgument(4, OS(B::kAdvanceCpAndGoto, on_goto)); + + CreateSequence(B::kCheckPosition) + .FollowedBy(B::kLoad4CurrentCharsUnchecked) + .FollowedBy(B::kAndCheck4Chars) + // Jump target is the offset of the next AndCheck4Chars (right after + // AdvanceCpAndGoto). + .IfArgumentEqualsOffset(OS(B::kAndCheck4Chars, on_equal), 0x24) + .FollowedBy(B::kAdvanceCpAndGoto) + // Jump target of AdvanceCpAndGoto is the first bytecode in this + // sequence. + .IfArgumentEqualsOffset(OS(B::kAdvanceCpAndGoto, on_goto), 0) + .FollowedBy(B::kAndCheck4Chars) + .FollowedBy(B::kAndCheckNot4Chars) + // Jump target is AdvanceCpAndGoto. + .IfArgumentEqualsOffset(OS(B::kAndCheckNot4Chars, on_not_equal), 0x1c) + .ReplaceWith(B::kSkipUntilOneOfMasked) + .MapArgument(1, OSN_FIRST(B::kLoad4CurrentCharsUnchecked, cp_offset)) + // TODO(jgruber): Remove manual alignment once possible. + .MapArgument(3, OS_PACKED(B::kAdvanceCpAndGoto, by), 4) + .MapArgument(2, OSN(B::kAndCheck4Chars, characters)) // c + .MapArgument(2, OSN(B::kAndCheck4Chars, mask)) // mask + // TODO(jgruber): Remove manual alignment once possible. + .MapArgument(0, OS_PACKED(B::kCheckPosition, cp_offset), + 4) // maximum offset + .MapArgument(4, OSN(B::kAndCheck4Chars, characters)) // exact chars1 + .MapArgument(4, OSN(B::kAndCheck4Chars, mask)) // exact mask1 + .MapArgument(5, OSN(B::kAndCheckNot4Chars, characters)) // exact chars2 + .MapArgument(5, OSN(B::kAndCheckNot4Chars, mask)) // exact mask2 + .MapArgument(4, OSN(B::kAndCheck4Chars, on_equal)) // goto when match1 + .EmitOffsetAfterSequence() // fallthrough / goto when match2 + .MapArgument(0, OSN(B::kCheckPosition, on_failure)) // goto on failure + .IgnoreArgument(3, OS(B::kAdvanceCpAndGoto, on_goto)) + .IgnoreArgument(2, OS(B::kAndCheck4Chars, on_equal)); + + // TODO(jgruber): kSkipUntilBitInTable is itself both a + // peephole-generated bc, AND a standard bytecode. Either we run to a fixed + // point, or we need to be careful around ordering (and specify the seq based + // on basic bytecodes). + // TODO(jgruber): The convenience macros below should be replaced. Ideally we + // should have easy and concise access to all of these fields, e.g. just + // + // kSkipUntilBitInTable::cp_offset.size + // kSkipUntilBitInTable::cp_offset.offset + // + // Once that's done, methods in this class should be refactored to use that: + // + // foo.MapArgument(0, kSkipUntilBitInTable::cp_offset) + // + // The original bytecode sequence for kSkipUntilOneOfMasked3 is: + // + // sequence offset name + // bc0 0 SkipUntilBitInTable + // bc1 20 CheckPosition + // bc2 28 Load4CurrentCharsUnchecked + // bc3 2c AndCheck4Chars + // bc4 3c AdvanceCpAndGoto + // bc5 48 Load4CurrentChars + // bc6 4c AndCheck4Chars + // bc7 5c AndCheck4Chars + // bc8 6c AndCheckNot4Chars + + { + static constexpr int kOffsetOfBc0SkipUntilBitInTable = 0x0; + static constexpr int kOffsetOfBc1CheckCurrentPosition = 0x20; + static constexpr int kOffsetOfBc4AdvanceBcAndGoto = 0x3c; + BytecodeSequenceNode& s0 = + CreateSequence(B::kSkipUntilBitInTable) + .IfArgumentEqualsOffset(OS(B::kSkipUntilBitInTable, on_no_match), + kOffsetOfBc1CheckCurrentPosition) + .IfArgumentEqualsOffset(OS(B::kSkipUntilBitInTable, on_no_match), + kOffsetOfBc1CheckCurrentPosition); + + DCHECK_EQ(s0.SequenceLength(), 0x20); + DCHECK_EQ(s0.SequenceLength(), kOffsetOfBc1CheckCurrentPosition); + static constexpr int kOffsetOfBc5Load4CurrentChars = 0x44; + BytecodeSequenceNode& s1 = + s0.FollowedBy(B::kCheckPosition) + .FollowedBy(B::kLoad4CurrentCharsUnchecked) + .FollowedBy(B::kAndCheck4Chars) + .IfArgumentEqualsOffset(OS(B::kAndCheck4Chars, on_equal), + kOffsetOfBc5Load4CurrentChars); + + DCHECK_EQ(s1.SequenceLength(), 0x3c); + DCHECK_EQ(s1.SequenceLength(), kOffsetOfBc4AdvanceBcAndGoto); + BytecodeSequenceNode& s2 = + s1.FollowedBy(B::kAdvanceCpAndGoto) + .IfArgumentEqualsOffset(OS(B::kAdvanceCpAndGoto, on_goto), + kOffsetOfBc0SkipUntilBitInTable); + + DCHECK_EQ(s2.SequenceLength(), 0x44); + DCHECK_EQ(s2.SequenceLength(), kOffsetOfBc5Load4CurrentChars); + BytecodeSequenceNode& s3 = + s2.FollowedBy(B::kLoad4CurrentChars) + .IfArgumentEqualsOffset(OS(B::kLoad4CurrentChars, on_failure), + kOffsetOfBc4AdvanceBcAndGoto) + .FollowedBy(B::kAndCheck4Chars) + .FollowedBy(B::kAndCheck4Chars) + .FollowedBy(B::kAndCheckNot4Chars) + .IfArgumentEqualsOffset(OS(B::kAndCheckNot4Chars, on_not_equal), + kOffsetOfBc4AdvanceBcAndGoto); + + // Subtle: The sequence below must be crafted so that all alignment + // requirements are implicitly fulfilled. + // TODO(jgruber): Remove the verbose size comments and the duplicate args + // that ensure alignment, once we've switched exclusively to the new + // bytecode format. + s3.ReplaceWith(B::kSkipUntilOneOfMasked3) + // Size 2 packed. + .MapArgument(0, OSN_FIRST(B::kSkipUntilBitInTable, cp_offset)) + // Size 4. + .MapArgument(0, OSN(B::kSkipUntilBitInTable, advance_by)) + // Size 16 + .MapArgument(0, OSN(B::kSkipUntilBitInTable, table)) + .IgnoreArgument(0, OS(B::kSkipUntilBitInTable, on_match)) + .IgnoreArgument(0, OS(B::kSkipUntilBitInTable, on_no_match)) + // Size 2. + // TODO(jgruber): We emit this twice to satisfy alignment requirements + // of the next argument. Remove the duplicate once EmitArgument + // properly handles this on its own. + .MapArgument(1, OSN(B::kCheckPosition, cp_offset)) + .MapArgument(1, OSN(B::kCheckPosition, cp_offset)) + // Size 4. + .MapArgument(1, OSN(B::kCheckPosition, on_failure)) + // Size 2. + // TODO(jgruber): We emit this twice to satisfy alignment requirements + // of the next argument. Remove the duplicate once EmitArgument + // properly handles this on its own. + .MapArgument(2, OSN(B::kLoad4CurrentCharsUnchecked, cp_offset)) + .MapArgument(2, OSN(B::kLoad4CurrentCharsUnchecked, cp_offset)) + // Size 4. + .MapArgument(3, OSN(B::kAndCheck4Chars, characters)) + // Size 4. + .MapArgument(3, OSN(B::kAndCheck4Chars, mask)) + .IgnoreArgument(3, OS(B::kAndCheck4Chars, on_equal)) + // Size 2. + .MapArgument(4, OSN(B::kAdvanceCpAndGoto, by)) + .IgnoreArgument(4, OS(B::kAdvanceCpAndGoto, on_goto)) + // Size 2. + .MapArgument(5, OSN(B::kLoad4CurrentChars, cp_offset)) + .IgnoreArgument(5, OS(B::kLoad4CurrentChars, on_failure)) + // Size 4. + .MapArgument(6, OSN(B::kAndCheck4Chars, characters)) + // Size 4. + .MapArgument(6, OSN(B::kAndCheck4Chars, mask)) + // Size 4. + .MapArgument(6, OSN(B::kAndCheck4Chars, on_equal)) + // Size 4. + .MapArgument(7, OSN(B::kAndCheck4Chars, characters)) + // Size 4. + .MapArgument(7, OSN(B::kAndCheck4Chars, mask)) + // Size 4. + .MapArgument(7, OSN(B::kAndCheck4Chars, on_equal)) + // Size 4. + .MapArgument(8, OSN(B::kAndCheckNot4Chars, characters)) + // Size 4. + .MapArgument(8, OSN(B::kAndCheckNot4Chars, mask)) + .IgnoreArgument(8, OS(B::kAndCheckNot4Chars, on_not_equal)) + // Size 4. + .EmitOffsetAfterSequence(); + } + +#undef OPERAND_OFFSET +#undef OPERAND_SIZE +#undef OPERAND_SIZE_PACKED +#undef OS +#undef OS_PACKED +#undef OSN_FIRST +#undef OSN } bool RegExpBytecodePeephole::OptimizeBytecode(const uint8_t* bytecode, int length) { int old_pc = 0; @@ -619,12 +863,11 @@ int replaced_len = TryOptimizeSequence(bytecode, length, old_pc); if (replaced_len > 0) { old_pc += replaced_len; did_optimize = true; } else { - int bc = bytecode[old_pc]; - int bc_len = RegExpBytecodeLength(bc); + int bc_len = RegExpBytecodes::Size(bytecode[old_pc]); CopyRangeToOutput(bytecode, old_pc, bc_len); old_pc += bc_len; } } @@ -639,13 +882,13 @@ MemCopy(to_address, &(*optimized_bytecode_buffer_.begin()), Length()); } int RegExpBytecodePeephole::Length() const { return pc(); } -BytecodeSequenceNode& RegExpBytecodePeephole::CreateSequence(int bytecode) { +BytecodeSequenceNode& RegExpBytecodePeephole::CreateSequence( + RegExpBytecode bytecode) { DCHECK(sequences_ != nullptr); - DCHECK(0 <= bytecode && bytecode < kRegExpBytecodeCount); return sequences_->FollowedBy(bytecode); } int RegExpBytecodePeephole::TryOptimizeSequence(const uint8_t* bytecode, @@ -657,16 +900,16 @@ int current_pc = start_pc; // Check for the longest valid sequence matching any of the pre-defined // sequences in the Trie data structure. while (current_pc < bytecode_length) { - seq_node = seq_node->Find(bytecode[current_pc]); + seq_node = seq_node->Find(RegExpBytecodes::FromByte(bytecode[current_pc])); if (seq_node == nullptr) break; if (!seq_node->CheckArguments(bytecode, start_pc)) break; if (seq_node->IsSequence()) valid_seq_end = seq_node; - current_pc += RegExpBytecodeLength(bytecode[current_pc]); + current_pc += RegExpBytecodes::Size(bytecode[current_pc]); } if (valid_seq_end) { EmitOptimization(start_pc, bytecode, *valid_seq_end); return valid_seq_end->SequenceLength(); @@ -684,45 +927,62 @@ // Jump sources that are mapped or marked as unused will be deleted at the end // of this method. We don't delete them immediately as we might need the // information when we have to preserve bytecodes at the end. // TODO(pthier): Replace with a stack-allocated data structure. ZoneLinkedList delete_jumps = ZoneLinkedList(zone()); + // List of offsets in the optimized sequence that need to be patched to the + // offset value right after the optimized sequence. + ZoneLinkedList after_sequence_offsets = + ZoneLinkedList(zone()); - uint32_t bc = last_node.OptimizedBytecode(); - EmitValue(bc); + RegExpBytecode bc = last_node.OptimizedBytecode(); + EmitValue(RegExpBytecodes::ToByte(bc)); for (size_t arg = 0; arg < last_node.ArgumentSize(); arg++) { BytecodeArgumentMapping arg_map = last_node.ArgumentMapping(arg); - int arg_pos = start_pc + arg_map.offset; - // If we map any jump source we mark the old source for deletion and insert - // a new jump. - auto jump_edge_iter = jump_edges_.find(arg_pos); - if (jump_edge_iter != jump_edges_.end()) { - int jump_source = jump_edge_iter->first; - int jump_destination = jump_edge_iter->second; - // Add new jump edge add current position. - jump_edges_mapped_.emplace(Length(), jump_destination); - // Mark old jump edge for deletion. - delete_jumps.push_back(jump_source); - // Decrement usage count of jump destination. - auto jump_count_iter = jump_usage_counts_.find(jump_destination); - DCHECK(jump_count_iter != jump_usage_counts_.end()); - int& usage_count = jump_count_iter->second; - --usage_count; + if (arg_map.type() == BytecodeArgumentMapping::Type::kDefault) { + int arg_pos = start_pc + arg_map.offset(); + // If we map any jump source we mark the old source for deletion and + // insert a new jump. + auto jump_edge_iter = jump_edges_.find(arg_pos); + if (jump_edge_iter != jump_edges_.end()) { + int jump_source = jump_edge_iter->first; + int jump_destination = jump_edge_iter->second; + // Add new jump edge add current position. + jump_edges_mapped_.emplace(Length(), jump_destination); + // Mark old jump edge for deletion. + delete_jumps.push_back(jump_source); + // Decrement usage count of jump destination. + auto jump_count_iter = jump_usage_counts_.find(jump_destination); + DCHECK(jump_count_iter != jump_usage_counts_.end()); + int& usage_count = jump_count_iter->second; + --usage_count; + } + // TODO(pthier): DCHECK that mapped arguments are never sources of jumps + // to destinations inside the sequence. + EmitArgument(start_pc, bytecode, arg_map); + } else { + DCHECK_EQ(arg_map.type(), BytecodeArgumentMapping::Type::kSpecial); + using enum BytecodeArgumentMapping::SpecialType; + switch (arg_map.special_type()) { + case kOffsetAfterSequence: + after_sequence_offsets.push_back(pc()); + // Reserve space to overwrite later with the pc after this sequence. + EmitValue(0); + break; + } } - // TODO(pthier): DCHECK that mapped arguments are never sources of jumps - // to destinations inside the sequence. - EmitArgument(start_pc, bytecode, arg_map); } + DCHECK_EQ(pc(), optimized_start_pc + - RegExpBytecodeLength(last_node.OptimizedBytecode())); + RegExpBytecodes::Size(last_node.OptimizedBytecode())); // Remove jumps from arguments we ignore. if (last_node.HasIgnoredArguments()) { for (auto ignored_arg = last_node.ArgumentIgnoredBegin(); ignored_arg != last_node.ArgumentIgnoredEnd(); ignored_arg++) { - auto jump_edge_iter = jump_edges_.find(start_pc + ignored_arg->offset); + auto jump_edge_iter = jump_edges_.find(start_pc + ignored_arg->offset()); if (jump_edge_iter != jump_edges_.end()) { int jump_source = jump_edge_iter->first; int jump_destination = jump_edge_iter->second; // Mark old jump edge for deletion. delete_jumps.push_back(jump_source); @@ -733,11 +993,11 @@ --usage_count; } } } - int fixup_length = RegExpBytecodeLength(bc) - last_node.SequenceLength(); + int fixup_length = RegExpBytecodes::Size(bc) - last_node.SequenceLength(); // Check if there are any jumps inside the old sequence. // If so we have to keep the bytecodes that are jumped to around. auto jump_destination_candidate = jump_usage_counts_.upper_bound(start_pc); int jump_candidate_destination = jump_destination_candidate->first; @@ -768,11 +1028,11 @@ preserve_from = jump_destination; } } // We preserve everything to the end of the sequence. This is conservative - // since it would be enough to preserve all bytecudes up to an unconditional + // since it would be enough to preserve all bytecodes up to an unconditional // jump. int preserve_length = start_pc + last_node.SequenceLength() - preserve_from; fixup_length += preserve_length; // Jumps after the start of the preserved sequence need fixup. AddJumpSourceFixup(fixup_length, @@ -795,10 +1055,15 @@ for (int del : delete_jumps) { if (del < preserve_from) { jump_edges_.erase(del); } } + + for (uint32_t offset : after_sequence_offsets) { + DCHECK_EQ(optimized_bytecode_buffer_[offset], 0); + OverwriteValue(offset, pc()); + } } void RegExpBytecodePeephole::AddJumpSourceFixup(int fixup, int pos) { auto previous_fixup = jump_source_fixups_.lower_bound(pos); DCHECK(previous_fixup != jump_source_fixups_.end()); @@ -877,11 +1142,11 @@ #ifdef DEBUG // TODO(pthier): This check could be better if we track the bytecodes // actually used and check if we jump to one of them. uint8_t jump_bc = optimized_bytecode_buffer_[fixed_jump_destination]; DCHECK_GT(jump_bc, 0); - DCHECK_LT(jump_bc, kRegExpBytecodeCount); + DCHECK_LT(jump_bc, RegExpBytecodes::kCount); #endif if (jump_destination != fixed_jump_destination) { OverwriteValue(jump_source, fixed_jump_destination); } @@ -927,71 +1192,65 @@ value); } void RegExpBytecodePeephole::EmitArgument(int start_pc, const uint8_t* bytecode, BytecodeArgumentMapping arg) { - int arg_pos = start_pc + arg.offset; - switch (arg.length) { + int arg_pos = start_pc + arg.offset(); + switch (arg.length()) { case 1: - DCHECK_EQ(arg.new_length, arg.length); + DCHECK_EQ(arg.new_length(), arg.length()); EmitValue(GetValue(bytecode, arg_pos)); break; case 2: - DCHECK_EQ(arg.new_length, arg.length); + DCHECK_EQ(arg.new_length(), arg.length()); EmitValue(GetValue(bytecode, arg_pos)); break; case 3: { // Length 3 only occurs in 'packed' arguments where the lowermost byte is // the current bytecode, and the remaining 3 bytes are the packed value. // // We load 4 bytes from position - 1 and shift out the bytecode. #ifdef V8_TARGET_BIG_ENDIAN UNIMPLEMENTED(); - int32_t val = 0; #else int32_t val = GetValue(bytecode, arg_pos - 1) >> kBitsPerByte; -#endif // V8_TARGET_BIG_ENDIAN - switch (arg.new_length) { + switch (arg.new_length()) { case 2: EmitValue(val); break; case 3: { // Pack with previously emitted value. auto prev_val = GetValue(&(*optimized_bytecode_buffer_.begin()), Length() - sizeof(uint32_t)); -#ifdef V8_TARGET_BIG_ENDIAN - UNIMPLEMENTED(); - USE(prev_val); -#else DCHECK_EQ(prev_val & 0xFFFFFF00, 0); OverwriteValue( pc() - sizeof(uint32_t), (static_cast(val) << 8) | (prev_val & 0xFF)); -#endif // V8_TARGET_BIG_ENDIAN break; } case 4: EmitValue(val); break; } break; +#endif // V8_TARGET_BIG_ENDIAN } case 4: - DCHECK_EQ(arg.new_length, arg.length); + DCHECK_EQ(arg.new_length(), arg.length()); EmitValue(GetValue(bytecode, arg_pos)); break; case 8: - DCHECK_EQ(arg.new_length, arg.length); + DCHECK_EQ(arg.new_length(), arg.length()); EmitValue(GetValue(bytecode, arg_pos)); break; default: CopyRangeToOutput(bytecode, arg_pos, - std::min(arg.length, arg.new_length)); - if (arg.length < arg.new_length) { - SetRange(0x00, arg.new_length - arg.length); + std::min(arg.length(), arg.new_length())); + if (arg.length() < arg.new_length()) { + SetRange(0x00, arg.new_length() - arg.length()); } break; } } diff --git a/js/src/irregexp/imported/regexp-bytecodes-inl.h b/js/src/irregexp/imported/regexp-bytecodes-inl.h new file mode 100644 --- /dev/null +++ b/js/src/irregexp/imported/regexp-bytecodes-inl.h @@ -0,0 +1,359 @@ +// Copyright 2025 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_BYTECODES_INL_H_ +#define V8_REGEXP_REGEXP_BYTECODES_INL_H_ + +#include "irregexp/imported/regexp-bytecodes.h" +// Include the non-inl header before the rest of the headers. + +#include +#include +#include + +#include "irregexp/imported/regexp-macro-assembler.h" // For StackCheckFlag + +namespace v8 { +namespace internal { + +template +struct RegExpOperandTypeTraits; + +#define DECLARE_BASIC_OPERAND_TYPE_TRAITS(Name, CType) \ + template <> \ + struct RegExpOperandTypeTraits { \ + static_assert(!std::is_pointer_v); \ + static constexpr uint8_t kSize = sizeof(CType); \ + using kCType = CType; \ + static constexpr bool kIsBasic = true; \ + static constexpr kCType kMinValue = std::numeric_limits::min(); \ + static constexpr kCType kMaxValue = std::numeric_limits::max(); \ + }; +BASIC_BYTECODE_OPERAND_TYPE_LIST(DECLARE_BASIC_OPERAND_TYPE_TRAITS) +#undef DECLARE_OPERAND_TYPE_TRAITS + +#define DECLARE_BASIC_OPERAND_TYPE_LIMITS_TRAITS(Name, CType, MinValue, \ + MaxValue) \ + template <> \ + struct RegExpOperandTypeTraits { \ + static_assert(!std::is_pointer_v); \ + static constexpr uint8_t kSize = sizeof(CType); \ + using kCType = CType; \ + static constexpr bool kIsBasic = true; \ + static_assert(std::is_enum_v || \ + MinValue >= std::numeric_limits::min()); \ + static_assert(std::is_enum_v || \ + MaxValue <= std::numeric_limits::max()); \ + static constexpr kCType kMinValue = MinValue; \ + static constexpr kCType kMaxValue = MaxValue; \ + }; +BASIC_BYTECODE_OPERAND_TYPE_LIMITS_LIST( + DECLARE_BASIC_OPERAND_TYPE_LIMITS_TRAITS) +#undef DECLARE_OPERAND_TYPE_LIMITS_TRAITS + +#define DECLARE_SPECIAL_OPERAND_TYPE_TRAITS(Name, Size) \ + template <> \ + struct RegExpOperandTypeTraits { \ + static constexpr uint8_t kSize = Size; \ + static constexpr bool kIsBasic = false; \ + }; +SPECIAL_BYTECODE_OPERAND_TYPE_LIST(DECLARE_SPECIAL_OPERAND_TYPE_TRAITS) +#undef DECLARE_OPERAND_TYPE_TRAITS + +namespace detail { + +// Bytecode is 4-byte aligned. +// We can pack operands if multiple operands fit into 4 bytes. +static constexpr int kBytecodeAlignment = 4; + +// Calculates packed offsets for each Bytecode operand. +// The first operand can be packed together with the bytecode at an unaligned +// offset 1. All other operands are aligned to their own size if +// they are "basic" types. +template +consteval auto CalculatePackedOffsets() { + constexpr int N = sizeof...(operand_types); + constexpr std::array kOperandSizes = { + RegExpOperandTypeTraits::kSize...}; + constexpr std::array kIsBasic = { + RegExpOperandTypeTraits::kIsBasic...}; + + std::array offsets{}; + int first_offset = sizeof(RegExpBytecode); + int offset = first_offset; + + for (size_t i = 0; i < N; ++i) { + uint8_t operand_size = kOperandSizes[i]; + + // An operand is only allowed to be unaligned, if it's packed with the + // bytecode. All subsequent basic operands must be aligned to their own + // size. + if (offset > first_offset && kIsBasic[i]) { + offset = RoundUp(offset, operand_size); + } + + // If the operand doesn't fit into the current 4-byte block, start a new + // 4-byte block. + if ((offset % kBytecodeAlignment) + operand_size > kBytecodeAlignment) { + offset = RoundUp(offset); + } + + offsets[i] = offset; + offset += operand_size; + } + + return offsets; +} + +template +struct RegExpBytecodeOperandsTraits { + static constexpr int kOperandCount = sizeof...(ops); + static constexpr std::array + kOperandTypes = {ops...}; + static constexpr std::array kOperandSizes = { + RegExpOperandTypeTraits::kSize...}; + static constexpr std::array kOperandOffsets = + CalculatePackedOffsets(); + static constexpr int kSize = RoundUp( + kOperandCount == 0 ? sizeof(RegExpBytecode) + : kOperandOffsets.back() + kOperandSizes.back()); +}; + +template +struct RegExpBytecodeOperandNames; + +#define DECLARE_OPERAND_NAMES(CamelName, OpNames, OpTypes) \ + template <> \ + struct RegExpBytecodeOperandNames { \ + enum class Operand { UNPAREN(OpNames) }; \ + using enum Operand; \ + }; +REGEXP_BYTECODE_LIST(DECLARE_OPERAND_NAMES) +#undef DECLARE_OPERAND_NAMES + +template +class RegExpBytecodeOperandsBase { + public: + using Operand = RegExpBytecodeOperandNames::Operand; + using Traits = RegExpBytecodeOperandsTraits; + static constexpr int kCount = Traits::kOperandCount; + static constexpr int kTotalSize = Traits::kSize; + static consteval int Index(Operand op) { return static_cast(op); } + static consteval int Size(Operand op) { + return Traits::kOperandSizes[Index(op)]; + } + static consteval int Offset(Operand op) { + return Traits::kOperandOffsets[Index(op)]; + } + static consteval RegExpBytecodeOperandType Type(Operand op) { + return Traits::kOperandTypes[Index(op)]; + } + + // Returns a tuple of all "real" (non-padding) operands. + static consteval auto GetOperandsTuple() { + return [](std::index_sequence) { + return std::tuple_cat([]() { + constexpr auto id = static_cast(I); + if constexpr (Type(id) == ReBcOpType::kPadding1 || + Type(id) == ReBcOpType::kPadding2) { + return std::tuple<>(); + } else { + return std::tuple(std::integral_constant{}); + } + }.template operator()()...); + }(std::make_index_sequence{}); + } + + static constexpr int kCountWithoutPadding = + std::tuple_size_v; + + // Calls |f| templatized by Operand for each Operand in the Operands list, + // ignoring padding. + // Example: + // using Operands = RegExpBytecodeOperands; + // size_t op_sizes = 0; + // Operands::ForEachOperand([]() { + // op_sizes += Operands::Size(op); + // }); + // Note that this gets evaluated at compile time, so op_sizes in the example + // above is essentially a constant. + template + static constexpr void ForEachOperand(Func&& f) { + constexpr auto filtered_ops = GetOperandsTuple(); + std::apply([&](auto... ops) { (..., f.template operator()()); }, + filtered_ops); + } + + // Similar to ForEachOperand, but additionally provides the current index as + // a template argument. The index is a sequential index of operands with + // filtered padding. + template + static constexpr void ForEachOperandWithIndex(Func&& f) { + constexpr auto filtered_ops = GetOperandsTuple(); + [&](std::index_sequence) { + (..., + f.template operator()< + std::tuple_element_t::value /* Operand */, + I /* Index */>()); + }(std::make_index_sequence>{}); + } + + // Similar to above, but calls |f| only for operands of a given type. + template + static constexpr void ForEachOperandOfType(Func&& f) { + ForEachOperand([&]() { + if constexpr (Type(operand) == OpType) { + f.template operator()(); + } + }); + } + + private: + template + requires(RegExpOperandTypeTraits::kIsBasic) + static auto GetAligned(const uint8_t* pc, int offset) { + DCHECK_EQ(RegExpBytecodes::FromPtr(pc), bc); + DCHECK_NE(offset, 1); + using CType = RegExpOperandTypeTraits::kCType; + DCHECK(IsAligned(offset, sizeof(CType))); + return *reinterpret_cast(pc + offset); + } + + // TODO(pthier): We can remove unaligned packing once we have fully switched + // to the new bytecode layout. This is for backwards-compatibility with the + // old layout only. + template + requires(RegExpOperandTypeTraits::kIsBasic) + static auto GetPacked(const uint8_t* pc, int offset) { + DCHECK_EQ(RegExpBytecodes::FromPtr(pc), bc); + // Only packing of 1-byte and 2-byte values with the bytecode is supported. + DCHECK_EQ(offset, 1); + constexpr int size = RegExpOperandTypeTraits::kSize; + static_assert(size <= 2); + using CType = RegExpOperandTypeTraits::kCType; + DCHECK_IMPLIES(size > 1, !IsAligned(offset, sizeof(CType))); + int32_t packed_value = *reinterpret_cast(pc); + return static_cast(packed_value >> BYTECODE_SHIFT); + } + + public: + template + requires(RegExpOperandTypeTraits::kIsBasic) + static auto Get(const uint8_t* pc, const DisallowGarbageCollection& no_gc) { + constexpr RegExpBytecodeOperandType OperandType = Type(op); + constexpr int offset = Offset(op); + // TODO(pthier): We can remove unaligned packing once we have fully switched + // to the new bytecode layout. This is for backwards-compatibility with the + // old layout only. + if constexpr (offset == 1) { + return GetPacked(pc, offset); + } else { + return GetAligned(pc, offset); + } + } + + template + requires(RegExpOperandTypeTraits::kIsBasic) + static auto Get(DirectHandle bytecode, int offset, + Zone* zone) { + // Basic operand types won't allocate, so we can always fallback to the + // GC-unsafe version. + DisallowGarbageCollection no_gc; + return Get(bytecode->begin() + offset, no_gc); + } + + template + requires(Type(op) == RegExpBytecodeOperandType::kBitTable) + static auto Get(const uint8_t* pc, const DisallowGarbageCollection& no_gc) { + static_assert(Size(op) == RegExpMacroAssembler::kTableSize / kBitsPerByte); + DCHECK_EQ(RegExpBytecodes::FromPtr(pc), bc); + constexpr int offset = Offset(op); + return pc + offset; + } + + template + requires(Type(op) == RegExpBytecodeOperandType::kBitTable) + static auto Get(DirectHandle bytecode, int offset, + Zone* zone) { + static_assert(Size(op) == RegExpMacroAssembler::kTableSize / kBitsPerByte); + DCHECK_EQ(RegExpBytecodes::FromPtr(bytecode->begin() + offset), bc); + constexpr int op_offset = Offset(op); + const uint8_t* start = bytecode->begin() + offset + op_offset; + const uint8_t* end = start + Size(op); + return ZoneVector(start, end, zone); + } +}; + +} // namespace detail + +#define PACK_OPTIONAL(x, ...) x __VA_OPT__(, ) __VA_ARGS__ + +#define DECLARE_OPERANDS(CamelName, OpNames, OpTypes) \ + template <> \ + class RegExpBytecodeOperands final \ + : public detail::RegExpBytecodeOperandsBase, \ + public AllStatic { \ + public: \ + using enum Operand; \ + }; + +REGEXP_BYTECODE_LIST(DECLARE_OPERANDS) +#undef DECLARE_OPERANDS + +namespace detail { + +#define DECLARE_BYTECODE_NAMES(CamelName, ...) #CamelName, +static constexpr const char* kBytecodeNames[] = { + REGEXP_BYTECODE_LIST(DECLARE_BYTECODE_NAMES)}; +#undef DECLARE_BYTECODE_NAMES + +#define DECLARE_BYTECODE_SIZES(CamelName, ...) \ + RegExpBytecodeOperands::kTotalSize, +static constexpr uint8_t kBytecodeSizes[] = { + REGEXP_BYTECODE_LIST(DECLARE_BYTECODE_SIZES)}; +#undef DECLARE_BYTECODE_SIZES + +} // namespace detail + +// static +template +decltype(auto) RegExpBytecodes::DispatchOnBytecode(RegExpBytecode bytecode, + Func&& f) { + switch (bytecode) { +#define CASE(CamelName, ...) \ + case RegExpBytecode::k##CamelName: \ + return f.template operator()(); + REGEXP_BYTECODE_LIST(CASE) +#undef CASE + } + UNREACHABLE(); +} + +// static +constexpr const char* RegExpBytecodes::Name(RegExpBytecode bytecode) { + return Name(ToByte(bytecode)); +} + +// static +constexpr const char* RegExpBytecodes::Name(uint8_t bytecode) { + DCHECK_LT(bytecode, kCount); + return detail::kBytecodeNames[bytecode]; +} + +// static +constexpr uint8_t RegExpBytecodes::Size(RegExpBytecode bytecode) { + return Size(ToByte(bytecode)); +} + +// static +constexpr uint8_t RegExpBytecodes::Size(uint8_t bytecode) { + DCHECK_LT(bytecode, kCount); + return detail::kBytecodeSizes[bytecode]; +} + +} // namespace internal +} // namespace v8 + +#endif // V8_REGEXP_REGEXP_BYTECODES_INL_H_ diff --git a/js/src/irregexp/imported/regexp-bytecodes.h b/js/src/irregexp/imported/regexp-bytecodes.h --- a/js/src/irregexp/imported/regexp-bytecodes.h +++ b/js/src/irregexp/imported/regexp-bytecodes.h @@ -8,247 +8,342 @@ #include "irregexp/RegExpShim.h" namespace v8 { namespace internal { -// Maximum number of bytecodes that will be used (next power of 2 of actually -// defined bytecodes). -// All slots between the last actually defined bytecode and maximum id will be -// filled with BREAKs, indicating an invalid operation. This way using -// BYTECODE_MASK guarantees no OOB access to the dispatch table. -constexpr int kRegExpPaddedBytecodeCount = 1 << 6; -constexpr int BYTECODE_MASK = kRegExpPaddedBytecodeCount - 1; -// The first argument is packed in with the byte code in one word, but so it -// has 24 bits, but it can be positive and negative so only use 23 bits for -// positive values. -const unsigned int MAX_FIRST_ARG = 0x7fffffu; +// The first argument is packed in with the byte code in one word. +// We only support packing of up to 2 bytes. +const unsigned int MAX_FIRST_ARG = 0xffffu; const int BYTECODE_SHIFT = 8; -static_assert(1 << BYTECODE_SHIFT > BYTECODE_MASK); + +// Basic operand types that have a direct mapping to a C-type. +// Getters/Setters for these are fully auto-generated. +// Format: V(Name, C type) +#define BASIC_BYTECODE_OPERAND_TYPE_LIST(V) \ + V(Int16, int16_t) \ + V(Int32, int32_t) \ + V(Uint32, uint32_t) \ + V(Char, base::uc16) \ + V(JumpTarget, uint32_t) + +#define BASIC_BYTECODE_OPERAND_TYPE_LIMITS_LIST(V) \ + V(Offset, int16_t, RegExpMacroAssembler::kMinCPOffset, \ + RegExpMacroAssembler::kMaxCPOffset) \ + /* TODO(433891213): Only for backwards-compatibility. Can be replaced with \ + */ \ + /* Offset once the old format is removed. */ \ + V(Offset32, int32_t, RegExpMacroAssembler::kMinCPOffset, \ + RegExpMacroAssembler::kMaxCPOffset) \ + V(Register, uint16_t, 0, RegExpMacroAssembler::kMaxRegister) \ + V(StackCheckFlag, RegExpMacroAssembler::StackCheckFlag, \ + RegExpMacroAssembler::StackCheckFlag::kNoStackLimitCheck, \ + RegExpMacroAssembler::StackCheckFlag::kCheckStackLimit) \ + V(StandardCharacterSet, StandardCharacterSet, \ + StandardCharacterSet::kEverything, StandardCharacterSet::kWord) + +// Special operand types that don't have a direct mapping to a C-type. +// Getters/Setters for these types need to be specialized manually. +#define SPECIAL_BYTECODE_OPERAND_TYPE_LIST(V) \ + V(BitTable, 16) \ + /* TODO(433891213): padding is only required for backwards compatibility \ + with the old layout. It can be removed after everything is using the new \ + layout. */ \ + V(Padding1, 1) \ + V(Padding2, 2) + +#define BYTECODE_OPERAND_TYPE_LIST(V) \ + BASIC_BYTECODE_OPERAND_TYPE_LIST(V) \ + BASIC_BYTECODE_OPERAND_TYPE_LIMITS_LIST(V) \ + SPECIAL_BYTECODE_OPERAND_TYPE_LIST(V) + +enum class RegExpBytecodeOperandType : uint8_t { +#define DECLARE_OPERAND(Name, ...) k##Name, + BYTECODE_OPERAND_TYPE_LIST(DECLARE_OPERAND) +#undef DECLARE_OPERAND +}; -// The list of bytecodes, in format: V(Name, Code, ByteLength). -// TODO(pthier): Argument offsets of bytecodes should be easily accessible by -// name or at least by position. -// TODO(jgruber): More precise types (e.g. int32/uint32 instead of value32). -#define BYTECODE_ITERATOR(V) \ - V(BREAK, 0, 4) /* bc8 */ \ - V(PUSH_CP, 1, 4) /* bc8 pad24 */ \ - V(PUSH_BT, 2, 8) /* bc8 pad24 offset32 */ \ - V(PUSH_REGISTER, 3, 4) /* bc8 reg_idx24 */ \ - V(SET_REGISTER_TO_CP, 4, 8) /* bc8 reg_idx24 offset32 */ \ - V(SET_CP_TO_REGISTER, 5, 4) /* bc8 reg_idx24 */ \ - V(SET_REGISTER_TO_SP, 6, 4) /* bc8 reg_idx24 */ \ - V(SET_SP_TO_REGISTER, 7, 4) /* bc8 reg_idx24 */ \ - V(SET_REGISTER, 8, 8) /* bc8 reg_idx24 value32 */ \ - V(ADVANCE_REGISTER, 9, 8) /* bc8 reg_idx24 value32 */ \ - V(POP_CP, 10, 4) /* bc8 pad24 */ \ - V(POP_BT, 11, 4) /* bc8 pad24 */ \ - V(POP_REGISTER, 12, 4) /* bc8 reg_idx24 */ \ - V(FAIL, 13, 4) /* bc8 pad24 */ \ - V(SUCCEED, 14, 4) /* bc8 pad24 */ \ - V(ADVANCE_CP, 15, 4) /* bc8 offset24 */ \ +using ReBcOpType = RegExpBytecodeOperandType; + +// Bytecodes that indicate something is invalid. These don't have a direct +// equivalent in RegExpMacroAssembler. +// It's a requirement that BREAK has an enum value of 0 (as e.g. jumps to offset +// 0 are considered invalid). +// Format: V(CamelName, (OperandNames...), (OperandTypes...)) +#define INVALID_BYTECODE_LIST(V) V(Break, (), ()) + +// Format: V(CamelName, (OperandNames...), (OperandTypes...)) +#define BASIC_BYTECODE_LIST(V) \ + V(PushCurrentPosition, (), ()) \ + V(PushBacktrack, (label), (ReBcOpType::kJumpTarget)) \ + V(WriteCurrentPositionToRegister, (register_index, cp_offset), \ + (ReBcOpType::kRegister, ReBcOpType::kOffset32)) \ + V(ReadCurrentPositionFromRegister, (register_index), \ + (ReBcOpType::kRegister)) \ + V(WriteStackPointerToRegister, (register_index), (ReBcOpType::kRegister)) \ + V(ReadStackPointerFromRegister, (register_index), (ReBcOpType::kRegister)) \ + V(SetRegister, (register_index, value), \ + (ReBcOpType::kRegister, ReBcOpType::kInt32)) \ + /* Clear registers in the range from_register to to_register (inclusive) */ \ + V(ClearRegisters, (padding, from_register, to_register), \ + (ReBcOpType::kPadding2, ReBcOpType::kRegister, ReBcOpType::kRegister)) \ + V(AdvanceRegister, (register_index, by), \ + (ReBcOpType::kRegister, ReBcOpType::kOffset32)) \ + V(PopCurrentPosition, (), ()) \ + /* TODO(pthier): PushRegister fits into 4 byte once the restrictions due */ \ + /* to the old layout are lifted */ \ + V(PushRegister, (register_index, padding, stack_check), \ + (ReBcOpType::kRegister, ReBcOpType::kPadding1, \ + ReBcOpType::kStackCheckFlag)) \ + V(PopRegister, (register_index), (ReBcOpType::kRegister)) \ + V(Fail, (), ()) \ + V(Succeed, (), ()) \ + V(AdvanceCurrentPosition, (by), (ReBcOpType::kOffset)) \ /* Jump to another bytecode given its offset. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x10 (fixed) Bytecode */ \ - /* 0x08 - 0x1F: 0x00 (unused) Padding */ \ - /* 0x20 - 0x3F: Address of bytecode to jump to */ \ - V(GOTO, 16, 8) /* bc8 pad24 addr32 */ \ + V(GoTo, (label), (ReBcOpType::kJumpTarget)) \ /* Check if offset is in range and load character at given offset. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x11 (fixed) Bytecode */ \ - /* 0x08 - 0x1F: Offset from current position */ \ - /* 0x20 - 0x3F: Address of bytecode when load is out of range */ \ - V(LOAD_CURRENT_CHAR, 17, 8) /* bc8 offset24 addr32 */ \ - /* Load character at given offset without range checks. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x12 (fixed) Bytecode */ \ - /* 0x08 - 0x1F: Offset from current position */ \ - V(LOAD_CURRENT_CHAR_UNCHECKED, 18, 4) /* bc8 offset24 */ \ - V(LOAD_2_CURRENT_CHARS, 19, 8) /* bc8 offset24 addr32 */ \ - V(LOAD_2_CURRENT_CHARS_UNCHECKED, 20, 4) /* bc8 offset24 */ \ - V(LOAD_4_CURRENT_CHARS, 21, 8) /* bc8 offset24 addr32 */ \ - V(LOAD_4_CURRENT_CHARS_UNCHECKED, 22, 4) /* bc8 offset24 */ \ - V(CHECK_4_CHARS, 23, 12) /* bc8 pad24 uint32 addr32 */ \ + V(LoadCurrentCharacter, (cp_offset, on_failure), \ + (ReBcOpType::kOffset, ReBcOpType::kJumpTarget)) \ + /* Checks if current position + given offset is in range. */ \ + /* I.e. jumps to |on_failure| if current pos + |cp_offset| >= subject len */ \ + V(CheckPosition, (cp_offset, on_failure), \ + (ReBcOpType::kOffset, ReBcOpType::kJumpTarget)) \ + V(CheckSpecialClassRanges, (character_set, on_no_match), \ + (ReBcOpType::kStandardCharacterSet, ReBcOpType::kJumpTarget)) \ /* Check if current character is equal to a given character */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x19 (fixed) Bytecode */ \ - /* 0x08 - 0x0F: 0x00 (unused) Padding */ \ - /* 0x10 - 0x1F: Character to check */ \ - /* 0x20 - 0x3F: Address of bytecode when matched */ \ - V(CHECK_CHAR, 24, 8) /* bc8 pad8 uint16 addr32 */ \ - V(CHECK_NOT_4_CHARS, 25, 12) /* bc8 pad24 uint32 addr32 */ \ - V(CHECK_NOT_CHAR, 26, 8) /* bc8 pad8 uint16 addr32 */ \ - V(AND_CHECK_4_CHARS, 27, 16) /* bc8 pad24 uint32 uint32 addr32 */ \ + V(CheckCharacter, (character, on_equal), \ + (ReBcOpType::kChar, ReBcOpType::kJumpTarget)) \ + V(CheckNotCharacter, (character, on_not_equal), \ + (ReBcOpType::kChar, ReBcOpType::kJumpTarget)) \ /* Checks if the current character combined with mask (bitwise and) */ \ /* matches a character (e.g. used when two characters in a disjunction */ \ /* differ by only a single bit */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x1c (fixed) Bytecode */ \ - /* 0x08 - 0x0F: 0x00 (unused) Padding */ \ - /* 0x10 - 0x1F: Character to match against (after mask aplied) */ \ - /* 0x20 - 0x3F: Bitmask bitwise and combined with current character */ \ - /* 0x40 - 0x5F: Address of bytecode when matched */ \ - V(AND_CHECK_CHAR, 28, 12) /* bc8 pad8 uint16 uint32 addr32 */ \ - V(AND_CHECK_NOT_4_CHARS, 29, 16) /* bc8 pad24 uint32 uint32 addr32 */ \ - V(AND_CHECK_NOT_CHAR, 30, 12) /* bc8 pad8 uint16 uint32 addr32 */ \ - V(MINUS_AND_CHECK_NOT_CHAR, 31, \ - 12) /* bc8 pad8 base::uc16 base::uc16 base::uc16 addr32 */ \ - V(CHECK_CHAR_IN_RANGE, 32, 12) /* bc8 pad24 base::uc16 base::uc16 addr32 */ \ - V(CHECK_CHAR_NOT_IN_RANGE, 33, \ - 12) /* bc8 pad24 base::uc16 base::uc16 addr32 */ \ + /* TODO(pthier): mask should be kChar */ \ + V(CheckCharacterAfterAnd, (character, mask, on_equal), \ + (ReBcOpType::kChar, ReBcOpType::kUint32, ReBcOpType::kJumpTarget)) \ + /* TODO(pthier): mask should be kChar */ \ + V(CheckNotCharacterAfterAnd, (character, mask, on_not_equal), \ + (ReBcOpType::kChar, ReBcOpType::kUint32, ReBcOpType::kJumpTarget)) \ + V(CheckNotCharacterAfterMinusAnd, (character, minus, mask, on_not_equal), \ + (ReBcOpType::kChar, ReBcOpType::kChar, ReBcOpType::kChar, \ + ReBcOpType::kJumpTarget)) \ + V(CheckCharacterInRange, (padding, from, to, on_in_range), \ + (ReBcOpType::kPadding2, ReBcOpType::kChar, ReBcOpType::kChar, \ + ReBcOpType::kJumpTarget)) \ + V(CheckCharacterNotInRange, (padding, from, to, on_not_in_range), \ + (ReBcOpType::kPadding2, ReBcOpType::kChar, ReBcOpType::kChar, \ + ReBcOpType::kJumpTarget)) \ + V(CheckCharacterLT, (limit, on_less), \ + (ReBcOpType::kChar, ReBcOpType::kJumpTarget)) \ + V(CheckCharacterGT, (limit, on_greater), \ + (ReBcOpType::kChar, ReBcOpType::kJumpTarget)) \ + V(IfRegisterLT, (register_index, comparand, on_less_than), \ + (ReBcOpType::kRegister, ReBcOpType::kInt32, ReBcOpType::kJumpTarget)) \ + V(IfRegisterGE, (register_index, comparand, on_greater_or_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kInt32, ReBcOpType::kJumpTarget)) \ + V(IfRegisterEqPos, (register_index, on_eq), \ + (ReBcOpType::kRegister, ReBcOpType::kJumpTarget)) \ + V(CheckAtStart, (cp_offset, on_at_start), \ + (ReBcOpType::kOffset, ReBcOpType::kJumpTarget)) \ + V(CheckNotAtStart, (cp_offset, on_not_at_start), \ + (ReBcOpType::kOffset, ReBcOpType::kJumpTarget)) \ + /* Checks if the current position matches top of backtrack stack */ \ + V(CheckFixedLengthLoop, (on_tos_equals_current_position), \ + (ReBcOpType::kJumpTarget)) \ + /* Advance character pointer by given offset and jump to another bytecode.*/ \ + V(SetCurrentPositionFromEnd, (by), (ReBcOpType::kOffset)) + +// Bytecodes dealing with multiple characters, introduced due to special logic +// in the bytecode-generator or requiring additional logic when assembling; +// e.g. they have arguments only used in the interpreter, different +// MacroAssembler names, non-default MacroAssembler arguments that need to be +// provided, etc. +// These share a method with Basic Bytecodes in RegExpMacroAssembler. +// Format: V(CamelName, (OperandNames...), (OperandTypes...)) +#define SPECIAL_BYTECODE_LIST(V) \ + V(Backtrack, (return_code), (ReBcOpType::kInt16)) \ + /* Load character at given offset without range checks. */ \ + V(LoadCurrentCharacterUnchecked, (cp_offset), (ReBcOpType::kOffset)) \ /* Checks if the current character matches any of the characters encoded */ \ /* in a bit table. Similar to/inspired by boyer moore string search */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x22 (fixed) Bytecode */ \ - /* 0x08 - 0x1F: 0x00 (unused) Padding */ \ - /* 0x20 - 0x3F: Address of bytecode when bit is set */ \ - /* 0x40 - 0xBF: Bit table */ \ - V(CHECK_BIT_IN_TABLE, 34, 24) /* bc8 pad24 addr32 bits128 */ \ - V(CHECK_LT, 35, 8) /* bc8 pad8 base::uc16 addr32 */ \ - V(CHECK_GT, 36, 8) /* bc8 pad8 base::uc16 addr32 */ \ - V(CHECK_NOT_BACK_REF, 37, 8) /* bc8 reg_idx24 addr32 */ \ - V(CHECK_NOT_BACK_REF_NO_CASE, 38, 8) /* bc8 reg_idx24 addr32 */ \ - V(CHECK_NOT_BACK_REF_NO_CASE_UNICODE, 39, 8) \ - V(CHECK_NOT_BACK_REF_BACKWARD, 40, 8) /* bc8 reg_idx24 addr32 */ \ - V(CHECK_NOT_BACK_REF_NO_CASE_BACKWARD, 41, 8) /* bc8 reg_idx24 addr32 */ \ - V(CHECK_NOT_BACK_REF_NO_CASE_UNICODE_BACKWARD, 42, 8) \ - V(CHECK_NOT_REGS_EQUAL, 43, 12) /* bc8 regidx24 reg_idx32 addr32 */ \ - V(CHECK_REGISTER_LT, 44, 12) /* bc8 reg_idx24 value32 addr32 */ \ - V(CHECK_REGISTER_GE, 45, 12) /* bc8 reg_idx24 value32 addr32 */ \ - V(CHECK_REGISTER_EQ_POS, 46, 8) /* bc8 reg_idx24 addr32 */ \ - V(CHECK_AT_START, 47, 8) /* bc8 pad24 addr32 */ \ - V(CHECK_NOT_AT_START, 48, 8) /* bc8 offset24 addr32 */ \ - /* Checks if the current position matches top of backtrack stack */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x31 (fixed) Bytecode */ \ - /* 0x08 - 0x1F: 0x00 (unused) Padding */ \ - /* 0x20 - 0x3F: Address of bytecode when current matches tos */ \ - V(CHECK_GREEDY, 49, 8) /* bc8 pad24 addr32 */ \ - /* Advance character pointer by given offset and jump to another bytecode.*/ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x32 (fixed) Bytecode */ \ - /* 0x08 - 0x1F: Number of characters to advance */ \ - /* 0x20 - 0x3F: Address of bytecode to jump to */ \ - V(ADVANCE_CP_AND_GOTO, 50, 8) /* bc8 offset24 addr32 */ \ - V(SET_CURRENT_POSITION_FROM_END, 51, 4) /* bc8 idx24 */ \ - /* Checks if current position + given offset is in range. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07: 0x34 (fixed) Bytecode */ \ - /* 0x08 - 0x1F: Offset from current position */ \ - /* 0x20 - 0x3F: Address of bytecode when position is out of range */ \ - V(CHECK_CURRENT_POSITION, 52, 8) /* bc8 idx24 addr32 */ \ + /* Todo(pthier): Change order to (table, label) and move to Basic */ \ + V(CheckBitInTable, (on_bit_set, table), \ + (ReBcOpType::kJumpTarget, ReBcOpType::kBitTable)) \ + V(Load2CurrentChars, (cp_offset, on_failure), \ + (ReBcOpType::kOffset, ReBcOpType::kJumpTarget)) \ + V(Load2CurrentCharsUnchecked, (cp_offset), (ReBcOpType::kOffset)) \ + V(Load4CurrentChars, (cp_offset, on_failure), \ + (ReBcOpType::kOffset, ReBcOpType::kJumpTarget)) \ + V(Load4CurrentCharsUnchecked, (cp_offset), (ReBcOpType::kOffset)) \ + V(Check4Chars, (characters, on_equal), \ + (ReBcOpType::kUint32, ReBcOpType::kJumpTarget)) \ + V(CheckNot4Chars, (characters, on_not_equal), \ + (ReBcOpType::kUint32, ReBcOpType::kJumpTarget)) \ + V(AndCheck4Chars, (characters, mask, on_equal), \ + (ReBcOpType::kUint32, ReBcOpType::kUint32, ReBcOpType::kJumpTarget)) \ + V(AndCheckNot4Chars, (characters, mask, on_not_equal), \ + (ReBcOpType::kUint32, ReBcOpType::kUint32, ReBcOpType::kJumpTarget)) \ + V(AdvanceCpAndGoto, (by, on_goto), \ + (ReBcOpType::kOffset, ReBcOpType::kJumpTarget)) \ + /* TODO(pthier): CheckNotBackRef variants could be merged into a single */ \ + /* Bytecode without increasing the size */ \ + V(CheckNotBackRef, (start_reg, on_not_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kJumpTarget)) \ + V(CheckNotBackRefNoCase, (start_reg, on_not_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kJumpTarget)) \ + V(CheckNotBackRefNoCaseUnicode, (start_reg, on_not_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kJumpTarget)) \ + V(CheckNotBackRefBackward, (start_reg, on_not_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kJumpTarget)) \ + V(CheckNotBackRefNoCaseBackward, (start_reg, on_not_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kJumpTarget)) \ + V(CheckNotBackRefNoCaseUnicodeBackward, (start_reg, on_not_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kJumpTarget)) \ + V(CheckNotRegsEqual, (reg1, reg2, on_not_equal), \ + (ReBcOpType::kRegister, ReBcOpType::kRegister, \ + ReBcOpType::kJumpTarget)) /* TODO(pthier): This Bytecode is unused. */ + +// Bytecodes generated by peephole optimization. These don't have a direct +// equivalent in the RegExpMacroAssembler. +// All peephole generated bytecodes should have a default implementation in +// RegExpMacroAssembler, that maps the optimized sequence back to the basic +// sequence they were created from. +// Format: V(CamelName, (OperandNames...), (OperandTypes...)) +#define PEEPHOLE_BYTECODE_LIST(V) \ /* Combination of: */ \ - /* LOAD_CURRENT_CHAR, CHECK_BIT_IN_TABLE and ADVANCE_CP_AND_GOTO */ \ - /* Emitted by RegExpBytecodePeepholeOptimization. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07 0x35 (fixed) Bytecode */ \ - /* 0x08 - 0x1F Load character offset from current position */ \ - /* 0x20 - 0x3F Number of characters to advance */ \ - /* 0x40 - 0xBF Bit Table */ \ - /* 0xC0 - 0xDF Address of bytecode when character is matched */ \ - /* 0xE0 - 0xFF Address of bytecode when no match */ \ - V(SKIP_UNTIL_BIT_IN_TABLE, 53, 32) \ + /* LoadCurrentCharacter, CheckBitInTable and AdvanceCpAndGoto */ \ + V(SkipUntilBitInTable, \ + (cp_offset, advance_by, table, on_match, on_no_match), \ + (ReBcOpType::kOffset, ReBcOpType::kOffset32, ReBcOpType::kBitTable, \ + ReBcOpType::kJumpTarget, ReBcOpType::kJumpTarget)) \ /* Combination of: */ \ - /* CHECK_CURRENT_POSITION, LOAD_CURRENT_CHAR_UNCHECKED, AND_CHECK_CHAR */ \ - /* and ADVANCE_CP_AND_GOTO */ \ - /* Emitted by RegExpBytecodePeepholeOptimization. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07 0x36 (fixed) Bytecode */ \ - /* 0x08 - 0x1F Load character offset from current position */ \ - /* 0x20 - 0x2F Number of characters to advance */ \ - /* 0x30 - 0x3F Character to match against (after mask applied) */ \ - /* 0x40 - 0x5F: Bitmask bitwise and combined with current character */ \ - /* 0x60 - 0x7F Minimum number of characters this pattern consumes */ \ - /* 0x80 - 0x9F Address of bytecode when character is matched */ \ - /* 0xA0 - 0xBF Address of bytecode when no match */ \ - V(SKIP_UNTIL_CHAR_AND, 54, 24) \ + /* CheckPosition, LoadCurrentCharacterUnchecked, CheckCharacterAfterAnd */ \ + /* and AdvanceCpAndGoto */ \ + /* TODO(pthier): mask should be kChar */ \ + /* TODO(pthier): eats_at_least should be Offset */ \ + V(SkipUntilCharAnd, \ + (cp_offset, advance_by, character, mask, eats_at_least, on_match, \ + on_no_match), \ + (ReBcOpType::kOffset, ReBcOpType::kOffset, ReBcOpType::kChar, \ + ReBcOpType::kUint32, ReBcOpType::kUint32, ReBcOpType::kJumpTarget, \ + ReBcOpType::kJumpTarget)) \ + /* Combination of: */ \ + /* LoadCurrentCharacter, CheckCharacter and AdvanceCpAndGoto */ \ + V(SkipUntilChar, (cp_offset, advance_by, character, on_match, on_no_match), \ + (ReBcOpType::kOffset, ReBcOpType::kOffset, ReBcOpType::kChar, \ + ReBcOpType::kJumpTarget, ReBcOpType::kJumpTarget)) \ /* Combination of: */ \ - /* LOAD_CURRENT_CHAR, CHECK_CHAR and ADVANCE_CP_AND_GOTO */ \ - /* Emitted by RegExpBytecodePeepholeOptimization. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07 0x37 (fixed) Bytecode */ \ - /* 0x08 - 0x1F Load character offset from current position */ \ - /* 0x20 - 0x2F Number of characters to advance */ \ - /* 0x30 - 0x3F Character to match */ \ - /* 0x40 - 0x5F Address of bytecode when character is matched */ \ - /* 0x60 - 0x7F Address of bytecode when no match */ \ - V(SKIP_UNTIL_CHAR, 55, 16) \ + /* CheckPosition, LoadCurrentCharacterUnchecked, CheckCharacter */ \ + /* and AdvanceCpAndGoto */ \ + V(SkipUntilCharPosChecked, \ + (cp_offset, advance_by, character, eats_at_least, on_match, on_no_match), \ + (ReBcOpType::kOffset, ReBcOpType::kOffset, ReBcOpType::kChar, \ + ReBcOpType::kUint32, ReBcOpType::kJumpTarget, ReBcOpType::kJumpTarget)) \ + /* TODO(pthier): eats_at_least should be Offset instead of Uint32 */ \ /* Combination of: */ \ - /* CHECK_CURRENT_POSITION, LOAD_CURRENT_CHAR_UNCHECKED, CHECK_CHAR */ \ - /* and ADVANCE_CP_AND_GOTO */ \ - /* Emitted by RegExpBytecodePeepholeOptimization. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07 0x38 (fixed) Bytecode */ \ - /* 0x08 - 0x1F Load character offset from current position */ \ - /* 0x20 - 0x2F Number of characters to advance */ \ - /* 0x30 - 0x3F Character to match */ \ - /* 0x40 - 0x5F Minimum number of characters this pattern consumes */ \ - /* 0x60 - 0x7F Address of bytecode when character is matched */ \ - /* 0x80 - 0x9F Address of bytecode when no match */ \ - V(SKIP_UNTIL_CHAR_POS_CHECKED, 56, 20) \ + /* LoadCurrentCharacter, CheckCharacter, CheckCharacter and */ \ + /* AdvanceCpAndGoto */ \ + V(SkipUntilCharOrChar, \ + (cp_offset, advance_by, padding, char1, char2, on_match, on_no_match), \ + (ReBcOpType::kOffset, ReBcOpType::kOffset, ReBcOpType::kPadding2, \ + ReBcOpType::kChar, ReBcOpType::kChar, ReBcOpType::kJumpTarget, \ + ReBcOpType::kJumpTarget)) \ + /* Combination of: */ \ + /* LoadCurrentCharacter, CheckCharacterGT, CheckBitInTable, GoTo and */ \ + /* AdvanceCpAndGoto */ \ + V(SkipUntilGtOrNotBitInTable, \ + (cp_offset, advance_by, character, table, on_match, on_no_match), \ + (ReBcOpType::kOffset, ReBcOpType::kOffset, ReBcOpType::kChar, \ + ReBcOpType::kBitTable, ReBcOpType::kJumpTarget, ReBcOpType::kJumpTarget)) \ /* Combination of: */ \ - /* LOAD_CURRENT_CHAR, CHECK_CHAR, CHECK_CHAR and ADVANCE_CP_AND_GOTO */ \ - /* Emitted by RegExpBytecodePeepholeOptimization. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07 0x39 (fixed) Bytecode */ \ - /* 0x08 - 0x1F Load character offset from current position */ \ - /* 0x20 - 0x3F Number of characters to advance */ \ - /* 0x40 - 0x4F Character to match */ \ - /* 0x50 - 0x5F Other Character to match */ \ - /* 0x60 - 0x7F Address of bytecode when either character is matched */ \ - /* 0x80 - 0x9F Address of bytecode when no match */ \ - V(SKIP_UNTIL_CHAR_OR_CHAR, 57, 20) \ + /* CheckPosition, Load4CurrentCharsUnchecked, AndCheck4Chars, */ \ + /* AdvanceCpAndGoto, AndCheck4Chars, AndCheckNot4Chars */ \ + /* This pattern is common for finding a match from an alternative with */ \ + /* few different characters. E.g. /[ab]bbbc|[de]eeef/. */ \ + V(SkipUntilOneOfMasked, \ + (cp_offset, advance_by, both_chars, both_mask, max_offset, chars1, mask1, \ + chars2, mask2, on_match1, on_match2, on_failure), \ + (ReBcOpType::kOffset, ReBcOpType::kOffset, ReBcOpType::kUint32, \ + ReBcOpType::kUint32, ReBcOpType::kOffset, ReBcOpType::kUint32, \ + ReBcOpType::kUint32, ReBcOpType::kUint32, ReBcOpType::kUint32, \ + ReBcOpType::kJumpTarget, ReBcOpType::kJumpTarget, \ + ReBcOpType::kJumpTarget)) \ /* Combination of: */ \ - /* LOAD_CURRENT_CHAR, CHECK_GT, CHECK_BIT_IN_TABLE, GOTO and */ \ - /* and ADVANCE_CP_AND_GOTO */ \ - /* Emitted by RegExpBytecodePeepholeOptimization. */ \ - /* Bit Layout: */ \ - /* 0x00 - 0x07 0x3A (fixed) Bytecode */ \ - /* 0x08 - 0x1F Load character offset from current position */ \ - /* 0x20 - 0x2F Number of characters to advance */ \ - /* 0x30 - 0x3F Character to check if it is less than current char */ \ - /* 0x40 - 0xBF Bit Table */ \ - /* 0xC0 - 0xDF Address of bytecode when character is matched */ \ - /* 0xE0 - 0xFF Address of bytecode when no match */ \ - V(SKIP_UNTIL_GT_OR_NOT_BIT_IN_TABLE, 58, 32) + /* SkipUntilBitInTable, CheckPosition, LoadCurrentCharacter, */ \ + /* CheckCharacterAfterAnd, AdvanceCurrentPosition, LoadCurrentCharacter, */ \ + /* CheckCharacterAfterAnd, CheckCharacterAfterAnd, */ \ + /* CheckNotCharacterAfterAnd. */ \ + /* This pattern is common for finding a match from an alternative, e.g.: */ \ + /* / +class RegExpBytecodeOperands; -static constexpr const char* const kRegExpBytecodeNames[] = { -#define DECLARE_BYTECODE_NAME(name, ...) #name, - BYTECODE_ITERATOR(DECLARE_BYTECODE_NAME) -#undef DECLARE_BYTECODE_NAME +class RegExpBytecodes final : public AllStatic { + public: + static constexpr int kCount = static_cast(RegExpBytecode::kLast) + 1; + static constexpr uint8_t ToByte(RegExpBytecode bc) { + return static_cast(bc); + } + static constexpr RegExpBytecode FromByte(uint8_t byte) { + DCHECK_LT(byte, kCount); + return static_cast(byte); + } + // Extract the bytecode from the given `ptr`, which must point at the + // word32-aligned region containing the bytecode (and maybe packed + // arguments). Endian-ness independent. + static constexpr RegExpBytecode FromPtr(const void* ptr) { + if (!std::is_constant_evaluated()) { + DCHECK(IsAligned(reinterpret_cast
(ptr), kUInt32Size)); + } + // Load the uint32_t value and implicitly cast to uint8_t. + return FromByte(*static_cast(ptr)); + } + + // Calls |f| templatized by RegExpBytecode. This allows the usage of the + // functions template argument in other templates. + // Example: + // RegExpBytecode bc = ; + // DispatchOnBytecode(bc, []() { DoFancyStuff(); }); + template + static decltype(auto) DispatchOnBytecode(RegExpBytecode bytecode, Func&& f); + + static constexpr const char* Name(RegExpBytecode bytecode); + static constexpr const char* Name(uint8_t bytecode); + + static constexpr uint8_t Size(RegExpBytecode bytecode); + static constexpr uint8_t Size(uint8_t bytecode); }; -inline constexpr const char* RegExpBytecodeName(int bytecode) { - DCHECK(base::IsInRange(bytecode, 0, kRegExpBytecodeCount - 1)); - return kRegExpBytecodeNames[bytecode]; -} - void RegExpBytecodeDisassembleSingle(const uint8_t* code_base, const uint8_t* pc); void RegExpBytecodeDisassemble(const uint8_t* code_base, int length, const char* pattern); diff --git a/js/src/irregexp/imported/regexp-bytecodes.cc b/js/src/irregexp/imported/regexp-bytecodes.cc --- a/js/src/irregexp/imported/regexp-bytecodes.cc +++ b/js/src/irregexp/imported/regexp-bytecodes.cc @@ -4,27 +4,29 @@ #include "irregexp/imported/regexp-bytecodes.h" #include +#include "irregexp/imported/regexp-bytecodes-inl.h" namespace v8 { namespace internal { void RegExpBytecodeDisassembleSingle(const uint8_t* code_base, const uint8_t* pc) { - int bytecode = *reinterpret_cast(pc) & BYTECODE_MASK; - PrintF("%s", RegExpBytecodeName(bytecode)); + // TODO(jgruber): Now that we know about operand types, improve printing. + RegExpBytecode bytecode = RegExpBytecodes::FromPtr(pc); + PrintF("%s", RegExpBytecodes::Name(bytecode)); // Args and the bytecode as hex. - for (int i = 0; i < RegExpBytecodeLength(bytecode); i++) { + for (int i = 0; i < RegExpBytecodes::Size(bytecode); i++) { PrintF(", %02x", pc[i]); } PrintF(" "); // Args as ascii. - for (int i = 1; i < RegExpBytecodeLength(bytecode); i++) { + for (int i = 1; i < RegExpBytecodes::Size(bytecode); i++) { unsigned char b = pc[i]; PrintF("%c", std::isprint(b) ? b : '.'); } PrintF("\n"); } @@ -33,15 +35,16 @@ const char* pattern) { PrintF("[generated bytecode for regexp pattern: '%s']\n", pattern); ptrdiff_t offset = 0; + // TODO(pthier): Consider using the RegExpBytecodeIterator. while (offset < length) { const uint8_t* const pc = code_base + offset; PrintF("%p %4" V8PRIxPTRDIFF " ", pc, offset); RegExpBytecodeDisassembleSingle(code_base, pc); - offset += RegExpBytecodeLength(*pc); + offset += RegExpBytecodes::Size(RegExpBytecodes::FromPtr(pc)); } } } // namespace internal } // namespace v8 diff --git a/js/src/irregexp/imported/regexp-code-generator.h b/js/src/irregexp/imported/regexp-code-generator.h new file mode 100644 --- /dev/null +++ b/js/src/irregexp/imported/regexp-code-generator.h @@ -0,0 +1,82 @@ +// Copyright 2025 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_CODE_GENERATOR_H_ +#define V8_REGEXP_REGEXP_CODE_GENERATOR_H_ + +#include "irregexp/imported/regexp-bytecode-iterator.h" +#include "irregexp/imported/regexp-bytecodes.h" +#include "irregexp/imported/regexp-error.h" +#include "irregexp/imported/regexp-macro-assembler.h" + +namespace v8 { +namespace internal { + +class RegExpCodeGenerator final { + public: + RegExpCodeGenerator(Isolate* isolate, RegExpMacroAssembler* masm, + DirectHandle bytecode); + + struct Result final { + explicit Result(DirectHandle code) : code_(code) {} + + static Result UnsupportedBytecode() { + return Result(RegExpError::kUnsupportedBytecode); + } + + bool Succeeded() const { return error_ == RegExpError::kNone; } + RegExpError error() const { return error_; } + DirectHandle code() const { return code_; } + + private: + explicit Result(RegExpError err) : error_(err) {} + + RegExpError error_ = RegExpError::kNone; + DirectHandle code_; + }; + + V8_NODISCARD Result Assemble(DirectHandle source, RegExpFlags flags); + + private: + // Returns the value for |operand_id| of the current bytecode in the format + // expected by the macro assembler. + // E.g. converts an uint32_t bytecode offset to a Label*. + template + auto GetArgumentValue(); + + // Returns all the argument values of the current bytecode as a tuple. + template + auto GetArgumentValuesAsTuple(); + + // Visit all bytecodes before any code is emmited. + // Allocates labels for all jump targets to support forward jumps. + void PreVisitBytecodes(); + void VisitBytecodes(); + template + void Visit(); + Label* GetLabel(uint32_t offset) const; + MacroAssembler* NativeMasm(); + + Isolate* isolate_; + Zone zone_; + RegExpMacroAssembler* masm_; + DirectHandle bytecode_; + RegExpBytecodeIterator iter_; + // Zone allocated Array of Labels for each offset. Access is only valid for + // offsets that are jump targets (indicated by jump_targets_). + Label* labels_; + // BitVector indicating if a specific offset is a valid jump target. + // Labels are allocated for all offsets that are jump targets. + BitVector jump_targets_; + // BitVector indicating if a specific offset is an indirect jump target. + // Indirect Jump Targets are all targets of `PushBacktrack`. + // This is required for CFI. + BitVector indirect_jump_targets_; + bool has_unsupported_bytecode_; +}; + +} // namespace internal +} // namespace v8 + +#endif // V8_REGEXP_REGEXP_CODE_GENERATOR_H_ diff --git a/js/src/irregexp/imported/regexp-code-generator.cc b/js/src/irregexp/imported/regexp-code-generator.cc new file mode 100644 --- /dev/null +++ b/js/src/irregexp/imported/regexp-code-generator.cc @@ -0,0 +1,549 @@ +// Copyright 2025 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 "irregexp/imported/regexp-code-generator.h" + +#include +#include +#include +#include + +#include "irregexp/imported/regexp-bytecode-iterator-inl.h" +#include "irregexp/imported/regexp-bytecodes-inl.h" + +namespace v8 { +namespace internal { + +#define __ masm_-> + +RegExpCodeGenerator::RegExpCodeGenerator( + Isolate* isolate, RegExpMacroAssembler* masm, + DirectHandle bytecode) + : isolate_(isolate), + zone_(isolate_->allocator(), ZONE_NAME), + masm_(masm), + bytecode_(bytecode), + iter_(bytecode_), + labels_(zone_.AllocateArray