[string] Add a fast path to String.p.replace

src/builtins/builtins-string-gen.cc

 // Copyright 2017 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-gen.h"
 #include "src/builtins/builtins-utils-gen.h"
 #include "src/builtins/builtins.h"
 #include "src/code-factory.h"
 #include "src/code-stub-assembler.h"
 #include "src/objects.h"
 
 namespace v8 {
 namespace internal {
 
 typedef CodeStubAssembler::RelationalComparisonMode RelationalComparisonMode;
 
 class StringBuiltinsAssembler : public CodeStubAssembler {
  public:
   explicit StringBuiltinsAssembler(compiler::CodeAssemblerState* state)
       : CodeStubAssembler(state) {}
 
+  // ES#sec-getsubstitution
+  Node* GetSubstitution(Node* context, Node* subject_string,
+                        Node* match_start_index, Node* match_end_index,
+                        Node* replace_string);
+
  protected:
   Node* DirectStringData(Node* string, Node* string_instance_type) {
     // Compute the effective offset of the first character.
     VARIABLE(var_data, MachineType::PointerRepresentation());
     Label if_sequential(this), if_external(this), if_join(this);
     Branch(Word32Equal(Word32And(string_instance_type,
                                  Int32Constant(kStringRepresentationMask)),
                        Int32Constant(kSeqStringTag)),
            &if_sequential, &if_external);
 
@@ skipping 73 matching lines @@
 
   Node* ToSmiBetweenZeroAnd(Node* context, Node* value, Node* limit);
 
   Node* LoadSurrogatePairAt(Node* string, Node* length, Node* index,
                             UnicodeEncoding encoding);
 
   void StringIndexOf(Node* receiver, Node* instance_type, Node* search_string,
                      Node* search_string_instance_type, Node* position,
                      std::function<void(Node*)> f_return);
 
+  Node* IndexOfDollarChar(Node* const context, Node* const string);
+
   Node* IsNullOrUndefined(Node* const value);
   void RequireObjectCoercible(Node* const context, Node* const value,
                               const char* method_name);
 
   Node* SmiIsNegative(Node* const value) {
     return SmiLessThan(value, SmiConstant(0));
   }
 
   // Implements boilerplate logic for {match, split, replace, search} of the
   // form:
@@ skipping 859 matching lines @@
   GotoIf(IsUndefined(maybe_func), &out);
 
   // Attempt to call the function.
 
   Node* const result = generic_call(maybe_func);
   Return(result);
 
   BIND(&out);
 }
 
+compiler::Node* StringBuiltinsAssembler::IndexOfDollarChar(Node* const context,
+                                                           Node* const string) {
+  CSA_ASSERT(this, IsString(string));
+
+  Node* const dollar_string = HeapConstant(
+      isolate()->factory()->LookupSingleCharacterStringFromCode('$'));
+  Node* const dollar_ix = CallBuiltin(Builtins::kStringIndexOf, context, string,
+                                      dollar_string, SmiConstant(0));
+
+  CSA_ASSERT(this, TaggedIsSmi(dollar_ix));
+  return dollar_ix;
+}
+
+compiler::Node* StringBuiltinsAssembler::GetSubstitution(
+    Node* context, Node* subject_string, Node* match_start_index,
+    Node* match_end_index, Node* replace_string) {
+  CSA_ASSERT(this, IsString(subject_string));
+  CSA_ASSERT(this, IsString(replace_string));
+  CSA_ASSERT(this, TaggedIsPositiveSmi(match_start_index));
+  CSA_ASSERT(this, TaggedIsPositiveSmi(match_end_index));
+
+  VARIABLE(var_result, MachineRepresentation::kTagged, replace_string);
+  Label runtime(this), out(this);
+
+  // In this primitive implementation we simply look for the next '$' char in
+  // {replace_string}. If it doesn't exist, we can simply return
+  // {replace_string} itself. If it does, then we delegate to
+  // String::GetSubstitution, passing in the index of the first '$' to avoid
+  // repeated scanning work.
+  // TODO(jgruber): Possibly extend this in the future to handle more complex
+  // cases without runtime calls.
+
+  Node* const dollar_index = IndexOfDollarChar(context, replace_string);
+  Branch(SmiIsNegative(dollar_index), &out, &runtime);
+
+  BIND(&runtime);
+  {
+    CSA_ASSERT(this, TaggedIsPositiveSmi(dollar_index));
+
+    Callable substring_callable = CodeFactory::SubString(isolate());
+    Node* const matched = CallStub(substring_callable, context, subject_string,
+                                   match_start_index, match_end_index);
+    Node* const replacement_string =
+        CallRuntime(Runtime::kGetSubstitution, context, matched, subject_string,
+                    match_start_index, replace_string, dollar_index);
+    var_result.Bind(replacement_string);
+
+    Goto(&out);
+  }
+
+  BIND(&out);
+  return var_result.value();
+}
+
 // ES6 #sec-string.prototype.replace
 TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) {
   Label out(this);
 
   Node* const receiver = Parameter(Descriptor::kReceiver);
   Node* const search = Parameter(Descriptor::kSearch);
   Node* const replace = Parameter(Descriptor::kReplace);
   Node* const context = Parameter(Descriptor::kContext);
 
   Node* const smi_zero = SmiConstant(0);
@@ skipping 22 matching lines @@
 
   Callable tostring_callable = CodeFactory::ToString(isolate());
   Callable indexof_callable = CodeFactory::StringIndexOf(isolate());
 
   Node* const subject_string = CallStub(tostring_callable, context, receiver);
   Node* const search_string = CallStub(tostring_callable, context, search);
 
   Node* const subject_length = LoadStringLength(subject_string);
   Node* const search_length = LoadStringLength(search_string);
 
-  // Fast-path single-char {search}, long {receiver}, and simple string
+  // Fast-path single-char {search}, long cons {receiver}, and simple string
   // {replace}.
   {
     Label next(this);
 
     GotoIfNot(SmiEqual(search_length, SmiConstant(1)), &next);
     GotoIfNot(SmiGreaterThan(subject_length, SmiConstant(0xFF)), &next);
     GotoIf(TaggedIsSmi(replace), &next);
     GotoIfNot(IsString(replace), &next);
 
-    Node* const dollar_string = HeapConstant(
-        isolate()->factory()->LookupSingleCharacterStringFromCode('$'));
-    Node* const dollar_ix =
-        CallStub(indexof_callable, context, replace, dollar_string, smi_zero);
-    GotoIfNot(SmiIsNegative(dollar_ix), &next);
+    Node* const subject_instance_type = LoadInstanceType(subject_string);
+    GotoIfNot(IsConsStringInstanceType(subject_instance_type), &next);
+
+    GotoIf(TaggedIsPositiveSmi(IndexOfDollarChar(context, replace)), &next);
 
     // Searching by traversing a cons string tree and replace with cons of
     // slices works only when the replaced string is a single character, being
     // replaced by a simple string and only pays off for long strings.
     // TODO(jgruber): Reevaluate if this is still beneficial.
     // TODO(jgruber): TailCallRuntime when it correctly handles adapter frames.
     Return(CallRuntime(Runtime::kStringReplaceOneCharWithString, context,
                        subject_string, search_string, replace));
 
     BIND(&next);
@@ skipping 68 matching lines @@
     Node* const replacement_string =
         CallStub(tostring_callable, context, replacement);
     var_result.Bind(CallStub(stringadd_callable, context, var_result.value(),
                              replacement_string));
     Goto(&out);
   }
 
   BIND(&if_notcallablereplace);
   {
     Node* const replace_string = CallStub(tostring_callable, context, replace);
-
-    // TODO(jgruber): Simplified GetSubstitution implementation in CSA.
-    Node* const matched = CallStub(substring_callable, context, subject_string,
-                                   match_start_index, match_end_index);
-    Node* const replacement_string =
-        CallRuntime(Runtime::kGetSubstitution, context, matched, subject_string,
-                    match_start_index, replace_string);
-    var_result.Bind(CallStub(stringadd_callable, context, var_result.value(),
-                             replacement_string));
+    Node* const replacement =
+        GetSubstitution(context, subject_string, match_start_index,
+                        match_end_index, replace_string);
+    var_result.Bind(
+        CallStub(stringadd_callable, context, var_result.value(), replacement));
     Goto(&out);
   }
 
   BIND(&out);
   {
     Node* const suffix = CallStub(substring_callable, context, subject_string,
                                   match_end_index, subject_length);
     Node* const result =
         CallStub(stringadd_callable, context, var_result.value(), suffix);
     Return(result);
@@ skipping 492 matching lines @@
     CallRuntime(Runtime::kThrowIncompatibleMethodReceiver, context,
                 HeapConstant(factory()->NewStringFromAsciiChecked(
                     "String Iterator.prototype.next", TENURED)),
                 iterator);
     Unreachable();
   }
 }
 
 }  // namespace internal
 }  // namespace v8