Inlining functions with control flow.

Inlining functions with control flow.

Functions containing control flow are now inlined and incrementally extend the graph in SSA form. For the special case of a function with only one exit, we locally update the dominator tree. If multiple exits occur, we currently recompute the dominator tree for the full resulting graph.

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

[zerny-google, 2012-09-24 11:37:29]

Add inlining of code containing control flow.

Inlining is split into two phases: 1) find call sites and 2) inline them.

FlowGraph::InlineCall attempts to recompute as little as possible leading to a
bit of code duplication.

[zerny-google, 2012-09-24 11:37:59]

Add inlining of code containing control flow.

Inlining is split into two phases: 1) find call sites and 2) inline them.

FlowGraph::InlineCall attempts to recompute as little as possible leading to a
bit of code duplication.

[Kevin Millikin (Google), 2012-09-24 14:45:51]

I like the approach.  Comments below, all on the actual mechanics of inlining
into the graph.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:732: // Helper to possibly reindex a phi after
splitting a block.
The comment needs to say that this happens while splitting a block ---
last_instruction of caller_block is the last instruction of the original,
unsplit block.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:740:
caller_block->last_instruction()->SuccessorAt(0)->AsJoinEntry();
SuccessorCount, SuccessorAt, IsJoinEntry, AsJoinEntry are all virtual functions.

We rely elsewhere on knowing the Goto is the only control instruction with a
single successor, so you can write:

GotoInstr* jump = caller_block->last_instruction()->AsGoto();
if (jump == NULL) return;
JoinEntryInstr* join = jump->successor();

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:747: if (join->phis() == NULL || pred_index + 1 ==
pred_count) return;
We like to parenthesize these:

if ((join->phis() == NULL) ||
    ((pred_index + 1) == pred_count)) {
  return;
}

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:755: while (++curr_index < pred_count) {
I'm not a fan of side effects in expressions.  This loop is already pretty
hairy, and it might be simpler as:

for (intptr_t i = pred_index + 1; i < pred_count; ++i) {
  bool found = (new_block_id < join->PredecessorAt(i)->block_id());
  Value* use = phi->InputAt(found ? pred_index : i);
  phi->SetInputAt(i - 1, use);
  use->set_use_index(i - 1);
  if (found) break;
}

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:767: static BlockEntryInstr* GetBlockEntry(Instruction*
instr) {
We have Instruction::GetBlock now, it can replace this function.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:782: class Exit : public ZoneAllocated {
This is just a struct.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:822: for (intptr_t i = 1; i <
callee_graph->preorder().length(); ++i) {
You can use one of the BlockIterators here --- expose the preorder_iterator() is
you want preorder.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:849: // The callee return now dominates blocks
dominated by the caller entry.
These are immediate dominators, right?  Maybe the comment should say something
like: The callee return is now the immediate dominator of blocks whose immediate
dominator was the caller entry.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:856: // The caller entry now dominates blocks dominated
by the callee entry.
Whatever you come up with above, this is exactly parallel.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:868: GrowableArray<Exit*>
exits(callee_exits->length());
This is pretty complicated with the sorting and extra struct.  I wonder if it
would be simpler to have callee_exits be a list of the blocks ending in return
rather than the returns?  You could just quicksort the list by block_id and I
think you'd have everything you need below.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:887: intptr_t env_count = call->env()->Length() -
call->ArgumentCount();
We should just avoid this for the relatively common case of inlining a function
that has no uses.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:910: ComputeDominators(&dominance_frontier);
Let's think of a way to avoid this.

[zerny-google, 2012-09-25 10:51:32]

Hi Slava,

This patch set addresses Kevin's comments. Could you have a look if this CL is
ready to land.

Thanks!

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:732: // Helper to possibly reindex a phi after
splitting a block.
On 2012/09/24 14:45:51, kmillikin wrote:
> The comment needs to say that this happens while splitting a block ---
> last_instruction of caller_block is the last instruction of the original,
> unsplit block.

Done.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:740:
caller_block->last_instruction()->SuccessorAt(0)->AsJoinEntry();
On 2012/09/24 14:45:51, kmillikin wrote:
> SuccessorCount, SuccessorAt, IsJoinEntry, AsJoinEntry are all virtual
functions.
> 
> We rely elsewhere on knowing the Goto is the only control instruction with a
> single successor, so you can write:
> 
> GotoInstr* jump = caller_block->last_instruction()->AsGoto();
> if (jump == NULL) return;
> JoinEntryInstr* join = jump->successor();

A lot nicer.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:747: if (join->phis() == NULL || pred_index + 1 ==
pred_count) return;
On 2012/09/24 14:45:51, kmillikin wrote:
> We like to parenthesize these:
> 
> if ((join->phis() == NULL) ||
>     ((pred_index + 1) == pred_count)) {
>   return;
> }

Done.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:755: while (++curr_index < pred_count) {
On 2012/09/24 14:45:51, kmillikin wrote:
> I'm not a fan of side effects in expressions.  This loop is already pretty
> hairy, and it might be simpler as:
> 
> for (intptr_t i = pred_index + 1; i < pred_count; ++i) {
>   bool found = (new_block_id < join->PredecessorAt(i)->block_id());
>   Value* use = phi->InputAt(found ? pred_index : i);
>   phi->SetInputAt(i - 1, use);
>   use->set_use_index(i - 1);
>   if (found) break;
> }

There are two issues with this restructuring. If the new_block_id is larger then
all others then InputAt(pred_index) will never be called, and also we need to
copy InputAt(pred_index) because it is overwritten the first time around the
loop.

After some more thought, the above is more general than need be. The new block
id, coming from the graph to be inlined, is larger than all block ids of the
caller graph. The break is therefore unneeded, and we can simply move each
following input down by one and write the pred_use at to the last index.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:767: static BlockEntryInstr* GetBlockEntry(Instruction*
instr) {
On 2012/09/24 14:45:51, kmillikin wrote:
> We have Instruction::GetBlock now, it can replace this function.

Done.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:782: class Exit : public ZoneAllocated {
On 2012/09/24 14:45:51, kmillikin wrote:
> This is just a struct.

Done.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:822: for (intptr_t i = 1; i <
callee_graph->preorder().length(); ++i) {
On 2012/09/24 14:45:51, kmillikin wrote:
> You can use one of the BlockIterators here --- expose the preorder_iterator()
is
> you want preorder.

Done.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:849: // The callee return now dominates blocks
dominated by the caller entry.
On 2012/09/24 14:45:51, kmillikin wrote:
> These are immediate dominators, right?  Maybe the comment should say something
> like: The callee return is now the immediate dominator of blocks whose
immediate
> dominator was the caller entry.

Done.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:856: // The caller entry now dominates blocks dominated
by the callee entry.
On 2012/09/24 14:45:51, kmillikin wrote:
> Whatever you come up with above, this is exactly parallel.

Done.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:868: GrowableArray<Exit*>
exits(callee_exits->length());
On 2012/09/24 14:45:51, kmillikin wrote:
> This is pretty complicated with the sorting and extra struct.  I wonder if it
> would be simpler to have callee_exits be a list of the blocks ending in return
> rather than the returns?  You could just quicksort the list by block_id and I
> think you'd have everything you need below.

Well, it will take a larger change to get a hold of block entry of a return
inside the flow-graph builder. I have replaced the code with use of Sort, but
still make a local copy of the exit blocks.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:887: intptr_t env_count = call->env()->Length() -
call->ArgumentCount();
On 2012/09/24 14:45:51, kmillikin wrote:
> We should just avoid this for the relatively common case of inlining a
function
> that has no uses.

Done for the case where both the input and environment use lists are empty.

http://codereview.chromium.org/10967007/diff/4001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:910: ComputeDominators(&dominance_frontier);
On 2012/09/24 14:45:51, kmillikin wrote:
> Let's think of a way to avoid this.

Will do so as a separate CL.

[zerny-google, 2012-09-26 11:51:42]

Added some test programs.

[srdjan, 2012-09-26 13:13:33]

http://codereview.chromium.org/10967007/diff/11003/tests/language/inline_valu...
File tests/language/inline_value_context_test.dart (right):

http://codereview.chromium.org/10967007/diff/11003/tests/language/inline_valu...
tests/language/inline_value_context_test.dart:39: InlineValueContext.testMain();
Since testMain runs only once, the optimized version will never run, will it?

[zerny-google, 2012-09-27 10:21:46]

Hi Srdjan,

Thanks for the feedback. I have updated the tests accordingly.

http://codereview.chromium.org/10967007/diff/11003/tests/language/inline_valu...
File tests/language/inline_value_context_test.dart (right):

http://codereview.chromium.org/10967007/diff/11003/tests/language/inline_valu...
tests/language/inline_value_context_test.dart:39: InlineValueContext.testMain();
On 2012/09/26 13:13:33, srdjan wrote:
> Since testMain runs only once, the optimized version will never run, will it?

Indeed. This should really be a test with two nested frames and the top one
occurring in a value context.