943410 - Use range analysis to eliminate bailouts for unsigned div and mod

Status: NEW

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

Description

[Dan Gohman [:sunfish]]

Currently, codegen for non-truncated unsigned div and mod requires bailouts for the case where the result is not in the Int32 range. Range analysis should be used to discover cases where bailouts are not needed.

Comment 1

[Anirudh Vemula]

Hey, I would like to take this one. This is my first time, so I might need some extra guidance in tackling this bug. Any help? Thanks

Comment 2

[Dan Gohman [:sunfish]]

Great! Feel free to ask any questions you have here in the bug or in IRC (irc.mozilla.org, #ionmonkey). The basic pattern for this kind of optimization is that a MDefinition's collectRangeInfoPreTrunc() method collects range information sets a flag on the MDefinition, and then things like fallible() can use the flag, and we can make Lowering and Codegen skip the bailouts using the flag. For some examples, see code for other operators for dealing with canBeNegativeZero_ flags (negative zero is another common bailout cause).

Comment 3

[Dan Gohman [:sunfish]]

Are you still interested in working on this? Let me know if there's anything unclear or if there's anything I can help with.

Comment 4

[Rohit Agrawal]

Hi, 
I am interested to work on this bug. I am developing for open source for the first time, so I might need to ask a lot of questions along the way.

As a starting point, I have built Firefox. Could you point me to the location of this bug in source?

Comment 5

[Nicolas B. Pierron [:nbp]]

Hi,

You will find the collectRangeInfo function in the RangeAnalysis.cpp file[1], which is settings flags on the MIR definition [2], and which is later used in the CodeGenerator [3].

The goal is to change the fallible method of MDiv such as we do not allocate any snapshot when we do not intend to bailout out of the code generated by the code generator.  Snapshots are allocated with assignSnapshot when we lower the instruction in the LIR generator [4].

[1] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/RangeAnalysis.cpp?from=RangeAnalysis.cpp#2718
[2] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/MIR.h#4523
[3] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/shared/CodeGenerator-x86-shared.cpp#1011
[4] http://dxr.mozilla.org/mozilla-central/source/js/src/jit/shared/Lowering-x86-shared.cpp#131

Comment 6

[Rohit Agrawal]

hi , thanks for assigning the bug to me, i am reading through the code and will come back with update/queries in a day.

Comment 7

[Rohit Agrawal]

Attachment: mypatch.diff

First patch based on discussion with nbp and sunfish in IRC chat.

Comment 8

[Till Schneidereit [:till]]

Comment on attachment 8460534 [details] [diff] [review]
mypatch.diff

nbp and sunfish might not have seen this patch, so requesting feedback from one of them.

Comment 9

[diwas joshi [:dij]]

hello, is somebody working on this bug because i would like to work on this bug, this would be my first bug so i might need some extra guidance debugging it. thanks!

Comment 10

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8460534 [details] [diff] [review]
mypatch.diff

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

Welcome, sorry for not replying sooner.
I guess I was not clear in my previous comment  (comment 5).

::: js/src/jit/MIR.cpp
@@ +1593,5 @@
>  
>  bool
>  MDiv::fallible() const
>  {
> +    return !isTruncated() || canBeNegativeZero || canBeDivideByZero || canBeNegativeOverflow;

In such case you are adding more way to make the return value of fallible to be true.
This means that we would be allocating more snapshots than necessary.

The idea is to reduce the number of times this function returns "true" and increase the number of times it returns "false".  The only condition being that we need to return "true" when the corresponding code-generator visit function execute a bailoutIf function.  The reason being that the bailoutIf function is the only function which requires a snapshot.

Basically, the idea is simple.  Look at the CodeGenerator file, note all the conditions needed to reach a bailout function.  And make sure that we follow the same conditions for allocating snapshots.  In other terms, to decide if the MDiv is fallible or not.

Comment 11

[andy.zsshen]

After some study for the Div-related codegen functions.
I tried to summarize the check points which will let the control flow
fall through bailoutIf():

* visitUDivOrMod():
 - isUnsigned() && canBeDivideByZero() && !isTruncated()
 - isUnsigned() && !canTruncateRemainder()
 - isUnsigned() && !isTruncated()

* visitDivPowTwoI():
 - !isTruncated() && divisor < 0

* visitDivOrModConstantI():
 - !isTruncated()
 - !isTruncated() && divisor < 0

* visitDivI()
 - canBeDivideByZero() && !canTrucateInfinities()
 - canBeNegativeOverflow() && !canTrucateOverflow()
 - !canTruncateNegativeZero() && canBeNegativeZero()
 - !canTruncateRemainder()

I noticed that all the truncation related function will invoke
isTruncated(). So the above check points can be further reduced to:
* visitUDivOrMod():
 - isUnsigned() && !isTruncated()

* visitDivPowTwoI():
 - !isTruncated() && divisor < 0

* visitDivOrModConstantI():
 - !isTruncated()

* visitDivI()
 - !isTruncated() && (canBeDivideByZero() || canBeNegativeOverflow() || canBeNegativeZero())

Currently, the MDiv::fallible() just contains !isTruncated().
To refine the condition, it may be helpful to include other kinds of checking flags
(like constant and divisor checking). Is that correct?

Comment 12

[Nicolas B. Pierron [:nbp]]

(In reply to andy.zsshen from comment #11)
> After some study for the Div-related codegen functions.
> I tried to summarize the check points which will let the control flow
> fall through bailoutIf():
> 
> * visitUDivOrMod():
>  - isUnsigned() && canBeDivideByZero() && !isTruncated()
>  - isUnsigned() && !canTruncateRemainder()
>  - isUnsigned() && !isTruncated()
> 
> * visitDivPowTwoI():
>  - !isTruncated() && divisor < 0
> 
> * visitDivOrModConstantI():
>  - !isTruncated()
>  - !isTruncated() && divisor < 0
> 
> * visitDivI()
>  - canBeDivideByZero() && !canTrucateInfinities()
>  - canBeNegativeOverflow() && !canTrucateOverflow()
>  - !canTruncateNegativeZero() && canBeNegativeZero()
>  - !canTruncateRemainder()
> 
> I noticed that all the truncation related function will invoke
> isTruncated(). So the above check points can be further reduced to:
> * visitUDivOrMod():
>  - isUnsigned() && !isTruncated()
> 
> * visitDivPowTwoI():
>  - !isTruncated() && divisor < 0

http://dxr.mozilla.org/mozilla-central/source/js/src/jit/shared/CodeGenerator-x86-shared.cpp#969

implies:
 - !isTruncated()

> 
> * visitDivOrModConstantI():
>  - !isTruncated()
> 
> * visitDivI()
>  - !isTruncated() && (canBeDivideByZero() || canBeNegativeOverflow() ||
> canBeNegativeZero())

Nice work!

> Currently, the MDiv::fallible() just contains !isTruncated().
> To refine the condition, it may be helpful to include other kinds of
> checking flags
> (like constant and divisor checking). Is that correct?

This is correct, especially for MDivI, which is the only one which is influenced by RangeAnalysis beyond the isTruncated flag at the moment.

Maybe it would be easier to have a special function on MDiv for each specialization, such as

  bool fallibleDivU() { return …; }
  bool fallibleDivPowTwoI() { return …; }
  bool fallibleDivConstantI() { return …; }
  bool fallibleDivI() { return …; }

What do you think?

Comment 13

[andy.zsshen]

I tried to merge these cases into a single function by 
using unsigned and constant checking flags.
Before patch submission, a preliminary draft is posted here:

bool
MDiv::fallible() const
{
    if (isUnsigned()) {
        // Handle visitUDivOrMod()
        return !isTruncated();
    } else {
        if (rhs()->isConstant()) {
            // Handle visitDivPowTwoI() and visitDivOrModConstantI()
            return !isTruncated();
        } else {
            // Handle visitDivI()
            return !isTruncated() &&  
                   (canBeDivideByZero() || canBeNegativeOverflow() || canBeNegativeZero());
        }
    }
}

If it is not appropriate, I may think for other approaches. :)

Comment 14

[Nicolas B. Pierron [:nbp]]

(In reply to andy.zsshen from comment #13)
> I tried to merge these cases into a single function by 
> using unsigned and constant checking flags.
> Before patch submission, a preliminary draft is posted here:
> 
> bool
> MDiv::fallible() const
> {
>     …
> }
> 
> If it is not appropriate, I may think for other approaches. :)

I like the fact that you want to mirror what the Lowering is doing, but you might also notice that we have multiple functions named lowerDivI in the tree, and not all of them have the same generated code.  Which is way I suggested the first approach.

Also, checking again in the fallible function implies that we redo the work done in the Lowering, which is not good, where they can be used as assertions to ensure that these functions are called under the right context.

Comment 15

[andy.zsshen]

For the first approach, the specialized checking functions might be:

bool
MDiv::fallibleDivU() const
{
    return !isTruncated();
}

bool
MDiv::fallibleDivPowTwoI() const
{
    return !isTruncated();
}

bool
MDiv::fallibleDivConstantI() const
{
    return !isTruncated();
}

bool
MDiv::fallibleDivI() const
{
    return !isTruncated() &&  
           (canBeDivideByZero() || canBeNegativeOverflow() || canBeNegativeZero());
}

And should we also change the invocations for MDiv::fallible() in Lowering-x86-shared.cpp
into the corresponding specialized checking?
For example:
LDivI *lir = new(alloc()) LDivI(useRegister(div->lhs()), useRegister(div->rhs()),
                                tempFixed(edx));
if (div->fallible())
    assignSnapshot(lir, Bailout_DoubleOutput);
====>
if (div->fallibleDivI())
    assignSnapshot(lit, Bailout_DoubleOutput);

Comment 16

[Nicolas B. Pierron [:nbp]]

(In reply to andy.zsshen from comment #15)
> For the first approach, the specialized checking functions might be:
> 
> […]
> 
> And should we also change the invocations for MDiv::fallible() in
> Lowering-x86-shared.cpp
> into the corresponding specialized checking?
> […]

Yes.

Comment 17

[andy.zsshen]

Attachment: Implement_MDivFallible.txt

Implement the specialized fallible functions for MDiv and change the invocations to fallible() in Lowering-x86-shared.cpp to these specialized ones.

Comment 18

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8535491 [details] [diff] [review]
Implement_MDivFallible.txt

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

Nice :)
You should request Level 1, to push these patches to try ;)

Comment 19

[andy.zsshen]

Sorry for the delayed response,

I did not notice that the level 1 access needs some formal processes.

Especially for the Committer's Agreement.

It may take some time to finish the request.

Comment 20

[Ryan VanderMeulen [:RyanVM]]

In the mean time, myself or Nicolas can push your patch to Try if you want. Don't let that slow you down :)

Comment 21

[andy.zsshen]

This patch failed to pass many test suits:
https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=4555634d209d
Thus I selected one case "jit-test/tests/auto-regress/bug687125.js" to examine the root cause.

In fact, there is a simple division operation "Math.floor(t/86400000)" in this script.
Since the denominator is a non-power-of-two constant, I expected the refined code should call
"MDiv::fallibleDivConstantI()" to check if the operation is fallible.
However, as GDB showed, it calls "MDiv::fallibleDivI"!

After inspection, I noticed that the code cannot pass a condition in "shared/Lowering-x86-shared.cpp":
"if (rhs != 0 && gen->optimizationInfo().registerAllocator() != RegisterAllocator_LSRA)"
The "rhs" equals "86400000" and is not zero.
But the "registerAllocator()" returns "RegisterAllocator_LSRA".
This might be the reason why the refined code cannot fall throught the correct fallible
checking functions.

I may check other failed cases to see if they also encounters the same problem.

Comment 22

[andy.zsshen]

Attachment: bug943410.js

Carry on the r+ from Implement_MDivFallible.txt

Comment 23

[andy.zsshen]

Comment on attachment 8546016 [details]
bug943410.js

Carry on the r+ from Implement_MDivFallible.txt

Comment 24

[Matthew Gaudet (he/him) [:mgaudet]]

I'm going to drop the good-first-bug tag here: I don't really think we want a new contributor to try to jump into Ion right now.

Comment 25

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee is inactive on Bugzilla, so the assignee is being reset.