Generate some intrinsics using our IR.

runtime/vm/intrinsifier.cc

Index: runtime/vm/intrinsifier.cc
===================================================================
--- runtime/vm/intrinsifier.cc	(revision 39909)
+++ runtime/vm/intrinsifier.cc	(working copy)
@@ -9,10 +9,21 @@
 #include "vm/object.h"
 #include "vm/symbols.h"
 
+#include "vm/flow_graph.h"

[zra, 2014/09/05 20:26:50]

Maybe alphabetize includes.

+#include "vm/flow_graph_compiler.h"
+#include "vm/flow_graph_allocator.h"
+#include "vm/flow_graph_builder.h"
+#include "vm/il_printer.h"
+#include "vm/intermediate_language.h"
+#include "vm/parser.h"
+
 namespace dart {
 
 DEFINE_FLAG(bool, intrinsify, true, "Instrinsify when possible");
 DECLARE_FLAG(bool, throw_on_javascript_int_overflow);
+DECLARE_FLAG(bool, code_comments);
+DECLARE_FLAG(bool, print_flow_graph);
+DECLARE_FLAG(bool, print_flow_graph_optimized);
 
 bool Intrinsifier::CanIntrinsify(const Function& function) {
   if (!FLAG_intrinsify) return false;
@@ -59,6 +70,7 @@
   ASSERT(!lib.IsNull());
   CORE_LIB_INTRINSIC_LIST(SETUP_FUNCTION);
   CORE_INTEGER_LIB_INTRINSIC_LIST(SETUP_FUNCTION);
+  GRAPH_CORE_INTRINSICS_LIST(SETUP_FUNCTION);
 
   // Set up all math lib functions that can be intrisified.
   lib = Library::MathLibrary();
@@ -69,6 +81,7 @@
   lib = Library::TypedDataLibrary();
   ASSERT(!lib.IsNull());
   TYPED_DATA_LIB_INTRINSIC_LIST(SETUP_FUNCTION);
+  GRAPH_TYPED_DATA_INTRINSICS_LIST(SETUP_FUNCTION);
 
   // Setup all dart:profiler lib functions that can be intrinsified.
   lib = Library::ProfilerLibrary();
@@ -79,14 +92,99 @@
 }
 
 
-void Intrinsifier::Intrinsify(const Function& function, Assembler* assembler) {
+static void EmitCodeFor(FlowGraphCompiler* compiler,
+                        FlowGraph* graph) {
+  compiler->assembler()->Comment("Graph intrinsic");
+  for (intptr_t i = 0; i < graph->reverse_postorder().length(); i++) {
+    BlockEntryInstr* block = graph->reverse_postorder()[i];
+    if (block->IsGraphEntry()) continue;  // No code for graph entry needed.
+    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+      Instruction* instr = it.Current();
+      if (FLAG_code_comments) compiler->EmitComment(instr);
+      if (instr->IsParallelMove()) {
+        compiler->parallel_move_resolver()->EmitNativeCode(
+            instr->AsParallelMove());
+      } else {
+        ASSERT(instr->locs() != NULL);
+        // Calls are not supported in intrinsics code.
+        ASSERT(!instr->locs()->always_calls());
+        // Intrinsic code only allows constants that can always be loaded
+        // without constant pool on all platforms. There is no constant pool
+        // register set up in intrinsic code. We could allow old-space constants
+        // as they don't move, but restrict to smi and VM objects for now.

[zra, 2014/09/05 20:26:51]

The Assemblers for each arch know which VM objects are always available in the
constant pool, and for which you don't need the pool for the current function,
so long as a Dart frame has been entered at some point before entering an
intrinsic (we've already made sure that's the case). The flag for
enabling/disabling constant pool access in the Assemblers should defer to that
logic and possibly be renamed to reflect this. Otherwise, e.g. loading
Bool::True and Bool::False in intrinsics on arm64 will be as many as four
instructions each, which we'd probably like to avoid, and code size on x64 will
grow due to large immediate loads.

[Florian Schneider, 2014/09/08 11:12:39]

Done.

+        ASSERT(!instr->IsConstant() ||
+               (instr->AsConstant()->value().IsSmi() ||
+                instr->AsConstant()->value().InVMHeap()));
+        instr->EmitNativeCode(compiler);
+      }
+    }
+  }
+}
+
+
+bool Intrinsifier::GraphIntrinsify(const ParsedFunction& parsed_function,
+                                   FlowGraphCompiler* compiler) {
+  ZoneGrowableArray<const ICData*>* ic_data_array =
+      new ZoneGrowableArray<const ICData*>();
+  FlowGraphBuilder builder(const_cast<ParsedFunction*>(&parsed_function),
+                           *ic_data_array,
+                           NULL,  // NULL = not inlining.
+                           -1);  // No OSR id.
+
+  intptr_t block_id = builder.AllocateBlockId();
+  TargetEntryInstr* normal_entry =
+      new TargetEntryInstr(block_id,
+                           CatchClauseNode::kInvalidTryIndex);
+  GraphEntryInstr* graph_entry = new GraphEntryInstr(
+      &parsed_function, normal_entry, -1);  // No OSR id.
+  FlowGraph* graph = new FlowGraph(builder, graph_entry, block_id);
+  const Function& function = parsed_function.function();
+  switch (function.recognized_kind()) {
+#define EMIT_CASE(test_class_name, test_function_name, enum_name, fp)          \
+    case MethodRecognizer::k##enum_name:                                       \
+      ASSERT(function.CheckSourceFingerprint(fp));                             \
+      if (!Build_##enum_name(graph)) return false;                             \
+      break;
+
+    GRAPH_INTRINSICS_LIST(EMIT_CASE);
+    default:
+      return false;
+#undef EMIT_CASE
+  }
+
+  if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) {
+    OS::Print("Intrinsic graph before\n");
+    FlowGraphPrinter printer(*graph);
+    printer.PrintBlocks();
+  }
+
+  // Perform register allocation on the SSA graph.
+  FlowGraphAllocator allocator(*graph, true);  // Intrinsic mode.
+  allocator.AllocateRegisters();
+
+  if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) {
+    OS::Print("Intrinsic graph after\n");
+    FlowGraphPrinter printer(*graph);
+    printer.PrintBlocks();
+  }
+  EmitCodeFor(compiler, graph);
+  return true;
+}
+
+
+void Intrinsifier::Intrinsify(const ParsedFunction& parsed_function,
+                              FlowGraphCompiler* compiler) {
+  const Function& function = parsed_function.function();
   if (!CanIntrinsify(function)) return;

[zra, 2014/09/05 20:26:50]

Please add curly braces.

[Florian Schneider, 2014/09/08 11:12:40]

Done.

 
+  if (GraphIntrinsify(parsed_function, compiler)) return;

[zra, 2014/09/05 20:26:51]

Here, too.

[Florian Schneider, 2014/09/08 11:12:40]

Done.

+
+
 #define EMIT_CASE(test_class_name, test_function_name, enum_name, fp)          \
     case MethodRecognizer::k##enum_name:                                       \
       ASSERT(function.CheckSourceFingerprint(fp));                             \
-      assembler->Comment("Intrinsic");                                         \
-      enum_name(assembler);                                                    \
+      compiler->assembler()->Comment("Intrinsic");                             \
+      enum_name(compiler->assembler());                                        \
       break;
 
   if (FLAG_throw_on_javascript_int_overflow && (Smi::kBits >= 32)) {
@@ -94,20 +192,13 @@
     // intrinsify when Smi > 32 bits if we are looking for javascript integer
     // overflow.
     switch (function.recognized_kind()) {
-      CORE_LIB_INTRINSIC_LIST(EMIT_CASE);
-      MATH_LIB_INTRINSIC_LIST(EMIT_CASE);
-      TYPED_DATA_LIB_INTRINSIC_LIST(EMIT_CASE);
-      PROFILER_LIB_INTRINSIC_LIST(EMIT_CASE);
+      ALL_INTRINSICS_NO_INTEGER_LIB_LIST(EMIT_CASE);
       default:
         break;
     }
   } else {
     switch (function.recognized_kind()) {
-      CORE_LIB_INTRINSIC_LIST(EMIT_CASE);
-      CORE_INTEGER_LIB_INTRINSIC_LIST(EMIT_CASE);
-      MATH_LIB_INTRINSIC_LIST(EMIT_CASE);
-      TYPED_DATA_LIB_INTRINSIC_LIST(EMIT_CASE);
-      PROFILER_LIB_INTRINSIC_LIST(EMIT_CASE);
+      ALL_INTRINSICS_LIST(EMIT_CASE);
       default:
         UNREACHABLE();
         break;
@@ -116,4 +207,353 @@
 #undef EMIT_INTRINSIC
 }
 
+
+class BlockBuilder : public ValueObject {
+ public:
+  BlockBuilder(FlowGraph* flow_graph, TargetEntryInstr* entry)
+      : flow_graph_(flow_graph), entry_(entry), current_(entry) { }
+
+  Definition* AddToInitialDefinitions(Definition* def) {
+    def->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
+    flow_graph_->AddToInitialDefinitions(def);
+    return def;
+  }
+
+  Definition* AddDefinition(Definition* def) {
+    def->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
+    current_ = current_->AppendInstruction(def);
+    return def;
+  }
+
+  Instruction* AddInstruction(Instruction* instr) {
+    current_ = current_->AppendInstruction(instr);
+    return instr;
+  }
+
+  void AddIntrinsicReturn(Value* value) {
+    ReturnInstr* instr = new ReturnInstr(-1,  // No token position.

[zra, 2014/09/05 20:26:51]

Scanner::kNoSourcePos ?

[Florian Schneider, 2014/09/08 11:12:40]

Replaced with function.token_pos()

+                                         value);
+    AddInstruction(instr);
+    entry_->set_last_instruction(instr);
+  }
+
+  Definition* AddParameter(intptr_t index) {
+    intptr_t adjustment = Intrinsifier::ParameterSlotFromSp();
+    return AddToInitialDefinitions(
+      new ParameterInstr(adjustment + index,
+                         flow_graph_->graph_entry(),
+                         SPREG));
+  }
+
+
+ private:
+  FlowGraph* flow_graph_;
+  BlockEntryInstr* entry_;
+  Instruction* current_;
+};
+
+
+static void PrepareIndexedOp(BlockBuilder* builder,
+                             Definition* array,
+                             Definition* index,
+                             intptr_t length_offset) {
+  builder->AddInstruction(
+      new CheckSmiInstr(new Value(index),
+                        Isolate::kNoDeoptId,
+                        -1));  // no token pos

[zra, 2014/09/05 20:26:51]

Scanner::kNoSourcePos ?

period after comment.

+
+  Definition* length = builder->AddDefinition(
+      new LoadFieldInstr(new Value(array),
+                         length_offset,
+                         Type::ZoneHandle(Type::SmiType()),
+                         true));  // immutable

[zra, 2014/09/05 20:26:51]

period after comment.

+  builder->AddInstruction(
+      new CheckArrayBoundInstr(new Value(length),
+                               new Value(index),
+                               Isolate::kNoDeoptId));
+}
+
+
+bool Intrinsifier::Build_ObjectArrayGetIndexed(FlowGraph* flow_graph) {
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* index = builder.AddParameter(1);
+  Definition* array = builder.AddParameter(2);
+
+  PrepareIndexedOp(&builder, array, index, Array::length_offset());
+
+  Definition* result = builder.AddDefinition(
+      new LoadIndexedInstr(new Value(array),
+                           new Value(index),
+                           Instance::ElementSizeFor(kArrayCid),  // index scale

[zra, 2014/09/05 20:26:51]

ditto.

+                           kArrayCid,
+                           Isolate::kNoDeoptId,
+                           -1));  // no token pos

[zra, 2014/09/05 20:26:51]

ditto.

+  builder.AddIntrinsicReturn(new Value(result));
+  return true;
+}
+
+
+bool Intrinsifier::Build_ImmutableArrayGetIndexed(FlowGraph* flow_graph) {
+  return Build_ObjectArrayGetIndexed(flow_graph);
+}
+
+
+bool Intrinsifier::Build_Uint8ArrayGetIndexed(FlowGraph* flow_graph) {
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* index = builder.AddParameter(1);
+  Definition* array = builder.AddParameter(2);
+
+  PrepareIndexedOp(&builder, array, index, TypedData::length_offset());
+
+  Definition* result = builder.AddDefinition(
+      new LoadIndexedInstr(new Value(array),
+                           new Value(index),
+                           1,  // index scale

[zra, 2014/09/05 20:26:51]

ditto.

+                           kTypedDataUint8ArrayCid,
+                           Isolate::kNoDeoptId,
+                           -1));  // no token pos

[zra, 2014/09/05 20:26:52]

ditto.

+  builder.AddIntrinsicReturn(new Value(result));
+  return true;
+}
+
+
+bool Intrinsifier::Build_ExternalUint8ArrayGetIndexed(FlowGraph* flow_graph) {
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* index = builder.AddParameter(1);
+  Definition* array = builder.AddParameter(2);
+
+  PrepareIndexedOp(&builder, array, index, ExternalTypedData::length_offset());
+
+  Definition* elements = builder.AddDefinition(
+      new LoadUntaggedInstr(new Value(array),
+                            ExternalTypedData::data_offset()));
+  Definition* result = builder.AddDefinition(
+      new LoadIndexedInstr(new Value(elements),
+                           new Value(index),
+                           1,  // index scale

[zra, 2014/09/05 20:26:50]

ditto.

+                           kExternalTypedDataUint8ArrayCid,
+                           Isolate::kNoDeoptId,
+                           -1));  // no token pos

[zra, 2014/09/05 20:26:51]

ditto.

+  builder.AddIntrinsicReturn(new Value(result));
+  return true;
+}
+
+
+bool Intrinsifier::Build_Uint8ArraySetIndexed(FlowGraph* flow_graph) {
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* value = builder.AddParameter(1);
+  Definition* index = builder.AddParameter(2);
+  Definition* array = builder.AddParameter(3);
+
+  PrepareIndexedOp(&builder, array, index, TypedData::length_offset());
+
+  builder.AddInstruction(
+      new CheckSmiInstr(new Value(value),
+                        Isolate::kNoDeoptId,
+                        -1));  // no token pos

[zra, 2014/09/05 20:26:51]

ditto.

+
+  builder.AddInstruction(
+      new StoreIndexedInstr(new Value(array),
+                            new Value(index),
+                            new Value(value),
+                            kNoStoreBarrier,
+                            1,  // index scale

[zra, 2014/09/05 20:26:51]

ditto.

+                            kTypedDataUint8ArrayCid,
+                            Isolate::kNoDeoptId,
+                            -1));  // no token pos.

[zra, 2014/09/05 20:26:50]

ditto.

+  // Return null.
+  Definition* null_def = builder.AddDefinition(
+      new ConstantInstr(Object::ZoneHandle(Object::null())));
+  builder.AddIntrinsicReturn(new Value(null_def));
+  return true;
+}
+
+
+bool Intrinsifier::Build_ExternalUint8ArraySetIndexed(FlowGraph* flow_graph) {
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* value = builder.AddParameter(1);
+  Definition* index = builder.AddParameter(2);
+  Definition* array = builder.AddParameter(3);
+
+  PrepareIndexedOp(&builder, array, index, ExternalTypedData::length_offset());
+
+  builder.AddInstruction(
+      new CheckSmiInstr(new Value(value),
+                        Isolate::kNoDeoptId,
+                        -1));  // no token pos

[zra, 2014/09/05 20:26:52]

ditto.

+  Definition* elements = builder.AddDefinition(
+      new LoadUntaggedInstr(new Value(array),
+                            ExternalTypedData::data_offset()));
+  builder.AddInstruction(
+      new StoreIndexedInstr(new Value(elements),
+                            new Value(index),
+                            new Value(value),
+                            kNoStoreBarrier,
+                            1,  // index scale

[zra, 2014/09/05 20:26:50]

ditto.

+                            kExternalTypedDataUint8ArrayCid,
+                            Isolate::kNoDeoptId,
+                            -1));  // no token pos.

[zra, 2014/09/05 20:26:50]

ditto.

+  // Return null.
+  Definition* null_def = builder.AddDefinition(
+      new ConstantInstr(Object::ZoneHandle(Object::null())));
+  builder.AddIntrinsicReturn(new Value(null_def));
+  return true;
+}
+
+
+bool Intrinsifier::Build_Float64ArraySetIndexed(FlowGraph* flow_graph) {
+  if (!FlowGraphCompiler::SupportsUnboxedDoubles()) return false;
+
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* value = builder.AddParameter(1);
+  Definition* index = builder.AddParameter(2);
+  Definition* array = builder.AddParameter(3);
+
+  PrepareIndexedOp(&builder, array, index, TypedData::length_offset());
+
+  const ICData& value_check = ICData::ZoneHandle(ICData::New(
+      flow_graph->parsed_function().function(),
+      String::Handle(flow_graph->parsed_function().function().name()),
+      Object::empty_array(),  // Dummy args. descr.
+      Isolate::kNoDeoptId,
+      1));
+  value_check.AddReceiverCheck(kDoubleCid,
+                               flow_graph->parsed_function().function());
+  builder.AddInstruction(
+      new CheckClassInstr(new Value(value),
+                          Isolate::kNoDeoptId,
+                          value_check,
+                          -1));

[zra, 2014/09/05 20:26:51]

ditto.

+  Definition* double_value = builder.AddDefinition(
+      new UnboxDoubleInstr(new Value(value), Isolate::kNoDeoptId));
+  // Manually adjust reaching type because there is no type propagation
+  // when building intrinsics.
+  double_value->AsUnboxDouble()->value()->SetReachingType(
+      ZoneCompileType::Wrap(CompileType::FromCid(kDoubleCid)));
+
+  builder.AddInstruction(
+      new StoreIndexedInstr(new Value(array),
+                            new Value(index),
+                            new Value(double_value),
+                            kNoStoreBarrier,
+                            8,  // index scale

[zra, 2014/09/05 20:26:51]

ditto.

+                            kTypedDataFloat64ArrayCid,
+                            Isolate::kNoDeoptId,
+                            -1));  // no token pos.

[zra, 2014/09/05 20:26:50]

ditto.

+  // Return null.
+  Definition* null_def = builder.AddDefinition(
+      new ConstantInstr(Object::ZoneHandle(Object::null())));
+  builder.AddIntrinsicReturn(new Value(null_def));
+  return true;
+}
+
+
+bool Intrinsifier::Build_Float64ArrayGetIndexed(FlowGraph* flow_graph) {
+  if (!FlowGraphCompiler::SupportsUnboxedDoubles()) return false;
+
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* index = builder.AddParameter(1);
+  Definition* array = builder.AddParameter(2);
+
+  PrepareIndexedOp(&builder, array, index, TypedData::length_offset());
+
+  Definition* unboxed_value = builder.AddDefinition(
+      new LoadIndexedInstr(new Value(array),
+                           new Value(index),
+                           8,  // index scale

[zra, 2014/09/05 20:26:51]

ditto.

+                           kTypedDataFloat64ArrayCid,
+                           Isolate::kNoDeoptId,
+                           -1));  // no token pos

[zra, 2014/09/05 20:26:52]

ditto.

+  Definition* result = builder.AddDefinition(
+      new BoxDoubleInstr(new Value(unboxed_value)));
+  builder.AddIntrinsicReturn(new Value(result));
+  return true;
+}
+
+
+static bool BuildLoadField(FlowGraph* flow_graph, intptr_t offset) {
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* array = builder.AddParameter(1);
+
+  Definition* length = builder.AddDefinition(
+      new LoadFieldInstr(new Value(array),
+                         offset,
+                         Type::ZoneHandle(),
+                         -1));  // No token pos

[zra, 2014/09/05 20:26:51]

ditto.

+  builder.AddIntrinsicReturn(new Value(length));
+  return true;
+}
+
+
+bool Intrinsifier::Build_ObjectArrayLength(FlowGraph* flow_graph) {
+  return BuildLoadField(flow_graph, Array::length_offset());
+}
+
+
+bool Intrinsifier::Build_ImmutableArrayLength(FlowGraph* flow_graph) {
+  return BuildLoadField(flow_graph, Array::length_offset());
+}
+
+
+bool Intrinsifier::Build_GrowableArrayLength(FlowGraph* flow_graph) {
+  return BuildLoadField(flow_graph, GrowableObjectArray::length_offset());
+}
+
+
+bool Intrinsifier::Build_StringBaseLength(FlowGraph* flow_graph) {
+  return BuildLoadField(flow_graph, String::length_offset());
+}
+
+
+bool Intrinsifier::Build_TypedDataLength(FlowGraph* flow_graph) {
+  return BuildLoadField(flow_graph, TypedData::length_offset());
+}
+
+
+bool Intrinsifier::Build_GrowableArrayCapacity(FlowGraph* flow_graph) {
+  GraphEntryInstr* graph_entry = flow_graph->graph_entry();
+  TargetEntryInstr* normal_entry = graph_entry->normal_entry();
+  BlockBuilder builder(flow_graph, normal_entry);
+
+  Definition* array = builder.AddParameter(1);
+
+  Definition* backing_store = builder.AddDefinition(
+      new LoadFieldInstr(new Value(array),
+                         GrowableObjectArray::data_offset(),
+                         Type::ZoneHandle(),
+                         -1));  // No token pos

[zra, 2014/09/05 20:26:50]

ditto.

+  Definition* capacity = builder.AddDefinition(
+      new LoadFieldInstr(new Value(backing_store),
+                         Array::length_offset(),
+                         Type::ZoneHandle(),
+                         -1));  // No token pos

[zra, 2014/09/05 20:26:51]

ditto.

+  builder.AddIntrinsicReturn(new Value(capacity));
+  return true;
+}
+
+
 }  // namespace dart