Refactored FlowGraphBuilder into a separate FlowGraph representation.

Refactored FlowGraphBuilder into a separate FlowGraph representation.


R=kmillikin@google.com
BUG=

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

[zerny-google, 2012-08-15 15:28:10]

There are still many things that can be cleaned but the structure here should be
suitable for continuing with inlining.

[srdjan, 2012-08-15 22:02:46]

Please add flow_graph.{cc,h} to the CL

[zerny-google, 2012-08-16 06:14:40]

Added flow_graph.{h,cc}

[Kevin Millikin (Google), 2012-08-16 08:09:57]

I have a bunch of style comments.  LGTM when they are addressed.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:136: FlowGraph flow_graph(parsed_function);
It's a bit strange (to me) that there is such a thing as an unbuilt graph.  For
some reason I expect something more like:

FlowGraphBuilder builder(...);
FlowGraph* graph = builder.BuildGraph();

Also, I'd put this declaration down closer to its first use (after the
TimerScope).

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:168: // Print flow graph to stdout.
Did we lose a "Before Optimizations:\n" that used to be printed here?

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:169: FlowGraphPrinter printer(parsed_function.function(),
I seems like this constructor could just take the graph as input, but feel free
to make that in a separate cleanup change.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:175: FlowGraphVisualizer
printer(parsed_function.function(),
Also here and most of the constructors below, the graph could be the input.

It's just a bit weird that a class that mutates the graph (e.g.,
FlowGraphOptimizer) does not take the graph itself as an argument.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.cc:57: reverse_postorder_.Add(postorder_[block_count - i -
1]);
I don't think a reversed copy of the other list adds much value.  I wonder if
anyone would complain if we removed it?

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.cc:472: }
There should be one or two lines of whitespace before the closing brace and it
should have a "// namespace dart" end-of-line comment.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph.h (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:8: #include "vm/ast.h"
Are you sure you need to include this?  I can't immediately see why.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:64: void ComputeOrders();
I like the name DiscoverBlocks better.  It seems more central that this is the
unique function that makes the implicit basic-block structure explicit.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:66: const ParsedFunction& parsed_function_;
Member variables should all be at the end of the private: section and grouped
together.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:103: GrowableArray<intptr_t> parent_;
These variables (parent_ and assigned_vars_) should have a comment that they are
used for SSA computation and but not maintained afterward.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:61:
block_order_(flow_graph->reverse_postorder()),
Instead of reading these fields out of the flow graph, it's probably better to
just use the values in the graph.  You can still define convenience accessors in
FlowGraphAllocator.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:518:
ASSERT(flow_graph_->copied_parameter_count() == 0 ||
This assert should have a comment explaining it.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:176: // TODO(vegorov): this field is used only
to call Bailout. Remove when
I don't think the TODO comment is accurate anymore (flow_graph_ is used for more
than calling Bailout).  The comment can be deleted.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_builder.cc:34: :
parsed_function_(flow_graph.parsed_function()),
These can also be stored in the flow graph instead of copied here, with
accessors in this class (unless you make the change that it is the builder that
creates the graph).

[zerny-google, 2012-08-16 11:52:26]

Revision based on Kevin's review.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:136: FlowGraph flow_graph(parsed_function);
On 2012/08/16 08:09:57, kmillikin wrote:
> It's a bit strange (to me) that there is such a thing as an unbuilt graph. 
For
> some reason I expect something more like:
> 
> FlowGraphBuilder builder(...);
> FlowGraph* graph = builder.BuildGraph();

Sure.

> Also, I'd put this declaration down closer to its first use (after the
> TimerScope).

Unfortunately the graph/block_order is used after the TimerScope.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:168: // Print flow graph to stdout.
On 2012/08/16 08:09:57, kmillikin wrote:
> Did we lose a "Before Optimizations:\n" that used to be printed here?

I can't seem to find that in git-svn, but will be happy to add it.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:169: FlowGraphPrinter printer(parsed_function.function(),
On 2012/08/16 08:09:57, kmillikin wrote:
> I seems like this constructor could just take the graph as input, but feel
free
> to make that in a separate cleanup change.

Yes. The other utilities should really take the graph instead of the block entry
arrays.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/compiler...
runtime/vm/compiler.cc:175: FlowGraphVisualizer
printer(parsed_function.function(),
On 2012/08/16 08:09:57, kmillikin wrote:
> Also here and most of the constructors below, the graph could be the input.
> 
> It's just a bit weird that a class that mutates the graph (e.g.,
> FlowGraphOptimizer) does not take the graph itself as an argument.

Yes.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.cc:57: reverse_postorder_.Add(postorder_[block_count - i -
1]);
On 2012/08/16 08:09:57, kmillikin wrote:
> I don't think a reversed copy of the other list adds much value.  I wonder if
> anyone would complain if we removed it?

Differing to a later CL.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.cc:472: }
On 2012/08/16 08:09:57, kmillikin wrote:
> There should be one or two lines of whitespace before the closing brace and it
> should have a "// namespace dart" end-of-line comment.

Done.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph.h (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:8: #include "vm/ast.h"
On 2012/08/16 08:09:57, kmillikin wrote:
> Are you sure you need to include this?  I can't immediately see why.

Thanks. It was the parser.h I needed.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:64: void ComputeOrders();
On 2012/08/16 08:09:57, kmillikin wrote:
> I like the name DiscoverBlocks better.  It seems more central that this is the
> unique function that makes the implicit basic-block structure explicit.

Ok

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:66: const ParsedFunction& parsed_function_;
On 2012/08/16 08:09:57, kmillikin wrote:
> Member variables should all be at the end of the private: section and grouped
> together.

Done.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph.h:103: GrowableArray<intptr_t> parent_;
On 2012/08/16 08:09:57, kmillikin wrote:
> These variables (parent_ and assigned_vars_) should have a comment that they
are
> used for SSA computation and but not maintained afterward.

Done.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:61:
block_order_(flow_graph->reverse_postorder()),
On 2012/08/16 08:09:57, kmillikin wrote:
> Instead of reading these fields out of the flow graph, it's probably better to
> just use the values in the graph.  You can still define convenience accessors
in
> FlowGraphAllocator.

Postponing to a later CL.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:518:
ASSERT(flow_graph_->copied_parameter_count() == 0 ||
On 2012/08/16 08:09:57, kmillikin wrote:
> This assert should have a comment explaining it.

Done.

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10857016/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:176: // TODO(vegorov): this field is used only
to call Bailout. Remove when
On 2012/08/16 08:09:57, kmillikin wrote:
> I don't think the TODO comment is accurate anymore (flow_graph_ is used for
more
> than calling Bailout).  The comment can be deleted.

Done.