blob: 02b6bbdd17e4a60bee0fc487dc43faa1f01470fa [file] [log] [blame]
// Copyright (c) 2020, the R8 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.
package com.android.tools.r8.horizontalclassmerging.policies;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexMethodSignature;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.DexTypeList;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.horizontalclassmerging.ClassInstanceFieldsMerger;
import com.android.tools.r8.horizontalclassmerging.HorizontalClassMerger.Mode;
import com.android.tools.r8.horizontalclassmerging.IRCodeProvider;
import com.android.tools.r8.horizontalclassmerging.InstanceInitializerAnalysis;
import com.android.tools.r8.horizontalclassmerging.InstanceInitializerDescription;
import com.android.tools.r8.horizontalclassmerging.MergeGroup;
import com.android.tools.r8.horizontalclassmerging.MultiClassPolicy;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
import com.android.tools.r8.utils.collections.ProgramMethodMap;
import com.google.common.collect.Iterators;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Optional;
import java.util.Set;
import java.util.function.Function;
/**
* Identifies when instance initializer merging is required and bails out. This is needed to ensure
* that we don't need to append extra null arguments at constructor call sites, such that the result
* of the final round of class merging can be described as a renaming only.
*
* <p>This policy requires that all instance initializers with the same signature (relaxed, by
* converting references types to java.lang.Object) have the same behavior.
*/
public class NoInstanceInitializerMerging extends MultiClassPolicy {
private final AppView<? extends AppInfoWithClassHierarchy> appView;
private final IRCodeProvider codeProvider;
public NoInstanceInitializerMerging(
AppView<? extends AppInfoWithClassHierarchy> appView,
IRCodeProvider codeProvider,
Mode mode) {
assert mode.isFinal();
this.appView = appView;
this.codeProvider = codeProvider;
}
@Override
public Collection<MergeGroup> apply(MergeGroup group) {
assert !group.hasTarget();
assert !group.hasInstanceFieldMap();
if (group.isInterfaceGroup()) {
return ListUtils.newLinkedList(group);
}
// When we merge equivalent instance initializers with different protos, we find the least upper
// bound of each parameter type. As a result of this, the final instance initializer signatures
// are not known until all instance initializers in the group are known. Therefore, we disallow
// merging of classes that have multiple methods with the same relaxed method signature (where
// reference parameters are converted to java.lang.Object), to ensure that merging will result
// in a simple renaming (specifically, we must not need to append null arguments to constructor
// calls due to constructor collisions).
group.removeIf(this::hasMultipleInstanceInitializersWithSameRelaxedSignature);
if (group.isEmpty()) {
return Collections.emptyList();
}
// We want to allow merging of equivalent instance initializers. Equivalence depends on the
// mapping of instance fields, so we must compute this mapping now.
group.selectTarget(appView);
group.selectInstanceFieldMap(appView);
Map<MergeGroup, Map<DexMethodSignature, ProgramMethod>> newGroups = new LinkedHashMap<>();
// Caching of instance initializer descriptions, which are used to determine equivalence.
// TODO(b/181846319): Make this cache available to the instance initializer merger so that we
// don't reanalyze instance initializers.
ProgramMethodMap<Optional<InstanceInitializerDescription>> instanceInitializerDescriptions =
ProgramMethodMap.create();
Function<ProgramMethod, Optional<InstanceInitializerDescription>>
instanceInitializerDescriptionProvider =
instanceInitializer ->
getOrComputeInstanceInitializerDescription(
group, instanceInitializer, instanceInitializerDescriptions);
// Partition group into smaller groups where there are no (non-equivalent) instance initializer
// collisions.
for (DexProgramClass clazz : group) {
MergeGroup newGroup = null;
Map<DexMethodSignature, ProgramMethod> classInstanceInitializers =
getInstanceInitializersByRelaxedSignature(clazz);
for (Entry<MergeGroup, Map<DexMethodSignature, ProgramMethod>> entry : newGroups.entrySet()) {
MergeGroup candidateGroup = entry.getKey();
Map<DexMethodSignature, ProgramMethod> groupInstanceInitializers = entry.getValue();
if (canAddClassToGroup(
classInstanceInitializers,
groupInstanceInitializers,
instanceInitializerDescriptionProvider)) {
newGroup = candidateGroup;
classInstanceInitializers.forEach(groupInstanceInitializers::put);
break;
}
}
if (newGroup != null) {
newGroup.add(clazz);
} else {
newGroups.put(new MergeGroup(clazz), classInstanceInitializers);
}
}
// Remove trivial groups and finalize the newly created groups.
Collection<MergeGroup> newNonTrivialGroups = removeTrivialGroups(newGroups.keySet());
setInstanceFieldMaps(newNonTrivialGroups, group);
return newNonTrivialGroups;
}
private boolean canAddClassToGroup(
Map<DexMethodSignature, ProgramMethod> classInstanceInitializers,
Map<DexMethodSignature, ProgramMethod> groupInstanceInitializers,
Function<ProgramMethod, Optional<InstanceInitializerDescription>>
instanceInitializerDescriptionProvider) {
for (Entry<DexMethodSignature, ProgramMethod> entry : classInstanceInitializers.entrySet()) {
DexMethodSignature relaxedSignature = entry.getKey();
ProgramMethod classInstanceInitializer = entry.getValue();
ProgramMethod groupInstanceInitializer = groupInstanceInitializers.get(relaxedSignature);
if (groupInstanceInitializer == null) {
continue;
}
Optional<InstanceInitializerDescription> classInstanceInitializerDescription =
instanceInitializerDescriptionProvider.apply(classInstanceInitializer);
if (!classInstanceInitializerDescription.isPresent()) {
return false;
}
Optional<InstanceInitializerDescription> groupInstanceInitializerDescription =
instanceInitializerDescriptionProvider.apply(groupInstanceInitializer);
if (!groupInstanceInitializerDescription.isPresent()
|| !classInstanceInitializerDescription.equals(groupInstanceInitializerDescription)) {
return false;
}
}
return true;
}
private boolean hasMultipleInstanceInitializersWithSameRelaxedSignature(DexProgramClass clazz) {
Iterator<ProgramMethod> instanceInitializers = clazz.programInstanceInitializers().iterator();
if (!instanceInitializers.hasNext()) {
// No instance initializers.
return false;
}
ProgramMethod first = instanceInitializers.next();
if (!instanceInitializers.hasNext()) {
// Only a single instance initializer.
return false;
}
Set<DexMethod> seen = SetUtils.newIdentityHashSet(getRelaxedSignature(first));
return Iterators.any(
instanceInitializers,
instanceInitializer -> !seen.add(getRelaxedSignature(instanceInitializer)));
}
private Map<DexMethodSignature, ProgramMethod> getInstanceInitializersByRelaxedSignature(
DexProgramClass clazz) {
Map<DexMethodSignature, ProgramMethod> result = new HashMap<>();
for (ProgramMethod instanceInitializer : clazz.programInstanceInitializers()) {
DexMethodSignature relaxedSignature = getRelaxedSignature(instanceInitializer).getSignature();
ProgramMethod previous = result.put(relaxedSignature, instanceInitializer);
assert previous == null;
}
return result;
}
private Optional<InstanceInitializerDescription> getOrComputeInstanceInitializerDescription(
MergeGroup group,
ProgramMethod instanceInitializer,
ProgramMethodMap<Optional<InstanceInitializerDescription>> instanceInitializerDescriptions) {
return instanceInitializerDescriptions.computeIfAbsent(
instanceInitializer,
key -> {
InstanceInitializerDescription instanceInitializerDescription =
InstanceInitializerAnalysis.analyze(
appView, codeProvider, group, instanceInitializer);
return Optional.ofNullable(instanceInitializerDescription);
});
}
private DexMethod getRelaxedSignature(ProgramMethod instanceInitializer) {
DexType objectType = appView.dexItemFactory().objectType;
DexTypeList parameters = instanceInitializer.getParameters();
DexTypeList relaxedParameters =
parameters.map(parameter -> parameter.isPrimitiveType() ? parameter : objectType);
return parameters != relaxedParameters
? appView
.dexItemFactory()
.createInstanceInitializer(instanceInitializer.getHolderType(), relaxedParameters)
: instanceInitializer.getReference();
}
private void setInstanceFieldMaps(Iterable<MergeGroup> newGroups, MergeGroup group) {
for (MergeGroup newGroup : newGroups) {
// Set target.
newGroup.selectTarget(appView);
// Construct mapping from instance fields on old target to instance fields on new target.
// Note the importance of this: If we create a fresh mapping from the instance fields of each
// source class to the new target class, we could invalidate the constructor equivalence.
Map<DexEncodedField, DexEncodedField> oldTargetToNewTargetInstanceFieldMap =
new IdentityHashMap<>();
if (newGroup.getTarget() != group.getTarget()) {
ClassInstanceFieldsMerger.mapFields(
appView,
group.getTarget(),
newGroup.getTarget(),
oldTargetToNewTargetInstanceFieldMap::put);
}
// Construct mapping from source to target fields.
MutableBidirectionalManyToOneMap<DexEncodedField, DexEncodedField> instanceFieldMap =
BidirectionalManyToOneHashMap.newLinkedHashMap();
newGroup.forEachSource(
source ->
source.forEachProgramInstanceField(
sourceField -> {
DexEncodedField oldTargetInstanceField =
group.getTargetInstanceField(sourceField).getDefinition();
DexEncodedField newTargetInstanceField =
oldTargetToNewTargetInstanceFieldMap.getOrDefault(
oldTargetInstanceField, oldTargetInstanceField);
instanceFieldMap.put(sourceField.getDefinition(), newTargetInstanceField);
}));
newGroup.setInstanceFieldMap(instanceFieldMap);
}
}
@Override
public String getName() {
return "NoInstanceInitializerMerging";
}
@Override
public boolean isIdentityForInterfaceGroups() {
return true;
}
}