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();
-  if (jump == NULL) return;
-  JoinEntryInstr* join = jump->successor();
-  intptr_t pred_index = join->IndexOfPredecessor(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.
-  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);
+// Helper to replace a block. For each successor of 'old_block', the
+// predecessors will be reordered to preserve block order sorting as well as the
+// phis if the successor is a join.
+void FlowGraph::ReplaceBlock(BlockEntryInstr* old_block,

[Kevin Millikin (Google), 2012/10/22 14:13:11]

I suggest ReplacePredecessor.  It replaces old_block with new_block as a
predecessor in all (original) successors of old_block.

+                             BlockEntryInstr* new_block) {
+  // Set the last instruction of the new block to that of the old block.
+  Instruction* last = old_block->last_instruction();
+  new_block->set_last_instruction(last);
+  // For each successor, update the predecessors.
+  for (intptr_t sidx = 0; sidx < last->SuccessorCount(); ++sidx) {
+    // If the successor is a target, update its predecessor.
+    TargetEntryInstr* target = last->SuccessorAt(sidx)->AsTargetEntry();
+    if (target != NULL) {
+      target->predecessor_ = new_block;
+      continue;
     }
-    // Write the predecessor use at the end.
-    phi->SetInputAt(pred_count - 1, pred_use);
-    pred_use->set_use_index(pred_count - 1);
+    // If the successor is a join, update each predecessor and the phis.
+    JoinEntryInstr* join = last->SuccessorAt(sidx)->AsJoinEntry();
+    ASSERT(join != NULL);
+    // Find the old predecessor index.
+    intptr_t old_index = join->IndexOfPredecessor(old_block);
+    intptr_t pred_count = join->PredecessorCount();
+    ASSERT(old_index >= 0);
+    ASSERT(old_index < pred_count);
+    // Determine the iteration direction.
+    intptr_t new_id = new_block->block_id();
+    intptr_t step, limit;
+    if (old_block->block_id() < new_id) {
+      step = 1;
+      limit = pred_count - 1;
+    } else {
+      step = -1;
+      limit = 0;
+    }
+    // Find the new predecessor index while reordering the predecessors.
+    intptr_t new_index = old_index;
+    for (; new_index != limit; new_index += step) {
+      if (join->predecessors_[new_index + step]->block_id() > new_id) break;

[Kevin Millikin (Google), 2012/10/22 14:13:11]

Split this loop so that the comparison works for both iteration directions.

+      join->predecessors_[new_index] = join->predecessors_[new_index + step];
+    }
+    join->predecessors_[new_index] = new_block;
+    // If the new and old predecessor index match there is nothing to update.
+    if ((join->phis() == NULL) || (old_index == new_index)) return;
+    // 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(old_index);
+      // Move uses between old and new.
+      for (intptr_t use_idx = old_index;
+           use_idx != new_index;
+           use_idx += step) {
+        Value* use = phi->InputAt(use_idx + step);
+        phi->SetInputAt(use_idx, use);
+        use->set_use_index(use_idx);
+      }
+      // Write the predecessor use.
+      phi->SetInputAt(new_index, pred_use);
+      pred_use->set_use_index(new_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);
-      // The callee return is now the immediate dominator of blocks whose
+      BlockEntryInstr* exit_block = exit->GetBlock();
+      // Pictorially, the graph structure is:
+      //
+      //   Bc : caller_entry    Bi : callee_entry
+      //     before_call          inlined_head
+      //     call               ... other blocks ...
+      //     after_call         Be : exit_block
+      //                          inlined_foot
+      // And becomes:
+      //
+      //   Bc : caller_entry
+      //     before_call
+      //     inlined_head
+      //   ... other blocks ...
+      //   Be : exit_block
+      //    inlined_foot
+      //    after_call
+      //
+      // For 'after_call', caller entry (Bc) is replaced by callee exit (Be).
+      ReplaceBlock(caller_entry, exit_block);
+      // For 'inlined_head', callee entry (Bi) is replaced by caller entry (Bc).
+      ReplaceBlock(callee_entry, caller_entry);
+      // The callee exit 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();
     }
   } 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();
+    // Replace the blocks after splitting (see comment in the len=1 case above).
+    ReplaceBlock(caller_entry, join);
+    ReplaceBlock(callee_entry, caller_entry);
+    // Update the last instruction pointers on each exit (ie, to the new goto).
+    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