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 8fe1c7e..44506fd 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -2118,7 +2118,7 @@
     }
 
     public boolean isAppendCharSequenceMethod(DexMethod method) {
-      return method == appendCharSequence;
+      return method == appendCharSequence || method == appendSubCharSequence;
     }
 
     public boolean isAppendObjectOrCharSequenceMethod(DexMethod method) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAction.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAction.java
index 05a91e5..4383519 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAction.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAction.java
@@ -7,6 +7,8 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.ir.analysis.type.Nullability;
+import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
@@ -102,28 +104,7 @@
       Instruction previous = iterator.previous();
       InvokeMethodWithReceiver invoke = previous.asInvokeMethodWithReceiver();
       assert invoke != null;
-      // If the block has catch handlers, inserting a constant string in the same block as the
-      // append violates our block representation in DEX since constant string is throwing. If the
-      // append is in a block with catch handlers, we simply insert a new constant string in the
-      // entry block after all arguments.
-      Value value;
-      if (!invoke.getBlock().hasCatchHandlers()) {
-        value =
-            iterator.insertConstStringInstruction(
-                appView, code, appView.dexItemFactory().createString(replacement));
-      } else {
-        InstructionListIterator stringInsertIterator = code.entryBlock().listIterator(code);
-        while (stringInsertIterator.hasNext()) {
-          Instruction next = stringInsertIterator.next();
-          if (!next.isArgument()) {
-            stringInsertIterator.previous();
-            break;
-          }
-        }
-        value =
-            stringInsertIterator.insertConstStringInstruction(
-                appView, code, appView.dexItemFactory().createString(replacement));
-      }
+      Value value = insertStringConstantInstruction(appView, code, iterator, invoke, replacement);
       iterator.next();
       DexMethod invokedMethod = invoke.getInvokedMethod();
       if (invoke.isInvokeConstructor(appView.dexItemFactory())) {
@@ -151,16 +132,6 @@
           || factory.stringBuilderMethods.isAppendStringMethod(method);
     }
 
-    private DexMethod getConstructorWithStringParameter(
-        DexMethod invokedMethod, DexItemFactory factory) {
-      if (invokedMethod.getHolderType() == factory.stringBufferType) {
-        return factory.stringBufferMethods.stringConstructor;
-      } else {
-        assert invokedMethod.getHolderType() == factory.stringBuilderType;
-        return factory.stringBuilderMethods.stringConstructor;
-      }
-    }
-
     private DexMethod getAppendWithStringParameter(
         DexMethod invokedMethod, DexItemFactory factory) {
       if (invokedMethod.getHolderType() == factory.stringBufferType) {
@@ -171,4 +142,128 @@
       }
     }
   }
+
+  class ReplaceByExistingString implements StringBuilderAction {
+
+    private final Value existingString;
+
+    public ReplaceByExistingString(Value existingString) {
+      assert existingString.isNeverNull();
+      this.existingString = existingString;
+    }
+
+    @Override
+    public void perform(
+        AppView<?> appView,
+        IRCode code,
+        InstructionListIterator iterator,
+        Instruction instruction,
+        StringBuilderOracle oracle) {
+      instruction.outValue().replaceUsers(existingString);
+      iterator.removeOrReplaceByDebugLocalRead();
+    }
+  }
+
+  class ReplaceByStringConcat implements StringBuilderAction {
+
+    private final Value first;
+    private final Value second;
+
+    private final String newConstant;
+
+    private ReplaceByStringConcat(Value first, Value second, String newConstant) {
+      assert first != null || newConstant != null;
+      assert second != null || newConstant != null;
+      this.first = first;
+      this.second = second;
+      this.newConstant = newConstant;
+    }
+
+    public static ReplaceByStringConcat replaceByValues(Value first, Value second) {
+      return new ReplaceByStringConcat(first, second, null);
+    }
+
+    public static ReplaceByStringConcat replaceByNewConstantConcatValue(
+        String newConstant, Value second) {
+      return new ReplaceByStringConcat(null, second, newConstant);
+    }
+
+    public static ReplaceByStringConcat replaceByValueConcatNewConstant(
+        Value first, String newConstant) {
+      return new ReplaceByStringConcat(first, null, newConstant);
+    }
+
+    @Override
+    public void perform(
+        AppView<?> appView,
+        IRCode code,
+        InstructionListIterator iterator,
+        Instruction instruction,
+        StringBuilderOracle oracle) {
+      Value constString = null;
+      if (newConstant != null) {
+        Instruction previous = iterator.previous();
+        constString =
+            insertStringConstantInstruction(appView, code, iterator, previous, newConstant);
+        iterator.next();
+      }
+      assert first != null || constString != null;
+      assert second != null || constString != null;
+      // To ensure that we do not fail narrowing when evaluating String.concat, we mark the type
+      // as maybe null.
+      Value newOutValue =
+          code.createValue(
+              TypeElement.stringClassType(appView, Nullability.maybeNull()),
+              instruction.getLocalInfo());
+      iterator.replaceCurrentInstruction(
+          InvokeVirtual.builder()
+              .setOutValue(newOutValue)
+              .setMethod(appView.dexItemFactory().stringMembers.concat)
+              .setArguments(
+                  ImmutableList.of(
+                      first != null ? first : constString, second != null ? second : constString))
+              .build());
+    }
+  }
+
+  static DexMethod getConstructorWithStringParameter(
+      DexMethod invokedMethod, DexItemFactory factory) {
+    if (invokedMethod.getHolderType() == factory.stringBufferType) {
+      return factory.stringBufferMethods.stringConstructor;
+    } else {
+      assert invokedMethod.getHolderType() == factory.stringBuilderType;
+      return factory.stringBuilderMethods.stringConstructor;
+    }
+  }
+
+  static Value insertStringConstantInstruction(
+      AppView<?> appView,
+      IRCode code,
+      InstructionListIterator iterator,
+      Instruction instruction,
+      String newString) {
+    // If the block has catch handlers, inserting a constant string in the same block as the
+    // append violates our block representation in DEX since constant string is throwing. If the
+    // append is in a block with catch handlers, we simply insert a new constant string in the
+    // entry block after all arguments.
+    Value value;
+    if (!instruction.getBlock().hasCatchHandlers()) {
+      value =
+          iterator.insertConstStringInstruction(
+              appView, code, appView.dexItemFactory().createString(newString));
+    } else {
+      InstructionListIterator stringInsertIterator = code.entryBlock().listIterator(code);
+      while (stringInsertIterator.hasNext()) {
+        Instruction next = stringInsertIterator.next();
+        if (!next.isArgument()) {
+          stringInsertIterator.previous();
+          break;
+        }
+      }
+      value =
+          stringInsertIterator.insertConstStringInstruction(
+              appView, code, appView.dexItemFactory().createString(newString));
+    }
+    return value;
+  }
 }
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 ee85c13..93c004f 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
@@ -33,7 +33,7 @@
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.EscapeNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.ImplicitToStringNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitNode;
-import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitOrAppend;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitOrAppendNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.LoopNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.NewInstanceNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.SplitReferenceNode;
@@ -273,7 +273,13 @@
               Value receiver = invoke.getReceiver();
               if (oracle.isInit(instruction)) {
                 InitNode initNode = createInitNode(instruction.asInvokeDirect());
-                initNode.setConstantArgument(oracle.getConstantArgument(instruction));
+                String constantArgument = oracle.getConstantArgument(instruction);
+                initNode.setConstantArgument(constantArgument);
+                if (constantArgument == null
+                    && oracle.isStringConstructor(instruction)
+                    && invoke.getFirstNonReceiverArgument().isNeverNull()) {
+                  initNode.setNonConstantArgument(invoke.getFirstNonReceiverArgument());
+                }
                 if (invoke.arguments().size() == 2) {
                   Value arg = invoke.getOperand(1);
                   if (oracle.hasStringBuilderType(arg)) {
@@ -288,9 +294,15 @@
                     escaped -> nodeConsumer.accept(escaped, createInspectionNode(instruction)));
               } else if (oracle.isAppend(instruction)) {
                 AppendNode appendNode = createAppendNode(instruction.asInvokeVirtual());
-                appendNode.setConstantArgument(oracle.getConstantArgument(instruction));
-                Value arg = invoke.getFirstNonReceiverArgument().getAliasedValue();
-                if (oracle.hasStringBuilderType(arg)) {
+                String constantArgument = oracle.getConstantArgument(instruction);
+                appendNode.setConstantArgument(constantArgument);
+                Value arg = invoke.getFirstNonReceiverArgument();
+                if (constantArgument == null
+                    && oracle.isAppendString(instruction)
+                    && arg.isNeverNull()) {
+                  appendNode.setNonConstantArgument(arg);
+                }
+                if (oracle.hasStringBuilderType(arg.getAliasedValue())) {
                   insertImplicitToStringNode(
                       arg, instruction, appendNode, escapeState, nodeConsumer);
                 }
@@ -341,7 +353,7 @@
           private void insertImplicitToStringNode(
               Value value,
               Instruction instruction,
-              InitOrAppend node,
+              InitOrAppendNode node,
               StringBuilderEscapeState escapeState,
               BiConsumer<Value, StringBuilderNode> nodeConsumer) {
             assert escapeState.isLiveStringBuilder(value);
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 c189299..5e01833 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
@@ -9,6 +9,7 @@
 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.android.tools.r8.ir.code.Value;
 import com.google.common.collect.Sets;
 import java.util.Set;
 
@@ -27,7 +28,15 @@
     StringBuilderInstruction asStringBuilderInstructionNode();
   }
 
-  interface InitOrAppend extends StringBuilderInstruction {
+  interface InitOrAppendNode extends StringBuilderInstruction {
+
+    boolean isInitNode();
+
+    boolean isAppendNode();
+
+    InitNode asInitNode();
+
+    AppendNode asAppendNode();
 
     boolean hasConstantArgument();
 
@@ -38,6 +47,22 @@
     void setImplicitToStringNode(ImplicitToStringNode node);
 
     ImplicitToStringNode getImplicitToStringNode();
+
+    boolean hasNonConstantArgument();
+
+    Value getNonConstantArgument();
+
+    default boolean hasConstantOrNonConstantArgument() {
+      return hasConstantArgument() || hasNonConstantArgument();
+    }
+
+    boolean hasSingleSuccessor();
+
+    boolean hasSinglePredecessor();
+
+    StringBuilderNode getSingleSuccessor();
+
+    StringBuilderNode getSinglePredecessor();
   }
 
   private final Set<StringBuilderNode> successors = Sets.newLinkedHashSet();
@@ -69,11 +94,11 @@
     return false;
   }
 
-  boolean isInitNode() {
+  public boolean isInitNode() {
     return false;
   }
 
-  boolean isAppendNode() {
+  public boolean isAppendNode() {
     return false;
   }
 
@@ -105,15 +130,15 @@
     return null;
   }
 
-  InitNode asInitNode() {
+  public InitNode asInitNode() {
     return null;
   }
 
-  AppendNode asAppendNode() {
+  public AppendNode asAppendNode() {
     return null;
   }
 
-  InitOrAppend asInitOrAppend() {
+  InitOrAppendNode asInitOrAppend() {
     return null;
   }
 
@@ -141,11 +166,11 @@
     return isDead;
   }
 
-  boolean hasSingleSuccessor() {
+  public boolean hasSingleSuccessor() {
     return successors.size() == 1;
   }
 
-  StringBuilderNode getSingleSuccessor() {
+  public StringBuilderNode getSingleSuccessor() {
     assert hasSingleSuccessor();
     return successors.iterator().next();
   }
@@ -159,11 +184,11 @@
     return successors;
   }
 
-  boolean hasSinglePredecessor() {
+  public boolean hasSinglePredecessor() {
     return predecessors.size() == 1;
   }
 
-  StringBuilderNode getSinglePredecessor() {
+  public StringBuilderNode getSinglePredecessor() {
     assert hasSinglePredecessor();
     return predecessors.iterator().next();
   }
@@ -278,18 +303,19 @@
 
   /** An initNode is where a StringBuilder/StringBuffer is initialized. */
   static class InitNode extends StringBuilderNode
-      implements InitOrAppend, StringBuilderInstruction {
+      implements InitOrAppendNode, StringBuilderInstruction {
 
     private final InvokeDirect instruction;
     private ImplicitToStringNode implicitToStringNode;
     private String constantArgument;
+    private Value nonConstantArgument;
 
     private InitNode(InvokeDirect instruction) {
       this.instruction = instruction;
     }
 
     @Override
-    boolean isInitNode() {
+    public boolean isInitNode() {
       return true;
     }
 
@@ -299,12 +325,12 @@
     }
 
     @Override
-    InitNode asInitNode() {
+    public InitNode asInitNode() {
       return this;
     }
 
     @Override
-    InitOrAppend asInitOrAppend() {
+    InitOrAppendNode asInitOrAppend() {
       return this;
     }
 
@@ -329,16 +355,6 @@
     }
 
     @Override
-    public void setImplicitToStringNode(ImplicitToStringNode node) {
-      implicitToStringNode = node;
-    }
-
-    @Override
-    public ImplicitToStringNode getImplicitToStringNode() {
-      return implicitToStringNode;
-    }
-
-    @Override
     public String getConstantArgument() {
       return constantArgument;
     }
@@ -347,22 +363,53 @@
     public boolean hasConstantArgument() {
       return constantArgument != null;
     }
+
+    public void setNonConstantArgument(Value value) {
+      assert value.isNeverNull();
+      this.nonConstantArgument = value;
+    }
+
+    @Override
+    public void setImplicitToStringNode(ImplicitToStringNode node) {
+      implicitToStringNode = node;
+    }
+
+    @Override
+    public ImplicitToStringNode getImplicitToStringNode() {
+      return implicitToStringNode;
+    }
+
+    @Override
+    public boolean hasNonConstantArgument() {
+      return nonConstantArgument != null;
+    }
+
+    @Override
+    public Value getNonConstantArgument() {
+      assert nonConstantArgument != null;
+      return nonConstantArgument;
+    }
+
+    boolean isConstructorInvokeSideEffectFree(StringBuilderOracle oracle) {
+      return oracle.isConstructorInvokeSideEffectFree(instruction);
+    }
   }
 
   /** AppendNodes are StringBuilder.append or StringBuffer.append. */
   static class AppendNode extends StringBuilderNode
-      implements InitOrAppend, StringBuilderInstruction {
+      implements InitOrAppendNode, StringBuilderInstruction {
 
     private final InvokeVirtual instruction;
     private ImplicitToStringNode implicitToStringNode;
     private String constantArgument;
+    private Value nonConstantArgument;
 
     private AppendNode(InvokeVirtual instruction) {
       this.instruction = instruction;
     }
 
     @Override
-    boolean isAppendNode() {
+    public boolean isAppendNode() {
       return true;
     }
 
@@ -372,12 +419,12 @@
     }
 
     @Override
-    AppendNode asAppendNode() {
+    public AppendNode asAppendNode() {
       return this;
     }
 
     @Override
-    InitOrAppend asInitOrAppend() {
+    InitOrAppendNode asInitOrAppend() {
       return this;
     }
 
@@ -412,6 +459,21 @@
     }
 
     @Override
+    public boolean hasNonConstantArgument() {
+      return nonConstantArgument != null;
+    }
+
+    public void setNonConstantArgument(Value value) {
+      assert value.isNeverNull();
+      this.nonConstantArgument = value;
+    }
+
+    @Override
+    public Value getNonConstantArgument() {
+      return nonConstantArgument;
+    }
+
+    @Override
     public String getConstantArgument() {
       return constantArgument;
     }
@@ -540,13 +602,13 @@
    */
   static class ImplicitToStringNode extends StringBuilderNode {
 
-    private final InitOrAppend initOrAppend;
+    private final InitOrAppendNode initOrAppend;
 
-    ImplicitToStringNode(InitOrAppend initOrAppend) {
+    ImplicitToStringNode(InitOrAppendNode initOrAppend) {
       this.initOrAppend = initOrAppend;
     }
 
-    public InitOrAppend getInitOrAppend() {
+    public InitOrAppendNode getInitOrAppend() {
       return initOrAppend;
     }
 
@@ -601,7 +663,7 @@
     return new OtherStringBuilderNode(instruction);
   }
 
-  static ImplicitToStringNode createImplicitToStringNode(InitOrAppend otherNode) {
+  static ImplicitToStringNode createImplicitToStringNode(InitOrAppendNode otherNode) {
     return new ImplicitToStringNode(otherNode);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNodeMuncher.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNodeMuncher.java
index 0659a8a..0fe609e 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNodeMuncher.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNodeMuncher.java
@@ -9,14 +9,18 @@
 import com.android.tools.r8.ir.optimize.string.StringBuilderAction.AppendWithNewConstantString;
 import com.android.tools.r8.ir.optimize.string.StringBuilderAction.RemoveStringBuilderAction;
 import com.android.tools.r8.ir.optimize.string.StringBuilderAction.ReplaceByConstantString;
+import com.android.tools.r8.ir.optimize.string.StringBuilderAction.ReplaceByExistingString;
+import com.android.tools.r8.ir.optimize.string.StringBuilderAction.ReplaceByStringConcat;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.AppendNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.ImplicitToStringNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitNode;
-import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitOrAppend;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitOrAppendNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.NewInstanceNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.StringBuilderInstruction;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNode.ToStringNode;
 import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
 import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
@@ -67,6 +71,14 @@
     public boolean isLooping(StringBuilderNode root) {
       return looping.contains(root);
     }
+
+    public boolean isEscaping(StringBuilderNode root) {
+      return escaping.contains(root);
+    }
+
+    public boolean isInspecting(StringBuilderNode root) {
+      return inspectingCapacity.contains(root);
+    }
   }
 
   private interface PeepholePattern {
@@ -93,30 +105,32 @@
     @Override
     public boolean optimize(
         StringBuilderNode root, StringBuilderNode currentNode, MunchingState munchingState) {
-      if (!currentNode.isAppendNode()) {
+      AppendNode appendNode = currentNode.asAppendNode();
+      if (appendNode == null || !appendNode.hasSinglePredecessor()) {
         return false;
       }
-      String currentConstantArgument = getConstantArgumentForNode(currentNode, munchingState);
-      if (currentConstantArgument == null || !currentNode.hasSinglePredecessor()) {
-        return false;
-      }
-      StringBuilderNode previous = currentNode.getSinglePredecessor();
-      String previousConstantArgument = getConstantArgumentForNode(previous, munchingState);
-      if (previousConstantArgument == null || !previous.hasSingleSuccessor()) {
+      InitOrAppendNode previous = currentNode.getSinglePredecessor().asInitOrAppend();
+      if (previous == null || !previous.hasSingleSuccessor()) {
         return false;
       }
       // The capacity changes based on the init call (on JVM it adds 16 to length of input).
       if (previous.isInitNode() && munchingState.inspectingCapacity.contains(root)) {
         return false;
       }
-      assert previous.isInitOrAppend();
+      String currentConstantArgument = getConstantArgumentForNode(appendNode, munchingState);
+      if (currentConstantArgument == null) {
+        return false;
+      }
+      String previousConstantArgument = getConstantArgumentForNode(previous, munchingState);
+      if (previousConstantArgument == null) {
+        return false;
+      }
       String newConstant = previousConstantArgument + currentConstantArgument;
-      InitOrAppend initOrAppend = previous.asInitOrAppend();
-      initOrAppend.setConstantArgument(newConstant);
+      previous.setConstantArgument(newConstant);
       munchingState.actions.put(
-          initOrAppend.getInstruction(), new AppendWithNewConstantString(newConstant));
+          previous.getInstruction(), new AppendWithNewConstantString(newConstant));
       munchingState.actions.put(
-          currentNode.asAppendNode().getInstruction(), RemoveStringBuilderAction.getInstance());
+          appendNode.getInstruction(), RemoveStringBuilderAction.getInstance());
       currentNode.removeNode();
       return true;
     }
@@ -126,13 +140,13 @@
    * This peephole will try to remove toString nodes and replace by a constant string:
    *
    * <pre>
-   * newInstance -> init("foo") -> append("bar") -> toString() =>
-   * newInstance -> init("foo") -> append("bar")
+   * newInstance -> init("foo") -> toString() => newInstance -> init("foo") -> append("bar")
+   * actions: [toString() => ReplaceByConstantString("foo")]
    * </pre>
    *
    * <p>If the node is an implicitToString, we update the append of another builder to have the new
-   * constant value directly. If not, we keep track of the outValue toString() had is replaced by a
-   * constant, by updating {@code MunchingState.optimizedStrings}
+   * constant value directly. If not, we keep track of the outValue toString() being replaced by a
+   * constant by updating {@code MunchingState.optimizedStrings}
    */
   private static class MunchToString implements PeepholePattern {
 
@@ -141,6 +155,9 @@
         StringBuilderNode originalRoot,
         StringBuilderNode currentNode,
         MunchingState munchingState) {
+      if (munchingState.isEscaping(originalRoot) || munchingState.isInspecting(originalRoot)) {
+        return false;
+      }
       if (!currentNode.isToStringNode() && !currentNode.isImplicitToStringNode()) {
         return false;
       }
@@ -148,48 +165,127 @@
       if (newInstanceNode == null || !newInstanceNode.hasSingleSuccessor()) {
         return false;
       }
-      StringBuilderNode init = newInstanceNode.getSingleSuccessor();
-      String rootConstantArgument = getConstantArgumentForNode(init, munchingState);
-      if (rootConstantArgument == null || !init.isInitNode()) {
+      InitNode init = newInstanceNode.getSingleSuccessor().asInitNode();
+      if (init == null || !init.hasSingleSuccessor()) {
         return false;
       }
-      // This is either <init>(str) -> toString() or <init>(str) -> append(str) -> toString()
+      if (!currentNode.hasSinglePredecessor() || currentNode.getSinglePredecessor() != init) {
+        return false;
+      }
+      String initConstantArgument = getConstantArgumentForNode(init, munchingState);
+      if (initConstantArgument == null) {
+        return false;
+      }
       // If the string builder dependency is directly given to another string builder, there is
       // no toString() but an append with this string builder as argument.
-      if (!currentNode.hasSinglePredecessor() || !init.hasSingleSuccessor()) {
-        return false;
-      }
-      String constantArgument = null;
-      if (currentNode.getSinglePredecessor() == init) {
-        constantArgument = rootConstantArgument;
-      } else {
-        StringBuilderNode expectedAppend = init.getSingleSuccessor();
-        StringBuilderNode expectedSameAppend = currentNode.getSinglePredecessor();
-        String appendConstantArgument = getConstantArgumentForNode(expectedAppend, munchingState);
-        if (expectedAppend == expectedSameAppend && appendConstantArgument != null) {
-          // TODO(b/190489514): See if this larger pattern is necessary.
-          assert false : "See why this larger pattern is necessary";
-          constantArgument = rootConstantArgument + appendConstantArgument;
-        }
-      }
-      if (constantArgument == null) {
-        return false;
-      }
       if (currentNode.isToStringNode()) {
         ToStringNode toStringNode = currentNode.asToStringNode();
         munchingState.actions.put(
-            toStringNode.getInstruction(), new ReplaceByConstantString(constantArgument));
+            toStringNode.getInstruction(), new ReplaceByConstantString(initConstantArgument));
         String oldValue =
             munchingState.optimizedStrings.put(
-                toStringNode.getInstruction().outValue(), constantArgument);
+                toStringNode.getInstruction().outValue(), initConstantArgument);
         assert oldValue == null;
       } else {
         assert currentNode.isImplicitToStringNode();
         ImplicitToStringNode implicitToStringNode = currentNode.asImplicitToStringNode();
-        InitOrAppend initOrAppend = implicitToStringNode.getInitOrAppend();
-        initOrAppend.setConstantArgument(constantArgument);
+        InitOrAppendNode initOrAppend = implicitToStringNode.getInitOrAppend();
+        initOrAppend.setConstantArgument(initConstantArgument);
         munchingState.actions.put(
-            initOrAppend.getInstruction(), new AppendWithNewConstantString(constantArgument));
+            initOrAppend.getInstruction(), new AppendWithNewConstantString(initConstantArgument));
+      }
+      munchingState.materializingInstructions.get(originalRoot).remove(currentNode);
+      currentNode.removeNode();
+      return true;
+    }
+  }
+
+  /**
+   * This peephole will try to remove toString nodes and replace by an invoke to String.concat:
+   *
+   * <pre>
+   * newInstance -> init(notNull(string)) -> append(notNull(otherString)) -> toString() =>
+   * newInstance -> init(notNull(string)) -> append(otherString)
+   * actions: [toString() => string.concat(otherString)]
+   * </pre>
+   *
+   * <p>This pattern only triggers when a constant munching of toString could happen.
+   */
+  private static class MunchToStringIntoStringConcat implements PeepholePattern {
+
+    @Override
+    public boolean optimize(
+        StringBuilderNode originalRoot,
+        StringBuilderNode currentNode,
+        MunchingState munchingState) {
+      if (munchingState.isEscaping(originalRoot) || munchingState.isInspecting(originalRoot)) {
+        return false;
+      }
+      // TODO(b/129200243): Handle implicit tostring nodes.
+      if (!currentNode.isToStringNode() || !currentNode.hasSinglePredecessor()) {
+        return false;
+      }
+      StringBuilderNode root = findFirstNonSentinelRoot(originalRoot);
+      if (!root.isNewInstanceNode() || !root.hasSingleSuccessor()) {
+        return false;
+      }
+      InitOrAppendNode firstNode = root.getSingleSuccessor().asInitNode();
+      if (firstNode == null || !firstNode.hasSingleSuccessor()) {
+        return false;
+      }
+      if (firstNode.asInitNode().isConstructorInvokeSideEffectFree(munchingState.oracle)
+          && "".equals(firstNode.getConstantArgument())
+          && firstNode.hasSingleSuccessor()) {
+        firstNode = firstNode.getSingleSuccessor().asAppendNode();
+        if (firstNode == null
+            || !firstNode.hasSinglePredecessor()
+            || !firstNode.hasSingleSuccessor()) {
+          return false;
+        }
+      }
+      // We cannot String.concat or return the string safely when it is not constant and maybe null.
+      if (!firstNode.hasConstantOrNonConstantArgument()) {
+        return false;
+      }
+      List<InitOrAppendNode> initOrAppends = Lists.newArrayList(firstNode);
+      if (currentNode.getSinglePredecessor() != firstNode) {
+        AppendNode appendAfterFirstNode = firstNode.getSingleSuccessor().asAppendNode();
+        AppendNode appendBeforeToString = currentNode.getSinglePredecessor().asAppendNode();
+        if (appendAfterFirstNode == null
+            || appendAfterFirstNode != appendBeforeToString
+            || !appendAfterFirstNode.hasConstantOrNonConstantArgument()) {
+          return false;
+        }
+        initOrAppends.add(appendAfterFirstNode);
+      }
+      // Check that all values are not constant otherwise we can compute the constant value and
+      // replace all entirely.
+      if (Iterables.all(initOrAppends, InitOrAppendNode::hasConstantArgument)) {
+        return false;
+      }
+      // Replace with the string itself.
+      Instruction currentInstruction = currentNode.asToStringNode().getInstruction();
+      InitOrAppendNode first = initOrAppends.get(0);
+      if (initOrAppends.size() == 1) {
+        munchingState.actions.put(
+            currentInstruction, new ReplaceByExistingString(first.getNonConstantArgument()));
+      } else {
+        InitOrAppendNode second = initOrAppends.get(1);
+        ReplaceByStringConcat concatAction;
+        if (first.hasConstantArgument()) {
+          concatAction =
+              ReplaceByStringConcat.replaceByNewConstantConcatValue(
+                  first.getConstantArgument(), second.getNonConstantArgument());
+        } else if (second.hasConstantArgument()) {
+          concatAction =
+              ReplaceByStringConcat.replaceByValueConcatNewConstant(
+                  first.getNonConstantArgument(), second.getConstantArgument());
+        } else {
+          concatAction =
+              ReplaceByStringConcat.replaceByValues(
+                  first.getNonConstantArgument(), second.getNonConstantArgument());
+        }
+        munchingState.actions.put(currentInstruction, concatAction);
       }
       munchingState.materializingInstructions.get(originalRoot).remove(currentNode);
       currentNode.removeNode();
@@ -198,21 +294,11 @@
   }
 
   private static String getConstantArgumentForNode(
-      StringBuilderNode node, MunchingState munchingState) {
-    if (node.isAppendNode()) {
-      AppendNode appendNode = node.asAppendNode();
-      if (appendNode.hasConstantArgument()) {
-        return appendNode.getConstantArgument();
-      }
-      return getOptimizedConstantArgument(appendNode, munchingState);
-    } else if (node.isInitNode()) {
-      InitNode initNode = node.asInitNode();
-      if (initNode.hasConstantArgument()) {
-        return initNode.getConstantArgument();
-      }
-      return getOptimizedConstantArgument(initNode, munchingState);
+      InitOrAppendNode node, MunchingState munchingState) {
+    if (node.hasConstantArgument()) {
+      return node.getConstantArgument();
     }
-    return null;
+    return getOptimizedConstantArgument(node, munchingState);
   }
 
   private static String getOptimizedConstantArgument(
@@ -262,7 +348,6 @@
             removeNode = true;
           }
         } else if (currentNode.isInitNode()
-            && currentNode.asInitNode().hasConstantArgument()
             && currentNode.hasSinglePredecessor()
             && currentNode.getSinglePredecessor().isNewInstanceNode()
             && currentNode.getSuccessors().isEmpty()
@@ -312,7 +397,12 @@
   }
 
   private static final PeepholePattern[] peepholePatterns =
-      new PeepholePattern[] {new MunchAppends(), new MunchToString(), new MunchNonMaterializing()};
+      new PeepholePattern[] {
+        new MunchAppends(),
+        new MunchToString(),
+        new MunchToStringIntoStringConcat(),
+        new MunchNonMaterializing()
+      };
 
   static boolean optimize(
       StringBuilderNode root, StringBuilderNode currentNode, MunchingState munchingState) {
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 063f791..8b59c2f 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
@@ -43,6 +43,12 @@
 
   boolean isInit(Instruction instruction);
 
+  boolean isAppendString(Instruction instruction);
+
+  boolean isStringConstructor(Instruction instruction);
+
+  boolean isConstructorInvokeSideEffectFree(Instruction instruction);
+
   class DefaultStringBuilderOracle implements StringBuilderOracle {
 
     private final DexItemFactory factory;
@@ -185,12 +191,12 @@
       }
       DexMethod invokedMethod = instruction.asInvokeMethod().getInvokedMethod();
       if (factory.stringBuilderMethods.isAppendObjectOrCharSequenceMethod(invokedMethod)
-          || factory.stringBufferMethods.isAppendObjectOrCharSequenceMethod(invokedMethod)
-          || factory.stringBuilderMethods.charSequenceConstructor == invokedMethod
-          || factory.stringBufferMethods.charSequenceConstructor == invokedMethod) {
-        assert instruction.inValues().size() == 2;
+          || factory.stringBufferMethods.isAppendObjectOrCharSequenceMethod(invokedMethod)) {
         return !instruction.inValues().get(1).getType().isStringType(factory);
       }
+      if (invokedMethod.isInstanceInitializer(factory)) {
+        return !isConstructorInvokeSideEffectFree(instruction);
+      }
       if (factory.stringBuilderMethods.isAppendCharArrayMethod(invokedMethod)
           || factory.stringBufferMethods.isAppendCharArrayMethod(invokedMethod)) {
         return instruction.asInvokeVirtual().getFirstNonReceiverArgument().isMaybeNull();
@@ -207,5 +213,41 @@
       return factory.stringBuilderMethods.isConstructorMethod(invokedMethod)
           || factory.stringBufferMethods.isConstructorMethod(invokedMethod);
     }
+
+    @Override
+    public boolean isAppendString(Instruction instruction) {
+      if (!instruction.isInvokeMethod()) {
+        return false;
+      }
+      DexMethod invokedMethod = instruction.asInvokeMethod().getInvokedMethod();
+      return factory.stringBuilderMethods.isAppendStringMethod(invokedMethod)
+          || factory.stringBufferMethods.isAppendStringMethod(invokedMethod);
+    }
+
+    @Override
+    public boolean isStringConstructor(Instruction instruction) {
+      if (!instruction.isInvokeMethod()) {
+        return false;
+      }
+      DexMethod invokedMethod = instruction.asInvokeMethod().getInvokedMethod();
+      return invokedMethod == factory.stringBuilderMethods.stringConstructor
+          || invokedMethod == factory.stringBufferMethods.stringConstructor;
+    }
+
+    @Override
+    public boolean isConstructorInvokeSideEffectFree(Instruction instruction) {
+      if (!instruction.isInvokeConstructor(factory)) {
+        return false;
+      }
+      DexMethod invokedMethod = instruction.asInvokeMethod().getInvokedMethod();
+      if (invokedMethod.getHolderType() == factory.stringBuilderType) {
+        return factory.stringBuilderMethods.constructorInvokeIsSideEffectFree(
+            invokedMethod, instruction.inValues());
+      } else {
+        assert invokedMethod.getHolderType() == factory.stringBufferType;
+        return factory.stringBufferMethods.constructorInvokeIsSideEffectFree(
+            invokedMethod, instruction.inValues());
+      }
+    }
   }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendConstantAppendNotNullTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendConstantAppendNotNullTest.java
index d4ac494..4646691 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendConstantAppendNotNullTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendConstantAppendNotNullTest.java
@@ -53,7 +53,6 @@
               MethodSubject methodSubject = inspect.clazz(Main.class).mainMethod();
               assertThat(methodSubject, isPresent());
               assertEquals(1, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
-              // TODO(b/129200243): Should only have two appends.
               assertEquals(3, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
             });
   }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendNotNullTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendNotNullTest.java
index c28729a..cbe8fa7 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendNotNullTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullAppendNotNullTest.java
@@ -13,6 +13,7 @@
 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.CodeMatchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -52,9 +53,9 @@
             inspect -> {
               MethodSubject methodSubject = inspect.clazz(Main.class).mainMethod();
               assertThat(methodSubject, isPresent());
-              // TODO(b/129200243): Should be String.concat.
-              assertEquals(1, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
-              assertEquals(2, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertThat(methodSubject, CodeMatchers.invokesMethodWithName("concat"));
             });
   }
 
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullTest.java
index d2c95ab..8005ed5 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatAppendNotNullTest.java
@@ -7,12 +7,14 @@
 import static com.android.tools.r8.ir.optimize.string.utils.StringBuilderCodeMatchers.countStringBuilderAppends;
 import static com.android.tools.r8.ir.optimize.string.utils.StringBuilderCodeMatchers.countStringBuilderInits;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
 
 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.CodeMatchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -52,9 +54,9 @@
             inspect -> {
               MethodSubject methodSubject = inspect.clazz(Main.class).mainMethod();
               assertThat(methodSubject, isPresent());
-              // TODO(b/129200243): This should just be arg.toString()
-              assertEquals(1, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
-              assertEquals(1, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertThat(methodSubject, not(CodeMatchers.invokesMethodWithName("concat")));
             });
   }
 
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatConstantInitTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatConstantInitTest.java
index 9b9280f..0f7d286 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatConstantInitTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatConstantInitTest.java
@@ -13,6 +13,7 @@
 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.CodeMatchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -52,9 +53,9 @@
             inspect -> {
               MethodSubject methodSubject = inspect.clazz(Main.class).mainMethod();
               assertThat(methodSubject, isPresent());
-              // TODO(b/129200243): Should be String.concat.
-              assertEquals(1, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
-              assertEquals(1, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertThat(methodSubject, CodeMatchers.invokesMethodWithName("concat"));
             });
   }
 
@@ -63,7 +64,7 @@
     public static void main(String[] args) {
       String arg = System.currentTimeMillis() > 0 ? "o" : null;
       if (arg != null) {
-        // The optimization should join "ok" into init and then append with arg.
+        // The optimization should join "ok" into init and then concat with arg.
         System.out.println(new StringBuilder("o").append("k").append(arg).toString());
       }
     }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullAppendNotNullTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullAppendNotNullTest.java
index 4dce8fd..aca301c 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullAppendNotNullTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullAppendNotNullTest.java
@@ -13,6 +13,7 @@
 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.CodeMatchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -52,9 +53,9 @@
             inspect -> {
               MethodSubject methodSubject = inspect.clazz(Main.class).mainMethod();
               assertThat(methodSubject, isPresent());
-              // TODO(b/129200243): Should be concat.
-              assertEquals(1, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
-              assertEquals(1, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertThat(methodSubject, CodeMatchers.invokesMethodWithName("concat"));
             });
   }
 
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullTest.java
index 690a604..4bb550e 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatInitNotNullTest.java
@@ -7,12 +7,14 @@
 import static com.android.tools.r8.ir.optimize.string.utils.StringBuilderCodeMatchers.countStringBuilderAppends;
 import static com.android.tools.r8.ir.optimize.string.utils.StringBuilderCodeMatchers.countStringBuilderInits;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
 
 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.CodeMatchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -52,9 +54,9 @@
             inspect -> {
               MethodSubject methodSubject = inspect.clazz(Main.class).mainMethod();
               assertThat(methodSubject, isPresent());
-              // TODO(b/129200243): This should just be the string as is.
-              assertEquals(1, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
+              assertEquals(0, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
               assertEquals(0, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertThat(methodSubject, not(CodeMatchers.invokesMethodWithName("concat")));
             });
   }
 
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatNoRewriteConstantsTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatNoRewriteConstantsTest.java
index 73e61bc..33320dc 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatNoRewriteConstantsTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatNoRewriteConstantsTest.java
@@ -7,12 +7,14 @@
 import static com.android.tools.r8.ir.optimize.string.utils.StringBuilderCodeMatchers.countStringBuilderAppends;
 import static com.android.tools.r8.ir.optimize.string.utils.StringBuilderCodeMatchers.countStringBuilderInits;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
 
 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.CodeMatchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -54,6 +56,7 @@
               assertThat(methodSubject, isPresent());
               assertEquals(0, countStringBuilderInits(methodSubject.asFoundMethodSubject()));
               assertEquals(0, countStringBuilderAppends(methodSubject.asFoundMethodSubject()));
+              assertThat(methodSubject, not(CodeMatchers.invokesMethodWithName("concat")));
             });
   }