1031396 - GVN misses DCE when an MDefinition is used multiple times by the same MNode

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Dan Gohman [:sunfish]]

When GVN deletes an MNode, it wants to walk up the node's use-def subgraph and delete definitions that become dead as a result. However, this is tricky, because the primary methods for removing instructions and phis, MBasicBlock::discardAt and MBasicBlock::discardPhiAt, clear the operand list of the definition being removed. If we examine the operand list before removing the node, the operands aren't dead yet, and if we examine it after, the operands aren't available anymore.

GVN partially works around this by scanning the operand list first, and using the WillBecomeDead function, which tests for a node having exactly one use. This doesn't catch the case where a definition is referred to multiple times by the same node.

One way to fix this would be to make WillBecomeDead check whether all the uses are from the same node.

Comment 1

[Ting-Yuan Huang]

I'm not sure but it looks like that |deadDefs_| can be changed to a queue and the deadness check can be postponed to where the def or phi are dequeued. The semantics of |deadDefs_| would then be changed that it no longer holds nodes surely to be deleted; Instead, it holds candidates which may be deleted or not. In this way, a def/phi can be deleted while its operands remain retrievable on the queue so |WillBecomeDead| wouldn't be needed anymore.

Would you mind if I work on this?

Comment 2

[Dan Gohman [:sunfish]]

I believe your idea would work, and would be a a simple and effective fix.

However, I've been thinking about how this code will evolve; I anticipate pulling functions like deleteDefsRecursively out into utility functions that can be used from other parts of the optimizer. The InWorklist flag is used in many places for many things, so it'd be nice to avoid it here. We can do this by having pushDeadInsOperands call discardOperand on each operand as it iterates. Then create a version of MBasicBlock::discard that just removes the instruction. Instead of discarding the operands itself, it would just assert that the operands are already discarded.

Does this make sense? You're welcome to work on this. If you have any questions or there's anything I can help with, feel free to ask here in this bug, or on IRC (irc.mozillla.org, #ionmonkey).

Comment 3

[Ting-Yuan Huang]

Attachment: bug1031396.patch

Yes, it looks better. Here is a patch implemented in the way you suggested. It discards/removes operands in pushDead{Ins,Phi}Operands() one after another so the operands can be deleted at most once, without relying the InWorklist flag.

As for test cases, may I know how to write a test to ensure that an optimization pass is effective? I mean, tests are good at verifying correctness but how does it tell if an optimization is effective or not?

Comment 4

[Dan Gohman [:sunfish]]

Comment on attachment 8460068 [details] [diff] [review]
bug1031396.patch

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

(In reply to Ting-Yuan Huang from comment #3)
> Created attachment 8460068 [details] [diff] [review]
> bug1031396.patch
> 
> Yes, it looks better. Here is a patch implemented in the way you suggested.
> It discards/removes operands in pushDead{Ins,Phi}Operands() one after
> another so the operands can be deleted at most once, without relying the
> InWorklist flag.

Looks good! Just a few minor comments below.

> As for test cases, may I know how to write a test to ensure that an
> optimization pass is effective? I mean, tests are good at verifying
> correctness but how does it tell if an optimization is effective or not?

I have started working on a way to do this. js/src/jsapi-tests/testJitFoldsTo.cpp is a unit test which constructs a minimal standalone MIRGraph, runs GVN, and tests that it performed a specific optimization. You could factor out the MinimalFunc class into a header file so that it can be shared by multiple tests, and then create a new test in that directory which uses it to test the new optimization.

In the patch description:
> Discard an instruction or phi in 2 phases.

I believe this is still describing the previous idea for this patch.

::: js/src/jit/MIR.h
@@ +225,5 @@
>          getUseFor(index)->discardProducer();
>      }
>  
> +#if DEBUG
> +    bool operandDiscarded(size_t index) {

This function can be const.

::: js/src/jit/ValueNumbering.cpp
@@ +221,5 @@
>  
>  // Assuming phi is dead, push each dead operand of phi not dominated by the phi
>  // to the delete worklist.
>  bool
>  ValueNumberer::pushDeadPhiOperands(MPhi *phi, const MBasicBlock *phiBlock)

With this function now removing phi operands, it'd be nice to rename it. How about discardPhiOperands? It'd also be nice to update its comment to mention that it actually removes operands from the phi in addition to adding them to the deadDefs_ worklist.

@@ +223,5 @@
>  // to the delete worklist.
>  bool
>  ValueNumberer::pushDeadPhiOperands(MPhi *phi, const MBasicBlock *phiBlock)
>  {
> +    // MPhi saves operands in a vector so we iterate reversely.

Instead of "reversely", say "in reverse".

@@ +239,5 @@
>  }
>  
>  // Assuming ins is dead, push each dead operand of ins to the delete worklist.
>  bool
>  ValueNumberer::pushDeadInsOperands(MInstruction *ins)

As with pushDeadPhiOperands, it'd be nice to rename this and update its comment.

Comment 5

[Ting-Yuan Huang]

Attachment: part.1 v2. r=sunfish

(In reply to Dan Gohman [:sunfish] from comment #4)
> I believe this is still describing the previous idea for this patch.

Would "Discard operands one after another so that dead ones are deleted exactly once." be fine?
 
> This function can be const.

Done.

> With this function now removing phi operands, it'd be nice to rename it. How
> about discardPhiOperands? It'd also be nice to update its comment to mention
> that it actually removes operands from the phi in addition to adding them to
> the deadDefs_ worklist.

Done.
 
> Instead of "reversely", say "in reverse".

Done.
 
> As with pushDeadPhiOperands, it'd be nice to rename this and update its
> comment.

Done.

Comment 6

[Ting-Yuan Huang]

Attachment: part.2 testcases

This part.2 patch add a test case to check if the MDefinition in question can be eliminated. It only tests for the case that there are multiple references from MInstructions.

When writing a test case for phis, I realized that it's not possible that a MDefinition appears twice in a phi input list. Is that correct?

Comment 7

[Ting-Yuan Huang]

Attachment: part.2 testcases

Sorry, the previous patch failed the style checks. This one should be OK:
https://tbpl.mozilla.org/?tree=Try&rev=8291ee2544c7

Comment 8

[Dan Gohman [:sunfish]]

Comment on attachment 8462368 [details] [diff] [review]
part.2 testcases

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

Looks good! Thanks for doing this. Just a few minor comments below, and I'd like to rename testJitGVN.h to something that isn't GVN-specific, since only the runGVN() part is GVN-specific, and MinimalFunc should be useful for testing other parts of the optimizer as well. How about testJitMinimalFunc.h?

::: js/src/jsapi-tests/testJitDCEinGVN.cpp
@@ +15,5 @@
> +
> +BEGIN_TEST(testJitDCEinGVN_ins)
> +{
> +    using namespace js;
> +    using namespace js::jit;

Please move these using declarations out to file scope. This file will only ever contain Jit unit tests, and tests are already somewhat verbose, so it's nice to keep per-test clutter down.

::: js/src/jsapi-tests/testJitFoldsTo.cpp
@@ +16,4 @@
>  BEGIN_TEST(testJitFoldsTo_DivReciprocal)
>  {
> +    using namespace js;
> +    using namespace js::jit;

Same here.

@@ +46,5 @@
>  
>  BEGIN_TEST(testJitFoldsTo_NoDivReciprocal)
>  {
> +    using namespace js;
> +    using namespace js::jit;

Same here.

::: js/src/jsapi-tests/testJitGVN.h
@@ +13,5 @@
> +#include "jit/ValueNumbering.h"
> +
> +namespace js {
> +namespace jit {
> +namespace {

Since this is now in a header file, it shouldn't use an anonymous namespace.

Comment 9

[Dan Gohman [:sunfish]]

> When writing a test case for phis, I realized that it's not possible that a
> MDefinition appears twice in a phi input list. Is that correct?

No; it can happen. If all inputs are the same, the phi will be eliminated. However, if the phi has more than 2 inputs and one of them is different, then the phi won't be eliminated.

Comment 10

[Dan Gohman [:sunfish]]

(In reply to Ting-Yuan Huang from comment #5)
> Created attachment 8462322 [details] [diff] [review]
> part.1 v2. r=sunfish
> 
> (In reply to Dan Gohman [:sunfish] from comment #4)
> > I believe this is still describing the previous idea for this patch.
> 
> Would "Discard operands one after another so that dead ones are deleted
> exactly once." be fine?

"exactly once" seems to emphasize that we have to be careful not to delete definitions multiple times, but that's not the main concern here, as we still have to check IsDead before we can delete anything.

The key thing that's happening here is that we're checking for definitions becoming dead after discarding each operand because the simplest time to check when a definition is dead is when its last use is discarded.

Comment 11

[Ting-Yuan Huang]

Attachment: part.1 v3

(In reply to Dan Gohman [:sunfish] from comment #9)
> > When writing a test case for phis, I realized that it's not possible that a
> > MDefinition appears twice in a phi input list. Is that correct?
> 
> No; it can happen. If all inputs are the same, the phi will be eliminated.
> However, if the phi has more than 2 inputs and one of them is different,
> then the phi won't be eliminated.

I had been thinking that it's a convention that each input of phi correspond to a unique predecessor of the phi's containing block, so that there are no repetitions in the input list:
http://dxr.mozilla.org/mozilla-central/source/js/src/jit/ValueNumbering.cpp?from=valuenumbering.cpp&case=true#239

Seems that this is not always true and has to be remedied.

So there are 2 diffs between the v2 and v3 patch:

1. The dominance is checked against op->block(), rather than phiBlock->getPredecessor(o), where o is just a number iterating through the phi input list.
2. Changed the commit message to:
Check the deadness of operands after discarding/removing them from dead instructions/phis.

Would you mind to review it again?

Comment 12

[Ting-Yuan Huang]

Attachment: part.2 v2, testcases

Thanks for reviewing this! I addressed the problems you pointed out and added a test for phi nodes. Would you mind to review the newly added phi test?

(In reply to Dan Gohman [:sunfish] from comment #8)
> Review of attachment 8462368 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Looks good! Thanks for doing this. Just a few minor comments below, and I'd
> like to rename testJitGVN.h to something that isn't GVN-specific, since only
> the runGVN() part is GVN-specific, and MinimalFunc should be useful for
> testing other parts of the optimizer as well. How about testJitMinimalFunc.h?
>

Done.
 
> ::: js/src/jsapi-tests/testJitDCEinGVN.cpp
> @@ +15,5 @@
> > +
> > +BEGIN_TEST(testJitDCEinGVN_ins)
> > +{
> > +    using namespace js;
> > +    using namespace js::jit;
> 
> Please move these using declarations out to file scope. This file will only
> ever contain Jit unit tests, and tests are already somewhat verbose, so it's
> nice to keep per-test clutter down.
> 

I found this in some other files and noticed that the tests are built in the unified build, that is, the .cpps are included in a file. However, there are also many files
states the using directive in the outer most scope. Anyway, I thinks both would be fine so this patch conforms to what you suggested.

> ::: js/src/jsapi-tests/testJitFoldsTo.cpp
> @@ +16,4 @@
> >  BEGIN_TEST(testJitFoldsTo_DivReciprocal)
> >  {
> > +    using namespace js;
> > +    using namespace js::jit;
> 
> Same here.
> 

Done.

> @@ +46,5 @@
> >  
> >  BEGIN_TEST(testJitFoldsTo_NoDivReciprocal)
> >  {
> > +    using namespace js;
> > +    using namespace js::jit;
> 
> Same here.
> 

Done.

> ::: js/src/jsapi-tests/testJitGVN.h
> @@ +13,5 @@
> > +#include "jit/ValueNumbering.h"
> > +
> > +namespace js {
> > +namespace jit {
> > +namespace {
> 
> Since this is now in a header file, it shouldn't use an anonymous namespace.

Done.

Comment 13

[Dan Gohman [:sunfish]]

(In reply to Ting-Yuan Huang from comment #11)
> Created attachment 8463202 [details] [diff] [review]
> part.1 v3
> 
> (In reply to Dan Gohman [:sunfish] from comment #9)
> > > When writing a test case for phis, I realized that it's not possible that a
> > > MDefinition appears twice in a phi input list. Is that correct?
> > 
> > No; it can happen. If all inputs are the same, the phi will be eliminated.
> > However, if the phi has more than 2 inputs and one of them is different,
> > then the phi won't be eliminated.
> 
> I had been thinking that it's a convention that each input of phi correspond
> to a unique predecessor of the phi's containing block, so that there are no
> repetitions in the input list:
> http://dxr.mozilla.org/mozilla-central/source/js/src/jit/ValueNumbering.
> cpp?from=valuenumbering.cpp&case=true#239

It's true that each input of a phi corresponds to a unique incoming edge of the phi's containing block. However, the inputs to a phi need not be defined in the actual predecessor blocks. For example, in code like this:

  r = foo();
  if (x == 0) {
     t = r;
  } else if (x < 3) {
     t = 0;
  } else {
     t = r;
  }
  use(t);

There would be a phi for t at the bottom which would have inputs (r, 0, r).

> Seems that this is not always true and has to be remedied.
> 
> So there are 2 diffs between the v2 and v3 patch:
> 
> 1. The dominance is checked against op->block(), rather than
> phiBlock->getPredecessor(o), where o is just a number iterating through the
> phi input list.

The change in your patch is indeed an improvement over the current code, as it would enable us to continue deleting in the case where op->block() dominates phiBlock and phiBlock dominates phi->getPredecessor(o).

> 2. Changed the commit message to:
> Check the deadness of operands after discarding/removing them from dead
> instructions/phis.

This sounds fine.

Comment 14

[Dan Gohman [:sunfish]]

Comment on attachment 8463202 [details] [diff] [review]
part.1 v3

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

This looks good!

Comment 15

[Dan Gohman [:sunfish]]

Comment on attachment 8463210 [details] [diff] [review]
part.2 v2, testcases

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

::: js/src/jsapi-tests/testJitDCEinGVN.cpp
@@ +77,5 @@
> +    MPhi *x = MPhi::New(func.alloc);
> +    x->addInputSlow(c1);
> +    x->addInputSlow(c1); // Test if multiple phi inputs can be handled.
> +    x->addInputSlow(c1); // Test if multiple phi inputs can be handled.
> +    x->addInputSlow(c3);

This adds more inputs to the phi than there are predecessor edges to the phi's block. Even if this currently works, I'd prefer to avoid passing invalid IL into GVN. Can you add some extra blocks so that the phi block has the same number of predecessors as the phi has inputs?

Comment 16

[Ting-Yuan Huang]

Attachment: part.2 v3, testcases

> This adds more inputs to the phi than there are predecessor edges to the
> phi's block. Even if this currently works, I'd prefer to avoid passing
> invalid IL into GVN. Can you add some extra blocks so that the phi block has
> the same number of predecessors as the phi has inputs?

Thanks. To make the test more natural, the test for phi was rewritten by modeling this:

 if (p) {
   x = 1.0;
   y = 3.0;
 } else if (q) {
   x = 2.0;
   y = 4.0;
 } else {
   x = 1.0;
   y = 5.0;
 }
 x = phi(1.0, 2.0, 1.0);
 y = phi(3.0, 4.0, 5.0);
 z = x * y;
 return y;

Comment 17

[Dan Gohman [:sunfish]]

Comment on attachment 8464006 [details] [diff] [review]
part.2 v3, testcases

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

Looks good! Thanks for adding these tests!

Comment 18

[Ting-Yuan Huang]

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

Comment 19

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4f6bb4623531
https://hg.mozilla.org/integration/mozilla-inbound/rev/a42af29d7dc2

Comment 20

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/4f6bb4623531
https://hg.mozilla.org/mozilla-central/rev/a42af29d7dc2