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 |