Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(13)

Side by Side Diff: runtime/vm/compiler.cc

Issue 539153002: Port and integrate the irregexp engine from V8 (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a 2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 #include "vm/compiler.h" 5 #include "vm/compiler.h"
6 6
7 #include "vm/assembler.h" 7 #include "vm/assembler.h"
8 8
9 #include "vm/ast_printer.h" 9 #include "vm/ast_printer.h"
10 #include "vm/block_scheduler.h" 10 #include "vm/block_scheduler.h"
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
56 DEFINE_FLAG(bool, range_analysis, true, "Enable range analysis"); 56 DEFINE_FLAG(bool, range_analysis, true, "Enable range analysis");
57 DEFINE_FLAG(bool, reorder_basic_blocks, true, "Enable basic-block reordering."); 57 DEFINE_FLAG(bool, reorder_basic_blocks, true, "Enable basic-block reordering.");
58 DEFINE_FLAG(bool, trace_compiler, false, "Trace compiler operations."); 58 DEFINE_FLAG(bool, trace_compiler, false, "Trace compiler operations.");
59 DEFINE_FLAG(bool, trace_bailout, false, "Print bailout from ssa compiler."); 59 DEFINE_FLAG(bool, trace_bailout, false, "Print bailout from ssa compiler.");
60 DEFINE_FLAG(bool, use_inlining, true, "Enable call-site inlining"); 60 DEFINE_FLAG(bool, use_inlining, true, "Enable call-site inlining");
61 DEFINE_FLAG(bool, verify_compiler, false, 61 DEFINE_FLAG(bool, verify_compiler, false,
62 "Enable compiler verification assertions"); 62 "Enable compiler verification assertions");
63 63
64 DECLARE_FLAG(bool, trace_failed_optimization_attempts); 64 DECLARE_FLAG(bool, trace_failed_optimization_attempts);
65 DECLARE_FLAG(bool, trace_patching); 65 DECLARE_FLAG(bool, trace_patching);
66 DECLARE_FLAG(bool, trace_irregexp);
66 67
67 // Compile a function. Should call only if the function has not been compiled. 68 // Compile a function. Should call only if the function has not been compiled.
68 // Arg0: function object. 69 // Arg0: function object.
69 DEFINE_RUNTIME_ENTRY(CompileFunction, 1) { 70 DEFINE_RUNTIME_ENTRY(CompileFunction, 1) {
70 const Function& function = Function::CheckedHandle(arguments.ArgAt(0)); 71 const Function& function = Function::CheckedHandle(arguments.ArgAt(0));
71 ASSERT(!function.HasCode()); 72 ASSERT(!function.HasCode());
72 const Error& error = Error::Handle(Compiler::CompileFunction(isolate, 73 const Error& error = Error::Handle(Compiler::CompileFunction(isolate,
73 function)); 74 function));
74 if (!error.IsNull()) { 75 if (!error.IsNull()) {
75 Exceptions::PropagateError(error); 76 Exceptions::PropagateError(error);
(...skipping 576 matching lines...) Expand 10 before | Expand all | Expand 10 after
652 } 653 }
653 is_compiled = false; 654 is_compiled = false;
654 } 655 }
655 // Reset global isolate state. 656 // Reset global isolate state.
656 isolate->set_deopt_id(prev_deopt_id); 657 isolate->set_deopt_id(prev_deopt_id);
657 } 658 }
658 return is_compiled; 659 return is_compiled;
659 } 660 }
660 661
661 662
663 // Return false if bailed out.
664 static bool CompileIrregexpFunctionHelper(ParsedFunction* parsed_function,
665 FlowGraph* flow_graph,
666 bool optimized,
667 intptr_t osr_id) {
668 const Function& function = parsed_function->function();
669 if (optimized && !function.IsOptimizable()) {
670 return false;
671 }
672 TimerScope timer(FLAG_compiler_stats, &CompilerStats::codegen_timer);
673 bool is_compiled = false;
674 Isolate* isolate = Isolate::Current();
675 HANDLESCOPE(isolate);
676
677 // We may reattempt compilation if the function needs to be assembled using
678 // far branches on ARM and MIPS. In the else branch of the setjmp call,
679 // done is set to false, and use_far_branches is set to true if there is a
680 // longjmp from the ARM or MIPS assemblers. In all other paths through this
681 // while loop, done is set to true. use_far_branches is always false on ia32
682 // and x64.
683 bool done = false;
684 // volatile because the variable may be clobbered by a longjmp.
685 volatile bool use_far_branches = false;
686 while (!done) {
687 const intptr_t prev_deopt_id = isolate->deopt_id();
688 LongJumpScope jump;
689 if (setjmp(*jump.Set()) == 0) {
690 // The flow graph is passed in.
691
692 if (FLAG_print_flow_graph ||
693 (optimized && FLAG_print_flow_graph_optimized)) {
694 if (osr_id == Isolate::kNoDeoptId) {
695 FlowGraphPrinter::PrintGraph("Before Optimizations", flow_graph);
696 } else {
697 FlowGraphPrinter::PrintGraph("For OSR", flow_graph);
698 }
699 }
700
701 BlockScheduler block_scheduler(flow_graph);
702 const bool reorder_blocks =
703 FlowGraph::ShouldReorderBlocks(function, optimized);
704 if (reorder_blocks) {
705 block_scheduler.AssignEdgeWeights();
706 }
707
708 if (optimized) {
709 TimerScope timer(FLAG_compiler_stats,
710 &CompilerStats::ssa_timer,
711 isolate);
712 // Transform to SSA (virtual register 0 and no inlining arguments).
713 flow_graph->ComputeSSA(0, NULL);
714 DEBUG_ASSERT(flow_graph->VerifyUseLists());
715 if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) {
716 FlowGraphPrinter::PrintGraph("After SSA", flow_graph);
717 }
718 }
719
720 // Collect all instance fields that are loaded in the graph and
721 // have non-generic type feedback attached to them that can
722 // potentially affect optimizations.
723 if (optimized) {
724 TimerScope timer(FLAG_compiler_stats,
725 &CompilerStats::graphoptimizer_timer,
726 isolate);
727
728 FlowGraphOptimizer optimizer(flow_graph);
729 optimizer.ApplyICData();
730 DEBUG_ASSERT(flow_graph->VerifyUseLists());
731
732 // Optimize (a << b) & c patterns, merge operations.
733 // Run early in order to have more opportunity to optimize left shifts.
734 optimizer.TryOptimizePatterns();
735 DEBUG_ASSERT(flow_graph->VerifyUseLists());
736
737 // Inlining (mutates the flow graph)
738 if (FLAG_use_inlining) {
739 TimerScope timer(FLAG_compiler_stats,
740 &CompilerStats::graphinliner_timer);
741 // Propagate types to create more inlining opportunities.
742 FlowGraphTypePropagator::Propagate(flow_graph);
743 DEBUG_ASSERT(flow_graph->VerifyUseLists());
744
745 // Use propagated class-ids to create more inlining opportunities.
746 optimizer.ApplyClassIds();
747 DEBUG_ASSERT(flow_graph->VerifyUseLists());
748
749 FlowGraphInliner inliner(flow_graph);
750 inliner.Inline();
751 // Use lists are maintained and validated by the inliner.
752 DEBUG_ASSERT(flow_graph->VerifyUseLists());
753 }
754
755 // Propagate types and eliminate more type tests.
756 FlowGraphTypePropagator::Propagate(flow_graph);
757 DEBUG_ASSERT(flow_graph->VerifyUseLists());
758
759 // Use propagated class-ids to optimize further.
760 optimizer.ApplyClassIds();
761 DEBUG_ASSERT(flow_graph->VerifyUseLists());
762
763 // Propagate types for potentially newly added instructions by
764 // ApplyClassIds(). Must occur before canonicalization.
765 FlowGraphTypePropagator::Propagate(flow_graph);
766 DEBUG_ASSERT(flow_graph->VerifyUseLists());
767
768 // Do optimizations that depend on the propagated type information.
769 if (optimizer.Canonicalize()) {
770 // Invoke Canonicalize twice in order to fully canonicalize patterns
771 // like "if (a & const == 0) { }".
772 optimizer.Canonicalize();
773 }
774 DEBUG_ASSERT(flow_graph->VerifyUseLists());
775
776 BranchSimplifier::Simplify(flow_graph);
777 DEBUG_ASSERT(flow_graph->VerifyUseLists());
778
779 IfConverter::Simplify(flow_graph);
780 DEBUG_ASSERT(flow_graph->VerifyUseLists());
781
782 if (FLAG_constant_propagation) {
783 ConstantPropagator::Optimize(flow_graph);
784 DEBUG_ASSERT(flow_graph->VerifyUseLists());
785 // A canonicalization pass to remove e.g. smi checks on smi constants.
786 optimizer.Canonicalize();
787 DEBUG_ASSERT(flow_graph->VerifyUseLists());
788 // Canonicalization introduced more opportunities for constant
789 // propagation.
790 ConstantPropagator::Optimize(flow_graph);
791 DEBUG_ASSERT(flow_graph->VerifyUseLists());
792 }
793
794 // Propagate types and eliminate even more type tests.
795 // Recompute types after constant propagation to infer more precise
796 // types for uses that were previously reached by now eliminated phis.
797 FlowGraphTypePropagator::Propagate(flow_graph);
798 DEBUG_ASSERT(flow_graph->VerifyUseLists());
799
800 // Unbox doubles. Performed after constant propagation to minimize
801 // interference from phis merging double values and tagged
802 // values coming from dead paths.
803 optimizer.SelectRepresentations();
804 DEBUG_ASSERT(flow_graph->VerifyUseLists());
805
806 if (FLAG_common_subexpression_elimination ||
807 FLAG_loop_invariant_code_motion) {
808 flow_graph->ComputeBlockEffects();
809 }
810
811 if (FLAG_common_subexpression_elimination) {
812 if (DominatorBasedCSE::Optimize(flow_graph)) {
813 DEBUG_ASSERT(flow_graph->VerifyUseLists());
814 // Do another round of CSE to take secondary effects into account:
815 // e.g. when eliminating dependent loads (a.x[0] + a.x[0])
816 // TODO(fschneider): Change to a one-pass optimization pass.
817 DominatorBasedCSE::Optimize(flow_graph);
818 DEBUG_ASSERT(flow_graph->VerifyUseLists());
819 }
820 }
821
822 // Run loop-invariant code motion right after load elimination since it
823 // depends on the numbering of loads from the previous load-elimination.
824 if (FLAG_loop_invariant_code_motion) {
825 LICM licm(flow_graph);
826 licm.Optimize();
827 DEBUG_ASSERT(flow_graph->VerifyUseLists());
828 }
829 flow_graph->RemoveRedefinitions();
830
831 // Optimize (a << b) & c patterns, merge operations.
832 // Run after CSE in order to have more opportunity to merge
833 // instructions that have same inputs.
834 optimizer.TryOptimizePatterns();
835 DEBUG_ASSERT(flow_graph->VerifyUseLists());
836
837 DeadStoreElimination::Optimize(flow_graph);
838
839 if (FLAG_range_analysis) {
840 // Propagate types after store-load-forwarding. Some phis may have
841 // become smi phis that can be processed by range analysis.
842 FlowGraphTypePropagator::Propagate(flow_graph);
843 DEBUG_ASSERT(flow_graph->VerifyUseLists());
844
845 // We have to perform range analysis after LICM because it
846 // optimistically moves CheckSmi through phis into loop preheaders
847 // making some phis smi.
848 optimizer.InferIntRanges();
849 DEBUG_ASSERT(flow_graph->VerifyUseLists());
850 }
851
852 if (FLAG_constant_propagation) {
853 // Constant propagation can use information from range analysis to
854 // find unreachable branch targets and eliminate branches that have
855 // the same true- and false-target.
856 ConstantPropagator::OptimizeBranches(flow_graph);
857 DEBUG_ASSERT(flow_graph->VerifyUseLists());
858 }
859
860 // Recompute types after code movement was done to ensure correct
861 // reaching types for hoisted values.
862 FlowGraphTypePropagator::Propagate(flow_graph);
863 DEBUG_ASSERT(flow_graph->VerifyUseLists());
864
865 // Optimize try-blocks.
866 TryCatchAnalyzer::Optimize(flow_graph);
867
868 // Detach environments from the instructions that can't deoptimize.
869 // Do it before we attempt to perform allocation sinking to minimize
870 // amount of materializations it has to perform.
871 optimizer.EliminateEnvironments();
872
873 DeadCodeElimination::EliminateDeadPhis(flow_graph);
874 DEBUG_ASSERT(flow_graph->VerifyUseLists());
875
876 if (optimizer.Canonicalize()) {
877 optimizer.Canonicalize();
878 }
879
880 // Attempt to sink allocations of temporary non-escaping objects to
881 // the deoptimization path.
882 AllocationSinking* sinking = NULL;
883 if (FLAG_allocation_sinking &&
884 (flow_graph->graph_entry()->SuccessorCount() == 1)) {
885 // TODO(fschneider): Support allocation sinking with try-catch.
886 sinking = new AllocationSinking(flow_graph);
887 sinking->Optimize();
888 }
889 DEBUG_ASSERT(flow_graph->VerifyUseLists());
890
891 // Ensure that all phis inserted by optimization passes have consistent
892 // representations.
893 optimizer.SelectRepresentations();
894
895 if (optimizer.Canonicalize()) {
896 // To fully remove redundant boxing (e.g. BoxDouble used only in
897 // environments and UnboxDouble instructions) instruction we
898 // first need to replace all their uses and then fold them away.
899 // For now we just repeat Canonicalize twice to do that.
900 // TODO(vegorov): implement a separate representation folding pass.
901 optimizer.Canonicalize();
902 }
903 DEBUG_ASSERT(flow_graph->VerifyUseLists());
904
905 if (sinking != NULL) {
906 // Remove all MaterializeObject instructions inserted by allocation
907 // sinking from the flow graph and let them float on the side
908 // referenced only from environments. Register allocator will consider
909 // them as part of a deoptimization environment.
910 sinking->DetachMaterializations();
911 }
912
913 // Compute and store graph informations (call & instruction counts)
914 // to be later used by the inliner.
915 FlowGraphInliner::CollectGraphInfo(flow_graph, true);
916
917 // Perform register allocation on the SSA graph.
918 FlowGraphAllocator allocator(*flow_graph);
919 allocator.AllocateRegisters();
920 if (reorder_blocks) block_scheduler.ReorderBlocks();
921
922 if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) {
923 FlowGraphPrinter::PrintGraph("After Optimizations", flow_graph);
924 }
925 }
926
927 Assembler assembler(use_far_branches);
928 FlowGraphCompiler graph_compiler(&assembler, flow_graph, optimized);
929 {
930 TimerScope timer(FLAG_compiler_stats,
931 &CompilerStats::graphcompiler_timer,
932 isolate);
933 graph_compiler.CompileGraph();
934 }
935 {
936 TimerScope timer(FLAG_compiler_stats,
937 &CompilerStats::codefinalizer_timer,
938 isolate);
939 const Code& code = Code::Handle(
940 Code::FinalizeCode(function, &assembler, optimized));
941 code.set_is_optimized(optimized);
942 graph_compiler.FinalizePcDescriptors(code);
943 graph_compiler.FinalizeDeoptInfo(code);
944 graph_compiler.FinalizeStackmaps(code);
945 code.set_var_descriptors(LocalVarDescriptors::Handle()); // Empty.
946 graph_compiler.FinalizeExceptionHandlers(code);
947 graph_compiler.FinalizeStaticCallTargetsTable(code);
948
949 if (optimized) {
950 if (osr_id == Isolate::kNoDeoptId) {
951 CodePatcher::PatchEntry(Code::Handle(function.CurrentCode()));
952 if (FLAG_trace_compiler || FLAG_trace_patching) {
953 if (FLAG_trace_compiler) {
954 OS::Print(" ");
955 }
956 OS::Print("Patch unoptimized '%s' entry point %#" Px "\n",
957 function.ToFullyQualifiedCString(),
958 Code::Handle(function.unoptimized_code()).EntryPoint());
959 }
960 }
961 function.AttachCode(code);
962
963 for (intptr_t i = 0;
964 i < flow_graph->guarded_fields()->length();
965 i++) {
966 const Field* field = (*flow_graph->guarded_fields())[i];
967 field->RegisterDependentCode(code);
968 }
969 } else { // not optimized.
970 if (function.ic_data_array() == Array::null()) {
971 function.SaveICDataMap(graph_compiler.deopt_id_to_ic_data());
972 }
973 function.set_unoptimized_code(code);
974 function.AttachCode(code);
975 ASSERT(CodePatcher::CodeIsPatchable(code));
976 }
977 if (parsed_function->HasDeferredPrefixes()) {
978 ZoneGrowableArray<const LibraryPrefix*>* prefixes =
979 parsed_function->deferred_prefixes();
980 for (intptr_t i = 0; i < prefixes->length(); i++) {
981 prefixes->At(i)->RegisterDependentCode(code);
982 }
983 }
984 }
985 is_compiled = true;
986 done = true;
987 } else {
988 // We bailed out or we encountered an error.
989 const Error& error = Error::Handle(
990 isolate->object_store()->sticky_error());
991
992 if (error.raw() == Object::branch_offset_error().raw()) {
993 // Compilation failed due to an out of range branch offset in the
994 // assembler. We try again (done = false) with far branches enabled.
995 done = false;
996 ASSERT(!use_far_branches);
997 use_far_branches = true;
998 } else {
999 // If the error isn't due to an out of range branch offset, we don't
1000 // try again (done = true), and indicate that we did not finish
1001 // compiling (is_compiled = false).
1002 if (FLAG_trace_bailout) {
1003 OS::Print("%s\n", error.ToErrorCString());
1004 }
1005 done = true;
1006 ASSERT(optimized);
1007 }
1008
1009 // Clear the error if it was not a real error, but just a bailout.
1010 if (error.IsLanguageError() &&
1011 (LanguageError::Cast(error).kind() == Report::kBailout)) {
1012 isolate->object_store()->clear_sticky_error();
1013 }
1014 is_compiled = false;
1015 }
1016 // Reset global isolate state.
1017 isolate->set_deopt_id(prev_deopt_id);
1018 }
1019 return is_compiled;
1020 }
1021
1022
662 static void DisassembleCode(const Function& function, bool optimized) { 1023 static void DisassembleCode(const Function& function, bool optimized) {
663 const char* function_fullname = function.ToFullyQualifiedCString(); 1024 const char* function_fullname = function.ToFullyQualifiedCString();
664 OS::Print("Code for %sfunction '%s' {\n", 1025 OS::Print("Code for %sfunction '%s' {\n",
665 optimized ? "optimized " : "", 1026 optimized ? "optimized " : "",
666 function_fullname); 1027 function_fullname);
667 const Code& code = Code::Handle(function.CurrentCode()); 1028 const Code& code = Code::Handle(function.CurrentCode());
668 code.Disassemble(); 1029 code.Disassemble();
669 OS::Print("}\n"); 1030 OS::Print("}\n");
670 1031
671 OS::Print("Pointer offsets for function: {\n"); 1032 OS::Print("Pointer offsets for function: {\n");
(...skipping 225 matching lines...) Expand 10 before | Expand all | Expand 10 after
897 // We got an error during compilation. 1258 // We got an error during compilation.
898 error = isolate->object_store()->sticky_error(); 1259 error = isolate->object_store()->sticky_error();
899 isolate->object_store()->clear_sticky_error(); 1260 isolate->object_store()->clear_sticky_error();
900 return error.raw(); 1261 return error.raw();
901 } 1262 }
902 UNREACHABLE(); 1263 UNREACHABLE();
903 return Error::null(); 1264 return Error::null();
904 } 1265 }
905 1266
906 1267
1268 // TODO(jgruber): Refactor into other functions.
1269 RawError* Compiler::CompileIrregexpFunction(
1270 ParsedFunction* parsed_function,
1271 FlowGraph* flow_graph) {
1272 Isolate* isolate = Isolate::Current();
1273 LongJumpScope jump;
1274 if (setjmp(*jump.Set()) == 0) {
1275 // Disassemble the generated code if tracing the irregexp engine.
1276 const bool stored_flag_disassemble = FLAG_disassemble;
1277 FLAG_disassemble = FLAG_trace_irregexp;
1278 // Non-optimized code generator.
1279 CompileIrregexpFunctionHelper(parsed_function, flow_graph,
1280 false, Isolate::kNoDeoptId);
1281 if (FLAG_disassemble) {
1282 DisassembleCode(parsed_function->function(), false);
1283 }
1284 FLAG_disassemble = stored_flag_disassemble;
1285 return Error::null();
1286 } else {
1287 Error& error = Error::Handle();
1288 // We got an error during compilation.
1289 error = isolate->object_store()->sticky_error();
1290 isolate->object_store()->clear_sticky_error();
1291 return error.raw();
1292 }
1293 UNREACHABLE();
1294 return Error::null();
1295 }
1296
1297
907 RawError* Compiler::CompileAllFunctions(const Class& cls) { 1298 RawError* Compiler::CompileAllFunctions(const Class& cls) {
908 Isolate* isolate = Isolate::Current(); 1299 Isolate* isolate = Isolate::Current();
909 Error& error = Error::Handle(isolate); 1300 Error& error = Error::Handle(isolate);
910 Array& functions = Array::Handle(isolate, cls.functions()); 1301 Array& functions = Array::Handle(isolate, cls.functions());
911 Function& func = Function::Handle(isolate); 1302 Function& func = Function::Handle(isolate);
912 // Class dynamic lives in the vm isolate. Its array fields cannot be set to 1303 // Class dynamic lives in the vm isolate. Its array fields cannot be set to
913 // an empty array. 1304 // an empty array.
914 if (functions.IsNull()) { 1305 if (functions.IsNull()) {
915 ASSERT(cls.IsDynamicClass()); 1306 ASSERT(cls.IsDynamicClass());
916 return error.raw(); 1307 return error.raw();
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after
1033 const Object& result = 1424 const Object& result =
1034 Object::Handle(isolate->object_store()->sticky_error()); 1425 Object::Handle(isolate->object_store()->sticky_error());
1035 isolate->object_store()->clear_sticky_error(); 1426 isolate->object_store()->clear_sticky_error();
1036 return result.raw(); 1427 return result.raw();
1037 } 1428 }
1038 UNREACHABLE(); 1429 UNREACHABLE();
1039 return Object::null(); 1430 return Object::null();
1040 } 1431 }
1041 1432
1042 } // namespace dart 1433 } // namespace dart
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698