Chromium Code Reviews| 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 |