pkg/compiler/lib/src/ssa/builder.dart - Issue 2301293002: kernel -> ssa: implement if-statements

Unified Diff: pkg/compiler/lib/src/ssa/builder.dart

Issue 2301293002: kernel -> ssa: implement if-statements (Closed)

Patch Set: Created 4 years, 3 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Index: pkg/compiler/lib/src/ssa/builder.dart

diff --git a/pkg/compiler/lib/src/ssa/builder.dart b/pkg/compiler/lib/src/ssa/builder.dart

index c9ef7eeb36a8334be1988372ff04a6645a278c72..a5216b263946051f88fd851b264e95851d397826 100644

--- a/pkg/compiler/lib/src/ssa/builder.dart

+++ b/pkg/compiler/lib/src/ssa/builder.dart

@@ -4,6 +4,7 @@

import 'dart:collection';

+import 'package:compiler/src/ssa/ssa_branch_builder.dart';

import 'package:js_runtime/shared/embedded_names.dart';

import '../closure.dart';

@@ -411,8 +412,6 @@ class SsaBuilder extends ast.Visitor

final List<Element> sourceElementStack = <Element>[];

- LocalsHandler localsHandler;

HInstruction rethrowableException;

Map<JumpTarget, JumpHandler> jumpTargets = <JumpTarget, JumpHandler>{};

@@ -1907,7 +1906,8 @@ class SsaBuilder extends ast.Visitor

push(attachPosition(instruction, node));

}

- HInstruction popBoolified() {

+ @override

+ HBoolify popBoolified() {

HInstruction value = pop();

if (_checkOrTrustTypes) {

return potentiallyCheckOrTrustType(value, compiler.coreTypes.boolType,

@@ -2537,31 +2537,75 @@ class SsaBuilder extends ast.Visitor

void visitThen(),

void visitElse(),

SourceInformation sourceInformation}) {

- SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, diagnosticNode);

+ SsaBranchBuilder branchBuilder =

+ new SsaBranchBuilder(this, compiler, diagnosticNode);

branchBuilder.handleIf(visitCondition, visitThen, visitElse,

sourceInformation: sourceInformation);

}

@override

void visitIfNull(ast.Send node, ast.Node left, ast.Node right, _) {

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleIfNull(() => visit(left), () => visit(right));

}

@override

void visitLogicalAnd(ast.Send node, ast.Node left, ast.Node right, _) {

- SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, node);

- branchBuilder.handleLogicalAndOrWithLeftNode(left, () {

- visit(right);

- }, isAnd: true);

+ SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, compiler, node);

+ // This method is similar to [SsaBranchBuilder.handleLogicalAndOr] but

+ // optimizes the case where left is a logical "and".

+ //

+ // For example (x && y) && z is transformed into x && (y && z):

+ // t0 = boolify(x);

+ // if (t0) {

+ // t1 = boolify(y);

+ // if (t1) {

+ // t2 = boolify(z);

+ // }

+ // t3 = phi(t2, false);

+ // }

+ // result = phi(t3, false);

+ void handleLogicalAndWithLeftNode(ast.Node left, void visitRight()) {

+ ast.Send send = left.asSend();

+ if (send != null && send.isLogicalAnd) {

+ ast.Node newLeft = send.receiver;

+ Link<ast.Node> link = send.argumentsNode.nodes;

+ assert(link.tail.isEmpty);

+ ast.Node middle = link.head;

+ handleLogicalAndWithLeftNode(

+ newLeft, () => handleLogicalAndWithLeftNode(middle, visitRight));

+ } else {

+ branchBuilder.handleLogicalAndOr(() => visit(left), visitRight,

+ isAnd: true);

+ }

+ handleLogicalAndWithLeftNode(left, () => visit(right));

}

@override

void visitLogicalOr(ast.Send node, ast.Node left, ast.Node right, _) {

- SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, node);

- branchBuilder.handleLogicalAndOrWithLeftNode(left, () {

- visit(right);

- }, isAnd: false);

+ SsaBranchBuilder branchBuilder = new SsaBranchBuilder(this, compiler, node);

+ // This method is similar to [SsaBranchBuilder.handleLogicalAndOr] but

+ // optimizes the case where left is a logical "or".

+ void handleLogicalOrWithLeftNode(ast.Node left, void visitRight()) {

Siggi Cherem (dart-lang) 2016/09/01 23:51:21 what if we keep the handleLogicalAndOrWithLeftNode

Harry Terkelsen 2016/09/02 17:52:27 Done.

+ ast.Send send = left.asSend();

+ if (send != null && send.isLogicalOr) {

+ ast.Node newLeft = send.receiver;

+ Link<ast.Node> link = send.argumentsNode.nodes;

+ assert(link.tail.isEmpty);

+ ast.Node middle = link.head;

+ handleLogicalOrWithLeftNode(

+ newLeft, () => handleLogicalOrWithLeftNode(middle, visitRight));

+ } else {

+ branchBuilder.handleLogicalAndOr(() => visit(left), visitRight,

+ isAnd: true);

Siggi Cherem (dart-lang) 2016/09/01 23:51:21 shouldn't this be "false"?

Harry Terkelsen 2016/09/02 17:52:27 oops! good catch

+ }

+ handleLogicalOrWithLeftNode(left, () => visit(right));

}

@override

@@ -2819,7 +2863,7 @@ class SsaBuilder extends ast.Visitor

// we will be able to later compress it as:

// t1 || t1.x

HInstruction expression;

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleConditional(

() {

expression = visitAndPop(receiver);

@@ -2835,7 +2879,7 @@ class SsaBuilder extends ast.Visitor

});

}

- /// Pushes a boolean checking [expression] against null.

+ @override

pushCheckNull(HInstruction expression) {

push(new HIdentity(

expression, graph.addConstantNull(compiler), null, backend.boolType));

@@ -3202,7 +3246,7 @@ class SsaBuilder extends ast.Visitor

ast.NodeList arguments, Selector selector, _) {

/// Desugar `exp?.m()` to `(t1 = exp) == null ? t1 : t1.m()`

HInstruction receiver;

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleConditional(() {

receiver = generateInstanceSendReceiver(node);

pushCheckNull(receiver);

@@ -5008,7 +5052,7 @@ class SsaBuilder extends ast.Visitor

}

if (node.isIfNullAssignment) {

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleIfNull(() => stack.add(getterInstruction), () {

addDynamicSendArgumentsToList(node, setterInputs);

generateSuperSendSet();

@@ -5328,7 +5372,7 @@ class SsaBuilder extends ast.Visitor

// if (t1 == null)

// t1 = x[i] = e;

// result = t1

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleIfNull(() => stack.add(getterInstruction), () {

visit(arguments.head);

HInstruction value = pop();

@@ -5376,7 +5420,7 @@ class SsaBuilder extends ast.Visitor

// else

// result = e.x = e2

HInstruction receiverInstruction;

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleConditional(

() {

receiverInstruction = generateInstanceSendReceiver(node);

@@ -5549,7 +5593,8 @@ class SsaBuilder extends ast.Visitor

receiver);

HInstruction getterInstruction = pop();

if (node.isIfNullAssignment) {

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher =

+ new SsaBranchBuilder(this, compiler, node);

brancher.handleIfNull(() => stack.add(getterInstruction), () {

visit(node.arguments.head);

generateInstanceSetterWithCompiledReceiver(node, receiver, pop());

@@ -5570,7 +5615,7 @@ class SsaBuilder extends ast.Visitor

// t1 = e

// t1 == null ? t1 : (t1.x = t1.x op e2);

HInstruction receiver;

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleConditional(() {

receiver = generateInstanceSendReceiver(node);

pushCheckNull(receiver);

@@ -5596,7 +5641,7 @@ class SsaBuilder extends ast.Visitor

}

HInstruction getterInstruction = pop();

if (node.isIfNullAssignment) {

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleIfNull(() => stack.add(getterInstruction), () {

visit(node.arguments.head);

generateNonInstanceSetter(node, element, pop());

@@ -6006,7 +6051,7 @@ class SsaBuilder extends ast.Visitor

}

visitConditional(ast.Conditional node) {

- SsaBranchBuilder brancher = new SsaBranchBuilder(this, node);

+ SsaBranchBuilder brancher = new SsaBranchBuilder(this, compiler, node);

brancher.handleConditional(() => visit(node.condition),

() => visit(node.thenExpression), () => visit(node.elseExpression));

}

@@ -7478,252 +7523,6 @@ class AstInliningState extends InliningState {

: super(function);

}

-class SsaBranch {

- final SsaBranchBuilder branchBuilder;

- final HBasicBlock block;

- LocalsHandler startLocals;

- LocalsHandler exitLocals;

- SubGraph graph;

- SsaBranch(this.branchBuilder) : block = new HBasicBlock();

-class SsaBranchBuilder {

- final SsaBuilder builder;

- final ast.Node diagnosticNode;

- SsaBranchBuilder(this.builder, [this.diagnosticNode]);

- Compiler get compiler => builder.compiler;

- void checkNotAborted() {

- if (builder.isAborted()) {

- compiler.unimplemented(diagnosticNode, "aborted control flow");

- }

- void buildCondition(

- void visitCondition(),

- SsaBranch conditionBranch,

- SsaBranch thenBranch,

- SsaBranch elseBranch,

- SourceInformation sourceInformation) {

- startBranch(conditionBranch);

- visitCondition();

- checkNotAborted();

- assert(identical(builder.current, builder.lastOpenedBlock));

- HInstruction conditionValue = builder.popBoolified();

- HIf branch = new HIf(conditionValue)..sourceInformation = sourceInformation;

- HBasicBlock conditionExitBlock = builder.current;

- builder.close(branch);

- conditionBranch.exitLocals = builder.localsHandler;

- conditionExitBlock.addSuccessor(thenBranch.block);

- conditionExitBlock.addSuccessor(elseBranch.block);

- bool conditionBranchLocalsCanBeReused =

- mergeLocals(conditionBranch, thenBranch, mayReuseFromLocals: true);

- mergeLocals(conditionBranch, elseBranch,

- mayReuseFromLocals: conditionBranchLocalsCanBeReused);

- conditionBranch.graph =

- new SubExpression(conditionBranch.block, conditionExitBlock);

- }

- /**

- * Returns true if the locals of the [fromBranch] may be reused. A [:true:]

- * return value implies that [mayReuseFromLocals] was set to [:true:].

- */

- bool mergeLocals(SsaBranch fromBranch, SsaBranch toBranch,

- {bool mayReuseFromLocals}) {

- LocalsHandler fromLocals = fromBranch.exitLocals;

- if (toBranch.startLocals == null) {

- if (mayReuseFromLocals) {

- toBranch.startLocals = fromLocals;

- return false;

- } else {

- toBranch.startLocals = new LocalsHandler.from(fromLocals);

- return true;

- }

- } else {

- toBranch.startLocals.mergeWith(fromLocals, toBranch.block);

- return true;

- }

- void startBranch(SsaBranch branch) {

- builder.graph.addBlock(branch.block);

- builder.localsHandler = branch.startLocals;

- builder.open(branch.block);

- }

- HInstruction buildBranch(SsaBranch branch, void visitBranch(),

- SsaBranch joinBranch, bool isExpression) {

- startBranch(branch);

- visitBranch();

- branch.graph = new SubGraph(branch.block, builder.lastOpenedBlock);

- branch.exitLocals = builder.localsHandler;

- if (!builder.isAborted()) {

- builder.goto(builder.current, joinBranch.block);

- mergeLocals(branch, joinBranch, mayReuseFromLocals: true);

- }

- if (isExpression) {

- checkNotAborted();

- return builder.pop();

- }

- return null;

- }

- handleIf(void visitCondition(), void visitThen(), void visitElse(),

- {SourceInformation sourceInformation}) {

- if (visitElse == null) {

- // Make sure to have an else part to avoid a critical edge. A

- // critical edge is an edge that connects a block with multiple

- // successors to a block with multiple predecessors. We avoid

- // such edges because they prevent inserting copies during code

- // generation of phi instructions.

- visitElse = () {};

- }

- _handleDiamondBranch(visitCondition, visitThen, visitElse,

- isExpression: false, sourceInformation: sourceInformation);

- }

- handleConditional(void visitCondition(), void visitThen(), void visitElse()) {

- assert(visitElse != null);

- _handleDiamondBranch(visitCondition, visitThen, visitElse,

- isExpression: true);

- }

- handleIfNull(void left(), void right()) {

- // x ?? y is transformed into: x == null ? y : x

- HInstruction leftExpression;

- handleConditional(() {

- left();

- leftExpression = builder.pop();

- builder.pushCheckNull(leftExpression);

- }, right, () => builder.stack.add(leftExpression));

- }

- void handleLogicalAndOr(void left(), void right(), {bool isAnd}) {

- // x && y is transformed into:

- // t0 = boolify(x);

- // if (t0) {

- // t1 = boolify(y);

- // }

- // result = phi(t1, false);

- //

- // x || y is transformed into:

- // t0 = boolify(x);

- // if (not(t0)) {

- // t1 = boolify(y);

- // }

- // result = phi(t1, true);

- HInstruction boolifiedLeft;

- HInstruction boolifiedRight;

- void visitCondition() {

- left();

- boolifiedLeft = builder.popBoolified();

- builder.stack.add(boolifiedLeft);

- if (!isAnd) {

- builder.push(new HNot(builder.pop(), builder.backend.boolType));

- }

- void visitThen() {

- right();

- boolifiedRight = builder.popBoolified();

- }

- handleIf(visitCondition, visitThen, null);

- HConstant notIsAnd =

- builder.graph.addConstantBool(!isAnd, builder.compiler);

- JavaScriptBackend backend = builder.backend;

- HPhi result = new HPhi.manyInputs(

- null, <HInstruction>[boolifiedRight, notIsAnd], backend.dynamicType);

- builder.current.addPhi(result);

- builder.stack.add(result);

- }

- void handleLogicalAndOrWithLeftNode(ast.Node left, void visitRight(),

- {bool isAnd}) {

- // This method is similar to [handleLogicalAndOr] but optimizes the case

- // where left is a logical "and" or logical "or".

- //

- // For example (x && y) && z is transformed into x && (y && z):

- // t0 = boolify(x);

- // if (t0) {

- // t1 = boolify(y);

- // if (t1) {

- // t2 = boolify(z);

- // }

- // t3 = phi(t2, false);

- // }

- // result = phi(t3, false);

- ast.Send send = left.asSend();

- if (send != null && (isAnd ? send.isLogicalAnd : send.isLogicalOr)) {

- ast.Node newLeft = send.receiver;

- Link<ast.Node> link = send.argumentsNode.nodes;

- assert(link.tail.isEmpty);

- ast.Node middle = link.head;

- handleLogicalAndOrWithLeftNode(

- newLeft,

- () =>

- handleLogicalAndOrWithLeftNode(middle, visitRight, isAnd: isAnd),

- isAnd: isAnd);

- } else {

- handleLogicalAndOr(() => builder.visit(left), visitRight, isAnd: isAnd);

- }

- void _handleDiamondBranch(

- void visitCondition(), void visitThen(), void visitElse(),

- {bool isExpression, SourceInformation sourceInformation}) {

- SsaBranch conditionBranch = new SsaBranch(this);

- SsaBranch thenBranch = new SsaBranch(this);

- SsaBranch elseBranch = new SsaBranch(this);

- SsaBranch joinBranch = new SsaBranch(this);

- conditionBranch.startLocals = builder.localsHandler;

- builder.goto(builder.current, conditionBranch.block);

- buildCondition(visitCondition, conditionBranch, thenBranch, elseBranch,

- sourceInformation);

- HInstruction thenValue =

- buildBranch(thenBranch, visitThen, joinBranch, isExpression);

- HInstruction elseValue =

- buildBranch(elseBranch, visitElse, joinBranch, isExpression);

- if (isExpression) {

- assert(thenValue != null && elseValue != null);

- JavaScriptBackend backend = builder.backend;

- HPhi phi = new HPhi.manyInputs(

- null, <HInstruction>[thenValue, elseValue], backend.dynamicType);

- joinBranch.block.addPhi(phi);

- builder.stack.add(phi);

- }

- HBasicBlock joinBlock;

- // If at least one branch did not abort, open the joinBranch.

- if (!joinBranch.block.predecessors.isEmpty) {

- startBranch(joinBranch);

- joinBlock = joinBranch.block;

- }

- HIfBlockInformation info = new HIfBlockInformation(

- new HSubExpressionBlockInformation(conditionBranch.graph),

- new HSubGraphBlockInformation(thenBranch.graph),

- new HSubGraphBlockInformation(elseBranch.graph));

- HBasicBlock conditionStartBlock = conditionBranch.block;

- conditionStartBlock.setBlockFlow(info, joinBlock);

- SubGraph conditionGraph = conditionBranch.graph;

- HIf branch = conditionGraph.end.last;

- assert(branch is HIf);

- branch.blockInformation = conditionStartBlock.blockFlow;

- }

class TypeBuilder implements DartTypeVisitor<dynamic, SsaBuilder> {

final ClassWorld classWorld;

« no previous file with comments | « no previous file | pkg/compiler/lib/src/ssa/builder_kernel.dart » ('j') | pkg/compiler/lib/src/ssa/builder_kernel.dart » ('J')