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

Side by Side Diff: lib/compiler/implementation/ssa/optimize.dart

Issue 10386086: RFC: Start refactoring to provide more than a single backend. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Next iteration Created 8 years, 7 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) 2011, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2011, 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 interface OptimizationPhase { 5 interface OptimizationPhase {
6 String get name(); 6 String get name();
7 void visitGraph(HGraph graph); 7 void visitGraph(HGraph graph);
8 } 8 }
9 9
10 class SsaOptimizerTask extends CompilerTask { 10 class SsaOptimizerTask extends CompilerTask {
11 SsaOptimizerTask(Compiler compiler) : super(compiler); 11 final JavaScriptBackend backend;
12 SsaOptimizerTask(JavaScriptBackend backend)
13 : this.backend = backend,
14 super(backend.compiler);
12 String get name() => 'SSA optimizer'; 15 String get name() => 'SSA optimizer';
16 Compiler get compiler() => backend.compiler;
13 17
14 void runPhases(HGraph graph, List<OptimizationPhase> phases) { 18 void runPhases(HGraph graph, List<OptimizationPhase> phases) {
15 for (OptimizationPhase phase in phases) { 19 for (OptimizationPhase phase in phases) {
16 phase.visitGraph(graph); 20 phase.visitGraph(graph);
17 compiler.tracer.traceGraph(phase.name, graph); 21 compiler.tracer.traceGraph(phase.name, graph);
18 } 22 }
19 } 23 }
20 24
21 void optimize(WorkItem work, HGraph graph) { 25 void optimize(WorkItem work, HGraph graph) {
22 measure(() { 26 measure(() {
23 List<OptimizationPhase> phases = <OptimizationPhase>[ 27 List<OptimizationPhase> phases = <OptimizationPhase>[
24 // Run trivial constant folding first to optimize 28 // Run trivial constant folding first to optimize
25 // some patterns useful for type conversion. 29 // some patterns useful for type conversion.
26 new SsaConstantFolder(compiler), 30 new SsaConstantFolder(backend),
27 new SsaTypeConversionInserter(compiler), 31 new SsaTypeConversionInserter(compiler),
28 new SsaTypePropagator(compiler), 32 new SsaTypePropagator(compiler),
29 new SsaCheckInserter(compiler), 33 new SsaCheckInserter(backend),
30 new SsaConstantFolder(compiler), 34 new SsaConstantFolder(backend),
31 new SsaRedundantPhiEliminator(), 35 new SsaRedundantPhiEliminator(),
32 new SsaDeadPhiEliminator(), 36 new SsaDeadPhiEliminator(),
33 new SsaGlobalValueNumberer(compiler), 37 new SsaGlobalValueNumberer(compiler),
34 new SsaCodeMotion(), 38 new SsaCodeMotion(),
35 new SsaDeadCodeEliminator()]; 39 new SsaDeadCodeEliminator()];
36 runPhases(graph, phases); 40 runPhases(graph, phases);
37 }); 41 });
38 } 42 }
39 43
40 bool trySpeculativeOptimizations(WorkItem work, HGraph graph) { 44 bool trySpeculativeOptimizations(WorkItem work, HGraph graph) {
41 return measure(() { 45 return measure(() {
42 // Run the phases that will generate type guards. 46 // Run the phases that will generate type guards.
43 List<OptimizationPhase> phases = <OptimizationPhase>[ 47 List<OptimizationPhase> phases = <OptimizationPhase>[
44 new SsaSpeculativeTypePropagator(compiler), 48 new SsaSpeculativeTypePropagator(compiler),
45 new SsaTypeGuardInserter(work), 49 new SsaTypeGuardInserter(work),
46 new SsaEnvironmentBuilder(compiler), 50 new SsaEnvironmentBuilder(compiler),
47 // Change the propagated types back to what they were before we 51 // Change the propagated types back to what they were before we
48 // speculatively propagated, so that we can generate the bailout 52 // speculatively propagated, so that we can generate the bailout
49 // version. 53 // version.
50 // Note that we do this even if there were no guards inserted. If a 54 // Note that we do this even if there were no guards inserted. If a
51 // guard is not beneficial enough we don't emit one, but there might 55 // guard is not beneficial enough we don't emit one, but there might
52 // still be speculative types on the instructions. 56 // still be speculative types on the instructions.
53 new SsaTypePropagator(compiler), 57 new SsaTypePropagator(compiler),
54 // Then run the [SsaCheckInserter] because the type propagator also 58 // Then run the [SsaCheckInserter] because the type propagator also
55 // propagated types non-speculatively. For example, it might have 59 // propagated types non-speculatively. For example, it might have
56 // propagated the type array for a call to the List constructor. 60 // propagated the type array for a call to the List constructor.
57 new SsaCheckInserter(compiler)]; 61 new SsaCheckInserter(backend)];
58 runPhases(graph, phases); 62 runPhases(graph, phases);
59 return !work.guards.isEmpty(); 63 return !work.guards.isEmpty();
60 }); 64 });
61 } 65 }
62 66
63 void prepareForSpeculativeOptimizations(WorkItem work, HGraph graph) { 67 void prepareForSpeculativeOptimizations(WorkItem work, HGraph graph) {
64 measure(() { 68 measure(() {
65 // In order to generate correct code for the bailout version, we did not 69 // In order to generate correct code for the bailout version, we did not
66 // propagate types from the instruction to the type guard. We do it 70 // propagate types from the instruction to the type guard. We do it
67 // now to be able to optimize further. 71 // now to be able to optimize further.
68 work.guards.forEach((HTypeGuard guard) { guard.isOn = true; }); 72 work.guards.forEach((HTypeGuard guard) { guard.isOn = true; });
69 // We also need to insert range and integer checks for the type 73 // We also need to insert range and integer checks for the type
70 // guards. Now that they claim to have a certain type, some 74 // guards. Now that they claim to have a certain type, some
71 // depending instructions might become builtin (like native array 75 // depending instructions might become builtin (like native array
72 // accesses) and need to be checked. 76 // accesses) and need to be checked.
73 // Also run the type propagator, to please the codegen in case 77 // Also run the type propagator, to please the codegen in case
74 // no other optimization is run. 78 // no other optimization is run.
75 runPhases(graph, 79 runPhases(graph,
76 <OptimizationPhase>[new SsaCheckInserter(compiler), 80 <OptimizationPhase>[new SsaCheckInserter(backend),
77 new SsaTypePropagator(compiler)]); 81 new SsaTypePropagator(compiler)]);
78 }); 82 });
79 } 83 }
80 } 84 }
81 85
82 /** 86 /**
83 * If both inputs to known operations are available execute the operation at 87 * If both inputs to known operations are available execute the operation at
84 * compile-time. 88 * compile-time.
85 */ 89 */
86 class SsaConstantFolder extends HBaseVisitor implements OptimizationPhase { 90 class SsaConstantFolder extends HBaseVisitor implements OptimizationPhase {
87 final String name = "SsaConstantFolder"; 91 final String name = "SsaConstantFolder";
88 final Compiler compiler; 92 final JavaScriptBackend backend;
89 HGraph graph; 93 HGraph graph;
94 Compiler get compiler() => backend.compiler;
90 95
91 SsaConstantFolder(this.compiler); 96 SsaConstantFolder(this.backend);
92 97
93 void visitGraph(HGraph visitee) { 98 void visitGraph(HGraph visitee) {
94 graph = visitee; 99 graph = visitee;
95 visitDominatorTree(visitee); 100 visitDominatorTree(visitee);
96 } 101 }
97 102
98 visitBasicBlock(HBasicBlock block) { 103 visitBasicBlock(HBasicBlock block) {
99 HInstruction instruction = block.first; 104 HInstruction instruction = block.first;
100 while (instruction !== null) { 105 while (instruction !== null) {
101 HInstruction next = instruction.next; 106 HInstruction next = instruction.next;
(...skipping 224 matching lines...) Expand 10 before | Expand all | Expand 10 after
326 List<HInstruction> users = instruction.usedBy; 331 List<HInstruction> users = instruction.usedBy;
327 int length = users.length; 332 int length = users.length;
328 for (int i = 0; i < length; i++) { 333 for (int i = 0; i < length; i++) {
329 if (users[i] is! HBoolify) return false; 334 if (users[i] is! HBoolify) return false;
330 } 335 }
331 return true; 336 return true;
332 } 337 }
333 338
334 HInstruction visitRelational(HRelational node) { 339 HInstruction visitRelational(HRelational node) {
335 if (allUsersAreBoolifies(node)) { 340 if (allUsersAreBoolifies(node)) {
336 Interceptors interceptors = compiler.builder.interceptors; 341 Interceptors interceptors = backend.builder.interceptors;
337 HStatic oldTarget = node.target; 342 HStatic oldTarget = node.target;
338 Element boolifiedInterceptor = 343 Element boolifiedInterceptor =
339 interceptors.getBoolifiedVersionOf(oldTarget.element); 344 interceptors.getBoolifiedVersionOf(oldTarget.element);
340 if (boolifiedInterceptor !== null) { 345 if (boolifiedInterceptor !== null) {
341 HStatic boolifiedTarget = new HStatic(boolifiedInterceptor); 346 HStatic boolifiedTarget = new HStatic(boolifiedInterceptor);
342 // We don't remove the [oldTarget] in case it is used by other 347 // We don't remove the [oldTarget] in case it is used by other
343 // instructions. If it is unused it will be treated as dead code and 348 // instructions. If it is unused it will be treated as dead code and
344 // discarded. 349 // discarded.
345 oldTarget.block.addAfter(oldTarget, boolifiedTarget); 350 oldTarget.block.addAfter(oldTarget, boolifiedTarget);
346 // Remove us as user from the [oldTarget]. 351 // Remove us as user from the [oldTarget].
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after
396 HInstruction visitIdentity(HIdentity node) { 401 HInstruction visitIdentity(HIdentity node) {
397 HInstruction newInstruction = handleIdentityCheck(node); 402 HInstruction newInstruction = handleIdentityCheck(node);
398 return newInstruction === null ? super.visitIdentity(node) : newInstruction; 403 return newInstruction === null ? super.visitIdentity(node) : newInstruction;
399 } 404 }
400 405
401 HInstruction foldBuiltinEqualsCheck(HEquals node) { 406 HInstruction foldBuiltinEqualsCheck(HEquals node) {
402 // TODO(floitsch): cache interceptors. 407 // TODO(floitsch): cache interceptors.
403 HInstruction newInstruction = handleIdentityCheck(node); 408 HInstruction newInstruction = handleIdentityCheck(node);
404 if (newInstruction === null) { 409 if (newInstruction === null) {
405 HStatic target = new HStatic( 410 HStatic target = new HStatic(
406 compiler.builder.interceptors.getTripleEqualsInterceptor()); 411 backend.builder.interceptors.getTripleEqualsInterceptor());
407 node.block.addBefore(node, target); 412 node.block.addBefore(node, target);
408 return new HIdentity(target, node.left, node.right); 413 return new HIdentity(target, node.left, node.right);
409 } else { 414 } else {
410 return newInstruction; 415 return newInstruction;
411 } 416 }
412 } 417 }
413 418
414 HInstruction visitEquals(HEquals node) { 419 HInstruction visitEquals(HEquals node) {
415 HInstruction left = node.left; 420 HInstruction left = node.left;
416 HInstruction right = node.right; 421 HInstruction right = node.right;
(...skipping 21 matching lines...) Expand all
438 // not implement operator=. 443 // not implement operator=.
439 return foldBuiltinEqualsCheck(node); 444 return foldBuiltinEqualsCheck(node);
440 } 445 }
441 } 446 }
442 447
443 if (right.isConstantNull()) { 448 if (right.isConstantNull()) {
444 if (left.propagatedType.isPrimitive()) { 449 if (left.propagatedType.isPrimitive()) {
445 return graph.addConstantBool(false); 450 return graph.addConstantBool(false);
446 } else { 451 } else {
447 // TODO(floitsch): cache interceptors. 452 // TODO(floitsch): cache interceptors.
448 Interceptors interceptors = compiler.builder.interceptors; 453 Interceptors interceptors = backend.builder.interceptors;
449 Element equalsElement = interceptors.getEqualsInterceptor(); 454 Element equalsElement = interceptors.getEqualsInterceptor();
450 // If we have a different element than [equalsElement], we 455 // If we have a different element than [equalsElement], we
451 // don't need to optimize this instruction to use another 456 // don't need to optimize this instruction to use another
452 // element: we know the element is either eqNull or eqNullB. 457 // element: we know the element is either eqNull or eqNullB.
453 if (node.element === equalsElement) { 458 if (node.element === equalsElement) {
454 Element targetElement = interceptors.getEqualsNullInterceptor(); 459 Element targetElement = interceptors.getEqualsNullInterceptor();
455 bool onlyUsedInBoolify = allUsersAreBoolifies(node); 460 bool onlyUsedInBoolify = allUsersAreBoolifies(node);
456 if (onlyUsedInBoolify) { 461 if (onlyUsedInBoolify) {
457 targetElement = interceptors.getBoolifiedVersionOf(targetElement); 462 targetElement = interceptors.getBoolifiedVersionOf(targetElement);
458 } 463 }
(...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after
577 if (type === null) return node; 582 if (type === null) return node;
578 if (!compiler.world.isOnlyFields(type, node.name)) return node; 583 if (!compiler.world.isOnlyFields(type, node.name)) return node;
579 return new HFieldSet(node.name, node.inputs[0], node.inputs[1]); 584 return new HFieldSet(node.name, node.inputs[0], node.inputs[1]);
580 } 585 }
581 } 586 }
582 587
583 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase { 588 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase {
584 final String name = "SsaCheckInserter"; 589 final String name = "SsaCheckInserter";
585 Element lengthInterceptor; 590 Element lengthInterceptor;
586 591
587 SsaCheckInserter(Compiler compiler) { 592 SsaCheckInserter(JavaScriptBackend backend) {
588 SourceString lengthString = const SourceString('length'); 593 SourceString lengthString = const SourceString('length');
589 lengthInterceptor = 594 lengthInterceptor =
590 compiler.builder.interceptors.getStaticGetInterceptor(lengthString); 595 backend.builder.interceptors.getStaticGetInterceptor(lengthString);
591 } 596 }
592 597
593 void visitGraph(HGraph graph) { 598 void visitGraph(HGraph graph) {
594 visitDominatorTree(graph); 599 visitDominatorTree(graph);
595 } 600 }
596 601
597 void visitBasicBlock(HBasicBlock block) { 602 void visitBasicBlock(HBasicBlock block) {
598 HInstruction instruction = block.first; 603 HInstruction instruction = block.first;
599 while (instruction !== null) { 604 while (instruction !== null) {
600 HInstruction next = instruction.next; 605 HInstruction next = instruction.next;
(...skipping 511 matching lines...) Expand 10 before | Expand all | Expand 10 after
1112 // the if block terminates. So any use of the instruction 1117 // the if block terminates. So any use of the instruction
1113 // after the join block should be changed to the new 1118 // after the join block should be changed to the new
1114 // instruction. 1119 // instruction.
1115 changeUsesDominatedBy(ifUser.joinBlock, input, convertedType); 1120 changeUsesDominatedBy(ifUser.joinBlock, input, convertedType);
1116 } 1121 }
1117 // TODO(ngeoffray): Also change uses for the then block on a HType 1122 // TODO(ngeoffray): Also change uses for the then block on a HType
1118 // that knows it is not of a specific Type. 1123 // that knows it is not of a specific Type.
1119 } 1124 }
1120 } 1125 }
1121 } 1126 }
OLDNEW
« lib/compiler/implementation/emitter.dart ('K') | « lib/compiler/implementation/ssa/codegen.dart ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698