Collect edge count profiling data and reorder basic blocks.

Collect edge count profiling data and reorder basic blocks.

In unoptimized code, collect edge counts for all edges.  Use the counts
to reorder basic blocks in optimized code.  Basic blocks are reordered
by using Pettis and Hansen's "Profile Guided Code Positioning" bottom-up
algorithm.

R=fschneider@google.com, regis@google.com, srdjan@google.com

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

[Kevin Millikin (Google), 2013-07-05 11:41:04]

This a combination of a request for comment and a code review.  Here's a short
guide to the change:

1. I have added edge counters to (almost) all edges.  We can remove some
counters but it makes the current change more complicated.  Edges without a
counter (e.g., from try to catch blocks) default to a count of 0.

2. I use a one element array for the edge counters.

3. For reordering, I use edge "weights" which is edge count per function entry. 
This allows intuitive scaling for inlined functions.

4. Regis and Zach, this is not implemented on ARM and MIPS.  I need idiomatic
code sequences for TargetEntryInstr::EmitNativeCode and
GotoInstr::EmitNativeCode, if you'd like to suggest them.

You can read the paper for the algorithm, it's pretty simple.  Here is a
summary: Initially add each block to a chain of length 1.  Consider all the
edges in order by decreasing weight.  If the source and target blocks of an edge
lie at the end and beginning (respectively) of different chains, combine the
chains.  Use a topological sort of the blocks to schedule the chains in order in
a single linear pass.

[regis, 2013-07-08 19:13:31]

LGTM

You can try these sequences on ARM and MIPS:

ARM:

    // Add an edge counter.
    const Array& counter = Array::ZoneHandle(Array::New(1, Heap::kOld));
    counter.SetAt(0, Smi::Handle(Smi::New(0)));
    __ Comment("Edge counter");
    __ LoadObject(R0, counter);
    __ ldr(IP, FieldAddress(R0, Array::element_offset(0));
    __ adds(IP, IP, ShifterOperand(Smi::RawValue(1)));
    __ LoadImmediate(IP, Smi::RawValue(Smi::kMaxValue), VS);  // If overflow.
    __ str(IP, FieldAddress(R0, Array::element_offset(0));


MIPS:

    // Add an edge counter.
    const Array& counter = Array::ZoneHandle(Array::New(1, Heap::kOld));
    counter.SetAt(0, Smi::Handle(Smi::New(0)));
    Label done;
    __ Comment("Edge counter");
    __ LoadObject(T0, counter);
    __ lw(T1, FieldAddress(T0, Array::element_offset(0));
    __ AddImmediateDetectOverflow(T1, T1, Smi::RawValue(1), CMPRES, T2);
    __ bgez(CMPRES, &done);
    __ delay_slot()->sw(T1, FieldAddress(T0, Array::element_offset(0));
    __ LoadImmediate(TMP1, Smi::RawValue(Smi::kMaxValue));
    __ sw(TMP1, FieldAddress(T0, Array::element_offset(0));  // If overflow.
    __ Bind(&done);

[Florian Schneider, 2013-08-12 11:30:09]

lgtm.

To reduce unoptimized code size it would be great to eliminate counter code for
blocks that already have a counting call. I can imagine this improvement also as
a separate CL.

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

https://codereview.chromium.org/18111006/diff/1/runtime/vm/block_scheduler.cc...
runtime/vm/block_scheduler.cc:48: double weight = 0.0;
style-nit: I would not hoist these two declarations out of the if- and
else-blocks.

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

https://codereview.chromium.org/18111006/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:298: BlockScheduler block_scheduler(flow_graph);
Maybe add a flag FLAG_reorder_basic_blocks to control reordering.

[Kevin Millikin (Google), 2013-08-13 11:14:57]

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

https://codereview.chromium.org/18111006/diff/1/runtime/vm/block_scheduler.cc...
runtime/vm/block_scheduler.cc:48: double weight = 0.0;
On 2013/08/12 11:30:09, Florian Schneider wrote:
> style-nit: I would not hoist these two declarations out of the if- and
> else-blocks.

OK, done.

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

https://codereview.chromium.org/18111006/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:298: BlockScheduler block_scheduler(flow_graph);
On 2013/08/12 11:30:09, Florian Schneider wrote:
> Maybe add a flag FLAG_reorder_basic_blocks to control reordering.

Done.

[srdjan, 2013-08-14 00:28:23]

LGTM

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

https://codereview.chromium.org/18111006/diff/1/runtime/vm/block_scheduler.cc...
runtime/vm/block_scheduler.cc:14: intptr_t deopt_id) {
This seems like quite slow way to extract edge counts. What is the impact on
compilation time?

https://codereview.chromium.org/18111006/diff/1/runtime/vm/block_scheduler.cc...
runtime/vm/block_scheduler.cc:18: // weights.
Some intrinsified functions should have edge counts as they are executed as part
of the slow path, however, those edgecounts are probably not
representative/reliable. What you are testing here is if this is an intrinsic
only code (no slow path).

https://codereview.chromium.org/18111006/diff/1/runtime/vm/block_scheduler.cc...
runtime/vm/block_scheduler.cc:48: double weight = 0.0;
On 2013/08/13 11:14:57, kmillikin wrote:
> On 2013/08/12 11:30:09, Florian Schneider wrote:
> > style-nit: I would not hoist these two declarations out of the if- and
> > else-blocks.
> 
> OK, done.

Could you please upload your changes.

https://codereview.chromium.org/18111006/diff/1/runtime/vm/block_scheduler.h
File runtime/vm/block_scheduler.h (right):

https://codereview.chromium.org/18111006/diff/1/runtime/vm/block_scheduler.h#...
runtime/vm/block_scheduler.h:25: FlowGraph* const flow_graph_;
DISALLOW_xxx

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

https://codereview.chromium.org/18111006/diff/1/runtime/vm/flow_graph_builder...
runtime/vm/flow_graph_builder.cc:3535: bool found =
graph_entry_->PruneUnreachable(this, graph_entry_, NULL, osr_id_,
Document what NULL means, e.g., const xxxx pkParent = NULL;

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

https://codereview.chromium.org/18111006/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language_ia32.cc:4323: // Add an edge counter.
I would add/use special counter objects, that way you would not by mistake grab
other objects in the code.

[Kevin Millikin (Google), 2013-08-28 09:17:26]

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