[regexp] Migrate @@match to TurboFan

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-utils.h"
 #include "src/builtins/builtins.h"
 
 #include "src/code-factory.h"
 #include "src/regexp/jsregexp.h"
 #include "src/regexp/regexp-utils.h"
@@ skipping 531 matching lines @@
   Node* const proto_map = a->LoadMap(a->LoadMapPrototype(map));
   Node* const proto_has_initialmap =
       a->WordEqual(proto_map, initial_proto_initial_map);
 
   // TODO(ishell): Update this check once map changes for constant field
   // tracking are landing.
 
   a->Branch(proto_has_initialmap, if_isunmodified, if_ismodified);
 }
 
+void BranchIfFastRegExpResult(CodeStubAssembler* a, Node* context, Node* map,
+                              CLabel* if_isunmodified, CLabel* if_ismodified) {
+  Node* const native_context = a->LoadNativeContext(context);
+  Node* const initial_regexp_result_map =
+      a->LoadContextElement(native_context, Context::REGEXP_RESULT_MAP_INDEX);
+
+  a->Branch(a->WordEqual(map, initial_regexp_result_map), if_isunmodified,
+            if_ismodified);
+}
+
 }  // namespace
 
 void Builtins::Generate_RegExpPrototypeFlagsGetter(CodeAssemblerState* state) {
   CodeStubAssembler a(state);
 
   Node* const receiver = a.Parameter(0);
   Node* const context = a.Parameter(3);
 
   Isolate* isolate = a.isolate();
   Node* const int_zero = a.IntPtrConstant(0);
@@ skipping 194 matching lines @@
 Node* FastFlagGetter(CodeStubAssembler* a, Node* const regexp,
                      JSRegExp::Flag flag) {
   Node* const smi_zero = a->SmiConstant(Smi::kZero);
   Node* const flags = a->LoadObjectField(regexp, JSRegExp::kFlagsOffset);
   Node* const mask = a->SmiConstant(Smi::FromInt(flag));
   Node* const is_flag_set = a->WordNotEqual(a->WordAnd(flags, mask), smi_zero);
 
   return is_flag_set;
 }
 
+// Load through the GetProperty stub.
+compiler::Node* SlowFlagGetter(CodeStubAssembler* a,
+                               compiler::Node* const context,
+                               compiler::Node* const regexp,
+                               JSRegExp::Flag flag) {
+  Factory* factory = a->isolate()->factory();
+
+  CLabel out(a);
+  CVariable var_result(a, MachineType::PointerRepresentation());
+
+  Node* name;
+
+  switch (flag) {
+    case JSRegExp::kGlobal:
+      name = a->HeapConstant(factory->global_string());
+      break;
+    case JSRegExp::kIgnoreCase:
+      name = a->HeapConstant(factory->ignoreCase_string());
+      break;
+    case JSRegExp::kMultiline:
+      name = a->HeapConstant(factory->multiline_string());
+      break;
+    case JSRegExp::kSticky:
+      name = a->HeapConstant(factory->sticky_string());
+      break;
+    case JSRegExp::kUnicode:
+      name = a->HeapConstant(factory->unicode_string());
+      break;
+    default:
+      UNREACHABLE();
+  }
+
+  Callable getproperty_callable = CodeFactory::GetProperty(a->isolate());
+  Node* const value = a->CallStub(getproperty_callable, context, regexp, name);
+
+  CLabel if_true(a), if_false(a);
+  a->BranchIfToBooleanIsTrue(value, &if_true, &if_false);
+
+  a->Bind(&if_true);
+  {
+    var_result.Bind(a->IntPtrConstant(1));
+    a->Goto(&out);
+  }
+
+  a->Bind(&if_false);
+  {
+    var_result.Bind(a->IntPtrConstant(0));
+    a->Goto(&out);
+  }
+
+  a->Bind(&out);
+  return var_result.value();
+}
+
 void Generate_FlagGetter(CodeStubAssembler* a, JSRegExp::Flag flag,
                          v8::Isolate::UseCounterFeature counter,
                          const char* method_name) {
   Node* const receiver = a->Parameter(0);
   Node* const context = a->Parameter(3);
 
   Isolate* isolate = a->isolate();
 
   // Check whether we have an unmodified regexp instance.
   CLabel if_isunmodifiedjsregexp(a),
@@ skipping 266 matching lines @@
 
   // Call exec.
   Node* const match_indices = RegExpExec(&a, context, receiver, string);
 
   // Return true iff exec matched successfully.
   Node* const result = a.Select(a.WordEqual(match_indices, a.NullConstant()),
                                 a.FalseConstant(), a.TrueConstant());
   a.Return(result);
 }
 
+namespace {
+
+Node* AdvanceStringIndex(CodeStubAssembler* a, Node* const string,
+                         Node* const index, Node* const is_unicode) {
+  CVariable var_result(a, MachineRepresentation::kTagged);
+
+  // Default to last_index + 1.
+  Node* const index_plus_one = a->SmiAdd(index, a->SmiConstant(1));
+  var_result.Bind(index_plus_one);
+
+  CLabel if_isunicode(a), out(a);
+  a->Branch(is_unicode, &if_isunicode, &out);
+
+  a->Bind(&if_isunicode);
+  {
+    Node* const string_length = a->LoadStringLength(string);
+    a->GotoUnless(a->SmiLessThan(index_plus_one, string_length), &out);
+
+    Node* const lead = a->StringCharCodeAt(string, index);
+    a->GotoUnless(a->Word32Equal(a->Word32And(lead, a->Int32Constant(0xFC00)),
+                                 a->Int32Constant(0xD800)),
+                  &out);
+
+    Node* const trail = a->StringCharCodeAt(string, index_plus_one);
+    a->GotoUnless(a->Word32Equal(a->Word32And(trail, a->Int32Constant(0xFC00)),
+                                 a->Int32Constant(0xDC00)),
+                  &out);
+
+    // At a surrogate pair, return index + 2.
+    Node* const index_plus_two = a->SmiAdd(index, a->SmiConstant(2));
+    var_result.Bind(index_plus_two);
+
+    a->Goto(&out);
+  }
+
+  a->Bind(&out);
+  return var_result.value();
+}
+
+Node* NewFixedArrayCapacity(CodeStubAssembler* a,
+                            Node* const current_capacity) {
+  CSA_ASSERT(a, a->IntPtrGreaterThan(current_capacity, a->IntPtrConstant(0)));
+
+  // Growth rate is analog to JSObject::NewElementsCapacity:
+  // new_capacity = (current_capacity + (current_capacity >> 1)) + 16.
+
+  Node* const new_capacity = a->IntPtrAdd(
+      a->IntPtrAdd(current_capacity, a->WordShr(current_capacity, 1)),
+      a->IntPtrConstant(16));
+
+  return new_capacity;
+}
+
+Node* GrowFixedArray(CodeStubAssembler* a, Node* const from_array,
+                     Node* const current_capacity, Node* const new_capacity) {
+  CSA_ASSERT(a, a->IntPtrGreaterThan(current_capacity, a->IntPtrConstant(0)));
+  CSA_ASSERT(a, a->IntPtrGreaterThan(new_capacity, current_capacity));
+
+  ElementsKind kind = FAST_ELEMENTS;
+  WriteBarrierMode barrier_mode = UPDATE_WRITE_BARRIER;
+  CodeStubAssembler::ParameterMode mode = CodeStubAssembler::INTPTR_PARAMETERS;

[Igor Sheludko, 2016/11/25 17:31:27]

|mode| should be passed from outside for consistency.

[jgruber, 2016/11/28 13:28:22]

Done. Refactored growable array handling into a GrowableFixedArray class since
the same code will also be used in an upcoming CL for @@split.

+
+  Node* const to_array = a->AllocateFixedArray(kind, new_capacity, mode);
+  a->CopyFixedArrayElements(kind, from_array, kind, to_array, current_capacity,
+                            new_capacity, barrier_mode, mode);
+
+  return to_array;
+}
+
+void Generate_RegExpPrototypeMatchBody(CodeStubAssembler* a,
+                                       Node* const receiver, Node* const string,
+                                       Node* const context,
+                                       const bool is_fastpath) {
+  Isolate* const isolate = a->isolate();
+
+  Node* const null = a->NullConstant();
+  Node* const int_zero = a->IntPtrConstant(0);
+  Node* const smi_zero = a->SmiConstant(Smi::kZero);
+
+  Node* const regexp = receiver;
+  Node* const is_global =
+      is_fastpath ? FastFlagGetter(a, regexp, JSRegExp::kGlobal)

[Igor Sheludko, 2016/11/25 17:31:27]

Maybe it's worth adding FlagGetter(..., bool is_fastpath).

[jgruber, 2016/11/28 13:28:22]

Done.

+                  : SlowFlagGetter(a, context, regexp, JSRegExp::kGlobal);
+
+  CLabel if_isglobal(a), if_isnotglobal(a);
+  a->Branch(is_global, &if_isglobal, &if_isnotglobal);
+
+  a->Bind(&if_isnotglobal);
+  {
+    Node* const result =
+        is_fastpath ? RegExpPrototypeExecInternal(a, context, regexp, string)
+                    : RegExpExec(a, context, regexp, string);
+    a->Return(result);
+  }
+
+  a->Bind(&if_isglobal);
+  {
+    Node* const is_unicode =
+        is_fastpath ? FastFlagGetter(a, regexp, JSRegExp::kUnicode)
+                    : SlowFlagGetter(a, context, regexp, JSRegExp::kUnicode);
+
+    if (is_fastpath) {
+      FastStoreLastIndex(a, context, regexp, smi_zero);
+    } else {
+      SlowStoreLastIndex(a, context, regexp, smi_zero);
+    }
+
+    // Allocate an array to store the resulting match strings.
+
+    const ElementsKind kind = FAST_ELEMENTS;
+    const CodeStubAssembler::ParameterMode mode =
+        CodeStubAssembler::INTPTR_PARAMETERS;
+
+    static const int kInitialArraySize = 8;
+    Node* const initial_capacity = a->IntPtrConstant(kInitialArraySize);
+    Node* const initial_array =
+        a->AllocateFixedArray(kind, initial_capacity, mode);
+
+    a->FillFixedArrayWithValue(kind, initial_array, int_zero, initial_capacity,
+                               Heap::kTheHoleValueRootIndex, mode);
+
+    CVariable var_array(a, MachineRepresentation::kTagged);
+    var_array.Bind(initial_array);
+
+    CVariable var_array_capacity(a, MachineType::PointerRepresentation());
+    var_array_capacity.Bind(initial_capacity);
+
+    // Loop preparations. Within the loop, collect results from RegExpExec
+    // and store match strings in the array.
+
+    CVariable var_i(a, MachineType::PointerRepresentation());
+    var_i.Bind(int_zero);
+
+    CVariable* vars[] = {&var_i, &var_array, &var_array_capacity};
+    CLabel loop(a, 3, vars), loop_done(a);
+    a->Goto(&loop);
+
+    a->Bind(&loop);
+    {
+      Node* const i = var_i.value();
+      Node* const array_capacity = var_array_capacity.value();
+
+      Node* const result =
+          is_fastpath ? RegExpPrototypeExecInternal(a, context, regexp, string)
+                      : RegExpExec(a, context, regexp, string);
+
+      CLabel if_didmatch(a), if_didnotmatch(a);
+      a->Branch(a->WordEqual(result, null), &if_didnotmatch, &if_didmatch);
+
+      a->Bind(&if_didnotmatch);
+      {
+        // Return null if there were no matches, otherwise just exit the loop.
+        a->GotoUnless(a->IntPtrEqual(i, int_zero), &loop_done);
+        a->Return(null);
+      }
+
+      a->Bind(&if_didmatch);
+      {
+        CVariable var_match(a, MachineRepresentation::kTagged);
+        CLabel fast_result(a), slow_result(a), match_loaded(a);
+        BranchIfFastRegExpResult(a, context, a->LoadMap(result), &fast_result,

[Igor Sheludko, 2016/11/25 17:31:27]

Is it possible that the RegExpPrototypeExecInternal returns a slow result
object? If not then we can deal only with fast results on the fast path.

[jgruber, 2016/11/28 13:28:21]

Done.

+                                 &slow_result);
+
+        a->Bind(&fast_result);
+        {
+          // TODO(jgruber): We could optimize further here and in other
+          // methods (e.g. @@search) by bypassing RegExp result construction.
+          Node* const result_fixed_array = a->LoadElements(result);
+          Node* const match =
+              a->LoadFixedArrayElement(result_fixed_array, int_zero, 0, mode);
+          var_match.Bind(match);
+          a->Goto(&match_loaded);
+        }
+
+        a->Bind(&slow_result);
+        {
+          Node* const name = a->HeapConstant(

[Igor Sheludko, 2016/11/25 17:31:27]

You can use SmiConstant(0) here.

+              isolate->factory()->NewStringFromAsciiChecked("0"));
+          Callable getproperty_callable = CodeFactory::GetProperty(isolate);

[Igor Sheludko, 2016/11/25 17:31:27]

// TODO(ishell): Use GetElement stub once it's available.

[jgruber, 2016/11/28 13:28:21]

Done.

+          Node* const match =
+              a->CallStub(getproperty_callable, context, result, name);
+
+          var_match.Bind(match);
+          a->Goto(&match_loaded);
+        }
+
+        a->Bind(&match_loaded);
+
+        // The match is guaranteed to be a string on the fast path.

[Igor Sheludko, 2016/11/25 17:31:27]

CSA_ASSERT that?

[jgruber, 2016/11/28 13:28:22]

Done.

+        Node* const match = is_fastpath
+                                ? var_match.value()
+                                : a->ToString(context, var_match.value());
+
+        // Store the match, growing the fixed array if needed.
+
+        CLabel grow_array(a), store_match(a);
+        a->Branch(a->IntPtrEqual(array_capacity, i), &grow_array, &store_match);
+
+        a->Bind(&grow_array);
+        {
+          Node* const new_array_capacity =
+              NewFixedArrayCapacity(a, array_capacity);
+          Node* const new_array = GrowFixedArray(
+              a, var_array.value(), array_capacity, new_array_capacity);
+
+          var_array_capacity.Bind(new_array_capacity);
+          var_array.Bind(new_array);
+          a->Goto(&store_match);
+        }
+
+        a->Bind(&store_match);
+
+        Node* const array = var_array.value();
+
+        WriteBarrierMode barrier_mode = UPDATE_WRITE_BARRIER;
+        a->StoreFixedArrayElement(array, i, match, barrier_mode, 0, mode);
+
+        // Increment our index counter.
+
+        Node* const new_i = a->IntPtrAdd(i, a->IntPtrConstant(1));
+        var_i.Bind(new_i);
+
+        // Advance last index if the match is the empty string.
+
+        Node* const match_length = a->LoadStringLength(match);
+        a->GotoUnless(a->SmiEqual(match_length, smi_zero), &loop);
+
+        Node* last_index = is_fastpath ? FastLoadLastIndex(a, context, regexp)
+                                       : SlowLoadLastIndex(a, context, regexp);
+
+        Callable tolength_callable = CodeFactory::ToLength(isolate);
+        last_index = a->CallStub(tolength_callable, context, last_index);
+
+        Node* const new_last_index =
+            AdvanceStringIndex(a, string, last_index, is_unicode);
+
+        if (is_fastpath) {
+          FastStoreLastIndex(a, context, regexp, new_last_index);
+        } else {
+          SlowStoreLastIndex(a, context, regexp, new_last_index);
+        }
+
+        a->Goto(&loop);
+      }
+    }
+
+    a->Bind(&loop_done);
+    {
+      // Wrap the match in a JSArray.
+
+      Node* const native_context = a->LoadNativeContext(context);
+      Node* const array_map = a->LoadJSArrayElementsMap(kind, native_context);
+      Node* const result_length = a->SmiTag(var_i.value());
+      Node* const result = a->AllocateUninitializedJSArrayWithoutElements(
+          kind, array_map, result_length, nullptr);
+
+      // Note: We do not currently shrink the fixed array.
+
+      a->StoreObjectField(result, JSObject::kElementsOffset, var_array.value());
+
+      a->Return(result);
+    }
+  }
+}
+
+}  // namespace
+
 // ES#sec-regexp.prototype-@@match
 // RegExp.prototype [ @@match ] ( string )
-BUILTIN(RegExpPrototypeMatch) {
-  HandleScope scope(isolate);
-  CHECK_RECEIVER(JSReceiver, recv, "RegExp.prototype.@@match");
-
-  Handle<Object> string_obj = args.atOrUndefined(isolate, 1);
-
-  Handle<String> string;
-  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, string,
-                                     Object::ToString(isolate, string_obj));
-
-  Handle<Object> global_obj;
-  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
-      isolate, global_obj,
-      JSReceiver::GetProperty(recv, isolate->factory()->global_string()));
-  const bool global = global_obj->BooleanValue();
-
-  if (!global) {
-    RETURN_RESULT_OR_FAILURE(
-        isolate,
-        RegExpUtils::RegExpExec(isolate, recv, string,
-                                isolate->factory()->undefined_value()));
-  }
-
-  Handle<Object> unicode_obj;
-  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
-      isolate, unicode_obj,
-      JSReceiver::GetProperty(recv, isolate->factory()->unicode_string()));
-  const bool unicode = unicode_obj->BooleanValue();
-
-  RETURN_FAILURE_ON_EXCEPTION(isolate,
-                              RegExpUtils::SetLastIndex(isolate, recv, 0));
-
-  static const int kInitialArraySize = 8;
-  Handle<FixedArray> elems =
-      isolate->factory()->NewFixedArrayWithHoles(kInitialArraySize);
-
-  int n = 0;
-  for (;; n++) {
-    Handle<Object> result;
-    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
-        isolate, result,
-        RegExpUtils::RegExpExec(isolate, recv, string,
-                                isolate->factory()->undefined_value()));
-
-    if (result->IsNull(isolate)) {
-      if (n == 0) return isolate->heap()->null_value();
-      break;
-    }
-
-    Handle<Object> match_obj;
-    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match_obj,
-                                       Object::GetElement(isolate, result, 0));
-
-    Handle<String> match;
-    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, match,
-                                       Object::ToString(isolate, match_obj));
-
-    elems = FixedArray::SetAndGrow(elems, n, match);
-
-    if (match->length() == 0) {
-      RETURN_FAILURE_ON_EXCEPTION(isolate, RegExpUtils::SetAdvancedStringIndex(
-                                               isolate, recv, string, unicode));
-    }
-  }
-
-  elems->Shrink(n);
-  return *isolate->factory()->NewJSArrayWithElements(elems);
+void Builtins::Generate_RegExpPrototypeMatch(CodeAssemblerState* state) {
+  CodeStubAssembler a(state);
+
+  Node* const maybe_receiver = a.Parameter(0);
+  Node* const maybe_string = a.Parameter(1);
+  Node* const context = a.Parameter(4);
+
+  // Ensure {maybe_receiver} is a JSReceiver.
+  Node* const map = ThrowIfNotJSReceiver(
+      &a, a.isolate(), context, maybe_receiver,
+      MessageTemplate::kIncompatibleMethodReceiver, "RegExp.prototype.@@match");
+  Node* const receiver = maybe_receiver;
+
+  // Convert {maybe_string} to a String.
+  Node* const string = a.ToString(context, maybe_string);
+
+  CLabel fast_path(&a), slow_path(&a);
+  BranchIfFastPath(&a, context, map, &fast_path, &slow_path);
+
+  a.Bind(&fast_path);
+  Generate_RegExpPrototypeMatchBody(&a, receiver, string, context, true);
+
+  a.Bind(&slow_path);
+  Generate_RegExpPrototypeMatchBody(&a, receiver, string, context, false);
 }
 
 namespace {
 
 void Generate_RegExpPrototypeSearchBody(CodeStubAssembler* a,
                                         Node* const receiver,
                                         Node* const string, Node* const context,
                                         bool is_fastpath) {
   Isolate* const isolate = a->isolate();
 
@@ skipping 40 matching lines @@
   {
     CLabel next(a);
     a->GotoUnless(a->WordEqual(match_indices, a->NullConstant()), &next);
     a->Return(a->SmiConstant(-1));
     a->Bind(&next);
   }
 
   // Return the index of the match.
   {
     CLabel fast_result(a), slow_result(a, CLabel::kDeferred);
-
-    Node* const native_context = a->LoadNativeContext(context);
-    Node* const initial_regexp_result_map =
-        a->LoadContextElement(native_context, Context::REGEXP_RESULT_MAP_INDEX);
-    Node* const match_indices_map = a->LoadMap(match_indices);
-
-    a->Branch(a->WordEqual(match_indices_map, initial_regexp_result_map),
-              &fast_result, &slow_result);
+    BranchIfFastRegExpResult(a, context, a->LoadMap(match_indices),

[Igor Sheludko, 2016/11/25 17:31:27]

Same here.

[jgruber, 2016/11/28 13:28:22]

Done.

+                             &fast_result, &slow_result);
 
     a->Bind(&fast_result);
     {
       Node* const index =
           a->LoadObjectField(match_indices, JSRegExpResult::kIndexOffset,
                              MachineType::AnyTagged());
       a->Return(index);
     }
 
     a->Bind(&slow_result);
@@ skipping 841 matching lines @@
   a.Bind(&if_matched);
   {
     Node* result = ConstructNewResultFromMatchInfo(isolate, &a, context,
                                                    match_indices, string);
     a.Return(result);
   }
 }
 
 }  // namespace internal
 }  // namespace v8