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 |