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 |