ART: Optimize StringBuilder append pattern.
Recognize appending with StringBuilder and replace the
entire expression with a runtime call that perfoms the
append in a more efficient manner.
For now, require the entire pattern to be in a single block
and be very strict about the StringBuilder environment uses.
Also, do not accept StringBuilder/char[]/Object/float/double
arguments as they throw non-OOME exceptions and/or require a
call from the entrypoint back to a helper function in Java;
these shall be implemented later.
Boot image size for aosp_taimen-userdebug:
- before:
arm/boot*.oat: 19653872
arm64/boot*.oat: 23292784
oat/arm64/services.odex: 22408664
- after:
arm/boot*.oat: 19432184 (-216KiB)
arm64/boot*.oat: 22992488 (-293KiB)
oat/arm64/services.odex: 22376776 (-31KiB)
Note that const-string in compiled boot image methods cannot
throw, but for apps it can and therefore its environment can
prevent the optimization for apps. We could implement either
a simple carve-out for const-string or generic environment
pruning to allow this pattern to be applied more often.
Results for the new StringBuilderAppendBenchmark on taimen:
timeAppendLongStrings: ~700ns -> ~200ns
timeAppendStringAndInt: ~220ns -> ~140ns
timeAppendStrings: ~200ns -> 130ns
Bug: 19575890
Test: 697-checker-string-append
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Test: aosp_taimen-userdebug boots.
Test: run-gtests.sh
Test: testrunner.py --target --optimizing
Test: vogar --benchmark art/benchmark/stringbuilder-append/src/StringBuilderAppendBenchmark.java
Change-Id: I51789bf299f5219f68ada4c077b6a1d3fe083964
diff --git a/benchmark/stringbuilder-append/info.txt b/benchmark/stringbuilder-append/info.txt
new file mode 100644
index 0000000..ae58812
--- /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 0000000..1550e81
--- /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 2bbb570..3b5699b 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 @@
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 f70ecb6..357c4bb 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -546,6 +546,8 @@
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 3086882..28a7583 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -5411,6 +5411,15 @@
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 6469c69..7adfe5d 100644
--- a/compiler/optimizing/code_generator_arm_vixl.cc
+++ b/compiler/optimizing/code_generator_arm_vixl.cc
@@ -5722,6 +5722,15 @@
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 72334af..b3bce78 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -9529,6 +9529,15 @@
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 0d3cb3b..0a3a3fa 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -7148,6 +7148,15 @@
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 ca1723b..7a73569 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -5510,6 +5510,15 @@
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 7c293b8..ee2ef77 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -4882,6 +4882,15 @@
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 e829576..9cc5cad 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 @@
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 @@
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 8a8b371..cb53ae3 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1438,6 +1438,7 @@
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 @@
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 c46aa18..2142727 100644
--- a/dex2oat/linker/oat_writer_test.cc
+++ b/dex2oat/linker/oat_writer_test.cc
@@ -469,7 +469,7 @@
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 cbaa68f..2325b0d 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -195,6 +195,7 @@
"signal_catcher.cc",
"stack.cc",
"stack_map.cc",
+ "string_builder_append.cc",
"thread.cc",
"thread_list.cc",
"thread_pool.cc",
@@ -240,6 +241,7 @@
"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 3ab6aa8..ecda78d 100644
--- a/runtime/arch/arm/quick_entrypoints_arm.S
+++ b/runtime/arch/arm/quick_entrypoints_arm.S
@@ -2215,6 +2215,17 @@
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 8b15238..1c252a2 100644
--- a/runtime/arch/arm64/quick_entrypoints_arm64.S
+++ b/runtime/arch/arm64/quick_entrypoints_arm64.S
@@ -2468,6 +2468,17 @@
#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 b10d1fc..5697185 100644
--- a/runtime/arch/mips/quick_entrypoints_mips.S
+++ b/runtime/arch/mips/quick_entrypoints_mips.S
@@ -2694,6 +2694,16 @@
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 ebf1d5b..c54e7bb 100644
--- a/runtime/arch/mips64/quick_entrypoints_mips64.S
+++ b/runtime/arch/mips64/quick_entrypoints_mips64.S
@@ -2476,6 +2476,16 @@
#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 306c4eb..b8ccd8e 100644
--- a/runtime/arch/x86/quick_entrypoints_x86.S
+++ b/runtime/arch/x86/quick_entrypoints_x86.S
@@ -2246,6 +2246,25 @@
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 39bf6e8..1177477 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 @@
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 ce12fde..f5bb5a3 100644
--- a/runtime/entrypoints/quick/quick_default_init_entrypoints.h
+++ b/runtime/entrypoints/quick/quick_default_init_entrypoints.h
@@ -121,6 +121,9 @@
// 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 243f7ec..954450f 100644
--- a/runtime/entrypoints/quick/quick_entrypoints.h
+++ b/runtime/entrypoints/quick/quick_entrypoints.h
@@ -34,6 +34,7 @@
class Class;
template<class MirrorType> class CompressedReference;
class Object;
+class String;
} // namespace mirror
class ArtMethod;
@@ -78,6 +79,11 @@
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 42b680e..21e248c 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 0000000..9afaf43
--- /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 fa287cb..3f4e91e 100644
--- a/runtime/entrypoints/runtime_asm_entrypoints.h
+++ b/runtime/entrypoints/runtime_asm_entrypoints.h
@@ -87,6 +87,8 @@
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 040a8c5..5b4275c 100644
--- a/runtime/entrypoints_order_test.cc
+++ b/runtime/entrypoints_order_test.cc
@@ -331,7 +331,9 @@
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 0c99852..64046d0 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 6b7dfd5..665446c 100644
--- a/runtime/mirror/string.h
+++ b/runtime/mirror/string.h
@@ -30,6 +30,7 @@
template<class T> class Handle;
template<class MirrorType> class ObjPtr;
+class StringBuilderAppend;
struct StringOffsets;
class StubTest_ReadBarrierForRoot_Test;
@@ -272,6 +273,7 @@
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 0000000..5a34e93
--- /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 0000000..fee6419
--- /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 0000000..b0aad4d
--- /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 0000000..cb612cb
--- /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 0000000..4f2fa19
--- /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);
+ }
+ }
+}