From 37f33a7087db7c1befb8ddeebcaed7d0f0c7efe2 Mon Sep 17 00:00:00 2001
From: "sgjesse@chromium.org"
 <sgjesse@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Thu, 28 Apr 2011 14:58:45 +0000
Subject: [PATCH] Improve modulo operation in lithium on IA32. Implement fast
 paths for the special cases like PowerOfTwo divisors and the dividend being
 smaller than the divisor (non-negative).

BUG=v8:1314

Review URL: http://codereview.chromium.org//6816049

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7704 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 AUTHORS                          |  1 +
 src/ia32/lithium-codegen-ia32.cc | 61 ++++++++++++++++++++++++++++----
 2 files changed, 55 insertions(+), 7 deletions(-)

diff --git a/AUTHORS b/AUTHORS
index 843d1d2a0..57b155fa6 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -39,4 +39,5 @@ Ryan Dahl <coldredlemur@gmail.com>
 Sanjoy Das <sanjoy@playingwithpointers.com>
 Subrato K De <subratokde@codeaurora.org>
 Vlad Burlik <vladbph@gmail.com>
+Yuqiang Xian <yuqiang.xian@intel.com>
 Zaheer Ahmad <zahmad@codeaurora.org>
diff --git a/src/ia32/lithium-codegen-ia32.cc b/src/ia32/lithium-codegen-ia32.cc
index 9e636f752..07ee7d62d 100644
--- a/src/ia32/lithium-codegen-ia32.cc
+++ b/src/ia32/lithium-codegen-ia32.cc
@@ -799,20 +799,61 @@ void LCodeGen::DoModI(LModI* instr) {
     __ and_(dividend, divisor - 1);
     __ bind(&done);
   } else {
-    LOperand* right = instr->InputAt(1);
-    ASSERT(ToRegister(instr->InputAt(0)).is(eax));
-    ASSERT(ToRegister(instr->result()).is(edx));
+    NearLabel done, remainder_eq_dividend, slow, do_subtraction, both_positive;
+    Register left_reg = ToRegister(instr->InputAt(0));
+    Register right_reg = ToRegister(instr->InputAt(1));
+    Register result_reg = ToRegister(instr->result());
 
-    Register right_reg = ToRegister(right);
+    ASSERT(left_reg.is(eax));
+    ASSERT(result_reg.is(edx));
     ASSERT(!right_reg.is(eax));
     ASSERT(!right_reg.is(edx));
 
     // Check for x % 0.
     if (instr->hydrogen()->CheckFlag(HValue::kCanBeDivByZero)) {
-      __ test(right_reg, ToOperand(right));
+      __ test(right_reg, Operand(right_reg));
       DeoptimizeIf(zero, instr->environment());
     }
 
+    __ test(left_reg, Operand(left_reg));
+    __ j(zero, &remainder_eq_dividend);
+    __ j(sign, &slow);
+
+    __ test(right_reg, Operand(right_reg));
+    __ j(not_sign, &both_positive);
+    // The sign of the divisor doesn't matter.
+    __ neg(right_reg);
+
+    __ bind(&both_positive);
+    // If the dividend is smaller than the nonnegative
+    // divisor, the dividend is the result.
+    __ cmp(left_reg, Operand(right_reg));
+    __ j(less, &remainder_eq_dividend);
+
+    // Check if the divisor is a PowerOfTwo integer.
+    Register scratch = ToRegister(instr->TempAt(0));
+    __ mov(scratch, right_reg);
+    __ sub(Operand(scratch), Immediate(1));
+    __ test(scratch, Operand(right_reg));
+    __ j(not_zero, &do_subtraction);
+    __ and_(left_reg, Operand(scratch));
+    __ jmp(&remainder_eq_dividend);
+
+    __ bind(&do_subtraction);
+    const int kUnfolds = 3;
+    // Try a few subtractions of the dividend.
+    __ mov(scratch, left_reg);
+    for (int i = 0; i < kUnfolds; i++) {
+      // Reduce the dividend by the divisor.
+      __ sub(left_reg, Operand(right_reg));
+      // Check if the dividend is less than the divisor.
+      __ cmp(left_reg, Operand(right_reg));
+      __ j(less, &remainder_eq_dividend);
+    }
+    __ mov(left_reg, scratch);
+
+    // Slow case, using idiv instruction.
+    __ bind(&slow);
     // Sign extend to edx.
     __ cdq();
 
@@ -820,12 +861,12 @@ void LCodeGen::DoModI(LModI* instr) {
     if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
       NearLabel positive_left;
       NearLabel done;
-      __ test(eax, Operand(eax));
+      __ test(left_reg, Operand(left_reg));
       __ j(not_sign, &positive_left);
       __ idiv(right_reg);
 
       // Test the remainder for 0, because then the result would be -0.
-      __ test(edx, Operand(edx));
+      __ test(result_reg, Operand(result_reg));
       __ j(not_zero, &done);
 
       DeoptimizeIf(no_condition, instr->environment());
@@ -835,6 +876,12 @@ void LCodeGen::DoModI(LModI* instr) {
     } else {
       __ idiv(right_reg);
     }
+    __ jmp(&done);
+
+    __ bind(&remainder_eq_dividend);
+    __ mov(result_reg, left_reg);
+
+    __ bind(&done);
   }
 }
 
-- 
2.34.1