Avoid rediscovering blocks on each call to FlowGraph::InlineCall.

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 3a4cfe8ae5c955a391ccc1eff3094d38af94f6be..779716bc888bee80d8749b670688c06e5640c0c5 100644
--- a/runtime/vm/flow_graph.cc
+++ b/runtime/vm/flow_graph.cc
@@ -30,7 +30,8 @@ FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
     preorder_(),
     postorder_(),
     reverse_postorder_(),
-    exits_(NULL) {
+    exits_(NULL),
+    invalid_dominator_tree_(true) {
   DiscoverBlocks();
 }
 
@@ -304,6 +305,7 @@ void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number) {
 //     (preorder block numbers of) blocks in the dominance frontier.
 void FlowGraph::ComputeDominators(
     GrowableArray<BitVector*>* dominance_frontier) {
+  invalid_dominator_tree_ = false;
   // Use the SEMI-NCA algorithm to compute dominators.  This is a two-pass
   // version of the Lengauer-Tarjan algorithm (LT is normally three passes)
   // that eliminates a pass by using nearest-common ancestor (NCA) to
@@ -725,37 +727,67 @@ void FlowGraph::Bailout(const char* reason) const {
 }
 
 
-// Helper to reorder phis after splitting a block.  The last instruction(s) of
-// the split block will now have a larger block id than any previously known
-// blocks. If the last instruction jumps to a join, we must reorder phi inputs
-// according to the block order, ie, we move this predecessor to the end.
-static void ReorderPhis(BlockEntryInstr* block) {
-  GotoInstr* jump = block->last_instruction()->AsGoto();
+// Helper to reorder predecessors and phis after splitting a block.  For each

[Kevin Millikin (Google), 2012/10/22 09:10:37]

Comment needs some updating---it's no longer called just for blocks that have
been split (e.g., at the call sites where old_block is callee_entry, where the
block callee_entry has actually been merged into caller_entry).

[zerny-google, 2012/10/22 13:21:31]

Done.

+// successor of 'old_block', the predecessors will be reordered to preserve
+// block order sorting. If the successor is a join, also the phi inputs will be
+// updated.
+// Prerequisite: the last-instruction pointers must not have been updated yet.
+void FlowGraph::ReorderPredecessors(BlockEntryInstr* old_block,

[Kevin Millikin (Google), 2012/10/22 09:10:37]

I find the naming and emphasis (on reordering) a bit confusing.  It's true that
it reorders even for the degenerate case of successors with one predecessor, but
I'd prefer to focus on the replacing.

It seems better to think of it as, for each successor of old_block, replacing
old_block as a predecessor with new_block.

[zerny-google, 2012/10/22 13:21:31]

I renamed it to ReplaceBlock, but that is not entirely accurate either because
old_block may still appear in the graph. The code replaces the block associated
with the exiting/last instruction, so maybe ReplaceBlockOfLastInstruction or
ReplaceLastInstructionBlock?

+                                    BlockEntryInstr* new_block) {
+  // If the last instruction is a branch, update the predecessor of the targets.
+  BranchInstr* branch = old_block->last_instruction()->AsBranch();

[Kevin Millikin (Google), 2012/10/22 09:10:37]

It doesn't make a huge difference, but this code could be more generic.  Instead
of specifically mentioning instructions Branch and Goto, it could just be
structured after SuccessorCount: 0, more than 1, or 1.  Everything else should
still work.

[zerny-google, 2012/10/22 13:21:31]

Done.

+  if (branch != NULL) {
+    for (intptr_t i = 0; i < branch->SuccessorCount(); ++i) {
+      TargetEntryInstr* target = branch->SuccessorAt(i)->AsTargetEntry();
+      ASSERT(target != NULL);
+      target->predecessor_ = new_block;
+    }
+    return;
+  }
+  // If the last instruction is a jump, update the join's predecessors and phis.
+  GotoInstr* jump = old_block->last_instruction()->AsGoto();
   if (jump == NULL) return;
+  // Find the old predecessor index
   JoinEntryInstr* join = jump->successor();
-  intptr_t pred_index = join->IndexOfPredecessor(block);
+  intptr_t pred_index = join->IndexOfPredecessor(old_block);
   intptr_t pred_count = join->PredecessorCount();
   ASSERT(pred_index >= 0);
   ASSERT(pred_index < pred_count);
-  // If the predecessor index is the last index there is nothing to update.
-  if ((join->phis() == NULL) || (pred_index + 1 == pred_count)) return;
-  // Otherwise, move the predecessor use to the end in each phi.
+  // Find the new predecessor index

[Kevin Millikin (Google), 2012/10/22 09:10:37]

It seems like we could do the search and move in the same pass.  Start at old
pred_index, and bubble elements up or down (depending on whether the block ID
has decreased or increased) until we find the sorted position.

[zerny-google, 2012/10/22 13:21:31]

Done.

+  intptr_t new_block_id = new_block->block_id();
+  intptr_t new_pred_index = -1;

[Kevin Millikin (Google), 2012/10/22 09:10:37]

Is it simpler to understand this if you shift the index so it's a usual for loop
(update at the end)?

intptr_t new_pred_index = 0;
for (; new_pred_index < pred_count - 1; ++new_pred_index) {
  if (join->predecessors_[new_pred_index]->block_id() > new_block_id) break;
}

[zerny-google, 2012/10/22 13:21:31]

No longer an issue with the new "find predecessor index".

+  while (new_pred_index < pred_count - 1) {
+    ++new_pred_index;
+    if (join->predecessors_[new_pred_index]->block_id() > new_block_id) break;
+  }
+  // Reorder the predecessors of the join.
+  intptr_t step = (new_pred_index > pred_index) ? 1 : -1;
+  intptr_t i = pred_index;
+  while (i != new_pred_index) {

[zerny-google, 2012/10/12 11:52:05]

I'll rewrite this to a for loop again (still using += step for the increment).

+    join->predecessors_[i] = join->predecessors_[i + step];
+    i += step;
+  }
+  join->predecessors_[new_pred_index] = new_block;
+  // If the new and old predecessor index match there is nothing to update.
+  if ((join->phis() == NULL) || (pred_index == new_pred_index)) return;

[Kevin Millikin (Google), 2012/10/22 09:10:37]

Can't you can skip the reordering of the predecessors as well, in the case that
pred_index == new_pred_index.  So, move that check earlier.

[zerny-google, 2012/10/22 13:21:31]

No, we still need to write the new_block at the new_index even if
new_index==old_index.

+  // Otherwise, reorder the predecessor uses in each phi.
   for (intptr_t i = 0; i < join->phis()->length(); ++i) {
     PhiInstr* phi = (*join->phis())[i];
     if (phi == NULL) continue;
     ASSERT(pred_count == phi->InputCount());
     // Save the predecessor use.
     Value* pred_use = phi->InputAt(pred_index);
-    // Move each of the following uses back by one.
-    ASSERT(pred_index < pred_count - 1);  // Will move at least one index.
-    for (intptr_t i = pred_index; i < pred_count - 1; ++i) {
-      Value* use = phi->InputAt(i + 1);
-      phi->SetInputAt(i, use);
-      use->set_use_index(i);
-    }
-    // Write the predecessor use at the end.
-    phi->SetInputAt(pred_count - 1, pred_use);
-    pred_use->set_use_index(pred_count - 1);
+    // Move uses between old and new.
+    intptr_t use_idx = pred_index;
+    while (use_idx != new_pred_index) {

[zerny-google, 2012/10/12 11:52:05]

I'll rewrite this to a for loop again (still using += step for the increment).

+      Value* use = phi->InputAt(use_idx + step);
+      phi->SetInputAt(use_idx, use);
+      use->set_use_index(use_idx);
+      use_idx += step;
+    }
+    // Write the predecessor use.
+    phi->SetInputAt(new_pred_index, pred_use);
+    pred_use->set_use_index(new_pred_index);
   }
 }
 
@@ -820,15 +852,19 @@ void FlowGraph::InlineCall(Definition* call, FlowGraph* callee_graph) {
     call->ReplaceUsesWith(exit->value()->definition());
     call->previous()->LinkTo(callee_entry->next());
     exit->previous()->LinkTo(call->next());
-    // In case of control flow, locally update the dominator tree.
+    // In case of control flow, locally update the predecessors, phis and
+    // dominator tree.
+    // TODO(zerny): should we leave the dominator tree since we recompute it
+    // after a full inlining pass.
     if (callee_graph->preorder().length() > 2) {
-      // 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.
-      ReorderPhis(caller_entry);
+      BlockEntryInstr* exit_block = exit->GetBlock();
+      // The caller block is split and the predecessors might need reordering.

[Kevin Millikin (Google), 2012/10/22 09:10:37]

'the predecessors' is unclear.  "The caller block has been split and the
predecessors of its successors may need to be reordered." or "The caller block
has been split and its successors may need their predecessors reordered."?

[zerny-google, 2012/10/22 13:21:31]

Done.

+      // The caller entry becomes the block of the callee entry block.

[Kevin Millikin (Google), 2012/10/22 09:10:37]

I don't think I understand this comment at all :)  The caller entry block has
been split at the point of the call and so its original successors now have
exit_block as a replacement predecessor; and the callee entry block has been
merged into the (split) caller entry block and so its successors now have
caller_entry as a replacement predecessor.

It should work to reorder the two calls to ReorderPredecessors, which matches
the way I think of the order of effects (the original block has to be split
before the callee_entry can be merged into it).

[zerny-google, 2012/10/22 13:21:31]

Done.

+      ReorderPredecessors(callee_entry, caller_entry);
+      // The callee exit block becomes the block of the caller entry block.
+      ReorderPredecessors(caller_entry, exit_block);
       // The callee return is now the immediate dominator of blocks whose
       // immediate dominator was the caller entry.
-      BlockEntryInstr* exit_block = exit->GetBlock();
       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];
@@ -843,8 +879,9 @@ void FlowGraph::InlineCall(Definition* call, FlowGraph* callee_graph) {
         block->set_dominator(caller_entry);
         caller_entry->AddDominatedBlock(block);
       }
-      // Recompute the block orders.
-      DiscoverBlocks();
+      // Update the last-instruction pointers.
+      exit_block->set_last_instruction(caller_entry->last_instruction());

[Kevin Millikin (Google), 2012/10/22 09:10:37]

It seems like this could also be moved into ReorderPredecessors if the order of
the two calls were swapped.

[zerny-google, 2012/10/22 13:21:31]

Done.

+      caller_entry->set_last_instruction(callee_entry->last_instruction());
     }
   } else {
     // Sort the list of exits by block id.
@@ -884,16 +921,31 @@ void FlowGraph::InlineCall(Definition* call, FlowGraph* callee_graph) {
       // Replace uses of the call with the phi.
       call->ReplaceUsesWith(phi);
     }
-    //  Remove the call from the graph.
+    // Remove the call from the graph.
     call->previous()->LinkTo(callee_entry->next());
     join->LinkTo(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.
-    ReorderPhis(caller_entry);
-    // Adjust pre/post orders and update the dominator tree.
-    DiscoverBlocks();
+    // The caller block is split and the predecessors might need reordering.
+    // The caller entry becomes the block of the callee entry block.
+    ReorderPredecessors(callee_entry, caller_entry);
+    // The join block becomes the block of the caller entry block.
+    ReorderPredecessors(caller_entry, join);
+    // Update the last instruction pointers.
+    join->set_last_instruction(caller_entry->last_instruction());
+    caller_entry->set_last_instruction(callee_entry->last_instruction());
+    for (intptr_t i = 0; i < exits.length(); ++i) {
+      exits[i]->set_last_instruction(
+          exits[i]->last_instruction()->previous()->next());
+    }
+    // Mark that the dominator tree is invalid.
     // TODO(zerny): Compute the dominator frontier locally.
+    invalid_dominator_tree_ = true;
+  }
+}
+
+
+void FlowGraph::RepairGraphAfterInlining() {
+  DiscoverBlocks();
+  if (invalid_dominator_tree_) {
     GrowableArray<BitVector*> dominance_frontier;
     ComputeDominators(&dominance_frontier);
   }