Port and integrate the irregexp engine from V8

runtime/vm/compiler.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/compiler.h"
 
 #include "vm/assembler.h"
 
 #include "vm/ast_printer.h"
 #include "vm/block_scheduler.h"
@@ skipping 11 matching lines @@
 #include "vm/flow_graph_compiler.h"
 #include "vm/flow_graph_inliner.h"
 #include "vm/flow_graph_optimizer.h"
 #include "vm/flow_graph_type_propagator.h"
 #include "vm/il_printer.h"
 #include "vm/longjump.h"
 #include "vm/object.h"
 #include "vm/object_store.h"
 #include "vm/os.h"
 #include "vm/parser.h"
+#include "vm/regexp_parser.h"
+#include "vm/regexp_assembler.h"
 #include "vm/scanner.h"
 #include "vm/symbols.h"
 #include "vm/tags.h"
 #include "vm/timer.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, allocation_sinking, true,
     "Attempt to sink temporary allocations to side exits");
 DEFINE_FLAG(bool, common_subexpression_elimination, true,
@@ skipping 14 matching lines @@
 DEFINE_FLAG(bool, range_analysis, true, "Enable range analysis");
 DEFINE_FLAG(bool, reorder_basic_blocks, true, "Enable basic-block reordering.");
 DEFINE_FLAG(bool, trace_compiler, false, "Trace compiler operations.");
 DEFINE_FLAG(bool, trace_bailout, false, "Print bailout from ssa compiler.");
 DEFINE_FLAG(bool, use_inlining, true, "Enable call-site inlining");
 DEFINE_FLAG(bool, verify_compiler, false,
     "Enable compiler verification assertions");
 
 DECLARE_FLAG(bool, trace_failed_optimization_attempts);
 DECLARE_FLAG(bool, trace_patching);
+DECLARE_FLAG(bool, trace_irregexp);
+
+// TODO(jgruber): Factor out unoptimizing/optimizing pipelines and remove
+// separate helpers functions & `optimizing` args.
+class CompilationPipeline : public ValueObject {
+ public:
+  virtual void ParseFunction(ParsedFunction* parsed_function) = 0;
+  virtual FlowGraph* BuildFlowGraph(

[Ivan Posva, 2014/10/09 09:54:15]

Why does this BuildFlowGraph method have a different API than the
FlowGraphBuilder constructor? In particular why do you need to pass a pointer to
ic_data_array instead of a const reference?

[jgruber1, 2014/10/09 13:36:16]

Done, modified RegExpEngine::Compile to take a const reference instead and
updated the signature to match FlowGraphBuilder.

+      ParsedFunction* parsed_function,
+      ZoneGrowableArray<const ICData*>* ic_data_array,
+      intptr_t osr_id) = 0;
+  virtual void FinalizeCompilation() = 0;
+  virtual ~CompilationPipeline() { }
+};
+
+
+class DefaultCompilationPipeline : public CompilationPipeline {
+ public:
+  virtual void ParseFunction(ParsedFunction* parsed_function) {
+    Parser::ParseFunction(parsed_function);
+    parsed_function->AllocateVariables();
+  }
+
+  virtual FlowGraph* BuildFlowGraph(
+      ParsedFunction* parsed_function,
+      ZoneGrowableArray<const ICData*>* ic_data_array,
+      intptr_t osr_id) {
+    // Build the flow graph.
+    FlowGraphBuilder builder(parsed_function,
+                             *ic_data_array,
+                             NULL,  // NULL = not inlining.
+                             osr_id);
+
+    return builder.BuildGraph();
+  }
+
+  virtual void FinalizeCompilation() { }
+};
+
+
+class IrregexpCompilationPipeline : public DefaultCompilationPipeline {
+ public:
+  explicit IrregexpCompilationPipeline(Isolate* isolate)
+    : macro_assembler_(NULL),
+      isolate_(isolate) { }
+
+  virtual void ParseFunction(ParsedFunction* parsed_function) {
+    RegExpParser::ParseFunction(parsed_function);
+    // Variables are allocated after compilation.
+  }
+
+  virtual FlowGraph* BuildFlowGraph(
+      ParsedFunction* parsed_function,
+      ZoneGrowableArray<const ICData*>* ic_data_array,
+      intptr_t osr_id) {
+    // Compile to the dart IR.
+    RegExpEngine::CompilationResult result =
+        RegExpEngine::Compile(parsed_function->regexp_compile_data(),
+                              parsed_function,
+                              ic_data_array);
+    macro_assembler_ = result.macro_assembler;
+
+    // Allocate variables now that we know the number of locals.
+    parsed_function->AllocateIrregexpVariables(result.num_stack_locals);
+
+    // Build the flow graph.
+    FlowGraphBuilder builder(parsed_function,
+                             *ic_data_array,
+                             NULL,  // NULL = not inlining.
+                             osr_id);
+
+    return new(isolate_) FlowGraph(builder,
+                                   result.graph_entry,
+                                   result.num_blocks);
+  }
+
+  virtual void FinalizeCompilation() {
+    macro_assembler_->FinalizeBlockOffsetTable();
+  }
+
+ private:
+  IRRegExpMacroAssembler* macro_assembler_;
+  Isolate* isolate_;
+};
+
 
 // Compile a function. Should call only if the function has not been compiled.
 //   Arg0: function object.
 DEFINE_RUNTIME_ENTRY(CompileFunction, 1) {
   const Function& function = Function::CheckedHandle(arguments.ArgAt(0));
   ASSERT(!function.HasCode());
   const Error& error = Error::Handle(Compiler::CompileFunction(isolate,
                                                                function));
   if (!error.IsNull()) {
     Exceptions::PropagateError(error);
@@ skipping 181 matching lines @@
     error = isolate->object_store()->sticky_error();
     isolate->object_store()->clear_sticky_error();
     return error.raw();
   }
   UNREACHABLE();
   return Error::null();
 }
 
 
 // Return false if bailed out.
-static bool CompileParsedFunctionHelper(ParsedFunction* parsed_function,
+static bool CompileParsedFunctionHelper(CompilationPipeline* pipeline,
+                                        ParsedFunction* parsed_function,
                                         bool optimized,
                                         intptr_t osr_id) {
   const Function& function = parsed_function->function();
   if (optimized && !function.IsOptimizable()) {
     return false;
   }
   TimerScope timer(FLAG_compiler_stats, &CompilerStats::codegen_timer);
   bool is_compiled = false;
   Isolate* isolate = Isolate::Current();
   HANDLESCOPE(isolate);
@@ skipping 36 matching lines @@
           if (FLAG_print_ic_data_map) {
             for (intptr_t i = 0; i < ic_data_array->length(); i++) {
               if ((*ic_data_array)[i] != NULL) {
                 OS::Print("%" Pd " ", i);
                 FlowGraphPrinter::PrintICData(*(*ic_data_array)[i]);
               }
             }
           }
         }
 
-        // Build the flow graph.
-        FlowGraphBuilder builder(parsed_function,
-                                 *ic_data_array,
-                                 NULL,  // NULL = not inlining.
-                                 osr_id);
-        flow_graph = builder.BuildGraph();
+        flow_graph = pipeline->BuildFlowGraph(parsed_function,
+                                              ic_data_array,
+                                              osr_id);
       }
 
       if (FLAG_print_flow_graph ||
           (optimized && FLAG_print_flow_graph_optimized)) {
         if (osr_id == Isolate::kNoDeoptId) {
           FlowGraphPrinter::PrintGraph("Before Optimizations", flow_graph);
         } else {
           FlowGraphPrinter::PrintGraph("For OSR", flow_graph);
         }
       }
@@ skipping 236 matching lines @@
         }
       }
 
       Assembler assembler(use_far_branches);
       FlowGraphCompiler graph_compiler(&assembler, flow_graph, optimized);
       {
         TimerScope timer(FLAG_compiler_stats,
                          &CompilerStats::graphcompiler_timer,
                          isolate);
         graph_compiler.CompileGraph();
+        pipeline->FinalizeCompilation();
       }
       {
         TimerScope timer(FLAG_compiler_stats,
                          &CompilerStats::codefinalizer_timer,
                          isolate);
         const Code& code = Code::Handle(
             Code::FinalizeCode(function, &assembler, optimized));
         code.set_is_optimized(optimized);
         graph_compiler.FinalizePcDescriptors(code);
         graph_compiler.FinalizeDeoptInfo(code);
@@ skipping 213 matching lines @@
             start + offset.Value(),
             function.ToFullyQualifiedCString(),
             code.raw());
       }
     }
     OS::Print("}\n");
   }
 }
 
 
-static RawError* CompileFunctionHelper(const Function& function,
+static RawError* CompileFunctionHelper(CompilationPipeline* pipeline,
+                                       const Function& function,
                                        bool optimized,
                                        intptr_t osr_id) {
   Isolate* isolate = Isolate::Current();
   StackZone zone(isolate);
   LongJumpScope jump;
   if (setjmp(*jump.Set()) == 0) {
     TIMERSCOPE(isolate, time_compilation);
     Timer per_compile_timer(FLAG_trace_compiler, "Compilation time");
     per_compile_timer.Start();
     ParsedFunction* parsed_function = new(isolate) ParsedFunction(
         isolate, Function::ZoneHandle(isolate, function.raw()));
     if (FLAG_trace_compiler) {
       OS::Print("Compiling %s%sfunction: '%s' @ token %" Pd ", size %" Pd "\n",
                 (osr_id == Isolate::kNoDeoptId ? "" : "osr "),
                 (optimized ? "optimized " : ""),
                 function.ToFullyQualifiedCString(),
                 function.token_pos(),
                 (function.end_token_pos() - function.token_pos()));
     }
     {
       HANDLESCOPE(isolate);
-      Parser::ParseFunction(parsed_function);
-      parsed_function->AllocateVariables();
+      pipeline->ParseFunction(parsed_function);
     }
 
-    const bool success =
-        CompileParsedFunctionHelper(parsed_function, optimized, osr_id);
+    const bool success = CompileParsedFunctionHelper(pipeline,
+                                                     parsed_function,
+                                                     optimized,
+                                                     osr_id);
     if (!success) {
       if (optimized) {
         // Optimizer bailed out. Disable optimizations and to never try again.
         if (FLAG_trace_compiler) {
           OS::Print("--> disabling optimizations for '%s'\n",
                     function.ToFullyQualifiedCString());
         } else if (FLAG_trace_failed_optimization_attempts) {
           OS::Print("Cannot optimize: %s\n",
                     function.ToFullyQualifiedCString());
         }
@@ skipping 33 matching lines @@
     return error.raw();
   }
   UNREACHABLE();
   return Error::null();
 }
 
 
 RawError* Compiler::CompileFunction(Isolate* isolate,
                                     const Function& function) {
   VMTagScope tagScope(isolate, VMTag::kCompileUnoptimizedTagId);
-  return CompileFunctionHelper(function, false, Isolate::kNoDeoptId);
+  if (function.IsIrregexpFunction()) {

[Ivan Posva, 2014/10/09 09:54:15]

CompilationPipeline* pipeline = CompilationPipeline::New(function);
return CompileFunctionHelper(pipeline, function, false, Isolate::kNoDeoptId);

Where CompilationPipeline::New allocates the appropriate Zone allocated
pipeline.

[jgruber1, 2014/10/09 13:36:17]

Done.

+    IrregexpCompilationPipeline pipeline(isolate);
+    return CompileFunctionHelper(
+          &pipeline, function, false, Isolate::kNoDeoptId);
+  } else {
+    DefaultCompilationPipeline pipeline;
+    return CompileFunctionHelper(
+          &pipeline, function, false, Isolate::kNoDeoptId);
+  }
 }
 
 
 RawError* Compiler::CompileOptimizedFunction(Isolate* isolate,
                                              const Function& function,
                                              intptr_t osr_id) {
   VMTagScope tagScope(isolate, VMTag::kCompileOptimizedTagId);
-  return CompileFunctionHelper(function, true, osr_id);
+  if (function.IsIrregexpFunction()) {
+    IrregexpCompilationPipeline pipeline(isolate);
+    return CompileFunctionHelper(&pipeline, function, true, osr_id);
+  } else {
+    DefaultCompilationPipeline pipeline;
+    return CompileFunctionHelper(&pipeline, function, true, osr_id);
+  }
 }
 
 
 // This is only used from unit tests.
 RawError* Compiler::CompileParsedFunction(
     ParsedFunction* parsed_function) {
   Isolate* isolate = Isolate::Current();
   LongJumpScope jump;
   if (setjmp(*jump.Set()) == 0) {
     // Non-optimized code generator.
-    CompileParsedFunctionHelper(parsed_function, false, Isolate::kNoDeoptId);
+    DefaultCompilationPipeline pipeline;
+    CompileParsedFunctionHelper(&pipeline,
+                                parsed_function,
+                                false,
+                                Isolate::kNoDeoptId);
     if (FLAG_disassemble) {
       DisassembleCode(parsed_function->function(), false);
     }
     return Error::null();
   } else {
     Error& error = Error::Handle();
     // We got an error during compilation.
     error = isolate->object_store()->sticky_error();
     isolate->object_store()->clear_sticky_error();
     return error.raw();
@@ skipping 56 matching lines @@
   ASSERT(field.value() == Object::transition_sentinel().raw());
   Isolate* isolate = Isolate::Current();
   StackZone zone(isolate);
   LongJumpScope jump;
   if (setjmp(*jump.Set()) == 0) {
     ParsedFunction* parsed_function =
         Parser::ParseStaticFieldInitializer(field);
 
     parsed_function->AllocateVariables();
     // Non-optimized code generator.
-    CompileParsedFunctionHelper(parsed_function, false, Isolate::kNoDeoptId);
+    DefaultCompilationPipeline pipeline;
+    CompileParsedFunctionHelper(&pipeline,
+                                parsed_function,
+                                false,
+                                Isolate::kNoDeoptId);
 
     // Invoke the function to evaluate the expression.
     const Function& initializer = parsed_function->function();
     const Object& result = PassiveObject::Handle(
         DartEntry::InvokeFunction(initializer, Object::empty_array()));
     return result.raw();
   } else {
     const Error& error =
         Error::Handle(isolate, isolate->object_store()->sticky_error());
     isolate->object_store()->clear_sticky_error();
@@ skipping 39 matching lines @@
     // would compile func automatically. We are checking fewer invariants
     // here.
     ParsedFunction* parsed_function = new ParsedFunction(isolate, func);
     parsed_function->SetNodeSequence(fragment);
     parsed_function->set_default_parameter_values(Object::null_array());
     parsed_function->EnsureExpressionTemp();
     fragment->scope()->AddVariable(parsed_function->expression_temp_var());
     parsed_function->AllocateVariables();
 
     // Non-optimized code generator.
-    CompileParsedFunctionHelper(parsed_function, false, Isolate::kNoDeoptId);
+    DefaultCompilationPipeline pipeline;
+    CompileParsedFunctionHelper(&pipeline,
+                                parsed_function,
+                                false,
+                                Isolate::kNoDeoptId);
 
     const Object& result = PassiveObject::Handle(
         DartEntry::InvokeFunction(func, Object::empty_array()));
     return result.raw();
   } else {
     const Object& result =
       PassiveObject::Handle(isolate->object_store()->sticky_error());
     isolate->object_store()->clear_sticky_error();
     return result.raw();
   }
   UNREACHABLE();
   return Object::null();
 }
 
 }  // namespace dart