1180874 - Use DivOrModConstantI instead of UDivOrMod for unsigned modulo with constant

Status: RESOLVED DUPLICATE of bug 1182203

(Core :: JavaScript Engine: JIT, defect)

Description

[Sander Mathijs van Veen]

Attachment: unsigned-modulo-with-constant.patch

Prior to the patch in bug 1176864, the 'fasta' benchmark uses the opcodes 'ShiftI:ursh' and 'DivOrModConstantI'. With the int32 truncate patch applied, the opcode 'Integer' and 'UDivOrMod:Truncated' are used. This causes a regression in the fasta benchmark. I suspect that the regression is a result of using the asm instruction 'div', which is expensive given the fact that fasta is doing modulo with a constant.

In 'LIRGeneratorX86Shared::lowerModI' (js/src/jit/x86-shared/Lowering-x86-shared.cpp), the check whether the modulo is unsigned is before the check if the rhs is a constant. Switching the if statements (see attached patch) will let fasta use 'DivOrModConstantI' instead of 'UDivOrMod:Truncated'.

Without the patch:
~~~
test_fasta_float (test_benchmark.benchmark) ...·                                
        clang: mean: 6.549 (+-0.017) secs  median: 6.542  range: 6.525-6.563  (noise: 0.257%)  (3 runs)
           sm: mean: 13.272 (+-0.022) secs  median: 13.264  range: 13.241-13.287  (noise: 0.164%)  (3 runs)   Relative: 2.03 X slower
     sm-noasm: mean: 16.342 (+-0.107) secs  median: 16.266  range: 16.257-16.493  (noise: 0.657%)  (3 runs)   Relative: 2.50 X slower
~~~

With the patch:
~~~
test_fasta_float (test_benchmark.benchmark) ...·                                
        clang: mean: 6.526 (+-0.015) secs  median: 6.515  range: 6.514-6.547  (noise: 0.233%)  (3 runs)
           sm: mean: 9.646 (+-0.020) secs  median: 9.635  range: 9.621-9.669  (noise: 0.205%)  (3 runs)   Relative: 1.48 X slower        
     sm-noasm: mean: 14.342 (+-0.022) secs  median: 14.334  range: 14.311-14.358  (noise: 0.157%)  (3 runs)   Relative: 2.20 X slower
~~~

The benchmark is ran on a machine with an i3 and linux 64-bit OS.

All jit-tests and jstests pass locally. Try build results are pending (currently 67% done): https://treeherder.mozilla.org/#/jobs?repo=try&revision=e7d5f1800c1b

Comment 1

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8630110 [details] [diff] [review]
unsigned-modulo-with-constant.patch

Review of attachment 8630110 [details] [diff] [review]:
-----------------------------------------------------------------

This looks good to me. :)
Do the same for lowerDivI.

Comment 2

[Sander Mathijs van Veen]

Attachment: bug1180874-unsigned-mod-and-div-with-constant.patch

I've changed the if-statements in lowerDivI as well.

Comment 3

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/596ee431b3d2

Comment 4

[Sander Mathijs van Veen]

This patch gave on AWFY Mac 64-bit a 26.8% improvement on asmjs-ubench-fasta (Firefox Ion): http://arewefastyet.com/#machine=29&view=single&suite=asmjs-ubench&subtest=fasta

Can this bug be marked as resolved/fixed?

Comment 5

[Jan de Mooij [:jandem]]

(In reply to Sander Mathijs van Veen from comment #4)
> This patch gave on AWFY Mac 64-bit a 26.8% improvement on asmjs-ubench-fasta
> (Firefox Ion):
> http://arewefastyet.com/#machine=29&view=single&suite=asmjs-
> ubench&subtest=fasta

Wow, thanks!

> Can this bug be marked as resolved/fixed?

That will happen when your patch lands on mozilla-central, likely later today or tomorrow.

Comment 6

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/596ee431b3d2

Comment 7

[Dan Gohman [:sunfish]]

The following testcase:

var asmdiv = (function(m) {
    "use asm"
    function f(x) {
        x = x|0;
        var z = 0;
        z = ((x>>>0) / 2)>>>0;
        return z|0;
    }
    return f;
})()

var plaindiv = function(x) {
    x = x|0;
    var z = 0;
    z = ((x>>>0) / 2)>>>0;
    return z|0;
}

var k = 0xf0000000;

print(asmdiv(k));
print(plaindiv(k));

is now being miscompiled.

Please take a look at the patches in bug 976110 which implement unsigned division by constants.

Comment 8

[Alon Zakai (:azakai)]

I am worried this might break asm.js content for Nightly users, given the testcase in the last comment - any very large unsigned division by a constant looks at risk (I assume "2" is not special)? That type of division very likely happens in large codebases like Unity and Unreal.

Perhaps we should back this out?

Comment 9

[Jan de Mooij [:jandem]]

(In reply to Alon Zakai (:azakai) from comment #8)
> Perhaps we should back this out?

Done:

https://hg.mozilla.org/integration/mozilla-inbound/rev/056d1e36d807

Comment 10

[Hannes Verschore [:h4writer]]

Comment on attachment 8630475 [details] [diff] [review]
bug1180874-unsigned-mod-and-div-with-constant.patch

Review of attachment 8630475 [details] [diff] [review]:
-----------------------------------------------------------------

A few comments about this patch:

1) Moving isUnsigned makes us do int32 division for constants instead of uint32 division for constants. Instead of moving down, we should look into adding constant lowering for lowerUDiv
2) This code only does the transform for our x86/x64 backend, but the arm/mips architectures have the same code and should get adjusted accordingly.

Comment 11

[Nicolas B. Pierron [:nbp]]

This sounds like the only problem is for values which ranges are above or equal to 2^31 unsigned numbers, which is not yet represented by any MIR instruction.

One thing we can do is save a flag on the MIR to claim that we can safely use a signed integer division/modulo to do the same operation.  This would not add to much things to this patch and make it work by just adding a few lines in RangeAnalysis.cpp and MIR.h.

Comment 12

[Ryan VanderMeulen [:RyanVM]]

Does this need to be hidden still now that the patch has been backed out?

Comment 13

[Alon Zakai (:azakai)]

Maybe I'm confused, but this bug and bug 976110 appear to overlap. Should these efforts be joined?

Comment 14

[Benjamin Bouvier [:bbouvier] (inactive)]

Another test case to add here, from bug 1181796:

g = (function() {
    "use asm"
    function f(i0) {
        i0 = i0 | 0
        return ((i0 >>> 32) % 2) | 0
    }
    return f
})()
g(4294967295)

This asserted with --no-threads --ion-eager --ion-check-range-analysis

Comment 15

[Andrew McCreight [:mccr8]]

(In reply to Ryan VanderMeulen [:RyanVM UTC-4] from comment #12)
> Does this need to be hidden still now that the patch has been backed out?

Comment 16

[Dan Gohman [:sunfish]]

We're good now.

Comment 17

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to Jan de Mooij [:jandem] from comment #9)
> (In reply to Alon Zakai (:azakai) from comment #8)
> > Perhaps we should back this out?
> 
> Done:
> 
> https://hg.mozilla.org/integration/mozilla-inbound/rev/056d1e36d807

To be clear, the backout made it to:

44: http://hg.mozilla.org/mozilla-central/rev/056d1e36d807
43: https://hg.mozilla.org/releases/mozilla-aurora/rev/056d1e36d807
42: https://hg.mozilla.org/releases/mozilla-beta/rev/056d1e36d807

and mozilla-release:

https://hg.mozilla.org/releases/mozilla-release/rev/056d1e36d807

Comment 18

[Nicolas B. Pierron [:nbp]]

This got fixed on x86 / x64 with Bug 1182203.