Convert diamond shaped control flow into a single conditional instruction.

Convert diamond shaped control flow into a single conditional instruction.

Adds a IfConverter pass that right now recognizes two simple patterns cond ? 0 : 2^n and cond ? x : x+-1 that can be generated without branches on ia32 and x64 using setcc instruction.

R=fschneider@google.com

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

[Florian Schneider, 2013-04-10 13:59:50]

LGTM.

Please ensure test coverage for both cases: power-of-two and increment by 1.

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

https://codereview.chromium.org/14057004/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3938: // TODO(vegorov): incorporate
nullability information into the lattice.
Maybe check Token::IsEqualityOperator(kind()) even if it only supports equality
right now.

https://codereview.chromium.org/14057004/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4840: BlockEntryInstr* pred1 =
block->PredecessorAt(0);
Why not use the same names as in the comments for all the blocks (ba, bb, bc and
bd)?

https://codereview.chromium.org/14057004/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4857: if
(IfThenElseInstr::Supports(comparison, v1, v2)) {
I think the code becomes simpler with an early return here:

if (!IfThenElseInstr::Supports(comparison, v1, v2)) return;

Then you can get rid of the changed flag, too.

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

https://codereview.chromium.org/14057004/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_ia32.cc:3680: ASSERT((kind_ ==
Token::kEQ_STRICT) || (kind_ == Token::kEQ) ||
ASSERT(Token::IsEqualityOperator(kind_))

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

https://codereview.chromium.org/14057004/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_x64.cc:241: // We need to have zero in EDX on
true_condition.
s/EDX/RDX/

https://codereview.chromium.org/14057004/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_x64.cc:250: __ shll(RDX, Immediate(shift +
kSmiTagSize));
s/shll/shlq

[Vyacheslav Egorov (Google), 2013-04-10 14:51:32]

Thanks you for the review. Comments addressed. Test added. Landing.

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

https://codereview.chromium.org/14057004/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3938: // TODO(vegorov): incorporate
nullability information into the lattice.
On 2013/04/10 13:59:50, Florian Schneider wrote:
> Maybe check Token::IsEqualityOperator(kind()) even if it only supports
equality
> right now.

Done.

https://codereview.chromium.org/14057004/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4840: BlockEntryInstr* pred1 =
block->PredecessorAt(0);
On 2013/04/10 13:59:50, Florian Schneider wrote:
> Why not use the same names as in the comments for all the blocks (ba, bb, bc
and
> bd)?

Changed names in the comment to reflect naming in the code.

https://codereview.chromium.org/14057004/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4857: if
(IfThenElseInstr::Supports(comparison, v1, v2)) {
On 2013/04/10 13:59:50, Florian Schneider wrote:
> I think the code becomes simpler with an early return here:
> 
> if (!IfThenElseInstr::Supports(comparison, v1, v2)) return;
> 
> Then you can get rid of the changed flag, too.
> 

Can't use early return (there is a loop around this code).

Could have used continue but I find inverted conditions hard to read. 

It'll be cool if we were writing compiler in a language with pattern matching,
but alas...

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

https://codereview.chromium.org/14057004/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_ia32.cc:3680: ASSERT((kind_ ==
Token::kEQ_STRICT) || (kind_ == Token::kEQ) ||
On 2013/04/10 13:59:50, Florian Schneider wrote:
> ASSERT(Token::IsEqualityOperator(kind_))

Done.

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

https://codereview.chromium.org/14057004/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_x64.cc:241: // We need to have zero in EDX on
true_condition.
On 2013/04/10 13:59:50, Florian Schneider wrote:
> s/EDX/RDX/

Done.

https://codereview.chromium.org/14057004/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_x64.cc:250: __ shll(RDX, Immediate(shift +
kSmiTagSize));
On 2013/04/10 13:59:50, Florian Schneider wrote:
> s/shll/shlq

Good catch!

[Vyacheslav Egorov (Google), 2013-04-10 15:10:15]

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

[srdjan, 2013-04-10 21:47:30]

dbc

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

https://codereview.chromium.org/14057004/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3955: bool result = (left.raw() ==
right.raw());
Since equality can be overridden, I do not think that you can compute result
unless the constants are of certain types (two smi's, etc). The code in
IfThenElseInstr::Supports limits the possible combination, but if that changes
this code could become invalid. Maybe you want to add asserts for allowed types?

[Vyacheslav Egorov (Google), 2013-04-10 21:51:28]

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

https://codereview.chromium.org/14057004/diff/7001/runtime/vm/flow_graph_opti...
runtime/vm/flow_graph_optimizer.cc:3955: bool result = (left.raw() ==
right.raw());
On 2013/04/10 21:47:30, srdjan wrote:
> Since equality can be overridden, I do not think that you can compute result
> unless the constants are of certain types (two smi's, etc). The code in
> IfThenElseInstr::Supports limits the possible combination, but if that changes
> this code could become invalid. Maybe you want to add asserts for allowed
types?

Agreed, this is fragile. 

The plan is to remove this code and encapsulate all codegeneration and constant
folding of comparisons in the ComparisonInstr which will actually stop being an
actual instruction all together. All current uses of comparisons will be
generated as:

v <- IfThenElse(Comparison(v1, v2) ? true : false)

instead of current

v <- Comparison(v1, v2)