Make the CFG depth-first traversal do more work for us.

Make the CFG depth-first traversal do more work for us.

Turn the depth-first traversal into a pass to discover the graph's basic
block structure.  Record basic-block predecessors in the block entry
instructions.  Also record the last instruction in a block in the block
entry instruction (giving constant-time access to the block's successors).

Also, record the depth-first spanning tree of the traversal to be used for
dominator computation.

R=srdjan@google.com
BUG=
TEST=

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

[Kevin Millikin (Google), 2012-03-19 18:05:12]

1. I think we should consider assigning block numbers as to the entry
instructions in the order we generate them, and use them instead of reverse
postorder for identifying blocks (e.g., print name, non-optimizing compiler).

2. Then we only need this pass in the optimizing backend.

3. And then we probably don't need postorder at all (right now), and I'll get
rid of it.  It's easy to add back if we every want, and a bit of a pain to
maintain or recompute if we compute it so early and want to change the graph
structure.

http://codereview.chromium.org/9730003/diff/1/runtime/vm/flow_graph_builder.cc
File runtime/vm/flow_graph_builder.cc (right):

http://codereview.chromium.org/9730003/diff/1/runtime/vm/flow_graph_builder.c...
runtime/vm/flow_graph_builder.cc:1674: GrowableArray<BlockEntryInstr*> parent;
parent is currently ignored.

[srdjan, 2012-03-19 18:43:35]

LGTM with one comment

http://codereview.chromium.org/9730003/diff/1/runtime/vm/intermediate_language.h
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/9730003/diff/1/runtime/vm/intermediate_languag...
runtime/vm/intermediate_language.h:914: BlockEntryInstr* predecessor_;
It is not publicly accessible, what is its use? Future use? Add getter? Ditto
for JoinEntryInstr.

[Kevin Millikin (Google), 2012-03-19 18:53:55]

Thanks for the review.  I'll hold off on exposing predecessors for another
change.

http://codereview.chromium.org/9730003/diff/1/runtime/vm/intermediate_language.h
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/9730003/diff/1/runtime/vm/intermediate_languag...
runtime/vm/intermediate_language.h:914: BlockEntryInstr* predecessor_;
On 2012/03/19 18:43:35, srdjan wrote:
> It is not publicly accessible, what is its use? Future use? Add getter? Ditto
> for JoinEntryInstr.

The dominator computation needs to iterate predecessors.

Let me leave it private for now with no accessor.  We might expose an accessor,
but what we really want is some kind of iterator interface, because we don't
want to have to distinguish between Target and Join in most cases just to
iterate the predecessors.