OLD | NEW |
---|---|
1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, 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 library cps_ir.optimization.inline; | 5 library cps_ir.optimization.inline; |
6 | 6 |
7 import 'cps_fragment.dart'; | 7 import 'cps_fragment.dart'; |
8 import 'cps_ir_builder.dart' show ThisParameterLocal; | 8 import 'cps_ir_builder.dart' show ThisParameterLocal; |
9 import 'cps_ir_nodes.dart'; | 9 import 'cps_ir_nodes.dart'; |
10 import 'optimizers.dart'; | 10 import 'optimizers.dart'; |
(...skipping 204 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
215 new ShrinkingReducer().rewrite(node); | 215 new ShrinkingReducer().rewrite(node); |
216 } | 216 } |
217 } | 217 } |
218 | 218 |
219 /// Compute an abstract size of an IR function definition. | 219 /// Compute an abstract size of an IR function definition. |
220 /// | 220 /// |
221 /// The size represents the cost of inlining at a call site. | 221 /// The size represents the cost of inlining at a call site. |
222 class SizeVisitor extends TrampolineRecursiveVisitor { | 222 class SizeVisitor extends TrampolineRecursiveVisitor { |
223 int size = 0; | 223 int size = 0; |
224 | 224 |
225 void countArgument(Reference<Primitive> argument, Parameter parameter) { | 225 void countArgument(Primitive argument, Parameter parameter) { |
226 // If a parameter is unused and the corresponding argument has only the | 226 // If a parameter is unused and the corresponding argument has only the |
227 // one use at the invocation, then inlining the call might enable | 227 // one use at the invocation, then inlining the call might enable |
228 // elimination of the argument. This 'pays for itself' by decreasing the | 228 // elimination of the argument. This 'pays for itself' by decreasing the |
229 // cost of inlining at the call site. | 229 // cost of inlining at the call site. |
230 if (argument != null && | 230 if (argument != null && argument.hasExactlyOneUse && parameter.hasNoUses) { |
231 argument.definition.hasExactlyOneUse && | 231 --size; |
232 parameter.hasNoUses) { | 232 } else if (argument == null && parameter != null) { |
233 // FIXME: Before this change, the dummy constant would count as paying | |
234 // for itself here. Mimic the same cost to preserve inlining decisions. | |
asgerf
2016/03/03 15:23:48
This is here to ensure the output is unchanged.
I
| |
233 --size; | 235 --size; |
234 } | 236 } |
235 } | 237 } |
236 | 238 |
237 static int sizeOf(InvocationPrimitive invoke, FunctionDefinition function) { | 239 static int sizeOf(InvocationPrimitive invoke, FunctionDefinition function) { |
238 SizeVisitor visitor = new SizeVisitor(); | 240 SizeVisitor visitor = new SizeVisitor(); |
239 visitor.visit(function); | 241 visitor.visit(function); |
240 visitor.countArgument(invoke.receiverRef, function.thisParameter); | 242 visitor.countArgument(invoke.interceptor, function.interceptorParameter); |
243 visitor.countArgument(invoke.receiver, function.receiverParameter); | |
241 for (int i = 0; i < invoke.argumentRefs.length; ++i) { | 244 for (int i = 0; i < invoke.argumentRefs.length; ++i) { |
242 visitor.countArgument(invoke.argumentRefs[i], function.parameters[i]); | 245 visitor.countArgument(invoke.argument(i), function.parameters[i]); |
243 } | 246 } |
244 return visitor.size; | 247 return visitor.size; |
245 } | 248 } |
246 | 249 |
247 // Inlining a function incurs a cost equal to the number of primitives and | 250 // Inlining a function incurs a cost equal to the number of primitives and |
248 // non-jump tail expressions. | 251 // non-jump tail expressions. |
249 // TODO(kmillikin): Tune the size computation and size bound. | 252 // TODO(kmillikin): Tune the size computation and size bound. |
250 processLetPrim(LetPrim node) => ++size; | 253 processLetPrim(LetPrim node) => ++size; |
251 processLetMutable(LetMutable node) => ++size; | 254 processLetMutable(LetMutable node) => ++size; |
252 processBranch(Branch node) => ++size; | 255 processBranch(Branch node) => ++size; |
253 processThrow(Throw nose) => ++size; | 256 processThrow(Throw nose) => ++size; |
254 processRethrow(Rethrow node) => ++size; | 257 processRethrow(Rethrow node) => ++size; |
255 | 258 |
256 // Discount primitives that do not generate code. | 259 // Discount primitives that do not generate code. |
257 processRefinement(Refinement node) => --size; | 260 processRefinement(Refinement node) => --size; |
258 processBoundsCheck(BoundsCheck node) { | 261 processBoundsCheck(BoundsCheck node) { |
259 if (node.hasNoChecks) { | 262 if (node.hasNoChecks) { |
260 --size; | 263 --size; |
261 } | 264 } |
262 } | 265 } |
263 | 266 |
264 processForeignCode(ForeignCode node) { | 267 processForeignCode(ForeignCode node) { |
265 // Count the number of nodes in the JS fragment, and discount the size | 268 // Count the number of nodes in the JS fragment, and discount the size |
266 // originally added by LetPrim. | 269 // originally added by LetPrim. |
267 JsSizeVisitor visitor = new JsSizeVisitor(); | 270 JsSizeVisitor visitor = new JsSizeVisitor(); |
268 node.codeTemplate.ast.accept(visitor); | 271 node.codeTemplate.ast.accept(visitor); |
269 size += visitor.size - 1; | 272 size += visitor.size - 1; |
270 } | 273 } |
274 | |
275 processInvokeMethod(InvokeMethod node) { | |
276 if (node.callingConvention == CallingConvention.DummyIntercepted) { | |
277 // FIXME: Before this change, the dummy constant would count for one. | |
278 // Mimic the same cost to preserve inlining decisions. | |
279 ++size; | |
asgerf
2016/03/03 15:23:48
Likewise.
| |
280 } | |
281 } | |
271 } | 282 } |
272 | 283 |
273 class JsSizeVisitor extends js.BaseVisitor { | 284 class JsSizeVisitor extends js.BaseVisitor { |
274 int size = 0; | 285 int size = 0; |
275 | 286 |
276 visitNode(js.Node node) { | 287 visitNode(js.Node node) { |
277 ++size; | 288 ++size; |
278 return super.visitNode(node); | 289 return super.visitNode(node); |
279 } | 290 } |
280 | 291 |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
321 // A successful inlining attempt will set the node's body to null, so it is | 332 // A successful inlining attempt will set the node's body to null, so it is |
322 // read before visiting the primitive. | 333 // read before visiting the primitive. |
323 Expression next = node.body; | 334 Expression next = node.body; |
324 Primitive replacement = visit(node.primitive); | 335 Primitive replacement = visit(node.primitive); |
325 if (replacement != null) { | 336 if (replacement != null) { |
326 node.primitive.replaceWithFragment(_fragment, replacement); | 337 node.primitive.replaceWithFragment(_fragment, replacement); |
327 } | 338 } |
328 return next; | 339 return next; |
329 } | 340 } |
330 | 341 |
331 TypeMask abstractType(Reference<Primitive> ref) { | 342 TypeMask abstractType(Primitive def) { |
332 return ref.definition.type ?? typeSystem.dynamicType; | 343 return def.type ?? typeSystem.dynamicType; |
333 } | 344 } |
334 | 345 |
335 /// Build the IR term for the function that adapts a call site targeting a | 346 /// Build the IR term for the function that adapts a call site targeting a |
336 /// function that takes optional arguments not passed at the call site. | 347 /// function that takes optional arguments not passed at the call site. |
337 FunctionDefinition buildAdapter(InvokeMethod node, FunctionElement target) { | 348 FunctionDefinition buildAdapter(InvokeMethod node, FunctionElement target) { |
338 Parameter thisParameter = new Parameter(new ThisParameterLocal(target)) | 349 Parameter thisParameter = new Parameter(new ThisParameterLocal(target)) |
339 ..type = node.receiver.type; | 350 ..type = node.receiver.type; |
351 Parameter interceptorParameter = node.interceptorRef != null | |
352 ? new Parameter(null) | |
353 : null; | |
340 List<Parameter> parameters = new List<Parameter>.generate( | 354 List<Parameter> parameters = new List<Parameter>.generate( |
341 node.argumentRefs.length, | 355 node.argumentRefs.length, |
342 (int index) { | 356 (int index) { |
343 // TODO(kmillikin): Use a hint for the parameter names. | 357 // TODO(kmillikin): Use a hint for the parameter names. |
344 return new Parameter(null) | 358 return new Parameter(null) |
345 ..type = node.argument(index).type; | 359 ..type = node.argument(index).type; |
346 }); | 360 }); |
347 Continuation returnContinuation = new Continuation.retrn(); | 361 Continuation returnContinuation = new Continuation.retrn(); |
348 CpsFragment cps = new CpsFragment(); | 362 CpsFragment cps = new CpsFragment(); |
349 | 363 |
350 FunctionSignature signature = target.functionSignature; | 364 FunctionSignature signature = target.functionSignature; |
351 int requiredParameterCount = signature.requiredParameterCount; | 365 int requiredParameterCount = signature.requiredParameterCount; |
352 if (node.callingConvention == CallingConvention.Intercepted || | |
353 node.callingConvention == CallingConvention.DummyIntercepted) { | |
354 ++requiredParameterCount; | |
355 } | |
356 List<Primitive> arguments = new List<Primitive>.generate( | 366 List<Primitive> arguments = new List<Primitive>.generate( |
357 requiredParameterCount, | 367 requiredParameterCount, |
358 (int index) => parameters[index]); | 368 (int index) => parameters[index]); |
359 | 369 |
360 int parameterIndex = requiredParameterCount; | 370 int parameterIndex = requiredParameterCount; |
361 CallStructure newCallStructure; | 371 CallStructure newCallStructure; |
362 if (signature.optionalParametersAreNamed) { | 372 if (signature.optionalParametersAreNamed) { |
363 List<String> incomingNames = | 373 List<String> incomingNames = |
364 node.selector.callStructure.getOrderedNamedArguments(); | 374 node.selector.callStructure.getOrderedNamedArguments(); |
365 List<String> outgoingNames = <String>[]; | 375 List<String> outgoingNames = <String>[]; |
(...skipping 23 matching lines...) Expand all Loading... | |
389 defaultValue.type = typeSystem.getParameterType(formal); | 399 defaultValue.type = typeSystem.getParameterType(formal); |
390 arguments.add(defaultValue); | 400 arguments.add(defaultValue); |
391 } | 401 } |
392 }); | 402 }); |
393 newCallStructure = new CallStructure(signature.parameterCount); | 403 newCallStructure = new CallStructure(signature.parameterCount); |
394 } | 404 } |
395 | 405 |
396 Selector newSelector = | 406 Selector newSelector = |
397 new Selector(node.selector.kind, node.selector.memberName, | 407 new Selector(node.selector.kind, node.selector.memberName, |
398 newCallStructure); | 408 newCallStructure); |
399 Primitive result = cps.invokeMethod(thisParameter, newSelector, node.mask, | 409 Primitive result = cps.invokeMethod(thisParameter, |
400 arguments, node.callingConvention); | 410 newSelector, |
411 node.mask, | |
412 arguments, | |
413 interceptor: interceptorParameter, | |
414 callingConvention: node.callingConvention); | |
401 result.type = typeSystem.getInvokeReturnType(node.selector, node.mask); | 415 result.type = typeSystem.getInvokeReturnType(node.selector, node.mask); |
402 returnContinuation.parameters.single.type = result.type; | 416 returnContinuation.parameters.single.type = result.type; |
403 cps.invokeContinuation(returnContinuation, <Primitive>[result]); | 417 cps.invokeContinuation(returnContinuation, <Primitive>[result]); |
404 return new FunctionDefinition(target, thisParameter, parameters, | 418 return new FunctionDefinition(target, thisParameter, parameters, |
405 returnContinuation, | 419 returnContinuation, |
406 cps.root); | 420 cps.root, |
421 interceptorParameter: interceptorParameter); | |
407 } | 422 } |
408 | 423 |
409 // Given an invocation and a known target, possibly perform inlining. | 424 // Given an invocation and a known target, possibly perform inlining. |
410 // | 425 // |
411 // An optional call structure indicates a dynamic call. Calls that are | 426 // An optional call structure indicates a dynamic call. Calls that are |
412 // already resolved statically have a null call structure. | 427 // already resolved statically have a null call structure. |
413 // | 428 // |
414 // The [Primitive] representing the result of the inlined call is returned | 429 // The [Primitive] representing the result of the inlined call is returned |
415 // if the call was inlined, and the inlined function body is available in | 430 // if the call was inlined, and the inlined function body is available in |
416 // [_fragment]. If the call was not inlined, null is returned. | 431 // [_fragment]. If the call was not inlined, null is returned. |
(...skipping 20 matching lines...) Expand all Loading... | |
437 } | 452 } |
438 | 453 |
439 if (isBlacklisted(target)) return null; | 454 if (isBlacklisted(target)) return null; |
440 | 455 |
441 if (invoke.callingConvention == CallingConvention.OneShotIntercepted) { | 456 if (invoke.callingConvention == CallingConvention.OneShotIntercepted) { |
442 // One-shot interceptor calls with a known target are only inserted on | 457 // One-shot interceptor calls with a known target are only inserted on |
443 // uncommon code paths, so they should not be inlined. | 458 // uncommon code paths, so they should not be inlined. |
444 return null; | 459 return null; |
445 } | 460 } |
446 | 461 |
447 Reference<Primitive> dartReceiver = invoke.dartReceiverRef; | 462 Primitive receiver = invoke.receiver; |
448 TypeMask abstractReceiver = | 463 TypeMask abstractReceiver = |
449 dartReceiver == null ? null : abstractType(dartReceiver); | 464 receiver == null ? null : abstractType(receiver); |
450 // The receiver is non-null in a method body, unless the receiver is known | 465 // The receiver is non-null in a method body, unless the receiver is known |
451 // to be `null` (isEmpty covers `null` and unreachable). | 466 // to be `null` (isEmpty covers `null` and unreachable). |
452 TypeMask abstractReceiverInMethod = abstractReceiver == null | 467 TypeMask abstractReceiverInMethod = abstractReceiver == null |
453 ? null | 468 ? null |
454 : abstractReceiver.isEmpty | 469 : abstractReceiver.isEmpty |
455 ? abstractReceiver | 470 ? abstractReceiver |
456 : abstractReceiver.nonNullable(); | 471 : abstractReceiver.nonNullable(); |
457 List<TypeMask> abstractArguments = | 472 List<TypeMask> abstractArguments = |
458 invoke.argumentRefs.map(abstractType).toList(); | 473 invoke.arguments.map(abstractType).toList(); |
459 var cachedResult = _inliner.cache.get(target, callStructure, | 474 var cachedResult = _inliner.cache.get(target, callStructure, |
460 abstractReceiverInMethod, | 475 abstractReceiverInMethod, |
461 abstractArguments); | 476 abstractArguments); |
462 | 477 |
463 // Negative inlining result in the cache. | 478 // Negative inlining result in the cache. |
464 if (cachedResult == InliningCache.NO_INLINE) return null; | 479 if (cachedResult == InliningCache.NO_INLINE) return null; |
465 | 480 |
466 Primitive finish(FunctionDefinition function) { | 481 Primitive finish(FunctionDefinition function) { |
467 _fragment = new CpsFragment(invoke.sourceInformation); | 482 _fragment = new CpsFragment(invoke.sourceInformation); |
468 Primitive receiver = invoke.receiver; | 483 Primitive receiver = invoke.receiver; |
469 List<Primitive> arguments = invoke.arguments.toList(); | 484 List<Primitive> arguments = invoke.arguments.toList(); |
470 // Add a null check to the inlined function body if necessary. The | 485 // Add a null check to the inlined function body if necessary. The |
471 // cached function body does not contain the null check. | 486 // cached function body does not contain the null check. |
472 if (dartReceiver != null && abstractReceiver.isNullable) { | 487 if (receiver != null && abstractReceiver.isNullable) { |
473 Primitive check = nullReceiverGuard( | 488 receiver = nullReceiverGuard( |
474 invoke, _fragment, dartReceiver.definition, abstractReceiver); | 489 invoke, _fragment, receiver, abstractReceiver); |
475 if (invoke.callingConvention == CallingConvention.Intercepted) { | |
476 arguments[0] = check; | |
477 } else { | |
478 receiver = check; | |
479 } | |
480 } | 490 } |
481 return _fragment.inlineFunction(function, receiver, arguments, | 491 return _fragment.inlineFunction(function, receiver, arguments, |
482 hint: invoke.hint); | 492 interceptor: invoke.interceptor, hint: invoke.hint); |
483 } | 493 } |
484 | 494 |
485 // Positive inlining result in the cache. | 495 // Positive inlining result in the cache. |
486 if (cachedResult is FunctionDefinition) { | 496 if (cachedResult is FunctionDefinition) { |
487 return finish(cachedResult); | 497 return finish(cachedResult); |
488 } | 498 } |
489 | 499 |
490 // We have not seen this combination of target and abstract arguments | 500 // We have not seen this combination of target and abstract arguments |
491 // before. Make an inlining decision. | 501 // before. Make an inlining decision. |
492 assert(cachedResult == InliningCache.ABSENT); | 502 assert(cachedResult == InliningCache.ABSENT); |
(...skipping 13 matching lines...) Expand all Loading... | |
506 // formal parameter count. Build the IR term for an adapter function | 516 // formal parameter count. Build the IR term for an adapter function |
507 // body. | 517 // body. |
508 if (backend.isNative(target)) { | 518 if (backend.isNative(target)) { |
509 // TODO(25548): Generate correct adaptor for native methods. | 519 // TODO(25548): Generate correct adaptor for native methods. |
510 return doNotInline(); | 520 return doNotInline(); |
511 } else { | 521 } else { |
512 function = buildAdapter(invoke, target); | 522 function = buildAdapter(invoke, target); |
513 } | 523 } |
514 } else { | 524 } else { |
515 function = compileToCpsIr(target); | 525 function = compileToCpsIr(target); |
516 void setValue(Variable variable, Reference<Primitive> value) { | 526 if (function.receiverParameter != null) { |
517 variable.type = value.definition.type; | 527 function.receiverParameter.type = abstractReceiverInMethod; |
518 } | 528 } |
519 if (invoke.callingConvention == CallingConvention.Intercepted) { | 529 for (int i = 0; i < invoke.argumentRefs.length; ++i) { |
520 setValue(function.thisParameter, invoke.receiverRef); | 530 function.parameters[i].type = invoke.argument(i).type; |
521 function.parameters[0].type = abstractReceiverInMethod; | |
522 for (int i = 1; i < invoke.argumentRefs.length; ++i) { | |
523 setValue(function.parameters[i], invoke.argumentRefs[i]); | |
524 } | |
525 } else { | |
526 if (invoke.receiverRef != null) { | |
527 function.thisParameter.type = abstractReceiverInMethod; | |
528 } | |
529 for (int i = 0; i < invoke.argumentRefs.length; ++i) { | |
530 setValue(function.parameters[i], invoke.argumentRefs[i]); | |
531 } | |
532 } | 531 } |
533 optimizeBeforeInlining(function); | 532 optimizeBeforeInlining(function); |
534 } | 533 } |
535 | 534 |
536 // Inline calls in the body. | 535 // Inline calls in the body. |
537 _inliner.rewrite(function, callStructure); | 536 _inliner.rewrite(function, callStructure); |
538 | 537 |
539 // Compute the size. | 538 // Compute the size. |
540 // TODO(kmillikin): Tune the size bound. | 539 // TODO(kmillikin): Tune the size bound. |
541 int size = SizeVisitor.sizeOf(invoke, function); | 540 int size = SizeVisitor.sizeOf(invoke, function); |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
575 } | 574 } |
576 | 575 |
577 | 576 |
578 @override | 577 @override |
579 Primitive visitInvokeStatic(InvokeStatic node) { | 578 Primitive visitInvokeStatic(InvokeStatic node) { |
580 return tryInlining(node, node.target, null); | 579 return tryInlining(node, node.target, null); |
581 } | 580 } |
582 | 581 |
583 @override | 582 @override |
584 Primitive visitInvokeMethod(InvokeMethod node) { | 583 Primitive visitInvokeMethod(InvokeMethod node) { |
585 Primitive receiver = node.dartReceiver; | 584 Primitive receiver = node.receiver; |
586 Element element = world.locateSingleElement(node.selector, receiver.type); | 585 Element element = world.locateSingleElement(node.selector, receiver.type); |
587 if (element == null || element is! FunctionElement) return null; | 586 if (element == null || element is! FunctionElement) return null; |
588 if (node.selector.isGetter != element.isGetter) return null; | 587 if (node.selector.isGetter != element.isGetter) return null; |
589 if (node.selector.isSetter != element.isSetter) return null; | 588 if (node.selector.isSetter != element.isSetter) return null; |
590 if (node.selector.name != element.name) return null; | 589 if (node.selector.name != element.name) return null; |
591 | 590 |
592 return tryInlining(node, element.asFunctionElement(), | 591 return tryInlining(node, element.asFunctionElement(), |
593 node.selector.callStructure); | 592 node.selector.callStructure); |
594 } | 593 } |
595 | 594 |
(...skipping 23 matching lines...) Expand all Loading... | |
619 (enclosingClass == backend.helpers.jsNumberClass || | 618 (enclosingClass == backend.helpers.jsNumberClass || |
620 enclosingClass == backend.helpers.jsDoubleClass || | 619 enclosingClass == backend.helpers.jsDoubleClass || |
621 enclosingClass == backend.helpers.jsIntClass)) { | 620 enclosingClass == backend.helpers.jsIntClass)) { |
622 // These should be handled by operator specialization. | 621 // These should be handled by operator specialization. |
623 return true; | 622 return true; |
624 } | 623 } |
625 if (target == backend.helpers.stringInterpolationHelper) return true; | 624 if (target == backend.helpers.stringInterpolationHelper) return true; |
626 return false; | 625 return false; |
627 } | 626 } |
628 } | 627 } |
OLD | NEW |