Fuse compare with branch at graph building time.

Fuse compare with branch at graph building time.
Committed: https://code.google.com/p/dart/source/detail?r=9762

[Kevin Millikin (Google), 2012-07-19 12:28:05]

My comments are all high-level ones---I agree that this still needs some
improvement.  As a step in the right direction, it LGTM to commit.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/flow_gr...
File runtime/vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/flow_gr...
runtime/vm/flow_graph_builder.cc:246: // TODO(srdjan): This code is clumsy. Try
to skip allocation of ComparisonComp
A way to do this is to implement TestGraphVisitor::ReturnComputation to inspect
the computation and if it matches the pattern add the branch instead (when
!FLAG_enable_type_checks, I suppose).

We would lose our handling of negation, but that can work too: negation in a
test context is just flipping the labels.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/flow_gr...
runtime/vm/flow_graph_builder.cc:269: compare_instr =
compare_instr->previous()->AsBind();
I guess previous() is non-NULL because boolean negate has an input operand and
we always materialize constants so the operand is always in the instruction
stream before the negate.

I'm a bit uncomfortable relying on that --- the graph is only partly constructed
so assuming too much about it constrains us.  (I'm actually uncomfortable
rewriting the graph this way during construction in general.  My experience is
that it leads to a lot of headaches.)

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
File runtime/vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
runtime/vm/intermediate_language.h:114: class ComparisonComp;
My high level comment is that we should look for a way to get rid of the
distinction between ComparisonComp and BranchInstr.  There is some duplication
there.  Many optimizations (e.g., type specialization) will apply to both of
them.

One idea might be to get rid of ComparisonComp as test+materialize in the
instruction stream.  Instead, there are only branches, and an instruction
ToBoolean(branch) that wraps a branch to go in the instruction stream and is a
definition.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
runtime/vm/intermediate_language.h:594: virtual Token::Kind kind() const = 0;
I would implement this as a member variable in class ComparisonComp instead of a
virtual function.  All (existing) subclasses except EqualityCompareComp already
store it in the instance anyway.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
runtime/vm/intermediate_language.h:1771: instr->set_previous(this);
I see why you did this, but I think we should avoid it.  If set_next() for a
doubly-linked list has the side effect of mutating the previous field of its
argument it's error prone -- you always have to read previous of X before
calling set_next(X).

Before this change, we did not maintain previous pointers during graph
construction but computed them afterwards.  I'd be happy with maintaining them
during graph construction (still not part of set_next), but then we should also
get rid of the computation of previous poitners in BuildGraph.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
runtime/vm/intermediate_language.h:2295: BranchInstr(intptr_t token_pos,
Indentation is weird.

[srdjan, 2012-07-19 15:33:58]

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/flow_gr...
File runtime/vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/flow_gr...
runtime/vm/flow_graph_builder.cc:269: compare_instr =
compare_instr->previous()->AsBind();
On 2012/07/19 12:28:05, kmillikin wrote:
> I guess previous() is non-NULL because boolean negate has an input operand and
> we always materialize constants so the operand is always in the instruction
> stream before the negate.
> 
> I'm a bit uncomfortable relying on that --- the graph is only partly
constructed
> so assuming too much about it constrains us.  (I'm actually uncomfortable
> rewriting the graph this way during construction in general.  My experience is
> that it leads to a lot of headaches.)

Agree.

Added another test:
if (compare_instr->previous() == NULL) return false;

Yes, the AST variations are pretty limited and known. I am also uncomfortable
doing it that way and will fix it. This way is too fragile as it depends too
much on how we exactly generate AST.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
File runtime/vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
runtime/vm/intermediate_language.h:114: class ComparisonComp;
On 2012/07/19 12:28:05, kmillikin wrote:
> My high level comment is that we should look for a way to get rid of the
> distinction between ComparisonComp and BranchInstr.  There is some duplication
> there.  Many optimizations (e.g., type specialization) will apply to both of
> them.
> 
> One idea might be to get rid of ComparisonComp as test+materialize in the
> instruction stream.  Instead, there are only branches, and an instruction
> ToBoolean(branch) that wraps a branch to go in the instruction stream and is a
> definition.

I agree.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
runtime/vm/intermediate_language.h:594: virtual Token::Kind kind() const = 0;
On 2012/07/19 12:28:05, kmillikin wrote:
> I would implement this as a member variable in class ComparisonComp instead of
a
> virtual function.  All (existing) subclasses except EqualityCompareComp
already
> store it in the instance anyway.

Done.

https://chromiumcodereview.appspot.com/10802025/diff/14002/runtime/vm/interme...
runtime/vm/intermediate_language.h:1771: instr->set_previous(this);
On 2012/07/19 12:28:05, kmillikin wrote:
> I see why you did this, but I think we should avoid it.  If set_next() for a
> doubly-linked list has the side effect of mutating the previous field of its
> argument it's error prone -- you always have to read previous of X before
> calling set_next(X).
> 
> Before this change, we did not maintain previous pointers during graph
> construction but computed them afterwards.  I'd be happy with maintaining them
> during graph construction (still not part of set_next), but then we should
also
> get rid of the computation of previous poitners in BuildGraph.

I will avoid it with the better way to construct the fused branch compare.