| 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 HTypeMap types; |
| 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(types)); |
| 21 generateAtUseSite.add(instruction); | 22 generateAtUseSite.add(instruction); |
| 22 } | 23 } |
| 23 | 24 |
| 24 SsaInstructionMerger(this.generateAtUseSite); | 25 SsaInstructionMerger(this.types, 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 if (!instruction.isBuiltin(types) || |
| 63 singleIdentityComparison(left, right, types) != null) { |
| 61 super.visitEquals(instruction); | 64 super.visitEquals(instruction); |
| 62 } | 65 } |
| 63 // Do nothing. | 66 // Do nothing. |
| 64 } | 67 } |
| 65 | 68 |
| 66 // An identity operation must only have its inputs generated at use site if | 69 // 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 / | 70 // does not require an expression with multiple uses (because of null / |
| 68 // undefined). | 71 // undefined). |
| 69 void visitIdentity(HIdentity instruction) { | 72 void visitIdentity(HIdentity instruction) { |
| 70 if (singleIdentityComparison(instruction.left, instruction.right) != null) { | 73 HInstruction left = instruction.left; |
| 74 HInstruction right = instruction.right; |
| 75 if (singleIdentityComparison(left, right, types) != null) { |
| 71 super.visitIdentity(instruction); | 76 super.visitIdentity(instruction); |
| 72 } | 77 } |
| 73 // Do nothing. | 78 // Do nothing. |
| 74 } | 79 } |
| 75 | 80 |
| 76 void visitTypeConversion(HTypeConversion instruction) { | 81 void visitTypeConversion(HTypeConversion instruction) { |
| 77 if (!instruction.isChecked) { | 82 if (!instruction.isChecked) { |
| 78 markAsGenerateAtUseSite(instruction); | 83 markAsGenerateAtUseSite(instruction); |
| 79 } else if (instruction.isCheckedModeCheck) { | 84 } else if (instruction.isCheckedModeCheck) { |
| 80 // Checked mode checks compile to code that only use their input | 85 // 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; | 135 for (HInstruction instruction = block.last.previous; |
| 131 instruction !== null; | 136 instruction !== null; |
| 132 instruction = instruction.previous) { | 137 instruction = instruction.previous) { |
| 133 if (generateAtUseSite.contains(instruction)) { | 138 if (generateAtUseSite.contains(instruction)) { |
| 134 continue; | 139 continue; |
| 135 } | 140 } |
| 136 if (instruction.isCodeMotionInvariant()) { | 141 if (instruction.isCodeMotionInvariant()) { |
| 137 markAsGenerateAtUseSite(instruction); | 142 markAsGenerateAtUseSite(instruction); |
| 138 continue; | 143 continue; |
| 139 } | 144 } |
| 140 if (instruction.isStatement) { | 145 if (instruction.isStatement(types)) { |
| 141 expectedInputs.clear(); | 146 expectedInputs.clear(); |
| 142 } | 147 } |
| 143 // See if the current instruction is the next non-trivial | 148 // See if the current instruction is the next non-trivial |
| 144 // expected input. | 149 // expected input. |
| 145 if (findInInputsAndPopNonMatching(instruction)) { | 150 if (findInInputsAndPopNonMatching(instruction)) { |
| 146 tryGenerateAtUseSite(instruction); | 151 tryGenerateAtUseSite(instruction); |
| 147 } else { | 152 } else { |
| 148 assert(expectedInputs.isEmpty()); | 153 assert(expectedInputs.isEmpty()); |
| 149 } | 154 } |
| 150 instruction.accept(this); | 155 instruction.accept(this); |
| 151 } | 156 } |
| 152 | 157 |
| 153 if (block.predecessors.length === 1 | 158 if (block.predecessors.length === 1 |
| 154 && isBlockSinglePredecessor(block.predecessors[0])) { | 159 && isBlockSinglePredecessor(block.predecessors[0])) { |
| 155 assert(block.phis.isEmpty()); | 160 assert(block.phis.isEmpty()); |
| 156 tryMergingExpressions(block.predecessors[0]); | 161 tryMergingExpressions(block.predecessors[0]); |
| 157 } else { | 162 } else { |
| 158 expectedInputs = null; | 163 expectedInputs = null; |
| 159 } | 164 } |
| 160 } | 165 } |
| 161 } | 166 } |
| 162 | 167 |
| 163 /** | 168 /** |
| 164 * Detect control flow arising from short-circuit logical and | 169 * Detect control flow arising from short-circuit logical and |
| 165 * conditional operators, and prepare the program to be generated | 170 * conditional operators, and prepare the program to be generated |
| 166 * using these operators instead of nested ifs and boolean variables. | 171 * using these operators instead of nested ifs and boolean variables. |
| 167 */ | 172 */ |
| 168 class SsaConditionMerger extends HGraphVisitor { | 173 class SsaConditionMerger extends HGraphVisitor { |
| 174 final HTypeMap types; |
| 169 Set<HInstruction> generateAtUseSite; | 175 Set<HInstruction> generateAtUseSite; |
| 170 Set<HInstruction> controlFlowOperators; | 176 Set<HInstruction> controlFlowOperators; |
| 171 | 177 |
| 172 void markAsGenerateAtUseSite(HInstruction instruction) { | 178 void markAsGenerateAtUseSite(HInstruction instruction) { |
| 173 assert(!instruction.isStatement); | 179 assert(!instruction.isStatement(types)); |
| 174 generateAtUseSite.add(instruction); | 180 generateAtUseSite.add(instruction); |
| 175 } | 181 } |
| 176 | 182 |
| 177 SsaConditionMerger(this.generateAtUseSite, this.controlFlowOperators); | 183 SsaConditionMerger(this.types, |
| 184 this.generateAtUseSite, |
| 185 this.controlFlowOperators); |
| 178 | 186 |
| 179 void visitGraph(HGraph graph) { | 187 void visitGraph(HGraph graph) { |
| 180 visitPostDominatorTree(graph); | 188 visitPostDominatorTree(graph); |
| 181 } | 189 } |
| 182 | 190 |
| 183 /** | 191 /** |
| 184 * Check if a block has at least one statement other than | 192 * Check if a block has at least one statement other than |
| 185 * [instruction]. | 193 * [instruction]. |
| 186 */ | 194 */ |
| 187 bool hasAnyStatement(HBasicBlock block, HInstruction instruction) { | 195 bool hasAnyStatement(HBasicBlock block, HInstruction instruction) { |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 257 | 265 |
| 258 if (end == null) return; | 266 if (end == null) return; |
| 259 if (end.phis.isEmpty()) return; | 267 if (end.phis.isEmpty()) return; |
| 260 if (end.phis.first !== end.phis.last) return; | 268 if (end.phis.first !== end.phis.last) return; |
| 261 HBasicBlock elseBlock = startIf.elseBlock; | 269 HBasicBlock elseBlock = startIf.elseBlock; |
| 262 | 270 |
| 263 if (end.predecessors[1] !== elseBlock) return; | 271 if (end.predecessors[1] !== elseBlock) return; |
| 264 HPhi phi = end.phis.first; | 272 HPhi phi = end.phis.first; |
| 265 HInstruction thenInput = phi.inputs[0]; | 273 HInstruction thenInput = phi.inputs[0]; |
| 266 HInstruction elseInput = phi.inputs[1]; | 274 HInstruction elseInput = phi.inputs[1]; |
| 267 if (thenInput.isStatement || elseInput.isStatement) return; | 275 if (thenInput.isStatement(types) || elseInput.isStatement(types)) return; |
| 268 | 276 |
| 269 if (hasAnyStatement(elseBlock, elseInput)) return; | 277 if (hasAnyStatement(elseBlock, elseInput)) return; |
| 270 assert(elseBlock.successors.length == 1); | 278 assert(elseBlock.successors.length == 1); |
| 271 assert(end.predecessors.length == 2); | 279 assert(end.predecessors.length == 2); |
| 272 | 280 |
| 273 HBasicBlock thenBlock = startIf.thenBlock; | 281 HBasicBlock thenBlock = startIf.thenBlock; |
| 274 // Skip trivial goto blocks. | 282 // Skip trivial goto blocks. |
| 275 while (thenBlock.successors[0] != end && thenBlock.first is HGoto) { | 283 while (thenBlock.successors[0] != end && thenBlock.first is HGoto) { |
| 276 thenBlock = thenBlock.successors[0]; | 284 thenBlock = thenBlock.successors[0]; |
| 277 } | 285 } |
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 318 } | 326 } |
| 319 | 327 |
| 320 // If [thenInput] is defined in the first predecessor, then it is only used | 328 // If [thenInput] is defined in the first predecessor, then it is only used |
| 321 // by [phi] and can be generated at use site. | 329 // by [phi] and can be generated at use site. |
| 322 if (thenInput.block === end.predecessors[0]) { | 330 if (thenInput.block === end.predecessors[0]) { |
| 323 assert(thenInput.usedBy.length == 1); | 331 assert(thenInput.usedBy.length == 1); |
| 324 markAsGenerateAtUseSite(thenInput); | 332 markAsGenerateAtUseSite(thenInput); |
| 325 } | 333 } |
| 326 } | 334 } |
| 327 } | 335 } |
| OLD | NEW |