diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
index 830516e..2606826 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
@@ -26,6 +26,7 @@
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
+import com.android.tools.r8.ir.code.InvokeStatic;
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.AppendNode;
@@ -262,7 +263,7 @@
               assert newInstanceValue != null;
               nodeConsumer.accept(
                   newInstanceValue, createNewInstanceNode(instruction.asNewInstance()));
-            } else {
+            } else if (instruction.isInvokeMethodWithReceiver()) {
               InvokeMethodWithReceiver invoke = instruction.asInvokeMethodWithReceiver();
               Value receiver = invoke.getReceiver();
               if (oracle.isInit(instruction)) {
@@ -316,6 +317,17 @@
                     escaped ->
                         nodeConsumer.accept(escaped, createOtherStringBuilderNode(instruction)));
               }
+            } else {
+              assert instruction.isInvokeStatic();
+              InvokeStatic invoke = instruction.asInvokeStatic();
+              assert invoke.getInvokedMethod()
+                  == appView.dexItemFactory().objectsMethods.toStringWithObject;
+              visitStringBuilderValues(
+                  invoke.getFirstOperand(),
+                  escapeState,
+                  actual ->
+                      nodeConsumer.accept(actual, createToStringNode(instruction.asInvokeMethod())),
+                  escaped -> nodeConsumer.accept(escaped, createInspectionNode(instruction)));
             }
           }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java
index bc92a0f..e2d46af 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java
@@ -63,7 +63,8 @@
       }
     }
     if (isStringBuilderInstruction) {
-      if (instruction.isInvokeMethodWithReceiver()) {
+      if (instruction.isInvokeMethod()) {
+        assert !instruction.inValues().isEmpty();
         Value firstOperand = instruction.getFirstOperand();
         if (!builder.getLiveStringBuilders().contains(firstOperand)) {
           // We can have constant NULL being the first operand, which we have not marked as
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNode.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNode.java
index 22d5c70..c189299 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNode.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNode.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InvokeDirect;
+import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.NewInstance;
 import com.google.common.collect.Sets;
@@ -426,9 +427,9 @@
    */
   static class ToStringNode extends StringBuilderNode implements StringBuilderInstruction {
 
-    private final InvokeVirtual instruction;
+    private final InvokeMethod instruction;
 
-    private ToStringNode(InvokeVirtual instruction) {
+    private ToStringNode(InvokeMethod instruction) {
       this.instruction = instruction;
     }
 
@@ -534,7 +535,7 @@
   }
 
   /**
-   * ImplicitToStringNode are placed a StringBuilder/StringBuffer is appended to another
+   * ImplicitToStringNode are placed when StringBuilder/StringBuffer is appended to another
    * StringBuilder/StringBuffer.
    */
   static class ImplicitToStringNode extends StringBuilderNode {
@@ -588,7 +589,7 @@
     return new AppendNode(instruction);
   }
 
-  static ToStringNode createToStringNode(InvokeVirtual instruction) {
+  static ToStringNode createToStringNode(InvokeMethod instruction) {
     return new ToStringNode(instruction);
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java
index dd49ae4..d7d7f59 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java
@@ -61,7 +61,8 @@
             || isStringBuildingMethod(factory.stringBufferMethods, invokedMethod)) {
           return true;
         }
-        return invokedMethod == factory.objectMembers.toString
+        return (invokedMethod == factory.objectMembers.toString
+                || invokedMethod == factory.objectsMethods.toStringWithObject)
             && isLiveStringBuilder.test(instruction.getFirstOperand());
       }
       return false;
@@ -87,17 +88,20 @@
 
     @Override
     public boolean isToString(Instruction instruction, Value value) {
-      if (!instruction.isInvokeVirtual()) {
+      if (!instruction.isInvokeMethod()) {
         return false;
       }
-      InvokeVirtual invoke = instruction.asInvokeVirtual();
-      if (invoke.getReceiver() != value) {
+      if (instruction.inValues().isEmpty()) {
         return false;
       }
-      DexMethod invokedMethod = invoke.getInvokedMethod();
+      if (instruction.getFirstOperand() != value) {
+        return false;
+      }
+      DexMethod invokedMethod = instruction.asInvokeMethod().getInvokedMethod();
       return factory.stringBuilderMethods.toString == invokedMethod
           || factory.stringBufferMethods.toString == invokedMethod
-          || factory.objectMembers.toString == invokedMethod;
+          || factory.objectMembers.toString == invokedMethod
+          || factory.objectsMethods.toStringWithObject == invokedMethod;
     }
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithObjectsToStringTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithObjectsToStringTest.java
index 9b7594b..4013021 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithObjectsToStringTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithObjectsToStringTest.java
@@ -42,9 +42,9 @@
             inspector -> {
               MethodSubject mainMethodSubject = inspector.clazz(Main.class).mainMethod();
               assertThat(mainMethodSubject, isPresent());
-              // TODO(b/219455761): Extend StringBuilder optimizer to Objects.toString().
+              // TODO(b/114002137): Also run for CF
               assertEquals(
-                  canUseJavaUtilObjects(parameters),
+                  parameters.isCfRuntime(),
                   mainMethodSubject
                       .streamInstructions()
                       .anyMatch(InstructionSubject::isNewInstance));