1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- 2 * vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 4 // Copyright 2012 the V8 project authors. All rights reserved. 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are 7 // met: 8 // 9 // * Redistributions of source code must retain the above copyright 10 // notice, this list of conditions and the following disclaimer. 11 // * Redistributions in binary form must reproduce the above 12 // copyright notice, this list of conditions and the following 13 // disclaimer in the documentation and/or other materials provided 14 // with the distribution. 15 // * Neither the name of Google Inc. nor the names of its 16 // contributors may be used to endorse or promote products derived 17 // from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 #ifndef V8_NATIVE_REGEXP_MACRO_ASSEMBLER_H_ 32 #define V8_NATIVE_REGEXP_MACRO_ASSEMBLER_H_ 33 34 #include "irregexp/RegExpMacroAssembler.h" 35 36 namespace js { 37 namespace irregexp { 38 39 struct InputOutputData 40 { 41 const void* inputStart; 42 const void* inputEnd; 43 44 // Index into inputStart (in chars) at which to begin matching. 45 size_t startIndex; 46 size_t* endIndex; 47 48 MatchPairs* matches; 49 50 // RegExpMacroAssembler::Result for non-global regexps, number of captures 51 // for global regexps. 52 int32_t result; 53 54 template <typename CharT> InputOutputDataInputOutputData55 InputOutputData(const CharT* inputStart, const CharT* inputEnd, 56 size_t startIndex, MatchPairs* matches, size_t* endIndex) 57 : inputStart(inputStart), 58 inputEnd(inputEnd), 59 startIndex(startIndex), 60 endIndex(endIndex), 61 matches(matches), 62 result(0) 63 {} 64 }; 65 66 struct FrameData 67 { 68 // Copy of the input/output data's data. 69 char16_t* inputStart; 70 size_t startIndex; 71 size_t* endIndex; 72 73 // Pointer to the character before the input start. 74 char16_t* inputStartMinusOne; 75 76 // Copy of the input MatchPairs registers, may be modified by JIT code. 77 int32_t* outputRegisters; 78 int32_t numOutputRegisters; 79 80 int32_t successfulCaptures; 81 82 void* backtrackStackBase; 83 }; 84 85 class MOZ_STACK_CLASS NativeRegExpMacroAssembler final : public RegExpMacroAssembler 86 { 87 public: 88 // Type of input string to generate code for. 89 enum Mode { LATIN1 = 1, CHAR16 = 2 }; 90 91 NativeRegExpMacroAssembler(JSContext* cx, LifoAlloc* alloc, Mode mode, int registers_to_save, 92 RegExpShared::JitCodeTables& tables); 93 94 // Inherited virtual methods. 95 RegExpCode GenerateCode(JSContext* cx, bool match_only) override; 96 int stack_limit_slack() override; 97 bool CanReadUnaligned() override; 98 void AdvanceCurrentPosition(int by) override; 99 void AdvanceRegister(int reg, int by) override; 100 void Backtrack() override; 101 void Bind(jit::Label* label) override; 102 void CheckAtStart(jit::Label* on_at_start) override; 103 void CheckCharacter(unsigned c, jit::Label* on_equal) override; 104 void CheckCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_equal) override; 105 void CheckCharacterGT(char16_t limit, jit::Label* on_greater) override; 106 void CheckCharacterLT(char16_t limit, jit::Label* on_less) override; 107 void CheckGreedyLoop(jit::Label* on_tos_equals_current_position) override; 108 void CheckNotAtStart(jit::Label* on_not_at_start) override; 109 void CheckNotBackReference(int start_reg, jit::Label* on_no_match) override; 110 void CheckNotBackReferenceIgnoreCase(int start_reg, jit::Label* on_no_match, bool unicode) override; 111 void CheckNotCharacter(unsigned c, jit::Label* on_not_equal) override; 112 void CheckNotCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_not_equal) override; 113 void CheckNotCharacterAfterMinusAnd(char16_t c, char16_t minus, char16_t and_with, 114 jit::Label* on_not_equal) override; 115 void CheckCharacterInRange(char16_t from, char16_t to, 116 jit::Label* on_in_range) override; 117 void CheckCharacterNotInRange(char16_t from, char16_t to, 118 jit::Label* on_not_in_range) override; 119 void CheckBitInTable(RegExpShared::JitCodeTable table, jit::Label* on_bit_set) override; 120 void CheckPosition(int cp_offset, jit::Label* on_outside_input) override; 121 void JumpOrBacktrack(jit::Label* to) override; 122 bool CheckSpecialCharacterClass(char16_t type, jit::Label* on_no_match) override; 123 void Fail() override; 124 void IfRegisterGE(int reg, int comparand, jit::Label* if_ge) override; 125 void IfRegisterLT(int reg, int comparand, jit::Label* if_lt) override; 126 void IfRegisterEqPos(int reg, jit::Label* if_eq) override; 127 void LoadCurrentCharacter(int cp_offset, jit::Label* on_end_of_input, 128 bool check_bounds = true, int characters = 1) override; 129 void PopCurrentPosition() override; 130 void PopRegister(int register_index) override; 131 void PushCurrentPosition() override; 132 void PushRegister(int register_index, StackCheckFlag check_stack_limit) override; 133 void ReadCurrentPositionFromRegister(int reg) override; 134 void ReadBacktrackStackPointerFromRegister(int reg) override; 135 void SetCurrentPositionFromEnd(int by) override; 136 void SetRegister(int register_index, int to) override; 137 bool Succeed() override; 138 void WriteCurrentPositionToRegister(int reg, int cp_offset) override; 139 void ClearRegisters(int reg_from, int reg_to) override; 140 void WriteBacktrackStackPointerToRegister(int reg) override; 141 void PushBacktrack(jit::Label* label) override; 142 void BindBacktrack(jit::Label* label) override; 143 144 // Compares two-byte strings case insensitively. 145 // Called from generated RegExp code. 146 static int CaseInsensitiveCompareUC16(jit::Address byte_offset1, 147 jit::Address byte_offset2, 148 size_t byte_length); 149 150 // Byte map of one byte characters with a 0xff if the character is a word 151 // character (digit, letter or underscore) and 0x00 otherwise. 152 // Used by generated RegExp code. 153 static const uint8_t word_character_map[256]; 154 155 // Byte size of chars in the string to match (decided by the Mode argument) char_size()156 inline int char_size() { return static_cast<int>(mode_); } factor()157 inline jit::Scale factor() { return mode_ == CHAR16 ? jit::TimesTwo : jit::TimesOne; } 158 159 jit::Label* BranchOrBacktrack(jit::Label* branch); 160 161 // Pushes a register or constant on the backtrack stack. Decrements the 162 // stack pointer by a word size and stores the register's value there. 163 void PushBacktrack(jit::Register value); 164 void PushBacktrack(int32_t value); 165 166 // Pop a value from the backtrack stack. 167 void PopBacktrack(jit::Register target); 168 169 // Check whether we are exceeding the stack limit on the backtrack stack. 170 void CheckBacktrackStackLimit(); 171 172 void LoadCurrentCharacterUnchecked(int cp_offset, int characters); 173 174 private: 175 jit::StackMacroAssembler masm; 176 RegExpShared::JitCodeTables& tables; 177 178 JSContext* cx; 179 Mode mode_; 180 jit::Label entry_label_; 181 jit::Label start_label_; 182 jit::Label backtrack_label_; 183 jit::Label success_label_; 184 jit::Label exit_label_; 185 jit::Label stack_overflow_label_; 186 jit::Label exit_with_exception_label_; 187 188 // Set of registers which are used by the code generator, and as such which 189 // are saved. 190 jit::LiveGeneralRegisterSet savedNonVolatileRegisters; 191 192 struct LabelPatch { 193 // Once it is bound via BindBacktrack, |label| becomes null and 194 // |labelOffset| is set. 195 jit::Label* label; 196 size_t labelOffset; 197 198 jit::CodeOffset patchOffset; 199 LabelPatchLabelPatch200 LabelPatch(jit::Label* label, jit::CodeOffset patchOffset) 201 : label(label), labelOffset(0), patchOffset(patchOffset) 202 {} 203 }; 204 205 Vector<LabelPatch, 4, SystemAllocPolicy> labelPatches; 206 207 // See RegExpMacroAssembler.cpp for the meaning of these registers. 208 jit::Register input_end_pointer; 209 jit::Register current_character; 210 jit::Register current_position; 211 jit::Register backtrack_stack_pointer; 212 jit::Register temp0, temp1, temp2; 213 214 // The frame_pointer-relative location of a regexp register. register_location(int register_index)215 jit::Address register_location(int register_index) { 216 checkRegister(register_index); 217 return jit::Address(masm.getStackPointer(), register_offset(register_index)); 218 } 219 register_offset(int register_index)220 int32_t register_offset(int register_index) { 221 return sizeof(FrameData) + register_index * sizeof(void*); 222 } 223 }; 224 225 } } // namespace js::irregexp 226 227 #endif // V8_NATIVE_REGEXP_MACRO_ASSEMBLER_H_ 228