From 8ab7bd6c8b10ad58758c33a1dc9326212bd200e9 Mon Sep 17 00:00:00 2001 From: agicsaki Date: Mon, 27 Jul 2015 10:25:10 -0700 Subject: [PATCH] Optimizing String.Equals as an intrinsic (x86) The third implementation of String.Equals. I added an intrinsic in x86 which is similar to the original java implementation of String.equals: an instanceof check, null check, length check, and reference equality check followed by a loop comparing strings character by character. Interesting Benchmarking Values: Optimizing Compiler on Nexus Player Intrinsic 15-30 Character Strings: 177 ns Original 15-30 Character Strings: 275 ns Intrinsic Null Argument: 59 ns Original Null Argument: 137 ns Intrinsic 100-1000 Character Strings: 1812 ns Original 100-1000 Character Strings: 6334 ns Bug: 21481923 Change-Id: Ia386e19b9dbfe0dac688b20ec93d8f90f67af47e --- compiler/dex/quick/dex_file_method_inliner.cc | 9 +++ compiler/dex/quick/dex_file_method_inliner.h | 2 + compiler/optimizing/intrinsics.cc | 2 + compiler/optimizing/intrinsics_arm.cc | 1 + compiler/optimizing/intrinsics_arm64.cc | 1 + compiler/optimizing/intrinsics_list.h | 1 + compiler/optimizing/intrinsics_x86.cc | 91 +++++++++++++++++++++++++++ compiler/optimizing/intrinsics_x86_64.cc | 1 + runtime/quick/inline_method_analyser.h | 1 + 9 files changed, 109 insertions(+) diff --git a/compiler/dex/quick/dex_file_method_inliner.cc b/compiler/dex/quick/dex_file_method_inliner.cc index 2568ee306..b83d132d4 100644 --- a/compiler/dex/quick/dex_file_method_inliner.cc +++ b/compiler/dex/quick/dex_file_method_inliner.cc @@ -56,6 +56,7 @@ static constexpr bool kIntrinsicIsStatic[] = { false, // kIntrinsicCharAt false, // kIntrinsicCompareTo false, // kIntrinsicGetCharsNoCheck + false, // kIntrinsicEquals false, // kIntrinsicIsEmptyOrLength false, // kIntrinsicIndexOf true, // kIntrinsicNewStringFromBytes @@ -92,6 +93,7 @@ static_assert(kIntrinsicIsStatic[kIntrinsicRoundDouble], "RoundDouble must be st static_assert(!kIntrinsicIsStatic[kIntrinsicReferenceGetReferent], "Get must not be static"); static_assert(!kIntrinsicIsStatic[kIntrinsicCharAt], "CharAt must not be static"); static_assert(!kIntrinsicIsStatic[kIntrinsicCompareTo], "CompareTo must not be static"); +static_assert(!kIntrinsicIsStatic[kIntrinsicEquals], "Equals must not be static"); static_assert(!kIntrinsicIsStatic[kIntrinsicGetCharsNoCheck], "GetCharsNoCheck must not be static"); static_assert(!kIntrinsicIsStatic[kIntrinsicIsEmptyOrLength], "IsEmptyOrLength must not be static"); static_assert(!kIntrinsicIsStatic[kIntrinsicIndexOf], "IndexOf must not be static"); @@ -189,6 +191,7 @@ const char* const DexFileMethodInliner::kNameCacheNames[] = { "getReferent", // kNameCacheReferenceGet "charAt", // kNameCacheCharAt "compareTo", // kNameCacheCompareTo + "equals", // kNameCacheEquals "getCharsNoCheck", // kNameCacheGetCharsNoCheck "isEmpty", // kNameCacheIsEmpty "indexOf", // kNameCacheIndexOf @@ -280,6 +283,8 @@ const DexFileMethodInliner::ProtoDef DexFileMethodInliner::kProtoCacheDefs[] = { { kClassCacheVoid, 2, { kClassCacheLong, kClassCacheLong } }, // kProtoCacheJS_V { kClassCacheVoid, 2, { kClassCacheLong, kClassCacheShort } }, + // kProtoCacheObject_Z + { kClassCacheBoolean, 1, { kClassCacheJavaLangObject } }, // kProtoCacheObjectJII_Z { kClassCacheBoolean, 4, { kClassCacheJavaLangObject, kClassCacheLong, kClassCacheInt, kClassCacheInt } }, @@ -411,6 +416,7 @@ const DexFileMethodInliner::IntrinsicDef DexFileMethodInliner::kIntrinsicMethods INTRINSIC(JavaLangString, CharAt, I_C, kIntrinsicCharAt, 0), INTRINSIC(JavaLangString, CompareTo, String_I, kIntrinsicCompareTo, 0), + INTRINSIC(JavaLangString, Equals, Object_Z, kIntrinsicEquals, 0), INTRINSIC(JavaLangString, GetCharsNoCheck, IICharArrayI_V, kIntrinsicGetCharsNoCheck, 0), INTRINSIC(JavaLangString, IsEmpty, _Z, kIntrinsicIsEmptyOrLength, kIntrinsicFlagIsEmpty), INTRINSIC(JavaLangString, IndexOf, II_I, kIntrinsicIndexOf, kIntrinsicFlagNone), @@ -581,6 +587,9 @@ bool DexFileMethodInliner::GenIntrinsic(Mir2Lir* backend, CallInfo* info) { return backend->GenInlinedCharAt(info); case kIntrinsicCompareTo: return backend->GenInlinedStringCompareTo(info); + case kIntrinsicEquals: + // Quick does not implement this intrinsic. + return false; case kIntrinsicGetCharsNoCheck: return backend->GenInlinedStringGetCharsNoCheck(info); case kIntrinsicIsEmptyOrLength: diff --git a/compiler/dex/quick/dex_file_method_inliner.h b/compiler/dex/quick/dex_file_method_inliner.h index a8cb9f0c3..0969ff8b2 100644 --- a/compiler/dex/quick/dex_file_method_inliner.h +++ b/compiler/dex/quick/dex_file_method_inliner.h @@ -170,6 +170,7 @@ class DexFileMethodInliner { kNameCacheReferenceGetReferent, kNameCacheCharAt, kNameCacheCompareTo, + kNameCacheEquals, kNameCacheGetCharsNoCheck, kNameCacheIsEmpty, kNameCacheIndexOf, @@ -242,6 +243,7 @@ class DexFileMethodInliner { kProtoCacheJJ_J, kProtoCacheJJ_V, kProtoCacheJS_V, + kProtoCacheObject_Z, kProtoCacheObjectJII_Z, kProtoCacheObjectJJJ_Z, kProtoCacheObjectJObjectObject_Z, diff --git a/compiler/optimizing/intrinsics.cc b/compiler/optimizing/intrinsics.cc index 8ef13e125..129ffd83c 100644 --- a/compiler/optimizing/intrinsics.cc +++ b/compiler/optimizing/intrinsics.cc @@ -187,6 +187,8 @@ static Intrinsics GetIntrinsic(InlineMethod method) { return Intrinsics::kStringCharAt; case kIntrinsicCompareTo: return Intrinsics::kStringCompareTo; + case kIntrinsicEquals: + return Intrinsics::kStringEquals; case kIntrinsicGetCharsNoCheck: return Intrinsics::kStringGetCharsNoCheck; case kIntrinsicIsEmptyOrLength: diff --git a/compiler/optimizing/intrinsics_arm.cc b/compiler/optimizing/intrinsics_arm.cc index b4dbf75f0..3f157c6e3 100644 --- a/compiler/optimizing/intrinsics_arm.cc +++ b/compiler/optimizing/intrinsics_arm.cc @@ -1068,6 +1068,7 @@ UNIMPLEMENTED_INTRINSIC(UnsafeCASLong) // High register pressure. UNIMPLEMENTED_INTRINSIC(SystemArrayCopyChar) UNIMPLEMENTED_INTRINSIC(ReferenceGetReferent) UNIMPLEMENTED_INTRINSIC(StringGetCharsNoCheck) +UNIMPLEMENTED_INTRINSIC(StringEquals) #undef UNIMPLEMENTED_INTRINSIC diff --git a/compiler/optimizing/intrinsics_arm64.cc b/compiler/optimizing/intrinsics_arm64.cc index 78ac167a8..aeae5764a 100644 --- a/compiler/optimizing/intrinsics_arm64.cc +++ b/compiler/optimizing/intrinsics_arm64.cc @@ -1202,6 +1202,7 @@ void IntrinsicCodeGeneratorARM64::Visit ## Name(HInvoke* invoke ATTRIBUTE_UNUSED UNIMPLEMENTED_INTRINSIC(SystemArrayCopyChar) UNIMPLEMENTED_INTRINSIC(ReferenceGetReferent) UNIMPLEMENTED_INTRINSIC(StringGetCharsNoCheck) +UNIMPLEMENTED_INTRINSIC(StringEquals) #undef UNIMPLEMENTED_INTRINSIC diff --git a/compiler/optimizing/intrinsics_list.h b/compiler/optimizing/intrinsics_list.h index 2c9248f52..6e6f17328 100644 --- a/compiler/optimizing/intrinsics_list.h +++ b/compiler/optimizing/intrinsics_list.h @@ -60,6 +60,7 @@ V(MemoryPokeShortNative, kStatic) \ V(StringCharAt, kDirect) \ V(StringCompareTo, kDirect) \ + V(StringEquals, kDirect) \ V(StringGetCharsNoCheck, kDirect) \ V(StringIndexOf, kDirect) \ V(StringIndexOfAfter, kDirect) \ diff --git a/compiler/optimizing/intrinsics_x86.cc b/compiler/optimizing/intrinsics_x86.cc index 0d6ca09f3..6399ee80b 100644 --- a/compiler/optimizing/intrinsics_x86.cc +++ b/compiler/optimizing/intrinsics_x86.cc @@ -945,6 +945,97 @@ void IntrinsicCodeGeneratorX86::VisitStringCompareTo(HInvoke* invoke) { __ Bind(slow_path->GetExitLabel()); } +void IntrinsicLocationsBuilderX86::VisitStringEquals(HInvoke* invoke) { + LocationSummary* locations = new (arena_) LocationSummary(invoke, + LocationSummary::kNoCall, + kIntrinsified); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + + // Request temporary registers, ECX and EDI needed for repe_cmpsw instruction. + locations->AddTemp(Location::RegisterLocation(ECX)); + locations->AddTemp(Location::RegisterLocation(EDI)); + + // Set output, ESI needed for repe_cmpsw instruction anyways. + locations->SetOut(Location::RegisterLocation(ESI)); +} + +void IntrinsicCodeGeneratorX86::VisitStringEquals(HInvoke* invoke) { + X86Assembler* assembler = GetAssembler(); + LocationSummary* locations = invoke->GetLocations(); + + Register str = locations->InAt(0).AsRegister(); + Register arg = locations->InAt(1).AsRegister(); + Register ecx = locations->GetTemp(0).AsRegister(); + Register edi = locations->GetTemp(1).AsRegister(); + Register esi = locations->Out().AsRegister(); + + Label end; + Label return_true; + Label return_false; + + // Get offsets of count, value, and class fields within a string object. + const uint32_t count_offset = mirror::String::CountOffset().Uint32Value(); + const uint32_t value_offset = mirror::String::ValueOffset().Uint32Value(); + const uint32_t class_offset = mirror::Object::ClassOffset().Uint32Value(); + + // Note that the null check must have been done earlier. + DCHECK(!invoke->CanDoImplicitNullCheckOn(invoke->InputAt(0))); + + // Check if input is null, return false if it is. + __ cmpl(arg, Immediate(0)); + __ j(kEqual, &return_false); + + // Instanceof check for the argument by comparing class fields. + // All string objects must have the same type since String cannot be subclassed. + // Receiver must be a string object, so its class field is equal to all strings' class fields. + // If the argument is a string object, its class field must be equal to receiver's class field. + __ movl(ecx, Address(str, class_offset)); + __ cmpl(ecx, Address(arg, class_offset)); + __ j(kNotEqual, &return_false); + + // Reference equality check, return true if same reference. + __ cmpl(str, arg); + __ j(kEqual, &return_true); + + // Load length of receiver string. + __ movl(ecx, Address(str, count_offset)); + // Check if lengths are equal, return false if they're not. + __ cmpl(ecx, Address(arg, count_offset)); + __ j(kNotEqual, &return_false); + // Return true if both strings are empty. + __ cmpl(ecx, Immediate(0)); + __ j(kEqual, &return_true); + + // Load starting addresses of string values into ESI/EDI as required for repe_cmpsw instruction. + __ leal(esi, Address(str, value_offset)); + __ leal(edi, Address(arg, value_offset)); + + // Divide string length by 2 to compare characters 2 at a time and adjust for odd lengths. + __ addl(ecx, Immediate(1)); + __ shrl(ecx, Immediate(1)); + + // Assertions that must hold in order to compare strings 2 characters at a time. + DCHECK_ALIGNED(value_offset, 4); + static_assert(IsAligned<4>(kObjectAlignment), "String of odd length is not zero padded"); + + // Loop to compare strings two characters at a time starting at the beginning of the string. + __ repe_cmpsl(); + // If strings are not equal, zero flag will be cleared. + __ j(kNotEqual, &return_false); + + // Return true and exit the function. + // If loop does not result in returning false, we return true. + __ Bind(&return_true); + __ movl(esi, Immediate(1)); + __ jmp(&end); + + // Return false and exit the function. + __ Bind(&return_false); + __ movl(esi, Immediate(0)); + __ Bind(&end); +} + static void CreateStringIndexOfLocations(HInvoke* invoke, ArenaAllocator* allocator, bool start_at_zero) { diff --git a/compiler/optimizing/intrinsics_x86_64.cc b/compiler/optimizing/intrinsics_x86_64.cc index ea342e938..6e737d6d3 100644 --- a/compiler/optimizing/intrinsics_x86_64.cc +++ b/compiler/optimizing/intrinsics_x86_64.cc @@ -1615,6 +1615,7 @@ void IntrinsicCodeGeneratorX86_64::Visit ## Name(HInvoke* invoke ATTRIBUTE_UNUSE UNIMPLEMENTED_INTRINSIC(StringGetCharsNoCheck) UNIMPLEMENTED_INTRINSIC(SystemArrayCopyChar) UNIMPLEMENTED_INTRINSIC(ReferenceGetReferent) +UNIMPLEMENTED_INTRINSIC(StringEquals) #undef UNIMPLEMENTED_INTRINSIC diff --git a/runtime/quick/inline_method_analyser.h b/runtime/quick/inline_method_analyser.h index 65bbcbebe..79c50e863 100644 --- a/runtime/quick/inline_method_analyser.h +++ b/runtime/quick/inline_method_analyser.h @@ -56,6 +56,7 @@ enum InlineMethodOpcode : uint16_t { kIntrinsicReferenceGetReferent, kIntrinsicCharAt, kIntrinsicCompareTo, + kIntrinsicEquals, // String equals kIntrinsicGetCharsNoCheck, kIntrinsicIsEmptyOrLength, kIntrinsicIndexOf, -- 2.11.0