Implement loop for global regexps in regexp assembler.

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

-// Copyright 2009 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 23 matching lines @@
 #include "regexp-stack.h"
 #include "macro-assembler.h"
 #include "regexp-macro-assembler.h"
 #include "arm/regexp-macro-assembler-arm.h"
 
 namespace v8 {
 namespace internal {
 
 #ifndef V8_INTERPRETED_REGEXP
 /*
  * This assembler uses the following register assignment convention

[Erik Corry, 2012/05/22 08:32:46]

This needs updating to include r4

[Yang, 2012/05/22 14:48:03]

Done.

  * - r5 : Pointer to current code object (Code*) including heap object tag.
  * - r6 : Current position in input, as negative offset from end of string.
  *        Please notice that this is the byte offset, not the character offset!
  * - r7 : Currently loaded character. Must be loaded using
  *        LoadCurrentCharacter before using any of the dispatch methods.
  * - r8 : points to tip of backtrack stack
  * - r9 : Unused, might be used by C code and expected unchanged.
  * - r10 : End of input (points to byte after last character in input).
  * - r11 : Frame pointer. Used to access arguments, local variables and
  *         RegExp registers.
  * - r12 : IP register, used by assembler. Very volatile.
  * - r13/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[52]  Isolate* isolate   (Address of the current isolate)
- *  - fp[48]  direct_call  (if 1, direct call from JavaScript code,
- *                          if 0, call through the runtime system).
- *  - fp[44]  stack_area_base (High end of the memory area to use as
- *                             backtracking stack).
+ *  - fp[56]  Isolate* isolate   (Address of the current isolate)
+ *  - fp[52]  direct_call        (if 1, direct call from JavaScript code,
+ *                                if 0, call through the runtime system).
+ *  - fp[48]  stack_area_base    (High end of the memory area to use as
+ *                                backtracking stack).
+ *  - fp[44]  capture array size (may fit multiple sets of matches)
  *  - fp[40]  int* capture_array (int[num_saved_registers_], for output).
  *  - fp[36]  secondary link/return address used by native call.
  *  --- sp when called ---
- *  - fp[32]  return address (lr).
- *  - fp[28]  old frame pointer (r11).
+ *  - fp[32]  return address     (lr).
+ *  - fp[28]  old frame pointer  (r11).
  *  - fp[0..24]  backup of registers r4..r10.
  *  --- frame pointer ----
  *  - 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).

[Erik Corry, 2012/05/22 08:32:46]

Inconsistent capitalization, not started by you.

[Yang, 2012/05/22 14:48:03]

Done.

  *  - 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 useful for global regexp to count matches)

[Erik Corry, 2012/05/22 08:32:46]

Does this lint?

[Yang, 2012/05/22 14:48:03]

Done.

+ *  - 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 553 matching lines @@
 }
 
 
 void RegExpMacroAssemblerARM::Fail() {
   __ mov(r0, Operand(FAILURE));
   __ jmp(&exit_label_);
 }
 
 
 Handle<HeapObject> RegExpMacroAssemblerARM::GetCode(Handle<String> source) {
+  Label return_r0, 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.
   // 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 = r4.bit() | r5.bit() | r6.bit() |
       r7.bit() | r8.bit() | r9.bit() | r10.bit() | fp.bit();
   RegList argument_registers = r0.bit() | r1.bit() | r2.bit() | r3.bit();
   __ stm(db_w, sp, argument_registers | registers_to_retain | lr.bit());
   // Set frame pointer in space for it if this is not a direct call
   // from generated code.
   __ add(frame_pointer(), sp, Operand(4 * kPointerSize));
+  __ mov(r0, Operand(0, RelocInfo::NONE));
+  __ push(r0);  // Make room for success counter and initialize it to 0.
   __ push(r0);  // Make room for "position - 1" constant (value is irrelevant).
   __ push(r0);  // Make room for "at start" constant (value is 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());
   __ mov(r0, Operand(stack_limit));
   __ ldr(r0, MemOperand(r0));
   __ sub(r0, sp, r0, SetCC);
   // Handle it if the stack pointer is already below the stack limit.
   __ b(ls, &stack_limit_hit);
   // Check if there is room for the variable number of registers above
   // the stack limit.
   __ cmp(r0, Operand(num_registers_ * kPointerSize));
   __ b(hs, &stack_ok);
   // Exit with OutOfMemory exception. There is not enough space on the stack
   // for our working registers.
   __ mov(r0, Operand(EXCEPTION));
-  __ jmp(&exit_label_);
+  __ jmp(&return_r0);
 
   __ bind(&stack_limit_hit);
   CallCheckStackGuardState(r0);
   __ cmp(r0, Operand(0, RelocInfo::NONE));
   // If returned value is non-zero, we exit with the returned value as result.
-  __ b(ne, &exit_label_);
+  __ b(ne, &return_r0);
 
   __ bind(&stack_ok);
 
   // Allocate space on stack for registers.
   __ sub(sp, sp, Operand(num_registers_ * kPointerSize));
   // Load string end.
   __ ldr(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
   // Load input start.
   __ ldr(r0, MemOperand(frame_pointer(), kInputStart));
   // Find negative length (offset of start relative to end).
   __ sub(current_input_offset(), r0, end_of_input_address());
   // Set r0 to address of char before start of the input string
   // (effectively string position -1).
   __ ldr(r1, MemOperand(frame_pointer(), kStartIndex));
   __ sub(r0, current_input_offset(), Operand(char_size()));
   __ sub(r0, r0, Operand(r1, LSL, (mode_ == UC16) ? 1 : 0));
   // Store this value in a local variable, for use when clearing
   // position registers.
   __ str(r0, MemOperand(frame_pointer(), kInputStartMinusOne));
 
+  // Initialize code pointer register
+  __ mov(code_pointer(), Operand(masm_->CodeObject()));
+  // Load previous char as initial value of current character register.
+  Label at_start, character_loaded;
   // Determine whether the start index is zero, that is at the start of the
-  // string, and store that value in a local variable.
-  __ cmp(r1, Operand(0));
+  // string, and store that value in a local variable.  Store the result to
+  // local variable kAtStart.
+  __ cmp(r1, Operand(0, RelocInfo::NONE));
   __ mov(r1, Operand(1), LeaveCC, eq);
   __ mov(r1, Operand(0, RelocInfo::NONE), LeaveCC, ne);
   __ str(r1, MemOperand(frame_pointer(), kAtStart));
+  // Load newline if index is at start.
+  __ mov(current_character(), Operand('\n'), LeaveCC, eq);

[Erik Corry, 2012/05/22 08:32:46]

Having conditional instructions here after non-conditional instructions that do
not affect the flags - that is too tricky.  Please refactor to use conventional
if-then-else branching.

[Yang, 2012/05/22 14:48:03]

Done.

+  __ b(eq, &character_loaded);
+  LoadCurrentCharacterUnchecked(-1, 1);  // Load previous char.
 
+  if (global()) {
+    // Initializing current-character already done, so skip it.
+    __ jmp(&character_loaded);
+    // Restart matching from here in a global regexp.
+    __ bind(&restart);
+    // In a restarted pass, initialize current-character here.
+    LoadCurrentCharacterUnchecked(-1, 1);

[Erik Corry, 2012/05/22 08:32:46]

In the global case the generated code isn't making much sense.  It's doing:

Load CurrentChar
jmp loaded
Load CurrentChar
bind loaded

[Yang, 2012/05/22 14:48:03]

Done.

+  }
+  __ bind(&character_loaded);
+
+  // 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.
-    __ add(r1, frame_pointer(), Operand(kRegisterZero));
-    __ mov(r2, Operand(num_saved_registers_));
-    Label init_loop;
-    __ bind(&init_loop);
-    __ str(r0, MemOperand(r1, kPointerSize, NegPostIndex));
-    __ sub(r2, r2, Operand(1), SetCC);
-    __ b(ne, &init_loop);
+    if (num_saved_registers_ > 8) {
+      // Address of register 0.
+      __ add(r1, frame_pointer(), Operand(kRegisterZero));
+      __ mov(r2, Operand(num_saved_registers_));
+      Label init_loop;
+      __ bind(&init_loop);
+      __ str(r0, MemOperand(r1, kPointerSize, NegPostIndex));
+      __ sub(r2, r2, Operand(1), SetCC);
+      __ b(ne, &init_loop);
+    } else {
+      for (int i = 0; i < num_saved_registers_; i++) {
+        __ str(r0, register_location(i));
+      }
+    }
   }
 
   // Initialize backtrack stack pointer.
   __ ldr(backtrack_stackpointer(), MemOperand(frame_pointer(), kStackHighEnd));
-  // Initialize code pointer register
-  __ mov(code_pointer(), Operand(masm_->CodeObject()));
-  // Load previous char as initial value of current character register.
-  Label at_start;
-  __ ldr(r0, MemOperand(frame_pointer(), kAtStart));
-  __ cmp(r0, Operand(0, RelocInfo::NONE));
-  __ b(ne, &at_start);
-  LoadCurrentCharacterUnchecked(-1, 1);  // Load previous char.
+
   __ jmp(&start_label_);
-  __ bind(&at_start);
-  __ mov(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
       __ ldr(r1, MemOperand(frame_pointer(), kInputStart));
       __ ldr(r0, MemOperand(frame_pointer(), kRegisterOutput));
       __ ldr(r2, MemOperand(frame_pointer(), kStartIndex));
       __ sub(r1, end_of_input_address(), r1);
       // r1 is length of input in bytes.
       if (mode_ == UC16) {
         __ mov(r1, Operand(r1, LSR, 1));
       }
       // r1 is length of input in characters.
       __ add(r1, r1, Operand(r2));
       // r1 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) {
         __ ldr(r2, register_location(i));
         __ ldr(r3, register_location(i + 1));
+        if (global()) {
+          // Keep capture start in r4 for the zero-length check later.
+          __ mov(r4, r2);
+        }
         if (mode_ == UC16) {
           __ add(r2, r1, Operand(r2, ASR, 1));
           __ add(r3, r1, Operand(r3, ASR, 1));
         } else {
           __ add(r2, r1, Operand(r2));
           __ add(r3, r1, Operand(r3));
         }
         __ str(r2, MemOperand(r0, kPointerSize, PostIndex));
         __ str(r3, MemOperand(r0, kPointerSize, PostIndex));
       }
     }
-    __ mov(r0, Operand(SUCCESS));
+
+    if (global()) {
+      // Restart matching if the regular expression is flagged as global.
+      __ ldr(r0, MemOperand(frame_pointer(), kSuccessfulCaptures));
+      __ ldr(r1, MemOperand(frame_pointer(), kNumOutputRegisters));
+      __ ldr(r2, MemOperand(frame_pointer(), kRegisterOutput));
+      // Increment success counter.
+      __ add(r0, r0, Operand(1));
+      __ str(r0, 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.
+      __ sub(r1, r1, Operand(num_saved_registers_));
+      // Check whether we have enough room for another set of capture results.
+      __ cmp(r1, Operand(num_saved_registers_));
+      __ b(lt, &return_r0);
+
+      __ str(r1, MemOperand(frame_pointer(), kNumOutputRegisters));
+      // Advance the location for output.
+      __ add(r2, r2, Operand(num_saved_registers_ * kPointerSize));
+      __ str(r2, MemOperand(frame_pointer(), kRegisterOutput));
+
+      // Prepare r0 to initialize registers with its value in the next run.
+      __ ldr(r0, MemOperand(frame_pointer(), kInputStartMinusOne));
+      // Special case for zero-length matches.
+      // r4: capture start index
+      __ cmp(current_input_offset(), r4);
+      // Not a zero-length match, restart.
+      __ b(ne, &restart);
+      // Offset from the end is zero if we already reached the end.
+      __ cmp(current_input_offset(), Operand(0));
+      __ b(eq, &exit_label_);
+      // Advance current position after a zero-length match.
+      __ add(current_input_offset(),
+             current_input_offset(),
+             Operand((mode_ == UC16) ? 2 : 1));
+      __ b(&restart);
+    } else {
+      __ mov(r0, Operand(SUCCESS));
+    }
   }
+
   // Exit and return r0
   __ bind(&exit_label_);
+  if (global()) {
+    __ ldr(r0, MemOperand(frame_pointer(), kSuccessfulCaptures));
+  }
+
+  __ bind(&return_r0);
   // Skip sp past regexp registers and local variables..
   __ mov(sp, frame_pointer());
   // Restore registers r4..r11 and return (restoring lr to pc).
   __ ldm(ia_w, sp, registers_to_retain | pc.bit());
 
   // 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_);
 
     CallCheckStackGuardState(r0);
     __ cmp(r0, Operand(0, RelocInfo::NONE));
     // If returning non-zero, we should end execution with the given
     // result as return value.
-    __ b(ne, &exit_label_);
+    __ b(ne, &return_r0);
 
     // String might have moved: Reload end of string from frame.

[Erik Corry, 2012/05/22 08:32:46]

If this happens will r4 be updated with the correct position?

[Yang, 2012/05/22 14:48:03]

r4 is a relative index from the end of string, therefore should not be affected
from moving the string.

     __ ldr(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
     SafeReturn();
   }
 
   // Backtrack stack overflow code.
   if (stack_overflow_label_.is_linked()) {
     SafeCallTarget(&stack_overflow_label_);
     // Reached if the backtrack-stack limit has been hit.
     Label grow_failed;
 
@@ skipping 14 matching lines @@
     __ mov(backtrack_stackpointer(), r0);
     // Restore saved registers and continue.
     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.
     __ mov(r0, Operand(EXCEPTION));
-    __ jmp(&exit_label_);
+    __ jmp(&return_r0);
   }
 
   CodeDesc code_desc;
   masm_->GetCode(&code_desc);
   Handle<Code> code = FACTORY->NewCode(code_desc,
                                        Code::ComputeFlags(Code::REGEXP),
                                        masm_->CodeObject());
   PROFILE(Isolate::Current(), RegExpCodeCreateEvent(*code, *source));
   return Handle<HeapObject>::cast(code);
 }
@@ skipping 427 matching lines @@
     __ ldr(sp, MemOperand(sp, 0));
   }
   __ mov(code_pointer(), Operand(masm_->CodeObject()));
 }
 
 
 void RegExpMacroAssemblerARM::LoadCurrentCharacterUnchecked(int cp_offset,
                                                             int characters) {
   Register offset = current_input_offset();
   if (cp_offset != 0) {
-    __ add(r0, current_input_offset(), Operand(cp_offset * char_size()));
-    offset = r0;
+    __ add(ip, current_input_offset(), Operand(cp_offset * char_size()));
+    offset = ip;

[Erik Corry, 2012/05/22 08:32:46]

This is setting a trap for a future programmer.  There are lots of instructions
that implicitly overwrite ip, so we should not use ip unless we have to, and if
we do it should be over 1-2 lines so you don't overlook that it is taken.

[Yang, 2012/05/22 14:48:03]

Using r4 now since it's not being used at this point.

   }
   // The ldr, str, ldrh, strh instructions can do unaligned accesses, if the CPU
   // and the operating system running on the target allow it.
   // If unaligned load/stores are not supported then this function must only
   // be used to load a single character at a time.
 #if !V8_TARGET_CAN_READ_UNALIGNED
   ASSERT(characters == 1);
 #endif
 
   if (mode_ == ASCII) {
@@ skipping 28 matching lines @@
   __ ldr(pc, MemOperand(sp, stack_alignment, PostIndex));
 }
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }}  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_ARM