blob: 5b45c236e8f08da07493acd08211f27f289ce1ea [file] [log] [blame]
// 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 '../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 '../js_backend/annotations.dart' as optimizerHints;
import '../js_backend/inferred_data.dart';
import '../js_backend/no_such_method_registry.dart';
import '../js_emitter/sorter.dart';
import '../native/behavior.dart' as native;
import '../options.dart';
import '../types/abstract_value_domain.dart';
import '../types/types.dart';
import '../universe/call_structure.dart';
import '../universe/selector.dart';
import '../universe/side_effects.dart';
import '../util/setlet.dart';
import '../world.dart';
import 'closure_tracer.dart';
import 'debug.dart' as debug;
import 'locals_handler.dart';
import 'list_tracer.dart';
import 'map_tracer.dart';
import 'type_graph_dump.dart';
import 'type_graph_inferrer.dart';
import 'type_graph_nodes.dart';
import 'type_system.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<T> {
/// 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;
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<T> get types;
Map<T, TypeInformation> get concreteTypes;
InferredDataBuilder get inferredDataBuilder;
FunctionEntity get mainElement;
void runOverAllElements();
void analyze(MemberEntity member);
void analyzeListAndEnqueue(ListTypeInformation 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<T> dataOfMember(MemberEntity element);
GlobalTypeInferenceElementData<T> lookupDataOfMember(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(T node, TypeInformation argument);
/// Registers a call to yield with an expression of type [argumentType] as
/// argument.
TypeInformation registerYield(T 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(
T 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,
T 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, T 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
/// [native.NativeBehavior].
TypeInformation typeOfNativeBehavior(native.NativeBehavior nativeBehavior);
bool returnsListElementType(Selector selector, AbstractValue mask);
bool returnsMapValueType(Selector selector, AbstractValue mask);
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 parameter and returns types should be trusted for
/// [member].
bool trustTypeAnnotations(MemberEntity member);
/// Returns `true` if inference of parameter types is disabled for [member].
bool assumeDynamic(MemberEntity member);
}
abstract class InferrerEngineImpl<T> extends InferrerEngine<T> {
static bool retainDataForTesting = false;
final Map<Local, TypeInformation> defaultTypeOfParameter =
new Map<Local, TypeInformation>();
final WorkQueue workQueue = new WorkQueue();
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;
final CompilerOptions options;
final Progress progress;
final DiagnosticReporter reporter;
final CompilerOutput _compilerOutput;
/// The [JClosedWorld] on which inference reasoning is based.
final JClosedWorld closedWorld;
final InferredDataBuilder inferredDataBuilder;
final TypeSystem<T> types;
final Map<T, TypeInformation> concreteTypes = new Map<T, TypeInformation>();
final Map<ir.Node, TypeInformation> concreteKernelTypes =
new Map<ir.Node, 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;
final Sorter sorter;
InferrerEngineImpl(
this.options,
this.progress,
this.reporter,
this._compilerOutput,
this.closedWorld,
this.noSuchMethodRegistry,
this.mainElement,
this.sorter,
this.inferredDataBuilder,
TypeSystemStrategy<T> typeSystemStrategy)
: this.types = new TypeSystem<T>(closedWorld, typeSystemStrategy);
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;
}
}
GlobalTypeInferenceElementData<T> createElementData();
// TODO(johnniwinther): Make this private again.
GlobalTypeInferenceElementData<T> dataOfMember(MemberEntity element) =>
_memberData.putIfAbsent(element, createElementData);
GlobalTypeInferenceElementData<T> lookupDataOfMember(MemberEntity element) =>
_memberData[element];
/**
* 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));
}
}
TypeInformation typeOfNativeBehavior(native.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 == native.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 {
mappedType = types.nonNullSubtype(type.element);
}
returnType = types.computeLUB(returnType, mappedType);
if (returnType == types.dynamicType) {
break;
}
}
return returnType;
}
void updateSelectorInMember(MemberEntity owner, CallType callType, T node,
Selector selector, AbstractValue mask) {
GlobalTypeInferenceElementData data = dataOfMember(owner);
assert(validCallType(callType, node));
switch (callType) {
case CallType.access:
data.setTypeMask(node, mask);
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;
}
}
bool checkIfExposesThis(ConstructorEntity element) {
return generativeConstructorsExposingThis.contains(element);
}
void recordExposesThis(ConstructorEntity element, bool exposesThis) {
if (exposesThis) {
generativeConstructorsExposingThis.add(element);
}
}
bool returnsListElementType(Selector selector, AbstractValue mask) {
return mask != null &&
abstractValueDomain.isContainer(mask) &&
returnsListElementTypeSet.contains(selector);
}
bool returnsMapValueType(Selector selector, AbstractValue mask) {
return mask != null && abstractValueDomain.isMap(mask) && selector.isIndex;
}
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);
}
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);
}
void runOverAllElements() {
progress.startPhase();
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 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.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();
}
static bool useSorterForTesting = false;
/// Call [analyze] for all live members.
void analyzeAllElements() {
Iterable<MemberEntity> processedMembers = closedWorld.processedMembers
.where((MemberEntity member) => !member.isAbstract);
Iterable<MemberEntity> members = useSorterForTesting
? sorter.sortMembers(processedMembers)
: sortMembers(processedMembers, computeMemberSize);
members.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.');
}
/// Compute a 'size' of [member] used for sorting member for the type
/// inference work-queue. Smallest members are processed first.
int computeMemberSize(MemberEntity member);
/// Returns the body node for [member].
T computeMemberBody(MemberEntity member);
/// Returns the `call` method on [cls] or the `noSuchMethod` if [cls] doesn't
/// implement `call`.
FunctionEntity lookupCallMethod(ClassEntity cls);
void analyze(MemberEntity element) {
if (analyzedElements.contains(element)) return;
analyzedElements.add(element);
T 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, T body);
/// Returns `true` if the [initializer] of the non-const static or top-level
/// [field] is potentially `null`.
bool isFieldInitializerPotentiallyNull(FieldEntity field, T initializer);
/// Returns the [ConstantValue] for the initial value of [field], or
/// `null` if the initializer is not a constant value.
ConstantValue getFieldConstant(FieldEntity field);
/// Returns `true` if [cls] has a 'call' method.
bool hasCallType(ClassEntity cls);
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)) {
// 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() {
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);
}
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);
});
}
}
void setDefaultTypeOfParameter(Local parameter, TypeInformation type,
{bool isInstanceMember}) {
assert(
type != null, failedAt(parameter, "No default type for $parameter."));
TypeInformation existing = defaultTypeOfParameter[parameter];
defaultTypeOfParameter[parameter] = type;
TypeInformation info = types.getInferredTypeOfParameter(parameter);
if (existing != null && existing is PlaceholderTypeInformation) {
// Replace references to [existing] to use [type] instead.
if (isInstanceMember) {
ParameterAssignments assignments = info.assignments;
assignments.replace(existing, type);
} else {
List<TypeInformation> assignments = info.assignments;
for (int i = 0; i < assignments.length; i++) {
if (assignments[i] == existing) {
assignments[i] = type;
}
}
}
// Also forward all users.
type.addUsersOf(existing);
} else {
assert(existing == null);
}
}
TypeInformation getDefaultTypeOfParameter(Local parameter) {
return defaultTypeOfParameter.putIfAbsent(parameter, () {
return new PlaceholderTypeInformation(
abstractValueDomain, types.currentMember);
});
}
bool hasAlreadyComputedTypeOfParameterDefault(Local parameter) {
TypeInformation seen = defaultTypeOfParameter[parameter];
return (seen != null && seen is! PlaceholderTypeInformation);
}
TypeInformation typeOfParameter(Local element) {
return types.getInferredTypeOfParameter(element);
}
TypeInformation typeOfMember(MemberEntity element) {
if (element is FunctionEntity) return types.functionType;
return types.getInferredTypeOfMember(element);
}
TypeInformation returnTypeOfMember(MemberEntity element) {
if (element is! FunctionEntity) return types.dynamicType;
return types.getInferredTypeOfMember(element);
}
void recordTypeOfField(FieldEntity element, TypeInformation type) {
types.getInferredTypeOfMember(element).addAssignment(type);
}
void recordReturnType(FunctionEntity element, TypeInformation type) {
TypeInformation info = types.getInferredTypeOfMember(element);
if (element.name == '==') {
// Even if x.== doesn't return a bool, 'x == null' evaluates to 'false'.
info.addAssignment(types.boolType);
}
// TODO(ngeoffray): Clean up. We do these checks because
// [SimpleTypesInferrer] deals with two different inferrers.
if (type == null) return;
if (info.assignments.isEmpty) info.addAssignment(type);
}
TypeInformation addReturnTypeForMethod(
FunctionEntity element, TypeInformation unused, TypeInformation newType) {
TypeInformation type = types.getInferredTypeOfMember(element);
// TODO(ngeoffray): Clean up. We do this check because
// [SimpleTypesInferrer] deals with two different inferrers.
if (element is ConstructorEntity && element.isGenerativeConstructor) {
return type;
}
type.addAssignment(newType);
return type;
}
TypeInformation registerCalledMember(
Object node,
Selector selector,
AbstractValue mask,
MemberEntity caller,
MemberEntity callee,
ArgumentsTypes arguments,
SideEffectsBuilder sideEffectsBuilder,
bool inLoop) {
CallSiteTypeInformation info = new StaticCallSiteTypeInformation(
abstractValueDomain,
types.currentMember,
node,
caller,
callee,
selector,
mask,
arguments,
inLoop);
// If this class has a 'call' method then we have essentially created a
// closure here. Register it as such so that it is traced.
// Note: we exclude factory constructors because they don't always create an
// instance of the type. They are static methods that delegate to some other
// generative constructor to do the actual creation of the object.
if (selector != null &&
selector.isCall &&
callee is ConstructorEntity &&
callee.isGenerativeConstructor) {
ClassEntity cls = callee.enclosingClass;
if (hasCallType(cls)) {
types.allocatedClosures.add(info);
}
}
info.addToGraph(this);
types.allocatedCalls.add(info);
updateSideEffects(sideEffectsBuilder, selector, callee);
return info;
}
TypeInformation registerCalledSelector(
CallType callType,
T node,
Selector selector,
AbstractValue mask,
TypeInformation receiverType,
MemberEntity caller,
ArgumentsTypes arguments,
SideEffectsBuilder sideEffectsBuilder,
{bool inLoop,
bool isConditional}) {
if (selector.isClosureCall) {
return registerCalledClosure(node, selector, mask, receiverType, caller,
arguments, sideEffectsBuilder,
inLoop: inLoop);
}
if (closedWorld.includesClosureCall(selector, mask)) {
sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
}
closedWorld.locateMembers(selector, mask).forEach((callee) {
updateSideEffects(sideEffectsBuilder, selector, callee);
});
CallSiteTypeInformation info = new DynamicCallSiteTypeInformation(
abstractValueDomain,
types.currentMember,
callType,
node,
caller,
selector,
mask,
receiverType,
arguments,
inLoop,
isConditional);
info.addToGraph(this);
types.allocatedCalls.add(info);
return info;
}
TypeInformation registerAwait(T node, TypeInformation argument) {
AwaitTypeInformation info = new AwaitTypeInformation<T>(
abstractValueDomain, types.currentMember, node);
info.addAssignment(argument);
types.allocatedTypes.add(info);
return info;
}
TypeInformation registerYield(T node, TypeInformation argument) {
YieldTypeInformation info = new YieldTypeInformation<T>(
abstractValueDomain, types.currentMember, node);
info.addAssignment(argument);
types.allocatedTypes.add(info);
return info;
}
TypeInformation registerCalledClosure(
T node,
Selector selector,
AbstractValue mask,
TypeInformation closure,
MemberEntity caller,
ArgumentsTypes arguments,
SideEffectsBuilder sideEffectsBuilder,
{bool inLoop}) {
sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
CallSiteTypeInformation info = new ClosureCallSiteTypeInformation(
abstractValueDomain,
types.currentMember,
node,
caller,
selector,
mask,
closure,
arguments,
inLoop);
info.addToGraph(this);
types.allocatedCalls.add(info);
return info;
}
void clear() {
void cleanup(TypeInformation info) {
if (!retainDataForTesting) {
info.cleanup();
}
}
types.allocatedCalls.forEach(cleanup);
types.allocatedCalls.clear();
defaultTypeOfParameter.clear();
types.parameterTypeInformations.values.forEach(cleanup);
types.memberTypeInformations.values.forEach(cleanup);
types.allocatedTypes.forEach(cleanup);
types.allocatedTypes.clear();
types.concreteTypes.clear();
types.allocatedClosures.forEach(cleanup);
types.allocatedClosures.clear();
analyzedElements.clear();
generativeConstructorsExposingThis.clear();
types.allocatedMaps.values.forEach(cleanup);
types.allocatedLists.values.forEach(cleanup);
}
Iterable<MemberEntity> getCallersOfForTesting(MemberEntity element) {
MemberTypeInformation info = types.getInferredTypeOfMember(element);
return info.callersForTesting;
}
TypeInformation typeOfMemberWithSelector(
MemberEntity element, Selector selector) {
if (element.name == Identifiers.noSuchMethod_ &&
selector.name != element.name) {
// An invocation can resolve to a [noSuchMethod], in which case
// we get the return type of [noSuchMethod].
return returnTypeOfMember(element);
} else if (selector.isGetter) {
if (element.isFunction) {
// [functionType] is null if the inferrer did not run.
return types.functionType == null
? types.dynamicType
: types.functionType;
} else if (element.isField) {
return typeOfMember(element);
} else if (element.isGetter) {
return returnTypeOfMember(element);
} else {
assert(false, failedAt(element, "Unexpected member $element"));
return types.dynamicType;
}
} else if (element.isGetter || element.isField) {
assert(selector.isCall || selector.isSetter);
return types.dynamicType;
} else {
return returnTypeOfMember(element);
}
}
/// 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) {
if (closedWorld.backendUsage.isFieldUsedByBackend(element)) {
return false;
}
if ((element.isTopLevel || element.isStatic) && !element.isAssignable) {
return true;
}
return true;
}
/// 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) {
return !closedWorld.backendUsage.isFunctionUsedByBackend(function);
}
@override
bool trustTypeAnnotations(MemberEntity member) {
return optimizerHints.trustTypeAnnotations(
closedWorld.elementEnvironment, commonElements, member);
}
@override
bool assumeDynamic(MemberEntity member) {
return optimizerHints.assumeDynamic(
closedWorld.elementEnvironment, commonElements, member);
}
// Sorts the resolved elements by size. We do this for this inferrer
// to get the same results for [ListTracer] compared to the
// [SimpleTypesInferrer].
static Iterable<MemberEntity> sortMembers(
Iterable<MemberEntity> members, int computeSize(MemberEntity member)) {
Map<int, Set<MemberEntity>> methodSizes =
groupMembers(members, computeSize);
int max = methodSizes.keys.fold(0, (a, b) => a > b ? a : b);
List<MemberEntity> result = <MemberEntity>[];
for (int i = 0; i <= max; i++) {
Set<MemberEntity> set = methodSizes[i];
if (set != null) result.addAll(set);
}
return result;
}
static Map<int, Set<MemberEntity>> groupMembers(
Iterable<MemberEntity> members, int computeSize(MemberEntity member)) {
Map<int, Set<MemberEntity>> methodSizes = <int, Set<MemberEntity>>{};
members.forEach((MemberEntity element) {
// Put the other operators in buckets by size, later to be added in
// size order.
int size = computeSize(element);
Set<MemberEntity> set =
methodSizes.putIfAbsent(size, () => new Setlet<MemberEntity>());
set.add(element);
});
return methodSizes;
}
}