Inlining functions with control flow.

runtime/vm/flow_graph.cc

Index: runtime/vm/flow_graph.cc
diff --git a/runtime/vm/flow_graph.cc b/runtime/vm/flow_graph.cc
index d434d610ebed6c587bd311253424cd663142f8e5..727d3e5de1e7212b64aa345fafd6a0cd35bcc090 100644
--- a/runtime/vm/flow_graph.cc
+++ b/runtime/vm/flow_graph.cc
@@ -15,10 +15,12 @@ namespace dart {
 DECLARE_FLAG(bool, trace_optimization);
 
 FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
-                     GraphEntryInstr* graph_entry)
+                     GraphEntryInstr* graph_entry,
+                     intptr_t max_block_id)
   : parent_(),
     assigned_vars_(),
     current_ssa_temp_index_(0),
+    max_block_id_(max_block_id),
     parsed_function_(builder.parsed_function()),
     num_copied_params_(builder.num_copied_params()),
     num_non_copied_params_(builder.num_non_copied_params()),
@@ -727,6 +729,40 @@ void FlowGraph::Bailout(const char* reason) const {
 }
 
 
+// Helper to possibly reindex a phi after splitting a block.

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

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.

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

Done.

+static void ReindexPhiAfterSplit(BlockEntryInstr* caller_block,
+                                 BlockEntryInstr* return_block) {
+  if (caller_block->last_instruction()->SuccessorCount() != 1 ||
+      !caller_block->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
+    return;
+  }
+  JoinEntryInstr* join =
+      caller_block->last_instruction()->SuccessorAt(0)->AsJoinEntry();

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

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();

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

A lot nicer.

+  intptr_t pred_index = join->IndexOfPredecessor(caller_block);
+  intptr_t pred_count = join->PredecessorCount();
+  ASSERT(pred_index >= 0);
+  ASSERT(pred_index < pred_count);
+  ASSERT(caller_block->block_id() < return_block->block_id());
+  // If the predecessor index is the last index there is nothing to update.
+  if (join->phis() == NULL || pred_index + 1 == pred_count) return;

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

We like to parenthesize these:

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

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

Done.

+  intptr_t new_block_id = return_block->block_id();
+  for (intptr_t i = 0; i < join->phis()->length(); ++i) {
+    PhiInstr* phi = (*join->phis())[i];
+    if (phi == NULL) continue;
+    ASSERT(pred_count == phi->InputCount());
+    Value* pred_use = phi->InputAt(pred_index);
+    intptr_t curr_index = pred_index;
+    while (++curr_index < pred_count) {

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

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;
}

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

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.

+      if (new_block_id < join->PredecessorAt(curr_index)->block_id()) break;
+      Value* use = phi->InputAt(curr_index);
+      phi->SetInputAt(curr_index - 1, use);
+      use->set_use_index(curr_index - 1);
+    }
+    phi->SetInputAt(curr_index - 1, pred_use);
+    pred_use->set_use_index(curr_index - 1);
+  }
+}
+
 // Helper to get the block-entry of an instruction.
 static BlockEntryInstr* GetBlockEntry(Instruction* instr) {

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

We have Instruction::GetBlock now, it can replace this function.

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

Done.

   while (!instr->IsBlockEntry()) instr = instr->previous();
@@ -742,6 +778,19 @@ static void Link(Instruction* prev, Instruction* next) {
 }
 
 
+// Triple containing a return exit, its value, and its containing block.
+class Exit : public ZoneAllocated {

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

This is just a struct.

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

Done.

+ public:
+  ReturnInstr* exit;
+  Value* value;
+  BlockEntryInstr* block;
+  explicit Exit(ReturnInstr* exit)
+      : exit(exit),
+        value(exit->value()),
+        block(GetBlockEntry(exit)) { }
+};
+
+
 // Inline a flow graph at a call site.
 //
 // Assumes the callee graph was computed by BuildGraph with an inlining context
@@ -751,13 +800,16 @@ static void Link(Instruction* prev, Instruction* next) {
 // After inlining the caller graph will correctly have adjusted the pre/post
 // orders, the dominator tree and the use lists.
 void FlowGraph::InlineCall(Definition* call, FlowGraph* callee_graph) {
+  ASSERT(call->previous() != NULL);
+  ASSERT(call->next() != NULL);
   ASSERT(callee_graph->exits() != NULL);
   ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1);
+  ASSERT(callee_graph->max_block_id() > max_block_id());
   ASSERT(callee_graph->max_virtual_register_number() >
          max_virtual_register_number());
 
-  // TODO(zerny): Implement support for callee graphs with control flow.
-  ASSERT(callee_graph->preorder().length() == 2);
+  // Adjust the max block id to the max block id of the callee graph.
+  max_block_id_ = callee_graph->max_block_id();
 
   // Adjust the SSA temp index by the callee graph's index.
   current_ssa_temp_index_ = callee_graph->max_virtual_register_number();
@@ -767,31 +819,96 @@ void FlowGraph::InlineCall(Definition* call, FlowGraph* callee_graph) {
   ZoneGrowableArray<ReturnInstr*>* callee_exits = callee_graph->exits();
 
   // 0. Attach the outer environment on each instruction in the callee graph.
-  for (ForwardInstructionIterator it(callee_entry); !it.Done(); it.Advance()) {
-    Instruction* instr = it.Current();
-    if (instr->CanDeoptimize()) call->env()->DeepCopyToOuter(instr);
+  for (intptr_t i = 1; i < callee_graph->preorder().length(); ++i) {

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

You can use one of the BlockIterators here --- expose the preorder_iterator() is
you want preorder.

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

Done.

+    for (ForwardInstructionIterator it(callee_graph->preorder()[i]);
+         !it.Done();
+         it.Advance()) {
+      Instruction* instr = it.Current();
+      if (instr->CanDeoptimize()) call->env()->DeepCopyToOuter(instr);
+    }
   }
 
   // 1. Insert the callee graph into the caller graph.
   if (callee_exits->is_empty()) {
-    // If no normal exits exist, inline and truncate the block after inlining.
-    Link(call->previous(), callee_entry->next());
-    caller_entry->set_last_instruction(callee_entry->last_instruction());
+    // TODO(zerny): Add support for non-local exits, such as throw.
+    UNREACHABLE();
   } else if (callee_exits->length() == 1) {
     ReturnInstr* exit = (*callee_exits)[0];
-    // TODO(zerny): Support one exit graph containing control flow.
-    ASSERT(callee_entry == GetBlockEntry(exit));
+    ASSERT(exit->previous() != NULL);
     // For just one exit, replace the uses and remove the call from the graph.
     call->ReplaceUsesWith(exit->value()->definition());
     Link(call->previous(), callee_entry->next());
     Link(exit->previous(), call->next());
+    // In case of control flow, locally update the dominator tree.
+    if (callee_graph->preorder().length() > 2) {
+      BlockEntryInstr* exit_block = GetBlockEntry(exit);
+      // The caller block is split and the new block id is that of the exit
+      // block. If the caller block had outgoing edges, reorder the phis so they
+      // are still ordered by block id.
+      ReindexPhiAfterSplit(caller_entry, exit_block);
+      // The callee return now dominates blocks dominated by the caller entry.

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

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.

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

Done.

+      ASSERT(exit_block->dominated_blocks().is_empty());
+      for (intptr_t i = 0; i < caller_entry->dominated_blocks().length(); ++i) {
+        BlockEntryInstr* block = caller_entry->dominated_blocks()[i];
+        block->set_dominator(exit_block);
+        exit_block->AddDominatedBlock(block);
+      }
+      // The caller entry now dominates blocks dominated by the callee entry.

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

Whatever you come up with above, this is exactly parallel.

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

Done.

+      caller_entry->ClearDominatedBlocks();
+      for (intptr_t i = 0; i < callee_entry->dominated_blocks().length(); ++i) {
+        BlockEntryInstr* block = callee_entry->dominated_blocks()[i];
+        block->set_dominator(caller_entry);
+        caller_entry->AddDominatedBlock(block);
+      }
+      // Recompute the block orders.
+      DiscoverBlocks();
+    }
   } else {
-    // TODO(zerny): Support multiple exits.
-    UNREACHABLE();
+    // Insertion sort the list of exits.
+    GrowableArray<Exit*> exits(callee_exits->length());

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

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.

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

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.

+    for (intptr_t i = 0; i < callee_exits->length(); ++i) {
+      Exit* exit = new Exit((*callee_exits)[i]);
+      intptr_t block_id = exit->block->block_id();
+      intptr_t index = 0;
+      while ((index < exits.length()) &&
+             (exits[index]->block->block_id() < block_id)) {
+        ++index;
+      }
+      exits.InsertAt(index, exit);
+    }
+    // Create a join of the returns.
+    JoinEntryInstr* join =
+        new JoinEntryInstr(++max_block_id_, CatchClauseNode::kInvalidTryIndex);
+    for (intptr_t i = 0; i < exits.length(); ++i) {
+      exits[i]->exit->previous()->Goto(join);
+      join->predecessors_.Add(exits[i]->block);
+    }
+    // Environment count: length before call - argument count (+ return)
+    intptr_t env_count = call->env()->Length() - call->ArgumentCount();

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

We should just avoid this for the relatively common case of inlining a function
that has no uses.

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

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

+    // Add a phi of the return values.
+    join->InsertPhi(env_count, env_count + 1);
+    PhiInstr* phi = join->phis()->Last();
+    phi->set_ssa_temp_index(alloc_ssa_temp_index());
+    phi->mark_alive();
+    for (intptr_t i = 0; i < exits.length(); ++i) {
+      Value* use = exits[i]->value;
+      phi->SetInputAt(i, use);
+      use->set_instruction(phi);
+      use->set_use_index(i);
+    }
+    // Replace uses of call with phi and remove call from the graph.
+    call->ReplaceUsesWith(phi);
+    Link(call->previous(), callee_entry->next());
+    Link(join, call->next());
+    // The caller block is split and the new block id is that of the join
+    // block. If the caller block had outgoing edges, reorder the phis so they
+    // are still ordered by block id.
+    ReindexPhiAfterSplit(caller_entry, join);
+    // Adjust pre/post orders and update the dominator tree.
+    DiscoverBlocks();
+    GrowableArray<BitVector*> dominance_frontier;
+    ComputeDominators(&dominance_frontier);

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

Let's think of a way to avoid this.

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

Will do so as a separate CL.

   }
-
-  // TODO(zerny): Adjust pre/post orders.
-  // TODO(zerny): Update dominator tree.
 }