Implement loop for global regexps in regexp assembler.

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

-// Copyright 2011 the V8 project authors. All rights reserved.
+// 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
 //       with the distribution.
@@ skipping 58 matching lines @@
  *
  * Each call to a C++ method should retain these registers.
  *
  * The stack will have the following content, in some order, indexable from the
  * frame pointer (see, e.g., kStackHighEnd):
  *    - Isolate* isolate     (Address of the current isolate)
  *    - direct_call          (if 1, direct call from JavaScript code, if 0 call
  *                            through the runtime system)
  *    - stack_area_base      (High end of the memory area to use as
  *                            backtracking stack)
+ *    - capture array size   (may fit multiple sets of matches)
  *    - int* capture_array   (int[num_saved_registers_], for output).
  *    - end of input         (Address of end of string)
  *    - start of input       (Address of first character in string)
  *    - start index          (character index of start)
  *    - String* input_string (input string)
  *    - return address
  *    - backup of callee save registers (rbx, possibly rsi and rdi).
+ *    - success counter      (only useful for global regexp to count matches)
  *    - Offset of location before start of input (effectively character
  *      position -1). Used to initialize capture registers to a non-position.
  *    - At start of string (if 1, we are starting at the start of the
  *      string, otherwise 0)
  *    - register 0  rbp[-n]   (Only positions must be stored in the first
  *    - register 1  rbp[-n-8]  num_saved_registers_ registers)
  *    - ...
  *
  * The first num_saved_registers_ registers are initialized to point to
  * "character -1" in the string (i.e., char_size() bytes before the first
@@ skipping 640 matching lines @@
     // Match any character.
     return true;
   // No custom implementation (yet): s(UC16), S(UC16).
   default:
     return false;
   }
 }
 
 
 void RegExpMacroAssemblerX64::Fail() {
-  ASSERT(FAILURE == 0);  // Return value for failure is zero.
-  __ Set(rax, 0);
+  STATIC_ASSERT(FAILURE == 0);  // Return value for failure is zero.
+  if (!global()) {
+    __ Set(rax, FAILURE);
+  }
   __ jmp(&exit_label_);
 }
 
 
 Handle<HeapObject> RegExpMacroAssemblerX64::GetCode(Handle<String> source) {
+  Label return_rax, restart;
   // 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.
@@ skipping 13 matching lines @@
   __ push(rdi);
   __ push(rbx);
 #else
   // GCC passes arguments in rdi, rsi, rdx, rcx, r8, r9 (and then on stack).
   // Push register parameters on stack for reference.
   ASSERT_EQ(kInputString, -1 * kPointerSize);
   ASSERT_EQ(kStartIndex, -2 * kPointerSize);
   ASSERT_EQ(kInputStart, -3 * kPointerSize);
   ASSERT_EQ(kInputEnd, -4 * kPointerSize);
   ASSERT_EQ(kRegisterOutput, -5 * kPointerSize);
-  ASSERT_EQ(kStackHighEnd, -6 * kPointerSize);
+  ASSERT_EQ(kNumOutputRegisters, -6 * kPointerSize);
   __ push(rdi);
   __ push(rsi);
   __ push(rdx);
   __ push(rcx);
   __ push(r8);
   __ push(r9);
 
   __ push(rbx);  // Callee-save
 #endif
 
+  __ push(Immediate(0));  // Number of successful matches in a global regexp.
   __ push(Immediate(0));  // Make room for "at start" constant.
 
   // 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());
   __ movq(rcx, rsp);
   __ movq(kScratchRegister, stack_limit);
   __ subq(rcx, Operand(kScratchRegister, 0));
   // Handle it if the stack pointer is already below the stack limit.
   __ j(below_equal, &stack_limit_hit);
   // Check if there is room for the variable number of registers above
   // the stack limit.
   __ cmpq(rcx, Immediate(num_registers_ * kPointerSize));
   __ j(above_equal, &stack_ok);
   // Exit with OutOfMemory exception. There is not enough space on the stack
   // for our working registers.
   __ Set(rax, EXCEPTION);
-  __ jmp(&exit_label_);
+  __ jmp(&return_rax);
 
   __ bind(&stack_limit_hit);
   __ Move(code_object_pointer(), masm_.CodeObject());
   CallCheckStackGuardState();  // Preserves no registers beside rbp and rsp.
   __ testq(rax, rax);
   // If returned value is non-zero, we exit with the returned value as result.
-  __ j(not_zero, &exit_label_);
+  __ j(not_zero, &return_rax);
 
   __ bind(&stack_ok);
 
   // Allocate space on stack for registers.
   __ subq(rsp, Immediate(num_registers_ * kPointerSize));
   // Load string length.
   __ movq(rsi, Operand(rbp, kInputEnd));
   // Load input position.
   __ movq(rdi, Operand(rbp, kInputStart));
   // Set up rdi to be negative offset from string end.
   __ subq(rdi, rsi);
   // Set rax to address of char before start of the string
   // (effectively string position -1).
   __ movq(rbx, Operand(rbp, kStartIndex));
   __ neg(rbx);
   if (mode_ == UC16) {
     __ lea(rax, Operand(rdi, rbx, times_2, -char_size()));
   } else {
     __ lea(rax, Operand(rdi, rbx, times_1, -char_size()));
   }
   // Store this value in a local variable, for use when clearing
   // position registers.
   __ movq(Operand(rbp, kInputStartMinusOne), rax);
 
+  // Initialize code object pointer.
+  __ Move(code_object_pointer(), masm_.CodeObject());
+
+  // Load previous char as initial value of current-character.
+  Label at_start, character_loaded;
+  __ cmpb(Operand(rbp, kStartIndex), Immediate(0));
+  __ j(equal, &at_start, Label::kNear);
+  LoadCurrentCharacterUnchecked(-1, 1);  // Load previous char.
+  __ jmp(&character_loaded, Label::kNear);
+  __ bind(&at_start);
+  __ Set(current_character(), '\n');
+
+  if (global()) {
+    // Initializing current-character already done, so skip it.
+    __ jmp(&character_loaded, Label::kNear);
+    // Restart matching from here in a global regexp.
+    __ bind(&restart);
+    // In a restarted pass, initialize current-character here.
+    LoadCurrentCharacterUnchecked(-1, 1);
+  }
+  __ bind(&character_loaded);
+
+  // Initialize on-stack registers.
   if (num_saved_registers_ > 0) {
     // Fill saved registers with initial value = start offset - 1
     // Fill in stack push order, to avoid accessing across an unwritten
     // page (a problem on Windows).
-    __ Set(rcx, kRegisterZero);
-    Label init_loop;
-    __ bind(&init_loop);
-    __ movq(Operand(rbp, rcx, times_1, 0), rax);
-    __ subq(rcx, Immediate(kPointerSize));
-    __ cmpq(rcx,
-            Immediate(kRegisterZero - num_saved_registers_ * kPointerSize));
-    __ j(greater, &init_loop);
-  }
-  // Ensure that we have written to each stack page, in order. Skipping a page
-  // on Windows can cause segmentation faults. Assuming page size is 4k.
-  const int kPageSize = 4096;
-  const int kRegistersPerPage = kPageSize / kPointerSize;
-  for (int i = num_saved_registers_ + kRegistersPerPage - 1;
-      i < num_registers_;
-      i += kRegistersPerPage) {
-    __ movq(register_location(i), rax);  // One write every page.
+    if (num_saved_registers_ > 8) {
+      __ Set(rcx, kRegisterZero);
+      Label init_loop;
+      __ bind(&init_loop);
+      __ movq(Operand(rbp, rcx, times_1, 0), rax);
+      __ subq(rcx, Immediate(kPointerSize));
+      __ cmpq(rcx,
+              Immediate(kRegisterZero - num_saved_registers_ * kPointerSize));
+      __ j(greater, &init_loop);
+    } else {  // Unroll the loop.
+      for (int i = 0; i < num_saved_registers_; i++) {
+        __ movq(register_location(i), rax);
+      }
+    }
   }
 
   // Initialize backtrack stack pointer.
   __ movq(backtrack_stackpointer(), Operand(rbp, kStackHighEnd));
-  // Initialize code object pointer.
-  __ Move(code_object_pointer(), masm_.CodeObject());
-  // Load previous char as initial value of current-character.
-  Label at_start;
-  __ cmpb(Operand(rbp, kStartIndex), Immediate(0));
-  __ j(equal, &at_start);
-  LoadCurrentCharacterUnchecked(-1, 1);  // Load previous char.
+
   __ jmp(&start_label_);
-  __ bind(&at_start);
-  __ Set(current_character(), '\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
       __ movq(rdx, Operand(rbp, kStartIndex));
       __ movq(rbx, Operand(rbp, kRegisterOutput));
       __ movq(rcx, Operand(rbp, kInputEnd));
       __ subq(rcx, Operand(rbp, kInputStart));
       if (mode_ == UC16) {
         __ lea(rcx, Operand(rcx, rdx, times_2, 0));
       } else {
         __ addq(rcx, rdx);
       }
       for (int i = 0; i < num_saved_registers_; i++) {
         __ movq(rax, register_location(i));
+        if (i == 0 && global()) {
+          // Keep capture start in rdx for the zero-length check later.
+          __ movq(rdx, rax);
+        }
         __ addq(rax, rcx);  // Convert to index from start, not end.
         if (mode_ == UC16) {
           __ sar(rax, Immediate(1));  // Convert byte index to character index.
         }
         __ movl(Operand(rbx, i * kIntSize), rax);
       }
     }
-    __ Set(rax, SUCCESS);
+
+    if (global()) {
+      // Restart matching if the regular expression is flagged as global.
+      // Increment success counter.
+      __ incq(Operand(rbp, kSuccessfulCaptures));
+      // Capture results have been stored, so the number of remaining global
+      // output registers is reduced by the number of stored captures.
+      __ movq(rcx, Operand(rbp, kNumOutputRegisters));
+      __ subq(rcx, Immediate(num_saved_registers_));
+      // Check whether we have enough room for another set of capture results.
+      __ cmpq(rcx, Immediate(num_saved_registers_));
+      __ j(less, &exit_label_);
+
+      __ movq(Operand(rbp, kNumOutputRegisters), rcx);
+      // Advance the location for output.
+      __ addq(Operand(rbp, kRegisterOutput),
+              Immediate(num_saved_registers_ * kIntSize));
+
+      // Prepare rax to initialize registers with its value in the next run.
+      __ movq(rax, Operand(rbp, kInputStartMinusOne));
+
+      // Special case for zero-length matches.
+      // rdx: capture start index
+      __ cmpq(rdi, rdx);
+      // Not a zero-length match, restart.
+      __ j(not_equal, &restart);
+      // rdi (offset from the end) is zero if we already reached the end.
+      __ testq(rdi, rdi);
+      __ j(zero, &exit_label_, Label::kNear);
+      // Advance current position after a zero-length match.
+      if (mode_ == UC16) {
+        __ addq(rdi, Immediate(2));
+      } else {
+        __ incq(rdi);
+      }
+      __ jmp(&restart);
+    } else {
+      __ movq(rax, Immediate(SUCCESS));
+    }
   }
 
-  // Exit and return rax
   __ bind(&exit_label_);
+  if (global()) {
+    // Return the number of successful captures.
+    __ movq(rax, Operand(rbp, kSuccessfulCaptures));
+  }
 
+  __ bind(&return_rax);
 #ifdef _WIN64
   // Restore callee save registers.
   __ lea(rsp, Operand(rbp, kLastCalleeSaveRegister));
   __ pop(rbx);
   __ pop(rdi);
   __ pop(rsi);
   // Stack now at rbp.
 #else
   // Restore callee save register.
   __ movq(rbx, Operand(rbp, kBackup_rbx));
@@ skipping 16 matching lines @@
   if (check_preempt_label_.is_linked()) {
     SafeCallTarget(&check_preempt_label_);
 
     __ push(backtrack_stackpointer());
     __ push(rdi);
 
     CallCheckStackGuardState();
     __ testq(rax, rax);
     // If returning non-zero, we should end execution with the given
     // result as return value.
-    __ j(not_zero, &exit_label_);
+    __ j(not_zero, &return_rax);
 
     // Restore registers.
     __ Move(code_object_pointer(), masm_.CodeObject());
     __ pop(rdi);
     __ pop(backtrack_stackpointer());
     // String might have moved: Reload esi from frame.
     __ movq(rsi, Operand(rbp, kInputEnd));
     SafeReturn();
   }
 
@@ skipping 40 matching lines @@
     __ pop(rsi);
 #endif
     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.
     __ Set(rax, EXCEPTION);
-    __ jmp(&exit_label_);
+    __ jmp(&return_rax);
   }
 
   FixupCodeRelativePositions();
 
   CodeDesc code_desc;
   masm_.GetCode(&code_desc);
   Isolate* isolate = ISOLATE;
   Handle<Code> code = isolate->factory()->NewCode(
       code_desc, Code::ComputeFlags(Code::REGEXP),
       masm_.CodeObject());
@@ skipping 434 matching lines @@
   }
 }
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }}  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_X64