Bug 153693 - B3 should reduce Mod(value, constant) to Div and Mul so that our Div optimizations can do things
Summary: B3 should reduce Mod(value, constant) to Div and Mul so that our Div optimiza...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on:
Blocks: 150507
  Show dependency treegraph
 
Reported: 2016-01-29 19:45 PST by Filip Pizlo
Modified: 2016-01-30 00:56 PST (History)
10 users (show)

See Also:


Attachments
the patch (5.41 KB, patch)
2016-01-29 19:48 PST, Filip Pizlo
sbarati: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2016-01-29 19:45:56 PST
Patch forthcoming.
Comment 1 Filip Pizlo 2016-01-29 19:48:55 PST
Created attachment 270286 [details]
the patch
Comment 2 Saam Barati 2016-01-29 20:39:46 PST
Comment on attachment 270286 [details]
the patch

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

R=me

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:726
> +                m_changed = true;

This indentation looks off to me (but I'm on my phone so maybe not)

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:762
> +                    // This does work for the D = -1 special case.

Why not turn D=-1 and D=1 into 0 as the result?

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:764
> +                    //                = -2^31 - -2^31 * -1

This should be:
-2^31 - (2^31 * -1)
Comment 3 Filip Pizlo 2016-01-29 21:05:01 PST
(In reply to comment #2)
> Comment on attachment 270286 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=270286&action=review
> 
> R=me
> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:726
> > +                m_changed = true;
> 
> This indentation looks off to me (but I'm on my phone so maybe not)
> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:762
> > +                    // This does work for the D = -1 special case.
> 
> Why not turn D=-1 and D=1 into 0 as the result?

Because I didn't know if that was correct.  I guess it is.

We already get this optimization since we have Sub(N,Mul(Div(N,1),1)) which reduces to Sub(N,Mul(N,1)) then Sub(N,N) and then 0.  Unless the strength reduction phase becomes very expensive, it's sort of nice that it handles a lot of things by induction.

> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:764
> > +                    //                = -2^31 - -2^31 * -1
> 
> This should be:
> -2^31 - (2^31 * -1)

I really did mean "-2^31 - ((-(2^31)) * -1)".  Is it not clear that this is what is meant from how I wrote it?
Comment 4 Filip Pizlo 2016-01-29 21:15:03 PST
Landed in http://trac.webkit.org/changeset/195882
Comment 5 Saam Barati 2016-01-29 23:59:46 PST
Comment on attachment 270286 [details]
the patch

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

>>> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:764
>>> +                    //                = -2^31 - -2^31 * -1
>> 
>> This should be:
>> -2^31 - (2^31 * -1)
> 
> I really did mean "-2^31 - ((-(2^31)) * -1)".  Is it not clear that this is what is meant from how I wrote it?

I understood your notation, but the calculation you wrote is incorrect:
-(2^31) - (-2^31 * -1) = -(2^31) - (2^31) = -2^32
because
-2^31 - -2^31 / -1 * -1 !== -(2^31) - (-2^31 * -1)
it is
-2^31 - -2^31 / -1 * -1 = -2^31 - (2^31 * -1) = -2^31 - (-2^31) = -2^31 + 2^31 = 0
Comment 6 Filip Pizlo 2016-01-30 00:54:49 PST
(In reply to comment #5)
> Comment on attachment 270286 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=270286&action=review
> 
> >>> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:764
> >>> +                    //                = -2^31 - -2^31 * -1
> >> 
> >> This should be:
> >> -2^31 - (2^31 * -1)
> > 
> > I really did mean "-2^31 - ((-(2^31)) * -1)".  Is it not clear that this is what is meant from how I wrote it?
> 
> I understood your notation, but the calculation you wrote is incorrect:
> -(2^31) - (-2^31 * -1) = -(2^31) - (2^31) = -2^32
> because
> -2^31 - -2^31 / -1 * -1 !== -(2^31) - (-2^31 * -1)
> it is
> -2^31 - -2^31 / -1 * -1 = -2^31 - (2^31 * -1) = -2^31 - (-2^31) = -2^31 +
> 2^31 = 0

This is int32 math.  In int32 math, -1 * -2^31 = -2*31.
Comment 7 Filip Pizlo 2016-01-30 00:56:07 PST
(In reply to comment #6)
> (In reply to comment #5)
> > Comment on attachment 270286 [details]
> > the patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=270286&action=review
> > 
> > >>> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:764
> > >>> +                    //                = -2^31 - -2^31 * -1
> > >> 
> > >> This should be:
> > >> -2^31 - (2^31 * -1)
> > > 
> > > I really did mean "-2^31 - ((-(2^31)) * -1)".  Is it not clear that this is what is meant from how I wrote it?
> > 
> > I understood your notation, but the calculation you wrote is incorrect:
> > -(2^31) - (-2^31 * -1) = -(2^31) - (2^31) = -2^32
> > because
> > -2^31 - -2^31 / -1 * -1 !== -(2^31) - (-2^31 * -1)
> > it is
> > -2^31 - -2^31 / -1 * -1 = -2^31 - (2^31 * -1) = -2^31 - (-2^31) = -2^31 +
> > 2^31 = 0
> 
> This is int32 math.  In int32 math, -1 * -2^31 = -2*31.

Also -2^31 / -1 = -2^31.  And 0 - -2^31 = -2^31.  And -(-2^31) = -2^31.