Bug 94779 – To reduce cost of converting type during modulo for integers

• Status: UNCONFIRMED
• Component: JavaScriptCore

[Hojong Han]

It's not necessary for remainder to convert type if both dividend and divisor are integers.
One thing to consider is whether the divisor is zero or not.

[Hojong Han]

Created attachment 160089 [details]
Patch

[Geoffrey Garen]

Comment on attachment 160089 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=160089&action=review

> Source/JavaScriptCore/dfg/DFGOperations.h:183
>  double DFG_OPERATION operationFModOnInts(int32_t, int32_t) WTF_INTERNAL;

You should remove this function, since you're replacing it.

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2545
> +    speculationCheck(Overflow, JSValueRegs(), NoNode, checkZero);

Did you verify what happens in the recovery path when this speculation fails?

[Hojong Han]

Thanks Geoffrey

(In reply to comment #2)
> (From update of attachment 160089 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=160089&action=review
> 
> > Source/JavaScriptCore/dfg/DFGOperations.h:183
> >  double DFG_OPERATION operationFModOnInts(int32_t, int32_t) WTF_INTERNAL;
> 
> You should remove this function, since you're replacing it.
> 
> > Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2545
> > +    speculationCheck(Overflow, JSValueRegs(), NoNode, checkZero);
> 
> Did you verify what happens in the recovery path when this speculation fails?
Could let me know more specific what "this speculation fails" means?
Do you intend to mention about speculationCheck() itself or checking speculation of the divisor?

[Filip Pizlo]

Comment on attachment 160089 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=160089&action=review

This patch will cause a regression on fast/js/integer-division-neg2tothe32-by-neg1.html.  Did you run that test?

Please make sure your code covers all of the corner cases where integer division fails, rather than just the obvious one (zero denominator).

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2539
> +    JITCompiler::Jump checkZero = m_jit.branch32(JITCompiler::Equal, op2GPR, TrustedImm32(0));

Why are you doing it this way?  Why not m_jit.branchTest32(JITCompiler::Zero, op2GPR)?

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2545
>> +    speculationCheck(Overflow, JSValueRegs(), NoNode, checkZero);
> 
> Did you verify what happens in the recovery path when this speculation fails?

This is completely wrong.  Why are you emitting a speculationCheck *after* the call?  The speculationCheck() should be exactly where the branch is.  Please hoist this up to the checkZero, above.

[Filip Pizlo]

(In reply to comment #3)
> Thanks Geoffrey
> 
> (In reply to comment #2)
> > (From update of attachment 160089 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=160089&action=review
> > 
> > > Source/JavaScriptCore/dfg/DFGOperations.h:183
> > >  double DFG_OPERATION operationFModOnInts(int32_t, int32_t) WTF_INTERNAL;
> > 
> > You should remove this function, since you're replacing it.
> > 
> > > Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2545
> > > +    speculationCheck(Overflow, JSValueRegs(), NoNode, checkZero);
> > 
> > Did you verify what happens in the recovery path when this speculation fails?
> Could let me know more specific what "this speculation fails" means?
> Do you intend to mention about speculationCheck() itself or checking speculation of the divisor?

I think he means both.  It appears that you have not tested this case.  I think that just running layout tests should be enough - we should have excellent coverage over corner cases of integer modulo.

That said, your code will pretty obviously cause badness (the speculationCheck() is invoked in the wrong place, and you're only checking for one of the corner cases, not all of them) so if layout tests do pass by some fluke, then you should add a new layout test or file a bug against Tools/Tests for the test to be improved.

[Hojong Han]

(In reply to comment #5)
> I think he means both.  It appears that you have not tested this case.  I think that just running layout tests should be enough - we should have excellent coverage over corner cases of integer modulo.
> 
> That said, your code will pretty obviously cause badness (the speculationCheck() is invoked in the wrong place, and you're only checking for one of the corner cases, not all of them) so if layout tests do pass by some fluke, then you should add a new layout test or file a bug against Tools/Tests for the test to be improved.

Thanks for advice, Filip

I just ran script "run-fast-jsc" because I thought it was enough to cover the corner cases as you explained. now I can find that some tests are missing such as  "fast/js/integer-division-neg2tothe32-by-neg1", etc on jsc-test-list.

[Hojong Han]

(In reply to comment #4)
> This is completely wrong.  Why are you emitting a speculationCheck *after* the call?  The speculationCheck() should be exactly where the branch is.  Please hoist this up to the checkZero, above.

Quick question!!
What's the role of speculationCheck? 
It just links branches to OSRExit as I understood so that I thought it doesn't matter whether speculationCheck is emitted after the call or before.
What's the expected badness if speculationCheck is emitted after the call?

Thanks for your guide in advance.

[Filip Pizlo]

(In reply to comment #7)
> (In reply to comment #4)
> > This is completely wrong.  Why are you emitting a speculationCheck *after* the call?  The speculationCheck() should be exactly where the branch is.  Please hoist this up to the checkZero, above.
> 
> Quick question!!
> What's the role of speculationCheck? 

It links the branch to the OSR exit.

> It just links branches to OSRExit as I understood so that I thought it doesn't matter whether speculationCheck is emitted after the call or before.

You're forgetting about register allocation.

> What's the expected badness if speculationCheck is emitted after the call?

In your case, you're calling flushRegisters() after emitting the speculation branch, but before calling speculationCheck().  So, the OSR exit offramp will think that all registers were flushed at the branch that is linked to it.

In general, you don't want to do:

Jump jump = m_jit.branch(...);
speculationCheck(..., jump);

If you can just do:

speculationCheck(..., m_jit.branch(...));

The latter is almost always guaranteed to work, while the former will start to become increasingly risky as you start putting things between the call to m_jit.branch and the speculationCheck().

[Hojong Han]

Created attachment 160691 [details]
Patch

[Hojong Han]

(In reply to comment #8)
Filip, could you take a look into my patch?

I didn't get any regression and it gives me better score at mathPrimes in BrowserMark.

[Filip Pizlo]

Comment on attachment 160691 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=160691&action=review

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2554
> +    callOperation(operationModOnInts, result.gpr(), op1GPR, op2GPR);

Have you tested -2^31%-1

[Hojong Han]

(In reply to comment #11)
> (From update of attachment 160691 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=160691&action=review
> 
> > Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2554
> > +    callOperation(operationModOnInts, result.gpr(), op1GPR, op2GPR);
> 
> Have you tested -2^31%-1

That case is included in integer-division-neg2tothe32-by-neg1.js as I know.
I ran that case with loop count greater than 1000 to make sure going though DFG.

[Filip Pizlo]

(In reply to comment #12)
> (In reply to comment #11)
> > (From update of attachment 160691 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=160691&action=review
> > 
> > > Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:2554
> > > +    callOperation(operationModOnInts, result.gpr(), op1GPR, op2GPR);
> > 
> > Have you tested -2^31%-1
> 
> That case is included in integer-division-neg2tothe32-by-neg1.js as I know.
> I ran that case with loop count greater than 1000 to make sure going though DFG.

Here's my concern: the C operation a%b where a is -2^31 and b is -1 has undefined behavior AFAIK. Your patch doesn't prevent that case from executing.

[Filip Pizlo]

Created attachment 164488 [details]
test case for C modulo

Run this on your compute:

cc -o test test.c
./test -2147483648 -1

You should get a SIGFPE on UNIX-like systems, or whatever the equivalent exception is on non-UNIX systems.

In general it is not safe to use C modulo for -2147483648/-1.

The reason why that code was written to call fmod() instead of using C modulo in the first place, was to ensure that we avoided this corner case.

While I appreciate that there are things that can be done to optimize this code path, I don't think you have done so in a safe way.

[Filip Pizlo]

Comment on attachment 160691 [details]
Patch

r- because you're not being careful enough with corner cases.

[Hojong Han]

(In reply to comment #14)
Really thank you for your review and comment, Filip

> Created an attachment (id=164488) [details]
> test case for C modulo
> 
> Run this on your compute:
> 
> cc -o test test.c
> ./test -2147483648 -1
> 
> You should get a SIGFPE on UNIX-like systems, or whatever the equivalent exception is on non-UNIX systems.
> 
> In general it is not safe to use C modulo for -2147483648/-1.

I did concern what you tested but my device, on linux, didn't throw any signal so I didn't add speculationCheck for (-2147483648).
Plus score was not good if the patch had have that check routine.

> 
> The reason why that code was written to call fmod() instead of using C modulo in the first place, was to ensure that we avoided this corner case.

During making this patch, I totally understood the reason why fmod() is called even if the cost is more expensive.

> 
> While I appreciate that there are things that can be done to optimize this code path, I don't think you have done so in a safe way.

I'm going to supplement the patch. Your interest will be necessary again.
Thanks again~

[Filip Pizlo]

(In reply to comment #16)
> (In reply to comment #14)
> Really thank you for your review and comment, Filip
> 
> > Created an attachment (id=164488) [details] [details]
> > test case for C modulo
> > 
> > Run this on your compute:
> > 
> > cc -o test test.c
> > ./test -2147483648 -1
> > 
> > You should get a SIGFPE on UNIX-like systems, or whatever the equivalent exception is on non-UNIX systems.
> > 
> > In general it is not safe to use C modulo for -2147483648/-1.
> 
> I did concern what you tested but my device, on linux, didn't throw any signal so I didn't add speculationCheck for (-2147483648).
> Plus score was not good if the patch had have that check routine.

I prefer a browser that doesn't crash over a browser that computes prime numbers quickly.

[Hojong Han]

(In reply to comment #17)
> (In reply to comment #16)
> I prefer a browser that doesn't crash over a browser that computes prime numbers quickly.

I totally agree with your thought. I'm appreciated for your comment.

[Hojong Han]

(In reply to comment #18)
> (In reply to comment #17)
> > (In reply to comment #16)
> > I prefer a browser that doesn't crash over a browser that computes prime numbers quickly.
> 
> I totally agree with your thought. I'm appreciated for your comment.

I figured out why the crash didn't occur on my device. That's because of the compile optimization level.

[Filip Pizlo]

(In reply to comment #19)
> (In reply to comment #18)
> > (In reply to comment #17)
> > > (In reply to comment #16)
> > > I prefer a browser that doesn't crash over a browser that computes prime numbers quickly.
> > 
> > I totally agree with your thought. I'm appreciated for your comment.
> 
> I figured out why the crash didn't occur on my device. That's because of the compile optimization level.

I'm curious about this.  Can you share more details?

For me, here's what I see:

If I make it obvious to my compiler (clang+llvm) what the constants are in the modulo operation, like so:

int a = -2147483647 - 1;
int b = -1;
return a % b; // a and b are known constants

Then I only crash when optimizations are disabled.  With optimizations, I do get a garbage result, however.

But if I make it non-obvious, such as in my test program that I attached, by virtue of the fact that the integers a and b are parsed from the command-line, then I do crash on (-2^31)%-1, regardless of optimization level.

Is there something different that is happening for you?

[Hojong Han]

(In reply to comment #20)
> (In reply to comment #19)
> > (In reply to comment #18)
> > > (In reply to comment #17)
> > > > (In reply to comment #16)
> > > > I prefer a browser that doesn't crash over a browser that computes prime numbers quickly.
> > > 
> > > I totally agree with your thought. I'm appreciated for your comment.
> > 
> > I figured out why the crash didn't occur on my device. That's because of the compile optimization level.
> 
> I'm curious about this.  Can you share more details?
> 
> For me, here's what I see:
> 
> If I make it obvious to my compiler (clang+llvm) what the constants are in the modulo operation, like so:

Now I'm using gcc.

> 
> int a = -2147483647 - 1;
> int b = -1;
> return a % b; // a and b are known constants
> 
> Then I only crash when optimizations are disabled.  With optimizations, I do get a garbage result, however.
> 

It's same as yours without optimizations but with optimizations I can get the right result, zero.

> But if I make it non-obvious, such as in my test program that I attached, by virtue of the fact that the integers a and b are parsed from the command-line, then I do crash on (-2^31)%-1, regardless of optimization level.
> 

non-obvious case is same as yours. 

> Is there something different that is happening for you?

[Filip Pizlo]

(In reply to comment #21)
> (In reply to comment #20)
> > (In reply to comment #19)
> > > (In reply to comment #18)
> > > > (In reply to comment #17)
> > > > > (In reply to comment #16)
> > > > > I prefer a browser that doesn't crash over a browser that computes prime numbers quickly.
> > > > 
> > > > I totally agree with your thought. I'm appreciated for your comment.
> > > 
> > > I figured out why the crash didn't occur on my device. That's because of the compile optimization level.
> > 
> > I'm curious about this.  Can you share more details?
> > 
> > For me, here's what I see:
> > 
> > If I make it obvious to my compiler (clang+llvm) what the constants are in the modulo operation, like so:
> 
> Now I'm using gcc.
> 
> > 
> > int a = -2147483647 - 1;
> > int b = -1;
> > return a % b; // a and b are known constants
> > 
> > Then I only crash when optimizations are disabled.  With optimizations, I do get a garbage result, however.
> > 
> 
> It's same as yours without optimizations but with optimizations I can get the right result, zero.
> 
> > But if I make it non-obvious, such as in my test program that I attached, by virtue of the fact that the integers a and b are parsed from the command-line, then I do crash on (-2^31)%-1, regardless of optimization level.
> > 
> 
> non-obvious case is same as yours. 

Strange.  That would imply that integer-division-neg2tothe32-by-neg1.js should have crashed.

Can you try the following program:

function notInlineable(a, b) {
    function foo() { } // use this to force-disable inlining
    return [foo, a % b];
}

for (var i = 0; i < 1000; ++i)
    print(notInlineable(-2147483648, -1));

[Hojong Han]

(In reply to comment #22)
> 
> Strange.  That would imply that integer-division-neg2tothe32-by-neg1.js should have crashed.
> 
> Can you try the following program:
> 
> function notInlineable(a, b) {
>     function foo() { } // use this to force-disable inlining
>     return [foo, a % b];
> }
> 
> for (var i = 0; i < 1000; ++i)
>     print(notInlineable(-2147483648, -1));

Do you want me to test that script with my test binary that the patch is applied? If yes, it gives me "function foo() { },0" a lot.

[Hojong Han]

(In reply to comment #23)
> (In reply to comment #22)
> 
> Do you want me to test that script with my test binary that the patch is applied? If yes, it gives me "function foo() { },0" a lot.

Webkit, now I'm using, is not the latest one. It's around July.

[Filip Pizlo]

(In reply to comment #24)
> (In reply to comment #23)
> > (In reply to comment #22)
> > 
> > Do you want me to test that script with my test binary that the patch is applied? If yes, it gives me "function foo() { },0" a lot.
> 
> Webkit, now I'm using, is not the latest one. It's around July.

Do you know if you're even compiling the non-inlineable function with DFG?

[Hojong Han]

Created attachment 164522 [details]
dfg debug verbose log

I can find this below from log.
Cannot handle code block 0x26ada0 because of opcode op_new_func.

Could it be an answer about what you asked?