| 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 162 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 173 void addLoopMarker(HBasicBlock header, int id) { | 173 void addLoopMarker(HBasicBlock header, int id) { |
| 174 assert(!loopMarkers.containsKey(header)); | 174 assert(!loopMarkers.containsKey(header)); |
| 175 loopMarkers[header] = id; | 175 loopMarkers[header] = id; |
| 176 } | 176 } |
| 177 | 177 |
| 178 void removeLoopMarker(HBasicBlock header) { | 178 void removeLoopMarker(HBasicBlock header) { |
| 179 assert(loopMarkers.containsKey(header)); | 179 assert(loopMarkers.containsKey(header)); |
| 180 loopMarkers.remove(header); | 180 loopMarkers.remove(header); |
| 181 } | 181 } |
| 182 | 182 |
| 183 bool isEmpty() => liveInstructions.isEmpty() && loopMarkers.isEmpty(); | 183 bool get isEmpty => liveInstructions.isEmpty && loopMarkers.isEmpty; |
| 184 bool contains(HInstruction instruction) => | 184 bool contains(HInstruction instruction) => |
| 185 liveInstructions.containsKey(instruction); | 185 liveInstructions.containsKey(instruction); |
| 186 String toString() => liveInstructions.toString(); | 186 String toString() => liveInstructions.toString(); |
| 187 } | 187 } |
| 188 | 188 |
| 189 /** | 189 /** |
| 190 * Builds the live intervals of each instruction. The algorithm visits | 190 * Builds the live intervals of each instruction. The algorithm visits |
| 191 * the graph post-dominator tree to find the last uses of an | 191 * the graph post-dominator tree to find the last uses of an |
| 192 * instruction, and computes the liveIns of each basic block. | 192 * instruction, and computes the liveIns of each basic block. |
| 193 */ | 193 */ |
| (...skipping 18 matching lines...) Expand all Loading... |
| 212 * The live intervals of instructions. | 212 * The live intervals of instructions. |
| 213 */ | 213 */ |
| 214 final Map<HInstruction, LiveInterval> liveIntervals; | 214 final Map<HInstruction, LiveInterval> liveIntervals; |
| 215 | 215 |
| 216 SsaLiveIntervalBuilder(this.compiler, this.generateAtUseSite) | 216 SsaLiveIntervalBuilder(this.compiler, this.generateAtUseSite) |
| 217 : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(), | 217 : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(), |
| 218 liveIntervals = new Map<HInstruction, LiveInterval>(); | 218 liveIntervals = new Map<HInstruction, LiveInterval>(); |
| 219 | 219 |
| 220 void visitGraph(HGraph graph) { | 220 void visitGraph(HGraph graph) { |
| 221 visitPostDominatorTree(graph); | 221 visitPostDominatorTree(graph); |
| 222 if (!liveInstructions[graph.entry].isEmpty()) { | 222 if (!liveInstructions[graph.entry].isEmpty) { |
| 223 compiler.internalError('LiveIntervalBuilder', | 223 compiler.internalError('LiveIntervalBuilder', |
| 224 node: compiler.currentElement.parseNode(compiler)); | 224 node: compiler.currentElement.parseNode(compiler)); |
| 225 } | 225 } |
| 226 } | 226 } |
| 227 | 227 |
| 228 void markInputsAsLiveInEnvironment(HInstruction instruction, | 228 void markInputsAsLiveInEnvironment(HInstruction instruction, |
| 229 LiveEnvironment environment) { | 229 LiveEnvironment environment) { |
| 230 for (int i = 0, len = instruction.inputs.length; i < len; i++) { | 230 for (int i = 0, len = instruction.inputs.length; i < len; i++) { |
| 231 markAsLiveInEnvironment(instruction.inputs[i], environment); | 231 markAsLiveInEnvironment(instruction.inputs[i], environment); |
| 232 } | 232 } |
| (...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 351 | 351 |
| 352 void addCopy(HInstruction source, HInstruction destination) { | 352 void addCopy(HInstruction source, HInstruction destination) { |
| 353 copies.add(new Copy(source, destination)); | 353 copies.add(new Copy(source, destination)); |
| 354 } | 354 } |
| 355 | 355 |
| 356 void addAssignment(HInstruction source, HInstruction destination) { | 356 void addAssignment(HInstruction source, HInstruction destination) { |
| 357 assignments.add(new Copy(source, destination)); | 357 assignments.add(new Copy(source, destination)); |
| 358 } | 358 } |
| 359 | 359 |
| 360 String toString() => 'Copies: $copies, assignments: $assignments'; | 360 String toString() => 'Copies: $copies, assignments: $assignments'; |
| 361 bool isEmpty() => copies.isEmpty() && assignments.isEmpty(); | 361 bool get isEmpty => copies.isEmpty && assignments.isEmpty; |
| 362 } | 362 } |
| 363 | 363 |
| 364 /** | 364 /** |
| 365 * Contains the mapping between instructions and their names for code | 365 * Contains the mapping between instructions and their names for code |
| 366 * generation, as well as the [CopyHandler] for each basic block. | 366 * generation, as well as the [CopyHandler] for each basic block. |
| 367 */ | 367 */ |
| 368 class VariableNames { | 368 class VariableNames { |
| 369 final Map<HInstruction, String> ownName; | 369 final Map<HInstruction, String> ownName; |
| 370 final Map<HBasicBlock, CopyHandler> copyHandlers; | 370 final Map<HBasicBlock, CopyHandler> copyHandlers; |
| 371 /** | 371 /** |
| (...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 451 String allocateWithHint(String originalName) { | 451 String allocateWithHint(String originalName) { |
| 452 int i = 0; | 452 int i = 0; |
| 453 String name = JsNames.getValid(originalName); | 453 String name = JsNames.getValid(originalName); |
| 454 while (usedNames.contains(name)) { | 454 while (usedNames.contains(name)) { |
| 455 name = JsNames.getValid('$originalName${i++}'); | 455 name = JsNames.getValid('$originalName${i++}'); |
| 456 } | 456 } |
| 457 return name; | 457 return name; |
| 458 } | 458 } |
| 459 | 459 |
| 460 String allocateTemporary() { | 460 String allocateTemporary() { |
| 461 while (!freeTemporaryNames.isEmpty()) { | 461 while (!freeTemporaryNames.isEmpty) { |
| 462 String name = freeTemporaryNames.removeLast(); | 462 String name = freeTemporaryNames.removeLast(); |
| 463 if (!usedNames.contains(name)) return name; | 463 if (!usedNames.contains(name)) return name; |
| 464 } | 464 } |
| 465 String name = 't${temporaryIndex++}'; | 465 String name = 't${temporaryIndex++}'; |
| 466 while (usedNames.contains(name)) name = 't${temporaryIndex++}'; | 466 while (usedNames.contains(name)) name = 't${temporaryIndex++}'; |
| 467 return name; | 467 return name; |
| 468 } | 468 } |
| 469 | 469 |
| 470 HPhi firstPhiUserWithElement(HInstruction instruction) { | 470 HPhi firstPhiUserWithElement(HInstruction instruction) { |
| 471 for (HInstruction user in instruction.usedBy) { | 471 for (HInstruction user in instruction.usedBy) { |
| (...skipping 111 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 583 block.forEachInstruction((HInstruction instruction) { | 583 block.forEachInstruction((HInstruction instruction) { |
| 584 handleInstruction(instruction, namer); | 584 handleInstruction(instruction, namer); |
| 585 }); | 585 }); |
| 586 } | 586 } |
| 587 | 587 |
| 588 /** | 588 /** |
| 589 * Returns whether [instruction] needs a name. Instructions that | 589 * Returns whether [instruction] needs a name. Instructions that |
| 590 * have no users or that are generated at use site does not need a name. | 590 * have no users or that are generated at use site does not need a name. |
| 591 */ | 591 */ |
| 592 bool needsName(HInstruction instruction) { | 592 bool needsName(HInstruction instruction) { |
| 593 if (instruction.usedBy.isEmpty()) return false; | 593 if (instruction.usedBy.isEmpty) return false; |
| 594 // TODO(ngeoffray): locals/parameters are being generated at use site, | 594 // TODO(ngeoffray): locals/parameters are being generated at use site, |
| 595 // but we need a name for them. We should probably not make | 595 // but we need a name for them. We should probably not make |
| 596 // them generate at use site to make things simpler. | 596 // them generate at use site to make things simpler. |
| 597 if (instruction is HLocalValue && instruction is !HThis) return true; | 597 if (instruction is HLocalValue && instruction is !HThis) return true; |
| 598 if (generateAtUseSite.contains(instruction)) return false; | 598 if (generateAtUseSite.contains(instruction)) return false; |
| 599 // A [HCheck] instruction that has control flow needs a name only if its | 599 // A [HCheck] instruction that has control flow needs a name only if its |
| 600 // checked input needs a name (e.g. a check [HConstant] does not | 600 // checked input needs a name (e.g. a check [HConstant] does not |
| 601 // need a name). | 601 // need a name). |
| 602 if (instruction is HCheck && instruction.isControlFlow()) { | 602 if (instruction is HCheck && instruction.isControlFlow()) { |
| 603 HCheck check = instruction; | 603 HCheck check = instruction; |
| (...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 650 if (!needsName(input)) { | 650 if (!needsName(input)) { |
| 651 names.addAssignment(predecessor, input, phi); | 651 names.addAssignment(predecessor, input, phi); |
| 652 } else { | 652 } else { |
| 653 names.addCopy(predecessor, input, phi); | 653 names.addCopy(predecessor, input, phi); |
| 654 } | 654 } |
| 655 } | 655 } |
| 656 | 656 |
| 657 namer.allocateName(phi); | 657 namer.allocateName(phi); |
| 658 } | 658 } |
| 659 } | 659 } |
| OLD | NEW |