| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2011, 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 interface OptimizationPhase { | |
| 6 String get name(); | |
| 7 void visitGraph(HGraph graph); | |
| 8 } | |
| 9 | |
| 10 class SsaOptimizerTask extends CompilerTask { | |
| 11 SsaOptimizerTask(Compiler compiler) : super(compiler); | |
| 12 String get name() => 'SSA optimizer'; | |
| 13 | |
| 14 void runPhases(HGraph graph, List<OptimizationPhase> phases) { | |
| 15 for (OptimizationPhase phase in phases) { | |
| 16 phase.visitGraph(graph); | |
| 17 compiler.tracer.traceGraph(phase.name, graph); | |
| 18 } | |
| 19 } | |
| 20 | |
| 21 void optimize(WorkItem work, HGraph graph) { | |
| 22 measure(() { | |
| 23 List<OptimizationPhase> phases = <OptimizationPhase>[ | |
| 24 new SsaConstantFolder(compiler), | |
| 25 new SsaRedundantPhiEliminator(), | |
| 26 new SsaDeadPhiEliminator(), | |
| 27 new SsaGlobalValueNumberer(compiler), | |
| 28 new SsaCodeMotion(), | |
| 29 new SsaDeadCodeEliminator()]; | |
| 30 runPhases(graph, phases); | |
| 31 }); | |
| 32 } | |
| 33 | |
| 34 bool trySpeculativeOptimizations(WorkItem work, HGraph graph) { | |
| 35 return measure(() { | |
| 36 // Run the phases that will generate type guards. We must also run | |
| 37 // [SsaCheckInserter] because the type propagator also propagates | |
| 38 // types non-speculatively. For example, it propagates the type | |
| 39 // array for a call to the List constructor. | |
| 40 List<OptimizationPhase> phases = <OptimizationPhase>[ | |
| 41 new SsaTypePropagator(compiler), | |
| 42 new SsaTypeGuardBuilder(compiler, work), | |
| 43 new SsaCheckInserter(compiler)]; | |
| 44 runPhases(graph, phases); | |
| 45 return !work.guards.isEmpty(); | |
| 46 }); | |
| 47 } | |
| 48 | |
| 49 void prepareForSpeculativeOptimizations(WorkItem work, HGraph graph) { | |
| 50 measure(() { | |
| 51 // In order to generate correct code for the bailout version, we did not | |
| 52 // propagate types from the instruction to the type guard. We do it | |
| 53 // now to be able to optimize further. | |
| 54 work.guards.forEach((HTypeGuard guard) { | |
| 55 guard.type = guard.guarded.type; | |
| 56 guard.guarded.type = HType.UNKNOWN; | |
| 57 }); | |
| 58 // We also need to insert range and integer checks for the type guards, | |
| 59 // now that they know their type. We did not need to do that | |
| 60 // before because instructions that reference a guard would | |
| 61 // have not tried to use, e.g. native array access, since the | |
| 62 // guard was not typed. | |
| 63 runPhases(graph, <OptimizationPhase>[new SsaCheckInserter(compiler)]); | |
| 64 }); | |
| 65 } | |
| 66 } | |
| 67 | |
| 68 /** | |
| 69 * If both inputs to known operations are available execute the operation at | |
| 70 * compile-time. | |
| 71 */ | |
| 72 class SsaConstantFolder extends HBaseVisitor implements OptimizationPhase { | |
| 73 final String name = "SsaConstantFolder"; | |
| 74 final Compiler compiler; | |
| 75 HGraph graph; | |
| 76 | |
| 77 SsaConstantFolder(this.compiler); | |
| 78 | |
| 79 void visitGraph(HGraph graph) { | |
| 80 this.graph = graph; | |
| 81 visitDominatorTree(graph); | |
| 82 } | |
| 83 | |
| 84 visitBasicBlock(HBasicBlock block) { | |
| 85 HInstruction instruction = block.first; | |
| 86 while (instruction !== null) { | |
| 87 HInstruction next = instruction.next; | |
| 88 HInstruction replacement = instruction.accept(this); | |
| 89 if (replacement !== instruction) { | |
| 90 if (!replacement.isInBasicBlock()) { | |
| 91 // The constant folding can return an instruction that is already | |
| 92 // part of the graph (like an input), so we only add the replacement | |
| 93 // if necessary. | |
| 94 block.addAfter(instruction, replacement); | |
| 95 } | |
| 96 block.rewrite(instruction, replacement); | |
| 97 block.remove(instruction); | |
| 98 // Because the constant folder runs after type propagation, we | |
| 99 // must update the type of this instruction manually. Later | |
| 100 // phases can then optimize this instruction based on its | |
| 101 // type. | |
| 102 replacement.updateType(); | |
| 103 } | |
| 104 instruction = next; | |
| 105 } | |
| 106 } | |
| 107 | |
| 108 HInstruction visitInstruction(HInstruction node) { | |
| 109 return node; | |
| 110 } | |
| 111 | |
| 112 HInstruction visitBoolify(HBoolify node) { | |
| 113 List<HInstruction> inputs = node.inputs; | |
| 114 assert(inputs.length == 1); | |
| 115 HInstruction input = inputs[0]; | |
| 116 if (input.isBoolean()) return input; | |
| 117 // All values !== true are boolified to false. | |
| 118 if (input.type.isKnown()) { | |
| 119 return graph.addConstantBool(false); | |
| 120 } | |
| 121 return node; | |
| 122 } | |
| 123 | |
| 124 HInstruction visitNot(HNot node) { | |
| 125 List<HInstruction> inputs = node.inputs; | |
| 126 assert(inputs.length == 1); | |
| 127 HInstruction input = inputs[0]; | |
| 128 if (input is HConstant) { | |
| 129 HConstant constant = input; | |
| 130 bool isTrue = constant.constant.isTrue(); | |
| 131 return graph.addConstantBool(!isTrue); | |
| 132 } | |
| 133 return node; | |
| 134 } | |
| 135 | |
| 136 HInstruction visitInvokeUnary(HInvokeUnary node) { | |
| 137 HInstruction operand = node.operand; | |
| 138 if (operand is HConstant) { | |
| 139 UnaryOperation operation = node.operation; | |
| 140 HConstant receiver = operand; | |
| 141 Constant folded = operation.fold(receiver.constant); | |
| 142 if (folded !== null) return graph.addConstant(folded); | |
| 143 } | |
| 144 return node; | |
| 145 } | |
| 146 | |
| 147 HInstruction visitInvokeInterceptor(HInvokeInterceptor node) { | |
| 148 if (node.name == const SourceString('length') && | |
| 149 node.inputs[1].isConstantString()) { | |
| 150 HConstant input = node.inputs[1]; | |
| 151 StringConstant constant = input.constant; | |
| 152 DartString string = constant.value; | |
| 153 return graph.addConstantInt(string.length); | |
| 154 } | |
| 155 return node; | |
| 156 } | |
| 157 | |
| 158 HInstruction visitInvokeBinary(HInvokeBinary node) { | |
| 159 HInstruction left = node.left; | |
| 160 HInstruction right = node.right; | |
| 161 if (left is HConstant && right is HConstant) { | |
| 162 BinaryOperation operation = node.operation; | |
| 163 HConstant op1 = left; | |
| 164 HConstant op2 = right; | |
| 165 Constant folded = operation.fold(op1.constant, op2.constant); | |
| 166 if (folded !== null) return graph.addConstant(folded); | |
| 167 } | |
| 168 return node; | |
| 169 } | |
| 170 | |
| 171 HInstruction visitEquals(HEquals node) { | |
| 172 HInstruction left = node.left; | |
| 173 HInstruction right = node.right; | |
| 174 if (!left.isConstant() && right.isConstantNull()) { | |
| 175 // TODO(floitsch): cache interceptors. | |
| 176 HStatic target = new HStatic( | |
| 177 compiler.builder.interceptors.getEqualsNullInterceptor()); | |
| 178 node.block.addBefore(node,target); | |
| 179 return new HEquals(target, node.left, node.right); | |
| 180 } | |
| 181 // All other cases are dealt with by the [visitInvokeBinary]. | |
| 182 return visitInvokeBinary(node); | |
| 183 } | |
| 184 | |
| 185 HInstruction visitTypeGuard(HTypeGuard node) { | |
| 186 HInstruction value = node.guarded; | |
| 187 return (value.type.combine(node.type) == value.type) ? value : node; | |
| 188 } | |
| 189 | |
| 190 HInstruction visitIntegerCheck(HIntegerCheck node) { | |
| 191 HInstruction value = node.value; | |
| 192 return value.isInteger() ? value : node; | |
| 193 } | |
| 194 | |
| 195 HInstruction visitIs(HIs node) { | |
| 196 Element element = node.typeExpression; | |
| 197 if (element.kind === ElementKind.TYPE_VARIABLE) { | |
| 198 compiler.unimplemented("visitIs for type variables"); | |
| 199 } | |
| 200 | |
| 201 HType expressionType = node.expression.type; | |
| 202 if (element === compiler.objectClass | |
| 203 || element === compiler.dynamicClass) { | |
| 204 return graph.addConstantBool(true); | |
| 205 } else if (expressionType.isInteger()) { | |
| 206 if (element === compiler.intClass || element === compiler.numClass) { | |
| 207 return graph.addConstantBool(true); | |
| 208 } else if (element === compiler.doubleClass) { | |
| 209 // We let the JS semantics decide for that check. Currently | |
| 210 // the code we emit will always return true. | |
| 211 return node; | |
| 212 } else { | |
| 213 return graph.addConstantBool(false); | |
| 214 } | |
| 215 } else if (expressionType.isDouble()) { | |
| 216 if (element === compiler.doubleClass || element === compiler.numClass) { | |
| 217 return graph.addConstantBool(true); | |
| 218 } else if (element === compiler.intClass) { | |
| 219 // We let the JS semantics decide for that check. Currently | |
| 220 // the code we emit will return true for a double that can be | |
| 221 // represented as a 31-bit integer. | |
| 222 return node; | |
| 223 } else { | |
| 224 return graph.addConstantBool(false); | |
| 225 } | |
| 226 } else if (expressionType.isNumber()) { | |
| 227 if (element === compiler.numClass) { | |
| 228 return graph.addConstantBool(true); | |
| 229 } | |
| 230 // We cannot just return false, because the expression may be of | |
| 231 // type int or double. | |
| 232 } else if (expressionType.isString()) { | |
| 233 if (element === compiler.stringClass | |
| 234 || Elements.isStringSupertype(element, compiler)) { | |
| 235 return graph.addConstantBool(true); | |
| 236 } else { | |
| 237 return graph.addConstantBool(false); | |
| 238 } | |
| 239 } else if (expressionType.isArray()) { | |
| 240 if (element === compiler.listClass | |
| 241 || Elements.isListSupertype(element, compiler)) { | |
| 242 return graph.addConstantBool(true); | |
| 243 } else { | |
| 244 return graph.addConstantBool(false); | |
| 245 } | |
| 246 } | |
| 247 return node; | |
| 248 } | |
| 249 } | |
| 250 | |
| 251 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase { | |
| 252 final String name = "SsaCheckInserter"; | |
| 253 Element lengthInterceptor; | |
| 254 | |
| 255 SsaCheckInserter(Compiler compiler) { | |
| 256 SourceString lengthString = const SourceString('length'); | |
| 257 lengthInterceptor = | |
| 258 compiler.builder.interceptors.getStaticGetInterceptor(lengthString); | |
| 259 } | |
| 260 | |
| 261 void visitGraph(HGraph graph) { | |
| 262 visitDominatorTree(graph); | |
| 263 } | |
| 264 | |
| 265 void visitBasicBlock(HBasicBlock block) { | |
| 266 HInstruction instruction = block.first; | |
| 267 while (instruction !== null) { | |
| 268 HInstruction next = instruction.next; | |
| 269 instruction = instruction.accept(this); | |
| 270 instruction = next; | |
| 271 } | |
| 272 } | |
| 273 | |
| 274 HBoundsCheck insertBoundsCheck(HInstruction node, | |
| 275 HInstruction receiver, | |
| 276 HInstruction index) { | |
| 277 HStatic interceptor = new HStatic(lengthInterceptor); | |
| 278 node.block.addBefore(node, interceptor); | |
| 279 HInvokeInterceptor length = new HInvokeInterceptor( | |
| 280 Selector.INVOCATION_0, | |
| 281 const SourceString("length"), | |
| 282 true, | |
| 283 <HInstruction>[interceptor, receiver]); | |
| 284 length.type = HType.NUMBER; | |
| 285 node.block.addBefore(node, length); | |
| 286 | |
| 287 HBoundsCheck check = new HBoundsCheck(length, index); | |
| 288 node.block.addBefore(node, check); | |
| 289 return check; | |
| 290 } | |
| 291 | |
| 292 HIntegerCheck insertIntegerCheck(HInstruction node, HInstruction value) { | |
| 293 HIntegerCheck check = new HIntegerCheck(value); | |
| 294 node.block.addBefore(node, check); | |
| 295 return check; | |
| 296 } | |
| 297 | |
| 298 void visitIndex(HIndex node) { | |
| 299 if (!node.builtin) return; | |
| 300 HInstruction index = insertIntegerCheck(node, node.index); | |
| 301 index = insertBoundsCheck(node, node.receiver, index); | |
| 302 HIndex newInstruction = new HIndex(node.target, node.receiver, index); | |
| 303 node.block.addBefore(node, newInstruction); | |
| 304 node.block.rewrite(node, newInstruction); | |
| 305 node.block.remove(node); | |
| 306 } | |
| 307 | |
| 308 void visitIndexAssign(HIndexAssign node) { | |
| 309 if (!node.builtin) return; | |
| 310 HInstruction index = insertIntegerCheck(node, node.index); | |
| 311 index = insertBoundsCheck(node, node.receiver, index); | |
| 312 HIndexAssign newInstruction = | |
| 313 new HIndexAssign(node.target, node.receiver, index, node.value); | |
| 314 node.block.addBefore(node, newInstruction); | |
| 315 node.block.rewrite(node, newInstruction); | |
| 316 node.block.remove(node); | |
| 317 } | |
| 318 } | |
| 319 | |
| 320 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase { | |
| 321 final String name = "SsaDeadCodeEliminator"; | |
| 322 | |
| 323 static bool isDeadCode(HInstruction instruction) { | |
| 324 // TODO(ngeoffray): the way we handle side effects is not right | |
| 325 // (e.g. branching instructions have side effects). | |
| 326 return !instruction.hasSideEffects() | |
| 327 && instruction.usedBy.isEmpty() | |
| 328 && instruction is !HCheck | |
| 329 && instruction is !HTypeGuard; | |
| 330 } | |
| 331 | |
| 332 void visitGraph(HGraph graph) { | |
| 333 visitPostDominatorTree(graph); | |
| 334 } | |
| 335 | |
| 336 void visitBasicBlock(HBasicBlock block) { | |
| 337 HInstruction instruction = block.last; | |
| 338 while (instruction !== null) { | |
| 339 var previous = instruction.previous; | |
| 340 if (isDeadCode(instruction)) block.remove(instruction); | |
| 341 instruction = previous; | |
| 342 } | |
| 343 } | |
| 344 } | |
| 345 | |
| 346 class SsaDeadPhiEliminator implements OptimizationPhase { | |
| 347 final String name = "SsaDeadPhiEliminator"; | |
| 348 | |
| 349 void visitGraph(HGraph graph) { | |
| 350 final List<HPhi> worklist = <HPhi>[]; | |
| 351 // A set to keep track of the live phis that we found. | |
| 352 final Set<HPhi> livePhis = new Set<HPhi>(); | |
| 353 | |
| 354 // Add to the worklist all live phis: phis referenced by non-phi | |
| 355 // instructions. | |
| 356 for (final block in graph.blocks) { | |
| 357 block.forEachPhi((HPhi phi) { | |
| 358 for (final user in phi.usedBy) { | |
| 359 if (user is !HPhi) { | |
| 360 worklist.add(phi); | |
| 361 livePhis.add(phi); | |
| 362 break; | |
| 363 } | |
| 364 } | |
| 365 }); | |
| 366 } | |
| 367 | |
| 368 // Process the worklist by propagating liveness to phi inputs. | |
| 369 while (!worklist.isEmpty()) { | |
| 370 HPhi phi = worklist.removeLast(); | |
| 371 for (final input in phi.inputs) { | |
| 372 if (input is HPhi && !livePhis.contains(input)) { | |
| 373 worklist.add(input); | |
| 374 livePhis.add(input); | |
| 375 } | |
| 376 } | |
| 377 } | |
| 378 | |
| 379 // Remove phis that are not live. | |
| 380 // Traverse in reverse order to remove phis with no uses before the | |
| 381 // phis that they might use. | |
| 382 // NOTICE: Doesn't handle circular references, but we don't currently | |
| 383 // create any. | |
| 384 List<HBasicBlock> blocks = graph.blocks; | |
| 385 for (int i = blocks.length - 1; i >= 0; i--) { | |
| 386 HBasicBlock block = blocks[i]; | |
| 387 HPhi current = block.phis.first; | |
| 388 HPhi next = null; | |
| 389 while (current != null) { | |
| 390 next = current.next; | |
| 391 if (!livePhis.contains(current) | |
| 392 // TODO(ahe): Not sure the following is correct. | |
| 393 && current.usedBy.isEmpty()) { | |
| 394 block.removePhi(current); | |
| 395 } | |
| 396 current = next; | |
| 397 } | |
| 398 } | |
| 399 } | |
| 400 } | |
| 401 | |
| 402 class SsaRedundantPhiEliminator implements OptimizationPhase { | |
| 403 final String name = "SsaRedundantPhiEliminator"; | |
| 404 | |
| 405 void visitGraph(HGraph graph) { | |
| 406 final List<HPhi> worklist = <HPhi>[]; | |
| 407 | |
| 408 // Add all phis in the worklist. | |
| 409 for (final block in graph.blocks) { | |
| 410 block.forEachPhi((HPhi phi) => worklist.add(phi)); | |
| 411 } | |
| 412 | |
| 413 while (!worklist.isEmpty()) { | |
| 414 HPhi phi = worklist.removeLast(); | |
| 415 | |
| 416 // If the phi has already been processed, continue. | |
| 417 if (!phi.isInBasicBlock()) continue; | |
| 418 | |
| 419 // Find if the inputs of the phi are the same instruction. | |
| 420 // The builder ensures that phi.inputs[0] cannot be the phi | |
| 421 // itself. | |
| 422 assert(phi.inputs[0] !== phi); | |
| 423 HInstruction candidate = phi.inputs[0]; | |
| 424 for (int i = 1; i < phi.inputs.length; i++) { | |
| 425 HInstruction input = phi.inputs[i]; | |
| 426 // If the input is the phi, the phi is still candidate for | |
| 427 // elimination. | |
| 428 if (input !== candidate && input !== phi) { | |
| 429 candidate = null; | |
| 430 break; | |
| 431 } | |
| 432 } | |
| 433 | |
| 434 // If the inputs are not the same, continue. | |
| 435 if (candidate == null) continue; | |
| 436 | |
| 437 // Because we're updating the users of this phi, we may have new | |
| 438 // phis candidate for elimination. Add phis that used this phi | |
| 439 // to the worklist. | |
| 440 for (final user in phi.usedBy) { | |
| 441 if (user is HPhi) worklist.add(user); | |
| 442 } | |
| 443 phi.block.rewrite(phi, candidate); | |
| 444 phi.block.removePhi(phi); | |
| 445 } | |
| 446 } | |
| 447 } | |
| 448 | |
| 449 class SsaGlobalValueNumberer implements OptimizationPhase { | |
| 450 final String name = "SsaGlobalValueNumberer"; | |
| 451 final Compiler compiler; | |
| 452 final Set<int> visited; | |
| 453 | |
| 454 List<int> blockChangesFlags; | |
| 455 List<int> loopChangesFlags; | |
| 456 | |
| 457 SsaGlobalValueNumberer(this.compiler) : visited = new Set<int>(); | |
| 458 | |
| 459 void visitGraph(HGraph graph) { | |
| 460 computeChangesFlags(graph); | |
| 461 moveLoopInvariantCode(graph); | |
| 462 visitBasicBlock(graph.entry, new ValueSet()); | |
| 463 } | |
| 464 | |
| 465 void moveLoopInvariantCode(HGraph graph) { | |
| 466 for (int i = graph.blocks.length - 1; i >= 0; i--) { | |
| 467 HBasicBlock block = graph.blocks[i]; | |
| 468 if (block.isLoopHeader()) { | |
| 469 int changesFlags = loopChangesFlags[block.id]; | |
| 470 HBasicBlock last = block.loopInformation.getLastBackEdge(); | |
| 471 for (int j = block.id; j <= last.id; j++) { | |
| 472 moveLoopInvariantCodeFromBlock(graph.blocks[j], block, changesFlags); | |
| 473 } | |
| 474 } | |
| 475 } | |
| 476 } | |
| 477 | |
| 478 void moveLoopInvariantCodeFromBlock(HBasicBlock block, | |
| 479 HBasicBlock loopHeader, | |
| 480 int changesFlags) { | |
| 481 HBasicBlock preheader = loopHeader.predecessors[0]; | |
| 482 int dependsFlags = HInstruction.computeDependsOnFlags(changesFlags); | |
| 483 HInstruction instruction = block.first; | |
| 484 while (instruction != null) { | |
| 485 HInstruction next = instruction.next; | |
| 486 if (instruction.useGvn() | |
| 487 && (instruction is !HCheck) | |
| 488 && (instruction.flags & dependsFlags) == 0) { | |
| 489 bool loopInvariantInputs = true; | |
| 490 List<HInstruction> inputs = instruction.inputs; | |
| 491 for (int i = 0, length = inputs.length; i < length; i++) { | |
| 492 if (isInputDefinedAfterDominator(inputs[i], preheader)) { | |
| 493 loopInvariantInputs = false; | |
| 494 break; | |
| 495 } | |
| 496 } | |
| 497 | |
| 498 // If the inputs are loop invariant, we can move the | |
| 499 // instruction from the current block to the pre-header block. | |
| 500 if (loopInvariantInputs) { | |
| 501 block.detach(instruction); | |
| 502 preheader.moveAtExit(instruction); | |
| 503 } | |
| 504 } | |
| 505 instruction = next; | |
| 506 } | |
| 507 } | |
| 508 | |
| 509 bool isInputDefinedAfterDominator(HInstruction input, | |
| 510 HBasicBlock dominator) { | |
| 511 return input.block.id > dominator.id; | |
| 512 } | |
| 513 | |
| 514 void visitBasicBlock(HBasicBlock block, ValueSet values) { | |
| 515 HInstruction instruction = block.first; | |
| 516 while (instruction !== null) { | |
| 517 HInstruction next = instruction.next; | |
| 518 int flags = instruction.getChangesFlags(); | |
| 519 if (flags != 0) { | |
| 520 assert(!instruction.useGvn()); | |
| 521 values.kill(flags); | |
| 522 } else if (instruction.useGvn()) { | |
| 523 HInstruction other = values.lookup(instruction); | |
| 524 if (other !== null) { | |
| 525 assert(other.gvnEquals(instruction) && instruction.gvnEquals(other)); | |
| 526 block.rewrite(instruction, other); | |
| 527 block.remove(instruction); | |
| 528 } else { | |
| 529 values.add(instruction); | |
| 530 } | |
| 531 } | |
| 532 instruction = next; | |
| 533 } | |
| 534 | |
| 535 List<HBasicBlock> dominatedBlocks = block.dominatedBlocks; | |
| 536 for (int i = 0, length = dominatedBlocks.length; i < length; i++) { | |
| 537 HBasicBlock dominated = dominatedBlocks[i]; | |
| 538 // No need to copy the value set for the last child. | |
| 539 ValueSet successorValues = (i == length - 1) ? values : values.copy(); | |
| 540 // If we have no values in our set, we do not have to kill | |
| 541 // anything. Also, if the range of block ids from the current | |
| 542 // block to the dominated block is empty, there is no blocks on | |
| 543 // any path from the current block to the dominated block so we | |
| 544 // don't have to do anything either. | |
| 545 assert(block.id < dominated.id); | |
| 546 if (!successorValues.isEmpty() && block.id + 1 < dominated.id) { | |
| 547 visited.clear(); | |
| 548 int changesFlags = getChangesFlagsForDominatedBlock(block, dominated); | |
| 549 successorValues.kill(changesFlags); | |
| 550 } | |
| 551 visitBasicBlock(dominated, successorValues); | |
| 552 } | |
| 553 } | |
| 554 | |
| 555 void computeChangesFlags(HGraph graph) { | |
| 556 // Create the changes flags lists. Make sure to initialize the | |
| 557 // loop changes flags list to zero so we can use bitwise or when | |
| 558 // propagating loop changes upwards. | |
| 559 final int length = graph.blocks.length; | |
| 560 blockChangesFlags = new List<int>(length); | |
| 561 loopChangesFlags = new List<int>(length); | |
| 562 for (int i = 0; i < length; i++) loopChangesFlags[i] = 0; | |
| 563 | |
| 564 // Run through all the basic blocks in the graph and fill in the | |
| 565 // changes flags lists. | |
| 566 for (int i = length - 1; i >= 0; i--) { | |
| 567 final HBasicBlock block = graph.blocks[i]; | |
| 568 final int id = block.id; | |
| 569 | |
| 570 // Compute block changes flags for the block. | |
| 571 int changesFlags = 0; | |
| 572 HInstruction instruction = block.first; | |
| 573 while (instruction !== null) { | |
| 574 instruction.prepareGvn(); | |
| 575 changesFlags |= instruction.getChangesFlags(); | |
| 576 instruction = instruction.next; | |
| 577 } | |
| 578 assert(blockChangesFlags[id] === null); | |
| 579 blockChangesFlags[id] = changesFlags; | |
| 580 | |
| 581 // Loop headers are part of their loop, so update the loop | |
| 582 // changes flags accordingly. | |
| 583 if (block.isLoopHeader()) { | |
| 584 loopChangesFlags[id] |= changesFlags; | |
| 585 } | |
| 586 | |
| 587 // Propagate loop changes flags upwards. | |
| 588 HBasicBlock parentLoopHeader = block.parentLoopHeader; | |
| 589 if (parentLoopHeader !== null) { | |
| 590 loopChangesFlags[parentLoopHeader.id] |= (block.isLoopHeader()) | |
| 591 ? loopChangesFlags[id] | |
| 592 : changesFlags; | |
| 593 } | |
| 594 } | |
| 595 } | |
| 596 | |
| 597 int getChangesFlagsForDominatedBlock(HBasicBlock dominator, | |
| 598 HBasicBlock dominated) { | |
| 599 int changesFlags = 0; | |
| 600 List<HBasicBlock> predecessors = dominated.predecessors; | |
| 601 for (int i = 0, length = predecessors.length; i < length; i++) { | |
| 602 HBasicBlock block = predecessors[i]; | |
| 603 int id = block.id; | |
| 604 // If the current predecessor block is on the path from the | |
| 605 // dominator to the dominated, it must have an id that is in the | |
| 606 // range from the dominator to the dominated. | |
| 607 if (dominator.id < id && id < dominated.id && !visited.contains(id)) { | |
| 608 visited.add(id); | |
| 609 changesFlags |= blockChangesFlags[id]; | |
| 610 changesFlags |= getChangesFlagsForDominatedBlock(dominator, block); | |
| 611 } | |
| 612 } | |
| 613 return changesFlags; | |
| 614 } | |
| 615 } | |
| 616 | |
| 617 // This phase merges equivalent instructions on different paths into | |
| 618 // one instruction in a dominator block. It runs through the graph | |
| 619 // post dominator order and computes a ValueSet for each block of | |
| 620 // instructions that can be moved to a dominator block. These | |
| 621 // instructions are the ones that: | |
| 622 // 1) can be used for GVN, and | |
| 623 // 2) do not use definitions of their own block. | |
| 624 // | |
| 625 // A basic block looks at its sucessors and finds the intersection of | |
| 626 // these computed ValueSet. It moves all instructions of the | |
| 627 // intersection into its own list of instructions. | |
| 628 class SsaCodeMotion extends HBaseVisitor implements OptimizationPhase { | |
| 629 final String name = "SsaCodeMotion"; | |
| 630 | |
| 631 List<ValueSet> values; | |
| 632 | |
| 633 void visitGraph(HGraph graph) { | |
| 634 values = new List<ValueSet>(graph.blocks.length); | |
| 635 for (int i = 0; i < graph.blocks.length; i++) { | |
| 636 values[graph.blocks[i].id] = new ValueSet(); | |
| 637 } | |
| 638 visitPostDominatorTree(graph); | |
| 639 } | |
| 640 | |
| 641 void visitBasicBlock(HBasicBlock block) { | |
| 642 List<HBasicBlock> successors = block.successors; | |
| 643 | |
| 644 // Phase 1: get the ValueSet of all successors, compute the | |
| 645 // intersection and move the instructions of the intersection into | |
| 646 // this block. | |
| 647 if (successors.length != 0) { | |
| 648 ValueSet instructions = values[successors[0].id]; | |
| 649 for (int i = 1; i < successors.length; i++) { | |
| 650 ValueSet other = values[successors[i].id]; | |
| 651 instructions = instructions.intersection(other); | |
| 652 } | |
| 653 | |
| 654 if (!instructions.isEmpty()) { | |
| 655 List<HInstruction> list = instructions.toList(); | |
| 656 for (HInstruction instruction in list) { | |
| 657 // Move the instruction to the current block. | |
| 658 instruction.block.detach(instruction); | |
| 659 block.moveAtExit(instruction); | |
| 660 // Go through all successors and rewrite their instruction | |
| 661 // to the shared one. | |
| 662 for (final successor in successors) { | |
| 663 HInstruction toRewrite = values[successor.id].lookup(instruction); | |
| 664 if (toRewrite != instruction) { | |
| 665 successor.rewrite(toRewrite, instruction); | |
| 666 successor.remove(toRewrite); | |
| 667 } | |
| 668 } | |
| 669 } | |
| 670 } | |
| 671 } | |
| 672 | |
| 673 // Don't try to merge instructions to a dominator if we have | |
| 674 // multiple predecessors. | |
| 675 if (block.predecessors.length != 1) return; | |
| 676 | |
| 677 // Phase 2: Go through all instructions of this block and find | |
| 678 // which instructions can be moved to a dominator block. | |
| 679 ValueSet set_ = values[block.id]; | |
| 680 HInstruction instruction = block.first; | |
| 681 int flags = 0; | |
| 682 while (instruction !== null) { | |
| 683 int dependsFlags = HInstruction.computeDependsOnFlags(flags); | |
| 684 flags |= instruction.getChangesFlags(); | |
| 685 | |
| 686 HInstruction current = instruction; | |
| 687 instruction = instruction.next; | |
| 688 | |
| 689 // TODO(ngeoffray): this check is needed because we currently do | |
| 690 // not have flags to express 'Gvn'able', but not movable. | |
| 691 if (current is HCheck) continue; | |
| 692 if (!current.useGvn()) continue; | |
| 693 if ((current.flags & dependsFlags) != 0) continue; | |
| 694 | |
| 695 bool canBeMoved = true; | |
| 696 for (final HInstruction input in current.inputs) { | |
| 697 if (input.block == block) { | |
| 698 canBeMoved = false; | |
| 699 break; | |
| 700 } | |
| 701 } | |
| 702 if (!canBeMoved) continue; | |
| 703 | |
| 704 // This is safe because we are running after GVN. | |
| 705 // TODO(ngeoffray): ensure GVN has been run. | |
| 706 set_.add(current); | |
| 707 } | |
| 708 } | |
| 709 } | |
| 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/