Last Comment Bug 734400 - IonMonkey: Elide DivBy0, NegOverflow, and NegZero checks in LDivI when inputs are appropriate constants.
: IonMonkey: Elide DivBy0, NegOverflow, and NegZero checks in LDivI when inputs...
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
: -- normal (vote)
: ---
Assigned To: Kannan Vijayan [:djvj]
:
Mentors:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2012-03-09 08:42 PST by Kannan Vijayan [:djvj]
Modified: 2012-03-13 16:32 PDT (History)
4 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Patch v1 (4.35 KB, patch)
2012-03-09 13:11 PST, Kannan Vijayan [:djvj]
no flags Details | Diff | Splinter Review
Patch v2 (7.03 KB, patch)
2012-03-12 14:13 PDT, Kannan Vijayan [:djvj]
jdemooij: review+
Details | Diff | Splinter Review
Patch v3 (6.90 KB, patch)
2012-03-13 10:11 PDT, Kannan Vijayan [:djvj]
jdemooij: review+
Details | Diff | Splinter Review

Description Kannan Vijayan [:djvj] 2012-03-09 08:42:18 PST
LDivI emits checks for divide by zero.  This can be elided in situations where the divisor is known to be non-zero (i.e. syntactically constant non-zero divisor).

Optimize these cases.
Comment 1 Kannan Vijayan [:djvj] 2012-03-09 13:11:43 PST
Created attachment 604505 [details] [diff] [review]
Patch v1
Comment 2 Jan de Mooij [:jandem] 2012-03-10 02:39:10 PST
Comment on attachment 604505 [details] [diff] [review]
Patch v1

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

Looks good!

While you are here, can you do something similar for the integer-overflow check (we don't need it if lhs != -2147483648 or rhs != -1), and the negative zero check (unnecessary if lhs != 0 or rhs >= 0)? These can just be 2 other methods. It's nice that in the (common) case where the divisor is a constant > 0, all three methods return false.

::: js/src/ion/shared/CodeGenerator-x86-shared.cpp
@@ +550,4 @@
>      JS_ASSERT(lhs == eax);
>  
>      // Prevent divide by zero.
> +    if(ins->possibleDivideByZero()) {

We usually call the method on the MIR instruction directly, so if you add a "MDiv *mir()" method to LDivI (which returns mir_->toDiv()), we can just call ins->mir()->possibleDivideByZero() here.

(tiny style-nit: add a space between the "if" and the "(")
Comment 3 Hannes Verschore [:h4writer] 2012-03-10 09:53:26 PST
CanOverflow and canBeNegativeZero would be awesome indeed!

Just had a look. And the implementation looks very different to the MMul version.
I think we should make it similar? (Asking second opinion to jandem or dvander.)

This means:
- possibleDivideByZero -> canBeDivideByZero ?

MMul does the following:
Has two booleans "canOverflow_" and "canBeNegativeZero_" set to true.
Has two functions "canOverflow()" and "canBeNegativeZero()" that just return the bool.
In the Foldsto function the booleans are set to false (if possible)
Also the function fallible() is adjusted. Because if the function doesn't need a bailout point. That function should return false.

LMul has a value pointing to the MMul (like Jan already said)
In the codegeneration (visitMul) the code takes the MMul from the LMul and asks if the checks are needed.
Comment 4 Kannan Vijayan [:djvj] 2012-03-12 09:22:27 PDT
Thanks for the feedback guys.

Hannes: good point on the fallible - I hadn't noticed that before.  However, I'm not sure if throwing in fields inside the MDiv class is the best idea, as it's been done in MMul.

That would eagerly check for a condition that only becomes relevant much later in the compilation process.  I can see there being a case for it if the routines are checked frequently, but it seems like this'll only be checked once: at code generation time.  Why do the eager work to compute and store those flags?  They may not end up being used anyway if the VM decides not to compile it later on.

I also notice that the MMul class's "canOverflow_" and "canBeNegativeZero_" fields are private and there are no setter methods.. so it seems like they're hard coded true for now.  Am I missing something?
Comment 5 Hannes Verschore [:h4writer] 2012-03-12 09:28:25 PDT
In the GVN phase the function Foldsto gets called. That function sets the values of canOverflow_ and canBeNegativeZero_.

About the eagerly. I'm not sure why you would want to wait till later? I don't think there is a phase later than GVN that could change the values?
Comment 6 Kannan Vijayan [:djvj] 2012-03-12 10:42:11 PDT
I'd put the question the other way: we're explicitly setting state that redundantly stores information that can be queried dynamically when needed.  Is there a good reason for that, as opposed to functionally computing them it necessary?

The two reasons which would justify that which come to my mind are:

1. That information may be destroyed at a later time, so by querying it early and setting it on the MInstruction you're preserving it for later.
2. The dynamic query could be invoked many times, leading to expensive checks being done multiple times, in which case saving the state in a MInstruction field is an optimization to improve compile times.

In this case, the information seems to be strictly queried at code-generation time.  It actually seems like it'd be useful to delay the check until as late as possible, to allow other optimizations at the MIR layer to operate, and potentially improve the number of situations where we can elide these runtime checks.

I'm not trying to say this with authority as I'm still pretty new to the codebase.. so let me know if any of the assumptions I'm making in my argument don't actually hold.
Comment 7 Hannes Verschore [:h4writer] 2012-03-12 11:00:29 PDT
Same for me. I'm only telling what my impression is/was (when I was there this summer). It could have changed already or I could misheard it ;)

But I was thinking about the following reason: We eventually want to do range analysis. So we know the range of a value. Based on this information we can change canOverflow and canBeNegativeZero too. This will be another phase in the compiler (or at the same time of GVN). I don't think this information will be saved until code generation ...

About the no setters for these values. That's because it isn't needed yet...
Comment 8 Kannan Vijayan [:djvj] 2012-03-12 14:13:13 PDT
Created attachment 605122 [details] [diff] [review]
Patch v2

Patch to elide checks for div-by-zero, negative-overflow, and negative-zero checks on integer divides.
Comment 9 Jan de Mooij [:jandem] 2012-03-13 02:00:58 PDT
Comment on attachment 605122 [details] [diff] [review]
Patch v2

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

Nice! r=me with the comments below addressed.

::: js/src/ion/MIR.h
@@ +1998,5 @@
> +    bool canBeDivideByZero() {
> +        MDefinition *rhs = getOperand(1);
> +        return rhs->isConstant() ?
> +                rhs->toConstant()->value().isInt32(0)
> +              : true;

Nit: rewriting it as if (...) return false; return true; like the other two methods may be a bit more readable.

@@ +2010,5 @@
> +        // negative overflow check can be skipped.
> +        if (lhs->isConstant() && !lhs->toConstant()->value().isInt32(INT32_MIN))
> +            return false;
> +
> +        // if rhs is a constant int != -1, likewise.

Style nit: comments should start with a capital letter and end with a period.

@@ +2012,5 @@
> +            return false;
> +
> +        // if rhs is a constant int != -1, likewise.
> +        if (rhs->isConstant() && !rhs->toConstant()->value().isInt32(-1))
> +            return false;

Add a "return true;" here.

@@ +2028,5 @@
> +        if (rhs->isConstant()) {
> +            const js::Value &val = rhs->toConstant()->value();
> +            if (val.isInt32() && (val.toInt32() >= 0))
> +                return false;
> +        }

And here.
Comment 10 Kannan Vijayan [:djvj] 2012-03-13 10:11:19 PDT
Created attachment 605440 [details] [diff] [review]
Patch v3

Takes care of style and correctness issues mentioned by Jan in Comment 9.
Comment 11 Jan de Mooij [:jandem] 2012-03-13 12:34:40 PDT
Comment on attachment 605440 [details] [diff] [review]
Patch v3

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

Looks good, r=me with the comment below addressed.

Do you have commit access or should I land this patch?

::: js/src/ion/MIR.h
@@ +2000,5 @@
>      }
> +
> +    bool canBeDivideByZero() {
> +        MDefinition *rhs = getOperand(1);
> +        if (rhs->isConstant() && rhs->toConstant()->value().isInt32(0))

This should have a "!" before the "rhs->toConstant()->value().."
Comment 12 David Anderson [:dvander] 2012-03-13 16:32:23 PDT
pushed w/ typo fixed: http://hg.mozilla.org/projects/ionmonkey/rev/10f5e15563f3

Note You need to log in before you can comment on or make changes to this bug.