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

src/builtins/builtins-string.cc

Index: src/builtins/builtins-string.cc
diff --git a/src/builtins/builtins-string.cc b/src/builtins/builtins-string.cc
index 7799b288e51842fbe773b0634ca077f524606b28..81d9dd8179ddb79f9780be3e48e48627fdfa5933 100644
--- a/src/builtins/builtins-string.cc
+++ b/src/builtins/builtins-string.cc
@@ -6,6 +6,7 @@
 #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 {
@@ -14,6 +15,43 @@ 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) {
@@ -568,7 +606,7 @@ bool IsValidCodePoint(Isolate* isolate, Handle<Object> value) {
 }
 
 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(
@@ -832,13 +870,124 @@ BUILTIN(StringPrototypeIncludes) {
   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);
+
+  // 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)));
+    }
+  }
 
-  return String::IndexOf(isolate, args.receiver(),
-                         args.atOrUndefined(isolate, 1),
-                         args.atOrUndefined(isolate, 2));
+  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
@@ -862,8 +1011,8 @@ BUILTIN(StringPrototypeLocaleCompare) {
 
   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();