| 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 part of ssa; | |
| 6 | |
| 7 /** | |
| 8 * Replaces some instructions with specialized versions to make codegen easier. | |
| 9 * Caches codegen information on nodes. | |
| 10 */ | |
| 11 class SsaInstructionSelection extends HBaseVisitor { | |
| 12 final Compiler compiler; | |
| 13 HGraph graph; | |
| 14 | |
| 15 SsaInstructionSelection(this.compiler); | |
| 16 | |
| 17 JavaScriptBackend get backend => compiler.backend; | |
| 18 | |
| 19 void visitGraph(HGraph graph) { | |
| 20 this.graph = graph; | |
| 21 visitDominatorTree(graph); | |
| 22 } | |
| 23 | |
| 24 visitBasicBlock(HBasicBlock block) { | |
| 25 HInstruction instruction = block.first; | |
| 26 while (instruction != null) { | |
| 27 HInstruction next = instruction.next; | |
| 28 HInstruction replacement = instruction.accept(this); | |
| 29 if (replacement != instruction && replacement != null) { | |
| 30 block.rewrite(instruction, replacement); | |
| 31 | |
| 32 // If the replacement instruction does not know its source element, use | |
| 33 // the source element of the instruction. | |
| 34 if (replacement.sourceElement == null) { | |
| 35 replacement.sourceElement = instruction.sourceElement; | |
| 36 } | |
| 37 if (replacement.sourcePosition == null) { | |
| 38 replacement.sourcePosition = instruction.sourcePosition; | |
| 39 } | |
| 40 if (!replacement.isInBasicBlock()) { | |
| 41 // The constant folding can return an instruction that is already | |
| 42 // part of the graph (like an input), so we only add the replacement | |
| 43 // if necessary. | |
| 44 block.addAfter(instruction, replacement); | |
| 45 // Visit the replacement as the next instruction in case it can also | |
| 46 // be constant folded away. | |
| 47 next = replacement; | |
| 48 } | |
| 49 block.remove(instruction); | |
| 50 } | |
| 51 instruction = next; | |
| 52 } | |
| 53 } | |
| 54 | |
| 55 HInstruction visitInstruction(HInstruction node) { | |
| 56 return node; | |
| 57 } | |
| 58 | |
| 59 HInstruction visitIs(HIs node) { | |
| 60 if (node.kind == HIs.RAW_CHECK) { | |
| 61 HInstruction interceptor = node.interceptor; | |
| 62 if (interceptor != null) { | |
| 63 return new HIsViaInterceptor(node.typeExpression, interceptor, | |
| 64 backend.boolType); | |
| 65 } | |
| 66 } | |
| 67 return node; | |
| 68 } | |
| 69 | |
| 70 HInstruction visitIdentity(HIdentity node) { | |
| 71 node.singleComparisonOp = simpleOp(node.left, node.right); | |
| 72 return node; | |
| 73 } | |
| 74 | |
| 75 String simpleOp(HInstruction left, HInstruction right) { | |
| 76 // Returns the single identity comparison (== or ===) or null if a more | |
| 77 // complex expression is required. | |
| 78 TypeMask leftType = left.instructionType; | |
| 79 TypeMask rightType = right.instructionType; | |
| 80 if (leftType.isNullable && rightType.isNullable) { | |
| 81 if (left.isConstantNull() || | |
| 82 right.isConstantNull() || | |
| 83 (left.isPrimitive(compiler) && | |
| 84 leftType == rightType)) { | |
| 85 return '=='; | |
| 86 } | |
| 87 return null; | |
| 88 } | |
| 89 return '==='; | |
| 90 } | |
| 91 | |
| 92 HInstruction visitInvokeDynamic(HInvokeDynamic node) { | |
| 93 if (node.isInterceptedCall) { | |
| 94 // Calls of the form | |
| 95 // | |
| 96 // a.foo$1(a, x) | |
| 97 // | |
| 98 // where the interceptor calling convention is used come from recognizing | |
| 99 // that 'a' is a 'self-interceptor'. If the selector matches only methods | |
| 100 // that ignore the explicit receiver parameter, replace occurences of the | |
| 101 // receiver argument with a dummy receiver '0': | |
| 102 // | |
| 103 // a.foo$1(a, x) ---> a.foo$1(0, x) | |
| 104 // | |
| 105 // This often reduces the number of references to 'a' to one, allowing 'a' | |
| 106 // to be generated at use to avoid a temporary, e.g. | |
| 107 // | |
| 108 // t1 = b.get$thing(); | |
| 109 // t1.foo$1(t1, x) | |
| 110 // ---> | |
| 111 // b.get$thing().foo$1(0, x) | |
| 112 // | |
| 113 Selector selector = node.selector; | |
| 114 if (backend.isInterceptedSelector(selector) && | |
| 115 !backend.isInterceptedMixinSelector(selector)) { | |
| 116 HInstruction interceptor = node.inputs[0]; | |
| 117 HInstruction receiverArgument = node.inputs[1]; | |
| 118 | |
| 119 if (interceptor.nonCheck() == receiverArgument.nonCheck()) { | |
| 120 // TODO(15933): Make automatically generated property extraction | |
| 121 // closures work with the dummy receiver optimization. | |
| 122 if (!selector.isGetter) { | |
| 123 ConstantValue constant = new DummyConstantValue( | |
| 124 receiverArgument.instructionType); | |
| 125 HConstant dummy = graph.addConstant(constant, compiler); | |
| 126 receiverArgument.usedBy.remove(node); | |
| 127 node.inputs[1] = dummy; | |
| 128 dummy.usedBy.add(node); | |
| 129 } | |
| 130 } | |
| 131 } | |
| 132 } | |
| 133 | |
| 134 return node; | |
| 135 } | |
| 136 | |
| 137 HInstruction visitFieldSet(HFieldSet setter) { | |
| 138 // Pattern match | |
| 139 // t1 = x.f; t2 = t1 + 1; x.f = t2; use(t2) --> ++x.f | |
| 140 // t1 = x.f; t2 = t1 op y; x.f = t2; use(t2) --> x.f op= y | |
| 141 // t1 = x.f; t2 = t1 + 1; x.f = t2; use(t1) --> x.f++ | |
| 142 HBasicBlock block = setter.block; | |
| 143 HInstruction op = setter.value; | |
| 144 HInstruction receiver = setter.receiver; | |
| 145 | |
| 146 bool isMatchingRead(HInstruction candidate) { | |
| 147 if (candidate is HFieldGet) { | |
| 148 if (candidate.element != setter.element) return false; | |
| 149 if (candidate.receiver != setter.receiver) return false; | |
| 150 // Recognize only three instructions in sequence in the same block. Thi
s | |
| 151 // could be broadened to allow non-interfering interleaved instructions. | |
| 152 if (op.block != block) return false; | |
| 153 if (candidate.block != block) return false; | |
| 154 if (setter.previous != op) return false; | |
| 155 if (op.previous != candidate) return false; | |
| 156 return true; | |
| 157 } | |
| 158 return false; | |
| 159 } | |
| 160 | |
| 161 HInstruction noMatchingRead() { | |
| 162 // If we have other HFieldSet optimizations, they go here. | |
| 163 return null; | |
| 164 } | |
| 165 | |
| 166 HInstruction replaceOp(HInstruction replacement, HInstruction getter) { | |
| 167 block.addBefore(setter, replacement); | |
| 168 block.remove(setter); | |
| 169 block.rewrite(op, replacement); | |
| 170 block.remove(op); | |
| 171 block.remove(getter); | |
| 172 return null; | |
| 173 } | |
| 174 | |
| 175 HInstruction plusOrMinus(String assignOp, String incrementOp) { | |
| 176 HInvokeBinary binary = op; | |
| 177 HInstruction left = binary.left; | |
| 178 HInstruction right = binary.right; | |
| 179 if (isMatchingRead(left)) { | |
| 180 if (left.usedBy.length == 1) { | |
| 181 if (right is HConstant && right.constant.isOne) { | |
| 182 HInstruction rmw = new HReadModifyWrite.preOp( | |
| 183 setter.element, incrementOp, receiver, op.instructionType); | |
| 184 return replaceOp(rmw, left); | |
| 185 } else { | |
| 186 HInstruction rmw = new HReadModifyWrite.assignOp( | |
| 187 setter.element, | |
| 188 assignOp, | |
| 189 receiver, right, op.instructionType); | |
| 190 return replaceOp(rmw, left); | |
| 191 } | |
| 192 } else if (op.usedBy.length == 1 && | |
| 193 right is HConstant && | |
| 194 right.constant.isOne) { | |
| 195 HInstruction rmw = new HReadModifyWrite.postOp( | |
| 196 setter.element, incrementOp, receiver, op.instructionType); | |
| 197 block.addAfter(left, rmw); | |
| 198 block.remove(setter); | |
| 199 block.remove(op); | |
| 200 block.rewrite(left, rmw); | |
| 201 block.remove(left); | |
| 202 return null; | |
| 203 } | |
| 204 } | |
| 205 return noMatchingRead(); | |
| 206 } | |
| 207 | |
| 208 HInstruction simple(String assignOp, | |
| 209 HInstruction left, HInstruction right) { | |
| 210 if (isMatchingRead(left)) { | |
| 211 if (left.usedBy.length == 1) { | |
| 212 HInstruction rmw = new HReadModifyWrite.assignOp( | |
| 213 setter.element, | |
| 214 assignOp, | |
| 215 receiver, right, op.instructionType); | |
| 216 return replaceOp(rmw, left); | |
| 217 } | |
| 218 } | |
| 219 return noMatchingRead(); | |
| 220 } | |
| 221 | |
| 222 HInstruction simpleBinary(String assignOp) { | |
| 223 HInvokeBinary binary = op; | |
| 224 return simple(assignOp, binary.left, binary.right); | |
| 225 } | |
| 226 | |
| 227 HInstruction bitop(String assignOp) { | |
| 228 // HBitAnd, HBitOr etc. are more difficult because HBitAnd(a.x, y) | |
| 229 // sometimes needs to be forced to unsigned: a.x = (a.x & y) >>> 0. | |
| 230 if (op.isUInt31(compiler)) return simpleBinary(assignOp); | |
| 231 return noMatchingRead(); | |
| 232 } | |
| 233 | |
| 234 if (op is HAdd) return plusOrMinus('+', '++'); | |
| 235 if (op is HSubtract) return plusOrMinus('-', '--'); | |
| 236 | |
| 237 if (op is HStringConcat) return simple('+', op.left, op.right); | |
| 238 | |
| 239 if (op is HMultiply) return simpleBinary('*'); | |
| 240 if (op is HDivide) return simpleBinary('/'); | |
| 241 | |
| 242 if (op is HBitAnd) return bitop('&'); | |
| 243 if (op is HBitOr) return bitop('|'); | |
| 244 if (op is HBitXor) return bitop('^'); | |
| 245 | |
| 246 return noMatchingRead(); | |
| 247 } | |
| 248 } | |
| 249 | |
| 250 /** | |
| 251 * Remove [HTypeKnown] instructions from the graph, to make codegen | |
| 252 * analysis easier. | |
| 253 */ | |
| 254 class SsaTypeKnownRemover extends HBaseVisitor { | |
| 255 | |
| 256 void visitGraph(HGraph graph) { | |
| 257 visitDominatorTree(graph); | |
| 258 } | |
| 259 | |
| 260 void visitBasicBlock(HBasicBlock block) { | |
| 261 HInstruction instruction = block.first; | |
| 262 while (instruction != null) { | |
| 263 HInstruction next = instruction.next; | |
| 264 instruction.accept(this); | |
| 265 instruction = next; | |
| 266 } | |
| 267 } | |
| 268 | |
| 269 void visitTypeKnown(HTypeKnown instruction) { | |
| 270 instruction.block.rewrite(instruction, instruction.checkedInput); | |
| 271 instruction.block.remove(instruction); | |
| 272 } | |
| 273 } | |
| 274 | |
| 275 /** | |
| 276 * Instead of emitting each SSA instruction with a temporary variable | |
| 277 * mark instructions that can be emitted at their use-site. | |
| 278 * For example, in: | |
| 279 * t0 = 4; | |
| 280 * t1 = 3; | |
| 281 * t2 = add(t0, t1); | |
| 282 * t0 and t1 would be marked and the resulting code would then be: | |
| 283 * t2 = add(4, 3); | |
| 284 */ | |
| 285 class SsaInstructionMerger extends HBaseVisitor { | |
| 286 final Compiler compiler; | |
| 287 /** | |
| 288 * List of [HInstruction] that the instruction merger expects in | |
| 289 * order when visiting the inputs of an instruction. | |
| 290 */ | |
| 291 List<HInstruction> expectedInputs; | |
| 292 /** | |
| 293 * Set of pure [HInstruction] that the instruction merger expects to | |
| 294 * find. The order of pure instructions do not matter, as they will | |
| 295 * not be affected by side effects. | |
| 296 */ | |
| 297 Set<HInstruction> pureInputs; | |
| 298 Set<HInstruction> generateAtUseSite; | |
| 299 | |
| 300 void markAsGenerateAtUseSite(HInstruction instruction) { | |
| 301 assert(!instruction.isJsStatement()); | |
| 302 generateAtUseSite.add(instruction); | |
| 303 } | |
| 304 | |
| 305 SsaInstructionMerger(this.generateAtUseSite, this.compiler); | |
| 306 | |
| 307 void visitGraph(HGraph graph) { | |
| 308 visitDominatorTree(graph); | |
| 309 } | |
| 310 | |
| 311 void analyzeInputs(HInstruction user, int start) { | |
| 312 List<HInstruction> inputs = user.inputs; | |
| 313 for (int i = start; i < inputs.length; i++) { | |
| 314 HInstruction input = inputs[i]; | |
| 315 if (!generateAtUseSite.contains(input) | |
| 316 && !input.isCodeMotionInvariant() | |
| 317 && input.usedBy.length == 1 | |
| 318 && input is !HPhi | |
| 319 && input is !HLocalValue | |
| 320 && !input.isJsStatement()) { | |
| 321 if (input.isPure()) { | |
| 322 // Only consider a pure input if it is in the same loop. | |
| 323 // Otherwise, we might move GVN'ed instruction back into the | |
| 324 // loop. | |
| 325 if (user.hasSameLoopHeaderAs(input)) { | |
| 326 // Move it closer to [user], so that instructions in | |
| 327 // between do not prevent making it generate at use site. | |
| 328 input.moveBefore(user); | |
| 329 pureInputs.add(input); | |
| 330 // Previous computations done on [input] are now invalid | |
| 331 // because we moved [input] to another place. So all | |
| 332 // non code motion invariant instructions need | |
| 333 // to be removed from the [generateAtUseSite] set. | |
| 334 input.inputs.forEach((instruction) { | |
| 335 if (!instruction.isCodeMotionInvariant()) { | |
| 336 generateAtUseSite.remove(instruction); | |
| 337 } | |
| 338 }); | |
| 339 // Visit the pure input now so that the expected inputs | |
| 340 // are after the expected inputs of [user]. | |
| 341 input.accept(this); | |
| 342 } | |
| 343 } else { | |
| 344 expectedInputs.add(input); | |
| 345 } | |
| 346 } | |
| 347 } | |
| 348 } | |
| 349 | |
| 350 void visitInstruction(HInstruction instruction) { | |
| 351 // A code motion invariant instruction is dealt before visiting it. | |
| 352 assert(!instruction.isCodeMotionInvariant()); | |
| 353 analyzeInputs(instruction, 0); | |
| 354 } | |
| 355 | |
| 356 // The codegen might use the input multiple times, so it must not be | |
| 357 // set generate at use site. | |
| 358 void visitIs(HIs instruction) {} | |
| 359 | |
| 360 // A bounds check method must not have its first input generated at use site, | |
| 361 // because it's using it twice. | |
| 362 void visitBoundsCheck(HBoundsCheck instruction) { | |
| 363 analyzeInputs(instruction, 1); | |
| 364 } | |
| 365 | |
| 366 // An identity operation must only have its inputs generated at use site if | |
| 367 // does not require an expression with multiple uses (because of null / | |
| 368 // undefined). | |
| 369 void visitIdentity(HIdentity instruction) { | |
| 370 if (instruction.singleComparisonOp != null) { | |
| 371 super.visitIdentity(instruction); | |
| 372 } | |
| 373 // Do nothing. | |
| 374 } | |
| 375 | |
| 376 void visitTypeConversion(HTypeConversion instruction) { | |
| 377 if (!instruction.isArgumentTypeCheck | |
| 378 && !instruction.isReceiverTypeCheck) { | |
| 379 assert(instruction.isCheckedModeCheck || instruction.isCastTypeCheck); | |
| 380 // Checked mode checks and cast checks compile to code that | |
| 381 // only use their input once, so we can safely visit them | |
| 382 // and try to merge the input. | |
| 383 visitInstruction(instruction); | |
| 384 } | |
| 385 } | |
| 386 | |
| 387 void visitTypeKnown(HTypeKnown instruction) { | |
| 388 // [HTypeKnown] instructions are removed before code generation. | |
| 389 assert(false); | |
| 390 } | |
| 391 | |
| 392 void tryGenerateAtUseSite(HInstruction instruction) { | |
| 393 if (instruction.isControlFlow()) return; | |
| 394 markAsGenerateAtUseSite(instruction); | |
| 395 } | |
| 396 | |
| 397 bool isBlockSinglePredecessor(HBasicBlock block) { | |
| 398 return block.successors.length == 1 | |
| 399 && block.successors[0].predecessors.length == 1; | |
| 400 } | |
| 401 | |
| 402 void visitBasicBlock(HBasicBlock block) { | |
| 403 // Compensate from not merging blocks: if the block is the | |
| 404 // single predecessor of its single successor, let the successor | |
| 405 // visit it. | |
| 406 if (isBlockSinglePredecessor(block)) return; | |
| 407 | |
| 408 tryMergingExpressions(block); | |
| 409 } | |
| 410 | |
| 411 void tryMergingExpressions(HBasicBlock block) { | |
| 412 // Visit each instruction of the basic block in last-to-first order. | |
| 413 // Keep a list of expected inputs of the current "expression" being | |
| 414 // merged. If instructions occur in the expected order, they are | |
| 415 // included in the expression. | |
| 416 | |
| 417 // The expectedInputs list holds non-trivial instructions that may | |
| 418 // be generated at their use site, if they occur in the correct order. | |
| 419 if (expectedInputs == null) expectedInputs = new List<HInstruction>(); | |
| 420 if (pureInputs == null) pureInputs = new Set<HInstruction>(); | |
| 421 | |
| 422 // Pop instructions from expectedInputs until instruction is found. | |
| 423 // Return true if it is found, or false if not. | |
| 424 bool findInInputsAndPopNonMatching(HInstruction instruction) { | |
| 425 assert(!instruction.isPure()); | |
| 426 while (!expectedInputs.isEmpty) { | |
| 427 HInstruction nextInput = expectedInputs.removeLast(); | |
| 428 assert(!generateAtUseSite.contains(nextInput)); | |
| 429 assert(nextInput.usedBy.length == 1); | |
| 430 if (identical(nextInput, instruction)) { | |
| 431 return true; | |
| 432 } | |
| 433 } | |
| 434 return false; | |
| 435 } | |
| 436 | |
| 437 block.last.accept(this); | |
| 438 for (HInstruction instruction = block.last.previous; | |
| 439 instruction != null; | |
| 440 instruction = instruction.previous) { | |
| 441 if (generateAtUseSite.contains(instruction)) { | |
| 442 continue; | |
| 443 } | |
| 444 if (instruction.isCodeMotionInvariant()) { | |
| 445 markAsGenerateAtUseSite(instruction); | |
| 446 continue; | |
| 447 } | |
| 448 if (instruction.isPure()) { | |
| 449 if (pureInputs.contains(instruction)) { | |
| 450 tryGenerateAtUseSite(instruction); | |
| 451 } else { | |
| 452 // If the input is not in the [pureInputs] set, it has not | |
| 453 // been visited or should not be generated at use-site. The most | |
| 454 // likely reason for the latter, is that the instruction is used | |
| 455 // in more than one location. | |
| 456 // We must either clear the expectedInputs, or move the pure | |
| 457 // instruction's inputs in front of the existing ones. | |
| 458 // Example: | |
| 459 // t1 = foo(); // side-effect. | |
| 460 // t2 = bar(); // side-effect. | |
| 461 // t3 = pure(t2); // used more than once. | |
| 462 // f(t1, t3); // expected inputs of 'f': t1. | |
| 463 // use(t3); | |
| 464 // | |
| 465 // If we don't clear the expected inputs we end up in a situation | |
| 466 // where pure pushes "t2" on top of "t1" leading to: | |
| 467 // t3 = pure(bar()); | |
| 468 // f(foo(), t3); | |
| 469 // use(t3); | |
| 470 // | |
| 471 // If we clear the expected-inputs list we have the correct | |
| 472 // output: | |
| 473 // t1 = foo(); | |
| 474 // t3 = pure(bar()); | |
| 475 // f(t1, t3); | |
| 476 // use(t3); | |
| 477 // | |
| 478 // Clearing is, however, not optimal. | |
| 479 // Example: | |
| 480 // t1 = foo(); // t1 is now used by `pure`. | |
| 481 // t2 = bar(); // t2 is now used by `f`. | |
| 482 // t3 = pure(t1); | |
| 483 // f(t2, t3); | |
| 484 // use(t3); | |
| 485 // | |
| 486 // If we clear the expected-inputs we can't generate-at-use any of | |
| 487 // the instructions. | |
| 488 // | |
| 489 // The optimal solution is to move the inputs of 'pure' in | |
| 490 // front of the expectedInputs list. This makes sense, since we | |
| 491 // push expected-inputs from left-to right, and the `pure` function | |
| 492 // invocation is "more left" (i.e. before) the first argument of `f`. | |
| 493 // With that approach we end up with: | |
| 494 // t3 = pure(foo(); | |
| 495 // f(bar(), t3); | |
| 496 // use(t3); | |
| 497 // | |
| 498 int oldLength = expectedInputs.length; | |
| 499 instruction.accept(this); | |
| 500 if (oldLength != 0 && oldLength != expectedInputs.length) { | |
| 501 // Move the pure instruction's inputs to the front. | |
| 502 List<HInstruction> newInputs = expectedInputs.sublist(oldLength); | |
| 503 int newCount = newInputs.length; | |
| 504 expectedInputs.setRange( | |
| 505 newCount, newCount + oldLength, expectedInputs); | |
| 506 expectedInputs.setRange(0, newCount, newInputs); | |
| 507 } | |
| 508 } | |
| 509 } else { | |
| 510 if (findInInputsAndPopNonMatching(instruction)) { | |
| 511 // The current instruction is the next non-trivial | |
| 512 // expected input. | |
| 513 tryGenerateAtUseSite(instruction); | |
| 514 } else { | |
| 515 assert(expectedInputs.isEmpty); | |
| 516 } | |
| 517 instruction.accept(this); | |
| 518 } | |
| 519 } | |
| 520 | |
| 521 if (block.predecessors.length == 1 | |
| 522 && isBlockSinglePredecessor(block.predecessors[0])) { | |
| 523 assert(block.phis.isEmpty); | |
| 524 tryMergingExpressions(block.predecessors[0]); | |
| 525 } else { | |
| 526 expectedInputs = null; | |
| 527 pureInputs = null; | |
| 528 } | |
| 529 } | |
| 530 } | |
| 531 | |
| 532 /** | |
| 533 * Detect control flow arising from short-circuit logical and | |
| 534 * conditional operators, and prepare the program to be generated | |
| 535 * using these operators instead of nested ifs and boolean variables. | |
| 536 */ | |
| 537 class SsaConditionMerger extends HGraphVisitor { | |
| 538 Set<HInstruction> generateAtUseSite; | |
| 539 Set<HInstruction> controlFlowOperators; | |
| 540 | |
| 541 void markAsGenerateAtUseSite(HInstruction instruction) { | |
| 542 assert(!instruction.isJsStatement()); | |
| 543 generateAtUseSite.add(instruction); | |
| 544 } | |
| 545 | |
| 546 SsaConditionMerger(this.generateAtUseSite, this.controlFlowOperators); | |
| 547 | |
| 548 void visitGraph(HGraph graph) { | |
| 549 visitPostDominatorTree(graph); | |
| 550 } | |
| 551 | |
| 552 /** | |
| 553 * Check if a block has at least one statement other than | |
| 554 * [instruction]. | |
| 555 */ | |
| 556 bool hasAnyStatement(HBasicBlock block, HInstruction instruction) { | |
| 557 // If [instruction] is not in [block], then if the block is not | |
| 558 // empty, we know there will be a statement to emit. | |
| 559 if (!identical(instruction.block, block)) return !identical(block.last, bloc
k.first); | |
| 560 | |
| 561 // If [instruction] is not the last instruction of the block | |
| 562 // before the control flow instruction, or the last instruction, | |
| 563 // then we will have to emit a statement for that last instruction. | |
| 564 if (instruction != block.last | |
| 565 && !identical(instruction, block.last.previous)) return true; | |
| 566 | |
| 567 // If one of the instructions in the block until [instruction] is | |
| 568 // not generated at use site, then we will have to emit a | |
| 569 // statement for it. | |
| 570 // TODO(ngeoffray): we could generate a comma separated | |
| 571 // list of expressions. | |
| 572 for (HInstruction temp = block.first; | |
| 573 !identical(temp, instruction); | |
| 574 temp = temp.next) { | |
| 575 if (!generateAtUseSite.contains(temp)) return true; | |
| 576 } | |
| 577 | |
| 578 return false; | |
| 579 } | |
| 580 | |
| 581 bool isSafeToGenerateAtUseSite(HInstruction user, HInstruction input) { | |
| 582 // A [HForeign] instruction uses operators and if we generate | |
| 583 // [input] at use site, the precedence might be wrong. | |
| 584 if (user is HForeign) return false; | |
| 585 // A [HCheck] instruction with control flow uses its input | |
| 586 // multiple times, so we avoid generating it at use site. | |
| 587 if (user is HCheck && user.isControlFlow()) return false; | |
| 588 // A [HIs] instruction uses its input multiple times, so we | |
| 589 // avoid generating it at use site. | |
| 590 if (user is HIs) return false; | |
| 591 return true; | |
| 592 } | |
| 593 | |
| 594 void visitBasicBlock(HBasicBlock block) { | |
| 595 if (block.last is !HIf) return; | |
| 596 HIf startIf = block.last; | |
| 597 HBasicBlock end = startIf.joinBlock; | |
| 598 | |
| 599 // We check that the structure is the following: | |
| 600 // If | |
| 601 // / \ | |
| 602 // / \ | |
| 603 // 1 expr goto | |
| 604 // goto / | |
| 605 // \ / | |
| 606 // \ / | |
| 607 // phi(expr, true|false) | |
| 608 // | |
| 609 // and the same for nested nodes: | |
| 610 // | |
| 611 // If | |
| 612 // / \ | |
| 613 // / \ | |
| 614 // 1 expr1 \ | |
| 615 // If \ | |
| 616 // / \ \ | |
| 617 // / \ goto | |
| 618 // 1 expr2 | | |
| 619 // goto goto | | |
| 620 // \ / | | |
| 621 // \ / | | |
| 622 // phi1(expr2, true|false) | |
| 623 // \ | | |
| 624 // \ | | |
| 625 // phi(phi1, true|false) | |
| 626 | |
| 627 if (end == null) return; | |
| 628 if (end.phis.isEmpty) return; | |
| 629 if (!identical(end.phis.first, end.phis.last)) return; | |
| 630 HBasicBlock elseBlock = startIf.elseBlock; | |
| 631 | |
| 632 if (!identical(end.predecessors[1], elseBlock)) return; | |
| 633 HPhi phi = end.phis.first; | |
| 634 HInstruction thenInput = phi.inputs[0]; | |
| 635 HInstruction elseInput = phi.inputs[1]; | |
| 636 if (thenInput.isJsStatement() || elseInput.isJsStatement()) return; | |
| 637 | |
| 638 if (hasAnyStatement(elseBlock, elseInput)) return; | |
| 639 assert(elseBlock.successors.length == 1); | |
| 640 assert(end.predecessors.length == 2); | |
| 641 | |
| 642 HBasicBlock thenBlock = startIf.thenBlock; | |
| 643 // Skip trivial goto blocks. | |
| 644 while (thenBlock.successors[0] != end && thenBlock.first is HGoto) { | |
| 645 thenBlock = thenBlock.successors[0]; | |
| 646 } | |
| 647 | |
| 648 // If the [thenBlock] is already a control flow operation, and does not | |
| 649 // have any statement and its join block is [end], we can emit a | |
| 650 // sequence of control flow operation. | |
| 651 if (controlFlowOperators.contains(thenBlock.last)) { | |
| 652 HIf otherIf = thenBlock.last; | |
| 653 if (!identical(otherIf.joinBlock, end)) { | |
| 654 // This could be a join block that just feeds into our join block. | |
| 655 HBasicBlock otherJoin = otherIf.joinBlock; | |
| 656 if (otherJoin.first != otherJoin.last) return; | |
| 657 if (otherJoin.successors.length != 1) return; | |
| 658 if (otherJoin.successors[0] != end) return; | |
| 659 if (otherJoin.phis.isEmpty) return; | |
| 660 if (!identical(otherJoin.phis.first, otherJoin.phis.last)) return; | |
| 661 HPhi otherPhi = otherJoin.phis.first; | |
| 662 if (thenInput != otherPhi) return; | |
| 663 if (elseInput != otherPhi.inputs[1]) return; | |
| 664 } | |
| 665 if (hasAnyStatement(thenBlock, otherIf)) return; | |
| 666 } else { | |
| 667 if (!identical(end.predecessors[0], thenBlock)) return; | |
| 668 if (hasAnyStatement(thenBlock, thenInput)) return; | |
| 669 assert(thenBlock.successors.length == 1); | |
| 670 } | |
| 671 | |
| 672 // From now on, we have recognized a control flow operation built from | |
| 673 // the builder. Mark the if instruction as such. | |
| 674 controlFlowOperators.add(startIf); | |
| 675 | |
| 676 // Find the next non-HGoto instruction following the phi. | |
| 677 HInstruction nextInstruction = phi.block.first; | |
| 678 while (nextInstruction is HGoto) { | |
| 679 nextInstruction = nextInstruction.block.successors[0].first; | |
| 680 } | |
| 681 | |
| 682 // If the operation is only used by the first instruction | |
| 683 // of its block and is safe to be generated at use site, mark it | |
| 684 // so. | |
| 685 if (phi.usedBy.length == 1 | |
| 686 && phi.usedBy[0] == nextInstruction | |
| 687 && isSafeToGenerateAtUseSite(phi.usedBy[0], phi)) { | |
| 688 markAsGenerateAtUseSite(phi); | |
| 689 } | |
| 690 | |
| 691 if (identical(elseInput.block, elseBlock)) { | |
| 692 assert(elseInput.usedBy.length == 1); | |
| 693 markAsGenerateAtUseSite(elseInput); | |
| 694 } | |
| 695 | |
| 696 // If [thenInput] is defined in the first predecessor, then it is only used | |
| 697 // by [phi] and can be generated at use site. | |
| 698 if (identical(thenInput.block, end.predecessors[0])) { | |
| 699 assert(thenInput.usedBy.length == 1); | |
| 700 markAsGenerateAtUseSite(thenInput); | |
| 701 } | |
| 702 } | |
| 703 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart