Closed Bug 1180874 Opened 6 years ago Closed 6 years ago

Use DivOrModConstantI instead of UDivOrMod for unsigned modulo with constant

Categories

(Core :: JavaScript Engine: JIT, defect)

defect
Not set
normal

Tracking

()

RESOLVED DUPLICATE of bug 1182203

People

(Reporter: sandervv, Assigned: sandervv)

References

Details

Attachments

(1 file, 1 obsolete file)

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
Attachment #8630110 - Flags: review?(nicolas.b.pierron)
Attachment #8630110 - Flags: review?(hv1989)
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.
Attachment #8630110 - Flags: review?(nicolas.b.pierron) → review+
Blocks: 1176864
See Also: 1176864
I've changed the if-statements in lowerDivI as well.
Attachment #8630110 - Attachment is obsolete: true
Attachment #8630110 - Flags: review?(hv1989)
Keywords: checkin-needed
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?
(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.
https://hg.mozilla.org/mozilla-central/rev/596ee431b3d2
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla42
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.
Group: javascript-core-security
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?
Assignee: nobody → sandervv
(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
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Target Milestone: mozilla42 → ---
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.
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.
Flags: in-testsuite?
Does this need to be hidden still now that the patch has been backed out?
Maybe I'm confused, but this bug and bug 976110 appear to overlap. Should these efforts be joined?
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
(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?
Flags: needinfo?(sunfish)
We're good now.
Group: javascript-core-security
Flags: needinfo?(sunfish)
This got fixed on x86 / x64 with Bug 1182203.
Status: REOPENED → RESOLVED
Closed: 6 years ago6 years ago
Resolution: --- → DUPLICATE
Duplicate of bug: 1182203
You need to log in before you can comment on or make changes to this bug.