Closed Bug 1064543 Opened 6 years ago Closed 4 years ago

DCE branches where true/false branch behave similar.

Categories

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

defect

Tracking

()

RESOLVED FIXED
mozilla47

People

(Reporter: h4writer, Assigned: jschulte)

References

Details

(Keywords: perf)

Attachments

(2 files, 6 obsolete files)

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.
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.
Flags: needinfo?(sunfish)
Blocks: 1064251
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.
Flags: needinfo?(sunfish)
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?
Attachment #8711065 - Flags: feedback?(hv1989)
Attached patch Fold MTest (obsolete) — Splinter Review
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?
Attachment #8711067 - Flags: feedback?(sunfish)
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?
Attachment #8711065 - Flags: feedback?(hv1989)
The definitions, which are tested in raytrace often have no typeSet, just their type. Based on this type, oldType is calculated.
Flags: needinfo?(hv1989)
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.
Attachment #8711067 - Flags: feedback?(sunfish)
(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?
Flags: needinfo?(hv1989)
Sure. Is this better?
Attachment #8711065 - Attachment is obsolete: true
Attachment #8711336 - Flags: feedback?(hv1989)
(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 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?
(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 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?
Attachment #8711336 - Flags: feedback?(hv1989)
Assignee: nobody → j_schulte
What do you think about this approach?
Attachment #8711336 - Attachment is obsolete: true
Attachment #8715868 - Flags: feedback?(hv1989)
Attached patch Fold MTest (obsolete) — Splinter Review
As I said, using the rerun-flag has no measurable impact compared to revisiting, so I agree, that we should go this way.
Attachment #8711067 - Attachment is obsolete: true
Attachment #8715869 - Flags: feedback?(hv1989)
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
Attachment #8715868 - Flags: feedback?(hv1989) → feedback+
Thanks for the quick feedback.
Attachment #8715868 - Attachment is obsolete: true
Attachment #8717606 - Flags: review?(hv1989)
Attachment #8717606 - Flags: review?(hv1989) → review+
Thanks! Sorry for the delay. I was on holiday last week and now trying to iterate my backlog.
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".
Attachment #8715869 - Flags: feedback?(hv1989) → feedback+
Only checkin "Don't emit FilterTypeSet when unnecessary", please.
Keywords: perf
Priority: -- → P5
Attached patch Fold MTestSplinter Review
Let's land this. Rebased and applied comments.
Attachment #8715869 - Attachment is obsolete: true
Attachment #8800865 - Flags: review?(hv1989)
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.
Attachment #8800865 - Flags: review?(hv1989) → review+
Depends on: 1311801
Status: NEW → RESOLVED
Closed: 4 years ago
Keywords: leave-open
Resolution: --- → FIXED
Target Milestone: --- → mozilla47
You need to log in before you can comment on or make changes to this bug.