Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99: */
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>
55 245 : 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 245 : result(0)
63 245 : {}
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 40 : 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);
96 : int stack_limit_slack();
97 : bool CanReadUnaligned();
98 : void AdvanceCurrentPosition(int by);
99 : void AdvanceRegister(int reg, int by);
100 : void Backtrack();
101 : void Bind(jit::Label* label);
102 : void CheckAtStart(jit::Label* on_at_start);
103 : void CheckCharacter(unsigned c, jit::Label* on_equal);
104 : void CheckCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_equal);
105 : void CheckCharacterGT(char16_t limit, jit::Label* on_greater);
106 : void CheckCharacterLT(char16_t limit, jit::Label* on_less);
107 : void CheckGreedyLoop(jit::Label* on_tos_equals_current_position);
108 : void CheckNotAtStart(jit::Label* on_not_at_start);
109 : void CheckNotBackReference(int start_reg, jit::Label* on_no_match);
110 : void CheckNotBackReferenceIgnoreCase(int start_reg, jit::Label* on_no_match, bool unicode);
111 : void CheckNotCharacter(unsigned c, jit::Label* on_not_equal);
112 : void CheckNotCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_not_equal);
113 : void CheckNotCharacterAfterMinusAnd(char16_t c, char16_t minus, char16_t and_with,
114 : jit::Label* on_not_equal);
115 : void CheckCharacterInRange(char16_t from, char16_t to,
116 : jit::Label* on_in_range);
117 : void CheckCharacterNotInRange(char16_t from, char16_t to,
118 : jit::Label* on_not_in_range);
119 : void CheckBitInTable(RegExpShared::JitCodeTable table, jit::Label* on_bit_set);
120 : void CheckPosition(int cp_offset, jit::Label* on_outside_input);
121 : void JumpOrBacktrack(jit::Label* to);
122 : bool CheckSpecialCharacterClass(char16_t type, jit::Label* on_no_match);
123 : void Fail();
124 : void IfRegisterGE(int reg, int comparand, jit::Label* if_ge);
125 : void IfRegisterLT(int reg, int comparand, jit::Label* if_lt);
126 : void IfRegisterEqPos(int reg, jit::Label* if_eq);
127 : void LoadCurrentCharacter(int cp_offset, jit::Label* on_end_of_input,
128 : bool check_bounds = true, int characters = 1);
129 : void PopCurrentPosition();
130 : void PopRegister(int register_index);
131 : void PushCurrentPosition();
132 : void PushRegister(int register_index, StackCheckFlag check_stack_limit);
133 : void ReadCurrentPositionFromRegister(int reg);
134 : void ReadBacktrackStackPointerFromRegister(int reg);
135 : void SetCurrentPositionFromEnd(int by);
136 : void SetRegister(int register_index, int to);
137 : bool Succeed();
138 : void WriteCurrentPositionToRegister(int reg, int cp_offset);
139 : void ClearRegisters(int reg_from, int reg_to);
140 : void WriteBacktrackStackPointerToRegister(int reg);
141 : void PushBacktrack(jit::Label* label);
142 : void BindBacktrack(jit::Label* label);
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)
156 572 : inline int char_size() { return static_cast<int>(mode_); }
157 40 : 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::MacroAssembler 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 :
200 206 : LabelPatch(jit::Label* label, jit::CodeOffset patchOffset)
201 206 : : label(label), labelOffset(0), patchOffset(patchOffset)
202 206 : {}
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.
215 720 : jit::Address register_location(int register_index) {
216 720 : checkRegister(register_index);
217 720 : return jit::Address(masm.getStackPointer(), register_offset(register_index));
218 : }
219 :
220 722 : int32_t register_offset(int register_index) {
221 722 : return sizeof(FrameData) + register_index * sizeof(void*);
222 : }
223 : };
224 :
225 : } } // namespace js::irregexp
226 :
227 : #endif // V8_NATIVE_REGEXP_MACRO_ASSEMBLER_H_
|
