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

Side by Side Diff: lib/compiler/implementation/ssa/optimize.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/nodes.dart ('k') | lib/compiler/implementation/ssa/tracer.dart » ('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 interface OptimizationPhase { 5 interface OptimizationPhase {
6 String get name(); 6 String get name();
7 void visitGraph(HGraph graph); 7 void visitGraph(HGraph graph);
8 } 8 }
9 9
10 class SsaOptimizerTask extends CompilerTask { 10 class SsaOptimizerTask extends CompilerTask {
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after
47 return !work.guards.isEmpty(); 47 return !work.guards.isEmpty();
48 }); 48 });
49 } 49 }
50 50
51 void prepareForSpeculativeOptimizations(WorkItem work, HGraph graph) { 51 void prepareForSpeculativeOptimizations(WorkItem work, HGraph graph) {
52 measure(() { 52 measure(() {
53 // In order to generate correct code for the bailout version, we did not 53 // In order to generate correct code for the bailout version, we did not
54 // propagate types from the instruction to the type guard. We do it 54 // propagate types from the instruction to the type guard. We do it
55 // now to be able to optimize further. 55 // now to be able to optimize further.
56 work.guards.forEach((HTypeGuard guard) { 56 work.guards.forEach((HTypeGuard guard) {
57 guard.type = guard.guarded.type; 57 guard.propagatedType = guard.guarded.propagatedType;
58 guard.guarded.type = HType.UNKNOWN; 58 guard.guarded.propagatedType = HType.UNKNOWN;
59 }); 59 });
60 // We also need to insert range and integer checks for the type guards, 60 // We also need to insert range and integer checks for the type guards,
61 // now that they know their type. We did not need to do that 61 // now that they know their type. We did not need to do that
62 // before because instructions that reference a guard would 62 // before because instructions that reference a guard would
63 // have not tried to use, e.g. native array access, since the 63 // have not tried to use, e.g. native array access, since the
64 // guard was not typed. 64 // guard was not typed.
65 runPhases(graph, <OptimizationPhase>[new SsaCheckInserter(compiler)]); 65 runPhases(graph, <OptimizationPhase>[new SsaCheckInserter(compiler)]);
66 }); 66 });
67 } 67 }
68 } 68 }
(...skipping 23 matching lines...) Expand all
92 if (!replacement.isInBasicBlock()) { 92 if (!replacement.isInBasicBlock()) {
93 // The constant folding can return an instruction that is already 93 // The constant folding can return an instruction that is already
94 // part of the graph (like an input), so we only add the replacement 94 // part of the graph (like an input), so we only add the replacement
95 // if necessary. 95 // if necessary.
96 block.addAfter(instruction, replacement); 96 block.addAfter(instruction, replacement);
97 } 97 }
98 block.rewrite(instruction, replacement); 98 block.rewrite(instruction, replacement);
99 block.remove(instruction); 99 block.remove(instruction);
100 // If the replacement instruction does not know its type yet, 100 // If the replacement instruction does not know its type yet,
101 // use the type of the instruction. 101 // use the type of the instruction.
102 if (!replacement.type.isKnown()) { 102 if (!replacement.propagatedType.isUseful()) {
103 replacement.type = instruction.type; 103 replacement.propagatedType = instruction.propagatedType;
104 } 104 }
105 } 105 }
106 instruction = next; 106 instruction = next;
107 } 107 }
108 } 108 }
109 109
110 HInstruction visitInstruction(HInstruction node) { 110 HInstruction visitInstruction(HInstruction node) {
111 return node; 111 return node;
112 } 112 }
113 113
114 HInstruction visitBoolify(HBoolify node) { 114 HInstruction visitBoolify(HBoolify node) {
115 List<HInstruction> inputs = node.inputs; 115 List<HInstruction> inputs = node.inputs;
116 assert(inputs.length == 1); 116 assert(inputs.length == 1);
117 HInstruction input = inputs[0]; 117 HInstruction input = inputs[0];
118 if (input.isBoolean()) return input; 118 if (input.isBoolean()) return input;
119 // All values !== true are boolified to false. 119 // All values !== true are boolified to false.
120 if (input.type.isKnown()) { 120 if (input.propagatedType.isUseful()) {
121 return graph.addConstantBool(false); 121 return graph.addConstantBool(false);
122 } 122 }
123 return node; 123 return node;
124 } 124 }
125 125
126 HInstruction visitNot(HNot node) { 126 HInstruction visitNot(HNot node) {
127 List<HInstruction> inputs = node.inputs; 127 List<HInstruction> inputs = node.inputs;
128 assert(inputs.length == 1); 128 assert(inputs.length == 1);
129 HInstruction input = inputs[0]; 129 HInstruction input = inputs[0];
130 if (input is HConstant) { 130 if (input is HConstant) {
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after
179 compiler.builder.interceptors.getEqualsNullInterceptor()); 179 compiler.builder.interceptors.getEqualsNullInterceptor());
180 node.block.addBefore(node,target); 180 node.block.addBefore(node,target);
181 return new HEquals(target, node.left, node.right); 181 return new HEquals(target, node.left, node.right);
182 } 182 }
183 // All other cases are dealt with by the [visitInvokeBinary]. 183 // All other cases are dealt with by the [visitInvokeBinary].
184 return visitInvokeBinary(node); 184 return visitInvokeBinary(node);
185 } 185 }
186 186
187 HInstruction visitTypeGuard(HTypeGuard node) { 187 HInstruction visitTypeGuard(HTypeGuard node) {
188 HInstruction value = node.guarded; 188 HInstruction value = node.guarded;
189 return (value.type.combine(node.type) == value.type) ? value : node; 189 HType combinedType = value.propagatedType.combine(node.propagatedType);
190 return (combinedType == value.propagatedType) ? value : node;
190 } 191 }
191 192
192 HInstruction visitIntegerCheck(HIntegerCheck node) { 193 HInstruction visitIntegerCheck(HIntegerCheck node) {
193 HInstruction value = node.value; 194 HInstruction value = node.value;
194 return value.isInteger() ? value : node; 195 return value.isInteger() ? value : node;
195 } 196 }
196 197
197 HInstruction visitIs(HIs node) { 198 HInstruction visitIs(HIs node) {
198 Type type = node.typeName; 199 Type type = node.typeName;
199 Element element = type.element; 200 Element element = type.element;
200 if (element.kind === ElementKind.TYPE_VARIABLE) { 201 if (element.kind === ElementKind.TYPE_VARIABLE) {
201 compiler.unimplemented("visitIs for type variables"); 202 compiler.unimplemented("visitIs for type variables");
202 } 203 }
203 204
204 HType expressionType = node.expression.type; 205 HType expressionType = node.expression.propagatedType;
205 if (element === compiler.objectClass 206 if (element === compiler.objectClass
206 || element === compiler.dynamicClass) { 207 || element === compiler.dynamicClass) {
207 return graph.addConstantBool(true); 208 return graph.addConstantBool(true);
208 } else if (expressionType.isInteger()) { 209 } else if (expressionType.isInteger()) {
209 if (element === compiler.intClass || element === compiler.numClass) { 210 if (element === compiler.intClass || element === compiler.numClass) {
210 return graph.addConstantBool(true); 211 return graph.addConstantBool(true);
211 } else if (element === compiler.doubleClass) { 212 } else if (element === compiler.doubleClass) {
212 // We let the JS semantics decide for that check. Currently 213 // We let the JS semantics decide for that check. Currently
213 // the code we emit will always return true. 214 // the code we emit will always return true.
214 return node; 215 return node;
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after
277 HBoundsCheck insertBoundsCheck(HInstruction node, 278 HBoundsCheck insertBoundsCheck(HInstruction node,
278 HInstruction receiver, 279 HInstruction receiver,
279 HInstruction index) { 280 HInstruction index) {
280 HStatic interceptor = new HStatic(lengthInterceptor); 281 HStatic interceptor = new HStatic(lengthInterceptor);
281 node.block.addBefore(node, interceptor); 282 node.block.addBefore(node, interceptor);
282 HInvokeInterceptor length = new HInvokeInterceptor( 283 HInvokeInterceptor length = new HInvokeInterceptor(
283 Selector.INVOCATION_0, 284 Selector.INVOCATION_0,
284 const SourceString("length"), 285 const SourceString("length"),
285 true, 286 true,
286 <HInstruction>[interceptor, receiver]); 287 <HInstruction>[interceptor, receiver]);
287 length.type = HType.NUMBER; 288 length.propagatedType = HType.INTEGER;
288 node.block.addBefore(node, length); 289 node.block.addBefore(node, length);
289 290
290 HBoundsCheck check = new HBoundsCheck(length, index); 291 HBoundsCheck check = new HBoundsCheck(length, index);
291 node.block.addBefore(node, check); 292 node.block.addBefore(node, check);
292 return check; 293 return check;
293 } 294 }
294 295
295 HIntegerCheck insertIntegerCheck(HInstruction node, HInstruction value) { 296 HIntegerCheck insertIntegerCheck(HInstruction node, HInstruction value) {
296 HIntegerCheck check = new HIntegerCheck(value); 297 HIntegerCheck check = new HIntegerCheck(value);
297 node.block.addBefore(node, check); 298 node.block.addBefore(node, check);
298 return check; 299 return check;
299 } 300 }
300 301
301 void visitIndex(HIndex node) { 302 void visitIndex(HIndex node) {
302 if (!node.builtin) return; 303 if (!node.receiver.isStringOrArray()) return;
303 if (node.index is HBoundsCheck) return; 304 HInstruction index = node.index;
304 HInstruction index = insertIntegerCheck(node, node.index); 305 if (index is HBoundsCheck) return;
306 if (!node.index.isInteger()) {
307 index = insertIntegerCheck(node, index);
308 }
305 index = insertBoundsCheck(node, node.receiver, index); 309 index = insertBoundsCheck(node, node.receiver, index);
306 HIndex newInstruction = new HIndex(node.target, node.receiver, index); 310 HIndex newInstruction = new HIndex(node.target, node.receiver, index);
307 node.block.addBefore(node, newInstruction); 311 node.block.addBefore(node, newInstruction);
308 node.block.rewrite(node, newInstruction); 312 node.block.rewrite(node, newInstruction);
309 node.block.remove(node); 313 node.block.remove(node);
310 } 314 }
311 315
312 void visitIndexAssign(HIndexAssign node) { 316 void visitIndexAssign(HIndexAssign node) {
313 if (!node.builtin) return; 317 if (!node.receiver.isMutableArray()) return;
314 if (node.index is HBoundsCheck) return; 318 HInstruction index = node.index;
315 HInstruction index = insertIntegerCheck(node, node.index); 319 if (index is HBoundsCheck) return;
320 if (!node.index.isInteger()) {
321 index = insertIntegerCheck(node, index);
322 }
316 index = insertBoundsCheck(node, node.receiver, index); 323 index = insertBoundsCheck(node, node.receiver, index);
317 HIndexAssign newInstruction = 324 HIndexAssign newInstruction =
318 new HIndexAssign(node.target, node.receiver, index, node.value); 325 new HIndexAssign(node.target, node.receiver, index, node.value);
319 node.block.addBefore(node, newInstruction); 326 node.block.addBefore(node, newInstruction);
320 node.block.rewrite(node, newInstruction); 327 node.block.rewrite(node, newInstruction);
321 node.block.remove(node); 328 node.block.remove(node);
322 } 329 }
323 } 330 }
324 331
325 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase { 332 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase {
(...skipping 379 matching lines...) Expand 10 before | Expand all | Expand 10 after
705 } 712 }
706 } 713 }
707 if (!canBeMoved) continue; 714 if (!canBeMoved) continue;
708 715
709 // This is safe because we are running after GVN. 716 // This is safe because we are running after GVN.
710 // TODO(ngeoffray): ensure GVN has been run. 717 // TODO(ngeoffray): ensure GVN has been run.
711 set_.add(current); 718 set_.add(current);
712 } 719 }
713 } 720 }
714 } 721 }
OLDNEW
« no previous file with comments | « lib/compiler/implementation/ssa/nodes.dart ('k') | lib/compiler/implementation/ssa/tracer.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698