| 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 import '../common.dart'; | 5 import '../common.dart'; |
| 6 import '../compiler.dart' show Compiler; | 6 import '../compiler.dart' show Compiler; |
| 7 import '../js_backend/js_backend.dart'; | 7 import '../js_backend/js_backend.dart'; |
| 8 import 'nodes.dart'; | 8 import 'nodes.dart'; |
| 9 | 9 |
| 10 /** | 10 /** |
| (...skipping 169 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 180 liveInstructions.containsKey(instruction); | 180 liveInstructions.containsKey(instruction); |
| 181 String toString() => liveInstructions.toString(); | 181 String toString() => liveInstructions.toString(); |
| 182 } | 182 } |
| 183 | 183 |
| 184 /** | 184 /** |
| 185 * Builds the live intervals of each instruction. The algorithm visits | 185 * Builds the live intervals of each instruction. The algorithm visits |
| 186 * the graph post-dominator tree to find the last uses of an | 186 * the graph post-dominator tree to find the last uses of an |
| 187 * instruction, and computes the liveIns of each basic block. | 187 * instruction, and computes the liveIns of each basic block. |
| 188 */ | 188 */ |
| 189 class SsaLiveIntervalBuilder extends HBaseVisitor { | 189 class SsaLiveIntervalBuilder extends HBaseVisitor { |
| 190 final Compiler compiler; | |
| 191 final Set<HInstruction> generateAtUseSite; | 190 final Set<HInstruction> generateAtUseSite; |
| 192 final Set<HInstruction> controlFlowOperators; | 191 final Set<HInstruction> controlFlowOperators; |
| 193 | 192 |
| 194 /** | 193 /** |
| 195 * A counter to assign start and end ids to live ranges. The initial | 194 * A counter to assign start and end ids to live ranges. The initial |
| 196 * value is not relevant. Note that instructionId goes downward to ease | 195 * value is not relevant. Note that instructionId goes downward to ease |
| 197 * reasoning about live ranges (the first instruction of a graph has | 196 * reasoning about live ranges (the first instruction of a graph has |
| 198 * the lowest id). | 197 * the lowest id). |
| 199 */ | 198 */ |
| 200 int instructionId = 0; | 199 int instructionId = 0; |
| 201 | 200 |
| 202 /** | 201 /** |
| 203 * The liveIns of basic blocks. | 202 * The liveIns of basic blocks. |
| 204 */ | 203 */ |
| 205 final Map<HBasicBlock, LiveEnvironment> liveInstructions; | 204 final Map<HBasicBlock, LiveEnvironment> liveInstructions; |
| 206 | 205 |
| 207 /** | 206 /** |
| 208 * The live intervals of instructions. | 207 * The live intervals of instructions. |
| 209 */ | 208 */ |
| 210 final Map<HInstruction, LiveInterval> liveIntervals; | 209 final Map<HInstruction, LiveInterval> liveIntervals; |
| 211 | 210 |
| 212 SsaLiveIntervalBuilder( | 211 SsaLiveIntervalBuilder(this.generateAtUseSite, this.controlFlowOperators) |
| 213 this.compiler, this.generateAtUseSite, this.controlFlowOperators) | |
| 214 : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(), | 212 : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(), |
| 215 liveIntervals = new Map<HInstruction, LiveInterval>(); | 213 liveIntervals = new Map<HInstruction, LiveInterval>(); |
| 216 | 214 |
| 217 DiagnosticReporter get reporter => compiler.reporter; | |
| 218 | |
| 219 void visitGraph(HGraph graph) { | 215 void visitGraph(HGraph graph) { |
| 220 visitPostDominatorTree(graph); | 216 visitPostDominatorTree(graph); |
| 221 if (!liveInstructions[graph.entry].isEmpty) { | 217 if (!liveInstructions[graph.entry].isEmpty) { |
| 222 reporter.internalError(CURRENT_ELEMENT_SPANNABLE, 'LiveIntervalBuilder.'); | 218 throw new SpannableAssertionFailure( |
| 219 CURRENT_ELEMENT_SPANNABLE, 'LiveIntervalBuilder.'); |
| 223 } | 220 } |
| 224 } | 221 } |
| 225 | 222 |
| 226 void markInputsAsLiveInEnvironment( | 223 void markInputsAsLiveInEnvironment( |
| 227 HInstruction instruction, LiveEnvironment environment) { | 224 HInstruction instruction, LiveEnvironment environment) { |
| 228 for (int i = 0, len = instruction.inputs.length; i < len; i++) { | 225 for (int i = 0, len = instruction.inputs.length; i < len; i++) { |
| 229 markAsLiveInEnvironment(instruction.inputs[i], environment); | 226 markAsLiveInEnvironment(instruction.inputs[i], environment); |
| 230 } | 227 } |
| 231 } | 228 } |
| 232 | 229 |
| (...skipping 255 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 488 copyHandlers.putIfAbsent(block, () => new CopyHandler()); | 485 copyHandlers.putIfAbsent(block, () => new CopyHandler()); |
| 489 handler.addAssignment(source, destination); | 486 handler.addAssignment(source, destination); |
| 490 } | 487 } |
| 491 } | 488 } |
| 492 | 489 |
| 493 /** | 490 /** |
| 494 * Allocates variable names for instructions, making sure they don't collide. | 491 * Allocates variable names for instructions, making sure they don't collide. |
| 495 */ | 492 */ |
| 496 class VariableNamer { | 493 class VariableNamer { |
| 497 final VariableNames names; | 494 final VariableNames names; |
| 498 final Compiler compiler; | 495 final Namer _namer; |
| 499 final Set<String> usedNames; | 496 final Set<String> usedNames; |
| 500 final List<String> freeTemporaryNames; | 497 final List<String> freeTemporaryNames; |
| 501 int temporaryIndex = 0; | 498 int temporaryIndex = 0; |
| 502 static final RegExp regexp = new RegExp('t[0-9]+'); | 499 static final RegExp regexp = new RegExp('t[0-9]+'); |
| 503 | 500 |
| 504 VariableNamer(LiveEnvironment environment, this.names, this.compiler) | 501 VariableNamer(LiveEnvironment environment, this.names, this._namer) |
| 505 : usedNames = new Set<String>(), | 502 : usedNames = new Set<String>(), |
| 506 freeTemporaryNames = new List<String>() { | 503 freeTemporaryNames = new List<String>() { |
| 507 // [VariableNames.swapTemp] is used when there is a cycle in a copy handler. | 504 // [VariableNames.swapTemp] is used when there is a cycle in a copy handler. |
| 508 // Therefore we make sure no one uses it. | 505 // Therefore we make sure no one uses it. |
| 509 usedNames.add(names.swapTemp); | 506 usedNames.add(names.swapTemp); |
| 510 | 507 |
| 511 // All liveIns instructions must have a name at this point, so we | 508 // All liveIns instructions must have a name at this point, so we |
| 512 // add them to the list of used names. | 509 // add them to the list of used names. |
| 513 environment.liveInstructions.forEach((HInstruction instruction, int index) { | 510 environment.liveInstructions.forEach((HInstruction instruction, int index) { |
| 514 String name = names.getName(instruction); | 511 String name = names.getName(instruction); |
| 515 if (name != null) { | 512 if (name != null) { |
| 516 usedNames.add(name); | 513 usedNames.add(name); |
| 517 names.addNameUsed(name); | 514 names.addNameUsed(name); |
| 518 } | 515 } |
| 519 }); | 516 }); |
| 520 } | 517 } |
| 521 | 518 |
| 522 String allocateWithHint(String originalName) { | 519 String allocateWithHint(String originalName) { |
| 523 int i = 0; | 520 int i = 0; |
| 524 JavaScriptBackend backend = compiler.backend; | 521 String name = _namer.safeVariableName(originalName); |
| 525 String name = backend.namer.safeVariableName(originalName); | |
| 526 while (usedNames.contains(name)) { | 522 while (usedNames.contains(name)) { |
| 527 name = backend.namer.safeVariableName('$originalName${i++}'); | 523 name = _namer.safeVariableName('$originalName${i++}'); |
| 528 } | 524 } |
| 529 return name; | 525 return name; |
| 530 } | 526 } |
| 531 | 527 |
| 532 String allocateTemporary() { | 528 String allocateTemporary() { |
| 533 while (!freeTemporaryNames.isEmpty) { | 529 while (!freeTemporaryNames.isEmpty) { |
| 534 String name = freeTemporaryNames.removeLast(); | 530 String name = freeTemporaryNames.removeLast(); |
| 535 if (!usedNames.contains(name)) return name; | 531 if (!usedNames.contains(name)) return name; |
| 536 } | 532 } |
| 537 String name = 't${temporaryIndex++}'; | 533 String name = 't${temporaryIndex++}'; |
| (...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 608 * the liveIns set as well as all the live intervals of instructions. | 604 * the liveIns set as well as all the live intervals of instructions. |
| 609 * It visits the graph in dominator order, so that at each entry of a | 605 * It visits the graph in dominator order, so that at each entry of a |
| 610 * block, the instructions in its liveIns set have names. | 606 * block, the instructions in its liveIns set have names. |
| 611 * | 607 * |
| 612 * When visiting a block, it goes through all instructions. For each | 608 * When visiting a block, it goes through all instructions. For each |
| 613 * instruction, it frees the names of the inputs that die at that | 609 * instruction, it frees the names of the inputs that die at that |
| 614 * instruction, and allocates a name to the instruction. For each phi, | 610 * instruction, and allocates a name to the instruction. For each phi, |
| 615 * it adds a copy to the CopyHandler of the corresponding predecessor. | 611 * it adds a copy to the CopyHandler of the corresponding predecessor. |
| 616 */ | 612 */ |
| 617 class SsaVariableAllocator extends HBaseVisitor { | 613 class SsaVariableAllocator extends HBaseVisitor { |
| 618 final Compiler compiler; | 614 final Namer _namer; |
| 619 final Map<HBasicBlock, LiveEnvironment> liveInstructions; | 615 final Map<HBasicBlock, LiveEnvironment> liveInstructions; |
| 620 final Map<HInstruction, LiveInterval> liveIntervals; | 616 final Map<HInstruction, LiveInterval> liveIntervals; |
| 621 final Set<HInstruction> generateAtUseSite; | 617 final Set<HInstruction> generateAtUseSite; |
| 622 | 618 |
| 623 final VariableNames names; | 619 final VariableNames names; |
| 624 | 620 |
| 625 SsaVariableAllocator(this.compiler, this.liveInstructions, this.liveIntervals, | 621 SsaVariableAllocator(this._namer, this.liveInstructions, this.liveIntervals, |
| 626 this.generateAtUseSite) | 622 this.generateAtUseSite) |
| 627 : this.names = new VariableNames(); | 623 : this.names = new VariableNames(); |
| 628 | 624 |
| 629 void visitGraph(HGraph graph) { | 625 void visitGraph(HGraph graph) { |
| 630 visitDominatorTree(graph); | 626 visitDominatorTree(graph); |
| 631 } | 627 } |
| 632 | 628 |
| 633 void visitBasicBlock(HBasicBlock block) { | 629 void visitBasicBlock(HBasicBlock block) { |
| 634 VariableNamer namer = | 630 VariableNamer variableNamer = |
| 635 new VariableNamer(liveInstructions[block], names, compiler); | 631 new VariableNamer(liveInstructions[block], names, _namer); |
| 636 | 632 |
| 637 block.forEachPhi((HPhi phi) { | 633 block.forEachPhi((HPhi phi) { |
| 638 handlePhi(phi, namer); | 634 handlePhi(phi, variableNamer); |
| 639 }); | 635 }); |
| 640 | 636 |
| 641 block.forEachInstruction((HInstruction instruction) { | 637 block.forEachInstruction((HInstruction instruction) { |
| 642 handleInstruction(instruction, namer); | 638 handleInstruction(instruction, variableNamer); |
| 643 }); | 639 }); |
| 644 } | 640 } |
| 645 | 641 |
| 646 /** | 642 /** |
| 647 * Returns whether [instruction] needs a name. Instructions that | 643 * Returns whether [instruction] needs a name. Instructions that |
| 648 * have no users or that are generated at use site do not need a name. | 644 * have no users or that are generated at use site do not need a name. |
| 649 */ | 645 */ |
| 650 bool needsName(instruction) { | 646 bool needsName(instruction) { |
| 651 if (instruction is HThis) return false; | 647 if (instruction is HThis) return false; |
| 652 if (instruction is HParameterValue) return true; | 648 if (instruction is HParameterValue) return true; |
| (...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 710 if (!needsName(input)) { | 706 if (!needsName(input)) { |
| 711 names.addAssignment(predecessor, input, phi); | 707 names.addAssignment(predecessor, input, phi); |
| 712 } else { | 708 } else { |
| 713 names.addCopy(predecessor, input, phi); | 709 names.addCopy(predecessor, input, phi); |
| 714 } | 710 } |
| 715 } | 711 } |
| 716 | 712 |
| 717 namer.allocateName(phi); | 713 namer.allocateName(phi); |
| 718 } | 714 } |
| 719 } | 715 } |
| OLD | NEW |