Restrict floating control to minimal control-connected component.

Restrict floating control to minimal control-connected component.

R=jarin@chromium.org
TEST=cctest/test-scheduler/NestedFloatingDiamondWithChain

[Michael Starzinger, 2014-11-25 18:35:42]

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

[Jarin, 2014-12-01 20:56:24]

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
File src/compiler/control-equivalence.h (right):

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:28: // down cycle equivalence for strongly
connected control flow graphs.
Did not quite understand the last sentence, perhaps you could to say "...
reduces to undirected cycle equivalence for..."?

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:30: // The algorithm is based on research by
Johnson, Pearson & Pingali which also
Could you give a more complete citation? (At least the name of the article.)

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:43: //  1) A breath-first backwards traversal
to determine the set of nodes that
typo: breadth

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:127: SetClass(node, recent->recent_class);
I am quite confused here when trying to match the algorithm to the one described
in the paper. Could you make the connection more explicit?

Specifically, I do not see how you handle the capping backedge business here.
(Since you do not do the capping backedges, it appears that you do not even use
the DFS numbers.) Why do not we need it?

I am also missing the edge that is supposed to connect the input and output
version of the node. Could you explain where/how is it encoded?

[Michael Starzinger, 2014-12-02 12:20:34]

Addressed comments. PTAL.

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
File src/compiler/control-equivalence.h (right):

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:28: // down cycle equivalence for strongly
connected control flow graphs.
On 2014/12/01 20:56:24, jarin wrote:
> Did not quite understand the last sentence, perhaps you could to say "...
> reduces to undirected cycle equivalence for..."?

Done.

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:30: // The algorithm is based on research by
Johnson, Pearson & Pingali which also
On 2014/12/01 20:56:24, jarin wrote:
> Could you give a more complete citation? (At least the name of the article.)

Done.

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:43: //  1) A breath-first backwards traversal
to determine the set of nodes that
On 2014/12/01 20:56:24, jarin wrote:
> typo: breadth

Done.

https://codereview.chromium.org/738613005/diff/20001/src/compiler/control-equ...
src/compiler/control-equivalence.h:127: SetClass(node, recent->recent_class);
On 2014/12/01 20:56:24, jarin wrote:
> I am quite confused here when trying to match the algorithm to the one
described
> in the paper. Could you make the connection more explicit?
> 
> Specifically, I do not see how you handle the capping backedge business here.
> (Since you do not do the capping backedges, it appears that you do not even
use
> the DFS numbers.) Why do not we need it?
> 
> I am also missing the edge that is supposed to connect the input and output
> version of the node. Could you explain where/how is it encoded?

Acknowledged.

As discussed offline: The capping backedges are not added yet, I still need to
write test cases that proof that (and why) we need them. As for traversal, I
added a comment that try to explain the implementation. And also I added
references to the algorithm from the paper as hints. Let me know if these
comments improve the situation.

[Jarin, 2014-12-02 12:31:07]

lgtm

[Michael Starzinger, 2014-12-02 15:26:35]

The CQ bit was checked by mstarzinger@chromium.org

[commit-bot: I haz the power, 2014-12-02 15:26:56]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/738613005/80001

[commit-bot: I haz the power, 2014-12-02 15:56:27]

Committed patchset #5 (id:80001)