OLD | NEW |
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 } |
OLD | NEW |