777262 - IonMonkey: Inline more compare operations

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

v8-raytrace testIntersection has a pretty hot comparison: 

if(shape != exclude){

Here we know "shape" is either a Plane or Sphere object (IIRC), and "exclude" is a Plane, Sphere or null. Currently we use CompareV because we can't use LCompare for the object comparison due to the possible null type for the RHS.

It would be nice if we had an instruction like CompareV that'd take two Values, and generate the comparisons based on the two type sets. So in this case we'd first check if the RHS is null, then do a pointer comparison for the objects (we know they have no equality hooks).

Probably not a large win or worth fixing right now, but we should do it eventually.

Comment 1

[Hannes Verschore [:h4writer]]

Quick and dirty hack shows a max increase of 5% on v8-raytrace for this.

Comment 2

[Hannes Verschore [:h4writer]]

Attachment: Implement Compare_Sentinel_Object

- Added an enum that defines the CompareType (instead of MIRType)
- Added Compare_Sentinel_Object, comparison with object/null/undefined
- Added LCompareV and LCompareVAndBranch, currently only used by Compare_Sentinel_Object,
  but could get improved and even be used for more inlined comparisons. At least that's the intention.

Nexto the improvements needed to implement Compare_Sentinel_Object, I changed the code to the other Compares too.
The improvements are listed here:

LIR-Common: 
- reordered the compares to have CompareX and CompareXAndBranch nexto eachother
- renamed LCompareV to LCompareVM

Lowering:
- CompareXAndBranch: reordered to be closer to MIRType definition order
- Compare: reordered to be closer to MIRType definition order and removed level of intendation

TypePolicy
- adjustInputs: do "'Bool compared to Bool' becomes 'Compare_Int32'" upfront. Increasing readability

Comment 3

[Hannes Verschore [:h4writer]]

Attachment: Implement Compare_Sentinel_Object

Like always forgot to qref

Comment 4

[Jeff Walden [:Waldo]]

Any chance I could get you to hold off on this til after I land bug 792108?  (Hopefully soon, just need to do final build-perf-testing.)  There's definite overlap between the two.

Comment 5

[Hannes Verschore [:h4writer]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #4)
> Any chance I could get you to hold off on this til after I land bug 792108? 
> (Hopefully soon, just need to do final build-perf-testing.)  There's
> definite overlap between the two.

Sure. I see no reason to postpone the review, because that bug doesn't alter behavior that I need to account for. This patch won't apply nicely on top of yours, but needed alterations are obvious. I.e. no functionality changes. But I will wait until your patch lands, before pushing...

Comment 6

[Hannes Verschore [:h4writer]]

Comment on attachment 691984 [details] [diff] [review]
Implement Compare_Sentinel_Object

Now that I think about it, the needed adjustments to do the checks based on typesets isn't that big anymore.

Comment 7

[Hannes Verschore [:h4writer]]

Attachment: Part 1: reorder compares

No functionality changes, just adjustments to make code more readable.
- visitCompareV to visitCompareVM
- LCompare* is followed by LCompare*AndBranch
- Order of compares are now in the order of MIRType_*
- Removed 1-intentation of visitCompare

Comment 8

[Hannes Verschore [:h4writer]]

Attachment: Part 2: add CompareType

Add a CompareType that atm mimics specialization. Next patch will add a new type (that has no MIRType_* alternative).

Comment 9

[Hannes Verschore [:h4writer]]

Attachment: Part 3: add Compare_TypeSet, WIP

Almost done. A few TODO's + a lot of testing

Comment 10

[Hannes Verschore [:h4writer]]

Attachment: Part 1: reorder compares

Few nits

Comment 11

[Hannes Verschore [:h4writer]]

Attachment: Part 3: add Compare_TypeSet

This is part3, adding the Compare_TypeSet. Note that I haven't rebased to tip yet, but I've added the extra check to disable objects that resemble undefined...

Comment 12

[Jan de Mooij [:jandem]]

Comment on attachment 693023 [details] [diff] [review]
Part 1: reorder compares

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

Cool, much nicer this way :) r=me with nits addressed.

::: js/src/ion/Lowering.cpp
@@ +413,5 @@
>          bool result;
>          if (comp->tryFold(&result))
>              return add(new LGoto(result ? ifTrue : ifFalse));
>  
> +        // Emit LCompare*AndBranch

Nit: full stop (.) at the end, same for the comments below.

@@ +439,5 @@
>          }
> +
> +        // Compare and branch Int32 or Object pointers
> +        if (comp->specialization() == MIRType_Int32 ||
> +            comp->specialization() == MIRType_Object) {

Nit: { goes on its own line if the condition spans multiple lines:

if (aaa ||
    bbb)
{

}

@@ +554,5 @@
> +    }
> +
> +    // Compare Int32 or Object pointers
> +    if (comp->specialization() == MIRType_Int32 ||
> +        comp->specialization() == MIRType_Object) {

Nit: { on its own line.

@@ +566,5 @@
> +    // Compare doubles
> +    if (comp->specialization() == MIRType_Double)
> +        return define(new LCompareD(useRegister(left), useRegister(right)), comp);
> +
> +    JS_NOT_REACHED("unrecognized compare type");

Nit: add a "return false;" here.

::: js/src/ion/TypePolicy.cpp
@@ +107,5 @@
> +    // If the LHS is boolean, we set the specialization to Compare_Int32.
> +    // This matches other comparisons of the form bool === bool and
> +    // generated code of Compare_Int32 is more efficient.
> +    if (specialization_ == MIRType_Boolean &&
> +        def->getOperand(0)->type() == MIRType_Boolean) {

Nit: { on its own line

@@ +108,5 @@
> +    // This matches other comparisons of the form bool === bool and
> +    // generated code of Compare_Int32 is more efficient.
> +    if (specialization_ == MIRType_Boolean &&
> +        def->getOperand(0)->type() == MIRType_Boolean) {
> +       JS_ASSERT(def->getOperand(1)->type() == MIRType_Boolean);

This assert does not always hold, getOperand(1) can be a Value we have to unbox like below. The loop below should handle this fine though (insert ToInt32), so just remove this assert.

Comment 13

[Jan de Mooij [:jandem]]

Comment on attachment 692938 [details] [diff] [review]
Part 2: add CompareType

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

Nice!

::: js/src/ion/Lowering.cpp
@@ +421,5 @@
>          // Compare and branch null/undefined
>          // The second operand has known null/undefined type,
>          // so just test the first operand.
> +        if (comp->compareType() == MCompare::Compare_Null ||
> +            comp->compareType() == MCompare::Compare_Undefined) {

Nit: { on its own line

@@ +534,5 @@
>          return emitAtUses(comp);
>  
>      // Compare Null and Undefined
> +    if (comp->compareType() == MCompare::Compare_Null ||
> +        comp->compareType() == MCompare::Compare_Undefined) {

Ditto.

::: js/src/ion/shared/CodeGenerator-x86-shared.cpp
@@ +202,5 @@
>      }
>  }
>  
>  void
> +CodeGeneratorX86Shared::emitCompare(MCompare::CompareType type, const LAllocation *left, const LAllocation *right)

Don't forget to make the same changes for ARM.

Comment 14

[Hannes Verschore [:h4writer]]

Attachment: Part 3: add Compare_Value

On IRC we discussed the logic is rather complicated for the few cases extra we would support. We said the most important thing to get in was undefined/object checks for v8-raytrace. Therefore this adds Compare_Value. It will report the compare of the full value (all bits). This is not always correct and therefore this optimization is only done when we are sure that the comparison equals the comparison of bits of the value.

Comment 15

[Jan de Mooij [:jandem]]

Comment on attachment 693394 [details] [diff] [review]
Part 3: add Compare_Value

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

Nice! I think it'd good to take another look after addressing these comments, but looks ready otherwise.

::: js/src/ion/Lowering.cpp
@@ +463,5 @@
> +        if (comp->compareType() == MCompare::Compare_Value) {
> +            LCompareVAndBranch *lir = new LCompareVAndBranch(ifTrue, ifFalse);
> +            if (!useBoxAtStart(lir, LCompareV::LhsInput, left))
> +                return false;
> +            if (!useBoxAtStart(lir, LCompareV::RhsInput, right))

Nit: s/LCompareV/LCompareVAndBranch

::: js/src/ion/MIR.cpp
@@ +1143,5 @@
>  
>          if (IsNullOrUndefined(rhs)) {
>              compareType_ = (rhs == MIRType_Null) ? Compare_Null : Compare_Undefined;
>              return;
>          }

Can you move the STRICTEQ/STRICTNE Compare_Boolean code here? Using Compare_Boolean is slightly more efficient than Compare_Value so we should check it first.

@@ +1146,5 @@
>              return;
>          }
> +
> +        // Determine if we can do a quick value check
> +        if (b.lhsTypes->knownPrimitiveOrObject() && b.rhsTypes->knownPrimitiveOrObject()) {

It would be good to move most of the code inside this "if" to a new function like

static bool
CanDoBitwiseComparison(JSContext *cx, JSOp op, TypeSet *lhs, TypeSet *rhs)

Also avoids extra indentation because you can "return false;" if for instance lhs->knownPrimitiveOrObject() returns false.

@@ +1163,5 @@
> +                 b.lhsTypes->hasObjectFlags(cx, types::OBJECT_FLAG_EMULATES_UNDEFINED)) ||
> +                (b.rhsTypes->objectOrSentinel() &&
> +                 b.rhsTypes->hasObjectFlags(cx, types::OBJECT_FLAG_EMULATES_UNDEFINED)))
> +            {
> +                return;

Use maybeObject() and combine the special-equality and emulates-undefined checks:

if (b.lhsTypes->maybeObject() &&
    (b.lhsTypes->hasObjectFlags(cx, types::OBJECT_FLAG_SPECIAL_EQUALITY) ||
     b.lhsTypes->hasObjectFlags(cx, types::OBJECT_FLAG_EMULATES_UNDEFINED))
{
    return;
}

@@ +1206,5 @@
> +                // For loosy comparison of an object with a Boolean/Number/String
> +                // the valueOf the object is taken. Therefore not supported.
> +                types::TypeFlags numbers = types::TYPE_FLAG_BOOLEAN |
> +                                           types::TYPE_FLAG_INT32;
> +                if ((b.lhsTypes->objectOrSentinel() &&

maybeObject()

@@ +1209,5 @@
> +                                           types::TYPE_FLAG_INT32;
> +                if ((b.lhsTypes->objectOrSentinel() &&
> +                     b.rhsTypes->hasAnyFlag(numbers)) ||
> +                    (b.lhsTypes->hasAnyFlag(numbers) &&
> +                     b.rhsTypes->objectOrSentinel()))

Same here.

Comment 16

[Hannes Verschore [:h4writer]]

Attachment: Part 3: add Compare_Value

With the requested adjustments to MCompare::infer

Comment 17

[Hannes Verschore [:h4writer]]

Comment on attachment 693819 [details] [diff] [review]
Part 3: add Compare_Value

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

::: js/src/ion/MIR.cpp
@@ +1159,5 @@
>          return;
>      }
>  
>      // Loose cross-integer/boolean comparisons may be treated as Int32.
> +    if (looseEq &&

Oops, should be !strictEq here. Because relational eq is still allowed

Comment 18

[Jan de Mooij [:jandem]]

Comment on attachment 693819 [details] [diff] [review]
Part 3: add Compare_Value

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

Looks good! r=me with comments below addressed.

::: js/src/ion/Lowering.cpp
@@ +463,5 @@
> +        if (comp->compareType() == MCompare::Compare_Value) {
> +            LCompareVAndBranch *lir = new LCompareVAndBranch(ifTrue, ifFalse);
> +            if (!useBoxAtStart(lir, LCompareV::LhsInput, left))
> +                return false;
> +            if (!useBoxAtStart(lir, LCompareV::RhsInput, right))

Nit: s/LCompareV/LCompareVAndBranch (2 times)

::: js/src/ion/MIR.cpp
@@ +1047,5 @@
> +static bool
> +CanDoValueBitwiseCmp(JSContext *cx, types::StackTypeSet *lhs, types::StackTypeSet *rhs, bool looseEq)
> +{
> +    // Only primitive (not double/string) or objects are supported.
> +    // I.e. Undefined/Null/Boolean/Int32/Double and Object

Nit: not Double.

::: js/src/ion/x86/CodeGenerator-x86.cpp
@@ +371,5 @@
> +
> +bool
> +CodeGeneratorX86::visitCompareV(LCompareV *lir)
> +{
> +    MCompare *mir = lir->mir();

Can you assert

JS_ASSERT(mir->jsop() == JSOP_EQ ||
          mir->jsop() == JSOP_NE ||
          mir->jsop() == JSOP_STRICTEQ ||
          mir->jsop() == JSOP_STRICTNE);

here?

@@ +397,5 @@
> +
> +bool
> +CodeGeneratorX86::visitCompareVAndBranch(LCompareVAndBranch *lir)
> +{
> +    MCompare *mir = lir->mir();

Same here (and also the x64 and ARM implementation).

Comment 19

[Hannes Verschore [:h4writer]]

On microbenchmark this shows to be 2x faster than the VMCall.
The remaining cases where we still take the VMCall are now:

kraken:
3x Compare_Unknown: u1n0b0i0d0s0o0 == u0n0b0i1d0s0o0  MIR0 == MIR3 rel1 loosy0 strict0
=> Implement relational undefined check. I think this should be always false?
1x Compare_Unknown: u0n0b0i0d0s0o0 == u0n0b0i0d0s1o0  MIR8 == MIR5 rel0 loosy1 strict0

sunspider:
1x Compare_Unknown: u0n1b0i1d1s0o0 == u1n1b0i1d1s0o0  MIR8 == MIR8 rel1 loosy0 strict0
1x Compare_Unknown: u0n1b0i1d1s0o0 == u1n0b0i1d1s0o0  MIR8 == MIR8 rel1 loosy0 strict0
2x Compare_Unknown: u0n1b0i1d1s0o0 == u0n0b0i1d1s0o0  MIR8 == MIR4 rel1 loosy0 strict0
=> Implement undefined/null/double relational comparison
3x Compare_Unknown: u0n0b0i0d0s1o0 == u0n0b0i0d0s1o0  MIR5 == MIR5 rel1 loosy0 strict0
=> Implement relational string comparison

v8
1x Compare_Unknown: u0n0b0i0d0s0o1 == u0n1b0i0d0s0o1  MIR6 == MIR8 rel0 loosy1 strict0
=> probably unknown object
1x Compare_Unknown: u0n0b0i1d0s0o0 == u0n0b0i0d0s0o0  MIR3 == MIR8 rel1 loosy0 strict0
2x Compare_Unknown: u0n0b0i0d0s0o0 == u0n0b0i1d0s0o0  MIR8 == MIR3 rel1 loosy0 strict0
4x Compare_Unknown: u0n0b0i0d0s0o0 == u0n0b0i0d0s1o0  MIR8 == MIR5 rel0 loosy1 strict0
18x Compare_Unknown: u0n0b0i0d0s1o0 == u0n0b0i1d0s1o0  MIR5 == MIR8 rel0 loosy0 strict1
=> String === String/Int
18x Compare_Unknown: u0n0b0i0d0s1o0 == u0n0b0i1d0s1o1  MIR5 == MIR8 rel0 loosy0 strict1
14x Compare_Unknown: u0n0b0i1d0s0o0 == u0n0b0i0d0s0o0  MIR3 == MIR8 rel1 loosy0 strict0

Remaining cases are with unknown types, or with possible not really important comparisons.

In other words the patch is definitely working. I see a 1% gain on v8-raytrace, but other benchmarks stay the same.

Comment 20

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6bc692ff1c10

Comment 21

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/6bc692ff1c10
https://hg.mozilla.org/mozilla-central/rev/2e6bec0c1f8a
https://hg.mozilla.org/mozilla-central/rev/80c7c3eee490