[runtime] Port simple String.prototype.indexOf cases to TF Builtin

src/builtins/builtins-string.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.h"
 #include "src/builtins/builtins-utils.h"
 
 #include "src/code-factory.h"
+#include "src/code-stub-assembler.h"
 #include "src/regexp/regexp-utils.h"
 
 namespace v8 {
 namespace internal {
 
 typedef CodeStubAssembler::ResultMode ResultMode;
 typedef CodeStubAssembler::RelationalComparisonMode RelationalComparisonMode;
 
+class StringBuiltinsAssembler : public CodeStubAssembler {
+ public:
+  explicit StringBuiltinsAssembler(compiler::CodeAssemblerState* state)
+      : CodeStubAssembler(state) {}
+
+ protected:
+  Node* LoadOneByteChar(Node* string, Node* index) {
+    return Load(MachineType::Uint8(), string, OneByteCharOffset(index));
+  }
+
+  Node* OneByteCharOffset(Node* index) {
+    return CharOffset(String::ONE_BYTE_ENCODING, index);
+  }
+
+  Node* CharOffset(String::Encoding encoding, Node* index) {
+    const int header = SeqOneByteString::kHeaderSize - kHeapObjectTag;
+    Node* offset = index;
+    if (encoding == String::TWO_BYTE_ENCODING) {
+      offset = IntPtrAddFoldConstants(offset, offset);
+    }
+    offset = IntPtrAddFoldConstants(offset, IntPtrConstant(header));
+    return offset;
+  }
+
+  void BranchIfSimpleOneByteStringInstanceType(Node* instance_type,

[Jakob Kummerow, 2016/12/06 06:58:40]

high-level comment: using bit masks would probably be faster:

const int kMask = kStringRepresentationMask | kStringEncodingMask;
const int kOneByteSeqString = kSeqStringTag | kOneByteStringTag;
Node* masked = Word32And(instance_type, Int32Constant(kMask));
Branch(Word32Equal(masked, Int32Constant(kOneByteSeqString)), if_true,
if_false);

In fact, you can check two instance types with a single branch if you extend the
above like so:

Word32Equal(Word32And(masked1, Word32Shl(masked2, 2)), 
            Int32Constant((kOneByteSeqString << 8) | kOneByteSeqString)

[Camillo Bruni, 2016/12/12 15:45:20]

Replaced with the simpler version to check with the mask for several string
types.
Still keeping the separate branches.

+                                               Label* if_true,
+                                               Label* if_false) {
+    Label if_not_one_byte_internalize(this);

[Jakob Kummerow, 2016/12/06 06:58:40]

nit: s/internalize/internalized/ (or you can call it "if_not_internalized" if
you like brevity)

+    Branch(IntPtrEqual(instance_type,

[Jakob Kummerow, 2016/12/06 06:58:40]

This should be either Word32Equal/Int32Constant, or IntPtrEqual/IntPtrConstant,
and matched up with its call sites. Don't mix bit widths!

+                       Int32Constant(ONE_BYTE_INTERNALIZED_STRING_TYPE)),
+           if_true, &if_not_one_byte_internalize);
+    Bind(&if_not_one_byte_internalize);
+    Branch(IntPtrEqual(instance_type, Int32Constant(ONE_BYTE_STRING_TYPE)),

[Jakob Kummerow, 2016/12/06 06:58:40]

same

+           if_true, if_false);
+  }
+};
+
 namespace {
 
 void GenerateStringEqual(CodeStubAssembler* assembler, ResultMode mode) {
   // Here's pseudo-code for the algorithm below in case of kDontNegateResult
   // mode; for kNegateResult mode we properly negate the result.
   //
   // if (lhs == rhs) return true;
   // if (lhs->length() != rhs->length()) return false;
   // if (lhs->IsInternalizedString() && rhs->IsInternalizedString()) {
   //   return false;
@@ skipping 534 matching lines @@
   }
 
   if (value->Number() < 0 || value->Number() > 0x10FFFF) {
     return false;
   }
 
   return true;
 }
 
 uc32 NextCodePoint(Isolate* isolate, BuiltinArguments args, int index) {
-  Handle<Object> value = args.at<Object>(1 + index);
+  Handle<Object> value = args.at(1 + index);
   ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, value, Object::ToNumber(value), -1);
   if (!IsValidCodePoint(isolate, value)) {
     isolate->Throw(*isolate->factory()->NewRangeError(
         MessageTemplate::kInvalidCodePoint, value));
     return -1;
   }
   return DoubleToUint32(value->Number());
 }
 
 }  // namespace
@@ skipping 243 matching lines @@
       Object::ToInteger(isolate, args.atOrUndefined(isolate, 2)));
 
   double index = std::max(position->Number(), 0.0);
   index = std::min(index, static_cast<double>(str->length()));
 
   int index_in_str = String::IndexOf(isolate, str, search_string,
                                      static_cast<uint32_t>(index));
   return *isolate->factory()->ToBoolean(index_in_str != -1);
 }
 
-// ES6 section 21.1.3.8 String.prototype.indexOf ( searchString [ , position ] )
-BUILTIN(StringPrototypeIndexOf) {
-  HandleScope handle_scope(isolate);
+// ES6 #sec-string.prototype.indexof
+TF_BUILTIN(StringPrototypeIndexOf, StringBuiltinsAssembler) {
+  Variable search_string(this, MachineRepresentation::kTagged),
+      position(this, MachineRepresentation::kTagged);
+  Label call_runtime(this), argc_0(this), no_argc_0(this), argc_1(this),
+      no_argc_1(this), argc_2(this), fast_path(this), return_minus_1(this);
 
-  return String::IndexOf(isolate, args.receiver(),
-                         args.atOrUndefined(isolate, 1),
-                         args.atOrUndefined(isolate, 2));
+  // Parameter(0) = nof arguments.

[Jakob Kummerow, 2016/12/06 06:58:40]

nit: this comment doesn't add anything (and runs the risk of getting stale).

[Camillo Bruni, 2016/12/12 15:45:20]

removed.

+  Node* argc =
+      ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount));
+  Node* context = Parameter(BuiltinDescriptor::kContext);
+
+  CodeStubArguments arguments(this, argc);
+  Node* const receiver = arguments.GetReceiver();

[Jakob Kummerow, 2016/12/06 06:58:40]

Is there a particular reason for the "const" annotations here and below?

[Camillo Bruni, 2016/12/12 15:45:20]

mostly copy-paste habit, doubt that they will add any value actually :)
Removed them all.

+
+  GotoIf(IntPtrEqual(argc, IntPtrConstant(0)), &argc_0);
+  GotoIf(IntPtrEqual(argc, IntPtrConstant(1)), &argc_1);
+  Goto(&argc_2);
+  Bind(&argc_0);
+  {
+    Comment("0 Argument case");
+    Node* const undefined = UndefinedConstant();
+    search_string.Bind(undefined);
+    position.Bind(undefined);
+    Goto(&call_runtime);
+  }
+  Bind(&argc_1);
+  {
+    Comment("1 Argument case");
+    search_string.Bind(arguments.AtIndex(0));
+    position.Bind(SmiConstant(0));
+    Goto(&fast_path);
+  }
+  Bind(&argc_2);
+  {
+    Comment("2 Argument case");
+    search_string.Bind(arguments.AtIndex(0));
+    position.Bind(arguments.AtIndex(1));
+    Goto(&fast_path);
+  }
+
+  Bind(&fast_path);
+  {
+    Label zero_length_needle(this);
+    GotoIf(TaggedIsSmi(receiver), &call_runtime);
+    Node* const instance_type = LoadInstanceType(receiver);
+    GotoUnless(IsStringInstanceType(instance_type), &call_runtime);
+
+    Node* const needle = search_string.value();
+    Node* const needle_instance_type = LoadInstanceType(needle);
+    GotoUnless(IsStringInstanceType(needle_instance_type), &call_runtime);
+    GotoUnless(TaggedIsSmi(position.value()), &call_runtime);
+
+    Node* const needle_length = SmiUntag(LoadStringLength(needle));
+    // Use possibly faster runtime fallback for long search strings.
+    GotoIf(IntPtrLessThan(IntPtrConstant(1), needle_length), &call_runtime);
+    Node* const string_length = SmiUntag(LoadStringLength(receiver));
+    Node* const start_position = SmiUntag(position.value());
+
+    GotoIf(IntPtrEqual(IntPtrConstant(0), needle_length), &zero_length_needle);
+    // Check that the needle fits in the start position.
+    GotoUnless(IntPtrLessThanOrEqual(needle_length,
+                                     IntPtrSub(string_length, start_position)),
+               &return_minus_1);
+    // Only support one-byte strings on the fast path.
+    Label check_needle(this), continue_fast_path(this);
+    BranchIfSimpleOneByteStringInstanceType(instance_type, &check_needle,

[Jakob Kummerow, 2016/12/06 06:58:40]

How important is the zero_length_needle case?
You have two instance-type branches first, then the zero_length_needle check,
then another two, more restrictive instance-type branches. You could collapse
all four into a single branch (see comment on
BranchIfSimpleOneByteStringInstanceType), at the cost of losing fast-path
support for zero-length needles that happen to have non-one-byte instance types
(not sure if that ever happens).

[Camillo Bruni, 2016/12/12 15:45:20]

Not that important, but it's easy enough to implement.
I've also seen evidence of having too big needle lengths on externalized strings
fairly high up in the list, which was the original motivation to have the
branches separate.

Here the top 20 parameters for string-indexof on our top25 + speedometer:

   1692 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=STRING_TYPE position=0.000000 receiver_len=1 search_len=9
   1746 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=ONE_BYTE_STRING_TYPE position=0.000000 receiver_len=1 search_len=10
   1899 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=STRING_TYPE position=0.000000 receiver_len=1 search_len=8
   2061 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=ONE_BYTE_STRING_TYPE position=0.000000 receiver_len=1 search_len=9
   2096 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=STRING_TYPE position=0.000000 receiver_len=2 search_len=4
   2142 indexof receiver_type=SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE
search_type=ONE_BYTE_STRING_TYPE position=0.000000 receiver_len=1 search_len=1
   2205 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=STRING_TYPE position=0.000000 receiver_len=1 search_len=7
   2304 indexof receiver_type=ONE_BYTE_STRING_TYPE
search_type=ONE_BYTE_STRING_TYPE position=0.000000 receiver_len=29 search_len=3
   2359 indexof receiver_type=ONE_BYTE_INTERNALIZED_STRING_TYPE
search_type=SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE position=0.000000
receiver_len=4 search_len=1
   3258 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=STRING_TYPE position=0.000000 receiver_len=1 search_len=5
   3405 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=ONE_BYTE_INTERNALIZED_STRING_TYPE position=0.000000 receiver_len=11
search_len=8
   3456 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=STRING_TYPE position=0.000000 receiver_len=1 search_len=6
   4583 indexof receiver_type=ONE_BYTE_INTERNALIZED_STRING_TYPE
search_type=ONE_BYTE_INTERNALIZED_STRING_TYPE position=0.000000 receiver_len=2
search_len=1
   4716 indexof receiver_type=EXTERNAL_ONE_BYTE_STRING_TYPE
search_type=STRING_TYPE position=0.000000 receiver_len=1 search_len=4
   8950 indexof receiver_type=ONE_BYTE_STRING_TYPE
search_type=ONE_BYTE_STRING_TYPE position=0.000000 receiver_len=2 search_len=11
   8951 indexof receiver_type=ONE_BYTE_STRING_TYPE
search_type=ONE_BYTE_STRING_TYPE position=0.000000 receiver_len=2 search_len=12
  11316 indexof receiver_type=SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE
search_type=SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE position=0.000000
receiver_len=1 search_len=1
  48364 indexof receiver_type=ONE_BYTE_INTERNALIZED_STRING_TYPE
search_type=ONE_BYTE_STRING_TYPE position=0.000000 receiver_len=42 search_len=1
  62396 indexof receiver_type=ONE_BYTE_INTERNALIZED_STRING_TYPE
search_type=SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE position=0.000000
receiver_len=42 search_len=1
  94056 indexof receiver_type=ONE_BYTE_INTERNALIZED_STRING_TYPE
search_type=ONE_BYTE_INTERNALIZED_STRING_TYPE position=0.000000 receiver_len=42
search_len=1

+                                            &call_runtime);
+    Bind(&check_needle);
+    BranchIfSimpleOneByteStringInstanceType(needle_instance_type,
+                                            &continue_fast_path, &call_runtime);
+    Bind(&continue_fast_path);
+
+    // Loops over 1-byte strings longer than 32 characters are implemented
+    // faster in C++ making use of faster vector operations.
+    GotoIf(IntPtrGreaterThan(string_length, IntPtrConstant(32)), &call_runtime);

[Camillo Bruni, 2016/12/05 16:32:33]

I tried unrolling a loop of 8 and 16 iterations respectively with only minor
improvements.

+
+    // Loop over the 1-byte string comparing against the single character of the
+    // needle.
+    MachineType type = MachineType::Uint8();
+    Node* const needle_byte = LoadOneByteChar(needle, IntPtrConstant(0));
+    Node* const start_offset = OneByteCharOffset(start_position);
+    Node* const end_offset = OneByteCharOffset(string_length);
+
+    Variable offset(this, MachineType::PointerRepresentation());
+
+    offset.Bind(start_offset);
+    Label loop(this, &offset), found(this);
+
+    Branch(WordEqual(offset.value(), end_offset), &return_minus_1, &loop);
+    Bind(&loop);

[Jakob Kummerow, 2016/12/06 06:58:40]

Consider using BuildFastLoop().

+    {
+      Node* const byte = Load(type, receiver, offset.value());
+      GotoIf(IntPtrEqual(byte, needle_byte), &found);

[Jakob Kummerow, 2016/12/06 06:58:40]

This should probably be Word32Equal.

+
+      offset.Bind(IntPtrAdd(offset.value(), IntPtrConstant(1)));
+      Branch(WordEqual(offset.value(), end_offset), &return_minus_1, &loop);
+    }
+    Bind(&found);
+    Node* const zero_offset = OneByteCharOffset(IntPtrConstant(0));
+    arguments.PopAndReturn(SmiTag(IntPtrSub(offset.value(), zero_offset)));
+
+    Bind(&zero_length_needle);
+    {
+      arguments.PopAndReturn(SmiTag(IntPtrMin(string_length, start_position)));
+    }
+  }
+
+  Bind(&return_minus_1);
+  { arguments.PopAndReturn(SmiConstant(-1)); }
+
+  Bind(&call_runtime);
+  {
+    Node* result =
+        CallRuntime(Runtime::kStringPrototypeIndexOf, context, receiver,
+                    search_string.value(), position.value());
+    arguments.PopAndReturn(result);
+  }
 }
 
 // ES6 section 21.1.3.9
 // String.prototype.lastIndexOf ( searchString [ , position ] )
 BUILTIN(StringPrototypeLastIndexOf) {
   HandleScope handle_scope(isolate);
   return String::LastIndexOf(isolate, args.receiver(),
                              args.atOrUndefined(isolate, 1),
                              args.atOrUndefined(isolate, 2));
 }
 
 // ES6 section 21.1.3.10 String.prototype.localeCompare ( that )
 //
 // This function is implementation specific.  For now, we do not
 // do anything locale specific.
 // If internationalization is enabled, then i18n.js will override this function
 // and provide the proper functionality, so this is just a fallback.
 BUILTIN(StringPrototypeLocaleCompare) {
   HandleScope handle_scope(isolate);
   DCHECK_EQ(2, args.length());
 
   TO_THIS_STRING(str1, "String.prototype.localeCompare");
   Handle<String> str2;
-  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
-      isolate, str2, Object::ToString(isolate, args.at<Object>(1)));
+  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, str2,
+                                     Object::ToString(isolate, args.at(1)));
 
   if (str1.is_identical_to(str2)) return Smi::kZero;  // Equal.
   int str1_length = str1->length();
   int str2_length = str2->length();
 
   // Decide trivial cases without flattening.
   if (str1_length == 0) {
     if (str2_length == 0) return Smi::kZero;  // Equal.
     return Smi::FromInt(-str2_length);
   } else {
@@ skipping 589 matching lines @@
         Runtime::kThrowIncompatibleMethodReceiver, context,
         assembler.HeapConstant(assembler.factory()->NewStringFromAsciiChecked(
             "String Iterator.prototype.next", TENURED)),
         iterator);
     assembler.Return(result);  // Never reached.
   }
 }
 
 }  // namespace internal
 }  // namespace v8