1 // Copyright 2008-2009 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "new-regexp/regexp-bytecode-generator.h"
6
7 #include "new-regexp/regexp-bytecode-generator-inl.h"
8 #include "new-regexp/regexp-bytecode-peephole.h"
9 #include "new-regexp/regexp-bytecodes.h"
10 #include "new-regexp/regexp-macro-assembler.h"
11
12 namespace v8 {
13 namespace internal {
14
RegExpBytecodeGenerator(Isolate * isolate,Zone * zone)15 RegExpBytecodeGenerator::RegExpBytecodeGenerator(Isolate* isolate, Zone* zone)
16 : RegExpMacroAssembler(isolate, zone),
17 buffer_(Vector<byte>::New(1024)),
18 pc_(0),
19 advance_current_end_(kInvalidPC),
20 jump_edges_(zone),
21 isolate_(isolate) {}
22
~RegExpBytecodeGenerator()23 RegExpBytecodeGenerator::~RegExpBytecodeGenerator() {
24 if (backtrack_.is_linked()) backtrack_.Unuse();
25 buffer_.Dispose();
26 }
27
28 RegExpBytecodeGenerator::IrregexpImplementation
Implementation()29 RegExpBytecodeGenerator::Implementation() {
30 return kBytecodeImplementation;
31 }
32
Bind(Label * l)33 void RegExpBytecodeGenerator::Bind(Label* l) {
34 advance_current_end_ = kInvalidPC;
35 DCHECK(!l->is_bound());
36 if (l->is_linked()) {
37 int pos = l->pos();
38 while (pos != 0) {
39 int fixup = pos;
40 pos = *reinterpret_cast<int32_t*>(buffer_.begin() + fixup);
41 *reinterpret_cast<uint32_t*>(buffer_.begin() + fixup) = pc_;
42 jump_edges_.emplace(fixup, pc_);
43 }
44 }
45 l->bind_to(pc_);
46 }
47
EmitOrLink(Label * l)48 void RegExpBytecodeGenerator::EmitOrLink(Label* l) {
49 if (l == nullptr) l = &backtrack_;
50 int pos = 0;
51 if (l->is_bound()) {
52 pos = l->pos();
53 jump_edges_.emplace(pc_, pos);
54 } else {
55 if (l->is_linked()) {
56 pos = l->pos();
57 }
58 l->link_to(pc_);
59 }
60 Emit32(pos);
61 }
62
PopRegister(int register_index)63 void RegExpBytecodeGenerator::PopRegister(int register_index) {
64 DCHECK_LE(0, register_index);
65 DCHECK_GE(kMaxRegister, register_index);
66 Emit(BC_POP_REGISTER, register_index);
67 }
68
PushRegister(int register_index,StackCheckFlag check_stack_limit)69 void RegExpBytecodeGenerator::PushRegister(int register_index,
70 StackCheckFlag check_stack_limit) {
71 DCHECK_LE(0, register_index);
72 DCHECK_GE(kMaxRegister, register_index);
73 Emit(BC_PUSH_REGISTER, register_index);
74 }
75
WriteCurrentPositionToRegister(int register_index,int cp_offset)76 void RegExpBytecodeGenerator::WriteCurrentPositionToRegister(int register_index,
77 int cp_offset) {
78 DCHECK_LE(0, register_index);
79 DCHECK_GE(kMaxRegister, register_index);
80 Emit(BC_SET_REGISTER_TO_CP, register_index);
81 Emit32(cp_offset); // Current position offset.
82 }
83
ClearRegisters(int reg_from,int reg_to)84 void RegExpBytecodeGenerator::ClearRegisters(int reg_from, int reg_to) {
85 DCHECK(reg_from <= reg_to);
86 for (int reg = reg_from; reg <= reg_to; reg++) {
87 SetRegister(reg, -1);
88 }
89 }
90
ReadCurrentPositionFromRegister(int register_index)91 void RegExpBytecodeGenerator::ReadCurrentPositionFromRegister(
92 int register_index) {
93 DCHECK_LE(0, register_index);
94 DCHECK_GE(kMaxRegister, register_index);
95 Emit(BC_SET_CP_TO_REGISTER, register_index);
96 }
97
WriteStackPointerToRegister(int register_index)98 void RegExpBytecodeGenerator::WriteStackPointerToRegister(int register_index) {
99 DCHECK_LE(0, register_index);
100 DCHECK_GE(kMaxRegister, register_index);
101 Emit(BC_SET_REGISTER_TO_SP, register_index);
102 }
103
ReadStackPointerFromRegister(int register_index)104 void RegExpBytecodeGenerator::ReadStackPointerFromRegister(int register_index) {
105 DCHECK_LE(0, register_index);
106 DCHECK_GE(kMaxRegister, register_index);
107 Emit(BC_SET_SP_TO_REGISTER, register_index);
108 }
109
SetCurrentPositionFromEnd(int by)110 void RegExpBytecodeGenerator::SetCurrentPositionFromEnd(int by) {
111 DCHECK(is_uint24(by));
112 Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
113 }
114
SetRegister(int register_index,int to)115 void RegExpBytecodeGenerator::SetRegister(int register_index, int to) {
116 DCHECK_LE(0, register_index);
117 DCHECK_GE(kMaxRegister, register_index);
118 Emit(BC_SET_REGISTER, register_index);
119 Emit32(to);
120 }
121
AdvanceRegister(int register_index,int by)122 void RegExpBytecodeGenerator::AdvanceRegister(int register_index, int by) {
123 DCHECK_LE(0, register_index);
124 DCHECK_GE(kMaxRegister, register_index);
125 Emit(BC_ADVANCE_REGISTER, register_index);
126 Emit32(by);
127 }
128
PopCurrentPosition()129 void RegExpBytecodeGenerator::PopCurrentPosition() { Emit(BC_POP_CP, 0); }
130
PushCurrentPosition()131 void RegExpBytecodeGenerator::PushCurrentPosition() { Emit(BC_PUSH_CP, 0); }
132
Backtrack()133 void RegExpBytecodeGenerator::Backtrack() { Emit(BC_POP_BT, 0); }
134
GoTo(Label * l)135 void RegExpBytecodeGenerator::GoTo(Label* l) {
136 if (advance_current_end_ == pc_) {
137 // Combine advance current and goto.
138 pc_ = advance_current_start_;
139 Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
140 EmitOrLink(l);
141 advance_current_end_ = kInvalidPC;
142 } else {
143 // Regular goto.
144 Emit(BC_GOTO, 0);
145 EmitOrLink(l);
146 }
147 }
148
PushBacktrack(Label * l)149 void RegExpBytecodeGenerator::PushBacktrack(Label* l) {
150 Emit(BC_PUSH_BT, 0);
151 EmitOrLink(l);
152 }
153
Succeed()154 bool RegExpBytecodeGenerator::Succeed() {
155 Emit(BC_SUCCEED, 0);
156 return false; // Restart matching for global regexp not supported.
157 }
158
Fail()159 void RegExpBytecodeGenerator::Fail() { Emit(BC_FAIL, 0); }
160
AdvanceCurrentPosition(int by)161 void RegExpBytecodeGenerator::AdvanceCurrentPosition(int by) {
162 DCHECK_LE(kMinCPOffset, by);
163 DCHECK_GE(kMaxCPOffset, by);
164 advance_current_start_ = pc_;
165 advance_current_offset_ = by;
166 Emit(BC_ADVANCE_CP, by);
167 advance_current_end_ = pc_;
168 }
169
CheckGreedyLoop(Label * on_tos_equals_current_position)170 void RegExpBytecodeGenerator::CheckGreedyLoop(
171 Label* on_tos_equals_current_position) {
172 Emit(BC_CHECK_GREEDY, 0);
173 EmitOrLink(on_tos_equals_current_position);
174 }
175
LoadCurrentCharacterImpl(int cp_offset,Label * on_failure,bool check_bounds,int characters,int eats_at_least)176 void RegExpBytecodeGenerator::LoadCurrentCharacterImpl(int cp_offset,
177 Label* on_failure,
178 bool check_bounds,
179 int characters,
180 int eats_at_least) {
181 DCHECK_GE(eats_at_least, characters);
182 if (eats_at_least > characters && check_bounds) {
183 DCHECK(is_int24(cp_offset + eats_at_least));
184 Emit(BC_CHECK_CURRENT_POSITION, cp_offset + eats_at_least);
185 EmitOrLink(on_failure);
186 check_bounds = false; // Load below doesn't need to check.
187 }
188
189 DCHECK_LE(kMinCPOffset, cp_offset);
190 DCHECK_GE(kMaxCPOffset, cp_offset);
191 int bytecode;
192 if (check_bounds) {
193 if (characters == 4) {
194 bytecode = BC_LOAD_4_CURRENT_CHARS;
195 } else if (characters == 2) {
196 bytecode = BC_LOAD_2_CURRENT_CHARS;
197 } else {
198 DCHECK_EQ(1, characters);
199 bytecode = BC_LOAD_CURRENT_CHAR;
200 }
201 } else {
202 if (characters == 4) {
203 bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
204 } else if (characters == 2) {
205 bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
206 } else {
207 DCHECK_EQ(1, characters);
208 bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
209 }
210 }
211 Emit(bytecode, cp_offset);
212 if (check_bounds) EmitOrLink(on_failure);
213 }
214
CheckCharacterLT(uc16 limit,Label * on_less)215 void RegExpBytecodeGenerator::CheckCharacterLT(uc16 limit, Label* on_less) {
216 Emit(BC_CHECK_LT, limit);
217 EmitOrLink(on_less);
218 }
219
CheckCharacterGT(uc16 limit,Label * on_greater)220 void RegExpBytecodeGenerator::CheckCharacterGT(uc16 limit, Label* on_greater) {
221 Emit(BC_CHECK_GT, limit);
222 EmitOrLink(on_greater);
223 }
224
CheckCharacter(uint32_t c,Label * on_equal)225 void RegExpBytecodeGenerator::CheckCharacter(uint32_t c, Label* on_equal) {
226 if (c > MAX_FIRST_ARG) {
227 Emit(BC_CHECK_4_CHARS, 0);
228 Emit32(c);
229 } else {
230 Emit(BC_CHECK_CHAR, c);
231 }
232 EmitOrLink(on_equal);
233 }
234
CheckAtStart(int cp_offset,Label * on_at_start)235 void RegExpBytecodeGenerator::CheckAtStart(int cp_offset, Label* on_at_start) {
236 Emit(BC_CHECK_AT_START, cp_offset);
237 EmitOrLink(on_at_start);
238 }
239
CheckNotAtStart(int cp_offset,Label * on_not_at_start)240 void RegExpBytecodeGenerator::CheckNotAtStart(int cp_offset,
241 Label* on_not_at_start) {
242 Emit(BC_CHECK_NOT_AT_START, cp_offset);
243 EmitOrLink(on_not_at_start);
244 }
245
CheckNotCharacter(uint32_t c,Label * on_not_equal)246 void RegExpBytecodeGenerator::CheckNotCharacter(uint32_t c,
247 Label* on_not_equal) {
248 if (c > MAX_FIRST_ARG) {
249 Emit(BC_CHECK_NOT_4_CHARS, 0);
250 Emit32(c);
251 } else {
252 Emit(BC_CHECK_NOT_CHAR, c);
253 }
254 EmitOrLink(on_not_equal);
255 }
256
CheckCharacterAfterAnd(uint32_t c,uint32_t mask,Label * on_equal)257 void RegExpBytecodeGenerator::CheckCharacterAfterAnd(uint32_t c, uint32_t mask,
258 Label* on_equal) {
259 if (c > MAX_FIRST_ARG) {
260 Emit(BC_AND_CHECK_4_CHARS, 0);
261 Emit32(c);
262 } else {
263 Emit(BC_AND_CHECK_CHAR, c);
264 }
265 Emit32(mask);
266 EmitOrLink(on_equal);
267 }
268
CheckNotCharacterAfterAnd(uint32_t c,uint32_t mask,Label * on_not_equal)269 void RegExpBytecodeGenerator::CheckNotCharacterAfterAnd(uint32_t c,
270 uint32_t mask,
271 Label* on_not_equal) {
272 if (c > MAX_FIRST_ARG) {
273 Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
274 Emit32(c);
275 } else {
276 Emit(BC_AND_CHECK_NOT_CHAR, c);
277 }
278 Emit32(mask);
279 EmitOrLink(on_not_equal);
280 }
281
CheckNotCharacterAfterMinusAnd(uc16 c,uc16 minus,uc16 mask,Label * on_not_equal)282 void RegExpBytecodeGenerator::CheckNotCharacterAfterMinusAnd(
283 uc16 c, uc16 minus, uc16 mask, Label* on_not_equal) {
284 Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
285 Emit16(minus);
286 Emit16(mask);
287 EmitOrLink(on_not_equal);
288 }
289
CheckCharacterInRange(uc16 from,uc16 to,Label * on_in_range)290 void RegExpBytecodeGenerator::CheckCharacterInRange(uc16 from, uc16 to,
291 Label* on_in_range) {
292 Emit(BC_CHECK_CHAR_IN_RANGE, 0);
293 Emit16(from);
294 Emit16(to);
295 EmitOrLink(on_in_range);
296 }
297
CheckCharacterNotInRange(uc16 from,uc16 to,Label * on_not_in_range)298 void RegExpBytecodeGenerator::CheckCharacterNotInRange(uc16 from, uc16 to,
299 Label* on_not_in_range) {
300 Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
301 Emit16(from);
302 Emit16(to);
303 EmitOrLink(on_not_in_range);
304 }
305
CheckBitInTable(Handle<ByteArray> table,Label * on_bit_set)306 void RegExpBytecodeGenerator::CheckBitInTable(Handle<ByteArray> table,
307 Label* on_bit_set) {
308 Emit(BC_CHECK_BIT_IN_TABLE, 0);
309 EmitOrLink(on_bit_set);
310 for (int i = 0; i < kTableSize; i += kBitsPerByte) {
311 int byte = 0;
312 for (int j = 0; j < kBitsPerByte; j++) {
313 if (table->get(i + j) != 0) byte |= 1 << j;
314 }
315 Emit8(byte);
316 }
317 }
318
CheckNotBackReference(int start_reg,bool read_backward,Label * on_not_equal)319 void RegExpBytecodeGenerator::CheckNotBackReference(int start_reg,
320 bool read_backward,
321 Label* on_not_equal) {
322 DCHECK_LE(0, start_reg);
323 DCHECK_GE(kMaxRegister, start_reg);
324 Emit(read_backward ? BC_CHECK_NOT_BACK_REF_BACKWARD : BC_CHECK_NOT_BACK_REF,
325 start_reg);
326 EmitOrLink(on_not_equal);
327 }
328
CheckNotBackReferenceIgnoreCase(int start_reg,bool read_backward,Label * on_not_equal)329 void RegExpBytecodeGenerator::CheckNotBackReferenceIgnoreCase(
330 int start_reg, bool read_backward, Label* on_not_equal) {
331 DCHECK_LE(0, start_reg);
332 DCHECK_GE(kMaxRegister, start_reg);
333 Emit(read_backward ? BC_CHECK_NOT_BACK_REF_NO_CASE_BACKWARD
334 : BC_CHECK_NOT_BACK_REF_NO_CASE,
335 start_reg);
336 EmitOrLink(on_not_equal);
337 }
338
IfRegisterLT(int register_index,int comparand,Label * on_less_than)339 void RegExpBytecodeGenerator::IfRegisterLT(int register_index, int comparand,
340 Label* on_less_than) {
341 DCHECK_LE(0, register_index);
342 DCHECK_GE(kMaxRegister, register_index);
343 Emit(BC_CHECK_REGISTER_LT, register_index);
344 Emit32(comparand);
345 EmitOrLink(on_less_than);
346 }
347
IfRegisterGE(int register_index,int comparand,Label * on_greater_or_equal)348 void RegExpBytecodeGenerator::IfRegisterGE(int register_index, int comparand,
349 Label* on_greater_or_equal) {
350 DCHECK_LE(0, register_index);
351 DCHECK_GE(kMaxRegister, register_index);
352 Emit(BC_CHECK_REGISTER_GE, register_index);
353 Emit32(comparand);
354 EmitOrLink(on_greater_or_equal);
355 }
356
IfRegisterEqPos(int register_index,Label * on_eq)357 void RegExpBytecodeGenerator::IfRegisterEqPos(int register_index,
358 Label* on_eq) {
359 DCHECK_LE(0, register_index);
360 DCHECK_GE(kMaxRegister, register_index);
361 Emit(BC_CHECK_REGISTER_EQ_POS, register_index);
362 EmitOrLink(on_eq);
363 }
364
GetCode(Handle<String> source)365 Handle<HeapObject> RegExpBytecodeGenerator::GetCode(Handle<String> source) {
366 Bind(&backtrack_);
367 Emit(BC_POP_BT, 0);
368
369 Handle<ByteArray> array;
370 if (FLAG_regexp_peephole_optimization) {
371 array = RegExpBytecodePeepholeOptimization::OptimizeBytecode(
372 isolate_, zone(), source, buffer_.begin(), length(), jump_edges_);
373 } else {
374 array = isolate_->factory()->NewByteArray(length());
375 Copy(array->GetDataStartAddress());
376 }
377
378 return array;
379 }
380
length()381 int RegExpBytecodeGenerator::length() { return pc_; }
382
Copy(byte * a)383 void RegExpBytecodeGenerator::Copy(byte* a) {
384 MemCopy(a, buffer_.begin(), length());
385 }
386
Expand()387 void RegExpBytecodeGenerator::Expand() {
388 Vector<byte> old_buffer = buffer_;
389 buffer_ = Vector<byte>::New(old_buffer.length() * 2);
390 MemCopy(buffer_.begin(), old_buffer.begin(), old_buffer.length());
391 old_buffer.Dispose();
392 }
393
394 } // namespace internal
395 } // namespace v8
396