PPC: Experimental support for RegExp lookbehind.

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

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #if V8_TARGET_ARCH_PPC
 
 #include "src/regexp/ppc/regexp-macro-assembler-ppc.h"
 
 #include "src/base/bits.h"
 #include "src/code-stubs.h"
@@ skipping 42 matching lines @@
  *  - fp[-8]  stack_area_base    (high end of the memory area to use as
  *                                backtracking stack).
  *  - fp[-12] capture array size (may fit multiple sets of matches)
  *  - fp[-16] int* capture_array (int[num_saved_registers_], for output).
  *  - fp[-20] end of input       (address of end of string).
  *  - fp[-24] start of input     (address of first character in string).
  *  - fp[-28] start index        (character index of start).
  *  - fp[-32] void* input_string (location of a handle containing the string).
  *  - fp[-36] success counter    (only for global regexps to count matches).
  *  - fp[-40] Offset of location before start of input (effectively character
- *            position -1). Used to initialize capture registers to a
+ *            string start - 1). Used to initialize capture registers to a
  *            non-position.
  *  - fp[-44] At start (if 1, we are starting at the start of the
  *    string, otherwise 0)
  *  - fp[-48] 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
@@ skipping 108 matching lines @@
 }
 
 
 void RegExpMacroAssemblerPPC::CheckCharacterGT(uc16 limit, Label* on_greater) {
   __ Cmpli(current_character(), Operand(limit), r0);
   BranchOrBacktrack(gt, on_greater);
 }
 
 
 void RegExpMacroAssemblerPPC::CheckAtStart(Label* on_at_start) {
-  Label not_at_start;
-  // Did we start the match at the start of the string at all?
-  __ LoadP(r3, MemOperand(frame_pointer(), kStartIndex));
-  __ cmpi(r3, Operand::Zero());
-  BranchOrBacktrack(ne, &not_at_start);
-
-  // If we did, are we still at the start of the input?
-  __ LoadP(r4, MemOperand(frame_pointer(), kInputStart));
-  __ mr(r0, current_input_offset());
-  __ add(r3, end_of_input_address(), r0);
-  __ cmp(r4, r3);
+  __ LoadP(r4, MemOperand(frame_pointer(), kStringStartMinusOne));
+  __ addi(r3, current_input_offset(), Operand(-char_size()));
+  __ cmp(r3, r4);
   BranchOrBacktrack(eq, on_at_start);
-  __ bind(&not_at_start);
 }
 
 
-void RegExpMacroAssemblerPPC::CheckNotAtStart(Label* on_not_at_start) {
-  // Did we start the match at the start of the string at all?
-  __ LoadP(r3, MemOperand(frame_pointer(), kStartIndex));
-  __ cmpi(r3, Operand::Zero());
-  BranchOrBacktrack(ne, on_not_at_start);
-  // If we did, are we still at the start of the input?
-  __ LoadP(r4, MemOperand(frame_pointer(), kInputStart));
-  __ add(r3, end_of_input_address(), current_input_offset());
+void RegExpMacroAssemblerPPC::CheckNotAtStart(int cp_offset,
+                                              Label* on_not_at_start) {
+  __ LoadP(r4, MemOperand(frame_pointer(), kStringStartMinusOne));
+  __ addi(r3, current_input_offset(),
+          Operand(-char_size() + cp_offset * char_size()));
   __ cmp(r3, r4);
   BranchOrBacktrack(ne, on_not_at_start);
 }
 
 
 void RegExpMacroAssemblerPPC::CheckCharacterLT(uc16 limit, Label* on_less) {
   __ Cmpli(current_character(), Operand(limit), r0);
   BranchOrBacktrack(lt, on_less);
 }
 
 
 void RegExpMacroAssemblerPPC::CheckGreedyLoop(Label* on_equal) {
   Label backtrack_non_equal;
   __ LoadP(r3, MemOperand(backtrack_stackpointer(), 0));
   __ cmp(current_input_offset(), r3);
   __ bne(&backtrack_non_equal);
   __ addi(backtrack_stackpointer(), backtrack_stackpointer(),
           Operand(kPointerSize));
 
   __ bind(&backtrack_non_equal);
   BranchOrBacktrack(eq, on_equal);
 }
 
 
 void RegExpMacroAssemblerPPC::CheckNotBackReferenceIgnoreCase(
-    int start_reg, Label* on_no_match) {
+    int start_reg, bool read_backward, Label* on_no_match) {
   Label fallthrough;
   __ LoadP(r3, register_location(start_reg), r0);  // Index of start of capture
   __ LoadP(r4, register_location(start_reg + 1), r0);  // Index of end
   __ sub(r4, r4, r3, LeaveOE, SetRC);                  // Length of capture.
 
-  // If length is zero, either the capture is empty or it is not participating.
-  // In either case succeed immediately.
+  // At this point, the capture registers are either both set or both cleared.
+  // If the capture length is zero, then the capture is either empty or cleared.
+  // Fall through in both cases.
   __ beq(&fallthrough, cr0);
 
   // Check that there are enough characters left in the input.
-  __ add(r0, r4, current_input_offset(), LeaveOE, SetRC);
-  //  __ cmn(r1, Operand(current_input_offset()));
-  BranchOrBacktrack(gt, on_no_match, cr0);
+  if (read_backward) {
+    __ LoadP(r6, MemOperand(frame_pointer(), kStringStartMinusOne));
+    __ add(r6, r6, r4);
+    __ cmp(current_input_offset(), r6);
+    BranchOrBacktrack(le, on_no_match);
+  } else {
+    __ add(r0, r4, current_input_offset(), LeaveOE, SetRC);
+    BranchOrBacktrack(gt, on_no_match, cr0);
+  }
 
   if (mode_ == LATIN1) {
     Label success;
     Label fail;
     Label loop_check;
 
     // r3 - offset of start of capture
     // r4 - length of capture
     __ add(r3, r3, end_of_input_address());
     __ add(r5, end_of_input_address(), current_input_offset());
+    if (read_backward) {
+      __ sub(r5, r5, r4);  // Offset by length when matching backwards.
+    }
     __ add(r4, r3, r4);
 
     // r3 - Address of start of capture.
     // r4 - Address of end of capture
     // r5 - Address of current input position.
 
     Label loop;
     __ bind(&loop);
     __ lbz(r6, MemOperand(r3));
     __ addi(r3, r3, Operand(char_size()));
@@ skipping 21 matching lines @@
     __ cmp(r3, r4);
     __ blt(&loop);
     __ b(&success);
 
     __ bind(&fail);
     BranchOrBacktrack(al, on_no_match);
 
     __ bind(&success);
     // Compute new value of character position after the matched part.
     __ sub(current_input_offset(), r5, end_of_input_address());
+    if (read_backward) {
+      __ LoadP(r3, register_location(start_reg));  // Index of start of capture
+      __ LoadP(r4,
+               register_location(start_reg + 1));  // Index of end of capture
+      __ add(current_input_offset(), current_input_offset(), r3);
+      __ sub(current_input_offset(), current_input_offset(), r4);
+    }
   } else {
     DCHECK(mode_ == UC16);
     int argument_count = 4;
     __ PrepareCallCFunction(argument_count, r5);
 
     // r3 - offset of start of capture
     // r4 - length of capture
 
     // Put arguments into arguments registers.
     // Parameters are
     //   r3: Address byte_offset1 - Address captured substring's start.
     //   r4: Address byte_offset2 - Address of current character position.
     //   r5: size_t byte_length - length of capture in bytes(!)
     //   r6: Isolate* isolate
 
     // Address of start of capture.
     __ add(r3, r3, end_of_input_address());
     // Length of capture.
     __ mr(r5, r4);
     // Save length in callee-save register for use on return.
     __ mr(r25, r4);
     // Address of current input position.
     __ add(r4, current_input_offset(), end_of_input_address());
+    if (read_backward) {
+      __ sub(r4, r4, r25);
+    }
     // Isolate.
     __ mov(r6, Operand(ExternalReference::isolate_address(isolate())));
 
     {
       AllowExternalCallThatCantCauseGC scope(masm_);
       ExternalReference function =
           ExternalReference::re_case_insensitive_compare_uc16(isolate());
       __ CallCFunction(function, argument_count);
     }
 
     // Check if function returned non-zero for success or zero for failure.
     __ cmpi(r3, Operand::Zero());
     BranchOrBacktrack(eq, on_no_match);
-    // On success, increment position by length of capture.
-    __ add(current_input_offset(), current_input_offset(), r25);
+
+    // On success, advance position by length of capture.
+    if (read_backward) {
+      __ sub(current_input_offset(), current_input_offset(), r25);
+    } else {
+      __ add(current_input_offset(), current_input_offset(), r25);
+    }
   }
 
   __ bind(&fallthrough);
 }
 
 
 void RegExpMacroAssemblerPPC::CheckNotBackReference(int start_reg,
+                                                    bool read_backward,
                                                     Label* on_no_match) {
   Label fallthrough;
   Label success;
 
   // Find length of back-referenced capture.
   __ LoadP(r3, register_location(start_reg), r0);
   __ LoadP(r4, register_location(start_reg + 1), r0);
   __ sub(r4, r4, r3, LeaveOE, SetRC);  // Length to check.
-  // Succeed on empty capture (including no capture).
+
+  // At this point, the capture registers are either both set or both cleared.
+  // If the capture length is zero, then the capture is either empty or cleared.
+  // Fall through in both cases.
   __ beq(&fallthrough, cr0);
 
   // Check that there are enough characters left in the input.
-  __ add(r0, r4, current_input_offset(), LeaveOE, SetRC);
-  BranchOrBacktrack(gt, on_no_match, cr0);
+  if (read_backward) {
+    __ LoadP(r6, MemOperand(frame_pointer(), kStringStartMinusOne));
+    __ add(r6, r6, r4);
+    __ cmp(current_input_offset(), r6);
+    BranchOrBacktrack(lt, on_no_match);
+  } else {
+    __ add(r0, r4, current_input_offset(), LeaveOE, SetRC);
+    BranchOrBacktrack(gt, on_no_match, cr0);
+  }
 
-  // Compute pointers to match string and capture string
+  // r3 - offset of start of capture
+  // r4 - length of capture
   __ add(r3, r3, end_of_input_address());
   __ add(r5, end_of_input_address(), current_input_offset());
+  if (read_backward) {
+    __ sub(r5, r5, r4);  // Offset by length when matching backwards.
+  }
   __ add(r4, r4, r3);
 
   Label loop;
   __ bind(&loop);
   if (mode_ == LATIN1) {
     __ lbz(r6, MemOperand(r3));
     __ addi(r3, r3, Operand(char_size()));
     __ lbz(r25, MemOperand(r5));
     __ addi(r5, r5, Operand(char_size()));
   } else {
     DCHECK(mode_ == UC16);
     __ lhz(r6, MemOperand(r3));
     __ addi(r3, r3, Operand(char_size()));
     __ lhz(r25, MemOperand(r5));
     __ addi(r5, r5, Operand(char_size()));
   }
   __ cmp(r6, r25);
   BranchOrBacktrack(ne, on_no_match);
   __ cmp(r3, r4);
   __ blt(&loop);
 
   // Move current character position to position after match.
   __ sub(current_input_offset(), r5, end_of_input_address());
+  if (read_backward) {
+    __ LoadP(r3, register_location(start_reg));  // Index of start of capture
+    __ LoadP(r4, register_location(start_reg + 1));  // Index of end of capture
+    __ add(current_input_offset(), current_input_offset(), r3);
+    __ sub(current_input_offset(), current_input_offset(), r4);
+  }
+
   __ bind(&fallthrough);
 }
 
 
 void RegExpMacroAssemblerPPC::CheckNotCharacter(unsigned c,
                                                 Label* on_not_equal) {
   __ Cmpli(current_character(), Operand(c), r0);
   BranchOrBacktrack(ne, on_not_equal);
 }
 
@@ skipping 230 matching lines @@
     RegList argument_registers = r3.bit() | r4.bit() | r5.bit() | r6.bit() |
                                  r7.bit() | r8.bit() | r9.bit() | r10.bit();
     __ mflr(r0);
     __ push(r0);
     __ MultiPush(argument_registers | registers_to_retain);
     // Set frame pointer in space for it if this is not a direct call
     // from generated code.
     __ addi(frame_pointer(), sp, Operand(8 * kPointerSize));
     __ li(r3, Operand::Zero());
     __ push(r3);  // Make room for success counter and initialize it to 0.
-    __ push(r3);  // Make room for "position - 1" constant (value is irrelevant)
+    __ push(r3);  // Make room for "string start - 1" 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(isolate());
     __ mov(r3, Operand(stack_limit));
     __ LoadP(r3, MemOperand(r3));
     __ sub(r3, sp, r3, LeaveOE, SetRC);
     // Handle it if the stack pointer is already below the stack limit.
@@ skipping 28 matching lines @@
     __ LoadP(r4, MemOperand(frame_pointer(), kStartIndex));
     __ subi(r3, current_input_offset(), Operand(char_size()));
     if (mode_ == UC16) {
       __ ShiftLeftImm(r0, r4, Operand(1));
       __ sub(r3, r3, r0);
     } else {
       __ sub(r3, r3, r4);
     }
     // Store this value in a local variable, for use when clearing
     // position registers.
-    __ StoreP(r3, MemOperand(frame_pointer(), kInputStartMinusOne));
+    __ StoreP(r3, MemOperand(frame_pointer(), kStringStartMinusOne));
 
     // Initialize code pointer register
     __ mov(code_pointer(), Operand(masm_->CodeObject()));
 
     Label load_char_start_regexp, start_regexp;
     // Load newline if index is at start, previous character otherwise.
     __ cmpi(r4, Operand::Zero());
     __ bne(&load_char_start_regexp);
     __ li(current_character(), Operand('\n'));
     __ b(&start_regexp);
@@ skipping 88 matching lines @@
         // Check whether we have enough room for another set of capture results.
         __ cmpi(r4, Operand(num_saved_registers_));
         __ blt(&return_r3);
 
         __ StoreP(r4, MemOperand(frame_pointer(), kNumOutputRegisters));
         // Advance the location for output.
         __ addi(r5, r5, Operand(num_saved_registers_ * kIntSize));
         __ StoreP(r5, MemOperand(frame_pointer(), kRegisterOutput));
 
         // Prepare r3 to initialize registers with its value in the next run.
-        __ LoadP(r3, MemOperand(frame_pointer(), kInputStartMinusOne));
+        __ LoadP(r3, MemOperand(frame_pointer(), kStringStartMinusOne));
 
         if (global_with_zero_length_check()) {
           // Special case for zero-length matches.
           // r25: capture start index
           __ cmp(current_input_offset(), r25);
           // Not a zero-length match, restart.
           __ bne(&load_char_start_regexp);
           // Offset from the end is zero if we already reached the end.
           __ cmpi(current_input_offset(), Operand::Zero());
           __ beq(&exit_label_);
@@ skipping 118 matching lines @@
 RegExpMacroAssembler::IrregexpImplementation
 RegExpMacroAssemblerPPC::Implementation() {
   return kPPCImplementation;
 }
 
 
 void RegExpMacroAssemblerPPC::LoadCurrentCharacter(int cp_offset,
                                                    Label* on_end_of_input,
                                                    bool check_bounds,
                                                    int characters) {
-  DCHECK(cp_offset >= -1);        // ^ and \b can look behind one character.
   DCHECK(cp_offset < (1 << 30));  // Be sane! (And ensure negation works)
   if (check_bounds) {
-    CheckPosition(cp_offset + characters - 1, on_end_of_input);
+    if (cp_offset >= 0) {
+      CheckPosition(cp_offset + characters - 1, on_end_of_input);
+    } else {
+      CheckPosition(cp_offset, on_end_of_input);
+    }
   }
   LoadCurrentCharacterUnchecked(cp_offset, characters);
 }
 
 
 void RegExpMacroAssemblerPPC::PopCurrentPosition() {
   Pop(current_input_offset());
 }
 
 
@@ skipping 68 matching lines @@
   } else {
     __ mov(r0, Operand(cp_offset * char_size()));
     __ add(r3, current_input_offset(), r0);
     __ StoreP(r3, register_location(reg), r0);
   }
 }
 
 
 void RegExpMacroAssemblerPPC::ClearRegisters(int reg_from, int reg_to) {
   DCHECK(reg_from <= reg_to);
-  __ LoadP(r3, MemOperand(frame_pointer(), kInputStartMinusOne));
+  __ LoadP(r3, MemOperand(frame_pointer(), kStringStartMinusOne));
   for (int reg = reg_from; reg <= reg_to; reg++) {
     __ StoreP(r3, register_location(reg), r0);
   }
 }
 
 
 void RegExpMacroAssemblerPPC::WriteStackPointerToRegister(int reg) {
   __ LoadP(r4, MemOperand(frame_pointer(), kStackHighEnd));
   __ sub(r3, backtrack_stackpointer(), r4);
   __ StoreP(r3, register_location(reg), r0);
@@ skipping 83 matching lines @@
   if (num_registers_ <= register_index) {
     num_registers_ = register_index + 1;
   }
   return MemOperand(frame_pointer(),
                     kRegisterZero - register_index * kPointerSize);
 }
 
 
 void RegExpMacroAssemblerPPC::CheckPosition(int cp_offset,
                                             Label* on_outside_input) {
-  __ Cmpi(current_input_offset(), Operand(-cp_offset * char_size()), r0);
-  BranchOrBacktrack(ge, on_outside_input);
+  if (cp_offset >= 0) {
+    __ Cmpi(current_input_offset(), Operand(-cp_offset * char_size()), r0);
+    BranchOrBacktrack(ge, on_outside_input);
+  } else {
+    __ LoadP(r4, MemOperand(frame_pointer(), kStringStartMinusOne));
+    __ addi(r3, current_input_offset(), Operand(cp_offset * char_size()));
+    __ cmp(r3, r4);
+    BranchOrBacktrack(le, on_outside_input);
+  }
 }
 
 
 void RegExpMacroAssemblerPPC::BranchOrBacktrack(Condition condition, Label* to,
                                                 CRegister cr) {
   if (condition == al) {  // Unconditional.
     if (to == NULL) {
       Backtrack();
       return;
     }
@@ skipping 96 matching lines @@
 }
 
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_TARGET_ARCH_PPC