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/codegen.dart' show | 5 import '../common/codegen.dart' show CodegenRegistry, CodegenWorkItem; |
6 CodegenRegistry, | 6 import '../common/tasks.dart' show CompilerTask; |
7 CodegenWorkItem; | 7 import '../compiler.dart' show Compiler; |
8 import '../common/tasks.dart' show | |
9 CompilerTask; | |
10 import '../compiler.dart' show | |
11 Compiler; | |
12 import '../constants/constant_system.dart'; | 8 import '../constants/constant_system.dart'; |
13 import '../constants/values.dart'; | 9 import '../constants/values.dart'; |
14 import '../core_types.dart' show | 10 import '../core_types.dart' show CoreClasses; |
15 CoreClasses; | |
16 import '../dart_types.dart'; | 11 import '../dart_types.dart'; |
17 import '../elements/elements.dart'; | 12 import '../elements/elements.dart'; |
18 import '../js/js.dart' as js; | 13 import '../js/js.dart' as js; |
19 import '../js_backend/backend_helpers.dart' show | 14 import '../js_backend/backend_helpers.dart' show BackendHelpers; |
20 BackendHelpers; | |
21 import '../js_backend/js_backend.dart'; | 15 import '../js_backend/js_backend.dart'; |
22 import '../native/native.dart' as native; | 16 import '../native/native.dart' as native; |
23 import '../tree/tree.dart' as ast; | 17 import '../tree/tree.dart' as ast; |
24 import '../types/types.dart'; | 18 import '../types/types.dart'; |
25 import '../universe/selector.dart' show | 19 import '../universe/selector.dart' show Selector; |
26 Selector; | 20 import '../universe/side_effects.dart' show SideEffects; |
27 import '../universe/side_effects.dart' show | |
28 SideEffects; | |
29 import '../util/util.dart'; | 21 import '../util/util.dart'; |
30 import '../world.dart' show | 22 import '../world.dart' show ClassWorld, World; |
31 ClassWorld, | |
32 World; | |
33 | 23 |
34 import 'nodes.dart'; | 24 import 'nodes.dart'; |
35 import 'types_propagation.dart'; | 25 import 'types_propagation.dart'; |
36 import 'types.dart'; | 26 import 'types.dart'; |
37 import 'value_range_analyzer.dart'; | 27 import 'value_range_analyzer.dart'; |
38 import 'value_set.dart'; | 28 import 'value_set.dart'; |
39 import 'interceptor_simplifier.dart'; | 29 import 'interceptor_simplifier.dart'; |
40 | 30 |
41 abstract class OptimizationPhase { | 31 abstract class OptimizationPhase { |
42 String get name; | 32 String get name; |
(...skipping 14 matching lines...) Expand all Loading... |
57 measureSubtask(phase.name, () => phase.visitGraph(graph)); | 47 measureSubtask(phase.name, () => phase.visitGraph(graph)); |
58 compiler.tracer.traceGraph(phase.name, graph); | 48 compiler.tracer.traceGraph(phase.name, graph); |
59 assert(graph.isValid()); | 49 assert(graph.isValid()); |
60 } | 50 } |
61 | 51 |
62 ConstantSystem constantSystem = compiler.backend.constantSystem; | 52 ConstantSystem constantSystem = compiler.backend.constantSystem; |
63 JavaScriptItemCompilationContext context = work.compilationContext; | 53 JavaScriptItemCompilationContext context = work.compilationContext; |
64 bool trustPrimitives = compiler.options.trustPrimitives; | 54 bool trustPrimitives = compiler.options.trustPrimitives; |
65 measure(() { | 55 measure(() { |
66 List<OptimizationPhase> phases = <OptimizationPhase>[ | 56 List<OptimizationPhase> phases = <OptimizationPhase>[ |
67 // Run trivial instruction simplification first to optimize | 57 // Run trivial instruction simplification first to optimize |
68 // some patterns useful for type conversion. | 58 // some patterns useful for type conversion. |
69 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 59 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
70 new SsaTypeConversionInserter(compiler), | 60 new SsaTypeConversionInserter(compiler), |
71 new SsaRedundantPhiEliminator(), | 61 new SsaRedundantPhiEliminator(), |
72 new SsaDeadPhiEliminator(), | 62 new SsaDeadPhiEliminator(), |
73 new SsaTypePropagator(compiler), | 63 new SsaTypePropagator(compiler), |
74 // After type propagation, more instructions can be | 64 // After type propagation, more instructions can be |
75 // simplified. | 65 // simplified. |
76 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 66 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
77 new SsaCheckInserter( | 67 new SsaCheckInserter( |
78 trustPrimitives, backend, work, context.boundsChecked), | 68 trustPrimitives, backend, work, context.boundsChecked), |
79 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 69 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
80 new SsaCheckInserter( | 70 new SsaCheckInserter( |
81 trustPrimitives, backend, work, context.boundsChecked), | 71 trustPrimitives, backend, work, context.boundsChecked), |
82 new SsaTypePropagator(compiler), | 72 new SsaTypePropagator(compiler), |
83 // Run a dead code eliminator before LICM because dead | 73 // Run a dead code eliminator before LICM because dead |
84 // interceptors are often in the way of LICM'able instructions. | 74 // interceptors are often in the way of LICM'able instructions. |
85 new SsaDeadCodeEliminator(compiler, this), | 75 new SsaDeadCodeEliminator(compiler, this), |
86 new SsaGlobalValueNumberer(compiler), | 76 new SsaGlobalValueNumberer(compiler), |
87 // After GVN, some instructions might need their type to be | 77 // After GVN, some instructions might need their type to be |
88 // updated because they now have different inputs. | 78 // updated because they now have different inputs. |
89 new SsaTypePropagator(compiler), | 79 new SsaTypePropagator(compiler), |
90 new SsaCodeMotion(), | 80 new SsaCodeMotion(), |
91 new SsaLoadElimination(compiler), | 81 new SsaLoadElimination(compiler), |
92 new SsaRedundantPhiEliminator(), | 82 new SsaRedundantPhiEliminator(), |
93 new SsaDeadPhiEliminator(), | 83 new SsaDeadPhiEliminator(), |
94 new SsaTypePropagator(compiler), | 84 new SsaTypePropagator(compiler), |
95 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), | 85 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), |
96 // Previous optimizations may have generated new | 86 // Previous optimizations may have generated new |
97 // opportunities for instruction simplification. | 87 // opportunities for instruction simplification. |
98 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 88 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
99 new SsaCheckInserter( | 89 new SsaCheckInserter( |
100 trustPrimitives, backend, work, context.boundsChecked), | 90 trustPrimitives, backend, work, context.boundsChecked), |
101 ]; | 91 ]; |
102 phases.forEach(runPhase); | 92 phases.forEach(runPhase); |
103 | 93 |
104 // Simplifying interceptors is not strictly just an optimization, it is | 94 // Simplifying interceptors is not strictly just an optimization, it is |
105 // required for implementation correctness because the code generator | 95 // required for implementation correctness because the code generator |
106 // assumes it is always performed. | 96 // assumes it is always performed. |
107 runPhase(new SsaSimplifyInterceptors(compiler, constantSystem, work)); | 97 runPhase(new SsaSimplifyInterceptors(compiler, constantSystem, work)); |
108 | 98 |
109 SsaDeadCodeEliminator dce = new SsaDeadCodeEliminator(compiler, this); | 99 SsaDeadCodeEliminator dce = new SsaDeadCodeEliminator(compiler, this); |
110 runPhase(dce); | 100 runPhase(dce); |
111 if (dce.eliminatedSideEffects) { | 101 if (dce.eliminatedSideEffects) { |
112 phases = <OptimizationPhase>[ | 102 phases = <OptimizationPhase>[ |
113 new SsaTypePropagator(compiler), | 103 new SsaTypePropagator(compiler), |
114 new SsaGlobalValueNumberer(compiler), | 104 new SsaGlobalValueNumberer(compiler), |
115 new SsaCodeMotion(), | 105 new SsaCodeMotion(), |
116 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), | 106 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), |
117 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 107 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
118 new SsaCheckInserter( | 108 new SsaCheckInserter( |
119 trustPrimitives, backend, work, context.boundsChecked), | 109 trustPrimitives, backend, work, context.boundsChecked), |
120 new SsaSimplifyInterceptors(compiler, constantSystem, work), | 110 new SsaSimplifyInterceptors(compiler, constantSystem, work), |
121 new SsaDeadCodeEliminator(compiler, this), | 111 new SsaDeadCodeEliminator(compiler, this), |
122 ]; | 112 ]; |
123 } else { | 113 } else { |
124 phases = <OptimizationPhase>[ | 114 phases = <OptimizationPhase>[ |
125 new SsaTypePropagator(compiler), | 115 new SsaTypePropagator(compiler), |
126 // Run the simplifier to remove unneeded type checks inserted by | 116 // Run the simplifier to remove unneeded type checks inserted by |
127 // type propagation. | 117 // type propagation. |
128 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 118 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
129 ]; | 119 ]; |
130 } | 120 } |
131 phases.forEach(runPhase); | 121 phases.forEach(runPhase); |
132 }); | 122 }); |
133 } | 123 } |
134 } | 124 } |
135 | 125 |
136 /// Returns `true` if [mask] represents only types that have a length that | 126 /// Returns `true` if [mask] represents only types that have a length that |
137 /// cannot change. The current implementation is conservative for the purpose | 127 /// cannot change. The current implementation is conservative for the purpose |
138 /// of identifying gvn-able lengths and mis-identifies some unions of fixed | 128 /// of identifying gvn-able lengths and mis-identifies some unions of fixed |
(...skipping 14 matching lines...) Expand all Loading... |
153 } | 143 } |
154 return false; | 144 return false; |
155 } | 145 } |
156 | 146 |
157 /** | 147 /** |
158 * If both inputs to known operations are available execute the operation at | 148 * If both inputs to known operations are available execute the operation at |
159 * compile-time. | 149 * compile-time. |
160 */ | 150 */ |
161 class SsaInstructionSimplifier extends HBaseVisitor | 151 class SsaInstructionSimplifier extends HBaseVisitor |
162 implements OptimizationPhase { | 152 implements OptimizationPhase { |
163 | |
164 // We don't produce constant-folded strings longer than this unless they have | 153 // We don't produce constant-folded strings longer than this unless they have |
165 // a single use. This protects against exponentially large constant folded | 154 // a single use. This protects against exponentially large constant folded |
166 // strings. | 155 // strings. |
167 static const MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH = 512; | 156 static const MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH = 512; |
168 | 157 |
169 final String name = "SsaInstructionSimplifier"; | 158 final String name = "SsaInstructionSimplifier"; |
170 final JavaScriptBackend backend; | 159 final JavaScriptBackend backend; |
171 final CodegenWorkItem work; | 160 final CodegenWorkItem work; |
172 final ConstantSystem constantSystem; | 161 final ConstantSystem constantSystem; |
173 HGraph graph; | 162 HGraph graph; |
174 Compiler get compiler => backend.compiler; | 163 Compiler get compiler => backend.compiler; |
175 final SsaOptimizerTask optimizer; | 164 final SsaOptimizerTask optimizer; |
176 | 165 |
177 SsaInstructionSimplifier(this.constantSystem, | 166 SsaInstructionSimplifier( |
178 this.backend, | 167 this.constantSystem, this.backend, this.optimizer, this.work); |
179 this.optimizer, | |
180 this.work); | |
181 | 168 |
182 CoreClasses get coreClasses => compiler.coreClasses; | 169 CoreClasses get coreClasses => compiler.coreClasses; |
183 | 170 |
184 BackendHelpers get helpers => backend.helpers; | 171 BackendHelpers get helpers => backend.helpers; |
185 | 172 |
186 void visitGraph(HGraph visitee) { | 173 void visitGraph(HGraph visitee) { |
187 graph = visitee; | 174 graph = visitee; |
188 visitDominatorTree(visitee); | 175 visitDominatorTree(visitee); |
189 } | 176 } |
190 | 177 |
191 visitBasicBlock(HBasicBlock block) { | 178 visitBasicBlock(HBasicBlock block) { |
192 HInstruction instruction = block.first; | 179 HInstruction instruction = block.first; |
193 while (instruction != null) { | 180 while (instruction != null) { |
194 HInstruction next = instruction.next; | 181 HInstruction next = instruction.next; |
195 HInstruction replacement = instruction.accept(this); | 182 HInstruction replacement = instruction.accept(this); |
196 if (replacement != instruction) { | 183 if (replacement != instruction) { |
197 block.rewrite(instruction, replacement); | 184 block.rewrite(instruction, replacement); |
198 | 185 |
199 // The intersection of double and int return conflicting, and | 186 // The intersection of double and int return conflicting, and |
200 // because of our number implementation for JavaScript, it | 187 // because of our number implementation for JavaScript, it |
201 // might be that an operation thought to return double, can be | 188 // might be that an operation thought to return double, can be |
202 // simplified to an int. For example: | 189 // simplified to an int. For example: |
203 // `2.5 * 10`. | 190 // `2.5 * 10`. |
204 if (!(replacement.isNumberOrNull(compiler) | 191 if (!(replacement.isNumberOrNull(compiler) && |
205 && instruction.isNumberOrNull(compiler))) { | 192 instruction.isNumberOrNull(compiler))) { |
206 // If we can replace [instruction] with [replacement], then | 193 // If we can replace [instruction] with [replacement], then |
207 // [replacement]'s type can be narrowed. | 194 // [replacement]'s type can be narrowed. |
208 TypeMask newType = replacement.instructionType.intersection( | 195 TypeMask newType = replacement.instructionType |
209 instruction.instructionType, compiler.world); | 196 .intersection(instruction.instructionType, compiler.world); |
210 replacement.instructionType = newType; | 197 replacement.instructionType = newType; |
211 } | 198 } |
212 | 199 |
213 // If the replacement instruction does not know its | 200 // If the replacement instruction does not know its |
214 // source element, use the source element of the | 201 // source element, use the source element of the |
215 // instruction. | 202 // instruction. |
216 if (replacement.sourceElement == null) { | 203 if (replacement.sourceElement == null) { |
217 replacement.sourceElement = instruction.sourceElement; | 204 replacement.sourceElement = instruction.sourceElement; |
218 } | 205 } |
219 if (replacement.sourceInformation == null) { | 206 if (replacement.sourceInformation == null) { |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
258 user.changeUse(node, constant); | 245 user.changeUse(node, constant); |
259 } | 246 } |
260 } | 247 } |
261 } | 248 } |
262 | 249 |
263 HInstruction visitParameterValue(HParameterValue node) { | 250 HInstruction visitParameterValue(HParameterValue node) { |
264 // It is possible for the parameter value to be assigned to in the function | 251 // It is possible for the parameter value to be assigned to in the function |
265 // body. If that happens then we should not forward the constant value to | 252 // body. If that happens then we should not forward the constant value to |
266 // its uses since since the uses reachable from the assignment may have | 253 // its uses since since the uses reachable from the assignment may have |
267 // values in addition to the constant passed to the function. | 254 // values in addition to the constant passed to the function. |
268 if (node.usedBy.any((user) => | 255 if (node.usedBy |
269 user is HLocalSet && identical(user.local, node))) { | 256 .any((user) => user is HLocalSet && identical(user.local, node))) { |
270 return node; | 257 return node; |
271 } | 258 } |
272 propagateConstantValueToUses(node); | 259 propagateConstantValueToUses(node); |
273 return node; | 260 return node; |
274 } | 261 } |
275 | 262 |
276 HInstruction visitBoolify(HBoolify node) { | 263 HInstruction visitBoolify(HBoolify node) { |
277 List<HInstruction> inputs = node.inputs; | 264 List<HInstruction> inputs = node.inputs; |
278 assert(inputs.length == 1); | 265 assert(inputs.length == 1); |
279 HInstruction input = inputs[0]; | 266 HInstruction input = inputs[0]; |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
334 ListConstantValue constant = constantInput.constant; | 321 ListConstantValue constant = constantInput.constant; |
335 return graph.addConstantInt(constant.length, compiler); | 322 return graph.addConstantInt(constant.length, compiler); |
336 } | 323 } |
337 Element element = helpers.jsIndexableLength; | 324 Element element = helpers.jsIndexableLength; |
338 bool isFixed = isFixedLength(actualReceiver.instructionType, compiler); | 325 bool isFixed = isFixedLength(actualReceiver.instructionType, compiler); |
339 TypeMask actualType = node.instructionType; | 326 TypeMask actualType = node.instructionType; |
340 ClassWorld classWorld = compiler.world; | 327 ClassWorld classWorld = compiler.world; |
341 TypeMask resultType = backend.positiveIntType; | 328 TypeMask resultType = backend.positiveIntType; |
342 // If we already have computed a more specific type, keep that type. | 329 // If we already have computed a more specific type, keep that type. |
343 if (HInstruction.isInstanceOf( | 330 if (HInstruction.isInstanceOf( |
344 actualType, helpers.jsUInt31Class, classWorld)) { | 331 actualType, helpers.jsUInt31Class, classWorld)) { |
345 resultType = backend.uint31Type; | 332 resultType = backend.uint31Type; |
346 } else if (HInstruction.isInstanceOf( | 333 } else if (HInstruction.isInstanceOf( |
347 actualType, helpers.jsUInt32Class, classWorld)) { | 334 actualType, helpers.jsUInt32Class, classWorld)) { |
348 resultType = backend.uint32Type; | 335 resultType = backend.uint32Type; |
349 } | 336 } |
350 HFieldGet result = new HFieldGet( | 337 HFieldGet result = new HFieldGet(element, actualReceiver, resultType, |
351 element, actualReceiver, resultType, | |
352 isAssignable: !isFixed); | 338 isAssignable: !isFixed); |
353 return result; | 339 return result; |
354 } else if (actualReceiver.isConstantMap()) { | 340 } else if (actualReceiver.isConstantMap()) { |
355 HConstant constantInput = actualReceiver; | 341 HConstant constantInput = actualReceiver; |
356 MapConstantValue constant = constantInput.constant; | 342 MapConstantValue constant = constantInput.constant; |
357 return graph.addConstantInt(constant.length, compiler); | 343 return graph.addConstantInt(constant.length, compiler); |
358 } | 344 } |
359 return null; | 345 return null; |
360 } | 346 } |
361 | 347 |
(...skipping 13 matching lines...) Expand all Loading... |
375 if (instruction != null) return instruction; | 361 if (instruction != null) return instruction; |
376 | 362 |
377 Selector selector = node.selector; | 363 Selector selector = node.selector; |
378 TypeMask mask = node.mask; | 364 TypeMask mask = node.mask; |
379 HInstruction input = node.inputs[1]; | 365 HInstruction input = node.inputs[1]; |
380 | 366 |
381 World world = compiler.world; | 367 World world = compiler.world; |
382 | 368 |
383 bool applies(Element element) { | 369 bool applies(Element element) { |
384 return selector.applies(element, world) && | 370 return selector.applies(element, world) && |
385 (mask == null || mask.canHit(element, selector, world)); | 371 (mask == null || mask.canHit(element, selector, world)); |
386 } | 372 } |
387 | 373 |
388 if (selector.isCall || selector.isOperator) { | 374 if (selector.isCall || selector.isOperator) { |
389 Element target; | 375 Element target; |
390 if (input.isExtendableArray(compiler)) { | 376 if (input.isExtendableArray(compiler)) { |
391 if (applies(helpers.jsArrayRemoveLast)) { | 377 if (applies(helpers.jsArrayRemoveLast)) { |
392 target = helpers.jsArrayRemoveLast; | 378 target = helpers.jsArrayRemoveLast; |
393 } else if (applies(helpers.jsArrayAdd)) { | 379 } else if (applies(helpers.jsArrayAdd)) { |
394 // The codegen special cases array calls, but does not | 380 // The codegen special cases array calls, but does not |
395 // inline argument type checks. | 381 // inline argument type checks. |
396 if (!compiler.options.enableTypeAssertions) { | 382 if (!compiler.options.enableTypeAssertions) { |
397 target = helpers.jsArrayAdd; | 383 target = helpers.jsArrayAdd; |
398 } | 384 } |
399 } | 385 } |
400 } else if (input.isStringOrNull(compiler)) { | 386 } else if (input.isStringOrNull(compiler)) { |
401 if (applies(helpers.jsStringSplit)) { | 387 if (applies(helpers.jsStringSplit)) { |
402 HInstruction argument = node.inputs[2]; | 388 HInstruction argument = node.inputs[2]; |
403 if (argument.isString(compiler)) { | 389 if (argument.isString(compiler)) { |
404 target = helpers.jsStringSplit; | 390 target = helpers.jsStringSplit; |
405 } | 391 } |
406 } else if (applies(helpers.jsStringOperatorAdd)) { | 392 } else if (applies(helpers.jsStringOperatorAdd)) { |
407 // `operator+` is turned into a JavaScript '+' so we need to | 393 // `operator+` is turned into a JavaScript '+' so we need to |
408 // make sure the receiver and the argument are not null. | 394 // make sure the receiver and the argument are not null. |
409 // TODO(sra): Do this via [node.specializer]. | 395 // TODO(sra): Do this via [node.specializer]. |
410 HInstruction argument = node.inputs[2]; | 396 HInstruction argument = node.inputs[2]; |
411 if (argument.isString(compiler) | 397 if (argument.isString(compiler) && !input.canBeNull()) { |
412 && !input.canBeNull()) { | |
413 return new HStringConcat(input, argument, node.instructionType); | 398 return new HStringConcat(input, argument, node.instructionType); |
414 } | 399 } |
415 } else if (applies(helpers.jsStringToString) | 400 } else if (applies(helpers.jsStringToString) && !input.canBeNull()) { |
416 && !input.canBeNull()) { | |
417 return input; | 401 return input; |
418 } | 402 } |
419 } | 403 } |
420 if (target != null) { | 404 if (target != null) { |
421 // TODO(ngeoffray): There is a strong dependency between codegen | 405 // TODO(ngeoffray): There is a strong dependency between codegen |
422 // and this optimization that the dynamic invoke does not need an | 406 // and this optimization that the dynamic invoke does not need an |
423 // interceptor. We currently need to keep a | 407 // interceptor. We currently need to keep a |
424 // HInvokeDynamicMethod and not create a HForeign because | 408 // HInvokeDynamicMethod and not create a HForeign because |
425 // HForeign is too opaque for the SsaCheckInserter (that adds a | 409 // HForeign is too opaque for the SsaCheckInserter (that adds a |
426 // bounds check on removeLast). Once we start inlining, the | 410 // bounds check on removeLast). Once we start inlining, the |
427 // bounds check will become explicit, so we won't need this | 411 // bounds check will become explicit, so we won't need this |
428 // optimization. | 412 // optimization. |
429 HInvokeDynamicMethod result = new HInvokeDynamicMethod( | 413 HInvokeDynamicMethod result = new HInvokeDynamicMethod(node.selector, |
430 node.selector, node.mask, | 414 node.mask, node.inputs.sublist(1), node.instructionType); |
431 node.inputs.sublist(1), node.instructionType); | |
432 result.element = target; | 415 result.element = target; |
433 return result; | 416 return result; |
434 } | 417 } |
435 } else if (selector.isGetter) { | 418 } else if (selector.isGetter) { |
436 if (selector.applies(helpers.jsIndexableLength, world)) { | 419 if (selector.applies(helpers.jsIndexableLength, world)) { |
437 HInstruction optimized = tryOptimizeLengthInterceptedGetter(node); | 420 HInstruction optimized = tryOptimizeLengthInterceptedGetter(node); |
438 if (optimized != null) return optimized; | 421 if (optimized != null) return optimized; |
439 } | 422 } |
440 } | 423 } |
441 | 424 |
442 return node; | 425 return node; |
443 } | 426 } |
444 | 427 |
445 HInstruction visitInvokeDynamicMethod(HInvokeDynamicMethod node) { | 428 HInstruction visitInvokeDynamicMethod(HInvokeDynamicMethod node) { |
446 propagateConstantValueToUses(node); | 429 propagateConstantValueToUses(node); |
447 if (node.isInterceptedCall) { | 430 if (node.isInterceptedCall) { |
448 HInstruction folded = handleInterceptedCall(node); | 431 HInstruction folded = handleInterceptedCall(node); |
449 if (folded != node) return folded; | 432 if (folded != node) return folded; |
450 } | 433 } |
451 | 434 |
452 TypeMask receiverType = node.getDartReceiver(compiler).instructionType; | 435 TypeMask receiverType = node.getDartReceiver(compiler).instructionType; |
453 Element element = | 436 Element element = |
454 compiler.world.locateSingleElement(node.selector, receiverType); | 437 compiler.world.locateSingleElement(node.selector, receiverType); |
455 // TODO(ngeoffray): Also fold if it's a getter or variable. | 438 // TODO(ngeoffray): Also fold if it's a getter or variable. |
456 if (element != null | 439 if (element != null && |
457 && element.isFunction | 440 element.isFunction |
458 // If we found out that the only target is a [:noSuchMethod:], | 441 // If we found out that the only target is a [:noSuchMethod:], |
459 // we just ignore it. | 442 // we just ignore it. |
460 && element.name == node.selector.name) { | 443 && |
| 444 element.name == node.selector.name) { |
461 FunctionElement method = element; | 445 FunctionElement method = element; |
462 | 446 |
463 if (backend.isNative(method)) { | 447 if (backend.isNative(method)) { |
464 HInstruction folded = tryInlineNativeMethod(node, method); | 448 HInstruction folded = tryInlineNativeMethod(node, method); |
465 if (folded != null) return folded; | 449 if (folded != null) return folded; |
466 } else { | 450 } else { |
467 // TODO(ngeoffray): If the method has optional parameters, | 451 // TODO(ngeoffray): If the method has optional parameters, |
468 // we should pass the default values. | 452 // we should pass the default values. |
469 FunctionSignature parameters = method.functionSignature; | 453 FunctionSignature parameters = method.functionSignature; |
470 if (parameters.optionalParameterCount == 0 || | 454 if (parameters.optionalParameterCount == 0 || |
471 parameters.parameterCount == | 455 parameters.parameterCount == node.selector.argumentCount) { |
472 node.selector.argumentCount) { | |
473 node.element = element; | 456 node.element = element; |
474 } | 457 } |
475 } | 458 } |
476 } | 459 } |
477 return node; | 460 return node; |
478 } | 461 } |
479 | 462 |
480 HInstruction tryInlineNativeMethod(HInvokeDynamicMethod node, | 463 HInstruction tryInlineNativeMethod( |
481 FunctionElement method) { | 464 HInvokeDynamicMethod node, FunctionElement method) { |
482 // Enable direct calls to a native method only if we don't run in checked | 465 // Enable direct calls to a native method only if we don't run in checked |
483 // mode, where the Dart version may have type annotations on parameters and | 466 // mode, where the Dart version may have type annotations on parameters and |
484 // return type that it should check. | 467 // return type that it should check. |
485 // Also check that the parameters are not functions: it's the callee that | 468 // Also check that the parameters are not functions: it's the callee that |
486 // will translate them to JS functions. | 469 // will translate them to JS functions. |
487 // | 470 // |
488 // TODO(ngeoffray): There are some cases where we could still inline in | 471 // TODO(ngeoffray): There are some cases where we could still inline in |
489 // checked mode if we know the arguments have the right type. And we could | 472 // checked mode if we know the arguments have the right type. And we could |
490 // do the closure conversion as well as the return type annotation check. | 473 // do the closure conversion as well as the return type annotation check. |
491 | 474 |
492 if (!node.isInterceptedCall) return null; | 475 if (!node.isInterceptedCall) return null; |
493 | 476 |
494 // TODO(sra): Check for legacy methods with bodies in the native strings. | 477 // TODO(sra): Check for legacy methods with bodies in the native strings. |
495 // foo() native 'return something'; | 478 // foo() native 'return something'; |
496 // They should not be used. | 479 // They should not be used. |
497 | 480 |
498 FunctionSignature signature = method.functionSignature; | 481 FunctionSignature signature = method.functionSignature; |
499 if (signature.optionalParametersAreNamed) return null; | 482 if (signature.optionalParametersAreNamed) return null; |
500 | 483 |
501 // Return types on native methods don't need to be checked, since the | 484 // Return types on native methods don't need to be checked, since the |
502 // declaration has to be truthful. | 485 // declaration has to be truthful. |
503 | 486 |
504 // The call site might omit optional arguments. The inlined code must | 487 // The call site might omit optional arguments. The inlined code must |
505 // preserve the number of arguments, so check only the actual arguments. | 488 // preserve the number of arguments, so check only the actual arguments. |
506 | 489 |
507 List<HInstruction> inputs = node.inputs.sublist(1); | 490 List<HInstruction> inputs = node.inputs.sublist(1); |
508 int inputPosition = 1; // Skip receiver. | 491 int inputPosition = 1; // Skip receiver. |
509 bool canInline = true; | 492 bool canInline = true; |
510 signature.forEachParameter((ParameterElement element) { | 493 signature.forEachParameter((ParameterElement element) { |
511 if (inputPosition++ < inputs.length && canInline) { | 494 if (inputPosition++ < inputs.length && canInline) { |
512 DartType type = element.type.unaliased; | 495 DartType type = element.type.unaliased; |
513 if (type is FunctionType) { | 496 if (type is FunctionType) { |
514 canInline = false; | 497 canInline = false; |
515 } | 498 } |
516 if (compiler.options.enableTypeAssertions) { | 499 if (compiler.options.enableTypeAssertions) { |
517 // TODO(sra): Check if [input] is guaranteed to pass the parameter | 500 // TODO(sra): Check if [input] is guaranteed to pass the parameter |
518 // type check. Consider using a strengthened type check to avoid | 501 // type check. Consider using a strengthened type check to avoid |
(...skipping 25 matching lines...) Expand all Loading... |
544 HConstant constantInstruction = index; | 527 HConstant constantInstruction = index; |
545 assert(!constantInstruction.constant.isInt); | 528 assert(!constantInstruction.constant.isInt); |
546 if (!constantSystem.isInt(constantInstruction.constant)) { | 529 if (!constantSystem.isInt(constantInstruction.constant)) { |
547 // -0.0 is a double but will pass the runtime integer check. | 530 // -0.0 is a double but will pass the runtime integer check. |
548 node.staticChecks = HBoundsCheck.ALWAYS_FALSE; | 531 node.staticChecks = HBoundsCheck.ALWAYS_FALSE; |
549 } | 532 } |
550 } | 533 } |
551 return node; | 534 return node; |
552 } | 535 } |
553 | 536 |
554 HInstruction foldBinary(BinaryOperation operation, | 537 HInstruction foldBinary( |
555 HInstruction left, | 538 BinaryOperation operation, HInstruction left, HInstruction right) { |
556 HInstruction right) { | |
557 if (left is HConstant && right is HConstant) { | 539 if (left is HConstant && right is HConstant) { |
558 HConstant op1 = left; | 540 HConstant op1 = left; |
559 HConstant op2 = right; | 541 HConstant op2 = right; |
560 ConstantValue folded = operation.fold(op1.constant, op2.constant); | 542 ConstantValue folded = operation.fold(op1.constant, op2.constant); |
561 if (folded != null) return graph.addConstant(folded, compiler); | 543 if (folded != null) return graph.addConstant(folded, compiler); |
562 } | 544 } |
563 return null; | 545 return null; |
564 } | 546 } |
565 | 547 |
566 HInstruction visitAdd(HAdd node) { | 548 HInstruction visitAdd(HAdd node) { |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
643 } | 625 } |
644 | 626 |
645 if (left.isConstantBoolean() && right.isBoolean(compiler)) { | 627 if (left.isConstantBoolean() && right.isBoolean(compiler)) { |
646 return compareConstant(left, right); | 628 return compareConstant(left, right); |
647 } | 629 } |
648 | 630 |
649 if (right.isConstantBoolean() && left.isBoolean(compiler)) { | 631 if (right.isConstantBoolean() && left.isBoolean(compiler)) { |
650 return compareConstant(right, left); | 632 return compareConstant(right, left); |
651 } | 633 } |
652 | 634 |
653 | |
654 if (identical(left.nonCheck(), right.nonCheck())) { | 635 if (identical(left.nonCheck(), right.nonCheck())) { |
655 // Avoid constant-folding `identical(x, x)` when `x` might be double. The | 636 // Avoid constant-folding `identical(x, x)` when `x` might be double. The |
656 // dart2js runtime has not always been consistent with the Dart | 637 // dart2js runtime has not always been consistent with the Dart |
657 // specification (section 16.0.1), which makes distinctions on NaNs and | 638 // specification (section 16.0.1), which makes distinctions on NaNs and |
658 // -0.0 that are hard to implement efficiently. | 639 // -0.0 that are hard to implement efficiently. |
659 if (left.isIntegerOrNull(compiler)) return makeTrue(); | 640 if (left.isIntegerOrNull(compiler)) return makeTrue(); |
660 if (!left.canBePrimitiveNumber(compiler)) return makeTrue(); | 641 if (!left.canBePrimitiveNumber(compiler)) return makeTrue(); |
661 } | 642 } |
662 | 643 |
663 return null; | 644 return null; |
664 } | 645 } |
665 | 646 |
666 HInstruction visitIdentity(HIdentity node) { | 647 HInstruction visitIdentity(HIdentity node) { |
667 HInstruction newInstruction = handleIdentityCheck(node); | 648 HInstruction newInstruction = handleIdentityCheck(node); |
668 return newInstruction == null ? super.visitIdentity(node) : newInstruction; | 649 return newInstruction == null ? super.visitIdentity(node) : newInstruction; |
669 } | 650 } |
670 | 651 |
671 void simplifyCondition(HBasicBlock block, | 652 void simplifyCondition( |
672 HInstruction condition, | 653 HBasicBlock block, HInstruction condition, bool value) { |
673 bool value) { | |
674 condition.dominatedUsers(block.first).forEach((user) { | 654 condition.dominatedUsers(block.first).forEach((user) { |
675 HInstruction newCondition = graph.addConstantBool(value, compiler); | 655 HInstruction newCondition = graph.addConstantBool(value, compiler); |
676 user.changeUse(condition, newCondition); | 656 user.changeUse(condition, newCondition); |
677 }); | 657 }); |
678 } | 658 } |
679 | 659 |
680 HInstruction visitIf(HIf node) { | 660 HInstruction visitIf(HIf node) { |
681 HInstruction condition = node.condition; | 661 HInstruction condition = node.condition; |
682 if (condition.isConstant()) return node; | 662 if (condition.isConstant()) return node; |
683 bool isNegated = condition is HNot; | 663 bool isNegated = condition is HNot; |
684 | 664 |
685 if (isNegated) { | 665 if (isNegated) { |
686 condition = condition.inputs[0]; | 666 condition = condition.inputs[0]; |
687 } else { | 667 } else { |
688 // It is possible for LICM to move a negated version of the | 668 // It is possible for LICM to move a negated version of the |
689 // condition out of the loop where it used. We still want to | 669 // condition out of the loop where it used. We still want to |
690 // simplify the nested use of the condition in that case, so | 670 // simplify the nested use of the condition in that case, so |
691 // we look for all dominating negated conditions and replace | 671 // we look for all dominating negated conditions and replace |
692 // nested uses of them with true or false. | 672 // nested uses of them with true or false. |
693 Iterable<HInstruction> dominating = condition.usedBy.where((user) => | 673 Iterable<HInstruction> dominating = condition.usedBy |
694 user is HNot && user.dominates(node)); | 674 .where((user) => user is HNot && user.dominates(node)); |
695 dominating.forEach((hoisted) { | 675 dominating.forEach((hoisted) { |
696 simplifyCondition(node.thenBlock, hoisted, false); | 676 simplifyCondition(node.thenBlock, hoisted, false); |
697 simplifyCondition(node.elseBlock, hoisted, true); | 677 simplifyCondition(node.elseBlock, hoisted, true); |
698 }); | 678 }); |
699 } | 679 } |
700 simplifyCondition(node.thenBlock, condition, !isNegated); | 680 simplifyCondition(node.thenBlock, condition, !isNegated); |
701 simplifyCondition(node.elseBlock, condition, isNegated); | 681 simplifyCondition(node.elseBlock, condition, isNegated); |
702 return node; | 682 return node; |
703 } | 683 } |
704 | 684 |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
746 return graph.addConstantBool(false, compiler); | 726 return graph.addConstantBool(false, compiler); |
747 } | 727 } |
748 } else if (expression.isNumber(compiler)) { | 728 } else if (expression.isNumber(compiler)) { |
749 if (element == coreClasses.numClass) { | 729 if (element == coreClasses.numClass) { |
750 return graph.addConstantBool(true, compiler); | 730 return graph.addConstantBool(true, compiler); |
751 } else { | 731 } else { |
752 // We cannot just return false, because the expression may be of | 732 // We cannot just return false, because the expression may be of |
753 // type int or double. | 733 // type int or double. |
754 } | 734 } |
755 } else if (expression.canBePrimitiveNumber(compiler) && | 735 } else if (expression.canBePrimitiveNumber(compiler) && |
756 element == coreClasses.intClass) { | 736 element == coreClasses.intClass) { |
757 // We let the JS semantics decide for that check. | 737 // We let the JS semantics decide for that check. |
758 return node; | 738 return node; |
759 // We need the [:hasTypeArguments:] check because we don't have | 739 // We need the [:hasTypeArguments:] check because we don't have |
760 // the notion of generics in the backend. For example, [:this:] in | 740 // the notion of generics in the backend. For example, [:this:] in |
761 // a class [:A<T>:], is currently always considered to have the | 741 // a class [:A<T>:], is currently always considered to have the |
762 // raw type. | 742 // raw type. |
763 } else if (!RuntimeTypes.hasTypeArguments(type)) { | 743 } else if (!RuntimeTypes.hasTypeArguments(type)) { |
764 TypeMask expressionMask = expression.instructionType; | 744 TypeMask expressionMask = expression.instructionType; |
765 assert(TypeMask.assertIsNormalized(expressionMask, classWorld)); | 745 assert(TypeMask.assertIsNormalized(expressionMask, classWorld)); |
766 TypeMask typeMask = (element == coreClasses.nullClass) | 746 TypeMask typeMask = (element == coreClasses.nullClass) |
767 ? new TypeMask.subtype(element, classWorld) | 747 ? new TypeMask.subtype(element, classWorld) |
768 : new TypeMask.nonNullSubtype(element, classWorld); | 748 : new TypeMask.nonNullSubtype(element, classWorld); |
769 if (expressionMask.union(typeMask, classWorld) == typeMask) { | 749 if (expressionMask.union(typeMask, classWorld) == typeMask) { |
770 return graph.addConstantBool(true, compiler); | 750 return graph.addConstantBool(true, compiler); |
771 } else if (expressionMask.isDisjoint(typeMask, compiler.world)) { | 751 } else if (expressionMask.isDisjoint(typeMask, compiler.world)) { |
772 return graph.addConstantBool(false, compiler); | 752 return graph.addConstantBool(false, compiler); |
(...skipping 26 matching lines...) Expand all Loading... |
799 } | 779 } |
800 | 780 |
801 HInstruction removeIfCheckAlwaysSucceeds(HCheck node, TypeMask checkedType) { | 781 HInstruction removeIfCheckAlwaysSucceeds(HCheck node, TypeMask checkedType) { |
802 ClassWorld classWorld = compiler.world; | 782 ClassWorld classWorld = compiler.world; |
803 if (checkedType.containsAll(classWorld)) return node; | 783 if (checkedType.containsAll(classWorld)) return node; |
804 HInstruction input = node.checkedInput; | 784 HInstruction input = node.checkedInput; |
805 TypeMask inputType = input.instructionType; | 785 TypeMask inputType = input.instructionType; |
806 return inputType.isInMask(checkedType, classWorld) ? input : node; | 786 return inputType.isInMask(checkedType, classWorld) ? input : node; |
807 } | 787 } |
808 | 788 |
809 VariableElement findConcreteFieldForDynamicAccess(HInstruction receiver, | 789 VariableElement findConcreteFieldForDynamicAccess( |
810 Selector selector) { | 790 HInstruction receiver, Selector selector) { |
811 TypeMask receiverType = receiver.instructionType; | 791 TypeMask receiverType = receiver.instructionType; |
812 return compiler.world.locateSingleField(selector, receiverType); | 792 return compiler.world.locateSingleField(selector, receiverType); |
813 } | 793 } |
814 | 794 |
815 HInstruction visitFieldGet(HFieldGet node) { | 795 HInstruction visitFieldGet(HFieldGet node) { |
816 if (node.isNullCheck) return node; | 796 if (node.isNullCheck) return node; |
817 var receiver = node.receiver; | 797 var receiver = node.receiver; |
818 if (node.element == helpers.jsIndexableLength) { | 798 if (node.element == helpers.jsIndexableLength) { |
819 JavaScriptItemCompilationContext context = work.compilationContext; | 799 JavaScriptItemCompilationContext context = work.compilationContext; |
820 if (context.allocatedFixedLists.contains(receiver)) { | 800 if (context.allocatedFixedLists.contains(receiver)) { |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
875 return node; | 855 return node; |
876 } | 856 } |
877 | 857 |
878 HInstruction visitInvokeDynamicGetter(HInvokeDynamicGetter node) { | 858 HInstruction visitInvokeDynamicGetter(HInvokeDynamicGetter node) { |
879 propagateConstantValueToUses(node); | 859 propagateConstantValueToUses(node); |
880 if (node.isInterceptedCall) { | 860 if (node.isInterceptedCall) { |
881 HInstruction folded = handleInterceptedCall(node); | 861 HInstruction folded = handleInterceptedCall(node); |
882 if (folded != node) return folded; | 862 if (folded != node) return folded; |
883 } | 863 } |
884 HInstruction receiver = node.getDartReceiver(compiler); | 864 HInstruction receiver = node.getDartReceiver(compiler); |
885 Element field = findConcreteFieldForDynamicAccess( | 865 Element field = findConcreteFieldForDynamicAccess(receiver, node.selector); |
886 receiver, node.selector); | |
887 if (field == null) return node; | 866 if (field == null) return node; |
888 return directFieldGet(receiver, field); | 867 return directFieldGet(receiver, field); |
889 } | 868 } |
890 | 869 |
891 HInstruction directFieldGet(HInstruction receiver, Element field) { | 870 HInstruction directFieldGet(HInstruction receiver, Element field) { |
892 bool isAssignable = !compiler.world.fieldNeverChanges(field); | 871 bool isAssignable = !compiler.world.fieldNeverChanges(field); |
893 | 872 |
894 TypeMask type; | 873 TypeMask type; |
895 if (backend.isNative(field.enclosingClass)) { | 874 if (backend.isNative(field.enclosingClass)) { |
896 type = TypeMaskFactory.fromNativeBehavior( | 875 type = TypeMaskFactory.fromNativeBehavior( |
897 native.NativeBehavior.ofFieldLoad(field, compiler), | 876 native.NativeBehavior.ofFieldLoad(field, compiler), compiler); |
898 compiler); | |
899 } else { | 877 } else { |
900 type = TypeMaskFactory.inferredTypeForElement(field, compiler); | 878 type = TypeMaskFactory.inferredTypeForElement(field, compiler); |
901 } | 879 } |
902 | 880 |
903 return new HFieldGet( | 881 return new HFieldGet(field, receiver, type, isAssignable: isAssignable); |
904 field, receiver, type, isAssignable: isAssignable); | |
905 } | 882 } |
906 | 883 |
907 HInstruction visitInvokeDynamicSetter(HInvokeDynamicSetter node) { | 884 HInstruction visitInvokeDynamicSetter(HInvokeDynamicSetter node) { |
908 if (node.isInterceptedCall) { | 885 if (node.isInterceptedCall) { |
909 HInstruction folded = handleInterceptedCall(node); | 886 HInstruction folded = handleInterceptedCall(node); |
910 if (folded != node) return folded; | 887 if (folded != node) return folded; |
911 } | 888 } |
912 | 889 |
913 HInstruction receiver = node.getDartReceiver(compiler); | 890 HInstruction receiver = node.getDartReceiver(compiler); |
914 VariableElement field = | 891 VariableElement field = |
915 findConcreteFieldForDynamicAccess(receiver, node.selector); | 892 findConcreteFieldForDynamicAccess(receiver, node.selector); |
916 if (field == null || !field.isAssignable) return node; | 893 if (field == null || !field.isAssignable) return node; |
917 // Use [:node.inputs.last:] in case the call follows the | 894 // Use [:node.inputs.last:] in case the call follows the |
918 // interceptor calling convention, but is not a call on an | 895 // interceptor calling convention, but is not a call on an |
919 // interceptor. | 896 // interceptor. |
920 HInstruction value = node.inputs.last; | 897 HInstruction value = node.inputs.last; |
921 if (compiler.options.enableTypeAssertions) { | 898 if (compiler.options.enableTypeAssertions) { |
922 DartType type = field.type; | 899 DartType type = field.type; |
923 if (!type.treatAsRaw || type.isTypeVariable) { | 900 if (!type.treatAsRaw || type.isTypeVariable) { |
924 // We cannot generate the correct type representation here, so don't | 901 // We cannot generate the correct type representation here, so don't |
925 // inline this access. | 902 // inline this access. |
926 return node; | 903 return node; |
927 } | 904 } |
928 HInstruction other = value.convertType( | 905 HInstruction other = |
929 compiler, | 906 value.convertType(compiler, type, HTypeConversion.CHECKED_MODE_CHECK); |
930 type, | |
931 HTypeConversion.CHECKED_MODE_CHECK); | |
932 if (other != value) { | 907 if (other != value) { |
933 node.block.addBefore(node, other); | 908 node.block.addBefore(node, other); |
934 value = other; | 909 value = other; |
935 } | 910 } |
936 } | 911 } |
937 return new HFieldSet(field, receiver, value); | 912 return new HFieldSet(field, receiver, value); |
938 } | 913 } |
939 | 914 |
940 HInstruction visitInvokeStatic(HInvokeStatic node) { | 915 HInstruction visitInvokeStatic(HInvokeStatic node) { |
941 propagateConstantValueToUses(node); | 916 propagateConstantValueToUses(node); |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1006 if (!constant.constant.isPrimitive) return node; | 981 if (!constant.constant.isPrimitive) return node; |
1007 if (constant.constant.isInt) { | 982 if (constant.constant.isInt) { |
1008 // Only constant-fold int.toString() when Dart and JS results the same. | 983 // Only constant-fold int.toString() when Dart and JS results the same. |
1009 // TODO(18103): We should be able to remove this work-around when issue | 984 // TODO(18103): We should be able to remove this work-around when issue |
1010 // 18103 is resolved by providing the correct string. | 985 // 18103 is resolved by providing the correct string. |
1011 IntConstantValue intConstant = constant.constant; | 986 IntConstantValue intConstant = constant.constant; |
1012 // Very conservative range. | 987 // Very conservative range. |
1013 if (!intConstant.isUInt32()) return node; | 988 if (!intConstant.isUInt32()) return node; |
1014 } | 989 } |
1015 PrimitiveConstantValue primitive = constant.constant; | 990 PrimitiveConstantValue primitive = constant.constant; |
1016 return graph.addConstant(constantSystem.createString( | 991 return graph.addConstant( |
1017 primitive.toDartString()), compiler); | 992 constantSystem.createString(primitive.toDartString()), compiler); |
1018 } | 993 } |
1019 return node; | 994 return node; |
1020 } | 995 } |
1021 | 996 |
1022 HInstruction visitOneShotInterceptor(HOneShotInterceptor node) { | 997 HInstruction visitOneShotInterceptor(HOneShotInterceptor node) { |
1023 return handleInterceptedCall(node); | 998 return handleInterceptedCall(node); |
1024 } | 999 } |
1025 } | 1000 } |
1026 | 1001 |
1027 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase { | 1002 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase { |
1028 final Set<HInstruction> boundsChecked; | 1003 final Set<HInstruction> boundsChecked; |
1029 final CodegenWorkItem work; | 1004 final CodegenWorkItem work; |
1030 final bool trustPrimitives; | 1005 final bool trustPrimitives; |
1031 final JavaScriptBackend backend; | 1006 final JavaScriptBackend backend; |
1032 final String name = "SsaCheckInserter"; | 1007 final String name = "SsaCheckInserter"; |
1033 HGraph graph; | 1008 HGraph graph; |
1034 | 1009 |
1035 SsaCheckInserter(this.trustPrimitives, | 1010 SsaCheckInserter( |
1036 this.backend, | 1011 this.trustPrimitives, this.backend, this.work, this.boundsChecked); |
1037 this.work, | |
1038 this.boundsChecked); | |
1039 | 1012 |
1040 BackendHelpers get helpers => backend.helpers; | 1013 BackendHelpers get helpers => backend.helpers; |
1041 | 1014 |
1042 void visitGraph(HGraph graph) { | 1015 void visitGraph(HGraph graph) { |
1043 this.graph = graph; | 1016 this.graph = graph; |
1044 | 1017 |
1045 // In --trust-primitives mode we don't add bounds checks. This is better | 1018 // In --trust-primitives mode we don't add bounds checks. This is better |
1046 // than trying to remove them later as the limit expression would become | 1019 // than trying to remove them later as the limit expression would become |
1047 // dead and require DCE. | 1020 // dead and require DCE. |
1048 if (trustPrimitives) return; | 1021 if (trustPrimitives) return; |
1049 | 1022 |
1050 visitDominatorTree(graph); | 1023 visitDominatorTree(graph); |
1051 } | 1024 } |
1052 | 1025 |
1053 void visitBasicBlock(HBasicBlock block) { | 1026 void visitBasicBlock(HBasicBlock block) { |
1054 HInstruction instruction = block.first; | 1027 HInstruction instruction = block.first; |
1055 while (instruction != null) { | 1028 while (instruction != null) { |
1056 HInstruction next = instruction.next; | 1029 HInstruction next = instruction.next; |
1057 instruction = instruction.accept(this); | 1030 instruction = instruction.accept(this); |
1058 instruction = next; | 1031 instruction = next; |
1059 } | 1032 } |
1060 } | 1033 } |
1061 | 1034 |
1062 HBoundsCheck insertBoundsCheck(HInstruction indexNode, | 1035 HBoundsCheck insertBoundsCheck( |
1063 HInstruction array, | 1036 HInstruction indexNode, HInstruction array, HInstruction indexArgument) { |
1064 HInstruction indexArgument) { | |
1065 Compiler compiler = backend.compiler; | 1037 Compiler compiler = backend.compiler; |
1066 HFieldGet length = new HFieldGet( | 1038 HFieldGet length = new HFieldGet( |
1067 helpers.jsIndexableLength, array, backend.positiveIntType, | 1039 helpers.jsIndexableLength, array, backend.positiveIntType, |
1068 isAssignable: !isFixedLength(array.instructionType, compiler)); | 1040 isAssignable: !isFixedLength(array.instructionType, compiler)); |
1069 indexNode.block.addBefore(indexNode, length); | 1041 indexNode.block.addBefore(indexNode, length); |
1070 | 1042 |
1071 TypeMask type = indexArgument.isPositiveInteger(compiler) | 1043 TypeMask type = indexArgument.isPositiveInteger(compiler) |
1072 ? indexArgument.instructionType | 1044 ? indexArgument.instructionType |
1073 : backend.positiveIntType; | 1045 : backend.positiveIntType; |
1074 HBoundsCheck check = new HBoundsCheck( | 1046 HBoundsCheck check = new HBoundsCheck(indexArgument, length, array, type); |
1075 indexArgument, length, array, type); | |
1076 indexNode.block.addBefore(indexNode, check); | 1047 indexNode.block.addBefore(indexNode, check); |
1077 // If the index input to the bounds check was not known to be an integer | 1048 // If the index input to the bounds check was not known to be an integer |
1078 // then we replace its uses with the bounds check, which is known to be an | 1049 // then we replace its uses with the bounds check, which is known to be an |
1079 // integer. However, if the input was already an integer we don't do this | 1050 // integer. However, if the input was already an integer we don't do this |
1080 // because putting in a check instruction might obscure the real nature of | 1051 // because putting in a check instruction might obscure the real nature of |
1081 // the index eg. if it is a constant. The range information from the | 1052 // the index eg. if it is a constant. The range information from the |
1082 // BoundsCheck instruction is attached to the input directly by | 1053 // BoundsCheck instruction is attached to the input directly by |
1083 // visitBoundsCheck in the SsaValueRangeAnalyzer. | 1054 // visitBoundsCheck in the SsaValueRangeAnalyzer. |
1084 if (!indexArgument.isInteger(compiler)) { | 1055 if (!indexArgument.isInteger(compiler)) { |
1085 indexArgument.replaceAllUsersDominatedBy(indexNode, check); | 1056 indexArgument.replaceAllUsersDominatedBy(indexNode, check); |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1124 Map<HInstruction, bool> trivialDeadStoreReceivers = | 1095 Map<HInstruction, bool> trivialDeadStoreReceivers = |
1125 new Maplet<HInstruction, bool>(); | 1096 new Maplet<HInstruction, bool>(); |
1126 bool eliminatedSideEffects = false; | 1097 bool eliminatedSideEffects = false; |
1127 | 1098 |
1128 SsaDeadCodeEliminator(this.compiler, this.optimizer); | 1099 SsaDeadCodeEliminator(this.compiler, this.optimizer); |
1129 | 1100 |
1130 HInstruction zapInstructionCache; | 1101 HInstruction zapInstructionCache; |
1131 HInstruction get zapInstruction { | 1102 HInstruction get zapInstruction { |
1132 if (zapInstructionCache == null) { | 1103 if (zapInstructionCache == null) { |
1133 // A constant with no type does not pollute types at phi nodes. | 1104 // A constant with no type does not pollute types at phi nodes. |
1134 ConstantValue constant = | 1105 ConstantValue constant = new SyntheticConstantValue( |
1135 new SyntheticConstantValue( | 1106 SyntheticConstantKind.EMPTY_VALUE, const TypeMask.nonNullEmpty()); |
1136 SyntheticConstantKind.EMPTY_VALUE, | |
1137 const TypeMask.nonNullEmpty()); | |
1138 zapInstructionCache = analyzer.graph.addConstant(constant, compiler); | 1107 zapInstructionCache = analyzer.graph.addConstant(constant, compiler); |
1139 } | 1108 } |
1140 return zapInstructionCache; | 1109 return zapInstructionCache; |
1141 } | 1110 } |
1142 | 1111 |
1143 /// Returns true of [foreign] will throw an noSuchMethod error if | 1112 /// Returns true of [foreign] will throw an noSuchMethod error if |
1144 /// receiver is `null` before having any other side-effects. | 1113 /// receiver is `null` before having any other side-effects. |
1145 bool templateThrowsNSMonNull(HForeignCode foreign, HInstruction receiver) { | 1114 bool templateThrowsNSMonNull(HForeignCode foreign, HInstruction receiver) { |
1146 if (foreign.inputs.length < 1) return false; | 1115 if (foreign.inputs.length < 1) return false; |
1147 if (foreign.inputs.first != receiver) return false; | 1116 if (foreign.inputs.first != receiver) return false; |
(...skipping 26 matching lines...) Expand all Loading... |
1174 return false; | 1143 return false; |
1175 } | 1144 } |
1176 | 1145 |
1177 /// Returns whether the next throwing instruction that may have side | 1146 /// Returns whether the next throwing instruction that may have side |
1178 /// effects after [instruction], throws [NoSuchMethodError] on the | 1147 /// effects after [instruction], throws [NoSuchMethodError] on the |
1179 /// same receiver of [instruction]. | 1148 /// same receiver of [instruction]. |
1180 bool hasFollowingThrowingNSM(HInstruction instruction) { | 1149 bool hasFollowingThrowingNSM(HInstruction instruction) { |
1181 HInstruction receiver = instruction.getDartReceiver(compiler); | 1150 HInstruction receiver = instruction.getDartReceiver(compiler); |
1182 HInstruction current = instruction.next; | 1151 HInstruction current = instruction.next; |
1183 do { | 1152 do { |
1184 if ((current.getDartReceiver(compiler) == receiver) | 1153 if ((current.getDartReceiver(compiler) == receiver) && |
1185 && current.canThrow()) { | 1154 current.canThrow()) { |
1186 return true; | 1155 return true; |
1187 } | 1156 } |
1188 if (current is HForeignCode && | 1157 if (current is HForeignCode && |
1189 templateThrowsNSMonNull(current, receiver)) { | 1158 templateThrowsNSMonNull(current, receiver)) { |
1190 return true; | 1159 return true; |
1191 } | 1160 } |
1192 if (current.canThrow() || current.sideEffects.hasSideEffects()) { | 1161 if (current.canThrow() || current.sideEffects.hasSideEffects()) { |
1193 return false; | 1162 return false; |
1194 } | 1163 } |
1195 HInstruction next = current.next; | 1164 HInstruction next = current.next; |
(...skipping 29 matching lines...) Expand all Loading... |
1225 if (use is HFieldSet) { | 1194 if (use is HFieldSet) { |
1226 // The use must be the receiver. Even if the use is also the argument, | 1195 // The use must be the receiver. Even if the use is also the argument, |
1227 // i.e. a.x = a, the store is still dead if all other uses are dead. | 1196 // i.e. a.x = a, the store is still dead if all other uses are dead. |
1228 if (use.getDartReceiver(compiler) == instruction) return true; | 1197 if (use.getDartReceiver(compiler) == instruction) return true; |
1229 } else if (use is HFieldGet) { | 1198 } else if (use is HFieldGet) { |
1230 assert(use.getDartReceiver(compiler) == instruction); | 1199 assert(use.getDartReceiver(compiler) == instruction); |
1231 if (isDeadCode(use)) return true; | 1200 if (isDeadCode(use)) return true; |
1232 } | 1201 } |
1233 return false; | 1202 return false; |
1234 } | 1203 } |
1235 return instruction.isAllocation | 1204 return instruction.isAllocation && |
1236 && instruction.isPure() | 1205 instruction.isPure() && |
1237 && trivialDeadStoreReceivers.putIfAbsent(instruction, | 1206 trivialDeadStoreReceivers.putIfAbsent( |
1238 () => instruction.usedBy.every(isDeadUse)); | 1207 instruction, () => instruction.usedBy.every(isDeadUse)); |
1239 } | 1208 } |
1240 | 1209 |
1241 bool isTrivialDeadStore(HInstruction instruction) { | 1210 bool isTrivialDeadStore(HInstruction instruction) { |
1242 return instruction is HFieldSet | 1211 return instruction is HFieldSet && |
1243 && isTrivialDeadStoreReceiver(instruction.getDartReceiver(compiler)); | 1212 isTrivialDeadStoreReceiver(instruction.getDartReceiver(compiler)); |
1244 } | 1213 } |
1245 | 1214 |
1246 bool isDeadCode(HInstruction instruction) { | 1215 bool isDeadCode(HInstruction instruction) { |
1247 if (!instruction.usedBy.isEmpty) return false; | 1216 if (!instruction.usedBy.isEmpty) return false; |
1248 if (isTrivialDeadStore(instruction)) return true; | 1217 if (isTrivialDeadStore(instruction)) return true; |
1249 if (instruction.sideEffects.hasSideEffects()) return false; | 1218 if (instruction.sideEffects.hasSideEffects()) return false; |
1250 if (instruction.canThrow() && | 1219 if (instruction.canThrow() && |
1251 instruction.onlyThrowsNSM() && | 1220 instruction.onlyThrowsNSM() && |
1252 hasFollowingThrowingNSM(instruction)) { | 1221 hasFollowingThrowingNSM(instruction)) { |
1253 return true; | 1222 return true; |
1254 } | 1223 } |
1255 return !instruction.canThrow() | 1224 return !instruction.canThrow() && |
1256 && instruction is !HParameterValue | 1225 instruction is! HParameterValue && |
1257 && instruction is !HLocalSet; | 1226 instruction is! HLocalSet; |
1258 } | 1227 } |
1259 | 1228 |
1260 void visitGraph(HGraph graph) { | 1229 void visitGraph(HGraph graph) { |
1261 analyzer = new SsaLiveBlockAnalyzer(graph, compiler, optimizer); | 1230 analyzer = new SsaLiveBlockAnalyzer(graph, compiler, optimizer); |
1262 analyzer.analyze(); | 1231 analyzer.analyze(); |
1263 visitPostDominatorTree(graph); | 1232 visitPostDominatorTree(graph); |
1264 cleanPhis(graph); | 1233 cleanPhis(graph); |
1265 } | 1234 } |
1266 | 1235 |
1267 void visitBasicBlock(HBasicBlock block) { | 1236 void visitBasicBlock(HBasicBlock block) { |
1268 bool isDeadBlock = analyzer.isDeadBlock(block); | 1237 bool isDeadBlock = analyzer.isDeadBlock(block); |
1269 block.isLive = !isDeadBlock; | 1238 block.isLive = !isDeadBlock; |
1270 // Start from the last non-control flow instruction in the block. | 1239 // Start from the last non-control flow instruction in the block. |
1271 HInstruction instruction = block.last.previous; | 1240 HInstruction instruction = block.last.previous; |
1272 while (instruction != null) { | 1241 while (instruction != null) { |
1273 var previous = instruction.previous; | 1242 var previous = instruction.previous; |
1274 if (isDeadBlock) { | 1243 if (isDeadBlock) { |
1275 eliminatedSideEffects = eliminatedSideEffects || | 1244 eliminatedSideEffects = |
1276 instruction.sideEffects.hasSideEffects(); | 1245 eliminatedSideEffects || instruction.sideEffects.hasSideEffects(); |
1277 removeUsers(instruction); | 1246 removeUsers(instruction); |
1278 block.remove(instruction); | 1247 block.remove(instruction); |
1279 } else if (isDeadCode(instruction)) { | 1248 } else if (isDeadCode(instruction)) { |
1280 block.remove(instruction); | 1249 block.remove(instruction); |
1281 } | 1250 } |
1282 instruction = previous; | 1251 instruction = previous; |
1283 } | 1252 } |
1284 } | 1253 } |
1285 | 1254 |
1286 void cleanPhis(HGraph graph) { | 1255 void cleanPhis(HGraph graph) { |
(...skipping 12 matching lines...) Expand all Loading... |
1299 int indexOfLive = -1; | 1268 int indexOfLive = -1; |
1300 for (int i = 0; i < predecessors.length; i++) { | 1269 for (int i = 0; i < predecessors.length; i++) { |
1301 if (predecessors[i].isLive) { | 1270 if (predecessors[i].isLive) { |
1302 if (indexOfLive >= 0) continue L; | 1271 if (indexOfLive >= 0) continue L; |
1303 indexOfLive = i; | 1272 indexOfLive = i; |
1304 } | 1273 } |
1305 } | 1274 } |
1306 // Run through the phis of the block and replace them with their input | 1275 // Run through the phis of the block and replace them with their input |
1307 // that comes from the only live predecessor if that dominates the phi. | 1276 // that comes from the only live predecessor if that dominates the phi. |
1308 block.forEachPhi((HPhi phi) { | 1277 block.forEachPhi((HPhi phi) { |
1309 HInstruction replacement = (indexOfLive >= 0) | 1278 HInstruction replacement = |
1310 ? phi.inputs[indexOfLive] : zapInstruction; | 1279 (indexOfLive >= 0) ? phi.inputs[indexOfLive] : zapInstruction; |
1311 if (replacement.dominates(phi)) { | 1280 if (replacement.dominates(phi)) { |
1312 block.rewrite(phi, replacement); | 1281 block.rewrite(phi, replacement); |
1313 block.removePhi(phi); | 1282 block.removePhi(phi); |
1314 } | 1283 } |
1315 }); | 1284 }); |
1316 } | 1285 } |
1317 } | 1286 } |
1318 | 1287 |
1319 void replaceInput(int i, HInstruction from, HInstruction by) { | 1288 void replaceInput(int i, HInstruction from, HInstruction by) { |
1320 from.inputs[i].usedBy.remove(from); | 1289 from.inputs[i].usedBy.remove(from); |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1394 IntValue lowerValue = switchRange.lower; | 1363 IntValue lowerValue = switchRange.lower; |
1395 IntValue upperValue = switchRange.upper; | 1364 IntValue upperValue = switchRange.upper; |
1396 int lower = lowerValue.value; | 1365 int lower = lowerValue.value; |
1397 int upper = upperValue.value; | 1366 int upper = upperValue.value; |
1398 Set<int> liveLabels = new Set<int>(); | 1367 Set<int> liveLabels = new Set<int>(); |
1399 for (int pos = 1; pos < node.inputs.length; pos++) { | 1368 for (int pos = 1; pos < node.inputs.length; pos++) { |
1400 HConstant input = node.inputs[pos]; | 1369 HConstant input = node.inputs[pos]; |
1401 if (!input.isConstantInteger()) continue; | 1370 if (!input.isConstantInteger()) continue; |
1402 IntConstantValue constant = input.constant; | 1371 IntConstantValue constant = input.constant; |
1403 int label = constant.primitiveValue; | 1372 int label = constant.primitiveValue; |
1404 if (!liveLabels.contains(label) && | 1373 if (!liveLabels.contains(label) && label <= upper && label >= lower) { |
1405 label <= upper && | |
1406 label >= lower) { | |
1407 markBlockLive(node.block.successors[pos - 1]); | 1374 markBlockLive(node.block.successors[pos - 1]); |
1408 liveLabels.add(label); | 1375 liveLabels.add(label); |
1409 } | 1376 } |
1410 } | 1377 } |
1411 if (liveLabels.length != upper - lower + 1) { | 1378 if (liveLabels.length != upper - lower + 1) { |
1412 markBlockLive(node.defaultTarget); | 1379 markBlockLive(node.defaultTarget); |
1413 } | 1380 } |
1414 return; | 1381 return; |
1415 } | 1382 } |
1416 } | 1383 } |
1417 visitControlFlow(node); | 1384 visitControlFlow(node); |
1418 } | 1385 } |
1419 } | 1386 } |
1420 | 1387 |
1421 class SsaDeadPhiEliminator implements OptimizationPhase { | 1388 class SsaDeadPhiEliminator implements OptimizationPhase { |
1422 final String name = "SsaDeadPhiEliminator"; | 1389 final String name = "SsaDeadPhiEliminator"; |
1423 | 1390 |
1424 void visitGraph(HGraph graph) { | 1391 void visitGraph(HGraph graph) { |
1425 final List<HPhi> worklist = <HPhi>[]; | 1392 final List<HPhi> worklist = <HPhi>[]; |
1426 // A set to keep track of the live phis that we found. | 1393 // A set to keep track of the live phis that we found. |
1427 final Set<HPhi> livePhis = new Set<HPhi>(); | 1394 final Set<HPhi> livePhis = new Set<HPhi>(); |
1428 | 1395 |
1429 // Add to the worklist all live phis: phis referenced by non-phi | 1396 // Add to the worklist all live phis: phis referenced by non-phi |
1430 // instructions. | 1397 // instructions. |
1431 for (final block in graph.blocks) { | 1398 for (final block in graph.blocks) { |
1432 block.forEachPhi((HPhi phi) { | 1399 block.forEachPhi((HPhi phi) { |
1433 for (final user in phi.usedBy) { | 1400 for (final user in phi.usedBy) { |
1434 if (user is !HPhi) { | 1401 if (user is! HPhi) { |
1435 worklist.add(phi); | 1402 worklist.add(phi); |
1436 livePhis.add(phi); | 1403 livePhis.add(phi); |
1437 break; | 1404 break; |
1438 } | 1405 } |
1439 } | 1406 } |
1440 }); | 1407 }); |
1441 } | 1408 } |
1442 | 1409 |
1443 // Process the worklist by propagating liveness to phi inputs. | 1410 // Process the worklist by propagating liveness to phi inputs. |
1444 while (!worklist.isEmpty) { | 1411 while (!worklist.isEmpty) { |
(...skipping 13 matching lines...) Expand all Loading... |
1458 // create any. | 1425 // create any. |
1459 List<HBasicBlock> blocks = graph.blocks; | 1426 List<HBasicBlock> blocks = graph.blocks; |
1460 for (int i = blocks.length - 1; i >= 0; i--) { | 1427 for (int i = blocks.length - 1; i >= 0; i--) { |
1461 HBasicBlock block = blocks[i]; | 1428 HBasicBlock block = blocks[i]; |
1462 HPhi current = block.phis.first; | 1429 HPhi current = block.phis.first; |
1463 HPhi next = null; | 1430 HPhi next = null; |
1464 while (current != null) { | 1431 while (current != null) { |
1465 next = current.next; | 1432 next = current.next; |
1466 if (!livePhis.contains(current) | 1433 if (!livePhis.contains(current) |
1467 // TODO(ahe): Not sure the following is correct. | 1434 // TODO(ahe): Not sure the following is correct. |
1468 && current.usedBy.isEmpty) { | 1435 && |
| 1436 current.usedBy.isEmpty) { |
1469 block.removePhi(current); | 1437 block.removePhi(current); |
1470 } | 1438 } |
1471 current = next; | 1439 current = next; |
1472 } | 1440 } |
1473 } | 1441 } |
1474 } | 1442 } |
1475 } | 1443 } |
1476 | 1444 |
1477 class SsaRedundantPhiEliminator implements OptimizationPhase { | 1445 class SsaRedundantPhiEliminator implements OptimizationPhase { |
1478 final String name = "SsaRedundantPhiEliminator"; | 1446 final String name = "SsaRedundantPhiEliminator"; |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1533 final Set<int> visited; | 1501 final Set<int> visited; |
1534 | 1502 |
1535 List<int> blockChangesFlags; | 1503 List<int> blockChangesFlags; |
1536 List<int> loopChangesFlags; | 1504 List<int> loopChangesFlags; |
1537 | 1505 |
1538 SsaGlobalValueNumberer(this.compiler) : visited = new Set<int>(); | 1506 SsaGlobalValueNumberer(this.compiler) : visited = new Set<int>(); |
1539 | 1507 |
1540 void visitGraph(HGraph graph) { | 1508 void visitGraph(HGraph graph) { |
1541 computeChangesFlags(graph); | 1509 computeChangesFlags(graph); |
1542 moveLoopInvariantCode(graph); | 1510 moveLoopInvariantCode(graph); |
1543 List<GvnWorkItem> workQueue = | 1511 List<GvnWorkItem> workQueue = <GvnWorkItem>[ |
1544 <GvnWorkItem>[new GvnWorkItem(graph.entry, new ValueSet())]; | 1512 new GvnWorkItem(graph.entry, new ValueSet()) |
| 1513 ]; |
1545 do { | 1514 do { |
1546 GvnWorkItem item = workQueue.removeLast(); | 1515 GvnWorkItem item = workQueue.removeLast(); |
1547 visitBasicBlock(item.block, item.valueSet, workQueue); | 1516 visitBasicBlock(item.block, item.valueSet, workQueue); |
1548 } while (!workQueue.isEmpty); | 1517 } while (!workQueue.isEmpty); |
1549 } | 1518 } |
1550 | 1519 |
1551 void moveLoopInvariantCode(HGraph graph) { | 1520 void moveLoopInvariantCode(HGraph graph) { |
1552 for (int i = graph.blocks.length - 1; i >= 0; i--) { | 1521 for (int i = graph.blocks.length - 1; i >= 0; i--) { |
1553 HBasicBlock block = graph.blocks[i]; | 1522 HBasicBlock block = graph.blocks[i]; |
1554 if (block.isLoopHeader()) { | 1523 if (block.isLoopHeader()) { |
1555 int changesFlags = loopChangesFlags[block.id]; | 1524 int changesFlags = loopChangesFlags[block.id]; |
1556 HLoopInformation info = block.loopInformation; | 1525 HLoopInformation info = block.loopInformation; |
1557 // Iterate over all blocks of this loop. Note that blocks in | 1526 // Iterate over all blocks of this loop. Note that blocks in |
1558 // inner loops are not visited here, but we know they | 1527 // inner loops are not visited here, but we know they |
1559 // were visited before because we are iterating in post-order. | 1528 // were visited before because we are iterating in post-order. |
1560 // So instructions that are GVN'ed in an inner loop are in their | 1529 // So instructions that are GVN'ed in an inner loop are in their |
1561 // loop entry, and [info.blocks] contains this loop entry. | 1530 // loop entry, and [info.blocks] contains this loop entry. |
1562 moveLoopInvariantCodeFromBlock(block, block, changesFlags); | 1531 moveLoopInvariantCodeFromBlock(block, block, changesFlags); |
1563 for (HBasicBlock other in info.blocks) { | 1532 for (HBasicBlock other in info.blocks) { |
1564 moveLoopInvariantCodeFromBlock(other, block, changesFlags); | 1533 moveLoopInvariantCodeFromBlock(other, block, changesFlags); |
1565 } | 1534 } |
1566 } | 1535 } |
1567 } | 1536 } |
1568 } | 1537 } |
1569 | 1538 |
1570 void moveLoopInvariantCodeFromBlock(HBasicBlock block, | 1539 void moveLoopInvariantCodeFromBlock( |
1571 HBasicBlock loopHeader, | 1540 HBasicBlock block, HBasicBlock loopHeader, int changesFlags) { |
1572 int changesFlags) { | |
1573 assert(block.parentLoopHeader == loopHeader || block == loopHeader); | 1541 assert(block.parentLoopHeader == loopHeader || block == loopHeader); |
1574 HBasicBlock preheader = loopHeader.predecessors[0]; | 1542 HBasicBlock preheader = loopHeader.predecessors[0]; |
1575 int dependsFlags = SideEffects.computeDependsOnFlags(changesFlags); | 1543 int dependsFlags = SideEffects.computeDependsOnFlags(changesFlags); |
1576 HInstruction instruction = block.first; | 1544 HInstruction instruction = block.first; |
1577 bool isLoopAlwaysTaken() { | 1545 bool isLoopAlwaysTaken() { |
1578 HInstruction instruction = loopHeader.last; | 1546 HInstruction instruction = loopHeader.last; |
1579 assert(instruction is HGoto || instruction is HLoopBranch); | 1547 assert(instruction is HGoto || instruction is HLoopBranch); |
1580 return instruction is HGoto | 1548 return instruction is HGoto || instruction.inputs[0].isConstantTrue(); |
1581 || instruction.inputs[0].isConstantTrue(); | |
1582 } | 1549 } |
1583 bool firstInstructionInLoop = block == loopHeader | 1550 bool firstInstructionInLoop = block == loopHeader |
1584 // Compensate for lack of code motion. | 1551 // Compensate for lack of code motion. |
1585 || (blockChangesFlags[loopHeader.id] == 0 | 1552 || |
1586 && isLoopAlwaysTaken() | 1553 (blockChangesFlags[loopHeader.id] == 0 && |
1587 && loopHeader.successors[0] == block); | 1554 isLoopAlwaysTaken() && |
| 1555 loopHeader.successors[0] == block); |
1588 while (instruction != null) { | 1556 while (instruction != null) { |
1589 HInstruction next = instruction.next; | 1557 HInstruction next = instruction.next; |
1590 if (instruction.useGvn() && instruction.isMovable | 1558 if (instruction.useGvn() && |
1591 && (!instruction.canThrow() || firstInstructionInLoop) | 1559 instruction.isMovable && |
1592 && !instruction.sideEffects.dependsOn(dependsFlags)) { | 1560 (!instruction.canThrow() || firstInstructionInLoop) && |
| 1561 !instruction.sideEffects.dependsOn(dependsFlags)) { |
1593 bool loopInvariantInputs = true; | 1562 bool loopInvariantInputs = true; |
1594 List<HInstruction> inputs = instruction.inputs; | 1563 List<HInstruction> inputs = instruction.inputs; |
1595 for (int i = 0, length = inputs.length; i < length; i++) { | 1564 for (int i = 0, length = inputs.length; i < length; i++) { |
1596 if (isInputDefinedAfterDominator(inputs[i], preheader)) { | 1565 if (isInputDefinedAfterDominator(inputs[i], preheader)) { |
1597 loopInvariantInputs = false; | 1566 loopInvariantInputs = false; |
1598 break; | 1567 break; |
1599 } | 1568 } |
1600 } | 1569 } |
1601 | 1570 |
1602 // If the inputs are loop invariant, we can move the | 1571 // If the inputs are loop invariant, we can move the |
1603 // instruction from the current block to the pre-header block. | 1572 // instruction from the current block to the pre-header block. |
1604 if (loopInvariantInputs) { | 1573 if (loopInvariantInputs) { |
1605 block.detach(instruction); | 1574 block.detach(instruction); |
1606 preheader.moveAtExit(instruction); | 1575 preheader.moveAtExit(instruction); |
1607 } else { | 1576 } else { |
1608 firstInstructionInLoop = false; | 1577 firstInstructionInLoop = false; |
1609 } | 1578 } |
1610 } | 1579 } |
1611 int oldChangesFlags = changesFlags; | 1580 int oldChangesFlags = changesFlags; |
1612 changesFlags |= instruction.sideEffects.getChangesFlags(); | 1581 changesFlags |= instruction.sideEffects.getChangesFlags(); |
1613 if (oldChangesFlags != changesFlags) { | 1582 if (oldChangesFlags != changesFlags) { |
1614 dependsFlags = SideEffects.computeDependsOnFlags(changesFlags); | 1583 dependsFlags = SideEffects.computeDependsOnFlags(changesFlags); |
1615 } | 1584 } |
1616 instruction = next; | 1585 instruction = next; |
1617 } | 1586 } |
1618 } | 1587 } |
1619 | 1588 |
1620 bool isInputDefinedAfterDominator(HInstruction input, | 1589 bool isInputDefinedAfterDominator(HInstruction input, HBasicBlock dominator) { |
1621 HBasicBlock dominator) { | |
1622 return input.block.id > dominator.id; | 1590 return input.block.id > dominator.id; |
1623 } | 1591 } |
1624 | 1592 |
1625 void visitBasicBlock( | 1593 void visitBasicBlock( |
1626 HBasicBlock block, ValueSet values, List<GvnWorkItem> workQueue) { | 1594 HBasicBlock block, ValueSet values, List<GvnWorkItem> workQueue) { |
1627 HInstruction instruction = block.first; | 1595 HInstruction instruction = block.first; |
1628 if (block.isLoopHeader()) { | 1596 if (block.isLoopHeader()) { |
1629 int flags = loopChangesFlags[block.id]; | 1597 int flags = loopChangesFlags[block.id]; |
1630 values.kill(flags); | 1598 values.kill(flags); |
1631 } | 1599 } |
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1700 | 1668 |
1701 // Loop headers are part of their loop, so update the loop | 1669 // Loop headers are part of their loop, so update the loop |
1702 // changes flags accordingly. | 1670 // changes flags accordingly. |
1703 if (block.isLoopHeader()) { | 1671 if (block.isLoopHeader()) { |
1704 loopChangesFlags[id] |= changesFlags; | 1672 loopChangesFlags[id] |= changesFlags; |
1705 } | 1673 } |
1706 | 1674 |
1707 // Propagate loop changes flags upwards. | 1675 // Propagate loop changes flags upwards. |
1708 HBasicBlock parentLoopHeader = block.parentLoopHeader; | 1676 HBasicBlock parentLoopHeader = block.parentLoopHeader; |
1709 if (parentLoopHeader != null) { | 1677 if (parentLoopHeader != null) { |
1710 loopChangesFlags[parentLoopHeader.id] |= (block.isLoopHeader()) | 1678 loopChangesFlags[parentLoopHeader.id] |= |
1711 ? loopChangesFlags[id] | 1679 (block.isLoopHeader()) ? loopChangesFlags[id] : changesFlags; |
1712 : changesFlags; | |
1713 } | 1680 } |
1714 } | 1681 } |
1715 } | 1682 } |
1716 | 1683 |
1717 int getChangesFlagsForDominatedBlock(HBasicBlock dominator, | 1684 int getChangesFlagsForDominatedBlock(HBasicBlock dominator, |
1718 HBasicBlock dominated, | 1685 HBasicBlock dominated, List<HBasicBlock> workQueue) { |
1719 List<HBasicBlock> workQueue) { | |
1720 int changesFlags = 0; | 1686 int changesFlags = 0; |
1721 List<HBasicBlock> predecessors = dominated.predecessors; | 1687 List<HBasicBlock> predecessors = dominated.predecessors; |
1722 for (int i = 0, length = predecessors.length; i < length; i++) { | 1688 for (int i = 0, length = predecessors.length; i < length; i++) { |
1723 HBasicBlock block = predecessors[i]; | 1689 HBasicBlock block = predecessors[i]; |
1724 int id = block.id; | 1690 int id = block.id; |
1725 // If the current predecessor block is on the path from the | 1691 // If the current predecessor block is on the path from the |
1726 // dominator to the dominated, it must have an id that is in the | 1692 // dominator to the dominated, it must have an id that is in the |
1727 // range from the dominator to the dominated. | 1693 // range from the dominator to the dominated. |
1728 if (dominator.id < id && id < dominated.id && !visited.contains(id)) { | 1694 if (dominator.id < id && id < dominated.id && !visited.contains(id)) { |
1729 visited.add(id); | 1695 visited.add(id); |
(...skipping 114 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1844 SsaTypeConversionInserter(this.compiler); | 1810 SsaTypeConversionInserter(this.compiler); |
1845 | 1811 |
1846 void visitGraph(HGraph graph) { | 1812 void visitGraph(HGraph graph) { |
1847 visitDominatorTree(graph); | 1813 visitDominatorTree(graph); |
1848 } | 1814 } |
1849 | 1815 |
1850 // Update users of [input] that are dominated by [:dominator.first:] | 1816 // Update users of [input] that are dominated by [:dominator.first:] |
1851 // to use [TypeKnown] of [input] instead. As the type information depends | 1817 // to use [TypeKnown] of [input] instead. As the type information depends |
1852 // on the control flow, we mark the inserted [HTypeKnown] nodes as | 1818 // on the control flow, we mark the inserted [HTypeKnown] nodes as |
1853 // non-movable. | 1819 // non-movable. |
1854 void insertTypePropagationForDominatedUsers(HBasicBlock dominator, | 1820 void insertTypePropagationForDominatedUsers( |
1855 HInstruction input, | 1821 HBasicBlock dominator, HInstruction input, TypeMask convertedType) { |
1856 TypeMask convertedType) { | |
1857 Setlet<HInstruction> dominatedUsers = input.dominatedUsers(dominator.first); | 1822 Setlet<HInstruction> dominatedUsers = input.dominatedUsers(dominator.first); |
1858 if (dominatedUsers.isEmpty) return; | 1823 if (dominatedUsers.isEmpty) return; |
1859 | 1824 |
1860 HTypeKnown newInput = new HTypeKnown.pinned(convertedType, input); | 1825 HTypeKnown newInput = new HTypeKnown.pinned(convertedType, input); |
1861 dominator.addBefore(dominator.first, newInput); | 1826 dominator.addBefore(dominator.first, newInput); |
1862 dominatedUsers.forEach((HInstruction user) { | 1827 dominatedUsers.forEach((HInstruction user) { |
1863 user.changeUse(input, newInput); | 1828 user.changeUse(input, newInput); |
1864 }); | 1829 }); |
1865 } | 1830 } |
1866 | 1831 |
(...skipping 11 matching lines...) Expand all Loading... |
1878 | 1843 |
1879 collectIfUsers(instruction, ifUsers, notIfUsers); | 1844 collectIfUsers(instruction, ifUsers, notIfUsers); |
1880 | 1845 |
1881 if (ifUsers.isEmpty && notIfUsers.isEmpty) return; | 1846 if (ifUsers.isEmpty && notIfUsers.isEmpty) return; |
1882 | 1847 |
1883 TypeMask convertedType = | 1848 TypeMask convertedType = |
1884 new TypeMask.nonNullSubtype(element, compiler.world); | 1849 new TypeMask.nonNullSubtype(element, compiler.world); |
1885 HInstruction input = instruction.expression; | 1850 HInstruction input = instruction.expression; |
1886 | 1851 |
1887 for (HIf ifUser in ifUsers) { | 1852 for (HIf ifUser in ifUsers) { |
1888 insertTypePropagationForDominatedUsers(ifUser.thenBlock, input, | 1853 insertTypePropagationForDominatedUsers( |
1889 convertedType); | 1854 ifUser.thenBlock, input, convertedType); |
1890 // TODO(ngeoffray): Also change uses for the else block on a type | 1855 // TODO(ngeoffray): Also change uses for the else block on a type |
1891 // that knows it is not of a specific type. | 1856 // that knows it is not of a specific type. |
1892 } | 1857 } |
1893 for (HIf ifUser in notIfUsers) { | 1858 for (HIf ifUser in notIfUsers) { |
1894 insertTypePropagationForDominatedUsers(ifUser.elseBlock, input, | 1859 insertTypePropagationForDominatedUsers( |
1895 convertedType); | 1860 ifUser.elseBlock, input, convertedType); |
1896 // TODO(ngeoffray): Also change uses for the then block on a type | 1861 // TODO(ngeoffray): Also change uses for the then block on a type |
1897 // that knows it is not of a specific type. | 1862 // that knows it is not of a specific type. |
1898 } | 1863 } |
1899 } | 1864 } |
1900 | 1865 |
1901 void visitIdentity(HIdentity instruction) { | 1866 void visitIdentity(HIdentity instruction) { |
1902 // At HIf(HIdentity(x, null)) strengthens x to non-null on else branch. | 1867 // At HIf(HIdentity(x, null)) strengthens x to non-null on else branch. |
1903 HInstruction left = instruction.left; | 1868 HInstruction left = instruction.left; |
1904 HInstruction right = instruction.right; | 1869 HInstruction right = instruction.right; |
1905 HInstruction input; | 1870 HInstruction input; |
(...skipping 11 matching lines...) Expand all Loading... |
1917 List<HInstruction> ifUsers = <HInstruction>[]; | 1882 List<HInstruction> ifUsers = <HInstruction>[]; |
1918 List<HInstruction> notIfUsers = <HInstruction>[]; | 1883 List<HInstruction> notIfUsers = <HInstruction>[]; |
1919 | 1884 |
1920 collectIfUsers(instruction, ifUsers, notIfUsers); | 1885 collectIfUsers(instruction, ifUsers, notIfUsers); |
1921 | 1886 |
1922 if (ifUsers.isEmpty && notIfUsers.isEmpty) return; | 1887 if (ifUsers.isEmpty && notIfUsers.isEmpty) return; |
1923 | 1888 |
1924 TypeMask nonNullType = input.instructionType.nonNullable(); | 1889 TypeMask nonNullType = input.instructionType.nonNullable(); |
1925 | 1890 |
1926 for (HIf ifUser in ifUsers) { | 1891 for (HIf ifUser in ifUsers) { |
1927 insertTypePropagationForDominatedUsers(ifUser.elseBlock, input, | 1892 insertTypePropagationForDominatedUsers( |
1928 nonNullType); | 1893 ifUser.elseBlock, input, nonNullType); |
1929 // Uses in thenBlock are `null`, but probably not common. | 1894 // Uses in thenBlock are `null`, but probably not common. |
1930 } | 1895 } |
1931 for (HIf ifUser in notIfUsers) { | 1896 for (HIf ifUser in notIfUsers) { |
1932 insertTypePropagationForDominatedUsers(ifUser.thenBlock, input, | 1897 insertTypePropagationForDominatedUsers( |
1933 nonNullType); | 1898 ifUser.thenBlock, input, nonNullType); |
1934 // Uses in elseBlock are `null`, but probably not common. | 1899 // Uses in elseBlock are `null`, but probably not common. |
1935 } | 1900 } |
1936 } | 1901 } |
1937 | 1902 |
1938 collectIfUsers(HInstruction instruction, | 1903 collectIfUsers(HInstruction instruction, List<HInstruction> ifUsers, |
1939 List<HInstruction> ifUsers, | 1904 List<HInstruction> notIfUsers) { |
1940 List<HInstruction> notIfUsers) { | |
1941 for (HInstruction user in instruction.usedBy) { | 1905 for (HInstruction user in instruction.usedBy) { |
1942 if (user is HIf) { | 1906 if (user is HIf) { |
1943 ifUsers.add(user); | 1907 ifUsers.add(user); |
1944 } else if (user is HNot) { | 1908 } else if (user is HNot) { |
1945 collectIfUsers(user, notIfUsers, ifUsers); | 1909 collectIfUsers(user, notIfUsers, ifUsers); |
1946 } | 1910 } |
1947 } | 1911 } |
1948 } | 1912 } |
1949 } | 1913 } |
1950 | 1914 |
(...skipping 24 matching lines...) Expand all Loading... |
1975 visitBasicBlock(blocks[j]); | 1939 visitBasicBlock(blocks[j]); |
1976 } | 1940 } |
1977 } | 1941 } |
1978 } | 1942 } |
1979 } | 1943 } |
1980 | 1944 |
1981 void visitBasicBlock(HBasicBlock block) { | 1945 void visitBasicBlock(HBasicBlock block) { |
1982 if (block.predecessors.length == 0) { | 1946 if (block.predecessors.length == 0) { |
1983 // Entry block. | 1947 // Entry block. |
1984 memorySet = new MemorySet(compiler); | 1948 memorySet = new MemorySet(compiler); |
1985 } else if (block.predecessors.length == 1 | 1949 } else if (block.predecessors.length == 1 && |
1986 && block.predecessors[0].successors.length == 1) { | 1950 block.predecessors[0].successors.length == 1) { |
1987 // No need to clone, there is no other successor for | 1951 // No need to clone, there is no other successor for |
1988 // `block.predecessors[0]`, and this block has only one | 1952 // `block.predecessors[0]`, and this block has only one |
1989 // predecessor. Since we are not going to visit | 1953 // predecessor. Since we are not going to visit |
1990 // `block.predecessors[0]` again, we can just re-use its | 1954 // `block.predecessors[0]` again, we can just re-use its |
1991 // [memorySet]. | 1955 // [memorySet]. |
1992 memorySet = memories[block.predecessors[0].id]; | 1956 memorySet = memories[block.predecessors[0].id]; |
1993 } else if (block.predecessors.length == 1) { | 1957 } else if (block.predecessors.length == 1) { |
1994 // Clone the memorySet of the predecessor, because it is also used | 1958 // Clone the memorySet of the predecessor, because it is also used |
1995 // by other successors of it. | 1959 // by other successors of it. |
1996 memorySet = memories[block.predecessors[0].id].clone(); | 1960 memorySet = memories[block.predecessors[0].id].clone(); |
1997 } else { | 1961 } else { |
1998 // Compute the intersection of all predecessors. | 1962 // Compute the intersection of all predecessors. |
1999 memorySet = memories[block.predecessors[0].id]; | 1963 memorySet = memories[block.predecessors[0].id]; |
2000 for (int i = 1; i < block.predecessors.length; i++) { | 1964 for (int i = 1; i < block.predecessors.length; i++) { |
2001 memorySet = memorySet.intersectionFor( | 1965 memorySet = memorySet.intersectionFor( |
2002 memories[block.predecessors[i].id], block, i); | 1966 memories[block.predecessors[i].id], block, i); |
2003 } | 1967 } |
2004 } | 1968 } |
2005 | 1969 |
2006 memories[block.id] = memorySet; | 1970 memories[block.id] = memorySet; |
2007 HInstruction instruction = block.first; | 1971 HInstruction instruction = block.first; |
2008 while (instruction != null) { | 1972 while (instruction != null) { |
2009 HInstruction next = instruction.next; | 1973 HInstruction next = instruction.next; |
2010 instruction.accept(this); | 1974 instruction.accept(this); |
2011 instruction = next; | 1975 instruction = next; |
2012 } | 1976 } |
2013 } | 1977 } |
2014 | 1978 |
2015 void visitFieldGet(HFieldGet instruction) { | 1979 void visitFieldGet(HFieldGet instruction) { |
2016 if (instruction.isNullCheck) return; | 1980 if (instruction.isNullCheck) return; |
2017 Element element = instruction.element; | 1981 Element element = instruction.element; |
2018 HInstruction receiver = | 1982 HInstruction receiver = instruction.getDartReceiver(compiler).nonCheck(); |
2019 instruction.getDartReceiver(compiler).nonCheck(); | |
2020 HInstruction existing = memorySet.lookupFieldValue(element, receiver); | 1983 HInstruction existing = memorySet.lookupFieldValue(element, receiver); |
2021 if (existing != null) { | 1984 if (existing != null) { |
2022 instruction.block.rewriteWithBetterUser(instruction, existing); | 1985 instruction.block.rewriteWithBetterUser(instruction, existing); |
2023 instruction.block.remove(instruction); | 1986 instruction.block.remove(instruction); |
2024 } else { | 1987 } else { |
2025 memorySet.registerFieldValue(element, receiver, instruction); | 1988 memorySet.registerFieldValue(element, receiver, instruction); |
2026 } | 1989 } |
2027 } | 1990 } |
2028 | 1991 |
2029 void visitFieldSet(HFieldSet instruction) { | 1992 void visitFieldSet(HFieldSet instruction) { |
2030 HInstruction receiver = | 1993 HInstruction receiver = instruction.getDartReceiver(compiler).nonCheck(); |
2031 instruction.getDartReceiver(compiler).nonCheck(); | |
2032 memorySet.registerFieldValueUpdate( | 1994 memorySet.registerFieldValueUpdate( |
2033 instruction.element, receiver, instruction.inputs.last); | 1995 instruction.element, receiver, instruction.inputs.last); |
2034 } | 1996 } |
2035 | 1997 |
2036 void visitForeignNew(HForeignNew instruction) { | 1998 void visitForeignNew(HForeignNew instruction) { |
2037 memorySet.registerAllocation(instruction); | 1999 memorySet.registerAllocation(instruction); |
2038 if (shouldTrackInitialValues(instruction)) { | 2000 if (shouldTrackInitialValues(instruction)) { |
2039 int argumentIndex = 0; | 2001 int argumentIndex = 0; |
2040 instruction.element.forEachInstanceField((_, Element member) { | 2002 instruction.element.forEachInstanceField((_, Element member) { |
2041 if (compiler.elementHasCompileTimeError(member)) return; | 2003 if (compiler.elementHasCompileTimeError(member)) return; |
(...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2143 /** | 2105 /** |
2144 * Holds values of memory places. | 2106 * Holds values of memory places. |
2145 */ | 2107 */ |
2146 class MemorySet { | 2108 class MemorySet { |
2147 final Compiler compiler; | 2109 final Compiler compiler; |
2148 | 2110 |
2149 /** | 2111 /** |
2150 * Maps a field to a map of receiver to value. | 2112 * Maps a field to a map of receiver to value. |
2151 */ | 2113 */ |
2152 final Map<Element, Map<HInstruction, HInstruction>> fieldValues = | 2114 final Map<Element, Map<HInstruction, HInstruction>> fieldValues = |
2153 <Element, Map<HInstruction, HInstruction>> {}; | 2115 <Element, Map<HInstruction, HInstruction>>{}; |
2154 | 2116 |
2155 /** | 2117 /** |
2156 * Maps a receiver to a map of keys to value. | 2118 * Maps a receiver to a map of keys to value. |
2157 */ | 2119 */ |
2158 final Map<HInstruction, Map<HInstruction, HInstruction>> keyedValues = | 2120 final Map<HInstruction, Map<HInstruction, HInstruction>> keyedValues = |
2159 <HInstruction, Map<HInstruction, HInstruction>> {}; | 2121 <HInstruction, Map<HInstruction, HInstruction>>{}; |
2160 | 2122 |
2161 /** | 2123 /** |
2162 * Set of objects that we know don't escape the current function. | 2124 * Set of objects that we know don't escape the current function. |
2163 */ | 2125 */ |
2164 final Setlet<HInstruction> nonEscapingReceivers = new Setlet<HInstruction>(); | 2126 final Setlet<HInstruction> nonEscapingReceivers = new Setlet<HInstruction>(); |
2165 | 2127 |
2166 MemorySet(this.compiler); | 2128 MemorySet(this.compiler); |
2167 | 2129 |
2168 JavaScriptBackend get backend => compiler.backend; | 2130 JavaScriptBackend get backend => compiler.backend; |
2169 | 2131 |
2170 /** | 2132 /** |
2171 * Returns whether [first] and [second] always alias to the same object. | 2133 * Returns whether [first] and [second] always alias to the same object. |
2172 */ | 2134 */ |
2173 bool mustAlias(HInstruction first, HInstruction second) { | 2135 bool mustAlias(HInstruction first, HInstruction second) { |
2174 return first == second; | 2136 return first == second; |
2175 } | 2137 } |
2176 | 2138 |
2177 /** | 2139 /** |
2178 * Returns whether [first] and [second] may alias to the same object. | 2140 * Returns whether [first] and [second] may alias to the same object. |
2179 */ | 2141 */ |
2180 bool mayAlias(HInstruction first, HInstruction second) { | 2142 bool mayAlias(HInstruction first, HInstruction second) { |
2181 if (mustAlias(first, second)) return true; | 2143 if (mustAlias(first, second)) return true; |
2182 if (isConcrete(first) && isConcrete(second)) return false; | 2144 if (isConcrete(first) && isConcrete(second)) return false; |
2183 if (nonEscapingReceivers.contains(first)) return false; | 2145 if (nonEscapingReceivers.contains(first)) return false; |
2184 if (nonEscapingReceivers.contains(second)) return false; | 2146 if (nonEscapingReceivers.contains(second)) return false; |
2185 // Typed arrays of different types might have a shared buffer. | 2147 // Typed arrays of different types might have a shared buffer. |
2186 if (couldBeTypedArray(first) && couldBeTypedArray(second)) return true; | 2148 if (couldBeTypedArray(first) && couldBeTypedArray(second)) return true; |
2187 return !first.instructionType.isDisjoint( | 2149 return !first.instructionType |
2188 second.instructionType, compiler.world); | 2150 .isDisjoint(second.instructionType, compiler.world); |
2189 } | 2151 } |
2190 | 2152 |
2191 bool isFinal(Element element) { | 2153 bool isFinal(Element element) { |
2192 return compiler.world.fieldNeverChanges(element); | 2154 return compiler.world.fieldNeverChanges(element); |
2193 } | 2155 } |
2194 | 2156 |
2195 bool isConcrete(HInstruction instruction) { | 2157 bool isConcrete(HInstruction instruction) { |
2196 return instruction is HForeignNew | 2158 return instruction is HForeignNew || |
2197 || instruction is HConstant | 2159 instruction is HConstant || |
2198 || instruction is HLiteralList; | 2160 instruction is HLiteralList; |
2199 } | 2161 } |
2200 | 2162 |
2201 bool couldBeTypedArray(HInstruction receiver) { | 2163 bool couldBeTypedArray(HInstruction receiver) { |
2202 JavaScriptBackend backend = compiler.backend; | 2164 JavaScriptBackend backend = compiler.backend; |
2203 return backend.couldBeTypedArray(receiver.instructionType); | 2165 return backend.couldBeTypedArray(receiver.instructionType); |
2204 } | 2166 } |
2205 | 2167 |
2206 /** | 2168 /** |
2207 * Returns whether [receiver] escapes the current function. | 2169 * Returns whether [receiver] escapes the current function. |
2208 */ | 2170 */ |
2209 bool escapes(HInstruction receiver) { | 2171 bool escapes(HInstruction receiver) { |
2210 return !nonEscapingReceivers.contains(receiver); | 2172 return !nonEscapingReceivers.contains(receiver); |
2211 } | 2173 } |
2212 | 2174 |
2213 void registerAllocation(HInstruction instruction) { | 2175 void registerAllocation(HInstruction instruction) { |
2214 nonEscapingReceivers.add(instruction); | 2176 nonEscapingReceivers.add(instruction); |
2215 } | 2177 } |
2216 | 2178 |
2217 /** | 2179 /** |
2218 * Sets `receiver.element` to contain [value]. Kills all potential | 2180 * Sets `receiver.element` to contain [value]. Kills all potential |
2219 * places that may be affected by this update. | 2181 * places that may be affected by this update. |
2220 */ | 2182 */ |
2221 void registerFieldValueUpdate(Element element, | 2183 void registerFieldValueUpdate( |
2222 HInstruction receiver, | 2184 Element element, HInstruction receiver, HInstruction value) { |
2223 HInstruction value) { | |
2224 if (backend.isNative(element)) { | 2185 if (backend.isNative(element)) { |
2225 return; // TODO(14955): Remove this restriction? | 2186 return; // TODO(14955): Remove this restriction? |
2226 } | 2187 } |
2227 // [value] is being set in some place in memory, we remove it from | 2188 // [value] is being set in some place in memory, we remove it from |
2228 // the non-escaping set. | 2189 // the non-escaping set. |
2229 nonEscapingReceivers.remove(value); | 2190 nonEscapingReceivers.remove(value); |
2230 Map<HInstruction, HInstruction> map = fieldValues.putIfAbsent( | 2191 Map<HInstruction, HInstruction> map = |
2231 element, () => <HInstruction, HInstruction> {}); | 2192 fieldValues.putIfAbsent(element, () => <HInstruction, HInstruction>{}); |
2232 map.forEach((key, value) { | 2193 map.forEach((key, value) { |
2233 if (mayAlias(receiver, key)) map[key] = null; | 2194 if (mayAlias(receiver, key)) map[key] = null; |
2234 }); | 2195 }); |
2235 map[receiver] = value; | 2196 map[receiver] = value; |
2236 } | 2197 } |
2237 | 2198 |
2238 /** | 2199 /** |
2239 * Registers that `receiver.element` is now [value]. | 2200 * Registers that `receiver.element` is now [value]. |
2240 */ | 2201 */ |
2241 void registerFieldValue(Element element, | 2202 void registerFieldValue( |
2242 HInstruction receiver, | 2203 Element element, HInstruction receiver, HInstruction value) { |
2243 HInstruction value) { | |
2244 if (backend.isNative(element)) { | 2204 if (backend.isNative(element)) { |
2245 return; // TODO(14955): Remove this restriction? | 2205 return; // TODO(14955): Remove this restriction? |
2246 } | 2206 } |
2247 Map<HInstruction, HInstruction> map = fieldValues.putIfAbsent( | 2207 Map<HInstruction, HInstruction> map = |
2248 element, () => <HInstruction, HInstruction> {}); | 2208 fieldValues.putIfAbsent(element, () => <HInstruction, HInstruction>{}); |
2249 map[receiver] = value; | 2209 map[receiver] = value; |
2250 } | 2210 } |
2251 | 2211 |
2252 /** | 2212 /** |
2253 * Returns the value stored in `receiver.element`. Returns null if | 2213 * Returns the value stored in `receiver.element`. Returns null if |
2254 * we don't know. | 2214 * we don't know. |
2255 */ | 2215 */ |
2256 HInstruction lookupFieldValue(Element element, HInstruction receiver) { | 2216 HInstruction lookupFieldValue(Element element, HInstruction receiver) { |
2257 Map<HInstruction, HInstruction> map = fieldValues[element]; | 2217 Map<HInstruction, HInstruction> map = fieldValues[element]; |
2258 return (map == null) ? null : map[receiver]; | 2218 return (map == null) ? null : map[receiver]; |
2259 } | 2219 } |
2260 | 2220 |
2261 /** | 2221 /** |
2262 * Kill all places that may be affected by this [instruction]. Also | 2222 * Kill all places that may be affected by this [instruction]. Also |
2263 * update the set of non-escaping objects in case [instruction] has | 2223 * update the set of non-escaping objects in case [instruction] has |
2264 * non-escaping objects in its inputs. | 2224 * non-escaping objects in its inputs. |
2265 */ | 2225 */ |
2266 void killAffectedBy(HInstruction instruction) { | 2226 void killAffectedBy(HInstruction instruction) { |
2267 // Even if [instruction] does not have side effects, it may use | 2227 // Even if [instruction] does not have side effects, it may use |
2268 // non-escaping objects and store them in a new object, which | 2228 // non-escaping objects and store them in a new object, which |
2269 // make these objects escaping. | 2229 // make these objects escaping. |
2270 // TODO(ngeoffray): We need a new side effect flag to know whether | 2230 // TODO(ngeoffray): We need a new side effect flag to know whether |
2271 // an instruction allocates an object. | 2231 // an instruction allocates an object. |
2272 instruction.inputs.forEach((input) { | 2232 instruction.inputs.forEach((input) { |
2273 nonEscapingReceivers.remove(input); | 2233 nonEscapingReceivers.remove(input); |
2274 }); | 2234 }); |
2275 | 2235 |
2276 if (instruction.sideEffects.changesInstanceProperty() | 2236 if (instruction.sideEffects.changesInstanceProperty() || |
2277 || instruction.sideEffects.changesStaticProperty()) { | 2237 instruction.sideEffects.changesStaticProperty()) { |
2278 fieldValues.forEach((element, map) { | 2238 fieldValues.forEach((element, map) { |
2279 if (isFinal(element)) return; | 2239 if (isFinal(element)) return; |
2280 map.forEach((receiver, value) { | 2240 map.forEach((receiver, value) { |
2281 if (escapes(receiver)) { | 2241 if (escapes(receiver)) { |
2282 map[receiver] = null; | 2242 map[receiver] = null; |
2283 } | 2243 } |
2284 }); | 2244 }); |
2285 }); | 2245 }); |
2286 } | 2246 } |
2287 | 2247 |
(...skipping 13 matching lines...) Expand all Loading... |
2301 * we don't know. | 2261 * we don't know. |
2302 */ | 2262 */ |
2303 HInstruction lookupKeyedValue(HInstruction receiver, HInstruction index) { | 2263 HInstruction lookupKeyedValue(HInstruction receiver, HInstruction index) { |
2304 Map<HInstruction, HInstruction> map = keyedValues[receiver]; | 2264 Map<HInstruction, HInstruction> map = keyedValues[receiver]; |
2305 return (map == null) ? null : map[index]; | 2265 return (map == null) ? null : map[index]; |
2306 } | 2266 } |
2307 | 2267 |
2308 /** | 2268 /** |
2309 * Registers that `receiver[index]` is now [value]. | 2269 * Registers that `receiver[index]` is now [value]. |
2310 */ | 2270 */ |
2311 void registerKeyedValue(HInstruction receiver, | 2271 void registerKeyedValue( |
2312 HInstruction index, | 2272 HInstruction receiver, HInstruction index, HInstruction value) { |
2313 HInstruction value) { | 2273 Map<HInstruction, HInstruction> map = |
2314 Map<HInstruction, HInstruction> map = keyedValues.putIfAbsent( | 2274 keyedValues.putIfAbsent(receiver, () => <HInstruction, HInstruction>{}); |
2315 receiver, () => <HInstruction, HInstruction> {}); | |
2316 map[index] = value; | 2275 map[index] = value; |
2317 } | 2276 } |
2318 | 2277 |
2319 /** | 2278 /** |
2320 * Sets `receiver[index]` to contain [value]. Kills all potential | 2279 * Sets `receiver[index]` to contain [value]. Kills all potential |
2321 * places that may be affected by this update. | 2280 * places that may be affected by this update. |
2322 */ | 2281 */ |
2323 void registerKeyedValueUpdate(HInstruction receiver, | 2282 void registerKeyedValueUpdate( |
2324 HInstruction index, | 2283 HInstruction receiver, HInstruction index, HInstruction value) { |
2325 HInstruction value) { | |
2326 nonEscapingReceivers.remove(value); | 2284 nonEscapingReceivers.remove(value); |
2327 keyedValues.forEach((key, values) { | 2285 keyedValues.forEach((key, values) { |
2328 if (mayAlias(receiver, key)) { | 2286 if (mayAlias(receiver, key)) { |
2329 // Typed arrays that are views of the same buffer may have different | 2287 // Typed arrays that are views of the same buffer may have different |
2330 // offsets or element sizes, unless they are the same typed array. | 2288 // offsets or element sizes, unless they are the same typed array. |
2331 bool weakIndex = couldBeTypedArray(key) && !mustAlias(receiver, key); | 2289 bool weakIndex = couldBeTypedArray(key) && !mustAlias(receiver, key); |
2332 values.forEach((otherIndex, otherValue) { | 2290 values.forEach((otherIndex, otherValue) { |
2333 if (weakIndex || mayAlias(index, otherIndex)) { | 2291 if (weakIndex || mayAlias(index, otherIndex)) { |
2334 values[otherIndex] = null; | 2292 values[otherIndex] = null; |
2335 } | 2293 } |
2336 }); | 2294 }); |
2337 } | 2295 } |
2338 }); | 2296 }); |
2339 | 2297 |
2340 // Typed arrays may narrow incoming values. | 2298 // Typed arrays may narrow incoming values. |
2341 if (couldBeTypedArray(receiver)) return; | 2299 if (couldBeTypedArray(receiver)) return; |
2342 | 2300 |
2343 Map<HInstruction, HInstruction> map = keyedValues.putIfAbsent( | 2301 Map<HInstruction, HInstruction> map = |
2344 receiver, () => <HInstruction, HInstruction> {}); | 2302 keyedValues.putIfAbsent(receiver, () => <HInstruction, HInstruction>{}); |
2345 map[index] = value; | 2303 map[index] = value; |
2346 } | 2304 } |
2347 | 2305 |
2348 /** | 2306 /** |
2349 * Returns null if either [first] or [second] is null. Otherwise | 2307 * Returns null if either [first] or [second] is null. Otherwise |
2350 * returns [first] if [first] and [second] are equal. Otherwise | 2308 * returns [first] if [first] and [second] are equal. Otherwise |
2351 * creates or re-uses a phi in [block] that holds [first] and [second]. | 2309 * creates or re-uses a phi in [block] that holds [first] and [second]. |
2352 */ | 2310 */ |
2353 HInstruction findCommonInstruction(HInstruction first, | 2311 HInstruction findCommonInstruction(HInstruction first, HInstruction second, |
2354 HInstruction second, | 2312 HBasicBlock block, int predecessorIndex) { |
2355 HBasicBlock block, | |
2356 int predecessorIndex) { | |
2357 if (first == null || second == null) return null; | 2313 if (first == null || second == null) return null; |
2358 if (first == second) return first; | 2314 if (first == second) return first; |
2359 TypeMask phiType = second.instructionType.union( | 2315 TypeMask phiType = |
2360 first.instructionType, compiler.world); | 2316 second.instructionType.union(first.instructionType, compiler.world); |
2361 if (first is HPhi && first.block == block) { | 2317 if (first is HPhi && first.block == block) { |
2362 HPhi phi = first; | 2318 HPhi phi = first; |
2363 phi.addInput(second); | 2319 phi.addInput(second); |
2364 phi.instructionType = phiType; | 2320 phi.instructionType = phiType; |
2365 return phi; | 2321 return phi; |
2366 } else { | 2322 } else { |
2367 HPhi phi = new HPhi.noInputs(null, phiType); | 2323 HPhi phi = new HPhi.noInputs(null, phiType); |
2368 block.addPhi(phi); | 2324 block.addPhi(phi); |
2369 // Previous predecessors had the same input. A phi must have | 2325 // Previous predecessors had the same input. A phi must have |
2370 // the same number of inputs as its block has predecessors. | 2326 // the same number of inputs as its block has predecessors. |
2371 for (int i = 0; i < predecessorIndex; i++) { | 2327 for (int i = 0; i < predecessorIndex; i++) { |
2372 phi.addInput(first); | 2328 phi.addInput(first); |
2373 } | 2329 } |
2374 phi.addInput(second); | 2330 phi.addInput(second); |
2375 return phi; | 2331 return phi; |
2376 } | 2332 } |
2377 } | 2333 } |
2378 | 2334 |
2379 /** | 2335 /** |
2380 * Returns the intersection between [this] and [other]. | 2336 * Returns the intersection between [this] and [other]. |
2381 */ | 2337 */ |
2382 MemorySet intersectionFor(MemorySet other, | 2338 MemorySet intersectionFor( |
2383 HBasicBlock block, | 2339 MemorySet other, HBasicBlock block, int predecessorIndex) { |
2384 int predecessorIndex) { | |
2385 MemorySet result = new MemorySet(compiler); | 2340 MemorySet result = new MemorySet(compiler); |
2386 if (other == null) return result; | 2341 if (other == null) return result; |
2387 | 2342 |
2388 fieldValues.forEach((element, values) { | 2343 fieldValues.forEach((element, values) { |
2389 var otherValues = other.fieldValues[element]; | 2344 var otherValues = other.fieldValues[element]; |
2390 if (otherValues == null) return; | 2345 if (otherValues == null) return; |
2391 values.forEach((receiver, value) { | 2346 values.forEach((receiver, value) { |
2392 HInstruction instruction = findCommonInstruction( | 2347 HInstruction instruction = findCommonInstruction( |
2393 value, otherValues[receiver], block, predecessorIndex); | 2348 value, otherValues[receiver], block, predecessorIndex); |
2394 if (instruction != null) { | 2349 if (instruction != null) { |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2430 | 2385 |
2431 keyedValues.forEach((receiver, values) { | 2386 keyedValues.forEach((receiver, values) { |
2432 result.keyedValues[receiver] = | 2387 result.keyedValues[receiver] = |
2433 new Map<HInstruction, HInstruction>.from(values); | 2388 new Map<HInstruction, HInstruction>.from(values); |
2434 }); | 2389 }); |
2435 | 2390 |
2436 result.nonEscapingReceivers.addAll(nonEscapingReceivers); | 2391 result.nonEscapingReceivers.addAll(nonEscapingReceivers); |
2437 return result; | 2392 return result; |
2438 } | 2393 } |
2439 } | 2394 } |
OLD | NEW |