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 |