| // Copyright (c) 2018, 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/compiler_pass.h" |
| |
| #include "vm/compiler/backend/block_scheduler.h" |
| #include "vm/compiler/backend/branch_optimizer.h" |
| #include "vm/compiler/backend/constant_propagator.h" |
| #include "vm/compiler/backend/flow_graph_checker.h" |
| #include "vm/compiler/backend/il_printer.h" |
| #include "vm/compiler/backend/inliner.h" |
| #include "vm/compiler/backend/linearscan.h" |
| #include "vm/compiler/backend/range_analysis.h" |
| #include "vm/compiler/backend/redundancy_elimination.h" |
| #include "vm/compiler/backend/type_propagator.h" |
| #include "vm/compiler/call_specializer.h" |
| #include "vm/compiler/compiler_timings.h" |
| #include "vm/compiler/write_barrier_elimination.h" |
| #if defined(DART_PRECOMPILER) |
| #include "vm/compiler/aot/aot_call_specializer.h" |
| #include "vm/compiler/aot/precompiler.h" |
| #endif |
| #include "vm/thread.h" |
| #include "vm/timeline.h" |
| |
| #define COMPILER_PASS_REPEAT(Name, Body) \ |
| class CompilerPass_##Name : public CompilerPass { \ |
| public: \ |
| CompilerPass_##Name() : CompilerPass(k##Name, #Name) {} \ |
| \ |
| static bool Register() { return true; } \ |
| \ |
| protected: \ |
| virtual bool DoBody(CompilerPassState* state) const { \ |
| FlowGraph* flow_graph = state->flow_graph(); \ |
| USE(flow_graph); \ |
| Body; \ |
| } \ |
| }; \ |
| static CompilerPass_##Name compiler_pass_##Name; |
| |
| #define COMPILER_PASS(Name, Body) \ |
| COMPILER_PASS_REPEAT(Name, { \ |
| Body; \ |
| return false; \ |
| }) |
| |
| namespace dart { |
| |
| CompilerPassState::CompilerPassState( |
| Thread* thread, |
| FlowGraph* flow_graph, |
| SpeculativeInliningPolicy* speculative_policy, |
| Precompiler* precompiler) |
| : thread(thread), |
| precompiler(precompiler), |
| inlining_depth(0), |
| sinking(NULL), |
| call_specializer(NULL), |
| speculative_policy(speculative_policy), |
| reorder_blocks(false), |
| sticky_flags(0), |
| flow_graph_(flow_graph) { |
| // Top scope function is at inlining id 0. |
| inline_id_to_function.Add(&flow_graph->parsed_function().function()); |
| // Top scope function has no caller (-1). |
| caller_inline_id.Add(-1); |
| // We do not add a token position for the top scope function to |
| // |inline_id_to_token_pos| because it is not (currently) inlined into |
| // another graph at a given token position. A side effect of this is that |
| // the length of |inline_id_to_function| and |caller_inline_id| is always |
| // larger than the length of |inline_id_to_token_pos| by one. |
| } |
| |
| CompilerPass* CompilerPass::passes_[CompilerPass::kNumPasses] = {NULL}; |
| |
| DEFINE_OPTION_HANDLER(CompilerPass::ParseFilters, |
| compiler_passes, |
| "List of comma separated compilation passes flags. " |
| "Use -Name to disable a pass, Name to print IL after it. " |
| "Do --compiler-passes=help for more information."); |
| DECLARE_FLAG(bool, print_flow_graph); |
| DECLARE_FLAG(bool, print_flow_graph_optimized); |
| |
| void CompilerPassState::set_flow_graph(FlowGraph* flow_graph) { |
| flow_graph_ = flow_graph; |
| if (call_specializer != nullptr) { |
| call_specializer->set_flow_graph(flow_graph); |
| } |
| } |
| |
| static const char* kCompilerPassesUsage = |
| "=== How to use --compiler-passes flag\n" |
| "\n" |
| "Pass the list of comma separated compiler pass filter flags.\n" |
| "\n" |
| "For the given pass Name the following flags are supported:\n" |
| "\n" |
| " -Name disable the pass\n" |
| " ]Name or Name print IL after the pass\n" |
| " [Name print IL before the pass\n" |
| " *Name print IL before and after the pass\n" |
| " * print IL after each pass.\n" |
| "\n" |
| " The flag can be followed by '+' which makes it sticky, e.g. Inlining+\n" |
| " would cause IL to be printed after all passes that follow inlining and\n" |
| " are not disabled.\n" |
| "\n" |
| "List of compiler passes:\n"; |
| |
| void CompilerPass::ParseFilters(const char* filter) { |
| if (filter == NULL || *filter == 0) { |
| return; |
| } |
| |
| if (strcmp(filter, "help") == 0) { |
| OS::PrintErr("%s", kCompilerPassesUsage); |
| for (intptr_t i = 0; i < kNumPasses; i++) { |
| if (passes_[i] != NULL) { |
| OS::PrintErr(" %s\n", passes_[i]->name()); |
| } |
| } |
| return; |
| } |
| |
| // Clear all flags. |
| for (intptr_t i = 0; i < kNumPasses; i++) { |
| if (passes_[i] != NULL) { |
| passes_[i]->flags_ = 0; |
| } |
| } |
| |
| for (const char *start = filter, *end = filter; *end != 0; |
| start = (end + 1)) { |
| // Search forward until the separator ',' or the end of filter is reached. |
| end = start; |
| while (*end != ',' && *end != '\0') { |
| end++; |
| } |
| if (start == end) { |
| OS::PrintErr("Ignoring empty compiler pass flag\n"); |
| continue; |
| } |
| |
| uint8_t flags = 0; |
| if (*start == '-') { |
| flags = kDisabled; |
| } else if (*start == ']') { |
| flags = kTraceAfter; |
| } else if (*start == '[') { |
| flags = kTraceBefore; |
| } else if (*start == '*') { |
| flags = kTraceBeforeOrAfter; |
| } |
| if (flags == 0) { |
| flags |= kTraceAfter; |
| } else { |
| start++; // Skip the modifier |
| } |
| |
| size_t suffix = 0; |
| if (end[-1] == '+') { |
| if (start == (end - 1)) { |
| OS::PrintErr("Sticky modifier '+' should follow pass name\n"); |
| continue; |
| } |
| flags |= kSticky; |
| suffix = 1; |
| } |
| |
| size_t length = (end - start) - suffix; |
| if (length != 0) { |
| char* pass_name = Utils::StrNDup(start, length); |
| CompilerPass* pass = FindPassByName(pass_name); |
| if (pass != NULL) { |
| pass->flags_ |= flags; |
| } else { |
| OS::PrintErr("Unknown compiler pass: %s\n", pass_name); |
| } |
| free(pass_name); |
| } else if (flags == kTraceBeforeOrAfter) { |
| for (intptr_t i = 0; i < kNumPasses; i++) { |
| if (passes_[i] != NULL) { |
| passes_[i]->flags_ = kTraceAfter; |
| } |
| } |
| } |
| } |
| } |
| |
| void CompilerPass::Run(CompilerPassState* state) const { |
| if (IsFlagSet(kDisabled)) { |
| return; |
| } |
| |
| if ((flags() & kSticky) != 0) { |
| state->sticky_flags |= flags(); |
| } |
| |
| const intptr_t kMaxRounds = 2; |
| Thread* thread = state->thread; |
| bool repeat = true; |
| for (intptr_t round = 1; round <= kMaxRounds && repeat; round++) { |
| if (round > 1) { |
| Get(kCanonicalize)->Run(state); |
| } |
| |
| PrintGraph(state, kTraceBefore, round); |
| { |
| TIMELINE_DURATION(thread, CompilerVerbose, name()); |
| { |
| COMPILER_TIMINGS_PASS_TIMER_SCOPE(thread, id()); |
| repeat = DoBody(state); |
| } |
| thread->CheckForSafepoint(); |
| } |
| PrintGraph(state, kTraceAfter, round); |
| #if defined(DEBUG) |
| FlowGraphChecker(state->flow_graph(), state->inline_id_to_function) |
| .Check(name()); |
| #endif |
| } |
| } |
| |
| void CompilerPass::PrintGraph(CompilerPassState* state, |
| Flag mask, |
| intptr_t round) const { |
| const intptr_t current_flags = flags() | state->sticky_flags; |
| FlowGraph* flow_graph = state->flow_graph(); |
| |
| if ((FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) && |
| flow_graph->should_print() && ((current_flags & mask) != 0)) { |
| Zone* zone = state->thread->zone(); |
| const char* when = mask == kTraceBefore ? "Before" : "After"; |
| const char* phase = |
| round == 1 |
| ? zone->PrintToString("%s %s", when, name()) |
| : zone->PrintToString("%s %s (round %" Pd ")", when, name(), round); |
| |
| FlowGraphPrinter::PrintGraph(phase, flow_graph); |
| } |
| } |
| |
| #define INVOKE_PASS(Name) \ |
| CompilerPass::Get(CompilerPass::k##Name)->Run(pass_state); |
| |
| #if defined(DART_PRECOMPILER) |
| #define INVOKE_PASS_AOT(Name) \ |
| if (mode == kAOT) { \ |
| INVOKE_PASS(Name); \ |
| } |
| #else |
| #define INVOKE_PASS_AOT(Name) |
| #endif |
| |
| void CompilerPass::RunGraphIntrinsicPipeline(CompilerPassState* pass_state) { |
| INVOKE_PASS(AllocateRegistersForGraphIntrinsic); |
| } |
| |
| void CompilerPass::RunInliningPipeline(PipelineMode mode, |
| CompilerPassState* pass_state) { |
| INVOKE_PASS(ApplyClassIds); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(ApplyICData); |
| INVOKE_PASS(Canonicalize); |
| // Run constant propagation to make sure we specialize for |
| // (optional) constant arguments passed into the inlined method. |
| INVOKE_PASS(ConstantPropagation); |
| // Constant propagation removes unreachable basic blocks and |
| // may open more opportunities for call specialization. |
| // Call specialization during inlining may cause more call |
| // sites to be discovered and more functions inlined. |
| INVOKE_PASS_AOT(ApplyClassIds); |
| // Optimize (a << b) & c patterns, merge instructions. Must occur |
| // before 'SelectRepresentations' which inserts conversion nodes. |
| INVOKE_PASS(TryOptimizePatterns); |
| } |
| |
| FlowGraph* CompilerPass::RunForceOptimizedPipeline( |
| PipelineMode mode, |
| CompilerPassState* pass_state) { |
| INVOKE_PASS(ComputeSSA); |
| INVOKE_PASS(SetOuterInliningId); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(Canonicalize); |
| INVOKE_PASS(BranchSimplify); |
| INVOKE_PASS(IfConvert); |
| INVOKE_PASS(ConstantPropagation); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(WidenSmiToInt32); |
| INVOKE_PASS(SelectRepresentations); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(TryCatchOptimization); |
| INVOKE_PASS(EliminateEnvironments); |
| INVOKE_PASS(EliminateDeadPhis); |
| // Currently DCE assumes that EliminateEnvironments has already been run, |
| // so it should not be lifted earlier than that pass. |
| INVOKE_PASS(DCE); |
| INVOKE_PASS(Canonicalize); |
| INVOKE_PASS_AOT(DelayAllocations); |
| INVOKE_PASS(EliminateWriteBarriers); |
| INVOKE_PASS(FinalizeGraph); |
| INVOKE_PASS(AllocateRegisters); |
| INVOKE_PASS(ReorderBlocks); |
| return pass_state->flow_graph(); |
| } |
| |
| FlowGraph* CompilerPass::RunPipeline(PipelineMode mode, |
| CompilerPassState* pass_state) { |
| INVOKE_PASS(ComputeSSA); |
| INVOKE_PASS_AOT(ApplyClassIds); |
| INVOKE_PASS_AOT(TypePropagation); |
| INVOKE_PASS(ApplyICData); |
| INVOKE_PASS(TryOptimizePatterns); |
| INVOKE_PASS(SetOuterInliningId); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(ApplyClassIds); |
| INVOKE_PASS(Inlining); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(ApplyClassIds); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(ApplyICData); |
| INVOKE_PASS(Canonicalize); |
| INVOKE_PASS(BranchSimplify); |
| INVOKE_PASS(IfConvert); |
| INVOKE_PASS(Canonicalize); |
| INVOKE_PASS(ConstantPropagation); |
| INVOKE_PASS(OptimisticallySpecializeSmiPhis); |
| INVOKE_PASS(TypePropagation); |
| // The extra call specialization pass in AOT is able to specialize more |
| // calls after ConstantPropagation, which removes unreachable code, and |
| // TypePropagation, which can infer more accurate types after removing |
| // unreachable code. |
| INVOKE_PASS_AOT(ApplyICData); |
| INVOKE_PASS_AOT(OptimizeTypedDataAccesses); |
| INVOKE_PASS(WidenSmiToInt32); |
| INVOKE_PASS(SelectRepresentations); |
| INVOKE_PASS(CSE); |
| INVOKE_PASS(LICM); |
| INVOKE_PASS(TryOptimizePatterns); |
| INVOKE_PASS(DSE); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(RangeAnalysis); |
| INVOKE_PASS(OptimizeBranches); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(TryCatchOptimization); |
| INVOKE_PASS(EliminateEnvironments); |
| INVOKE_PASS(EliminateDeadPhis); |
| // Currently DCE assumes that EliminateEnvironments has already been run, |
| // so it should not be lifted earlier than that pass. |
| INVOKE_PASS(DCE); |
| INVOKE_PASS(Canonicalize); |
| INVOKE_PASS_AOT(DelayAllocations); |
| // Repeat branches optimization after DCE, as it could make more |
| // empty blocks. |
| INVOKE_PASS(OptimizeBranches); |
| INVOKE_PASS(AllocationSinking_Sink); |
| INVOKE_PASS(EliminateDeadPhis); |
| INVOKE_PASS(DCE); |
| INVOKE_PASS(TypePropagation); |
| INVOKE_PASS(SelectRepresentations); |
| INVOKE_PASS(Canonicalize); |
| INVOKE_PASS(UseTableDispatch); |
| INVOKE_PASS(EliminateStackOverflowChecks); |
| INVOKE_PASS(Canonicalize); |
| INVOKE_PASS(AllocationSinking_DetachMaterializations); |
| INVOKE_PASS(EliminateWriteBarriers); |
| INVOKE_PASS(FinalizeGraph); |
| INVOKE_PASS(AllocateRegisters); |
| INVOKE_PASS(ReorderBlocks); |
| return pass_state->flow_graph(); |
| } |
| |
| FlowGraph* CompilerPass::RunPipelineWithPasses( |
| CompilerPassState* state, |
| std::initializer_list<CompilerPass::Id> passes) { |
| for (auto pass_id : passes) { |
| passes_[pass_id]->Run(state); |
| } |
| return state->flow_graph(); |
| } |
| |
| COMPILER_PASS(ComputeSSA, { |
| // Transform to SSA (virtual register 0 and no inlining arguments). |
| flow_graph->ComputeSSA(0, NULL); |
| }); |
| |
| COMPILER_PASS(ApplyICData, { state->call_specializer->ApplyICData(); }); |
| |
| COMPILER_PASS(TryOptimizePatterns, { flow_graph->TryOptimizePatterns(); }); |
| |
| COMPILER_PASS(SetOuterInliningId, |
| { FlowGraphInliner::SetInliningId(flow_graph, 0); }); |
| |
| COMPILER_PASS(Inlining, { |
| FlowGraphInliner inliner( |
| flow_graph, &state->inline_id_to_function, &state->inline_id_to_token_pos, |
| &state->caller_inline_id, state->speculative_policy, state->precompiler); |
| state->inlining_depth = inliner.Inline(); |
| }); |
| |
| COMPILER_PASS(TypePropagation, |
| { FlowGraphTypePropagator::Propagate(flow_graph); }); |
| |
| COMPILER_PASS(ApplyClassIds, { state->call_specializer->ApplyClassIds(); }); |
| |
| COMPILER_PASS(EliminateStackOverflowChecks, { |
| if (!flow_graph->IsCompiledForOsr()) { |
| CheckStackOverflowElimination::EliminateStackOverflow(flow_graph); |
| } |
| }); |
| |
| COMPILER_PASS(Canonicalize, { |
| // Do optimizations that depend on the propagated type information. |
| if (flow_graph->Canonicalize()) { |
| flow_graph->Canonicalize(); |
| } |
| }); |
| |
| COMPILER_PASS(BranchSimplify, { BranchSimplifier::Simplify(flow_graph); }); |
| |
| COMPILER_PASS(IfConvert, { IfConverter::Simplify(flow_graph); }); |
| |
| COMPILER_PASS_REPEAT(ConstantPropagation, { |
| ConstantPropagator::Optimize(flow_graph); |
| return true; |
| }); |
| |
| // Optimistically convert loop phis that have a single non-smi input |
| // coming from the loop pre-header into smi-phis. |
| COMPILER_PASS(OptimisticallySpecializeSmiPhis, { |
| LICM licm(flow_graph); |
| licm.OptimisticallySpecializeSmiPhis(); |
| }); |
| |
| COMPILER_PASS(WidenSmiToInt32, { |
| // Where beneficial convert Smi operations into Int32 operations. |
| // Only meanigful for 32bit platforms right now. |
| flow_graph->WidenSmiToInt32(); |
| }); |
| |
| COMPILER_PASS(SelectRepresentations, { |
| // Unbox doubles. Performed after constant propagation to minimize |
| // interference from phis merging double values and tagged |
| // values coming from dead paths. |
| flow_graph->SelectRepresentations(); |
| }); |
| |
| COMPILER_PASS(UseTableDispatch, { |
| if (FLAG_use_bare_instructions && FLAG_use_table_dispatch) { |
| state->call_specializer->ReplaceInstanceCallsWithDispatchTableCalls(); |
| } |
| }); |
| |
| COMPILER_PASS_REPEAT(CSE, { return DominatorBasedCSE::Optimize(flow_graph); }); |
| |
| COMPILER_PASS(LICM, { |
| flow_graph->RenameUsesDominatedByRedefinitions(); |
| DEBUG_ASSERT(flow_graph->VerifyRedefinitions()); |
| LICM licm(flow_graph); |
| licm.Optimize(); |
| flow_graph->RemoveRedefinitions(/*keep_checks*/ true); |
| }); |
| |
| COMPILER_PASS(DSE, { DeadStoreElimination::Optimize(flow_graph); }); |
| |
| COMPILER_PASS(RangeAnalysis, { |
| // We have to perform range analysis after LICM because it |
| // optimistically moves CheckSmi through phis into loop preheaders |
| // making some phis smi. |
| RangeAnalysis range_analysis(flow_graph); |
| range_analysis.Analyze(); |
| }); |
| |
| COMPILER_PASS(OptimizeBranches, { |
| // 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); |
| }); |
| |
| COMPILER_PASS(OptimizeTypedDataAccesses, |
| { TypedDataSpecializer::Optimize(flow_graph); }); |
| |
| COMPILER_PASS(TryCatchOptimization, { |
| OptimizeCatchEntryStates(flow_graph, |
| /*is_aot=*/CompilerState::Current().is_aot()); |
| }); |
| |
| COMPILER_PASS(EliminateEnvironments, { flow_graph->EliminateEnvironments(); }); |
| |
| COMPILER_PASS(EliminateDeadPhis, |
| { DeadCodeElimination::EliminateDeadPhis(flow_graph); }); |
| |
| COMPILER_PASS(DCE, { DeadCodeElimination::EliminateDeadCode(flow_graph); }); |
| |
| COMPILER_PASS(DelayAllocations, { DelayAllocations::Optimize(flow_graph); }); |
| |
| COMPILER_PASS(AllocationSinking_Sink, { |
| // TODO(vegorov): Support allocation sinking with try-catch. |
| if (flow_graph->graph_entry()->catch_entries().is_empty()) { |
| state->sinking = new AllocationSinking(flow_graph); |
| state->sinking->Optimize(); |
| } |
| }); |
| |
| COMPILER_PASS(AllocationSinking_DetachMaterializations, { |
| if (state->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. |
| state->sinking->DetachMaterializations(); |
| } |
| }); |
| |
| COMPILER_PASS(AllocateRegisters, { |
| flow_graph->InsertPushArguments(); |
| // Ensure loop hierarchy has been computed. |
| flow_graph->GetLoopHierarchy(); |
| // Perform register allocation on the SSA graph. |
| FlowGraphAllocator allocator(*flow_graph); |
| allocator.AllocateRegisters(); |
| }); |
| |
| COMPILER_PASS(AllocateRegistersForGraphIntrinsic, { |
| // Ensure loop hierarchy has been computed. |
| flow_graph->GetLoopHierarchy(); |
| // Perform register allocation on the SSA graph. |
| FlowGraphAllocator allocator(*flow_graph, /*intrinsic_mode=*/true); |
| allocator.AllocateRegisters(); |
| }); |
| |
| COMPILER_PASS(ReorderBlocks, { |
| if (state->reorder_blocks) { |
| BlockScheduler::ReorderBlocks(flow_graph); |
| } |
| }); |
| |
| COMPILER_PASS(EliminateWriteBarriers, { EliminateWriteBarriers(flow_graph); }); |
| |
| COMPILER_PASS(FinalizeGraph, { |
| // At the end of the pipeline, force recomputing and caching graph |
| // information (instruction and call site counts) for the (assumed) |
| // non-specialized case with better values, for future inlining. |
| intptr_t instruction_count = 0; |
| intptr_t call_site_count = 0; |
| FlowGraphInliner::CollectGraphInfo(flow_graph, |
| /*constants_count*/ 0, |
| /*force*/ true, &instruction_count, |
| &call_site_count); |
| flow_graph->function().set_inlining_depth(state->inlining_depth); |
| // Remove redefinitions for the rest of the pipeline. |
| flow_graph->RemoveRedefinitions(); |
| }); |
| |
| } // namespace dart |