diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index 46a587f..1e51047 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -1136,6 +1136,9 @@
       _mov(Dest, T);
       break;
     case InstArithmetic::Udiv:
+      // div and idiv are the few arithmetic operators that do not allow
+      // immediates as the operand.
+      Src1 = legalize(Src1, Legal_Reg | Legal_Mem);
       if (Dest->getType() == IceType_i8) {
         Variable *T_ah = NULL;
         Constant *Zero = Ctx->getConstantInt(IceType_i8, 0);
@@ -1152,6 +1155,7 @@
       }
       break;
     case InstArithmetic::Sdiv:
+      Src1 = legalize(Src1, Legal_Reg | Legal_Mem);
       T_edx = makeReg(IceType_i32, Reg_edx);
       _mov(T, Src0, Reg_eax);
       _cdq(T_edx, T);
@@ -1159,6 +1163,7 @@
       _mov(Dest, T);
       break;
     case InstArithmetic::Urem:
+      Src1 = legalize(Src1, Legal_Reg | Legal_Mem);
       if (Dest->getType() == IceType_i8) {
         Variable *T_ah = NULL;
         Constant *Zero = Ctx->getConstantInt(IceType_i8, 0);
@@ -1175,6 +1180,7 @@
       }
       break;
     case InstArithmetic::Srem:
+      Src1 = legalize(Src1, Legal_Reg | Legal_Mem);
       T_edx = makeReg(IceType_i32, Reg_edx);
       _mov(T, Src0, Reg_eax);
       _cdq(T_edx, T);
@@ -1370,7 +1376,7 @@
   // computing the strength-reduced result at translation time, but we're
   // unlikely to see something like that in the bitcode that the optimizer
   // wouldn't have already taken care of.
-  Operand *Src0RM = legalize(Inst->getSrc(0), Legal_Reg | Legal_Mem, true);
+  Operand *Src0RM = legalize(Inst->getSrc(0), Legal_Reg | Legal_Mem);
   switch (CastKind) {
   default:
     Func->setError("Cast type not supported");
diff --git a/tests_lit/llvm2ice_tests/div_legalization.ll b/tests_lit/llvm2ice_tests/div_legalization.ll
new file mode 100644
index 0000000..2088eff
--- /dev/null
+++ b/tests_lit/llvm2ice_tests/div_legalization.ll
@@ -0,0 +1,68 @@
+; This is a regression test that idiv and div operands are legalized
+; (they cannot be constants and can only be reg/mem for x86).
+
+; RUN: %llvm2ice -O2 --verbose none %s | FileCheck %s
+; RUN: %llvm2ice -Om1 --verbose none %s | FileCheck %s
+; RUN: %llvm2ice --verbose none %s | FileCheck --check-prefix=ERRORS %s
+; RUN: %llvm2iceinsts %s | %szdiff %s | FileCheck --check-prefix=DUMP %s
+; RUN: %llvm2iceinsts --pnacl %s | %szdiff %s \
+; RUN:                           | FileCheck --check-prefix=DUMP %s
+
+define i32 @Sdiv_const8_b(i8 %a) {
+; CHECK-LABEL: Sdiv_const8_b
+entry:
+  %div = sdiv i8 %a, 12
+; CHECK: mov {{.*}}, 12
+; CHECK-NOT: idiv 12
+  %div_ext = sext i8 %div to i32
+  ret i32 %div_ext
+}
+
+define i32 @Sdiv_const16_b(i16 %a) {
+; CHECK-LABEL: Sdiv_const16_b
+entry:
+  %div = sdiv i16 %a, 1234
+; CHECK: mov {{.*}}, 1234
+; CHECK-NOT: idiv 1234
+  %div_ext = sext i16 %div to i32
+  ret i32 %div_ext
+}
+
+define i32 @Sdiv_const32_b(i32 %a) {
+; CHECK-LABEL: Sdiv_const32_b
+entry:
+  %div = sdiv i32 %a, 1234
+; CHECK: mov {{.*}}, 1234
+; CHECK-NOT: idiv 1234
+  ret i32 %div
+}
+
+define i32 @Srem_const_b(i32 %a) {
+; CHECK-LABEL: Srem_const_b
+entry:
+  %rem = srem i32 %a, 2345
+; CHECK: mov {{.*}}, 2345
+; CHECK-NOT: idiv 2345
+  ret i32 %rem
+}
+
+define i32 @Udiv_const_b(i32 %a) {
+; CHECK-LABEL: Udiv_const_b
+entry:
+  %div = udiv i32 %a, 3456
+; CHECK: mov {{.*}}, 3456
+; CHECK-NOT: div 3456
+  ret i32 %div
+}
+
+define i32 @Urem_const_b(i32 %a) {
+; CHECK-LABEL: Urem_const_b
+entry:
+  %rem = urem i32 %a, 4567
+; CHECK: mov {{.*}}, 4567
+; CHECK-NOT: div 4567
+  ret i32 %rem
+}
+
+; ERRORS-NOT: ICE translation error
+; DUMP-NOT: SZ