| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 /** | |
| 6 * Instead of emitting each SSA instruction with a temporary variable | |
| 7 * mark instructions that can be emitted at their use-site. | |
| 8 * For example, in: | |
| 9 * t0 = 4; | |
| 10 * t1 = 3; | |
| 11 * t2 = add(t0, t1); | |
| 12 * t0 and t1 would be marked and the resulting code would then be: | |
| 13 * t2 = add(4, 3); | |
| 14 */ | |
| 15 class SsaInstructionMerger extends HBaseVisitor { | |
| 16 List<HInstruction> expectedInputs; | |
| 17 Set<HInstruction> generateAtUseSite; | |
| 18 | |
| 19 SsaInstructionMerger(this.generateAtUseSite); | |
| 20 | |
| 21 void visitGraph(HGraph graph) { | |
| 22 visitDominatorTree(graph); | |
| 23 } | |
| 24 | |
| 25 bool usedOnlyByPhis(instruction) { | |
| 26 for (HInstruction user in instruction.usedBy) { | |
| 27 if (user is !HPhi) return false; | |
| 28 } | |
| 29 return true; | |
| 30 } | |
| 31 | |
| 32 void visitInstruction(HInstruction instruction) { | |
| 33 // A code motion invariant instruction is dealt before visiting it. | |
| 34 assert(!instruction.isCodeMotionInvariant()); | |
| 35 for (HInstruction input in instruction.inputs) { | |
| 36 if (!generateAtUseSite.contains(input) | |
| 37 && !input.isCodeMotionInvariant() | |
| 38 && input.usedBy.length == 1) { | |
| 39 expectedInputs.add(input); | |
| 40 } | |
| 41 } | |
| 42 } | |
| 43 | |
| 44 // The codegen might use the input multiple times, so it must not be | |
| 45 // set generate at use site. | |
| 46 void visitIs(HIs instruction) {} | |
| 47 | |
| 48 // A check method must not have its input generate at use site, | |
| 49 // because it's using it multiple times. | |
| 50 void visitCheck(HCheck instruction) {} | |
| 51 | |
| 52 // A type guard should not generate its input at use site, otherwise | |
| 53 // they would not be alive. | |
| 54 void visitTypeGuard(HTypeGuard instruction) {} | |
| 55 | |
| 56 void tryGenerateAtUseSite(HInstruction instruction) { | |
| 57 // A type guard should never be generate at use site, otherwise we | |
| 58 // cannot bailout. | |
| 59 if (instruction is HTypeGuard) return; | |
| 60 | |
| 61 // A check should never be generate at use site, otherwise we | |
| 62 // cannot throw. | |
| 63 if (instruction is HCheck) return; | |
| 64 | |
| 65 generateAtUseSite.add(instruction); | |
| 66 } | |
| 67 | |
| 68 bool isBlockSinglePredecessor(HBasicBlock block) { | |
| 69 return block.successors.length === 1 | |
| 70 && block.successors[0].predecessors.length === 1; | |
| 71 } | |
| 72 | |
| 73 void visitBasicBlock(HBasicBlock block) { | |
| 74 // Compensate from not merging blocks: if the block is the | |
| 75 // single predecessor of its single successor, let the successor | |
| 76 // visit it. | |
| 77 if (isBlockSinglePredecessor(block)) return; | |
| 78 | |
| 79 tryMergingExpressions(block); | |
| 80 } | |
| 81 | |
| 82 void tryMergingExpressions(HBasicBlock block) { | |
| 83 // Visit each instruction of the basic block in last-to-first order. | |
| 84 // Keep a list of expected inputs of the current "expression" being | |
| 85 // merged. If instructions occur in the expected order, they are | |
| 86 // included in the expression. | |
| 87 | |
| 88 // The expectedInputs list holds non-trivial instructions that may | |
| 89 // be generated at their use site, if they occur in the correct order. | |
| 90 if (expectedInputs === null) expectedInputs = new List<HInstruction>(); | |
| 91 | |
| 92 // Pop instructions from expectedInputs until instruction is found. | |
| 93 // Return true if it is found, or false if not. | |
| 94 bool findInInputs(HInstruction instruction) { | |
| 95 while (!expectedInputs.isEmpty()) { | |
| 96 HInstruction nextInput = expectedInputs.removeLast(); | |
| 97 assert(!generateAtUseSite.contains(nextInput)); | |
| 98 assert(nextInput.usedBy.length == 1); | |
| 99 if (nextInput == instruction) { | |
| 100 return true; | |
| 101 } | |
| 102 } | |
| 103 return false; | |
| 104 } | |
| 105 | |
| 106 block.last.accept(this); | |
| 107 for (HInstruction instruction = block.last.previous; | |
| 108 instruction !== null; | |
| 109 instruction = instruction.previous) { | |
| 110 if (generateAtUseSite.contains(instruction)) { | |
| 111 continue; | |
| 112 } | |
| 113 if (instruction.isCodeMotionInvariant()) { | |
| 114 generateAtUseSite.add(instruction); | |
| 115 continue; | |
| 116 } | |
| 117 bool foundInInputs = false; | |
| 118 // See if the current instruction is the next non-trivial | |
| 119 // expected input. If not, drop the expectedInputs and | |
| 120 // start over. | |
| 121 if (findInInputs(instruction)) { | |
| 122 foundInInputs = true; | |
| 123 tryGenerateAtUseSite(instruction); | |
| 124 } else { | |
| 125 assert(expectedInputs.isEmpty()); | |
| 126 } | |
| 127 if (foundInInputs || usedOnlyByPhis(instruction)) { | |
| 128 // Try merging all non-trivial inputs. | |
| 129 instruction.accept(this); | |
| 130 } | |
| 131 } | |
| 132 | |
| 133 if (block.predecessors.length === 1 | |
| 134 && isBlockSinglePredecessor(block.predecessors[0])) { | |
| 135 tryMergingExpressions(block.predecessors[0]); | |
| 136 } else { | |
| 137 expectedInputs = null; | |
| 138 } | |
| 139 } | |
| 140 } | |
| 141 | |
| 142 /** | |
| 143 * Detect control flow arising from short-circuit logical operators, and | |
| 144 * prepare the program to be generated using these operators instead of | |
| 145 * nested ifs and boolean variables. | |
| 146 */ | |
| 147 class SsaConditionMerger extends HGraphVisitor { | |
| 148 Set<HInstruction> generateAtUseSite; | |
| 149 Map<HPhi, String> logicalOperations; | |
| 150 | |
| 151 SsaConditionMerger(this.generateAtUseSite, this.logicalOperations); | |
| 152 | |
| 153 void visitGraph(HGraph graph) { | |
| 154 visitDominatorTree(graph); | |
| 155 } | |
| 156 | |
| 157 /** | |
| 158 * Returns true if the given instruction is an expression that uses up all | |
| 159 * instructions up to the given [limit]. | |
| 160 * | |
| 161 * That is, all instructions starting after the [limit] block (at the branch | |
| 162 * leading to the [instruction]) down to the given [instruction] can be | |
| 163 * generated at use-site. | |
| 164 */ | |
| 165 bool isExpression(HInstruction instruction, HBasicBlock limit) { | |
| 166 if (instruction is HPhi && !logicalOperations.containsKey(instruction)) { | |
| 167 return false; | |
| 168 } | |
| 169 while (instruction.previous != null) { | |
| 170 instruction = instruction.previous; | |
| 171 if (!generateAtUseSite.contains(instruction)) { | |
| 172 return false; | |
| 173 } | |
| 174 } | |
| 175 HBasicBlock block = instruction.block; | |
| 176 if (!block.phis.isEmpty()) return false; | |
| 177 if (instruction is HPhi && logicalOperations.containsKey(instruction)) { | |
| 178 return isExpression(instruction.inputs[0], limit); | |
| 179 } | |
| 180 return block.predecessors.length == 1 && block.predecessors[0] == limit; | |
| 181 } | |
| 182 | |
| 183 void replaceWithLogicalOperator(HPhi phi, String type) { | |
| 184 if (canGenerateAtUseSite(phi)) generateAtUseSite.add(phi); | |
| 185 logicalOperations[phi] = type; | |
| 186 } | |
| 187 | |
| 188 bool canGenerateAtUseSite(HPhi phi) { | |
| 189 if (phi.usedBy.length != 1) return false; | |
| 190 assert(phi.next == null); | |
| 191 HInstruction use = phi.usedBy[0]; | |
| 192 | |
| 193 HInstruction current = phi.block.first; | |
| 194 while (current != use) { | |
| 195 if (!generateAtUseSite.contains(current)) return false; | |
| 196 if (current.next != null) { | |
| 197 current = current.next; | |
| 198 } else if (current is HPhi) { | |
| 199 current = current.block.first; | |
| 200 } else { | |
| 201 assert(current is HControlFlow); | |
| 202 if (current is !HGoto) return false; | |
| 203 HBasicBlock nextBlock = current.block.successors[0]; | |
| 204 if (!nextBlock.phis.isEmpty()) { | |
| 205 current = nextBlock.phis.first; | |
| 206 } else { | |
| 207 current = nextBlock.first; | |
| 208 } | |
| 209 } | |
| 210 } | |
| 211 return true; | |
| 212 } | |
| 213 | |
| 214 void detectLogicControlFlow(HPhi phi) { | |
| 215 // Check for the most common pattern for a short-circuit logic operation: | |
| 216 // B0 b0 = ...; if (b0) goto B1 else B2 (or: if (!b0) goto B2 else B1) | |
| 217 // |\ | |
| 218 // | B1 b1 = ...; goto B2 | |
| 219 // |/ | |
| 220 // B2 b2 = phi(b0,b1); if(b2) ... | |
| 221 // TODO(lrn): Also recognize ?:-flow? | |
| 222 | |
| 223 if (phi.inputs.length != 2) return; | |
| 224 HInstruction first = phi.inputs[0]; | |
| 225 HBasicBlock firstBlock = first.block; | |
| 226 HInstruction second = phi.inputs[1]; | |
| 227 HBasicBlock secondBlock = second.block; | |
| 228 // Check second input of phi being an expression followed by a goto. | |
| 229 if (second.usedBy.length != 1) return; | |
| 230 HInstruction secondNext = | |
| 231 (second is HPhi) ? secondBlock.first : second.next; | |
| 232 if (secondNext != secondBlock.last) return; | |
| 233 if (secondBlock.last is !HGoto) return; | |
| 234 if (secondBlock.successors[0] != phi.block) return; | |
| 235 if (!isExpression(second, firstBlock)) return; | |
| 236 // Check first input of phi being followed by a (possibly negated) | |
| 237 // conditional branch based on the same value. | |
| 238 if (firstBlock != phi.block.dominator) return; | |
| 239 if (firstBlock.last is !HConditionalBranch) return; | |
| 240 HConditionalBranch firstBranch = firstBlock.last; | |
| 241 // Must be used both for value and for control to avoid the second branch. | |
| 242 if (first.usedBy.length != 2) return; | |
| 243 if (firstBlock.successors[1] != phi.block) return; | |
| 244 HInstruction firstNext = (first is HPhi) ? firstBlock.first : first.next; | |
| 245 if (firstNext == firstBranch && | |
| 246 firstBranch.condition == first) { | |
| 247 replaceWithLogicalOperator(phi, "&&"); | |
| 248 } else if (firstNext is HNot && | |
| 249 firstNext.inputs[0] == first && | |
| 250 generateAtUseSite.contains(firstNext) && | |
| 251 firstNext.next == firstBlock.last && | |
| 252 firstBranch.condition == firstNext) { | |
| 253 replaceWithLogicalOperator(phi, "||"); | |
| 254 } else { | |
| 255 return; | |
| 256 } | |
| 257 // Detected as logic control flow. Mark the corresponding | |
| 258 // inputs as generated at use site. These will now be generated | |
| 259 // as part of an expression. | |
| 260 generateAtUseSite.add(first); | |
| 261 generateAtUseSite.add(firstBlock.last); | |
| 262 generateAtUseSite.add(second); | |
| 263 generateAtUseSite.add(secondBlock.last); | |
| 264 } | |
| 265 | |
| 266 void visitBasicBlock(HBasicBlock block) { | |
| 267 if (!block.phis.isEmpty() && | |
| 268 block.phis.first == block.phis.last) { | |
| 269 detectLogicControlFlow(block.phis.first); | |
| 270 } | |
| 271 } | |
| 272 } | |
| 273 | |
| 274 // Precedence information for JavaScript operators. | |
| 275 class JSPrecedence { | |
| 276 // Used as precedence for something that's not even an expression. | |
| 277 static final int STATEMENT_PRECEDENCE = 0; | |
| 278 // Precedences of JS operators. | |
| 279 static final int EXPRESSION_PRECEDENCE = 1; | |
| 280 static final int ASSIGNMENT_PRECEDENCE = 2; | |
| 281 static final int CONDITIONAL_PRECEDENCE = 3; | |
| 282 static final int LOGICAL_OR_PRECEDENCE = 4; | |
| 283 static final int LOGICAL_AND_PRECEDENCE = 5; | |
| 284 static final int BITWISE_OR_PRECEDENCE = 6; | |
| 285 static final int BITWISE_XOR_PRECEDENCE = 7; | |
| 286 static final int BITWISE_AND_PRECEDENCE = 8; | |
| 287 static final int EQUALITY_PRECEDENCE = 9; | |
| 288 static final int RELATIONAL_PRECEDENCE = 10; | |
| 289 static final int SHIFT_PRECEDENCE = 11; | |
| 290 static final int ADDITIVE_PRECEDENCE = 12; | |
| 291 static final int MULTIPLICATIVE_PRECEDENCE = 13; | |
| 292 static final int PREFIX_PRECEDENCE = 14; | |
| 293 static final int POSTFIX_PRECEDENCE = 15; | |
| 294 static final int CALL_PRECEDENCE = 16; | |
| 295 // We never use "new MemberExpression" without arguments, so we can | |
| 296 // combine CallExpression and MemberExpression without ambiguity. | |
| 297 static final int MEMBER_PRECEDENCE = CALL_PRECEDENCE; | |
| 298 static final int PRIMARY_PRECEDENCE = 17; | |
| 299 | |
| 300 // The operators that an occur in HBinaryOp. | |
| 301 static final Map<String, JSBinaryOperatorPrecedence> binary = const { | |
| 302 "||" : const JSBinaryOperatorPrecedence(LOGICAL_OR_PRECEDENCE, | |
| 303 LOGICAL_AND_PRECEDENCE), | |
| 304 "&&" : const JSBinaryOperatorPrecedence(LOGICAL_AND_PRECEDENCE, | |
| 305 BITWISE_OR_PRECEDENCE), | |
| 306 "|" : const JSBinaryOperatorPrecedence(BITWISE_OR_PRECEDENCE, | |
| 307 BITWISE_XOR_PRECEDENCE), | |
| 308 "^" : const JSBinaryOperatorPrecedence(BITWISE_XOR_PRECEDENCE, | |
| 309 BITWISE_AND_PRECEDENCE), | |
| 310 "&" : const JSBinaryOperatorPrecedence(BITWISE_AND_PRECEDENCE, | |
| 311 EQUALITY_PRECEDENCE), | |
| 312 "==" : const JSBinaryOperatorPrecedence(EQUALITY_PRECEDENCE, | |
| 313 RELATIONAL_PRECEDENCE), | |
| 314 "!=" : const JSBinaryOperatorPrecedence(EQUALITY_PRECEDENCE, | |
| 315 RELATIONAL_PRECEDENCE), | |
| 316 "===" : const JSBinaryOperatorPrecedence(EQUALITY_PRECEDENCE, | |
| 317 RELATIONAL_PRECEDENCE), | |
| 318 "!==" : const JSBinaryOperatorPrecedence(EQUALITY_PRECEDENCE, | |
| 319 RELATIONAL_PRECEDENCE), | |
| 320 "<" : const JSBinaryOperatorPrecedence(RELATIONAL_PRECEDENCE, | |
| 321 SHIFT_PRECEDENCE), | |
| 322 ">" : const JSBinaryOperatorPrecedence(RELATIONAL_PRECEDENCE, | |
| 323 SHIFT_PRECEDENCE), | |
| 324 "<=" : const JSBinaryOperatorPrecedence(RELATIONAL_PRECEDENCE, | |
| 325 SHIFT_PRECEDENCE), | |
| 326 ">=" : const JSBinaryOperatorPrecedence(RELATIONAL_PRECEDENCE, | |
| 327 SHIFT_PRECEDENCE), | |
| 328 "<<" : const JSBinaryOperatorPrecedence(SHIFT_PRECEDENCE, | |
| 329 ADDITIVE_PRECEDENCE), | |
| 330 ">>" : const JSBinaryOperatorPrecedence(SHIFT_PRECEDENCE, | |
| 331 ADDITIVE_PRECEDENCE), | |
| 332 ">>>" : const JSBinaryOperatorPrecedence(SHIFT_PRECEDENCE, | |
| 333 ADDITIVE_PRECEDENCE), | |
| 334 "+" : const JSBinaryOperatorPrecedence(ADDITIVE_PRECEDENCE, | |
| 335 MULTIPLICATIVE_PRECEDENCE), | |
| 336 "-" : const JSBinaryOperatorPrecedence(ADDITIVE_PRECEDENCE, | |
| 337 MULTIPLICATIVE_PRECEDENCE), | |
| 338 "*" : const JSBinaryOperatorPrecedence(MULTIPLICATIVE_PRECEDENCE, | |
| 339 PREFIX_PRECEDENCE), | |
| 340 "/" : const JSBinaryOperatorPrecedence(MULTIPLICATIVE_PRECEDENCE, | |
| 341 PREFIX_PRECEDENCE), | |
| 342 "%" : const JSBinaryOperatorPrecedence(MULTIPLICATIVE_PRECEDENCE, | |
| 343 PREFIX_PRECEDENCE), | |
| 344 }; | |
| 345 } | |
| 346 | |
| 347 class JSBinaryOperatorPrecedence { | |
| 348 final int left; | |
| 349 final int right; | |
| 350 const JSBinaryOperatorPrecedence(this.left, this.right); | |
| 351 // All binary operators (excluding assignment) are left associative. | |
| 352 int get precedence() => left; | |
| 353 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 9873021:
Move frog/leg to lib/compiler/implementation. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/