1034184 - Improve the "filter types at branches" infrastructure

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Hannes Verschore [:h4writer]]

We now improves types at branches. It is now done for MCompare/MNot and MIsObject is coming. But it seems that we might want to generalize it a bit more. Since there are a few shortcomings with it.

1) We can only improve types at "one subject"
2) We can't really easily reason about a full test.

e.g.
>     (typeof v === "object" && v !== null) ||
>      typeof v === "function" ||
>     (typeof v === "undefined" && v !== undefined)
This is the JS variant of IsObject. In extremes it would be cool if could deduce this too.

e.g.
> IsObject(fromValue) && ObjectIsTypedObject(fromValue)
Is used a lot in builtin/TypedObject.js

So this bug is about generalizing the current implementation a bit. Allow for more subjects being investigated and make it possible to deduce rules from the full test.

Comment 1

[Hannes Verschore [:h4writer]]

Other examples that we might want to be able to optimize is:
> MInstanceOf
=> remove all types from the typeset that aren't an instance of the given thing

> MTypeOf
=> only keep the types that TypeOf has

> MHasClass
...

Sushant94 is willing to have a look at this. The first objective is to refactor to find something that would make it possible to do such things (without looking at performance yet).

Comment 2

[Sushant Dinesh]

Attachment: [WIP] Improve filtering at test

This is just the beginning. I am not entirely sure if the isPhi() case is required as it does not seem to be making any difference (Maybe I haven't written a proper test case. Will look into that)
It would be better if we could make the ifs into switch-case type.

Comment 3

[Hannes Verschore [:h4writer]]

Comment on attachment 8457926 [details] [diff] [review]
[WIP] Improve filtering at test

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

This is already a good start. It looks already better than before.

There are some concerns I have:
- The isPhi test. As currently stated there is a fault in it. You cannot just look at the operands and optimize both:
 
>    [ test a ]
>    ____|_________
>   |              |
>   |              |
> [ goto ]      [ goto ]
>   |              |
>   |              |
>    --------------
>          |
>      [ phi a b  ]
>      [ test phi ]

in the last "test" you will optimize for both "a" and "b. But that is not correct. In this case the true branch will be taken if "a OR b" is true.
So the only thing we can say is that the type of "phi" is "A UNION B".

- You should kill "MCompare::filtersUndefinedOrNull" and "MTest::filtersUndefinedOrNull" and move the logic into testWalk (imho not a good name, but that's something that can be addressed lateron).

- You shouldn't use "goto"'s at all

Comment 4

[Sushant Dinesh]

Attachment: [WIP] Improve filtering at test

Addressed some of the issues mentioned above.
I don't like the name testWalk either, but as you said we can rename that later.
And for isPhi() I am not entirely sure as what I should do. I will start looking into it right away.

Comment 5

[Hannes Verschore [:h4writer]]

Comment on attachment 8459481 [details] [diff] [review]
[WIP] Improve filtering at test

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

::: js/src/jit/IonBuilder.cpp
@@ +3084,5 @@
> +}
> +
> +void
> +IonBuilder::testWalk(MDefinition *ins, bool isNot,bool trueBranch, MTest *test)
> +{

Nice.

Possible improvements:
1) You can remove the "isNot" boolean. And instead of using "isNot". Just flip the "trueBranch" value. As a result the ins->IsNot() case becomes: if (ins->isNot()) testWalk(ins->getOperand(0), !trueBranch, test);
2) What about having a switch/case for the instructions? Phi/Compare/Not/IsObject.

Comment 6

[Sushant Dinesh]

Attachment: [WIP] Improve filtering at test v2

Added detecting the required triangular structure.
Still have to add the filter when OR is encountered.

Comment 7

[Hannes Verschore [:h4writer]]

Comment on attachment 8461668 [details] [diff] [review]
[WIP] Improve filtering at test v2

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

Looks good. You don't need to request feedback every time (since that is time consuming).
Normally feedback is for "hey, I've done something, it isn't quite finished yet, but it already shows where I want to go. Is this a good approach?".
In this case we discussed this approach and agreed to do it this way, so no need to reconfirm it ;).
You can just post patches called "WIP" to show progress, but no need to ask me feedback every time.

- There are still a lot of white spaces
- This patch doesn't contain the removal of "filtersUndefinedOrNull" function anymore

::: js/src/jit/IonBuilder.cpp
@@ +3167,5 @@
> +                }
> +            }
> +            break;
> +        case MDefinition::Op_Phi:
> +            if (!detectStructure(ins, &branchIsTrue))

"detectAndOrStructure"

@@ +3170,5 @@
> +        case MDefinition::Op_Phi:
> +            if (!detectStructure(ins, &branchIsTrue))
> +                return;
> +            // Now we have detected the triangular structure and determined if it was an AND or an OR.
> +            if (branchIsTrue) {

"branchIsAnd" I suppose?

Comment 8

[Sushant Dinesh]

I cannot remove filtersUndefinedOrNull as it was being used in other places and was unsure as to what to do about them.
Ya, I was aware of the whitespaces but thought I'll take care of that later (In the final patch).
And I'll rename the functions as suggested.
I am not really sure as to what is to be done when OR is encountered though.

Comment 9

[Hannes Verschore [:h4writer]]

For OR you can do something like:

> if (a || b) {
>    
> } else {
>     // Improve types here
> }

since the else branch is actually: !(a || b)
which equals: (!a && !b)

So you can do something alike for the else branch...

Comment 10

[Hannes Verschore [:h4writer]]

(In reply to Sushant Dinesh from comment #8)
> I cannot remove filtersUndefinedOrNull as it was being used in other places
> and was unsure as to what to do about them.

It should only be used by this. So you should be able to remove it, if you find all places where it is used. Using dxr, you can find the callers etc. Just click on "filterTypesAtTest" and you will see some options:
http://dxr.mozilla.org/mozilla-central/source/js/src/jit/IonBuilder.cpp#1912

Comment 11

[Sushant Dinesh]

Attachment: Improve filtering at test part 1

Added filtering for OR as suggested in the above comment.
If the main part is now complete I think I'll move on to making the replacement more efficient. Any ideas for this?

Comment 12

[Hannes Verschore [:h4writer]]

Comment on attachment 8465539 [details] [diff] [review]
Improve filtering at test part 1

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

Sorry about the immense delay. Time went faster than expected, sorry.

I've went over the review and pointed out what I could.
But since it is so easy to introduce bugs here, I would want to have a second look,
running and testing the infrastructure with my own crafted scripts.
(If possible feel free to add js test scripts. E.g. one that fails because of the error in jsinfer.h in cloneNoObjects)

Thanks a lot for this improvement already !

::: js/src/jit/IonBuilder.cpp
@@ +3140,5 @@
> +    return true;
> +}
> +
> +void
> +IonBuilder::testWalk(MDefinition *ins,bool trueBranch, MTest *test)

s/testWalk/improveTypesAtTest/

@@ +3144,5 @@
> +IonBuilder::testWalk(MDefinition *ins,bool trueBranch, MTest *test)
> +{
> +    // When there is a AND or OR we will have to explore both the sides of the operation.
> +    // We will explore one side completely and when we reach the end i.e. null, we will go to the other side.
> +    // To add a new filter, add a new function to return the filtered typeset and also add a new if to test for the required instruction.

All comments may only be 80 letters long (inclusive whitespace before the comment).

@@ +3172,5 @@
> +                return;
> +            // Now we have detected the triangular structure and determined if it was an AND or an OR.
> +            if (branchIsAnd) {
> +                testWalk(ins->toPhi()->getOperand(0), trueBranch, test);
> +                testWalk(ins->toPhi()->getOperand(1), trueBranch, test);

For "And" this is only correct if "trueBranch == true"

@@ +3174,5 @@
> +            if (branchIsAnd) {
> +                testWalk(ins->toPhi()->getOperand(0), trueBranch, test);
> +                testWalk(ins->toPhi()->getOperand(1), trueBranch, test);
> +            } else {
> +                if (!trueBranch) {

Can you try to come up with a nice short and understandable comment that explains why this is correct. Something explaining the what I'm describing here, but denser and more understandable (if possible):

// if (a || b) {
// } else {
// }
//
// in the else case:
// !(a || b)
//
// which equals to
// !a && !b
//
// In which case we can use the logic of branchIsAnd:
// testWalk(MNot::new(ins->toPhi()->getOperand(0)), !truebranch, test);
// testWalk(MNot::new(ins->toPhi()->getOperand(1)), !truebranch, test);
//
// Which is (using logic of MNot):
// testWalk(ins->toPhi()->getOperand(0), truebranch, test);
// testWalk(ins->toPhi()->getOperand(1)), truebranch, test);

@@ +3217,5 @@
> +            }
> +    }
> +
> +    if ((filtersUndefined && subject->resultTypeSet()->hasType(types::Type::UndefinedType()))
> +         || (filtersNull && subject->resultTypeSet()->hasType(types::Type::NullType()))) {

Nit: this { need on a new line.

@@ +3231,5 @@
> +}
> +
> +bool
> +IonBuilder::improveTypesAtTest(MTest *test)
> +{

remove this function and directly call testWalk, where we now call improveTypesAtTest

::: js/src/jsinfer.cpp
@@ +693,5 @@
>  
> +TemporaryTypeSet *
> +TypeSet::cloneNoObjects(LifoAlloc *alloc)
> +{
> +    TemporaryTypeSet *res = clone(alloc);

This is not correct, since a TypeSet can contain "AnyObject" or specific objects. You only remove the AnyObject, but not the specific objects.

Though we might want to do this differently here. Instead of creating something and removing the contents afterwards:

new(result) TemporaryTypeSet(flags, nullptr);

This will create a TemporaryTypeSet with given flags without any specific objects ;).

::: js/src/jsinfer.h
@@ +625,5 @@
>      TemporaryTypeSet *filter(LifoAlloc *alloc, bool filterUndefined, bool filterNull) const;
>  
>      // Create a new TemporaryTypeSet where the type has been set to object.
>      TemporaryTypeSet *cloneObjectsOnly(LifoAlloc *alloc);
> +    TemporaryTypeSet *cloneNoObjects(LifoAlloc *alloc);

s/cloneNoObjects/cloneWithoutObjects/

Comment 13

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

I was forced to remove the default case as this caused jit-tests to fail as it was trying to optimize types it should not.
Also I noticed that in some cases the argument to MIsObject() is a MPhi due to which replaceTypeSet is failing. Any idea on how to go about filtering in such cases?

Comment 14

[Sushant Dinesh]

Attachment: [WIP] Part2

Comment 15

[Hannes Verschore [:h4writer]]

Comment on attachment 8472959 [details] [diff] [review]
[WIP] Part2

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

::: js/src/jit/IonBuilder.cpp
@@ +3076,5 @@
> +        if (ins->isFilterTypeSet()) {
> +            if (!(ins->toFilterTypeSet()->getOperand(0) == subject) || !(ins->toFilterTypeSet()->dependency() == test))
> +                continue;
> +            types::TemporaryTypeSet *intersect = types::TypeSet::intersectSets(ins->toFilterTypeSet()->resultTypeSet(), type, alloc_->lifoAlloc());
> +            ins->toFilterTypeSet()->setResultTypeSet(intersect);

you should adjust "resultType" too, based on the intersected TypeSet. See the constructor of MFilterTypeSet on how that is done.

Comment 16

[Sushant Dinesh]

Attachment: [WIP] Part2

Fixed the problem stated above.

Comment 17

[Hannes Verschore [:h4writer]]

Comment on attachment 8472207 [details] [diff] [review]
Improve filtering at test - part1

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

::: js/src/jsinfer.cpp
@@ +694,5 @@
> +TemporaryTypeSet *
> +TypeSet::cloneWithoutObjects(LifoAlloc *alloc)
> +{
> +    TemporaryTypeSet *res = new(alloc) TemporaryTypeSet(flags, nullptr);
> +    res->flags &= ~TYPE_FLAG_ANYOBJECT;

TemporaryTypeSet *res = alloc->new_<TemporaryTypeSet>();
res->flags = flags & ~TYPE_FLAG_ANYOBJECT;

this will also solve the segmentation fault you saw ;)

Comment 18

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

Comment 19

[Sushant Dinesh]

Attachment: Improve filtering at test - part2

Comment 20

[Hannes Verschore [:h4writer]]

Comment on attachment 8475394 [details] [diff] [review]
Improve filtering at test - part1

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

Awesome work. Thanks! Did a real/normal review now. After this we should be almost ready to land this.

::: js/src/jit/IonBuilder.cpp
@@ +1908,5 @@
>          return ControlStatus_Error;
>      graph().moveBlockToEnd(current);
>  
>      if (state.branch.test)
> +        improveTypesAtTest(state.branch.test->getOperand(0), state.branch.test->ifTrue() == current, state.branch.test);

- I think this line is longer than 100 chars. Can you split this line into multiple lines?
e.g. add "MTest *test = state.branch.test;".
and use that variable:
improveTypesAtTest(test->getOperand(0), test->ifTrue() == current, state.branch.test);
- Test if improveTypeAtTest fails. I explain this change a bit lower. If it fails you'll need to return ControlStatus_Error;

@@ +3062,5 @@
>      return ControlStatus_Jumped;
>  }
>  
> +void
> +IonBuilder::replaceTypeSet(MDefinition *subject,types::TemporaryTypeSet *type, MTest *test)

Style nit: add space after "subject,"

@@ +3083,5 @@
>      }
> +}
> +
> +bool
> +IonBuilder::detectAndOrStructure(MDefinition *ins,bool *branchIsAnd)

- Can you adjust MDefinition to MPhi as input
- Style nit: add a space after "ins,"

@@ +3091,5 @@
> +
> +    MTest *initialTest;
> +    MBasicBlock *initialBlock;
> +    MBasicBlock *branchBlock;
> +    MBasicBlock *testBlock = current->getPredecessor(0);

I think this should be ins->block(); We want to know if the given MPhi is part of such and/or structure. (Not the current block. Which in most cases is the same, but is not a limit.).

@@ +3124,5 @@
> +
> +    MPhi *phi = ins->toPhi();
> +
> +    if (phi->block() != testBlock || !phi->hasOneDefUse())
> +        return false;

- This phi->block() != testBlock
Is not needed anymore, because of previous comment.
- !phi->hasOneDefUse()
Why do you think this check is needed? IIUC the more uses it has, to more uses we can replace with a better typeset ;).

@@ +3129,5 @@
> +
> +    for(MPhiIterator iter = testBlock->phisBegin(); iter != testBlock->phisEnd(); ++iter) {
> +        if (*iter != phi)
> +            return false;
> +    }

What is the intention of this check? I think this isn't needed?

@@ +3146,5 @@
> +}
> +
> +void
> +IonBuilder::improveTypesAtTest(MDefinition *ins,bool trueBranch, MTest *test)
> +{

Can you make this function fallible? This should fail if an allocation fails.

@@ +3162,5 @@
> +
> +    switch(ins->op()) {
> +        case MDefinition::Op_Not:
> +            improveTypesAtTest(ins->toNot()->getOperand(0), !trueBranch, test);
> +            break;

s/break/return/

@@ +3167,5 @@
> +        case MDefinition::Op_IsObject:
> +            if (trueBranch)
> +                type = ins->getOperand(0)->resultTypeSet()->cloneObjectsOnly(alloc_->lifoAlloc());
> +            else
> +                //type = ins->getOperand(0)->resultTypeSet()->cloneWithoutObjects(alloc_->lifoAlloc());

Style nit: make sure a line only constains 100 characters (inclusive with the spaces before the line). E.g. create variable that contains the "ins->getOperand(0)->resultTypeSet()" that can be used in the if and else case.

@@ +3170,5 @@
> +            else
> +                //type = ins->getOperand(0)->resultTypeSet()->cloneWithoutObjects(alloc_->lifoAlloc());
> +            if (type)
> +                subject = ins->getOperand(0);
> +            break;

We need to propagate an allocation failure, so:

if (!type)
    return false;

subject = ins->getOperand(0);

@@ +3176,5 @@
> +            if (!detectAndOrStructure(ins, &branchIsAnd))
> +                return;
> +            // Now we have detected the triangular structure and determined if it was an AND or an OR.
> +            if (branchIsAnd) {
> +                if(trueBranch) {

Style nit: add space after the "if"

@@ +3178,5 @@
> +            // Now we have detected the triangular structure and determined if it was an AND or an OR.
> +            if (branchIsAnd) {
> +                if(trueBranch) {
> +                    improveTypesAtTest(ins->toPhi()->getOperand(0), trueBranch, test);
> +                    improveTypesAtTest(ins->toPhi()->getOperand(1), trueBranch, test);

trueBranch equals true. So you can put "true" here.

@@ +3201,5 @@
> +                    improveTypesAtTest(ins->toPhi()->getOperand(0), false, test);
> +                    improveTypesAtTest(ins->toPhi()->getOperand(1), false, test);
> +                }
> +            }
> +            break;

s/break/return true;/

@@ +3204,5 @@
> +            }
> +            break;
> +        case MDefinition::Op_Compare:
> +            if (ins->toCompare()->compareType() != MCompare::Compare_Undefined &&
> +                ins->toCompare()->compareType() != MCompare::Compare_Null)

Style nit: an if statement that covers multiple lines, need to have {} around it's body.

@@ +3214,5 @@
> +                      ins->toCompare()->jsop() == JSOP_EQ);
> +
> +            // JSOP_*NE only removes undefined/null from if/true branch
> +            if (!trueBranch && (ins->toCompare()->jsop() == JSOP_STRICTNE ||
> +                ins->toCompare()->jsop() == JSOP_NE))

Style nit: an if statement that covers multiple lines, need to have {} around it's body.

@@ +3219,5 @@
> +                return;
> +
> +            // JSOP_*EQ only removes undefined/null from else/false branch
> +            if (trueBranch && (ins->toCompare()->jsop() == JSOP_STRICTEQ ||
> +                ins->toCompare()->jsop() == JSOP_EQ))

Style nit: an if statement that covers multiple lines, need to have {} around it's body.

@@ +3247,5 @@
> +         || (filtersNull && subject->resultTypeSet()->hasType(types::Type::NullType())))
> +    {
> +        type = subject->resultTypeSet()->filter(alloc_->lifoAlloc(), filtersUndefined,
> +                filtersNull);
> +    }

- Can you move this creation of "type" to the appropiate case statement? So where you set the variable filtersUndefined/filtersNull.
- can you check "type" and "return false" on allocation failure.

@@ +3251,5 @@
> +    }
> +
> +    // If subject is set we can optimize. Hence we call replace to replace with the new typeset.
> +    if (subject && type)
> +        replaceTypeSet(subject, type, test);

You can remove the "type" and "subject" check here.
1) subject gets already tested a little bit higher
2) type should always contain something if we are here. Plz add MOZ_ASSERT(type); to be sure.

@@ +3709,5 @@
>      if (!setCurrentAndSpecializePhis(ifTrue))
>          return false;
>  
>      // Filter the types in the true branch.
> +    improveTypesAtTest(test->getOperand(0), test->ifTrue() == current, test);

- Test if improveTypeAtTest fails. If it fails you'll need to return ControlStatus_Error;

::: js/src/jsinfer.cpp
@@ +693,5 @@
>  
> +TemporaryTypeSet *
> +TypeSet::cloneWithoutObjects(LifoAlloc *alloc)
> +{
> +    TemporaryTypeSet *res = alloc->new_<TemporaryTypeSet>();

Test if res isn't a nullptr and return nullptr in this case. (OOM failure)

Comment 21

[Hannes Verschore [:h4writer]]

Comment on attachment 8475395 [details] [diff] [review]
Improve filtering at test - part2

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

::: js/src/jit/IonBuilder.cpp
@@ +3063,5 @@
>  }
>  
>  void
>  IonBuilder::replaceTypeSet(MDefinition *subject,types::TemporaryTypeSet *type, MTest *test)
>  {

Can you make this fallible on OOM. So it return false when an allocation fails. Every use should test if it has fails and propagate this error.

@@ +3074,5 @@
>              continue;
> +
> +        if (ins->isFilterTypeSet()) {
> +            if (!(ins->toFilterTypeSet()->getOperand(0) == subject) || !(ins->toFilterTypeSet()->dependency() == test))
> +                continue;

Can you restructure this, so we take the false branch in this case, instead of just "continue"?

Making the structure of this function like:

for() {
   // Improve typeset if possible.
   if (ins->isFilterTypeSet() && ins->getOperand(0) == subject && ins->dependency() == test) {
       ...
       continue;
   }

   if (subject == ins) {
       ...
   }
}

@@ +3075,5 @@
> +
> +        if (ins->isFilterTypeSet()) {
> +            if (!(ins->toFilterTypeSet()->getOperand(0) == subject) || !(ins->toFilterTypeSet()->dependency() == test))
> +                continue;
> +            types::TemporaryTypeSet *intersect = types::TypeSet::intersectSets(ins->toFilterTypeSet()->resultTypeSet(), type, alloc_->lifoAlloc());

can you test intersect isn't nullptr (OOM) and return false in that case.

::: js/src/jit/MIR.h
@@ +9704,5 @@
>  {
>      MFilterTypeSet(MDefinition *def, types::TemporaryTypeSet *types)
>        : MUnaryInstruction(def)
>      {
> +      //  MOZ_ASSERT(!types->unknown());

This assert should stay.

@@ +9705,5 @@
>      MFilterTypeSet(MDefinition *def, types::TemporaryTypeSet *types)
>        : MUnaryInstruction(def)
>      {
> +      //  MOZ_ASSERT(!types->unknown());
> +      //  MOZ_ASSERT(def->type() == types->getKnownMIRType());

Please remove this comment

::: js/src/jsinfer.cpp
@@ +723,5 @@
>  }
>  
> +/* static */ TemporaryTypeSet *
> +TypeSet::intersectSets(TemporaryTypeSet *a, TemporaryTypeSet *b, LifoAlloc *alloc)
> +{

Logically this function can do better on "unknownObject"

a intersection b
with a or b containing "unknownObject" now returns "unknownObject".

But if a is "unknownObject", we can just take all known objects from b
And if b is "unknownObject", we can just take all known objects from a

@@ +727,5 @@
> +{
> +    TemporaryTypeSet *res = alloc->new_<TemporaryTypeSet>(a->baseFlags() & b->baseFlags(),
> +            static_cast<TypeObjectKey**>(nullptr));
> +
> +    if(!res)

Style nit: add space after "if"

@@ +730,5 @@
> +
> +    if(!res)
> +        return nullptr;
> +
> +    if(res->unknownObject())

Style nit: add space after "if"

Comment 22

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

Comment 23

[Sushant Dinesh]

Attachment: Improve filtering at test - part2

Hey,
Thanks for your review :)
I hope I've covered everything. If there is anything I've missed or if something is wrong, Let me know.

Thanks!

Comment 24

[Hannes Verschore [:h4writer]]

Comment on attachment 8476785 [details] [diff] [review]
Improve filtering at test - part1

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

Almost only style nits to make it a bit more readable. Logic is fine (except for the cloneWithoutObjects).

::: js/src/jit/IonBuilder.cpp
@@ +3147,5 @@
> +    // as much type information as possible.
> +
> +    types::TemporaryTypeSet *type = nullptr;
> +    bool filtersUndefined = false;
> +    bool filtersNull = false;

These two bools are only needed for "case MDefinition::Op_Compare". Can you move it there?

@@ +3164,5 @@
> +                type = ins->getOperand(0)->resultTypeSet()
> +                    ->cloneObjectsOnly(alloc_->lifoAlloc());
> +            else
> +                type = ins->getOperand(0)->resultTypeSet()
> +                    ->cloneWithoutObjects(alloc_->lifoAlloc());

This is a bit ugly. Can you create a variable:
TemporaryTypeSet *oldType = ins->getOperand(0)->resultTypeSet();

@@ +3200,5 @@
> +                    improveTypesAtTest(ins->toPhi()->getOperand(1), false, test);
> +                }
> +            }
> +            return true;
> +        case MDefinition::Op_Compare:

This case is quite long. Can you create a function "improveTypesAtCompare" that has this logic?
And do the "replaceTypeSet" also in that function.

@@ +3214,5 @@
> +                      ins->toCompare()->jsop() == JSOP_EQ);
> +
> +            // JSOP_*NE only removes undefined/null from if/true branch
> +            if (!trueBranch && (ins->toCompare()->jsop() == JSOP_STRICTNE ||
> +                ins->toCompare()->jsop() == JSOP_NE)) 

Style nit: remove white space.

@@ +3239,5 @@
> +
> +            if (!subject)
> +                return false;
> +
> +            if(!subject->resultTypeSet() || subject->resultTypeSet()->unknown())

Style nit: space between "if" and "("

@@ +3719,5 @@
>      if (!setCurrentAndSpecializePhis(ifTrue))
>          return false;
>  
>      // Filter the types in the true branch.
> +    if(!improveTypesAtTest(test->getOperand(0), test->ifTrue() == current, test))

Style nit: add space between "if" and "("

::: js/src/jit/IonBuilder.h
@@ +348,5 @@
> +    // Improve the type information at tests
> +    bool improveTypesAtTest(MDefinition *ins, bool trueBranch, MTest *test);
> +    // Used to detect triangular structure at test.
> +    bool detectAndOrStructure(MPhi *ins, bool *branchIsTrue);
> +    void testWalk(MDefinition *ins, bool trueBranch, MTest *test);

I think this function doesn't exist anymore. So can get removed.

::: js/src/jsinfer.cpp
@@ +697,5 @@
> +    TemporaryTypeSet *res = alloc->new_<TemporaryTypeSet>();
> +    if (res == nullptr)
> +        return nullptr;
> +
> +    res->flags &= ~TYPE_FLAG_ANYOBJECT;

This should be:
res->flags = flags & ~TYPE_FLAG_ANYOBJECT;

(You create an empty TypeSet, not a clone. It doesn't has the information of flags yet ;))

Comment 25

[Hannes Verschore [:h4writer]]

Comment on attachment 8476786 [details] [diff] [review]
Improve filtering at test - part2

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

There are still a lot of whitespaces in this patch. Can you remove all the trailing ones?

::: js/src/jit/IonBuilder.cpp
@@ +3077,1 @@
>              continue;

No need for this anymore

@@ +3085,5 @@
> +            if (!intersect)
> +                return false;
> +
> +            ins->toFilterTypeSet()->setResultType(intersect->getKnownMIRType());
> +            ins->toFilterTypeSet()->setResultTypeSet(intersect);

You need to add a "continue;" here

@@ +3086,5 @@
> +                return false;
> +
> +            ins->toFilterTypeSet()->setResultType(intersect->getKnownMIRType());
> +            ins->toFilterTypeSet()->setResultTypeSet(intersect);
> +        } 

Style nit: can you add a newline here?

::: js/src/jsinfer.cpp
@@ +736,5 @@
> +        res = alloc->new_<TemporaryTypeSet>(a->baseFlags(),
> +                static_cast<TypeObjectKey**>(nullptr));
> +    else
> +        res = alloc->new_<TemporaryTypeSet>(a->baseFlags() & b->baseFlags(),
> +                static_cast<TypeObjectKey**>(nullptr));

Oh, I think you misunderstood it here.

If a is unknownObject and b isn't. You can return the ObjectSet from b and the intersection of the flags.
If b is unknownObject and a isn't. You can return the ObjectSet from a and the intersection of the flags.
if a and b are unknownObject, you just return unknownObject (with intersection of the flags.
if a and b have an objectSet, you need to intersect the objectSet and insect the flags.

*Note: Style nits: if a body of an if/else if/else is longer than a line it needs to be surrounded by "{}"

@@ +744,5 @@
> +
> +    if (res->unknownObject())
> +        return res;
> +
> +    for(size_t i = 0; i < a->getObjectCount() && !res->unknownObject(); i++) {

Style nit: please add a space between "for" and "("

Comment 26

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

Comment 27

[Sushant Dinesh]

Attachment: Improve filtering at test - part2

Comment 28

[Hannes Verschore [:h4writer]]

Comment on attachment 8478872 [details] [diff] [review]
Improve filtering at test - part1

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

I'm running out of comments. I promise ;)

::: js/src/jit/IonBuilder.cpp
@@ +3170,5 @@
> +    if (trueBranch && (ins->jsop() == JSOP_STRICTEQ ||
> +                       ins->jsop() == JSOP_EQ))
> +    {
> +        return true;
> +    }

Can you create a follow-up bug, that support an extra case?
I.e. if the ifbranch is filtering undefined/null, this means the elsebranch is always undefined/null. The first is implemented the latter isn't.

@@ +3211,5 @@
> +    // as much type information as possible.
> +
> +    types::TemporaryTypeSet *type = nullptr;
> +
> +    MDefinition *subject = nullptr;

Only the isObject case uses these variables. Move these to that case-statement.

@@ +3212,5 @@
> +
> +    types::TemporaryTypeSet *type = nullptr;
> +
> +    MDefinition *subject = nullptr;
> +    bool branchIsAnd = true;

Nit: Move the boolean in the case-statement.

@@ +3218,5 @@
> +    if (!ins)
> +        return true;
> +
> +    switch(ins->op()) {
> +        case MDefinition::Op_Not:

Oh I overlooked this every time?
Style nit: the case should only have two spaces, instead of four. And the body of the case too. So the amount of spaces between the switch and body is four spaces in total.

@@ +3222,5 @@
> +        case MDefinition::Op_Not:
> +            improveTypesAtTest(ins->toNot()->getOperand(0), !trueBranch, test);
> +            return true;
> +        case MDefinition::Op_IsObject:
> +            {

This should be on the "case" line.
"case XXX: {"

@@ +3278,5 @@
> +
> +
> +    MOZ_ASSERT(type);
> +
> +    replaceTypeSet(subject, type, test);

Only used by the isObject case. Please move in there ;)

Comment 29

[Hannes Verschore [:h4writer]]

Comment on attachment 8478873 [details] [diff] [review]
Improve filtering at test - part2

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

Thanks. This looks correct now ;)

::: js/src/jit/IonBuilder.cpp
@@ +3302,5 @@
>  
>  
>      MOZ_ASSERT(type);
>  
> +    if(!replaceTypeSet(subject, type, test))

Style nit: There needs to be a space between the "if" and "(" ;)

::: js/src/jsinfer.cpp
@@ +737,5 @@
> +    if (res->unknownObject())
> +        return res;
> +
> +    if (a->unkownObject() && b->unknownObject())
> +        return res;

you can remove this line. Since this is covered by "res->unknownObject()".
Can you instead add:
MOZ_ASSERT(!a->unknownObject() || !b->unknownObject());

@@ +750,5 @@
> +        for (size_t i = 0; i < a->getObjectCount() && !res->unknownObject(); i++)
> +            res->addType(Type::ObjectType(a->getObject(i)), alloc);
> +        return res;
> +    }
> +

Can you add
MOZ_ASSERT(!a->unknownObject() && !b->unknownObject());

@@ +752,5 @@
> +        return res;
> +    }
> +
> +    for (size_t i = 0; i < a->getObjectCount() && !res->unknownObject(); i++) {
> +        for (size_t j = 0; j < b->getObjectCount() && !res->unknownObject(); j++) {

You can remove the "!res->unknownObject()" check on both for-loops.

Comment 30

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

Comment 31

[Sushant Dinesh]

Attachment: Improve filtering at test - part2

Comment 32

[Hannes Verschore [:h4writer]]

Comment on attachment 8479083 [details] [diff] [review]
Improve filtering at test - part1

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

Style nit: There are trailing whitespaces in this patch. Can you remove them?

::: js/src/jit/IonBuilder.cpp
@@ +3228,5 @@
> +        if (!type)
> +            return false;
> +        subject = ins->getOperand(0);
> +        
> +        MOZ_ASSERT(type);

You can remove this ASSERT now, since we just tested "type" two lines before. It won't have changed ;)

@@ +3266,5 @@
> +                improveTypesAtTest(ins->toPhi()->getOperand(1), false, test);
> +            }
> +        }
> +      }
> +      return true;

Can you move the "return true", inside the case block scope "a.k.a. {}"

Comment 33

[Hannes Verschore [:h4writer]]

It's time to request access to commit to the tryserver ;).
Can you request L1 access for try? Add me in CC on the bug and I'll vouch for you.
https://www.mozilla.org/hacking/committer/

Comment 34

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

carry over r+ from previous patch.

Comment 35

[Sushant Dinesh]

Pushed to try: https://tbpl.mozilla.org/?tree=Try&rev=21eee755a538

Hope the options I gave to try server was fine.

Comment 36

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

Fixed tryserver failures

Comment 37

[Sushant Dinesh]

https://tbpl.mozilla.org/?tree=Try&rev=c9a658d7be53

Comment 38

[Sushant Dinesh]

Turns out the failures might not have had anything to do with this patch. I pulled latest Mozilla-central and then applied my patches and push to try: https://tbpl.mozilla.org/?tree=Try&rev=d500b8ea4a5f

Comment 39

[Hannes Verschore [:h4writer]]

Comment on attachment 8482745 [details] [diff] [review]
Improve filtering at test - part1

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

I really wanted to push this today, but there is one issue holding me back. Quite straightforward though. We just disable an optimization a bit too early. We can do better ;).

::: js/src/jit/IonBuilder.cpp
@@ +3219,5 @@
> +      case MDefinition::Op_IsObject: {
> +        MDefinition *subject = nullptr;
> +        types::TemporaryTypeSet *type = nullptr;
> +        types::TemporaryTypeSet *oldType = ins->getOperand(0)->resultTypeSet();
> +        

Nit: plz remove space.

@@ +3223,5 @@
> +        
> +        if (!oldType)
> +            return true;
> +        if (!oldType->hasType(types::Type::AnyObjectType()))
> +            return true;

This isn't optimal. That means we will only do when there is "AnyObject" in the TypeSet. We might want to support this optimization in a broader range:

1) oldType->hasType(types::Type::AnyObjectType()) is correct. But please use oldType->unknownObject()

2) or when a typeset contains actual objects: getObjectCount() != 0 and for(i) getObject(i) != nullptr. (Can you made a new function which test this in jsinfer.h?

::: js/src/jsinfer.cpp
@@ +694,5 @@
> +TemporaryTypeSet *
> +TypeSet::cloneWithoutObjects(LifoAlloc *alloc)
> +{
> +    TemporaryTypeSet *res = alloc->new_<TemporaryTypeSet>();
> +    if (res == nullptr)

if (res)

Comment 40

[Hannes Verschore [:h4writer]]

Comment on attachment 8482745 [details] [diff] [review]
Improve filtering at test - part1

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

::: js/src/jsinfer.cpp
@@ +694,5 @@
> +TemporaryTypeSet *
> +TypeSet::cloneWithoutObjects(LifoAlloc *alloc)
> +{
> +    TemporaryTypeSet *res = alloc->new_<TemporaryTypeSet>();
> +    if (res == nullptr)

oh I meant "if (!res)"

Comment 41

[Hannes Verschore [:h4writer]]

Comment on attachment 8482745 [details] [diff] [review]
Improve filtering at test - part1

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

::: js/src/jsinfer.cpp
@@ +697,5 @@
> +    TemporaryTypeSet *res = alloc->new_<TemporaryTypeSet>();
> +    if (res == nullptr)
> +        return nullptr;
> +
> +    res->flags = flags & ~TYPE_FLAG_ANYOBJECT;

So apparently you need to add "res->setBaseObjectCount(0);" here. The objectCount is saved in the flags, so the above line copy's that and assumes we have objects. While we didn't want to have. This fixes the failures I saw ;)

Comment 42

[Sushant Dinesh]

Attachment: Improve filtering at test - part1

Added the changes.

Comment 43

[Sushant Dinesh]

Attachment: Improve filtering at test - part2

Fixed replaceTypeSet which was causing the tests to fail. I copied over the "Don't replace the typeSet if subject is more accurate" from ensureDefiniteTypeSet and now it seems to be working fine.

Comment 44

[Sushant Dinesh]

https://tbpl.mozilla.org/?tree=Try&rev=15f47108a068

Comment 45

[Hannes Verschore [:h4writer]]

Comment on attachment 8485376 [details] [diff] [review]
Improve filtering at test - part1

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

These are some extra changes I made before pushing

::: js/src/jit/IonBuilder.cpp
@@ +3216,5 @@
> +
> +    switch(ins->op()) {
> +      case MDefinition::Op_Not:
> +        improveTypesAtTest(ins->toNot()->getOperand(0), !trueBranch, test);
> +        return true;

return improveTypesAtTest(...);

@@ +3224,5 @@
> +        types::TemporaryTypeSet *oldType = ins->getOperand(0)->resultTypeSet();
> +
> +        if (!oldType)
> +            return true;
> +        if (!oldType->unknownObject() && oldType->checkNullObject())

I changed this to:
if (oldType->unknown() || !oldType->mightBeMIRType(MIRType_Object)) 
That way we don't have to introduce checkNullObject

@@ +3248,5 @@
> +        // Now we have detected the triangular structure and determined if it was an AND or an OR.
> +        if (branchIsAnd) {
> +            if (trueBranch) {
> +                improveTypesAtTest(ins->toPhi()->getOperand(0), true, test);
> +                improveTypesAtTest(ins->toPhi()->getOperand(1), true, test);

Look at the return of "improveTypesAtTest"

@@ +3268,5 @@
> +             *
> +             */
> +            if (!trueBranch) {
> +                improveTypesAtTest(ins->toPhi()->getOperand(0), false, test);
> +                improveTypesAtTest(ins->toPhi()->getOperand(1), false, test);

Look at the return of improveTypesAtTest

@@ +3278,5 @@
> +      case MDefinition::Op_Compare:
> +        if (!improveTypesAtCompare(ins->toCompare(), trueBranch, test))
> +            return false;
> +
> +        return true;

Just "return improveTypesAtCompare()"

@@ +3741,5 @@
>          return false;
>  
>      // Filter the types in the true branch.
> +    if (!improveTypesAtTest(test->getOperand(0), test->ifTrue() == current, test))
> +        return ControlStatus_Error;

return false;

Comment 46

[Hannes Verschore [:h4writer]]

Comment on attachment 8485377 [details] [diff] [review]
Improve filtering at test - part2

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

I'll push both patches upstream soonish. (These are the alterations I made)

::: js/src/jit/IonBuilder.cpp
@@ +3096,5 @@
> +                if (subject->type() != type->getKnownMIRType() &&
> +                    type->getKnownMIRType() == MIRType_Value)
> +                {
> +                    continue;
> +                }

This is totally not needed. So I removed it. Though I had to alter cloneObjects. There was a bug in it.

::: js/src/jsinfer.cpp
@@ +746,5 @@
> +    res = alloc->new_<TemporaryTypeSet>(a->baseFlags() & b->baseFlags(),
> +                static_cast<TypeObjectKey**>(nullptr));
> +    if (!res)
> +        return nullptr;
> +

add res->setBaseObjectCount(0);

@@ +755,5 @@
> +
> +    if (a->unknownObject()) {
> +        for (size_t i = 0; i < b->getObjectCount() && !res->unknownObject(); i++)
> +            res->addType(Type::ObjectType(b->getObject(i)), alloc);
> +        return res;

remove the !res->unknownObject()

@@ +760,5 @@
> +    }
> +
> +    if (b->unknownObject()) {
> +        for (size_t i = 0; i < a->getObjectCount() && !res->unknownObject(); i++)
> +            res->addType(Type::ObjectType(a->getObject(i)), alloc);

remove the !res->unknownObject()

Comment 47

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e0d00b4a15fe
https://hg.mozilla.org/integration/mozilla-inbound/rev/784efb03fa57

Comment 48

[Hannes Verschore [:h4writer]]

Extra fix and disabling and/or since it is breaking octane-typescript
https://hg.mozilla.org/integration/mozilla-inbound/rev/583e40a84116

Comment 49

[Hannes Verschore [:h4writer]]

Gives already a 2.5% improvement on octane-richards

Comment 50

[Sushant Dinesh]

(In reply to Hannes Verschore [:h4writer] from comment #49)
> Gives already a 2.5% improvement on octane-richards

That sounds good :D

Any idea why it is breaking octane-typescript? I would like to look into it but I can do it earliest by Sunday. Is there a log or something which I can look at?

And Thanks :D

Comment 51

[Hannes Verschore [:h4writer]]

(In reply to Sushant Dinesh from comment #50)
> (In reply to Hannes Verschore [:h4writer] from comment #49)
> Any idea why it is breaking octane-typescript? I would like to look into it
> but I can do it earliest by Sunday. Is there a log or something which I can
> look at?

You can run octane yourself. The source used on awfy is: https://github.com/h4writer/arewefastyet/tree/master/benchmarks/octane. So you can take that. The error is related to the branchBlock not being finished building yet (or something like that).

Comment 52

[Hannes Verschore [:h4writer]]

Attachment: Adjust detectAndOrStructure

So this is kinda similar to the code in MaybeFoldAndOrBlock to find a diamond structure. I tried to unite both, but there is a big difference. In MaybeFoldAndOrBlock we are at the top of the graph, here we come in at the bottom. Also there are some constraints, since we are in IonBuilder and some blocks will not be finished yet. So the order is important here.

As a result I didn't share the code.

Comment 53

[Hannes Verschore [:h4writer]]

@Sushant: I decided to fix this myself, since you have currently exams and because this is a hard part to get right. Even for me. That way you can also focus on the follow-up bugs ;)

Comment 54

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/e0d00b4a15fe
https://hg.mozilla.org/mozilla-central/rev/784efb03fa57
https://hg.mozilla.org/mozilla-central/rev/583e40a84116

Comment 55

[Hugh Nougher [:Hughman]]

(In reply to Hannes Verschore [:h4writer] from comment #48)
> Extra fix and disabling and/or since it is breaking octane-typescript
> https://hg.mozilla.org/integration/mozilla-inbound/rev/583e40a84116

This also appears to have undone a regression in octane-Crypto and octane-EarleyBoyer. Hopefully the coming patch doesn't have the same regression.

Reopened because its not all landed yet.

Comment 56

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Fix type = typo

Doh, didn't catch this in the review over IRC. Feel free either to embed into one of your patches, or r+ and i'll land it this morning :)

Comment 57

[Hannes Verschore [:h4writer]]

Comment on attachment 8487725 [details] [diff] [review]
Fix type = typo

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

Oh, good catch! If you don't want to spend time on it I will land it together with the patch that is still waiting for r? ;). Else feel free to push.

Comment 58

[Benjamin Bouvier [:bbouvier] (inactive)]

Just pushed (the typo was triggering a build warning):
https://hg.mozilla.org/integration/mozilla-inbound/rev/5f0e31371150

Comment 59

[Brian Hackett [Laid off!]]

Comment on attachment 8487585 [details] [diff] [review]
Adjust detectAndOrStructure

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

::: js/src/jit/IonBuilder.cpp
@@ +3139,5 @@
> +    //         \     |
> +    //        testBlock
> +    //
> +    // Where testBlock contains only a test on a phi combining two values
> +    // pushed onto the stack by initialBlock and branchBlock.

This sentence isn't accurate, maybe change this to:

// Where ins is a phi from testBlock which combines two values
// pushed onto the stack by initialBlock and branchBlock.

Comment 60

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5f0e31371150

Comment 61

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/568cefaf88a9

Comment 62

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/568cefaf88a9