diff options
33 files changed, 1215 insertions, 3 deletions
diff --git a/benchmark/stringbuilder-append/info.txt b/benchmark/stringbuilder-append/info.txt new file mode 100644 index 0000000000..ae588123d1 --- /dev/null +++ b/benchmark/stringbuilder-append/info.txt @@ -0,0 +1 @@ +Benchmarks for the StringBuilder append pattern. diff --git a/benchmark/stringbuilder-append/src/StringBuilderAppendBenchmark.java b/benchmark/stringbuilder-append/src/StringBuilderAppendBenchmark.java new file mode 100644 index 0000000000..1550e81bf7 --- /dev/null +++ b/benchmark/stringbuilder-append/src/StringBuilderAppendBenchmark.java @@ -0,0 +1,62 @@ +/* + * Copyright (C) 2019 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +public class StringBuilderAppendBenchmark { + public static String string1 = "s1"; + public static String string2 = "s2"; + public static String longString1 = "This is a long string 1"; + public static String longString2 = "This is a long string 2"; + public static int int1 = 42; + + public void timeAppendStrings(int count) { + String s1 = string1; + String s2 = string2; + int sum = 0; + for (int i = 0; i < count; ++i) { + String result = s1 + s2; + sum += result.length(); // Make sure the append is not optimized away. + } + if (sum != count * (s1.length() + s2.length())) { + throw new AssertionError(); + } + } + + public void timeAppendLongStrings(int count) { + String s1 = longString1; + String s2 = longString2; + int sum = 0; + for (int i = 0; i < count; ++i) { + String result = s1 + s2; + sum += result.length(); // Make sure the append is not optimized away. + } + if (sum != count * (s1.length() + s2.length())) { + throw new AssertionError(); + } + } + + public void timeAppendStringAndInt(int count) { + String s1 = string1; + int i1 = int1; + int sum = 0; + for (int i = 0; i < count; ++i) { + String result = s1 + i1; + sum += result.length(); // Make sure the append is not optimized away. + } + if (sum != count * (s1.length() + Integer.toString(i1).length())) { + throw new AssertionError(); + } + } +} diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc index 2bbb570c8d..3b5699bccd 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -64,6 +64,7 @@ #include "ssa_liveness_analysis.h" #include "stack_map.h" #include "stack_map_stream.h" +#include "string_builder_append.h" #include "thread-current-inl.h" #include "utils/assembler.h" @@ -599,6 +600,57 @@ void CodeGenerator::GenerateInvokeCustomCall(HInvokeCustom* invoke) { InvokeRuntime(entrypoint, invoke, invoke->GetDexPc(), nullptr); } +void CodeGenerator::CreateStringBuilderAppendLocations(HStringBuilderAppend* instruction, + Location out) { + ArenaAllocator* allocator = GetGraph()->GetAllocator(); + LocationSummary* locations = + new (allocator) LocationSummary(instruction, LocationSummary::kCallOnMainOnly); + locations->SetOut(out); + instruction->GetLocations()->SetInAt(instruction->FormatIndex(), + Location::ConstantLocation(instruction->GetFormat())); + + uint32_t format = static_cast<uint32_t>(instruction->GetFormat()->GetValue()); + uint32_t f = format; + PointerSize pointer_size = InstructionSetPointerSize(GetInstructionSet()); + size_t stack_offset = static_cast<size_t>(pointer_size); // Start after the ArtMethod*. + for (size_t i = 0, num_args = instruction->GetNumberOfArguments(); i != num_args; ++i) { + StringBuilderAppend::Argument arg_type = + static_cast<StringBuilderAppend::Argument>(f & StringBuilderAppend::kArgMask); + switch (arg_type) { + case StringBuilderAppend::Argument::kStringBuilder: + case StringBuilderAppend::Argument::kString: + case StringBuilderAppend::Argument::kCharArray: + static_assert(sizeof(StackReference<mirror::Object>) == sizeof(uint32_t), "Size check."); + FALLTHROUGH_INTENDED; + case StringBuilderAppend::Argument::kBoolean: + case StringBuilderAppend::Argument::kChar: + case StringBuilderAppend::Argument::kInt: + case StringBuilderAppend::Argument::kFloat: + locations->SetInAt(i, Location::StackSlot(stack_offset)); + break; + case StringBuilderAppend::Argument::kLong: + case StringBuilderAppend::Argument::kDouble: + stack_offset = RoundUp(stack_offset, sizeof(uint64_t)); + locations->SetInAt(i, Location::DoubleStackSlot(stack_offset)); + // Skip the low word, let the common code skip the high word. + stack_offset += sizeof(uint32_t); + break; + default: + LOG(FATAL) << "Unexpected arg format: 0x" << std::hex + << (f & StringBuilderAppend::kArgMask) << " full format: 0x" << format; + UNREACHABLE(); + } + f >>= StringBuilderAppend::kBitsPerArg; + stack_offset += sizeof(uint32_t); + } + DCHECK_EQ(f, 0u); + + size_t param_size = stack_offset - static_cast<size_t>(pointer_size); + DCHECK_ALIGNED(param_size, kVRegSize); + size_t num_vregs = param_size / kVRegSize; + graph_->UpdateMaximumNumberOfOutVRegs(num_vregs); +} + void CodeGenerator::CreateUnresolvedFieldLocationSummary( HInstruction* field_access, DataType::Type field_type, diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h index f70ecb612d..357c4bb606 100644 --- a/compiler/optimizing/code_generator.h +++ b/compiler/optimizing/code_generator.h @@ -546,6 +546,8 @@ class CodeGenerator : public DeletableArenaObject<kArenaAllocCodeGenerator> { void GenerateInvokeCustomCall(HInvokeCustom* invoke); + void CreateStringBuilderAppendLocations(HStringBuilderAppend* instruction, Location out); + void CreateUnresolvedFieldLocationSummary( HInstruction* field_access, DataType::Type field_type, diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index 3086882678..28a7583845 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -5411,6 +5411,15 @@ void InstructionCodeGeneratorARM64::VisitStaticFieldSet(HStaticFieldSet* instruc HandleFieldSet(instruction, instruction->GetFieldInfo(), instruction->GetValueCanBeNull()); } +void LocationsBuilderARM64::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + codegen_->CreateStringBuilderAppendLocations(instruction, LocationFrom(x0)); +} + +void InstructionCodeGeneratorARM64::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + __ Mov(w0, instruction->GetFormat()->GetValue()); + codegen_->InvokeRuntime(kQuickStringBuilderAppend, instruction, instruction->GetDexPc()); +} + void LocationsBuilderARM64::VisitUnresolvedInstanceFieldGet( HUnresolvedInstanceFieldGet* instruction) { FieldAccessCallingConventionARM64 calling_convention; diff --git a/compiler/optimizing/code_generator_arm_vixl.cc b/compiler/optimizing/code_generator_arm_vixl.cc index 6469c6964a..7adfe5d71d 100644 --- a/compiler/optimizing/code_generator_arm_vixl.cc +++ b/compiler/optimizing/code_generator_arm_vixl.cc @@ -5722,6 +5722,15 @@ void InstructionCodeGeneratorARMVIXL::VisitStaticFieldSet(HStaticFieldSet* instr HandleFieldSet(instruction, instruction->GetFieldInfo(), instruction->GetValueCanBeNull()); } +void LocationsBuilderARMVIXL::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + codegen_->CreateStringBuilderAppendLocations(instruction, LocationFrom(r0)); +} + +void InstructionCodeGeneratorARMVIXL::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + __ Mov(r0, instruction->GetFormat()->GetValue()); + codegen_->InvokeRuntime(kQuickStringBuilderAppend, instruction, instruction->GetDexPc()); +} + void LocationsBuilderARMVIXL::VisitUnresolvedInstanceFieldGet( HUnresolvedInstanceFieldGet* instruction) { FieldAccessCallingConventionARMVIXL calling_convention; diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc index 72334afa40..b3bce78940 100644 --- a/compiler/optimizing/code_generator_mips.cc +++ b/compiler/optimizing/code_generator_mips.cc @@ -9529,6 +9529,15 @@ void InstructionCodeGeneratorMIPS::VisitStaticFieldSet(HStaticFieldSet* instruct instruction->GetValueCanBeNull()); } +void LocationsBuilderMIPS::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + codegen_->CreateStringBuilderAppendLocations(instruction, Location::RegisterLocation(V0)); +} + +void InstructionCodeGeneratorMIPS::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + __ LoadConst32(A0, instruction->GetFormat()->GetValue()); + codegen_->InvokeRuntime(kQuickStringBuilderAppend, instruction, instruction->GetDexPc()); +} + void LocationsBuilderMIPS::VisitUnresolvedInstanceFieldGet( HUnresolvedInstanceFieldGet* instruction) { FieldAccessCallingConventionMIPS calling_convention; diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc index 0d3cb3b8ca..0a3a3fa156 100644 --- a/compiler/optimizing/code_generator_mips64.cc +++ b/compiler/optimizing/code_generator_mips64.cc @@ -7148,6 +7148,15 @@ void InstructionCodeGeneratorMIPS64::VisitStaticFieldSet(HStaticFieldSet* instru HandleFieldSet(instruction, instruction->GetFieldInfo(), instruction->GetValueCanBeNull()); } +void LocationsBuilderMIPS64::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + codegen_->CreateStringBuilderAppendLocations(instruction, Location::RegisterLocation(V0)); +} + +void InstructionCodeGeneratorMIPS64::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + __ LoadConst32(A0, instruction->GetFormat()->GetValue()); + codegen_->InvokeRuntime(kQuickStringBuilderAppend, instruction, instruction->GetDexPc()); +} + void LocationsBuilderMIPS64::VisitUnresolvedInstanceFieldGet( HUnresolvedInstanceFieldGet* instruction) { FieldAccessCallingConventionMIPS64 calling_convention; diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index ca1723bfd2..7a73569ea5 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -5510,6 +5510,15 @@ void InstructionCodeGeneratorX86::VisitInstanceFieldGet(HInstanceFieldGet* instr HandleFieldGet(instruction, instruction->GetFieldInfo()); } +void LocationsBuilderX86::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + codegen_->CreateStringBuilderAppendLocations(instruction, Location::RegisterLocation(EAX)); +} + +void InstructionCodeGeneratorX86::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + __ movl(EAX, Immediate(instruction->GetFormat()->GetValue())); + codegen_->InvokeRuntime(kQuickStringBuilderAppend, instruction, instruction->GetDexPc()); +} + void LocationsBuilderX86::VisitUnresolvedInstanceFieldGet( HUnresolvedInstanceFieldGet* instruction) { FieldAccessCallingConventionX86 calling_convention; diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 7c293b8605..ee2ef77850 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -4882,6 +4882,15 @@ void InstructionCodeGeneratorX86_64::VisitStaticFieldSet(HStaticFieldSet* instru HandleFieldSet(instruction, instruction->GetFieldInfo(), instruction->GetValueCanBeNull()); } +void LocationsBuilderX86_64::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + codegen_->CreateStringBuilderAppendLocations(instruction, Location::RegisterLocation(RAX)); +} + +void InstructionCodeGeneratorX86_64::VisitStringBuilderAppend(HStringBuilderAppend* instruction) { + __ movl(CpuRegister(RDI), Immediate(instruction->GetFormat()->GetValue())); + codegen_->InvokeRuntime(kQuickStringBuilderAppend, instruction, instruction->GetDexPc()); +} + void LocationsBuilderX86_64::VisitUnresolvedInstanceFieldGet( HUnresolvedInstanceFieldGet* instruction) { FieldAccessCallingConventionX86_64 calling_convention; diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index e829576479..9cc5cad55a 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -25,6 +25,7 @@ #include "mirror/class-inl.h" #include "scoped_thread_state_change-inl.h" #include "sharpening.h" +#include "string_builder_append.h" namespace art { @@ -2479,6 +2480,186 @@ static bool NoEscapeForStringBufferReference(HInstruction* reference, HInstructi return false; } +static bool TryReplaceStringBuilderAppend(HInvoke* invoke) { + DCHECK_EQ(invoke->GetIntrinsic(), Intrinsics::kStringBuilderToString); + if (invoke->CanThrowIntoCatchBlock()) { + return false; + } + + HBasicBlock* block = invoke->GetBlock(); + HInstruction* sb = invoke->InputAt(0); + + // We support only a new StringBuilder, otherwise we cannot ensure that + // the StringBuilder data does not need to be populated for other users. + if (!sb->IsNewInstance()) { + return false; + } + + // For now, we support only single-block recognition. + // (Ternary operators feeding the append could be implemented.) + for (const HUseListNode<HInstruction*>& use : sb->GetUses()) { + if (use.GetUser()->GetBlock() != block) { + return false; + } + } + + // Collect args and check for unexpected uses. + // We expect one call to a constructor with no arguments, one constructor fence (unless + // eliminated), some number of append calls and one call to StringBuilder.toString(). + bool seen_constructor = false; + bool seen_constructor_fence = false; + bool seen_to_string = false; + uint32_t format = 0u; + uint32_t num_args = 0u; + HInstruction* args[StringBuilderAppend::kMaxArgs]; // Added in reverse order. + for (const HUseListNode<HInstruction*>& use : sb->GetUses()) { + // The append pattern uses the StringBuilder only as the first argument. + if (use.GetIndex() != 0u) { + return false; + } + // We see the uses in reverse order because they are inserted at the front + // of the singly-linked list, so the StringBuilder.append() must come first. + HInstruction* user = use.GetUser(); + if (!seen_to_string) { + if (user->IsInvokeVirtual() && + user->AsInvokeVirtual()->GetIntrinsic() == Intrinsics::kStringBuilderToString) { + seen_to_string = true; + continue; + } else { + return false; + } + } + // Then we should see the arguments. + if (user->IsInvokeVirtual()) { + HInvokeVirtual* as_invoke_virtual = user->AsInvokeVirtual(); + DCHECK(!seen_constructor); + DCHECK(!seen_constructor_fence); + StringBuilderAppend::Argument arg; + switch (as_invoke_virtual->GetIntrinsic()) { + case Intrinsics::kStringBuilderAppendObject: + // TODO: Unimplemented, needs to call String.valueOf(). + return false; + case Intrinsics::kStringBuilderAppendString: + arg = StringBuilderAppend::Argument::kString; + break; + case Intrinsics::kStringBuilderAppendCharArray: + // TODO: Unimplemented, StringBuilder.append(char[]) can throw NPE and we would + // not have the correct stack trace for it. + return false; + case Intrinsics::kStringBuilderAppendBoolean: + arg = StringBuilderAppend::Argument::kBoolean; + break; + case Intrinsics::kStringBuilderAppendChar: + arg = StringBuilderAppend::Argument::kChar; + break; + case Intrinsics::kStringBuilderAppendInt: + arg = StringBuilderAppend::Argument::kInt; + break; + case Intrinsics::kStringBuilderAppendLong: + arg = StringBuilderAppend::Argument::kLong; + break; + case Intrinsics::kStringBuilderAppendCharSequence: { + ReferenceTypeInfo rti = user->AsInvokeVirtual()->InputAt(1)->GetReferenceTypeInfo(); + if (!rti.IsValid()) { + return false; + } + ScopedObjectAccess soa(Thread::Current()); + Handle<mirror::Class> input_type = rti.GetTypeHandle(); + DCHECK(input_type != nullptr); + if (input_type.Get() == GetClassRoot<mirror::String>()) { + arg = StringBuilderAppend::Argument::kString; + } else { + // TODO: Check and implement for StringBuilder. We could find the StringBuilder's + // internal char[] inconsistent with the length, or the string compression + // of the result could be compromised with a concurrent modification, and + // we would need to throw appropriate exceptions. + return false; + } + break; + } + case Intrinsics::kStringBuilderAppendFloat: + case Intrinsics::kStringBuilderAppendDouble: + // TODO: Unimplemented, needs to call FloatingDecimal.getBinaryToASCIIConverter(). + return false; + default: { + return false; + } + } + // Uses of the append return value should have been replaced with the first input. + DCHECK(!as_invoke_virtual->HasUses()); + DCHECK(!as_invoke_virtual->HasEnvironmentUses()); + if (num_args == StringBuilderAppend::kMaxArgs) { + return false; + } + format = (format << StringBuilderAppend::kBitsPerArg) | static_cast<uint32_t>(arg); + args[num_args] = as_invoke_virtual->InputAt(1u); + ++num_args; + } else if (user->IsInvokeStaticOrDirect() && + user->AsInvokeStaticOrDirect()->GetResolvedMethod() != nullptr && + user->AsInvokeStaticOrDirect()->GetResolvedMethod()->IsConstructor() && + user->AsInvokeStaticOrDirect()->GetNumberOfArguments() == 1u) { + // After arguments, we should see the constructor. + // We accept only the constructor with no extra arguments. + DCHECK(!seen_constructor); + DCHECK(!seen_constructor_fence); + seen_constructor = true; + } else if (user->IsConstructorFence()) { + // The last use we see is the constructor fence. + DCHECK(seen_constructor); + DCHECK(!seen_constructor_fence); + seen_constructor_fence = true; + } else { + return false; + } + } + + if (num_args == 0u) { + return false; + } + + // Check environment uses. + for (const HUseListNode<HEnvironment*>& use : sb->GetEnvUses()) { + HInstruction* holder = use.GetUser()->GetHolder(); + if (holder->GetBlock() != block) { + return false; + } + // Accept only calls on the StringBuilder (which shall all be removed). + // TODO: Carve-out for const-string? Or rely on environment pruning (to be implemented)? + if (holder->InputCount() == 0 || holder->InputAt(0) != sb) { + return false; + } + } + + // Create replacement instruction. + HIntConstant* fmt = block->GetGraph()->GetIntConstant(static_cast<int32_t>(format)); + ArenaAllocator* allocator = block->GetGraph()->GetAllocator(); + HStringBuilderAppend* append = + new (allocator) HStringBuilderAppend(fmt, num_args, allocator, invoke->GetDexPc()); + append->SetReferenceTypeInfo(invoke->GetReferenceTypeInfo()); + for (size_t i = 0; i != num_args; ++i) { + append->SetArgumentAt(i, args[num_args - 1u - i]); + } + block->InsertInstructionBefore(append, invoke); + invoke->ReplaceWith(append); + // Copy environment, except for the StringBuilder uses. + for (size_t i = 0, size = invoke->GetEnvironment()->Size(); i != size; ++i) { + if (invoke->GetEnvironment()->GetInstructionAt(i) == sb) { + invoke->GetEnvironment()->RemoveAsUserOfInput(i); + invoke->GetEnvironment()->SetRawEnvAt(i, nullptr); + } + } + append->CopyEnvironmentFrom(invoke->GetEnvironment()); + // Remove the old instruction. + block->RemoveInstruction(invoke); + // Remove the StringBuilder's uses and StringBuilder. + while (sb->HasNonEnvironmentUses()) { + block->RemoveInstruction(sb->GetUses().front().GetUser()); + } + DCHECK(!sb->HasEnvironmentUses()); + block->RemoveInstruction(sb); + return true; +} + // Certain allocation intrinsics are not removed by dead code elimination // because of potentially throwing an OOM exception or other side effects. // This method removes such intrinsics when special circumstances allow. @@ -2493,6 +2674,9 @@ void InstructionSimplifierVisitor::SimplifyAllocationIntrinsic(HInvoke* invoke) invoke->GetBlock()->RemoveInstruction(invoke); RecordSimplification(); } + } else if (invoke->GetIntrinsic() == Intrinsics::kStringBuilderToString && + TryReplaceStringBuilderAppend(invoke)) { + RecordSimplification(); } } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 8a8b371758..cb53ae3ada 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -1438,6 +1438,7 @@ class HLoopInformationOutwardIterator : public ValueObject { M(Shr, BinaryOperation) \ M(StaticFieldGet, Instruction) \ M(StaticFieldSet, Instruction) \ + M(StringBuilderAppend, Instruction) \ M(UnresolvedInstanceFieldGet, Instruction) \ M(UnresolvedInstanceFieldSet, Instruction) \ M(UnresolvedStaticFieldGet, Instruction) \ @@ -6889,6 +6890,55 @@ class HStaticFieldSet final : public HExpression<2> { const FieldInfo field_info_; }; +class HStringBuilderAppend final : public HVariableInputSizeInstruction { + public: + HStringBuilderAppend(HIntConstant* format, + uint32_t number_of_arguments, + ArenaAllocator* allocator, + uint32_t dex_pc) + : HVariableInputSizeInstruction( + kStringBuilderAppend, + DataType::Type::kReference, + // The runtime call may read memory from inputs. It never writes outside + // of the newly allocated result object (or newly allocated helper objects). + SideEffects::AllReads().Union(SideEffects::CanTriggerGC()), + dex_pc, + allocator, + number_of_arguments + /* format */ 1u, + kArenaAllocInvokeInputs) { + DCHECK_GE(number_of_arguments, 1u); // There must be something to append. + SetRawInputAt(FormatIndex(), format); + } + + void SetArgumentAt(size_t index, HInstruction* argument) { + DCHECK_LE(index, GetNumberOfArguments()); + SetRawInputAt(index, argument); + } + + // Return the number of arguments, excluding the format. + size_t GetNumberOfArguments() const { + DCHECK_GE(InputCount(), 1u); + return InputCount() - 1u; + } + + size_t FormatIndex() const { + return GetNumberOfArguments(); + } + + HIntConstant* GetFormat() { + return InputAt(FormatIndex())->AsIntConstant(); + } + + bool NeedsEnvironment() const override { return true; } + + bool CanThrow() const override { return true; } + + DECLARE_INSTRUCTION(StringBuilderAppend); + + protected: + DEFAULT_COPY_CONSTRUCTOR(StringBuilderAppend); +}; + class HUnresolvedInstanceFieldGet final : public HExpression<1> { public: HUnresolvedInstanceFieldGet(HInstruction* obj, diff --git a/dex2oat/linker/oat_writer_test.cc b/dex2oat/linker/oat_writer_test.cc index c46aa18703..2142727dae 100644 --- a/dex2oat/linker/oat_writer_test.cc +++ b/dex2oat/linker/oat_writer_test.cc @@ -469,7 +469,7 @@ TEST_F(OatTest, OatHeaderSizeCheck) { EXPECT_EQ(56U, sizeof(OatHeader)); EXPECT_EQ(4U, sizeof(OatMethodOffsets)); EXPECT_EQ(8U, sizeof(OatQuickMethodHeader)); - EXPECT_EQ(166 * static_cast<size_t>(GetInstructionSetPointerSize(kRuntimeISA)), + EXPECT_EQ(167 * static_cast<size_t>(GetInstructionSetPointerSize(kRuntimeISA)), sizeof(QuickEntryPoints)); } diff --git a/runtime/Android.bp b/runtime/Android.bp index cbaa68f1f8..2325b0d288 100644 --- a/runtime/Android.bp +++ b/runtime/Android.bp @@ -195,6 +195,7 @@ libart_cc_defaults { "signal_catcher.cc", "stack.cc", "stack_map.cc", + "string_builder_append.cc", "thread.cc", "thread_list.cc", "thread_pool.cc", @@ -240,6 +241,7 @@ libart_cc_defaults { "entrypoints/quick/quick_jni_entrypoints.cc", "entrypoints/quick/quick_lock_entrypoints.cc", "entrypoints/quick/quick_math_entrypoints.cc", + "entrypoints/quick/quick_string_builder_append_entrypoints.cc", "entrypoints/quick/quick_thread_entrypoints.cc", "entrypoints/quick/quick_throw_entrypoints.cc", "entrypoints/quick/quick_trampoline_entrypoints.cc", diff --git a/runtime/arch/arm/quick_entrypoints_arm.S b/runtime/arch/arm/quick_entrypoints_arm.S index 3ab6aa8812..ecda78dc07 100644 --- a/runtime/arch/arm/quick_entrypoints_arm.S +++ b/runtime/arch/arm/quick_entrypoints_arm.S @@ -2215,6 +2215,17 @@ ENTRY art_quick_l2f pop {pc} END art_quick_l2f + .extern artStringBuilderAppend +ENTRY art_quick_string_builder_append + SETUP_SAVE_REFS_ONLY_FRAME r2 @ save callee saves in case of GC + add r1, sp, #(FRAME_SIZE_SAVE_REFS_ONLY + __SIZEOF_POINTER__) @ pass args + mov r2, rSELF @ pass Thread::Current + bl artStringBuilderAppend @ (uint32_t, const unit32_t*, Thread*) + RESTORE_SAVE_REFS_ONLY_FRAME + REFRESH_MARKING_REGISTER + RETURN_IF_RESULT_IS_NON_ZERO_OR_DELIVER +END art_quick_string_builder_append + .macro CONDITIONAL_CBZ reg, reg_if, dest .ifc \reg, \reg_if cbz \reg, \dest diff --git a/runtime/arch/arm64/quick_entrypoints_arm64.S b/runtime/arch/arm64/quick_entrypoints_arm64.S index 8b1523859d..1c252a2f3b 100644 --- a/runtime/arch/arm64/quick_entrypoints_arm64.S +++ b/runtime/arch/arm64/quick_entrypoints_arm64.S @@ -2468,6 +2468,17 @@ ENTRY art_quick_indexof #endif END art_quick_indexof + .extern artStringBuilderAppend +ENTRY art_quick_string_builder_append + SETUP_SAVE_REFS_ONLY_FRAME // save callee saves in case of GC + add x1, sp, #(FRAME_SIZE_SAVE_REFS_ONLY + __SIZEOF_POINTER__) // pass args + mov x2, xSELF // pass Thread::Current + bl artStringBuilderAppend // (uint32_t, const unit32_t*, Thread*) + RESTORE_SAVE_REFS_ONLY_FRAME + REFRESH_MARKING_REGISTER + RETURN_IF_RESULT_IS_NON_ZERO_OR_DELIVER +END art_quick_string_builder_append + /* * Create a function `name` calling the ReadBarrier::Mark routine, * getting its argument and returning its result through W register diff --git a/runtime/arch/mips/quick_entrypoints_mips.S b/runtime/arch/mips/quick_entrypoints_mips.S index b10d1fc849..5697185f55 100644 --- a/runtime/arch/mips/quick_entrypoints_mips.S +++ b/runtime/arch/mips/quick_entrypoints_mips.S @@ -2694,6 +2694,16 @@ ENTRY_NO_GP art_quick_string_compareto subu $v0, $t0, $t1 # return (this.charAt(i) - anotherString.charAt(i)) END art_quick_string_compareto + .extern artStringBuilderAppend +ENTRY art_quick_string_builder_append + SETUP_SAVE_REFS_ONLY_FRAME # save callee saves in case of GC + la $t9, artStringBuilderAppend + addiu $a1, $sp, ARG_SLOT_SIZE + FRAME_SIZE_SAVE_REFS_ONLY + __SIZEOF_POINTER__ # pass args + jalr $t9 # (uint32_t, const unit32_t*, Thread*) + move $a2, rSELF # pass Thread::Current + RETURN_IF_RESULT_IS_NON_ZERO_OR_DELIVER +END art_quick_string_builder_append + /* * Create a function `name` calling the ReadBarrier::Mark routine, * getting its argument and returning its result through register diff --git a/runtime/arch/mips64/quick_entrypoints_mips64.S b/runtime/arch/mips64/quick_entrypoints_mips64.S index ebf1d5b0b4..c54e7bb7f1 100644 --- a/runtime/arch/mips64/quick_entrypoints_mips64.S +++ b/runtime/arch/mips64/quick_entrypoints_mips64.S @@ -2476,6 +2476,16 @@ ENTRY_NO_GP art_quick_indexof #endif END art_quick_indexof + .extern artStringBuilderAppend +ENTRY art_quick_string_builder_append + SETUP_SAVE_REFS_ONLY_FRAME # save callee saves in case of GC + dla $t9, artStringBuilderAppend + daddiu $a1, $sp, FRAME_SIZE_SAVE_REFS_ONLY + __SIZEOF_POINTER__ # pass args + jalr $t9 # (uint32_t, const unit32_t*, Thread*) + move $a2, rSELF # pass Thread::Current + RETURN_IF_RESULT_IS_NON_ZERO_OR_DELIVER +END art_quick_string_builder_append + /* * Create a function `name` calling the ReadBarrier::Mark routine, * getting its argument and returning its result through register diff --git a/runtime/arch/x86/quick_entrypoints_x86.S b/runtime/arch/x86/quick_entrypoints_x86.S index 306c4ebd9b..b8ccd8e025 100644 --- a/runtime/arch/x86/quick_entrypoints_x86.S +++ b/runtime/arch/x86/quick_entrypoints_x86.S @@ -2246,6 +2246,25 @@ DEFINE_FUNCTION art_quick_string_compareto ret END_FUNCTION art_quick_string_compareto +DEFINE_FUNCTION art_quick_string_builder_append + SETUP_SAVE_REFS_ONLY_FRAME ebx, ebx // save ref containing registers for GC + // Outgoing argument set up + leal FRAME_SIZE_SAVE_REFS_ONLY + __SIZEOF_POINTER__(%esp), %edi // prepare args + push %eax // push padding + CFI_ADJUST_CFA_OFFSET(4) + pushl %fs:THREAD_SELF_OFFSET // pass Thread::Current() + CFI_ADJUST_CFA_OFFSET(4) + push %edi // pass args + CFI_ADJUST_CFA_OFFSET(4) + push %eax // pass format + CFI_ADJUST_CFA_OFFSET(4) + call SYMBOL(artStringBuilderAppend) // (uint32_t, const unit32_t*, Thread*) + addl MACRO_LITERAL(16), %esp // pop arguments + CFI_ADJUST_CFA_OFFSET(-16) + RESTORE_SAVE_REFS_ONLY_FRAME // restore frame up to return address + RETURN_IF_RESULT_IS_NON_ZERO_OR_DELIVER // return or deliver exception +END_FUNCTION art_quick_string_builder_append + // Create a function `name` calling the ReadBarrier::Mark routine, // getting its argument and returning its result through register // `reg`, saving and restoring all caller-save registers. diff --git a/runtime/arch/x86_64/quick_entrypoints_x86_64.S b/runtime/arch/x86_64/quick_entrypoints_x86_64.S index 39bf6e8d6c..1177477b9e 100644 --- a/runtime/arch/x86_64/quick_entrypoints_x86_64.S +++ b/runtime/arch/x86_64/quick_entrypoints_x86_64.S @@ -2201,6 +2201,16 @@ DEFINE_FUNCTION art_quick_instance_of ret END_FUNCTION art_quick_instance_of +DEFINE_FUNCTION art_quick_string_builder_append + SETUP_SAVE_REFS_ONLY_FRAME // save ref containing registers for GC + // Outgoing argument set up + leaq FRAME_SIZE_SAVE_REFS_ONLY + __SIZEOF_POINTER__(%rsp), %rsi // pass args + movq %gs:THREAD_SELF_OFFSET, %rdx // pass Thread::Current() + call artStringBuilderAppend // (uint32_t, const unit32_t*, Thread*) + RESTORE_SAVE_REFS_ONLY_FRAME // restore frame up to return address + RETURN_IF_RESULT_IS_NON_ZERO_OR_DELIVER // return or deliver exception +END_FUNCTION art_quick_string_builder_append + // Create a function `name` calling the ReadBarrier::Mark routine, // getting its argument and returning its result through register // `reg`, saving and restoring all caller-save registers. diff --git a/runtime/entrypoints/quick/quick_default_init_entrypoints.h b/runtime/entrypoints/quick/quick_default_init_entrypoints.h index ce12fdee5f..f5bb5a37e7 100644 --- a/runtime/entrypoints/quick/quick_default_init_entrypoints.h +++ b/runtime/entrypoints/quick/quick_default_init_entrypoints.h @@ -121,6 +121,9 @@ static void DefaultInitEntryPoints(JniEntryPoints* jpoints, QuickEntryPoints* qp // Deoptimize qpoints->pDeoptimize = art_quick_deoptimize_from_compiled_code; + + // StringBuilder append + qpoints->pStringBuilderAppend = art_quick_string_builder_append; } } // namespace art diff --git a/runtime/entrypoints/quick/quick_entrypoints.h b/runtime/entrypoints/quick/quick_entrypoints.h index 243f7ec1e2..954450fe7a 100644 --- a/runtime/entrypoints/quick/quick_entrypoints.h +++ b/runtime/entrypoints/quick/quick_entrypoints.h @@ -34,6 +34,7 @@ class Array; class Class; template<class MirrorType> class CompressedReference; class Object; +class String; } // namespace mirror class ArtMethod; @@ -78,6 +79,11 @@ extern mirror::Object* JniMethodEndWithReferenceSynchronized(jobject result, jobject locked, Thread* self) NO_THREAD_SAFETY_ANALYSIS HOT_ATTR; +extern "C" mirror::String* artStringBuilderAppend(uint32_t format, + const uint32_t* args, + Thread* self) + REQUIRES_SHARED(Locks::mutator_lock_) HOT_ATTR; + extern void ReadBarrierJni(mirror::CompressedReference<mirror::Object>* handle_on_stack, Thread* self) NO_THREAD_SAFETY_ANALYSIS HOT_ATTR; diff --git a/runtime/entrypoints/quick/quick_entrypoints_list.h b/runtime/entrypoints/quick/quick_entrypoints_list.h index 42b680e05a..21e248c554 100644 --- a/runtime/entrypoints/quick/quick_entrypoints_list.h +++ b/runtime/entrypoints/quick/quick_entrypoints_list.h @@ -169,6 +169,8 @@ V(NewStringFromStringBuffer, void, void) \ V(NewStringFromStringBuilder, void, void) \ \ + V(StringBuilderAppend, void*, uint32_t) \ +\ V(ReadBarrierJni, void, mirror::CompressedReference<mirror::Object>*, Thread*) \ V(ReadBarrierMarkReg00, mirror::Object*, mirror::Object*) \ V(ReadBarrierMarkReg01, mirror::Object*, mirror::Object*) \ diff --git a/runtime/entrypoints/quick/quick_string_builder_append_entrypoints.cc b/runtime/entrypoints/quick/quick_string_builder_append_entrypoints.cc new file mode 100644 index 0000000000..9afaf439dc --- /dev/null +++ b/runtime/entrypoints/quick/quick_string_builder_append_entrypoints.cc @@ -0,0 +1,30 @@ +/* + * Copyright (C) 2019 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "quick_entrypoints.h" + +#include "string_builder_append.h" +#include "obj_ptr-inl.h" + +namespace art { + +extern "C" mirror::String* artStringBuilderAppend(uint32_t format, + const uint32_t* args, + Thread* self) { + return StringBuilderAppend::AppendF(format, args, self).Ptr(); +} + +} // namespace art diff --git a/runtime/entrypoints/runtime_asm_entrypoints.h b/runtime/entrypoints/runtime_asm_entrypoints.h index fa287cb0ad..3f4e91ed91 100644 --- a/runtime/entrypoints/runtime_asm_entrypoints.h +++ b/runtime/entrypoints/runtime_asm_entrypoints.h @@ -87,6 +87,8 @@ static inline const void* GetQuickInstrumentationExitPc() { return reinterpret_cast<const void*>(art_quick_instrumentation_exit); } +extern "C" void* art_quick_string_builder_append(uint32_t format); + } // namespace art #endif // ART_RUNTIME_ENTRYPOINTS_RUNTIME_ASM_ENTRYPOINTS_H_ diff --git a/runtime/entrypoints_order_test.cc b/runtime/entrypoints_order_test.cc index 040a8c5432..5b4275cbad 100644 --- a/runtime/entrypoints_order_test.cc +++ b/runtime/entrypoints_order_test.cc @@ -331,7 +331,9 @@ class EntrypointsOrderTest : public CommonRuntimeTest { sizeof(void*)); EXPECT_OFFSET_DIFFNP(QuickEntryPoints, pNewStringFromStringBuffer, pNewStringFromStringBuilder, sizeof(void*)); - EXPECT_OFFSET_DIFFNP(QuickEntryPoints, pNewStringFromStringBuilder, pReadBarrierJni, + EXPECT_OFFSET_DIFFNP(QuickEntryPoints, pNewStringFromStringBuilder, pStringBuilderAppend, + sizeof(void*)); + EXPECT_OFFSET_DIFFNP(QuickEntryPoints, pStringBuilderAppend, pReadBarrierJni, sizeof(void*)); EXPECT_OFFSET_DIFFNP(QuickEntryPoints, pReadBarrierJni, pReadBarrierMarkReg00, sizeof(void*)); EXPECT_OFFSET_DIFFNP(QuickEntryPoints, pReadBarrierMarkReg00, pReadBarrierMarkReg01, diff --git a/runtime/image.cc b/runtime/image.cc index 0c99852a48..64046d025d 100644 --- a/runtime/image.cc +++ b/runtime/image.cc @@ -29,7 +29,7 @@ namespace art { const uint8_t ImageHeader::kImageMagic[] = { 'a', 'r', 't', '\n' }; -const uint8_t ImageHeader::kImageVersion[] = { '0', '7', '5', '\0' }; // SB.append() intrinsics +const uint8_t ImageHeader::kImageVersion[] = { '0', '7', '6', '\0' }; // SBAppend simplification. ImageHeader::ImageHeader(uint32_t image_reservation_size, uint32_t component_count, diff --git a/runtime/mirror/string.h b/runtime/mirror/string.h index 6b7dfd5d84..665446c1f4 100644 --- a/runtime/mirror/string.h +++ b/runtime/mirror/string.h @@ -30,6 +30,7 @@ enum AllocatorType : char; template<class T> class Handle; template<class MirrorType> class ObjPtr; +class StringBuilderAppend; struct StringOffsets; class StubTest_ReadBarrierForRoot_Test; @@ -272,6 +273,7 @@ class MANAGED String final : public Object { uint8_t value_compressed_[0]; }; + friend class art::StringBuilderAppend; friend struct art::StringOffsets; // for verifying offset information DISALLOW_IMPLICIT_CONSTRUCTORS(String); diff --git a/runtime/string_builder_append.cc b/runtime/string_builder_append.cc new file mode 100644 index 0000000000..5a34e9368a --- /dev/null +++ b/runtime/string_builder_append.cc @@ -0,0 +1,364 @@ +/* + * Copyright (C) 2019 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "string_builder_append.h" + +#include "base/casts.h" +#include "base/logging.h" +#include "common_throws.h" +#include "gc/heap.h" +#include "mirror/string-alloc-inl.h" +#include "obj_ptr-inl.h" +#include "runtime.h" + +namespace art { + +class StringBuilderAppend::Builder { + public: + Builder(uint32_t format, const uint32_t* args, Thread* self) + : format_(format), + args_(args), + hs_(self) {} + + int32_t CalculateLengthWithFlag() REQUIRES_SHARED(Locks::mutator_lock_); + + void operator()(ObjPtr<mirror::Object> obj, size_t usable_size) const + REQUIRES_SHARED(Locks::mutator_lock_); + + private: + static size_t Uint64Length(uint64_t value); + + static size_t Int64Length(int64_t value) { + uint64_t v = static_cast<uint64_t>(value); + return (value >= 0) ? Uint64Length(v) : 1u + Uint64Length(-v); + } + + static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint8_t* data) + REQUIRES_SHARED(Locks::mutator_lock_) { + DCHECK(new_string->IsCompressed()); + DCHECK_GE(new_string->GetLength(), data - new_string->GetValueCompressed()); + return new_string->GetLength() - (data - new_string->GetValueCompressed()); + } + + static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint16_t* data) + REQUIRES_SHARED(Locks::mutator_lock_) { + DCHECK(!new_string->IsCompressed()); + DCHECK_GE(new_string->GetLength(), data - new_string->GetValue()); + return new_string->GetLength() - (data - new_string->GetValue()); + } + + template <typename CharType, size_t size> + static CharType* AppendLiteral(ObjPtr<mirror::String> new_string, + CharType* data, + const char (&literal)[size]) REQUIRES_SHARED(Locks::mutator_lock_); + + template <typename CharType> + static CharType* AppendString(ObjPtr<mirror::String> new_string, + CharType* data, + ObjPtr<mirror::String> str) REQUIRES_SHARED(Locks::mutator_lock_); + + template <typename CharType> + static CharType* AppendInt64(ObjPtr<mirror::String> new_string, + CharType* data, + int64_t value) REQUIRES_SHARED(Locks::mutator_lock_); + + template <typename CharType> + void StoreData(ObjPtr<mirror::String> new_string, CharType* data) const + REQUIRES_SHARED(Locks::mutator_lock_); + + static constexpr char kNull[] = "null"; + static constexpr size_t kNullLength = sizeof(kNull) - 1u; + static constexpr char kTrue[] = "true"; + static constexpr size_t kTrueLength = sizeof(kTrue) - 1u; + static constexpr char kFalse[] = "false"; + static constexpr size_t kFalseLength = sizeof(kFalse) - 1u; + + // The format and arguments to append. + const uint32_t format_; + const uint32_t* const args_; + + // References are moved to the handle scope during CalculateLengthWithFlag(). + StackHandleScope<kMaxArgs> hs_; + + // The length and flag to store when the AppendBuilder is used as a pre-fence visitor. + int32_t length_with_flag_ = 0u; +}; + +inline size_t StringBuilderAppend::Builder::Uint64Length(uint64_t value) { + if (value == 0u) { + return 1u; + } + // Calculate floor(log2(value)). + size_t log2_value = BitSizeOf<uint64_t>() - 1u - CLZ(value); + // Calculate an estimate of floor(log10(value)). + // log10(2) = 0.301029996 > 0.296875 = 19/64 + // floor(log10(v)) == floor(log2(v) * log10(2)) + // >= floor(log2(v) * 19/64) + // >= floor(floor(log2(v)) * 19/64) + // This estimate is no more that one off from the actual value because log2(value) < 64 and thus + // log2(v) * log10(2) - log2(v) * 19/64 < 64*(log10(2) - 19/64) + // for the first approximation and + // log2(v) * 19/64 - floor(log2(v)) * 19/64 < 19/64 + // for the second one. Together, + // 64*(log10(2) - 19/64) + 19/64 = 0.56278 < 1 . + size_t log10_value_estimate = log2_value * 19u / 64u; + static constexpr uint64_t bounds[] = { + UINT64_C(9), + UINT64_C(99), + UINT64_C(999), + UINT64_C(9999), + UINT64_C(99999), + UINT64_C(999999), + UINT64_C(9999999), + UINT64_C(99999999), + UINT64_C(999999999), + UINT64_C(9999999999), + UINT64_C(99999999999), + UINT64_C(999999999999), + UINT64_C(9999999999999), + UINT64_C(99999999999999), + UINT64_C(999999999999999), + UINT64_C(9999999999999999), + UINT64_C(99999999999999999), + UINT64_C(999999999999999999), + UINT64_C(9999999999999999999), + }; + // Add 1 for the lowest digit, add another 1 if the estimate was too low. + DCHECK_LT(log10_value_estimate, std::size(bounds)); + size_t adjustment = (value > bounds[log10_value_estimate]) ? 2u : 1u; + return log10_value_estimate + adjustment; +} + +template <typename CharType, size_t size> +inline CharType* StringBuilderAppend::Builder::AppendLiteral(ObjPtr<mirror::String> new_string, + CharType* data, + const char (&literal)[size]) { + static_assert(size >= 2, "We need something to append."); + + // Literals are zero-terminated. + constexpr size_t length = size - 1u; + DCHECK_EQ(literal[length], '\0'); + + DCHECK_LE(length, RemainingSpace(new_string, data)); + for (size_t i = 0; i != length; ++i) { + data[i] = literal[i]; + } + return data + length; +} + +template <typename CharType> +inline CharType* StringBuilderAppend::Builder::AppendString(ObjPtr<mirror::String> new_string, + CharType* data, + ObjPtr<mirror::String> str) { + size_t length = dchecked_integral_cast<size_t>(str->GetLength()); + DCHECK_LE(length, RemainingSpace(new_string, data)); + if (sizeof(CharType) == sizeof(uint8_t) || str->IsCompressed()) { + DCHECK(str->IsCompressed()); + const uint8_t* value = str->GetValueCompressed(); + for (size_t i = 0; i != length; ++i) { + data[i] = value[i]; + } + } else { + const uint16_t* value = str->GetValue(); + for (size_t i = 0; i != length; ++i) { + data[i] = dchecked_integral_cast<CharType>(value[i]); + } + } + return data + length; +} + +template <typename CharType> +inline CharType* StringBuilderAppend::Builder::AppendInt64(ObjPtr<mirror::String> new_string, + CharType* data, + int64_t value) { + DCHECK_GE(RemainingSpace(new_string, data), Int64Length(value)); + uint64_t v = static_cast<uint64_t>(value); + if (value < 0) { + *data = '-'; + ++data; + v = -v; + } + size_t length = Uint64Length(v); + // Write the digits from the end, do not write the most significant digit + // in the loop to avoid an unnecessary division. + for (size_t i = 1; i != length; ++i) { + uint64_t digit = v % UINT64_C(10); + v /= UINT64_C(10); + data[length - i] = '0' + static_cast<char>(digit); + } + DCHECK_LE(v, 10u); + *data = '0' + static_cast<char>(v); + return data + length; +} + +inline int32_t StringBuilderAppend::Builder::CalculateLengthWithFlag() { + static_assert(static_cast<size_t>(Argument::kEnd) == 0u, "kEnd must be 0."); + bool compressible = mirror::kUseStringCompression; + uint64_t length = 0u; + const uint32_t* current_arg = args_; + for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) { + DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast)); + switch (static_cast<Argument>(f & kArgMask)) { + case Argument::kString: { + Handle<mirror::String> str = + hs_.NewHandle(reinterpret_cast32<mirror::String*>(*current_arg)); + if (str != nullptr) { + length += str->GetLength(); + compressible = compressible && str->IsCompressed(); + } else { + length += kNullLength; + } + break; + } + case Argument::kBoolean: { + length += (*current_arg != 0u) ? kTrueLength : kFalseLength; + break; + } + case Argument::kChar: { + length += 1u; + compressible = compressible && + mirror::String::IsASCII(reinterpret_cast<const uint16_t*>(current_arg)[0]); + break; + } + case Argument::kInt: { + length += Int64Length(static_cast<int32_t>(*current_arg)); + break; + } + case Argument::kLong: { + current_arg = AlignUp(current_arg, sizeof(int64_t)); + length += Int64Length(*reinterpret_cast<const int64_t*>(current_arg)); + ++current_arg; // Skip the low word, let the common code skip the high word. + break; + } + + case Argument::kStringBuilder: + case Argument::kCharArray: + case Argument::kObject: + case Argument::kFloat: + case Argument::kDouble: + LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex + << (f & kArgMask) << " full format: 0x" << std::hex << format_; + UNREACHABLE(); + default: + LOG(FATAL) << "Unexpected arg format: 0x" << std::hex + << (f & kArgMask) << " full format: 0x" << std::hex << format_; + UNREACHABLE(); + } + ++current_arg; + DCHECK_LE(hs_.NumberOfReferences(), kMaxArgs); + } + + if (length > std::numeric_limits<int32_t>::max()) { + // We cannot allocate memory for the entire result. + hs_.Self()->ThrowNewException("Ljava/lang/OutOfMemoryError;", + "Out of memory for StringBuilder append."); + return -1; + } + + length_with_flag_ = mirror::String::GetFlaggedCount(length, compressible); + return length_with_flag_; +} + +template <typename CharType> +inline void StringBuilderAppend::Builder::StoreData(ObjPtr<mirror::String> new_string, + CharType* data) const { + size_t handle_index = 0u; + const uint32_t* current_arg = args_; + for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) { + DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast)); + switch (static_cast<Argument>(f & kArgMask)) { + case Argument::kString: { + ObjPtr<mirror::String> str = + ObjPtr<mirror::String>::DownCast(hs_.GetReference(handle_index)); + ++handle_index; + if (str != nullptr) { + data = AppendString(new_string, data, str); + } else { + data = AppendLiteral(new_string, data, kNull); + } + break; + } + case Argument::kBoolean: { + if (*current_arg != 0u) { + data = AppendLiteral(new_string, data, kTrue); + } else { + data = AppendLiteral(new_string, data, kFalse); + } + break; + } + case Argument::kChar: { + DCHECK_GE(RemainingSpace(new_string, data), 1u); + *data = *reinterpret_cast<const CharType*>(current_arg); + ++data; + break; + } + case Argument::kInt: { + data = AppendInt64(new_string, data, static_cast<int32_t>(*current_arg)); + break; + } + case Argument::kLong: { + current_arg = AlignUp(current_arg, sizeof(int64_t)); + data = AppendInt64(new_string, data, *reinterpret_cast<const int64_t*>(current_arg)); + ++current_arg; // Skip the low word, let the common code skip the high word. + break; + } + + case Argument::kStringBuilder: + case Argument::kCharArray: + case Argument::kFloat: + case Argument::kDouble: + LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex + << (f & kArgMask) << " full format: 0x" << std::hex << format_; + UNREACHABLE(); + default: + LOG(FATAL) << "Unexpected arg format: 0x" << std::hex + << (f & kArgMask) << " full format: 0x" << std::hex << format_; + UNREACHABLE(); + } + ++current_arg; + DCHECK_LE(handle_index, hs_.NumberOfReferences()); + } + DCHECK_EQ(RemainingSpace(new_string, data), 0u) << std::hex << format_; +} + +inline void StringBuilderAppend::Builder::operator()(ObjPtr<mirror::Object> obj, + size_t usable_size ATTRIBUTE_UNUSED) const { + ObjPtr<mirror::String> new_string = ObjPtr<mirror::String>::DownCast(obj); + new_string->SetCount(length_with_flag_); + if (mirror::String::IsCompressed(length_with_flag_)) { + StoreData(new_string, new_string->GetValueCompressed()); + } else { + StoreData(new_string, new_string->GetValue()); + } +} + +ObjPtr<mirror::String> StringBuilderAppend::AppendF(uint32_t format, + const uint32_t* args, + Thread* self) { + Builder builder(format, args, self); + self->AssertNoPendingException(); + int32_t length_with_flag = builder.CalculateLengthWithFlag(); + if (self->IsExceptionPending()) { + return nullptr; + } + gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); + ObjPtr<mirror::String> result = mirror::String::Alloc</*kIsInstrumented=*/ true>( + self, length_with_flag, allocator_type, builder); + + return result; +} + +} // namespace art diff --git a/runtime/string_builder_append.h b/runtime/string_builder_append.h new file mode 100644 index 0000000000..fee64198f9 --- /dev/null +++ b/runtime/string_builder_append.h @@ -0,0 +1,67 @@ +/* + * Copyright (C) 2019 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_RUNTIME_STRING_BUILDER_APPEND_H_ +#define ART_RUNTIME_STRING_BUILDER_APPEND_H_ + +#include <stddef.h> +#include <stdint.h> + +#include "base/bit_utils.h" +#include "base/locks.h" +#include "obj_ptr.h" + +namespace art { + +class Thread; + +namespace mirror { +class String; +} // namespace mirror + +class StringBuilderAppend { + public: + enum class Argument : uint8_t { + kEnd = 0u, + kObject, + kStringBuilder, + kString, + kCharArray, + kBoolean, + kChar, + kInt, + kLong, + kFloat, + kDouble, + kLast = kDouble + }; + + static constexpr size_t kBitsPerArg = + MinimumBitsToStore(static_cast<size_t>(Argument::kLast)); + static constexpr size_t kMaxArgs = BitSizeOf<uint32_t>() / kBitsPerArg; + static_assert(kMaxArgs * kBitsPerArg == BitSizeOf<uint32_t>(), "Expecting no extra bits."); + static constexpr uint32_t kArgMask = MaxInt<uint32_t>(kBitsPerArg); + + static ObjPtr<mirror::String> AppendF(uint32_t format, const uint32_t* args, Thread* self) + REQUIRES_SHARED(Locks::mutator_lock_); + + private: + class Builder; +}; + +} // namespace art + +#endif // ART_RUNTIME_STRING_BUILDER_APPEND_H_ diff --git a/test/697-checker-string-append/expected.txt b/test/697-checker-string-append/expected.txt new file mode 100644 index 0000000000..b0aad4deb5 --- /dev/null +++ b/test/697-checker-string-append/expected.txt @@ -0,0 +1 @@ +passed diff --git a/test/697-checker-string-append/info.txt b/test/697-checker-string-append/info.txt new file mode 100644 index 0000000000..cb612cb024 --- /dev/null +++ b/test/697-checker-string-append/info.txt @@ -0,0 +1 @@ +Test for String append pattern recognition. diff --git a/test/697-checker-string-append/src/Main.java b/test/697-checker-string-append/src/Main.java new file mode 100644 index 0000000000..4f2fa19bc4 --- /dev/null +++ b/test/697-checker-string-append/src/Main.java @@ -0,0 +1,254 @@ +/* + * Copyright 2019 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +public class Main { + public static void main(String[] args) { + testAppendStringAndLong(); + testAppendStringAndInt(); + testAppendStringAndString(); + testMiscelaneous(); + testNoArgs(); + System.out.println("passed"); + } + + private static final String APPEND_LONG_PREFIX = "Long/"; + private static final String[] APPEND_LONG_TEST_CASES = { + "Long/0", + "Long/1", + "Long/9", + "Long/10", + "Long/99", + "Long/100", + "Long/999", + "Long/1000", + "Long/9999", + "Long/10000", + "Long/99999", + "Long/100000", + "Long/999999", + "Long/1000000", + "Long/9999999", + "Long/10000000", + "Long/99999999", + "Long/100000000", + "Long/999999999", + "Long/1000000000", + "Long/9999999999", + "Long/10000000000", + "Long/99999999999", + "Long/100000000000", + "Long/999999999999", + "Long/1000000000000", + "Long/9999999999999", + "Long/10000000000000", + "Long/99999999999999", + "Long/100000000000000", + "Long/999999999999999", + "Long/1000000000000000", + "Long/9999999999999999", + "Long/10000000000000000", + "Long/99999999999999999", + "Long/100000000000000000", + "Long/999999999999999999", + "Long/1000000000000000000", + "Long/9223372036854775807", // Long.MAX_VALUE + "Long/-1", + "Long/-9", + "Long/-10", + "Long/-99", + "Long/-100", + "Long/-999", + "Long/-1000", + "Long/-9999", + "Long/-10000", + "Long/-99999", + "Long/-100000", + "Long/-999999", + "Long/-1000000", + "Long/-9999999", + "Long/-10000000", + "Long/-99999999", + "Long/-100000000", + "Long/-999999999", + "Long/-1000000000", + "Long/-9999999999", + "Long/-10000000000", + "Long/-99999999999", + "Long/-100000000000", + "Long/-999999999999", + "Long/-1000000000000", + "Long/-9999999999999", + "Long/-10000000000000", + "Long/-99999999999999", + "Long/-100000000000000", + "Long/-999999999999999", + "Long/-1000000000000000", + "Long/-9999999999999999", + "Long/-10000000000000000", + "Long/-99999999999999999", + "Long/-100000000000000000", + "Long/-999999999999999999", + "Long/-1000000000000000000", + "Long/-9223372036854775808", // Long.MIN_VALUE + }; + + /// CHECK-START: java.lang.String Main.$noinline$appendStringAndLong(java.lang.String, long) instruction_simplifier (before) + /// CHECK-NOT: StringBuilderAppend + + /// CHECK-START: java.lang.String Main.$noinline$appendStringAndLong(java.lang.String, long) instruction_simplifier (after) + /// CHECK: StringBuilderAppend + public static String $noinline$appendStringAndLong(String s, long l) { + return new StringBuilder().append(s).append(l).toString(); + } + + public static void testAppendStringAndLong() { + for (String expected : APPEND_LONG_TEST_CASES) { + long l = Long.valueOf(expected.substring(APPEND_LONG_PREFIX.length())); + String result = $noinline$appendStringAndLong(APPEND_LONG_PREFIX, l); + assertEquals(expected, result); + } + } + + private static final String APPEND_INT_PREFIX = "Int/"; + private static final String[] APPEND_INT_TEST_CASES = { + "Int/0", + "Int/1", + "Int/9", + "Int/10", + "Int/99", + "Int/100", + "Int/999", + "Int/1000", + "Int/9999", + "Int/10000", + "Int/99999", + "Int/100000", + "Int/999999", + "Int/1000000", + "Int/9999999", + "Int/10000000", + "Int/99999999", + "Int/100000000", + "Int/999999999", + "Int/1000000000", + "Int/2147483647", // Integer.MAX_VALUE + "Int/-1", + "Int/-9", + "Int/-10", + "Int/-99", + "Int/-100", + "Int/-999", + "Int/-1000", + "Int/-9999", + "Int/-10000", + "Int/-99999", + "Int/-100000", + "Int/-999999", + "Int/-1000000", + "Int/-9999999", + "Int/-10000000", + "Int/-99999999", + "Int/-100000000", + "Int/-999999999", + "Int/-1000000000", + "Int/-2147483648", // Integer.MIN_VALUE + }; + + /// CHECK-START: java.lang.String Main.$noinline$appendStringAndInt(java.lang.String, int) instruction_simplifier (before) + /// CHECK-NOT: StringBuilderAppend + + /// CHECK-START: java.lang.String Main.$noinline$appendStringAndInt(java.lang.String, int) instruction_simplifier (after) + /// CHECK: StringBuilderAppend + public static String $noinline$appendStringAndInt(String s, int i) { + return new StringBuilder().append(s).append(i).toString(); + } + + public static void testAppendStringAndInt() { + for (String expected : APPEND_INT_TEST_CASES) { + int i = Integer.valueOf(expected.substring(APPEND_INT_PREFIX.length())); + String result = $noinline$appendStringAndInt(APPEND_INT_PREFIX, i); + assertEquals(expected, result); + } + } + + public static String $noinline$appendStringAndString(String s1, String s2) { + return new StringBuilder().append(s1).append(s2).toString(); + } + + public static void testAppendStringAndString() { + assertEquals("nullnull", $noinline$appendStringAndString(null, null)); + assertEquals("nullTEST", $noinline$appendStringAndString(null, "TEST")); + assertEquals("TESTnull", $noinline$appendStringAndString("TEST", null)); + assertEquals("abcDEFGH", $noinline$appendStringAndString("abc", "DEFGH")); + // Test with a non-ASCII character. + assertEquals("test\u0131", $noinline$appendStringAndString("test", "\u0131")); + assertEquals("\u0131test", $noinline$appendStringAndString("\u0131", "test")); + assertEquals("\u0131test\u0131", $noinline$appendStringAndString("\u0131", "test\u0131")); + } + + /// CHECK-START: java.lang.String Main.$noinline$appendSLILC(java.lang.String, long, int, long, char) instruction_simplifier (before) + /// CHECK-NOT: StringBuilderAppend + + /// CHECK-START: java.lang.String Main.$noinline$appendSLILC(java.lang.String, long, int, long, char) instruction_simplifier (after) + /// CHECK: StringBuilderAppend + public static String $noinline$appendSLILC(String s, + long l1, + int i, + long l2, + char c) { + return new StringBuilder().append(s) + .append(l1) + .append(i) + .append(l2) + .append(c).toString(); + } + + public static void testMiscelaneous() { + assertEquals("x17-1q", + $noinline$appendSLILC("x", 1L, 7, -1L, 'q')); + assertEquals("null17-1q", + $noinline$appendSLILC(null, 1L, 7, -1L, 'q')); + assertEquals("x\u013117-1q", + $noinline$appendSLILC("x\u0131", 1L, 7, -1L, 'q')); + assertEquals("x427-1q", + $noinline$appendSLILC("x", 42L, 7, -1L, 'q')); + assertEquals("x1-42-1q", + $noinline$appendSLILC("x", 1L, -42, -1L, 'q')); + assertEquals("x17424242q", + $noinline$appendSLILC("x", 1L, 7, 424242L, 'q')); + assertEquals("x17-1\u0131", + $noinline$appendSLILC("x", 1L, 7, -1L, '\u0131')); + } + + /// CHECK-START: java.lang.String Main.$noinline$appendNothing() instruction_simplifier (before) + /// CHECK-NOT: StringBuilderAppend + + /// CHECK-START: java.lang.String Main.$noinline$appendNothing() instruction_simplifier (after) + /// CHECK-NOT: StringBuilderAppend + public static String $noinline$appendNothing() { + return new StringBuilder().toString(); + } + + public static void testNoArgs() { + assertEquals("", $noinline$appendNothing()); + } + + public static void assertEquals(String expected, String actual) { + if (!expected.equals(actual)) { + throw new AssertionError("Expected: " + expected + ", actual: " + actual); + } + } +} |