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

Side by Side Diff: lib/compiler/implementation/ssa/types.dart

Issue 10098001: Refactor type propagation. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Address comments and add new test. Created 8 years, 8 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 | Annotate | Revision Log
« no previous file with comments | « lib/compiler/implementation/ssa/tracer.dart ('k') | tests/language/language-leg.status » ('j') | 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) 2011, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2011, 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 class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase { 5 class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase {
6 6
7 final Map<int, HInstruction> workmap; 7 final Map<int, HInstruction> workmap;
8 final List<int> worklist; 8 final List<int> worklist;
9 final Compiler compiler; 9 final Compiler compiler;
10 String get name() => 'type propagator'; 10 String get name() => 'type propagator';
11 11
12 SsaTypePropagator(Compiler this.compiler) 12 SsaTypePropagator(Compiler this.compiler)
13 : workmap = new Map<int, HInstruction>(), 13 : workmap = new Map<int, HInstruction>(),
14 worklist = new List<int>(); 14 worklist = new List<int>();
15 15
16 16
17 HType computeType(HInstruction instruction) => instruction.computeType(); 17 HType computeType(HInstruction instruction) {
18 return instruction.computeTypeFromInputTypes();
19 }
18 20
19 // Re-compute and update the type of the instruction. Returns 21 // Re-compute and update the type of the instruction. Returns
20 // whether or not the type was changed. 22 // whether or not the type was changed.
21 bool updateType(HInstruction instruction) { 23 bool updateType(HInstruction instruction) {
22 if (instruction.type.isConflicting()) return false; 24 if (instruction.propagatedType.isConflicting()) return false;
23 // Constants have the type they have. It can't be changed.
24 if (instruction.isConstant()) return false;
25 25
26 HType oldType = instruction.type; 26 HType oldType = instruction.propagatedType;
27 HType newType = computeType(instruction); 27 HType newType = instruction.hasGuaranteedType()
28 instruction.type = oldType.combine(newType); 28 ? instruction.guaranteedType
29 return oldType !== instruction.type; 29 : computeType(instruction);
30 instruction.propagatedType = oldType.combine(newType);
31 return oldType !== instruction.propagatedType;
30 } 32 }
31 33
32 void visitGraph(HGraph graph) { 34 void visitGraph(HGraph graph) {
33 visitDominatorTree(graph); 35 visitDominatorTree(graph);
34 processWorklist(); 36 processWorklist();
35 } 37 }
36 38
37 visitBasicBlock(HBasicBlock block) { 39 visitBasicBlock(HBasicBlock block) {
38 if (block.isLoopHeader()) { 40 if (block.isLoopHeader()) {
39 block.forEachPhi((HPhi phi) { 41 block.forEachPhi((HPhi phi) {
40 // Set the initial type for the phi. 42 // Set the initial type for the phi. In theory we would need to mark the
41 phi.type = phi.inputs[0].type; 43 // type of all other incoming edges as "unitialized" and take this into
44 // account when doing the propagation inside the phis. Just setting
45 // the [propagatedType] is however easier.
46 phi.propagatedType = phi.inputs[0].propagatedType;
42 addToWorkList(phi); 47 addToWorkList(phi);
43 }); 48 });
44 } else { 49 } else {
45 block.forEachPhi((HPhi phi) { 50 block.forEachPhi((HPhi phi) {
46 if (updateType(phi)) addUsersAndInputsToWorklist(phi); 51 if (updateType(phi)) addDependentInstructionsToWorkList(phi);
47 }); 52 });
48 } 53 }
49 54
50 HInstruction instruction = block.first; 55 HInstruction instruction = block.first;
51 while (instruction !== null) { 56 while (instruction !== null) {
52 if (updateType(instruction)) addUsersAndInputsToWorklist(instruction); 57 if (updateType(instruction)) {
58 addDependentInstructionsToWorkList(instruction);
59 }
53 instruction = instruction.next; 60 instruction = instruction.next;
54 } 61 }
55 } 62 }
56 63
57 void processWorklist() { 64 void processWorklist() {
58 while (!worklist.isEmpty()) { 65 while (!worklist.isEmpty()) {
59 int id = worklist.removeLast(); 66 int id = worklist.removeLast();
60 HInstruction instruction = workmap[id]; 67 HInstruction instruction = workmap[id];
61 assert(instruction !== null); 68 assert(instruction !== null);
62 workmap.remove(id); 69 workmap.remove(id);
63 if (updateType(instruction)) addUsersAndInputsToWorklist(instruction); 70 if (updateType(instruction)) {
71 addDependentInstructionsToWorkList(instruction);
72 }
64 } 73 }
65 } 74 }
66 75
67 void addUsersAndInputsToWorklist(HInstruction instruction) { 76 void addDependentInstructionsToWorkList(HInstruction instruction) {
68 for (int i = 0, length = instruction.usedBy.length; i < length; i++) { 77 for (int i = 0, length = instruction.usedBy.length; i < length; i++) {
78 // The non-speculative type propagator only propagates types forward. We
79 // thus only need to add the users of the [instruction] to the list.
69 addToWorkList(instruction.usedBy[i]); 80 addToWorkList(instruction.usedBy[i]);
70 } 81 }
71 for (int i = 0, length = instruction.inputs.length; i < length; i++) {
72 addToWorkList(instruction.inputs[i]);
73 }
74 } 82 }
75 83
76 void addToWorkList(HInstruction instruction) { 84 void addToWorkList(HInstruction instruction) {
77 final int id = instruction.id; 85 final int id = instruction.id;
78 if (!workmap.containsKey(id)) { 86 if (!workmap.containsKey(id)) {
79 worklist.add(id); 87 worklist.add(id);
80 workmap[id] = instruction; 88 workmap[id] = instruction;
81 } 89 }
82 } 90 }
83 } 91 }
84 92
85 class SsaSpeculativeTypePropagator extends SsaTypePropagator { 93 class SsaSpeculativeTypePropagator extends SsaTypePropagator {
86 final String name = 'speculative type propagator'; 94 final String name = 'speculative type propagator';
87 SsaSpeculativeTypePropagator(Compiler compiler) : super(compiler); 95 SsaSpeculativeTypePropagator(Compiler compiler) : super(compiler);
88 96
97 void addDependentInstructionsToWorkList(HInstruction instruction) {
98 // The speculative type propagator propagates types forward and backward.
99 // Not only do we need to add the users of the [instruction] to the list.
100 // We also need to add the inputs fo the [instruction], since they might
101 // want to propagate the desired outgoing type.
102 for (int i = 0, length = instruction.usedBy.length; i < length; i++) {
103 addToWorkList(instruction.usedBy[i]);
104 }
105 for (int i = 0, length = instruction.inputs.length; i < length; i++) {
106 addToWorkList(instruction.inputs[i]);
107 }
108 }
109
89 HType computeDesiredType(HInstruction instruction) { 110 HType computeDesiredType(HInstruction instruction) {
90 HType desiredType = HType.UNKNOWN; 111 HType desiredType = HType.UNKNOWN;
91 for (final user in instruction.usedBy) { 112 for (final user in instruction.usedBy) {
92 desiredType = 113 desiredType =
93 desiredType.combine(user.computeDesiredInputType(instruction)); 114 desiredType.combine(user.computeDesiredTypeForInput(instruction));
94 // No need to continue if two users disagree on the type. 115 // No need to continue if two users disagree on the type.
95 if (desiredType.isConflicting()) break; 116 if (desiredType.isConflicting()) break;
96 } 117 }
97 return desiredType; 118 return desiredType;
98 } 119 }
99 120
100 HType computeType(HInstruction instruction) { 121 HType computeType(HInstruction instruction) {
101 HType newType = super.computeType(instruction); 122 HType newType = super.computeType(instruction);
123 // [computeDesiredType] goes to all usedBys and lets them compute their
124 // desired type. By setting the [newType] here we give them more context to
125 // work with.
126 instruction.propagatedType = newType;
102 HType desiredType = computeDesiredType(instruction); 127 HType desiredType = computeDesiredType(instruction);
103 // If the desired type is conflicting just return the computed 128 // If the desired type is conflicting just return the computed type.
104 // type.
105 if (desiredType.isConflicting()) return newType; 129 if (desiredType.isConflicting()) return newType;
106 return newType.combine(desiredType); 130 return newType.combine(desiredType);
107 } 131 }
108 } 132 }
OLDNEW
« no previous file with comments | « lib/compiler/implementation/ssa/tracer.dart ('k') | tests/language/language-leg.status » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698