blob: 6e7ad540b2594492c0e9f7f5327ea04623d86d52 [file] [log] [blame]
// Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
import 'package:kernel/ast.dart' as ir;
import '../elements/elements.dart' show JumpTarget, LabelDefinition;
import '../io/source_information.dart';
import '../tree/tree.dart' as ast;
import 'builder.dart';
import 'builder_kernel.dart';
import 'graph_builder.dart';
import 'jump_handler.dart';
import 'kernel_ast_adapter.dart';
import 'locals_handler.dart';
import 'nodes.dart';
/// Builds the SSA graph for loop nodes.
abstract class LoopHandler<T> {
final GraphBuilder builder;
/// Builds a graph for the given [loop] node.
/// For while loops, [initialize] and [update] are null.
/// The [condition] function must return a boolean result.
/// None of the functions must leave anything on the stack.
void handleLoop(T loop, void initialize(), HInstruction condition(),
void update(), void body()) {
// Generate:
// <initializer>
// loop-entry:
// if (!<condition>) goto loop-exit;
// <body>
// <updates>
// goto loop-entry;
// loop-exit:
// The initializer.
SubExpression initializerGraph = null;
HBasicBlock startBlock;
if (initialize != null) {
HBasicBlock initializerBlock = builder.openNewBlock();
startBlock = initializerBlock;
initializerGraph = new SubExpression(initializerBlock, builder.current);
JumpHandler jumpHandler = beginLoopHeader(loop);
HLoopInformation loopInfo = builder.current.loopInformation;
HBasicBlock conditionBlock = builder.current;
if (startBlock == null) startBlock = conditionBlock;
HInstruction conditionInstruction = condition();
HBasicBlock conditionEndBlock =
builder.close(new HLoopBranch(conditionInstruction));
SubExpression conditionExpression =
new SubExpression(conditionBlock, conditionEndBlock);
// Save the values of the local variables at the end of the condition
// block. These are the values that will flow to the loop exit if the
// condition fails.
LocalsHandler savedLocals = new LocalsHandler.from(builder.localsHandler);
// The body.
HBasicBlock beginBodyBlock = builder.addNewBlock();
SubGraph bodyGraph = new SubGraph(beginBodyBlock, builder.lastOpenedBlock);
HBasicBlock bodyBlock = builder.current;
if (builder.current != null) builder.close(new HGoto());
SubExpression updateGraph;
bool loopIsDegenerate = !jumpHandler.hasAnyContinue() && bodyBlock == null;
if (!loopIsDegenerate) {
// Update.
// We create an update block, even when we are in a while loop. There the
// update block is the jump-target for continue statements. We could avoid
// the creation if there is no continue, but for now we always create it.
HBasicBlock updateBlock = builder.addNewBlock();
List<LocalsHandler> continueHandlers = <LocalsHandler>[];
.forEachContinue((HContinue instruction, LocalsHandler locals) {
if (bodyBlock != null) {
builder.localsHandler =
continueHandlers[0].mergeMultiple(continueHandlers, updateBlock);
List<LabelDefinition> labels = jumpHandler.labels;
JumpTarget target = getTargetDefinition(loop);
if (labels.isNotEmpty) {
new HLabeledBlockInformation(
new HSubGraphBlockInformation(bodyGraph), jumpHandler.labels,
isContinue: true),
} else if (target != null && target.isContinueTarget) {
new HLabeledBlockInformation.implicit(
new HSubGraphBlockInformation(bodyGraph), target,
isContinue: true),
HBasicBlock updateEndBlock = builder.close(new HGoto());
// The back-edge completing the cycle.
updateGraph = new SubExpression(updateBlock, updateEndBlock);
// Avoid a critical edge from the condition to the loop-exit body.
HBasicBlock conditionExitBlock = builder.addNewBlock();;
builder.close(new HGoto());
endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
HLoopBlockInformation info = new HLoopBlockInformation(
startBlock.setBlockFlow(info, builder.current);
loopInfo.loopBlockInformation = info;
} else {
// The body of the for/while loop always aborts, so there is no back edge.
// We turn the code into:
// if (condition) {
// body;
// } else {
// // We always create an empty else block to avoid critical edges.
// }
// If there is any break in the body, we attach a synthetic
// label to the if.
HBasicBlock elseBlock = builder.addNewBlock();;
builder.close(new HGoto());
// Pass the elseBlock as the branchBlock, because that's the block we go
// to just before leaving the 'loop'.
endLoop(conditionBlock, elseBlock, jumpHandler, savedLocals);
SubGraph elseGraph = new SubGraph(elseBlock, elseBlock);
// Remove the loop information attached to the header.
conditionBlock.loopInformation = null;
// Remove the [HLoopBranch] instruction and replace it with
// [HIf].
HInstruction condition = conditionEndBlock.last.inputs[0];
conditionEndBlock.addAtExit(new HIf(condition));
HIfBlockInformation info = new HIfBlockInformation(
conditionEndBlock.setBlockFlow(info, builder.current);
HIf ifBlock = conditionEndBlock.last;
ifBlock.blockInformation = conditionEndBlock.blockFlow;
// If the body has any break, attach a synthesized label to the
// if block.
if (jumpHandler.hasAnyBreak()) {
JumpTarget target = getTargetDefinition(loop);
LabelDefinition label = target.addLabel(null, 'loop');
SubGraph labelGraph = new SubGraph(conditionBlock, builder.current);
HLabeledBlockInformation labelInfo = new HLabeledBlockInformation(
new HSubGraphBlockInformation(labelGraph),
conditionBlock.setBlockFlow(labelInfo, builder.current);
jumpHandler.forEachBreak((HBreak breakInstruction, _) {
HBasicBlock block = breakInstruction.block;
block.addAtExit(new HBreak.toLabel(label));
/// Creates a new loop-header block. The previous [current] block
/// is closed with an [HGoto] and replaced by the newly created block.
/// Also notifies the locals handler that we're entering a loop.
JumpHandler beginLoopHeader(T node) {
HBasicBlock previousBlock = builder.close(new HGoto());
JumpHandler jumpHandler = createJumpHandler(node, isLoopJump: true);
HBasicBlock loopEntry = builder.graph
.addNewLoopHeaderBlock(, jumpHandler.labels);
return jumpHandler;
/// Ends the loop.
/// It does this by:
/// - creating a new block and adding it as successor to the [branchExitBlock]
/// and any blocks that end in break.
/// - opening the new block (setting as [current]).
/// - notifying the locals handler that we're exiting a loop.
/// [savedLocals] are the locals from the end of the loop condition.
/// [branchExitBlock] is the exit (branching) block of the condition.
/// Generally this is not the top of the loop, since this would lead to
/// critical edges. It is null for degenerate do-while loops that have no back
/// edge because they abort (throw/return/break in the body and have no
/// continues).
void endLoop(HBasicBlock loopEntry, HBasicBlock branchExitBlock,
JumpHandler jumpHandler, LocalsHandler savedLocals) {
HBasicBlock loopExitBlock = builder.addNewBlock();
List<LocalsHandler> breakHandlers = <LocalsHandler>[];
// Collect data for the successors and the phis at each break.
jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
// The exit block is a successor of the loop condition if it is reached.
// We don't add the successor in the case of a while/for loop that aborts
// because the caller of endLoop will be wiring up a special empty else
// block instead.
if (branchExitBlock != null) {
// Update the phis at the loop entry with the current values of locals.
// Start generating code for the exit block.;
// Create a new localsHandler for the loopExitBlock with the correct phis.
if (!breakHandlers.isEmpty) {
if (branchExitBlock != null) {
// Add the values of the locals at the end of the condition block to
// the phis. These are the values that flow to the exit if the
// condition fails.
builder.localsHandler =
savedLocals.mergeMultiple(breakHandlers, loopExitBlock);
} else {
builder.localsHandler = savedLocals;
/// Returns the jump target defined by [node].
JumpTarget getTargetDefinition(T node);
/// Returns the corresponding AST node for [node].
ast.Node getNode(T node);
/// Determine what kind of loop [node] represents.
/// The result is one of the kinds defined in [HLoopBlockInformation].
int loopKind(T node);
/// Returns the source information for the loop [node].
SourceInformation loopSourceInformation(T node);
/// Creates a [JumpHandler] for a statement. The node must be a jump
/// target. If there are no breaks or continues targeting the statement,
/// a special "null handler" is returned.
/// [isLoopJump] is [:true:] when the jump handler is for a loop. This is used
/// to distinguish the synthesized loop created for a switch statement with
/// continue statements from simple switch statements.
JumpHandler createJumpHandler(T node, {bool isLoopJump});
/// A loop handler for the builder that just uses AST nodes directly.
class SsaLoopHandler extends LoopHandler<ast.Node> {
final SsaBuilder builder;
SsaLoopHandler(SsaBuilder builder)
: this.builder = builder,
JumpTarget getTargetDefinition(ast.Node node) {
return builder.elements.getTargetDefinition(node);
ast.Node getNode(ast.Node node) => node;
int loopKind(ast.Node node) => node.accept(const _SsaLoopTypeVisitor());
SourceInformation loopSourceInformation(ast.Node node) =>
JumpHandler createJumpHandler(ast.Node node, {bool isLoopJump}) =>
builder.createJumpHandler(node, isLoopJump: isLoopJump);
class _SsaLoopTypeVisitor extends ast.Visitor {
const _SsaLoopTypeVisitor();
int visitNode(ast.Node node) => HLoopBlockInformation.NOT_A_LOOP;
int visitWhile(ast.While node) => HLoopBlockInformation.WHILE_LOOP;
int visitFor(ast.For node) => HLoopBlockInformation.FOR_LOOP;
int visitDoWhile(ast.DoWhile node) => HLoopBlockInformation.DO_WHILE_LOOP;
int visitAsyncForIn(ast.AsyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP;
int visitSyncForIn(ast.SyncForIn node) => HLoopBlockInformation.FOR_IN_LOOP;
int visitSwitchStatement(ast.SwitchStatement node) =>
// TODO(het): Since kernel simplifies loop breaks and continues, we should
// rewrite the loop handler from scratch to account for the simplified structure
class KernelLoopHandler extends LoopHandler<ir.TreeNode> {
final KernelSsaBuilder builder;
KernelAstAdapter get astAdapter => builder.astAdapter;
KernelLoopHandler(KernelSsaBuilder builder)
: this.builder = builder,
JumpHandler createJumpHandler(ir.TreeNode node, {bool isLoopJump}) =>
builder.createJumpHandler(node, isLoopJump: isLoopJump);
ast.Node getNode(ir.TreeNode node) => astAdapter.getNode(node);
JumpTarget getTargetDefinition(ir.TreeNode node) =>
int loopKind(ir.TreeNode node) => node.accept(new _KernelLoopTypeVisitor());
// TODO(het): return the actual source information
SourceInformation loopSourceInformation(ir.TreeNode node) => null;
class _KernelLoopTypeVisitor extends ir.Visitor<int> {
int defaultNode(ir.Node node) => HLoopBlockInformation.NOT_A_LOOP;
int visitWhileStatement(ir.WhileStatement node) =>
int visitForStatement(ir.ForStatement node) => HLoopBlockInformation.FOR_LOOP;
int visitDoStatement(ir.DoStatement node) =>
int visitForInStatement(ir.ForInStatement node) =>
int visitSwitchStatement(ir.SwitchStatement node) =>