[regexp] Port RegExpExecStub to CSA (mostly)

src/builtins/builtins-regexp.cc

 // Copyright 2016 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.
 
 #include "src/builtins/builtins-regexp.h"
 
 #include "src/builtins/builtins-constructor.h"
 #include "src/builtins/builtins-utils.h"
 #include "src/builtins/builtins.h"
 #include "src/code-factory.h"
@@ skipping 197 matching lines @@
       var_i.Bind(i_plus_2);
       Branch(IntPtrGreaterThanOrEqual(var_i.value(), names_length), &out,
              &loop);
     }
   }
 
   Bind(&out);
   return result;
 }
 
+void RegExpBuiltinsAssembler::GetStringPointers(
+    Node* const string, Node* const offset, Node* const last_index,
+    Node* const string_length, bool is_one_byte, Variable* var_string_start,
+    Variable* var_string_end) {
+  DCHECK_EQ(var_string_start->rep(), MachineType::PointerRepresentation());
+  DCHECK_EQ(var_string_end->rep(), MachineType::PointerRepresentation());
+
+  STATIC_ASSERT(SeqOneByteString::kHeaderSize == SeqTwoByteString::kHeaderSize);
+  const int kHeaderSize = SeqOneByteString::kHeaderSize - kHeapObjectTag;
+  const ElementsKind kind = is_one_byte ? UINT8_ELEMENTS : UINT16_ELEMENTS;
+
+  Node* const from_offset = ElementOffsetFromIndex(
+      IntPtrAdd(offset, last_index), kind, INTPTR_PARAMETERS, kHeaderSize);
+  var_string_start->Bind(IntPtrAdd(string, from_offset));
+
+  Node* const to_offset = ElementOffsetFromIndex(
+      IntPtrAdd(offset, string_length), kind, INTPTR_PARAMETERS, kHeaderSize);
+  var_string_end->Bind(IntPtrAdd(string, to_offset));
+}
+
+Node* RegExpBuiltinsAssembler::IrregexpExec(Node* const context,
+                                            Node* const regexp,
+                                            Node* const string,
+                                            Node* const last_index,
+                                            Node* const match_info) {
+// Just jump directly to runtime if native RegExp is not selected at compile
+// time or if regexp entry in generated code is turned off runtime switch or
+// at compilation.
+#ifdef V8_INTERPRETED_REGEXP
+  return CallRuntime(Runtime::kRegExpExec, context, regexp, string, last_index,
+                     match_info);
+#else   // V8_INTERPRETED_REGEXP
+  CSA_ASSERT(this, TaggedIsNotSmi(regexp));
+  CSA_ASSERT(this, HasInstanceType(regexp, JS_REGEXP_TYPE));
+
+  CSA_ASSERT(this, TaggedIsNotSmi(string));
+  CSA_ASSERT(this, IsString(string));
+
+  CSA_ASSERT(this, IsHeapNumberMap(LoadReceiverMap(last_index)));
+  CSA_ASSERT(this, IsFixedArrayMap(LoadReceiverMap(match_info)));
+
+  Node* const int_zero = IntPtrConstant(0);
+
+  Variable var_result(this, MachineRepresentation::kTagged);
+  Variable var_string(this, MachineType::PointerRepresentation(), int_zero);
+  Variable var_string_offset(this, MachineType::PointerRepresentation(),
+                             int_zero);
+  Variable var_string_instance_type(this, MachineRepresentation::kWord32,
+                                    Int32Constant(0));
+
+  Label out(this), runtime(this, Label::kDeferred);
+
+  // External constants.
+  Node* const regexp_stack_memory_size_address = ExternalConstant(
+      ExternalReference::address_of_regexp_stack_memory_size(isolate()));
+  Node* const static_offsets_vector_address = ExternalConstant(
+      ExternalReference::address_of_static_offsets_vector(isolate()));
+  Node* const pending_exception_address = ExternalConstant(
+      ExternalReference(Isolate::kPendingExceptionAddress, isolate()));
+
+  // Ensure that a RegExp stack is allocated.
+  {
+    Node* const stack_size =
+        Load(MachineType::IntPtr(), regexp_stack_memory_size_address);
+    GotoIf(IntPtrEqual(stack_size, int_zero), &runtime);
+  }
+
+  Node* const data = LoadObjectField(regexp, JSRegExp::kDataOffset);
+  {
+    // Check that the RegExp has been compiled (data contains a fixed array).
+    CSA_ASSERT(this, TaggedIsNotSmi(data));
+    CSA_ASSERT(this, HasInstanceType(data, FIXED_ARRAY_TYPE));
+
+    // Check the type of the RegExp. Only continue if type is
+    // JSRegExp::IRREGEXP.
+    Node* const tag = LoadFixedArrayElement(data, JSRegExp::kTagIndex);
+    GotoIfNot(SmiEqual(tag, SmiConstant(JSRegExp::IRREGEXP)), &runtime);
+
+    // Check (number_of_captures + 1) * 2 <= offsets vector size
+    // Or              number_of_captures <= offsets vector size / 2 - 1
+    Node* const capture_count =
+        LoadFixedArrayElement(data, JSRegExp::kIrregexpCaptureCountIndex);
+    CSA_ASSERT(this, TaggedIsSmi(capture_count));
+
+    STATIC_ASSERT(Isolate::kJSRegexpStaticOffsetsVectorSize >= 2);
+    GotoIf(SmiAbove(
+               capture_count,
+               SmiConstant(Isolate::kJSRegexpStaticOffsetsVectorSize / 2 - 1)),
+           &runtime);
+  }
+
+  // Unpack the string if possible.
+
+  var_string.Bind(BitcastTaggedToWord(string));
+  var_string_offset.Bind(int_zero);
+  var_string_instance_type.Bind(LoadInstanceType(string));
+
+  {
+    TryUnpackString(&var_string, &var_string_offset, &var_string_instance_type,
+                    &runtime);
+
+    // At this point, {var_string} may contain a faked sequential string (i.e.
+    // an external string with an adjusted offset) so we cannot assert
+    // IsString({var_string}). We also cannot allocate after this point since
+    // GC could move {var_string}'s underlying string.
+  }
+
+  Node* const smi_string_length = LoadStringLength(string);
+
+  // Bail out to runtime for invalid {last_index} values.
+  GotoIfNot(TaggedIsSmi(last_index), &runtime);
+  GotoIf(SmiAboveOrEqual(last_index, smi_string_length), &runtime);
+
+  // Load the irregexp code object and offsets into the subject string. Both
+  // depend on whether the string is one- or two-byte.
+
+  Node* const int_last_index = SmiUntag(last_index);
+
+  Variable var_string_start(this, MachineType::PointerRepresentation());
+  Variable var_string_end(this, MachineType::PointerRepresentation());
+  Variable var_code(this, MachineRepresentation::kTagged);
+
+  {
+    Node* const int_string_length = SmiUntag(smi_string_length);
+
+    Node* const string_instance_type = var_string_instance_type.value();
+    CSA_ASSERT(this, IsSequentialStringInstanceType(string_instance_type));
+
+    Label next(this), if_isonebyte(this), if_istwobyte(this, Label::kDeferred);
+    Branch(IsOneByteStringInstanceType(string_instance_type), &if_isonebyte,
+           &if_istwobyte);
+
+    Bind(&if_isonebyte);
+    {
+      const bool kIsOneByte = true;
+      GetStringPointers(var_string.value(), var_string_offset.value(),
+                        int_last_index, int_string_length, kIsOneByte,
+                        &var_string_start, &var_string_end);
+      var_code.Bind(
+          LoadFixedArrayElement(data, JSRegExp::kIrregexpLatin1CodeIndex));
+      Goto(&next);
+    }
+
+    Bind(&if_istwobyte);
+    {
+      const bool kIsOneByte = false;
+      GetStringPointers(var_string.value(), var_string_offset.value(),
+                        int_last_index, int_string_length, kIsOneByte,
+                        &var_string_start, &var_string_end);
+      var_code.Bind(
+          LoadFixedArrayElement(data, JSRegExp::kIrregexpUC16CodeIndex));
+      Goto(&next);
+    }
+
+    Bind(&next);
+  }
+
+  // Check that the irregexp code has been generated for the actual string
+  // encoding. If it has, the field contains a code object otherwise it contains
+  // smi (code flushing support).
+
+  Node* const code = var_code.value();
+  GotoIf(TaggedIsSmi(code), &runtime);
+  CSA_ASSERT(this, HasInstanceType(code, CODE_TYPE));
+
+  Label if_success(this), if_failure(this),
+      if_exception(this, Label::kDeferred);
+  {
+    IncrementCounter(isolate()->counters()->regexp_entry_native(), 1);
+
+    Callable exec_callable = CodeFactory::RegExpExec(isolate());

[Igor Sheludko, 2017/03/15 00:39:04]

I'd rather name the stub and this function the other way round. What's left in
the stub is actually IrregexpExecStub (or CallIrrexpStub or IrregexpEntryStub)
while this whole function is what used to be RegExpExec code.

[jgruber, 2017/03/15 13:43:44]

Renamed the function RegExpExecInternal. The stub will be removed once issues on
arm/arm64 are fixed.

+    Node* const result = CallStub(
+        exec_callable, context, string, TruncateWordToWord32(int_last_index),
+        var_string_start.value(), var_string_end.value(), code);
+
+    // Check the result.
+    // We expect exactly one result since we force the called regexp to behave

[Igor Sheludko, 2017/03/15 00:39:03]

s/we force/the stub forces/ or maybe add a comment above the call that the stub
internally enforces the lookup to be non-global.

[jgruber, 2017/03/15 13:43:44]

Done.

+    // as non-global.
+    GotoIf(SmiEqual(result, SmiConstant(1)), &if_success);
+    GotoIf(SmiEqual(result, SmiConstant(NativeRegExpMacroAssembler::FAILURE)),
+           &if_failure);
+    GotoIf(SmiEqual(result, SmiConstant(NativeRegExpMacroAssembler::EXCEPTION)),
+           &if_exception);
+
+    CSA_ASSERT(
+        this, SmiEqual(result, SmiConstant(NativeRegExpMacroAssembler::RETRY)));
+    Goto(&runtime);
+  }
+
+  Bind(&if_success);
+  {
+    // Check that the last match info has space for the capture registers and
+    // the additional information. Ensure no overflow in add.
+    STATIC_ASSERT(FixedArray::kMaxLength < kMaxInt - FixedArray::kLengthOffset);
+    Node* const available_slots =
+        SmiSub(LoadFixedArrayBaseLength(match_info),
+               SmiConstant(RegExpMatchInfo::kLastMatchOverhead));
+    Node* const capture_count =
+        LoadFixedArrayElement(data, JSRegExp::kIrregexpCaptureCountIndex);

[Igor Sheludko, 2017/03/15 00:39:04]

Maybe
// Calculate number of capture registers (number_of_captures + 1) * 2

[jgruber, 2017/03/15 13:43:44]

Done.

+    Node* const register_count =
+        SmiShl(SmiAdd(capture_count, SmiConstant(1)), 1);
+    GotoIf(SmiGreaterThan(register_count, available_slots), &runtime);
+
+    // Fill match_info.
+
+    StoreFixedArrayElement(match_info, RegExpMatchInfo::kNumberOfCapturesIndex,
+                           register_count, SKIP_WRITE_BARRIER);
+    StoreFixedArrayElement(match_info, RegExpMatchInfo::kLastSubjectIndex,
+                           string);
+    StoreFixedArrayElement(match_info, RegExpMatchInfo::kLastInputIndex,
+                           string);
+
+    // Fill match and capture offsets in match_info.
+    {
+      Node* const limit_offset = ElementOffsetFromIndex(
+          register_count, INT32_ELEMENTS, SMI_PARAMETERS, 0);
+
+      Node* const to_offset = ElementOffsetFromIndex(
+          IntPtrConstant(RegExpMatchInfo::kFirstCaptureIndex), FAST_ELEMENTS,
+          INTPTR_PARAMETERS, RegExpMatchInfo::kHeaderSize - kHeapObjectTag);
+      Variable var_to_offset(this, MachineType::PointerRepresentation(),
+                             to_offset);
+
+      VariableList vars({&var_to_offset}, zone());
+      BuildFastLoop(
+          vars, int_zero, limit_offset,
+          [this, static_offsets_vector_address, match_info,

[Igor Sheludko, 2017/03/15 00:39:04]

[=, &var_to_offset]

[jgruber, 2017/03/15 13:43:44]

Done.

+           &var_to_offset](Node* offset) {
+            Node* const value = Load(MachineType::Int32(),
+                                     static_offsets_vector_address, offset);
+            Node* const smi_value = SmiFromWord32(value);
+            StoreNoWriteBarrier(MachineRepresentation::kTagged, match_info,
+                                var_to_offset.value(), smi_value);
+            Increment(var_to_offset, kPointerSize);
+          },
+          kInt32Size, INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
+    }
+
+    var_result.Bind(match_info);
+    Goto(&out);
+  }
+
+  Bind(&if_failure);
+  {
+    var_result.Bind(NullConstant());
+    Goto(&out);
+  }
+
+  Bind(&if_exception);
+  {
+    Node* const pending_exception =
+        Load(MachineType::AnyTagged(), pending_exception_address);
+
+    // If there is no pending exception, a

[Igor Sheludko, 2017/03/15 00:39:03]

Please reformat the comment.

[jgruber, 2017/03/15 13:43:44]

Done.

+    // stack overflow (on the backtrack stack) was detected in RegExp code.
+
+    Label stack_overflow(this), rethrow(this);
+    Branch(IsTheHole(pending_exception), &stack_overflow, &rethrow);

[Igor Sheludko, 2017/03/15 00:39:03]

AFAICT the only non-gc-safe thing the Irregexp code does when it's called from
JS (is_direct = true) is calling a
NativeRegExpMacroAssembler::CheckStackGuardState() which in turn can only create
and throw a stack overflow exception (in direct mode). So I guess if you remove
the isolate->StackOverflow(); from CheckStackGuardState() and let this code
actually reach the &stack_overflow block then you can probably skip the exit
frame construction and call the Irregexp code directly from CSA as a C function.
And this hole check will then become an assert and &rethow case will not be
necessary anymore.
WDYT?

[jgruber, 2017/03/15 13:43:44]

Great find. The initial goal was to completely remove the stub, awesome that we
can accomplish that. We're still blocked by issues on arm/arm64, but I'll remove
the stub once that's done.

+
+    Bind(&stack_overflow);
+    TailCallRuntime(Runtime::kThrowStackOverflow, context);
+
+    Bind(&rethrow);
+    TailCallRuntime(Runtime::kRegExpExecReThrow, context);
+  }
+
+  Bind(&runtime);
+  {
+    Node* const result = CallRuntime(Runtime::kRegExpExec, context, regexp,
+                                     string, last_index, match_info);
+    var_result.Bind(result);
+    Goto(&out);
+  }
+
+  Bind(&out);
+  return var_result.value();
+#endif  // V8_INTERPRETED_REGEXP
+}
+
 // ES#sec-regexp.prototype.exec
 // RegExp.prototype.exec ( string )
 // Implements the core of RegExp.prototype.exec but without actually
 // constructing the JSRegExpResult. Returns either null (if the RegExp did not
 // match) or a fixed array containing match indices as returned by
 // RegExpExecStub.
 Node* RegExpBuiltinsAssembler::RegExpPrototypeExecBodyWithoutResult(
     Node* const context, Node* const regexp, Node* const string,
     Label* if_didnotmatch, const bool is_fastpath) {
   Isolate* const isolate = this->isolate();
@@ skipping 76 matching lines @@
   Node* match_indices;
   Label successful_match(this);
   Bind(&run_exec);
   {
     // Get last match info from the context.
     Node* const native_context = LoadNativeContext(context);
     Node* const last_match_info = LoadContextElement(
         native_context, Context::REGEXP_LAST_MATCH_INFO_INDEX);
 
     // Call the exec stub.
-    Callable exec_callable = CodeFactory::RegExpExec(isolate);
-    match_indices = CallStub(exec_callable, context, regexp, string,
-                             var_lastindex.value(), last_match_info);
+    match_indices = IrregexpExec(context, regexp, string, var_lastindex.value(),

[jgruber, 2017/03/13 12:27:37]

This will add even more to the snapshot size. It's probably time to convert some
inlined code into stub calls.

[Igor Sheludko, 2017/03/15 00:39:03]

Why not leave this code in the stub in this CL?

[jgruber, 2017/03/15 13:43:44]

I have a follow-up CL that sets up a couple more stub calls for slow paths,
reducing snapshot size overall.

+                                 last_match_info);
     var_result.Bind(match_indices);
 
     // {match_indices} is either null or the RegExpMatchInfo array.
     // Return early if exec failed, possibly updating last index.
     GotoIfNot(WordEqual(match_indices, null), &successful_match);
 
     GotoIfNot(should_update_last_index, if_didnotmatch);
 
     StoreLastIndex(context, regexp, smi_zero, is_fastpath);
     Goto(if_didnotmatch);
@@ skipping 1476 matching lines @@
   Bind(&slow_path);
   RegExpPrototypeSearchBodySlow(context, receiver, string);
 }
 
 // Generates the fast path for @@split. {regexp} is an unmodified JSRegExp,
 // {string} is a String, and {limit} is a Smi.
 void RegExpBuiltinsAssembler::RegExpPrototypeSplitBody(Node* const context,
                                                        Node* const regexp,
                                                        Node* const string,
                                                        Node* const limit) {
-  Isolate* isolate = this->isolate();
-
   Node* const null = NullConstant();
   Node* const smi_zero = SmiConstant(0);
   Node* const int_zero = IntPtrConstant(0);
   Node* const int_limit = SmiUntag(limit);
 
   const ElementsKind kind = FAST_ELEMENTS;
   const ParameterMode mode = CodeStubAssembler::INTPTR_PARAMETERS;
 
   Node* const allocation_site = nullptr;
   Node* const native_context = LoadNativeContext(context);
@@ skipping 14 matching lines @@
   // array depending on whether the {regexp} matches.
   {
     Label next(this), if_stringisempty(this, Label::kDeferred);
     Branch(SmiEqual(string_length, smi_zero), &if_stringisempty, &next);
 
     Bind(&if_stringisempty);
     {
       Node* const last_match_info = LoadContextElement(
           native_context, Context::REGEXP_LAST_MATCH_INFO_INDEX);
 
-      Callable exec_callable = CodeFactory::RegExpExec(isolate);
-      Node* const match_indices = CallStub(exec_callable, context, regexp,
-                                           string, smi_zero, last_match_info);
+      Node* const match_indices =
+          IrregexpExec(context, regexp, string, smi_zero, last_match_info);
 
       Label return_singleton_array(this);
       Branch(WordEqual(match_indices, null), &return_singleton_array,
              &return_empty_array);
 
       Bind(&return_singleton_array);
       {
         Node* const length = SmiConstant(1);
         Node* const capacity = IntPtrConstant(1);
         Node* const result = AllocateJSArray(kind, array_map, capacity, length,
@@ skipping 37 matching lines @@
       Branch(SmiEqual(next_search_from, string_length), &push_suffix_and_out,
              &next);
       Bind(&next);
     }
 
     // Search for the given {regexp}.
 
     Node* const last_match_info = LoadContextElement(
         native_context, Context::REGEXP_LAST_MATCH_INFO_INDEX);
 
-    Callable exec_callable = CodeFactory::RegExpExec(isolate);
-    Node* const match_indices = CallStub(exec_callable, context, regexp, string,
-                                         next_search_from, last_match_info);
+    Node* const match_indices = IrregexpExec(context, regexp, string,
+                                             next_search_from, last_match_info);
 
     // We're done if no match was found.
     {
       Label next(this);
       Branch(WordEqual(match_indices, null), &push_suffix_and_out, &next);
       Bind(&next);
     }
 
     Node* const match_from = LoadFixedArrayElement(
         match_indices, RegExpMatchInfo::kFirstCaptureIndex);
@@ skipping 626 matching lines @@
   Node* const string = Parameter(2);
   Node* const context = Parameter(5);
 
   Node* const null = NullConstant();
   Node* const smi_zero = SmiConstant(Smi::FromInt(0));
 
   Node* const native_context = LoadNativeContext(context);
   Node* const internal_match_info = LoadContextElement(
       native_context, Context::REGEXP_INTERNAL_MATCH_INFO_INDEX);
 
-  Callable exec_callable = CodeFactory::RegExpExec(isolate());
-  Node* const match_indices = CallStub(exec_callable, context, regexp, string,
-                                       smi_zero, internal_match_info);
+  Node* const match_indices =
+      IrregexpExec(context, regexp, string, smi_zero, internal_match_info);
 
   Label if_matched(this), if_didnotmatch(this);
   Branch(WordEqual(match_indices, null), &if_didnotmatch, &if_matched);
 
   Bind(&if_didnotmatch);
   Return(null);
 
   Bind(&if_matched);
   {
     Node* result =
         ConstructNewResultFromMatchInfo(context, regexp, match_indices, string);
     Return(result);
   }
 }
 
 }  // namespace internal
 }  // namespace v8