Implement a branch optimization pass.

Implement a branch optimization pass.

Branch optimization pushes some branches that test the value of a phi
to the predecessor blocks.  This can avoid materializing a boolean
object solely for the purposes of branching on its boolean value.

The optimization is performed after inlinining which creates
opportunities, and before constant propagation, because it exposes
opportunities for unreachable code elimination.

R=vegorov@google.com
BUG=

Committed: https://code.google.com/p/dart/source/detail?r=19682

[Vyacheslav Egorov (Google), 2013-03-06 16:44:22]

lgtm

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/flow_graph_opti...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:4426: BranchInstr*
BranchSimplifier::RewriteBranch(BranchInstr* branch,
I'd call it CloneBranch CloneRewrittenBranch or CloneRewriteBranch or something
to indicate that it actually creates a new branch not changes old one.

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:4544: phi->UnuseAllInputs();
What about old branch? I think it also should do UnuseAllInputs somewhere.

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.cc:1176: return HasUses() ? this : NULL;
I'd really like to see a more generic dead code elimination pass.

[Kevin Millikin (Google), 2013-03-08 10:38:10]

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/flow_graph_opti...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:4426: BranchInstr*
BranchSimplifier::RewriteBranch(BranchInstr* branch,
On 2013/03/06 16:44:22, Vyacheslav Egorov (Google) wrote:
> I'd call it CloneBranch CloneRewrittenBranch or CloneRewriteBranch or
something
> to indicate that it actually creates a new branch not changes old one.

Functional update is the default :)

I'll change it to CloneBranch to satisfy you.

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:4544: phi->UnuseAllInputs();
On 2013/03/06 16:44:22, Vyacheslav Egorov (Google) wrote:
> What about old branch? I think it also should do UnuseAllInputs somewhere.

Sure, I can.  I didn't because it's inputs are known to be phi and a constant in
the same block and the block is being removed from the graph.

I suppose it's safer to do it here in case we match more complicated patterns,
though the ASSERT in the compiler will catch any violation.

What do you think?

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/intermediate_la...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/12540002/diff/2001/runtime/vm/intermediate_la...
runtime/vm/intermediate_language.cc:1176: return HasUses() ? this : NULL;
On 2013/03/06 16:44:22, Vyacheslav Egorov (Google) wrote:
> I'd really like to see a more generic dead code elimination pass.

Me too, but this doesn't really seem like an abuse of Canonicalize to me.

[Kevin Millikin (Google), 2013-03-08 11:14:18]

Committed patchset #3 manually as r19682 (presubmit successful).