| OLD | NEW |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 Loading... |
| 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 } |
| OLD | NEW |