Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(4)

Side by Side Diff: pkg/compiler/lib/src/ssa/variable_allocator.dart

Issue 2777163002: Make codegen and optimizations depend more directly on data objects. (Closed)
Patch Set: Created 3 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « pkg/compiler/lib/src/ssa/types_propagation.dart ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « pkg/compiler/lib/src/ssa/types_propagation.dart ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698