MIPS: Reland "Handle non-power-of-2 divisors in division-like operations".

src/mips/lithium-codegen-mips.cc

 // Copyright 2012 the V8 project authors. All rights reserved.7
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1114 matching lines @@
   __ Branch(USE_DELAY_SLOT, &done, ge, left_reg, Operand(zero_reg));
   __ mfhi(result_reg);
 
   if (hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
     DeoptimizeIf(eq, instr->environment(), result_reg, Operand(zero_reg));
   }
   __ bind(&done);
 }
 
 
-void LCodeGen::EmitSignedIntegerDivisionByConstant(
-    Register result,
-    Register dividend,
-    int32_t divisor,
-    Register remainder,
-    Register scratch,
-    LEnvironment* environment) {
-  ASSERT(!AreAliased(dividend, scratch, at, no_reg));
-
-  uint32_t divisor_abs = abs(divisor);
-
-  int32_t power_of_2_factor =
-    CompilerIntrinsics::CountTrailingZeros(divisor_abs);
-
-  switch (divisor_abs) {
-    case 0:
-      DeoptimizeIf(al, environment);
-      return;
-
-    case 1:
-      if (divisor > 0) {
-        __ Move(result, dividend);
-      } else {
-        __ SubuAndCheckForOverflow(result, zero_reg, dividend, scratch);
-        DeoptimizeIf(lt, environment, scratch, Operand(zero_reg));
-      }
-      // Compute the remainder.
-      __ Move(remainder, zero_reg);
-      return;
-
-    default:
-      if (IsPowerOf2(divisor_abs)) {
-        // Branch and condition free code for integer division by a power
-        // of two.
-        int32_t power = WhichPowerOf2(divisor_abs);
-        if (power > 1) {
-          __ sra(scratch, dividend, power - 1);
-        }
-        __ srl(scratch, scratch, 32 - power);
-        __ Addu(scratch, dividend, Operand(scratch));
-        __ sra(result, scratch,  power);
-        // Negate if necessary.
-        // We don't need to check for overflow because the case '-1' is
-        // handled separately.
-        if (divisor < 0) {
-          ASSERT(divisor != -1);
-          __ Subu(result, zero_reg, Operand(result));
-        }
-        // Compute the remainder.
-        if (divisor > 0) {
-          __ sll(scratch, result, power);
-          __ Subu(remainder, dividend, Operand(scratch));
-        } else {
-          __ sll(scratch, result, power);
-          __ Addu(remainder, dividend, Operand(scratch));
-        }
-        return;
-      } else if (LChunkBuilder::HasMagicNumberForDivisor(divisor)) {
-        // Use magic numbers for a few specific divisors.
-        // Details and proofs can be found in:
-        // - Hacker's Delight, Henry S. Warren, Jr.
-        // - The PowerPC Compiler Writer's Guide
-        // and probably many others.
-        //
-        // We handle
-        //   <divisor with magic numbers> * <power of 2>
-        // but not
-        //   <divisor with magic numbers> * <other divisor with magic numbers>
-        DivMagicNumbers magic_numbers =
-          DivMagicNumberFor(divisor_abs >> power_of_2_factor);
-        // Branch and condition free code for integer division by a power
-        // of two.
-        const int32_t M = magic_numbers.M;
-        const int32_t s = magic_numbers.s + power_of_2_factor;
-
-        __ li(scratch, Operand(M));
-        __ mult(dividend, scratch);
-        __ mfhi(scratch);
-        if (M < 0) {
-          __ Addu(scratch, scratch, Operand(dividend));
-        }
-        if (s > 0) {
-          __ sra(scratch, scratch, s);
-          __ mov(scratch, scratch);
-        }
-        __ srl(at, dividend, 31);
-        __ Addu(result, scratch, Operand(at));
-        if (divisor < 0) __ Subu(result, zero_reg, Operand(result));
-        // Compute the remainder.
-        __ li(scratch, Operand(divisor));
-        __ Mul(scratch, result, Operand(scratch));
-        __ Subu(remainder, dividend, Operand(scratch));
-      } else {
-        __ li(scratch, Operand(divisor));
-        __ div(dividend, scratch);
-        __ mfhi(remainder);
-        __ mflo(result);
-      }
-  }
-}
-
-
 void LCodeGen::DoDivI(LDivI* instr) {
   const Register left = ToRegister(instr->left());
   const Register right = ToRegister(instr->right());
   const Register result = ToRegister(instr->result());
 
   // On MIPS div is asynchronous - it will run in the background while we
   // check for special cases.
   __ div(left, right);
 
   // Check for x / 0.
@@ skipping 30 matching lines @@
   DoubleRegister multiplier = ToDoubleRegister(instr->multiplier());
   DoubleRegister multiplicand = ToDoubleRegister(instr->multiplicand());
 
   // This is computed in-place.
   ASSERT(addend.is(ToDoubleRegister(instr->result())));
 
   __ madd_d(addend, addend, multiplier, multiplicand);
 }
 
 
+void LCodeGen::DoFlooringDivByPowerOf2I(LFlooringDivByPowerOf2I* instr) {
+  Register dividend = ToRegister(instr->dividend());
+  int32_t divisor = instr->divisor();
+  ASSERT(dividend.is(ToRegister(instr->result())));
+  Register scratch = scratch0();
+
+  // If the divisor is positive, things are easy: There can be no deopts and we
+  // can simply do an arithmetic right shift.
+  if (divisor == 1) return;
+  uint16_t shift = WhichPowerOf2Abs(divisor);
+  if (divisor > 1) {
+    __ sra(dividend, dividend, shift);
+    return;
+  }
+
+  // If the divisor is negative, we have to negate and handle edge cases.
+  Label not_kmin_int, done;
+  __ Subu(scratch, zero_reg, dividend);
+  if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+    DeoptimizeIf(eq, instr->environment(), scratch, Operand(zero_reg));
+  }
+  if (instr->hydrogen()->left()->RangeCanInclude(kMinInt)) {
+    // Note that we could emit branch-free code, but that would need one more
+    // register.
+    __ Branch(&not_kmin_int, ne, dividend, Operand(kMinInt));
+    if (divisor == -1) {
+      DeoptimizeIf(al, instr->environment());
+    } else {
+      __ li(dividend, Operand(kMinInt / divisor));
+      __ Branch(&done);
+    }
+  }
+  __ bind(&not_kmin_int);
+  __ sra(dividend, scratch, shift);
+  __ bind(&done);
+}
+
+
 void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) {
-  Register left = ToRegister(instr->dividend());
-  Register remainder = ToRegister(instr->temp());
-  Register scratch = scratch0();
+  Register dividend = ToRegister(instr->dividend());
+  int32_t divisor = instr->divisor();
   Register result = ToRegister(instr->result());
+  ASSERT(!dividend.is(result));
 
-  ASSERT(instr->divisor()->IsConstantOperand());
-  Label done;
-  int32_t divisor = ToInteger32(LConstantOperand::cast(instr->divisor()));
-  if (divisor < 0) {
-    DeoptimizeIf(eq, instr->environment(), left, Operand(zero_reg));
+  if (divisor == 0) {
+    DeoptimizeIf(al, instr->environment());
+    return;
   }
-  EmitSignedIntegerDivisionByConstant(result,
-                                      left,
-                                      divisor,
-                                      remainder,
-                                      scratch,
-                                      instr->environment());
-  // We performed a truncating division. Correct the result if necessary.
-  __ Branch(&done, eq, remainder, Operand(zero_reg), USE_DELAY_SLOT);
-  __ Xor(scratch , remainder, Operand(divisor));
-  __ Branch(&done, ge, scratch, Operand(zero_reg));
-  __ Subu(result, result, Operand(1));
-  __ bind(&done);
+
+  // Check for (0 / -x) that will produce negative zero.
+  HMathFloorOfDiv* hdiv = instr->hydrogen();
+  if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) &&
+      hdiv->left()->RangeCanInclude(0) && divisor < 0) {
+    DeoptimizeIf(eq, instr->environment(), dividend, Operand(zero_reg));
+  }
+
+  __ FlooringDiv(result, dividend, divisor);
 }
 
 
 void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) {
   const Register result = ToRegister(instr->result());
   const Register left = ToRegister(instr->left());
   const Register remainder = ToRegister(instr->temp());
   const Register scratch = scratch0();
 
   Label done;
@@ skipping 4464 matching lines @@
   __ Subu(scratch, result, scratch);
   __ lw(result, FieldMemOperand(scratch,
                                 FixedArray::kHeaderSize - kPointerSize));
   __ bind(&done);
 }
 
 
 #undef __
 
 } }  // namespace v8::internal