Inlining of static calls with trivial function bodies.

runtime/vm/flow_graph_inliner.cc

Index: runtime/vm/flow_graph_inliner.cc
diff --git a/runtime/vm/flow_graph_inliner.cc b/runtime/vm/flow_graph_inliner.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ef20c6568b8376bbc0e7f3536aa8b175187a4620
--- /dev/null
+++ b/runtime/vm/flow_graph_inliner.cc
@@ -0,0 +1,219 @@
+// 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_inliner.h"
+
+#include "vm/object.h"

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

These are normally sorted alphabetically (M-x sort-lines).

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

Done.

+#include "vm/object_store.h"
+#include "vm/flags.h"
+#include "vm/flow_graph.h"
+#include "vm/flow_graph_builder.h"
+#include "vm/il_printer.h"
+#include "vm/longjump.h"
+
+namespace dart {
+
+DEFINE_FLAG(bool, trace_inlining, false, "Trace inlining");
+DEFINE_FLAG(charp, inlining_filter, NULL, "Inline only in named function");
+DECLARE_FLAG(bool, print_flow_graph);
+
+class CallSiteInliner : public FlowGraphVisitor {
+ public:
+  explicit CallSiteInliner(FlowGraph* flow_graph)
+      : FlowGraphVisitor(flow_graph->postorder()),
+        caller_graph_(flow_graph),
+        next_ssa_temp_index_(flow_graph->max_virtual_register_number()),
+        inlined_(false) { }
+

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

Too many blank lines.

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

Done.

+
+  void TryInlining(const Function& function,
+                   GrowableArray<Value*>* arguments,
+                   StaticCallComp* comp,  // TODO(zerny): Generalize to calls.
+                   BindInstr* instr) {
+    // Parse the callee function.
+    ParsedFunction parsed_function(function);
+    Parser::ParseFunction(&parsed_function);
+    FlowGraphBuilder builder(parsed_function);
+
+    // Install bailout jump.
+    Isolate* isolate = Isolate::Current();
+    LongJump* base = isolate->long_jump_base();
+    LongJump jump;
+    isolate->set_long_jump_base(&jump);
+    if (setjmp(*jump.Set()) == 0) {
+      // Build the callee graph.
+      FlowGraph* callee_graph =
+          builder.BuildGraphForInlining(FlowGraphBuilder::kValueContext);
+
+      // Bailout if the callee graph contains control flow.
+      if (callee_graph->preorder().length() != 2) {
+        isolate->set_long_jump_base(base);
+        if (FLAG_trace_inlining) {
+          OS::Print("Inline aborted %s\nReason: control flow\n",
+                    parsed_function.function().ToFullyQualifiedCString());
+        }
+        return;
+      }
+
+      // Bailout if the formal/actual parameter count does not match.
+      if (arguments->length() != callee_graph->parameter_count()) {
+        if (FLAG_trace_inlining) {
+          OS::Print("Inline aborted %s\nReason: formal/actual mismatch\n",
+                    parsed_function.function().ToFullyQualifiedCString());
+        }
+        return;
+      }

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

You may also want to bailout if the callee has named arguments, since you do not
know if the order at caller matches.

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

Done.

+
+      if (FLAG_trace_inlining && FLAG_print_flow_graph) {
+        OS::Print("Callee graph for inlining %s\n",

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

Might be useful to write 'before SSA' here and 'after SSA' later.

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

Done.

+                  parsed_function.function().ToFullyQualifiedCString());
+        FlowGraphPrinter printer(*callee_graph);
+        printer.PrintBlocks();
+      }
+
+      // Compute SSA on the callee graph. (catching bailouts)
+      callee_graph->ComputeSSAForInlining(next_ssa_temp_index_);
+
+      // Build succeeded so we restore the bailout jump.
+      isolate->set_long_jump_base(base);
+
+      if (FLAG_trace_inlining && FLAG_print_flow_graph) {
+        OS::Print("Callee graph for inlining %s\n",
+                  parsed_function.function().ToFullyQualifiedCString());
+        FlowGraphPrinter printer(*callee_graph);
+        printer.PrintBlocks();
+      }
+
+      callee_graph->ComputeUseLists();
+
+      // TODO(zerny): Do optimization passes on the callee graph.
+
+      // TODO(zerny): If result is more than size threshold then abort.
+
+      // TODO(zerny): If effort is less than threshold then inline recursively.
+
+      // Plug result in the caller graph.
+      caller_graph_->InlineCall(instr, comp, callee_graph);
+      next_ssa_temp_index_ = caller_graph_->max_virtual_register_number();
+
+      // Replace all the formal parameters with the actuals.
+      for (intptr_t i = 0; i < arguments->length(); ++i) {
+        Value* val = callee_graph->graph_entry()->start_env()->values()[i];
+        ASSERT(val != NULL && val->IsUse());
+        ParameterInstr* param = val->AsUse()->definition()->AsParameter();
+        ASSERT(param != NULL);
+        param->ReplaceUsesWith((*arguments)[i]);
+      }
+
+      inlined_ = true;
+      if (FLAG_trace_inlining) {
+        OS::Print("Inlined %s\n",
+                  parsed_function.function().ToFullyQualifiedCString());
+      }
+    } else {
+      Error& error = Error::Handle();
+      error = isolate->object_store()->sticky_error();
+      isolate->object_store()->clear_sticky_error();
+      isolate->set_long_jump_base(base);
+      if (FLAG_trace_inlining) {
+        OS::Print("Inline aborted for %s\nReason: %s\n",
+                  parsed_function.function().ToFullyQualifiedCString(),
+                  error.ToErrorCString());
+      }
+    }
+  }
+
+
+  void VisitBind(BindInstr* instr) {
+    instr->computation()->Accept(this, instr);
+  }
+
+  void VisitPolymorphicInstanceCall(PolymorphicInstanceCallComp* comp,
+                                    BindInstr* instr) {
+    // if (FLAG_trace_inlining) OS::Print("Polymorphic call\n");

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

Remove the commented-out code.

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

Done.

+  }
+
+  void VisitInstanceCall(InstanceCallComp* comp, BindInstr* instr) {
+    // if (FLAG_trace_inlining) OS::Print("Instance call\n");

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

remove dead code.

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

Done.

+  }
+
+  void VisitStaticCall(StaticCallComp* comp, BindInstr* instr) {
+    if (FLAG_trace_inlining) OS::Print("Static call\n");
+    GrowableArray<Value*> arguments(comp->ArgumentCount());
+    for (int i = 0; i < comp->ArgumentCount(); ++i) {
+      arguments.Add(comp->ArgumentAt(i)->value());
+    }
+    TryInlining(comp->function(), &arguments, comp, instr);
+  }
+
+  void VisitClosureCall(ClosureCallComp* comp, BindInstr* instr) {

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

Remove all this code for now, too.

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

Done.

+    if (FLAG_trace_inlining) OS::Print("Closure call\n");
+    // Find the closure of the callee.
+    ASSERT(comp->ArgumentCount() > 0);
+    UseVal* rator = comp->ArgumentAt(0)->value()->AsUse();
+    if (rator == NULL) {
+      if (FLAG_trace_inlining) OS::Print("Inline aborted: non-use operator.\n");
+      return;
+    }
+    BindInstr* defn = rator->definition()->AsBind();
+    if (defn == NULL) {
+      if (FLAG_trace_inlining) {
+        OS::Print("Inline aborted: non-bind operator.\n");
+      }
+      return;
+    }
+    const CreateClosureComp* closure = defn->computation()->AsCreateClosure();
+    if (closure == NULL) {
+      if (FLAG_trace_inlining) {
+        OS::Print("Inline aborted: non-closure operator.\n");
+      }
+      return;
+    }
+
+    GrowableArray<Value*> arguments(comp->ArgumentCount() - 1);
+    for (int i = 1; i < comp->ArgumentCount(); ++i) {
+      arguments.Add(comp->ArgumentAt(i)->value());
+    }
+
+    // TODO(zerny): Generalize TryInlining.
+    // TryInlining(closure->function(), &arguments, comp, instr);
+  }

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

Closure calls are rare in the benchmarks targeted. I would focus rather on
PolymorphicInstanceCall instead.

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

Ok.

+
+  bool inlined() const { return inlined_; }
+
+ private:
+  FlowGraph* caller_graph_;
+  intptr_t next_ssa_temp_index_;
+  bool inlined_;
+};
+
+
+void FlowGraphInliner::Inline() {
+  if ((FLAG_inlining_filter != NULL) &&
+      (strstr(flow_graph_->
+              parsed_function().function().ToFullyQualifiedCString(),
+              FLAG_inlining_filter) == NULL))
+    return;

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

Use curly braces if if-statement needs more than one line.

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

Done.

+
+  if (FLAG_trace_inlining && FLAG_print_flow_graph) {
+    OS::Print("Before Inlining of %s\n", flow_graph_->
+              parsed_function().function().ToFullyQualifiedCString());
+    FlowGraphPrinter printer(*flow_graph_);
+    printer.PrintBlocks();
+  }
+
+  CallSiteInliner inliner(flow_graph_);
+  inliner.VisitBlocks();
+
+  if (inliner.inlined()) {
+    if (FLAG_trace_inlining && FLAG_print_flow_graph) {
+      OS::Print("After Inlining of %s\n", flow_graph_->
+                parsed_function().function().ToFullyQualifiedCString());
+      FlowGraphPrinter printer(*flow_graph_);
+      printer.PrintBlocks();
+    }
+  }
+}
+
+}  // namespace dart