Inlining of static calls with trivial function bodies.

runtime/vm/flow_graph.cc

Index: runtime/vm/flow_graph.cc
diff --git a/runtime/vm/flow_graph.cc b/runtime/vm/flow_graph.cc
index 90cbd1e90730f1c9932c0b6db18b02e3e42c6930..00763d29e0a094e39e9547d5f0efea4a7aeee250 100644
--- a/runtime/vm/flow_graph.cc
+++ b/runtime/vm/flow_graph.cc
@@ -8,6 +8,7 @@
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
+#include "vm/growable_array.h"
 
 namespace dart {
 
@@ -23,7 +24,8 @@ FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
     graph_entry_(graph_entry),
     preorder_(),
     postorder_(),
-    reverse_postorder_() {
+    reverse_postorder_(),
+    exits_(NULL) {
   DiscoverBlocks();
 }
 
@@ -297,6 +299,13 @@ void FlowGraph::ComputeSSA() {
 }
 
 
+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.
@@ -683,4 +692,70 @@ void FlowGraph::Bailout(const char* reason) const {
 }
 
 
+// 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