Move code around in preparation for better inlining.

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 740 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 replace a predecessor block. For each successor of 'old_block', the
-// predecessors will be reordered to preserve block-order sorting of the
-// predecessors as well as the phis if the successor is a join.
-void FlowGraph::ReplacePredecessor(BlockEntryInstr* 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;
-    }
-    // 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);
-    // Find the new predecessor index while reordering the predecessors.
-    intptr_t new_id = new_block->block_id();
-    intptr_t new_index = old_index;
-    if (old_block->block_id() < new_id) {
-      // Search upwards, bubbling down intermediate predecessors.
-      for (; new_index < pred_count - 1; ++new_index) {
-        if (join->predecessors_[new_index + 1]->block_id() > new_id) break;
-        join->predecessors_[new_index] = join->predecessors_[new_index + 1];
-      }
-    } else {
-      // Search downwards, bubbling up intermediate predecessors.
-      for (; new_index > 0; --new_index) {
-        if (join->predecessors_[new_index - 1]->block_id() < new_id) break;
-        join->predecessors_[new_index] = join->predecessors_[new_index - 1];
-      }
-    }
-    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.
-      intptr_t step = (old_index < new_index) ? 1 : -1;
-      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);
-    }
-  }
-}
-
-
-// Inline a flow graph at a call site.
-//
-// Assumes the callee graph was computed by BuildGraph with an inlining context
-// and transformed to SSA with ComputeSSA with a correct virtual register
-// number, and that the use lists have been correctly computed.
-//
-// 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,
-                           ValueInliningContext* inlining_context) {
-  ASSERT(call->previous() != NULL);
-  ASSERT(call->next() != 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());
-
-  // 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();
-
-  BlockEntryInstr* caller_entry = call->GetBlock();
-  TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry();
-
-  // Attach the outer environment on each instruction in the callee graph.
-  for (BlockIterator block_it = callee_graph->postorder_iterator();
-       !block_it.Done();
-       block_it.Advance()) {
-    for (ForwardInstructionIterator it(block_it.Current());
-         !it.Done();
-         it.Advance()) {
-      Instruction* instr = it.Current();
-      // TODO(zerny): Avoid creating unnecessary environments. Note that some
-      // optimizations need deoptimization info for non-deoptable instructions,
-      // eg, LICM on GOTOs.
-      if (instr->env() != NULL) call->env()->DeepCopyToOuter(instr);
-    }
-  }
-
-  // Insert the callee graph into the caller graph.  First sort the list of
-  // exits by block id (recording block entries as a side effect).
-  inlining_context->SortExits();
-  if (inlining_context->NumExits() == 0) {
-    // TODO(zerny): Add support for non-local exits, such as throw.
-    UNREACHABLE();
-  } else if (inlining_context->NumExits() == 1) {
-    // For just one exit, replace the uses and remove the call from the graph.
-    call->ReplaceUsesWith(inlining_context->ValueAt(0)->definition());
-    call->previous()->LinkTo(callee_entry->next());
-    inlining_context->LastInstructionAt(0)->LinkTo(call->next());
-    // 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) {
-      BlockEntryInstr* exit_block = inlining_context->ExitBlockAt(0);
-      // 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).
-      ReplacePredecessor(caller_entry, exit_block);
-      // For 'inlined_head', callee entry (Bi) is replaced by caller entry (Bc).
-      ReplacePredecessor(callee_entry, caller_entry);
-      // The callee exit is now the immediate dominator of blocks whose
-      // immediate dominator was the caller entry.
-      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);
-      }
-    }
-  } else {
-    // Create a join of the returns.
-    JoinEntryInstr* join =
-        new JoinEntryInstr(++max_block_id_, CatchClauseNode::kInvalidTryIndex);
-    intptr_t count = inlining_context->NumExits();
-    for (intptr_t i = 0; i < count; ++i) {
-      inlining_context->LastInstructionAt(i)->Goto(join);
-      // Directly add the predecessors of the join in ascending block id order.
-      join->predecessors_.Add(inlining_context->ExitBlockAt(i));
-    }
-    // If the call has uses, create a phi of the returns.
-    if (call->HasUses()) {
-      // Environment count: length before call - argument count (+ return)
-      intptr_t env_count = call->env()->Length() - call->ArgumentCount();
-      // 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 < count; ++i) {
-        Value* value = inlining_context->ValueAt(i);
-        phi->SetInputAt(i, value);
-        value->set_instruction(phi);
-        value->set_use_index(i);
-      }
-      // Replace uses of the call with the phi.
-      call->ReplaceUsesWith(phi);
-    }
-    // Remove the call from the graph.
-    call->previous()->LinkTo(callee_entry->next());
-    join->LinkTo(call->next());
-    // Replace the blocks after splitting (see comment in the len=1 case above).
-    ReplacePredecessor(caller_entry, join);
-    ReplacePredecessor(callee_entry, caller_entry);
-    // Update the last instruction pointers on each exit block to the new goto.
-    for (intptr_t i = 0; i < count; ++i) {
-      inlining_context->ExitBlockAt(i)->set_last_instruction(
-          inlining_context->LastInstructionAt(i)->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