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/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index dd13dfc..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
@@ -590,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/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index a8ff665..d199f37 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -558,4 +558,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