diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index ce97d08..8f46be4 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -1135,6 +1135,8 @@
     public final DexMethod requireNonNull;
     public final DexMethod requireNonNullWithMessage;
     public final DexMethod requireNonNullWithMessageSupplier;
+    public final DexMethod toStringWithObject =
+        createMethod(objectsType, createProto(stringType, objectType), "toString");
 
     private ObjectsMethods() {
       DexString requireNonNullMethodName = createString("requireNonNull");
@@ -1549,6 +1551,8 @@
     public final DexMethod toString;
 
     private final Set<DexMethod> appendMethods;
+    private final Set<DexMethod> appendPrimitiveMethods;
+
     private StringBuildingMethods(DexType receiver) {
       DexString append = createString("append");
 
@@ -1567,7 +1571,6 @@
       appendObject = createMethod(receiver, createProto(receiver, objectType), append);
       appendString = createMethod(receiver, createProto(receiver, stringType), append);
       appendStringBuffer = createMethod(receiver, createProto(receiver, stringBufferType), append);
-
       charSequenceConstructor =
           createMethod(receiver, createProto(voidType, charSequenceType), constructorMethodName);
       defaultConstructor = createMethod(receiver, createProto(voidType), constructorMethodName);
@@ -1592,6 +1595,9 @@
               appendObject,
               appendString,
               appendStringBuffer);
+      appendPrimitiveMethods =
+          ImmutableSet.of(
+              appendBoolean, appendChar, appendInt, appendDouble, appendFloat, appendLong);
       constructorMethods =
           ImmutableSet.of(
               charSequenceConstructor, defaultConstructor, intConstructor, stringConstructor);
@@ -1603,6 +1609,22 @@
       return appendMethods.contains(method);
     }
 
+    public boolean isAppendObjectMethod(DexMethod method) {
+      return method == appendObject;
+    }
+
+    public boolean isAppendPrimitiveMethod(DexMethod method) {
+      return appendPrimitiveMethods.contains(method);
+    }
+
+    public boolean isAppendStringMethod(DexMethod method) {
+      return method == appendString;
+    }
+
+    public boolean isConstructorMethod(DexMethod method) {
+      return constructorMethods.contains(method);
+    }
+
     public boolean constructorInvokeIsSideEffectFree(InvokeMethod invoke) {
       DexMethod invokedMethod = invoke.getInvokedMethod();
       if (invokedMethod == charSequenceConstructor) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
index a3f8421..c9c5c3a 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
@@ -275,6 +275,18 @@
   }
 
   @Override
+  public void replaceCurrentInstructionWithConstString(
+      AppView<?> appView, IRCode code, DexString value) {
+    if (current == null) {
+      throw new IllegalStateException();
+    }
+
+    // Replace the instruction by const-string.
+    ConstString constString = code.createStringConstant(appView, value, current.getLocalInfo());
+    replaceCurrentInstruction(constString);
+  }
+
+  @Override
   public void replaceCurrentInstructionWithStaticGet(
       AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
     if (current == null) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
index cb33b18..db3f81e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
@@ -53,6 +53,12 @@
   }
 
   @Override
+  public void replaceCurrentInstructionWithConstString(
+      AppView<?> appView, IRCode code, DexString value) {
+    instructionIterator.replaceCurrentInstructionWithConstString(appView, code, value);
+  }
+
+  @Override
   public void replaceCurrentInstructionWithStaticGet(
       AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
     instructionIterator.replaceCurrentInstructionWithStaticGet(
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
index 792018b..493c560 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
@@ -96,6 +96,14 @@
 
   void replaceCurrentInstructionWithConstInt(IRCode code, int value);
 
+  void replaceCurrentInstructionWithConstString(AppView<?> appView, IRCode code, DexString value);
+
+  default void replaceCurrentInstructionWithConstString(
+      AppView<?> appView, IRCode code, String value) {
+    replaceCurrentInstructionWithConstString(
+        appView, code, appView.dexItemFactory().createString(value));
+  }
+
   void replaceCurrentInstructionWithStaticGet(
       AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues);
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index 6daa9a4..9d7d69b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -30,7 +30,9 @@
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.google.common.collect.ImmutableList;
 import java.util.BitSet;
+import java.util.Collections;
 import java.util.List;
 
 public abstract class InvokeMethod extends Invoke {
@@ -238,4 +240,30 @@
     }
     return false;
   }
+
+  abstract static class Builder<B extends Builder<B, I>, I extends InvokeMethod>
+      extends BuilderBase<B, I> {
+
+    protected DexMethod method;
+    protected List<Value> arguments = Collections.emptyList();
+
+    public B setArguments(List<Value> arguments) {
+      assert arguments != null;
+      this.arguments = arguments;
+      return self();
+    }
+
+    public B setSingleArgument(Value argument) {
+      return setArguments(ImmutableList.of(argument));
+    }
+
+    public B setMethod(DexMethod method) {
+      this.method = method;
+      return self();
+    }
+
+    public B setMethod(DexClassAndMethod method) {
+      return setMethod(method.getReference());
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
index 3139d20..1b3aef3 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
@@ -27,8 +27,6 @@
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.ir.optimize.inliner.WhyAreYouNotInliningReporter;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.google.common.collect.ImmutableList;
-import java.util.Collections;
 import java.util.List;
 
 public class InvokeStatic extends InvokeMethod {
@@ -235,29 +233,7 @@
         .classInitializationMayHaveSideEffectsInContext(appView, context);
   }
 
-  public static class Builder extends BuilderBase<Builder, InvokeStatic> {
-
-    private DexMethod method;
-    private List<Value> arguments = Collections.emptyList();
-
-    public Builder setArguments(List<Value> arguments) {
-      assert arguments != null;
-      this.arguments = arguments;
-      return this;
-    }
-
-    public Builder setSingleArgument(Value argument) {
-      return setArguments(ImmutableList.of(argument));
-    }
-
-    public Builder setMethod(DexMethod method) {
-      this.method = method;
-      return this;
-    }
-
-    public Builder setMethod(DexClassAndMethod method) {
-      return setMethod(method.getReference());
-    }
+  public static class Builder extends InvokeMethod.Builder<Builder, InvokeStatic> {
 
     @Override
     public InvokeStatic build() {
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
index d4f737e..e063b8f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
@@ -33,6 +33,10 @@
     super(target, result, arguments);
   }
 
+  public static Builder builder() {
+    return new Builder();
+  }
+
   @Override
   public boolean getInterfaceBit() {
     return false;
@@ -167,4 +171,17 @@
     return ClassInitializationAnalysis.InstructionUtils.forInvokeVirtual(
         this, clazz, context, appView, mode, assumption);
   }
+
+  public static class Builder extends InvokeMethod.Builder<Builder, InvokeVirtual> {
+
+    @Override
+    public InvokeVirtual build() {
+      return amend(new InvokeVirtual(method, outValue, arguments));
+    }
+
+    @Override
+    public Builder self() {
+      return this;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
index 889089f..4f4e2c6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
@@ -73,6 +73,12 @@
   }
 
   @Override
+  public void replaceCurrentInstructionWithConstString(
+      AppView<?> appView, IRCode code, DexString value) {
+    currentBlockIterator.replaceCurrentInstructionWithConstString(appView, code, value);
+  }
+
+  @Override
   public void replaceCurrentInstructionWithStaticGet(
       AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
     currentBlockIterator.replaceCurrentInstructionWithStaticGet(
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/BooleanMethodOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/BooleanMethodOptimizer.java
index 69bdef8..2c93f77 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/BooleanMethodOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/BooleanMethodOptimizer.java
@@ -19,7 +19,7 @@
 import com.android.tools.r8.ir.code.Value;
 import java.util.Set;
 
-public class BooleanMethodOptimizer implements LibraryMethodModelCollection {
+public class BooleanMethodOptimizer extends StatelessLibraryMethodModelCollection {
 
   private final AppView<?> appView;
   private final DexItemFactory dexItemFactory;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/EnumMethodOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/EnumMethodOptimizer.java
index 4323220..5ee7017 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/EnumMethodOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/EnumMethodOptimizer.java
@@ -19,7 +19,8 @@
 import com.android.tools.r8.ir.code.Value;
 import java.util.Set;
 
-public class EnumMethodOptimizer implements LibraryMethodModelCollection {
+public class EnumMethodOptimizer extends StatelessLibraryMethodModelCollection {
+
   private final AppView<?> appView;
 
   EnumMethodOptimizer(AppView<?> appView) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java
index d6c8ada..5c38b07 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMemberOptimizer.java
@@ -35,7 +35,7 @@
   /** The library types that are modeled. */
   private final Set<DexType> modeledLibraryTypes = Sets.newIdentityHashSet();
 
-  private final Map<DexType, LibraryMethodModelCollection> libraryMethodModelCollections =
+  private final Map<DexType, LibraryMethodModelCollection<?>> libraryMethodModelCollections =
       new IdentityHashMap<>();
 
   public LibraryMemberOptimizer(AppView<?> appView) {
@@ -43,6 +43,7 @@
     register(new BooleanMethodOptimizer(appView));
     register(new ObjectMethodOptimizer(appView));
     register(new ObjectsMethodOptimizer(appView));
+    register(new StringBuilderMethodOptimizer(appView));
     register(new StringMethodOptimizer(appView));
     if (appView.enableWholeProgramOptimizations()) {
       // Subtyping is required to prove the enum class is a subtype of java.lang.Enum.
@@ -98,9 +99,9 @@
     return modeledLibraryTypes.contains(type);
   }
 
-  private void register(LibraryMethodModelCollection optimizer) {
+  private void register(LibraryMethodModelCollection<?> optimizer) {
     DexType modeledType = optimizer.getType();
-    LibraryMethodModelCollection existing =
+    LibraryMethodModelCollection<?> existing =
         libraryMethodModelCollections.put(modeledType, optimizer);
     assert existing == null;
     modeledLibraryTypes.add(modeledType);
@@ -114,13 +115,16 @@
       MethodProcessingId methodProcessingId) {
     Set<Value> affectedValues = Sets.newIdentityHashSet();
     InstructionListIterator instructionIterator = code.instructionListIterator();
+    Map<LibraryMethodModelCollection<?>, LibraryMethodModelCollection.State> optimizationStates =
+        new IdentityHashMap<>();
     while (instructionIterator.hasNext()) {
       Instruction instruction = instructionIterator.next();
       if (instruction.isInvokeMethod()) {
         InvokeMethod invoke = instruction.asInvokeMethod();
         DexClassAndMethod singleTarget = invoke.lookupSingleTarget(appView, code.context());
         if (singleTarget != null) {
-          optimizeInvoke(code, instructionIterator, invoke, singleTarget, affectedValues);
+          optimizeInvoke(
+              code, instructionIterator, invoke, singleTarget, affectedValues, optimizationStates);
         }
       }
     }
@@ -134,10 +138,15 @@
       InstructionListIterator instructionIterator,
       InvokeMethod invoke,
       DexClassAndMethod singleTarget,
-      Set<Value> affectedValues) {
-    LibraryMethodModelCollection optimizer =
+      Set<Value> affectedValues,
+      Map<LibraryMethodModelCollection<?>, LibraryMethodModelCollection.State> optimizationStates) {
+    LibraryMethodModelCollection<?> optimizer =
         libraryMethodModelCollections.getOrDefault(
             singleTarget.getHolderType(), NopLibraryMethodModelCollection.getInstance());
-    optimizer.optimize(code, instructionIterator, invoke, singleTarget, affectedValues);
+    LibraryMethodModelCollection.State optimizationState =
+        optimizationStates.computeIfAbsent(
+            optimizer, LibraryMethodModelCollection::createInitialState);
+    optimizer.optimize(
+        code, instructionIterator, invoke, singleTarget, affectedValues, optimizationState);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodModelCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodModelCollection.java
index 843e9ab..463f7e7 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodModelCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodModelCollection.java
@@ -10,10 +10,15 @@
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.library.LibraryMethodModelCollection.State;
 import java.util.Set;
 
 /** Used to model the behavior of library methods for optimization purposes. */
-public interface LibraryMethodModelCollection {
+public interface LibraryMethodModelCollection<T extends State> {
+
+  default T createInitialState() {
+    return null;
+  }
 
   /**
    * The library class whose methods are being modeled by this collection of models. As an example,
@@ -30,5 +35,20 @@
       InstructionListIterator instructionIterator,
       InvokeMethod invoke,
       DexClassAndMethod singleTarget,
-      Set<Value> affectedValues);
+      Set<Value> affectedValues,
+      T state);
+
+  @SuppressWarnings("unchecked")
+  default void optimize(
+      IRCode code,
+      InstructionListIterator instructionIterator,
+      InvokeMethod invoke,
+      DexClassAndMethod singleTarget,
+      Set<Value> affectedValues,
+      Object state) {
+    optimize(code, instructionIterator, invoke, singleTarget, affectedValues, (T) state);
+  }
+
+  /** Thread local optimization state to allow caching, etc. */
+  interface State {}
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodSideEffectModelCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodSideEffectModelCollection.java
index 55d1dc3..70ace2b 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodSideEffectModelCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/LibraryMethodSideEffectModelCollection.java
@@ -36,6 +36,7 @@
             .put(dexItemFactory.npeMethods.initWithMessage, alwaysTrue())
             .put(dexItemFactory.objectMembers.constructor, alwaysTrue())
             .put(dexItemFactory.objectMembers.getClass, alwaysTrue())
+            .put(dexItemFactory.stringBuilderMethods.toString, alwaysTrue())
             .put(dexItemFactory.stringMembers.hashCode, alwaysTrue());
     putAll(builder, dexItemFactory.classMethods.getNames, alwaysTrue());
     putAll(
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/LogMethodOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/LogMethodOptimizer.java
index f8847d3..aa93f3c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/LogMethodOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/LogMethodOptimizer.java
@@ -17,7 +17,7 @@
 import com.android.tools.r8.shaking.ProguardConfiguration;
 import java.util.Set;
 
-public class LogMethodOptimizer implements LibraryMethodModelCollection {
+public class LogMethodOptimizer extends StatelessLibraryMethodModelCollection {
 
   private static final int VERBOSE = 2;
   private static final int DEBUG = 3;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/NopLibraryMethodModelCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/library/NopLibraryMethodModelCollection.java
index f852393..2eeb165 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/NopLibraryMethodModelCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/NopLibraryMethodModelCollection.java
@@ -13,7 +13,7 @@
 import com.android.tools.r8.ir.code.Value;
 import java.util.Set;
 
-public class NopLibraryMethodModelCollection implements LibraryMethodModelCollection {
+public class NopLibraryMethodModelCollection extends StatelessLibraryMethodModelCollection {
 
   private static final NopLibraryMethodModelCollection INSTANCE =
       new NopLibraryMethodModelCollection();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectMethodOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectMethodOptimizer.java
index f16af45..c325500 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectMethodOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectMethodOptimizer.java
@@ -14,7 +14,7 @@
 import com.android.tools.r8.ir.code.Value;
 import java.util.Set;
 
-public class ObjectMethodOptimizer implements LibraryMethodModelCollection {
+public class ObjectMethodOptimizer extends StatelessLibraryMethodModelCollection {
 
   private final DexItemFactory dexItemFactory;
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectsMethodOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectsMethodOptimizer.java
index 8fcc1ac..9d0c8c8 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectsMethodOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/ObjectsMethodOptimizer.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexItemFactory.ObjectsMethods;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.InstructionListIterator;
@@ -14,12 +15,17 @@
 import com.android.tools.r8.ir.code.Value;
 import java.util.Set;
 
-public class ObjectsMethodOptimizer implements LibraryMethodModelCollection {
+public class ObjectsMethodOptimizer extends StatelessLibraryMethodModelCollection {
 
+  private final AppView<?> appView;
   private final DexItemFactory dexItemFactory;
+  private final ObjectsMethods objectsMethods;
 
   ObjectsMethodOptimizer(AppView<?> appView) {
-    this.dexItemFactory = appView.dexItemFactory();
+    DexItemFactory dexItemFactory = appView.dexItemFactory();
+    this.appView = appView;
+    this.dexItemFactory = dexItemFactory;
+    this.objectsMethods = dexItemFactory.objectsMethods;
   }
 
   @Override
@@ -34,14 +40,16 @@
       InvokeMethod invoke,
       DexClassAndMethod singleTarget,
       Set<Value> affectedValues) {
-    if (dexItemFactory.objectsMethods.isRequireNonNullMethod(singleTarget.getReference())) {
+    if (objectsMethods.isRequireNonNullMethod(singleTarget.getReference())) {
       optimizeRequireNonNull(instructionIterator, invoke, affectedValues);
+    } else if (singleTarget.getReference() == objectsMethods.toStringWithObject) {
+      optimizeToStringWithObject(code, instructionIterator, invoke, affectedValues);
     }
   }
 
   private void optimizeRequireNonNull(
       InstructionListIterator instructionIterator, InvokeMethod invoke, Set<Value> affectedValues) {
-    Value inValue = invoke.inValues().get(0);
+    Value inValue = invoke.getFirstArgument();
     if (inValue.getType().isDefinitelyNotNull()) {
       Value outValue = invoke.outValue();
       if (outValue != null) {
@@ -52,4 +60,18 @@
       instructionIterator.removeOrReplaceByDebugLocalRead();
     }
   }
+
+  private void optimizeToStringWithObject(
+      IRCode code,
+      InstructionListIterator instructionIterator,
+      InvokeMethod invoke,
+      Set<Value> affectedValues) {
+    Value object = invoke.getFirstArgument();
+    if (object.getType().isDefinitelyNull()) {
+      instructionIterator.replaceCurrentInstructionWithConstString(appView, code, "null");
+      if (invoke.hasOutValue()) {
+        affectedValues.addAll(invoke.outValue().affectedValues());
+      }
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/StatelessLibraryMethodModelCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/library/StatelessLibraryMethodModelCollection.java
new file mode 100644
index 0000000..6754170
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/StatelessLibraryMethodModelCollection.java
@@ -0,0 +1,43 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.library;
+
+import com.android.tools.r8.graph.DexClassAndMethod;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.library.StatelessLibraryMethodModelCollection.State;
+import java.util.Set;
+
+public abstract class StatelessLibraryMethodModelCollection
+    implements LibraryMethodModelCollection<State> {
+
+  @Override
+  public final State createInitialState() {
+    return null;
+  }
+
+  public abstract void optimize(
+      IRCode code,
+      InstructionListIterator instructionIterator,
+      InvokeMethod invoke,
+      DexClassAndMethod singleTarget,
+      Set<Value> affectedValues);
+
+  @Override
+  public final void optimize(
+      IRCode code,
+      InstructionListIterator instructionIterator,
+      InvokeMethod invoke,
+      DexClassAndMethod singleTarget,
+      Set<Value> affectedValues,
+      State state) {
+    assert state == null;
+    optimize(code, instructionIterator, invoke, singleTarget, affectedValues);
+  }
+
+  static class State implements LibraryMethodModelCollection.State {}
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/StringBuilderMethodOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/StringBuilderMethodOptimizer.java
new file mode 100644
index 0000000..a88bae9
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/StringBuilderMethodOptimizer.java
@@ -0,0 +1,236 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.library;
+
+import static com.android.tools.r8.ir.code.Opcodes.INVOKE_DIRECT;
+import static com.android.tools.r8.ir.code.Opcodes.INVOKE_VIRTUAL;
+import static com.android.tools.r8.ir.code.Opcodes.NEW_INSTANCE;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClassAndMethod;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexItemFactory.StringBuildingMethods;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeDirect;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.library.StringBuilderMethodOptimizer.State;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Sets;
+import it.unimi.dsi.fastutil.objects.Reference2BooleanMap;
+import it.unimi.dsi.fastutil.objects.Reference2BooleanOpenHashMap;
+import java.util.Set;
+
+public class StringBuilderMethodOptimizer implements LibraryMethodModelCollection<State> {
+
+  private final DexItemFactory dexItemFactory;
+  private final InternalOptions options;
+  private final StringBuildingMethods stringBuilderMethods;
+
+  StringBuilderMethodOptimizer(AppView<?> appView) {
+    DexItemFactory dexItemFactory = appView.dexItemFactory();
+    this.dexItemFactory = dexItemFactory;
+    this.options = appView.options();
+    this.stringBuilderMethods = dexItemFactory.stringBuilderMethods;
+  }
+
+  @Override
+  public State createInitialState() {
+    return new State();
+  }
+
+  @Override
+  public DexType getType() {
+    return dexItemFactory.stringBuilderType;
+  }
+
+  @Override
+  public void optimize(
+      IRCode code,
+      InstructionListIterator instructionIterator,
+      InvokeMethod invoke,
+      DexClassAndMethod singleTarget,
+      Set<Value> affectedValues,
+      State state) {
+    if (invoke.isInvokeMethodWithReceiver()) {
+      InvokeMethodWithReceiver invokeWithReceiver = invoke.asInvokeMethodWithReceiver();
+      if (stringBuilderMethods.isAppendMethod(singleTarget.getReference())) {
+        optimizeAppend(instructionIterator, invokeWithReceiver, singleTarget, state);
+      }
+    }
+  }
+
+  private void optimizeAppend(
+      InstructionListIterator instructionIterator,
+      InvokeMethodWithReceiver invoke,
+      DexClassAndMethod singleTarget,
+      State state) {
+    if (!state.isUnusedBuilder(invoke.getReceiver())) {
+      return;
+    }
+    if (invoke.hasOutValue()) {
+      invoke.outValue().replaceUsers(invoke.getReceiver());
+    }
+    DexMethod appendMethod = singleTarget.getReference();
+    if (stringBuilderMethods.isAppendPrimitiveMethod(appendMethod)
+        || stringBuilderMethods.isAppendStringMethod(appendMethod)) {
+      instructionIterator.removeOrReplaceByDebugLocalRead();
+    } else if (stringBuilderMethods.isAppendObjectMethod(appendMethod)) {
+      Value object = invoke.getArgument(1);
+      if (object.isNeverNull()) {
+        instructionIterator.replaceCurrentInstruction(
+            InvokeVirtual.builder()
+                .setSingleArgument(object)
+                .setMethod(dexItemFactory.objectMembers.toString)
+                .build());
+      } else if (options.canUseJavaUtilObjects()) {
+        instructionIterator.replaceCurrentInstruction(
+            InvokeStatic.builder()
+                .setSingleArgument(object)
+                .setMethod(dexItemFactory.objectsMethods.toStringWithObject)
+                .build());
+        // Allow the java.util.Objects optimizer to optimize the newly added toString().
+        instructionIterator.previous();
+      }
+    }
+  }
+
+  class State implements LibraryMethodModelCollection.State {
+
+    final Reference2BooleanMap<Value> unusedBuilders = new Reference2BooleanOpenHashMap<>();
+
+    boolean isUnusedBuilder(Value value) {
+      if (!unusedBuilders.containsKey(value)) {
+        computeIsUnusedBuilder(value);
+        assert unusedBuilders.containsKey(value);
+      }
+      return unusedBuilders.getBoolean(value);
+    }
+
+    private void computeIsUnusedBuilder(Value value) {
+      assert !unusedBuilders.containsKey(value);
+
+      Set<Value> aliases = Sets.newIdentityHashSet();
+      boolean isUnused = computeAllAliasesIfUnusedStringBuilder(value, aliases);
+      aliases.forEach(alias -> unusedBuilders.put(alias, isUnused));
+    }
+
+    /**
+     * Adds all the aliases of the given StringBuilder value to {@param aliases}, or returns false
+     * if all aliases were not found (e.g., due to a phi user).
+     */
+    private boolean computeAllAliasesIfUnusedStringBuilder(Value value, Set<Value> aliases) {
+      WorkList<Value> worklist = WorkList.newIdentityWorkList(value);
+      while (worklist.hasNext()) {
+        Value alias = worklist.next();
+        aliases.add(alias);
+
+        if (unusedBuilders.containsKey(alias)) {
+          assert !unusedBuilders.getBoolean(alias);
+          return false;
+        }
+
+        // Don't track phi aliases.
+        if (alias.hasPhiUsers()) {
+          return false;
+        }
+
+        // Analyze root, if any.
+        if (alias.isPhi()) {
+          return false;
+        }
+
+        Instruction definition = alias.definition;
+        switch (definition.opcode()) {
+          case NEW_INSTANCE:
+            assert definition.asNewInstance().clazz == dexItemFactory.stringBuilderType;
+            break;
+
+          case INVOKE_VIRTUAL:
+            {
+              InvokeVirtual invoke = definition.asInvokeVirtual();
+              if (!stringBuilderMethods.isAppendMethod(invoke.getInvokedMethod())) {
+                // Unhandled definition.
+                return false;
+              }
+              worklist.addIfNotSeen(invoke.getReceiver());
+            }
+            break;
+
+          default:
+            // Unhandled definition.
+            return false;
+        }
+
+        // Analyze all users.
+        for (Instruction user : alias.uniqueUsers()) {
+          switch (user.opcode()) {
+            case INVOKE_DIRECT:
+              {
+                InvokeDirect invoke = user.asInvokeDirect();
+
+                // Only allow invokes where the string builder value is the receiver.
+                if (invoke.arguments().lastIndexOf(alias) > 0) {
+                  return false;
+                }
+
+                // Only allow invoke-direct instructions that target the string builder constructor.
+                if (!stringBuilderMethods.isConstructorMethod(invoke.getInvokedMethod())) {
+                  return false;
+                }
+              }
+              break;
+
+            case INVOKE_VIRTUAL:
+              {
+                InvokeVirtual invoke = user.asInvokeVirtual();
+
+                // Only allow invokes where the string builder value is the receiver.
+                if (invoke.arguments().lastIndexOf(alias) > 0) {
+                  return false;
+                }
+
+                DexMethod invokedMethod = invoke.getInvokedMethod();
+
+                // Allow calls to append(), but make sure to introduce the newly introduced alias,
+                // if append() has an out-value.
+                if (stringBuilderMethods.isAppendMethod(invokedMethod)) {
+                  if (invoke.hasOutValue()) {
+                    worklist.addIfNotSeen(invoke.outValue());
+                  }
+                  break;
+                }
+
+                // Allow calls to toString().
+                if (invokedMethod == stringBuilderMethods.toString) {
+                  // Only allow unused StringBuilders.
+                  if (invoke.hasOutValue() && invoke.outValue().hasNonDebugUsers()) {
+                    return false;
+                  }
+                  break;
+                }
+
+                // Invoke to unhandled method, give up.
+                return false;
+              }
+
+            default:
+              // Unhandled user, give up.
+              return false;
+          }
+        }
+      }
+      return true;
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/StringMethodOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/library/StringMethodOptimizer.java
index 18ad3e6..c8d04ae 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/StringMethodOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/StringMethodOptimizer.java
@@ -18,7 +18,7 @@
 import com.android.tools.r8.ir.code.Value;
 import java.util.Set;
 
-public class StringMethodOptimizer implements LibraryMethodModelCollection {
+public class StringMethodOptimizer extends StatelessLibraryMethodModelCollection {
 
   private final AppView<?> appView;
   private final DexItemFactory dexItemFactory;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
index cd9fe4e..a61662c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
@@ -30,6 +30,7 @@
 import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
 import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.NewInstance;
 import com.android.tools.r8.ir.code.NumberConversion;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueType;
@@ -215,10 +216,9 @@
     private Set<Value> findAllLocalBuilders() {
       // During the first iteration, collect builders that are locally created.
       // TODO(b/114002137): Make sure new-instance is followed by <init> before any other calls.
-      for (Instruction instr : code.instructions()) {
-        if (instr.isNewInstance()
-            && optimizationConfiguration.isBuilderType(instr.asNewInstance().clazz)) {
-          Value builder = instr.asNewInstance().dest();
+      for (NewInstance newInstance : code.<NewInstance>instructions(Instruction::isNewInstance)) {
+        if (optimizationConfiguration.isBuilderType(newInstance.clazz)) {
+          Value builder = newInstance.asNewInstance().dest();
           assert !builderToStringCounts.containsKey(builder);
           builderToStringCounts.put(builder, 0);
         }
@@ -228,24 +228,21 @@
       }
       int concatenationCount = 0;
       // During the second iteration, count builders' usage.
-      for (Instruction instr : code.instructions()) {
-        if (instr.isInvokeMethod()) {
-          InvokeMethod invoke = instr.asInvokeMethod();
-          DexMethod invokedMethod = invoke.getInvokedMethod();
-          if (optimizationConfiguration.isAppendMethod(invokedMethod)) {
-            concatenationCount++;
-            // The analysis might be overwhelmed.
-            if (concatenationCount > CONCATENATION_THRESHOLD) {
-              return ImmutableSet.of();
-            }
-          } else if (optimizationConfiguration.isToStringMethod(invokedMethod)) {
-            assert invoke.arguments().size() == 1;
-            Value receiver = invoke.getArgument(0).getAliasedValue();
-            for (Value builder : collectAllLinkedBuilders(receiver)) {
-              if (builderToStringCounts.containsKey(builder)) {
-                int count = builderToStringCounts.getInt(builder);
-                builderToStringCounts.put(builder, count + 1);
-              }
+      for (InvokeMethod invoke : code.<InvokeMethod>instructions(Instruction::isInvokeMethod)) {
+        DexMethod invokedMethod = invoke.getInvokedMethod();
+        if (optimizationConfiguration.isAppendMethod(invokedMethod)) {
+          concatenationCount++;
+          // The analysis might be overwhelmed.
+          if (concatenationCount > CONCATENATION_THRESHOLD) {
+            return ImmutableSet.of();
+          }
+        } else if (optimizationConfiguration.isToStringMethod(invokedMethod)) {
+          assert invoke.arguments().size() == 1;
+          Value receiver = invoke.getArgument(0).getAliasedValue();
+          for (Value builder : collectAllLinkedBuilders(receiver)) {
+            if (builderToStringCounts.containsKey(builder)) {
+              int count = builderToStringCounts.getInt(builder);
+              builderToStringCounts.put(builder, count + 1);
             }
           }
         }
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index fb8655a..239c409 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -1587,6 +1587,10 @@
     return intermediate || hasMinApi(AndroidApiLevel.L);
   }
 
+  public boolean canUseJavaUtilObjects() {
+    return (isGeneratingClassFiles() && !cfToCfDesugar) || hasMinApi(AndroidApiLevel.K);
+  }
+
   public boolean canUseRequireNonNull() {
     return isGeneratingDex() && hasMinApi(AndroidApiLevel.K);
   }
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index 7f140a7..e1d4c9e 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -1702,6 +1702,11 @@
     return AndroidApiLevel.L;
   }
 
+  public static boolean canUseJavaUtilObjects(TestParameters parameters) {
+    return parameters.isCfRuntime()
+        || parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.K);
+  }
+
   public static boolean canUseRequireNonNull(TestParameters parameters) {
     return parameters.isDexRuntime()
         && parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.K);
diff --git a/src/test/java/com/android/tools/r8/debuginfo/CannonicalizeWithInline.java b/src/test/java/com/android/tools/r8/debuginfo/CanonicalizeWithInline.java
similarity index 61%
rename from src/test/java/com/android/tools/r8/debuginfo/CannonicalizeWithInline.java
rename to src/test/java/com/android/tools/r8/debuginfo/CanonicalizeWithInline.java
index ff58696..395f29f 100644
--- a/src/test/java/com/android/tools/r8/debuginfo/CannonicalizeWithInline.java
+++ b/src/test/java/com/android/tools/r8/debuginfo/CanonicalizeWithInline.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.debuginfo;
 
+import com.android.tools.r8.AssumeMayHaveSideEffects;
+import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.OutputMode;
 import com.android.tools.r8.R8TestCompileResult;
 import com.android.tools.r8.TestBase;
@@ -15,7 +17,7 @@
 import org.junit.Assert;
 import org.junit.Test;
 
-public class CannonicalizeWithInline extends TestBase {
+public class CanonicalizeWithInline extends TestBase {
 
   private int getNumberOfDebugInfos(Path file) throws IOException {
     DexSection[] dexSections = DexParser.parseMapFrom(file);
@@ -28,25 +30,23 @@
   }
 
   @Test
-  public void testCannonicalize() throws Exception {
-    Class clazzA = ClassA.class;
-    Class clazzB = ClassB.class;
+  public void testCanonicalize() throws Exception {
+    Class<?> clazzA = ClassA.class;
+    Class<?> clazzB = ClassB.class;
 
-    R8TestCompileResult result = testForR8(Backend.DEX)
-        .addProgramClasses(clazzA, clazzB)
-        .addKeepRules(
-            "-keepattributes SourceFile,LineNumberTable",
-            "-keep class ** {\n" +
-                "public void call(int);\n" +
-            "}"
-        )
-        // String concatenation optimization will remove dead builders in foobar.
-        .addOptionsModification(o -> o.enableStringConcatenationOptimization = false)
-        .compile();
+    R8TestCompileResult result =
+        testForR8(Backend.DEX)
+            .addProgramClasses(clazzA, clazzB)
+            .addKeepRules(
+                "-keepattributes SourceFile,LineNumberTable",
+                "-keep class ** {\n" + "public void call(int);\n" + "}")
+            .enableInliningAnnotations()
+            .enableSideEffectAnnotations()
+            .compile();
     Path classesPath = temp.getRoot().toPath();
     result.app.write(classesPath, OutputMode.DexIndexed);
-    int numberOfDebugInfos = getNumberOfDebugInfos(
-        Paths.get(temp.getRoot().getCanonicalPath(), "classes.dex"));
+    int numberOfDebugInfos =
+        getNumberOfDebugInfos(Paths.get(temp.getRoot().getCanonicalPath(), "classes.dex"));
     Assert.assertEquals(1, numberOfDebugInfos);
   }
 
@@ -57,11 +57,17 @@
   public static class ClassA {
 
     public void call(int a) {
-        foobar(a);
+      foobar(a);
     }
 
     private String foobar(int a) {
-      String s = "aFoobar" + a;
+      return doSomething(a);
+    }
+
+    @AssumeMayHaveSideEffects
+    @NeverInline
+    private String doSomething(int a) {
+      String s = "bFoobar" + a;
       return s;
     }
   }
@@ -73,6 +79,12 @@
     }
 
     private String foobar(int a) {
+      return doSomething(a);
+    }
+
+    @AssumeMayHaveSideEffects
+    @NeverInline
+    private String doSomething(int a) {
       String s = "bFoobar" + a;
       return s;
     }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderFromCharSequenceWithAppendObjectTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderFromCharSequenceWithAppendObjectTest.java
new file mode 100644
index 0000000..46dfe04
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderFromCharSequenceWithAppendObjectTest.java
@@ -0,0 +1,74 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.string;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class UnusedStringBuilderFromCharSequenceWithAppendObjectTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public UnusedStringBuilderFromCharSequenceWithAppendObjectTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithEmptyOutput();
+    // TODO(christofferqa): Should succeed with output;
+    //  .assertSuccessWithOutputLines(
+    //      "CustomCharSequence.length()",
+    //      "CustomCharSequence.length()",
+    //      "CustomCharSequence.length()",
+    //      "CustomCharSequence.charAt(0)");
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      new StringBuilder(new CustomCharSequence());
+    }
+  }
+
+  static class CustomCharSequence implements CharSequence {
+
+    @Override
+    public int length() {
+      System.out.println("CustomCharSequence.length()");
+      return 1;
+    }
+
+    @Override
+    public char charAt(int i) {
+      if (i != 0) {
+        throw new RuntimeException();
+      }
+      System.out.println("CustomCharSequence.charAt(0)");
+      return 0;
+    }
+
+    @Override
+    public CharSequence subSequence(int i, int i1) {
+      throw new RuntimeException();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendDefinitelyNullObjectTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendDefinitelyNullObjectTest.java
new file mode 100644
index 0000000..f5f615d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendDefinitelyNullObjectTest.java
@@ -0,0 +1,58 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.string;
+
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.instantiatesClass;
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithName;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class UnusedStringBuilderWithAppendDefinitelyNullObjectTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public UnusedStringBuilderWithAppendDefinitelyNullObjectTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              MethodSubject mainMethod = inspector.clazz(Main.class).mainMethod();
+              assertThat(mainMethod, not(instantiatesClass(StringBuilder.class)));
+              assertThat(mainMethod, not(invokesMethodWithName("toString")));
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithEmptyOutput();
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      Object o = null;
+      new StringBuilder().append(o).toString();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendMaybeNullObjectTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendMaybeNullObjectTest.java
new file mode 100644
index 0000000..7d23755
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendMaybeNullObjectTest.java
@@ -0,0 +1,66 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.string;
+
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.instantiatesClass;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class UnusedStringBuilderWithAppendMaybeNullObjectTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public UnusedStringBuilderWithAppendMaybeNullObjectTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              MethodSubject mainMethod = inspector.clazz(Main.class).mainMethod();
+              assertThat(
+                  mainMethod,
+                  notIf(instantiatesClass(StringBuilder.class), canUseJavaUtilObjects(parameters)));
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithEmptyOutput();
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      A a = System.currentTimeMillis() < 0 ? new A() : null;
+      new StringBuilder().append(a).toString();
+    }
+  }
+
+  static class A {
+
+    @Override
+    public String toString() {
+      return "A";
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendObjectSideEffectTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendObjectSideEffectTest.java
new file mode 100644
index 0000000..934dfd2
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendObjectSideEffectTest.java
@@ -0,0 +1,64 @@
+// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.string;
+
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.instantiatesClass;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class UnusedStringBuilderWithAppendObjectSideEffectTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public UnusedStringBuilderWithAppendObjectSideEffectTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              MethodSubject mainMethod = inspector.clazz(Main.class).mainMethod();
+              assertThat(mainMethod, not(instantiatesClass(StringBuilder.class)));
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("A");
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      new StringBuilder().append(new A()).toString();
+    }
+  }
+
+  static class A {
+
+    @Override
+    public String toString() {
+      System.out.println("A");
+      return "A";
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendObjectTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendObjectTest.java
index 25918c8..72c3721 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendObjectTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/UnusedStringBuilderWithAppendObjectTest.java
@@ -4,12 +4,14 @@
 
 package com.android.tools.r8.ir.optimize.string;
 
-import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithName;
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.instantiatesClass;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
 import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -36,10 +38,12 @@
         .setMinApi(parameters.getApiLevel())
         .compile()
         .inspect(
-            inspector ->
-                // TODO(b/174285670): StringBuilder should be removed.
-                assertThat(
-                    inspector.clazz(Main.class).mainMethod(), invokesMethodWithName("append")))
+            inspector -> {
+              MethodSubject mainMethod = inspector.clazz(Main.class).mainMethod();
+              assertThat(
+                  mainMethod,
+                  notIf(instantiatesClass(StringBuilder.class), canUseJavaUtilObjects(parameters)));
+            })
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithEmptyOutput();
   }
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
index fa7b74e..986312c 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
@@ -73,6 +73,12 @@
     }
 
     @Override
+    public void replaceCurrentInstructionWithConstString(
+        AppView<?> appView, IRCode code, DexString value) {
+      throw new Unimplemented();
+    }
+
+    @Override
     public void replaceCurrentInstructionWithStaticGet(
         AppView<?> appView, IRCode code, DexField field, Set<Value> affectedValues) {
       throw new Unimplemented();
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java
index ed4d158..654f3a1 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java
@@ -44,6 +44,37 @@
     };
   }
 
+  public static Matcher<MethodSubject> instantiatesClass(Class<?> clazz) {
+    return instantiatesClass(clazz.getTypeName());
+  }
+
+  public static Matcher<MethodSubject> instantiatesClass(String clazz) {
+    return new TypeSafeMatcher<MethodSubject>() {
+      @Override
+      protected boolean matchesSafely(MethodSubject subject) {
+        if (!subject.isPresent()) {
+          return false;
+        }
+        if (!subject.getMethod().hasCode()) {
+          return false;
+        }
+        return subject
+            .streamInstructions()
+            .anyMatch(instruction -> instruction.isNewInstance(clazz));
+      }
+
+      @Override
+      public void describeTo(Description description) {
+        description.appendText("instantiates class `" + clazz + "`");
+      }
+
+      @Override
+      public void describeMismatchSafely(final MethodSubject subject, Description description) {
+        description.appendText("method did not");
+      }
+    };
+  }
+
   public static Matcher<MethodSubject> invokesMethod(MethodSubject targetSubject) {
     if (!targetSubject.isPresent()) {
       throw new IllegalArgumentException();