Issue #1677 - Part 1: Import new V8 regexp code with Mozilla's header modifications

1 files changed, 1029 insertions, 0 deletions

diff --git a/js/src/regexp/regexp-bytecode-peephole.cc b/js/src/regexp/regexp-bytecode-peephole.cc
new file mode 100644
index 000000000..2bc1b5aa2
--- /dev/null
+++ b/js/src/regexp/regexp-bytecode-peephole.cc
@@ -0,0 +1,1029 @@
+// 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 "regexp/regexp-bytecode-peephole.h"
+
+#include "regexp/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 byte* 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_;
+};
+
+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 byte* bytecode, int length);
+  // Copies the internal bytecode buffer to another buffer. The caller is
+  // responsible for allocating/freeing the memory.
+  void CopyOptimizedBytecode(byte* 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 byte* bytecode, 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 byte* 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 byte* orig_bytecode, int start, int length);
+  void SetRange(byte value, int count);
+  void EmitArgument(int start_pc, const byte* bytecode,
+                    BytecodeArgumentMapping arg);
+  int pc() const;
+  Zone* zone() const;
+
+  ZoneVector<byte> 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 byte* buffer, int pos) {
+  DCHECK(IsAligned(reinterpret_cast<Address>(buffer + pos), alignof(T)));
+  return *reinterpret_cast<const T*>(buffer + pos);
+}
+
+int32_t GetArgumentValue(const byte* bytecode, int offset, int length) {
+  switch (length) {
+    case 1:
+      return GetValue<byte>(bytecode, offset);
+      break;
+    case 2:
+      return GetValue<int16_t>(bytecode, offset);
+      break;
+    case 4:
+      return GetValue<int32_t>(bytecode, offset);
+      break;
+    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_(new (zone->New(sizeof(*argument_mapping_)))
+                            ZoneVector<BytecodeArgumentMapping>(zone)),
+      argument_check_(new (zone->New(sizeof(*argument_check_)))
+                          ZoneLinkedList<BytecodeArgumentCheck>(zone)),
+      argument_ignored_(new (zone->New(sizeof(*argument_ignored_)))
+                            ZoneLinkedList<BytecodeArgument>(zone)),
+      zone_(zone) {}
+
+BytecodeSequenceNode& BytecodeSequenceNode::FollowedBy(int bytecode) {
+  DCHECK(0 <= bytecode && bytecode < kRegExpBytecodeCount);
+
+  if (children_.find(bytecode) == children_.end()) {
+    BytecodeSequenceNode* new_node =
+        new (zone()->New(sizeof(BytecodeSequenceNode)))
+            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 byte* 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_GE(index, 0);
+  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_(new (zone->New(sizeof(*sequences_))) 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 byte* bytecode,
+                                              int length) {
+  int old_pc = 0;
+  bool did_optimize = false;
+
+  while (old_pc < length) {
+    int replaced_len = TryOptimizeSequence(bytecode, 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(byte* 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 byte* bytecode,
+                                                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 ((seq_node = seq_node->Find(bytecode[current_pc]))) {
+    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 byte* 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.
+  byte 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());
+  byte* value_byte_iter = reinterpret_cast<byte*>(&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) {
+  byte* value_byte_iter = reinterpret_cast<byte*>(&value);
+  byte* 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 byte* 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(byte 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 byte* bytecode,
+                                          BytecodeArgumentMapping arg) {
+  int arg_pos = start_pc + arg.offset;
+  switch (arg.length) {
+    case 1:
+      DCHECK_EQ(arg.new_length, arg.length);
+      EmitValue(GetValue<byte>(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, 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<ByteArray> RegExpBytecodePeepholeOptimization::OptimizeBytecode(
+    Isolate* isolate, Zone* zone, Handle<String> source, const byte* bytecode,
+    int length, const ZoneUnorderedMap<int, int>& jump_edges) {
+  RegExpBytecodePeephole peephole(zone, length, jump_edges);
+  bool did_optimize = peephole.OptimizeBytecode(bytecode, length);
+  Handle<ByteArray> array = isolate->factory()->NewByteArray(peephole.Length());
+  peephole.CopyOptimizedBytecode(array->GetDataStartAddress());
+
+  if (did_optimize && FLAG_trace_regexp_peephole_optimization) {
+    PrintF("Original Bytecode:\n");
+    RegExpBytecodeDisassemble(bytecode, length, source->ToCString().get());
+    PrintF("Optimized Bytecode:\n");
+    RegExpBytecodeDisassemble(array->GetDataStartAddress(), peephole.Length(),
+                              source->ToCString().get());
+  }
+
+  return array;
+}
+
+}  // namespace internal
+}  // namespace v8