Port and integrate the irregexp engine from V8

runtime/vm/compiler.cc

Index: runtime/vm/compiler.cc
diff --git a/runtime/vm/compiler.cc b/runtime/vm/compiler.cc
index 7d4387be499b25f58953b7c98a2bf09d71172901..e416af2034e787619e3ad606caa7b091fc7579db 100644
--- a/runtime/vm/compiler.cc
+++ b/runtime/vm/compiler.cc
@@ -63,6 +63,7 @@ DEFINE_FLAG(bool, verify_compiler, false,
 
 DECLARE_FLAG(bool, trace_failed_optimization_attempts);
 DECLARE_FLAG(bool, trace_patching);
+DECLARE_FLAG(bool, trace_irregexp);
 
 // Compile a function. Should call only if the function has not been compiled.
 //   Arg0: function object.
@@ -659,6 +660,366 @@ static bool CompileParsedFunctionHelper(ParsedFunction* parsed_function,
 }
 
 
+// Return false if bailed out.
+static bool CompileIrregexpFunctionHelper(ParsedFunction* parsed_function,
+                                          FlowGraph* flow_graph,
+                                          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);
+
+  // We may reattempt compilation if the function needs to be assembled using
+  // far branches on ARM and MIPS. In the else branch of the setjmp call,
+  // done is set to false, and use_far_branches is set to true if there is a
+  // longjmp from the ARM or MIPS assemblers. In all other paths through this
+  // while loop, done is set to true. use_far_branches is always false on ia32
+  // and x64.
+  bool done = false;
+  // volatile because the variable may be clobbered by a longjmp.
+  volatile bool use_far_branches = false;
+  while (!done) {
+    const intptr_t prev_deopt_id = isolate->deopt_id();
+    LongJumpScope jump;
+    if (setjmp(*jump.Set()) == 0) {
+      // The flow graph is passed in.
+
+      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);
+        }
+      }
+
+      BlockScheduler block_scheduler(flow_graph);
+      const bool reorder_blocks =
+          FlowGraph::ShouldReorderBlocks(function, optimized);
+      if (reorder_blocks) {
+        block_scheduler.AssignEdgeWeights();
+      }
+
+      if (optimized) {
+        TimerScope timer(FLAG_compiler_stats,
+                         &CompilerStats::ssa_timer,
+                         isolate);
+        // Transform to SSA (virtual register 0 and no inlining arguments).
+        flow_graph->ComputeSSA(0, NULL);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+        if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) {
+          FlowGraphPrinter::PrintGraph("After SSA", flow_graph);
+        }
+      }
+
+      // Collect all instance fields that are loaded in the graph and
+      // have non-generic type feedback attached to them that can
+      // potentially affect optimizations.
+      if (optimized) {
+        TimerScope timer(FLAG_compiler_stats,
+                         &CompilerStats::graphoptimizer_timer,
+                         isolate);
+
+        FlowGraphOptimizer optimizer(flow_graph);
+        optimizer.ApplyICData();
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Optimize (a << b) & c patterns, merge operations.
+        // Run early in order to have more opportunity to optimize left shifts.
+        optimizer.TryOptimizePatterns();
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Inlining (mutates the flow graph)
+        if (FLAG_use_inlining) {
+          TimerScope timer(FLAG_compiler_stats,
+                           &CompilerStats::graphinliner_timer);
+          // Propagate types to create more inlining opportunities.
+          FlowGraphTypePropagator::Propagate(flow_graph);
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+          // Use propagated class-ids to create more inlining opportunities.
+          optimizer.ApplyClassIds();
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+          FlowGraphInliner inliner(flow_graph);
+          inliner.Inline();
+          // Use lists are maintained and validated by the inliner.
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+        }
+
+        // Propagate types and eliminate more type tests.
+        FlowGraphTypePropagator::Propagate(flow_graph);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Use propagated class-ids to optimize further.
+        optimizer.ApplyClassIds();
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Propagate types for potentially newly added instructions by
+        // ApplyClassIds(). Must occur before canonicalization.
+        FlowGraphTypePropagator::Propagate(flow_graph);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Do optimizations that depend on the propagated type information.
+        if (optimizer.Canonicalize()) {
+          // Invoke Canonicalize twice in order to fully canonicalize patterns
+          // like "if (a & const == 0) { }".
+          optimizer.Canonicalize();
+        }
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        BranchSimplifier::Simplify(flow_graph);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        IfConverter::Simplify(flow_graph);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        if (FLAG_constant_propagation) {
+          ConstantPropagator::Optimize(flow_graph);
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+          // A canonicalization pass to remove e.g. smi checks on smi constants.
+          optimizer.Canonicalize();
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+          // Canonicalization introduced more opportunities for constant
+          // propagation.
+          ConstantPropagator::Optimize(flow_graph);
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+        }
+
+        // Propagate types and eliminate even more type tests.
+        // Recompute types after constant propagation to infer more precise
+        // types for uses that were previously reached by now eliminated phis.
+        FlowGraphTypePropagator::Propagate(flow_graph);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Unbox doubles. Performed after constant propagation to minimize
+        // interference from phis merging double values and tagged
+        // values coming from dead paths.
+        optimizer.SelectRepresentations();
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        if (FLAG_common_subexpression_elimination ||
+            FLAG_loop_invariant_code_motion) {
+          flow_graph->ComputeBlockEffects();
+        }
+
+        if (FLAG_common_subexpression_elimination) {
+          if (DominatorBasedCSE::Optimize(flow_graph)) {
+            DEBUG_ASSERT(flow_graph->VerifyUseLists());
+            // Do another round of CSE to take secondary effects into account:
+            // e.g. when eliminating dependent loads (a.x[0] + a.x[0])
+            // TODO(fschneider): Change to a one-pass optimization pass.
+            DominatorBasedCSE::Optimize(flow_graph);
+            DEBUG_ASSERT(flow_graph->VerifyUseLists());
+          }
+        }
+
+        // Run loop-invariant code motion right after load elimination since it
+        // depends on the numbering of loads from the previous load-elimination.
+        if (FLAG_loop_invariant_code_motion) {
+          LICM licm(flow_graph);
+          licm.Optimize();
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+        }
+        flow_graph->RemoveRedefinitions();
+
+        // Optimize (a << b) & c patterns, merge operations.
+        // Run after CSE in order to have more opportunity to merge
+        // instructions that have same inputs.
+        optimizer.TryOptimizePatterns();
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        DeadStoreElimination::Optimize(flow_graph);
+
+        if (FLAG_range_analysis) {
+          // Propagate types after store-load-forwarding. Some phis may have
+          // become smi phis that can be processed by range analysis.
+          FlowGraphTypePropagator::Propagate(flow_graph);
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+          // We have to perform range analysis after LICM because it
+          // optimistically moves CheckSmi through phis into loop preheaders
+          // making some phis smi.
+          optimizer.InferIntRanges();
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+        }
+
+        if (FLAG_constant_propagation) {
+          // Constant propagation can use information from range analysis to
+          // find unreachable branch targets and eliminate branches that have
+          // the same true- and false-target.
+          ConstantPropagator::OptimizeBranches(flow_graph);
+          DEBUG_ASSERT(flow_graph->VerifyUseLists());
+        }
+
+        // Recompute types after code movement was done to ensure correct
+        // reaching types for hoisted values.
+        FlowGraphTypePropagator::Propagate(flow_graph);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Optimize try-blocks.
+        TryCatchAnalyzer::Optimize(flow_graph);
+
+        // Detach environments from the instructions that can't deoptimize.
+        // Do it before we attempt to perform allocation sinking to minimize
+        // amount of materializations it has to perform.
+        optimizer.EliminateEnvironments();
+
+        DeadCodeElimination::EliminateDeadPhis(flow_graph);
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        if (optimizer.Canonicalize()) {
+          optimizer.Canonicalize();
+        }
+
+        // Attempt to sink allocations of temporary non-escaping objects to
+        // the deoptimization path.
+        AllocationSinking* sinking = NULL;
+        if (FLAG_allocation_sinking &&
+            (flow_graph->graph_entry()->SuccessorCount()  == 1)) {
+          // TODO(fschneider): Support allocation sinking with try-catch.
+          sinking = new AllocationSinking(flow_graph);
+          sinking->Optimize();
+        }
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        // Ensure that all phis inserted by optimization passes have consistent
+        // representations.
+        optimizer.SelectRepresentations();
+
+        if (optimizer.Canonicalize()) {
+          // To fully remove redundant boxing (e.g. BoxDouble used only in
+          // environments and UnboxDouble instructions) instruction we
+          // first need to replace all their uses and then fold them away.
+          // For now we just repeat Canonicalize twice to do that.
+          // TODO(vegorov): implement a separate representation folding pass.
+          optimizer.Canonicalize();
+        }
+        DEBUG_ASSERT(flow_graph->VerifyUseLists());
+
+        if (sinking != NULL) {
+          // Remove all MaterializeObject instructions inserted by allocation
+          // sinking from the flow graph and let them float on the side
+          // referenced only from environments. Register allocator will consider
+          // them as part of a deoptimization environment.
+          sinking->DetachMaterializations();
+        }
+
+        // Compute and store graph informations (call & instruction counts)
+        // to be later used by the inliner.
+        FlowGraphInliner::CollectGraphInfo(flow_graph, true);
+
+        // Perform register allocation on the SSA graph.
+        FlowGraphAllocator allocator(*flow_graph);
+        allocator.AllocateRegisters();
+        if (reorder_blocks) block_scheduler.ReorderBlocks();
+
+        if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) {
+          FlowGraphPrinter::PrintGraph("After Optimizations", flow_graph);
+        }
+      }
+
+      Assembler assembler(use_far_branches);
+      FlowGraphCompiler graph_compiler(&assembler, flow_graph, optimized);
+      {
+        TimerScope timer(FLAG_compiler_stats,
+                         &CompilerStats::graphcompiler_timer,
+                         isolate);
+        graph_compiler.CompileGraph();
+      }
+      {
+        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);
+        graph_compiler.FinalizeStackmaps(code);
+        code.set_var_descriptors(LocalVarDescriptors::Handle());  // Empty.
+        graph_compiler.FinalizeExceptionHandlers(code);
+        graph_compiler.FinalizeStaticCallTargetsTable(code);
+
+        if (optimized) {
+          if (osr_id == Isolate::kNoDeoptId) {
+            CodePatcher::PatchEntry(Code::Handle(function.CurrentCode()));
+            if (FLAG_trace_compiler || FLAG_trace_patching) {
+              if (FLAG_trace_compiler) {
+                OS::Print("  ");
+              }
+              OS::Print("Patch unoptimized '%s' entry point %#" Px "\n",
+                  function.ToFullyQualifiedCString(),
+                  Code::Handle(function.unoptimized_code()).EntryPoint());
+            }
+          }
+          function.AttachCode(code);
+
+          for (intptr_t i = 0;
+               i < flow_graph->guarded_fields()->length();
+               i++) {
+            const Field* field = (*flow_graph->guarded_fields())[i];
+            field->RegisterDependentCode(code);
+          }
+        } else {  // not optimized.
+          if (function.ic_data_array() == Array::null()) {
+            function.SaveICDataMap(graph_compiler.deopt_id_to_ic_data());
+          }
+          function.set_unoptimized_code(code);
+          function.AttachCode(code);
+          ASSERT(CodePatcher::CodeIsPatchable(code));
+        }
+        if (parsed_function->HasDeferredPrefixes()) {
+          ZoneGrowableArray<const LibraryPrefix*>* prefixes =
+              parsed_function->deferred_prefixes();
+          for (intptr_t i = 0; i < prefixes->length(); i++) {
+            prefixes->At(i)->RegisterDependentCode(code);
+          }
+        }
+      }
+      is_compiled = true;
+      done = true;
+    } else {
+      // We bailed out or we encountered an error.
+      const Error& error = Error::Handle(
+          isolate->object_store()->sticky_error());
+
+      if (error.raw() == Object::branch_offset_error().raw()) {
+        // Compilation failed due to an out of range branch offset in the
+        // assembler. We try again (done = false) with far branches enabled.
+        done = false;
+        ASSERT(!use_far_branches);
+        use_far_branches = true;
+      } else {
+        // If the error isn't due to an out of range branch offset, we don't
+        // try again (done = true), and indicate that we did not finish
+        // compiling (is_compiled = false).
+        if (FLAG_trace_bailout) {
+          OS::Print("%s\n", error.ToErrorCString());
+        }
+        done = true;
+        ASSERT(optimized);
+      }
+
+      // Clear the error if it was not a real error, but just a bailout.
+      if (error.IsLanguageError() &&
+          (LanguageError::Cast(error).kind() == Report::kBailout)) {
+        isolate->object_store()->clear_sticky_error();
+      }
+      is_compiled = false;
+    }
+    // Reset global isolate state.
+    isolate->set_deopt_id(prev_deopt_id);
+  }
+  return is_compiled;
+}
+
+
 static void DisassembleCode(const Function& function, bool optimized) {
   const char* function_fullname = function.ToFullyQualifiedCString();
   OS::Print("Code for %sfunction '%s' {\n",
@@ -904,6 +1265,36 @@ RawError* Compiler::CompileParsedFunction(
 }
 
 
+// TODO(jgruber): Refactor into other functions.
+RawError* Compiler::CompileIrregexpFunction(
+    ParsedFunction* parsed_function,
+    FlowGraph* flow_graph) {
+  Isolate* isolate = Isolate::Current();
+  LongJumpScope jump;
+  if (setjmp(*jump.Set()) == 0) {
+    // Disassemble the generated code if tracing the irregexp engine.
+    const bool stored_flag_disassemble = FLAG_disassemble;
+    FLAG_disassemble = FLAG_trace_irregexp;
+    // Non-optimized code generator.
+    CompileIrregexpFunctionHelper(parsed_function, flow_graph,
+                                  false, Isolate::kNoDeoptId);
+    if (FLAG_disassemble) {
+      DisassembleCode(parsed_function->function(), false);
+    }
+    FLAG_disassemble = stored_flag_disassemble;
+    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();
+  }
+  UNREACHABLE();
+  return Error::null();
+}
+
+
 RawError* Compiler::CompileAllFunctions(const Class& cls) {
   Isolate* isolate = Isolate::Current();
   Error& error = Error::Handle(isolate);