Reapply "Inlining of static calls with trivial function bodies."

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"
+#include "vm/growable_array.h"
 
 namespace dart {
 
 FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
                      GraphEntryInstr* graph_entry)
   : parent_(),
     assigned_vars_(),
     current_ssa_temp_index_(0),
     parsed_function_(builder.parsed_function()),
     copied_parameter_count_(builder.copied_parameter_count()),
     non_copied_parameter_count_(builder.non_copied_parameter_count()),
     stack_local_count_(builder.stack_local_count()),
     graph_entry_(graph_entry),
     preorder_(),
     postorder_(),
-    reverse_postorder_() {
+    reverse_postorder_(),
+    exits_(NULL) {
   DiscoverBlocks();
 }
 
 
 void FlowGraph::DiscoverBlocks() {
   // Initialize state.
   preorder_.TruncateTo(0);
   postorder_.TruncateTo(0);
   reverse_postorder_.TruncateTo(0);
   parent_.TruncateTo(0);
@@ skipping 248 matching lines @@
 }
 
 
 void FlowGraph::ComputeUseLists() {
   DEBUG_ASSERT(ResetUseLists());
   ComputeUseListsRecursive(graph_entry_);
   DEBUG_ASSERT(ValidateUseLists());
 }
 
 
-void FlowGraph::ComputeSSA() {
+void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number) {
+  current_ssa_temp_index_ = next_virtual_register_number;
   GrowableArray<BitVector*> dominance_frontier;
   ComputeDominators(&preorder_, &parent_, &dominance_frontier);
   InsertPhis(preorder_, assigned_vars_, dominance_frontier);
   GrowableArray<PhiInstr*> live_phis;
   // Rename uses to reference inserted phis where appropriate.
   // Collect phis that reach a non-environment use.
   Rename(&live_phis);
   // Propagate alive mark transitively from alive phis.
   MarkLivePhis(&live_phis);
 }
@@ skipping 367 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 get the block-entry of an instruction.
+static BlockEntryInstr* GetBlockEntry(Instruction* instr) {
+  while (!instr->IsBlockEntry()) instr = instr->previous();
+  return instr->AsBlockEntry();
+}
+
+
+// Helper to link two instructions in the graph.
+static void Link(Instruction* prev, Instruction* next) {
+  ASSERT(prev != next);
+  prev->set_next(next);
+  next->set_previous(prev);
+}
+
+
+// Inline a flow graph at a call site.
+//
+// Assumes the callee graph was computed with BuildGraphForInlining and
+// transformed to SSA with ComputeSSAForInlining, 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(BindInstr* caller_instr,
+                           StaticCallComp* caller_comp,
+                           FlowGraph* callee_graph) {
+  ASSERT(callee_graph->exits() != NULL);
+  ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1);
+  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 SSA temp index by the callee graph's index.
+  current_ssa_temp_index_ = callee_graph->max_virtual_register_number();
+
+  TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry();
+  ZoneGrowableArray<ReturnInstr*>* callee_exits = callee_graph->exits();
+
+  // 1. Insert the callee graph into the caller graph.
+  if (callee_exits->length() == 1) {
+    ReturnInstr* exit = (*callee_exits)[0];
+    // TODO(zerny): Support one exit graph containing control flow.
+    ASSERT(callee_entry == GetBlockEntry(exit));
+    // For just one exit, replace the uses and remove the call from the graph.
+    caller_instr->ReplaceUsesWith(exit->value()->AsUse()->definition());
+    Link(caller_instr->previous(), callee_entry->next());
+    Link(exit->previous(), caller_instr->next());
+  } else {
+    // TODO(zerny): Support multiple exits.
+    UNREACHABLE();
+  }
+
+  // TODO(zerny): Adjust pre/post orders.
+  // TODO(zerny): Update dominator tree.
+
+  // Remove original arguments to the call.
+  for (intptr_t i = 0; i < caller_comp->ArgumentCount(); ++i) {
+    PushArgumentInstr* push = caller_comp->ArgumentAt(i);
+    push->ReplaceUsesWith(push->value()->AsUse()->definition());
+    push->RemoveFromGraph();
+  }
+}
+
+
 }  // namespace dart