1564942 - Optimise MPow for Int32 values

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement, P1)

Description

[André Bargull [:anba]]

MPow with an Int32 base-operand (and an Int32 power-operand) is implemented as MToNumberInt32(MPow(MToDouble(int32), int32)) which makes it slower than an exponentiation with a Double base-operand. That means implementing Int32 specialisations for JSOP_POW (bug 1188079) will currently lead to a performance degradation, because JSOP_POW currently always uses the Double base-operand version.

Example:

function f() {
    // Math.pow(int, int) -> int: 580ms
    // Math.pow(double, int) -> double: 435ms

    // With patches:
    // Math.pow(int, int) -> int: 340ms

    // For comparison:
    // int**int -> int: 450ms
    // double**int -> double: 435ms

    // Int32 operand.
    // var xs = [2, 2];

    // Double operand.
    var xs = [2.1, 2.1];

    var ys = [3, 3];

    var q = 0;
    var t = dateNow();
    for (var i = 0; i < 50000000; ++i) {
        var x = xs[i & 1];
        var y = ys[i & 1];
        // q += x ** y;
        q += Math.pow(x, y);
    }
    print(dateNow() - t, q);
}

Comment 1

[André Bargull [:anba]]

Attachment: Bug 1564942 - Part 1: Add braces to if-statements in MPow. r=jandem!

Comment 2

[André Bargull [:anba]]

Attachment: Bug 1564942 - Part 2: Avoid negative zero check when the base operand in MPow is an Int32. r=jandem!

That way the trailing DoubleToInt32 doesn't emit the negative zero check sequence:

movq       %xmm0, %rax
cmpq       $0x1, %rax
jo         .Lfrom0000

Depends on D37583

Comment 3

[André Bargull [:anba]]

Attachment: Bug 1564942 - Part 3: Compute MPow for Int32 values directly on Int32 operands. r=jandem!

Instead of computing pow(int32, int32) -> int32 as MToNumberInt32(MPow(MToDouble(int32), int32))
directly exponentiate both operands in the Int32 space by adding LPowII which inlines
js::powi(double, int).

When MPow is used with a constant power which can be folded to MMul, this change will lead to
better codegen, too. For example Math.pow(x, 2) where x is an Int32 value, currently generates
the following assembly:

# instruction Int32ToDouble
xorpd      %xmm0, %xmm0
cvtsi2sd   %eax, %xmm0
# instruction MathD:mul
mulsd      %xmm0, %xmm0
# instruction DoubleToInt32
cvttsd2si  %xmm0, %eax
xorpd      %xmm15, %xmm15
cvtsi2sd   %eax, %xmm15
ucomisd    %xmm15, %xmm0
jp         .Lfrom0000
jne        .Lfrom0000

With this patch, this assembly will be generated:

# instruction MoveGroup
movl       %eax, %ecx
# instruction MulI
imull      %ecx, %eax
jo         .Lfrom0000

Depends on D37584

Comment 4

[André Bargull [:anba]]

Attachment: Bug 1564942 - Part 3: Avoid an extra `mov` when multiplying an operand with itself. r=jandem!

Similar to LIRGeneratorX86Shared::lowerForALU, try to use the same register when multiplying an
operand with itself.

This change improves the generated assembly for Math.pow(x, 2) from:

# instruction MoveGroup
movl       %eax, %ecx
# instruction MulI
imull      %ecx, %eax
jo         .Lfrom0000

to:

# instruction MulI
imull      %eax, %eax
jo         .Lfrom0000

Depends on D37585

Comment 5

[André Bargull [:anba]]

Attachment: Bug 1564942 - Part 4: Lower MPow to a series of shift-instructions when the base operand is a power of two. r=jandem!

In-tree users of Math.pow show that the function is often called with the base operand equal to
two. This case can easily be optimised to a series of shift-instructions for any power of two. For
now this optimisation is only taken for 2^i with i in {1..8} to avoid generating too many
consecutive shift-instructions. 2^8 = 256 was chosen as the limit, because it is the maximum power
of two base operand for Math.pow used in-tree.

Depends on D37586

Comment 6

[Cristian Brindusan [:cbrindusan]]

Landing of part 1 and 2 failed due to:

"applying /tmp/tmp1iTtSV
js/src/jit/MIR.cpp
Hunk #1 FAILED at 3003.
Hunk #2 FAILED at 3014.
2 out of 3 hunks FAILED -- saving rejects to file js/src/jit/MIR.cpp.rej"

:anba can you please take a look?

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/0017d61a5a0f
Part 1: Add braces to if-statements in MPow. r=jandem
https://hg.mozilla.org/integration/autoland/rev/91d3f5dc57c9
Part 2: Avoid negative zero check when the base operand in MPow is an Int32. r=jandem
https://hg.mozilla.org/integration/autoland/rev/cee3bb013291
Part 3: Avoid an extra `mov` when multiplying an operand with itself. r=jandem
https://hg.mozilla.org/integration/autoland/rev/ed869f61d924
Part 4: Lower MPow to a series of shift-instructions when the base operand is a power of two. r=jandem

Comment 8

[Noemi Erli[:noemi_erli]]

Backed out 4 changesets (Bug 1564942) for causing SM bustage in pow-base-power-of-two.js CLOSED TREE

Push with failures: https://treeherder.mozilla.org/#/jobs?repo=autoland&group_state=expanded&resultStatus=testfailed%2Cbusted%2Cexception&revision=ed869f61d92437944115e25abe6deecd2d4ce07a&selectedTaskRun=fBtjlMlyS5q2SF5XB5r81A-0

Failure log: https://treeherder.mozilla.org/logviewer.html#/jobs?job_id=305661284&repo=autoland&lineNumber=36022

Backout: https://hg.mozilla.org/integration/autoland/rev/b2df79a80c0303df9d710800ae37dce56847eef5

Comment 9

[André Bargull [:anba]]

std::pow is off by one ULP on Windows, which needs to be taken into account for the test case...

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/5b9343de266b
Part 1: Add braces to if-statements in MPow. r=jandem
https://hg.mozilla.org/integration/autoland/rev/bfc836af8677
Part 2: Avoid negative zero check when the base operand in MPow is an Int32. r=jandem
https://hg.mozilla.org/integration/autoland/rev/7765391a4142
Part 3: Avoid an extra `mov` when multiplying an operand with itself. r=jandem
https://hg.mozilla.org/integration/autoland/rev/796d8685f8ce
Part 4: Lower MPow to a series of shift-instructions when the base operand is a power of two. r=jandem

Comment 11

[Bogdan Tara[:bogdan_tara | bogdant]]

https://hg.mozilla.org/mozilla-central/rev/5b9343de266b
https://hg.mozilla.org/mozilla-central/rev/bfc836af8677
https://hg.mozilla.org/mozilla-central/rev/7765391a4142
https://hg.mozilla.org/mozilla-central/rev/796d8685f8ce