MIPS: Implement loop for global regexps in regexp assembler.

src/mips/regexp-macro-assembler-mips.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 25 matching lines @@
 #include "macro-assembler.h"
 #include "regexp-macro-assembler.h"
 #include "mips/regexp-macro-assembler-mips.h"
 
 namespace v8 {
 namespace internal {
 
 #ifndef V8_INTERPRETED_REGEXP
 /*
  * This assembler uses the following register assignment convention
+ * - t7 : Temporarily stores the index of capture start after a matching pass
+ *        for a global regexp.
  * - t1 : Pointer to current code object (Code*) including heap object tag.
  * - t2 : Current position in input, as negative offset from end of string.
  *        Please notice that this is the byte offset, not the character offset!
  * - t3 : Currently loaded character. Must be loaded using
  *        LoadCurrentCharacter before using any of the dispatch methods.
- * - t4 : points to tip of backtrack stack
+ * - t4 : Points to tip of backtrack stack
  * - t5 : Unused.
  * - t6 : End of input (points to byte after last character in input).
  * - fp : Frame pointer. Used to access arguments, local variables and
  *         RegExp registers.
- * - sp : points to tip of C stack.
+ * - sp : Points to tip of C stack.
  *
  * The remaining registers are free for computations.
  * Each call to a public method should retain this convention.
  *
  * The stack will have the following structure:
  *
- *  - fp[56]  direct_call  (if 1, direct call from JavaScript code,
+ *  - fp[64]  Isolate* isolate   (address of the current isolate)
+ *  - fp[60]  direct_call  (if 1, direct call from JavaScript code,
  *                          if 0, call through the runtime system).
- *  - fp[52]  stack_area_base (High end of the memory area to use as
+ *  - fp[56]  stack_area_base (High end of the memory area to use as
  *                             backtracking stack).
+ *  - fp[52]  capture array size (may fit multiple sets of matches)
  *  - fp[48]  int* capture_array (int[num_saved_registers_], for output).
  *  - fp[44]  secondary link/return address used by native call.
  *  --- sp when called ---
- *  - fp[40]  return address (lr).
- *  - fp[36]  old frame pointer (r11).
+ *  - fp[40]  return address      (lr).
+ *  - fp[36]  old frame pointer   (r11).
  *  - fp[0..32]  backup of registers s0..s7.
  *  --- frame pointer ----
- *  - fp[-4]  end of input       (Address of end of string).
- *  - fp[-8]  start of input     (Address of first character in string).
+ *  - fp[-4]  end of input       (address of end of string).
+ *  - fp[-8]  start of input     (address of first character in string).
  *  - fp[-12] start index        (character index of start).
  *  - fp[-16] void* input_string (location of a handle containing the string).
- *  - fp[-20] Offset of location before start of input (effectively character
+ *  - fp[-20] success counter    (only for global regexps to count matches).
+ *  - fp[-24] Offset of location before start of input (effectively character
  *            position -1). Used to initialize capture registers to a
  *            non-position.
- *  - fp[-24] At start (if 1, we are starting at the start of the
+ *  - fp[-28] At start (if 1, we are starting at the start of the
  *    string, otherwise 0)
- *  - fp[-28] register 0         (Only positions must be stored in the first
+ *  - fp[-32] register 0         (Only positions must be stored in the first
  *  -         register 1          num_saved_registers_ registers)
  *  -         ...
  *  -         register num_registers-1
  *  --- sp ---
  *
  * The first num_saved_registers_ registers are initialized to point to
  * "character -1" in the string (i.e., char_size() bytes before the first
  * character of the string). The remaining registers start out as garbage.
  *
  * The data up to the return address must be placed there by the calling
@@ skipping 100 matching lines @@
 
 
 void RegExpMacroAssemblerMIPS::CheckCharacterGT(uc16 limit, Label* on_greater) {
   BranchOrBacktrack(on_greater, gt, current_character(), Operand(limit));
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckAtStart(Label* on_at_start) {
   Label not_at_start;
   // Did we start the match at the start of the string at all?
-  __ lw(a0, MemOperand(frame_pointer(), kAtStart));
-  BranchOrBacktrack(&not_at_start, eq, a0, Operand(zero_reg));
+  __ lw(a0, MemOperand(frame_pointer(), kStartIndex));
+  BranchOrBacktrack(&not_at_start, ne, a0, Operand(zero_reg));
 
   // If we did, are we still at the start of the input?
   __ lw(a1, MemOperand(frame_pointer(), kInputStart));
   __ Addu(a0, end_of_input_address(), Operand(current_input_offset()));
   BranchOrBacktrack(on_at_start, eq, a0, Operand(a1));
   __ bind(&not_at_start);
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckNotAtStart(Label* on_not_at_start) {
   // Did we start the match at the start of the string at all?
-  __ lw(a0, MemOperand(frame_pointer(), kAtStart));
-  BranchOrBacktrack(on_not_at_start, eq, a0, Operand(zero_reg));
+  __ lw(a0, MemOperand(frame_pointer(), kStartIndex));
+  BranchOrBacktrack(on_not_at_start, ne, a0, Operand(zero_reg));
   // If we did, are we still at the start of the input?
   __ lw(a1, MemOperand(frame_pointer(), kInputStart));
   __ Addu(a0, end_of_input_address(), Operand(current_input_offset()));
   BranchOrBacktrack(on_not_at_start, ne, a0, Operand(a1));
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckCharacterLT(uc16 limit, Label* on_less) {
   BranchOrBacktrack(on_less, lt, current_character(), Operand(limit));
 }
@@ skipping 404 matching lines @@
 }
 
 
 void RegExpMacroAssemblerMIPS::Fail() {
   __ li(v0, Operand(FAILURE));
   __ jmp(&exit_label_);
 }
 
 
 Handle<HeapObject> RegExpMacroAssemblerMIPS::GetCode(Handle<String> source) {
+  Label return_v0;
   if (masm_->has_exception()) {
     // If the code gets corrupted due to long regular expressions and lack of
     // space on trampolines, an internal exception flag is set. If this case
     // is detected, we will jump into exit sequence right away.
     __ bind_to(&entry_label_, internal_failure_label_.pos());
   } else {
     // Finalize code - write the entry point code now we know how many
     // registers we need.
 
     // Entry code:
     __ bind(&entry_label_);
 
     // Tell the system that we have a stack frame.  Because the type is MANUAL,
     // no is generated.
     FrameScope scope(masm_, StackFrame::MANUAL);
 
     // Actually emit code to start a new stack frame.
     // Push arguments
     // Save callee-save registers.
     // Start new stack frame.
     // Store link register in existing stack-cell.
     // Order here should correspond to order of offset constants in header file.
     RegList registers_to_retain = s0.bit() | s1.bit() | s2.bit() |
         s3.bit() | s4.bit() | s5.bit() | s6.bit() | s7.bit() | fp.bit();
     RegList argument_registers = a0.bit() | a1.bit() | a2.bit() | a3.bit();
     __ MultiPush(argument_registers | registers_to_retain | ra.bit());
     // Set frame pointer in space for it if this is not a direct call
     // from generated code.
     __ Addu(frame_pointer(), sp, Operand(4 * kPointerSize));
+    __ mov(a0, zero_reg);
+    __ push(a0);  // Make room for success counter and initialize it to 0.
     __ push(a0);  // Make room for "position - 1" constant (value irrelevant).
-    __ push(a0);  // Make room for "at start" constant (value irrelevant).
 
     // Check if we have space on the stack for registers.
     Label stack_limit_hit;
     Label stack_ok;
 
     ExternalReference stack_limit =
         ExternalReference::address_of_stack_limit(masm_->isolate());
     __ li(a0, Operand(stack_limit));
     __ lw(a0, MemOperand(a0));
     __ Subu(a0, sp, a0);
     // Handle it if the stack pointer is already below the stack limit.
     __ Branch(&stack_limit_hit, le, a0, Operand(zero_reg));
     // Check if there is room for the variable number of registers above
     // the stack limit.
     __ Branch(&stack_ok, hs, a0, Operand(num_registers_ * kPointerSize));
     // Exit with OutOfMemory exception. There is not enough space on the stack
     // for our working registers.
     __ li(v0, Operand(EXCEPTION));
-    __ jmp(&exit_label_);
+    __ jmp(&return_v0);
 
     __ bind(&stack_limit_hit);
     CallCheckStackGuardState(a0);
     // If returned value is non-zero, we exit with the returned value as result.
-    __ Branch(&exit_label_, ne, v0, Operand(zero_reg));
+    __ Branch(&return_v0, ne, v0, Operand(zero_reg));
 
     __ bind(&stack_ok);
     // Allocate space on stack for registers.
     __ Subu(sp, sp, Operand(num_registers_ * kPointerSize));
     // Load string end.
     __ lw(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
     // Load input start.
     __ lw(a0, MemOperand(frame_pointer(), kInputStart));
     // Find negative length (offset of start relative to end).
     __ Subu(current_input_offset(), a0, end_of_input_address());
     // Set a0 to address of char before start of the input string
     // (effectively string position -1).
     __ lw(a1, MemOperand(frame_pointer(), kStartIndex));
     __ Subu(a0, current_input_offset(), Operand(char_size()));
     __ sll(t5, a1, (mode_ == UC16) ? 1 : 0);
     __ Subu(a0, a0, t5);
     // Store this value in a local variable, for use when clearing
     // position registers.
     __ sw(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
 
-    // Determine whether the start index is zero, that is at the start of the
-    // string, and store that value in a local variable.
-    __ mov(t5, a1);
-    __ li(a1, Operand(1));
-    __ Movn(a1, zero_reg, t5);
-    __ sw(a1, MemOperand(frame_pointer(), kAtStart));
+    // Initialize code pointer register
+    __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
 
+    Label load_char_start_regexp, start_regexp;
+    // Load newline if index is at start, previous character otherwise.
+    __ Branch(&load_char_start_regexp, ne, a1, Operand(zero_reg));
+    __ li(current_character(), Operand('\n'));
+    __ jmp(&start_regexp);
+
+    // Global regexp restarts matching here.
+    __ bind(&load_char_start_regexp);
+    // Load previous char as initial value of current character register.
+    LoadCurrentCharacterUnchecked(-1, 1);
+    __ bind(&start_regexp);
+
+    // Initialize on-stack registers.
     if (num_saved_registers_ > 0) {  // Always is, if generated from a regexp.
       // Fill saved registers with initial value = start offset - 1.
-
-      // Address of register 0.
-      __ Addu(a1, frame_pointer(), Operand(kRegisterZero));
-      __ li(a2, Operand(num_saved_registers_));
-      Label init_loop;
-      __ bind(&init_loop);
-      __ sw(a0, MemOperand(a1));
-      __ Addu(a1, a1, Operand(-kPointerSize));
-      __ Subu(a2, a2, Operand(1));
-      __ Branch(&init_loop, ne, a2, Operand(zero_reg));
+      if (num_saved_registers_ > 8) {
+        // Address of register 0.
+        __ Addu(a1, frame_pointer(), Operand(kRegisterZero));
+        __ li(a2, Operand(num_saved_registers_));
+        Label init_loop;
+        __ bind(&init_loop);
+        __ sw(a0, MemOperand(a1));
+        __ Addu(a1, a1, Operand(-kPointerSize));
+        __ Subu(a2, a2, Operand(1));
+        __ Branch(&init_loop, ne, a2, Operand(zero_reg));
+      } else {
+        for (int i = 0; i < num_saved_registers_; i++) {
+          __ sw(a0, register_location(i));
+        }
+      }
     }
 
     // Initialize backtrack stack pointer.
     __ lw(backtrack_stackpointer(), MemOperand(frame_pointer(), kStackHighEnd));
-    // Initialize code pointer register
-    __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
-    // Load previous char as initial value of current character register.
-    Label at_start;
-    __ lw(a0, MemOperand(frame_pointer(), kAtStart));
-    __ Branch(&at_start, ne, a0, Operand(zero_reg));
-    LoadCurrentCharacterUnchecked(-1, 1);  // Load previous char.
-    __ jmp(&start_label_);
-    __ bind(&at_start);
-    __ li(current_character(), Operand('\n'));
+
     __ jmp(&start_label_);
 
 
     // Exit code:
     if (success_label_.is_linked()) {
       // Save captures when successful.
       __ bind(&success_label_);
       if (num_saved_registers_ > 0) {
         // Copy captures to output.
         __ lw(a1, MemOperand(frame_pointer(), kInputStart));
         __ lw(a0, MemOperand(frame_pointer(), kRegisterOutput));
         __ lw(a2, MemOperand(frame_pointer(), kStartIndex));
         __ Subu(a1, end_of_input_address(), a1);
         // a1 is length of input in bytes.
         if (mode_ == UC16) {
           __ srl(a1, a1, 1);
         }
         // a1 is length of input in characters.
         __ Addu(a1, a1, Operand(a2));
         // a1 is length of string in characters.
 
         ASSERT_EQ(0, num_saved_registers_ % 2);
         // Always an even number of capture registers. This allows us to
         // unroll the loop once to add an operation between a load of a register
         // and the following use of that register.
         for (int i = 0; i < num_saved_registers_; i += 2) {
           __ lw(a2, register_location(i));
           __ lw(a3, register_location(i + 1));
+          if (global()) {
+            // Keep capture start in a4 for the zero-length check later.
+            __ mov(t7, a2);
+          }
           if (mode_ == UC16) {
             __ sra(a2, a2, 1);
             __ Addu(a2, a2, a1);
             __ sra(a3, a3, 1);
             __ Addu(a3, a3, a1);
           } else {
             __ Addu(a2, a1, Operand(a2));
             __ Addu(a3, a1, Operand(a3));
           }
           __ sw(a2, MemOperand(a0));
           __ Addu(a0, a0, kPointerSize);
           __ sw(a3, MemOperand(a0));
           __ Addu(a0, a0, kPointerSize);
         }
       }
-      __ li(v0, Operand(SUCCESS));
+
+      if (global()) {
+        // Restart matching if the regular expression is flagged as global.
+        __ lw(a0, MemOperand(frame_pointer(), kSuccessfulCaptures));
+        __ lw(a1, MemOperand(frame_pointer(), kNumOutputRegisters));
+        __ lw(a2, MemOperand(frame_pointer(), kRegisterOutput));
+        // Increment success counter.
+        __ Addu(a0, a0, 1);
+        __ sw(a0, MemOperand(frame_pointer(), kSuccessfulCaptures));
+        // Capture results have been stored, so the number of remaining global
+        // output registers is reduced by the number of stored captures.
+        __ Subu(a1, a1, num_saved_registers_);
+        // Check whether we have enough room for another set of capture results.
+        __ mov(v0, a0);
+        __ Branch(&return_v0, lt, a1, Operand(num_saved_registers_));
+
+        __ sw(a1, MemOperand(frame_pointer(), kNumOutputRegisters));
+        // Advance the location for output.
+        __ Addu(a2, a2, num_saved_registers_ * kPointerSize);
+        __ sw(a2, MemOperand(frame_pointer(), kRegisterOutput));
+
+        // Prepare a0 to initialize registers with its value in the next run.
+        __ lw(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
+        // Special case for zero-length matches.
+        // t7: capture start index
+        // Not a zero-length match, restart.
+        __ Branch(&load_char_start_regexp, ne, current_input_offset(), Operand(t7));
+        // Offset from the end is zero if we already reached the end.
+        __ Branch(&exit_label_, eq, current_input_offset(), Operand(zero_reg));
+        // Advance current position after a zero-length match.
+        __ Addu(current_input_offset(),
+                current_input_offset(),
+                Operand((mode_ == UC16) ? 2 : 1));
+        __ Branch(&load_char_start_regexp);
+      } else {
+        __ li(v0, Operand(SUCCESS));
+      }
     }
     // Exit and return v0.
     __ bind(&exit_label_);
+    if (global()) {
+      __ lw(v0, MemOperand(frame_pointer(), kSuccessfulCaptures));
+    }
+
+    __ bind(&return_v0);
     // Skip sp past regexp registers and local variables..
     __ mov(sp, frame_pointer());
     // Restore registers s0..s7 and return (restoring ra to pc).
     __ MultiPop(registers_to_retain | ra.bit());
     __ Ret();
 
     // Backtrack code (branch target for conditional backtracks).
     if (backtrack_label_.is_linked()) {
       __ bind(&backtrack_label_);
       Backtrack();
     }
 
     Label exit_with_exception;
 
     // Preempt-code.
     if (check_preempt_label_.is_linked()) {
       SafeCallTarget(&check_preempt_label_);
       // Put regexp engine registers on stack.
       RegList regexp_registers_to_retain = current_input_offset().bit() |
           current_character().bit() | backtrack_stackpointer().bit();
       __ MultiPush(regexp_registers_to_retain);
       CallCheckStackGuardState(a0);
       __ MultiPop(regexp_registers_to_retain);
       // If returning non-zero, we should end execution with the given
       // result as return value.
-      __ Branch(&exit_label_, ne, v0, Operand(zero_reg));
+      __ Branch(&return_v0, ne, v0, Operand(zero_reg));
 
       // String might have moved: Reload end of string from frame.
       __ lw(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
       __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
       SafeReturn();
     }
 
     // Backtrack stack overflow code.
     if (stack_overflow_label_.is_linked()) {
       SafeCallTarget(&stack_overflow_label_);
@@ skipping 23 matching lines @@
       __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
       __ lw(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
       SafeReturn();
     }
 
     if (exit_with_exception.is_linked()) {
       // If any of the code above needed to exit with an exception.
       __ bind(&exit_with_exception);
       // Exit with Result EXCEPTION(-1) to signal thrown exception.
       __ li(v0, Operand(EXCEPTION));
-      __ jmp(&exit_label_);
+      __ jmp(&return_v0);
     }
   }
 
   CodeDesc code_desc;
   masm_->GetCode(&code_desc);
   Handle<Code> code = FACTORY->NewCode(code_desc,
                                        Code::ComputeFlags(Code::REGEXP),
                                        masm_->CodeObject());
   LOG(Isolate::Current(), RegExpCodeCreateEvent(*code, *source));
   return Handle<HeapObject>::cast(code);
@@ skipping 127 matching lines @@
 }
 
 
 void RegExpMacroAssemblerMIPS::SetRegister(int register_index, int to) {
   ASSERT(register_index >= num_saved_registers_);  // Reserved for positions!
   __ li(a0, Operand(to));
   __ sw(a0, register_location(register_index));
 }
 
 
-void RegExpMacroAssemblerMIPS::Succeed() {
+bool RegExpMacroAssemblerMIPS::Succeed() {
   __ jmp(&success_label_);
+  return global();
 }
 
 
 void RegExpMacroAssemblerMIPS::WriteCurrentPositionToRegister(int reg,
                                                               int cp_offset) {
   if (cp_offset == 0) {
     __ sw(current_input_offset(), register_location(reg));
   } else {
     __ Addu(a0, current_input_offset(), Operand(cp_offset * char_size()));
     __ sw(a0, register_location(reg));
@@ skipping 246 matching lines @@
     __ lw(sp, MemOperand(sp, 16));
   }
   __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
 }
 
 
 void RegExpMacroAssemblerMIPS::LoadCurrentCharacterUnchecked(int cp_offset,
                                                              int characters) {
   Register offset = current_input_offset();
   if (cp_offset != 0) {
-    __ Addu(a0, current_input_offset(), Operand(cp_offset * char_size()));
-    offset = a0;
+    // t7 is not being used to store the capture start index at this point.
+    __ Addu(t7, current_input_offset(), Operand(cp_offset * char_size()));
+    offset = t7;
   }
   // We assume that we cannot do unaligned loads on MIPS, so this function
   // must only be used to load a single character at a time.
   ASSERT(characters == 1);
   __ Addu(t5, end_of_input_address(), Operand(offset));
   if (mode_ == ASCII) {
     __ lbu(current_character(), MemOperand(t5, 0));
   } else {
     ASSERT(mode_ == UC16);
     __ lhu(current_character(), MemOperand(t5, 0));
@@ skipping 18 matching lines @@
 }
 
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }}  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_MIPS