1064543 - DCE branches where true/false branch behave similar.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect, P5)

Description

[Hannes Verschore [:h4writer]]

When we have a branch where the body of the if/else branch have only NOPs or if the contents are not fallible (i.e. no guards) and no uses, we can just remove the test and the compare before.

We have this already on some benchmarks, but with bug 1064537 we have this on a hot path. If we remove the compare in there we will have a 10% improvement.

Comment 1

[Hannes Verschore [:h4writer]]

Does this optimization fit somewhere in DCE or UCE? It feels like UCE, since we can just remove one of the two paths of a branch (at random :D).  Or DCE since the result is that we can remove the MTest and MCompare going before this branch.

Comment 2

[Dan Gohman [:sunfish]]

I think once bug 1029830 lands (hopefully soon!), this will fit in MTest::foldsTo, as it will also enable cascading optimizations there. My only concern is that we don't want to do too many compile-time-expensive things in foldsTo methods, but perhaps this one is not too bad.

Comment 3

[Johannes Schulte [:jschulte]]

Attachment: Don't emit FilterTypeSet when unnecessary

In raytrace we often insert MFilterTypeSet into otherwise empty branches, although it seems like they don't add new information. This prohibits the optimization in this bug and others (this patch alone is ~2% win on raytrace). Is this a reasonable approach to handle these cases?

Comment 4

[Johannes Schulte [:jschulte]]

Attachment: Fold MTest

With bug 1176230 this results in a ~5% win on raytrace. I also tried just re-running GVN, which didn't have any performance impact. Not sure, what's more elegant and whether the overall approach is sound?

Comment 5

[Hannes Verschore [:h4writer]]

Comment on attachment 8711065 [details] [diff] [review]
Don't emit FilterTypeSet when unnecessary

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

Looking at this, I remember putting a similar check, since I didn't want to have MFilterTypeSets for no reason:
https://dxr.mozilla.org/mozilla-central/source/js/src/jit/IonBuilder.cpp#3534

Is this check not good enough and missing some things?

Comment 6

[Johannes Schulte [:jschulte]]

The definitions, which are tested in raytrace often have no typeSet, just their type. Based on this type, oldType is calculated.

Comment 7

[Hannes Verschore [:h4writer]]

Comment on attachment 8711067 [details] [diff] [review]
Fold MTest

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

I haven't looked fully at the code yet, but I have a question.

If you compare if the successors of MTest are all equal. Did you also check that the MPhi's are redudent?

>          [block1]
>          ...
>          MTest block2 block3
> 
> [block2]            [block3]
> MGoto block 4       MGoto block4
> 
>          [block6]
>          MPhi value1, value2
>          ...

We can only remove block2 and block3 if the MPhi has the same operand for every block.
Else removing it would be wrong.

Now I do think that DCE and UCE might already do that.
Might be good to check/test that.

Comment 8

[Hannes Verschore [:h4writer]]

(In reply to Johannes Schulte [:jschulte] from comment #6)
> The definitions, which are tested in raytrace often have no typeSet, just
> their type. Based on this type, oldType is calculated.

In that case, can you improve the check there that it also checks if the type equals the mirType from the TemporaryTypeSet?

Comment 9

[Johannes Schulte [:jschulte]]

Attachment: Don't emit FilterTypeSet when unnecessary

Sure. Is this better?

Comment 10

[Johannes Schulte [:jschulte]]

(In reply to Hannes Verschore [:h4writer] from comment #7)
> I haven't looked fully at the code yet, but I have a question.
> 
> If you compare if the successors of MTest are all equal. Did you also check
> that the MPhi's are redudent?
I think I don't really understand what you mean, could you explain a bit more? We only fold the test, if the successor of the branches has no phis. Are there any other blocks, whose MPhi's I have to take in account?
> 
> >          [block1]
> >          ...
> >          MTest block2 block3
> > 
> > [block2]            [block3]
> > MGoto block 4       MGoto block4
> > 
> >          [block6]
> >          MPhi value1, value2
> >          ...
> 
> We can only remove block2 and block3 if the MPhi has the same operand for
> every block.
> Else removing it would be wrong.
> 
> Now I do think that DCE and UCE might already do that.
> Might be good to check/test that.
Yes, MPhi::operandIfRedundant should do that.

Comment 11

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8711067 [details] [diff] [review]
Fold MTest

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

::: js/src/jit/ValueNumbering.cpp
@@ +1018,4 @@
>                  return false;
>              ++numVisited;
> +            if (revisitBlock) {
> +                for (iter--, numVisited--; *iter != revisitBlock; iter--) {

I would recommend against that, as this function is currently doing a lot of thing, and I do not expect it to be able to reenter safely.

Have you tried to use the rerun_ flag instead?

Comment 12

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #7)
> Comment on attachment 8711067 [details] [diff] [review]
> Fold MTest
> 
> Review of attachment 8711067 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> I haven't looked fully at the code yet, but I have a question.
> 
> If you compare if the successors of MTest are all equal. Did you also check
> that the MPhi's are redudent?

Checking successorWithPhi is a way to check that the next block has an empty Phi list.

Comment 13

[Hannes Verschore [:h4writer]]

Comment on attachment 8711336 [details] [diff] [review]
Don't emit FilterTypeSet when unnecessary

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

::: js/src/jit/IonBuilder.cpp
@@ +3531,5 @@
>      if (type->unknown())
>          return true;
>  
>      if (subject->resultTypeSet() && type->equals(subject->resultTypeSet()))
>          return true;

This line does what you want to accomplish, if there is a resultTypeSet.

@@ +3534,5 @@
>      if (subject->resultTypeSet() && type->equals(subject->resultTypeSet()))
>          return true;
>  
> +    if (subject->type() == type->getKnownMIRType())
> +        return true;

1) Now this newly added line should as a result only be done if resultTypeSet is not set!

2) MIRType is less precise than a TemporaryTypeSet.
e.g.:
MIRType_Object VS TemporaryTypeSet <specific object>
MIRType_Value VS TemporaryTypeSet <boolean, integer, string>
...

Therefore your newly added line might be a bit too invasive.

I think a better way would be to create a TemporaryTypSet constructor with MIRType as input.
And let it set the correct types in that TemporaryTypeSet and afterward call "equals" on it.
If that makes sense for you?

Comment 14

[Johannes Schulte [:jschulte]]

Attachment: Don't emit FilterTypeSet when unnecessary

What do you think about this approach?

Comment 15

[Johannes Schulte [:jschulte]]

Attachment: Fold MTest

As I said, using the rerun-flag has no measurable impact compared to revisiting, so I agree, that we should go this way.

Comment 16

[Hannes Verschore [:h4writer]]

Comment on attachment 8715868 [details] [diff] [review]
Don't emit FilterTypeSet when unnecessary

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

Looks good!

::: js/src/jit/IonBuilder.cpp
@@ +3530,5 @@
>  {
>      if (type->unknown())
>          return true;
>  
> +    if (subject->resultTypeSet()) {

Can you add a small comment on what this does?
E.g.: Don't emit MFilterTypeSet if it doesn't improve the typeset.

::: js/src/vm/TypeInference.h
@@ +661,5 @@
>      }
>  
> +    TemporaryTypeSet(LifoAlloc* alloc, jit::MIRType type)
> +      : TemporaryTypeSet(alloc, PrimitiveType(ValueTypeFromMIRType(type)))
> +    {}

Awesome.
I think there is only 1 missing item:
1) This will fail on MIRType_Value

Comment 17

[Johannes Schulte [:jschulte]]

Attachment: Don't emit FilterTypeSet when unnecessary

Thanks for the quick feedback.

Comment 18

[Hannes Verschore [:h4writer]]

Thanks! Sorry for the delay. I was on holiday last week and now trying to iterate my backlog.

Comment 19

[Hannes Verschore [:h4writer]]

Comment on attachment 8715869 [details] [diff] [review]
Fold MTest

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

Good idea and looks very clean already. I only have some small tips to improve it.

First of all (not required).
Can you split the foldsTo function into:
MTest:foldsDoubleNegation
MTest:foldsConstant
MTest:foldsTypes
MTest:foldsNeedlessControlFlow
Just seems a bit clearer.

::: js/src/jit/MIR.cpp
@@ +435,5 @@
> +    }
> +
> +    MBasicBlock* successor = ifTrue()->numSuccessors() == 1 ? ifTrue()->getSuccessor(0) : nullptr;
> +    if (ifFalse()->numSuccessors() != 1 || ifFalse()->getSuccessor(0) != successor)
> +        return this;

can't we change this in:

if (ifTrue()->numSuccessors() != 1 || ifFalse()->numSuccessors() != 1)
    return this;
if (ifTrue()->getSuccessor(0) != ifFalse()->getSuccessor(0))
    return this;

@@ +441,5 @@
> +    if (ifTrue()->successorWithPhis())
> +        return this;
> +
> +    successor->addPredecessorWithoutPhis(block());
> +    return MGoto::New(alloc, successor);

Can't we just do:
- return MGoto::New(alloc, ifTrue());

Just take one of the two successors at random. They don't make a difference.
And the instructions still in the block will get DCE eventually, since they don't have any use.
Then we don't have to use "addPredecessorWithoutPhis".

Comment 20

[Johannes Schulte [:jschulte]]

Attachment: Don't emit FilterTypeSet when unnecessary

https://treeherder.mozilla.org/#/jobs?repo=try&revision=00916d57156b

Comment 21

[Johannes Schulte [:jschulte]]

Only checkin "Don't emit FilterTypeSet when unnecessary", please.

Comment 22

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/017122d17ff0

Comment 23

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/017122d17ff0

Comment 24

[Johannes Schulte [:jschulte]]

Attachment: Fold MTest

Let's land this. Rebased and applied comments.

Comment 25

[Hannes Verschore [:h4writer]]

Comment on attachment 8800865 [details] [diff] [review]
Fold MTest

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

\0/, thank you for moving this forward again!
Can you open a new bug for this? That way this bug report doesn't track two patches ranging different firefox versions.