Iterative graph traversal in FlowGraph::DiscoverBlocks()

Iterative graph traversal in FlowGraph::DiscoverBlocks()

The motivation behind this change is that very large functions could
cause stack overflows in the (previously recursive) DiscoverBlocks
function. This commit introduces replaces recursive traversal by
iterative algorithms. Postorder traversal had to be removed from
DiscoverBlocks and is now done in a separate pass.

BUG=21109
R=vegorov@google.com

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

[jgruber1, 2014-10-02 13:38:30]

jgruber@google.com changed reviewers:
+ fschneider@google.com, vegorov@google.com

[Vyacheslav Egorov (Google), 2014-10-07 12:43:17]

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

https://codereview.chromium.org/617933003/diff/1/runtime/vm/flow_graph.cc#new...
runtime/vm/flow_graph.cc:214: GrowableArray<BlockEntryEdge> block_stack;
I would really like to have this block_stack die after DiscoverBlock(). 

We run DiscoverBlocks multiple times during the optimization phase and if this
stack is big - I don't want it to polute the Zone. 

Maybe we could have a StackZone above it?

https://codereview.chromium.org/617933003/diff/1/runtime/vm/flow_graph.cc#new...
runtime/vm/flow_graph.cc:225: const intptr_t block_count = preorder_.length();
Maybe I am missing something but I think you can build both orders with one
loop. 

class State {
  final block;
  int idx;

  State(this.block) : succ = 0;
}

visit(block) {
  // 0. if block already has preorder number return false
  // 1. assign preoder number
  // 2. find last instruction
  // 3. return true
}

discover() {
  final stack = [new State(entry)];
  visit(stack.last);
  while (!stack.isEmpty) {
    final state = stack.last;
    if (state.idx < state.block.successors.length) {
      final succ = state.block.successors[state.idx++];
      if (visit(succ)) {
        if (!state.block.successors.isEmpty) {
          stack.add(new State(succ));
        } else {
          // assign post order number to succ.
        }
      }
    } else {
      // assign post order number to state.block
      stack.removeLast();
    }
  }
}

You can even combine recursion and iteration (e.g. do recursion and then switch
to iteration when reaching certain depth).

[jgruber1, 2014-10-08 15:11:29]

PTAL.

Golem:
http://173.255.127.20:8080/Comparison#targetA=dart;machineTypeA=linux-x64;rev...

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

https://codereview.chromium.org/617933003/diff/1/runtime/vm/flow_graph.cc#new...
runtime/vm/flow_graph.cc:214: GrowableArray<BlockEntryEdge> block_stack;
On 2014/10/07 12:43:17, Vyacheslav Egorov (Google) wrote:
> I would really like to have this block_stack die after DiscoverBlock(). 
> 
> We run DiscoverBlocks multiple times during the optimization phase and if this
> stack is big - I don't want it to polute the Zone. 
> 
> Maybe we could have a StackZone above it?

Done. I didn't realize the array memory sticks around since the array is
allocated on the stack, but it's obvious in hindsight.

https://codereview.chromium.org/617933003/diff/1/runtime/vm/flow_graph.cc#new...
runtime/vm/flow_graph.cc:225: const intptr_t block_count = preorder_.length();
On 2014/10/07 12:43:17, Vyacheslav Egorov (Google) wrote:
> Maybe I am missing something but I think you can build both orders with one
> loop. 
> 
> class State {
>   final block;
>   int idx;
> 
>   State(this.block) : succ = 0;
> }
> 
> visit(block) {
>   // 0. if block already has preorder number return false
>   // 1. assign preoder number
>   // 2. find last instruction
>   // 3. return true
> }
> 
> discover() {
>   final stack = [new State(entry)];
>   visit(stack.last);
>   while (!stack.isEmpty) {
>     final state = stack.last;
>     if (state.idx < state.block.successors.length) {
>       final succ = state.block.successors[state.idx++];
>       if (visit(succ)) {
>         if (!state.block.successors.isEmpty) {
>           stack.add(new State(succ));
>         } else {
>           // assign post order number to succ.
>         }
>       }
>     } else {
>       // assign post order number to state.block
>       stack.removeLast();
>     }
>   }
> }
> 
> You can even combine recursion and iteration (e.g. do recursion and then
switch
> to iteration when reaching certain depth). 

Good point, done.

[zerny-google, 2014-10-09 09:53:31]

zerny@google.com changed reviewers:
+ zerny@google.com

[zerny-google, 2014-10-09 09:53:32]

A small nit. As discussed offline, the benchmarks don't indicate a regression
compared to the recursive algorithm, so it seems best to just stick to the
iterative one (as opposed to a mixed solution).

https://codereview.chromium.org/617933003/diff/20001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/617933003/diff/20001/runtime/vm/flow_graph.cc...
runtime/vm/flow_graph.cc:188:
block_stack.Add(BlockTraversalState(graph_entry_));
Nit: consistent use of graph_entry()/graph_entry_

[jgruber1, 2014-10-09 14:08:36]

https://codereview.chromium.org/617933003/diff/20001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/617933003/diff/20001/runtime/vm/flow_graph.cc...
runtime/vm/flow_graph.cc:188:
block_stack.Add(BlockTraversalState(graph_entry_));
On 2014/10/09 09:53:32, zerny-google wrote:
> Nit: consistent use of graph_entry()/graph_entry_

Done.

[Vyacheslav Egorov (Google), 2014-10-09 14:22:19]

LGTM 

though I am a bit concerned that there will be too much re-allocation happening
when we grow block_stack. 

but if it is not visible on benchmarks at the moment we can ignore it.

https://codereview.chromium.org/617933003/diff/40001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/617933003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.h:1158: bool DiscoverBlock(
Please document return value (when it returns true and when it returns false)

[jgruber1, 2014-10-09 15:35:34]

Committed patchset #4 (id:60001) manually as 41016 (presubmit successful).