path: root/js/src/regexp/regexp-bytecode-peephole.cc

// 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_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