diff --git a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
index 85a2509..a5599fa 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
@@ -19,6 +19,7 @@
 public class NewInstance extends Instruction {
 
   public final DexType clazz;
+  private boolean allowSpilling = true;
 
   public NewInstance(DexType clazz, Value dest) {
     super(dest);
@@ -109,4 +110,12 @@
   public boolean triggersInitializationOfClass(DexType klass) {
     return clazz == klass;
   }
+
+  public void markNoSpilling() {
+    allowSpilling = false;
+  }
+
+  public boolean isSpillingAllowed() {
+    return allowSpilling;
+  }
 }
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 90a9898..306d7a1 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
@@ -627,6 +627,10 @@
     printC1VisualizerHeader(method);
     printMethod(code, "Initial IR (SSA)");
 
+    if (options.canHaveArtStringNewInitBug()) {
+      codeRewriter.ensureDirectStringNewToInit(code);
+    }
+
     if (options.debug) {
       codeRewriter.simplifyDebugLocals(code);
     }
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 3ea434a..6ab4845 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
@@ -60,6 +60,7 @@
 import com.android.tools.r8.ir.code.MemberType;
 import com.android.tools.r8.ir.code.NewArrayEmpty;
 import com.android.tools.r8.ir.code.NewArrayFilledData;
+import com.android.tools.r8.ir.code.NewInstance;
 import com.android.tools.r8.ir.code.NumericType;
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Position;
@@ -97,9 +98,12 @@
 import it.unimi.dsi.fastutil.ints.IntLists;
 import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
 import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Comparator;
+import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
@@ -2683,4 +2687,147 @@
     // When we fall out of the loop the iterator is in the last eol block.
     iterator.add(new InvokeVirtual(printLn, null, ImmutableList.of(out, empty)));
   }
+
+  public static void ensureDirectStringNewToInit(IRCode code) {
+    DexItemFactory factory = code.options.itemFactory;
+    for (BasicBlock block : code.blocks) {
+      for (InstructionListIterator it = block.listIterator(); it.hasNext(); ) {
+        Instruction instruction = it.next();
+        if (instruction.isInvokeDirect()) {
+          InvokeDirect invoke = instruction.asInvokeDirect();
+          DexMethod method = invoke.getInvokedMethod();
+          if (factory.isConstructor(method)
+              && method.holder == factory.stringType
+              && invoke.getReceiver().isPhi()) {
+            NewInstance newInstance = findNewInstance(invoke.getReceiver().asPhi());
+            replaceTrivialNewInstancePhis(newInstance.outValue());
+            if (invoke.getReceiver().isPhi()) {
+              throw new CompilationError(
+                  "Failed to remove trivial phis between new-instance and <init>");
+            }
+            newInstance.markNoSpilling();
+          }
+        }
+      }
+    }
+  }
+
+  private static NewInstance findNewInstance(Phi phi) {
+    Set<Phi> seen = new HashSet<>();
+    Set<Value> values = new HashSet<>();
+    recursiveAddOperands(phi, seen, values);
+    if (values.size() != 1) {
+      throw new CompilationError("Failed to identify unique new-instance for <init>");
+    }
+    Value newInstanceValue = values.iterator().next();
+    if (newInstanceValue.definition == null || !newInstanceValue.definition.isNewInstance()) {
+      throw new CompilationError("Invalid defining value for call to <init>");
+    }
+    return newInstanceValue.definition.asNewInstance();
+  }
+
+  private static void recursiveAddOperands(Phi phi, Set<Phi> seen, Set<Value> values) {
+    for (Value operand : phi.getOperands()) {
+      if (!operand.isPhi()) {
+        values.add(operand);
+      } else {
+        Phi phiOp = operand.asPhi();
+        if (seen.add(phiOp)) {
+          recursiveAddOperands(phiOp, seen, values);
+        }
+      }
+    }
+  }
+
+  // If an <init> call takes place on a phi the code must contain an irreducible loop between the
+  // new-instance and the <init>. Assuming the code is verifiable, new-instance must flow to a
+  // unique <init>. Here we compute the set of strongly connected phis making use of the
+  // new-instance value and replace all trivial ones by the new-instance value.
+  // This is a simplified variant of the removeRedundantPhis algorithm in Section 3.2 of:
+  // http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
+  private static void replaceTrivialNewInstancePhis(Value newInstanceValue) {
+    List<Set<Value>> components = new SCC().computeSCC(newInstanceValue);
+    for (int i = components.size() - 1; i >= 0; i--) {
+      Set<Value> component = components.get(i);
+      if (component.size() == 1 && component.iterator().next() == newInstanceValue) {
+        continue;
+      }
+      Set<Phi> trivialPhis = new HashSet<>();
+      for (Value value : component) {
+        boolean isTrivial = true;
+        Phi p = value.asPhi();
+        for (Value op : p.getOperands()) {
+          if (op != newInstanceValue && !component.contains(op)) {
+            isTrivial = false;
+            break;
+          }
+        }
+        if (isTrivial) {
+          trivialPhis.add(p);
+        }
+      }
+      for (Phi trivialPhi : trivialPhis) {
+        for (Value op : trivialPhi.getOperands()) {
+          op.removePhiUser(trivialPhi);
+        }
+        trivialPhi.replaceUsers(newInstanceValue);
+        trivialPhi.getBlock().removePhi(trivialPhi);
+      }
+    }
+  }
+
+  // Dijkstra's path-based strongly-connected components algorithm.
+  // https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm
+  private static class SCC {
+
+    private int currentTime = 0;
+    private final Reference2IntMap<Value> discoverTime = new Reference2IntOpenHashMap<>();
+    private final Set<Value> unassignedSet = new HashSet<>();
+    private final Deque<Value> unassignedStack = new ArrayDeque<>();
+    private final Deque<Value> preorderStack = new ArrayDeque<>();
+    private final List<Set<Value>> components = new ArrayList<>();
+
+    public List<Set<Value>> computeSCC(Value v) {
+      assert currentTime == 0;
+      dfs(v);
+      return components;
+    }
+
+    private void dfs(Value value) {
+      discoverTime.put(value, currentTime++);
+      unassignedSet.add(value);
+      unassignedStack.push(value);
+      preorderStack.push(value);
+      for (Phi phi : value.uniquePhiUsers()) {
+        if (!discoverTime.containsKey(phi)) {
+          // If not seen yet, continue the search.
+          dfs(phi);
+        } else if (unassignedSet.contains(phi)) {
+          // If seen already and the element is on the unassigned stack we have found a cycle.
+          // Pop off everything discovered later than the target from the preorder stack. This may
+          // not coincide with the cycle as an outer cycle may already have popped elements off.
+          int discoverTimeOfPhi = discoverTime.getInt(phi);
+          while (discoverTimeOfPhi < discoverTime.getInt(preorderStack.peek())) {
+            preorderStack.pop();
+          }
+        }
+      }
+      if (preorderStack.peek() == value) {
+        // If the current element is the top of the preorder stack, then we are at entry to a
+        // strongly-connected component consisting of this element and every element above this
+        // element on the stack.
+        Set<Value> component = new HashSet<>(unassignedStack.size());
+        while (true) {
+          Value member = unassignedStack.pop();
+          unassignedSet.remove(member);
+          component.add(member);
+          if (member == value) {
+            components.add(component);
+            break;
+          }
+        }
+        preorderStack.pop();
+      }
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index 0976087..d2c7701 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
@@ -1819,6 +1819,10 @@
       // we allow ourselves to look at monitor spill candidates as well. Registers holding objects
       // used as monitors should not be spilled if we can avoid it. Spilling them can lead
       // to Art lock verification issues.
+      // Also, at this point we still don't allow splitting any string new-instance instructions
+      // that have been explicitly blocked. Doing so could lead to a behavioral bug on some ART
+      // runtimes (b/80118070). To remove this restriction, we would need to know when the call to
+      // <init> has definitely happened, and would be safe to split the value after that point.
       if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
         candidate = getLargestValidCandidate(
             unhandledInterval, registerConstraint, needsRegisterPair, usePositions, Type.MONITOR);
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
index c8e6e4c..bf65310 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
@@ -522,6 +522,13 @@
     return usedInMonitorOperations;
   }
 
+  public boolean isNewStringInstanceDisallowingSpilling() {
+    // Due to b/80118070 some String new-instances must not be spilled.
+    return value.definition != null
+        && value.definition.isNewInstance()
+        && !value.definition.asNewInstance().isSpillingAllowed();
+  }
+
   public int numberOfUsesWithConstraint() {
     int count = 0;
     for (LiveIntervalsUse use : getUses()) {
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java
index 459114b..eff8bea 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java
@@ -23,6 +23,7 @@
   private int[] backing;
   private final BitSet registerHoldsConstant;
   private final BitSet registerHoldsMonitor;
+  private final BitSet registerHoldsNewStringInstanceDisallowingSpilling;
 
   public RegisterPositions(int limit) {
     this.limit = limit;
@@ -32,6 +33,7 @@
     }
     registerHoldsConstant = new BitSet(limit);
     registerHoldsMonitor = new BitSet(limit);
+    registerHoldsNewStringInstanceDisallowingSpilling = new BitSet(limit);
   }
 
   public boolean hasType(int index, Type type) {
@@ -41,7 +43,9 @@
       case CONST_NUMBER:
         return holdsConstant(index);
       case OTHER:
-        return !holdsMonitor(index) && !holdsConstant(index);
+        return !holdsMonitor(index)
+            && !holdsConstant(index)
+            && !holdsNewStringInstanceDisallowingSpilling(index);
       case ANY:
         return true;
       default:
@@ -55,6 +59,10 @@
 
   private boolean holdsMonitor(int index) { return registerHoldsMonitor.get(index); }
 
+  private boolean holdsNewStringInstanceDisallowingSpilling(int index) {
+    return registerHoldsNewStringInstanceDisallowingSpilling.get(index);
+  }
+
   public void set(int index, int value) {
     if (index >= backing.length) {
       grow(index + 1);
@@ -66,6 +74,8 @@
     set(index, value);
     registerHoldsConstant.set(index, intervals.isConstantNumberInterval());
     registerHoldsMonitor.set(index, intervals.usedInMonitorOperation());
+    registerHoldsNewStringInstanceDisallowingSpilling.set(
+        index, intervals.isNewStringInstanceDisallowingSpilling());
   }
 
   public int get(int index) {
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 68796ac..436c94f 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -620,4 +620,12 @@
   public boolean canHaveDex2OatLinkedListBug() {
     return minApiLevel < AndroidApiLevel.N.getLevel();
   }
+
+  // Art 7.0.0 and later Art JIT may perform an invalid optimization if a string new-instance does
+  // not flow directly to the init call.
+  //
+  // See b/78493232 and b/80118070.
+  public boolean canHaveArtStringNewInitBug() {
+    return minApiLevel <= AndroidApiLevel.P.getLevel();
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232.java b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232.java
index 2e4d6cf..fa4e3e1 100644
--- a/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232.java
+++ b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232.java
@@ -7,11 +7,9 @@
 import com.android.tools.r8.ClassFileConsumer.ArchiveConsumer;
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.ToolHelper.DexVm;
 import java.io.IOException;
 import java.nio.file.Path;
 import java.nio.file.Paths;
-import org.junit.Assume;
 import org.junit.Test;
 
 public class Regress78493232 extends AsmTestBase {
@@ -20,7 +18,6 @@
   public void test() throws Exception {
     // Run test on JVM and ART(x86) to ensure expected behavior.
     // Running the same test on an ARM JIT causes errors.
-    Assume.assumeTrue(ToolHelper.getDexVm() != DexVm.ART_7_0_0_HOST); // b/78866151
     ensureSameOutput(
         Regress78493232Dump.CLASS_NAME,
         Regress78493232Dump.dump(),
diff --git a/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232Dump_WithPhi.java b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232Dump_WithPhi.java
new file mode 100644
index 0000000..8a6bdcf
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232Dump_WithPhi.java
@@ -0,0 +1,337 @@
+// Copyright (c) 2018, 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.regress.b78493232;
+
+import com.android.tools.r8.utils.DescriptorUtils;
+import org.objectweb.asm.ClassWriter;
+import org.objectweb.asm.FieldVisitor;
+import org.objectweb.asm.Label;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+public class Regress78493232Dump_WithPhi implements Opcodes {
+
+  public static final String CLASS_NAME = "regress78493232.Test";
+  public static final String CLASS_DESC = DescriptorUtils.javaTypeToDescriptor(CLASS_NAME);
+  public static final String CLASS_INTERNAL = DescriptorUtils.descriptorToInternalName(CLASS_DESC);
+
+  public static final String UTILS_CLASS_NAME = Regress78493232Utils.class.getCanonicalName();
+  public static final String UTILS_CLASS_DESC =
+      DescriptorUtils.javaTypeToDescriptor(UTILS_CLASS_NAME);
+  public static final String UTILS_CLASS_INTERNAL =
+      DescriptorUtils.descriptorToInternalName(UTILS_CLASS_DESC);
+
+  static final int iterations = 1000;
+
+  // Arguments that have been seen when issue occurred.
+  static byte arg0 = 13;
+  static short arg1 = 25;
+  static int arg2 = 312;
+
+  // Static state of the class seen when the issue occurred.
+  static int staticIntA = 0;
+  static int staticIntB = 29;
+  static byte[] staticByteArray =
+      new byte[] {
+        63, 101, 52, -33, 9, -21, 21, 51, -59, -6, 65, -27, -37, -2, -5, 1, 33, -33, 2, 13, 4, -12,
+        -53, 54, 2, -15, 46, 2, 13, 4, -3, 30, -47, 9, 0, -13, 3, -11, -10, 13, -2, 61, -69, -6, 6,
+        -1, 15, -8, 63, -22, -33, -19, 50, -35, -3, 7, 8, 2, -7, 9, -21, 21, 51, -62, 11, -13, 7,
+        57, -37, -38, 6, -1, 15, -8, -53, 3, -19, 19, 50, -53, 3, -19, 19, 50, 9, -21, 21, 51, -59,
+        -6, 65, -27, -6, 10, -51, 21, -2, -11, -4, 11, -6, 1, 1, 11, -3, 61, -50, 50, -75, 75, -52,
+        0, 52, -53, -9, -3, -4, 14, 2, -15, 49, -41, 11, -18, 0, 39, -35, 14, -3, -1, -13, 9, -21,
+        21, 51, -59, -6, 65, -70, 7, -3, 12, -5, -9, 2, -13, 23, -27, 9, -11, 15, -6, 11, 11, 11, 7,
+        16, -31, -2, 4, 7, 9, -21, 21, 51, -69, 14, 2, -18, 3, 9, -11, -5, 75, -37, -18, 2, -18, 3,
+        13, 19, -15, -13, 10, -11, 2, -1, -7, 7, -15, 15, 5, 9, -11, 15, 13, 4, -3, -18, 3, 0, 13,
+        -9, -6, 32, -21, -4, 8, 24, -28, -3, 0, 3, -10, 9, -21, 21, 51, -59, -6, 65, -20, -55, 5,
+        15, 36, -49, 0, 17, -24, 48, -37, -2, -5, 1, 33, -33, 2, 13, 4, -12, 9, -21, 21, 51, -59,
+        -6, 65, -24, -35, -3, 7, 22, -38, 1, 4, -5, 1, 33, -33, 2, 13, 4, -12, 1, 11, -3, 61, -50,
+        50, -75, 75, -52, 0, 52, -52, 63, -77, 2, -15, 47, -51, 4, 15, -13, 4, 13, -11, 25, -33, 5,
+        -3, 17, -6, 2, 33, -37, -9, 13, 2, -17, 5, -3, -7, -3, 14, -3, 33, -41, 11, -18, 0, 2, -15,
+        43, -37, -5, -1, 19, -13, 11, -2, -13, 10, -14, 3, 6, 5, 54, -65, -4, 69, -23, -41, -8, 13,
+        -9, 3, 1, 1, 8, -9, -6, 21, -4, 20, -8, 9, -21, 21, 51, -62, 11, -13, 7, 57, -21, -41, 11,
+        -18, 0, 39, -35, 14, -3, -1, -13, -3, 14, -3, 32, -33, -19, 1, 11, -3, 62, -51, 51, -76, 76,
+        -53, 0, 53, -54, 14, -15, 33, -18, 0, 1, 9, -21, 21, 51, -59, -6, 65, -22, -29, -19, 19, 24,
+        -37, -2, -5, 1, 33, -33, 2, 13, 4, -12, 2, -15, 36, -34, 3, -1, 11, -13, -2, -5, 2, -15, 51,
+        -33, -17, 4, 3, -9, 1, 15, 21, -17, -19, 12, 9, -21, 21, 51, -59, -6, 65, -24, -35, -3, 7,
+        9, -21, 21, 51, -59, -6, 65, -24, -35, -3, 7, 33, -33, -14, 16, -15, 9, -7, -4, 5, -3, 21,
+        -3, 19, -8, 9, -19, 4, 43, -37, -6
+      };
+
+  public static byte[] dump() {
+    return dump(arg0, arg1, arg2, staticIntA, staticIntB, staticByteArray);
+  }
+
+  public static byte[] dump(
+      byte arg0, short arg1, int arg2, int staticIntA, int staticIntB, byte[] staticByteArray) {
+    ClassWriter cw = new ClassWriter(ClassWriter.COMPUTE_MAXS | ClassWriter.COMPUTE_FRAMES);
+    FieldVisitor fv;
+    MethodVisitor mv;
+
+    cw.visit(V1_6, ACC_PUBLIC + ACC_SUPER, CLASS_INTERNAL, null, "java/lang/Object", null);
+
+    {
+      fv = cw.visitField(ACC_PRIVATE + ACC_FINAL + ACC_STATIC, "staticByteArray", "[B", null, null);
+      fv.visitEnd();
+    }
+    {
+      fv = cw.visitField(ACC_PRIVATE + ACC_STATIC, "staticIntA", "I", null, null);
+      fv.visitEnd();
+    }
+    {
+      fv = cw.visitField(ACC_PRIVATE + ACC_STATIC, "staticIntB", "I", null, null);
+      fv.visitEnd();
+    }
+
+    {
+      mv = cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "run", "()Ljava/lang/String;", null, null);
+      mv.visitCode();
+      mv.visitIntInsn(BIPUSH, arg0);
+      mv.visitIntInsn(SIPUSH, arg1);
+      mv.visitIntInsn(SIPUSH, arg2);
+      mv.visitMethodInsn(
+          INVOKESTATIC, CLASS_INTERNAL, "methodCausingIssue", "(BSI)Ljava/lang/String;", false);
+      mv.visitInsn(ARETURN);
+      mv.visitMaxs(-1, -1);
+      mv.visitEnd();
+    }
+
+    {
+      mv = cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "getHash", "()I", null, null);
+      mv.visitCode();
+      getHash(mv);
+      mv.visitInsn(IRETURN);
+      mv.visitMaxs(-1, -1);
+      mv.visitEnd();
+    }
+
+    {
+      mv = cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null);
+      mv.visitCode();
+
+      mv.visitInsn(ICONST_0);
+      mv.visitVarInsn(ISTORE, 1);
+      Label l0 = new Label();
+      mv.visitLabel(l0);
+      mv.visitVarInsn(ILOAD, 1);
+      mv.visitLdcInsn(new Integer(iterations));
+      Label l1 = new Label();
+      mv.visitJumpInsn(IF_ICMPGE, l1);
+      mv.visitMethodInsn(INVOKESTATIC, CLASS_INTERNAL, "run", "()Ljava/lang/String;", false);
+      mv.visitVarInsn(ILOAD, 1);
+      mv.visitMethodInsn(
+          INVOKESTATIC, UTILS_CLASS_INTERNAL, "compare", "(Ljava/lang/String;I)V", false);
+      mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticIntA", "I");
+      mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticIntB", "I");
+      mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticByteArray", "[B");
+      mv.visitVarInsn(ILOAD, 1);
+      mv.visitMethodInsn(INVOKESTATIC, UTILS_CLASS_INTERNAL, "compareHash", "(II[BI)V", false);
+      mv.visitIincInsn(1, 1);
+      mv.visitJumpInsn(GOTO, l0);
+      mv.visitLabel(l1);
+      mv.visitLdcInsn("Completed successfully after " + iterations + " iterations");
+      mv.visitMethodInsn(
+          INVOKESTATIC, UTILS_CLASS_INTERNAL, "println", "(Ljava/lang/String;)V", false);
+      mv.visitInsn(RETURN);
+      mv.visitMaxs(-1, -1);
+      mv.visitEnd();
+    }
+
+    {
+      mv = cw.visitMethod(ACC_STATIC, "<clinit>", "()V", null, null);
+      mv.visitCode();
+      mv.visitIntInsn(BIPUSH, staticIntA);
+      mv.visitFieldInsn(PUTSTATIC, CLASS_INTERNAL, "staticIntA", "I");
+      mv.visitIntInsn(BIPUSH, staticIntB);
+      mv.visitFieldInsn(PUTSTATIC, CLASS_INTERNAL, "staticIntB", "I");
+      mv.visitLdcInsn(staticByteArray.length);
+      mv.visitIntInsn(NEWARRAY, T_BYTE);
+      for (int i = 0; i < staticByteArray.length; i++) {
+        mv.visitInsn(DUP);
+        mv.visitIntInsn(SIPUSH, i);
+        mv.visitIntInsn(BIPUSH, staticByteArray[i]);
+        mv.visitInsn(BASTORE);
+      }
+      mv.visitFieldInsn(PUTSTATIC, CLASS_INTERNAL, "staticByteArray", "[B");
+      mv.visitInsn(RETURN);
+      mv.visitMaxs(-1, -1);
+      mv.visitEnd();
+    }
+
+    {
+      mv =
+          cw.visitMethod(
+              ACC_PRIVATE + ACC_STATIC,
+              "methodCausingIssue",
+              "(BSI)Ljava/lang/String;",
+              null,
+              null);
+      mv.visitCode();
+      Label l0 = new Label();
+      mv.visitJumpInsn(GOTO, l0);
+      mv.visitLabel(l0);
+      mv.visitIntInsn(SIPUSH, 472);
+      mv.visitVarInsn(ILOAD, 2);
+      mv.visitInsn(ISUB);
+      mv.visitVarInsn(ISTORE, 2);
+      mv.visitInsn(ICONST_0);
+      mv.visitVarInsn(ISTORE, 3);
+      mv.visitTypeInsn(NEW, "java/lang/String");
+      mv.visitVarInsn(ASTORE, 10);
+      mv.visitIntInsn(BIPUSH, 119);
+      mv.visitVarInsn(ILOAD, 0);
+      mv.visitInsn(ISUB);
+      mv.visitVarInsn(ISTORE, 0);
+      mv.visitIincInsn(1, 1);
+      mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticByteArray", "[B");
+      mv.visitVarInsn(ASTORE, 4);
+      mv.visitVarInsn(ILOAD, 1);
+      mv.visitIntInsn(NEWARRAY, T_BYTE);
+      mv.visitVarInsn(ALOAD, 4);
+      Label l1 = new Label();
+      mv.visitJumpInsn(IFNONNULL, l1);
+      Label l2 = new Label();
+      mv.visitJumpInsn(GOTO, l2);
+      mv.visitLabel(l1);
+      Label l3 = new Label();
+      mv.visitJumpInsn(GOTO, l3);
+      mv.visitLabel(l2);
+      mv.visitVarInsn(ILOAD, 1);
+      mv.visitVarInsn(ILOAD, 2);
+      Label l4 = new Label();
+      mv.visitJumpInsn(GOTO, l4);
+      Label l5 = new Label();
+      mv.visitLabel(l5);
+      mv.visitInsn(INEG);
+      mv.visitInsn(IADD);
+      mv.visitVarInsn(ISTORE, 0);
+      mv.visitJumpInsn(GOTO, l3);
+      mv.visitLabel(l3);
+      mv.visitInsn(DUP);
+      mv.visitVarInsn(ILOAD, 3);
+      mv.visitIincInsn(3, 1);
+      mv.visitVarInsn(ILOAD, 0);
+      mv.visitInsn(I2B);
+      mv.visitInsn(BASTORE);
+      mv.visitVarInsn(ILOAD, 3);
+      mv.visitVarInsn(ILOAD, 1);
+      Label l6 = new Label();
+      mv.visitJumpInsn(IF_ICMPNE, l6);
+      Label l7 = new Label();
+      Label l7_b0 = new Label();
+      Label l7_b1 = new Label();
+      Label l7_join = new Label();
+      mv.visitJumpInsn(GOTO, l7);
+      mv.visitLabel(l6);
+      Label l8 = new Label();
+      mv.visitJumpInsn(GOTO, l8);
+      // Depending on the argument either load the new-instance string or null on the stack.
+      mv.visitLabel(l7);
+      mv.visitVarInsn(ILOAD, 0);
+      mv.visitJumpInsn(IFEQ, l7_b1);
+      mv.visitLabel(l7_b0);
+      mv.visitInsn(ACONST_NULL);
+      mv.visitJumpInsn(GOTO, l7_join);
+      mv.visitLabel(l7_b1);
+      mv.visitVarInsn(ALOAD, 10);
+      // Swap the new-instance or null, with the byte-array.
+      mv.visitLabel(l7_join);
+      mv.visitInsn(SWAP);
+      // Load the new-instacne and swap again with the byte-array.
+      mv.visitVarInsn(ALOAD, 10);
+      mv.visitInsn(SWAP);
+      mv.visitInsn(ICONST_0);
+      // Invoke special will now always be on the new-instance as receiver.
+      mv.visitMethodInsn(INVOKESPECIAL, "java/lang/String", "<init>", "([BI)V", false);
+      // Return will be either new-instance or null.
+      // This will force a non-trivial phi of the new-instance on this block, ie, prior to <init>.
+      // This phi must remain.
+      mv.visitInsn(ARETURN);
+      mv.visitLabel(l8);
+      mv.visitVarInsn(ILOAD, 0);
+      mv.visitVarInsn(ALOAD, 4);
+      mv.visitIincInsn(2, 1);
+      mv.visitVarInsn(ILOAD, 2);
+      mv.visitInsn(BALOAD);
+      Label l9 = new Label();
+      mv.visitJumpInsn(GOTO, l9);
+      mv.visitLabel(l4);
+      mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticIntB", "I");
+      mv.visitIntInsn(BIPUSH, 125);
+      mv.visitInsn(IADD);
+      mv.visitInsn(DUP);
+      mv.visitIntInsn(SIPUSH, 128);
+      mv.visitInsn(IREM);
+      mv.visitFieldInsn(PUTSTATIC, CLASS_INTERNAL, "staticIntA", "I");
+      mv.visitInsn(ICONST_2);
+      mv.visitInsn(IREM);
+      Label l10 = new Label();
+      mv.visitJumpInsn(IFEQ, l10);
+      Label l11 = new Label();
+      mv.visitJumpInsn(GOTO, l11);
+      mv.visitLabel(l10);
+      Label l12 = new Label();
+      mv.visitJumpInsn(GOTO, l12);
+      Label l13 = new Label();
+      mv.visitLabel(l13);
+      mv.visitInsn(INEG);
+      mv.visitInsn(IADD);
+      mv.visitVarInsn(ISTORE, 0);
+      mv.visitJumpInsn(GOTO, l3);
+      mv.visitLabel(l9);
+      mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticIntA", "I");
+      mv.visitIntInsn(BIPUSH, 29);
+      mv.visitInsn(IADD);
+      mv.visitInsn(DUP);
+      mv.visitIntInsn(SIPUSH, 128);
+      mv.visitInsn(IREM);
+      mv.visitFieldInsn(PUTSTATIC, CLASS_INTERNAL, "staticIntB", "I");
+      mv.visitInsn(ICONST_2);
+      mv.visitInsn(IREM);
+      Label l14 = new Label();
+      mv.visitJumpInsn(IFNE, l14);
+      Label l15 = new Label();
+      mv.visitJumpInsn(GOTO, l15);
+      mv.visitLabel(l14);
+      Label l16 = new Label();
+      mv.visitJumpInsn(GOTO, l16);
+      Label l17 = new Label();
+      mv.visitLabel(l17);
+      mv.visitInsn(INEG);
+      mv.visitInsn(IADD);
+      mv.visitVarInsn(ISTORE, 0);
+      mv.visitJumpInsn(GOTO, l3);
+      Label l18 = new Label();
+      mv.visitLabel(l18);
+      mv.visitTableSwitchInsn(0, 1, l11, new Label[] {l13, l5});
+      mv.visitLabel(l12);
+      mv.visitInsn(ICONST_1);
+      mv.visitJumpInsn(GOTO, l18);
+      mv.visitLabel(l11);
+      mv.visitInsn(ICONST_0);
+      mv.visitJumpInsn(GOTO, l18);
+      Label l19 = new Label();
+      mv.visitLabel(l19);
+      mv.visitTableSwitchInsn(0, 1, l15, new Label[] {l5, l17});
+      mv.visitLabel(l16);
+      mv.visitInsn(ICONST_0);
+      mv.visitJumpInsn(GOTO, l19);
+      mv.visitLabel(l15);
+      mv.visitInsn(ICONST_1);
+      mv.visitJumpInsn(GOTO, l19);
+      mv.visitMaxs(8, 5);
+      mv.visitEnd();
+    }
+
+    cw.visitEnd();
+
+    return cw.toByteArray();
+  }
+
+  private static void getHash(MethodVisitor mv) {
+    mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticIntA", "I");
+    mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticIntB", "I");
+    mv.visitFieldInsn(GETSTATIC, CLASS_INTERNAL, "staticByteArray", "[B");
+    mv.visitMethodInsn(INVOKESTATIC, UTILS_CLASS_INTERNAL, "getHash", "(II[B)I", false);
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232_WithPhi.java b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232_WithPhi.java
new file mode 100644
index 0000000..3c7c465
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232_WithPhi.java
@@ -0,0 +1,23 @@
+// Copyright (c) 2018, 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.regress.b78493232;
+
+import com.android.tools.r8.AsmTestBase;
+import com.android.tools.r8.ToolHelper;
+import org.junit.Test;
+
+// Variant of Regress78493232, but where the new-instance is forced to flow to a non-trivial phi
+// function prior to the call to <init>.
+public class Regress78493232_WithPhi extends AsmTestBase {
+
+  @Test
+  public void test() throws Exception {
+    // Run test on JVM and ART(x86) to ensure expected behavior.
+    // Running the same test on an ARM JIT causes errors.
+    ensureSameOutput(
+        Regress78493232Dump_WithPhi.CLASS_NAME,
+        Regress78493232Dump_WithPhi.dump(),
+        ToolHelper.getClassAsBytes(Regress78493232Utils.class));
+  }
+}