Optimize conditional branches that have same true/false targets.

Optimize conditional branches that have same true/false targets.

Branches that have the same true/false target, or where both
target blocks reach the same common join block via empty blocks
can be replaced by a goto to the common join block.

In code like this

var a = unknown();
var b = null;
if (a == null || b == null) {
  ...
}

it eliminates the test (a == null) if b is known to be null. Until now,
the compiler could only eliminate the test for b, if a was known.

R=kmillikin@google.com

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

[Florian Schneider, 2013-09-09 15:47:17]

This is part of the ongoing work to seamlessly inline == operator calls. It
allows the optimizer to eliminate the null-tests for the inputs of an equality
operation, if one of the inputs are known to be 'null'.

[Kevin Millikin (Google), 2013-09-27 11:03:43]

LGTM.  I have some suggested naming improvements.

https://codereview.chromium.org/23549020/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:460:
ConstantPropagator::RemoveRedundantBranches(flow_graph);
Since Optimize and RemoveRedundant go together, I'd just move the redundant
branch elimination into OptimizeBranches.  (Plus, OptimizeBranches is too
generic if you have a separate, descriptively named RemoveRedundantBranches, and
it's confusing to have differently named public RemoveRedundant and private
EliminateRedundant that implements it.  You dodge all those issues by putting
EliminateRedundant inside Optimize).

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:6702: return block->next()->IsGoto()
I swear we have exactly this same function somewhere else.  Maybe in the
compiler when we do empty block elimination?

It could just be a method on the BlockEntry, I think.

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.h (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.h:252: // if (a == null) || (b == null) {
You need more parentheses in the comment :)

https://codereview.chromium.org/23549020/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:964: void
BlockEntryInstr::UnuseAllInstructions() {
The name is a bit off.  We don't use instructions (they use their inputs), so it
doesn't make sense to unuse them.  Maybe ClearAllInstructions?

[srdjan, 2013-09-27 15:44:11]

DBC

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:6707: // Traverses a chain of empty blocks
and return the first
Why only 60 chars per line?
s/return/returns/

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:6730: // where true- and false-target are the
same.
s/target/targets/

[Florian Schneider, 2013-09-30 12:19:23]

https://codereview.chromium.org/23549020/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:460:
ConstantPropagator::RemoveRedundantBranches(flow_graph);
On 2013/09/27 11:03:43, kmillikin wrote:
> Since Optimize and RemoveRedundant go together, I'd just move the redundant
> branch elimination into OptimizeBranches.  (Plus, OptimizeBranches is too
> generic if you have a separate, descriptively named RemoveRedundantBranches,
and
> it's confusing to have differently named public RemoveRedundant and private
> EliminateRedundant that implements it.  You dodge all those issues by putting
> EliminateRedundant inside Optimize).

Done.

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:6702: return block->next()->IsGoto()
On 2013/09/27 11:03:43, kmillikin wrote:
> I swear we have exactly this same function somewhere else.  Maybe in the
> compiler when we do empty block elimination?
> 
> It could just be a method on the BlockEntry, I think.

We have one that deals with blocks after translated out of SSA where it checks
for parallel moves instead of phis. I could add the union of both.

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:6707: // Traverses a chain of empty blocks
and return the first
On 2013/09/27 15:44:11, srdjan wrote:
> Why only 60 chars per line?
> s/return/returns/

Done.

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:6730: // where true- and false-target are the
same.
On 2013/09/27 15:44:11, srdjan wrote:
> s/target/targets/

Done.

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.h (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.h:252: // if (a == null) || (b == null) {
On 2013/09/27 11:03:43, kmillikin wrote:
> You need more parentheses in the comment :)

Less is more :)

Done.

https://codereview.chromium.org/23549020/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:964: void
BlockEntryInstr::UnuseAllInstructions() {
On 2013/09/27 11:03:43, kmillikin wrote:
> The name is a bit off.  We don't use instructions (they use their inputs), so
it
> doesn't make sense to unuse them.  Maybe ClearAllInstructions?

Done.

[Kevin Millikin (Google), 2013-09-30 12:27:40]

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/23549020/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:6702: return block->next()->IsGoto()
Nah, it's not necessary.

[Florian Schneider, 2013-09-30 12:41:41]

Committed patchset #2 manually as r28050 (presubmit successful).