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

runtime/vm/flow_graph.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph.h"
 
 #include "vm/bit_vector.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
@@ skipping 12 matching lines @@
     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()),
     num_stack_locals_(builder.num_stack_locals()),
     graph_entry_(graph_entry),
     preorder_(),
     postorder_(),
     reverse_postorder_(),
-    exits_(NULL) {
+    exits_(NULL),
+    invalid_dominator_tree_(true) {
   DiscoverBlocks();
 }
 
 
 void FlowGraph::DiscoverBlocks() {
   // Initialize state.
   preorder_.Clear();
   postorder_.Clear();
   reverse_postorder_.Clear();
   parent_.Clear();
@@ skipping 253 matching lines @@
 
 // Compute immediate dominators and the dominance frontier for each basic
 // block.  As a side effect of the algorithm, sets the immediate dominator
 // of each basic block.
 //
 // dominance_frontier: an output parameter encoding the dominance frontier.
 //     The array maps the preorder block number of a block to the set of
 //     (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
   // compute immediate dominators from semidominators.  It also removes a
   // level of indirection in the link-eval forest data structure.
   //
   // The algorithm is described in Georgiadis, Tarjan, and Werneck's
   // "Finding Dominators in Practice".
   // See http://www.cs.princeton.edu/~rwerneck/dominators/ .
 
@@ skipping 401 matching lines @@
   const char* function_name = parsed_function_.function().ToCString();
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
-// 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);
+    // 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 at the end.
-    phi->SetInputAt(pred_count - 1, pred_use);
-    pred_use->set_use_index(pred_count - 1);
+    // Write the predecessor use.
+    phi->SetInputAt(new_pred_index, pred_use);
+    pred_use->set_use_index(new_pred_index);
   }
 }
 
 
 // Helper to sort a list of blocks.
 static int LowestBlockIdFirst(BlockEntryInstr* const* a,
                               BlockEntryInstr* const* b) {
   return (*a)->block_id() - (*b)->block_id();
 }
 
@@ skipping 44 matching lines @@
   if (callee_exits->is_empty()) {
     // TODO(zerny): Add support for non-local exits, such as throw.
     UNREACHABLE();
   } else if (callee_exits->length() == 1) {
     ReturnInstr* exit = (*callee_exits)[0];
     ASSERT(exit->previous() != NULL);
     // For just one exit, replace the uses and remove the call from the 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];
         block->set_dominator(exit_block);
         exit_block->AddDominatedBlock(block);
       }
       // The caller entry is now the immediate dominator of blocks whose
       // immediate dominator was the callee entry.
       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();
+      // 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.
     GrowableArray<BlockEntryInstr*> exits(callee_exits->length());
     for (intptr_t i = 0; i < callee_exits->length(); ++i) {
       exits.Add((*callee_exits)[i]->GetBlock());
     }
     exits.Sort(LowestBlockIdFirst);
     // Create a join of the returns.
     JoinEntryInstr* join =
@@ skipping 19 matching lines @@
         ReturnInstr* exit_instr = exits[i]->last_instruction()->AsReturn();
         ASSERT(exit_instr != NULL);
         Value* use = exit_instr->value();
         phi->SetInputAt(i, use);
         use->set_instruction(phi);
         use->set_use_index(i);
       }
       // 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);
   }
 }
 
 
 intptr_t FlowGraph::InstructionCount() const {
   intptr_t size = 0;
   // Iterate each block, skipping the graph entry.
   for (intptr_t i = 1; i < preorder_.length(); ++i) {
     for (ForwardInstructionIterator it(preorder_[i]);
          !it.Done();
          it.Advance()) {
       ++size;
     }
   }
   return size;
 }
 
 
 }  // namespace dart