Merge commit '65ab16a350c417b2da9db0506ed95f3cc6156527' into dev-release

diff --git a/src/main/java/com/android/tools/r8/D8.java b/src/main/java/com/android/tools/r8/D8.java
index 34f4de6..3887ee7 100644
--- a/src/main/java/com/android/tools/r8/D8.java
+++ b/src/main/java/com/android/tools/r8/D8.java

@@ -337,31 +337,13 @@
         timing.end();
       }
 
-      timing.time("Finalize synthetics", () -> finalizeApplication(appView, executor, timing));
-
-      timing.time(
-          "Horizontal merger",
-          () ->
-              HorizontalClassMerger.createForD8ClassMerging(appView)
-                  .runIfNecessary(executor, timing));
-
-      timing.time(
-          "Signature rewriter",
-          () ->
-              new GenericSignatureRewriter(appView)
-                  .runForD8(appView.appInfo().classes(), executor));
-
-      timing.time(
-          "Kotlin metadata rewriter", () -> new KotlinMetadataRewriter(appView).runForD8(executor));
+      finalizeApplication(appView, executor, timing);
 
       timing.end(); // post-converter
 
       if (options.isGeneratingClassFiles()) {
         new CfApplicationWriter(appView, marker).write(options.getClassFileConsumer(), inputApp);
       } else {
-        if (options.apiModelingOptions().enableStubbingOfClasses) {
-          new ApiReferenceStubber(appView).run(executor);
-        }
         new ApplicationWriter(appView, marker == null ? null : ImmutableList.copyOf(markers))
             .write(executor, inputApp);
       }
@@ -397,7 +379,28 @@
   private static void finalizeApplication(
       AppView<AppInfo> appView, ExecutorService executorService, Timing timing)
       throws ExecutionException {
-    SyntheticFinalization.finalize(appView, timing, executorService);
+    timing.time(
+        "Finalize synthetics",
+        () -> SyntheticFinalization.finalize(appView, timing, executorService));
+
+    timing.time(
+        "Horizontal merger",
+        () ->
+            HorizontalClassMerger.createForD8ClassMerging(appView)
+                .runIfNecessary(executorService, timing));
+
+    timing.time(
+        "Signature rewriter",
+        () ->
+            new GenericSignatureRewriter(appView)
+                .runForD8(appView.appInfo().classes(), executorService));
+
+    timing.time(
+        "Kotlin metadata rewriter",
+        () -> new KotlinMetadataRewriter(appView).runForD8(executorService));
+
+    timing.time(
+        "Api reference stubber", () -> new ApiReferenceStubber(appView).run(executorService));
   }
 
   private static DexApplication rewriteNonDexInputs(

diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
index 3e59e50..492e61a 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java

@@ -163,10 +163,7 @@
   }
 
   public ApplicationWriter(AppView<?> appView, List<Marker> markers) {
-    this(
-        appView,
-        markers,
-        null);
+    this(appView, markers, null);
   }
 
   public ApplicationWriter(

diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index b785927..51a4a4a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java

@@ -447,10 +447,6 @@
     return isInstanceInitializer() || isClassInitializer();
   }
 
-  public boolean isInitializer(boolean isStatic) {
-    return isStatic ? isClassInitializer() : isInstanceInitializer();
-  }
-
   public boolean isInstanceInitializer() {
     checkIfObsolete();
     return accessFlags.isConstructor() && !accessFlags.isStatic();

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 c0aaa95..8fe1c7e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java

@@ -2172,6 +2172,10 @@
       assert false : "Unexpected invoke targeting `" + invokedMethod.toSourceString() +  "`";
       return false;
     }
+
+    public boolean isAppendCharArrayMethod(DexMethod method) {
+      return method == appendCharArray || method == appendSubCharArray;
+    }
   }
 
   public class SupplierMembers extends LibraryMembers {

diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoEnums.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoEnums.java
index e037345..342a3fb 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoEnums.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoEnums.java

@@ -52,7 +52,7 @@
     } else if (clazz.type == appView.dexItemFactory().enumType) {
       result = true;
     } else {
-      DexClass superClass = appView.definitionFor(clazz.superType);
+      DexClass superClass = clazz.hasSuperType() ? appView.definitionFor(clazz.superType) : null;
       result = superClass != null && isEnumSubtype(superClass);
     }
     cache.put(clazz, result);

diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
index 4e43590..13f8213 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java

@@ -159,18 +159,24 @@
       return true;
     }
 
-    // Check that all usages of the array are array stores.
-    for (Instruction user : array.uniqueUsers()) {
-      if (!user.isArrayPut() || user.asArrayPut().array() != array) {
-        return true;
-      }
-    }
-
-    if (array.numberOfPhiUsers() > 0) {
+    if (array.hasPhiUsers()) {
       // The array could be used indirectly.
       return true;
     }
 
+    // Check that all usages of the array are array stores.
+    for (Instruction user : array.aliasedUsers()) {
+      if (user.isAssume()) {
+        if (user.outValue().hasPhiUsers()) {
+          return true;
+        }
+        continue;
+      }
+      if (!user.isArrayPut() || user.asArrayPut().array().getAliasedValue() != array) {
+        return true;
+      }
+    }
+
     return false;
   }
 

diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 432311b..550ea8b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java

@@ -22,6 +22,7 @@
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.StringUtils.BraceType;
@@ -53,6 +54,7 @@
 import java.util.function.BiFunction;
 import java.util.function.Consumer;
 import java.util.function.Function;
+import java.util.function.Predicate;
 
 /**
  * Basic block abstraction.
@@ -718,6 +720,10 @@
     return instructions;
   }
 
+  public <T extends Instruction> Iterable<T> getInstructions(Predicate<Instruction> predicate) {
+    return IterableUtils.filter(getInstructions(), predicate);
+  }
+
   public Iterable<Instruction> instructionsAfter(Instruction instruction) {
     return () -> iterator(instruction);
   }

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 bdbe697..1d40f99 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

@@ -33,6 +33,7 @@
 import java.util.ListIterator;
 import java.util.Set;
 import java.util.function.Consumer;
+import java.util.function.UnaryOperator;
 
 public class BasicBlockInstructionListIterator implements InstructionListIterator {
 
@@ -439,7 +440,7 @@
   public void replaceCurrentInstructionWithThrow(
       AppView<?> appView,
       IRCode code,
-      ListIterator<BasicBlock> blockIterator,
+      BasicBlockIterator blockIterator,
       Value exceptionValue,
       Set<BasicBlock> blocksToRemove,
       Set<Value> affectedValues) {
@@ -657,12 +658,18 @@
 
   @Override
   public BasicBlock splitCopyCatchHandlers(
-      IRCode code, ListIterator<BasicBlock> blockIterator, InternalOptions options) {
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      InternalOptions options,
+      UnaryOperator<BasicBlock> repositioningBlock) {
     BasicBlock splitBlock = split(code, blockIterator, false);
     assert !block.hasCatchHandlers();
     if (splitBlock.hasCatchHandlers()) {
       block.copyCatchHandlers(code, blockIterator, splitBlock, options);
     }
+    if (repositioningBlock != null) {
+      blockIterator.positionAfterPreviousBlock(repositioningBlock.apply(splitBlock));
+    }
     return splitBlock;
   }
 

diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java
index 4de1c80..50c15bb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockIterator.java

@@ -64,6 +64,15 @@
     return listIterator.previousIndex();
   }
 
+  public BasicBlock positionAfterPreviousBlock(BasicBlock previousBlock) {
+    return positionAfterPreviousBlock(currentBlock -> currentBlock == previousBlock);
+  }
+
+  public BasicBlock positionAfterPreviousBlock(Predicate<BasicBlock> predicate) {
+    previousUntil(predicate);
+    return next();
+  }
+
   public BasicBlock previousUntil(Predicate<BasicBlock> predicate) {
     return IteratorUtils.previousUntil(this, predicate);
   }

diff --git a/src/main/java/com/android/tools/r8/ir/code/FieldGet.java b/src/main/java/com/android/tools/r8/ir/code/FieldGet.java
index ec663fb..4d4a55b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/FieldGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/FieldGet.java

@@ -13,6 +13,10 @@
 
   TypeElement getOutType();
 
+  boolean isInstanceGet();
+
+  boolean isStaticGet();
+
   boolean hasUsedOutValue();
 
   Value outValue();

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 4962981..ae400dc 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

@@ -18,6 +18,7 @@
 import java.util.NoSuchElementException;
 import java.util.Set;
 import java.util.function.Consumer;
+import java.util.function.UnaryOperator;
 
 public class IRCodeInstructionListIterator implements InstructionListIterator {
 
@@ -105,7 +106,7 @@
   public void replaceCurrentInstructionWithThrow(
       AppView<?> appView,
       IRCode code,
-      ListIterator<BasicBlock> blockIterator,
+      BasicBlockIterator blockIterator,
       Value exceptionValue,
       Set<BasicBlock> blocksToRemove,
       Set<Value> affectedValues) {
@@ -135,7 +136,10 @@
 
   @Override
   public BasicBlock splitCopyCatchHandlers(
-      IRCode code, ListIterator<BasicBlock> blockIterator, InternalOptions options) {
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      InternalOptions options,
+      UnaryOperator<BasicBlock> repositioningBlock) {
     throw new Unimplemented();
   }
 

diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
index b88555d..6f571d0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java

@@ -39,6 +39,25 @@
     super(field, dest, object);
   }
 
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  public static InstanceGet copyOf(IRCode code, InstanceGet original) {
+    Value newValue =
+        new Value(code.valueNumberGenerator.next(), original.getOutType(), original.getLocalInfo());
+    return copyOf(newValue, original);
+  }
+
+  public static InstanceGet copyOf(Value newValue, InstanceGet original) {
+    assert newValue != original.outValue();
+    return InstanceGet.builder()
+        .setField(original.getField())
+        .setObject(original.object())
+        .setOutValue(newValue)
+        .build();
+  }
+
   @Override
   public int opcode() {
     return Opcodes.INSTANCE_GET;
@@ -234,4 +253,35 @@
   public boolean instructionMayTriggerMethodInvocation(AppView<?> appView, ProgramMethod context) {
     return false;
   }
+
+  @Override
+  public boolean instructionTypeCanBeCanonicalized() {
+    return true;
+  }
+
+  public static class Builder extends BuilderBase<Builder, InstanceGet> {
+
+    private DexField field;
+    private Value object;
+
+    public Builder setField(DexField field) {
+      this.field = field;
+      return this;
+    }
+
+    public Builder setObject(Value object) {
+      this.object = object;
+      return this;
+    }
+
+    @Override
+    public InstanceGet build() {
+      return amend(new InstanceGet(outValue, object, field));
+    }
+
+    @Override
+    public Builder self() {
+      return this;
+    }
+  }
 }

diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java
index 539f0d7..04ee188 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java

@@ -19,6 +19,13 @@
 
   Instruction previous();
 
+  default void previous(int times) {
+    while (times > 0) {
+      previous();
+      times--;
+    }
+  }
+
   /**
    * Peek the next instruction.
    *

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 e13fe25..0cb7228 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

@@ -19,6 +19,8 @@
 import java.util.ListIterator;
 import java.util.Set;
 import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
 
 public interface InstructionListIterator
     extends InstructionIterator, ListIterator<Instruction>, PreviousUntilIterator<Instruction> {
@@ -29,12 +31,18 @@
       Instruction instruction,
       InternalOptions options);
 
-  default void addBefore(Instruction instruction) {
-    previous();
+  default void addAndPositionBeforeNewInstruction(Instruction instruction) {
     add(instruction);
-    next();
+    Instruction previous = previous();
+    assert previous == instruction;
   }
 
+  default void addBeforeAndPositionBeforeNewInstruction(Instruction instruction) {
+    previous();
+    add(instruction);
+    Instruction previous = previous();
+    assert previous == instruction;
+  }
   /** See {@link #replaceCurrentInstruction(Instruction, Set)}. */
   default void replaceCurrentInstruction(Instruction newInstruction) {
     replaceCurrentInstruction(newInstruction, null);
@@ -107,6 +115,16 @@
       Value value,
       Position position);
 
+  default Instruction positionAfterPreviousInstruction(Instruction previousInstruction) {
+    return positionAfterPreviousInstruction(
+        currentInstruction -> currentInstruction == previousInstruction);
+  }
+
+  default Instruction positionAfterPreviousInstruction(Predicate<Instruction> predicate) {
+    previousUntil(predicate);
+    return next();
+  }
+
   boolean replaceCurrentInstructionByNullCheckIfPossible(AppView<?> appView, ProgramMethod context);
 
   default boolean removeOrReplaceCurrentInstructionByInitClassIfPossible(
@@ -147,7 +165,7 @@
   void replaceCurrentInstructionWithThrow(
       AppView<?> appView,
       IRCode code,
-      ListIterator<BasicBlock> blockIterator,
+      BasicBlockIterator blockIterator,
       Value exceptionValue,
       Set<BasicBlock> blocksToRemove,
       Set<Value> affectedValues);
@@ -199,8 +217,16 @@
     return split(code, null);
   }
 
+  default BasicBlock splitCopyCatchHandlers(
+      IRCode code, BasicBlockIterator blockIterator, InternalOptions options) {
+    return splitCopyCatchHandlers(code, blockIterator, options, null);
+  }
+
   BasicBlock splitCopyCatchHandlers(
-      IRCode code, ListIterator<BasicBlock> blockIterator, InternalOptions options);
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      InternalOptions options,
+      UnaryOperator<BasicBlock> repositioningBlock);
 
   /**
    * Split the block into three blocks. The first split is at the point of the {@link ListIterator}

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 91b51be..ed95689 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

@@ -17,6 +17,7 @@
 import java.util.ListIterator;
 import java.util.Set;
 import java.util.function.Consumer;
+import java.util.function.UnaryOperator;
 
 public class LinearFlowInstructionListIterator implements InstructionListIterator {
 
@@ -124,7 +125,7 @@
   public void replaceCurrentInstructionWithThrow(
       AppView<?> appView,
       IRCode code,
-      ListIterator<BasicBlock> blockIterator,
+      BasicBlockIterator blockIterator,
       Value exceptionValue,
       Set<BasicBlock> blocksToRemove,
       Set<Value> affectedValues) {
@@ -156,8 +157,12 @@
 
   @Override
   public BasicBlock splitCopyCatchHandlers(
-      IRCode code, ListIterator<BasicBlock> blockIterator, InternalOptions options) {
-    return currentBlockIterator.splitCopyCatchHandlers(code, blockIterator, options);
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      InternalOptions options,
+      UnaryOperator<BasicBlock> repositioningBlock) {
+    return currentBlockIterator.splitCopyCatchHandlers(
+        code, blockIterator, options, repositioningBlock);
   }
 
   @Override

diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 276a72c..52dc8b3 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java

@@ -128,7 +128,6 @@
   private final CfgPrinter printer;
   public final CodeRewriter codeRewriter;
   private final NaturalIntLoopRemover naturalIntLoopRemover = new NaturalIntLoopRemover();
-  private final ConstantCanonicalizer constantCanonicalizer;
   public final MemberValuePropagation<?> memberValuePropagation;
   private final LensCodeRewriter lensCodeRewriter;
   private final Inliner inliner;
@@ -176,7 +175,6 @@
     this.options = appView.options();
     this.printer = printer;
     this.codeRewriter = new CodeRewriter(appView);
-    this.constantCanonicalizer = new ConstantCanonicalizer(codeRewriter);
     this.classInitializerDefaultsOptimization =
         new ClassInitializerDefaultsOptimization(appView, this);
     this.stringOptimizer = new StringOptimizer(appView);
@@ -1430,7 +1428,9 @@
     // TODO(mkroghj) Test if shorten live ranges is worth it.
     if (!options.isGeneratingClassFiles()) {
       timing.begin("Canonicalize constants");
-      constantCanonicalizer.canonicalize(appView, code);
+      ConstantCanonicalizer constantCanonicalizer =
+          new ConstantCanonicalizer(appView, codeRewriter, context, code);
+      constantCanonicalizer.canonicalize();
       timing.end();
       previous = printMethod(code, "IR after constant canonicalization (SSA)", previous);
       timing.begin("Create constants for literal instructions");
@@ -1438,7 +1438,7 @@
       timing.end();
       previous = printMethod(code, "IR after constant literals (SSA)", previous);
       timing.begin("Shorten live ranges");
-      codeRewriter.shortenLiveRanges(code);
+      codeRewriter.shortenLiveRanges(code, constantCanonicalizer);
       timing.end();
       previous = printMethod(code, "IR after shorten live ranges (SSA)", previous);
     }

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 1cf1e36..38afb5d 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java

@@ -7,6 +7,12 @@
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
 import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+import static com.android.tools.r8.ir.code.Opcodes.CONST_CLASS;
+import static com.android.tools.r8.ir.code.Opcodes.CONST_NUMBER;
+import static com.android.tools.r8.ir.code.Opcodes.CONST_STRING;
+import static com.android.tools.r8.ir.code.Opcodes.DEX_ITEM_BASED_CONST_STRING;
+import static com.android.tools.r8.ir.code.Opcodes.INSTANCE_GET;
+import static com.android.tools.r8.ir.code.Opcodes.STATIC_GET;
 
 import com.android.tools.r8.algorithms.scc.SCC;
 import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
@@ -43,15 +49,18 @@
 import com.android.tools.r8.ir.code.ArrayPut;
 import com.android.tools.r8.ir.code.Assume;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.Binop;
 import com.android.tools.r8.ir.code.CatchHandlers;
 import com.android.tools.r8.ir.code.CatchHandlers.CatchHandler;
 import com.android.tools.r8.ir.code.CheckCast;
+import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.ConstInstruction;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.ConstString;
 import com.android.tools.r8.ir.code.DebugLocalWrite;
 import com.android.tools.r8.ir.code.DebugLocalsChange;
+import com.android.tools.r8.ir.code.DexItemBasedConstString;
 import com.android.tools.r8.ir.code.DominatorTree;
 import com.android.tools.r8.ir.code.Goto;
 import com.android.tools.r8.ir.code.IRCode;
@@ -100,7 +109,6 @@
 import com.android.tools.r8.utils.InternalOutputMode;
 import com.android.tools.r8.utils.LazyBox;
 import com.android.tools.r8.utils.LongInterval;
-import com.android.tools.r8.utils.SetUtils;
 import com.google.common.base.Equivalence;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ArrayListMultimap;
@@ -137,13 +145,13 @@
 import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Map;
 import java.util.PriorityQueue;
 import java.util.Set;
-import java.util.function.Consumer;
 import java.util.function.Predicate;
 
 public class CodeRewriter {
@@ -1833,187 +1841,205 @@
     return true;
   }
 
-  public void shortenLiveRanges(IRCode code) {
+  public void shortenLiveRanges(IRCode code, ConstantCanonicalizer canonicalizer) {
     if (options.testing.disableShortenLiveRanges) {
       return;
     }
-    // Currently, we are only shortening the live range of ConstNumbers in the entry block
-    // and ConstStrings with one user.
-    // TODO(ager): Generalize this to shorten live ranges for more instructions? Currently
-    // doing so seems to make things worse.
     LazyBox<DominatorTree> dominatorTreeMemoization = new LazyBox<>(() -> new DominatorTree(code));
-    Map<BasicBlock, Map<Value, Instruction>> addConstantInBlock = new IdentityHashMap<>();
+    Map<BasicBlock, LinkedHashMap<Value, Instruction>> addConstantInBlock = new IdentityHashMap<>();
     LinkedList<BasicBlock> blocks = code.blocks;
     for (BasicBlock block : blocks) {
-      if (block == blocks.getFirst()) {
-        // For the first block process all ConstNumber as well as ConstString instructions.
-        shortenLiveRangesInsideBlock(
-            code,
-            block,
-            dominatorTreeMemoization,
-            addConstantInBlock,
-            insn ->
-                (insn.isConstNumber() && insn.outValue().hasAnyUsers())
-                    || (insn.isConstString() && insn.outValue().hasAnyUsers()));
-      } else {
-        // For all following blocks only process ConstString with just one use.
-        shortenLiveRangesInsideBlock(
-            code,
-            block,
-            dominatorTreeMemoization,
-            addConstantInBlock,
-            insn -> insn.isConstString() && insn.outValue().numberOfAllUsers() == 1);
-      }
+      shortenLiveRangesInsideBlock(
+          code,
+          block,
+          dominatorTreeMemoization,
+          addConstantInBlock,
+          canonicalizer::isConstantCanonicalizationCandidate);
     }
 
     // Heuristic to decide if constant instructions are shared in dominator block
     // of usages or moved to the usages.
 
     // Process all blocks in stable order to avoid non-determinism of hash map iterator.
-    for (BasicBlock block : blocks) {
-      Map<Value, Instruction> constants = addConstantInBlock.get(block);
-      if (constants == null) {
+    BasicBlockIterator blockIterator = code.listIterator();
+    while (blockIterator.hasNext()) {
+      BasicBlock block = blockIterator.next();
+      Map<Value, Instruction> movedInstructions = addConstantInBlock.get(block);
+      if (movedInstructions == null) {
         continue;
       }
-
-      Set<Value> alreadyMoved = SetUtils.newIdentityHashSet(constants.size());
-      if (block != blocks.getFirst() && constants.size() > STOP_SHARED_CONSTANT_THRESHOLD) {
-        // If there are too many constants in the same block, they are copied rather than shared
-        // except if they are used by phi instructions or they are a string constants.
-        assert constants instanceof LinkedHashMap;
-        for (Instruction constantInstruction : constants.values()) {
-          if (!constantInstruction.outValue().hasPhiUsers()
-              && !constantInstruction.isConstString()) {
-            assert constantInstruction.isConstNumber();
-            ConstNumber constNumber = constantInstruction.asConstNumber();
-            Value constantValue = constantInstruction.outValue();
-            assert constantValue.hasUsers();
-            assert constantValue.numberOfUsers() == constantValue.numberOfAllUsers();
-            for (Instruction user : constantValue.uniqueUsers()) {
-              ConstNumber newCstNum = ConstNumber.copyOf(code, constNumber);
-              newCstNum.setPosition(user.getPosition());
-              InstructionListIterator iterator = user.getBlock().listIterator(code, user);
-              iterator.previous();
-              iterator.add(newCstNum);
-              user.replaceValue(constantValue, newCstNum.outValue());
-            }
-            constantValue.clearUsers();
-            alreadyMoved.add(constantInstruction.outValue());
-          }
-        }
+      assert !movedInstructions.isEmpty();
+      if (!block.isEntry() && movedInstructions.size() > STOP_SHARED_CONSTANT_THRESHOLD) {
+        // If there are too many constant numbers in the same block they are copied rather than
+        // shared unless used by a phi.
+        movedInstructions
+            .values()
+            .removeIf(
+                movedInstruction -> {
+                  if (movedInstruction.outValue().hasPhiUsers()
+                      || !movedInstruction.isConstNumber()) {
+                    return false;
+                  }
+                  ConstNumber constNumber = movedInstruction.asConstNumber();
+                  Value constantValue = movedInstruction.outValue();
+                  for (Instruction user : constantValue.uniqueUsers()) {
+                    ConstNumber newCstNum = ConstNumber.copyOf(code, constNumber);
+                    newCstNum.setPosition(user.getPosition());
+                    InstructionListIterator iterator = user.getBlock().listIterator(code, user);
+                    iterator.previous();
+                    iterator.add(newCstNum);
+                    user.replaceValue(constantValue, newCstNum.outValue());
+                  }
+                  constantValue.clearUsers();
+                  return true;
+                });
       }
 
       // Add constant into the dominator block of usages.
       boolean hasCatchHandlers = block.hasCatchHandlers();
-      InstructionListIterator it = block.listIterator(code);
-      while (it.hasNext()) {
-        Instruction instruction = it.next();
-        if (instruction.isJumpInstruction()
-            || (hasCatchHandlers && instruction.instructionTypeCanThrow())
-            || (options.canHaveCmpIfFloatBug() && instruction.isCmp())) {
+      InstructionListIterator instructionIterator = block.listIterator(code);
+      while (instructionIterator.hasNext()) {
+        Instruction insertionPoint = instructionIterator.next();
+        if (insertionPoint.isJumpInstruction()
+            || (hasCatchHandlers && insertionPoint.instructionTypeCanThrow())
+            || (options.canHaveCmpIfFloatBug() && insertionPoint.isCmp())) {
           break;
         }
-        forEachUse(
-            instruction,
-            use -> {
-              Instruction constantInstruction = constants.get(use);
-              if (constantInstruction != null && !alreadyMoved.contains(use)) {
-                it.previous();
-                constantInstruction.setPosition(instruction.getPosition());
-                it.add(constantInstruction);
-                it.next();
-                alreadyMoved.add(use);
-              }
-            });
-      }
-      // Insert remaining constant instructions prior to the "exit".
-      Instruction next = it.previous();
-      for (Instruction constantInstruction : constants.values()) {
-        if (!alreadyMoved.contains(constantInstruction.outValue())) {
-          constantInstruction.setPosition(next.getPosition());
-          it.add(constantInstruction);
+        for (Value use :
+            Iterables.concat(insertionPoint.inValues(), insertionPoint.getDebugValues())) {
+          Instruction movedInstruction = movedInstructions.remove(use);
+          if (movedInstruction != null) {
+            instructionIterator =
+                insertInstructionWithShortenedLiveRange(
+                    code, blockIterator, instructionIterator, movedInstruction, insertionPoint);
+          }
         }
       }
+
+      // Insert remaining constant instructions prior to the "exit".
+      Instruction insertionPoint = instructionIterator.peekPrevious();
+      for (Instruction movedInstruction : movedInstructions.values()) {
+        instructionIterator =
+            insertInstructionWithShortenedLiveRange(
+                code, blockIterator, instructionIterator, movedInstruction, insertionPoint);
+      }
     }
 
     assert code.isConsistentSSA(appView);
   }
 
-  private void forEachUse(Instruction instruction, Consumer<Value> fn) {
-    instruction.inValues().forEach(fn);
-    instruction.getDebugValues().forEach(fn);
+  private InstructionListIterator insertInstructionWithShortenedLiveRange(
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      InstructionListIterator instructionIterator,
+      Instruction movedInstruction,
+      Instruction insertionPoint) {
+    Instruction previous = instructionIterator.previous();
+    assert previous == insertionPoint;
+    movedInstruction.setPosition(
+        getPositionForMovedNonThrowingInstruction(movedInstruction, insertionPoint));
+    if (movedInstruction.instructionTypeCanThrow()
+        && insertionPoint.getBlock().hasCatchHandlers()) {
+      // Split the block and reset the block iterator.
+      BasicBlock splitBlock =
+          instructionIterator.splitCopyCatchHandlers(code, blockIterator, appView.options());
+      BasicBlock previousBlock = blockIterator.previousUntil(b -> b == splitBlock);
+      assert previousBlock == splitBlock;
+      blockIterator.next();
+
+      // Add the constant instruction before the exit instruction.
+      assert !instructionIterator.hasNext();
+      instructionIterator.previous();
+      instructionIterator.add(movedInstruction);
+
+      // Continue insertion at the entry of the split block.
+      instructionIterator = splitBlock.listIterator(code);
+    } else {
+      instructionIterator.add(movedInstruction);
+    }
+    Instruction next = instructionIterator.next();
+    assert next == insertionPoint;
+    return instructionIterator;
+  }
+
+  private Position getPositionForMovedNonThrowingInstruction(
+      Instruction movedInstruction, Instruction insertionPoint) {
+    // If the type of the moved instruction is throwing and we don't have a position at the
+    // insertion point, we use the special synthetic-none position, which is OK as the moved
+    // instruction instance is known not to throw (or we would not be allowed the move it).
+    if (movedInstruction.instructionTypeCanThrow() && !insertionPoint.getPosition().isSome()) {
+      return Position.syntheticNone();
+    }
+    return insertionPoint.getPosition();
   }
 
   private void shortenLiveRangesInsideBlock(
       IRCode code,
       BasicBlock block,
       LazyBox<DominatorTree> dominatorTreeMemoization,
-      Map<BasicBlock, Map<Value, Instruction>> addConstantInBlock,
-      Predicate<ConstInstruction> selector) {
+      Map<BasicBlock, LinkedHashMap<Value, Instruction>> addConstantInBlock,
+      Predicate<Instruction> selector) {
     InstructionListIterator iterator = block.listIterator(code);
     while (iterator.hasNext()) {
-      Instruction next = iterator.next();
-      if (!next.isConstInstruction()) {
+      Instruction instruction = iterator.next();
+      if (instruction.hasUnusedOutValue() || instruction.outValue().hasLocalInfo()) {
         continue;
       }
 
-      // We don't want to push const string instructions down into code that has monitors since
-      // we may attach catch handlers that are not catch-all when inlining. This is symmetric in how
-      // we don't do const string canonicalization.
-      if ((next.isConstString() || next.isDexItemBasedConstString())
-          && code.metadata().mayHaveMonitorInstruction()) {
+      if (!selector.test(instruction)) {
         continue;
       }
 
-      ConstInstruction instruction = next.asConstInstruction();
-      if (!selector.test(instruction) || instruction.outValue().hasLocalInfo()) {
-        continue;
-      }
-      Set<Instruction> uniqueUsers = instruction.outValue().uniqueUsers();
-      // Here we try to stop wasting time in the common case of large array of constants creation.
-      // We do not want to move a high number of constants up just to move them down because it
-      // takes multiple seconds in some cases (ZoneName clinit for instance).
-      // In array creation, the pattern is something like:
+      // Here we try to stop wasting time in the common case where constants are used immediately
+      // after their definition.
+      //
+      // This is especially important for the creation of large arrays, which has the following code
+      // pattern repeated many times, where the two loaded constants are only used by the ArrayPut
+      // instruction.
+      //
       //   Const number (the array index)
       //   Const (the array entry value)
       //   ArrayPut
-      // And both constants are used only in the put. The heuristic is therefore to check for
-      // constants used only once if the use is within the next two instructions, and only swap
-      // them if that is the case (cannot shorten the live range anyway).
-      // This heuristic drops down the time spent in large array of constant creation in
-      // shortenLiveRanges from multiple seconds to multiple milliseconds.
-      if (uniqueUsers.size() == 1 && instruction.outValue().uniquePhiUsers().size() == 0) {
-        Instruction uniqueUse = uniqueUsers.iterator().next();
-        if (iterator.hasNext()) {
-          Instruction nextNext = iterator.next();
-          if (uniqueUse == nextNext && nextNext.isArrayPut()) {
-            assert !uniqueUse.isConstInstruction();
+      //
+      // The heuristic is therefore to check for constants used only once if the use is within the
+      // next two instructions, and only swap them if that is the case (cannot shorten the live
+      // range anyway).
+      if (instruction.outValue().hasSingleUniqueUser() && !instruction.outValue().hasPhiUsers()) {
+        Instruction uniqueUse = instruction.outValue().singleUniqueUser();
+        Instruction next = iterator.next();
+        if (uniqueUse == next) {
+          continue;
+        }
+        if (next.hasOutValue()
+            && next.outValue().hasSingleUniqueUser()
+            && !next.outValue().hasPhiUsers()
+            && iterator.hasNext()) {
+          Instruction nextNext = iterator.peekNext();
+          Instruction uniqueUseNext = next.outValue().singleUniqueUser();
+          if (uniqueUse == nextNext && uniqueUseNext == nextNext) {
             continue;
           }
-          if (nextNext.isConstInstruction()) {
-            Set<Instruction> uniqueUsersNext = nextNext.outValue().uniqueUsers();
-            if (uniqueUsersNext.size() == 1
-                && nextNext.outValue().uniquePhiUsers().size() == 0
-                && iterator.hasNext()) {
-              Instruction nextNextNext = iterator.peekNext();
-              Instruction uniqueUseNext = uniqueUsersNext.iterator().next();
-              if (uniqueUse == nextNextNext
-                  && uniqueUseNext == nextNextNext
-                  && nextNextNext.isArrayPut()) {
-                continue;
-              }
-            }
-          }
-          iterator.previous();
         }
+        iterator.previous();
+        // The call to removeOrReplaceByDebugLocalRead() at the end of this method will remove the
+        // last returned element of this iterator. Therefore, we re-read this element from the
+        // iterator.
+        iterator.previous();
+        iterator.next();
       }
       // Collect the blocks for all users of the constant.
-      List<BasicBlock> userBlocks = new LinkedList<>();
-      for (Instruction user : uniqueUsers) {
+      Set<BasicBlock> userBlocks = new LinkedHashSet<>();
+      for (Instruction user : instruction.outValue().uniqueUsers()) {
         userBlocks.add(user.getBlock());
       }
       for (Phi phi : instruction.outValue().uniquePhiUsers()) {
-        userBlocks.add(phi.getBlock());
+        int predecessorIndex = 0;
+        for (Value operand : phi.getOperands()) {
+          if (operand == instruction.outValue()) {
+            userBlocks.add(phi.getBlock().getPredecessors().get(predecessorIndex));
+          }
+          predecessorIndex++;
+        }
       }
       // Locate the closest dominator block for all user blocks.
       DominatorTree dominatorTree = dominatorTreeMemoization.computeIfAbsent();
@@ -2044,14 +2070,35 @@
         }
       }
 
-      Map<Value, Instruction> csts =
-          addConstantInBlock.computeIfAbsent(dominator, k -> new LinkedHashMap<>());
-
-      ConstInstruction copy = instruction.isConstNumber()
-          ? ConstNumber.copyOf(code, instruction.asConstNumber())
-          : ConstString.copyOf(code, instruction.asConstString());
+      Instruction copy;
+      switch (instruction.opcode()) {
+        case CONST_CLASS:
+          copy = ConstClass.copyOf(code, instruction.asConstClass());
+          break;
+        case CONST_NUMBER:
+          copy = ConstNumber.copyOf(code, instruction.asConstNumber());
+          break;
+        case CONST_STRING:
+          copy = ConstString.copyOf(code, instruction.asConstString());
+          break;
+        case DEX_ITEM_BASED_CONST_STRING:
+          copy = DexItemBasedConstString.copyOf(code, instruction.asDexItemBasedConstString());
+          break;
+        case INSTANCE_GET:
+          copy = InstanceGet.copyOf(code, instruction.asInstanceGet());
+          break;
+        case STATIC_GET:
+          copy = StaticGet.copyOf(code, instruction.asStaticGet());
+          break;
+        default:
+          throw new Unreachable();
+      }
       instruction.outValue().replaceUsers(copy.outValue());
-      csts.put(copy.outValue(), copy);
+      addConstantInBlock
+          .computeIfAbsent(dominator, k -> new LinkedHashMap<>())
+          .put(copy.outValue(), copy);
+      assert iterator.peekPrevious() == instruction;
+      iterator.removeOrReplaceByDebugLocalRead();
     }
   }
 

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
index 7082cc6..5275a80 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java

@@ -7,50 +7,152 @@
 import static com.android.tools.r8.ir.code.Opcodes.CONST_NUMBER;
 import static com.android.tools.r8.ir.code.Opcodes.CONST_STRING;
 import static com.android.tools.r8.ir.code.Opcodes.DEX_ITEM_BASED_CONST_STRING;
+import static com.android.tools.r8.ir.code.Opcodes.INSTANCE_GET;
 import static com.android.tools.r8.ir.code.Opcodes.STATIC_GET;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
-import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.FieldAccessFlags;
+import com.android.tools.r8.graph.FieldResolutionResult.SingleFieldResolutionResult;
+import com.android.tools.r8.graph.ProgramField;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.analysis.value.SingleFieldValue;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.ConstString;
 import com.android.tools.r8.ir.code.DexItemBasedConstString;
+import com.android.tools.r8.ir.code.FieldGet;
+import com.android.tools.r8.ir.code.FieldInstruction;
 import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InstanceGet;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InstructionOrPhi;
+import com.android.tools.r8.ir.code.InvokeDirect;
+import com.android.tools.r8.ir.code.NewInstance;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.OptionalBool;
+import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.Hash.Strategy;
 import it.unimi.dsi.fastutil.objects.Object2ObjectLinkedOpenCustomHashMap;
 import it.unimi.dsi.fastutil.objects.Object2ObjectMap;
 import it.unimi.dsi.fastutil.objects.Object2ObjectSortedMap.FastSortedEntrySet;
 import java.util.ArrayList;
+import java.util.Collections;
+import java.util.IdentityHashMap;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Map;
+import java.util.Set;
 
 /**
  * Canonicalize constants.
  */
 public class ConstantCanonicalizer {
+
   // Threshold to limit the number of constant canonicalization.
   private static final int MAX_CANONICALIZED_CONSTANT = 22;
 
+  private final AppView<?> appView;
   private final CodeRewriter codeRewriter;
+  private final ProgramMethod context;
+  private final IRCode code;
 
-  public ConstantCanonicalizer(CodeRewriter codeRewriter) {
+  private OptionalBool isAccessingVolatileField = OptionalBool.unknown();
+  private Set<InstanceGet> ineligibleInstanceGetInstructions;
+
+  public ConstantCanonicalizer(
+      AppView<?> appView, CodeRewriter codeRewriter, ProgramMethod context, IRCode code) {
+    this.appView = appView;
     this.codeRewriter = codeRewriter;
+    this.context = context;
+    this.code = code;
   }
 
-  public void canonicalize(AppView<?> appView, IRCode code) {
-    ProgramMethod context = code.context();
-    Object2ObjectLinkedOpenCustomHashMap<Instruction, List<Value>> valuesDefinedByConstant =
+  private ConstantCanonicalizer clear() {
+    isAccessingVolatileField = OptionalBool.unknown();
+    ineligibleInstanceGetInstructions = null;
+    return this;
+  }
+
+  private boolean getOrComputeIsAccessingVolatileField() {
+    if (isAccessingVolatileField.isUnknown()) {
+      isAccessingVolatileField = OptionalBool.of(computeIsAccessingVolatileField());
+    }
+    return isAccessingVolatileField.isTrue();
+  }
+
+  private boolean computeIsAccessingVolatileField() {
+    if (!appView.hasClassHierarchy()) {
+      // Conservatively return true.
+      return true;
+    }
+    AppInfoWithClassHierarchy appInfo = appView.appInfoWithClassHierarchy();
+    for (FieldInstruction fieldGet :
+        code.<FieldInstruction>instructions(Instruction::isFieldInstruction)) {
+      SingleFieldResolutionResult<?> resolutionResult =
+          appInfo.resolveField(fieldGet.getField()).asSingleFieldResolutionResult();
+      if (resolutionResult == null
+          || resolutionResult.getResolvedField().getAccessFlags().isVolatile()) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  private Set<InstanceGet> getOrComputeIneligibleInstanceGetInstructions() {
+    if (ineligibleInstanceGetInstructions == null) {
+      ineligibleInstanceGetInstructions = computeIneligibleInstanceGetInstructions();
+    }
+    return ineligibleInstanceGetInstructions;
+  }
+
+  private Set<InstanceGet> computeIneligibleInstanceGetInstructions() {
+    Set<InstanceGet> ineligibleInstanceGetInstructions = Sets.newIdentityHashSet();
+    for (BasicBlock catchHandlerBlock : computeDirectAndIndirectCatchHandlerBlocks()) {
+      for (InstanceGet instanceGet :
+          catchHandlerBlock.<InstanceGet>getInstructions(Instruction::isInstanceGet)) {
+        // If the receiver is defined in a block with catch handlers and the definition of the
+        // receiver is not throwing (typically defined by an assume instruction or a phi), then we
+        // cant split the block and copy the catch handlers, since the canonicalized constant would
+        // then not be defined on the exceptional edge.
+        Value object = instanceGet.object();
+        if (!object.isDefinedByInstructionSatisfying(Instruction::instructionTypeCanThrow)
+            && object.getBlock().hasCatchHandlers()) {
+          ineligibleInstanceGetInstructions.add(instanceGet);
+        }
+      }
+    }
+    return ineligibleInstanceGetInstructions;
+  }
+
+  private Set<BasicBlock> computeDirectAndIndirectCatchHandlerBlocks() {
+    WorkList<BasicBlock> catchHandlerBlocks = WorkList.newIdentityWorkList();
+    for (BasicBlock block : code.getBlocks()) {
+      if (block.entry().isMoveException()) {
+        catchHandlerBlocks.addIfNotSeen(block);
+      }
+    }
+    while (catchHandlerBlocks.hasNext()) {
+      BasicBlock block = catchHandlerBlocks.next();
+      catchHandlerBlocks.addIfNotSeen(block.getSuccessors());
+    }
+    return catchHandlerBlocks.getSeenSet();
+  }
+
+  public ConstantCanonicalizer canonicalize() {
+    Object2ObjectLinkedOpenCustomHashMap<Instruction, List<Instruction>> valuesDefinedByConstant =
         new Object2ObjectLinkedOpenCustomHashMap<>(
             new Strategy<Instruction>() {
 
@@ -67,8 +169,9 @@
                     return candidate.asConstString().getValue().hashCode();
                   case DEX_ITEM_BASED_CONST_STRING:
                     return candidate.asDexItemBasedConstString().getItem().hashCode();
+                  case INSTANCE_GET:
                   case STATIC_GET:
-                    return candidate.asStaticGet().getField().hashCode();
+                    return candidate.asFieldGet().getField().hashCode();
                   default:
                     throw new Unreachable();
                 }
@@ -76,133 +179,114 @@
 
               @Override
               public boolean equals(Instruction a, Instruction b) {
-                // Constants with local info must not be canonicalized and must be filtered.
-                assert a == null || !a.outValue().hasLocalInfo();
-                assert b == null || !b.outValue().hasLocalInfo();
-                return a == b || (a != null && b != null && a.identicalNonValueNonPositionParts(b));
+                if (a == b) {
+                  return true;
+                }
+                if (a == null || b == null || a.getClass() != b.getClass()) {
+                  return false;
+                }
+                if (a.isInstanceGet() && a.getFirstOperand() != b.getFirstOperand()) {
+                  return false;
+                }
+                return a.identicalNonValueNonPositionParts(b);
               }
             });
 
     // Collect usages of constants that can be canonicalized.
-    for (Instruction current : code.instructions()) {
-      // Interested only in instructions types that can be canonicalized, i.e., ConstClass,
-      // ConstNumber, (DexItemBased)?ConstString, and StaticGet.
-      if (!current.instructionTypeCanBeCanonicalized()) {
-        continue;
+    for (Instruction instruction : code.instructions()) {
+      if (isConstantCanonicalizationCandidate(instruction)) {
+        valuesDefinedByConstant
+            .computeIfAbsent(instruction, ignoreKey(ArrayList::new))
+            .add(instruction);
       }
-      // Do not canonicalize ConstClass that may have side effects. Its original instructions
-      // will not be removed by dead code remover due to the side effects.
-      if (current.isConstClass() && current.instructionMayHaveSideEffects(appView, context)) {
-        continue;
-      }
-      // Do not canonicalize ConstString instructions if there are monitor operations in the code.
-      // That could lead to unbalanced locking and could lead to situations where OOM exceptions
-      // could leave a synchronized method without unlocking the monitor.
-      if ((current.isConstString() || current.isDexItemBasedConstString())
-          && code.metadata().mayHaveMonitorInstruction()) {
-        continue;
-      }
-      // Canonicalize effectively final fields that are guaranteed to be written before they are
-      // read. This is only OK if the instruction cannot have side effects.
-      if (current.isStaticGet()) {
-        AbstractValue abstractValue = current.outValue().getAbstractValue(appView, context);
-        if (!abstractValue.isSingleFieldValue()) {
-          continue;
-        }
-        SingleFieldValue singleFieldValue = abstractValue.asSingleFieldValue();
-        DexType fieldHolderType = singleFieldValue.getField().getHolderType();
-        if (context.getDefinition().isClassInitializer()
-            && context.getHolderType() == fieldHolderType) {
-          // Avoid that canonicalization inserts a read before the unique write in the class
-          // initializer, as that would change the program behavior.
-          continue;
-        }
-        DexClass fieldHolder = appView.definitionFor(fieldHolderType);
-        DexEncodedField field = singleFieldValue.getField().lookupOnClass(fieldHolder);
-        if (field == null
-            || !field.isEnum()
-            || current.instructionMayHaveSideEffects(appView, context)) {
-          // Only allow canonicalization of enums.
-          continue;
-        }
-      }
-      // Constants with local info must not be canonicalized and must be filtered.
-      if (current.outValue().hasLocalInfo()) {
-        continue;
-      }
-      // Constants that are used by invoke range are not canonicalized to be compliant with the
-      // optimization splitRangeInvokeConstant that gives the register allocator more freedom in
-      // assigning register to ranged invokes which can greatly reduce the number of register
-      // needed (and thereby code size as well). Thus no need to do a transformation that should
-      // be removed later by another optimization.
-      if (constantUsedByInvokeRange(current)) {
-        continue;
-      }
-      List<Value> oldValuesDefinedByConstant =
-          valuesDefinedByConstant.computeIfAbsent(current, k -> new ArrayList<>());
-      oldValuesDefinedByConstant.add(current.outValue());
     }
 
     if (valuesDefinedByConstant.isEmpty()) {
-      return;
+      return clear();
     }
 
     // Double-check the entry block does not have catch handlers.
     // Otherwise, we need to split it before moving canonicalized const-string, which may throw.
     assert !code.entryBlock().hasCatchHandlers();
-    FastSortedEntrySet<Instruction, List<Value>> entries =
+    FastSortedEntrySet<Instruction, List<Instruction>> entries =
         valuesDefinedByConstant.object2ObjectEntrySet();
     // Sort the most frequently used constant first and exclude constant use only one time, such
     // as the {@code MAX_CANONICALIZED_CONSTANT} will be canonicalized into the entry block.
-    Iterator<Object2ObjectMap.Entry<Instruction, List<Value>>> iterator =
+    Iterator<Object2ObjectMap.Entry<Instruction, List<Instruction>>> iterator =
         entries.stream()
             .filter(a -> a.getValue().size() > 1)
             .sorted((a, b) -> Integer.compare(b.getValue().size(), a.getValue().size()))
             .limit(MAX_CANONICALIZED_CONSTANT)
             .iterator();
-
     if (!iterator.hasNext()) {
-      return;
+      return clear();
     }
 
     boolean shouldSimplifyIfs = false;
+
+    // Insert instructions in the entry block.
+    Map<InstructionOrPhi, List<Instruction>> pendingInsertions = new IdentityHashMap<>();
     do {
-      Object2ObjectMap.Entry<Instruction, List<Value>> entry = iterator.next();
+      Object2ObjectMap.Entry<Instruction, List<Instruction>> entry = iterator.next();
       Instruction canonicalizedConstant = entry.getKey();
       assert canonicalizedConstant.instructionTypeCanBeCanonicalized();
-      Instruction newConst;
+      Instruction newInstruction;
       if (canonicalizedConstant.getBlock().isEntry()) {
-        newConst = canonicalizedConstant;
+        newInstruction = canonicalizedConstant;
       } else {
-        switch (canonicalizedConstant.opcode()) {
-          case CONST_CLASS:
-            newConst = ConstClass.copyOf(code, canonicalizedConstant.asConstClass());
-            break;
-          case CONST_NUMBER:
-            newConst = ConstNumber.copyOf(code, canonicalizedConstant.asConstNumber());
-            break;
-          case CONST_STRING:
-            newConst = ConstString.copyOf(code, canonicalizedConstant.asConstString());
-            break;
-          case DEX_ITEM_BASED_CONST_STRING:
-            newConst =
-                DexItemBasedConstString.copyOf(
-                    code, canonicalizedConstant.asDexItemBasedConstString());
-            break;
-          case STATIC_GET:
-            newConst = StaticGet.copyOf(code, canonicalizedConstant.asStaticGet());
-            break;
-          default:
-            throw new Unreachable();
+        newInstruction = createMaterializingInstruction(canonicalizedConstant);
+        InstructionOrPhi insertionPoint = getInsertionPointForCanonicalizedConstant(newInstruction);
+        if (insertionPoint == null) {
+          insertCanonicalizedConstantInEntryBlock(newInstruction);
+        } else {
+          // Record that this instruction needs to be inserted at the insertion position. Note that
+          // the insertion position may later be moved if it is itself subject to canonicalization.
+          addPendingInsertion(insertionPoint, newInstruction, pendingInsertions);
         }
-        insertCanonicalizedConstant(code, newConst);
       }
-      for (Value outValue : entry.getValue()) {
-        outValue.replaceUsers(newConst.outValue());
+      // Remove the canonicalized instructions.
+      for (Instruction oldInstruction : entry.getValue()) {
+        if (oldInstruction != newInstruction) {
+          oldInstruction.outValue().replaceUsers(newInstruction.outValue());
+          oldInstruction
+              .getBlock()
+              .listIterator(code, oldInstruction)
+              .removeOrReplaceByDebugLocalRead();
+
+          // If the removed instruction is an insertion point for another constant, then record that
+          // the constant should instead be inserted at the point where the removed instruction has
+          // been moved to.
+          for (Instruction pendingInsertion :
+              removePendingInsertions(oldInstruction, pendingInsertions)) {
+            addPendingInsertion(newInstruction, pendingInsertion, pendingInsertions);
+          }
+        }
       }
-      shouldSimplifyIfs |= newConst.outValue().hasUserThatMatches(Instruction::isIf);
+      shouldSimplifyIfs |= newInstruction.outValue().hasUserThatMatches(Instruction::isIf);
     } while (iterator.hasNext());
 
+    // Insert instructions that cannot be inserted in the entry block.
+    if (!pendingInsertions.isEmpty()) {
+      BasicBlockIterator blockIterator = code.listIterator();
+      while (blockIterator.hasNext()) {
+        BasicBlock block = blockIterator.next();
+        InstructionListIterator instructionIterator = block.listIterator(code);
+        for (Phi insertionPoint : block.getPhis()) {
+          instructionIterator =
+              insertPendingInsertions(
+                  blockIterator, instructionIterator, insertionPoint, pendingInsertions);
+        }
+        while (instructionIterator.hasNext()) {
+          Instruction insertionPoint = instructionIterator.next();
+          instructionIterator =
+              insertPendingInsertions(
+                  blockIterator, instructionIterator, insertionPoint, pendingInsertions);
+        }
+      }
+    }
+
+    assert pendingInsertions.isEmpty();
+
     shouldSimplifyIfs |= code.removeAllDeadAndTrivialPhis();
 
     if (shouldSimplifyIfs) {
@@ -210,9 +294,265 @@
     }
 
     assert code.isConsistentSSA(appView);
+    return clear();
   }
 
-  private static void insertCanonicalizedConstant(IRCode code, Instruction canonicalizedConstant) {
+  private void addPendingInsertion(
+      InstructionOrPhi insertionPoint,
+      Instruction newInstruction,
+      Map<InstructionOrPhi, List<Instruction>> pendingInsertions) {
+    pendingInsertions
+        .computeIfAbsent(insertionPoint, ignoreKey(ArrayList::new))
+        .add(newInstruction);
+  }
+
+  private InstructionListIterator insertPendingInsertions(
+      BasicBlockIterator blockIterator,
+      InstructionListIterator instructionIterator,
+      InstructionOrPhi insertionPoint,
+      Map<InstructionOrPhi, List<Instruction>> pendingInsertions) {
+    List<Instruction> pendingInsertionsAtInsertionPoint =
+        removePendingInsertions(insertionPoint, pendingInsertions);
+    if (pendingInsertionsAtInsertionPoint.isEmpty()) {
+      return instructionIterator;
+    }
+    WorkList<Instruction> worklist =
+        WorkList.newIdentityWorkList(pendingInsertionsAtInsertionPoint);
+    while (worklist.hasNext()) {
+      Instruction newInstruction = worklist.next();
+      List<Instruction> pendingInsertionsAfterNewInstruction =
+          removePendingInsertions(newInstruction, pendingInsertions);
+      if (pendingInsertionsAfterNewInstruction.isEmpty()) {
+        instructionIterator =
+            insertCanonicalizedConstantAtInsertionPoint(
+                blockIterator, instructionIterator, insertionPoint, newInstruction);
+      } else {
+        // Process pending insertions before the current instruction to ensure the current
+        // instruction ends up first in the instruction stream.
+        worklist.addIfNotSeen(pendingInsertionsAfterNewInstruction);
+        worklist.addIgnoringSeenSet(newInstruction);
+      }
+    }
+    return instructionIterator;
+  }
+
+  private List<Instruction> removePendingInsertions(
+      InstructionOrPhi insertionPoint, Map<InstructionOrPhi, List<Instruction>> pendingInsertions) {
+    List<Instruction> pendingInstructionsAtInsertionPosition =
+        pendingInsertions.remove(insertionPoint);
+    return pendingInstructionsAtInsertionPosition != null
+        ? pendingInstructionsAtInsertionPosition
+        : Collections.emptyList();
+  }
+
+  private InstructionOrPhi getInsertionPointForCanonicalizedConstant(Instruction newInstruction) {
+    switch (newInstruction.opcode()) {
+      case CONST_CLASS:
+      case CONST_NUMBER:
+      case CONST_STRING:
+      case DEX_ITEM_BASED_CONST_STRING:
+      case STATIC_GET:
+        // Insert in entry block.
+        return null;
+      case INSTANCE_GET:
+        {
+          InstanceGet instanceGet = newInstruction.asInstanceGet();
+          Value object = instanceGet.object();
+          if (object.isThis()) {
+            return null;
+          }
+          if (object.isPhi()) {
+            return object.asPhi();
+          }
+          Instruction definition = object.getDefinition();
+          if (definition.isArgument()) {
+            return code.getLastArgument();
+          }
+          if (definition.isNewInstance()) {
+            InvokeDirect uniqueConstructorInvoke =
+                definition.asNewInstance().getUniqueConstructorInvoke(appView.dexItemFactory());
+            // This is guaranteed to be non-null by isConstantCanonicalizationCandidate.
+            assert uniqueConstructorInvoke != null;
+            return uniqueConstructorInvoke;
+          }
+          return definition;
+        }
+      default:
+        throw new Unreachable();
+    }
+  }
+
+  private Instruction createMaterializingInstruction(Instruction canonicalizedConstant) {
+    switch (canonicalizedConstant.opcode()) {
+      case CONST_CLASS:
+        return ConstClass.copyOf(code, canonicalizedConstant.asConstClass());
+      case CONST_NUMBER:
+        return ConstNumber.copyOf(code, canonicalizedConstant.asConstNumber());
+      case CONST_STRING:
+        return ConstString.copyOf(code, canonicalizedConstant.asConstString());
+      case DEX_ITEM_BASED_CONST_STRING:
+        return DexItemBasedConstString.copyOf(
+            code, canonicalizedConstant.asDexItemBasedConstString());
+      case INSTANCE_GET:
+        return InstanceGet.copyOf(code, canonicalizedConstant.asInstanceGet());
+      case STATIC_GET:
+        return StaticGet.copyOf(code, canonicalizedConstant.asStaticGet());
+      default:
+        throw new Unreachable();
+    }
+  }
+
+  public boolean isConstantCanonicalizationCandidate(Instruction instruction) {
+    // Interested only in instructions types that can be canonicalized, i.e., ConstClass,
+    // ConstNumber, (DexItemBased)?ConstString, InstanceGet and StaticGet.
+    switch (instruction.opcode()) {
+      case CONST_CLASS:
+        // Do not canonicalize ConstClass that may have side effects. Its original instructions
+        // will not be removed by dead code remover due to the side effects.
+        if (instruction.instructionMayHaveSideEffects(appView, context)) {
+          return false;
+        }
+        break;
+      case CONST_NUMBER:
+        break;
+      case CONST_STRING:
+      case DEX_ITEM_BASED_CONST_STRING:
+        break;
+      case INSTANCE_GET:
+        {
+          InstanceGet instanceGet = instruction.asInstanceGet();
+          if (instanceGet.instructionMayHaveSideEffects(appView, context)) {
+            return false;
+          }
+          if (instanceGet.object().isDefinedByInstructionSatisfying(Instruction::isNewInstance)) {
+            NewInstance newInstance = instanceGet.object().getDefinition().asNewInstance();
+            if (newInstance.getUniqueConstructorInvoke(appView.dexItemFactory()) == null) {
+              return false;
+            }
+          }
+          if (!isReadOfFinalFieldOutsideInitializer(instanceGet)) {
+            return false;
+          }
+          if (getOrComputeIneligibleInstanceGetInstructions().contains(instanceGet)) {
+            return false;
+          }
+          break;
+        }
+      case STATIC_GET:
+        {
+          // Canonicalize effectively final fields that are guaranteed to be written before they are
+          // read. This is only OK if the instruction cannot have side effects.
+          StaticGet staticGet = instruction.asStaticGet();
+          if (staticGet.instructionMayHaveSideEffects(appView, context)) {
+            return false;
+          }
+          if (!isReadOfFinalFieldOutsideInitializer(staticGet)
+              && !isEffectivelyFinalField(staticGet)) {
+            return false;
+          }
+          break;
+        }
+      default:
+        assert !instruction.instructionTypeCanBeCanonicalized() : instruction.toString();
+        return false;
+    }
+    // Constants with local info must not be canonicalized and must be filtered.
+    if (instruction.outValue().hasLocalInfo()) {
+      return false;
+    }
+    // Do not canonicalize throwing instructions if there are monitor operations in the code.
+    // That could lead to unbalanced locking and could lead to situations where OOM exceptions
+    // could leave a synchronized method without unlocking the monitor.
+    if (instruction.instructionTypeCanThrow() && code.metadata().mayHaveMonitorInstruction()) {
+      return false;
+    }
+    // Constants that are used by invoke range are not canonicalized to be compliant with the
+    // optimization splitRangeInvokeConstant that gives the register allocator more freedom in
+    // assigning register to ranged invokes which can greatly reduce the number of register
+    // needed (and thereby code size as well). Thus no need to do a transformation that should
+    // be removed later by another optimization.
+    if (constantUsedByInvokeRange(instruction)) {
+      return false;
+    }
+    return true;
+  }
+
+  private boolean isReadOfFinalFieldOutsideInitializer(FieldGet fieldGet) {
+    if (getOrComputeIsAccessingVolatileField()) {
+      // A final field may be initialized concurrently. A requirement for this is that the field is
+      // volatile. However, the reading or writing of another volatile field also allows for
+      // concurrently initializing a non-volatile field. See also redundant field load elimination.
+      return false;
+    }
+    AppView<? extends AppInfoWithClassHierarchy> appViewWithClassHierarchy =
+        appView.withClassHierarchy();
+    SingleFieldResolutionResult<?> resolutionResult =
+        appViewWithClassHierarchy
+            .appInfo()
+            .resolveField(fieldGet.getField())
+            .asSingleFieldResolutionResult();
+    if (resolutionResult == null) {
+      // Not known to be final.
+      return false;
+    }
+    if (!resolutionResult.isSingleProgramFieldResolutionResult()) {
+      // We can't rely on the final flag of non-program fields.
+      return false;
+    }
+    ProgramField resolvedField = resolutionResult.getSingleProgramField();
+    FieldAccessFlags accessFlags = resolvedField.getAccessFlags();
+    assert !accessFlags.isVolatile();
+    // TODO(b/236661949): Add support for effectively final fields so that this also works well
+    //  without -allowaccessmodification.
+    if (!accessFlags.isFinal()) {
+      return false;
+    }
+    if (appView.getKeepInfo(resolvedField).isPinned(appView.options())) {
+      // The final flag could be unset using reflection.
+      return false;
+    }
+    if (context.getDefinition().isInitializer()
+        && context.getAccessFlags().isStatic() == fieldGet.isStaticGet()) {
+      if (context.getHolder() == resolvedField.getHolder()) {
+        // If this is an initializer on the field's holder, then bail out, since the field value is
+        // only known to be final after object/class creation.
+        return false;
+      }
+      if (fieldGet.isInstanceGet()
+          && appViewWithClassHierarchy
+              .appInfo()
+              .isSubtype(context.getHolder(), resolvedField.getHolder())) {
+        // If an instance initializer reads a final instance field declared in a super class, we
+        // cannot hoist the read above the parent constructor call.
+        return false;
+      }
+    }
+    if (!resolutionResult.getInitialResolutionHolder().isResolvable(appView)) {
+      // If this field read is guarded by an API level check, hoisting of this field could lead to
+      // a ClassNotFoundException on some API levels.
+      return false;
+    }
+    return true;
+  }
+
+  private boolean isEffectivelyFinalField(StaticGet staticGet) {
+    AbstractValue abstractValue = staticGet.outValue().getAbstractValue(appView, context);
+    if (!abstractValue.isSingleFieldValue()) {
+      return false;
+    }
+    SingleFieldValue singleFieldValue = abstractValue.asSingleFieldValue();
+    DexType fieldHolderType = singleFieldValue.getField().getHolderType();
+    if (context.getDefinition().isClassInitializer()
+        && context.getHolderType() == fieldHolderType) {
+      // Avoid that canonicalization inserts a read before the unique write in the class
+      // initializer, as that would change the program behavior.
+      return false;
+    }
+    DexClass fieldHolder = appView.definitionFor(fieldHolderType);
+    return singleFieldValue.getField().lookupOnClass(fieldHolder) != null;
+  }
+
+  private void insertCanonicalizedConstantInEntryBlock(Instruction canonicalizedConstant) {
     BasicBlock entryBlock = code.entryBlock();
     // Insert the constant instruction at the start of the block right after the argument
     // instructions. It is important that the const instruction is put before any instruction
@@ -229,6 +569,63 @@
     it.add(canonicalizedConstant);
   }
 
+  private InstructionListIterator insertCanonicalizedConstantAtInsertionPoint(
+      BasicBlockIterator blockIterator,
+      InstructionListIterator instructionIterator,
+      InstructionOrPhi insertionPoint,
+      Instruction newInstruction) {
+    // If the insertion point is a phi, then we're inserting the new instruction before all other
+    // instructions in the block.
+    assert !insertionPoint.isPhi() || !instructionIterator.hasPrevious();
+    // If the insertion point is not a phi, the iterator is positioned immediately after the
+    // insertion point.
+    assert insertionPoint.isPhi() || instructionIterator.peekPrevious() == insertionPoint;
+    newInstruction.setPosition(
+        getPositionForCanonicalizationConstantAtInsertionPoint(insertionPoint, newInstruction));
+    if (newInstruction.instructionTypeCanThrow()
+        && insertionPoint.getBlock().hasCatchHandlers()
+        && insertionPoint.getBlock().canThrow()) {
+      // Split the block and rewind the block iterator to the insertion block.
+      BasicBlock splitBlock =
+          instructionIterator.splitCopyCatchHandlers(
+              code, blockIterator, appView.options(), ignore -> insertionPoint.getBlock());
+      if (insertionPoint.isPhi()) {
+        // Add new instruction before the goto and position the instruction iterator before the
+        // first instruction (i.e., at the phi position).
+        assert insertionPoint.getBlock().getInstructions().size() == 1;
+        instructionIterator.addBeforeAndPositionBeforeNewInstruction(newInstruction);
+        assert !instructionIterator.hasPrevious();
+      } else {
+        // Add the new instruction after the insertion point. If the block containing the insertion
+        // point can throw, we insert the new instruction in the beginning of the split block.
+        // Otherwise, we insert it in the end of the insertion block.
+        if (insertionPoint.getBlock().canThrow()) {
+          assert !splitBlock.canThrow();
+          splitBlock.listIterator(code).add(newInstruction);
+        } else {
+          assert splitBlock.canThrow();
+          instructionIterator.addBeforeAndPositionBeforeNewInstruction(newInstruction);
+        }
+        instructionIterator.positionAfterPreviousInstruction(insertionPoint.asInstruction());
+      }
+    } else {
+      instructionIterator.addAndPositionBeforeNewInstruction(newInstruction);
+    }
+    return instructionIterator;
+  }
+
+  private Position getPositionForCanonicalizationConstantAtInsertionPoint(
+      InstructionOrPhi insertionPoint, Instruction newInstruction) {
+    Position insertionPosition =
+        insertionPoint.isPhi()
+            ? insertionPoint.getBlock().getPosition()
+            : insertionPoint.asInstruction().getPosition();
+    if (newInstruction.instructionTypeCanThrow() && insertionPosition.isNone()) {
+      return Position.syntheticNone();
+    }
+    return insertionPosition;
+  }
+
   private static boolean constantUsedByInvokeRange(Instruction constant) {
     for (Instruction user : constant.outValue().uniqueUsers()) {
       if (user.isInvoke() && user.asInvoke().requiredArgumentRegisters() > 5) {

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
index 5930cd3..8a023db 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java

@@ -17,6 +17,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.code.Assume;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.DominatorTree;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
@@ -32,7 +33,6 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import java.util.IdentityHashMap;
-import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
 
@@ -65,7 +65,7 @@
     Map<Value, Map<DexType, Value>> castedReceiverCache = new IdentityHashMap<>();
     Set<SafeCheckCast> newCheckCastInstructions = Sets.newIdentityHashSet();
 
-    ListIterator<BasicBlock> blocks = code.listIterator();
+    BasicBlockIterator blocks = code.listIterator();
     while (blocks.hasNext()) {
       BasicBlock block = blocks.next();
       InstructionListIterator it = block.listIterator(code);

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index f0980f3..9a38d14 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java

@@ -1212,9 +1212,7 @@
   }
 
   private void applyMemberValuePropagationToInlinee(
-      IRCode code,
-      ListIterator<BasicBlock> blockIterator,
-      Set<BasicBlock> inlineeBlocks) {
+      IRCode code, BasicBlockIterator blockIterator, Set<BasicBlock> inlineeBlocks) {
     Set<Value> affectedValues = Sets.newIdentityHashSet();
     new R8MemberValuePropagation(appView)
         .run(code, blockIterator, affectedValues, inlineeBlocks::contains);

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
index ed028ee..7327231 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java

@@ -20,6 +20,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.code.ArrayAccess;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.If;
@@ -48,7 +49,6 @@
 import java.util.IdentityHashMap;
 import java.util.Iterator;
 import java.util.List;
-import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
 
@@ -124,7 +124,7 @@
     ProgramMethod context = code.context();
     Map<Instruction, DexType> convertedEnums = createInitialConvertedEnums(code, prototypeChanges);
     Set<Phi> affectedPhis = Sets.newIdentityHashSet();
-    ListIterator<BasicBlock> blocks = code.listIterator();
+    BasicBlockIterator blocks = code.listIterator();
     Set<BasicBlock> seenBlocks = Sets.newIdentityHashSet();
     Set<Instruction> instructionsToRemove = Sets.newIdentityHashSet();
     Value zeroConstValue = null;

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/D8MemberValuePropagation.java b/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/D8MemberValuePropagation.java
index 020d86e..b9ab26a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/D8MemberValuePropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/D8MemberValuePropagation.java

@@ -8,7 +8,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.code.ArrayGet;
-import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.InstanceGet;
 import com.android.tools.r8.ir.code.InstancePut;
@@ -18,7 +18,6 @@
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.optimize.membervaluepropagation.assume.AssumeInfo;
-import java.util.ListIterator;
 import java.util.Set;
 
 public class D8MemberValuePropagation extends MemberValuePropagation<AppInfo> {
@@ -31,7 +30,7 @@
   void rewriteArrayGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       ArrayGet arrayGet) {
     // Intentionally empty.
@@ -41,7 +40,7 @@
   void rewriteInstanceGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       InstanceGet current) {
     // Intentionally empty.
@@ -57,7 +56,7 @@
       IRCode code,
       ProgramMethod context,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       InvokeMethod invoke) {
     // Intentionally empty.
@@ -67,7 +66,7 @@
   void rewriteStaticGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       StaticGet current) {
     AssumeInfo assumeInfo = appView.getAssumeInfoCollection().get(current.getField());

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/MemberValuePropagation.java b/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/MemberValuePropagation.java
index 14a54b1..4d89225 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/MemberValuePropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/MemberValuePropagation.java

@@ -24,6 +24,7 @@
 import com.android.tools.r8.ir.analysis.value.SingleValue;
 import com.android.tools.r8.ir.code.ArrayGet;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.IRMetadata;
 import com.android.tools.r8.ir.code.InstanceGet;
@@ -38,7 +39,6 @@
 import com.android.tools.r8.ir.optimize.membervaluepropagation.assume.AssumeInfo;
 import com.android.tools.r8.utils.IteratorUtils;
 import com.google.common.collect.Sets;
-import java.util.ListIterator;
 import java.util.Set;
 import java.util.function.Predicate;
 
@@ -71,7 +71,7 @@
 
   public void run(
       IRCode code,
-      ListIterator<BasicBlock> blockIterator,
+      BasicBlockIterator blockIterator,
       Set<Value> affectedValues,
       Predicate<BasicBlock> blockTester) {
     ProgramMethod context = code.context();
@@ -118,14 +118,14 @@
   abstract void rewriteArrayGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       ArrayGet arrayGet);
 
   abstract void rewriteInstanceGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       InstanceGet current);
 
@@ -136,14 +136,14 @@
       IRCode code,
       ProgramMethod context,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       InvokeMethod invoke);
 
   abstract void rewriteStaticGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       StaticGet current);
 
@@ -152,7 +152,7 @@
   boolean applyAssumeInfo(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       Instruction current,
       AssumeInfo assumeInfo) {

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/R8MemberValuePropagation.java b/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/R8MemberValuePropagation.java
index bc33a3a..587a78c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/R8MemberValuePropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/membervaluepropagation/R8MemberValuePropagation.java

@@ -20,6 +20,7 @@
 import com.android.tools.r8.ir.analysis.value.UnknownValue;
 import com.android.tools.r8.ir.code.ArrayGet;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.FieldInstruction;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.InstanceGet;
@@ -36,7 +37,6 @@
 import com.android.tools.r8.ir.optimize.membervaluepropagation.assume.AssumeInfo;
 import com.android.tools.r8.ir.optimize.membervaluepropagation.assume.AssumeInfoLookup;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.ListIterator;
 import java.util.Set;
 
 public class R8MemberValuePropagation extends MemberValuePropagation<AppInfoWithLiveness> {
@@ -51,7 +51,7 @@
   void rewriteArrayGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       ArrayGet arrayGet) {
     TypeElement arrayType = arrayGet.array().getType();
@@ -123,7 +123,7 @@
       IRCode code,
       ProgramMethod context,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       InvokeMethod invoke) {
     if (invoke.hasUnusedOutValue()) {
@@ -208,7 +208,7 @@
   void rewriteInstanceGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       InstanceGet current) {
     rewriteFieldGet(code, affectedValues, blocks, iterator, current);
@@ -218,7 +218,7 @@
   void rewriteStaticGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       StaticGet current) {
     rewriteFieldGet(code, affectedValues, blocks, iterator, current);
@@ -227,7 +227,7 @@
   private void rewriteFieldGet(
       IRCode code,
       Set<Value> affectedValues,
-      ListIterator<BasicBlock> blocks,
+      BasicBlockIterator blocks,
       InstructionListIterator iterator,
       FieldInstruction current) {
     DexField field = current.getField();

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 2606826..ee85c13 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

@@ -35,6 +35,8 @@
 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.LoopNode;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.NewInstanceNode;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.SplitReferenceNode;
 import com.android.tools.r8.ir.optimize.string.StringBuilderNodeMuncher.MunchingState;
 import com.android.tools.r8.ir.optimize.string.StringBuilderOracle.DefaultStringBuilderOracle;
 import com.android.tools.r8.utils.DepthFirstSearchWorkListBase.DepthFirstSearchWorkList;
@@ -42,6 +44,9 @@
 import com.android.tools.r8.utils.TraversalContinuation;
 import com.android.tools.r8.utils.WorkList;
 import com.google.common.collect.Sets;
+import it.unimi.dsi.fastutil.objects.Reference2IntLinkedOpenHashMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap.Entry;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.IdentityHashMap;
@@ -284,7 +289,7 @@
               } else if (oracle.isAppend(instruction)) {
                 AppendNode appendNode = createAppendNode(instruction.asInvokeVirtual());
                 appendNode.setConstantArgument(oracle.getConstantArgument(instruction));
-                Value arg = invoke.getOperand(1).getAliasedValue();
+                Value arg = invoke.getFirstNonReceiverArgument().getAliasedValue();
                 if (oracle.hasStringBuilderType(arg)) {
                   insertImplicitToStringNode(
                       arg, instruction, appendNode, escapeState, nodeConsumer);
@@ -416,10 +421,13 @@
               DFSNodeWithState<BasicBlock, StringBuilderGraphState> node,
               List<DFSNodeWithState<BasicBlock, StringBuilderGraphState>> childStates) {
             StringBuilderGraphState state = node.getState();
+            Reference2IntMap<Value> rootsInChildStateCounts =
+                new Reference2IntLinkedOpenHashMap<>();
             for (DFSNodeWithState<BasicBlock, StringBuilderGraphState> childState : childStates) {
               StringBuilderGraphState childGraphState = childState.getState();
               childGraphState.roots.forEach(
                   (value, sbNode) -> {
+                    rootsInChildStateCounts.put(value, rootsInChildStateCounts.getInt(value) + 1);
                     StringBuilderNode currentRoot = state.roots.get(value);
                     StringBuilderNode currentTail = state.tails.get(value);
                     if (currentRoot == null) {
@@ -446,6 +454,18 @@
                 childGraphState.isPartOfLoop = true;
               }
             }
+            // To ensure that we account for control flow correctly, we insert split reference nodes
+            // for all roots we've seen in only a subset of child states.
+            for (Entry<Value> valueEntry : rootsInChildStateCounts.reference2IntEntrySet()) {
+              assert valueEntry.getIntValue() <= childStates.size();
+              if (valueEntry.getIntValue() < childStates.size()) {
+                SplitReferenceNode splitNode = StringBuilderNode.createSplitReferenceNode();
+                StringBuilderNode tail = state.tails.get(valueEntry.getKey());
+                assert tail != null;
+                splitNode.addPredecessor(tail);
+                tail.addSuccessor(splitNode);
+              }
+            }
             if (state.isPartOfLoop) {
               state.roots.replaceAll(
                   (value, currentRoot) -> {
@@ -475,6 +495,7 @@
       Map<Value, StringBuilderNode> stringBuilderGraphs) {
     Map<Instruction, StringBuilderAction> actions = new IdentityHashMap<>();
     // Build state to allow munching over the string builder graphs.
+    Map<StringBuilderNode, NewInstanceNode> newInstances = new IdentityHashMap<>();
     Set<StringBuilderNode> inspectingCapacity = Sets.newIdentityHashSet();
     Set<StringBuilderNode> looping = Sets.newIdentityHashSet();
     Map<StringBuilderNode, Set<StringBuilderNode>> materializing = new IdentityHashMap<>();
@@ -492,6 +513,10 @@
           while (workList.hasNext()) {
             StringBuilderNode next = workList.next();
             nodeToRoots.put(next, root);
+            if (next.isNewInstanceNode()) {
+              StringBuilderNode existing = newInstances.put(root, next.asNewInstanceNode());
+              assert existing == null;
+            }
             if (next.isInitOrAppend()) {
               ImplicitToStringNode dependency = next.asInitOrAppend().getImplicitToStringNode();
               if (dependency != null) {
@@ -508,7 +533,7 @@
               escaping.add(root);
             }
             if (next.isToStringNode() || next.isImplicitToStringNode()) {
-              materializingInstructions.add(root);
+              materializingInstructions.add(next);
             }
             if (next.isInspectingNode()) {
               inspectingCapacity.add(root);
@@ -518,7 +543,8 @@
         });
 
     MunchingState munchingState =
-        new MunchingState(actions, escaping, inspectingCapacity, looping, materializing, oracle);
+        new MunchingState(
+            actions, escaping, inspectingCapacity, looping, materializing, newInstances, oracle);
 
     boolean keepMunching = true;
     for (int i = 0; i < NUMBER_OF_MUNCHING_PASSES && keepMunching; i++) {

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 01be10c..0659a8a 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

@@ -13,6 +13,7 @@
 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.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;
@@ -39,6 +40,7 @@
     private final Set<StringBuilderNode> inspectingCapacity;
     private final Set<StringBuilderNode> looping;
     private final Map<StringBuilderNode, Set<StringBuilderNode>> materializingInstructions;
+    private final Map<StringBuilderNode, NewInstanceNode> newInstances;
     private final Map<Value, String> optimizedStrings = new IdentityHashMap<>();
 
     MunchingState(
@@ -47,14 +49,24 @@
         Set<StringBuilderNode> inspectingCapacity,
         Set<StringBuilderNode> looping,
         Map<StringBuilderNode, Set<StringBuilderNode>> materializingInstructions,
+        Map<StringBuilderNode, NewInstanceNode> newInstances,
         StringBuilderOracle oracle) {
       this.actions = actions;
       this.escaping = escaping;
       this.inspectingCapacity = inspectingCapacity;
       this.looping = looping;
       this.materializingInstructions = materializingInstructions;
+      this.newInstances = newInstances;
       this.oracle = oracle;
     }
+
+    public NewInstanceNode getNewInstanceNode(StringBuilderNode root) {
+      return newInstances.get(root);
+    }
+
+    public boolean isLooping(StringBuilderNode root) {
+      return looping.contains(root);
+    }
   }
 
   private interface PeepholePattern {
@@ -132,11 +144,11 @@
       if (!currentNode.isToStringNode() && !currentNode.isImplicitToStringNode()) {
         return false;
       }
-      StringBuilderNode root = findFirstNonSentinelRoot(originalRoot);
-      if (!root.isNewInstanceNode() || !root.hasSingleSuccessor()) {
+      NewInstanceNode newInstanceNode = munchingState.getNewInstanceNode(originalRoot);
+      if (newInstanceNode == null || !newInstanceNode.hasSingleSuccessor()) {
         return false;
       }
-      StringBuilderNode init = root.getSingleSuccessor();
+      StringBuilderNode init = newInstanceNode.getSingleSuccessor();
       String rootConstantArgument = getConstantArgumentForNode(init, munchingState);
       if (rootConstantArgument == null || !init.isInitNode()) {
         return false;
@@ -167,7 +179,6 @@
         ToStringNode toStringNode = currentNode.asToStringNode();
         munchingState.actions.put(
             toStringNode.getInstruction(), new ReplaceByConstantString(constantArgument));
-        munchingState.materializingInstructions.get(originalRoot).remove(currentNode);
         String oldValue =
             munchingState.optimizedStrings.put(
                 toStringNode.getInstruction().outValue(), constantArgument);
@@ -180,29 +191,12 @@
         munchingState.actions.put(
             initOrAppend.getInstruction(), new AppendWithNewConstantString(constantArgument));
       }
+      munchingState.materializingInstructions.get(originalRoot).remove(currentNode);
       currentNode.removeNode();
       return true;
     }
   }
 
-  /**
-   * Find the first non split reference node or loop-node, which are nodes inserted to track
-   * control-flow.
-   */
-  private static StringBuilderNode findFirstNonSentinelRoot(StringBuilderNode root) {
-    WorkList<StringBuilderNode> workList = WorkList.newIdentityWorkList(root);
-    while (workList.hasNext()) {
-      StringBuilderNode node = workList.next();
-      if (!node.isSplitReferenceNode() && !node.isLoopNode()) {
-        return node;
-      }
-      if (node.hasSingleSuccessor()) {
-        workList.addIfNotSeen(node.getSingleSuccessor());
-      }
-    }
-    return root;
-  }
-
   private static String getConstantArgumentForNode(
       StringBuilderNode node, MunchingState munchingState) {
     if (node.isAppendNode()) {
@@ -249,7 +243,7 @@
         // Remove appends if the string builder do not escape, is not inspected or materialized
         // and if it is not part of a loop.
         removeNode = false;
-        if (currentNode.isSplitReferenceNode()) {
+        if (currentNode.isSplitReferenceNode() && !munchingState.isLooping(root)) {
           removeNode = currentNode.getSuccessors().isEmpty() || currentNode.hasSinglePredecessor();
         } else if (currentNode.isAppendNode() && !isEscaping) {
           AppendNode appendNode = currentNode.asAppendNode();
@@ -261,7 +255,7 @@
                   && currentNode.getSuccessors().isEmpty();
           if (canRemoveIfNoInspectionOrMaterializing
               && canRemoveIfLastAndNoLoop
-              && munchingState.oracle.canObserveStringBuilderCall(
+              && !munchingState.oracle.canObserveStringBuilderCall(
                   currentNode.asAppendNode().getInstruction())) {
             munchingState.actions.put(
                 appendNode.getInstruction(), RemoveStringBuilderAction.getInstance());

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 d7d7f59..063f791 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

@@ -12,6 +12,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InvokeDirect;
+import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.Value;
 import java.util.List;
@@ -109,7 +110,8 @@
       if (!instruction.isInvokeMethodWithReceiver()) {
         return null;
       }
-      if (isAppend(instruction)) {
+      if (isAppend(instruction)
+          && !isAppendWithSubArray(instruction.asInvokeMethodWithReceiver())) {
         return getConstantStringForAppend(instruction.asInvokeVirtual());
       } else if (isInit(instruction)) {
         return getConstantStringForInit(instruction.asInvokeDirect());
@@ -165,14 +167,16 @@
         return false;
       }
       DexMethod invokedMethod = instruction.asInvokeMethod().getInvokedMethod();
-      if (factory.stringBuilderMethods.isAppendSubArrayMethod(invokedMethod)
-          || factory.stringBufferMethods.isAppendSubArrayMethod(invokedMethod)) {
-        return false;
-      }
       return factory.stringBuilderMethods.isAppendMethod(invokedMethod)
           || factory.stringBufferMethods.isAppendMethod(invokedMethod);
     }
 
+    public boolean isAppendWithSubArray(InvokeMethodWithReceiver instruction) {
+      DexMethod invokedMethod = instruction.asInvokeMethod().getInvokedMethod();
+      return factory.stringBuilderMethods.isAppendSubArrayMethod(invokedMethod)
+          || factory.stringBufferMethods.isAppendSubArrayMethod(invokedMethod);
+    }
+
     @Override
     public boolean canObserveStringBuilderCall(Instruction instruction) {
       if (!instruction.isInvokeMethod()) {
@@ -185,7 +189,11 @@
           || factory.stringBuilderMethods.charSequenceConstructor == invokedMethod
           || factory.stringBufferMethods.charSequenceConstructor == invokedMethod) {
         assert instruction.inValues().size() == 2;
-        return instruction.inValues().get(1).getType().isStringType(factory);
+        return !instruction.inValues().get(1).getType().isStringType(factory);
+      }
+      if (factory.stringBuilderMethods.isAppendCharArrayMethod(invokedMethod)
+          || factory.stringBufferMethods.isAppendCharArrayMethod(invokedMethod)) {
+        return instruction.asInvokeVirtual().getFirstNonReceiverArgument().isMaybeNull();
       }
       return false;
     }

diff --git a/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java b/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java
index 707bf1c..6586750 100644
--- a/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java

@@ -261,9 +261,7 @@
     String name = getNamingLens().lookupInternalName(clazz.type);
     String signature = clazz.getClassSignature().toRenamedString(getNamingLens(), isTypeMissing);
     String superName =
-        clazz.type == options.itemFactory.objectType
-            ? null
-            : getNamingLens().lookupInternalName(clazz.superType);
+        clazz.hasSuperType() ? getNamingLens().lookupInternalName(clazz.superType) : null;
     String[] interfaces = new String[clazz.interfaces.values.length];
     for (int i = 0; i < clazz.interfaces.values.length; i++) {
       interfaces[i] = getNamingLens().lookupInternalName(clazz.interfaces.values[i]);

diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
index 7f4c47d..eb07f4b 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java

@@ -3,7 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.kotlin;
 
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.getInvalidKotlinInfo;
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.getNoKotlinInfo;
 import static com.android.tools.r8.kotlin.KotlinSyntheticClassInfo.getFlavour;
 
@@ -19,7 +18,6 @@
 import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.graph.DexValue.DexValueArray;
 import com.android.tools.r8.kotlin.KotlinSyntheticClassInfo.Flavour;
-import com.android.tools.r8.utils.StringDiagnostic;
 import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.function.Consumer;
@@ -36,7 +34,8 @@
   private static final int SYNTHETIC_CLASS_KIND = 3;
 
   public static KotlinClassLevelInfo getKotlinInfo(
-      DexClass clazz, AppView<?> appView, Consumer<DexEncodedMethod> keepByteCode) {
+      DexClass clazz, AppView<?> appView, Consumer<DexEncodedMethod> keepByteCode)
+      throws KotlinMetadataException {
     DexAnnotation meta =
         clazz.annotations().getFirstMatching(appView.dexItemFactory().kotlinMetadataType);
     return meta != null ? getKotlinInfo(clazz, appView, keepByteCode, meta) : getNoKotlinInfo();
@@ -46,35 +45,18 @@
       DexClass clazz,
       AppView<?> appView,
       Consumer<DexEncodedMethod> keepByteCode,
-      DexAnnotation annotation) {
-    try {
-      Kotlin kotlin = appView.dexItemFactory().kotlin;
-      KotlinClassMetadata kMetadata = toKotlinClassMetadata(kotlin, annotation.annotation);
-      return createKotlinInfo(kotlin, clazz, kMetadata, appView, keepByteCode);
-    } catch (ClassCastException | InconsistentKotlinMetadataException | MetadataError e) {
-      appView
-          .reporter()
-          .info(
-              new StringDiagnostic(
-                  "Class "
-                      + clazz.type.toSourceString()
-                      + " has malformed kotlin.Metadata: "
-                      + e.getMessage()));
-      return getInvalidKotlinInfo();
-    } catch (Throwable e) {
-      appView
-          .reporter()
-          .info(
-              new StringDiagnostic(
-                  "Unexpected error while reading "
-                      + clazz.type.toSourceString()
-                      + "'s kotlin.Metadata: "
-                      + e.getMessage()));
-      return getNoKotlinInfo();
+      DexAnnotation annotation)
+      throws KotlinMetadataException {
+    Kotlin kotlin = appView.dexItemFactory().kotlin;
+    KotlinClassMetadata kMetadata = toKotlinClassMetadata(kotlin, annotation.annotation);
+    if (kMetadata == null) {
+      throw new KotlinMetadataException();
     }
+    return createKotlinInfo(kotlin, clazz, kMetadata, appView, keepByteCode);
   }
 
-  public static boolean isLambda(AppView<?> appView, DexClass clazz) {
+  public static boolean isLambda(AppView<?> appView, DexClass clazz)
+      throws KotlinMetadataException {
     DexItemFactory dexItemFactory = appView.dexItemFactory();
     Kotlin kotlin = dexItemFactory.kotlin;
     Flavour flavour = getFlavour(clazz, kotlin);
@@ -108,7 +90,7 @@
   }
 
   public static KotlinClassMetadata toKotlinClassMetadata(
-      Kotlin kotlin, DexEncodedAnnotation metadataAnnotation) {
+      Kotlin kotlin, DexEncodedAnnotation metadataAnnotation) throws KotlinMetadataException {
     return toKotlinClassMetadata(kotlin, toElementMap(metadataAnnotation));
   }
 
@@ -122,12 +104,11 @@
   }
 
   private static KotlinClassMetadata toKotlinClassMetadata(
-      Kotlin kotlin, Map<DexString, DexAnnotationElement> elementMap) {
+      Kotlin kotlin, Map<DexString, DexAnnotationElement> elementMap)
+      throws KotlinMetadataException {
     int k = getKind(kotlin, elementMap);
     DexAnnotationElement metadataVersion = elementMap.get(kotlin.metadata.metadataVersion);
     int[] mv = metadataVersion == null ? null : getUnboxedIntArray(metadataVersion.value, "mv");
-    DexAnnotationElement bytecodeVersion = elementMap.get(kotlin.metadata.bytecodeVersion);
-    int[] bv = bytecodeVersion == null ? null : getUnboxedIntArray(bytecodeVersion.value, "bv");
     DexAnnotationElement data1 = elementMap.get(kotlin.metadata.data1);
     String[] d1 = data1 == null ? null : getUnboxedStringArray(data1.value, "d1");
     DexAnnotationElement data2 = elementMap.get(kotlin.metadata.data2);
@@ -139,8 +120,12 @@
     DexAnnotationElement extraInt = elementMap.get(kotlin.metadata.extraInt);
     Integer xi = extraInt == null ? null : (Integer) extraInt.value.getBoxedValue();
 
-    KotlinClassHeader header = new KotlinClassHeader(k, mv, bv, d1, d2, xs, pn, xi);
-    return KotlinClassMetadata.read(header);
+    try {
+      KotlinClassHeader header = new KotlinClassHeader(k, mv, d1, d2, xs, pn, xi);
+      return KotlinClassMetadata.read(header);
+    } catch (ClassCastException | InconsistentKotlinMetadataException | MetadataError e) {
+      throw new KotlinMetadataException(e);
+    }
   }
 
   private static int getKind(Kotlin kotlin, Map<DexString, DexAnnotationElement> elementMap) {

diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java
index 83947d7..66dc1be 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java

@@ -13,6 +13,9 @@
 
 public class KotlinMetadataDiagnostic implements Diagnostic {
 
+  private static final String LINK_TO_PAGE =
+      "https://developer.android.com/studio/build/kotlin-d8-r8-versions";
+
   private final Origin origin;
   private final Position position;
   private final String message;
@@ -73,4 +76,14 @@
             + StringUtils.LINE_SEPARATOR
             + StringUtils.stacktraceAsString(t));
   }
+
+  static KotlinMetadataDiagnostic unknownMetadataVersion() {
+    return new KotlinMetadataDiagnostic(
+        Origin.unknown(),
+        Position.UNKNOWN,
+        "An error occurred when parsing kotlin metadata. This normally happens when using a newer"
+            + " version of kotlin than the kotlin version released when this version of R8 was"
+            + " created. To find compatible kotlin versions, please see: "
+            + LINK_TO_PAGE);
+  }
 }

diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java
index 2a3698b..6b5d589 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java

@@ -5,6 +5,7 @@
 package com.android.tools.r8.kotlin;
 
 import static com.android.tools.r8.kotlin.KotlinClassMetadataReader.hasKotlinClassMetadataAnnotation;
+import static com.android.tools.r8.kotlin.KotlinMetadataUtils.getInvalidKotlinInfo;
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.getNoKotlinInfo;
 
 import com.android.tools.r8.errors.Unreachable;
@@ -26,6 +27,7 @@
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.Enqueuer.EnqueuerDefinitionSupplier;
 import com.android.tools.r8.shaking.KeepClassInfo;
+import com.android.tools.r8.utils.StringDiagnostic;
 import com.google.common.collect.Sets;
 import java.util.Set;
 
@@ -36,6 +38,7 @@
   private final AppView<?> appView;
   private final EnqueuerDefinitionSupplier enqueuerDefinitionSupplier;
   private final Set<DexType> prunedTypes;
+  private boolean reportedUnknownMetadataVersion;
 
   public KotlinMetadataEnqueuerExtension(
       AppView<?> appView,
@@ -66,26 +69,52 @@
       enqueuer.forAllLiveClasses(
           clazz -> {
             assert clazz.getKotlinInfo().isNoKotlinInformation();
-            if (enqueuer
-                .getKeepInfo(clazz)
-                .isKotlinMetadataRemovalAllowed(appView.options(), keepKotlinMetadata)) {
-              if (KotlinClassMetadataReader.isLambda(appView, clazz)
-                  && clazz.hasClassInitializer()) {
-                feedback.classInitializerMayBePostponed(clazz.getClassInitializer());
+            try {
+              if (enqueuer
+                  .getKeepInfo(clazz)
+                  .isKotlinMetadataRemovalAllowed(appView.options(), keepKotlinMetadata)) {
+                if (KotlinClassMetadataReader.isLambda(appView, clazz)
+                    && clazz.hasClassInitializer()) {
+                  feedback.classInitializerMayBePostponed(clazz.getClassInitializer());
+                }
+                clazz.clearKotlinInfo();
+                clazz.removeAnnotations(
+                    annotation ->
+                        annotation.getAnnotationType()
+                            == appView.dexItemFactory().kotlinMetadataType);
+              } else {
+                clazz.setKotlinInfo(
+                    KotlinClassMetadataReader.getKotlinInfo(
+                        clazz,
+                        appView,
+                        method -> keepByteCodeFunctions.add(method.getReference())));
+                if (clazz.getEnclosingMethodAttribute() != null
+                    && clazz.getEnclosingMethodAttribute().getEnclosingMethod() != null) {
+                  localOrAnonymousClasses.add(clazz);
+                }
               }
-              clazz.clearKotlinInfo();
-              clazz.removeAnnotations(
-                  annotation ->
-                      annotation.getAnnotationType()
-                          == appView.dexItemFactory().kotlinMetadataType);
-            } else {
-              clazz.setKotlinInfo(
-                  KotlinClassMetadataReader.getKotlinInfo(
-                      clazz, appView, method -> keepByteCodeFunctions.add(method.getReference())));
-              if (clazz.getEnclosingMethodAttribute() != null
-                  && clazz.getEnclosingMethodAttribute().getEnclosingMethod() != null) {
-                localOrAnonymousClasses.add(clazz);
-              }
+            } catch (KotlinMetadataException e) {
+              appView
+                  .reporter()
+                  .info(
+                      new StringDiagnostic(
+                          "Class "
+                              + clazz.type.toSourceString()
+                              + " has malformed kotlin.Metadata: "
+                              + e.getMessage()));
+              clazz.setKotlinInfo(getInvalidKotlinInfo());
+              reportUnknownMetadataVersion();
+            } catch (Throwable e) {
+              appView
+                  .reporter()
+                  .info(
+                      new StringDiagnostic(
+                          "Unexpected error while reading "
+                              + clazz.type.toSourceString()
+                              + "'s kotlin.Metadata: "
+                              + e.getMessage()));
+              clazz.setKotlinInfo(getNoKotlinInfo());
+              reportUnknownMetadataVersion();
             }
           });
       for (DexProgramClass localOrAnonymousClass : localOrAnonymousClasses) {
@@ -138,6 +167,13 @@
         });
   }
 
+  private void reportUnknownMetadataVersion() {
+    if (!reportedUnknownMetadataVersion) {
+      reportedUnknownMetadataVersion = true;
+      appView.reporter().warning(KotlinMetadataDiagnostic.unknownMetadataVersion());
+    }
+  }
+
   public class KotlinMetadataDefinitionSupplier implements DexDefinitionSupplier {
 
     private final ProgramDefinition context;

diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataException.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataException.java
new file mode 100644
index 0000000..4ed669e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataException.java

@@ -0,0 +1,15 @@
+// Copyright (c) 2022, 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.kotlin;
+
+/** Exception class to ensure that exceptions arising from kotlin metadata parsing are handled */
+public class KotlinMetadataException extends Exception {
+
+  KotlinMetadataException() {}
+
+  KotlinMetadataException(Throwable cause) {
+    super(cause);
+  }
+}

diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
index 5353319..415995e 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataRewriter.java

@@ -195,11 +195,15 @@
 
   private boolean verifyRewrittenMetadataIsEquivalent(
       DexAnnotation original, DexAnnotation rewritten) {
-    String originalMetadata =
-        kotlinMetadataToString("", toKotlinClassMetadata(kotlin, original.annotation));
-    String rewrittenMetadata =
-        kotlinMetadataToString("", toKotlinClassMetadata(kotlin, rewritten.annotation));
-    assert originalMetadata.equals(rewrittenMetadata) : "The metadata should be equivalent";
+    try {
+      String originalMetadata =
+          kotlinMetadataToString("", toKotlinClassMetadata(kotlin, original.annotation));
+      String rewrittenMetadata =
+          kotlinMetadataToString("", toKotlinClassMetadata(kotlin, rewritten.annotation));
+      assert originalMetadata.equals(rewrittenMetadata) : "The metadata should be equivalent";
+    } catch (KotlinMetadataException ignored) {
+
+    }
     return true;
   }
 
@@ -228,11 +232,6 @@
           new DexAnnotationElement(
               kotlin.metadata.metadataVersion, createIntArray(metadataVersion)));
     }
-    if (writeMetadataFieldInfo.writeByteCodeVersion) {
-      elements.add(
-          new DexAnnotationElement(
-              kotlin.metadata.bytecodeVersion, createIntArray(header.getBytecodeVersion())));
-    }
     if (writeMetadataFieldInfo.writeKind) {
       elements.add(
           new DexAnnotationElement(kotlin.metadata.kind, DexValueInt.create(header.getKind())));

diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java b/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
index 3eb0ec1..bdd2b9b 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java

@@ -18,8 +18,8 @@
 import com.google.gson.JsonObject;
 import com.google.gson.JsonParser;
 import java.io.IOException;
+import java.util.ArrayList;
 import java.util.HashMap;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Objects;
 import java.util.function.Consumer;
@@ -512,7 +512,7 @@
       if (peekChar(0) == ')') {
         arguments = new String[0];
       } else {
-        List<String> items = new LinkedList<>();
+        List<String> items = new ArrayList<>();
         items.add(parseType(true));
         skipWhitespace();
         while (peekChar(0) != ')') {

diff --git a/src/main/java/com/android/tools/r8/optimize/AccessModifier.java b/src/main/java/com/android/tools/r8/optimize/AccessModifier.java
index d8b5946..c1ee380 100644
--- a/src/main/java/com/android/tools/r8/optimize/AccessModifier.java
+++ b/src/main/java/com/android/tools/r8/optimize/AccessModifier.java

@@ -148,7 +148,8 @@
         && !accessInfo.isWrittenFromMethodHandle()
         && accessInfo.isWrittenOnlyInMethodSatisfying(
             method ->
-                method.getDefinition().isInitializer(flags.isStatic())
+                method.getDefinition().isInitializer()
+                    && method.getAccessFlags().isStatic() == flags.isStatic()
                     && method.getHolder() == field.getHolder())
         && !flags.isFinal()
         && !flags.isVolatile()) {

diff --git a/src/main/java/com/android/tools/r8/repackaging/RepackagingConstraintGraph.java b/src/main/java/com/android/tools/r8/repackaging/RepackagingConstraintGraph.java
index 63f4483..8145a9b 100644
--- a/src/main/java/com/android/tools/r8/repackaging/RepackagingConstraintGraph.java
+++ b/src/main/java/com/android/tools/r8/repackaging/RepackagingConstraintGraph.java

@@ -105,7 +105,9 @@
         new RepackagingUseRegistry(appView, this, clazz, libraryBoundaryNode);
 
     // Trace the references to the immediate super types.
-    registry.registerTypeReference(clazz.getSuperType(), appView.graphLens());
+    if (clazz.superType != null) {
+      registry.registerTypeReference(clazz.getSuperType(), appView.graphLens());
+    }
     clazz.interfaces.forEach(type -> registry.registerTypeReference(type, appView.graphLens()));
 
     // Trace the references from the class annotations.
@@ -156,11 +158,13 @@
         .forEachType(type -> registry.registerTypeReference(type, appView.graphLens()));
 
     // Check if this overrides a package-private method.
-    DexClass superClass =
-        appView.definitionFor(method.getHolder().getSuperType(), method.getHolder());
-    if (superClass != null) {
-      registry.registerMemberAccess(
-          appView.appInfo().resolveMethodOnLegacy(superClass, method.getReference()));
+    if (method.getHolder().superType != null) {
+      DexClass superClass =
+          appView.definitionFor(method.getHolder().getSuperType(), method.getHolder());
+      if (superClass != null) {
+        registry.registerMemberAccess(
+            appView.appInfo().resolveMethodOnLegacy(superClass, method.getReference()));
+      }
     }
 
     // Trace the references in the method and method parameter annotations.

diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
index 527cec3..6065527 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java

@@ -35,6 +35,7 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
@@ -53,6 +54,7 @@
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.IdentityHashMap;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -592,14 +594,12 @@
           List<EquivalenceGroup<T>> groups =
               groupEquivalent(appView, members, intermediate, classToFeatureSplitMap);
           for (EquivalenceGroup<T> group : groups) {
-            // If the group already has a representative, then this representative is pinned.
-            // Otherwise, we select a deterministic representative.
-            if (group.hasRepresentative()) {
+            // If the group has a pinned representative don't construct an external type.
+            if (group.isPinned(appView)) {
               EquivalenceGroup<T> previous =
                   equivalences.put(group.getRepresentative().getHolder().getType(), group);
               assert previous == null;
             } else {
-              group.selectDeterministicRepresentative();
               groupsPerPrefix
                   .computeIfAbsent(
                       group.getRepresentative().getPrefixForExternalSyntheticType(),
@@ -666,52 +666,94 @@
       List<T> potentialEquivalence,
       boolean intermediate,
       ClassToFeatureSplitMap classToFeatureSplitMap) {
-    List<EquivalenceGroup<T>> groups = new ArrayList<>();
-    // Each other member is in a shared group if it is actually equivalent to the first member.
-    for (T synthetic : potentialEquivalence) {
-      if (groups.size() > GROUP_COUNT_THRESHOLD) {
-        return ListUtils.map(
-            potentialEquivalence, m -> new EquivalenceGroup<>(m, isPinned(appView, m)));
+    // Fast path the singleton groups.
+    if (potentialEquivalence.size() == 1) {
+      return ImmutableList.of(EquivalenceGroup.singleton(potentialEquivalence.get(0)));
+    }
+    assert !potentialEquivalence.isEmpty();
+
+    // Sort the potential members and split them up into potential groups of members that are
+    // actually equal.
+    GraphLens graphLens = appView.graphLens();
+    boolean includeContext =
+        intermediate || appView.options().getStartupOptions().isStartupInstrumentationEnabled();
+    List<T> sortedPotentialMembers =
+        ListUtils.sort(
+            potentialEquivalence,
+            (a, b) -> a.compareTo(b, includeContext, graphLens, classToFeatureSplitMap));
+    List<List<T>> potentialGroups = new ArrayList<>();
+    {
+      List<T> currentGroup = new ArrayList<>();
+      T currentRepresentative = sortedPotentialMembers.get(0);
+      currentGroup.add(currentRepresentative);
+      for (int i = 1; i < sortedPotentialMembers.size(); i++) {
+        T member = sortedPotentialMembers.get(i);
+        if (!currentRepresentative.isEquivalentTo(
+            member, includeContext, graphLens, classToFeatureSplitMap)) {
+          potentialGroups.add(currentGroup);
+          currentGroup = new ArrayList<>();
+          currentRepresentative = member;
+        }
+        currentGroup.add(member);
       }
-      boolean mustBeRepresentative = isPinned(appView, synthetic);
-      EquivalenceGroup<T> equivalenceGroup = null;
-      for (EquivalenceGroup<T> group : groups) {
-        boolean includeContext =
-            intermediate || appView.options().getStartupOptions().isStartupInstrumentationEnabled();
-        if (synthetic.isEquivalentTo(
-            group.hasRepresentative()
-                ? group.getRepresentative()
-                : group.getFirstNonRepresentativeMember(),
-            includeContext,
-            appView.graphLens(),
-            classToFeatureSplitMap)) {
-          if (mustBeRepresentative && group.hasRepresentative()) {
-            // Check if the current synthetic is smaller than the group's representative. If so,
-            // then replace the representative, to ensure deterministic groups, and create a new
-            // singleton group containing the old representative. Otherwise, just add a singleton
-            // group containing the new synthetic.
-            T representative = group.getRepresentative();
-            if (representative
-                    .toReference()
-                    .getReference()
-                    .compareTo(synthetic.toReference().getReference())
-                > 0) {
-              group.replaceAndRemoveRepresentative(synthetic);
-              synthetic = representative;
+      potentialGroups.add(currentGroup);
+    }
+
+    // Compute the actual groups by picking the group representatives. In cases of pinned members
+    // this may need to split out representatives into their own singleton groups.
+    List<EquivalenceGroup<T>> actualGroups = new ArrayList<>();
+    for (List<T> potentialGroup : potentialGroups) {
+      assert !potentialGroup.isEmpty();
+      if (potentialGroup.size() == 1) {
+        actualGroups.add(EquivalenceGroup.singleton(potentialGroup.get(0)));
+        continue;
+      }
+      List<T> forcedRepresentatives = null;
+      if (appView.enableWholeProgramOptimizations()) {
+        Iterator<T> it = potentialGroup.iterator();
+        while (it.hasNext()) {
+          T member = it.next();
+          boolean mustBeRepresentative = isPinned(appView, member);
+          if (mustBeRepresentative) {
+            if (forcedRepresentatives == null) {
+              forcedRepresentatives = new ArrayList<>();
             }
-          } else {
-            equivalenceGroup = group;
+            forcedRepresentatives.add(member);
+            it.remove();
           }
-          break;
         }
       }
-      if (equivalenceGroup != null) {
-        equivalenceGroup.add(synthetic, mustBeRepresentative);
+      if (forcedRepresentatives != null) {
+        assert appView.enableWholeProgramOptimizations();
+        T representative =
+            findSmallestMember(
+                forcedRepresentatives,
+                other -> actualGroups.add(EquivalenceGroup.pinnedSingleton(other)));
+        actualGroups.add(EquivalenceGroup.pinnedGroup(representative, potentialGroup));
       } else {
-        groups.add(new EquivalenceGroup<>(synthetic, mustBeRepresentative));
+        List<T> members = new ArrayList<>(potentialGroup.size() - 1);
+        T representative = findSmallestMember(potentialGroup, members::add);
+        actualGroups.add(EquivalenceGroup.unpinnedGroup(representative, members));
       }
     }
-    return groups;
+    return actualGroups;
+  }
+
+  private static <T extends SyntheticDefinition<?, T, ?>> T findSmallestMember(
+      List<T> members, Consumer<T> notSmallestCallback) {
+    assert !members.isEmpty();
+    T smallest = members.get(0);
+    for (int i = 1; i < members.size(); i++) {
+      T member = members.get(i);
+      if (member.toReference().getReference().compareTo(smallest.toReference().getReference())
+          < 0) {
+        notSmallestCallback.accept(smallest);
+        smallest = member;
+      } else {
+        notSmallestCallback.accept(member);
+      }
+    }
+    return smallest;
   }
 
   /**
@@ -846,28 +888,47 @@
   private static class EquivalenceGroup<T extends SyntheticDefinition<?, T, ?>> {
 
     // The members of the equivalence group, *excluding* the representative.
-    private List<T> members = new ArrayList<>();
-    private T representative;
+    private final List<T> members;
+    private final T representative;
+    private final OptionalBool pinned;
 
-    EquivalenceGroup(T member, boolean isRepresentative) {
-      add(member, isRepresentative);
+    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> singleton(T member) {
+      return new EquivalenceGroup<>(member, ImmutableList.of(), OptionalBool.UNKNOWN);
     }
 
-    void add(T member, boolean isRepresentative) {
-      if (isRepresentative) {
-        assert !hasRepresentative();
-        representative = member;
-      } else {
-        members.add(member);
+    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> unpinnedGroup(
+        T representative, List<T> members) {
+      return new EquivalenceGroup<>(
+          representative, Collections.unmodifiableList(members), OptionalBool.FALSE);
+    }
+
+    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> pinnedSingleton(T member) {
+      return new EquivalenceGroup<>(member, ImmutableList.of(), OptionalBool.TRUE);
+    }
+
+    static <T extends SyntheticDefinition<?, T, ?>> EquivalenceGroup<T> pinnedGroup(
+        T representative, List<T> members) {
+      return new EquivalenceGroup<>(
+          representative, Collections.unmodifiableList(members), OptionalBool.TRUE);
+    }
+
+    private EquivalenceGroup(T representative, List<T> members, OptionalBool pinned) {
+      assert representative != null;
+      assert members != null;
+      assert pinned != null;
+      this.members = members;
+      this.representative = representative;
+      this.pinned = pinned;
+    }
+
+    public boolean isPinned(AppView<?> appView) {
+      if (pinned.isTrue()) {
+        return true;
       }
-    }
-
-    int compareToIncludingContext(
-        EquivalenceGroup<T> other,
-        GraphLens graphLens,
-        ClassToFeatureSplitMap classToFeatureSplitMap) {
-      return getRepresentative()
-          .compareTo(other.getRepresentative(), true, graphLens, classToFeatureSplitMap);
+      if (pinned.isFalse()) {
+        return false;
+      }
+      return SyntheticFinalization.isPinned(appView, representative);
     }
 
     public void forEach(Consumer<T> consumer) {
@@ -879,64 +940,23 @@
       members.forEach(consumer);
     }
 
-    T getFirstNonRepresentativeMember() {
-      assert !members.isEmpty();
-      return members.get(0);
-    }
-
     T getRepresentative() {
-      assert hasRepresentative();
       return representative;
     }
 
-    boolean hasRepresentative() {
-      return representative != null;
-    }
-
     boolean isDerivedFromMainDexList(MainDexInfo mainDexInfo) {
       return getRepresentative().getContext().isDerivedFromMainDexList(mainDexInfo)
           || Iterables.any(
               members, member -> member.getContext().isDerivedFromMainDexList(mainDexInfo));
     }
 
-    void replaceAndRemoveRepresentative(T representative) {
-      assert hasRepresentative();
-      this.representative = representative;
-    }
-
-    void selectDeterministicRepresentative() {
-      // Pick a deterministic member as representative.
-      assert !hasRepresentative();
-      int representativeIndex = 0;
-      for (int i = 1; i < members.size(); i++) {
-        T next = members.get(i);
-        T representative = members.get(representativeIndex);
-        if (next.toReference().getReference().compareTo(representative.toReference().getReference())
-            < 0) {
-          representativeIndex = i;
-        }
-      }
-      T representative = members.get(representativeIndex);
-      members.set(representativeIndex, ListUtils.last(members));
-      ListUtils.removeLast(members);
-      setRepresentative(representative);
-    }
-
-    void setRepresentative(T representative) {
-      assert !hasRepresentative();
-      this.representative = representative;
-    }
-
     @Override
     public String toString() {
-      if (hasRepresentative()) {
-        return "EquivalenceGroup{ size = "
-            + (members.size() + 1)
-            + ", repr = "
-            + getRepresentative()
-            + " }";
-      }
-      return "EquivalenceGroup{ size = " + members.size() + " }";
+      return "EquivalenceGroup{ size = "
+          + (members.size() + 1)
+          + ", repr = "
+          + getRepresentative()
+          + " }";
     }
   }
 }

diff --git a/src/main/java/com/android/tools/r8/utils/IterableUtils.java b/src/main/java/com/android/tools/r8/utils/IterableUtils.java
index 1c4aef5..cd6dcb6 100644
--- a/src/main/java/com/android/tools/r8/utils/IterableUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/IterableUtils.java

@@ -88,7 +88,8 @@
     return -1;
   }
 
-  public static <T> Iterable<T> filter(Iterable<T> iterable, Predicate<? super T> predicate) {
+  public static <S, T extends S> Iterable<T> filter(
+      Iterable<S> iterable, Predicate<? super S> predicate) {
     return () -> IteratorUtils.filter(iterable.iterator(), predicate);
   }
 

diff --git a/src/main/java/com/android/tools/r8/utils/ListUtils.java b/src/main/java/com/android/tools/r8/utils/ListUtils.java
index 9c6e2a7..406d482 100644
--- a/src/main/java/com/android/tools/r8/utils/ListUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ListUtils.java

@@ -268,12 +268,26 @@
     void accept(T item, int index);
   }
 
+  public static <T> List<T> sort(List<T> items, Comparator<T> comparator) {
+    List<T> sorted = new ArrayList<>(items);
+    sorted.sort(comparator);
+    return sorted;
+  }
+
   public static <T> void destructiveSort(List<T> items, Comparator<T> comparator) {
     items.sort(comparator);
   }
 
   // Utility to add a slow verification of a comparator as part of sorting. Note that this
   // should not generally be used in asserts unless the quadratic behavior can be tolerated.
+  public static <T> List<T> sortAndVerify(List<T> items, Comparator<T> comparator) {
+    List<T> sorted = sort(items, comparator);
+    assert verifyComparatorOnSortedList(sorted, comparator);
+    return sorted;
+  }
+
+  // Utility to add a slow verification of a comparator as part of sorting. Note that this
+  // should not generally be used in asserts unless the quadratic behavior can be tolerated.
   public static <T> void destructiveSortAndVerify(List<T> items, Comparator<T> comparator) {
     destructiveSort(items, comparator);
     assert verifyComparatorOnSortedList(items, comparator);

diff --git a/src/test/java/com/android/tools/r8/compatproguard/AtomicFieldUpdaterTest.java b/src/test/java/com/android/tools/r8/compatproguard/AtomicFieldUpdaterTest.java
index 3d3aecc..bdb4119 100644
--- a/src/test/java/com/android/tools/r8/compatproguard/AtomicFieldUpdaterTest.java
+++ b/src/test/java/com/android/tools/r8/compatproguard/AtomicFieldUpdaterTest.java

@@ -126,10 +126,9 @@
 
     DexCode code = method.getMethod().getCode().asDexCode();
     assertTrue(code.instructions[0] instanceof DexConstClass);
-    assertTrue(code.instructions[1] instanceof DexConstClass);
-    assertTrue(code.instructions[2] instanceof DexConstString);
-    DexConstString constString = (DexConstString) code.instructions[2];
-    assertNotEquals("foo", constString.getString().toString());
+    assertTrue(code.instructions[1] instanceof DexConstString);
+    assertNotEquals("foo", code.instructions[1].asConstString().getString().toString());
+    assertTrue(code.instructions[2] instanceof DexConstClass);
     assertTrue(code.instructions[3] instanceof DexInvokeStatic);
     assertTrue(code.instructions[4] instanceof DexReturnVoid);
   }

diff --git a/src/test/java/com/android/tools/r8/compatproguard/GetMembersTest.java b/src/test/java/com/android/tools/r8/compatproguard/GetMembersTest.java
index 7a30afd..812eb63 100644
--- a/src/test/java/com/android/tools/r8/compatproguard/GetMembersTest.java
+++ b/src/test/java/com/android/tools/r8/compatproguard/GetMembersTest.java

@@ -93,15 +93,14 @@
     assertTrue(method.isPresent());
 
     DexCode code = method.getMethod().getCode().asDexCode();
-    assertTrue(code.instructions[0] instanceof DexConstClass);
-    assertTrue(code.instructions[1] instanceof DexConst4);
-    assertTrue(code.instructions[2] instanceof DexNewArray);
-    assertTrue(code.instructions[3] instanceof DexConst4);
+    assertTrue(code.instructions[0] instanceof DexConst4);
+    assertTrue(code.instructions[1] instanceof DexNewArray);
+    assertTrue(code.instructions[2] instanceof DexConst4);
+    assertTrue(code.instructions[3] instanceof DexConstClass);
     assertTrue(code.instructions[4] instanceof DexAputObject);
     assertTrue(code.instructions[5] instanceof DexConstClass);
     assertTrue(code.instructions[6] instanceof DexConstString);
-    DexConstString constString = (DexConstString) code.instructions[6];
-    assertNotEquals("foo", constString.getString().toString());
+    assertNotEquals("foo", code.instructions[6].asConstString().getString().toString());
     assertTrue(code.instructions[7] instanceof DexInvokeVirtual);
     assertTrue(code.instructions[8] instanceof DexReturnVoid);
   }

diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdk11/InputStreamTransferToTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdk11/InputStreamTransferToTest.java
index 54c88bf..70d445d 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdk11/InputStreamTransferToTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdk11/InputStreamTransferToTest.java

@@ -4,10 +4,11 @@
 
 package com.android.tools.r8.desugar.desugaredlibrary.jdk11;
 
-import static com.android.tools.r8.desugar.desugaredlibrary.test.CompilationSpecification.DEFAULT_SPECIFICATIONS;
+import static com.android.tools.r8.desugar.desugaredlibrary.test.CompilationSpecification.SPECIFICATIONS_WITH_CF2CF;
 import static com.android.tools.r8.desugar.desugaredlibrary.test.LibraryDesugaringSpecification.JDK11_PATH;
 
 import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestRuntime.CfVm;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.desugar.desugaredlibrary.DesugaredLibraryTestBase;
 import com.android.tools.r8.desugar.desugaredlibrary.test.CompilationSpecification;
@@ -17,6 +18,7 @@
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.List;
+import org.junit.Assume;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -38,9 +40,9 @@
   @Parameters(name = "{0}, spec: {1}, {2}")
   public static List<Object[]> data() {
     return buildParameters(
-        getTestParameters().withAllRuntimesAndApiLevels().build(),
+        getTestParameters().withAllRuntimesAndApiLevels().enableApiLevelsForCf().build(),
         ImmutableList.of(JDK11_PATH),
-        DEFAULT_SPECIFICATIONS);
+        SPECIFICATIONS_WITH_CF2CF);
   }
 
   public InputStreamTransferToTest(
@@ -54,6 +56,11 @@
 
   @Test
   public void test() throws Exception {
+    // The method is not present on JDK8 so if we don't desugar that won't work.
+    Assume.assumeFalse(
+        parameters.isCfRuntime(CfVm.JDK8)
+            && !libraryDesugaringSpecification.hasNioFileDesugaring(parameters)
+            && compilationSpecification.isCfToCf());
     testForDesugaredLibrary(parameters, libraryDesugaringSpecification, compilationSpecification)
         .addProgramFiles(INPUT_JAR)
         .addKeepMainRule(MAIN_CLASS)

diff --git a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/InstanceGetOnNewInstanceCanonicalizationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/InstanceGetOnNewInstanceCanonicalizationTest.java
new file mode 100644
index 0000000..d8950eb
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/InstanceGetOnNewInstanceCanonicalizationTest.java

@@ -0,0 +1,70 @@
+// Copyright (c) 2022, 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.canonicalization;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+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.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class InstanceGetOnNewInstanceCanonicalizationTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              MethodSubject mainMethodSubject = inspector.clazz(Main.class).mainMethod();
+              assertThat(mainMethodSubject, isPresent());
+              assertEquals(
+                  parameters.isCfRuntime() ? 2 : 1,
+                  mainMethodSubject
+                      .streamInstructions()
+                      .filter(InstructionSubject::isInstanceGet)
+                      .count());
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello, world!");
+  }
+
+  static class Main {
+
+    final String field = System.currentTimeMillis() > 0 ? ", " : null;
+
+    public static void main(String[] args) {
+      Main main = new Main();
+      if (System.currentTimeMillis() > 0) {
+        System.out.print("Hello");
+        System.out.print(main.field);
+        System.out.println("world!");
+      } else {
+        System.out.println(main.field);
+      }
+    }
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/InstanceGetOnPhiCanonicalizationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/InstanceGetOnPhiCanonicalizationTest.java
new file mode 100644
index 0000000..8fafc8f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/InstanceGetOnPhiCanonicalizationTest.java

@@ -0,0 +1,70 @@
+// Copyright (c) 2022, 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.canonicalization;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+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.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class InstanceGetOnPhiCanonicalizationTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              MethodSubject mainMethodSubject = inspector.clazz(Main.class).mainMethod();
+              assertThat(mainMethodSubject, isPresent());
+              assertEquals(
+                  parameters.isCfRuntime() ? 2 : 1,
+                  mainMethodSubject
+                      .streamInstructions()
+                      .filter(InstructionSubject::isInstanceGet)
+                      .count());
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello, world!");
+  }
+
+  static class Main {
+
+    final String field = System.currentTimeMillis() > 0 ? ", " : null;
+
+    public static void main(String[] args) {
+      Main main = System.currentTimeMillis() > 0 ? new Main() : new Main();
+      if (System.currentTimeMillis() > 0) {
+        System.out.print("Hello");
+        System.out.print(main.field);
+        System.out.println("world!");
+      } else {
+        System.out.println(main.field);
+      }
+    }
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderTests.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderTests.java
index e7c5301..86fcb86 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderTests.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderTests.java

@@ -217,17 +217,21 @@
         .apply(parameters)
         .inspect(
             inspector -> {
-              if (parameters.isCfRuntime()) {
-                // TODO(b/114002137): for now, string concatenation depends on rewriteMoveResult.
-                return;
-              }
               MethodSubject method = inspector.method(stringBuilderTest.method);
               assertThat(method, isPresent());
               FoundMethodSubject foundMethodSubject = method.asFoundMethodSubject();
               assertEquals(
                   stringBuilderTest.stringBuilders, countStringBuilderInits(foundMethodSubject));
-              assertEquals(
-                  stringBuilderTest.appends, countStringBuilderAppends(foundMethodSubject));
+              if (parameters.isCfRuntime()
+                  && (stringBuilderTest.getMethodName().equals("diamondWithUseTest")
+                      || stringBuilderTest.getMethodName().equals("intoPhiTest"))) {
+                // We are not doing block suffix optimization in CF.
+                assertEquals(
+                    stringBuilderTest.appends + 1, countStringBuilderAppends(foundMethodSubject));
+              } else {
+                assertEquals(
+                    stringBuilderTest.appends, countStringBuilderAppends(foundMethodSubject));
+              }
               assertEquals(
                   stringBuilderTest.toStrings, countStringBuilderToStrings(foundMethodSubject));
             })

diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithConstantsBeforeAndInOpenEndedIfInLoopTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithConstantsBeforeAndInOpenEndedIfInLoopTest.java
new file mode 100644
index 0000000..67d3d66
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithConstantsBeforeAndInOpenEndedIfInLoopTest.java

@@ -0,0 +1,58 @@
+// Copyright (c) 2022, 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 com.google.common.collect.Sets;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+/** This is a regression test for b/237674850 */
+@RunWith(Parameterized.class)
+public class StringBuilderWithConstantsBeforeAndInOpenEndedIfInLoopTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public StringBuilderWithConstantsBeforeAndInOpenEndedIfInLoopTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class)
+        .addKeepMainRule(TestClass.class)
+        .addOptionsModification(
+            options ->
+                options.itemFactory.libraryMethodsReturningReceiver = Sets.newIdentityHashSet())
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class, "1", "3")
+        .assertSuccessWithOutputLines("0.1.2.3.");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      StringBuilder builder = new StringBuilder();
+      builder.append("0.");
+      for (int i = 0; i < args.length; ++i) {
+        builder.append(args[i]);
+        builder.append(".");
+        if (i != args.length - 1) {
+          builder.append("2.");
+        }
+      }
+      System.out.println(builder.toString());
+    }
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithConstantsBeforeAndInOpenEndedIfTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithConstantsBeforeAndInOpenEndedIfTest.java
new file mode 100644
index 0000000..4219d7f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderWithConstantsBeforeAndInOpenEndedIfTest.java

@@ -0,0 +1,53 @@
+// Copyright (c) 2022, 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 com.google.common.collect.Sets;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class StringBuilderWithConstantsBeforeAndInOpenEndedIfTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public StringBuilderWithConstantsBeforeAndInOpenEndedIfTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class)
+        .addKeepMainRule(TestClass.class)
+        .addOptionsModification(
+            options ->
+                options.itemFactory.libraryMethodsReturningReceiver = Sets.newIdentityHashSet())
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("foo");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      StringBuilder builder = new StringBuilder();
+      builder.append("foo");
+      if (System.currentTimeMillis() == 0) {
+        builder.append("bar");
+      }
+      System.out.println(builder.toString());
+    }
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java b/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java
index 20a3077..8add503 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java

@@ -5,7 +5,7 @@
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -13,6 +13,8 @@
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.InstructionSubject;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import it.unimi.dsi.fastutil.longs.LongArrayList;
+import it.unimi.dsi.fastutil.longs.LongList;
 import java.util.Iterator;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -46,16 +48,13 @@
 
               MethodSubject m = c.uniqueMethodWithName("invokeRangeTest");
               assertThat(m, isPresent());
-              long prev;
-              long curr = -1;
               Iterator<InstructionSubject> it =
                   m.iterateInstructions(InstructionSubject::isConstNumber);
+              LongList numbers = new LongArrayList();
               while (it.hasNext()) {
-                InstructionSubject instr = it.next();
-                prev = curr;
-                curr = instr.getConstNumber();
-                assertTrue(prev < curr);
+                numbers.add(it.next().getConstNumber());
               }
+              assertEquals(new LongArrayList(new long[] {0, 1, 2, 3, 4, 5}), numbers);
             });
   }
 

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 90d7195..8983d39 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

@@ -35,6 +35,7 @@
 import java.util.ListIterator;
 import java.util.Set;
 import java.util.function.Consumer;
+import java.util.function.UnaryOperator;
 import org.junit.Test;
 
 public class RegisterMoveSchedulerTest {
@@ -122,7 +123,7 @@
     public void replaceCurrentInstructionWithThrow(
         AppView<?> appView,
         IRCode code,
-        ListIterator<BasicBlock> blockIterator,
+        BasicBlockIterator blockIterator,
         Value exceptionValue,
         Set<BasicBlock> blocksToRemove,
         Set<Value> affectedValues) {
@@ -212,7 +213,10 @@
 
     @Override
     public BasicBlock splitCopyCatchHandlers(
-        IRCode code, ListIterator<BasicBlock> blockIterator, InternalOptions options) {
+        IRCode code,
+        BasicBlockIterator blockIterator,
+        InternalOptions options,
+        UnaryOperator<BasicBlock> repositioningBlock) {
       throw new Unimplemented();
     }
 

diff --git a/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java b/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java
index 039ba9a..83ea780 100644
--- a/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java
+++ b/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java

@@ -651,10 +651,10 @@
         code,
         ImmutableList.of(
             DexInvokeDirect.class,
-            DexConstClass.class,
             DexConst4.class,
             DexNewArray.class,
             DexConst4.class,
+            DexConstClass.class,
             DexAputObject.class,
             DexConstString.class,
             DexInvokeStatic.class,
@@ -712,10 +712,10 @@
         code,
         ImmutableList.of(
             DexInvokeDirect.class,
-            DexConstClass.class,
             DexConst4.class,
             DexNewArray.class,
             DexConst4.class,
+            DexConstClass.class,
             DexAputObject.class,
             DexConstString.class,
             DexInvokeStatic.class,

diff --git a/src/test/java/com/android/tools/r8/repackage/RepackageObjectOnProgramPathTest.java b/src/test/java/com/android/tools/r8/repackage/RepackageObjectOnProgramPathTest.java
index 1e0b59e..4c20192 100644
--- a/src/test/java/com/android/tools/r8/repackage/RepackageObjectOnProgramPathTest.java
+++ b/src/test/java/com/android/tools/r8/repackage/RepackageObjectOnProgramPathTest.java

@@ -4,13 +4,10 @@
 
 package com.android.tools.r8.repackage;
 
-import static org.junit.Assert.assertThrows;
 import static org.objectweb.asm.Opcodes.ACC_PUBLIC;
 import static org.objectweb.asm.Opcodes.ACC_SUPER;
 import static org.objectweb.asm.Opcodes.V1_8;
 
-import com.android.tools.r8.CompilationFailedException;
-import com.android.tools.r8.DiagnosticsMatcher;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -35,22 +32,17 @@
 
   @Test
   public void testR8() throws Exception {
-    assertThrows(
-        CompilationFailedException.class,
-        () -> {
-          testForR8(parameters.getBackend())
-              .addProgramClassFileData(dumpObject())
-              .addProgramClasses(A.class, Main.class)
-              .setMinApi(parameters.getApiLevel())
-              .enableInliningAnnotations()
-              .addKeepMainRule(Main.class)
-              .addDontWarn("*")
-              .compileWithExpectedDiagnostics(
-                  diagnostics ->
-                      // TODO(b/237124748): We should not throw an error.
-                      diagnostics.assertErrorThatMatches(
-                          DiagnosticsMatcher.diagnosticException(NullPointerException.class)));
-        });
+    testForR8(parameters.getBackend())
+        .addProgramClassFileData(dumpObject())
+        .addProgramClasses(A.class, Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .enableInliningAnnotations()
+        .addKeepMainRule(Main.class)
+        .addDontWarn("*")
+        .addKeepClassRules(Object.class)
+        .allowDiagnosticWarningMessages()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("A::foo");
   }
 
   public static byte[] dumpObject() {

diff --git a/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java b/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java
index 35dee6e..fd50cd6 100644
--- a/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java
+++ b/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java

@@ -180,8 +180,8 @@
         ":return",
         "  return v0");
     DexCode code = method.getCode().asDexCode();
-    assertEquals(10, code.instructions.length);
-    assertTrue(code.instructions[9] instanceof DexReturn);
+    assertEquals(12, code.instructions.length);
+    assertTrue(code.instructions[11] instanceof DexReturn);
   }
 
   @Test
@@ -452,6 +452,6 @@
     // TODO(sgjesse): Maybe this test is too fragile, as it leaves quite a lot of code, so the
     // expectation might need changing with other optimizations.
     // TODO(zerny): Consider optimizing the fallthrough branch of conditionals to not be return.
-    assertEquals(24, code.instructions.length);
+    assertEquals(26, code.instructions.length);
   }
 }

diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
index cb65261..2c304ad 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java

@@ -25,6 +25,7 @@
 import com.android.tools.r8.graph.NestMemberClassAttribute;
 import com.android.tools.r8.graph.PermittedSubclassAttribute;
 import com.android.tools.r8.kotlin.KotlinClassMetadataReader;
+import com.android.tools.r8.kotlin.KotlinMetadataException;
 import com.android.tools.r8.naming.ClassNamingForNameMapper;
 import com.android.tools.r8.naming.MemberNaming;
 import com.android.tools.r8.naming.MemberNaming.FieldSignature;
@@ -544,9 +545,14 @@
     if (!annotationSubject.isPresent()) {
       return new AbsentKmClassSubject();
     }
-    KotlinClassMetadata metadata =
-        KotlinClassMetadataReader.toKotlinClassMetadata(
-            codeInspector.getFactory().kotlin, annotationSubject.getAnnotation());
+    KotlinClassMetadata metadata = null;
+    try {
+      metadata =
+          KotlinClassMetadataReader.toKotlinClassMetadata(
+              codeInspector.getFactory().kotlin, annotationSubject.getAnnotation());
+    } catch (KotlinMetadataException e) {
+      throw new RuntimeException(e);
+    }
     assertTrue(metadata instanceof KotlinClassMetadata.Class);
     KotlinClassMetadata.Class kClass = (KotlinClassMetadata.Class) metadata;
     return new FoundKmClassSubject(codeInspector, getDexProgramClass(), kClass.toKmClass());
@@ -558,9 +564,14 @@
     if (!annotationSubject.isPresent()) {
       return new AbsentKmPackageSubject();
     }
-    KotlinClassMetadata metadata =
-        KotlinClassMetadataReader.toKotlinClassMetadata(
-            codeInspector.getFactory().kotlin, annotationSubject.getAnnotation());
+    KotlinClassMetadata metadata = null;
+    try {
+      metadata =
+          KotlinClassMetadataReader.toKotlinClassMetadata(
+              codeInspector.getFactory().kotlin, annotationSubject.getAnnotation());
+    } catch (KotlinMetadataException e) {
+      throw new RuntimeException(e);
+    }
     assertTrue(metadata instanceof KotlinClassMetadata.FileFacade
         || metadata instanceof KotlinClassMetadata.MultiFileClassPart);
     if (metadata instanceof KotlinClassMetadata.FileFacade) {
@@ -579,8 +590,12 @@
     if (!annotationSubject.isPresent()) {
       return null;
     }
-    return KotlinClassMetadataReader.toKotlinClassMetadata(
-        codeInspector.getFactory().kotlin, annotationSubject.getAnnotation());
+    try {
+      return KotlinClassMetadataReader.toKotlinClassMetadata(
+          codeInspector.getFactory().kotlin, annotationSubject.getAnnotation());
+    } catch (KotlinMetadataException e) {
+      throw new RuntimeException(e);
+    }
   }
 
   @Override

diff --git a/tools/tag_versions.py b/tools/tag_versions.py
index ebf14ba..28a1cae 100755
--- a/tools/tag_versions.py
+++ b/tools/tag_versions.py

@@ -44,7 +44,10 @@
   if args.branch:
     tag_r8_branch(args.branch, args)
   elif args.agp:
-    tag_agp_version(args.agp, args)
+    if (args.agp == 'all'):
+      tag_all_agp_versions(args)
+    else:
+      tag_agp_version(args.agp, args)
   else:
     print("Should use a top-level option, such as --branch or --agp.")
     return 1
@@ -71,6 +74,26 @@
     return None
   return output
 
+def tag_all_agp_versions(args):
+  with utils.TempDir() as temp:
+    url = "%s/maven-metadata.xml" % AGP_MAVEN
+    metadata = os.path.join(temp, "maven-metadata.xml")
+    try:
+      urllib.request.urlretrieve(url, metadata)
+    except urllib.error.HTTPError as e:
+      print('Could not find maven-metadata.xml for agp')
+      print(e)
+      return 1
+    with open(metadata, 'r') as file:
+      data = file.read()
+      pattern = r'<version>(.+)</version>'
+      matches = re.findall(pattern, data)
+      matches.reverse()
+      for version in matches:
+        print('Tagging agp version ' + version)
+        tag_agp_version(version, args)
+
+
 def tag_agp_version(agp, args):
   tag = 'agp-%s' % agp
   result = get_tag_info_on_origin(tag)