| 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 * The [LiveRange] class covers a range where an instruction is live. | 6 * The [LiveRange] class covers a range where an instruction is live. |
| 7 */ | 7 */ |
| 8 class LiveRange { | 8 class LiveRange { |
| 9 final int start; | 9 final int start; |
| 10 // [end] is not final because it can be updated due to loops. | 10 // [end] is not final because it can be updated due to loops. |
| (...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 108 | 108 |
| 109 /** | 109 /** |
| 110 * Remove an instruction from the liveIn set. This method also | 110 * Remove an instruction from the liveIn set. This method also |
| 111 * updates the live interval of [instruction] to contain the new | 111 * updates the live interval of [instruction] to contain the new |
| 112 * range: [id, / id contained in [liveInstructions] /]. | 112 * range: [id, / id contained in [liveInstructions] /]. |
| 113 */ | 113 */ |
| 114 void remove(HInstruction instruction, int id) { | 114 void remove(HInstruction instruction, int id) { |
| 115 // Special case the HCheck instruction to have the same live | 115 // Special case the HCheck instruction to have the same live |
| 116 // interval as the instruction it is checking. | 116 // interval as the instruction it is checking. |
| 117 if (instruction is HCheck) { | 117 if (instruction is HCheck) { |
| 118 HInstruction input = instruction.checkedInput; | 118 var input = instruction.checkedInput; |
| 119 while (input is HCheck) input = input.checkedInput; | 119 while (input is HCheck) input = input.checkedInput; |
| 120 liveIntervals.putIfAbsent(input, () => new LiveInterval()); | 120 liveIntervals.putIfAbsent(input, () => new LiveInterval()); |
| 121 liveIntervals.putIfAbsent(instruction, () => liveIntervals[input]); | 121 liveIntervals.putIfAbsent(instruction, () => liveIntervals[input]); |
| 122 return; | 122 } else { |
| 123 LiveInterval range = liveIntervals.putIfAbsent( |
| 124 instruction, () => new LiveInterval()); |
| 125 int lastId = liveInstructions[instruction]; |
| 126 // If [lastId] is null, then this instruction is not being used. |
| 127 range.add(new LiveRange(id, lastId == null ? id : lastId)); |
| 128 // The instruction is defined at [id]. |
| 129 range.start = id; |
| 123 } | 130 } |
| 124 LiveInterval range = liveIntervals.putIfAbsent( | |
| 125 instruction, () => new LiveInterval()); | |
| 126 int lastId = liveInstructions[instruction]; | |
| 127 // If [lastId] is null, then this instruction is not being used. | |
| 128 range.add(new LiveRange(id, lastId == null ? id : lastId)); | |
| 129 // The instruction is defined at [id]. | |
| 130 range.start = id; | |
| 131 liveInstructions.remove(instruction); | 131 liveInstructions.remove(instruction); |
| 132 } | 132 } |
| 133 | 133 |
| 134 /** | 134 /** |
| 135 * Add [instruction] to the liveIn set. If the instruction is not | 135 * Add [instruction] to the liveIn set. If the instruction is not |
| 136 * already in the set, we save the id where it dies. | 136 * already in the set, we save the id where it dies. |
| 137 */ | 137 */ |
| 138 void add(HInstruction instruction, int userId) { | 138 void add(HInstruction instruction, int userId) { |
| 139 // Special case the HCheck instruction to use the actual checked | |
| 140 // instruction. | |
| 141 while (instruction is HCheck) instruction = instruction.checkedInput; | |
| 142 // Note that we are visiting the grap in post-dominator order, so | 139 // Note that we are visiting the grap in post-dominator order, so |
| 143 // the first time we see a variable is when it dies. | 140 // the first time we see a variable is when it dies. |
| 144 liveInstructions.putIfAbsent(instruction, () => userId); | 141 liveInstructions.putIfAbsent(instruction, () => userId); |
| 142 if (instruction is HCheck) { |
| 143 // Special case the HCheck instruction to mark the actual |
| 144 // checked instruction live. |
| 145 liveInstructions.putIfAbsent(instruction, () => userId); |
| 146 var input = instruction.checkedInput; |
| 147 while (input is HCheck) input = input.checkedInput; |
| 148 liveInstructions.putIfAbsent(input, () => userId); |
| 149 } |
| 145 } | 150 } |
| 146 | 151 |
| 147 /** | 152 /** |
| 148 * Merge this environment with [other]. Update the end id of | 153 * Merge this environment with [other]. Update the end id of |
| 149 * instructions in case they are different between this and [other]. | 154 * instructions in case they are different between this and [other]. |
| 150 */ | 155 */ |
| 151 void mergeWith(LiveEnvironment other) { | 156 void mergeWith(LiveEnvironment other) { |
| 152 other.liveInstructions.forEach((HInstruction instruction, int existingId) { | 157 other.liveInstructions.forEach((HInstruction instruction, int existingId) { |
| 153 // If both environments have the same instruction id of where | 158 // If both environments have the same instruction id of where |
| 154 // [instruction] dies, there is no need to update the live | 159 // [instruction] dies, there is no need to update the live |
| (...skipping 272 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 427 if (user is HPhi && user.sourceElement !== null) { | 432 if (user is HPhi && user.sourceElement !== null) { |
| 428 return user; | 433 return user; |
| 429 } | 434 } |
| 430 } | 435 } |
| 431 return null; | 436 return null; |
| 432 } | 437 } |
| 433 | 438 |
| 434 String allocateName(HInstruction instruction) { | 439 String allocateName(HInstruction instruction) { |
| 435 String name; | 440 String name; |
| 436 if (instruction is HCheck) { | 441 if (instruction is HCheck) { |
| 437 // Special case the check instruction to use the name of its | 442 // Special case this instruction to use the name of its |
| 438 // checked instruction. | 443 // input if it has one. |
| 439 HCheck check = instruction; | 444 var temp = instruction; |
| 440 name = names.ownName[check.checkedInput]; | 445 do { |
| 441 // If the name is null, then the checked input is being | 446 temp = temp.checkedInput; |
| 442 // generated at use site, and we don't need a name for the check | 447 name = names.ownName[temp]; |
| 443 // instruction. | 448 } while (name == null && temp is HCheck); |
| 444 if (name == null) return null; | 449 if (name !== null) return addAllocatedName(instruction, name); |
| 445 } else if (instruction is HParameterValue) { | 450 } else if (instruction is HParameterValue) { |
| 446 HParameterValue parameter = instruction; | 451 HParameterValue parameter = instruction; |
| 447 name = parameterNames[parameter.sourceElement]; | 452 name = parameterNames[parameter.sourceElement]; |
| 448 if (name == null) { | 453 if (name == null) { |
| 449 name = allocateWithHint(parameter.sourceElement.name.slowToString()); | 454 name = allocateWithHint(parameter.sourceElement.name.slowToString()); |
| 450 } | 455 } |
| 451 } else if (instruction.sourceElement !== null) { | 456 return addAllocatedName(instruction, name); |
| 457 } |
| 458 |
| 459 if (instruction.sourceElement !== null) { |
| 452 name = allocateWithHint(instruction.sourceElement.name.slowToString()); | 460 name = allocateWithHint(instruction.sourceElement.name.slowToString()); |
| 453 } else { | 461 } else { |
| 454 // We could not find an element for the instruction. If the | 462 // We could not find an element for the instruction. If the |
| 455 // instruction is used by a phi, try to use the name of the phi. | 463 // instruction is used by a phi, try to use the name of the phi. |
| 456 // Otherwise, just allocate a temporary name. | 464 // Otherwise, just allocate a temporary name. |
| 457 HPhi phi = firstPhiUserWithElement(instruction); | 465 HPhi phi = firstPhiUserWithElement(instruction); |
| 458 if (phi !== null) { | 466 if (phi !== null) { |
| 459 name = allocateWithHint(phi.sourceElement.name.slowToString()); | 467 name = allocateWithHint(phi.sourceElement.name.slowToString()); |
| 460 } else { | 468 } else { |
| 461 name = allocateTemporary(); | 469 name = allocateTemporary(); |
| 462 } | 470 } |
| 463 } | 471 } |
| 472 |
| 473 return addAllocatedName(instruction, name); |
| 474 } |
| 475 |
| 476 String addAllocatedName(HInstruction instruction, String name) { |
| 464 usedNames.add(name); | 477 usedNames.add(name); |
| 465 names.ownName[instruction] = name; | 478 names.ownName[instruction] = name; |
| 466 return name; | 479 return name; |
| 467 } | 480 } |
| 468 | 481 |
| 469 /** | 482 /** |
| 470 * Frees [instruction]'s name so it can be used for other instructions. | 483 * Frees [instruction]'s name so it can be used for other instructions. |
| 471 */ | 484 */ |
| 472 void freeName(HInstruction instruction) { | 485 void freeName(HInstruction instruction) { |
| 473 String ownName = names.ownName[instruction]; | 486 String ownName = names.ownName[instruction]; |
| (...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 527 * Returns whether [instruction] needs a name. Instructions that | 540 * Returns whether [instruction] needs a name. Instructions that |
| 528 * have no users or that are generated at use site does not need a name. | 541 * have no users or that are generated at use site does not need a name. |
| 529 */ | 542 */ |
| 530 bool needsName(HInstruction instruction) { | 543 bool needsName(HInstruction instruction) { |
| 531 if (instruction.usedBy.isEmpty()) return false; | 544 if (instruction.usedBy.isEmpty()) return false; |
| 532 // TODO(ngeoffray): parameters are being generated at use site, | 545 // TODO(ngeoffray): parameters are being generated at use site, |
| 533 // but we need a name for parameters. We should probably not make | 546 // but we need a name for parameters. We should probably not make |
| 534 // them generate at use site to make things simpler. | 547 // them generate at use site to make things simpler. |
| 535 if (instruction is HParameterValue && instruction is !HThis) return true; | 548 if (instruction is HParameterValue && instruction is !HThis) return true; |
| 536 if (generateAtUseSite.contains(instruction)) return false; | 549 if (generateAtUseSite.contains(instruction)) return false; |
| 550 // A [HCheck] instruction that has control flow needs a name only if its |
| 551 // checked input needs a name (e.g. a check [HConstant] does not |
| 552 // need a name). |
| 553 if (instruction is HCheck && instruction.isControlFlow()) { |
| 554 HCheck check = instruction; |
| 555 return needsName(instruction.checkedInput); |
| 556 } |
| 537 return true; | 557 return true; |
| 538 } | 558 } |
| 539 | 559 |
| 540 /** | 560 /** |
| 541 * Returns whether [instruction] dies at the instruction [at]. | 561 * Returns whether [instruction] dies at the instruction [at]. |
| 542 */ | 562 */ |
| 543 bool diesAt(HInstruction instruction, HInstruction at) { | 563 bool diesAt(HInstruction instruction, HInstruction at) { |
| 544 LiveInterval atInterval = liveIntervals[at]; | 564 LiveInterval atInterval = liveIntervals[at]; |
| 545 LiveInterval instructionInterval = liveIntervals[instruction]; | 565 LiveInterval instructionInterval = liveIntervals[instruction]; |
| 546 int start = atInterval.start; | 566 int start = atInterval.start; |
| (...skipping 24 matching lines...) Expand all Loading... |
| 571 if (!needsName(input)) { | 591 if (!needsName(input)) { |
| 572 names.addAssignment(predecessor, input, phi); | 592 names.addAssignment(predecessor, input, phi); |
| 573 } else { | 593 } else { |
| 574 names.addCopy(predecessor, input, phi); | 594 names.addCopy(predecessor, input, phi); |
| 575 } | 595 } |
| 576 } | 596 } |
| 577 | 597 |
| 578 namer.allocateName(phi); | 598 namer.allocateName(phi); |
| 579 } | 599 } |
| 580 } | 600 } |
| OLD | NEW |