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

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

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

Powered by Google App Engine
This is Rietveld 408576698