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

src/utils.h

 // 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 67 matching lines @@
     case 4: bits++;  // Fall through.
     case 2: bits++;  // Fall through.
     case 1: break;
   }
   ASSERT_EQ(1 << bits, original_x);
   return bits;
   return 0;
 }
 
 
+// Magic numbers for integer division.
+// These are kind of 2's complement reciprocal of the 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.
+// See details in the implementation of the algorithm in
+// lithium-codegen-arm.cc : LCodeGen::TryEmitSignedIntegerDivisionByConstant().
+struct DivMagicNumbers {
+  unsigned M;
+  unsigned s;
+};
+
+const DivMagicNumbers InvalidDivMagicNumber= {0, 0};
+const DivMagicNumbers DivMagicNumberFor3   = {0x55555556, 0};
+const DivMagicNumbers DivMagicNumberFor5   = {0x66666667, 1};
+const DivMagicNumbers DivMagicNumberFor6   = {0x2aaaaaab, 0};
+const DivMagicNumbers DivMagicNumberFor7   = {0x92492493, 2};
+const DivMagicNumbers DivMagicNumberFor9   = {0x38e38e39, 1};
+const DivMagicNumbers DivMagicNumberFor10  = {0x66666667, 2};
+const DivMagicNumbers DivMagicNumberFor11  = {0x2e8ba2e9, 1};
+const DivMagicNumbers DivMagicNumberFor12  = {0x2aaaaaab, 1};
+const DivMagicNumbers DivMagicNumberFor25  = {0x51eb851f, 3};
+const DivMagicNumbers DivMagicNumberFor125 = {0x10624dd3, 3};
+const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8};
+
+const DivMagicNumbers DivMagicNumberFor(int32_t divisor);
+
+
 // The C++ standard leaves the semantics of '>>' undefined for
 // negative signed operands. Most implementations do the right thing,
 // though.
 inline int ArithmeticShiftRight(int x, int s) {
   return x >> s;
 }
 
 
 // Compute the 0-relative offset of some absolute value x of type T.
 // This allows conversion of Addresses and integral types into
@@ skipping 852 matching lines @@
     ASSERT(element < static_cast<int>(sizeof(T) * CHAR_BIT));
     return 1 << element;
   }
 
   T bits_;
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_UTILS_H_