Intrinsify _StringBase._substringMatches to speedup indexOf/startsWith/endsWith under precompilatio…

runtime/vm/intrinsifier_x64.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/globals.h"  // Needed here to get TARGET_ARCH_X64.
 #if defined(TARGET_ARCH_X64)
 
 #include "vm/intrinsifier.h"
 
 #include "vm/assembler.h"
@@ skipping 1577 matching lines @@
   __ j(NOT_EQUAL, &fall_through, Assembler::kNearJump);
   ASSERT(kSmiTagShift == 1);
   __ movzxw(RAX, FieldAddress(RAX, RCX, TIMES_1, OneByteString::data_offset()));
   __ SmiTag(RAX);
   __ ret();
 
   __ Bind(&fall_through);
 }
 
 
+void GenerateSubstringMatchesSpecialization(Assembler* assembler,
+                                            intptr_t receiver_cid,
+                                            intptr_t other_cid,
+                                            Label* return_true,
+                                            Label* return_false) {
+  __ movq(R8, FieldAddress(RAX, String::length_offset()));
+  __ movq(R9, FieldAddress(RCX, String::length_offset()));
+
+  // if (other.length == 0) return true;
+  __ cmpq(R9, Immediate(Smi::Value(0)));

[Florian Schneider, 2015/11/18 10:26:03]

testq(R9, R9)

[rmacnak, 2015/11/18 22:33:32]

Done.

+  __ j(EQUAL, return_true);
+
+  // if (start < 0) return false;
+  __ cmpq(RBX, Immediate(Smi::Value(0)));

[Florian Schneider, 2015/11/18 10:26:03]

alternative - I saw gcc doing this:

__ testq(RBX, RBX);
__ j(SIGN, return false);

[rmacnak, 2015/11/18 22:33:32]

Neat.

+  __ j(LESS, return_false);
+
+  // if (start + other.length > this.length) return false;
+  __ movq(R11, RBX);
+  __ addq(R11, R9);
+  __ cmpq(R11, R8);
+  __ j(GREATER, return_false);
+
+  __ SmiUntag(RBX);  // start
+  __ SmiUntag(R9);   // other.length
+  __ movq(R11, Immediate(0));  // i = 0
+
+  // while (i < len)
+  Label loop;

[Florian Schneider, 2015/11/18 10:26:03]

Applies to all archs:

Maybe you can move the condition to the end of the loop and branch to to the
condition from here to save one branch per iteration?

Label cond;
__ jmp(&cond);
__ Bind(&loop);

[rmacnak, 2015/11/18 22:33:32]

We can even drop the first check as it is handled by the earlier bailout of
other.length == 0.

+  __ Bind(&loop);
+  __ cmpq(R11, R9);
+  __ j(GREATER_EQUAL, return_true);
+
+  // this.codeUnitAt(i + start)
+  // clobbering this.length
+  __ movq(R8, R11);
+  __ addq(R8, RBX);
+  if (receiver_cid == kOneByteStringCid) {
+    __ movzxb(R12,
+              FieldAddress(RAX, R8, TIMES_1, OneByteString::data_offset()));
+  } else {
+    ASSERT(receiver_cid == kTwoByteStringCid);
+    __ movzxw(R12,
+              FieldAddress(RAX, R8, TIMES_2, TwoByteString::data_offset()));
+  }
+  // other.codeUnitAt(i)
+  if (other_cid == kOneByteStringCid) {
+    __ movzxb(R13,
+              FieldAddress(RCX, R11, TIMES_1, OneByteString::data_offset()));
+  } else {
+    ASSERT(other_cid == kTwoByteStringCid);
+    __ movzxw(R13,
+              FieldAddress(RCX, R11, TIMES_2, TwoByteString::data_offset()));
+  }
+  __ cmpq(R12, R13);
+  __ j(NOT_EQUAL, return_false);
+
+  // i++;
+  __ addq(R11, Immediate(1));

[Florian Schneider, 2015/11/18 10:26:03]

Move condition to here:

__ Bind(&cond);
__ cmpq(R11, R9);
__ j(LESS, &loop);
__ jmp(&return_true);

[rmacnak, 2015/11/18 22:33:32]

Done.

+  __ jmp(&loop, Assembler::kNearJump);
+}
+
+
+// bool _substringMatches(int start, String other)
+void Intrinsifier::StringBaseSubstringMatches(Assembler* assembler) {
+  Label fall_through, return_true, return_false, try_two_byte;
+  __ movq(RAX, Address(RSP, + 3 * kWordSize));  // receiver
+  __ movq(RBX, Address(RSP, + 2 * kWordSize));  // start
+  __ movq(RCX, Address(RSP, + 1 * kWordSize));  // other
+
+  __ testq(RBX, Immediate(kSmiTagMask));
+  __ j(NOT_ZERO, &fall_through);  // Non-smi index.
+
+  __ CompareClassId(RCX, kOneByteStringCid);
+  __ j(NOT_EQUAL, &fall_through);
+
+  __ CompareClassId(RAX, kOneByteStringCid);
+  __ j(NOT_EQUAL, &try_two_byte);
+
+  GenerateSubstringMatchesSpecialization(assembler,
+                                         kOneByteStringCid,
+                                         kOneByteStringCid,
+                                         &return_true,
+                                         &return_false);
+
+  __ Bind(&try_two_byte);
+  __ CompareClassId(RAX, kTwoByteStringCid);
+  __ j(NOT_EQUAL, &fall_through);
+
+  GenerateSubstringMatchesSpecialization(assembler,
+                                         kTwoByteStringCid,
+                                         kOneByteStringCid,
+                                         &return_true,
+                                         &return_false);
+
+  __ Bind(&return_true);
+  __ LoadObject(RAX, Bool::True());
+  __ ret();
+
+  __ Bind(&return_false);
+  __ LoadObject(RAX, Bool::False());
+  __ ret();
+
+  __ Bind(&fall_through);
+}
+
+
 void Intrinsifier::StringBaseCharAt(Assembler* assembler) {
   Label fall_through, try_two_byte_string;
   __ movq(RCX, Address(RSP, + 1 * kWordSize));  // Index.
   __ movq(RAX, Address(RSP, + 2 * kWordSize));  // String.
   __ testq(RCX, Immediate(kSmiTagMask));
   __ j(NOT_ZERO, &fall_through);  // Non-smi index.
   // Range check.
   __ cmpq(RCX, FieldAddress(RAX, String::length_offset()));
   // Runtime throws exception.
   __ j(ABOVE_EQUAL, &fall_through);
@@ skipping 391 matching lines @@
   __ LoadIsolate(RAX);
   __ movq(RAX, Address(RAX, Isolate::current_tag_offset()));
   __ ret();
 }
 
 #undef __
 
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_X64