| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library cps_ir.optimization.inline; | |
| 6 | |
| 7 import 'cps_fragment.dart'; | |
| 8 import 'cps_ir_builder.dart' show ThisParameterLocal; | |
| 9 import 'cps_ir_nodes.dart'; | |
| 10 import 'optimizers.dart'; | |
| 11 import 'type_mask_system.dart' show TypeMaskSystem; | |
| 12 import '../compiler.dart' show Compiler; | |
| 13 import '../dart_types.dart' show DartType, GenericType; | |
| 14 import '../io/source_information.dart' show SourceInformation; | |
| 15 import '../world.dart' show World; | |
| 16 import '../constants/values.dart' show ConstantValue; | |
| 17 import '../elements/elements.dart'; | |
| 18 import '../js_backend/js_backend.dart' show JavaScriptBackend; | |
| 19 import '../js_backend/codegen/task.dart' show CpsFunctionCompiler; | |
| 20 import '../types/types.dart' show | |
| 21 FlatTypeMask, ForwardingTypeMask, TypeMask, UnionTypeMask; | |
| 22 import '../universe/call_structure.dart' show CallStructure; | |
| 23 import '../universe/selector.dart' show Selector; | |
| 24 | |
| 25 /// Inlining stack entries. | |
| 26 /// | |
| 27 /// During inlining, a stack is used to detect cycles in the call graph. | |
| 28 class StackEntry { | |
| 29 // Dynamically resolved calls might be targeting an adapter function that | |
| 30 // fills in optional arguments not passed at the call site. Therefore these | |
| 31 // calls are represented by the eventual target and the call structure at | |
| 32 // the call site, which together identify the target. Statically resolved | |
| 33 // calls are represented by the target element and a null call structure. | |
| 34 final ExecutableElement target; | |
| 35 final CallStructure callStructure; | |
| 36 | |
| 37 StackEntry(this.target, this.callStructure); | |
| 38 | |
| 39 bool match(ExecutableElement otherTarget, CallStructure otherCallStructure) { | |
| 40 if (target != otherTarget) return false; | |
| 41 if (callStructure == null) return otherCallStructure == null; | |
| 42 return otherCallStructure != null && | |
| 43 callStructure.match(otherCallStructure); | |
| 44 } | |
| 45 } | |
| 46 | |
| 47 /// Inlining cache entries. | |
| 48 class CacheEntry { | |
| 49 // The cache maps a function element to a list of entries, where each entry | |
| 50 // is a tuple of (call structure, abstract receiver, abstract arguments) | |
| 51 // along with the inlining decision and optional IR function definition. | |
| 52 final CallStructure callStructure; | |
| 53 final TypeMask receiver; | |
| 54 final List<TypeMask> arguments; | |
| 55 | |
| 56 final bool decision; | |
| 57 final FunctionDefinition function; | |
| 58 | |
| 59 CacheEntry(this.callStructure, this.receiver, this.arguments, this.decision, | |
| 60 this.function); | |
| 61 | |
| 62 bool match(CallStructure otherCallStructure, TypeMask otherReceiver, | |
| 63 List<TypeMask> otherArguments) { | |
| 64 if (callStructure == null) { | |
| 65 if (otherCallStructure != null) return false; | |
| 66 } else if (otherCallStructure == null || | |
| 67 !callStructure.match(otherCallStructure)) { | |
| 68 return false; | |
| 69 } | |
| 70 | |
| 71 if (receiver != otherReceiver) return false; | |
| 72 assert(arguments.length == otherArguments.length); | |
| 73 for (int i = 0; i < arguments.length; ++i) { | |
| 74 if (arguments[i] != otherArguments[i]) return false; | |
| 75 } | |
| 76 return true; | |
| 77 } | |
| 78 } | |
| 79 | |
| 80 /// An inlining cache. | |
| 81 /// | |
| 82 /// During inlining a cache is used to remember inlining decisions for shared | |
| 83 /// parts of the call graph, to avoid exploring them more than once. | |
| 84 /// | |
| 85 /// The cache maps a tuple of (function element, call structure, | |
| 86 /// abstract receiver, abstract arguments) to a boolean inlining decision and | |
| 87 /// an IR function definition if the decision is positive. | |
| 88 class InliningCache { | |
| 89 static const int ABSENT = -1; | |
| 90 static const int NO_INLINE = 0; | |
| 91 | |
| 92 final Map<ExecutableElement, List<CacheEntry>> map = | |
| 93 <ExecutableElement, List<CacheEntry>>{}; | |
| 94 | |
| 95 // When function definitions are put into or removed from the cache, they are | |
| 96 // copied because the compiler passes will mutate them. | |
| 97 final CopyingVisitor copier = new CopyingVisitor(); | |
| 98 | |
| 99 void _putInternal(ExecutableElement element, CallStructure callStructure, | |
| 100 TypeMask receiver, | |
| 101 List<TypeMask> arguments, | |
| 102 bool decision, | |
| 103 FunctionDefinition function) { | |
| 104 map.putIfAbsent(element, () => <CacheEntry>[]) | |
| 105 .add(new CacheEntry(callStructure, receiver, arguments, decision, | |
| 106 function)); | |
| 107 } | |
| 108 | |
| 109 /// Put a positive inlining decision in the cache. | |
| 110 /// | |
| 111 /// A positive inlining decision maps to an IR function definition. | |
| 112 void putPositive(ExecutableElement element, CallStructure callStructure, | |
| 113 TypeMask receiver, | |
| 114 List<TypeMask> arguments, | |
| 115 FunctionDefinition function) { | |
| 116 _putInternal(element, callStructure, receiver, arguments, true, | |
| 117 copier.copy(function)); | |
| 118 } | |
| 119 | |
| 120 /// Put a negative inlining decision in the cache. | |
| 121 void putNegative(ExecutableElement element, | |
| 122 CallStructure callStructure, | |
| 123 TypeMask receiver, | |
| 124 List<TypeMask> arguments) { | |
| 125 _putInternal(element, callStructure, receiver, arguments, false, null); | |
| 126 } | |
| 127 | |
| 128 /// Look up a tuple in the cache. | |
| 129 /// | |
| 130 /// A positive lookup result return the IR function definition. A negative | |
| 131 /// lookup result returns [NO_INLINE]. If there is no cached result, | |
| 132 /// [ABSENT] is returned. | |
| 133 get(ExecutableElement element, CallStructure callStructure, TypeMask receiver, | |
| 134 List<TypeMask> arguments) { | |
| 135 List<CacheEntry> entries = map[element]; | |
| 136 if (entries != null) { | |
| 137 for (CacheEntry entry in entries) { | |
| 138 if (entry.match(callStructure, receiver, arguments)) { | |
| 139 if (entry.decision) { | |
| 140 FunctionDefinition function = copier.copy(entry.function); | |
| 141 ParentVisitor.setParents(function); | |
| 142 return function; | |
| 143 } | |
| 144 return NO_INLINE; | |
| 145 } | |
| 146 } | |
| 147 } | |
| 148 return ABSENT; | |
| 149 } | |
| 150 } | |
| 151 | |
| 152 class Inliner implements Pass { | |
| 153 get passName => 'Inline calls'; | |
| 154 | |
| 155 final CpsFunctionCompiler functionCompiler; | |
| 156 | |
| 157 final InliningCache cache = new InliningCache(); | |
| 158 | |
| 159 final List<StackEntry> stack = <StackEntry>[]; | |
| 160 | |
| 161 Inliner(this.functionCompiler); | |
| 162 | |
| 163 bool isCalledOnce(Element element) { | |
| 164 return functionCompiler.compiler.typesTask.typesInferrer.isCalledOnce( | |
| 165 element); | |
| 166 } | |
| 167 | |
| 168 void rewrite(FunctionDefinition node, [CallStructure callStructure]) { | |
| 169 Element function = node.element; | |
| 170 | |
| 171 // Inlining in asynchronous or generator functions is disabled. Inlining | |
| 172 // triggers a bug in the async rewriter. | |
| 173 // TODO(kmillikin): Fix the bug and eliminate this restriction if it makes | |
| 174 // sense. | |
| 175 if (function is FunctionElement && | |
| 176 function.asyncMarker != AsyncMarker.SYNC) { | |
| 177 return; | |
| 178 } | |
| 179 | |
| 180 stack.add(new StackEntry(function, callStructure)); | |
| 181 new InliningVisitor(this).visit(node); | |
| 182 assert(stack.last.match(function, callStructure)); | |
| 183 stack.removeLast(); | |
| 184 new ShrinkingReducer().rewrite(node); | |
| 185 } | |
| 186 } | |
| 187 | |
| 188 /// Compute an abstract size of an IR function definition. | |
| 189 /// | |
| 190 /// The size represents the cost of inlining at a call site. | |
| 191 class SizeVisitor extends TrampolineRecursiveVisitor { | |
| 192 int size = 0; | |
| 193 | |
| 194 void countArgument(Reference<Primitive> argument, Parameter parameter) { | |
| 195 // If a parameter is unused and the corresponding argument has only the | |
| 196 // one use at the invocation, then inlining the call might enable | |
| 197 // elimination of the argument. This 'pays for itself' by decreasing the | |
| 198 // cost of inlining at the call site. | |
| 199 if (argument != null && | |
| 200 argument.definition.hasExactlyOneUse && | |
| 201 parameter.hasNoUses) { | |
| 202 --size; | |
| 203 } | |
| 204 } | |
| 205 | |
| 206 static int sizeOf(InvocationPrimitive invoke, FunctionDefinition function) { | |
| 207 SizeVisitor visitor = new SizeVisitor(); | |
| 208 visitor.visit(function); | |
| 209 visitor.countArgument(invoke.receiver, function.thisParameter); | |
| 210 for (int i = 0; i < invoke.arguments.length; ++i) { | |
| 211 visitor.countArgument(invoke.arguments[i], function.parameters[i]); | |
| 212 } | |
| 213 return visitor.size; | |
| 214 } | |
| 215 | |
| 216 // Inlining a function incurs a cost equal to the number of primitives and | |
| 217 // non-jump tail expressions. | |
| 218 // TODO(kmillikin): Tune the size computation and size bound. | |
| 219 processLetPrim(LetPrim node) => ++size; | |
| 220 processLetMutable(LetMutable node) => ++size; | |
| 221 processBranch(Branch node) => ++size; | |
| 222 processThrow(Throw nose) => ++size; | |
| 223 processRethrow(Rethrow node) => ++size; | |
| 224 } | |
| 225 | |
| 226 class InliningVisitor extends TrampolineRecursiveVisitor { | |
| 227 final Inliner _inliner; | |
| 228 | |
| 229 // A successful inlining attempt returns the [Primitive] that represents the | |
| 230 // result of the inlined call or null. If the result is non-null, the body | |
| 231 // of the inlined function is available in this field. | |
| 232 CpsFragment _fragment; | |
| 233 | |
| 234 InliningVisitor(this._inliner); | |
| 235 | |
| 236 JavaScriptBackend get backend => _inliner.functionCompiler.backend; | |
| 237 TypeMaskSystem get typeSystem => _inliner.functionCompiler.typeSystem; | |
| 238 World get world => _inliner.functionCompiler.compiler.world; | |
| 239 | |
| 240 FunctionDefinition compileToCpsIr(AstElement element) { | |
| 241 return _inliner.functionCompiler.compileToCpsIr(element); | |
| 242 } | |
| 243 | |
| 244 void optimizeBeforeInlining(FunctionDefinition function) { | |
| 245 _inliner.functionCompiler.optimizeCpsBeforeInlining(function); | |
| 246 } | |
| 247 | |
| 248 void applyCpsPass(Pass pass, FunctionDefinition function) { | |
| 249 return _inliner.functionCompiler.applyCpsPass(pass, function); | |
| 250 } | |
| 251 | |
| 252 bool isRecursive(Element target, CallStructure callStructure) { | |
| 253 return _inliner.stack.any((StackEntry s) => s.match(target, callStructure)); | |
| 254 } | |
| 255 | |
| 256 @override | |
| 257 Expression traverseLetPrim(LetPrim node) { | |
| 258 // A successful inlining attempt will set the node's body to null, so it is | |
| 259 // read before visiting the primitive. | |
| 260 Expression next = node.body; | |
| 261 Primitive replacement = visit(node.primitive); | |
| 262 if (replacement != null) { | |
| 263 node.primitive.replaceWithFragment(_fragment, replacement); | |
| 264 } | |
| 265 return next; | |
| 266 } | |
| 267 | |
| 268 TypeMask abstractType(Reference<Primitive> ref) { | |
| 269 return ref.definition.type ?? typeSystem.dynamicType; | |
| 270 } | |
| 271 | |
| 272 /// Build the IR term for the function that adapts a call site targeting a | |
| 273 /// function that takes optional arguments not passed at the call site. | |
| 274 FunctionDefinition buildAdapter(InvokeMethod node, FunctionElement target) { | |
| 275 Parameter thisParameter = new Parameter(new ThisParameterLocal(target)) | |
| 276 ..type = node.receiver.definition.type; | |
| 277 List<Parameter> parameters = new List<Parameter>.generate( | |
| 278 node.arguments.length, | |
| 279 (int index) { | |
| 280 // TODO(kmillikin): Use a hint for the parameter names. | |
| 281 return new Parameter(null) | |
| 282 ..type = node.arguments[index].definition.type; | |
| 283 }); | |
| 284 Continuation returnContinuation = new Continuation.retrn(); | |
| 285 CpsFragment cps = new CpsFragment(); | |
| 286 | |
| 287 FunctionSignature signature = target.functionSignature; | |
| 288 int requiredParameterCount = signature.requiredParameterCount; | |
| 289 if (node.callingConvention == CallingConvention.Intercepted || | |
| 290 node.callingConvention == CallingConvention.DummyIntercepted) { | |
| 291 ++requiredParameterCount; | |
| 292 } | |
| 293 List<Primitive> arguments = new List<Primitive>.generate( | |
| 294 requiredParameterCount, | |
| 295 (int index) => parameters[index]); | |
| 296 | |
| 297 int parameterIndex = requiredParameterCount; | |
| 298 CallStructure newCallStructure; | |
| 299 if (signature.optionalParametersAreNamed) { | |
| 300 List<String> incomingNames = | |
| 301 node.selector.callStructure.getOrderedNamedArguments(); | |
| 302 List<String> outgoingNames = <String>[]; | |
| 303 int nameIndex = 0; | |
| 304 signature.orderedOptionalParameters.forEach((ParameterElement formal) { | |
| 305 if (nameIndex < incomingNames.length && | |
| 306 formal.name == incomingNames[nameIndex]) { | |
| 307 arguments.add(parameters[parameterIndex++]); | |
| 308 ++nameIndex; | |
| 309 } else { | |
| 310 Constant defaultValue = cps.makeConstant( | |
| 311 backend.constants.getConstantValueForVariable(formal)); | |
| 312 defaultValue.type = typeSystem.getParameterType(formal); | |
| 313 arguments.add(defaultValue); | |
| 314 } | |
| 315 outgoingNames.add(formal.name); | |
| 316 }); | |
| 317 newCallStructure = | |
| 318 new CallStructure(signature.parameterCount, outgoingNames); | |
| 319 } else { | |
| 320 signature.forEachOptionalParameter((ParameterElement formal) { | |
| 321 if (parameterIndex < parameters.length) { | |
| 322 arguments.add(parameters[parameterIndex++]); | |
| 323 } else { | |
| 324 Constant defaultValue = cps.makeConstant( | |
| 325 backend.constants.getConstantValueForVariable(formal)); | |
| 326 defaultValue.type = typeSystem.getParameterType(formal); | |
| 327 arguments.add(defaultValue); | |
| 328 } | |
| 329 }); | |
| 330 newCallStructure = new CallStructure(signature.parameterCount); | |
| 331 } | |
| 332 | |
| 333 Selector newSelector = | |
| 334 new Selector(node.selector.kind, node.selector.memberName, | |
| 335 newCallStructure); | |
| 336 Primitive result = cps.invokeMethod(thisParameter, newSelector, node.mask, | |
| 337 arguments, node.callingConvention); | |
| 338 result.type = typeSystem.getInvokeReturnType(node.selector, node.mask); | |
| 339 cps.invokeContinuation(returnContinuation, <Primitive>[result]); | |
| 340 return new FunctionDefinition(target, thisParameter, parameters, | |
| 341 returnContinuation, | |
| 342 cps.root); | |
| 343 } | |
| 344 | |
| 345 // Given an invocation and a known target, possibly perform inlining. | |
| 346 // | |
| 347 // An optional call structure indicates a dynamic call. Calls that are | |
| 348 // already resolved statically have a null call structure. | |
| 349 // | |
| 350 // The [Primitive] representing the result of the inlined call is returned | |
| 351 // if the call was inlined, and the inlined function body is available in | |
| 352 // [_fragment]. If the call was not inlined, null is returned. | |
| 353 Primitive tryInlining(InvocationPrimitive invoke, FunctionElement target, | |
| 354 CallStructure callStructure) { | |
| 355 // Quick checks: do not inline or even cache calls to targets without an | |
| 356 // AST node or targets that are asynchronous or generator functions. | |
| 357 if (!target.hasNode) return null; | |
| 358 if (target.asyncMarker != AsyncMarker.SYNC) return null; | |
| 359 | |
| 360 Reference<Primitive> dartReceiver = invoke.dartReceiverReference; | |
| 361 TypeMask abstractReceiver = | |
| 362 dartReceiver == null ? null : abstractType(dartReceiver); | |
| 363 List<TypeMask> abstractArguments = | |
| 364 invoke.arguments.map(abstractType).toList(); | |
| 365 var cachedResult = _inliner.cache.get(target, callStructure, | |
| 366 abstractReceiver, | |
| 367 abstractArguments); | |
| 368 | |
| 369 // Negative inlining result in the cache. | |
| 370 if (cachedResult == InliningCache.NO_INLINE) return null; | |
| 371 | |
| 372 // Positive inlining result in the cache. | |
| 373 if (cachedResult is FunctionDefinition) { | |
| 374 FunctionDefinition function = cachedResult; | |
| 375 _fragment = new CpsFragment(invoke.sourceInformation); | |
| 376 Primitive receiver = invoke.receiver?.definition; | |
| 377 List<Primitive> arguments = | |
| 378 invoke.arguments.map((Reference ref) => ref.definition).toList(); | |
| 379 // Add a null check to the inlined function body if necessary. The | |
| 380 // cached function body does not contain the null check. | |
| 381 if (dartReceiver != null && abstractReceiver.isNullable) { | |
| 382 Primitive check = | |
| 383 _fragment.letPrim(new NullCheck(dartReceiver.definition, | |
| 384 invoke.sourceInformation)); | |
| 385 check.type = abstractReceiver.nonNullable(); | |
| 386 if (invoke.callingConvention == CallingConvention.Intercepted) { | |
| 387 arguments[0] = check; | |
| 388 } else { | |
| 389 receiver = check; | |
| 390 } | |
| 391 } | |
| 392 return _fragment.inlineFunction(function, receiver, arguments, | |
| 393 hint: invoke.hint); | |
| 394 } | |
| 395 | |
| 396 // We have not seen this combination of target and abstract arguments | |
| 397 // before. Make an inlining decision. | |
| 398 assert(cachedResult == InliningCache.ABSENT); | |
| 399 Primitive doNotInline() { | |
| 400 _inliner.cache.putNegative(target, callStructure, abstractReceiver, | |
| 401 abstractArguments); | |
| 402 return null; | |
| 403 } | |
| 404 if (backend.annotations.noInline(target)) return doNotInline(); | |
| 405 if (isRecursive(target, callStructure)) return doNotInline(); | |
| 406 | |
| 407 FunctionDefinition function; | |
| 408 if (callStructure != null && | |
| 409 target.functionSignature.parameterCount != | |
| 410 callStructure.argumentCount) { | |
| 411 // The argument count at the call site does not match the target's | |
| 412 // formal parameter count. Build the IR term for an adapter function | |
| 413 // body. | |
| 414 function = buildAdapter(invoke, target); | |
| 415 } else { | |
| 416 function = _inliner.functionCompiler.compileToCpsIr(target); | |
| 417 void setValue(Variable variable, Reference<Primitive> value) { | |
| 418 variable.type = value.definition.type; | |
| 419 } | |
| 420 if (invoke.receiver != null) { | |
| 421 setValue(function.thisParameter, invoke.receiver); | |
| 422 } | |
| 423 for (int i = 0; i < invoke.arguments.length; ++i) { | |
| 424 setValue(function.parameters[i], invoke.arguments[i]); | |
| 425 } | |
| 426 optimizeBeforeInlining(function); | |
| 427 } | |
| 428 | |
| 429 // Inline calls in the body. | |
| 430 _inliner.rewrite(function, callStructure); | |
| 431 | |
| 432 // Compute the size. | |
| 433 // TODO(kmillikin): Tune the size bound. | |
| 434 int size = SizeVisitor.sizeOf(invoke, function); | |
| 435 if (!_inliner.isCalledOnce(target) && size > 11) return doNotInline(); | |
| 436 | |
| 437 _inliner.cache.putPositive(target, callStructure, abstractReceiver, | |
| 438 abstractArguments, function); | |
| 439 _fragment = new CpsFragment(invoke.sourceInformation); | |
| 440 Primitive receiver = invoke.receiver?.definition; | |
| 441 List<Primitive> arguments = | |
| 442 invoke.arguments.map((Reference ref) => ref.definition).toList(); | |
| 443 if (dartReceiver != null && abstractReceiver.isNullable) { | |
| 444 Primitive check = | |
| 445 _fragment.letPrim(new NullCheck(dartReceiver.definition, | |
| 446 invoke.sourceInformation)); | |
| 447 check.type = abstractReceiver.nonNullable(); | |
| 448 if (invoke.callingConvention == CallingConvention.Intercepted) { | |
| 449 arguments[0] = check; | |
| 450 } else { | |
| 451 receiver = check; | |
| 452 } | |
| 453 } | |
| 454 return _fragment.inlineFunction(function, receiver, arguments, | |
| 455 hint: invoke.hint); | |
| 456 } | |
| 457 | |
| 458 @override | |
| 459 Primitive visitInvokeStatic(InvokeStatic node) { | |
| 460 return tryInlining(node, node.target, null); | |
| 461 } | |
| 462 | |
| 463 @override | |
| 464 Primitive visitInvokeMethod(InvokeMethod node) { | |
| 465 Primitive receiver = node.dartReceiver; | |
| 466 Element element = world.locateSingleElement(node.selector, receiver.type); | |
| 467 if (element == null || element is! FunctionElement) return null; | |
| 468 if (node.selector.isGetter != element.isGetter) return null; | |
| 469 if (node.selector.isSetter != element.isSetter) return null; | |
| 470 if (node.selector.name != element.name) return null; | |
| 471 | |
| 472 return tryInlining(node, element.asFunctionElement(), | |
| 473 node.selector.callStructure); | |
| 474 } | |
| 475 | |
| 476 @override | |
| 477 Primitive visitInvokeMethodDirectly(InvokeMethodDirectly node) { | |
| 478 if (node.selector.isGetter != node.target.isGetter) return null; | |
| 479 if (node.selector.isSetter != node.target.isSetter) return null; | |
| 480 return tryInlining(node, node.target, null); | |
| 481 } | |
| 482 | |
| 483 @override | |
| 484 Primitive visitInvokeConstructor(InvokeConstructor node) { | |
| 485 if (node.dartType is GenericType) { | |
| 486 // We cannot inline a constructor invocation containing type arguments | |
| 487 // because CreateInstance in the body does not know the type arguments. | |
| 488 // We would incorrectly instantiate a class like A instead of A<B>. | |
| 489 // TODO(kmillikin): try to fix this. | |
| 490 GenericType generic = node.dartType; | |
| 491 if (generic.typeArguments.any((DartType t) => !t.isDynamic)) return null; | |
| 492 } | |
| 493 return tryInlining(node, node.target, null); | |
| 494 } | |
| 495 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1542003003:
Revert "dart2js: Initial implementation of inlining." (Closed)
Base URL: git@github.com:dart-lang/sdk.git@master