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 253 matching lines @@
   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);
 }
 
 
+void FlowGraph::ComputeSSAForInlining(
+    intptr_t callers_max_virtual_register_number) {
+  current_ssa_temp_index_ = callers_max_virtual_register_number;
+  ComputeSSA();
+}
+
+
 // 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.
 //
 // preorder: an input list of basic block entries in preorder.  The
 //     algorithm relies on the block ordering.
 //
 // parent: an input parameter encoding a depth-first spanning tree of
 //     the control flow graph.  The array maps the preorder block
 //     number of a block to the preorder block number of its spanning
@@ skipping 366 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 ancestor of an instruction.

[Kevin Millikin (Google), 2012/08/29 14:01:04]

'ancestor' makes me think of trees.

[zerny-google, 2012/08/30 07:31:40]

Done.

+static BlockEntryInstr* GetBlockEntry(Instruction* instr) {
+  while (!instr->IsBlockEntry()) instr = instr->previous();
+  return instr->AsBlockEntry();
+}
+
+
+// Helper to link two instruction in the graph.

[srdjan, 2012/08/29 21:31:33]

s/instruction/instructions/

[zerny-google, 2012/08/30 07:31:40]

Done.

+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());
+    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());
+    push->RemoveFromGraph();
+  }
+}
+
+
 }  // namespace dart