diff --git a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
index c2cfe42..ae43001 100644
--- a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
@@ -97,6 +97,11 @@
   }
 
   @Override
+  public InternalOptions getOptions() {
+    return options;
+  }
+
+  @Override
   public void allocateRegisters(boolean debug) {
     assert options.debug == debug;
     allocateRegisters();
diff --git a/src/main/java/com/android/tools/r8/ir/code/Binop.java b/src/main/java/com/android/tools/r8/ir/code/Binop.java
index f751669..c2f21ac 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Binop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Binop.java
@@ -26,8 +26,13 @@
   public Binop(NumericType type, Value dest, Value left, Value right) {
     super(dest);
     this.type = type;
-    addInValue(left);
-    addInValue(right);
+    if (isCommutative() && (!right.isConstNumber() && left.isConstNumber())) {
+      addInValue(right);
+      addInValue(left);
+    } else {
+      addInValue(left);
+      addInValue(right);
+    }
   }
 
   public NumericType getNumericType() {
@@ -53,7 +58,8 @@
       return ((leftRegister == destRegister) ||
           (isCommutative() && rightRegister == destRegister)) &&
           leftRegister <= U4BIT_MAX &&
-          rightRegister <= U4BIT_MAX;
+          rightRegister <= U4BIT_MAX &&
+          !(allocator.getOptions().canHaveMul2AddrBug() && isMul());
     }
     return false;
   }
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 a54208d..67a4783 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
@@ -1549,8 +1549,7 @@
     insertAt.nextUntil(i ->
         i.inValues().contains(instruction.outValue())
         || i.isJumpInstruction()
-        || (hasCatchHandlers && i.instructionTypeCanThrow())
-        || (options.canHaveBoundsCheckEliminationBug() && i.isArrayLength()));
+        || (hasCatchHandlers && i.instructionTypeCanThrow()));
     Instruction next = insertAt.previous();
     instruction.forceSetPosition(
         next.isGoto() ? next.asGoto().getTarget().getPosition() : next.getPosition());
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 dbce627..8ad7a32 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
@@ -298,10 +298,11 @@
     ranges.sort(LocalRange::compareTo);
 
     // At each instruction compute the changes to live locals.
-    boolean localsChanged = false;
     LinkedList<LocalRange> openRanges = new LinkedList<>();
     Iterator<LocalRange> rangeIterator = ranges.iterator();
     LocalRange nextStartingRange = rangeIterator.next();
+    Int2ReferenceMap<DebugLocalInfo> ending = new Int2ReferenceOpenHashMap<>();
+    Int2ReferenceMap<DebugLocalInfo> starting = new Int2ReferenceOpenHashMap<>();
 
     for (BasicBlock block : blocks) {
       // Skip past all spill moves to obtain the instruction number of the actual first instruction.
@@ -347,42 +348,52 @@
           instruction.clearDebugValues();
           instructionIterator.remove();
         }
-        if (isSpillInstruction(instruction)) {
+        if (!instructionIterator.hasNext()) {
+          break;
+        }
+        Instruction nextInstruction = instructionIterator.peekNext();
+        if (isSpillInstruction(nextInstruction)) {
+          // No need to insert a DebugLocalsChange instruction before a spill instruction.
           continue;
         }
-        int index = instruction.getNumber();
+        int index = nextInstruction.getNumber();
         ListIterator<LocalRange> it = openRanges.listIterator(0);
-        Int2ReferenceMap<DebugLocalInfo> ending = new Int2ReferenceOpenHashMap<>();
-        Int2ReferenceMap<DebugLocalInfo> starting = new Int2ReferenceOpenHashMap<>();
         while (it.hasNext()) {
           LocalRange openRange = it.next();
-          // Any local change is inserted after the instruction so end is inclusive.
-          if (openRange.end <= index) {
+          // Close ranges up-to but excluding the first instruction.
+          if (!isLocalLiveAtInstruction(nextInstruction, openRange)) {
             it.remove();
             assert currentLocals.get(openRange.register) == openRange.local;
             currentLocals.remove(openRange.register);
-            localsChanged = true;
             ending.put(openRange.register, openRange.local);
           }
         }
-        while (nextStartingRange != null && nextStartingRange.start <= index) {
+        while (nextStartingRange != null && nextStartingRange.start < index) {
           // If the range is live at this index open it.
-          if (index < nextStartingRange.end) {
+          if (isLocalLiveAtInstruction(nextInstruction, nextStartingRange)) {
             openRanges.add(nextStartingRange);
             assert !currentLocals.containsKey(nextStartingRange.register);
             currentLocals.put(nextStartingRange.register, nextStartingRange.local);
             starting.put(nextStartingRange.register, nextStartingRange.local);
-            localsChanged = true;
           }
           nextStartingRange = rangeIterator.hasNext() ? rangeIterator.next() : null;
         }
-        if (localsChanged && instruction.getBlock().exit() != instruction) {
-          DebugLocalsChange change = createLocalsChange(ending, starting);
-          if (change != null) {
-            instructionIterator.add(change);
+        // Compute the final change in locals and insert it before nextInstruction.
+        boolean localsChanged = !ending.isEmpty() || !starting.isEmpty();
+        if (localsChanged) {
+          boolean skipChange =
+              nextInstruction == nextInstruction.getBlock().exit() && nextInstruction.isGoto();
+          if (!skipChange) {
+            DebugLocalsChange change = createLocalsChange(ending, starting);
+            if (change != null) {
+              // Insert the DebugLocalsChange instruction before nextInstruction.
+              instructionIterator.add(change);
+            }
           }
+          // Create new maps for the next DebugLocalsChange instruction.
+          ending = new Int2ReferenceOpenHashMap<>();
+          starting = new Int2ReferenceOpenHashMap<>();
         }
-        localsChanged = false;
       }
     }
   }
@@ -391,11 +402,6 @@
     return isLocalLiveAtInstruction(instruction, range.start, range.end, range.value);
   }
 
-  public static boolean isLocalLiveAtInstruction(
-      Instruction instruction, LiveRange range, Value value) {
-    return isLocalLiveAtInstruction(instruction, range.start, range.end, value);
-  }
-
   private static boolean isLocalLiveAtInstruction(
       Instruction instruction, int start, int end, Value value) {
     int number = instruction.getNumber();
@@ -584,6 +590,11 @@
     return getRegisterForValue(value, instructionNumber);
   }
 
+  @Override
+  public InternalOptions getOptions() {
+    return options;
+  }
+
   private ImmutableList<BasicBlock> computeLivenessInformation() {
     ImmutableList<BasicBlock> blocks = code.numberInstructions();
     liveAtEntrySets = code.computeLiveAtEntrySets();
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterAllocator.java
index 79ba8db..8fcc6b0 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterAllocator.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.ir.regalloc;
 
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.InternalOptions;
 
 public interface RegisterAllocator {
   void allocateRegisters(boolean debug);
@@ -11,4 +12,5 @@
   int getRegisterForValue(Value value, int instructionNumber);
   boolean argumentValueUsesHighRegister(Value value, int instructionNumber);
   int getArgumentOrAllocateRegisterForValue(Value value, int instructionNumber);
+  InternalOptions getOptions();
 }
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
index 2dbc015..3dc151d 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
@@ -296,8 +296,18 @@
         scheduler.addMove(
             new RegisterMove(move.to.getRegister(), move.type, move.from.getValue().definition));
       } else if (move.to.getRegister() != move.from.getRegister()) {
-        scheduler.addMove(
-            new RegisterMove(move.to.getRegister(), move.from.getRegister(), move.type));
+        // In case the runtime might have a bound-check elimination bug we make sure to define all
+        // indexing constants with an actual const instruction rather than a move. This appears to
+        // avoid a bug where the index variable could end up being uninitialized.
+        if (code.options.canHaveBoundsCheckEliminationBug()
+            && move.from.getValue().isConstNumber()
+            && move.type == MoveType.SINGLE) {
+          scheduler.addMove(
+              new RegisterMove(move.to.getRegister(), move.type, move.from.getValue().definition));
+        } else {
+          scheduler.addMove(
+              new RegisterMove(move.to.getRegister(), move.from.getRegister(), move.type));
+        }
       }
     }
     scheduler.schedule();
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 a8ff665..4099912 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -488,18 +488,16 @@
   // Some Lollipop versions of Art found in the wild perform invalid bounds
   // check elimination. There is a fast path of loops and a slow path.
   // The bailout to the slow path is performed too early and therefore
-  // the loop variable might not be defined in the slow path code leading
+  // the array-index variable might not be defined in the slow path code leading
   // to use of undefined registers as indices into arrays. The result
   // is ArrayIndexOutOfBounds exceptions.
   //
-  // In an attempt to help these Art VMs get the loop variable initialized
-  // early, we do not lower constants past array-length instructions when
-  // building for Lollipop or below.
+  // In an attempt to help these Art VMs, all single-width constants are initialized and not moved.
   //
   // There is no guarantee that this works, but it does make the problem
   // disappear on the one known instance of this problem.
   //
-  // See b/69364976.
+  // See b/69364976 and b/77996377.
   public boolean canHaveBoundsCheckEliminationBug() {
     return minApiLevel <= AndroidApiLevel.L.getLevel();
   }
@@ -558,4 +556,26 @@
   public boolean canHaveCmpLongBug() {
     return minApiLevel < AndroidApiLevel.L.getLevel();
   }
+
+  // Some Lollipop VMs incorrectly optimize code with mul2addr instructions. In particular,
+  // the following hash code method produces wrong results after optimizations:
+  //
+  //    0:   0x00: IgetObject          v0, v3, Field java.lang.Class MultiClassKey.first
+  //    1:   0x02: InvokeVirtual       { v0 } Ljava/lang/Object;->hashCode()I
+  //    2:   0x05: MoveResult          v0
+  //    3:   0x06: Const16             v1, 0x001f (31)
+  //    4:   0x08: MulInt2Addr         v1, v0
+  //    5:   0x09: IgetObject          v2, v3, Field java.lang.Class MultiClassKey.second
+  //    6:   0x0b: InvokeVirtual       { v2 } Ljava/lang/Object;->hashCode()I
+  //    7:   0x0e: MoveResult          v2
+  //    8:   0x0f: AddInt2Addr         v1, v2
+  //    9:   0x10: Return              v1
+  //
+  // It seems that the issue is the MulInt2Addr instructions. Avoiding that, the VM computes
+  // hash codes correctly also after optimizations.
+  //
+  // This issue has only been observed on a Verizon Ellipsis 8 tablet. See b/76115465.
+  public boolean canHaveMul2AddrBug() {
+    return minApiLevel < AndroidApiLevel.M.getLevel();
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java b/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
index 45b99e3..d51d5c3 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
@@ -27,6 +27,7 @@
 import com.android.tools.r8.code.Throw;
 import com.android.tools.r8.graph.DexCode;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.DexInspector;
 import com.android.tools.r8.utils.DexInspector.ClassSubject;
 import com.android.tools.r8.utils.DexInspector.MethodSubject;
@@ -96,6 +97,7 @@
     R8Command command =
         R8Command.builder()
             .addProgramFiles(getInputFile())
+            .setMinApiLevel(AndroidApiLevel.M.getLevel())
             .setOutput(out, OutputMode.DexIndexed)
             .addProguardConfigurationFiles(Paths.get(keepRulesFile))
             .build();
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java
index 2ea44eb..55195a4 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.utils.InternalOptions;
 import org.junit.Test;
 
 public class IdenticalAfterRegisterAllocationTest {
@@ -41,6 +42,11 @@
     public int getArgumentOrAllocateRegisterForValue(Value value, int instructionNumber) {
       return value.getNumber();
     }
+
+    @Override
+    public InternalOptions getOptions() {
+      return new InternalOptions();
+    }
   }
 
   @Test