[v8-dev] Optimise Math.floor(x/y) to use integer division for specific divisor....

src/arm/lithium-arm.cc

Index: src/arm/lithium-arm.cc
===================================================================
--- src/arm/lithium-arm.cc	(revision 11193)
+++ src/arm/lithium-arm.cc	(working copy)
@@ -1319,6 +1319,79 @@
 }
 
 
+bool LChunkBuilder::HasMagicNumberForDivisor(int32_t divisor) {
+  uint32_t divisor_abs = abs(divisor);
+  // Dividing by 0, 1, and powers of 2 is easy.
+  // Note that IsPowerOf2(0) returns true;
+  ASSERT(IsPowerOf2(0) == true);
+  if (IsPowerOf2(divisor_abs)) return true;
+
+  // We have 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>
+  int32_t power_of_2_factor =
+    CompilerIntrinsics::CountTrailingZeros(divisor_abs);
+  DivMagicNumbers magic_numbers =
+    DivMagicNumberFor(divisor_abs >> power_of_2_factor);
+  if (magic_numbers.M != InvalidDivMagicNumber.M) return true;
+
+  return false;
+}
+
+
+HValue* LChunkBuilder::SimplifiedDividendForMathFloorOfDiv(HValue* dividend) {
+  // A change from an integer32 can be replaced by the integer32 value.
+  if (dividend->IsChange() &&
+      HChange::cast(dividend)->from().IsInteger32()) {
+    return HChange::cast(dividend)->value();
+  }
+  // Change representation to integer32 if the constant can be represented as an
+  // integer32 value.
+  if (dividend->IsConstant() &&
+      HConstant::cast(dividend)->HasInteger32Value()) {

[fschneider, 2012/04/17 07:41:10]

This would only occur is in Math.floor(a/b) both a and b are constants. In this
case the division would be folded already, right? So you can probably leave out
this case here.

[Alexandre, 2012/04/17 10:01:50]

In short: yes we should remove it.

Long:
Divisions are folded at hydrogen generation time.
From what I remember I found out when testing that in rare cases later
optimizations stages could yield this case again. 
In a previous patch not handling this case would raised an error. Now we would
just miss an optimization if we don't handle it.
I ran the tests quickly and did not see this situation occuring any more. So it
seems we should really remove it.


On 2012/04/17 07:41:10, fschneider wrote:

+    return HConstant::cast(dividend)->CopyToRepresentation(
+        Representation::Integer32());
+  }
+  return NULL;
+}
+
+
+HValue* LChunkBuilder::SimplifiedDivisorForMathFloorOfDiv(HValue* divisor) {
+  // Only optimize when we have magic numbers for the divisor.
+  // The standard integer division routine is usually slower than transitionning
+  // to VFP.
+  if (divisor->IsConstant() &&
+      HConstant::cast(divisor)->HasInteger32Value()) {
+    HConstant* constant_val = HConstant::cast(divisor);
+    int32_t int32_val = constant_val->Integer32Value();
+    if (LChunkBuilder::HasMagicNumberForDivisor(int32_val)) {
+      return constant_val->CopyToRepresentation(Representation::Integer32());
+    }
+  }
+  return NULL;
+}
+
+
+LInstruction* LChunkBuilder::DoMathFloorOfDiv(HMathFloorOfDiv* instr) {
+    HValue* right = instr->right();
+    LOperand* dividend = UseRegister(instr->left());
+    LOperand* divisor = UseRegisterOrConstant(right);
+    LOperand* remainder = TempRegister();
+    ASSERT(right->IsConstant() &&
+           HConstant::cast(right)->HasInteger32Value() &&
+           HasMagicNumberForDivisor(HConstant::cast(right)->Integer32Value()));
+    return AssignEnvironment(DefineAsRegister(
+          new LMathFloorOfDiv(dividend, divisor, remainder)));
+}
+
+
 LInstruction* LChunkBuilder::DoMod(HMod* instr) {
   if (instr->representation().IsInteger32()) {
     ASSERT(instr->left()->representation().IsInteger32());