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);
+        }
+    }
+}