blob: d6071ee6402f329051c94d9b2254bff23b7ccf03 [file] [log] [blame]
// 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