| OLD | NEW |
|---|
| (Empty) | |
| 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 |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 import 'package:kernel/ast.dart' as ir; |
| 6 |
| 7 import '../elements/elements.dart'; |
| 8 import '../io/source_information.dart'; |
| 9 import '../tree/tree.dart' as ast; |
| 10 |
| 11 import 'builder.dart'; |
| 12 import 'builder_kernel.dart'; |
| 13 import 'graph_builder.dart'; |
| 14 import 'jump_handler.dart'; |
| 15 import 'kernel_ast_adapter.dart'; |
| 16 import 'locals_handler.dart'; |
| 17 import 'nodes.dart'; |
| 18 |
| 19 /// Builds the SSA graph for loop nodes. |
| 20 abstract class LoopHandler<T> { |
| 21 final GraphBuilder builder; |
| 22 |
| 23 LoopHandler(this.builder); |
| 24 |
| 25 /// Builds a graph for the given [loop] node. |
| 26 /// |
| 27 /// For while loops, [initialize] and [update] are null. |
| 28 /// The [condition] function must return a boolean result. |
| 29 /// None of the functions must leave anything on the stack. |
| 30 void handleLoop(T loop, void initialize(), HInstruction condition(), |
| 31 void update(), void body()) { |
| 32 // Generate: |
| 33 // <initializer> |
| 34 // loop-entry: |
| 35 // if (!<condition>) goto loop-exit; |
| 36 // <body> |
| 37 // <updates> |
| 38 // goto loop-entry; |
| 39 // loop-exit: |
| 40 |
| 41 builder.localsHandler.startLoop(getNode(loop)); |
| 42 |
| 43 // The initializer. |
| 44 SubExpression initializerGraph = null; |
| 45 HBasicBlock startBlock; |
| 46 if (initialize != null) { |
| 47 HBasicBlock initializerBlock = builder.openNewBlock(); |
| 48 startBlock = initializerBlock; |
| 49 initialize(); |
| 50 assert(!builder.isAborted()); |
| 51 initializerGraph = new SubExpression(initializerBlock, builder.current); |
| 52 } |
| 53 |
| 54 builder.loopDepth++; |
| 55 JumpHandler jumpHandler = beginLoopHeader(loop); |
| 56 HLoopInformation loopInfo = builder.current.loopInformation; |
| 57 HBasicBlock conditionBlock = builder.current; |
| 58 if (startBlock == null) startBlock = conditionBlock; |
| 59 |
| 60 HInstruction conditionInstruction = condition(); |
| 61 HBasicBlock conditionEndBlock = |
| 62 builder.close(new HLoopBranch(conditionInstruction)); |
| 63 SubExpression conditionExpression = |
| 64 new SubExpression(conditionBlock, conditionEndBlock); |
| 65 |
| 66 // Save the values of the local variables at the end of the condition |
| 67 // block. These are the values that will flow to the loop exit if the |
| 68 // condition fails. |
| 69 LocalsHandler savedLocals = new LocalsHandler.from(builder.localsHandler); |
| 70 |
| 71 // The body. |
| 72 HBasicBlock beginBodyBlock = builder.addNewBlock(); |
| 73 conditionEndBlock.addSuccessor(beginBodyBlock); |
| 74 builder.open(beginBodyBlock); |
| 75 |
| 76 builder.localsHandler.enterLoopBody(getNode(loop)); |
| 77 body(); |
| 78 |
| 79 SubGraph bodyGraph = new SubGraph(beginBodyBlock, builder.lastOpenedBlock); |
| 80 HBasicBlock bodyBlock = builder.current; |
| 81 if (builder.current != null) builder.close(new HGoto()); |
| 82 |
| 83 SubExpression updateGraph; |
| 84 |
| 85 bool loopIsDegenerate = !jumpHandler.hasAnyContinue() && bodyBlock == null; |
| 86 if (!loopIsDegenerate) { |
| 87 // Update. |
| 88 // We create an update block, even when we are in a while loop. There the |
| 89 // update block is the jump-target for continue statements. We could avoid |
| 90 // the creation if there is no continue, but for now we always create it. |
| 91 HBasicBlock updateBlock = builder.addNewBlock(); |
| 92 |
| 93 List<LocalsHandler> continueHandlers = <LocalsHandler>[]; |
| 94 jumpHandler |
| 95 .forEachContinue((HContinue instruction, LocalsHandler locals) { |
| 96 instruction.block.addSuccessor(updateBlock); |
| 97 continueHandlers.add(locals); |
| 98 }); |
| 99 |
| 100 if (bodyBlock != null) { |
| 101 continueHandlers.add(builder.localsHandler); |
| 102 bodyBlock.addSuccessor(updateBlock); |
| 103 } |
| 104 |
| 105 builder.open(updateBlock); |
| 106 builder.localsHandler = |
| 107 continueHandlers[0].mergeMultiple(continueHandlers, updateBlock); |
| 108 |
| 109 List<LabelDefinition> labels = jumpHandler.labels(); |
| 110 JumpTarget target = getTargetDefinition(loop); |
| 111 if (!labels.isEmpty) { |
| 112 beginBodyBlock.setBlockFlow( |
| 113 new HLabeledBlockInformation( |
| 114 new HSubGraphBlockInformation(bodyGraph), jumpHandler.labels(), |
| 115 isContinue: true), |
| 116 updateBlock); |
| 117 } else if (target != null && target.isContinueTarget) { |
| 118 beginBodyBlock.setBlockFlow( |
| 119 new HLabeledBlockInformation.implicit( |
| 120 new HSubGraphBlockInformation(bodyGraph), target, |
| 121 isContinue: true), |
| 122 updateBlock); |
| 123 } |
| 124 |
| 125 builder.localsHandler.enterLoopUpdates(getNode(loop)); |
| 126 |
| 127 update(); |
| 128 |
| 129 HBasicBlock updateEndBlock = builder.close(new HGoto()); |
| 130 // The back-edge completing the cycle. |
| 131 updateEndBlock.addSuccessor(conditionBlock); |
| 132 updateGraph = new SubExpression(updateBlock, updateEndBlock); |
| 133 |
| 134 // Avoid a critical edge from the condition to the loop-exit body. |
| 135 HBasicBlock conditionExitBlock = builder.addNewBlock(); |
| 136 builder.open(conditionExitBlock); |
| 137 builder.close(new HGoto()); |
| 138 conditionEndBlock.addSuccessor(conditionExitBlock); |
| 139 |
| 140 endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals); |
| 141 |
| 142 conditionBlock.postProcessLoopHeader(); |
| 143 HLoopBlockInformation info = new HLoopBlockInformation( |
| 144 loopKind(loop), |
| 145 builder.wrapExpressionGraph(initializerGraph), |
| 146 builder.wrapExpressionGraph(conditionExpression), |
| 147 builder.wrapStatementGraph(bodyGraph), |
| 148 builder.wrapExpressionGraph(updateGraph), |
| 149 conditionBlock.loopInformation.target, |
| 150 conditionBlock.loopInformation.labels, |
| 151 loopSourceInformation(loop)); |
| 152 |
| 153 startBlock.setBlockFlow(info, builder.current); |
| 154 loopInfo.loopBlockInformation = info; |
| 155 } else { |
| 156 // The body of the for/while loop always aborts, so there is no back edge. |
| 157 // We turn the code into: |
| 158 // if (condition) { |
| 159 // body; |
| 160 // } else { |
| 161 // // We always create an empty else block to avoid critical edges. |
| 162 // } |
| 163 // |
| 164 // If there is any break in the body, we attach a synthetic |
| 165 // label to the if. |
| 166 HBasicBlock elseBlock = builder.addNewBlock(); |
| 167 builder.open(elseBlock); |
| 168 builder.close(new HGoto()); |
| 169 // Pass the elseBlock as the branchBlock, because that's the block we go |
| 170 // to just before leaving the 'loop'. |
| 171 endLoop(conditionBlock, elseBlock, jumpHandler, savedLocals); |
| 172 |
| 173 SubGraph elseGraph = new SubGraph(elseBlock, elseBlock); |
| 174 // Remove the loop information attached to the header. |
| 175 conditionBlock.loopInformation = null; |
| 176 |
| 177 // Remove the [HLoopBranch] instruction and replace it with |
| 178 // [HIf]. |
| 179 HInstruction condition = conditionEndBlock.last.inputs[0]; |
| 180 conditionEndBlock.addAtExit(new HIf(condition)); |
| 181 conditionEndBlock.addSuccessor(elseBlock); |
| 182 conditionEndBlock.remove(conditionEndBlock.last); |
| 183 HIfBlockInformation info = new HIfBlockInformation( |
| 184 builder.wrapExpressionGraph(conditionExpression), |
| 185 builder.wrapStatementGraph(bodyGraph), |
| 186 builder.wrapStatementGraph(elseGraph)); |
| 187 |
| 188 conditionEndBlock.setBlockFlow(info, builder.current); |
| 189 HIf ifBlock = conditionEndBlock.last; |
| 190 ifBlock.blockInformation = conditionEndBlock.blockFlow; |
| 191 |
| 192 // If the body has any break, attach a synthesized label to the |
| 193 // if block. |
| 194 if (jumpHandler.hasAnyBreak()) { |
| 195 JumpTarget target = getTargetDefinition(loop); |
| 196 LabelDefinition label = target.addLabel(null, 'loop'); |
| 197 label.setBreakTarget(); |
| 198 SubGraph labelGraph = new SubGraph(conditionBlock, builder.current); |
| 199 HLabeledBlockInformation labelInfo = new HLabeledBlockInformation( |
| 200 new HSubGraphBlockInformation(labelGraph), |
| 201 <LabelDefinition>[label]); |
| 202 |
| 203 conditionBlock.setBlockFlow(labelInfo, builder.current); |
| 204 |
| 205 jumpHandler.forEachBreak((HBreak breakInstruction, _) { |
| 206 HBasicBlock block = breakInstruction.block; |
| 207 block.addAtExit(new HBreak.toLabel(label)); |
| 208 block.remove(breakInstruction); |
| 209 }); |
| 210 } |
| 211 } |
| 212 jumpHandler.close(); |
| 213 builder.loopDepth--; |
| 214 } |
| 215 |
| 216 /// Creates a new loop-header block. The previous [current] block |
| 217 /// is closed with an [HGoto] and replaced by the newly created block. |
| 218 /// Also notifies the locals handler that we're entering a loop. |
| 219 JumpHandler beginLoopHeader(T node) { |
| 220 assert(!builder.isAborted()); |
| 221 HBasicBlock previousBlock = builder.close(new HGoto()); |
| 222 |
| 223 JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: true); |
| 224 HBasicBlock loopEntry = builder.graph |
| 225 .addNewLoopHeaderBlock(jumpHandler.target, jumpHandler.labels()); |
| 226 previousBlock.addSuccessor(loopEntry); |
| 227 builder.open(loopEntry); |
| 228 |
| 229 builder.localsHandler.beginLoopHeader(loopEntry); |
| 230 return jumpHandler; |
| 231 } |
| 232 |
| 233 /// Ends the loop. |
| 234 /// |
| 235 /// It does this by: |
| 236 /// - creating a new block and adding it as successor to the [branchExitBlock] |
| 237 /// and any blocks that end in break. |
| 238 /// - opening the new block (setting as [current]). |
| 239 /// - notifying the locals handler that we're exiting a loop. |
| 240 /// |
| 241 /// [savedLocals] are the locals from the end of the loop condition. |
| 242 /// |
| 243 /// [branchExitBlock] is the exit (branching) block of the condition. |
| 244 /// Generally this is not the top of the loop, since this would lead to |
| 245 /// critical edges. It is null for degenerate do-while loops that have no back |
| 246 /// edge because they abort (throw/return/break in the body and have no |
| 247 /// continues). |
| 248 void endLoop(HBasicBlock loopEntry, HBasicBlock branchExitBlock, |
| 249 JumpHandler jumpHandler, LocalsHandler savedLocals) { |
| 250 HBasicBlock loopExitBlock = builder.addNewBlock(); |
| 251 |
| 252 List<LocalsHandler> breakHandlers = <LocalsHandler>[]; |
| 253 // Collect data for the successors and the phis at each break. |
| 254 jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) { |
| 255 breakInstruction.block.addSuccessor(loopExitBlock); |
| 256 breakHandlers.add(locals); |
| 257 }); |
| 258 |
| 259 // The exit block is a successor of the loop condition if it is reached. |
| 260 // We don't add the successor in the case of a while/for loop that aborts |
| 261 // because the caller of endLoop will be wiring up a special empty else |
| 262 // block instead. |
| 263 if (branchExitBlock != null) { |
| 264 branchExitBlock.addSuccessor(loopExitBlock); |
| 265 } |
| 266 // Update the phis at the loop entry with the current values of locals. |
| 267 builder.localsHandler.endLoop(loopEntry); |
| 268 |
| 269 // Start generating code for the exit block. |
| 270 builder.open(loopExitBlock); |
| 271 |
| 272 // Create a new localsHandler for the loopExitBlock with the correct phis. |
| 273 if (!breakHandlers.isEmpty) { |
| 274 if (branchExitBlock != null) { |
| 275 // Add the values of the locals at the end of the condition block to |
| 276 // the phis. These are the values that flow to the exit if the |
| 277 // condition fails. |
| 278 breakHandlers.add(savedLocals); |
| 279 } |
| 280 builder.localsHandler = |
| 281 savedLocals.mergeMultiple(breakHandlers, loopExitBlock); |
| 282 } else { |
| 283 builder.localsHandler = savedLocals; |
| 284 } |
| 285 } |
| 286 |
| 287 /// Returns the jump target defined by [node]. |
| 288 JumpTarget getTargetDefinition(T node); |
| 289 |
| 290 /// Returns the corresponding AST node for [node]. |
| 291 ast.Node getNode(T node); |
| 292 |
| 293 /// Determine what kind of loop [node] represents. |
| 294 /// |
| 295 /// The result is one of the kinds defined in [HLoopBlockInformation]. |
| 296 int loopKind(T node); |
| 297 |
| 298 /// Returns the source information for the loop [node]. |
| 299 SourceInformation loopSourceInformation(T node); |
| 300 |
| 301 /// Creates a [JumpHandler] for a statement. The node must be a jump |
| 302 /// target. If there are no breaks or continues targeting the statement, |
| 303 /// a special "null handler" is returned. |
| 304 /// |
| 305 /// [isLoopJump] is [:true:] when the jump handler is for a loop. This is used |
| 306 /// to distinguish the synthesized loop created for a switch statement with |
| 307 /// continue statements from simple switch statements. |
| 308 JumpHandler createJumpHandler(T node, {bool isLoopJump}); |
| 309 } |
| 310 |
| 311 /// A loop handler for the builder that just uses AST nodes directly. |
| 312 class SsaLoopHandler extends LoopHandler<ast.Node> { |
| 313 final SsaBuilder builder; |
| 314 |
| 315 SsaLoopHandler(SsaBuilder builder) |
| 316 : this.builder = builder, |
| 317 super(builder); |
| 318 |
| 319 @override |
| 320 JumpTarget getTargetDefinition(ast.Node node) { |
| 321 return builder.elements.getTargetDefinition(node); |
| 322 } |
| 323 |
| 324 @override |
| 325 ast.Node getNode(ast.Node node) => node; |
| 326 |
| 327 @override |
| 328 int loopKind(ast.Node node) => node.accept(const _SsaLoopTypeVisitor()); |
| 329 |
| 330 @override |
| 331 SourceInformation loopSourceInformation(ast.Node node) => |
| 332 builder.sourceInformationBuilder.buildLoop(node); |
| 333 |
| 334 @override |
| 335 JumpHandler createJumpHandler(ast.Node node, {bool isLoopJump}) => |
| 336 builder.createJumpHandler(node, isLoopJump: isLoopJump); |
| 337 } |
| 338 |
| 339 class _SsaLoopTypeVisitor extends ast.Visitor { |
| 340 const _SsaLoopTypeVisitor(); |
| 341 int visitNode(ast.Node node) => HLoopBlockInformation.NOT_A_LOOP; |
| 342 int visitWhile(ast.While node) => HLoopBlockInformation.WHILE_LOOP; |
| 343 int visitFor(ast.For node) => HLoopBlockInformation.FOR_LOOP; |
| 344 int visitDoWhile(ast.DoWhile node) => HLoopBlockInformation.DO_WHILE_LOOP; |
| 345 int visitAsyncForIn(ast.AsyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP; |
| 346 int visitSyncForIn(ast.SyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP; |
| 347 int visitSwitchStatement(ast.SwitchStatement node) => |
| 348 HLoopBlockInformation.SWITCH_CONTINUE_LOOP; |
| 349 } |
| 350 |
| 351 // TODO(het): Since kernel simplifies loop breaks and continues, we should |
| 352 // rewrite the loop handler from scratch to account for the simplified structure |
| 353 class KernelLoopHandler extends LoopHandler<ir.Node> { |
| 354 final KernelSsaBuilder builder; |
| 355 |
| 356 KernelAstAdapter get astAdapter => builder.astAdapter; |
| 357 |
| 358 KernelLoopHandler(KernelSsaBuilder builder) |
| 359 : this.builder = builder, |
| 360 super(builder); |
| 361 |
| 362 @override |
| 363 JumpHandler createJumpHandler(ir.Node node, {bool isLoopJump}) { |
| 364 JumpTarget element = getTargetDefinition(node); |
| 365 if (element == null || !identical(element.statement, node)) { |
| 366 // No breaks or continues to this node. |
| 367 return new NullJumpHandler(builder.compiler.reporter); |
| 368 } |
| 369 if (isLoopJump && node is ast.SwitchStatement) { |
| 370 // Create a special jump handler for loops created for switch statements |
| 371 // with continue statements. |
| 372 return new SwitchCaseJumpHandler(builder, element, getNode(node)); |
| 373 } |
| 374 return new JumpHandler(builder, element); |
| 375 } |
| 376 |
| 377 @override |
| 378 ast.Node getNode(ir.Node node) => astAdapter.getNode(node); |
| 379 |
| 380 @override |
| 381 JumpTarget getTargetDefinition(ir.Node node) => |
| 382 astAdapter.getTargetDefinition(node); |
| 383 |
| 384 @override |
| 385 int loopKind(ir.Node node) => node.accept(new _KernelLoopTypeVisitor()); |
| 386 |
| 387 // TODO(het): return the actual source information |
| 388 @override |
| 389 SourceInformation loopSourceInformation(ir.Node node) => null; |
| 390 } |
| 391 |
| 392 class _KernelLoopTypeVisitor extends ir.Visitor<int> { |
| 393 @override |
| 394 int defaultNode(ir.Node node) => HLoopBlockInformation.NOT_A_LOOP; |
| 395 |
| 396 @override |
| 397 int visitWhileStatement(ir.WhileStatement node) => |
| 398 HLoopBlockInformation.WHILE_LOOP; |
| 399 |
| 400 @override |
| 401 int visitForStatement(ir.ForStatement node) => HLoopBlockInformation.FOR_LOOP; |
| 402 |
| 403 @override |
| 404 int visitDoStatement(ir.DoStatement node) => |
| 405 HLoopBlockInformation.DO_WHILE_LOOP; |
| 406 |
| 407 @override |
| 408 int visitForInStatement(ir.ForInStatement node) => |
| 409 HLoopBlockInformation.FOR_IN_LOOP; |
| 410 |
| 411 @override |
| 412 int visitSwitchStatement(ir.SwitchStatement node) => |
| 413 HLoopBlockInformation.SWITCH_CONTINUE_LOOP; |
| 414 } |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2360673003:
kernel->ssa: Implement for-loops and while-loops (Closed)
