1138881 - Improve types at AndOr

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Hannes Verschore [:h4writer]]

We currently don't improve types at:
var b = a || 1;

'a' will still contain "undefined or null", which makes 'b' do value operations instead of integer operations.

Improves knockout from 3500 to 3800 in a quick test.

Comment 1

[Hannes Verschore [:h4writer]]

Attachment: WIP

This alters how we construct AndOr in IonBuilder. So all "detectAndOr" tests will need to get adjusted.

Comment 2

[Hannes Verschore [:h4writer]]

function test(x) {
    var t = x || 1
    return Math.min(t, 1)
}

for (var i=0; i<100000000; i++) {
    test(undefined)
    test(2)
}

Before: 0m1.783s
After: 0m0.178s

Comment 3

[Hannes Verschore [:h4writer]]

Attachment: Part 1: Improve types at && ||

This adjust the logic in how we create && || in IonBuilder. It now has two branches and a join block, instead of 1 branch and a join block. That extra branch is needed for when we want to improve the types at that branch.

This has some nice improvements:
- MaybeFoldAndOrBlock can get removed, since it now has the same structure as MaybeFoldConditionBlock !
- Doing "a && a.test()" is now much faster, since we know 'undefined' cannot go to a.test().
- Also "var t = x || 1" will have a smaller typeset with 'undefined' removed.

There is one caveat:
MaybeFoldAndOrBlock only works if the phiblock has only 1 phi in it. The 'improve types at branches' infrastructure can introduce an extra phi and disable the folding. This can get fixed. I will do that in part 2.

Comment 4

[Brian Hackett [Laid off!]]

Comment on attachment 8576668 [details] [diff] [review]
Part 1: Improve types at && ||

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

::: js/src/jit/IonAnalysis.cpp
@@ +313,1 @@
>      }

These braces are unnecessary now.

::: js/src/jit/IonBuilder.cpp
@@ +2661,4 @@
>          return ControlStatus_Error;
>  
> +    // End the rhs.
> +    current->end(MGoto::New(alloc(), join));

This looks kind of weird in contrast to the 'End the lhs' part.  Where does the rhs become marked as a predecessor of |join|?

Comment 5

[Hannes Verschore [:h4writer]]

Attachment: Part 2: Allow fixing andor blocks which have MFilterTypeSet

Comment 6

[Brian Hackett [Laid off!]]

Comment on attachment 8579022 [details] [diff] [review]
Part 2: Allow fixing andor blocks which have MFilterTypeSet

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

::: js/src/jit/IonAnalysis.cpp
@@ +109,5 @@
> +        if (operand->isFilterTypeSet() && operand->toFilterTypeSet()->input() == a)
> +            continue;
> +        return false;
> +    }
> +    return true;

If this is a phi(FilterTypeSet(a),a) then this method will return false, which doesn't seem right and is different from what the above comment says.

@@ +284,5 @@
>      MDefinition *falseResult = phi->getOperand(phiBlock->indexForPredecessor(falseBranch));
>  
>      // OK, we found the desired pattern, now transform the graph.
>  
> +    // Path up phi's that filter their input.

Patch?

@@ +293,5 @@
> +        MOZ_ASSERT(PhiRedudantOrFilters(*iter));
> +
> +        MDefinition *replace = (*iter)->getOperand(0);
> +        if (replace->isFilterTypeSet())
> +            replace = replace->toFilterTypeSet()->input();

If this is a phi(FilterTypeSet(a),FilterTypeSet(a)) then this logic will strip out that FilterTypeSet, which doesn't seem like the right thing to do.

Comment 7

[Hannes Verschore [:h4writer]]

(In reply to Brian Hackett (:bhackett) from comment #6)
> Comment on attachment 8579022 [details] [diff] [review]
> Part 2: Allow fixing andor blocks which have MFilterTypeSet
> 
> Review of attachment 8579022 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/IonAnalysis.cpp
> @@ +109,5 @@
> > +        if (operand->isFilterTypeSet() && operand->toFilterTypeSet()->input() == a)
> > +            continue;
> > +        return false;
> > +    }
> > +    return true;
> 
> If this is a phi(FilterTypeSet(a),a) then this method will return false,
> which doesn't seem right and is different from what the above comment says.

Good catch. I lost this when cleaning the patch before submitting apparently.

> 
> @@ +284,5 @@
> >      MDefinition *falseResult = phi->getOperand(phiBlock->indexForPredecessor(falseBranch));
> >  
> >      // OK, we found the desired pattern, now transform the graph.
> >  
> > +    // Path up phi's that filter their input.
> 
> Patch?

yes

> 
> @@ +293,5 @@
> > +        MOZ_ASSERT(PhiRedudantOrFilters(*iter));
> > +
> > +        MDefinition *replace = (*iter)->getOperand(0);
> > +        if (replace->isFilterTypeSet())
> > +            replace = replace->toFilterTypeSet()->input();
> 
> If this is a phi(FilterTypeSet(a),FilterTypeSet(a)) then this logic will
> strip out that FilterTypeSet, which doesn't seem like the right thing to do.

This is actually what I want to do:

>        MTest a
>         /  \
> Trueblock  FalseBlock

Here a MFilterTypeSet can get added on the true and false block. In the true case, undefined/null e.a. can get removed, in the false case we sometimes can remove the objects. So MPhi(MFilterTypeSet a, MFilterTypeSet a) should get considered.

Maybe I could add an extra test that makes sure the MFiltertypeSets depends on the same MTest?

Comment 8

[Hannes Verschore [:h4writer]]

Attachment: Part 2: Allow fixing andor blocks which have MFilterTypeSet

Comment 9

[Brian Hackett [Laid off!]]

Comment on attachment 8579521 [details] [diff] [review]
Part 2: Allow fixing andor blocks which have MFilterTypeSet

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

::: js/src/jit/IonAnalysis.cpp
@@ +100,5 @@
> +// - phi(a, filtertypeset(a))
> +// => Same semantic as just using a
> +// - phi(filtertypeset(a), filtertypeset(a))
> +// => Same semantic as a, if the phi combines all paths from the control
> +//    instructions that created the filtertypesets.

This comment and function don't make sense to me.

So filtertypeset(a, t) means "this is equivalent to a, except we know its type is in t".  t needs to be a subset of types(a), otherwise the filtertypeset would be weakening type information.  filtertypeset(a, types(a)) is equivalent to a.  phi(filtertypeset(a, t1), filtertypeset(a, t2)) can be simplified to filtertypeset(a, t1 union t2).

Then, phi(a, filtertypeset(a, t1)) is equivalent to phi(filtertypeset(a, types(a)), filtertypeset(a, t1)), which can be simplified to filtertypeset(a, types(a) union t1), which can be simplified to just |a| since t1 is a subset of types(a).  The control instruction that created the filtertypesets doesn't seem relevant.

@@ +323,5 @@
> +        MOZ_ASSERT(IsPhiRedudantFilter(*iter));
> +
> +        MDefinition *replace = (*iter)->getOperand(0);
> +        if (replace->isFilterTypeSet())
> +            replace = replace->toFilterTypeSet()->input();

This still does the wrong thing if this is phi(filtertypeset(a, t), filtertypeset(a, t)), by simplifying it to |a| rather than filtertypeset(a, t)

Comment 10

[Hannes Verschore [:h4writer]]

Attachment: Part 2: Allow fixing andor blocks which have MFilterTypeSet

Updated with the remarks and suggestions which we discussed on irc yesterday

Comment 11

[Brian Hackett [Laid off!]]

Comment on attachment 8579958 [details] [diff] [review]
Part 2: Allow fixing andor blocks which have MFilterTypeSet

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

::: js/src/jit/IonAnalysis.cpp
@@ +93,5 @@
>      }
>      return true;
>  }
>  
> +// Find phi's that are redudant:

no "'"

@@ +99,5 @@
> +// 1) phi(a, a)
> +//     can get replaced by a
> +//
> +// 2) phi(filtertypeset(foo, type1), filtertypeset(foo, type1))
> +//     equals filtertypeset(foo, type1)

Maybe s/foo/a/ for consistency.

::: js/src/jit/MIR.h
@@ +682,5 @@
> +            return true;
> +        }
> +
> +        // Typesets should equal.
> +        return resultTypeSet()->equals(ins->resultTypeSet());

This is a lot of new logic that does similar things to what existing phi operations already do.  Could this be implemented using jit::MergeTypes()?  Something like:

MIRType type = this->type();
TemporaryTypeSet *types = this->resultTypeSet();

if (!MergeTypes(&type, &types, ins->type(), ins->resultTypeSet())
    CrashOrWhatever();

if (type != this->type())
    return false;

if (!!types != !!this->resultTypeSet())
    return false;

if (types && !types->equals(this->resultTypeSet())
    return false;

return true;

It would also be nice if this was a generic utility function instead (like MergeTypes) since there isn't anything phi specific here.  Additionally, it would be fine if IsPhiRedudantFilter just returned true instead of calling this function, if there was a comment describing the loss of type information occurring at that point.

Comment 12

[Hannes Verschore [:h4writer]]

I've added EqualTypes which reuses TypeSetIncludes:
https://hg.mozilla.org/integration/mozilla-inbound/rev/2b873082da2f
https://hg.mozilla.org/integration/mozilla-inbound/rev/72e99bad5294

Comment 13

[Ryan VanderMeulen [:RyanVM]]

Backed out for being the likely cause of intermittent browser_vimemacs.js crashes.
https://hg.mozilla.org/integration/mozilla-inbound/rev/893a00744491

https://treeherder.mozilla.org/logviewer.html#?job_id=8047471&repo=mozilla-inbound
https://treeherder.mozilla.org/logviewer.html#?job_id=8046485&repo=mozilla-inbound
https://treeherder.mozilla.org/logviewer.html#?job_id=8043037&repo=mozilla-inbound

Comment 14

[Hannes Verschore [:h4writer]]

Reproduced the browser_vimemacs.js crashes and fixed the issue:
https://hg.mozilla.org/integration/mozilla-inbound/rev/72747e5f217f
https://hg.mozilla.org/integration/mozilla-inbound/rev/20550635935b

Comment 15

[Guilherme Lima]

Seems like this patch is the resposible for a few regressions on AWFY (2% on richards, 20% on gaussian-blur, 6% on shumway-crypto, 14% on misc-bugs-608733-interpreter, 5% on misc-bugs-608733-trace-compiler)

Comment 16

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/72747e5f217f
https://hg.mozilla.org/mozilla-central/rev/20550635935b

Comment 17

[Jan de Mooij [:jandem]]

NI for comment 15.

Comment 18

[Hannes Verschore [:h4writer]]

Already looking into it. Part 3 will solve it. "DetectAndOrStructure" is now faulty and as a result we aren't improving types at andor anymore.

Comment 19

[Hannes Verschore [:h4writer]]

Also this is recorded as:
http://arewefastyet.com/regressions/#/regression/87360

(still need to look why the 'misc' regressions weren't detected. Also on my todolist)

Comment 20

[Hannes Verschore [:h4writer]]

Attachment: WIP part 3

Hmm that didn't fix the octane-richards issues. Looking further.

Comment 21

[Hannes Verschore [:h4writer]]

Attachment: Part 4: Fold the redudant OR compare away.

There was a difference with "MaybeFoldConditionBlock" and "MaybeFoldAndOrBlock". As a result we didn't eliminate the redudant compare which we used to do.

Comment 22

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e0d7904d5d21

Comment 23

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/e0d7904d5d21

Comment 24

[Hannes Verschore [:h4writer]]

Confirmed fixes the regressions: http://arewefastyet.com/regressions/#/regression/172011