| OLD | NEW |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 type_graph_inferrer; | 5 library type_graph_inferrer; |
| 6 | 6 |
| 7 import 'dart:collection' show Queue; | 7 import 'dart:collection' show Queue; |
| 8 | 8 |
| 9 import '../common.dart'; | 9 import '../common.dart'; |
| 10 import '../common/names.dart' show Identifiers; | 10 import '../common/names.dart' show Identifiers; |
| 11 import '../compiler.dart' show Compiler; | 11 import '../compiler.dart' show Compiler; |
| 12 import '../constants/expressions.dart' show ConstantExpression; | 12 import '../constants/expressions.dart' show ConstantExpression; |
| 13 import '../constants/values.dart'; | 13 import '../constants/values.dart'; |
| 14 import '../dart_types.dart' show DartType; | 14 import '../dart_types.dart' show DartType; |
| 15 import '../elements/elements.dart'; | 15 import '../elements/elements.dart'; |
| 16 import '../js_backend/js_backend.dart' show Annotations, JavaScriptBackend; | 16 import '../js_backend/js_backend.dart' show Annotations, JavaScriptBackend; |
| 17 import '../resolution/tree_elements.dart' show TreeElementMapping; | 17 import '../resolution/tree_elements.dart' show TreeElementMapping; |
| 18 import '../tree/dartstring.dart' show DartString; | 18 import '../tree/dartstring.dart' show DartString; |
| 19 import '../tree/tree.dart' as ast show Node, LiteralBool, TryStatement; | 19 import '../tree/tree.dart' as ast show Node, LiteralBool, TryStatement; |
| 20 import '../types/constants.dart' show computeTypeMask; | 20 import '../types/constants.dart' show computeTypeMask; |
| 21 import '../types/masks.dart' | 21 import '../types/masks.dart' |
| 22 show CommonMasks, ContainerTypeMask, MapTypeMask, TypeMask; | 22 show CommonMasks, ContainerTypeMask, MapTypeMask, TypeMask; |
| 23 import '../types/types.dart' show TypesInferrer; | 23 import '../types/types.dart' show TypesInferrer; |
| 24 import '../universe/call_structure.dart' show CallStructure; | 24 import '../universe/call_structure.dart' show CallStructure; |
| 25 import '../universe/selector.dart' show Selector; | 25 import '../universe/selector.dart' show Selector; |
| 26 import '../universe/side_effects.dart' show SideEffects; | 26 import '../universe/side_effects.dart' show SideEffects; |
| 27 import '../util/util.dart' show Setlet; | 27 import '../util/util.dart' show Setlet; |
| 28 import '../world.dart' show ClosedWorld; | 28 import '../world.dart' show ClosedWorld, ClosedWorldRefiner; |
| 29 import 'closure_tracer.dart'; | 29 import 'closure_tracer.dart'; |
| 30 import 'debug.dart' as debug; | 30 import 'debug.dart' as debug; |
| 31 import 'inferrer_visitor.dart' show ArgumentsTypes, TypeSystem; | 31 import 'inferrer_visitor.dart' show ArgumentsTypes, TypeSystem; |
| 32 import 'list_tracer.dart'; | 32 import 'list_tracer.dart'; |
| 33 import 'map_tracer.dart'; | 33 import 'map_tracer.dart'; |
| 34 import 'simple_types_inferrer.dart'; | 34 import 'simple_types_inferrer.dart'; |
| 35 import 'type_graph_dump.dart'; | 35 import 'type_graph_dump.dart'; |
| 36 import 'type_graph_nodes.dart'; | 36 import 'type_graph_nodes.dart'; |
| 37 | 37 |
| 38 class TypeInformationSystem extends TypeSystem<TypeInformation> { | 38 class TypeInformationSystem extends TypeSystem<TypeInformation> { |
| 39 final Compiler compiler; | |
| 40 final ClosedWorld closedWorld; | 39 final ClosedWorld closedWorld; |
| 41 final CommonMasks commonMasks; | |
| 42 | 40 |
| 43 /// [ElementTypeInformation]s for elements. | 41 /// [ElementTypeInformation]s for elements. |
| 44 final Map<Element, TypeInformation> typeInformations = | 42 final Map<Element, TypeInformation> typeInformations = |
| 45 new Map<Element, TypeInformation>(); | 43 new Map<Element, TypeInformation>(); |
| 46 | 44 |
| 47 /// [ListTypeInformation] for allocated lists. | 45 /// [ListTypeInformation] for allocated lists. |
| 48 final Map<ast.Node, TypeInformation> allocatedLists = | 46 final Map<ast.Node, TypeInformation> allocatedLists = |
| 49 new Map<ast.Node, TypeInformation>(); | 47 new Map<ast.Node, TypeInformation>(); |
| 50 | 48 |
| 51 /// [MapTypeInformation] for allocated Maps. | 49 /// [MapTypeInformation] for allocated Maps. |
| (...skipping 13 matching lines...) Expand all Loading... |
| 65 | 63 |
| 66 Iterable<TypeInformation> get allTypes => [ | 64 Iterable<TypeInformation> get allTypes => [ |
| 67 typeInformations.values, | 65 typeInformations.values, |
| 68 allocatedLists.values, | 66 allocatedLists.values, |
| 69 allocatedMaps.values, | 67 allocatedMaps.values, |
| 70 allocatedClosures, | 68 allocatedClosures, |
| 71 concreteTypes.values, | 69 concreteTypes.values, |
| 72 allocatedTypes | 70 allocatedTypes |
| 73 ].expand((x) => x); | 71 ].expand((x) => x); |
| 74 | 72 |
| 75 TypeInformationSystem(Compiler compiler, this.commonMasks) | 73 TypeInformationSystem(this.closedWorld) { |
| 76 : this.compiler = compiler, | 74 nonNullEmptyType = getConcreteTypeFor(commonMasks.emptyType); |
| 77 this.closedWorld = compiler.closedWorld { | |
| 78 nonNullEmptyType = getConcreteTypeFor(const TypeMask.nonNullEmpty()); | |
| 79 } | 75 } |
| 80 | 76 |
| 77 CommonMasks get commonMasks => closedWorld.commonMasks; |
| 78 |
| 81 /// Used to group [TypeInformation] nodes by the element that triggered their | 79 /// Used to group [TypeInformation] nodes by the element that triggered their |
| 82 /// creation. | 80 /// creation. |
| 83 MemberTypeInformation _currentMember = null; | 81 MemberTypeInformation _currentMember = null; |
| 84 MemberTypeInformation get currentMember => _currentMember; | 82 MemberTypeInformation get currentMember => _currentMember; |
| 85 | 83 |
| 86 void withMember(MemberElement element, action) { | 84 void withMember(MemberElement element, action) { |
| 87 assert(invariant(element, _currentMember == null, | 85 assert(invariant(element, _currentMember == null, |
| 88 message: "Already constructing graph for $_currentMember.")); | 86 message: "Already constructing graph for $_currentMember.")); |
| 89 _currentMember = getInferredTypeOf(element); | 87 _currentMember = getInferredTypeOf(element); |
| 90 action(); | 88 action(); |
| (...skipping 267 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 358 return nonNullEmptyType; | 356 return nonNullEmptyType; |
| 359 } | 357 } |
| 360 | 358 |
| 361 bool isNull(TypeInformation type) { | 359 bool isNull(TypeInformation type) { |
| 362 return type == nullType; | 360 return type == nullType; |
| 363 } | 361 } |
| 364 | 362 |
| 365 TypeInformation allocateList( | 363 TypeInformation allocateList( |
| 366 TypeInformation type, ast.Node node, Element enclosing, | 364 TypeInformation type, ast.Node node, Element enclosing, |
| 367 [TypeInformation elementType, int length]) { | 365 [TypeInformation elementType, int length]) { |
| 368 ClassElement typedDataClass = compiler.commonElements.typedDataClass; | 366 ClassElement typedDataClass = closedWorld.commonElements.typedDataClass; |
| 369 bool isTypedArray = typedDataClass != null && | 367 bool isTypedArray = typedDataClass != null && |
| 370 closedWorld.isInstantiated(typedDataClass) && | 368 closedWorld.isInstantiated(typedDataClass) && |
| 371 type.type.satisfies(typedDataClass, closedWorld); | 369 type.type.satisfies(typedDataClass, closedWorld); |
| 372 bool isConst = (type.type == commonMasks.constListType); | 370 bool isConst = (type.type == commonMasks.constListType); |
| 373 bool isFixed = | 371 bool isFixed = |
| 374 (type.type == commonMasks.fixedListType) || isConst || isTypedArray; | 372 (type.type == commonMasks.fixedListType) || isConst || isTypedArray; |
| 375 bool isElementInferred = isConst || isTypedArray; | 373 bool isElementInferred = isConst || isTypedArray; |
| 376 | 374 |
| 377 int inferredLength = isFixed ? length : null; | 375 int inferredLength = isFixed ? length : null; |
| 378 TypeMask elementTypeMask = | 376 TypeMask elementTypeMask = |
| (...skipping 183 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 562 * | 560 * |
| 563 */ | 561 */ |
| 564 class TypeGraphInferrerEngine | 562 class TypeGraphInferrerEngine |
| 565 extends InferrerEngine<TypeInformation, TypeInformationSystem> { | 563 extends InferrerEngine<TypeInformation, TypeInformationSystem> { |
| 566 final Map<Element, TypeInformation> defaultTypeOfParameter = | 564 final Map<Element, TypeInformation> defaultTypeOfParameter = |
| 567 new Map<Element, TypeInformation>(); | 565 new Map<Element, TypeInformation>(); |
| 568 final List<CallSiteTypeInformation> allocatedCalls = | 566 final List<CallSiteTypeInformation> allocatedCalls = |
| 569 <CallSiteTypeInformation>[]; | 567 <CallSiteTypeInformation>[]; |
| 570 final WorkQueue workQueue = new WorkQueue(); | 568 final WorkQueue workQueue = new WorkQueue(); |
| 571 final Element mainElement; | 569 final Element mainElement; |
| 572 final CommonMasks commonMasks; | |
| 573 final Set<Element> analyzedElements = new Set<Element>(); | 570 final Set<Element> analyzedElements = new Set<Element>(); |
| 574 | 571 |
| 575 /// The maximum number of times we allow a node in the graph to | 572 /// The maximum number of times we allow a node in the graph to |
| 576 /// change types. If a node reaches that limit, we give up | 573 /// change types. If a node reaches that limit, we give up |
| 577 /// inferencing on it and give it the dynamic type. | 574 /// inferencing on it and give it the dynamic type. |
| 578 final int MAX_CHANGE_COUNT = 6; | 575 final int MAX_CHANGE_COUNT = 6; |
| 579 | 576 |
| 580 int overallRefineCount = 0; | 577 int overallRefineCount = 0; |
| 581 int addedInGraph = 0; | 578 int addedInGraph = 0; |
| 582 | 579 |
| 583 TypeGraphInferrerEngine( | 580 TypeGraphInferrerEngine(Compiler compiler, ClosedWorld closedWorld, |
| 584 Compiler compiler, CommonMasks commonMasks, this.mainElement) | 581 ClosedWorldRefiner closedWorldRefiner, this.mainElement) |
| 585 : commonMasks = commonMasks, | 582 : super(compiler, closedWorld, closedWorldRefiner, |
| 586 super(compiler, new TypeInformationSystem(compiler, commonMasks)); | 583 new TypeInformationSystem(closedWorld)); |
| 587 | 584 |
| 588 JavaScriptBackend get backend => compiler.backend; | 585 JavaScriptBackend get backend => compiler.backend; |
| 589 Annotations get annotations => backend.annotations; | 586 Annotations get annotations => backend.annotations; |
| 590 DiagnosticReporter get reporter => compiler.reporter; | 587 DiagnosticReporter get reporter => compiler.reporter; |
| 588 CommonMasks get commonMasks => closedWorld.commonMasks; |
| 591 | 589 |
| 592 /** | 590 /** |
| 593 * A set of selector names that [List] implements, that we know return | 591 * A set of selector names that [List] implements, that we know return |
| 594 * their element type. | 592 * their element type. |
| 595 */ | 593 */ |
| 596 final Set<Selector> returnsListElementTypeSet = | 594 final Set<Selector> returnsListElementTypeSet = |
| 597 new Set<Selector>.from(<Selector>[ | 595 new Set<Selector>.from(<Selector>[ |
| 598 new Selector.getter(const PublicName('first')), | 596 new Selector.getter(const PublicName('first')), |
| 599 new Selector.getter(const PublicName('last')), | 597 new Selector.getter(const PublicName('last')), |
| 600 new Selector.getter(const PublicName('single')), | 598 new Selector.getter(const PublicName('single')), |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 696 | 694 |
| 697 Set<FunctionElement> bailedOutOn = new Set<FunctionElement>(); | 695 Set<FunctionElement> bailedOutOn = new Set<FunctionElement>(); |
| 698 | 696 |
| 699 // Trace closures to potentially infer argument types. | 697 // Trace closures to potentially infer argument types. |
| 700 types.allocatedClosures.forEach((info) { | 698 types.allocatedClosures.forEach((info) { |
| 701 void trace( | 699 void trace( |
| 702 Iterable<FunctionElement> elements, ClosureTracerVisitor tracer) { | 700 Iterable<FunctionElement> elements, ClosureTracerVisitor tracer) { |
| 703 tracer.run(); | 701 tracer.run(); |
| 704 if (!tracer.continueAnalyzing) { | 702 if (!tracer.continueAnalyzing) { |
| 705 elements.forEach((FunctionElement e) { | 703 elements.forEach((FunctionElement e) { |
| 706 compiler.inferenceWorld.registerMightBePassedToApply(e); | 704 closedWorldRefiner.registerMightBePassedToApply(e); |
| 707 if (debug.VERBOSE) print("traced closure $e as ${true} (bail)"); | 705 if (debug.VERBOSE) print("traced closure $e as ${true} (bail)"); |
| 708 e.functionSignature.forEachParameter((parameter) { | 706 e.functionSignature.forEachParameter((parameter) { |
| 709 types | 707 types |
| 710 .getInferredTypeOf(parameter) | 708 .getInferredTypeOf(parameter) |
| 711 .giveUp(this, clearAssignments: false); | 709 .giveUp(this, clearAssignments: false); |
| 712 }); | 710 }); |
| 713 }); | 711 }); |
| 714 bailedOutOn.addAll(elements); | 712 bailedOutOn.addAll(elements); |
| 715 return; | 713 return; |
| 716 } | 714 } |
| 717 elements | 715 elements |
| 718 .where((e) => !bailedOutOn.contains(e)) | 716 .where((e) => !bailedOutOn.contains(e)) |
| 719 .forEach((FunctionElement e) { | 717 .forEach((FunctionElement e) { |
| 720 e.functionSignature.forEachParameter((parameter) { | 718 e.functionSignature.forEachParameter((parameter) { |
| 721 var info = types.getInferredTypeOf(parameter); | 719 var info = types.getInferredTypeOf(parameter); |
| 722 info.maybeResume(); | 720 info.maybeResume(); |
| 723 workQueue.add(info); | 721 workQueue.add(info); |
| 724 }); | 722 }); |
| 725 if (tracer.tracedType.mightBePassedToFunctionApply) { | 723 if (tracer.tracedType.mightBePassedToFunctionApply) { |
| 726 compiler.inferenceWorld.registerMightBePassedToApply(e); | 724 closedWorldRefiner.registerMightBePassedToApply(e); |
| 727 } | 725 } |
| 728 if (debug.VERBOSE) { | 726 if (debug.VERBOSE) { |
| 729 print("traced closure $e as " | 727 print("traced closure $e as " |
| 730 "${compiler.inferenceWorld | 728 "${closedWorldRefiner |
| 731 .getCurrentlyKnownMightBePassedToApply(e)}"); | 729 .getCurrentlyKnownMightBePassedToApply(e)}"); |
| 732 } | 730 } |
| 733 }); | 731 }); |
| 734 } | 732 } |
| 735 | 733 |
| 736 if (info is ClosureTypeInformation) { | 734 if (info is ClosureTypeInformation) { |
| 737 Iterable<FunctionElement> elements = [info.element]; | 735 Iterable<FunctionElement> elements = [info.element]; |
| 738 trace(elements, new ClosureTracerVisitor(elements, info, this)); | 736 trace(elements, new ClosureTracerVisitor(elements, info, this)); |
| 739 } else if (info is CallSiteTypeInformation) { | 737 } else if (info is CallSiteTypeInformation) { |
| 740 if (info is StaticCallSiteTypeInformation && | 738 if (info is StaticCallSiteTypeInformation && |
| (...skipping 166 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 907 } | 905 } |
| 908 } else { | 906 } else { |
| 909 recordReturnType(element, type); | 907 recordReturnType(element, type); |
| 910 } | 908 } |
| 911 } | 909 } |
| 912 | 910 |
| 913 void processLoopInformation() { | 911 void processLoopInformation() { |
| 914 allocatedCalls.forEach((info) { | 912 allocatedCalls.forEach((info) { |
| 915 if (!info.inLoop) return; | 913 if (!info.inLoop) return; |
| 916 if (info is StaticCallSiteTypeInformation) { | 914 if (info is StaticCallSiteTypeInformation) { |
| 917 compiler.inferenceWorld.addFunctionCalledInLoop(info.calledElement); | 915 closedWorldRefiner.addFunctionCalledInLoop(info.calledElement); |
| 918 } else if (info.mask != null && !info.mask.containsAll(closedWorld)) { | 916 } else if (info.mask != null && !info.mask.containsAll(closedWorld)) { |
| 919 // For instance methods, we only register a selector called in a | 917 // For instance methods, we only register a selector called in a |
| 920 // loop if it is a typed selector, to avoid marking too many | 918 // loop if it is a typed selector, to avoid marking too many |
| 921 // methods as being called from within a loop. This cuts down | 919 // methods as being called from within a loop. This cuts down |
| 922 // on the code bloat. | 920 // on the code bloat. |
| 923 info.targets.forEach(compiler.inferenceWorld.addFunctionCalledInLoop); | 921 info.targets.forEach(closedWorldRefiner.addFunctionCalledInLoop); |
| 924 } | 922 } |
| 925 }); | 923 }); |
| 926 } | 924 } |
| 927 | 925 |
| 928 void refine() { | 926 void refine() { |
| 929 while (!workQueue.isEmpty) { | 927 while (!workQueue.isEmpty) { |
| 930 if (compiler.shouldPrintProgress) { | 928 if (compiler.shouldPrintProgress) { |
| 931 reporter.log('Inferred $overallRefineCount types.'); | 929 reporter.log('Inferred $overallRefineCount types.'); |
| 932 compiler.progress.reset(); | 930 compiler.progress.reset(); |
| 933 } | 931 } |
| (...skipping 413 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1347 } | 1345 } |
| 1348 | 1346 |
| 1349 void recordCapturedLocalRead(Local local) {} | 1347 void recordCapturedLocalRead(Local local) {} |
| 1350 | 1348 |
| 1351 void recordLocalUpdate(Local local, TypeInformation type) {} | 1349 void recordLocalUpdate(Local local, TypeInformation type) {} |
| 1352 } | 1350 } |
| 1353 | 1351 |
| 1354 class TypeGraphInferrer implements TypesInferrer { | 1352 class TypeGraphInferrer implements TypesInferrer { |
| 1355 TypeGraphInferrerEngine inferrer; | 1353 TypeGraphInferrerEngine inferrer; |
| 1356 final Compiler compiler; | 1354 final Compiler compiler; |
| 1357 final CommonMasks commonMasks; | 1355 final ClosedWorld closedWorld; |
| 1358 TypeGraphInferrer(this.compiler, this.commonMasks); | 1356 final ClosedWorldRefiner closedWorldRefiner; |
| 1357 |
| 1358 TypeGraphInferrer(this.compiler, this.closedWorld, this.closedWorldRefiner); |
| 1359 | 1359 |
| 1360 String get name => 'Graph inferrer'; | 1360 String get name => 'Graph inferrer'; |
| 1361 |
| 1362 CommonMasks get commonMasks => closedWorld.commonMasks; |
| 1363 |
| 1361 TypeMask get _dynamicType => commonMasks.dynamicType; | 1364 TypeMask get _dynamicType => commonMasks.dynamicType; |
| 1362 | 1365 |
| 1363 void analyzeMain(Element main) { | 1366 void analyzeMain(Element main) { |
| 1364 inferrer = new TypeGraphInferrerEngine(compiler, commonMasks, main); | 1367 inferrer = new TypeGraphInferrerEngine( |
| 1368 compiler, closedWorld, closedWorldRefiner, main); |
| 1365 inferrer.runOverAllElements(); | 1369 inferrer.runOverAllElements(); |
| 1366 } | 1370 } |
| 1367 | 1371 |
| 1368 TypeMask getReturnTypeOfElement(Element element) { | 1372 TypeMask getReturnTypeOfElement(Element element) { |
| 1369 if (compiler.disableTypeInference) return _dynamicType; | 1373 if (compiler.disableTypeInference) return _dynamicType; |
| 1370 // Currently, closure calls return dynamic. | 1374 // Currently, closure calls return dynamic. |
| 1371 if (element is! FunctionElement) return _dynamicType; | 1375 if (element is! FunctionElement) return _dynamicType; |
| 1372 return inferrer.types.getInferredTypeOf(element).type; | 1376 return inferrer.types.getInferredTypeOf(element).type; |
| 1373 } | 1377 } |
| 1374 | 1378 |
| (...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1432 bool isCalledOnce(Element element) { | 1436 bool isCalledOnce(Element element) { |
| 1433 if (compiler.disableTypeInference) return false; | 1437 if (compiler.disableTypeInference) return false; |
| 1434 MemberTypeInformation info = inferrer.types.getInferredTypeOf(element); | 1438 MemberTypeInformation info = inferrer.types.getInferredTypeOf(element); |
| 1435 return info.isCalledOnce(); | 1439 return info.isCalledOnce(); |
| 1436 } | 1440 } |
| 1437 | 1441 |
| 1438 void clear() { | 1442 void clear() { |
| 1439 inferrer.clear(); | 1443 inferrer.clear(); |
| 1440 } | 1444 } |
| 1441 } | 1445 } |
| OLD | NEW |