| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, 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 /** | 5 /** |
| 6 * Instead of emitting each SSA instruction with a temporary variable | 6 * Instead of emitting each SSA instruction with a temporary variable |
| 7 * mark instructions that can be emitted at their use-site. | 7 * mark instructions that can be emitted at their use-site. |
| 8 * For example, in: | 8 * For example, in: |
| 9 * t0 = 4; | 9 * t0 = 4; |
| 10 * t1 = 3; | 10 * t1 = 3; |
| 11 * t2 = add(t0, t1); | 11 * t2 = add(t0, t1); |
| 12 * t0 and t1 would be marked and the resulting code would then be: | 12 * t0 and t1 would be marked and the resulting code would then be: |
| 13 * t2 = add(4, 3); | 13 * t2 = add(4, 3); |
| 14 */ | 14 */ |
| 15 class SsaInstructionMerger extends HBaseVisitor { | 15 class SsaInstructionMerger extends HBaseVisitor { |
| 16 JavaScriptWorkItem work; |
| 16 List<HInstruction> expectedInputs; | 17 List<HInstruction> expectedInputs; |
| 17 Set<HInstruction> generateAtUseSite; | 18 Set<HInstruction> generateAtUseSite; |
| 18 | 19 |
| 19 void markAsGenerateAtUseSite(HInstruction instruction) { | 20 void markAsGenerateAtUseSite(HInstruction instruction) { |
| 20 assert(!instruction.isStatement); | 21 assert(!instruction.isStatement(work.types)); |
| 21 generateAtUseSite.add(instruction); | 22 generateAtUseSite.add(instruction); |
| 22 } | 23 } |
| 23 | 24 |
| 24 SsaInstructionMerger(this.generateAtUseSite); | 25 SsaInstructionMerger(this.work, this.generateAtUseSite); |
| 25 | 26 |
| 26 void visitGraph(HGraph graph) { | 27 void visitGraph(HGraph graph) { |
| 27 visitDominatorTree(graph); | 28 visitDominatorTree(graph); |
| 28 } | 29 } |
| 29 | 30 |
| 30 void visitInstruction(HInstruction instruction) { | 31 void visitInstruction(HInstruction instruction) { |
| 31 // A code motion invariant instruction is dealt before visiting it. | 32 // A code motion invariant instruction is dealt before visiting it. |
| 32 assert(!instruction.isCodeMotionInvariant()); | 33 assert(!instruction.isCodeMotionInvariant()); |
| 33 for (HInstruction input in instruction.inputs) { | 34 for (HInstruction input in instruction.inputs) { |
| 34 if (!generateAtUseSite.contains(input) | 35 if (!generateAtUseSite.contains(input) |
| (...skipping 14 matching lines...) Expand all Loading... |
| 49 void visitCheck(HCheck instruction) {} | 50 void visitCheck(HCheck instruction) {} |
| 50 | 51 |
| 51 // A type guard should not generate its input at use site, otherwise | 52 // A type guard should not generate its input at use site, otherwise |
| 52 // they would not be alive. | 53 // they would not be alive. |
| 53 void visitTypeGuard(HTypeGuard instruction) {} | 54 void visitTypeGuard(HTypeGuard instruction) {} |
| 54 | 55 |
| 55 // If an equality operation is builtin it must only have its inputs generated | 56 // If an equality operation is builtin it must only have its inputs generated |
| 56 // at use site if it does not require an expression with repeated uses | 57 // at use site if it does not require an expression with repeated uses |
| 57 // (because of null / undefined). | 58 // (because of null / undefined). |
| 58 void visitEquals(HEquals instruction) { | 59 void visitEquals(HEquals instruction) { |
| 59 if (!instruction.builtin || | 60 HInstruction left = instruction.left; |
| 60 singleIdentityComparison(instruction.left, instruction.right) != null) { | 61 HInstruction right = instruction.right; |
| 62 HTypeMap types = work.types; |
| 63 if (!instruction.isBuiltin(types) || |
| 64 singleIdentityComparison(left, right, types) != null) { |
| 61 super.visitEquals(instruction); | 65 super.visitEquals(instruction); |
| 62 } | 66 } |
| 63 // Do nothing. | 67 // Do nothing. |
| 64 } | 68 } |
| 65 | 69 |
| 66 // An identity operation must only have its inputs generated at use site if | 70 // An identity operation must only have its inputs generated at use site if |
| 67 // does not require an expression with multiple uses (because of null / | 71 // does not require an expression with multiple uses (because of null / |
| 68 // undefined). | 72 // undefined). |
| 69 void visitIdentity(HIdentity instruction) { | 73 void visitIdentity(HIdentity instruction) { |
| 70 if (singleIdentityComparison(instruction.left, instruction.right) != null) { | 74 HInstruction left = instruction.left; |
| 75 HInstruction right = instruction.right; |
| 76 HTypeMap types = work.types; |
| 77 if (singleIdentityComparison(left, right, types) != null) { |
| 71 super.visitIdentity(instruction); | 78 super.visitIdentity(instruction); |
| 72 } | 79 } |
| 73 // Do nothing. | 80 // Do nothing. |
| 74 } | 81 } |
| 75 | 82 |
| 76 void visitTypeConversion(HTypeConversion instruction) { | 83 void visitTypeConversion(HTypeConversion instruction) { |
| 77 if (!instruction.isChecked) { | 84 if (!instruction.isChecked) { |
| 78 markAsGenerateAtUseSite(instruction); | 85 markAsGenerateAtUseSite(instruction); |
| 79 } else if (instruction.isCheckedModeCheck) { | 86 } else if (instruction.isCheckedModeCheck) { |
| 80 // Checked mode checks compile to code that only use their input | 87 // Checked mode checks compile to code that only use their input |
| (...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 130 for (HInstruction instruction = block.last.previous; | 137 for (HInstruction instruction = block.last.previous; |
| 131 instruction !== null; | 138 instruction !== null; |
| 132 instruction = instruction.previous) { | 139 instruction = instruction.previous) { |
| 133 if (generateAtUseSite.contains(instruction)) { | 140 if (generateAtUseSite.contains(instruction)) { |
| 134 continue; | 141 continue; |
| 135 } | 142 } |
| 136 if (instruction.isCodeMotionInvariant()) { | 143 if (instruction.isCodeMotionInvariant()) { |
| 137 markAsGenerateAtUseSite(instruction); | 144 markAsGenerateAtUseSite(instruction); |
| 138 continue; | 145 continue; |
| 139 } | 146 } |
| 140 if (instruction.isStatement) { | 147 if (instruction.isStatement(work.types)) { |
| 141 expectedInputs.clear(); | 148 expectedInputs.clear(); |
| 142 } | 149 } |
| 143 // See if the current instruction is the next non-trivial | 150 // See if the current instruction is the next non-trivial |
| 144 // expected input. | 151 // expected input. |
| 145 if (findInInputsAndPopNonMatching(instruction)) { | 152 if (findInInputsAndPopNonMatching(instruction)) { |
| 146 tryGenerateAtUseSite(instruction); | 153 tryGenerateAtUseSite(instruction); |
| 147 } else { | 154 } else { |
| 148 assert(expectedInputs.isEmpty()); | 155 assert(expectedInputs.isEmpty()); |
| 149 } | 156 } |
| 150 instruction.accept(this); | 157 instruction.accept(this); |
| 151 } | 158 } |
| 152 | 159 |
| 153 if (block.predecessors.length === 1 | 160 if (block.predecessors.length === 1 |
| 154 && isBlockSinglePredecessor(block.predecessors[0])) { | 161 && isBlockSinglePredecessor(block.predecessors[0])) { |
| 155 assert(block.phis.isEmpty()); | 162 assert(block.phis.isEmpty()); |
| 156 tryMergingExpressions(block.predecessors[0]); | 163 tryMergingExpressions(block.predecessors[0]); |
| 157 } else { | 164 } else { |
| 158 expectedInputs = null; | 165 expectedInputs = null; |
| 159 } | 166 } |
| 160 } | 167 } |
| 161 } | 168 } |
| 162 | 169 |
| 163 /** | 170 /** |
| 164 * Detect control flow arising from short-circuit logical and | 171 * Detect control flow arising from short-circuit logical and |
| 165 * conditional operators, and prepare the program to be generated | 172 * conditional operators, and prepare the program to be generated |
| 166 * using these operators instead of nested ifs and boolean variables. | 173 * using these operators instead of nested ifs and boolean variables. |
| 167 */ | 174 */ |
| 168 class SsaConditionMerger extends HGraphVisitor { | 175 class SsaConditionMerger extends HGraphVisitor { |
| 176 final JavaScriptWorkItem work; |
| 169 Set<HInstruction> generateAtUseSite; | 177 Set<HInstruction> generateAtUseSite; |
| 170 Set<HInstruction> controlFlowOperators; | 178 Set<HInstruction> controlFlowOperators; |
| 171 | 179 |
| 172 void markAsGenerateAtUseSite(HInstruction instruction) { | 180 void markAsGenerateAtUseSite(HInstruction instruction) { |
| 173 assert(!instruction.isStatement); | 181 assert(!instruction.isStatement(work.types)); |
| 174 generateAtUseSite.add(instruction); | 182 generateAtUseSite.add(instruction); |
| 175 } | 183 } |
| 176 | 184 |
| 177 SsaConditionMerger(this.generateAtUseSite, this.controlFlowOperators); | 185 SsaConditionMerger(this.work, |
| 186 this.generateAtUseSite, |
| 187 this.controlFlowOperators); |
| 178 | 188 |
| 179 void visitGraph(HGraph graph) { | 189 void visitGraph(HGraph graph) { |
| 180 visitPostDominatorTree(graph); | 190 visitPostDominatorTree(graph); |
| 181 } | 191 } |
| 182 | 192 |
| 183 /** | 193 /** |
| 184 * Check if a block has at least one statement other than | 194 * Check if a block has at least one statement other than |
| 185 * [instruction]. | 195 * [instruction]. |
| 186 */ | 196 */ |
| 187 bool hasAnyStatement(HBasicBlock block, HInstruction instruction) { | 197 bool hasAnyStatement(HBasicBlock block, HInstruction instruction) { |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 257 | 267 |
| 258 if (end == null) return; | 268 if (end == null) return; |
| 259 if (end.phis.isEmpty()) return; | 269 if (end.phis.isEmpty()) return; |
| 260 if (end.phis.first !== end.phis.last) return; | 270 if (end.phis.first !== end.phis.last) return; |
| 261 HBasicBlock elseBlock = startIf.elseBlock; | 271 HBasicBlock elseBlock = startIf.elseBlock; |
| 262 | 272 |
| 263 if (end.predecessors[1] !== elseBlock) return; | 273 if (end.predecessors[1] !== elseBlock) return; |
| 264 HPhi phi = end.phis.first; | 274 HPhi phi = end.phis.first; |
| 265 HInstruction thenInput = phi.inputs[0]; | 275 HInstruction thenInput = phi.inputs[0]; |
| 266 HInstruction elseInput = phi.inputs[1]; | 276 HInstruction elseInput = phi.inputs[1]; |
| 267 if (thenInput.isStatement || elseInput.isStatement) return; | 277 HTypeMap types = work.types; |
| 278 if (thenInput.isStatement(types) || elseInput.isStatement(types)) return; |
| 268 | 279 |
| 269 if (hasAnyStatement(elseBlock, elseInput)) return; | 280 if (hasAnyStatement(elseBlock, elseInput)) return; |
| 270 assert(elseBlock.successors.length == 1); | 281 assert(elseBlock.successors.length == 1); |
| 271 assert(end.predecessors.length == 2); | 282 assert(end.predecessors.length == 2); |
| 272 | 283 |
| 273 HBasicBlock thenBlock = startIf.thenBlock; | 284 HBasicBlock thenBlock = startIf.thenBlock; |
| 274 // Skip trivial goto blocks. | 285 // Skip trivial goto blocks. |
| 275 while (thenBlock.successors[0] != end && thenBlock.first is HGoto) { | 286 while (thenBlock.successors[0] != end && thenBlock.first is HGoto) { |
| 276 thenBlock = thenBlock.successors[0]; | 287 thenBlock = thenBlock.successors[0]; |
| 277 } | 288 } |
| (...skipping 121 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 399 }; | 410 }; |
| 400 } | 411 } |
| 401 | 412 |
| 402 class JSBinaryOperatorPrecedence { | 413 class JSBinaryOperatorPrecedence { |
| 403 final int left; | 414 final int left; |
| 404 final int right; | 415 final int right; |
| 405 const JSBinaryOperatorPrecedence(this.left, this.right); | 416 const JSBinaryOperatorPrecedence(this.left, this.right); |
| 406 // All binary operators (excluding assignment) are left associative. | 417 // All binary operators (excluding assignment) are left associative. |
| 407 int get precedence() => left; | 418 int get precedence() => left; |
| 408 } | 419 } |
| OLD | NEW |