x86/x64 port of Math.floor(x/y) to use integer division for specific divisor

src/ia32/lithium-codegen-ia32.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // 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 1004 matching lines @@
   // Sign extend to edx.
   __ cdq();
   __ idiv(right_reg);
 
   // Deoptimize if remainder is not 0.
   __ test(edx, Operand(edx));
   DeoptimizeIf(not_zero, instr->environment());
 }
 
 
+void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) {
+  ASSERT(instr->InputAt(1)->IsConstantOperand());
+
+  Register dividend = ToRegister(instr->InputAt(0));
+  int32_t divisor = ToInteger32(LConstantOperand::cast(instr->InputAt(1)));
+  Register result = ToRegister(instr->result());
+
+  switch (divisor) {
+  case 0:
+    DeoptimizeIf(no_condition, instr->environment());
+    return;
+
+  case 1:
+    __ Move(result, dividend);
+    return;
+
+  case -1:
+    __ Move(result, dividend);
+    __ neg(result);
+    if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+      DeoptimizeIf(zero, instr->environment());
+    }
+    if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
+      DeoptimizeIf(overflow, instr->environment());
+    }
+    return;
+  }
+
+  uint32_t divisor_abs = abs(divisor);
+  if (IsPowerOf2(divisor_abs)) {
+    int32_t power = WhichPowerOf2(divisor_abs);
+    if (divisor < 0) {
+      // Input[dividend] is clobbered.
+      // The sequence is tedious because neg(dividend) might overflow.

[Yang, 2012/06/20 12:19:42]

I took a second look. Wouldn't we circumvent this problem if we simply divide
first and then negate? We would then observe three distinct cases (if divisor <
0):
- divisor is -1: we can simply do a NEG. Only if divident is kMinInt would NEG
overflow. We guard against this case first and deopt here, since we would
require a double representation for the result anyway (because (-kMinInt) >
kMaxInt). This case has already been dealt with in the switch!
- divisor is -2 or less, and divident is 0: we bail out if kBailoutOnMinusZero
is set, otherwise return 0.
- divisor is -2 or less, and divident is not 0: we calculate
divident/divisor_abs by shifting and set the sign with neg. We don't expect
overflow for neg because divident/divisor_abs cannot be kMinInt.

Did I overlook anything? With this, we don't clobber divident, so it doesn't
have to be reserved with UseTempRegister.

[Zheng Liu, 2012/06/20 13:54:15]

As a floor() op, it's not symmetric around zero.
e.g. Math.floor(1/-4) => -1

+      __ mov(result, dividend);
+      __ sar(dividend, 31);
+      __ neg(result);
+      if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+        DeoptimizeIf(zero, instr->environment());
+      }
+      __ shl(dividend, 32 - power);
+      __ sar(result, power);
+      __ not_(dividend);
+      // Clear result.sign if dividend.sign is set.
+      __ and_(result, dividend);
+    } else {
+      __ Move(result, dividend);
+      __ sar(result, power);
+    }
+  } else {
+    ASSERT(ToRegister(instr->InputAt(0)).is(eax));
+    ASSERT(ToRegister(instr->result()).is(edx));
+    Register scratch = ToRegister(instr->TempAt(0));
+
+    // Find b which: 2^b < divisor_abs < 2^(b+1).
+    unsigned b = 31 - CompilerIntrinsics::CountLeadingZeros(divisor_abs);

[Yang, 2012/06/20 12:19:42]

I assume divisor_abs == divisor here? Maybe use the former here can avoid some
confusions.

[Zheng Liu, 2012/06/20 13:54:15]

Here abs(divisor) is not-power-of-two. divisor could be negative.

+    unsigned shift = 32 + b;  // Precision +1bit (effectively).
+    double multiplier_f =
+        static_cast<double>(static_cast<uint64_t>(1) << shift) / divisor_abs;
+    int64_t multiplier;
+    if (multiplier_f - floor(multiplier_f) < 0.5) {
+        multiplier = floor(multiplier_f);
+    } else {
+        multiplier = floor(multiplier_f) + 1;
+    }
+    // The multiplier is a uint32.
+    ASSERT(multiplier > 0 &&
+           multiplier < (static_cast<int64_t>(1) << 32));
+    __ mov(scratch, dividend);
+    if (divisor < 0 &&
+        instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+      __ test(dividend, dividend);
+      DeoptimizeIf(zero, instr->environment());
+    }
+    __ mov(edx, multiplier);
+    __ imul(edx);
+    if (static_cast<int32_t>(multiplier) < 0) {
+      __ add(edx, scratch);
+    }
+    Register reg_lo = eax;
+    Register reg_byte_scratch = scratch;
+    if (!reg_byte_scratch.is_byte_register()) {
+        __ xchg(reg_lo, reg_byte_scratch);
+        reg_lo = scratch;
+        reg_byte_scratch = eax;
+    }
+    if (divisor < 0) {
+      __ xor_(reg_byte_scratch, reg_byte_scratch);
+      __ cmp(reg_lo, 0x40000000);
+      __ setcc(above, reg_byte_scratch);
+      __ neg(edx);
+      __ sub(edx, reg_byte_scratch);
+    } else {
+      __ xor_(reg_byte_scratch, reg_byte_scratch);
+      __ cmp(reg_lo, 0xC0000000);
+      __ setcc(above_equal, reg_byte_scratch);
+      __ add(edx, reg_byte_scratch);
+    }
+    __ sar(edx, shift - 32);
+  }
+}
+
+
 void LCodeGen::DoMulI(LMulI* instr) {
   Register left = ToRegister(instr->InputAt(0));
   LOperand* right = instr->InputAt(1);
 
   if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
     __ mov(ToRegister(instr->TempAt(0)), left);
   }
 
   if (right->IsConstantOperand()) {
     // Try strength reductions on the multiplication.
@@ skipping 4194 matching lines @@
                               FixedArray::kHeaderSize - kPointerSize));
   __ bind(&done);
 }
 
 
 #undef __
 
 } }  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_IA32