1 // Copyright 2012 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 #if V8_TARGET_ARCH_MIPS
34 #include "code-stubs.h"
35 #include "regexp-stack.h"
36 #include "macro-assembler.h"
37 #include "regexp-macro-assembler.h"
38 #include "mips/regexp-macro-assembler-mips.h"
43 #ifndef V8_INTERPRETED_REGEXP
45 * This assembler uses the following register assignment convention
46 * - t7 : Temporarily stores the index of capture start after a matching pass
47 * for a global regexp.
48 * - t1 : Pointer to current code object (Code*) including heap object tag.
49 * - t2 : Current position in input, as negative offset from end of string.
50 * Please notice that this is the byte offset, not the character offset!
51 * - t3 : Currently loaded character. Must be loaded using
52 * LoadCurrentCharacter before using any of the dispatch methods.
53 * - t4 : Points to tip of backtrack stack
55 * - t6 : End of input (points to byte after last character in input).
56 * - fp : Frame pointer. Used to access arguments, local variables and
58 * - sp : Points to tip of C stack.
60 * The remaining registers are free for computations.
61 * Each call to a public method should retain this convention.
63 * The stack will have the following structure:
65 * - fp[64] Isolate* isolate (address of the current isolate)
66 * - fp[60] direct_call (if 1, direct call from JavaScript code,
67 * if 0, call through the runtime system).
68 * - fp[56] stack_area_base (High end of the memory area to use as
69 * backtracking stack).
70 * - fp[52] capture array size (may fit multiple sets of matches)
71 * - fp[48] int* capture_array (int[num_saved_registers_], for output).
72 * - fp[44] secondary link/return address used by native call.
73 * --- sp when called ---
74 * - fp[40] return address (lr).
75 * - fp[36] old frame pointer (r11).
76 * - fp[0..32] backup of registers s0..s7.
77 * --- frame pointer ----
78 * - fp[-4] end of input (address of end of string).
79 * - fp[-8] start of input (address of first character in string).
80 * - fp[-12] start index (character index of start).
81 * - fp[-16] void* input_string (location of a handle containing the string).
82 * - fp[-20] success counter (only for global regexps to count matches).
83 * - fp[-24] Offset of location before start of input (effectively character
84 * position -1). Used to initialize capture registers to a
86 * - fp[-28] At start (if 1, we are starting at the start of the
87 * string, otherwise 0)
88 * - fp[-32] register 0 (Only positions must be stored in the first
89 * - register 1 num_saved_registers_ registers)
91 * - register num_registers-1
94 * The first num_saved_registers_ registers are initialized to point to
95 * "character -1" in the string (i.e., char_size() bytes before the first
96 * character of the string). The remaining registers start out as garbage.
98 * The data up to the return address must be placed there by the calling
99 * code and the remaining arguments are passed in registers, e.g. by calling the
100 * code entry as cast to a function with the signature:
101 * int (*match)(String* input_string,
105 * Address secondary_return_address, // Only used by native call.
106 * int* capture_output_array,
107 * byte* stack_area_base,
108 * bool direct_call = false)
109 * The call is performed by NativeRegExpMacroAssembler::Execute()
110 * (in regexp-macro-assembler.cc) via the CALL_GENERATED_REGEXP_CODE macro
111 * in mips/simulator-mips.h.
112 * When calling as a non-direct call (i.e., from C++ code), the return address
113 * area is overwritten with the ra register by the RegExp code. When doing a
114 * direct call from generated code, the return address is placed there by
115 * the calling code, as in a normal exit frame.
118 #define __ ACCESS_MASM(masm_)
120 RegExpMacroAssemblerMIPS::RegExpMacroAssemblerMIPS(
122 int registers_to_save,
124 : NativeRegExpMacroAssembler(zone),
125 masm_(new MacroAssembler(zone->isolate(), NULL, kRegExpCodeSize)),
127 num_registers_(registers_to_save),
128 num_saved_registers_(registers_to_save),
134 internal_failure_label_() {
135 ASSERT_EQ(0, registers_to_save % 2);
136 __ jmp(&entry_label_); // We'll write the entry code later.
137 // If the code gets too big or corrupted, an internal exception will be
138 // raised, and we will exit right away.
139 __ bind(&internal_failure_label_);
140 __ li(v0, Operand(FAILURE));
142 __ bind(&start_label_); // And then continue from here.
146 RegExpMacroAssemblerMIPS::~RegExpMacroAssemblerMIPS() {
148 // Unuse labels in case we throw away the assembler without calling GetCode.
149 entry_label_.Unuse();
150 start_label_.Unuse();
151 success_label_.Unuse();
152 backtrack_label_.Unuse();
154 check_preempt_label_.Unuse();
155 stack_overflow_label_.Unuse();
156 internal_failure_label_.Unuse();
160 int RegExpMacroAssemblerMIPS::stack_limit_slack() {
161 return RegExpStack::kStackLimitSlack;
165 void RegExpMacroAssemblerMIPS::AdvanceCurrentPosition(int by) {
167 __ Addu(current_input_offset(),
168 current_input_offset(), Operand(by * char_size()));
173 void RegExpMacroAssemblerMIPS::AdvanceRegister(int reg, int by) {
175 ASSERT(reg < num_registers_);
177 __ lw(a0, register_location(reg));
178 __ Addu(a0, a0, Operand(by));
179 __ sw(a0, register_location(reg));
184 void RegExpMacroAssemblerMIPS::Backtrack() {
186 // Pop Code* offset from backtrack stack, add Code* and jump to location.
188 __ Addu(a0, a0, code_pointer());
193 void RegExpMacroAssemblerMIPS::Bind(Label* label) {
198 void RegExpMacroAssemblerMIPS::CheckCharacter(uint32_t c, Label* on_equal) {
199 BranchOrBacktrack(on_equal, eq, current_character(), Operand(c));
203 void RegExpMacroAssemblerMIPS::CheckCharacterGT(uc16 limit, Label* on_greater) {
204 BranchOrBacktrack(on_greater, gt, current_character(), Operand(limit));
208 void RegExpMacroAssemblerMIPS::CheckAtStart(Label* on_at_start) {
210 // Did we start the match at the start of the string at all?
211 __ lw(a0, MemOperand(frame_pointer(), kStartIndex));
212 BranchOrBacktrack(¬_at_start, ne, a0, Operand(zero_reg));
214 // If we did, are we still at the start of the input?
215 __ lw(a1, MemOperand(frame_pointer(), kInputStart));
216 __ Addu(a0, end_of_input_address(), Operand(current_input_offset()));
217 BranchOrBacktrack(on_at_start, eq, a0, Operand(a1));
218 __ bind(¬_at_start);
222 void RegExpMacroAssemblerMIPS::CheckNotAtStart(Label* on_not_at_start) {
223 // Did we start the match at the start of the string at all?
224 __ lw(a0, MemOperand(frame_pointer(), kStartIndex));
225 BranchOrBacktrack(on_not_at_start, ne, a0, Operand(zero_reg));
226 // If we did, are we still at the start of the input?
227 __ lw(a1, MemOperand(frame_pointer(), kInputStart));
228 __ Addu(a0, end_of_input_address(), Operand(current_input_offset()));
229 BranchOrBacktrack(on_not_at_start, ne, a0, Operand(a1));
233 void RegExpMacroAssemblerMIPS::CheckCharacterLT(uc16 limit, Label* on_less) {
234 BranchOrBacktrack(on_less, lt, current_character(), Operand(limit));
238 void RegExpMacroAssemblerMIPS::CheckGreedyLoop(Label* on_equal) {
239 Label backtrack_non_equal;
240 __ lw(a0, MemOperand(backtrack_stackpointer(), 0));
241 __ Branch(&backtrack_non_equal, ne, current_input_offset(), Operand(a0));
242 __ Addu(backtrack_stackpointer(),
243 backtrack_stackpointer(),
244 Operand(kPointerSize));
245 __ bind(&backtrack_non_equal);
246 BranchOrBacktrack(on_equal, eq, current_input_offset(), Operand(a0));
250 void RegExpMacroAssemblerMIPS::CheckNotBackReferenceIgnoreCase(
252 Label* on_no_match) {
254 __ lw(a0, register_location(start_reg)); // Index of start of capture.
255 __ lw(a1, register_location(start_reg + 1)); // Index of end of capture.
256 __ Subu(a1, a1, a0); // Length of capture.
258 // If length is zero, either the capture is empty or it is not participating.
259 // In either case succeed immediately.
260 __ Branch(&fallthrough, eq, a1, Operand(zero_reg));
262 __ Addu(t5, a1, current_input_offset());
263 // Check that there are enough characters left in the input.
264 BranchOrBacktrack(on_no_match, gt, t5, Operand(zero_reg));
266 if (mode_ == ASCII) {
271 // a0 - offset of start of capture.
272 // a1 - length of capture.
273 __ Addu(a0, a0, Operand(end_of_input_address()));
274 __ Addu(a2, end_of_input_address(), Operand(current_input_offset()));
275 __ Addu(a1, a0, Operand(a1));
277 // a0 - Address of start of capture.
278 // a1 - Address of end of capture.
279 // a2 - Address of current input position.
283 __ lbu(a3, MemOperand(a0, 0));
284 __ addiu(a0, a0, char_size());
285 __ lbu(t0, MemOperand(a2, 0));
286 __ addiu(a2, a2, char_size());
288 __ Branch(&loop_check, eq, t0, Operand(a3));
290 // Mismatch, try case-insensitive match (converting letters to lower-case).
291 __ Or(a3, a3, Operand(0x20)); // Convert capture character to lower-case.
292 __ Or(t0, t0, Operand(0x20)); // Also convert input character.
293 __ Branch(&fail, ne, t0, Operand(a3));
294 __ Subu(a3, a3, Operand('a'));
295 __ Branch(&loop_check, ls, a3, Operand('z' - 'a'));
296 // Latin-1: Check for values in range [224,254] but not 247.
297 __ Subu(a3, a3, Operand(224 - 'a'));
298 // Weren't Latin-1 letters.
299 __ Branch(&fail, hi, a3, Operand(254 - 224));
301 __ Branch(&fail, eq, a3, Operand(247 - 224));
303 __ bind(&loop_check);
304 __ Branch(&loop, lt, a0, Operand(a1));
311 // Compute new value of character position after the matched part.
312 __ Subu(current_input_offset(), a2, end_of_input_address());
314 ASSERT(mode_ == UC16);
315 // Put regexp engine registers on stack.
316 RegList regexp_registers_to_retain = current_input_offset().bit() |
317 current_character().bit() | backtrack_stackpointer().bit();
318 __ MultiPush(regexp_registers_to_retain);
320 int argument_count = 4;
321 __ PrepareCallCFunction(argument_count, a2);
323 // a0 - offset of start of capture.
324 // a1 - length of capture.
326 // Put arguments into arguments registers.
328 // a0: Address byte_offset1 - Address captured substring's start.
329 // a1: Address byte_offset2 - Address of current character position.
330 // a2: size_t byte_length - length of capture in bytes(!).
331 // a3: Isolate* isolate.
333 // Address of start of capture.
334 __ Addu(a0, a0, Operand(end_of_input_address()));
335 // Length of capture.
337 // Save length in callee-save register for use on return.
339 // Address of current input position.
340 __ Addu(a1, current_input_offset(), Operand(end_of_input_address()));
342 __ li(a3, Operand(ExternalReference::isolate_address(masm_->isolate())));
345 AllowExternalCallThatCantCauseGC scope(masm_);
346 ExternalReference function =
347 ExternalReference::re_case_insensitive_compare_uc16(masm_->isolate());
348 __ CallCFunction(function, argument_count);
351 // Restore regexp engine registers.
352 __ MultiPop(regexp_registers_to_retain);
353 __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
354 __ lw(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
356 // Check if function returned non-zero for success or zero for failure.
357 BranchOrBacktrack(on_no_match, eq, v0, Operand(zero_reg));
358 // On success, increment position by length of capture.
359 __ Addu(current_input_offset(), current_input_offset(), Operand(s3));
362 __ bind(&fallthrough);
366 void RegExpMacroAssemblerMIPS::CheckNotBackReference(
368 Label* on_no_match) {
372 // Find length of back-referenced capture.
373 __ lw(a0, register_location(start_reg));
374 __ lw(a1, register_location(start_reg + 1));
375 __ Subu(a1, a1, a0); // Length to check.
376 // Succeed on empty capture (including no capture).
377 __ Branch(&fallthrough, eq, a1, Operand(zero_reg));
379 __ Addu(t5, a1, current_input_offset());
380 // Check that there are enough characters left in the input.
381 BranchOrBacktrack(on_no_match, gt, t5, Operand(zero_reg));
383 // Compute pointers to match string and capture string.
384 __ Addu(a0, a0, Operand(end_of_input_address()));
385 __ Addu(a2, end_of_input_address(), Operand(current_input_offset()));
386 __ Addu(a1, a1, Operand(a0));
390 if (mode_ == ASCII) {
391 __ lbu(a3, MemOperand(a0, 0));
392 __ addiu(a0, a0, char_size());
393 __ lbu(t0, MemOperand(a2, 0));
394 __ addiu(a2, a2, char_size());
396 ASSERT(mode_ == UC16);
397 __ lhu(a3, MemOperand(a0, 0));
398 __ addiu(a0, a0, char_size());
399 __ lhu(t0, MemOperand(a2, 0));
400 __ addiu(a2, a2, char_size());
402 BranchOrBacktrack(on_no_match, ne, a3, Operand(t0));
403 __ Branch(&loop, lt, a0, Operand(a1));
405 // Move current character position to position after match.
406 __ Subu(current_input_offset(), a2, end_of_input_address());
407 __ bind(&fallthrough);
411 void RegExpMacroAssemblerMIPS::CheckNotCharacter(uint32_t c,
412 Label* on_not_equal) {
413 BranchOrBacktrack(on_not_equal, ne, current_character(), Operand(c));
417 void RegExpMacroAssemblerMIPS::CheckCharacterAfterAnd(uint32_t c,
420 __ And(a0, current_character(), Operand(mask));
421 Operand rhs = (c == 0) ? Operand(zero_reg) : Operand(c);
422 BranchOrBacktrack(on_equal, eq, a0, rhs);
426 void RegExpMacroAssemblerMIPS::CheckNotCharacterAfterAnd(uint32_t c,
428 Label* on_not_equal) {
429 __ And(a0, current_character(), Operand(mask));
430 Operand rhs = (c == 0) ? Operand(zero_reg) : Operand(c);
431 BranchOrBacktrack(on_not_equal, ne, a0, rhs);
435 void RegExpMacroAssemblerMIPS::CheckNotCharacterAfterMinusAnd(
439 Label* on_not_equal) {
440 ASSERT(minus < String::kMaxUtf16CodeUnit);
441 __ Subu(a0, current_character(), Operand(minus));
442 __ And(a0, a0, Operand(mask));
443 BranchOrBacktrack(on_not_equal, ne, a0, Operand(c));
447 void RegExpMacroAssemblerMIPS::CheckCharacterInRange(
450 Label* on_in_range) {
451 __ Subu(a0, current_character(), Operand(from));
452 // Unsigned lower-or-same condition.
453 BranchOrBacktrack(on_in_range, ls, a0, Operand(to - from));
457 void RegExpMacroAssemblerMIPS::CheckCharacterNotInRange(
460 Label* on_not_in_range) {
461 __ Subu(a0, current_character(), Operand(from));
462 // Unsigned higher condition.
463 BranchOrBacktrack(on_not_in_range, hi, a0, Operand(to - from));
467 void RegExpMacroAssemblerMIPS::CheckBitInTable(
468 Handle<ByteArray> table,
470 __ li(a0, Operand(table));
471 if (mode_ != ASCII || kTableMask != String::kMaxOneByteCharCode) {
472 __ And(a1, current_character(), Operand(kTableSize - 1));
475 __ Addu(a0, a0, current_character());
478 __ lbu(a0, FieldMemOperand(a0, ByteArray::kHeaderSize));
479 BranchOrBacktrack(on_bit_set, ne, a0, Operand(zero_reg));
483 bool RegExpMacroAssemblerMIPS::CheckSpecialCharacterClass(uc16 type,
484 Label* on_no_match) {
485 // Range checks (c in min..max) are generally implemented by an unsigned
486 // (c - min) <= (max - min) check.
489 // Match space-characters.
490 if (mode_ == ASCII) {
491 // One byte space characters are '\t'..'\r', ' ' and \u00a0.
493 __ Branch(&success, eq, current_character(), Operand(' '));
494 // Check range 0x09..0x0d.
495 __ Subu(a0, current_character(), Operand('\t'));
496 __ Branch(&success, ls, a0, Operand('\r' - '\t'));
498 BranchOrBacktrack(on_no_match, ne, a0, Operand(0x00a0 - '\t'));
504 // The emitted code for generic character classes is good enough.
507 // Match ASCII digits ('0'..'9').
508 __ Subu(a0, current_character(), Operand('0'));
509 BranchOrBacktrack(on_no_match, hi, a0, Operand('9' - '0'));
512 // Match non ASCII-digits.
513 __ Subu(a0, current_character(), Operand('0'));
514 BranchOrBacktrack(on_no_match, ls, a0, Operand('9' - '0'));
517 // Match non-newlines (not 0x0a('\n'), 0x0d('\r'), 0x2028 and 0x2029).
518 __ Xor(a0, current_character(), Operand(0x01));
519 // See if current character is '\n'^1 or '\r'^1, i.e., 0x0b or 0x0c.
520 __ Subu(a0, a0, Operand(0x0b));
521 BranchOrBacktrack(on_no_match, ls, a0, Operand(0x0c - 0x0b));
523 // Compare original value to 0x2028 and 0x2029, using the already
524 // computed (current_char ^ 0x01 - 0x0b). I.e., check for
525 // 0x201d (0x2028 - 0x0b) or 0x201e.
526 __ Subu(a0, a0, Operand(0x2028 - 0x0b));
527 BranchOrBacktrack(on_no_match, ls, a0, Operand(1));
532 // Match newlines (0x0a('\n'), 0x0d('\r'), 0x2028 and 0x2029).
533 __ Xor(a0, current_character(), Operand(0x01));
534 // See if current character is '\n'^1 or '\r'^1, i.e., 0x0b or 0x0c.
535 __ Subu(a0, a0, Operand(0x0b));
536 if (mode_ == ASCII) {
537 BranchOrBacktrack(on_no_match, hi, a0, Operand(0x0c - 0x0b));
540 BranchOrBacktrack(&done, ls, a0, Operand(0x0c - 0x0b));
541 // Compare original value to 0x2028 and 0x2029, using the already
542 // computed (current_char ^ 0x01 - 0x0b). I.e., check for
543 // 0x201d (0x2028 - 0x0b) or 0x201e.
544 __ Subu(a0, a0, Operand(0x2028 - 0x0b));
545 BranchOrBacktrack(on_no_match, hi, a0, Operand(1));
551 if (mode_ != ASCII) {
552 // Table is 128 entries, so all ASCII characters can be tested.
553 BranchOrBacktrack(on_no_match, hi, current_character(), Operand('z'));
555 ExternalReference map = ExternalReference::re_word_character_map();
556 __ li(a0, Operand(map));
557 __ Addu(a0, a0, current_character());
558 __ lbu(a0, MemOperand(a0, 0));
559 BranchOrBacktrack(on_no_match, eq, a0, Operand(zero_reg));
564 if (mode_ != ASCII) {
565 // Table is 128 entries, so all ASCII characters can be tested.
566 __ Branch(&done, hi, current_character(), Operand('z'));
568 ExternalReference map = ExternalReference::re_word_character_map();
569 __ li(a0, Operand(map));
570 __ Addu(a0, a0, current_character());
571 __ lbu(a0, MemOperand(a0, 0));
572 BranchOrBacktrack(on_no_match, ne, a0, Operand(zero_reg));
573 if (mode_ != ASCII) {
579 // Match any character.
581 // No custom implementation (yet): s(UC16), S(UC16).
588 void RegExpMacroAssemblerMIPS::Fail() {
589 __ li(v0, Operand(FAILURE));
590 __ jmp(&exit_label_);
594 Handle<HeapObject> RegExpMacroAssemblerMIPS::GetCode(Handle<String> source) {
596 if (masm_->has_exception()) {
597 // If the code gets corrupted due to long regular expressions and lack of
598 // space on trampolines, an internal exception flag is set. If this case
599 // is detected, we will jump into exit sequence right away.
600 __ bind_to(&entry_label_, internal_failure_label_.pos());
602 // Finalize code - write the entry point code now we know how many
603 // registers we need.
606 __ bind(&entry_label_);
608 // Tell the system that we have a stack frame. Because the type is MANUAL,
610 FrameScope scope(masm_, StackFrame::MANUAL);
612 // Actually emit code to start a new stack frame.
614 // Save callee-save registers.
615 // Start new stack frame.
616 // Store link register in existing stack-cell.
617 // Order here should correspond to order of offset constants in header file.
618 RegList registers_to_retain = s0.bit() | s1.bit() | s2.bit() |
619 s3.bit() | s4.bit() | s5.bit() | s6.bit() | s7.bit() | fp.bit();
620 RegList argument_registers = a0.bit() | a1.bit() | a2.bit() | a3.bit();
621 __ MultiPush(argument_registers | registers_to_retain | ra.bit());
622 // Set frame pointer in space for it if this is not a direct call
623 // from generated code.
624 __ Addu(frame_pointer(), sp, Operand(4 * kPointerSize));
625 __ mov(a0, zero_reg);
626 __ push(a0); // Make room for success counter and initialize it to 0.
627 __ push(a0); // Make room for "position - 1" constant (value irrelevant).
629 // Check if we have space on the stack for registers.
630 Label stack_limit_hit;
633 ExternalReference stack_limit =
634 ExternalReference::address_of_stack_limit(masm_->isolate());
635 __ li(a0, Operand(stack_limit));
636 __ lw(a0, MemOperand(a0));
638 // Handle it if the stack pointer is already below the stack limit.
639 __ Branch(&stack_limit_hit, le, a0, Operand(zero_reg));
640 // Check if there is room for the variable number of registers above
642 __ Branch(&stack_ok, hs, a0, Operand(num_registers_ * kPointerSize));
643 // Exit with OutOfMemory exception. There is not enough space on the stack
644 // for our working registers.
645 __ li(v0, Operand(EXCEPTION));
648 __ bind(&stack_limit_hit);
649 CallCheckStackGuardState(a0);
650 // If returned value is non-zero, we exit with the returned value as result.
651 __ Branch(&return_v0, ne, v0, Operand(zero_reg));
654 // Allocate space on stack for registers.
655 __ Subu(sp, sp, Operand(num_registers_ * kPointerSize));
657 __ lw(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
659 __ lw(a0, MemOperand(frame_pointer(), kInputStart));
660 // Find negative length (offset of start relative to end).
661 __ Subu(current_input_offset(), a0, end_of_input_address());
662 // Set a0 to address of char before start of the input string
663 // (effectively string position -1).
664 __ lw(a1, MemOperand(frame_pointer(), kStartIndex));
665 __ Subu(a0, current_input_offset(), Operand(char_size()));
666 __ sll(t5, a1, (mode_ == UC16) ? 1 : 0);
668 // Store this value in a local variable, for use when clearing
669 // position registers.
670 __ sw(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
672 // Initialize code pointer register
673 __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
675 Label load_char_start_regexp, start_regexp;
676 // Load newline if index is at start, previous character otherwise.
677 __ Branch(&load_char_start_regexp, ne, a1, Operand(zero_reg));
678 __ li(current_character(), Operand('\n'));
679 __ jmp(&start_regexp);
681 // Global regexp restarts matching here.
682 __ bind(&load_char_start_regexp);
683 // Load previous char as initial value of current character register.
684 LoadCurrentCharacterUnchecked(-1, 1);
685 __ bind(&start_regexp);
687 // Initialize on-stack registers.
688 if (num_saved_registers_ > 0) { // Always is, if generated from a regexp.
689 // Fill saved registers with initial value = start offset - 1.
690 if (num_saved_registers_ > 8) {
691 // Address of register 0.
692 __ Addu(a1, frame_pointer(), Operand(kRegisterZero));
693 __ li(a2, Operand(num_saved_registers_));
696 __ sw(a0, MemOperand(a1));
697 __ Addu(a1, a1, Operand(-kPointerSize));
698 __ Subu(a2, a2, Operand(1));
699 __ Branch(&init_loop, ne, a2, Operand(zero_reg));
701 for (int i = 0; i < num_saved_registers_; i++) {
702 __ sw(a0, register_location(i));
707 // Initialize backtrack stack pointer.
708 __ lw(backtrack_stackpointer(), MemOperand(frame_pointer(), kStackHighEnd));
710 __ jmp(&start_label_);
714 if (success_label_.is_linked()) {
715 // Save captures when successful.
716 __ bind(&success_label_);
717 if (num_saved_registers_ > 0) {
718 // Copy captures to output.
719 __ lw(a1, MemOperand(frame_pointer(), kInputStart));
720 __ lw(a0, MemOperand(frame_pointer(), kRegisterOutput));
721 __ lw(a2, MemOperand(frame_pointer(), kStartIndex));
722 __ Subu(a1, end_of_input_address(), a1);
723 // a1 is length of input in bytes.
727 // a1 is length of input in characters.
728 __ Addu(a1, a1, Operand(a2));
729 // a1 is length of string in characters.
731 ASSERT_EQ(0, num_saved_registers_ % 2);
732 // Always an even number of capture registers. This allows us to
733 // unroll the loop once to add an operation between a load of a register
734 // and the following use of that register.
735 for (int i = 0; i < num_saved_registers_; i += 2) {
736 __ lw(a2, register_location(i));
737 __ lw(a3, register_location(i + 1));
738 if (i == 0 && global_with_zero_length_check()) {
739 // Keep capture start in a4 for the zero-length check later.
748 __ Addu(a2, a1, Operand(a2));
749 __ Addu(a3, a1, Operand(a3));
751 __ sw(a2, MemOperand(a0));
752 __ Addu(a0, a0, kPointerSize);
753 __ sw(a3, MemOperand(a0));
754 __ Addu(a0, a0, kPointerSize);
759 // Restart matching if the regular expression is flagged as global.
760 __ lw(a0, MemOperand(frame_pointer(), kSuccessfulCaptures));
761 __ lw(a1, MemOperand(frame_pointer(), kNumOutputRegisters));
762 __ lw(a2, MemOperand(frame_pointer(), kRegisterOutput));
763 // Increment success counter.
765 __ sw(a0, MemOperand(frame_pointer(), kSuccessfulCaptures));
766 // Capture results have been stored, so the number of remaining global
767 // output registers is reduced by the number of stored captures.
768 __ Subu(a1, a1, num_saved_registers_);
769 // Check whether we have enough room for another set of capture results.
771 __ Branch(&return_v0, lt, a1, Operand(num_saved_registers_));
773 __ sw(a1, MemOperand(frame_pointer(), kNumOutputRegisters));
774 // Advance the location for output.
775 __ Addu(a2, a2, num_saved_registers_ * kPointerSize);
776 __ sw(a2, MemOperand(frame_pointer(), kRegisterOutput));
778 // Prepare a0 to initialize registers with its value in the next run.
779 __ lw(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
781 if (global_with_zero_length_check()) {
782 // Special case for zero-length matches.
783 // t7: capture start index
784 // Not a zero-length match, restart.
786 &load_char_start_regexp, ne, current_input_offset(), Operand(t7));
787 // Offset from the end is zero if we already reached the end.
788 __ Branch(&exit_label_, eq, current_input_offset(),
790 // Advance current position after a zero-length match.
791 __ Addu(current_input_offset(),
792 current_input_offset(),
793 Operand((mode_ == UC16) ? 2 : 1));
796 __ Branch(&load_char_start_regexp);
798 __ li(v0, Operand(SUCCESS));
801 // Exit and return v0.
802 __ bind(&exit_label_);
804 __ lw(v0, MemOperand(frame_pointer(), kSuccessfulCaptures));
808 // Skip sp past regexp registers and local variables..
809 __ mov(sp, frame_pointer());
810 // Restore registers s0..s7 and return (restoring ra to pc).
811 __ MultiPop(registers_to_retain | ra.bit());
814 // Backtrack code (branch target for conditional backtracks).
815 if (backtrack_label_.is_linked()) {
816 __ bind(&backtrack_label_);
820 Label exit_with_exception;
823 if (check_preempt_label_.is_linked()) {
824 SafeCallTarget(&check_preempt_label_);
825 // Put regexp engine registers on stack.
826 RegList regexp_registers_to_retain = current_input_offset().bit() |
827 current_character().bit() | backtrack_stackpointer().bit();
828 __ MultiPush(regexp_registers_to_retain);
829 CallCheckStackGuardState(a0);
830 __ MultiPop(regexp_registers_to_retain);
831 // If returning non-zero, we should end execution with the given
832 // result as return value.
833 __ Branch(&return_v0, ne, v0, Operand(zero_reg));
835 // String might have moved: Reload end of string from frame.
836 __ lw(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
837 __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
841 // Backtrack stack overflow code.
842 if (stack_overflow_label_.is_linked()) {
843 SafeCallTarget(&stack_overflow_label_);
844 // Reached if the backtrack-stack limit has been hit.
845 // Put regexp engine registers on stack first.
846 RegList regexp_registers = current_input_offset().bit() |
847 current_character().bit();
848 __ MultiPush(regexp_registers);
850 // Call GrowStack(backtrack_stackpointer(), &stack_base)
851 static const int num_arguments = 3;
852 __ PrepareCallCFunction(num_arguments, a0);
853 __ mov(a0, backtrack_stackpointer());
854 __ Addu(a1, frame_pointer(), Operand(kStackHighEnd));
855 __ li(a2, Operand(ExternalReference::isolate_address(masm_->isolate())));
856 ExternalReference grow_stack =
857 ExternalReference::re_grow_stack(masm_->isolate());
858 __ CallCFunction(grow_stack, num_arguments);
859 // Restore regexp registers.
860 __ MultiPop(regexp_registers);
861 // If return NULL, we have failed to grow the stack, and
862 // must exit with a stack-overflow exception.
863 __ Branch(&exit_with_exception, eq, v0, Operand(zero_reg));
864 // Otherwise use return value as new stack pointer.
865 __ mov(backtrack_stackpointer(), v0);
866 // Restore saved registers and continue.
867 __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
868 __ lw(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
872 if (exit_with_exception.is_linked()) {
873 // If any of the code above needed to exit with an exception.
874 __ bind(&exit_with_exception);
875 // Exit with Result EXCEPTION(-1) to signal thrown exception.
876 __ li(v0, Operand(EXCEPTION));
882 masm_->GetCode(&code_desc);
883 Handle<Code> code = isolate()->factory()->NewCode(
884 code_desc, Code::ComputeFlags(Code::REGEXP), masm_->CodeObject());
885 LOG(masm_->isolate(), RegExpCodeCreateEvent(*code, *source));
886 return Handle<HeapObject>::cast(code);
890 void RegExpMacroAssemblerMIPS::GoTo(Label* to) {
900 void RegExpMacroAssemblerMIPS::IfRegisterGE(int reg,
903 __ lw(a0, register_location(reg));
904 BranchOrBacktrack(if_ge, ge, a0, Operand(comparand));
908 void RegExpMacroAssemblerMIPS::IfRegisterLT(int reg,
911 __ lw(a0, register_location(reg));
912 BranchOrBacktrack(if_lt, lt, a0, Operand(comparand));
916 void RegExpMacroAssemblerMIPS::IfRegisterEqPos(int reg,
918 __ lw(a0, register_location(reg));
919 BranchOrBacktrack(if_eq, eq, a0, Operand(current_input_offset()));
923 RegExpMacroAssembler::IrregexpImplementation
924 RegExpMacroAssemblerMIPS::Implementation() {
925 return kMIPSImplementation;
929 void RegExpMacroAssemblerMIPS::LoadCurrentCharacter(int cp_offset,
930 Label* on_end_of_input,
933 ASSERT(cp_offset >= -1); // ^ and \b can look behind one character.
934 ASSERT(cp_offset < (1<<30)); // Be sane! (And ensure negation works).
936 CheckPosition(cp_offset + characters - 1, on_end_of_input);
938 LoadCurrentCharacterUnchecked(cp_offset, characters);
942 void RegExpMacroAssemblerMIPS::PopCurrentPosition() {
943 Pop(current_input_offset());
947 void RegExpMacroAssemblerMIPS::PopRegister(int register_index) {
949 __ sw(a0, register_location(register_index));
953 void RegExpMacroAssemblerMIPS::PushBacktrack(Label* label) {
954 if (label->is_bound()) {
955 int target = label->pos();
956 __ li(a0, Operand(target + Code::kHeaderSize - kHeapObjectTag));
958 Assembler::BlockTrampolinePoolScope block_trampoline_pool(masm_);
959 Label after_constant;
960 __ Branch(&after_constant);
961 int offset = masm_->pc_offset();
962 int cp_offset = offset + Code::kHeaderSize - kHeapObjectTag;
964 masm_->label_at_put(label, offset);
965 __ bind(&after_constant);
966 if (is_int16(cp_offset)) {
967 __ lw(a0, MemOperand(code_pointer(), cp_offset));
969 __ Addu(a0, code_pointer(), cp_offset);
970 __ lw(a0, MemOperand(a0, 0));
978 void RegExpMacroAssemblerMIPS::PushCurrentPosition() {
979 Push(current_input_offset());
983 void RegExpMacroAssemblerMIPS::PushRegister(int register_index,
984 StackCheckFlag check_stack_limit) {
985 __ lw(a0, register_location(register_index));
987 if (check_stack_limit) CheckStackLimit();
991 void RegExpMacroAssemblerMIPS::ReadCurrentPositionFromRegister(int reg) {
992 __ lw(current_input_offset(), register_location(reg));
996 void RegExpMacroAssemblerMIPS::ReadStackPointerFromRegister(int reg) {
997 __ lw(backtrack_stackpointer(), register_location(reg));
998 __ lw(a0, MemOperand(frame_pointer(), kStackHighEnd));
999 __ Addu(backtrack_stackpointer(), backtrack_stackpointer(), Operand(a0));
1003 void RegExpMacroAssemblerMIPS::SetCurrentPositionFromEnd(int by) {
1004 Label after_position;
1005 __ Branch(&after_position,
1007 current_input_offset(),
1008 Operand(-by * char_size()));
1009 __ li(current_input_offset(), -by * char_size());
1010 // On RegExp code entry (where this operation is used), the character before
1011 // the current position is expected to be already loaded.
1012 // We have advanced the position, so it's safe to read backwards.
1013 LoadCurrentCharacterUnchecked(-1, 1);
1014 __ bind(&after_position);
1018 void RegExpMacroAssemblerMIPS::SetRegister(int register_index, int to) {
1019 ASSERT(register_index >= num_saved_registers_); // Reserved for positions!
1020 __ li(a0, Operand(to));
1021 __ sw(a0, register_location(register_index));
1025 bool RegExpMacroAssemblerMIPS::Succeed() {
1026 __ jmp(&success_label_);
1031 void RegExpMacroAssemblerMIPS::WriteCurrentPositionToRegister(int reg,
1033 if (cp_offset == 0) {
1034 __ sw(current_input_offset(), register_location(reg));
1036 __ Addu(a0, current_input_offset(), Operand(cp_offset * char_size()));
1037 __ sw(a0, register_location(reg));
1042 void RegExpMacroAssemblerMIPS::ClearRegisters(int reg_from, int reg_to) {
1043 ASSERT(reg_from <= reg_to);
1044 __ lw(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
1045 for (int reg = reg_from; reg <= reg_to; reg++) {
1046 __ sw(a0, register_location(reg));
1051 void RegExpMacroAssemblerMIPS::WriteStackPointerToRegister(int reg) {
1052 __ lw(a1, MemOperand(frame_pointer(), kStackHighEnd));
1053 __ Subu(a0, backtrack_stackpointer(), a1);
1054 __ sw(a0, register_location(reg));
1058 bool RegExpMacroAssemblerMIPS::CanReadUnaligned() {
1065 void RegExpMacroAssemblerMIPS::CallCheckStackGuardState(Register scratch) {
1066 int stack_alignment = OS::ActivationFrameAlignment();
1068 // Align the stack pointer and save the original sp value on the stack.
1069 __ mov(scratch, sp);
1070 __ Subu(sp, sp, Operand(kPointerSize));
1071 ASSERT(IsPowerOf2(stack_alignment));
1072 __ And(sp, sp, Operand(-stack_alignment));
1073 __ sw(scratch, MemOperand(sp));
1075 __ mov(a2, frame_pointer());
1077 __ li(a1, Operand(masm_->CodeObject()), CONSTANT_SIZE);
1079 // We need to make room for the return address on the stack.
1080 ASSERT(IsAligned(stack_alignment, kPointerSize));
1081 __ Subu(sp, sp, Operand(stack_alignment));
1083 // Stack pointer now points to cell where return address is to be written.
1084 // Arguments are in registers, meaning we teat the return address as
1085 // argument 5. Since DirectCEntryStub will handleallocating space for the C
1086 // argument slots, we don't need to care about that here. This is how the
1087 // stack will look (sp meaning the value of sp at this moment):
1088 // [sp + 3] - empty slot if needed for alignment.
1089 // [sp + 2] - saved sp.
1090 // [sp + 1] - second word reserved for return value.
1091 // [sp + 0] - first word reserved for return value.
1093 // a0 will point to the return address, placed by DirectCEntry.
1096 ExternalReference stack_guard_check =
1097 ExternalReference::re_check_stack_guard_state(masm_->isolate());
1098 __ li(t9, Operand(stack_guard_check));
1099 DirectCEntryStub stub;
1100 stub.GenerateCall(masm_, t9);
1102 // DirectCEntryStub allocated space for the C argument slots so we have to
1103 // drop them with the return address from the stack with loading saved sp.
1104 // At this point stack must look:
1105 // [sp + 7] - empty slot if needed for alignment.
1106 // [sp + 6] - saved sp.
1107 // [sp + 5] - second word reserved for return value.
1108 // [sp + 4] - first word reserved for return value.
1109 // [sp + 3] - C argument slot.
1110 // [sp + 2] - C argument slot.
1111 // [sp + 1] - C argument slot.
1112 // [sp + 0] - C argument slot.
1113 __ lw(sp, MemOperand(sp, stack_alignment + kCArgsSlotsSize));
1115 __ li(code_pointer(), Operand(masm_->CodeObject()));
1119 // Helper function for reading a value out of a stack frame.
1120 template <typename T>
1121 static T& frame_entry(Address re_frame, int frame_offset) {
1122 return reinterpret_cast<T&>(Memory::int32_at(re_frame + frame_offset));
1126 int RegExpMacroAssemblerMIPS::CheckStackGuardState(Address* return_address,
1129 Isolate* isolate = frame_entry<Isolate*>(re_frame, kIsolate);
1130 if (isolate->stack_guard()->IsStackOverflow()) {
1131 isolate->StackOverflow();
1135 // If not real stack overflow the stack guard was used to interrupt
1136 // execution for another purpose.
1138 // If this is a direct call from JavaScript retry the RegExp forcing the call
1139 // through the runtime system. Currently the direct call cannot handle a GC.
1140 if (frame_entry<int>(re_frame, kDirectCall) == 1) {
1144 // Prepare for possible GC.
1145 HandleScope handles(isolate);
1146 Handle<Code> code_handle(re_code);
1148 Handle<String> subject(frame_entry<String*>(re_frame, kInputString));
1150 bool is_ascii = subject->IsOneByteRepresentationUnderneath();
1152 ASSERT(re_code->instruction_start() <= *return_address);
1153 ASSERT(*return_address <=
1154 re_code->instruction_start() + re_code->instruction_size());
1156 MaybeObject* result = Execution::HandleStackGuardInterrupt(isolate);
1158 if (*code_handle != re_code) { // Return address no longer valid.
1159 int delta = code_handle->address() - re_code->address();
1160 // Overwrite the return address on the stack.
1161 *return_address += delta;
1164 if (result->IsException()) {
1168 Handle<String> subject_tmp = subject;
1169 int slice_offset = 0;
1171 // Extract the underlying string and the slice offset.
1172 if (StringShape(*subject_tmp).IsCons()) {
1173 subject_tmp = Handle<String>(ConsString::cast(*subject_tmp)->first());
1174 } else if (StringShape(*subject_tmp).IsSliced()) {
1175 SlicedString* slice = SlicedString::cast(*subject_tmp);
1176 subject_tmp = Handle<String>(slice->parent());
1177 slice_offset = slice->offset();
1180 // String might have changed.
1181 if (subject_tmp->IsOneByteRepresentation() != is_ascii) {
1182 // If we changed between an ASCII and an UC16 string, the specialized
1183 // code cannot be used, and we need to restart regexp matching from
1184 // scratch (including, potentially, compiling a new version of the code).
1188 // Otherwise, the content of the string might have moved. It must still
1189 // be a sequential or external string with the same content.
1190 // Update the start and end pointers in the stack frame to the current
1191 // location (whether it has actually moved or not).
1192 ASSERT(StringShape(*subject_tmp).IsSequential() ||
1193 StringShape(*subject_tmp).IsExternal());
1195 // The original start address of the characters to match.
1196 const byte* start_address = frame_entry<const byte*>(re_frame, kInputStart);
1198 // Find the current start address of the same character at the current string
1200 int start_index = frame_entry<int>(re_frame, kStartIndex);
1201 const byte* new_address = StringCharacterPosition(*subject_tmp,
1202 start_index + slice_offset);
1204 if (start_address != new_address) {
1205 // If there is a difference, update the object pointer and start and end
1206 // addresses in the RegExp stack frame to match the new value.
1207 const byte* end_address = frame_entry<const byte* >(re_frame, kInputEnd);
1208 int byte_length = static_cast<int>(end_address - start_address);
1209 frame_entry<const String*>(re_frame, kInputString) = *subject;
1210 frame_entry<const byte*>(re_frame, kInputStart) = new_address;
1211 frame_entry<const byte*>(re_frame, kInputEnd) = new_address + byte_length;
1212 } else if (frame_entry<const String*>(re_frame, kInputString) != *subject) {
1213 // Subject string might have been a ConsString that underwent
1214 // short-circuiting during GC. That will not change start_address but
1215 // will change pointer inside the subject handle.
1216 frame_entry<const String*>(re_frame, kInputString) = *subject;
1223 MemOperand RegExpMacroAssemblerMIPS::register_location(int register_index) {
1224 ASSERT(register_index < (1<<30));
1225 if (num_registers_ <= register_index) {
1226 num_registers_ = register_index + 1;
1228 return MemOperand(frame_pointer(),
1229 kRegisterZero - register_index * kPointerSize);
1233 void RegExpMacroAssemblerMIPS::CheckPosition(int cp_offset,
1234 Label* on_outside_input) {
1235 BranchOrBacktrack(on_outside_input,
1237 current_input_offset(),
1238 Operand(-cp_offset * char_size()));
1242 void RegExpMacroAssemblerMIPS::BranchOrBacktrack(Label* to,
1243 Condition condition,
1245 const Operand& rt) {
1246 if (condition == al) { // Unconditional.
1255 __ Branch(&backtrack_label_, condition, rs, rt);
1258 __ Branch(to, condition, rs, rt);
1262 void RegExpMacroAssemblerMIPS::SafeCall(Label* to,
1265 const Operand& rt) {
1266 __ BranchAndLink(to, cond, rs, rt);
1270 void RegExpMacroAssemblerMIPS::SafeReturn() {
1272 __ Addu(t5, ra, Operand(masm_->CodeObject()));
1277 void RegExpMacroAssemblerMIPS::SafeCallTarget(Label* name) {
1279 __ Subu(ra, ra, Operand(masm_->CodeObject()));
1284 void RegExpMacroAssemblerMIPS::Push(Register source) {
1285 ASSERT(!source.is(backtrack_stackpointer()));
1286 __ Addu(backtrack_stackpointer(),
1287 backtrack_stackpointer(),
1288 Operand(-kPointerSize));
1289 __ sw(source, MemOperand(backtrack_stackpointer()));
1293 void RegExpMacroAssemblerMIPS::Pop(Register target) {
1294 ASSERT(!target.is(backtrack_stackpointer()));
1295 __ lw(target, MemOperand(backtrack_stackpointer()));
1296 __ Addu(backtrack_stackpointer(), backtrack_stackpointer(), kPointerSize);
1300 void RegExpMacroAssemblerMIPS::CheckPreemption() {
1301 // Check for preemption.
1302 ExternalReference stack_limit =
1303 ExternalReference::address_of_stack_limit(masm_->isolate());
1304 __ li(a0, Operand(stack_limit));
1305 __ lw(a0, MemOperand(a0));
1306 SafeCall(&check_preempt_label_, ls, sp, Operand(a0));
1310 void RegExpMacroAssemblerMIPS::CheckStackLimit() {
1311 ExternalReference stack_limit =
1312 ExternalReference::address_of_regexp_stack_limit(masm_->isolate());
1314 __ li(a0, Operand(stack_limit));
1315 __ lw(a0, MemOperand(a0));
1316 SafeCall(&stack_overflow_label_, ls, backtrack_stackpointer(), Operand(a0));
1320 void RegExpMacroAssemblerMIPS::LoadCurrentCharacterUnchecked(int cp_offset,
1322 Register offset = current_input_offset();
1323 if (cp_offset != 0) {
1324 // t7 is not being used to store the capture start index at this point.
1325 __ Addu(t7, current_input_offset(), Operand(cp_offset * char_size()));
1328 // We assume that we cannot do unaligned loads on MIPS, so this function
1329 // must only be used to load a single character at a time.
1330 ASSERT(characters == 1);
1331 __ Addu(t5, end_of_input_address(), Operand(offset));
1332 if (mode_ == ASCII) {
1333 __ lbu(current_character(), MemOperand(t5, 0));
1335 ASSERT(mode_ == UC16);
1336 __ lhu(current_character(), MemOperand(t5, 0));
1343 #endif // V8_INTERPRETED_REGEXP
1345 }} // namespace v8::internal
1347 #endif // V8_TARGET_ARCH_MIPS