Fix scheduler to correctly schedule nested diamonds.

Fix scheduler to correctly schedule nested diamonds.

The scheduler rewires control based on the last *control*
node that appears in the schedule of a block. This is not
sufficient to account for dependencies.

This patch adds additional dependencies to floating control
nodes. Given a floating control node A, every non-control
dependency of every node B that depends on A is introduces
as an additional dependency of A.

This allows the scheduler to correctly schedule two
diamonds A, B, if their only correct schedule is to
schedule B into the ifTrue successor in A.

TEST=cctest/test-scheduler/NestedFloatingDiamonds
R=mstarzinger@chromium.org, titzer@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=24561

[sigurds, 2014-09-25 12:07:07]

PTAL

[titzer, 2014-09-25 12:19:24]

https://codereview.chromium.org/602083003/diff/1/src/compiler/scheduler.cc
File src/compiler/scheduler.cc (right):

https://codereview.chromium.org/602083003/diff/1/src/compiler/scheduler.cc#ne...
src/compiler/scheduler.cc:658: one_placed = true;
So this basically matches the first node that is either a floating control node
or has a floating control node as a control dependency.

This is not quite correct because if there is more than one such non-control
node that depends on a floating control node, then they could in fact be pushed
down to different blocks. Placing the merge in one or the other of the blocks
wouldn't dominate the remaining. E.g. suppose there are two phis hanging off the
merge of a floating diamond. Then the two phis can be scheduled independently of
the merge. The merge definitely dominates the phis. That's where it needs to be
placed.

Now that I look at this loop again, you can just return from this method after
the first one is placed (no need to continue processing the block). That will
simplify this condition a bit.

Actually, I am not even sure if we need to return anything from this method now.

https://codereview.chromium.org/602083003/diff/1/src/compiler/verifier.cc
File src/compiler/verifier.cc (right):

https://codereview.chromium.org/602083003/diff/1/src/compiler/verifier.cc#new...
src/compiler/verifier.cc:274: static bool Dominates(Schedule* schedule, Node*
dominator, Node* dominee) {
You should walk up the dominator tree and very the dominator is in that chain.
It's not enough to just have an RPO number that is lower.

[titzer, 2014-09-26 10:44:39]

https://codereview.chromium.org/602083003/diff/1/src/compiler/verifier.cc
File src/compiler/verifier.cc (right):

https://codereview.chromium.org/602083003/diff/1/src/compiler/verifier.cc#new...
src/compiler/verifier.cc:274: static bool Dominates(Schedule* schedule, Node*
dominator, Node* dominee) {
On 2014/09/25 12:19:24, titzer wrote:
> You should walk up the dominator tree and very the dominator is in that chain.
> It's not enough to just have an RPO number that is lower.

BTW can you split this check out into a separate CL and land it? It'd be nice to
have right away.

[sigurds, 2014-09-26 11:35:24]

Your concern was right; we now have unit-tests that expose the failure before
the patch as well as after the patch.

I now propose this changelist. Please take a look and let me know what you
think.

There are really two changes in there. One is the fix to the scheduler, and the
other is a minor fix that prevents unreachable blocks from being generated
(otherwise the new verifier check fails on several tests).

https://codereview.chromium.org/602083003/diff/1/src/compiler/scheduler.cc
File src/compiler/scheduler.cc (right):

https://codereview.chromium.org/602083003/diff/1/src/compiler/scheduler.cc#ne...
src/compiler/scheduler.cc:658: one_placed = true;
On 2014/09/25 12:19:24, titzer wrote:
> So this basically matches the first node that is either a floating control
node
> or has a floating control node as a control dependency.
> 
> This is not quite correct because if there is more than one such non-control
> node that depends on a floating control node, then they could in fact be
pushed
> down to different blocks. Placing the merge in one or the other of the blocks
> wouldn't dominate the remaining. E.g. suppose there are two phis hanging off
the
> merge of a floating diamond. Then the two phis can be scheduled independently
of
> the merge. The merge definitely dominates the phis. That's where it needs to
be
> placed.
> 
> Now that I look at this loop again, you can just return from this method after
> the first one is placed (no need to continue processing the block). That will
> simplify this condition a bit.
> 
> Actually, I am not even sure if we need to return anything from this method
now.

This is a valid point, I added a unit test to expose the faulty behaviour in my
patch:

cctest/test-scheduler/PhisPushedDownToDifferentBranches

https://codereview.chromium.org/602083003/diff/1/src/compiler/verifier.cc
File src/compiler/verifier.cc (right):

https://codereview.chromium.org/602083003/diff/1/src/compiler/verifier.cc#new...
src/compiler/verifier.cc:274: static bool Dominates(Schedule* schedule, Node*
dominator, Node* dominee) {
On 2014/09/25 12:19:24, titzer wrote:
> You should walk up the dominator tree and very the dominator is in that chain.
> It's not enough to just have an RPO number that is lower.

Done.

[sigurds, 2014-09-26 13:43:41]

I addressed the comments from our internal discussion.

[titzer, 2014-10-07 07:48:26]

LGTM

Willing to land as is, but this is pretty yucky.

https://codereview.chromium.org/602083003/diff/60001/src/compiler/scheduler.cc
File src/compiler/scheduler.cc (right):

https://codereview.chromium.org/602083003/diff/60001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:462: if
(OperatorProperties::IsBasicBlockBegin(to->op()) &&
I think this should only be EffectPhi and Phi, and floating_control and
connected_control should be mutually exclusive.

[Michael Starzinger, 2014-10-10 10:49:03]

mstarzinger@chromium.org changed reviewers:
+ mstarzinger@chromium.org

[Michael Starzinger, 2014-10-10 10:49:04]

LGTM.

I haven't done a thorough review. But I am also fine with landing this
(especially the tests and the verification). I will tackle the "yucky-ness" of
this change in the upcoming weeks.

[sigurds, 2014-10-13 13:07:59]

Committed patchset #6 (id:170001) manually as 24561 (presubmit successful).

[sigurds, 2014-10-13 13:08:18]

https://codereview.chromium.org/602083003/diff/60001/src/compiler/scheduler.cc
File src/compiler/scheduler.cc (right):

https://codereview.chromium.org/602083003/diff/60001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:462: if
(OperatorProperties::IsBasicBlockBegin(to->op()) &&
On 2014/10/07 07:48:26, titzer wrote:
> I think this should only be EffectPhi and Phi, and floating_control and
> connected_control should be mutually exclusive.

I'm doing the IsBasicBlockBegin check to make sure to add the additional
dependencies only once per (Effect)Phi.