Closed Bug 1138881 Opened 5 years ago Closed 5 years ago

Improve types at AndOr

Categories

(Core :: JavaScript Engine: JIT, defect)

x86_64
Linux
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla40
Tracking Status
firefox40 --- fixed

People

(Reporter: h4writer, Assigned: h4writer)

References

(Blocks 1 open bug)

Details

Attachments

(4 files, 3 obsolete files)

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.
Blocks: 1118938
Attached patch WIP (obsolete) — Splinter Review
This alters how we construct AndOr in IonBuilder. So all "detectAndOr" tests will need to get adjusted.
Assignee: nobody → hv1989
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
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.
Attachment #8571904 - Attachment is obsolete: true
Attachment #8576668 - Flags: review?(bhackett1024)
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|?
Attachment #8576668 - Flags: review?(bhackett1024) → review+
Attachment #8579022 - Flags: review?(bhackett1024)
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.
Attachment #8579022 - Flags: review?(bhackett1024)
(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?
Attachment #8579022 - Attachment is obsolete: true
Attachment #8579521 - Flags: review?(bhackett1024)
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)
Attachment #8579521 - Flags: review?(bhackett1024)
Updated with the remarks and suggestions which we discussed on irc yesterday
Attachment #8579521 - Attachment is obsolete: true
Attachment #8579958 - Flags: review?(bhackett1024)
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.
Attachment #8579958 - Flags: review?(bhackett1024) → review+
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)
https://hg.mozilla.org/mozilla-central/rev/72747e5f217f
https://hg.mozilla.org/mozilla-central/rev/20550635935b
Status: NEW → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla40
NI for comment 15.
Flags: needinfo?(hv1989)
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.
Flags: needinfo?(hv1989)
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)
Attached patch WIP part 3Splinter Review
Hmm that didn't fix the octane-richards issues. Looking further.
There was a difference with "MaybeFoldConditionBlock" and "MaybeFoldAndOrBlock". As a result we didn't eliminate the redudant compare which we used to do.
Attachment #8587461 - Flags: review?(bhackett1024)
Attachment #8587461 - Flags: review?(bhackett1024) → review+
Depends on: 1153153
You need to log in before you can comment on or make changes to this bug.