Source code
Revision control
Copy as Markdown
Other Tools
// Copyright 2019 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-peephole.h"
#include "irregexp/imported/regexp-bytecodes.h"
namespace v8 {
namespace internal {
namespace {
struct BytecodeArgument {
int offset;
int length;
BytecodeArgument(int offset, int length) : offset(offset), length(length) {}
};
struct BytecodeArgumentMapping : BytecodeArgument {
int new_length;
BytecodeArgumentMapping(int offset, int length, int new_length)
: BytecodeArgument(offset, length), new_length(new_length) {}
};
struct BytecodeArgumentCheck : BytecodeArgument {
enum CheckType { kCheckAddress = 0, kCheckValue };
CheckType type;
int check_offset;
int check_length;
BytecodeArgumentCheck(int offset, int length, int check_offset)
: BytecodeArgument(offset, length),
type(kCheckAddress),
check_offset(check_offset) {}
BytecodeArgumentCheck(int offset, int length, int check_offset,
int check_length)
: BytecodeArgument(offset, length),
type(kCheckValue),
check_offset(check_offset),
check_length(check_length) {}
};
// 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);
// Adds a new node as child of the current node if it isn't a child already.
BytecodeSequenceNode& FollowedBy(int bytecode);
// Marks the end of a sequence and sets optimized bytecode to replace all
// bytecodes of the sequence with.
BytecodeSequenceNode& ReplaceWith(int 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()).
// bytecode_index_in_sequence: Zero-based index of the referred bytecode
// within the sequence (e.g. the bytecode passed to CreateSequence() has
// index 0).
// 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).
// argument_byte_length: Length of the argument.
// new_argument_byte_length: Length of the argument in the new bytecode
// (= 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);
// 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).
// argument_byte_length: Length of the argument.
// check_byte_offset: Zero-based offset relative to the beginning of the
// sequence that needs to match the value given by argument_offset. (e.g.
// check_byte_offset 0 matches the address of the first bytecode in the
// sequence).
BytecodeSequenceNode& IfArgumentEqualsOffset(int argument_offset,
int argument_byte_length,
int check_byte_offset);
// 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
// argument of another bytecode in the sequence.
// This is similar to IfArgumentEqualsOffset, except that this method matches
// the values of both arguments.
BytecodeSequenceNode& IfArgumentEqualsValueAtOffset(
int argument_offset, int argument_byte_length,
int other_bytecode_index_in_sequence, int other_argument_offset,
int other_argument_byte_length);
// Marks an argument as unused.
// All arguments that are not mapped explicitly have to be marked as unused.
// bytecode_index_in_sequence: Zero-based index of the referred bytecode
// within the sequence (e.g. the bytecode passed to CreateSequence() has
// index 0).
// 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).
// argument_byte_length: Length of the argument.
BytecodeSequenceNode& IgnoreArgument(int bytecode_index_in_sequence,
int argument_offset,
int argument_byte_length);
// Checks if the current node is valid for the sequence. I.e. all conditions
// set by IfArgumentEqualsOffset and IfArgumentEquals are fulfilled by this
// node for the actual bytecode sequence.
bool CheckArguments(const uint8_t* bytecode, int pc);
// 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 child of the current node matching the given bytecode or
// nullptr if no such child is found.
BytecodeSequenceNode* Find(int 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.
// Invoking this method is only allowed on nodes that mark the end of a valid
// sequence (i.e. if IsSequence())
BytecodeArgumentMapping ArgumentMapping(size_t index) const;
// Returns an iterator to begin of ignored arguments.
// Invoking this method is only allowed on nodes that mark the end of a valid
// sequence (i.e. if IsSequence())
ZoneLinkedList<BytecodeArgument>::iterator ArgumentIgnoredBegin() const;
// Returns an iterator to end of ignored arguments.
// Invoking this method is only allowed on nodes that mark the end of a valid
// sequence (i.e. if IsSequence())
ZoneLinkedList<BytecodeArgument>::iterator ArgumentIgnoredEnd() const;
// Returns whether the current node has ignored argument or not.
bool HasIgnoredArguments() const;
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_;
int index_in_sequence_;
int start_offset_;
BytecodeSequenceNode* parent_;
ZoneUnorderedMap<int, BytecodeSequenceNode*> children_;
ZoneVector<BytecodeArgumentMapping>* argument_mapping_;
ZoneLinkedList<BytecodeArgumentCheck>* argument_check_;
ZoneLinkedList<BytecodeArgument>* 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<int, int>& jump_edges);
// Parses bytecode and fills the internal buffer with the potentially
// optimized bytecode. Returns true when optimizations were performed, false
// otherwise.
bool OptimizeBytecode(const uint8_t* bytecode, int length);
// Copies the internal bytecode buffer to another buffer. The caller is
// responsible for allocating/freeing the memory.
void CopyOptimizedBytecode(uint8_t* to_address) const;
int Length() const;
private:
// Sets up all sequences that are going to be used.
void DefineStandardSequences();
// Starts a new bytecode sequence.
BytecodeSequenceNode& CreateSequence(int 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
// start of the sequence in bytecode and last_node is the last
// BytecodeSequenceNode of the matching sequence found.
void EmitOptimization(int start_pc, const uint8_t* bytecode,
const BytecodeSequenceNode& last_node);
// Adds a relative jump source fixup at pos.
// Jump source fixups are used to find offsets in the new bytecode that
// contain jump sources.
void AddJumpSourceFixup(int fixup, int pos);
// Adds a relative jump destination fixup at pos.
// Jump destination fixups are used to find offsets in the new bytecode that
// can be jumped to.
void AddJumpDestinationFixup(int fixup, int pos);
// Sets an absolute jump destination fixup at pos.
void SetJumpDestinationFixup(int fixup, int pos);
// Prepare internal structures used to fixup jumps.
void PrepareJumpStructures(const ZoneUnorderedMap<int, int>& jump_edges);
// Updates all jump targets in the new bytecode.
void FixJumps();
// Update a single jump.
void FixJump(int jump_source, int jump_destination);
void AddSentinelFixups(int pos);
template <typename T>
void EmitValue(T value);
template <typename T>
void OverwriteValue(int offset, T value);
void CopyRangeToOutput(const uint8_t* orig_bytecode, int start, int length);
void SetRange(uint8_t value, int count);
void EmitArgument(int start_pc, const uint8_t* bytecode,
BytecodeArgumentMapping arg);
int pc() const;
Zone* zone() const;
ZoneVector<uint8_t> optimized_bytecode_buffer_;
BytecodeSequenceNode* sequences_;
// Jumps used in old bytecode.
// Key: Jump source (offset where destination is stored in old bytecode)
// Value: Destination
ZoneMap<int, int> jump_edges_;
// Jumps used in new bytecode.
// Key: Jump source (offset where destination is stored in new bytecode)
// Value: Destination
ZoneMap<int, int> jump_edges_mapped_;
// Number of times a jump destination is used within the bytecode.
// Key: Jump destination (offset in old bytecode).
// Value: Number of times jump destination is used.
ZoneMap<int, int> jump_usage_counts_;
// Maps offsets in old bytecode to fixups of sources (delta to new bytecode).
// Key: Offset in old bytecode from where the fixup is valid.
// Value: Delta to map jump source from old bytecode to new bytecode in bytes.
ZoneMap<int, int> jump_source_fixups_;
// Maps offsets in old bytecode to fixups of destinations (delta to new
// bytecode).
// Key: Offset in old bytecode from where the fixup is valid.
// Value: Delta to map jump destinations from old bytecode to new bytecode in
// bytes.
ZoneMap<int, int> jump_destination_fixups_;
Zone* zone_;
DISALLOW_IMPLICIT_CONSTRUCTORS(RegExpBytecodePeephole);
};
template <typename T>
T GetValue(const uint8_t* buffer, int pos) {
DCHECK(IsAligned(reinterpret_cast<Address>(buffer + pos), alignof(T)));
return *reinterpret_cast<const T*>(buffer + pos);
}
int32_t GetArgumentValue(const uint8_t* bytecode, int offset, int length) {
switch (length) {
case 1:
return GetValue<uint8_t>(bytecode, offset);
case 2:
return GetValue<int16_t>(bytecode, offset);
case 4:
return GetValue<int32_t>(bytecode, offset);
default:
UNREACHABLE();
}
}
BytecodeSequenceNode::BytecodeSequenceNode(int bytecode, Zone* zone)
: bytecode_(bytecode),
bytecode_replacement_(kDummyBytecode),
index_in_sequence_(0),
start_offset_(0),
parent_(nullptr),
children_(ZoneUnorderedMap<int, BytecodeSequenceNode*>(zone)),
argument_mapping_(zone->New<ZoneVector<BytecodeArgumentMapping>>(zone)),
argument_check_(zone->New<ZoneLinkedList<BytecodeArgumentCheck>>(zone)),
argument_ignored_(zone->New<ZoneLinkedList<BytecodeArgument>>(zone)),
zone_(zone) {}
BytecodeSequenceNode& BytecodeSequenceNode::FollowedBy(int bytecode) {
DCHECK(0 <= bytecode && bytecode < kRegExpBytecodeCount);
if (children_.find(bytecode) == children_.end()) {
BytecodeSequenceNode* new_node =
zone()->New<BytecodeSequenceNode>(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_);
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);
bytecode_replacement_ = bytecode;
return *this;
}
BytecodeSequenceNode& BytecodeSequenceNode::MapArgument(
int bytecode_index_in_sequence, int argument_offset,
int argument_byte_length, int new_argument_byte_length) {
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_));
int absolute_offset = ref_node.start_offset_ + argument_offset;
if (new_argument_byte_length == 0) {
new_argument_byte_length = argument_byte_length;
}
argument_mapping_->push_back(BytecodeArgumentMapping{
absolute_offset, argument_byte_length, new_argument_byte_length});
return *this;
}
BytecodeSequenceNode& BytecodeSequenceNode::IfArgumentEqualsOffset(
int argument_offset, int argument_byte_length, int check_byte_offset) {
DCHECK_LT(argument_offset, RegExpBytecodeLength(bytecode_));
DCHECK(argument_byte_length == 1 || argument_byte_length == 2 ||
argument_byte_length == 4);
int absolute_offset = start_offset_ + argument_offset;
argument_check_->push_back(BytecodeArgumentCheck{
absolute_offset, argument_byte_length, check_byte_offset});
return *this;
}
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_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_));
int absolute_offset = start_offset_ + argument_offset;
int other_absolute_offset = ref_node.start_offset_ + other_argument_offset;
argument_check_->push_back(
BytecodeArgumentCheck{absolute_offset, argument_byte_length,
other_absolute_offset, other_argument_byte_length});
return *this;
}
BytecodeSequenceNode& BytecodeSequenceNode::IgnoreArgument(
int bytecode_index_in_sequence, int argument_offset,
int argument_byte_length) {
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_));
int absolute_offset = ref_node.start_offset_ + argument_offset;
argument_ignored_->push_back(
BytecodeArgument{absolute_offset, argument_byte_length});
return *this;
}
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);
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);
is_valid &= value == other_value;
} else {
UNREACHABLE();
}
}
return is_valid;
}
bool BytecodeSequenceNode::IsSequence() const {
return bytecode_replacement_ != kDummyBytecode;
}
int BytecodeSequenceNode::SequenceLength() const {
return start_offset_ + RegExpBytecodeLength(bytecode_);
}
int BytecodeSequenceNode::OptimizedBytecode() const {
return bytecode_replacement_;
}
BytecodeSequenceNode* BytecodeSequenceNode::Find(int bytecode) const {
auto found = children_.find(bytecode);
if (found == children_.end()) return nullptr;
return found->second;
}
size_t BytecodeSequenceNode::ArgumentSize() const {
DCHECK(IsSequence());
return argument_mapping_->size();
}
BytecodeArgumentMapping BytecodeSequenceNode::ArgumentMapping(
size_t index) const {
DCHECK(IsSequence());
DCHECK(argument_mapping_ != nullptr);
DCHECK_LT(index, argument_mapping_->size());
return argument_mapping_->at(index);
}
ZoneLinkedList<BytecodeArgument>::iterator
BytecodeSequenceNode::ArgumentIgnoredBegin() const {
DCHECK(IsSequence());
DCHECK(argument_ignored_ != nullptr);
return argument_ignored_->begin();
}
ZoneLinkedList<BytecodeArgument>::iterator
BytecodeSequenceNode::ArgumentIgnoredEnd() const {
DCHECK(IsSequence());
DCHECK(argument_ignored_ != nullptr);
return argument_ignored_->end();
}
bool BytecodeSequenceNode::HasIgnoredArguments() const {
return argument_ignored_ != nullptr;
}
BytecodeSequenceNode& BytecodeSequenceNode::GetNodeByIndexInSequence(
int index_in_sequence) {
DCHECK_LE(index_in_sequence, index_in_sequence_);
if (index_in_sequence < index_in_sequence_) {
DCHECK(parent_ != nullptr);
return parent_->GetNodeByIndexInSequence(index_in_sequence);
} else {
return *this;
}
}
Zone* BytecodeSequenceNode::zone() const { return zone_; }
RegExpBytecodePeephole::RegExpBytecodePeephole(
Zone* zone, size_t buffer_size,
const ZoneUnorderedMap<int, int>& jump_edges)
: optimized_bytecode_buffer_(zone),
sequences_(zone->New<BytecodeSequenceNode>(
BytecodeSequenceNode::kDummyBytecode, zone)),
jump_edges_(zone),
jump_edges_mapped_(zone),
jump_usage_counts_(zone),
jump_source_fixups_(zone),
jump_destination_fixups_(zone),
zone_(zone) {
optimized_bytecode_buffer_.reserve(buffer_size);
PrepareJumpStructures(jump_edges);
DefineStandardSequences();
// Sentinel fixups at beginning of bytecode (position -1) so we don't have to
// check for end of iterator inside the fixup loop.
// In general fixups are deltas of original offsets of jump
// sources/destinations (in the old bytecode) to find them in the new
// bytecode. All jump targets are fixed after the new bytecode is fully
// emitted in the internal buffer.
AddSentinelFixups(-1);
// Sentinel fixups at end of (old) bytecode so we don't have to check for
// end of iterator inside the fixup loop.
DCHECK_LE(buffer_size, std::numeric_limits<int>::max());
AddSentinelFixups(static_cast<int>(buffer_size));
}
void RegExpBytecodePeephole::DefineStandardSequences() {
// 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
// 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
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
// 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
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
// 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
// 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
// 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)
.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
// 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
}
bool RegExpBytecodePeephole::OptimizeBytecode(const uint8_t* bytecode,
int length) {
int old_pc = 0;
bool did_optimize = false;
while (old_pc < length) {
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);
CopyRangeToOutput(bytecode, old_pc, bc_len);
old_pc += bc_len;
}
}
if (did_optimize) {
FixJumps();
}
return did_optimize;
}
void RegExpBytecodePeephole::CopyOptimizedBytecode(uint8_t* to_address) const {
MemCopy(to_address, &(*optimized_bytecode_buffer_.begin()), Length());
}
int RegExpBytecodePeephole::Length() const { return pc(); }
BytecodeSequenceNode& RegExpBytecodePeephole::CreateSequence(int bytecode) {
DCHECK(sequences_ != nullptr);
DCHECK(0 <= bytecode && bytecode < kRegExpBytecodeCount);
return sequences_->FollowedBy(bytecode);
}
int RegExpBytecodePeephole::TryOptimizeSequence(const uint8_t* bytecode,
int bytecode_length,
int start_pc) {
BytecodeSequenceNode* seq_node = sequences_;
BytecodeSequenceNode* valid_seq_end = nullptr;
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]);
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]);
}
if (valid_seq_end) {
EmitOptimization(start_pc, bytecode, *valid_seq_end);
return valid_seq_end->SequenceLength();
}
return 0;
}
void RegExpBytecodePeephole::EmitOptimization(
int start_pc, const uint8_t* bytecode,
const BytecodeSequenceNode& last_node) {
#ifdef DEBUG
int optimized_start_pc = pc();
#endif
// 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<int> delete_jumps = ZoneLinkedList<int>(zone());
uint32_t bc = last_node.OptimizedBytecode();
EmitValue(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;
}
// 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()));
// 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);
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);
// 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;
}
}
}
int fixup_length = RegExpBytecodeLength(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;
int jump_candidate_count = jump_destination_candidate->second;
// Jump destinations only jumped to from inside the sequence will be ignored.
while (jump_destination_candidate != jump_usage_counts_.end() &&
jump_candidate_count == 0) {
++jump_destination_candidate;
jump_candidate_destination = jump_destination_candidate->first;
jump_candidate_count = jump_destination_candidate->second;
}
int preserve_from = start_pc + last_node.SequenceLength();
if (jump_destination_candidate != jump_usage_counts_.end() &&
jump_candidate_destination < start_pc + last_node.SequenceLength()) {
preserve_from = jump_candidate_destination;
// Check if any jump in the sequence we are preserving has a jump
// destination inside the optimized sequence before the current position we
// want to preserve. If so we have to preserve all bytecodes starting at
// this jump destination.
for (auto jump_iter = jump_edges_.lower_bound(preserve_from);
jump_iter != jump_edges_.end() &&
jump_iter->first /* jump source */ <
start_pc + last_node.SequenceLength();
++jump_iter) {
int jump_destination = jump_iter->second;
if (jump_destination > start_pc && jump_destination < preserve_from) {
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
// 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,
start_pc + last_node.SequenceLength() - preserve_length);
// All jump targets after the start of the optimized sequence need to be
// fixed relative to the length of the optimized sequence including
// bytecodes we preserved.
AddJumpDestinationFixup(fixup_length, start_pc + 1);
// Jumps to the sequence we preserved need absolute fixup as they could
// occur before or after the sequence.
SetJumpDestinationFixup(pc() - preserve_from, preserve_from);
CopyRangeToOutput(bytecode, preserve_from, preserve_length);
} else {
AddJumpDestinationFixup(fixup_length, start_pc + 1);
// Jumps after the end of the old sequence need fixup.
AddJumpSourceFixup(fixup_length, start_pc + last_node.SequenceLength());
}
// Delete jumps we definitely don't need anymore
for (int del : delete_jumps) {
if (del < preserve_from) {
jump_edges_.erase(del);
}
}
}
void RegExpBytecodePeephole::AddJumpSourceFixup(int fixup, int pos) {
auto previous_fixup = jump_source_fixups_.lower_bound(pos);
DCHECK(previous_fixup != jump_source_fixups_.end());
DCHECK(previous_fixup != jump_source_fixups_.begin());
int previous_fixup_value = (--previous_fixup)->second;
jump_source_fixups_[pos] = previous_fixup_value + fixup;
}
void RegExpBytecodePeephole::AddJumpDestinationFixup(int fixup, int pos) {
auto previous_fixup = jump_destination_fixups_.lower_bound(pos);
DCHECK(previous_fixup != jump_destination_fixups_.end());
DCHECK(previous_fixup != jump_destination_fixups_.begin());
int previous_fixup_value = (--previous_fixup)->second;
jump_destination_fixups_[pos] = previous_fixup_value + fixup;
}
void RegExpBytecodePeephole::SetJumpDestinationFixup(int fixup, int pos) {
auto previous_fixup = jump_destination_fixups_.lower_bound(pos);
DCHECK(previous_fixup != jump_destination_fixups_.end());
DCHECK(previous_fixup != jump_destination_fixups_.begin());
int previous_fixup_value = (--previous_fixup)->second;
jump_destination_fixups_.emplace(pos, fixup);
jump_destination_fixups_.emplace(pos + 1, previous_fixup_value);
}
void RegExpBytecodePeephole::PrepareJumpStructures(
const ZoneUnorderedMap<int, int>& jump_edges) {
for (auto jump_edge : jump_edges) {
int jump_source = jump_edge.first;
int jump_destination = jump_edge.second;
jump_edges_.emplace(jump_source, jump_destination);
jump_usage_counts_[jump_destination]++;
}
}
void RegExpBytecodePeephole::FixJumps() {
int position_fixup = 0;
// Next position where fixup changes.
auto next_source_fixup = jump_source_fixups_.lower_bound(0);
int next_source_fixup_offset = next_source_fixup->first;
int next_source_fixup_value = next_source_fixup->second;
for (auto jump_edge : jump_edges_) {
int jump_source = jump_edge.first;
int jump_destination = jump_edge.second;
while (jump_source >= next_source_fixup_offset) {
position_fixup = next_source_fixup_value;
++next_source_fixup;
next_source_fixup_offset = next_source_fixup->first;
next_source_fixup_value = next_source_fixup->second;
}
jump_source += position_fixup;
FixJump(jump_source, jump_destination);
}
// Mapped jump edges don't need source fixups, as the position already is an
// offset in the new bytecode.
for (auto jump_edge : jump_edges_mapped_) {
int jump_source = jump_edge.first;
int jump_destination = jump_edge.second;
FixJump(jump_source, jump_destination);
}
}
void RegExpBytecodePeephole::FixJump(int jump_source, int jump_destination) {
int fixed_jump_destination =
jump_destination +
(--jump_destination_fixups_.upper_bound(jump_destination))->second;
DCHECK_LT(fixed_jump_destination, Length());
#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);
#endif
if (jump_destination != fixed_jump_destination) {
OverwriteValue<uint32_t>(jump_source, fixed_jump_destination);
}
}
void RegExpBytecodePeephole::AddSentinelFixups(int pos) {
jump_source_fixups_.emplace(pos, 0);
jump_destination_fixups_.emplace(pos, 0);
}
template <typename T>
void RegExpBytecodePeephole::EmitValue(T value) {
DCHECK(optimized_bytecode_buffer_.begin() + pc() ==
optimized_bytecode_buffer_.end());
uint8_t* value_byte_iter = reinterpret_cast<uint8_t*>(&value);
optimized_bytecode_buffer_.insert(optimized_bytecode_buffer_.end(),
value_byte_iter,
value_byte_iter + sizeof(T));
}
template <typename T>
void RegExpBytecodePeephole::OverwriteValue(int offset, T value) {
uint8_t* value_byte_iter = reinterpret_cast<uint8_t*>(&value);
uint8_t* value_byte_iter_end = value_byte_iter + sizeof(T);
while (value_byte_iter < value_byte_iter_end) {
optimized_bytecode_buffer_[offset++] = *value_byte_iter++;
}
}
void RegExpBytecodePeephole::CopyRangeToOutput(const uint8_t* orig_bytecode,
int start, int length) {
DCHECK(optimized_bytecode_buffer_.begin() + pc() ==
optimized_bytecode_buffer_.end());
optimized_bytecode_buffer_.insert(optimized_bytecode_buffer_.end(),
orig_bytecode + start,
orig_bytecode + start + length);
}
void RegExpBytecodePeephole::SetRange(uint8_t value, int count) {
DCHECK(optimized_bytecode_buffer_.begin() + pc() ==
optimized_bytecode_buffer_.end());
optimized_bytecode_buffer_.insert(optimized_bytecode_buffer_.end(), count,
value);
}
void RegExpBytecodePeephole::EmitArgument(int start_pc, const uint8_t* bytecode,
BytecodeArgumentMapping arg) {
int arg_pos = start_pc + arg.offset;
switch (arg.length) {
case 1:
DCHECK_EQ(arg.new_length, arg.length);
EmitValue(GetValue<uint8_t>(bytecode, arg_pos));
break;
case 2:
DCHECK_EQ(arg.new_length, arg.length);
EmitValue(GetValue<uint16_t>(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<int32_t>(bytecode, arg_pos - 1) >> kBitsPerByte;
#endif // V8_TARGET_BIG_ENDIAN
switch (arg.new_length) {
case 2:
EmitValue<uint16_t>(val);
break;
case 3: {
// Pack with previously emitted value.
auto prev_val =
GetValue<int32_t>(&(*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<uint32_t>(
pc() - sizeof(uint32_t),
(static_cast<uint32_t>(val) << 8) | (prev_val & 0xFF));
#endif // V8_TARGET_BIG_ENDIAN
break;
}
case 4:
EmitValue<uint32_t>(val);
break;
}
break;
}
case 4:
DCHECK_EQ(arg.new_length, arg.length);
EmitValue(GetValue<uint32_t>(bytecode, arg_pos));
break;
case 8:
DCHECK_EQ(arg.new_length, arg.length);
EmitValue(GetValue<uint64_t>(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);
}
break;
}
}
int RegExpBytecodePeephole::pc() const {
DCHECK_LE(optimized_bytecode_buffer_.size(), std::numeric_limits<int>::max());
return static_cast<int>(optimized_bytecode_buffer_.size());
}
Zone* RegExpBytecodePeephole::zone() const { return zone_; }
} // namespace
// static
Handle<TrustedByteArray> RegExpBytecodePeepholeOptimization::OptimizeBytecode(
Isolate* isolate, Zone* zone, DirectHandle<String> source,
const uint8_t* bytecode, int length,
const ZoneUnorderedMap<int, int>& jump_edges) {
RegExpBytecodePeephole peephole(zone, length, jump_edges);
bool did_optimize = peephole.OptimizeBytecode(bytecode, length);
Handle<TrustedByteArray> array =
isolate->factory()->NewTrustedByteArray(peephole.Length());
peephole.CopyOptimizedBytecode(array->begin());
if (did_optimize && v8_flags.trace_regexp_peephole_optimization) {
PrintF("Original Bytecode:\n");
RegExpBytecodeDisassemble(bytecode, length, source->ToCString().get());
PrintF("Optimized Bytecode:\n");
RegExpBytecodeDisassemble(array->begin(), peephole.Length(),
source->ToCString().get());
}
return array;
}
} // namespace internal
} // namespace v8