| OLD | NEW |
|---|
| 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2016, 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 import 'package:kernel/ast.dart' as ir; | 5 import 'package:kernel/ast.dart' as ir; |
| 6 | 6 |
| 7 import '../closure.dart' show LoopClosureRepresentationInfo; | 7 import '../closure.dart' show LoopClosureRepresentationInfo; |
| 8 import '../elements/jumps.dart'; | 8 import '../elements/jumps.dart'; |
| 9 import '../io/source_information.dart'; | 9 import '../io/source_information.dart'; |
| 10 import '../tree/tree.dart' as ast; | 10 import '../tree/tree.dart' as ast; |
| (...skipping 10 matching lines...) Expand all Loading... |
| 21 abstract class LoopHandler<T> { | 21 abstract class LoopHandler<T> { |
| 22 final GraphBuilder builder; | 22 final GraphBuilder builder; |
| 23 | 23 |
| 24 LoopHandler(this.builder); | 24 LoopHandler(this.builder); |
| 25 | 25 |
| 26 /// Builds a graph for the given [loop] node. | 26 /// Builds a graph for the given [loop] node. |
| 27 /// | 27 /// |
| 28 /// For while loops, [initialize] and [update] are null. | 28 /// For while loops, [initialize] and [update] are null. |
| 29 /// The [condition] function must return a boolean result. | 29 /// The [condition] function must return a boolean result. |
| 30 /// None of the functions must leave anything on the stack. | 30 /// None of the functions must leave anything on the stack. |
| 31 void handleLoop(T loop, LoopClosureRepresentationInfo loopClosureInfo, | 31 void handleLoop( |
| 32 void initialize(), HInstruction condition(), void update(), void body()) { | 32 T loop, |
| 33 LoopClosureRepresentationInfo loopClosureInfo, |
| 34 JumpTarget jumpTarget, |
| 35 void initialize(), |
| 36 HInstruction condition(), |
| 37 void update(), |
| 38 void body()) { |
| 33 // Generate: | 39 // Generate: |
| 34 // <initializer> | 40 // <initializer> |
| 35 // loop-entry: | 41 // loop-entry: |
| 36 // if (!<condition>) goto loop-exit; | 42 // if (!<condition>) goto loop-exit; |
| 37 // <body> | 43 // <body> |
| 38 // <updates> | 44 // <updates> |
| 39 // goto loop-entry; | 45 // goto loop-entry; |
| 40 // loop-exit: | 46 // loop-exit: |
| 41 | 47 |
| 42 builder.localsHandler.startLoop(loopClosureInfo); | 48 builder.localsHandler.startLoop(loopClosureInfo); |
| 43 | 49 |
| 44 // The initializer. | 50 // The initializer. |
| 45 SubExpression initializerGraph = null; | 51 SubExpression initializerGraph = null; |
| 46 HBasicBlock startBlock; | 52 HBasicBlock startBlock; |
| 47 if (initialize != null) { | 53 if (initialize != null) { |
| 48 HBasicBlock initializerBlock = builder.openNewBlock(); | 54 HBasicBlock initializerBlock = builder.openNewBlock(); |
| 49 startBlock = initializerBlock; | 55 startBlock = initializerBlock; |
| 50 initialize(); | 56 initialize(); |
| 51 assert(!builder.isAborted()); | 57 assert(!builder.isAborted()); |
| 52 initializerGraph = new SubExpression(initializerBlock, builder.current); | 58 initializerGraph = new SubExpression(initializerBlock, builder.current); |
| 53 } | 59 } |
| 54 | 60 |
| 55 builder.loopDepth++; | 61 builder.loopDepth++; |
| 56 JumpHandler jumpHandler = beginLoopHeader(loop); | 62 JumpHandler jumpHandler = beginLoopHeader(loop, jumpTarget); |
| 57 HLoopInformation loopInfo = builder.current.loopInformation; | 63 HLoopInformation loopInfo = builder.current.loopInformation; |
| 58 HBasicBlock conditionBlock = builder.current; | 64 HBasicBlock conditionBlock = builder.current; |
| 59 if (startBlock == null) startBlock = conditionBlock; | 65 if (startBlock == null) startBlock = conditionBlock; |
| 60 | 66 |
| 61 HInstruction conditionInstruction = condition(); | 67 HInstruction conditionInstruction = condition(); |
| 62 HBasicBlock conditionEndBlock = | 68 HBasicBlock conditionEndBlock = |
| 63 builder.close(new HLoopBranch(conditionInstruction)); | 69 builder.close(new HLoopBranch(conditionInstruction)); |
| 64 SubExpression conditionExpression = | 70 SubExpression conditionExpression = |
| 65 new SubExpression(conditionBlock, conditionEndBlock); | 71 new SubExpression(conditionBlock, conditionEndBlock); |
| 66 | 72 |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 101 if (bodyBlock != null) { | 107 if (bodyBlock != null) { |
| 102 continueHandlers.add(builder.localsHandler); | 108 continueHandlers.add(builder.localsHandler); |
| 103 bodyBlock.addSuccessor(updateBlock); | 109 bodyBlock.addSuccessor(updateBlock); |
| 104 } | 110 } |
| 105 | 111 |
| 106 builder.open(updateBlock); | 112 builder.open(updateBlock); |
| 107 builder.localsHandler = | 113 builder.localsHandler = |
| 108 continueHandlers[0].mergeMultiple(continueHandlers, updateBlock); | 114 continueHandlers[0].mergeMultiple(continueHandlers, updateBlock); |
| 109 | 115 |
| 110 List<LabelDefinition> labels = jumpHandler.labels; | 116 List<LabelDefinition> labels = jumpHandler.labels; |
| 111 JumpTarget target = getTargetDefinition(loop); | |
| 112 if (labels.isNotEmpty) { | 117 if (labels.isNotEmpty) { |
| 113 beginBodyBlock.setBlockFlow( | 118 beginBodyBlock.setBlockFlow( |
| 114 new HLabeledBlockInformation( | 119 new HLabeledBlockInformation( |
| 115 new HSubGraphBlockInformation(bodyGraph), jumpHandler.labels, | 120 new HSubGraphBlockInformation(bodyGraph), jumpHandler.labels, |
| 116 isContinue: true), | 121 isContinue: true), |
| 117 updateBlock); | 122 updateBlock); |
| 118 } else if (target != null && target.isContinueTarget) { | 123 } else if (jumpTarget != null && jumpTarget.isContinueTarget) { |
| 119 beginBodyBlock.setBlockFlow( | 124 beginBodyBlock.setBlockFlow( |
| 120 new HLabeledBlockInformation.implicit( | 125 new HLabeledBlockInformation.implicit( |
| 121 new HSubGraphBlockInformation(bodyGraph), target, | 126 new HSubGraphBlockInformation(bodyGraph), jumpTarget, |
| 122 isContinue: true), | 127 isContinue: true), |
| 123 updateBlock); | 128 updateBlock); |
| 124 } | 129 } |
| 125 | 130 |
| 126 builder.localsHandler.enterLoopUpdates(loopClosureInfo); | 131 builder.localsHandler.enterLoopUpdates(loopClosureInfo); |
| 127 | 132 |
| 128 update(); | 133 update(); |
| 129 | 134 |
| 130 HBasicBlock updateEndBlock = builder.close(new HGoto()); | 135 HBasicBlock updateEndBlock = builder.close(new HGoto()); |
| 131 // The back-edge completing the cycle. | 136 // The back-edge completing the cycle. |
| (...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 186 builder.wrapStatementGraph(bodyGraph), | 191 builder.wrapStatementGraph(bodyGraph), |
| 187 builder.wrapStatementGraph(elseGraph)); | 192 builder.wrapStatementGraph(elseGraph)); |
| 188 | 193 |
| 189 conditionEndBlock.setBlockFlow(info, builder.current); | 194 conditionEndBlock.setBlockFlow(info, builder.current); |
| 190 HIf ifBlock = conditionEndBlock.last; | 195 HIf ifBlock = conditionEndBlock.last; |
| 191 ifBlock.blockInformation = conditionEndBlock.blockFlow; | 196 ifBlock.blockInformation = conditionEndBlock.blockFlow; |
| 192 | 197 |
| 193 // If the body has any break, attach a synthesized label to the | 198 // If the body has any break, attach a synthesized label to the |
| 194 // if block. | 199 // if block. |
| 195 if (jumpHandler.hasAnyBreak()) { | 200 if (jumpHandler.hasAnyBreak()) { |
| 196 JumpTarget target = getTargetDefinition(loop); | 201 LabelDefinition label = |
| 197 LabelDefinition label = target.addLabel(null, 'loop'); | 202 jumpTarget.addLabel(null, 'loop', isBreakTarget: true); |
| 198 label.setBreakTarget(); | |
| 199 SubGraph labelGraph = new SubGraph(conditionBlock, builder.current); | 203 SubGraph labelGraph = new SubGraph(conditionBlock, builder.current); |
| 200 HLabeledBlockInformation labelInfo = new HLabeledBlockInformation( | 204 HLabeledBlockInformation labelInfo = new HLabeledBlockInformation( |
| 201 new HSubGraphBlockInformation(labelGraph), | 205 new HSubGraphBlockInformation(labelGraph), |
| 202 <LabelDefinition>[label]); | 206 <LabelDefinition>[label]); |
| 203 | 207 |
| 204 conditionBlock.setBlockFlow(labelInfo, builder.current); | 208 conditionBlock.setBlockFlow(labelInfo, builder.current); |
| 205 | 209 |
| 206 jumpHandler.forEachBreak((HBreak breakInstruction, _) { | 210 jumpHandler.forEachBreak((HBreak breakInstruction, _) { |
| 207 HBasicBlock block = breakInstruction.block; | 211 HBasicBlock block = breakInstruction.block; |
| 208 block.addAtExit(new HBreak.toLabel(label)); | 212 block.addAtExit(new HBreak.toLabel(label)); |
| 209 block.remove(breakInstruction); | 213 block.remove(breakInstruction); |
| 210 }); | 214 }); |
| 211 } | 215 } |
| 212 } | 216 } |
| 213 jumpHandler.close(); | 217 jumpHandler.close(); |
| 214 builder.loopDepth--; | 218 builder.loopDepth--; |
| 215 } | 219 } |
| 216 | 220 |
| 217 /// Creates a new loop-header block. The previous [current] block | 221 /// Creates a new loop-header block. The previous [current] block |
| 218 /// is closed with an [HGoto] and replaced by the newly created block. | 222 /// is closed with an [HGoto] and replaced by the newly created block. |
| 219 /// Also notifies the locals handler that we're entering a loop. | 223 /// Also notifies the locals handler that we're entering a loop. |
| 220 JumpHandler beginLoopHeader(T node) { | 224 JumpHandler beginLoopHeader(T node, JumpTarget jumpTarget) { |
| 221 assert(!builder.isAborted()); | 225 assert(!builder.isAborted()); |
| 222 HBasicBlock previousBlock = builder.close(new HGoto()); | 226 HBasicBlock previousBlock = builder.close(new HGoto()); |
| 223 | 227 |
| 224 JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: true); | 228 JumpHandler jumpHandler = |
| 229 createJumpHandler(node, jumpTarget, isLoopJump: true); |
| 225 HBasicBlock loopEntry = builder.graph | 230 HBasicBlock loopEntry = builder.graph |
| 226 .addNewLoopHeaderBlock(jumpHandler.target, jumpHandler.labels); | 231 .addNewLoopHeaderBlock(jumpHandler.target, jumpHandler.labels); |
| 227 previousBlock.addSuccessor(loopEntry); | 232 previousBlock.addSuccessor(loopEntry); |
| 228 builder.open(loopEntry); | 233 builder.open(loopEntry); |
| 229 | 234 |
| 230 builder.localsHandler.beginLoopHeader(loopEntry); | 235 builder.localsHandler.beginLoopHeader(loopEntry); |
| 231 return jumpHandler; | 236 return jumpHandler; |
| 232 } | 237 } |
| 233 | 238 |
| 234 /// Ends the loop. | 239 /// Ends the loop. |
| (...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 278 // condition fails. | 283 // condition fails. |
| 279 breakHandlers.add(savedLocals); | 284 breakHandlers.add(savedLocals); |
| 280 } | 285 } |
| 281 builder.localsHandler = | 286 builder.localsHandler = |
| 282 savedLocals.mergeMultiple(breakHandlers, loopExitBlock); | 287 savedLocals.mergeMultiple(breakHandlers, loopExitBlock); |
| 283 } else { | 288 } else { |
| 284 builder.localsHandler = savedLocals; | 289 builder.localsHandler = savedLocals; |
| 285 } | 290 } |
| 286 } | 291 } |
| 287 | 292 |
| 288 /// Returns the jump target defined by [node]. | |
| 289 JumpTarget getTargetDefinition(T node); | |
| 290 | |
| 291 /// Determine what kind of loop [node] represents. | 293 /// Determine what kind of loop [node] represents. |
| 292 /// | 294 /// |
| 293 /// The result is one of the kinds defined in [HLoopBlockInformation]. | 295 /// The result is one of the kinds defined in [HLoopBlockInformation]. |
| 294 int loopKind(T node); | 296 int loopKind(T node); |
| 295 | 297 |
| 296 /// Returns the source information for the loop [node]. | 298 /// Returns the source information for the loop [node]. |
| 297 SourceInformation loopSourceInformation(T node); | 299 SourceInformation loopSourceInformation(T node); |
| 298 | 300 |
| 299 /// Creates a [JumpHandler] for a statement. The node must be a jump | 301 /// Creates a [JumpHandler] for a statement. The node must be a jump |
| 300 /// target. If there are no breaks or continues targeting the statement, | 302 /// target. If there are no breaks or continues targeting the statement, |
| 301 /// a special "null handler" is returned. | 303 /// a special "null handler" is returned. |
| 302 /// | 304 /// |
| 303 /// [isLoopJump] is [:true:] when the jump handler is for a loop. This is used | 305 /// [isLoopJump] is [:true:] when the jump handler is for a loop. This is used |
| 304 /// to distinguish the synthesized loop created for a switch statement with | 306 /// to distinguish the synthesized loop created for a switch statement with |
| 305 /// continue statements from simple switch statements. | 307 /// continue statements from simple switch statements. |
| 306 JumpHandler createJumpHandler(T node, {bool isLoopJump}); | 308 JumpHandler createJumpHandler(T node, JumpTarget jumpTarget, |
| 309 {bool isLoopJump}); |
| 307 } | 310 } |
| 308 | 311 |
| 309 /// A loop handler for the builder that just uses AST nodes directly. | 312 /// A loop handler for the builder that just uses AST nodes directly. |
| 310 class SsaLoopHandler extends LoopHandler<ast.Node> { | 313 class SsaLoopHandler extends LoopHandler<ast.Node> { |
| 311 final SsaAstGraphBuilder builder; | 314 final SsaAstGraphBuilder builder; |
| 312 | 315 |
| 313 SsaLoopHandler(SsaAstGraphBuilder builder) | 316 SsaLoopHandler(SsaAstGraphBuilder builder) |
| 314 : this.builder = builder, | 317 : this.builder = builder, |
| 315 super(builder); | 318 super(builder); |
| 316 | 319 |
| 317 @override | 320 @override |
| 318 JumpTarget getTargetDefinition(ast.Node node) { | |
| 319 return builder.elements.getTargetDefinition(node); | |
| 320 } | |
| 321 | |
| 322 @override | |
| 323 int loopKind(ast.Node node) => node.accept(const _SsaLoopTypeVisitor()); | 321 int loopKind(ast.Node node) => node.accept(const _SsaLoopTypeVisitor()); |
| 324 | 322 |
| 325 @override | 323 @override |
| 326 SourceInformation loopSourceInformation(ast.Node node) => | 324 SourceInformation loopSourceInformation(ast.Node node) => |
| 327 builder.sourceInformationBuilder.buildLoop(node); | 325 builder.sourceInformationBuilder.buildLoop(node); |
| 328 | 326 |
| 329 @override | 327 @override |
| 330 JumpHandler createJumpHandler(ast.Node node, {bool isLoopJump}) => | 328 JumpHandler createJumpHandler(ast.Node node, JumpTarget jumpTarget, |
| 331 builder.createJumpHandler(node, isLoopJump: isLoopJump); | 329 {bool isLoopJump}) => |
| 330 builder.createJumpHandler(node, jumpTarget, isLoopJump: isLoopJump); |
| 332 } | 331 } |
| 333 | 332 |
| 334 class _SsaLoopTypeVisitor extends ast.Visitor { | 333 class _SsaLoopTypeVisitor extends ast.Visitor { |
| 335 const _SsaLoopTypeVisitor(); | 334 const _SsaLoopTypeVisitor(); |
| 336 int visitNode(ast.Node node) => HLoopBlockInformation.NOT_A_LOOP; | 335 int visitNode(ast.Node node) => HLoopBlockInformation.NOT_A_LOOP; |
| 337 int visitWhile(ast.While node) => HLoopBlockInformation.WHILE_LOOP; | 336 int visitWhile(ast.While node) => HLoopBlockInformation.WHILE_LOOP; |
| 338 int visitFor(ast.For node) => HLoopBlockInformation.FOR_LOOP; | 337 int visitFor(ast.For node) => HLoopBlockInformation.FOR_LOOP; |
| 339 int visitDoWhile(ast.DoWhile node) => HLoopBlockInformation.DO_WHILE_LOOP; | 338 int visitDoWhile(ast.DoWhile node) => HLoopBlockInformation.DO_WHILE_LOOP; |
| 340 int visitAsyncForIn(ast.AsyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP; | 339 int visitAsyncForIn(ast.AsyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP; |
| 341 int visitSyncForIn(ast.SyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP; | 340 int visitSyncForIn(ast.SyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP; |
| 342 int visitSwitchStatement(ast.SwitchStatement node) => | 341 int visitSwitchStatement(ast.SwitchStatement node) => |
| 343 HLoopBlockInformation.SWITCH_CONTINUE_LOOP; | 342 HLoopBlockInformation.SWITCH_CONTINUE_LOOP; |
| 344 } | 343 } |
| 345 | 344 |
| 346 // TODO(het): Since kernel simplifies loop breaks and continues, we should | 345 // TODO(het): Since kernel simplifies loop breaks and continues, we should |
| 347 // rewrite the loop handler from scratch to account for the simplified structure | 346 // rewrite the loop handler from scratch to account for the simplified structure |
| 348 class KernelLoopHandler extends LoopHandler<ir.TreeNode> { | 347 class KernelLoopHandler extends LoopHandler<ir.TreeNode> { |
| 349 final KernelSsaGraphBuilder builder; | 348 final KernelSsaGraphBuilder builder; |
| 350 | 349 |
| 351 KernelAstAdapter get astAdapter => builder.astAdapter; | 350 KernelAstAdapter get astAdapter => builder.astAdapter; |
| 352 | 351 |
| 353 KernelLoopHandler(KernelSsaGraphBuilder builder) | 352 KernelLoopHandler(KernelSsaGraphBuilder builder) |
| 354 : this.builder = builder, | 353 : this.builder = builder, |
| 355 super(builder); | 354 super(builder); |
| 356 | 355 |
| 357 @override | 356 @override |
| 358 JumpHandler createJumpHandler(ir.TreeNode node, {bool isLoopJump}) => | 357 JumpHandler createJumpHandler(ir.TreeNode node, JumpTarget jumpTarget, |
| 359 builder.createJumpHandler(node, isLoopJump: isLoopJump); | 358 {bool isLoopJump}) => |
| 360 | 359 builder.createJumpHandler(node, jumpTarget, isLoopJump: isLoopJump); |
| 361 @override | |
| 362 JumpTarget getTargetDefinition(ir.TreeNode node) => | |
| 363 builder.localsMap.getJumpTarget(node); | |
| 364 | 360 |
| 365 @override | 361 @override |
| 366 int loopKind(ir.TreeNode node) => node.accept(new _KernelLoopTypeVisitor()); | 362 int loopKind(ir.TreeNode node) => node.accept(new _KernelLoopTypeVisitor()); |
| 367 | 363 |
| 368 // TODO(het): return the actual source information | 364 // TODO(het): return the actual source information |
| 369 @override | 365 @override |
| 370 SourceInformation loopSourceInformation(ir.TreeNode node) => null; | 366 SourceInformation loopSourceInformation(ir.TreeNode node) => null; |
| 371 } | 367 } |
| 372 | 368 |
| 373 class _KernelLoopTypeVisitor extends ir.Visitor<int> { | 369 class _KernelLoopTypeVisitor extends ir.Visitor<int> { |
| (...skipping 12 matching lines...) Expand all Loading... |
| 386 HLoopBlockInformation.DO_WHILE_LOOP; | 382 HLoopBlockInformation.DO_WHILE_LOOP; |
| 387 | 383 |
| 388 @override | 384 @override |
| 389 int visitForInStatement(ir.ForInStatement node) => | 385 int visitForInStatement(ir.ForInStatement node) => |
| 390 HLoopBlockInformation.FOR_IN_LOOP; | 386 HLoopBlockInformation.FOR_IN_LOOP; |
| 391 | 387 |
| 392 @override | 388 @override |
| 393 int visitSwitchStatement(ir.SwitchStatement node) => | 389 int visitSwitchStatement(ir.SwitchStatement node) => |
| 394 HLoopBlockInformation.SWITCH_CONTINUE_LOOP; | 390 HLoopBlockInformation.SWITCH_CONTINUE_LOOP; |
| 395 } | 391 } |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2954463002:
Refactoring to prepare for kernel based jump targets (Closed)
