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

src/utils.h

Index: src/utils.h
===================================================================
--- src/utils.h	(revision 11193)
+++ src/utils.h	(working copy)
@@ -85,6 +85,35 @@
 }
 
 
+// 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};

[alexeif, 2012/04/17 16:59:28]

How about adding 60, 100 and 1000? They seem to have even higher rate than 625.

[Alexandre, 2012/04/17 17:12:22]

We can generate optimized code for numbers with an absolute value equals that is
representable by
 <1, or k for which we have a magic number> * 2^n
So optimized code can be generated for these:
60 = 15 * 2^2
100 = 25 * 2^2
1000 = 125 * 2^3

This is detailed in the arm files.

On 2012/04/17 16:59:28, alexeif wrote:

[alexeif, 2012/04/17 18:30:26]

Oh, I see, it has a shift anyway. Btw, why do you need constants for evens 6 and
10?

[Alexandre, 2012/04/18 09:03:59]

Fair question! I actually noticed a non-optimal pattern in the patch (1
instruction difference). Details below.
Since there were a couple of other comments I'll fix that and upload a new
patch.

Optimized code for the pattern
  <k  for which we have a magic number> * 2^n
can require a bit more code (1 instr on ARM) than for
  <k for which we have a magic number>

Using magic numbers for 6 spares one instruction compare to using those for 3
plus the code for the factor 2.
For 10 it does not make a difference here.

And actually, my implementation is non-optimal if divisor == 6...
I first search for the greatest power of 2 dividing the divisor, and check if we
have magic numbers for the odd part.
That means the pattern '3 * 2' is used. One instruction less efficient :(

On 2012/04/17 18:30:26, alexeif wrote:

+
+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.