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 '../compiler.dart'; |
| 6 import '../io/source_information.dart'; |
| 7 import '../js_backend/js_backend.dart'; |
| 8 import '../tree/tree.dart' as ast; |
| 9 |
| 10 import 'graph_builder.dart'; |
| 11 import 'locals_handler.dart'; |
| 12 import 'nodes.dart'; |
| 13 |
| 14 class SsaBranch { |
| 15 final SsaBranchBuilder branchBuilder; |
| 16 final HBasicBlock block; |
| 17 LocalsHandler startLocals; |
| 18 LocalsHandler exitLocals; |
| 19 SubGraph graph; |
| 20 |
| 21 SsaBranch(this.branchBuilder) : block = new HBasicBlock(); |
| 22 } |
| 23 |
| 24 class SsaBranchBuilder { |
| 25 final GraphBuilder builder; |
| 26 final Compiler compiler; |
| 27 final ast.Node diagnosticNode; |
| 28 |
| 29 SsaBranchBuilder(this.builder, this.compiler, [this.diagnosticNode]); |
| 30 |
| 31 void checkNotAborted() { |
| 32 if (builder.isAborted()) { |
| 33 compiler.unimplemented(diagnosticNode, "aborted control flow"); |
| 34 } |
| 35 } |
| 36 |
| 37 void buildCondition( |
| 38 void visitCondition(), |
| 39 SsaBranch conditionBranch, |
| 40 SsaBranch thenBranch, |
| 41 SsaBranch elseBranch, |
| 42 SourceInformation sourceInformation) { |
| 43 startBranch(conditionBranch); |
| 44 visitCondition(); |
| 45 checkNotAborted(); |
| 46 assert(identical(builder.current, builder.lastOpenedBlock)); |
| 47 HInstruction conditionValue = builder.popBoolified(); |
| 48 HIf branch = new HIf(conditionValue)..sourceInformation = sourceInformation; |
| 49 HBasicBlock conditionExitBlock = builder.current; |
| 50 builder.close(branch); |
| 51 conditionBranch.exitLocals = builder.localsHandler; |
| 52 conditionExitBlock.addSuccessor(thenBranch.block); |
| 53 conditionExitBlock.addSuccessor(elseBranch.block); |
| 54 bool conditionBranchLocalsCanBeReused = |
| 55 mergeLocals(conditionBranch, thenBranch, mayReuseFromLocals: true); |
| 56 mergeLocals(conditionBranch, elseBranch, |
| 57 mayReuseFromLocals: conditionBranchLocalsCanBeReused); |
| 58 |
| 59 conditionBranch.graph = |
| 60 new SubExpression(conditionBranch.block, conditionExitBlock); |
| 61 } |
| 62 |
| 63 /** |
| 64 * Returns true if the locals of the [fromBranch] may be reused. A [:true:] |
| 65 * return value implies that [mayReuseFromLocals] was set to [:true:]. |
| 66 */ |
| 67 bool mergeLocals(SsaBranch fromBranch, SsaBranch toBranch, |
| 68 {bool mayReuseFromLocals}) { |
| 69 LocalsHandler fromLocals = fromBranch.exitLocals; |
| 70 if (toBranch.startLocals == null) { |
| 71 if (mayReuseFromLocals) { |
| 72 toBranch.startLocals = fromLocals; |
| 73 return false; |
| 74 } else { |
| 75 toBranch.startLocals = new LocalsHandler.from(fromLocals); |
| 76 return true; |
| 77 } |
| 78 } else { |
| 79 toBranch.startLocals.mergeWith(fromLocals, toBranch.block); |
| 80 return true; |
| 81 } |
| 82 } |
| 83 |
| 84 void startBranch(SsaBranch branch) { |
| 85 builder.graph.addBlock(branch.block); |
| 86 builder.localsHandler = branch.startLocals; |
| 87 builder.open(branch.block); |
| 88 } |
| 89 |
| 90 HInstruction buildBranch(SsaBranch branch, void visitBranch(), |
| 91 SsaBranch joinBranch, bool isExpression) { |
| 92 startBranch(branch); |
| 93 visitBranch(); |
| 94 branch.graph = new SubGraph(branch.block, builder.lastOpenedBlock); |
| 95 branch.exitLocals = builder.localsHandler; |
| 96 if (!builder.isAborted()) { |
| 97 builder.goto(builder.current, joinBranch.block); |
| 98 mergeLocals(branch, joinBranch, mayReuseFromLocals: true); |
| 99 } |
| 100 if (isExpression) { |
| 101 checkNotAborted(); |
| 102 return builder.pop(); |
| 103 } |
| 104 return null; |
| 105 } |
| 106 |
| 107 handleIf(void visitCondition(), void visitThen(), void visitElse(), |
| 108 {SourceInformation sourceInformation}) { |
| 109 if (visitElse == null) { |
| 110 // Make sure to have an else part to avoid a critical edge. A |
| 111 // critical edge is an edge that connects a block with multiple |
| 112 // successors to a block with multiple predecessors. We avoid |
| 113 // such edges because they prevent inserting copies during code |
| 114 // generation of phi instructions. |
| 115 visitElse = () {}; |
| 116 } |
| 117 |
| 118 _handleDiamondBranch(visitCondition, visitThen, visitElse, |
| 119 isExpression: false, sourceInformation: sourceInformation); |
| 120 } |
| 121 |
| 122 handleConditional(void visitCondition(), void visitThen(), void visitElse()) { |
| 123 assert(visitElse != null); |
| 124 _handleDiamondBranch(visitCondition, visitThen, visitElse, |
| 125 isExpression: true); |
| 126 } |
| 127 |
| 128 handleIfNull(void left(), void right()) { |
| 129 // x ?? y is transformed into: x == null ? y : x |
| 130 HInstruction leftExpression; |
| 131 handleConditional(() { |
| 132 left(); |
| 133 leftExpression = builder.pop(); |
| 134 builder.pushCheckNull(leftExpression); |
| 135 }, right, () => builder.stack.add(leftExpression)); |
| 136 } |
| 137 |
| 138 /// Creates the graph for '&&' or '||' operators. |
| 139 /// |
| 140 /// x && y is transformed into: |
| 141 /// |
| 142 /// t0 = boolify(x); |
| 143 /// if (t0) { |
| 144 /// t1 = boolify(y); |
| 145 /// } |
| 146 /// result = phi(t1, false); |
| 147 /// |
| 148 /// x || y is transformed into: |
| 149 /// |
| 150 /// t0 = boolify(x); |
| 151 /// if (not(t0)) { |
| 152 /// t1 = boolify(y); |
| 153 /// } |
| 154 /// result = phi(t1, true); |
| 155 void handleLogicalBinary(void left(), void right(), {bool isAnd}) { |
| 156 HInstruction boolifiedLeft; |
| 157 HInstruction boolifiedRight; |
| 158 |
| 159 void visitCondition() { |
| 160 left(); |
| 161 boolifiedLeft = builder.popBoolified(); |
| 162 builder.stack.add(boolifiedLeft); |
| 163 if (!isAnd) { |
| 164 JavaScriptBackend backend = compiler.backend; |
| 165 builder.push(new HNot(builder.pop(), backend.boolType)); |
| 166 } |
| 167 } |
| 168 |
| 169 void visitThen() { |
| 170 right(); |
| 171 boolifiedRight = builder.popBoolified(); |
| 172 } |
| 173 |
| 174 handleIf(visitCondition, visitThen, null); |
| 175 HConstant notIsAnd = builder.graph.addConstantBool(!isAnd, compiler); |
| 176 JavaScriptBackend backend = compiler.backend; |
| 177 HPhi result = new HPhi.manyInputs( |
| 178 null, <HInstruction>[boolifiedRight, notIsAnd], backend.dynamicType); |
| 179 builder.current.addPhi(result); |
| 180 builder.stack.add(result); |
| 181 } |
| 182 |
| 183 void _handleDiamondBranch( |
| 184 void visitCondition(), void visitThen(), void visitElse(), |
| 185 {bool isExpression, SourceInformation sourceInformation}) { |
| 186 SsaBranch conditionBranch = new SsaBranch(this); |
| 187 SsaBranch thenBranch = new SsaBranch(this); |
| 188 SsaBranch elseBranch = new SsaBranch(this); |
| 189 SsaBranch joinBranch = new SsaBranch(this); |
| 190 |
| 191 conditionBranch.startLocals = builder.localsHandler; |
| 192 builder.goto(builder.current, conditionBranch.block); |
| 193 |
| 194 buildCondition(visitCondition, conditionBranch, thenBranch, elseBranch, |
| 195 sourceInformation); |
| 196 HInstruction thenValue = |
| 197 buildBranch(thenBranch, visitThen, joinBranch, isExpression); |
| 198 HInstruction elseValue = |
| 199 buildBranch(elseBranch, visitElse, joinBranch, isExpression); |
| 200 |
| 201 if (isExpression) { |
| 202 assert(thenValue != null && elseValue != null); |
| 203 JavaScriptBackend backend = compiler.backend; |
| 204 HPhi phi = new HPhi.manyInputs( |
| 205 null, <HInstruction>[thenValue, elseValue], backend.dynamicType); |
| 206 joinBranch.block.addPhi(phi); |
| 207 builder.stack.add(phi); |
| 208 } |
| 209 |
| 210 HBasicBlock joinBlock; |
| 211 // If at least one branch did not abort, open the joinBranch. |
| 212 if (!joinBranch.block.predecessors.isEmpty) { |
| 213 startBranch(joinBranch); |
| 214 joinBlock = joinBranch.block; |
| 215 } |
| 216 |
| 217 HIfBlockInformation info = new HIfBlockInformation( |
| 218 new HSubExpressionBlockInformation(conditionBranch.graph), |
| 219 new HSubGraphBlockInformation(thenBranch.graph), |
| 220 new HSubGraphBlockInformation(elseBranch.graph)); |
| 221 |
| 222 HBasicBlock conditionStartBlock = conditionBranch.block; |
| 223 conditionStartBlock.setBlockFlow(info, joinBlock); |
| 224 SubGraph conditionGraph = conditionBranch.graph; |
| 225 HIf branch = conditionGraph.end.last; |
| 226 assert(branch is HIf); |
| 227 branch.blockInformation = conditionStartBlock.blockFlow; |
| 228 } |
| 229 } |
OLD | NEW |