-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
inferrer_engine.dart
1654 lines (1484 loc) · 57.3 KB
/
inferrer_engine.dart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
import 'package:kernel/ast.dart' as ir;
import '../../compiler_new.dart';
import '../closure.dart';
import '../common.dart';
import '../common/names.dart';
import '../compiler.dart';
import '../common_elements.dart';
import '../constants/values.dart';
import '../elements/entities.dart';
import '../elements/names.dart';
import '../elements/types.dart';
import '../js_backend/inferred_data.dart';
import '../js_backend/no_such_method_registry.dart';
import '../js_model/element_map.dart';
import '../js_model/js_world.dart';
import '../js_model/locals.dart';
import '../native/behavior.dart';
import '../options.dart';
import '../serialization/serialization.dart';
import '../universe/call_structure.dart';
import '../universe/selector.dart';
import '../universe/side_effects.dart';
import '../world.dart';
import 'abstract_value_domain.dart';
import 'builder_kernel.dart';
import 'closure_tracer.dart';
import 'debug.dart' as debug;
import 'locals_handler.dart';
import 'list_tracer.dart';
import 'map_tracer.dart';
import 'set_tracer.dart';
import 'type_graph_dump.dart';
import 'type_graph_inferrer.dart';
import 'type_graph_nodes.dart';
import 'type_system.dart';
import 'types.dart';
/// An inferencing engine that computes a call graph of [TypeInformation] nodes
/// by visiting the AST of the application, and then does the inferencing on the
/// graph.
abstract class InferrerEngine {
/// A set of selector names that [List] implements, that we know return their
/// element type.
final Set<Selector> returnsListElementTypeSet =
new Set<Selector>.from(<Selector>[
new Selector.getter(const PublicName('first')),
new Selector.getter(const PublicName('last')),
new Selector.getter(const PublicName('single')),
new Selector.call(const PublicName('singleWhere'), CallStructure.ONE_ARG),
new Selector.call(const PublicName('elementAt'), CallStructure.ONE_ARG),
new Selector.index(),
new Selector.call(const PublicName('removeAt'), CallStructure.ONE_ARG),
new Selector.call(const PublicName('removeLast'), CallStructure.NO_ARGS)
]);
CompilerOptions get options;
/// The [JClosedWorld] on which inference reasoning is based.
JClosedWorld get closedWorld;
DiagnosticReporter get reporter;
AbstractValueDomain get abstractValueDomain =>
closedWorld.abstractValueDomain;
CommonElements get commonElements => closedWorld.commonElements;
// TODO(johnniwinther): This should be part of [ClosedWorld] or
// [ClosureWorldRefiner].
NoSuchMethodData get noSuchMethodData => closedWorld.noSuchMethodData;
TypeSystem get types;
Map<ir.TreeNode, TypeInformation> get concreteTypes;
InferredDataBuilder get inferredDataBuilder;
FunctionEntity get mainElement;
void runOverAllElements();
void analyze(MemberEntity member);
void analyzeListAndEnqueue(ListTypeInformation info);
void analyzeSetAndEnqueue(SetTypeInformation info);
void analyzeMapAndEnqueue(MapTypeInformation info);
/// Notifies to the inferrer that [analyzedElement] can have return type
/// [newType]. [currentType] is the type the inference has currently found.
///
/// Returns the new type for [analyzedElement].
TypeInformation addReturnTypeForMethod(
FunctionEntity element, TypeInformation unused, TypeInformation newType);
/// Applies [f] to all elements in the universe that match [selector] and
/// [mask]. If [f] returns false, aborts the iteration.
void forEachElementMatching(
Selector selector, AbstractValue mask, bool f(MemberEntity element));
/// Returns the [TypeInformation] node for the default value of a parameter.
/// If this is queried before it is set by [setDefaultTypeOfParameter], a
/// [PlaceholderTypeInformation] is returned, which will later be replaced
/// by the actual node when [setDefaultTypeOfParameter] is called.
///
/// Invariant: After graph construction, no [PlaceholderTypeInformation] nodes
/// should be present and a default type for each parameter should exist.
TypeInformation getDefaultTypeOfParameter(Local parameter);
/// This helper breaks abstractions but is currently required to work around
/// the wrong modeling of default values of optional parameters of
/// synthetic constructors.
///
/// TODO(johnniwinther): Remove once default values of synthetic parameters
/// are fixed.
bool hasAlreadyComputedTypeOfParameterDefault(Local parameter);
/// Sets the type of a parameter's default value to [type]. If the global
/// mapping in [defaultTypeOfParameter] already contains a type, it must be
/// a [PlaceholderTypeInformation], which will be replaced. All its uses are
/// updated.
void setDefaultTypeOfParameter(Local parameter, TypeInformation type,
{bool isInstanceMember});
Iterable<MemberEntity> getCallersOfForTesting(MemberEntity element);
// TODO(johnniwinther): Make this private again.
GlobalTypeInferenceElementData dataOfMember(MemberEntity element);
bool checkIfExposesThis(ConstructorEntity element);
void recordExposesThis(ConstructorEntity element, bool exposesThis);
/// Records that the return type [element] is of type [type].
void recordReturnType(FunctionEntity element, TypeInformation type);
/// Records that [element] is of type [type].
void recordTypeOfField(FieldEntity element, TypeInformation type);
/// Registers a call to await with an expression of type [argumentType] as
/// argument.
TypeInformation registerAwait(ir.Node node, TypeInformation argument);
/// Registers a call to yield with an expression of type [argumentType] as
/// argument.
TypeInformation registerYield(ir.Node node, TypeInformation argument);
/// Registers that [caller] calls [closure] with [arguments].
///
/// [sideEffectsBuilder] will be updated to incorporate the potential callees'
/// side effects.
///
/// [inLoop] tells whether the call happens in a loop.
TypeInformation registerCalledClosure(
ir.Node node,
Selector selector,
AbstractValue mask,
TypeInformation closure,
MemberEntity caller,
ArgumentsTypes arguments,
SideEffectsBuilder sideEffectsBuilder,
{bool inLoop});
/// Registers that [caller] calls [callee] at location [node], with
/// [selector], and [arguments]. Note that [selector] is null for forwarding
/// constructors.
///
/// [sideEffectsBuilder] will be updated to incorporate [callee]'s side
/// effects.
///
/// [inLoop] tells whether the call happens in a loop.
TypeInformation registerCalledMember(
Object node,
Selector selector,
AbstractValue mask,
MemberEntity caller,
MemberEntity callee,
ArgumentsTypes arguments,
SideEffectsBuilder sideEffectsBuilder,
bool inLoop);
/// Registers that [caller] calls [selector] with [receiverType] as receiver,
/// and [arguments].
///
/// [sideEffectsBuilder] will be updated to incorporate the potential callees'
/// side effects.
///
/// [inLoop] tells whether the call happens in a loop.
TypeInformation registerCalledSelector(
CallType callType,
ir.Node node,
Selector selector,
AbstractValue mask,
TypeInformation receiverType,
MemberEntity caller,
ArgumentsTypes arguments,
SideEffectsBuilder sideEffectsBuilder,
{bool inLoop,
bool isConditional});
/// Update the assignments to parameters in the graph. [remove] tells whether
/// assignments must be added or removed. If [init] is false, parameters are
/// added to the work queue.
void updateParameterAssignments(TypeInformation caller, MemberEntity callee,
ArgumentsTypes arguments, Selector selector, AbstractValue mask,
{bool remove, bool addToQueue: true});
void updateSelectorInMember(MemberEntity owner, CallType callType,
ir.Node node, Selector selector, AbstractValue mask);
/// Returns the return type of [element].
TypeInformation returnTypeOfMember(MemberEntity element);
/// Returns the type of [element] when being called with [selector].
TypeInformation typeOfMemberWithSelector(
MemberEntity element, Selector selector);
/// Returns the type of [element].
TypeInformation typeOfMember(MemberEntity element);
/// Returns the type of [element].
TypeInformation typeOfParameter(Local element);
/// Returns the type for [nativeBehavior]. See documentation on
/// [NativeBehavior].
TypeInformation typeOfNativeBehavior(NativeBehavior nativeBehavior);
/// For a given selector, return a shared dynamic call site that will be used
/// to combine the results of multiple dynamic calls in the program via
/// [IndirectDynamicCallSiteTypeInformation].
///
/// This is used only for scalability reasons: if there are too many targets
/// and call sites, we may have a quadratic number of edges in the graph, so
/// we add a level of indirection to merge the information and keep the graph
/// smaller.
DynamicCallSiteTypeInformation typeOfSharedDynamicCall(
Selector selector, CallStructure structure);
bool returnsListElementType(Selector selector, AbstractValue mask);
bool returnsMapValueType(Selector selector, AbstractValue mask);
void close();
void clear();
/// Returns true if global optimizations such as type inferencing can apply to
/// the field [element].
///
/// One category of elements that do not apply is runtime helpers that the
/// backend calls, but the optimizations don't see those calls.
bool canFieldBeUsedForGlobalOptimizations(FieldEntity element);
/// Returns true if global optimizations such as type inferencing can apply to
/// the parameter [element].
///
/// One category of elements that do not apply is runtime helpers that the
/// backend calls, but the optimizations don't see those calls.
bool canFunctionParametersBeUsedForGlobalOptimizations(
FunctionEntity function);
/// Returns `true` if inference of parameter types is disabled for [member].
bool assumeDynamic(MemberEntity member);
}
class InferrerEngineImpl extends InferrerEngine {
final Map<Local, TypeInformation> defaultTypeOfParameter =
new Map<Local, TypeInformation>();
final WorkQueue workQueue = new WorkQueue();
@override
final FunctionEntity mainElement;
final Set<MemberEntity> analyzedElements = new Set<MemberEntity>();
/// The maximum number of times we allow a node in the graph to
/// change types. If a node reaches that limit, we give up
/// inferencing on it and give it the dynamic type.
final int MAX_CHANGE_COUNT = 6;
int overallRefineCount = 0;
int addedInGraph = 0;
@override
final CompilerOptions options;
final Progress progress;
@override
final DiagnosticReporter reporter;
final CompilerOutput _compilerOutput;
@override
final JsClosedWorld closedWorld;
@override
final InferredDataBuilder inferredDataBuilder;
@override
final TypeSystem types;
@override
final Map<ir.TreeNode, TypeInformation> concreteTypes =
new Map<ir.TreeNode, TypeInformation>();
final Set<ConstructorEntity> generativeConstructorsExposingThis =
new Set<ConstructorEntity>();
/// Data computed internally within elements, like the type-mask of a send a
/// list allocation, or a for-in loop.
final Map<MemberEntity, GlobalTypeInferenceElementData> _memberData =
new Map<MemberEntity, GlobalTypeInferenceElementData>();
final NoSuchMethodRegistry noSuchMethodRegistry;
InferrerEngineImpl(
this.options,
this.progress,
this.reporter,
this._compilerOutput,
this.closedWorld,
this.noSuchMethodRegistry,
this.mainElement,
this.inferredDataBuilder)
: this.types = new TypeSystem(
closedWorld, new KernelTypeSystemStrategy(closedWorld));
ElementEnvironment get _elementEnvironment => closedWorld.elementEnvironment;
@override
void forEachElementMatching(
Selector selector, AbstractValue mask, bool f(MemberEntity element)) {
Iterable<MemberEntity> elements = closedWorld.locateMembers(selector, mask);
for (MemberEntity e in elements) {
if (!f(e)) return;
}
}
// TODO(johnniwinther): Make this private again.
@override
GlobalTypeInferenceElementData dataOfMember(MemberEntity element) =>
_memberData[element] ??= new KernelGlobalTypeInferenceElementData();
/// Update [sideEffects] with the side effects of [callee] being
/// called with [selector].
void updateSideEffects(SideEffectsBuilder sideEffectsBuilder,
Selector selector, MemberEntity callee) {
if (callee.isField) {
if (callee.isInstanceMember) {
if (selector.isSetter) {
sideEffectsBuilder.setChangesInstanceProperty();
} else if (selector.isGetter) {
sideEffectsBuilder.setDependsOnInstancePropertyStore();
} else {
sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
}
} else {
if (selector.isSetter) {
sideEffectsBuilder.setChangesStaticProperty();
} else if (selector.isGetter) {
sideEffectsBuilder.setDependsOnStaticPropertyStore();
} else {
sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
}
}
} else if (callee.isGetter && !selector.isGetter) {
sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
} else {
sideEffectsBuilder
.addInput(inferredDataBuilder.getSideEffectsBuilder(callee));
}
}
@override
TypeInformation typeOfNativeBehavior(NativeBehavior nativeBehavior) {
if (nativeBehavior == null) return types.dynamicType;
List typesReturned = nativeBehavior.typesReturned;
if (typesReturned.isEmpty) return types.dynamicType;
TypeInformation returnType;
for (var type in typesReturned) {
TypeInformation mappedType;
if (type == SpecialType.JsObject) {
mappedType = types.nonNullExact(commonElements.objectClass);
} else if (type == commonElements.stringType) {
mappedType = types.stringType;
} else if (type == commonElements.intType) {
mappedType = types.intType;
} else if (type == commonElements.numType ||
type == commonElements.doubleType) {
// Note: the backend double class is specifically for non-integer
// doubles, and a native behavior returning 'double' does not guarantee
// a non-integer return type, so we return the number type for those.
mappedType = types.numType;
} else if (type == commonElements.boolType) {
mappedType = types.boolType;
} else if (type == commonElements.nullType) {
mappedType = types.nullType;
} else if (type.isVoid) {
mappedType = types.nullType;
} else if (type.isDynamic) {
return types.dynamicType;
} else if (type.isInterfaceType) {
mappedType = types.nonNullSubtype(type.element);
} else {
mappedType = types.dynamicType;
}
returnType = types.computeLUB(returnType, mappedType);
if (returnType == types.dynamicType) {
break;
}
}
return returnType;
}
@override
void updateSelectorInMember(MemberEntity owner, CallType callType,
ir.Node node, Selector selector, AbstractValue mask) {
KernelGlobalTypeInferenceElementData data = dataOfMember(owner);
assert(validCallType(callType, node, selector));
switch (callType) {
case CallType.access:
data.setTypeMask(node, mask);
break;
case CallType.indirectAccess:
// indirect access is not diretly recorded in the result data.
break;
case CallType.forIn:
if (selector == Selectors.iterator) {
data.setIteratorTypeMask(node, mask);
} else if (selector == Selectors.current) {
data.setCurrentTypeMask(node, mask);
} else {
assert(selector == Selectors.moveNext);
data.setMoveNextTypeMask(node, mask);
}
break;
}
}
@override
bool checkIfExposesThis(ConstructorEntity element) {
return generativeConstructorsExposingThis.contains(element);
}
@override
void recordExposesThis(ConstructorEntity element, bool exposesThis) {
if (exposesThis) {
generativeConstructorsExposingThis.add(element);
}
}
@override
bool returnsListElementType(Selector selector, AbstractValue mask) {
return mask != null &&
abstractValueDomain.isContainer(mask) &&
returnsListElementTypeSet.contains(selector);
}
@override
bool returnsMapValueType(Selector selector, AbstractValue mask) {
return mask != null && abstractValueDomain.isMap(mask) && selector.isIndex;
}
@override
void analyzeListAndEnqueue(ListTypeInformation info) {
if (info.analyzed) return;
info.analyzed = true;
ListTracerVisitor tracer = new ListTracerVisitor(info, this);
bool succeeded = tracer.run();
if (!succeeded) return;
info.bailedOut = false;
info.elementType.inferred = true;
if (abstractValueDomain.isSpecializationOf(
info.originalType, abstractValueDomain.fixedListType)) {
info.checksGrowable = tracer.callsGrowableMethod;
}
tracer.assignments.forEach(info.elementType.addAssignment);
// Enqueue the list for later refinement
workQueue.add(info);
workQueue.add(info.elementType);
}
@override
void analyzeSetAndEnqueue(SetTypeInformation info) {
if (info.analyzed) return;
info.analyzed = true;
SetTracerVisitor tracer = new SetTracerVisitor(info, this);
bool succeeded = tracer.run();
if (!succeeded) return;
info.bailedOut = false;
info.elementType.inferred = true;
tracer.assignments.forEach(info.elementType.addAssignment);
// Enqueue the set for later refinement.
workQueue.add(info);
workQueue.add(info.elementType);
}
@override
void analyzeMapAndEnqueue(MapTypeInformation info) {
if (info.analyzed) return;
info.analyzed = true;
MapTracerVisitor tracer = new MapTracerVisitor(info, this);
bool succeeded = tracer.run();
if (!succeeded) return;
info.bailedOut = false;
for (int i = 0; i < tracer.keyAssignments.length; ++i) {
TypeInformation newType = info.addEntryAssignment(abstractValueDomain,
tracer.keyAssignments[i], tracer.valueAssignments[i]);
if (newType != null) workQueue.add(newType);
}
for (TypeInformation map in tracer.mapAssignments) {
workQueue.addAll(info.addMapAssignment(abstractValueDomain, map));
}
info.markAsInferred();
workQueue.add(info.keyType);
workQueue.add(info.valueType);
workQueue.addAll(info.typeInfoMap.values);
workQueue.add(info);
}
@override
void runOverAllElements() {
analyzeAllElements();
TypeGraphDump dump =
debug.PRINT_GRAPH ? new TypeGraphDump(_compilerOutput, this) : null;
dump?.beforeAnalysis();
buildWorkQueue();
refine();
// Try to infer element types of lists and compute their escape information.
types.allocatedLists.values.forEach((TypeInformation info) {
analyzeListAndEnqueue(info);
});
// Try to infer element types of sets and compute their escape information.
types.allocatedSets.values.forEach((TypeInformation info) {
analyzeSetAndEnqueue(info);
});
// Try to infer the key and value types for maps and compute the values'
// escape information.
types.allocatedMaps.values.forEach((TypeInformation info) {
analyzeMapAndEnqueue(info);
});
Set<FunctionEntity> bailedOutOn = new Set<FunctionEntity>();
// Trace closures to potentially infer argument types.
types.allocatedClosures.forEach((dynamic info) {
void trace(
Iterable<FunctionEntity> elements, ClosureTracerVisitor tracer) {
tracer.run();
if (!tracer.continueAnalyzing) {
elements.forEach((FunctionEntity element) {
inferredDataBuilder.registerMightBePassedToApply(element);
if (debug.VERBOSE) {
print("traced closure $element as ${true} (bail)");
}
types.strategy.forEachParameter(element, (Local parameter) {
types
.getInferredTypeOfParameter(parameter)
.giveUp(this, clearAssignments: false);
});
});
bailedOutOn.addAll(elements);
return;
}
elements
.where((e) => !bailedOutOn.contains(e))
.forEach((FunctionEntity element) {
types.strategy.forEachParameter(element, (Local parameter) {
ParameterTypeInformation info =
types.getInferredTypeOfParameter(parameter);
info.maybeResume();
workQueue.add(info);
});
if (tracer.tracedType.mightBePassedToFunctionApply) {
inferredDataBuilder.registerMightBePassedToApply(element);
}
if (debug.VERBOSE) {
print("traced closure $element as "
"${inferredDataBuilder.getCurrentlyKnownMightBePassedToApply(element)}");
}
});
}
if (info is ClosureTypeInformation) {
Iterable<FunctionEntity> elements = [info.closure];
trace(elements, new ClosureTracerVisitor(elements, info, this));
} else if (info is CallSiteTypeInformation) {
if (info is StaticCallSiteTypeInformation &&
info.selector != null &&
info.selector.isCall) {
// This is a constructor call to a class with a call method. So we
// need to trace the call method here.
FunctionEntity calledElement = info.calledElement;
assert(calledElement is ConstructorEntity &&
calledElement.isGenerativeConstructor);
ClassEntity cls = calledElement.enclosingClass;
FunctionEntity callMethod = lookupCallMethod(cls);
assert(callMethod != null, failedAt(cls));
Iterable<FunctionEntity> elements = [callMethod];
trace(elements, new ClosureTracerVisitor(elements, info, this));
} else {
// We only are interested in functions here, as other targets
// of this closure call are not a root to trace but an intermediate
// for some other function.
Iterable<FunctionEntity> elements = new List<FunctionEntity>.from(
info.callees.where((e) => e.isFunction));
trace(elements, new ClosureTracerVisitor(elements, info, this));
}
} else if (info is MemberTypeInformation) {
trace(<FunctionEntity>[info.member],
new StaticTearOffClosureTracerVisitor(info.member, info, this));
} else if (info is ParameterTypeInformation) {
failedAt(
NO_LOCATION_SPANNABLE, 'Unexpected closure allocation info $info');
}
});
dump?.beforeTracing();
// Reset all nodes that use lists/maps that have been inferred, as well
// as nodes that use elements fetched from these lists/maps. The
// workset for a new run of the analysis will be these nodes.
Set<TypeInformation> seenTypes = new Set<TypeInformation>();
while (!workQueue.isEmpty) {
TypeInformation info = workQueue.remove();
if (seenTypes.contains(info)) continue;
// If the node cannot be reset, we do not need to update its users either.
if (!info.reset(this)) continue;
seenTypes.add(info);
workQueue.addAll(info.users);
}
workQueue.addAll(seenTypes);
refine();
if (debug.PRINT_SUMMARY) {
types.allocatedLists.values.forEach((_info) {
ListTypeInformation info = _info;
print('${info.type} '
'for ${abstractValueDomain.getAllocationNode(info.originalType)} '
'at ${abstractValueDomain.getAllocationElement(info.originalType)}'
'after ${info.refineCount}');
});
types.allocatedSets.values.forEach((_info) {
SetTypeInformation info = _info;
print('${info.type} '
'for ${abstractValueDomain.getAllocationNode(info.originalType)} '
'at ${abstractValueDomain.getAllocationElement(info.originalType)} '
'after ${info.refineCount}');
});
types.allocatedMaps.values.forEach((_info) {
MapTypeInformation info = _info;
print('${info.type} '
'for ${abstractValueDomain.getAllocationNode(info.originalType)} '
'at ${abstractValueDomain.getAllocationElement(info.originalType)}'
'after ${info.refineCount}');
});
types.allocatedClosures.forEach((TypeInformation info) {
if (info is ElementTypeInformation) {
print('${info.getInferredSignature(types)} for '
'${info.debugName}');
} else if (info is ClosureTypeInformation) {
print('${info.getInferredSignature(types)} for '
'${info.debugName}');
} else if (info is DynamicCallSiteTypeInformation) {
if (info.hasClosureCallTargets) {
print('<Closure.call>');
}
for (MemberEntity target in info.concreteTargets) {
if (target is FunctionEntity) {
print('${types.getInferredSignatureOfMethod(target)} '
'for ${target}');
} else {
print('${types.getInferredTypeOfMember(target).type} '
'for ${target}');
}
}
} else if (info is StaticCallSiteTypeInformation) {
ClassEntity cls = info.calledElement.enclosingClass;
FunctionEntity callMethod = lookupCallMethod(cls);
print('${types.getInferredSignatureOfMethod(callMethod)} for ${cls}');
} else {
print('${info.type} for some unknown kind of closure');
}
});
analyzedElements.forEach((MemberEntity elem) {
TypeInformation type = types.getInferredTypeOfMember(elem);
print('${elem} :: ${type} from ${type.assignments} ');
});
}
dump?.afterAnalysis();
reporter.log('Inferred $overallRefineCount types.');
processLoopInformation();
}
/// Call [analyze] for all live members.
void analyzeAllElements() {
Iterable<MemberEntity> processedMembers = closedWorld.processedMembers
.where((MemberEntity member) => !member.isAbstract);
progress.startPhase();
processedMembers.forEach((MemberEntity member) {
progress.showProgress(
'Added ', addedInGraph, ' elements in inferencing graph.');
// This also forces the creation of the [ElementTypeInformation] to ensure
// it is in the graph.
types.withMember(member, () => analyze(member));
});
reporter.log('Added $addedInGraph elements in inferencing graph.');
}
/// Returns the body node for [member].
ir.Node computeMemberBody(MemberEntity member) {
MemberDefinition definition =
closedWorld.elementMap.getMemberDefinition(member);
switch (definition.kind) {
case MemberKind.regular:
ir.Member node = definition.node;
if (node is ir.Field) {
return getFieldInitializer(closedWorld.elementMap, member);
} else if (node is ir.Procedure) {
return node.function;
}
break;
case MemberKind.constructor:
return definition.node;
case MemberKind.constructorBody:
ir.Member node = definition.node;
if (node is ir.Constructor) {
return node.function;
} else if (node is ir.Procedure) {
return node.function;
}
break;
case MemberKind.closureCall:
ir.LocalFunction node = definition.node;
return node.function;
case MemberKind.closureField:
case MemberKind.signature:
case MemberKind.generatorBody:
break;
}
failedAt(member, 'Unexpected member definition: $definition.');
return null;
}
/// Returns the `call` method on [cls] or the `noSuchMethod` if [cls] doesn't
/// implement `call`.
FunctionEntity lookupCallMethod(ClassEntity cls) {
FunctionEntity function =
_elementEnvironment.lookupClassMember(cls, Identifiers.call);
if (function == null || function.isAbstract) {
function =
_elementEnvironment.lookupClassMember(cls, Identifiers.noSuchMethod_);
}
return function;
}
@override
void analyze(MemberEntity element) {
if (analyzedElements.contains(element)) return;
analyzedElements.add(element);
ir.Node body = computeMemberBody(element);
TypeInformation type;
reporter.withCurrentElement(element, () {
type = computeMemberTypeInformation(element, body);
});
addedInGraph++;
if (element.isField) {
FieldEntity field = element;
if (!field.isAssignable) {
// If [element] is final and has an initializer, we record
// the inferred type.
if (body != null) {
if (type is! ListTypeInformation && type is! MapTypeInformation) {
// For non-container types, the constant handler does
// constant folding that could give more precise results.
ConstantValue value = getFieldConstant(field);
if (value != null) {
if (value.isFunction) {
FunctionConstantValue functionConstant = value;
FunctionEntity function = functionConstant.element;
type = types.allocateClosure(function);
} else {
// Although we might find a better type, we have to keep
// the old type around to ensure that we get a complete view
// of the type graph and do not drop any flow edges.
AbstractValue refinedType =
abstractValueDomain.computeAbstractValueForConstant(value);
type = new NarrowTypeInformation(
abstractValueDomain, type, refinedType);
types.allocatedTypes.add(type);
}
}
}
recordTypeOfField(field, type);
} else if (!element.isInstanceMember) {
recordTypeOfField(field, types.nullType);
}
} else if (body == null) {
// Only update types of static fields if there is no
// assignment. Instance fields are dealt with in the constructor.
if (element.isStatic || element.isTopLevel) {
recordTypeOfField(field, type);
}
} else {
recordTypeOfField(field, type);
}
if ((element.isStatic || element.isTopLevel) &&
body != null &&
!element.isConst) {
if (isFieldInitializerPotentiallyNull(element, body)) {
recordTypeOfField(field, types.nullType);
}
}
} else {
FunctionEntity method = element;
recordReturnType(method, type);
}
}
/// Visits [body] to compute the [TypeInformation] node for [member].
TypeInformation computeMemberTypeInformation(
MemberEntity member, ir.Node body) {
KernelTypeGraphBuilder visitor = new KernelTypeGraphBuilder(
options,
closedWorld,
this,
member,
body,
closedWorld.globalLocalsMap.getLocalsMap(member),
closedWorld.elementMap.getStaticTypeProvider(member));
return visitor.run();
}
/// Returns `true` if the [initializer] of the non-const static or top-level
/// [field] is potentially `null`.
bool isFieldInitializerPotentiallyNull(
FieldEntity field, ir.Node initializer) {
// TODO(13429): We could do better here by using the
// constant handler to figure out if it's a lazy field or not.
// TODO(johnniwinther): Implement the ad-hoc check in ast inferrer? This
// mimicks that ast inferrer which return `true` for [ast.Send] and
// non-const [ast.NewExpression].
if (initializer is ir.MethodInvocation ||
initializer is ir.PropertyGet ||
initializer is ir.PropertySet ||
initializer is ir.StaticInvocation ||
initializer is ir.StaticGet ||
initializer is ir.StaticSet ||
initializer is ir.Let ||
initializer is ir.ConstructorInvocation && !initializer.isConst) {
return true;
}
return false;
}
/// Returns the [ConstantValue] for the initial value of [field], or
/// `null` if the initializer is not a constant value.
ConstantValue getFieldConstant(FieldEntity field) {
return closedWorld.fieldAnalysis.getFieldData(field).initialValue;
}
/// Returns `true` if [cls] has a 'call' method.
bool hasCallType(ClassEntity cls) {
return closedWorld.elementMap.types
.getCallType(closedWorld.elementEnvironment.getThisType(cls)) !=
null;
}
void processLoopInformation() {
types.allocatedCalls.forEach((CallSiteTypeInformation info) {
if (!info.inLoop) return;
// We can't compute the callees of closures, no new information to add.
if (info is ClosureCallSiteTypeInformation) {
return;
}
if (info is StaticCallSiteTypeInformation) {
MemberEntity member = info.calledElement;
inferredDataBuilder.addFunctionCalledInLoop(member);
} else if (info.mask != null &&
abstractValueDomain.containsAll(info.mask).isDefinitelyFalse) {
// For instance methods, we only register a selector called in a
// loop if it is a typed selector, to avoid marking too many
// methods as being called from within a loop. This cuts down
// on the code bloat.
info.callees.forEach((MemberEntity element) {
inferredDataBuilder.addFunctionCalledInLoop(element);
});
}
});
}
void refine() {
progress.startPhase();
while (!workQueue.isEmpty) {
progress.showProgress('Inferred ', overallRefineCount, ' types.');
TypeInformation info = workQueue.remove();
AbstractValue oldType = info.type;
AbstractValue newType = info.refine(this);
// Check that refinement has not accidentally changed the type.
assert(oldType == info.type);
if (info.abandonInferencing) info.doNotEnqueue = true;
if ((info.type = newType) != oldType) {
overallRefineCount++;
info.refineCount++;
if (info.refineCount > MAX_CHANGE_COUNT) {
if (debug.ANOMALY_WARN) {
print("ANOMALY WARNING: max refinement reached for $info");
}
info.giveUp(this);
info.type = info.refine(this);
info.doNotEnqueue = true;
}
workQueue.addAll(info.users);
if (info.hasStableType(this)) {
info.stabilize(this);
}
}
}
}
void buildWorkQueue() {
workQueue.addAll(types.orderedTypeInformations);
workQueue.addAll(types.allocatedTypes);
workQueue.addAll(types.allocatedClosures);
workQueue.addAll(types.allocatedCalls);
}
@override
void updateParameterAssignments(TypeInformation caller, MemberEntity callee,
ArgumentsTypes arguments, Selector selector, AbstractValue mask,
{bool remove, bool addToQueue: true}) {
if (callee.name == Identifiers.noSuchMethod_) return;
if (callee.isField) {
if (selector.isSetter) {
ElementTypeInformation info = types.getInferredTypeOfMember(callee);
if (remove) {
info.removeAssignment(arguments.positional[0]);
} else {
info.addAssignment(arguments.positional[0]);
}
if (addToQueue) workQueue.add(info);
}
} else if (callee.isGetter) {
return;
} else if (selector != null && selector.isGetter) {
// We are tearing a function off and thus create a closure.
assert(callee.isFunction);
MemberTypeInformation info = types.getInferredTypeOfMember(callee);
if (remove) {
info.closurizedCount--;
} else {
info.closurizedCount++;
if (callee.isStatic || callee.isTopLevel) {
types.allocatedClosures.add(info);
} else {
// We add the call-site type information here so that we
// can benefit from further refinement of the selector.
types.allocatedClosures.add(caller);
}
types.strategy.forEachParameter(callee, (Local parameter) {
ParameterTypeInformation info =
types.getInferredTypeOfParameter(parameter);
info.tagAsTearOffClosureParameter(this);
if (addToQueue) workQueue.add(info);
});
}
} else {
FunctionEntity method = callee;
ParameterStructure parameterStructure = method.parameterStructure;
int parameterIndex = 0;
types.strategy.forEachParameter(callee, (Local parameter) {
TypeInformation type;
if (parameterIndex < parameterStructure.requiredParameters) {
type = arguments.positional[parameterIndex];
} else if (parameterStructure.namedParameters.isNotEmpty) {
type = arguments.named[parameter.name];
} else if (parameterIndex < arguments.positional.length) {
type = arguments.positional[parameterIndex];
}
if (type == null) type = getDefaultTypeOfParameter(parameter);
TypeInformation info = types.getInferredTypeOfParameter(parameter);
if (remove) {
info.removeAssignment(type);
} else {
info.addAssignment(type);
}
parameterIndex++;
if (addToQueue) workQueue.add(info);
});