1// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
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.
4
5#include "vm/compiler/compiler_pass.h"
6
7#include "vm/compiler/backend/block_scheduler.h"
8#include "vm/compiler/backend/branch_optimizer.h"
9#include "vm/compiler/backend/constant_propagator.h"
10#include "vm/compiler/backend/flow_graph_checker.h"
11#include "vm/compiler/backend/il_deserializer.h"
12#include "vm/compiler/backend/il_printer.h"
13#include "vm/compiler/backend/il_serializer.h"
14#include "vm/compiler/backend/inliner.h"
15#include "vm/compiler/backend/linearscan.h"
16#include "vm/compiler/backend/range_analysis.h"
17#include "vm/compiler/backend/redundancy_elimination.h"
18#include "vm/compiler/backend/type_propagator.h"
19#include "vm/compiler/call_specializer.h"
20#include "vm/compiler/write_barrier_elimination.h"
21#if defined(DART_PRECOMPILER)
22#include "vm/compiler/aot/aot_call_specializer.h"
23#include "vm/compiler/aot/precompiler.h"
24#endif
25#include "vm/timeline.h"
26
27#define COMPILER_PASS_REPEAT(Name, Body) \
28 class CompilerPass_##Name : public CompilerPass { \
29 public: \
30 CompilerPass_##Name() : CompilerPass(k##Name, #Name) {} \
31 \
32 static bool Register() { return true; } \
33 \
34 protected: \
35 virtual bool DoBody(CompilerPassState* state) const { \
36 FlowGraph* flow_graph = state->flow_graph(); \
37 USE(flow_graph); \
38 Body; \
39 } \
40 }; \
41 static CompilerPass_##Name compiler_pass_##Name;
42
43#define COMPILER_PASS(Name, Body) \
44 COMPILER_PASS_REPEAT(Name, { \
45 Body; \
46 return false; \
47 })
48
49namespace dart {
50
51CompilerPass* CompilerPass::passes_[CompilerPass::kNumPasses] = {NULL};
52
53DEFINE_OPTION_HANDLER(CompilerPass::ParseFilters,
54 compiler_passes,
55 "List of comma separated compilation passes flags. "
56 "Use -Name to disable a pass, Name to print IL after it. "
57 "Do --compiler-passes=help for more information.");
58DEFINE_FLAG(bool,
59 early_round_trip_serialization,
60 false,
61 "Perform early round trip serialization compiler pass.");
62DEFINE_FLAG(bool,
63 late_round_trip_serialization,
64 false,
65 "Perform late round trip serialization compiler pass.");
66DECLARE_FLAG(bool, print_flow_graph);
67DECLARE_FLAG(bool, print_flow_graph_optimized);
68
69void CompilerPassState::set_flow_graph(FlowGraph* flow_graph) {
70 flow_graph_ = flow_graph;
71 if (call_specializer != nullptr) {
72 call_specializer->set_flow_graph(flow_graph);
73 }
74}
75
76static const char* kCompilerPassesUsage =
77 "=== How to use --compiler-passes flag\n"
78 "\n"
79 "Pass the list of comma separated compiler pass filter flags.\n"
80 "\n"
81 "For the given pass Name the following flags are supported:\n"
82 "\n"
83 " -Name disable the pass\n"
84 " ]Name or Name print IL after the pass\n"
85 " [Name print IL before the pass\n"
86 " *Name print IL before and after the pass\n"
87 " * print IL after each pass.\n"
88 "\n"
89 " The flag can be followed by '+' which makes it sticky, e.g. Inlining+\n"
90 " would cause IL to be printed after all passes that follow inlining and\n"
91 " are not disabled.\n"
92 "\n"
93 "List of compiler passes:\n";
94
95void CompilerPass::ParseFilters(const char* filter) {
96 if (filter == NULL || *filter == 0) {
97 return;
98 }
99
100 if (strcmp(filter, "help") == 0) {
101 OS::PrintErr("%s", kCompilerPassesUsage);
102 for (intptr_t i = 0; i < kNumPasses; i++) {
103 if (passes_[i] != NULL) {
104 OS::PrintErr(" %s\n", passes_[i]->name());
105 }
106 }
107 return;
108 }
109
110 // Clear all flags.
111 for (intptr_t i = 0; i < kNumPasses; i++) {
112 if (passes_[i] != NULL) {
113 passes_[i]->flags_ = 0;
114 }
115 }
116
117 for (const char *start = filter, *end = filter; *end != 0;
118 start = (end + 1)) {
119 // Search forward until the separator ',' or the end of filter is reached.
120 end = start;
121 while (*end != ',' && *end != '\0') {
122 end++;
123 }
124 if (start == end) {
125 OS::PrintErr("Ignoring empty compiler pass flag\n");
126 continue;
127 }
128
129 uint8_t flags = 0;
130 if (*start == '-') {
131 flags = kDisabled;
132 } else if (*start == ']') {
133 flags = kTraceAfter;
134 } else if (*start == '[') {
135 flags = kTraceBefore;
136 } else if (*start == '*') {
137 flags = kTraceBeforeOrAfter;
138 }
139 if (flags == 0) {
140 flags |= kTraceAfter;
141 } else {
142 start++; // Skip the modifier
143 }
144
145 size_t suffix = 0;
146 if (end[-1] == '+') {
147 if (start == (end - 1)) {
148 OS::PrintErr("Sticky modifier '+' should follow pass name\n");
149 continue;
150 }
151 flags |= kSticky;
152 suffix = 1;
153 }
154
155 size_t length = (end - start) - suffix;
156 if (length != 0) {
157 char* pass_name = Utils::StrNDup(start, length);
158 CompilerPass* pass = FindPassByName(pass_name);
159 if (pass != NULL) {
160 pass->flags_ |= flags;
161 } else {
162 OS::PrintErr("Unknown compiler pass: %s\n", pass_name);
163 }
164 free(pass_name);
165 } else if (flags == kTraceBeforeOrAfter) {
166 for (intptr_t i = 0; i < kNumPasses; i++) {
167 if (passes_[i] != NULL) {
168 passes_[i]->flags_ = kTraceAfter;
169 }
170 }
171 }
172 }
173}
174
175void CompilerPass::Run(CompilerPassState* state) const {
176 if (IsFlagSet(kDisabled)) {
177 return;
178 }
179
180 if ((flags() & kSticky) != 0) {
181 state->sticky_flags |= flags();
182 }
183
184 const intptr_t kMaxRounds = 2;
185 Thread* thread = state->thread;
186 bool repeat = true;
187 for (intptr_t round = 1; round <= kMaxRounds && repeat; round++) {
188 if (round > 1) {
189 Get(kCanonicalize)->Run(state);
190 }
191
192 PrintGraph(state, kTraceBefore, round);
193 {
194 TIMELINE_DURATION(thread, CompilerVerbose, name());
195 repeat = DoBody(state);
196 thread->CheckForSafepoint();
197 }
198 PrintGraph(state, kTraceAfter, round);
199#if defined(DEBUG)
200 FlowGraphChecker(state->flow_graph()).Check(name());
201#endif
202 }
203}
204
205void CompilerPass::PrintGraph(CompilerPassState* state,
206 Flag mask,
207 intptr_t round) const {
208 const intptr_t current_flags = flags() | state->sticky_flags;
209 FlowGraph* flow_graph = state->flow_graph();
210
211 if ((FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) &&
212 flow_graph->should_print() && ((current_flags & mask) != 0)) {
213 Zone* zone = state->thread->zone();
214 const char* when = mask == kTraceBefore ? "Before" : "After";
215 const char* phase =
216 round == 1
217 ? zone->PrintToString("%s %s", when, name())
218 : zone->PrintToString("%s %s (round %" Pd ")", when, name(), round);
219
220 FlowGraphPrinter::PrintGraph(phase, flow_graph);
221 }
222}
223
224#define INVOKE_PASS(Name) \
225 CompilerPass::Get(CompilerPass::k##Name)->Run(pass_state);
226
227#if defined(DART_PRECOMPILER)
228#define INVOKE_PASS_AOT(Name) \
229 if (mode == kAOT) { \
230 INVOKE_PASS(Name); \
231 }
232#else
233#define INVOKE_PASS_AOT(Name)
234#endif
235
236void CompilerPass::RunGraphIntrinsicPipeline(CompilerPassState* pass_state) {
237 INVOKE_PASS(AllocateRegistersForGraphIntrinsic);
238}
239
240void CompilerPass::RunInliningPipeline(PipelineMode mode,
241 CompilerPassState* pass_state) {
242 INVOKE_PASS(ApplyClassIds);
243 INVOKE_PASS(TypePropagation);
244 INVOKE_PASS(ApplyICData);
245 INVOKE_PASS(Canonicalize);
246 // Run constant propagation to make sure we specialize for
247 // (optional) constant arguments passed into the inlined method.
248 INVOKE_PASS(ConstantPropagation);
249 // Constant propagation removes unreachable basic blocks and
250 // may open more opportunities for call specialization.
251 // Call specialization during inlining may cause more call
252 // sites to be discovered and more functions inlined.
253 INVOKE_PASS_AOT(ApplyClassIds);
254 // Optimize (a << b) & c patterns, merge instructions. Must occur
255 // before 'SelectRepresentations' which inserts conversion nodes.
256 INVOKE_PASS(TryOptimizePatterns);
257}
258
259FlowGraph* CompilerPass::RunForceOptimizedPipeline(
260 PipelineMode mode,
261 CompilerPassState* pass_state) {
262 INVOKE_PASS(ComputeSSA);
263 if (FLAG_early_round_trip_serialization) {
264 INVOKE_PASS(RoundTripSerialization);
265 }
266 INVOKE_PASS(TypePropagation);
267 INVOKE_PASS(Canonicalize);
268 INVOKE_PASS(BranchSimplify);
269 INVOKE_PASS(IfConvert);
270 INVOKE_PASS(ConstantPropagation);
271 INVOKE_PASS(TypePropagation);
272 INVOKE_PASS(WidenSmiToInt32);
273 INVOKE_PASS(SelectRepresentations);
274 INVOKE_PASS(TypePropagation);
275 INVOKE_PASS(TryCatchOptimization);
276 INVOKE_PASS(EliminateEnvironments);
277 INVOKE_PASS(EliminateDeadPhis);
278 // Currently DCE assumes that EliminateEnvironments has already been run,
279 // so it should not be lifted earlier than that pass.
280 INVOKE_PASS(DCE);
281 INVOKE_PASS(Canonicalize);
282 INVOKE_PASS_AOT(DelayAllocations);
283 INVOKE_PASS(EliminateWriteBarriers);
284 INVOKE_PASS(FinalizeGraph);
285 INVOKE_PASS_AOT(SerializeGraph);
286 if (FLAG_late_round_trip_serialization) {
287 INVOKE_PASS(RoundTripSerialization);
288 }
289 INVOKE_PASS(AllocateRegisters);
290 INVOKE_PASS(ReorderBlocks);
291 return pass_state->flow_graph();
292}
293
294FlowGraph* CompilerPass::RunPipeline(PipelineMode mode,
295 CompilerPassState* pass_state) {
296 INVOKE_PASS(ComputeSSA);
297 if (FLAG_early_round_trip_serialization) {
298 INVOKE_PASS(RoundTripSerialization);
299 }
300 INVOKE_PASS_AOT(ApplyClassIds);
301 INVOKE_PASS_AOT(TypePropagation);
302 INVOKE_PASS(ApplyICData);
303 INVOKE_PASS(TryOptimizePatterns);
304 INVOKE_PASS(SetOuterInliningId);
305 INVOKE_PASS(TypePropagation);
306 INVOKE_PASS(ApplyClassIds);
307 INVOKE_PASS(Inlining);
308 INVOKE_PASS(TypePropagation);
309 INVOKE_PASS(ApplyClassIds);
310 INVOKE_PASS(TypePropagation);
311 INVOKE_PASS(ApplyICData);
312 INVOKE_PASS(Canonicalize);
313 INVOKE_PASS(BranchSimplify);
314 INVOKE_PASS(IfConvert);
315 INVOKE_PASS(Canonicalize);
316 INVOKE_PASS(ConstantPropagation);
317 INVOKE_PASS(OptimisticallySpecializeSmiPhis);
318 INVOKE_PASS(TypePropagation);
319 // The extra call specialization pass in AOT is able to specialize more
320 // calls after ConstantPropagation, which removes unreachable code, and
321 // TypePropagation, which can infer more accurate types after removing
322 // unreachable code.
323 INVOKE_PASS_AOT(ApplyICData);
324 INVOKE_PASS_AOT(OptimizeTypedDataAccesses);
325 INVOKE_PASS(WidenSmiToInt32);
326 INVOKE_PASS(SelectRepresentations);
327 INVOKE_PASS(CSE);
328 INVOKE_PASS(LICM);
329 INVOKE_PASS(TryOptimizePatterns);
330 INVOKE_PASS(DSE);
331 INVOKE_PASS(TypePropagation);
332 INVOKE_PASS(RangeAnalysis);
333 INVOKE_PASS(OptimizeBranches);
334 INVOKE_PASS(TypePropagation);
335 INVOKE_PASS(TryCatchOptimization);
336 INVOKE_PASS(EliminateEnvironments);
337 INVOKE_PASS(EliminateDeadPhis);
338 // Currently DCE assumes that EliminateEnvironments has already been run,
339 // so it should not be lifted earlier than that pass.
340 INVOKE_PASS(DCE);
341 INVOKE_PASS(Canonicalize);
342 INVOKE_PASS_AOT(DelayAllocations);
343 // Repeat branches optimization after DCE, as it could make more
344 // empty blocks.
345 INVOKE_PASS(OptimizeBranches);
346 INVOKE_PASS(AllocationSinking_Sink);
347 INVOKE_PASS(EliminateDeadPhis);
348 INVOKE_PASS(DCE);
349 INVOKE_PASS(TypePropagation);
350 INVOKE_PASS(SelectRepresentations);
351 INVOKE_PASS(Canonicalize);
352 INVOKE_PASS(UseTableDispatch);
353 INVOKE_PASS(EliminateStackOverflowChecks);
354 INVOKE_PASS(Canonicalize);
355 INVOKE_PASS(AllocationSinking_DetachMaterializations);
356 INVOKE_PASS(EliminateWriteBarriers);
357 INVOKE_PASS(FinalizeGraph);
358 // If we are serializing the flow graph, do it now before we start
359 // doing register allocation.
360 INVOKE_PASS_AOT(SerializeGraph);
361 if (FLAG_late_round_trip_serialization) {
362 INVOKE_PASS(RoundTripSerialization);
363 }
364 INVOKE_PASS(AllocateRegisters);
365 INVOKE_PASS(ReorderBlocks);
366 return pass_state->flow_graph();
367}
368
369FlowGraph* CompilerPass::RunPipelineWithPasses(
370 CompilerPassState* state,
371 std::initializer_list<CompilerPass::Id> passes) {
372 for (auto pass_id : passes) {
373 passes_[pass_id]->Run(state);
374 }
375 return state->flow_graph();
376}
377
378COMPILER_PASS(ComputeSSA, {
379 // Transform to SSA (virtual register 0 and no inlining arguments).
380 flow_graph->ComputeSSA(0, NULL);
381});
382
383COMPILER_PASS(ApplyICData, { state->call_specializer->ApplyICData(); });
384
385COMPILER_PASS(TryOptimizePatterns, { flow_graph->TryOptimizePatterns(); });
386
387COMPILER_PASS(SetOuterInliningId,
388 { FlowGraphInliner::SetInliningId(flow_graph, 0); });
389
390COMPILER_PASS(Inlining, {
391 FlowGraphInliner inliner(
392 flow_graph, &state->inline_id_to_function, &state->inline_id_to_token_pos,
393 &state->caller_inline_id, state->speculative_policy, state->precompiler);
394 state->inlining_depth = inliner.Inline();
395});
396
397COMPILER_PASS(TypePropagation,
398 { FlowGraphTypePropagator::Propagate(flow_graph); });
399
400COMPILER_PASS(ApplyClassIds, { state->call_specializer->ApplyClassIds(); });
401
402COMPILER_PASS(EliminateStackOverflowChecks, {
403 if (!flow_graph->IsCompiledForOsr()) {
404 CheckStackOverflowElimination::EliminateStackOverflow(flow_graph);
405 }
406});
407
408COMPILER_PASS(Canonicalize, {
409 // Do optimizations that depend on the propagated type information.
410 if (flow_graph->Canonicalize()) {
411 flow_graph->Canonicalize();
412 }
413});
414
415COMPILER_PASS(BranchSimplify, { BranchSimplifier::Simplify(flow_graph); });
416
417COMPILER_PASS(IfConvert, { IfConverter::Simplify(flow_graph); });
418
419COMPILER_PASS_REPEAT(ConstantPropagation, {
420 ConstantPropagator::Optimize(flow_graph);
421 return true;
422});
423
424// Optimistically convert loop phis that have a single non-smi input
425// coming from the loop pre-header into smi-phis.
426COMPILER_PASS(OptimisticallySpecializeSmiPhis, {
427 LICM licm(flow_graph);
428 licm.OptimisticallySpecializeSmiPhis();
429});
430
431COMPILER_PASS(WidenSmiToInt32, {
432 // Where beneficial convert Smi operations into Int32 operations.
433 // Only meanigful for 32bit platforms right now.
434 flow_graph->WidenSmiToInt32();
435});
436
437COMPILER_PASS(SelectRepresentations, {
438 // Unbox doubles. Performed after constant propagation to minimize
439 // interference from phis merging double values and tagged
440 // values coming from dead paths.
441 flow_graph->SelectRepresentations();
442});
443
444COMPILER_PASS(UseTableDispatch, {
445 if (FLAG_use_bare_instructions && FLAG_use_table_dispatch) {
446 state->call_specializer->ReplaceInstanceCallsWithDispatchTableCalls();
447 }
448});
449
450COMPILER_PASS_REPEAT(CSE, { return DominatorBasedCSE::Optimize(flow_graph); });
451
452COMPILER_PASS(LICM, {
453 flow_graph->RenameUsesDominatedByRedefinitions();
454 DEBUG_ASSERT(flow_graph->VerifyRedefinitions());
455 LICM licm(flow_graph);
456 licm.Optimize();
457 flow_graph->RemoveRedefinitions(/*keep_checks*/ true);
458});
459
460COMPILER_PASS(DSE, { DeadStoreElimination::Optimize(flow_graph); });
461
462COMPILER_PASS(RangeAnalysis, {
463 // We have to perform range analysis after LICM because it
464 // optimistically moves CheckSmi through phis into loop preheaders
465 // making some phis smi.
466 RangeAnalysis range_analysis(flow_graph);
467 range_analysis.Analyze();
468});
469
470COMPILER_PASS(OptimizeBranches, {
471 // Constant propagation can use information from range analysis to
472 // find unreachable branch targets and eliminate branches that have
473 // the same true- and false-target.
474 ConstantPropagator::OptimizeBranches(flow_graph);
475});
476
477COMPILER_PASS(OptimizeTypedDataAccesses,
478 { TypedDataSpecializer::Optimize(flow_graph); });
479
480COMPILER_PASS(TryCatchOptimization, {
481 OptimizeCatchEntryStates(flow_graph,
482 /*is_aot=*/CompilerState::Current().is_aot());
483});
484
485COMPILER_PASS(EliminateEnvironments, { flow_graph->EliminateEnvironments(); });
486
487COMPILER_PASS(EliminateDeadPhis,
488 { DeadCodeElimination::EliminateDeadPhis(flow_graph); });
489
490COMPILER_PASS(DCE, { DeadCodeElimination::EliminateDeadCode(flow_graph); });
491
492COMPILER_PASS(DelayAllocations, { DelayAllocations::Optimize(flow_graph); });
493
494COMPILER_PASS(AllocationSinking_Sink, {
495 // TODO(vegorov): Support allocation sinking with try-catch.
496 if (flow_graph->graph_entry()->catch_entries().is_empty()) {
497 state->sinking = new AllocationSinking(flow_graph);
498 state->sinking->Optimize();
499 }
500});
501
502COMPILER_PASS(AllocationSinking_DetachMaterializations, {
503 if (state->sinking != NULL) {
504 // Remove all MaterializeObject instructions inserted by allocation
505 // sinking from the flow graph and let them float on the side
506 // referenced only from environments. Register allocator will consider
507 // them as part of a deoptimization environment.
508 state->sinking->DetachMaterializations();
509 }
510});
511
512COMPILER_PASS(AllocateRegisters, {
513 flow_graph->InsertPushArguments();
514 // Ensure loop hierarchy has been computed.
515 flow_graph->GetLoopHierarchy();
516 // Perform register allocation on the SSA graph.
517 FlowGraphAllocator allocator(*flow_graph);
518 allocator.AllocateRegisters();
519});
520
521COMPILER_PASS(AllocateRegistersForGraphIntrinsic, {
522 // Ensure loop hierarchy has been computed.
523 flow_graph->GetLoopHierarchy();
524 // Perform register allocation on the SSA graph.
525 FlowGraphAllocator allocator(*flow_graph, /*intrinsic_mode=*/true);
526 allocator.AllocateRegisters();
527});
528
529COMPILER_PASS(ReorderBlocks, {
530 if (state->reorder_blocks) {
531 BlockScheduler::ReorderBlocks(flow_graph);
532 }
533});
534
535COMPILER_PASS(EliminateWriteBarriers, { EliminateWriteBarriers(flow_graph); });
536
537COMPILER_PASS(FinalizeGraph, {
538 // At the end of the pipeline, force recomputing and caching graph
539 // information (instruction and call site counts) for the (assumed)
540 // non-specialized case with better values, for future inlining.
541 intptr_t instruction_count = 0;
542 intptr_t call_site_count = 0;
543 FlowGraphInliner::CollectGraphInfo(flow_graph,
544 /*constants_count*/ 0,
545 /*force*/ true, &instruction_count,
546 &call_site_count);
547 flow_graph->function().set_inlining_depth(state->inlining_depth);
548 // Remove redefinitions for the rest of the pipeline.
549 flow_graph->RemoveRedefinitions();
550});
551
552#if defined(DART_PRECOMPILER)
553COMPILER_PASS(SerializeGraph, {
554 if (state->precompiler == nullptr) return state;
555 if (auto stream = state->precompiler->il_serialization_stream()) {
556 auto file_write = Dart::file_write_callback();
557 ASSERT(file_write != nullptr);
558
559 const intptr_t kInitialBufferSize = 1 * MB;
560 TextBuffer buffer(kInitialBufferSize);
561 StackZone stack_zone(Thread::Current());
562 FlowGraphSerializer::SerializeToBuffer(stack_zone.GetZone(), flow_graph,
563 &buffer);
564
565 file_write(buffer.buffer(), buffer.length(), stream);
566 }
567});
568#endif
569
570COMPILER_PASS(RoundTripSerialization, {
571 FlowGraphDeserializer::RoundTripSerialization(state);
572 ASSERT(state->flow_graph() != nullptr);
573})
574
575} // namespace dart
576