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 && | |
232 parameter.hasNoUses) { | |
233 --size; | 231 --size; |
234 } | 232 } |
235 } | 233 } |
236 | 234 |
237 static int sizeOf(InvocationPrimitive invoke, FunctionDefinition function) { | 235 static int sizeOf(InvocationPrimitive invoke, FunctionDefinition function) { |
238 SizeVisitor visitor = new SizeVisitor(); | 236 SizeVisitor visitor = new SizeVisitor(); |
239 visitor.visit(function); | 237 visitor.visit(function); |
240 visitor.countArgument(invoke.receiverRef, function.thisParameter); | 238 if (invoke.callingConvention == CallingConvention.Intercepted) { |
| 239 // Note that if the invocation is a dummy-intercepted call, then the |
| 240 // target has an unused interceptor parameter, but the caller provides |
| 241 // no interceptor argument. |
| 242 visitor.countArgument(invoke.interceptor, function.interceptorParameter); |
| 243 } |
| 244 visitor.countArgument(invoke.receiver, function.receiverParameter); |
241 for (int i = 0; i < invoke.argumentRefs.length; ++i) { | 245 for (int i = 0; i < invoke.argumentRefs.length; ++i) { |
242 visitor.countArgument(invoke.argumentRefs[i], function.parameters[i]); | 246 visitor.countArgument(invoke.argument(i), function.parameters[i]); |
243 } | 247 } |
244 return visitor.size; | 248 return visitor.size; |
245 } | 249 } |
246 | 250 |
247 // Inlining a function incurs a cost equal to the number of primitives and | 251 // Inlining a function incurs a cost equal to the number of primitives and |
248 // non-jump tail expressions. | 252 // non-jump tail expressions. |
249 // TODO(kmillikin): Tune the size computation and size bound. | 253 // TODO(kmillikin): Tune the size computation and size bound. |
250 processLetPrim(LetPrim node) => ++size; | 254 processLetPrim(LetPrim node) => ++size; |
251 processLetMutable(LetMutable node) => ++size; | 255 processLetMutable(LetMutable node) => ++size; |
252 processBranch(Branch node) => ++size; | 256 processBranch(Branch node) => ++size; |
(...skipping 25 matching lines...) Expand all Loading... |
278 return super.visitNode(node); | 282 return super.visitNode(node); |
279 } | 283 } |
280 | 284 |
281 visitInterpolatedExpression(js.InterpolatedExpression node) { | 285 visitInterpolatedExpression(js.InterpolatedExpression node) { |
282 // Suppress call to visitNode. Placeholders should not be counted, because | 286 // Suppress call to visitNode. Placeholders should not be counted, because |
283 // the argument has already been counted, and will in most cases be inserted | 287 // the argument has already been counted, and will in most cases be inserted |
284 // directly in the placeholder. | 288 // directly in the placeholder. |
285 } | 289 } |
286 } | 290 } |
287 | 291 |
288 | |
289 class InliningVisitor extends TrampolineRecursiveVisitor { | 292 class InliningVisitor extends TrampolineRecursiveVisitor { |
290 final Inliner _inliner; | 293 final Inliner _inliner; |
291 | 294 |
292 // A successful inlining attempt returns the [Primitive] that represents the | 295 // A successful inlining attempt returns the [Primitive] that represents the |
293 // result of the inlined call or null. If the result is non-null, the body | 296 // result of the inlined call or null. If the result is non-null, the body |
294 // of the inlined function is available in this field. | 297 // of the inlined function is available in this field. |
295 CpsFragment _fragment; | 298 CpsFragment _fragment; |
296 | 299 |
297 InliningVisitor(this._inliner); | 300 InliningVisitor(this._inliner); |
298 | 301 |
(...skipping 22 matching lines...) Expand all Loading... |
321 // A successful inlining attempt will set the node's body to null, so it is | 324 // A successful inlining attempt will set the node's body to null, so it is |
322 // read before visiting the primitive. | 325 // read before visiting the primitive. |
323 Expression next = node.body; | 326 Expression next = node.body; |
324 Primitive replacement = visit(node.primitive); | 327 Primitive replacement = visit(node.primitive); |
325 if (replacement != null) { | 328 if (replacement != null) { |
326 node.primitive.replaceWithFragment(_fragment, replacement); | 329 node.primitive.replaceWithFragment(_fragment, replacement); |
327 } | 330 } |
328 return next; | 331 return next; |
329 } | 332 } |
330 | 333 |
331 TypeMask abstractType(Reference<Primitive> ref) { | 334 TypeMask abstractType(Primitive def) { |
332 return ref.definition.type ?? typeSystem.dynamicType; | 335 return def.type ?? typeSystem.dynamicType; |
333 } | 336 } |
334 | 337 |
335 /// Build the IR term for the function that adapts a call site targeting a | 338 /// 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. | 339 /// function that takes optional arguments not passed at the call site. |
337 FunctionDefinition buildAdapter(InvokeMethod node, FunctionElement target) { | 340 FunctionDefinition buildAdapter(InvokeMethod node, FunctionElement target) { |
338 Parameter thisParameter = new Parameter(new ThisParameterLocal(target)) | 341 Parameter thisParameter = new Parameter(new ThisParameterLocal(target)) |
339 ..type = node.receiver.type; | 342 ..type = node.receiver.type; |
| 343 Parameter interceptorParameter = node.interceptorRef != null |
| 344 ? new Parameter(null) |
| 345 : null; |
340 List<Parameter> parameters = new List<Parameter>.generate( | 346 List<Parameter> parameters = new List<Parameter>.generate( |
341 node.argumentRefs.length, | 347 node.argumentRefs.length, |
342 (int index) { | 348 (int index) { |
343 // TODO(kmillikin): Use a hint for the parameter names. | 349 // TODO(kmillikin): Use a hint for the parameter names. |
344 return new Parameter(null) | 350 return new Parameter(null) |
345 ..type = node.argument(index).type; | 351 ..type = node.argument(index).type; |
346 }); | 352 }); |
347 Continuation returnContinuation = new Continuation.retrn(); | 353 Continuation returnContinuation = new Continuation.retrn(); |
348 CpsFragment cps = new CpsFragment(); | 354 CpsFragment cps = new CpsFragment(); |
349 | 355 |
350 FunctionSignature signature = target.functionSignature; | 356 FunctionSignature signature = target.functionSignature; |
351 int requiredParameterCount = signature.requiredParameterCount; | 357 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( | 358 List<Primitive> arguments = new List<Primitive>.generate( |
357 requiredParameterCount, | 359 requiredParameterCount, |
358 (int index) => parameters[index]); | 360 (int index) => parameters[index]); |
359 | 361 |
360 int parameterIndex = requiredParameterCount; | 362 int parameterIndex = requiredParameterCount; |
361 CallStructure newCallStructure; | 363 CallStructure newCallStructure; |
362 if (signature.optionalParametersAreNamed) { | 364 if (signature.optionalParametersAreNamed) { |
363 List<String> incomingNames = | 365 List<String> incomingNames = |
364 node.selector.callStructure.getOrderedNamedArguments(); | 366 node.selector.callStructure.getOrderedNamedArguments(); |
365 List<String> outgoingNames = <String>[]; | 367 List<String> outgoingNames = <String>[]; |
(...skipping 23 matching lines...) Expand all Loading... |
389 defaultValue.type = typeSystem.getParameterType(formal); | 391 defaultValue.type = typeSystem.getParameterType(formal); |
390 arguments.add(defaultValue); | 392 arguments.add(defaultValue); |
391 } | 393 } |
392 }); | 394 }); |
393 newCallStructure = new CallStructure(signature.parameterCount); | 395 newCallStructure = new CallStructure(signature.parameterCount); |
394 } | 396 } |
395 | 397 |
396 Selector newSelector = | 398 Selector newSelector = |
397 new Selector(node.selector.kind, node.selector.memberName, | 399 new Selector(node.selector.kind, node.selector.memberName, |
398 newCallStructure); | 400 newCallStructure); |
399 Primitive result = cps.invokeMethod(thisParameter, newSelector, node.mask, | 401 Primitive result = cps.invokeMethod(thisParameter, |
400 arguments, node.callingConvention); | 402 newSelector, |
| 403 node.mask, |
| 404 arguments, |
| 405 interceptor: interceptorParameter, |
| 406 callingConvention: node.callingConvention); |
401 result.type = typeSystem.getInvokeReturnType(node.selector, node.mask); | 407 result.type = typeSystem.getInvokeReturnType(node.selector, node.mask); |
402 returnContinuation.parameters.single.type = result.type; | 408 returnContinuation.parameters.single.type = result.type; |
403 cps.invokeContinuation(returnContinuation, <Primitive>[result]); | 409 cps.invokeContinuation(returnContinuation, <Primitive>[result]); |
404 return new FunctionDefinition(target, thisParameter, parameters, | 410 return new FunctionDefinition(target, thisParameter, parameters, |
405 returnContinuation, | 411 returnContinuation, |
406 cps.root); | 412 cps.root, |
| 413 interceptorParameter: interceptorParameter); |
407 } | 414 } |
408 | 415 |
409 // Given an invocation and a known target, possibly perform inlining. | 416 // Given an invocation and a known target, possibly perform inlining. |
410 // | 417 // |
411 // An optional call structure indicates a dynamic call. Calls that are | 418 // An optional call structure indicates a dynamic call. Calls that are |
412 // already resolved statically have a null call structure. | 419 // already resolved statically have a null call structure. |
413 // | 420 // |
414 // The [Primitive] representing the result of the inlined call is returned | 421 // 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 | 422 // if the call was inlined, and the inlined function body is available in |
416 // [_fragment]. If the call was not inlined, null is returned. | 423 // [_fragment]. If the call was not inlined, null is returned. |
(...skipping 20 matching lines...) Expand all Loading... |
437 } | 444 } |
438 | 445 |
439 if (isBlacklisted(target)) return null; | 446 if (isBlacklisted(target)) return null; |
440 | 447 |
441 if (invoke.callingConvention == CallingConvention.OneShotIntercepted) { | 448 if (invoke.callingConvention == CallingConvention.OneShotIntercepted) { |
442 // One-shot interceptor calls with a known target are only inserted on | 449 // One-shot interceptor calls with a known target are only inserted on |
443 // uncommon code paths, so they should not be inlined. | 450 // uncommon code paths, so they should not be inlined. |
444 return null; | 451 return null; |
445 } | 452 } |
446 | 453 |
447 Reference<Primitive> dartReceiver = invoke.dartReceiverRef; | 454 Primitive receiver = invoke.receiver; |
448 TypeMask abstractReceiver = | 455 TypeMask abstractReceiver = |
449 dartReceiver == null ? null : abstractType(dartReceiver); | 456 receiver == null ? null : abstractType(receiver); |
450 // The receiver is non-null in a method body, unless the receiver is known | 457 // The receiver is non-null in a method body, unless the receiver is known |
451 // to be `null` (isEmpty covers `null` and unreachable). | 458 // to be `null` (isEmpty covers `null` and unreachable). |
452 TypeMask abstractReceiverInMethod = abstractReceiver == null | 459 TypeMask abstractReceiverInMethod = abstractReceiver == null |
453 ? null | 460 ? null |
454 : abstractReceiver.isEmptyOrNull | 461 : abstractReceiver.isEmptyOrNull |
455 ? abstractReceiver | 462 ? abstractReceiver |
456 : abstractReceiver.nonNullable(); | 463 : abstractReceiver.nonNullable(); |
457 List<TypeMask> abstractArguments = | 464 List<TypeMask> abstractArguments = |
458 invoke.argumentRefs.map(abstractType).toList(); | 465 invoke.arguments.map(abstractType).toList(); |
459 var cachedResult = _inliner.cache.get(target, callStructure, | 466 var cachedResult = _inliner.cache.get(target, callStructure, |
460 abstractReceiverInMethod, | 467 abstractReceiverInMethod, |
461 abstractArguments); | 468 abstractArguments); |
462 | 469 |
463 // Negative inlining result in the cache. | 470 // Negative inlining result in the cache. |
464 if (cachedResult == InliningCache.NO_INLINE) return null; | 471 if (cachedResult == InliningCache.NO_INLINE) return null; |
465 | 472 |
466 Primitive finish(FunctionDefinition function) { | 473 Primitive finish(FunctionDefinition function) { |
467 _fragment = new CpsFragment(invoke.sourceInformation); | 474 _fragment = new CpsFragment(invoke.sourceInformation); |
468 Primitive receiver = invoke.receiver; | 475 Primitive receiver = invoke.receiver; |
469 List<Primitive> arguments = invoke.arguments.toList(); | 476 List<Primitive> arguments = invoke.arguments.toList(); |
470 // Add a null check to the inlined function body if necessary. The | 477 // Add a null check to the inlined function body if necessary. The |
471 // cached function body does not contain the null check. | 478 // cached function body does not contain the null check. |
472 if (dartReceiver != null && abstractReceiver.isNullable) { | 479 if (receiver != null && abstractReceiver.isNullable) { |
473 Primitive check = nullReceiverGuard( | 480 receiver = nullReceiverGuard( |
474 invoke, _fragment, dartReceiver.definition, abstractReceiver); | 481 invoke, _fragment, receiver, abstractReceiver); |
475 if (invoke.callingConvention == CallingConvention.Intercepted) { | |
476 arguments[0] = check; | |
477 } else { | |
478 receiver = check; | |
479 } | |
480 } | 482 } |
481 return _fragment.inlineFunction(function, receiver, arguments, | 483 return _fragment.inlineFunction(function, receiver, arguments, |
482 hint: invoke.hint); | 484 interceptor: invoke.interceptor, hint: invoke.hint); |
483 } | 485 } |
484 | 486 |
485 // Positive inlining result in the cache. | 487 // Positive inlining result in the cache. |
486 if (cachedResult is FunctionDefinition) { | 488 if (cachedResult is FunctionDefinition) { |
487 return finish(cachedResult); | 489 return finish(cachedResult); |
488 } | 490 } |
489 | 491 |
490 // We have not seen this combination of target and abstract arguments | 492 // We have not seen this combination of target and abstract arguments |
491 // before. Make an inlining decision. | 493 // before. Make an inlining decision. |
492 assert(cachedResult == InliningCache.ABSENT); | 494 assert(cachedResult == InliningCache.ABSENT); |
(...skipping 13 matching lines...) Expand all Loading... |
506 // formal parameter count. Build the IR term for an adapter function | 508 // formal parameter count. Build the IR term for an adapter function |
507 // body. | 509 // body. |
508 if (backend.isNative(target)) { | 510 if (backend.isNative(target)) { |
509 // TODO(25548): Generate correct adaptor for native methods. | 511 // TODO(25548): Generate correct adaptor for native methods. |
510 return doNotInline(); | 512 return doNotInline(); |
511 } else { | 513 } else { |
512 function = buildAdapter(invoke, target); | 514 function = buildAdapter(invoke, target); |
513 } | 515 } |
514 } else { | 516 } else { |
515 function = compileToCpsIr(target); | 517 function = compileToCpsIr(target); |
516 void setValue(Variable variable, Reference<Primitive> value) { | 518 if (function.receiverParameter != null) { |
517 variable.type = value.definition.type; | 519 function.receiverParameter.type = abstractReceiverInMethod; |
518 } | 520 } |
519 if (invoke.callingConvention == CallingConvention.Intercepted) { | 521 for (int i = 0; i < invoke.argumentRefs.length; ++i) { |
520 setValue(function.thisParameter, invoke.receiverRef); | 522 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 } | 523 } |
533 optimizeBeforeInlining(function); | 524 optimizeBeforeInlining(function); |
534 } | 525 } |
535 | 526 |
536 // Inline calls in the body. | 527 // Inline calls in the body. |
537 _inliner.rewrite(function, callStructure); | 528 _inliner.rewrite(function, callStructure); |
538 | 529 |
539 // Compute the size. | 530 // Compute the size. |
540 // TODO(kmillikin): Tune the size bound. | 531 // TODO(kmillikin): Tune the size bound. |
541 int size = SizeVisitor.sizeOf(invoke, function); | 532 int size = SizeVisitor.sizeOf(invoke, function); |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
575 } | 566 } |
576 | 567 |
577 | 568 |
578 @override | 569 @override |
579 Primitive visitInvokeStatic(InvokeStatic node) { | 570 Primitive visitInvokeStatic(InvokeStatic node) { |
580 return tryInlining(node, node.target, null); | 571 return tryInlining(node, node.target, null); |
581 } | 572 } |
582 | 573 |
583 @override | 574 @override |
584 Primitive visitInvokeMethod(InvokeMethod node) { | 575 Primitive visitInvokeMethod(InvokeMethod node) { |
585 Primitive receiver = node.dartReceiver; | 576 Primitive receiver = node.receiver; |
586 Element element = world.locateSingleElement(node.selector, receiver.type); | 577 Element element = world.locateSingleElement(node.selector, receiver.type); |
587 if (element == null || element is! FunctionElement) return null; | 578 if (element == null || element is! FunctionElement) return null; |
588 if (node.selector.isGetter != element.isGetter) return null; | 579 if (node.selector.isGetter != element.isGetter) return null; |
589 if (node.selector.isSetter != element.isSetter) return null; | 580 if (node.selector.isSetter != element.isSetter) return null; |
590 if (node.selector.name != element.name) return null; | 581 if (node.selector.name != element.name) return null; |
591 | 582 |
592 return tryInlining(node, element.asFunctionElement(), | 583 return tryInlining(node, element.asFunctionElement(), |
593 node.selector.callStructure); | 584 node.selector.callStructure); |
594 } | 585 } |
595 | 586 |
(...skipping 23 matching lines...) Expand all Loading... |
619 (enclosingClass == backend.helpers.jsNumberClass || | 610 (enclosingClass == backend.helpers.jsNumberClass || |
620 enclosingClass == backend.helpers.jsDoubleClass || | 611 enclosingClass == backend.helpers.jsDoubleClass || |
621 enclosingClass == backend.helpers.jsIntClass)) { | 612 enclosingClass == backend.helpers.jsIntClass)) { |
622 // These should be handled by operator specialization. | 613 // These should be handled by operator specialization. |
623 return true; | 614 return true; |
624 } | 615 } |
625 if (target == backend.helpers.stringInterpolationHelper) return true; | 616 if (target == backend.helpers.stringInterpolationHelper) return true; |
626 return false; | 617 return false; |
627 } | 618 } |
628 } | 619 } |
OLD | NEW |