Parallelize vertical class merging
Change-Id: I7301960537f59beae1a6961e6a9ac5411723de21
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
index aa03ea2..2a3da47 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
@@ -6,18 +6,15 @@
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.features.FeatureSplitBoundaryOptimizationUtils;
-import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexClassAndMember;
import com.android.tools.r8.graph.DexClassAndMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexReference;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.FieldResolutionResult.SingleFieldResolutionResult;
-import com.android.tools.r8.graph.MethodResolutionResult;
import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.graph.lens.GraphLens;
@@ -25,16 +22,12 @@
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.TriFunction;
-import com.android.tools.r8.verticalclassmerging.SingleTypeMapperGraphLens;
// Computes the inlining constraint for a given instruction.
public class InliningConstraints {
private AppView<AppInfoWithLiveness> appView;
- private boolean allowStaticInterfaceMethodCalls = true;
-
// Currently used only by the vertical class merger (in all other cases this is the identity).
//
// When merging a type A into its subtype B we need to inline A.<init>() into B.<init>().
@@ -64,10 +57,6 @@
allowStaticInterfaceMethodCalls = false;
}
- private boolean isVerticalClassMerging() {
- return graphLens instanceof SingleTypeMapperGraphLens;
- }
-
public ConstraintWithTarget forAlwaysMaterializingUser() {
return ConstraintWithTarget.ALWAYS;
}
@@ -176,15 +165,17 @@
if (lookup.holder.isArrayType()) {
return ConstraintWithTarget.ALWAYS;
}
- MethodResolutionResult resolutionResult =
- appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(lookup);
- DexClassAndMethod target =
- singleTargetWhileVerticalClassMerging(
- resolutionResult, context, MethodResolutionResult::lookupInvokeDirectTarget);
- if (target != null) {
- return forResolvedMember(resolutionResult.getInitialResolutionHolder(), context, target);
+ SingleResolutionResult<?> resolutionResult =
+ appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(lookup).asSingleResolution();
+ if (resolutionResult == null) {
+ return ConstraintWithTarget.NEVER;
}
- return ConstraintWithTarget.NEVER;
+ DexClassAndMethod target =
+ resolutionResult.lookupInvokeDirectTarget(context.getHolder(), appView);
+ if (target == null) {
+ return ConstraintWithTarget.NEVER;
+ }
+ return forResolvedMember(resolutionResult.getInitialResolutionHolder(), context, target);
}
public ConstraintWithTarget forInvokeInterface(DexMethod method, ProgramMethod context) {
@@ -211,55 +202,20 @@
if (lookup.holder.isArrayType()) {
return ConstraintWithTarget.ALWAYS;
}
- MethodResolutionResult resolutionResult =
- appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(lookup);
+ SingleResolutionResult<?> resolutionResult =
+ appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(lookup).asSingleResolution();
+ if (resolutionResult == null) {
+ return ConstraintWithTarget.NEVER;
+ }
DexClassAndMethod target =
- singleTargetWhileVerticalClassMerging(
- resolutionResult, context, MethodResolutionResult::lookupInvokeStaticTarget);
- if (!allowStaticInterfaceMethodCalls && target != null) {
- // See b/120121170.
- DexClass methodClass = appView.definitionFor(graphLens.lookupType(target.getHolderType()));
- if (methodClass != null && methodClass.isInterface() && target.getDefinition().hasCode()) {
- return ConstraintWithTarget.NEVER;
- }
+ resolutionResult.lookupInvokeStaticTarget(context.getHolder(), appView);
+ if (target == null) {
+ return ConstraintWithTarget.NEVER;
}
if (target != null) {
return forResolvedMember(resolutionResult.getInitialResolutionHolder(), context, target);
}
- return ConstraintWithTarget.NEVER;
- }
-
- @SuppressWarnings({"ConstantConditions", "ReferenceEquality"})
- private DexClassAndMethod singleTargetWhileVerticalClassMerging(
- MethodResolutionResult resolutionResult,
- ProgramMethod context,
- TriFunction<
- MethodResolutionResult,
- DexProgramClass,
- AppView<? extends AppInfoWithClassHierarchy>,
- DexClassAndMethod>
- lookup) {
- if (!resolutionResult.isSingleResolution()) {
- return null;
- }
- DexClassAndMethod lookupResult = lookup.apply(resolutionResult, context.getHolder(), appView);
- if (!isVerticalClassMerging() || lookupResult != null) {
- return lookupResult;
- }
- assert isVerticalClassMerging();
- assert graphLens.lookupType(context.getHolder().superType) == context.getHolderType();
- DexProgramClass superContext =
- appView.programDefinitionFor(context.getHolder().superType, context);
- if (superContext == null) {
- return null;
- }
- DexClassAndMethod alternativeDexEncodedMethod =
- lookup.apply(resolutionResult, superContext, appView);
- if (alternativeDexEncodedMethod != null
- && alternativeDexEncodedMethod.getHolderType() == superContext.type) {
- return alternativeDexEncodedMethod;
- }
- return null;
+ return forResolvedMember(resolutionResult.getInitialResolutionHolder(), context, target);
}
public ConstraintWithTarget forInvokeSuper(DexMethod method, ProgramMethod context) {
@@ -394,10 +350,6 @@
DexClass initialResolutionHolder,
ProgramMethod context,
DexClassAndMember<?, ?> resolvedMember) {
- if (resolvedMember == null) {
- // This will fail at runtime.
- return ConstraintWithTarget.NEVER;
- }
ConstraintWithTarget featureSplitInliningConstraint =
FeatureSplitBoundaryOptimizationUtils.getInliningConstraintForResolvedMember(
context, resolvedMember, appView);
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/ClassMerger.java b/src/main/java/com/android/tools/r8/verticalclassmerging/ClassMerger.java
index 44b2d2c..5fb872d 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/ClassMerger.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/ClassMerger.java
@@ -47,7 +47,6 @@
import com.android.tools.r8.utils.CollectionUtils;
import com.android.tools.r8.utils.MethodSignatureEquivalence;
import com.android.tools.r8.utils.ObjectUtils;
-import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.Streams;
@@ -79,7 +78,7 @@
private final VerticalClassMergerGraphLens.Builder deferredRenamings;
private final DexItemFactory dexItemFactory;
private final VerticalClassMergerGraphLens.Builder lensBuilder;
- private final MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses;
+ private final VerticallyMergedClasses.Builder verticallyMergedClassesBuilder;
private final DexProgramClass source;
private final DexProgramClass target;
@@ -91,15 +90,14 @@
ClassMerger(
AppView<AppInfoWithLiveness> appView,
VerticalClassMergerGraphLens.Builder lensBuilder,
- MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses,
+ VerticallyMergedClasses.Builder verticallyMergedClassesBuilder,
DexProgramClass source,
DexProgramClass target) {
- DexItemFactory dexItemFactory = appView.dexItemFactory();
this.appView = appView;
- this.deferredRenamings = new VerticalClassMergerGraphLens.Builder(dexItemFactory);
- this.dexItemFactory = dexItemFactory;
+ this.deferredRenamings = new VerticalClassMergerGraphLens.Builder(appView);
+ this.dexItemFactory = appView.dexItemFactory();
this.lensBuilder = lensBuilder;
- this.mergedClasses = mergedClasses;
+ this.verticallyMergedClassesBuilder = verticallyMergedClassesBuilder;
this.source = source;
this.target = target;
}
@@ -585,7 +583,7 @@
// the code above. However, instructions on the form "invoke-super A.m()" should also be
// changed into "invoke-direct D.m$C()". This is achieved by also considering the classes
// that have been merged into [holder].
- Set<DexType> mergedTypes = mergedClasses.getKeys(holder.getType());
+ Set<DexType> mergedTypes = verticallyMergedClassesBuilder.getSourcesFor(holder);
for (DexType type : mergedTypes) {
DexMethod signatureInType = oldTargetReference.withHolder(type, dexItemFactory);
// Resolution would have succeeded if the method used to be in [type], or if one of
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/CollisionDetector.java b/src/main/java/com/android/tools/r8/verticalclassmerging/CollisionDetector.java
index ca22d3d..961f719 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/CollisionDetector.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/CollisionDetector.java
@@ -11,7 +11,6 @@
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.Timing;
-import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
import it.unimi.dsi.fastutil.ints.Int2IntMap;
import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
@@ -26,7 +25,6 @@
private final DexItemFactory dexItemFactory;
private final Collection<DexMethod> invokes;
- private final MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses;
private final DexType source;
private final Reference2IntMap<DexProto> sourceProtoCache;
@@ -39,12 +37,10 @@
CollisionDetector(
AppView<AppInfoWithLiveness> appView,
Collection<DexMethod> invokes,
- MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses,
DexType source,
DexType target) {
this.dexItemFactory = appView.dexItemFactory();
this.invokes = invokes;
- this.mergedClasses = mergedClasses;
this.source = source;
this.sourceProtoCache = new Reference2IntOpenHashMap<>(invokes.size() / 2);
this.sourceProtoCache.defaultReturnValue(NOT_FOUND);
@@ -115,7 +111,7 @@
int accumulator = 0;
for (DexType parameterBaseType : proto.getParameterBaseTypes(dexItemFactory)) {
// Substitute the type with the already merged class to estimate what it will look like.
- DexType mappedType = mergedClasses.getOrDefault(parameterBaseType, parameterBaseType);
+ DexType mappedType = parameterBaseType;
accumulator <<= 1;
bitsUsed++;
if (mappedType.isIdenticalTo(type)) {
@@ -130,7 +126,7 @@
}
// We also take the return type into account for potential conflicts.
DexType returnBaseType = proto.getReturnType().toBaseType(dexItemFactory);
- DexType mappedReturnType = mergedClasses.getOrDefault(returnBaseType, returnBaseType);
+ DexType mappedReturnType = returnBaseType;
accumulator <<= 1;
if (mappedReturnType.isIdenticalTo(type)) {
accumulator |= 1;
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/ConnectedComponentVerticalClassMerger.java b/src/main/java/com/android/tools/r8/verticalclassmerging/ConnectedComponentVerticalClassMerger.java
new file mode 100644
index 0000000..a823a1a
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/ConnectedComponentVerticalClassMerger.java
@@ -0,0 +1,239 @@
+// Copyright (c) 2023, 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.verticalclassmerging;
+
+import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexProto;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
+import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.MainDexInfo;
+import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.collect.Iterables;
+import it.unimi.dsi.fastutil.objects.Reference2BooleanOpenHashMap;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ExecutionException;
+
+public class ConnectedComponentVerticalClassMerger {
+
+ private final AppView<AppInfoWithLiveness> appView;
+ private final MainDexInfo mainDexInfo;
+
+ private Collection<DexMethod> invokes;
+
+ // The resulting graph lens that should be used after class merging.
+ private final VerticalClassMergerGraphLens.Builder lensBuilder;
+
+ // All the bridge methods that have been synthesized during vertical class merging.
+ private final List<SynthesizedBridgeCode> synthesizedBridges = new ArrayList<>();
+
+ private final VerticallyMergedClasses.Builder verticallyMergedClassesBuilder =
+ VerticallyMergedClasses.builder();
+
+ ConnectedComponentVerticalClassMerger(AppView<AppInfoWithLiveness> appView) {
+ this.appView = appView;
+ this.mainDexInfo = appView.appInfo().getMainDexInfo();
+ this.lensBuilder = new VerticalClassMergerGraphLens.Builder(appView);
+ }
+
+ public VerticalClassMergerResult.Builder run(
+ Set<DexProgramClass> connectedComponent,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
+ Set<DexProgramClass> pinnedClasses,
+ Timing timing)
+ throws ExecutionException {
+ // Visit the program classes in a top-down order according to the class hierarchy.
+ VerticalClassMergerPolicyExecutor policyExecutor =
+ new VerticalClassMergerPolicyExecutor(
+ appView, pinnedClasses, verticallyMergedClassesBuilder);
+ Set<DexProgramClass> mergeCandidates =
+ policyExecutor.run(connectedComponent, immediateSubtypingInfo);
+ List<DexProgramClass> mergeCandidatesSorted =
+ ListUtils.sort(mergeCandidates, Comparator.comparing(DexProgramClass::getType));
+ TopDownClassHierarchyTraversal.forProgramClasses(appView)
+ .visit(
+ mergeCandidatesSorted,
+ clazz ->
+ mergeClassIfPossible(
+ clazz, immediateSubtypingInfo, mergeCandidates, policyExecutor, timing));
+ return VerticalClassMergerResult.builder(
+ lensBuilder, synthesizedBridges, verticallyMergedClassesBuilder);
+ }
+
+ private void mergeClassIfPossible(
+ DexProgramClass clazz,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
+ Set<DexProgramClass> mergeCandidates,
+ VerticalClassMergerPolicyExecutor policyExecutor,
+ Timing timing)
+ throws ExecutionException {
+ if (!mergeCandidates.contains(clazz)) {
+ return;
+ }
+ List<DexProgramClass> subclasses = immediateSubtypingInfo.getSubclasses(clazz);
+ if (subclasses.size() != 1) {
+ return;
+ }
+ DexProgramClass targetClass = ListUtils.first(subclasses);
+ assert !verticallyMergedClassesBuilder.isMergeSource(targetClass);
+ if (verticallyMergedClassesBuilder.isMergeTarget(clazz)) {
+ return;
+ }
+ if (verticallyMergedClassesBuilder.isMergeTarget(targetClass)) {
+ if (!policyExecutor.isStillMergeCandidate(clazz, targetClass)) {
+ return;
+ }
+ } else {
+ assert policyExecutor.isStillMergeCandidate(clazz, targetClass);
+ }
+
+ // Guard against the case where we have two methods that may get the same signature
+ // if we replace types. This is rare, so we approximate and err on the safe side here.
+ CollisionDetector collisionDetector =
+ new CollisionDetector(
+ appView,
+ getInvokes(immediateSubtypingInfo, mergeCandidates),
+ clazz.getType(),
+ targetClass.getType());
+ if (collisionDetector.mayCollide(timing)) {
+ return;
+ }
+
+ // Check with main dex classes to see if we are allowed to merge.
+ if (!mainDexInfo.canMerge(clazz, targetClass, appView.getSyntheticItems())) {
+ return;
+ }
+
+ ClassMerger merger =
+ new ClassMerger(appView, lensBuilder, verticallyMergedClassesBuilder, clazz, targetClass);
+ if (merger.merge()) {
+ verticallyMergedClassesBuilder.add(clazz, targetClass);
+ // Commit the changes to the graph lens.
+ lensBuilder.merge(merger.getRenamings());
+ synthesizedBridges.addAll(merger.getSynthesizedBridges());
+ }
+ }
+
+ private Collection<DexMethod> getInvokes(
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo, Set<DexProgramClass> mergeCandidates) {
+ if (invokes == null) {
+ invokes =
+ new OverloadedMethodSignaturesRetriever(immediateSubtypingInfo, mergeCandidates)
+ .get(mergeCandidates);
+ }
+ return invokes;
+ }
+
+ // Collects all potentially overloaded method signatures that reference at least one type that
+ // may be the source or target of a merge operation.
+ private class OverloadedMethodSignaturesRetriever {
+ private final Reference2BooleanOpenHashMap<DexProto> cache =
+ new Reference2BooleanOpenHashMap<>();
+ private final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
+ private final Set<DexType> mergeeCandidates = new HashSet<>();
+
+ public OverloadedMethodSignaturesRetriever(
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
+ Set<DexProgramClass> mergeCandidates) {
+ for (DexProgramClass mergeCandidate : mergeCandidates) {
+ List<DexProgramClass> subclasses = immediateSubtypingInfo.getSubclasses(mergeCandidate);
+ if (subclasses.size() == 1) {
+ mergeeCandidates.add(ListUtils.first(subclasses).getType());
+ }
+ }
+ }
+
+ public Collection<DexMethod> get(Set<DexProgramClass> mergeCandidates) {
+ Map<DexString, DexProto> overloadingInfo = new HashMap<>();
+
+ // Find all signatures that may reference a type that could be the source or target of a
+ // merge operation.
+ Set<Wrapper<DexMethod>> filteredSignatures = new HashSet<>();
+ for (DexProgramClass clazz : appView.appInfo().classes()) {
+ for (DexEncodedMethod encodedMethod : clazz.methods()) {
+ DexMethod method = encodedMethod.getReference();
+ DexClass definition = appView.definitionFor(method.getHolderType());
+ if (definition != null
+ && definition.isProgramClass()
+ && protoMayReferenceMergedSourceOrTarget(method.getProto(), mergeCandidates)) {
+ filteredSignatures.add(equivalence.wrap(method));
+
+ // Record that we have seen a method named [signature.name] with the proto
+ // [signature.proto]. If at some point, we find a method with the same name, but a
+ // different proto, it could be the case that a method with the given name is
+ // overloaded.
+ DexProto existing =
+ overloadingInfo.computeIfAbsent(method.getName(), key -> method.getProto());
+ if (existing.isNotIdenticalTo(DexProto.SENTINEL)
+ && !existing.equals(method.getProto())) {
+ // Mark that this signature is overloaded by mapping it to SENTINEL.
+ overloadingInfo.put(method.getName(), DexProto.SENTINEL);
+ }
+ }
+ }
+ }
+
+ List<DexMethod> result = new ArrayList<>();
+ for (Wrapper<DexMethod> wrappedSignature : filteredSignatures) {
+ DexMethod signature = wrappedSignature.get();
+
+ // Ignore those method names that are definitely not overloaded since they cannot lead to
+ // any collisions.
+ if (overloadingInfo.get(signature.getName()).isIdenticalTo(DexProto.SENTINEL)) {
+ result.add(signature);
+ }
+ }
+ return result;
+ }
+
+ private boolean protoMayReferenceMergedSourceOrTarget(
+ DexProto proto, Set<DexProgramClass> mergeCandidates) {
+ boolean result;
+ if (cache.containsKey(proto)) {
+ result = cache.getBoolean(proto);
+ } else {
+ result =
+ Iterables.any(
+ proto.getTypes(),
+ type -> typeMayReferenceMergedSourceOrTarget(type, mergeCandidates));
+ cache.put(proto, result);
+ }
+ return result;
+ }
+
+ private boolean typeMayReferenceMergedSourceOrTarget(
+ DexType type, Set<DexProgramClass> mergeCandidates) {
+ type = type.toBaseType(appView.dexItemFactory());
+ if (type.isClassType()) {
+ if (mergeeCandidates.contains(type)) {
+ return true;
+ }
+ DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(type));
+ if (clazz != null) {
+ return mergeCandidates.contains(clazz.asProgramClass());
+ }
+ }
+ return false;
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/SingleTypeMapperGraphLens.java b/src/main/java/com/android/tools/r8/verticalclassmerging/SingleTypeMapperGraphLens.java
deleted file mode 100644
index 55a1a0a..0000000
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/SingleTypeMapperGraphLens.java
+++ /dev/null
@@ -1,138 +0,0 @@
-// Copyright (c) 2023, 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.verticalclassmerging;
-
-import static com.android.tools.r8.ir.code.InvokeType.VIRTUAL;
-
-import com.android.tools.r8.errors.Unreachable;
-import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexClass;
-import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexProgramClass;
-import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.graph.lens.FieldLookupResult;
-import com.android.tools.r8.graph.lens.GraphLens;
-import com.android.tools.r8.graph.lens.MethodLookupResult;
-import com.android.tools.r8.graph.lens.NonIdentityGraphLens;
-import com.android.tools.r8.graph.proto.RewrittenPrototypeDescription;
-import com.android.tools.r8.ir.code.InvokeType;
-import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
-
-public class SingleTypeMapperGraphLens extends NonIdentityGraphLens {
-
- private final VerticalClassMergerGraphLens.Builder lensBuilder;
- private final MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses;
-
- private final DexProgramClass source;
- private final DexProgramClass target;
-
- public SingleTypeMapperGraphLens(
- AppView<AppInfoWithLiveness> appView,
- VerticalClassMergerGraphLens.Builder lensBuilder,
- MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses,
- DexProgramClass source,
- DexProgramClass target) {
- super(appView, GraphLens.getIdentityLens());
- this.lensBuilder = lensBuilder;
- this.mergedClasses = mergedClasses;
- this.source = source;
- this.target = target;
- }
-
- @Override
- public Iterable<DexType> getOriginalTypes(DexType type) {
- throw new Unreachable();
- }
-
- @Override
- public DexType getPreviousClassType(DexType type) {
- throw new Unreachable();
- }
-
- @Override
- public final DexType getNextClassType(DexType type) {
- return type.isIdenticalTo(source.getType())
- ? target.getType()
- : mergedClasses.getOrDefault(type, type);
- }
-
- @Override
- public DexField getPreviousFieldSignature(DexField field) {
- throw new Unreachable();
- }
-
- @Override
- public DexField getNextFieldSignature(DexField field) {
- throw new Unreachable();
- }
-
- @Override
- public DexMethod getPreviousMethodSignature(DexMethod method) {
- throw new Unreachable();
- }
-
- @Override
- public DexMethod getNextMethodSignature(DexMethod method) {
- throw new Unreachable();
- }
-
- @Override
- public MethodLookupResult lookupMethod(
- DexMethod method, DexMethod context, InvokeType type, GraphLens codeLens) {
- // First look up the method using the existing graph lens (for example, the type will have
- // changed if the method was publicized by ClassAndMemberPublicizer).
- MethodLookupResult lookup = appView.graphLens().lookupMethod(method, context, type, codeLens);
- // Then check if there is a renaming due to the vertical class merger.
- DexMethod newMethod = lensBuilder.methodMap.get(lookup.getReference());
- if (newMethod == null) {
- return lookup;
- }
- MethodLookupResult.Builder methodLookupResultBuilder =
- MethodLookupResult.builder(this)
- .setReference(newMethod)
- .setPrototypeChanges(lookup.getPrototypeChanges())
- .setType(lookup.getType());
- if (lookup.getType() == InvokeType.INTERFACE) {
- // If an interface has been merged into a class, invoke-interface needs to be translated
- // to invoke-virtual.
- DexClass clazz = appView.definitionFor(newMethod.holder);
- if (clazz != null && !clazz.accessFlags.isInterface()) {
- assert appView.definitionFor(method.holder).accessFlags.isInterface();
- methodLookupResultBuilder.setType(VIRTUAL);
- }
- }
- return methodLookupResultBuilder.build();
- }
-
- @Override
- protected MethodLookupResult internalDescribeLookupMethod(
- MethodLookupResult previous, DexMethod context, GraphLens codeLens) {
- // This is unreachable since we override the implementation of lookupMethod() above.
- throw new Unreachable();
- }
-
- @Override
- public RewrittenPrototypeDescription lookupPrototypeChangesForMethodDefinition(
- DexMethod method, GraphLens codeLens) {
- throw new Unreachable();
- }
-
- @Override
- public DexField lookupField(DexField field, GraphLens codeLens) {
- return lensBuilder.fieldMap.getOrDefault(field, field);
- }
-
- @Override
- protected FieldLookupResult internalDescribeLookupField(FieldLookupResult previous) {
- // This is unreachable since we override the implementation of lookupField() above.
- throw new Unreachable();
- }
-
- @Override
- public boolean isContextFreeForMethods(GraphLens codeLens) {
- return true;
- }
-}
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java
index a9132b3..ef70058 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMerger.java
@@ -5,63 +5,34 @@
import static com.android.tools.r8.graph.DexClassAndMethod.asProgramMethodOrNull;
import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
-import static com.android.tools.r8.utils.AndroidApiLevelUtils.getApiReferenceLevelForMerging;
-import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
-import com.android.tools.r8.androidapi.ComputedApiLevel;
-import com.android.tools.r8.features.FeatureSplitBoundaryOptimizationUtils;
import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.CfCode;
-import com.android.tools.r8.graph.Code;
-import com.android.tools.r8.graph.DexClass;
-import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProgramClass;
-import com.android.tools.r8.graph.DexProto;
import com.android.tools.r8.graph.DexReference;
-import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
-import com.android.tools.r8.graph.LookupResult.LookupResultSuccess;
-import com.android.tools.r8.graph.ObjectAllocationInfoCollection;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.graph.PrunedItems;
-import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
import com.android.tools.r8.graph.lens.GraphLens;
-import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
+import com.android.tools.r8.optimize.argumentpropagation.utils.ProgramClassesBidirectedGraph;
import com.android.tools.r8.profile.art.ArtProfileCompletenessChecker;
import com.android.tools.r8.profile.rewriting.ProfileCollectionAdditions;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.shaking.KeepInfoCollection;
-import com.android.tools.r8.shaking.MainDexInfo;
-import com.android.tools.r8.utils.Box;
-import com.android.tools.r8.utils.FieldSignatureEquivalence;
import com.android.tools.r8.utils.InternalOptions;
-import com.android.tools.r8.utils.ListUtils;
-import com.android.tools.r8.utils.MethodSignatureEquivalence;
-import com.android.tools.r8.utils.ObjectUtils;
+import com.android.tools.r8.utils.ThreadUtils;
import com.android.tools.r8.utils.Timing;
-import com.android.tools.r8.utils.TraversalContinuation;
-import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
-import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
-import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
-import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
-import com.google.common.base.Equivalence;
-import com.google.common.base.Equivalence.Wrapper;
+import com.android.tools.r8.utils.Timing.TimingMerger;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
-import it.unimi.dsi.fastutil.objects.Reference2BooleanOpenHashMap;
+import com.google.common.collect.Streams;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedHashSet;
import java.util.List;
-import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
@@ -79,74 +50,31 @@
private final AppView<AppInfoWithLiveness> appView;
private final DexItemFactory dexItemFactory;
private final InternalOptions options;
- private Collection<DexMethod> invokes;
-
- // Set of merge candidates. Note that this must have a deterministic iteration order.
- private final Set<DexProgramClass> mergeCandidates = new LinkedHashSet<>();
-
- // Map from source class to target class.
- private final MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses =
- BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
-
- private final MutableBidirectionalManyToOneMap<DexType, DexType> mergedInterfaces =
- BidirectionalManyToOneHashMap.newIdentityHashMap();
-
- // Set of types that must not be merged into their subtype.
- private final Set<DexProgramClass> pinnedClasses = Sets.newIdentityHashSet();
-
- // The resulting graph lens that should be used after class merging.
- private final VerticalClassMergerGraphLens.Builder lensBuilder;
-
- // All the bridge methods that have been synthesized during vertical class merging.
- private final List<SynthesizedBridgeCode> synthesizedBridges = new ArrayList<>();
-
- private final MainDexInfo mainDexInfo;
public VerticalClassMerger(AppView<AppInfoWithLiveness> appView) {
- AppInfoWithLiveness appInfo = appView.appInfo();
this.appView = appView;
this.dexItemFactory = appView.dexItemFactory();
this.options = appView.options();
- this.mainDexInfo = appInfo.getMainDexInfo();
- this.lensBuilder = new VerticalClassMergerGraphLens.Builder(dexItemFactory);
- }
-
- private void initializeMergeCandidates(ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
- for (DexProgramClass sourceClass : appView.appInfo().classesWithDeterministicOrder()) {
- List<DexProgramClass> subclasses = immediateSubtypingInfo.getSubclasses(sourceClass);
- if (subclasses.size() != 1) {
- continue;
- }
- DexProgramClass targetClass = ListUtils.first(subclasses);
- if (!isMergeCandidate(sourceClass, targetClass)) {
- continue;
- }
- if (!isStillMergeCandidate(sourceClass, targetClass)) {
- continue;
- }
- if (mergeMayLeadToIllegalAccesses(sourceClass, targetClass)) {
- continue;
- }
- mergeCandidates.add(sourceClass);
- }
}
// Returns a set of types that must not be merged into other types.
- private void initializePinnedTypes() {
+ private Set<DexProgramClass> getPinnedClasses() {
+ Set<DexProgramClass> pinnedClasses = Sets.newIdentityHashSet();
+
// For all pinned fields, also pin the type of the field (because changing the type of the field
// implicitly changes the signature of the field). Similarly, for all pinned methods, also pin
// the return type and the parameter types of the method.
// TODO(b/156715504): Compute referenced-by-pinned in the keep info objects.
- List<DexReference> pinnedItems = new ArrayList<>();
+ List<DexReference> pinnedReferences = new ArrayList<>();
KeepInfoCollection keepInfo = appView.getKeepInfo();
- keepInfo.forEachPinnedType(pinnedItems::add, options);
- keepInfo.forEachPinnedMethod(pinnedItems::add, options);
- keepInfo.forEachPinnedField(pinnedItems::add, options);
- extractPinnedItems(pinnedItems);
+ keepInfo.forEachPinnedType(pinnedReferences::add, options);
+ keepInfo.forEachPinnedMethod(pinnedReferences::add, options);
+ keepInfo.forEachPinnedField(pinnedReferences::add, options);
+ extractPinnedClasses(pinnedReferences, pinnedClasses);
for (DexProgramClass clazz : appView.appInfo().classes()) {
if (Iterables.any(clazz.methods(), method -> method.getAccessFlags().isNative())) {
- markClassAsPinned(clazz);
+ markClassAsPinned(clazz, pinnedClasses);
}
}
@@ -155,39 +83,42 @@
// SpecialToDefaultMethod). However, in a class, that would lead to a verification error.
// Therefore, we disallow merging such interfaces into their subtypes.
for (DexMethod signature : appView.appInfo().getVirtualMethodsTargetedByInvokeDirect()) {
- markTypeAsPinned(signature.getHolderType());
+ markTypeAsPinned(signature.getHolderType(), pinnedClasses);
}
// The set of targets that must remain for proper resolution error cases should not be merged.
// TODO(b/192821424): Can be removed if handled.
- extractPinnedItems(appView.appInfo().getFailedMethodResolutionTargets());
+ extractPinnedClasses(appView.appInfo().getFailedMethodResolutionTargets(), pinnedClasses);
+
+ return pinnedClasses;
}
- private <T extends DexReference> void extractPinnedItems(Iterable<T> items) {
+ private <T extends DexReference> void extractPinnedClasses(
+ Iterable<T> items, Set<DexProgramClass> pinnedClasses) {
for (DexReference item : items) {
if (item.isDexType()) {
- markTypeAsPinned(item.asDexType());
+ markTypeAsPinned(item.asDexType(), pinnedClasses);
} else if (item.isDexField()) {
// Pin the holder and the type of the field.
DexField field = item.asDexField();
- markTypeAsPinned(field.getHolderType());
- markTypeAsPinned(field.getType());
+ markTypeAsPinned(field.getHolderType(), pinnedClasses);
+ markTypeAsPinned(field.getType(), pinnedClasses);
} else {
assert item.isDexMethod();
// Pin the holder, the return type and the parameter types of the method. If we were to
// merge any of these types into their sub classes, then we would implicitly change the
// signature of this method.
DexMethod method = item.asDexMethod();
- markTypeAsPinned(method.getHolderType());
- markTypeAsPinned(method.getReturnType());
+ markTypeAsPinned(method.getHolderType(), pinnedClasses);
+ markTypeAsPinned(method.getReturnType(), pinnedClasses);
for (DexType parameterType : method.getParameters()) {
- markTypeAsPinned(parameterType);
+ markTypeAsPinned(parameterType, pinnedClasses);
}
}
}
}
- private void markTypeAsPinned(DexType type) {
+ private void markTypeAsPinned(DexType type, Set<DexProgramClass> pinnedClasses) {
DexType baseType = type.toBaseType(dexItemFactory);
if (!baseType.isClassType() || appView.appInfo().isPinnedWithDefinitionLookup(baseType)) {
// We check for the case where the type is pinned according to appInfo.isPinned,
@@ -197,316 +128,14 @@
DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(baseType));
if (clazz != null) {
- markClassAsPinned(clazz);
+ markClassAsPinned(clazz, pinnedClasses);
}
}
- private void markClassAsPinned(DexProgramClass clazz) {
+ private void markClassAsPinned(DexProgramClass clazz, Set<DexProgramClass> pinnedClasses) {
pinnedClasses.add(clazz);
}
- // Returns true if [clazz] is a merge candidate. Note that the result of the checks in this
- // method do not change in response to any class merges.
- private boolean isMergeCandidate(DexProgramClass sourceClass, DexProgramClass targetClass) {
- assert targetClass != null;
- ObjectAllocationInfoCollection allocationInfo =
- appView.appInfo().getObjectAllocationInfoCollection();
- if (allocationInfo.isInstantiatedDirectly(sourceClass)
- || allocationInfo.isInterfaceWithUnknownSubtypeHierarchy(sourceClass)
- || allocationInfo.isImmediateInterfaceOfInstantiatedLambda(sourceClass)
- || !appView.getKeepInfo(sourceClass).isVerticalClassMergingAllowed(options)
- || pinnedClasses.contains(sourceClass)) {
- return false;
- }
-
- assert sourceClass
- .traverseProgramMembers(
- member -> {
- assert !appView.getKeepInfo(member).isPinned(options);
- return TraversalContinuation.doContinue();
- })
- .shouldContinue();
-
- if (!FeatureSplitBoundaryOptimizationUtils.isSafeForVerticalClassMerging(
- sourceClass, targetClass, appView)) {
- return false;
- }
- if (appView.appServices().allServiceTypes().contains(sourceClass.getType())
- && appView.getKeepInfo(targetClass).isPinned(options)) {
- return false;
- }
- if (sourceClass.isAnnotation()) {
- return false;
- }
- if (!sourceClass.isInterface()
- && targetClass.isSerializable(appView)
- && !appView.appInfo().isSerializable(sourceClass.getType())) {
- // https://docs.oracle.com/javase/8/docs/platform/serialization/spec/serial-arch.html
- // 1.10 The Serializable Interface
- // ...
- // A Serializable class must do the following:
- // ...
- // * Have access to the no-arg constructor of its first non-serializable superclass
- return false;
- }
-
- // If there is a constructor in the target, make sure that all source constructors can be
- // inlined.
- if (!Iterables.isEmpty(targetClass.programInstanceInitializers())) {
- TraversalContinuation<?, ?> result =
- sourceClass.traverseProgramInstanceInitializers(
- method -> TraversalContinuation.breakIf(disallowInlining(method, targetClass)));
- if (result.shouldBreak()) {
- return false;
- }
- }
- if (sourceClass.getEnclosingMethodAttribute() != null
- || !sourceClass.getInnerClasses().isEmpty()) {
- // TODO(b/147504070): Consider merging of enclosing-method and inner-class attributes.
- return false;
- }
- // We abort class merging when merging across nests or from a nest to non-nest.
- // Without nest this checks null == null.
- if (ObjectUtils.notIdentical(targetClass.getNestHost(), sourceClass.getNestHost())) {
- return false;
- }
-
- // If there is an invoke-special to a default interface method and we are not merging into an
- // interface, then abort, since invoke-special to a virtual class method requires desugaring.
- if (sourceClass.isInterface() && !targetClass.isInterface()) {
- TraversalContinuation<?, ?> result =
- sourceClass.traverseProgramMethods(
- method -> {
- boolean foundInvokeSpecialToDefaultLibraryMethod =
- method.registerCodeReferencesWithResult(
- new InvokeSpecialToDefaultLibraryMethodUseRegistry(appView, method));
- return TraversalContinuation.breakIf(foundInvokeSpecialToDefaultLibraryMethod);
- });
- if (result.shouldBreak()) {
- return false;
- }
- }
- return true;
- }
-
- // Returns true if [clazz] is a merge candidate. Note that the result of the checks in this
- // method may change in response to class merges. Therefore, this method should always be called
- // before merging [clazz] into its subtype.
- private boolean isStillMergeCandidate(DexProgramClass sourceClass, DexProgramClass targetClass) {
- assert isMergeCandidate(sourceClass, targetClass);
- assert !mergedClasses.containsValue(sourceClass.getType());
- // For interface types, this is more complicated, see:
- // https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-5.html#jvms-5.5
- // We basically can't move the clinit, since it is not called when implementing classes have
- // their clinit called - except when the interface has a default method.
- if ((sourceClass.hasClassInitializer() && targetClass.hasClassInitializer())
- || targetClass.classInitializationMayHaveSideEffects(
- appView, type -> type.isIdenticalTo(sourceClass.getType()))
- || (sourceClass.isInterface()
- && sourceClass.classInitializationMayHaveSideEffects(appView))) {
- // TODO(herhut): Handle class initializers.
- return false;
- }
- boolean sourceCanBeSynchronizedOn =
- appView.appInfo().isLockCandidate(sourceClass)
- || sourceClass.hasStaticSynchronizedMethods();
- boolean targetCanBeSynchronizedOn =
- appView.appInfo().isLockCandidate(targetClass)
- || targetClass.hasStaticSynchronizedMethods();
- if (sourceCanBeSynchronizedOn && targetCanBeSynchronizedOn) {
- return false;
- }
- if (targetClass.getEnclosingMethodAttribute() != null
- || !targetClass.getInnerClasses().isEmpty()) {
- // TODO(b/147504070): Consider merging of enclosing-method and inner-class attributes.
- return false;
- }
- if (methodResolutionMayChange(sourceClass, targetClass)) {
- return false;
- }
- // Field resolution first considers the direct interfaces of [targetClass] before it proceeds
- // to the super class.
- if (fieldResolutionMayChange(sourceClass, targetClass)) {
- return false;
- }
- // Only merge if api reference level of source class is equal to target class. The check is
- // somewhat expensive.
- if (appView.options().apiModelingOptions().isApiCallerIdentificationEnabled()) {
- AndroidApiLevelCompute apiLevelCompute = appView.apiLevelCompute();
- ComputedApiLevel sourceApiLevel =
- getApiReferenceLevelForMerging(apiLevelCompute, sourceClass);
- ComputedApiLevel targetApiLevel =
- getApiReferenceLevelForMerging(apiLevelCompute, targetClass);
- if (!sourceApiLevel.equals(targetApiLevel)) {
- return false;
- }
- }
- return true;
- }
-
- private boolean mergeMayLeadToIllegalAccesses(DexProgramClass source, DexProgramClass target) {
- if (source.isSamePackage(target)) {
- // When merging two classes from the same package, we only need to make sure that [source]
- // does not get less visible, since that could make a valid access to [source] from another
- // package illegal after [source] has been merged into [target].
- assert source.getAccessFlags().isPackagePrivateOrPublic();
- assert target.getAccessFlags().isPackagePrivateOrPublic();
- // TODO(b/287891322): Allow merging if `source` is only accessed from inside its own package.
- return source.getAccessFlags().isPublic() && target.getAccessFlags().isPackagePrivate();
- }
-
- // Check that all accesses to [source] and its members from inside the current package of
- // [source] will continue to work. This is guaranteed if [target] is public and all members of
- // [source] are either private or public.
- //
- // (Deliberately not checking all accesses to [source] since that would be expensive.)
- if (!target.isPublic()) {
- return true;
- }
- for (DexType sourceInterface : source.getInterfaces()) {
- DexClass sourceInterfaceClass = appView.definitionFor(sourceInterface);
- if (sourceInterfaceClass != null && !sourceInterfaceClass.isPublic()) {
- return true;
- }
- }
- for (DexEncodedField field : source.fields()) {
- if (!(field.isPublic() || field.isPrivate())) {
- return true;
- }
- }
- for (DexEncodedMethod method : source.methods()) {
- if (!(method.isPublic() || method.isPrivate())) {
- return true;
- }
- // Check if the target is overriding and narrowing the access.
- if (method.isPublic()) {
- DexEncodedMethod targetOverride = target.lookupVirtualMethod(method.getReference());
- if (targetOverride != null && !targetOverride.isPublic()) {
- return true;
- }
- }
- }
- // Check that all accesses from [source] to classes or members from the current package of
- // [source] will continue to work. This is guaranteed if the methods of [source] do not access
- // any private or protected classes or members from the current package of [source].
- TraversalContinuation<?, ?> result =
- source.traverseProgramMethods(
- method -> {
- boolean foundIllegalAccess =
- method.registerCodeReferencesWithResult(
- new IllegalAccessDetector(appView, method));
- if (foundIllegalAccess) {
- return TraversalContinuation.doBreak();
- }
- return TraversalContinuation.doContinue();
- });
- return result.shouldBreak();
- }
-
- private Collection<DexMethod> getInvokes(ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
- if (invokes == null) {
- invokes = new OverloadedMethodSignaturesRetriever(immediateSubtypingInfo).get();
- }
- return invokes;
- }
-
- // Collects all potentially overloaded method signatures that reference at least one type that
- // may be the source or target of a merge operation.
- private class OverloadedMethodSignaturesRetriever {
- private final Reference2BooleanOpenHashMap<DexProto> cache =
- new Reference2BooleanOpenHashMap<>();
- private final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
- private final Set<DexType> mergeeCandidates = new HashSet<>();
-
- public OverloadedMethodSignaturesRetriever(
- ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
- for (DexProgramClass mergeCandidate : mergeCandidates) {
- List<DexProgramClass> subclasses = immediateSubtypingInfo.getSubclasses(mergeCandidate);
- if (subclasses.size() == 1) {
- mergeeCandidates.add(ListUtils.first(subclasses).getType());
- }
- }
- }
-
- public Collection<DexMethod> get() {
- Map<DexString, DexProto> overloadingInfo = new HashMap<>();
-
- // Find all signatures that may reference a type that could be the source or target of a
- // merge operation.
- Set<Wrapper<DexMethod>> filteredSignatures = new HashSet<>();
- for (DexProgramClass clazz : appView.appInfo().classes()) {
- for (DexEncodedMethod encodedMethod : clazz.methods()) {
- DexMethod method = encodedMethod.getReference();
- DexClass definition = appView.definitionFor(method.getHolderType());
- if (definition != null
- && definition.isProgramClass()
- && protoMayReferenceMergedSourceOrTarget(method.getProto())) {
- filteredSignatures.add(equivalence.wrap(method));
-
- // Record that we have seen a method named [signature.name] with the proto
- // [signature.proto]. If at some point, we find a method with the same name, but a
- // different proto, it could be the case that a method with the given name is
- // overloaded.
- DexProto existing =
- overloadingInfo.computeIfAbsent(method.getName(), key -> method.getProto());
- if (existing.isNotIdenticalTo(DexProto.SENTINEL)
- && !existing.equals(method.getProto())) {
- // Mark that this signature is overloaded by mapping it to SENTINEL.
- overloadingInfo.put(method.getName(), DexProto.SENTINEL);
- }
- }
- }
- }
-
- List<DexMethod> result = new ArrayList<>();
- for (Wrapper<DexMethod> wrappedSignature : filteredSignatures) {
- DexMethod signature = wrappedSignature.get();
-
- // Ignore those method names that are definitely not overloaded since they cannot lead to
- // any collisions.
- if (overloadingInfo.get(signature.getName()).isIdenticalTo(DexProto.SENTINEL)) {
- result.add(signature);
- }
- }
- return result;
- }
-
- private boolean protoMayReferenceMergedSourceOrTarget(DexProto proto) {
- boolean result;
- if (cache.containsKey(proto)) {
- result = cache.getBoolean(proto);
- } else {
- result = false;
- if (typeMayReferenceMergedSourceOrTarget(proto.getReturnType())) {
- result = true;
- } else {
- for (DexType type : proto.getParameters()) {
- if (typeMayReferenceMergedSourceOrTarget(type)) {
- result = true;
- break;
- }
- }
- }
- cache.put(proto, result);
- }
- return result;
- }
-
- private boolean typeMayReferenceMergedSourceOrTarget(DexType type) {
- type = type.toBaseType(dexItemFactory);
- if (type.isClassType()) {
- if (mergeeCandidates.contains(type)) {
- return true;
- }
- DexClass clazz = appView.definitionFor(type);
- if (clazz != null && clazz.isProgramClass()) {
- return mergeCandidates.contains(clazz.asProgramClass());
- }
- }
- return false;
- }
- }
-
public static void runIfNecessary(
AppView<AppInfoWithLiveness> appView, ExecutorService executorService, Timing timing)
throws ExecutionException {
@@ -527,59 +156,103 @@
}
private void run(ExecutorService executorService, Timing timing) throws ExecutionException {
+ timing.begin("Setup");
ImmediateProgramSubtypingInfo immediateSubtypingInfo =
ImmediateProgramSubtypingInfo.create(appView);
-
- initializePinnedTypes(); // Must be initialized prior to mergeCandidates.
- initializeMergeCandidates(immediateSubtypingInfo);
-
- timing.begin("merge");
- // Visit the program classes in a top-down order according to the class hierarchy.
- TopDownClassHierarchyTraversal.forProgramClasses(appView)
- .visit(
- mergeCandidates, clazz -> mergeClassIfPossible(clazz, immediateSubtypingInfo, timing));
+ List<Set<DexProgramClass>> connectedComponents =
+ new ProgramClassesBidirectedGraph(appView, immediateSubtypingInfo)
+ .computeStronglyConnectedComponents();
+ Set<DexProgramClass> pinnedClasses = getPinnedClasses();
timing.end();
- VerticallyMergedClasses verticallyMergedClasses =
- new VerticallyMergedClasses(mergedClasses, mergedInterfaces);
- appView.setVerticallyMergedClasses(verticallyMergedClasses);
- if (verticallyMergedClasses.isEmpty()) {
+ // Apply class merging concurrently in disjoint class hierarchies.
+ VerticalClassMergerResult verticalClassMergerResult =
+ mergeClassesInConnectedComponents(
+ connectedComponents, immediateSubtypingInfo, pinnedClasses, executorService, timing);
+ appView.setVerticallyMergedClasses(verticalClassMergerResult.getVerticallyMergedClasses());
+ if (verticalClassMergerResult.isEmpty()) {
return;
}
timing.begin("fixup");
VerticalClassMergerGraphLens lens =
- new VerticalClassMergerTreeFixer(
- appView, lensBuilder, verticallyMergedClasses, synthesizedBridges)
- .fixupTypeReferences();
- KeepInfoCollection keepInfo = appView.getKeepInfo();
- keepInfo.mutate(
- mutator ->
- mutator.removeKeepInfoForMergedClasses(
- PrunedItems.builder().setRemovedClasses(mergedClasses.keySet()).build()));
- timing.end();
+ new VerticalClassMergerTreeFixer(appView, verticalClassMergerResult).run(timing);
+ updateKeepInfoForMergedClasses(verticalClassMergerResult);
+ assert verifyGraphLens(lens, verticalClassMergerResult);
+ updateArtProfiles(lens, verticalClassMergerResult);
+ appView.rewriteWithLens(lens, executorService, timing);
+ updateKeepInfoForSynthesizedBridges(verticalClassMergerResult);
+ appView.notifyOptimizationFinishedForTesting();
+ }
- assert lens != null;
- assert verifyGraphLens(lens);
+ private VerticalClassMergerResult mergeClassesInConnectedComponents(
+ List<Set<DexProgramClass>> connectedComponents,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo,
+ Set<DexProgramClass> pinnedClasses,
+ ExecutorService executorService,
+ Timing timing)
+ throws ExecutionException {
+ VerticalClassMergerResult.Builder verticalClassMergerResult =
+ VerticalClassMergerResult.builder(appView);
+ TimingMerger merger = timing.beginMerger("Merge classes", executorService);
+ Collection<Timing> timings =
+ ThreadUtils.processItemsWithResults(
+ connectedComponents,
+ connectedComponent -> {
+ Timing threadTiming = Timing.create("Merge classes in component", options);
+ VerticalClassMergerResult.Builder verticalClassMergerComponentResult =
+ new ConnectedComponentVerticalClassMerger(appView)
+ .run(connectedComponent, immediateSubtypingInfo, pinnedClasses, threadTiming);
+ verticalClassMergerResult.merge(verticalClassMergerComponentResult);
+ threadTiming.end();
+ return threadTiming;
+ },
+ appView.options().getThreadingModule(),
+ executorService);
+ merger.add(timings);
+ merger.end();
+ return verticalClassMergerResult.build();
+ }
+ private void updateArtProfiles(
+ VerticalClassMergerGraphLens verticalClassMergerLens,
+ VerticalClassMergerResult verticalClassMergerResult) {
// Include bridges in art profiles.
ProfileCollectionAdditions profileCollectionAdditions =
ProfileCollectionAdditions.create(appView);
if (!profileCollectionAdditions.isNop()) {
+ List<SynthesizedBridgeCode> synthesizedBridges =
+ verticalClassMergerResult.getSynthesizedBridges();
for (SynthesizedBridgeCode synthesizedBridge : synthesizedBridges) {
profileCollectionAdditions.applyIfContextIsInProfile(
- lens.getPreviousMethodSignature(synthesizedBridge.getMethod()),
+ verticalClassMergerLens.getPreviousMethodSignature(synthesizedBridge.getMethod()),
additionsBuilder -> additionsBuilder.addRule(synthesizedBridge.getMethod()));
}
}
profileCollectionAdditions.commit(appView);
+ }
- // Rewrite collections using the lens.
- appView.rewriteWithLens(lens, executorService, timing);
-
- // Copy keep info to newly synthesized methods.
+ private void updateKeepInfoForMergedClasses(VerticalClassMergerResult verticalClassMergerResult) {
+ KeepInfoCollection keepInfo = appView.getKeepInfo();
keepInfo.mutate(
mutator -> {
+ VerticallyMergedClasses verticallyMergedClasses =
+ verticalClassMergerResult.getVerticallyMergedClasses();
+ mutator.removeKeepInfoForMergedClasses(
+ PrunedItems.builder()
+ .setRemovedClasses(verticallyMergedClasses.getSources())
+ .build());
+ });
+ }
+
+ private void updateKeepInfoForSynthesizedBridges(
+ VerticalClassMergerResult verticalClassMergerResult) {
+ // Copy keep info to newly synthesized methods.
+ KeepInfoCollection keepInfo = appView.getKeepInfo();
+ keepInfo.mutate(
+ mutator -> {
+ List<SynthesizedBridgeCode> synthesizedBridges =
+ verticalClassMergerResult.getSynthesizedBridges();
for (SynthesizedBridgeCode synthesizedBridge : synthesizedBridges) {
ProgramMethod bridge =
asProgramMethodOrNull(appView.definitionFor(synthesizedBridge.getMethod()));
@@ -592,11 +265,10 @@
assert false;
}
});
-
- appView.notifyOptimizationFinishedForTesting();
}
- private boolean verifyGraphLens(VerticalClassMergerGraphLens graphLens) {
+ private boolean verifyGraphLens(
+ VerticalClassMergerGraphLens graphLens, VerticalClassMergerResult verticalClassMergerResult) {
// Note that the method assertReferencesNotModified() relies on getRenamedFieldSignature() and
// getRenamedMethodSignature() instead of lookupField() and lookupMethod(). This is important
// for this check to succeed, since it is not guaranteed that calling lookupMethod() with a
@@ -625,6 +297,7 @@
// pinned, because this rewriting does not affect A.method() in any way.
assert graphLens.assertPinnedNotModified(appView);
+ VerticallyMergedClasses mergedClasses = verticalClassMergerResult.getVerticallyMergedClasses();
for (DexProgramClass clazz : appView.appInfo().classes()) {
for (DexEncodedMethod encodedMethod : clazz.methods()) {
DexMethod method = encodedMethod.getReference();
@@ -650,195 +323,10 @@
// Verify that all types are up-to-date. After vertical class merging, there should be no
// more references to types that have been merged into another type.
- assert !mergedClasses.containsKey(method.getReturnType());
- assert Arrays.stream(method.getParameters().getBacking())
- .noneMatch(mergedClasses::containsKey);
+ assert Streams.stream(method.getReferencedBaseTypes(dexItemFactory))
+ .noneMatch(mergedClasses::hasBeenMergedIntoSubtype);
}
}
return true;
}
-
- private boolean methodResolutionMayChange(DexProgramClass source, DexProgramClass target) {
- for (DexEncodedMethod virtualSourceMethod : source.virtualMethods()) {
- DexEncodedMethod directTargetMethod =
- target.lookupDirectMethod(virtualSourceMethod.getReference());
- if (directTargetMethod != null) {
- // A private method shadows a virtual method. This situation is rare, since it is not
- // allowed by javac. Therefore, we just give up in this case. (In principle, it would be
- // possible to rename the private method in the subclass, and then move the virtual method
- // to the subclass without changing its name.)
- return true;
- }
- }
-
- // When merging an interface into a class, all instructions on the form "invoke-interface
- // [source].m" are changed into "invoke-virtual [target].m". We need to abort the merge if this
- // transformation could hide IncompatibleClassChangeErrors.
- if (source.isInterface() && !target.isInterface()) {
- List<DexEncodedMethod> defaultMethods = new ArrayList<>();
- for (DexEncodedMethod virtualMethod : source.virtualMethods()) {
- if (!virtualMethod.accessFlags.isAbstract()) {
- defaultMethods.add(virtualMethod);
- }
- }
-
- // For each of the default methods, the subclass [target] could inherit another default method
- // with the same signature from another interface (i.e., there is a conflict). In such cases,
- // instructions on the form "invoke-interface [source].foo()" will fail with an Incompatible-
- // ClassChangeError.
- //
- // Example:
- // interface I1 { default void m() {} }
- // interface I2 { default void m() {} }
- // class C implements I1, I2 {
- // ... invoke-interface I1.m ... <- IncompatibleClassChangeError
- // }
- for (DexEncodedMethod method : defaultMethods) {
- // Conservatively find all possible targets for this method.
- LookupResultSuccess lookupResult =
- appView
- .appInfo()
- .resolveMethodOnInterfaceLegacy(method.getHolderType(), method.getReference())
- .lookupVirtualDispatchTargets(target, appView)
- .asLookupResultSuccess();
- assert lookupResult != null;
- if (lookupResult == null) {
- return true;
- }
- if (lookupResult.contains(method)) {
- Box<Boolean> found = new Box<>(false);
- lookupResult.forEach(
- interfaceTarget -> {
- if (ObjectUtils.identical(interfaceTarget.getDefinition(), method)) {
- return;
- }
- DexClass enclosingClass = interfaceTarget.getHolder();
- if (enclosingClass != null && enclosingClass.isInterface()) {
- // Found a default method that is different from the one in [source], aborting.
- found.set(true);
- }
- },
- lambdaTarget -> {
- // The merger should already have excluded lambda implemented interfaces.
- assert false;
- });
- if (found.get()) {
- return true;
- }
- }
- }
- }
- return false;
- }
-
- private void mergeClassIfPossible(
- DexProgramClass clazz, ImmediateProgramSubtypingInfo immediateSubtypingInfo, Timing timing)
- throws ExecutionException {
- if (!mergeCandidates.contains(clazz)) {
- return;
- }
- List<DexProgramClass> subclasses = immediateSubtypingInfo.getSubclasses(clazz);
- if (subclasses.size() != 1) {
- return;
- }
- DexProgramClass targetClass = ListUtils.first(subclasses);
- assert !mergedClasses.containsKey(targetClass.getType());
- if (mergedClasses.containsValue(clazz.getType())) {
- return;
- }
- assert isMergeCandidate(clazz, targetClass);
- if (mergedClasses.containsValue(targetClass.getType())) {
- if (!isStillMergeCandidate(clazz, targetClass)) {
- return;
- }
- } else {
- assert isStillMergeCandidate(clazz, targetClass);
- }
-
- // Guard against the case where we have two methods that may get the same signature
- // if we replace types. This is rare, so we approximate and err on the safe side here.
- CollisionDetector collisionDetector =
- new CollisionDetector(
- appView,
- getInvokes(immediateSubtypingInfo),
- mergedClasses,
- clazz.getType(),
- targetClass.getType());
- if (collisionDetector.mayCollide(timing)) {
- return;
- }
-
- // Check with main dex classes to see if we are allowed to merge.
- if (!mainDexInfo.canMerge(clazz, targetClass, appView.getSyntheticItems())) {
- return;
- }
-
- ClassMerger merger = new ClassMerger(appView, lensBuilder, mergedClasses, clazz, targetClass);
- if (merger.merge()) {
- mergedClasses.put(clazz.getType(), targetClass.getType());
- if (clazz.isInterface()) {
- mergedInterfaces.put(clazz.getType(), targetClass.getType());
- }
- // Commit the changes to the graph lens.
- lensBuilder.merge(merger.getRenamings());
- synthesizedBridges.addAll(merger.getSynthesizedBridges());
- }
- }
-
- private boolean fieldResolutionMayChange(DexClass source, DexClass target) {
- if (source.getType().isIdenticalTo(target.getSuperType())) {
- // If there is a "iget Target.f" or "iput Target.f" instruction in target, and the class
- // Target implements an interface that declares a static final field f, this should yield an
- // IncompatibleClassChangeError.
- // TODO(christofferqa): In the following we only check if a static field from an interface
- // shadows an instance field from [source]. We could actually check if there is an iget/iput
- // instruction whose resolution would be affected by the merge. The situation where a static
- // field shadows an instance field is probably not widespread in practice, though.
- FieldSignatureEquivalence equivalence = FieldSignatureEquivalence.get();
- Set<Wrapper<DexField>> staticFieldsInInterfacesOfTarget = new HashSet<>();
- for (DexType interfaceType : target.getInterfaces()) {
- DexClass clazz = appView.definitionFor(interfaceType);
- for (DexEncodedField staticField : clazz.staticFields()) {
- staticFieldsInInterfacesOfTarget.add(equivalence.wrap(staticField.getReference()));
- }
- }
- for (DexEncodedField instanceField : source.instanceFields()) {
- if (staticFieldsInInterfacesOfTarget.contains(
- equivalence.wrap(instanceField.getReference()))) {
- // An instruction "iget Target.f" or "iput Target.f" that used to hit a static field in an
- // interface would now hit an instance field from [source], so that an IncompatibleClass-
- // ChangeError would no longer be thrown. Abort merge.
- return true;
- }
- }
- }
- return false;
- }
-
- private boolean disallowInlining(ProgramMethod method, DexProgramClass context) {
- if (appView.options().inlinerOptions().enableInlining) {
- Code code = method.getDefinition().getCode();
- if (code.isCfCode()) {
- CfCode cfCode = code.asCfCode();
- SingleTypeMapperGraphLens lens =
- new SingleTypeMapperGraphLens(
- appView, lensBuilder, mergedClasses, method.getHolder(), context);
- ConstraintWithTarget constraint = cfCode.computeInliningConstraint(appView, lens, method);
- if (constraint.isNever()) {
- return true;
- }
- // Constructors can have references beyond the root main dex classes. This can increase the
- // size of the main dex dependent classes and we should bail out.
- if (mainDexInfo.disallowInliningIntoContext(appView, context, method)) {
- return true;
- }
- return false;
- } else if (code.isDefaultInstanceInitializerCode()) {
- return false;
- }
- // For non-jar/cf code we currently cannot guarantee that markForceInline() will succeed.
- }
- return true;
- }
-
}
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java
index eebae8e..f4d2461 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java
@@ -17,6 +17,7 @@
import com.android.tools.r8.graph.proto.ArgumentInfoCollection;
import com.android.tools.r8.graph.proto.RewrittenPrototypeDescription;
import com.android.tools.r8.ir.code.InvokeType;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
@@ -58,15 +59,15 @@
// For the invocation "invoke-virtual A.m()" in B.m2, this graph lens will return the method B.m.
public class VerticalClassMergerGraphLens extends NestedGraphLens {
- interface GraphLensLookupResultProvider {
+ public interface GraphLensLookupResultProvider {
MethodLookupResult get(RewrittenPrototypeDescription prototypeChanges);
}
- private VerticallyMergedClasses mergedClasses;
+ private final VerticallyMergedClasses mergedClasses;
private final Map<DexType, Map<DexMethod, GraphLensLookupResultProvider>>
contextualVirtualToDirectMethodMaps;
- private Set<DexMethod> mergedMethods;
+ private final Set<DexMethod> mergedMethods;
private final Map<DexMethod, DexMethod> originalMethodSignaturesForBridges;
private final Map<DexMethod, RewrittenPrototypeDescription> prototypeChanges;
@@ -198,6 +199,7 @@
public static class Builder {
+ private final AppView<AppInfoWithLiveness> appView;
private final DexItemFactory dexItemFactory;
protected final MutableBidirectionalOneToOneMap<DexField, DexField> fieldMap =
@@ -216,13 +218,17 @@
private final Map<DexProto, DexProto> cache = new IdentityHashMap<>();
- Builder(DexItemFactory dexItemFactory) {
- this.dexItemFactory = dexItemFactory;
+ Builder(AppView<AppInfoWithLiveness> appView) {
+ this.appView = appView;
+ this.dexItemFactory = appView.dexItemFactory();
}
@SuppressWarnings("ReferenceEquality")
- static Builder createBuilderForFixup(Builder builder, VerticallyMergedClasses mergedClasses) {
- Builder newBuilder = new Builder(builder.dexItemFactory);
+ static Builder createBuilderForFixup(VerticalClassMergerResult verticalClassMergerResult) {
+ Builder builder = verticalClassMergerResult.getLensBuilder();
+ VerticallyMergedClasses mergedClasses =
+ verticalClassMergerResult.getVerticallyMergedClasses();
+ Builder newBuilder = new Builder(builder.appView);
builder.fieldMap.forEach(
(key, value) ->
newBuilder.map(
@@ -279,8 +285,7 @@
return newBuilder;
}
- public VerticalClassMergerGraphLens build(
- AppView<?> appView, VerticallyMergedClasses mergedClasses) {
+ public VerticalClassMergerGraphLens build(VerticallyMergedClasses mergedClasses) {
if (mergedClasses.isEmpty()) {
return null;
}
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerPolicyExecutor.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerPolicyExecutor.java
new file mode 100644
index 0000000..e69e96e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerPolicyExecutor.java
@@ -0,0 +1,406 @@
+// Copyright (c) 2023, 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.verticalclassmerging;
+
+import static com.android.tools.r8.utils.AndroidApiLevelUtils.getApiReferenceLevelForMerging;
+
+import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
+import com.android.tools.r8.androidapi.ComputedApiLevel;
+import com.android.tools.r8.features.FeatureSplitBoundaryOptimizationUtils;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.graph.Code;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
+import com.android.tools.r8.graph.LookupResult.LookupResultSuccess;
+import com.android.tools.r8.graph.ObjectAllocationInfoCollection;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.MainDexInfo;
+import com.android.tools.r8.utils.Box;
+import com.android.tools.r8.utils.FieldSignatureEquivalence;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.ObjectUtils;
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+// TODO(b/315252934): Parallelize policy execution over connected program components.
+public class VerticalClassMergerPolicyExecutor {
+
+ private final AppView<AppInfoWithLiveness> appView;
+ private final InternalOptions options;
+ private final MainDexInfo mainDexInfo;
+ private final Set<DexProgramClass> pinnedClasses;
+ private final VerticallyMergedClasses.Builder verticallyMergedClassesBuilder;
+
+ VerticalClassMergerPolicyExecutor(
+ AppView<AppInfoWithLiveness> appView,
+ Set<DexProgramClass> pinnedClasses,
+ VerticallyMergedClasses.Builder verticallyMergedClassesInComponentBuilder) {
+ this.appView = appView;
+ this.options = appView.options();
+ this.mainDexInfo = appView.appInfo().getMainDexInfo();
+ this.pinnedClasses = pinnedClasses;
+ this.verticallyMergedClassesBuilder = verticallyMergedClassesInComponentBuilder;
+ }
+
+ Set<DexProgramClass> run(
+ Set<DexProgramClass> connectedComponent,
+ ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+ Set<DexProgramClass> mergeCandidates = Sets.newIdentityHashSet();
+ for (DexProgramClass sourceClass : connectedComponent) {
+ List<DexProgramClass> subclasses = immediateSubtypingInfo.getSubclasses(sourceClass);
+ if (subclasses.size() != 1) {
+ continue;
+ }
+ DexProgramClass targetClass = ListUtils.first(subclasses);
+ if (!isMergeCandidate(sourceClass, targetClass)) {
+ continue;
+ }
+ if (!isStillMergeCandidate(sourceClass, targetClass)) {
+ continue;
+ }
+ if (mergeMayLeadToIllegalAccesses(sourceClass, targetClass)) {
+ continue;
+ }
+ mergeCandidates.add(sourceClass);
+ }
+ return mergeCandidates;
+ }
+
+ // Returns true if [clazz] is a merge candidate. Note that the result of the checks in this
+ // method do not change in response to any class merges.
+ private boolean isMergeCandidate(DexProgramClass sourceClass, DexProgramClass targetClass) {
+ assert targetClass != null;
+ ObjectAllocationInfoCollection allocationInfo =
+ appView.appInfo().getObjectAllocationInfoCollection();
+ if (allocationInfo.isInstantiatedDirectly(sourceClass)
+ || allocationInfo.isInterfaceWithUnknownSubtypeHierarchy(sourceClass)
+ || allocationInfo.isImmediateInterfaceOfInstantiatedLambda(sourceClass)
+ || !appView.getKeepInfo(sourceClass).isVerticalClassMergingAllowed(options)
+ || pinnedClasses.contains(sourceClass)) {
+ return false;
+ }
+
+ assert sourceClass
+ .traverseProgramMembers(
+ member -> {
+ assert !appView.getKeepInfo(member).isPinned(options);
+ return TraversalContinuation.doContinue();
+ })
+ .shouldContinue();
+
+ if (!FeatureSplitBoundaryOptimizationUtils.isSafeForVerticalClassMerging(
+ sourceClass, targetClass, appView)) {
+ return false;
+ }
+ if (appView.appServices().allServiceTypes().contains(sourceClass.getType())
+ && appView.getKeepInfo(targetClass).isPinned(options)) {
+ return false;
+ }
+ if (sourceClass.isAnnotation()) {
+ return false;
+ }
+ if (!sourceClass.isInterface()
+ && targetClass.isSerializable(appView)
+ && !appView.appInfo().isSerializable(sourceClass.getType())) {
+ // https://docs.oracle.com/javase/8/docs/platform/serialization/spec/serial-arch.html
+ // 1.10 The Serializable Interface
+ // ...
+ // A Serializable class must do the following:
+ // ...
+ // * Have access to the no-arg constructor of its first non-serializable superclass
+ return false;
+ }
+
+ // If there is a constructor in the target, make sure that all source constructors can be
+ // inlined.
+ if (!Iterables.isEmpty(targetClass.programInstanceInitializers())) {
+ TraversalContinuation<?, ?> result =
+ sourceClass.traverseProgramInstanceInitializers(
+ method -> TraversalContinuation.breakIf(disallowInlining(method, targetClass)));
+ if (result.shouldBreak()) {
+ return false;
+ }
+ }
+ if (sourceClass.hasEnclosingMethodAttribute() || !sourceClass.getInnerClasses().isEmpty()) {
+ return false;
+ }
+ // We abort class merging when merging across nests or from a nest to non-nest.
+ // Without nest this checks null == null.
+ if (ObjectUtils.notIdentical(targetClass.getNestHost(), sourceClass.getNestHost())) {
+ return false;
+ }
+
+ // If there is an invoke-special to a default interface method and we are not merging into an
+ // interface, then abort, since invoke-special to a virtual class method requires desugaring.
+ if (sourceClass.isInterface() && !targetClass.isInterface()) {
+ TraversalContinuation<?, ?> result =
+ sourceClass.traverseProgramMethods(
+ method -> {
+ boolean foundInvokeSpecialToDefaultLibraryMethod =
+ method.registerCodeReferencesWithResult(
+ new InvokeSpecialToDefaultLibraryMethodUseRegistry(appView, method));
+ return TraversalContinuation.breakIf(foundInvokeSpecialToDefaultLibraryMethod);
+ });
+ if (result.shouldBreak()) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Returns true if {@param sourceClass} is a merge candidate. Note that the result of the checks
+ * in this method may change in response to class merges. Therefore, this method should always be
+ * called before merging {@param sourceClass} into {@param targetClass}.
+ */
+ boolean isStillMergeCandidate(DexProgramClass sourceClass, DexProgramClass targetClass) {
+ assert !verticallyMergedClassesBuilder.isMergeTarget(sourceClass);
+ // For interface types, this is more complicated, see:
+ // https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-5.html#jvms-5.5
+ // We basically can't move the clinit, since it is not called when implementing classes have
+ // their clinit called - except when the interface has a default method.
+ if ((sourceClass.hasClassInitializer() && targetClass.hasClassInitializer())
+ || targetClass.classInitializationMayHaveSideEffects(
+ appView, type -> type.isIdenticalTo(sourceClass.getType()))
+ || (sourceClass.isInterface()
+ && sourceClass.classInitializationMayHaveSideEffects(appView))) {
+ return false;
+ }
+ boolean sourceCanBeSynchronizedOn =
+ appView.appInfo().isLockCandidate(sourceClass)
+ || sourceClass.hasStaticSynchronizedMethods();
+ boolean targetCanBeSynchronizedOn =
+ appView.appInfo().isLockCandidate(targetClass)
+ || targetClass.hasStaticSynchronizedMethods();
+ if (sourceCanBeSynchronizedOn && targetCanBeSynchronizedOn) {
+ return false;
+ }
+ if (targetClass.hasEnclosingMethodAttribute() || !targetClass.getInnerClasses().isEmpty()) {
+ return false;
+ }
+ if (methodResolutionMayChange(sourceClass, targetClass)) {
+ return false;
+ }
+ // Field resolution first considers the direct interfaces of [targetClass] before it proceeds
+ // to the super class.
+ if (fieldResolutionMayChange(sourceClass, targetClass)) {
+ return false;
+ }
+ // Only merge if api reference level of source class is equal to target class. The check is
+ // somewhat expensive.
+ if (appView.options().apiModelingOptions().isApiCallerIdentificationEnabled()) {
+ AndroidApiLevelCompute apiLevelCompute = appView.apiLevelCompute();
+ ComputedApiLevel sourceApiLevel =
+ getApiReferenceLevelForMerging(apiLevelCompute, sourceClass);
+ ComputedApiLevel targetApiLevel =
+ getApiReferenceLevelForMerging(apiLevelCompute, targetClass);
+ if (!sourceApiLevel.equals(targetApiLevel)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private boolean disallowInlining(ProgramMethod method, DexProgramClass context) {
+ if (!appView.options().inlinerOptions().enableInlining) {
+ return true;
+ }
+ Code code = method.getDefinition().getCode();
+ if (code.isCfCode()) {
+ CfCode cfCode = code.asCfCode();
+ ConstraintWithTarget constraint =
+ cfCode.computeInliningConstraint(appView, appView.graphLens(), method);
+ if (constraint.isNever()) {
+ return true;
+ }
+ // Constructors can have references beyond the root main dex classes. This can increase the
+ // size of the main dex dependent classes and we should bail out.
+ if (mainDexInfo.disallowInliningIntoContext(appView, context, method)) {
+ return true;
+ }
+ return false;
+ }
+ if (code.isDefaultInstanceInitializerCode()) {
+ return false;
+ }
+ return true;
+ }
+
+ private boolean fieldResolutionMayChange(DexClass source, DexClass target) {
+ if (source.getType().isIdenticalTo(target.getSuperType())) {
+ // If there is a "iget Target.f" or "iput Target.f" instruction in target, and the class
+ // Target implements an interface that declares a static final field f, this should yield an
+ // IncompatibleClassChangeError.
+ // TODO(christofferqa): In the following we only check if a static field from an interface
+ // shadows an instance field from [source]. We could actually check if there is an iget/iput
+ // instruction whose resolution would be affected by the merge. The situation where a static
+ // field shadows an instance field is probably not widespread in practice, though.
+ FieldSignatureEquivalence equivalence = FieldSignatureEquivalence.get();
+ Set<Wrapper<DexField>> staticFieldsInInterfacesOfTarget = new HashSet<>();
+ for (DexType interfaceType : target.getInterfaces()) {
+ DexClass clazz = appView.definitionFor(interfaceType);
+ for (DexEncodedField staticField : clazz.staticFields()) {
+ staticFieldsInInterfacesOfTarget.add(equivalence.wrap(staticField.getReference()));
+ }
+ }
+ for (DexEncodedField instanceField : source.instanceFields()) {
+ if (staticFieldsInInterfacesOfTarget.contains(
+ equivalence.wrap(instanceField.getReference()))) {
+ // An instruction "iget Target.f" or "iput Target.f" that used to hit a static field in an
+ // interface would now hit an instance field from [source], so that an IncompatibleClass-
+ // ChangeError would no longer be thrown. Abort merge.
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private boolean mergeMayLeadToIllegalAccesses(DexProgramClass source, DexProgramClass target) {
+ if (source.isSamePackage(target)) {
+ // When merging two classes from the same package, we only need to make sure that [source]
+ // does not get less visible, since that could make a valid access to [source] from another
+ // package illegal after [source] has been merged into [target].
+ assert source.getAccessFlags().isPackagePrivateOrPublic();
+ assert target.getAccessFlags().isPackagePrivateOrPublic();
+ // TODO(b/287891322): Allow merging if `source` is only accessed from inside its own package.
+ return source.getAccessFlags().isPublic() && target.getAccessFlags().isPackagePrivate();
+ }
+
+ // Check that all accesses to [source] and its members from inside the current package of
+ // [source] will continue to work. This is guaranteed if [target] is public and all members of
+ // [source] are either private or public.
+ //
+ // (Deliberately not checking all accesses to [source] since that would be expensive.)
+ if (!target.isPublic()) {
+ return true;
+ }
+ for (DexType sourceInterface : source.getInterfaces()) {
+ DexClass sourceInterfaceClass = appView.definitionFor(sourceInterface);
+ if (sourceInterfaceClass != null && !sourceInterfaceClass.isPublic()) {
+ return true;
+ }
+ }
+ for (DexEncodedField field : source.fields()) {
+ if (!(field.isPublic() || field.isPrivate())) {
+ return true;
+ }
+ }
+ for (DexEncodedMethod method : source.methods()) {
+ if (!(method.isPublic() || method.isPrivate())) {
+ return true;
+ }
+ // Check if the target is overriding and narrowing the access.
+ if (method.isPublic()) {
+ DexEncodedMethod targetOverride = target.lookupVirtualMethod(method.getReference());
+ if (targetOverride != null && !targetOverride.isPublic()) {
+ return true;
+ }
+ }
+ }
+ // Check that all accesses from [source] to classes or members from the current package of
+ // [source] will continue to work. This is guaranteed if the methods of [source] do not access
+ // any private or protected classes or members from the current package of [source].
+ TraversalContinuation<?, ?> result =
+ source.traverseProgramMethods(
+ method -> {
+ boolean foundIllegalAccess =
+ method.registerCodeReferencesWithResult(
+ new IllegalAccessDetector(appView, method));
+ if (foundIllegalAccess) {
+ return TraversalContinuation.doBreak();
+ }
+ return TraversalContinuation.doContinue();
+ });
+ return result.shouldBreak();
+ }
+
+ private boolean methodResolutionMayChange(DexProgramClass source, DexProgramClass target) {
+ for (DexEncodedMethod virtualSourceMethod : source.virtualMethods()) {
+ DexEncodedMethod directTargetMethod =
+ target.lookupDirectMethod(virtualSourceMethod.getReference());
+ if (directTargetMethod != null) {
+ // A private method shadows a virtual method. This situation is rare, since it is not
+ // allowed by javac. Therefore, we just give up in this case. (In principle, it would be
+ // possible to rename the private method in the subclass, and then move the virtual method
+ // to the subclass without changing its name.)
+ return true;
+ }
+ }
+
+ // When merging an interface into a class, all instructions on the form "invoke-interface
+ // [source].m" are changed into "invoke-virtual [target].m". We need to abort the merge if this
+ // transformation could hide IncompatibleClassChangeErrors.
+ if (source.isInterface() && !target.isInterface()) {
+ List<DexEncodedMethod> defaultMethods = new ArrayList<>();
+ for (DexEncodedMethod virtualMethod : source.virtualMethods()) {
+ if (!virtualMethod.accessFlags.isAbstract()) {
+ defaultMethods.add(virtualMethod);
+ }
+ }
+
+ // For each of the default methods, the subclass [target] could inherit another default method
+ // with the same signature from another interface (i.e., there is a conflict). In such cases,
+ // instructions on the form "invoke-interface [source].foo()" will fail with an Incompatible-
+ // ClassChangeError.
+ //
+ // Example:
+ // interface I1 { default void m() {} }
+ // interface I2 { default void m() {} }
+ // class C implements I1, I2 {
+ // ... invoke-interface I1.m ... <- IncompatibleClassChangeError
+ // }
+ for (DexEncodedMethod method : defaultMethods) {
+ // Conservatively find all possible targets for this method.
+ LookupResultSuccess lookupResult =
+ appView
+ .appInfo()
+ .resolveMethodOnInterfaceLegacy(method.getHolderType(), method.getReference())
+ .lookupVirtualDispatchTargets(target, appView)
+ .asLookupResultSuccess();
+ assert lookupResult != null;
+ if (lookupResult == null) {
+ return true;
+ }
+ if (lookupResult.contains(method)) {
+ Box<Boolean> found = new Box<>(false);
+ lookupResult.forEach(
+ interfaceTarget -> {
+ if (ObjectUtils.identical(interfaceTarget.getDefinition(), method)) {
+ return;
+ }
+ DexClass enclosingClass = interfaceTarget.getHolder();
+ if (enclosingClass != null && enclosingClass.isInterface()) {
+ // Found a default method that is different from the one in [source], aborting.
+ found.set(true);
+ }
+ },
+ lambdaTarget -> {
+ // The merger should already have excluded lambda implemented interfaces.
+ assert false;
+ });
+ if (found.get()) {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerResult.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerResult.java
new file mode 100644
index 0000000..a98e6c3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerResult.java
@@ -0,0 +1,87 @@
+// Copyright (c) 2023, 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.verticalclassmerging;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import java.util.ArrayList;
+import java.util.List;
+
+public class VerticalClassMergerResult {
+
+ private final VerticalClassMergerGraphLens.Builder lensBuilder;
+ private final List<SynthesizedBridgeCode> synthesizedBridges;
+ private final VerticallyMergedClasses verticallyMergedClasses;
+
+ public VerticalClassMergerResult(
+ VerticalClassMergerGraphLens.Builder lensBuilder,
+ List<SynthesizedBridgeCode> synthesizedBridges,
+ VerticallyMergedClasses verticallyMergedClasses) {
+ this.lensBuilder = lensBuilder;
+ this.synthesizedBridges = synthesizedBridges;
+ this.verticallyMergedClasses = verticallyMergedClasses;
+ }
+
+ public static Builder builder(AppView<AppInfoWithLiveness> appView) {
+ return new Builder(appView);
+ }
+
+ public static Builder builder(
+ VerticalClassMergerGraphLens.Builder lensBuilder,
+ List<SynthesizedBridgeCode> synthesizedBridges,
+ VerticallyMergedClasses.Builder verticallyMergedClassesBuilder) {
+ return new Builder(lensBuilder, synthesizedBridges, verticallyMergedClassesBuilder);
+ }
+
+ VerticalClassMergerGraphLens.Builder getLensBuilder() {
+ return lensBuilder;
+ }
+
+ List<SynthesizedBridgeCode> getSynthesizedBridges() {
+ return synthesizedBridges;
+ }
+
+ VerticallyMergedClasses getVerticallyMergedClasses() {
+ return verticallyMergedClasses;
+ }
+
+ boolean isEmpty() {
+ return verticallyMergedClasses.isEmpty();
+ }
+
+ public static class Builder {
+
+ private final VerticalClassMergerGraphLens.Builder lensBuilder;
+ private final List<SynthesizedBridgeCode> synthesizedBridges;
+ private final VerticallyMergedClasses.Builder verticallyMergedClassesBuilder;
+
+ Builder(AppView<AppInfoWithLiveness> appView) {
+ this(
+ new VerticalClassMergerGraphLens.Builder(appView),
+ new ArrayList<>(),
+ VerticallyMergedClasses.builder());
+ }
+
+ Builder(
+ VerticalClassMergerGraphLens.Builder lensBuilder,
+ List<SynthesizedBridgeCode> synthesizedBridges,
+ VerticallyMergedClasses.Builder verticallyMergedClassesBuilder) {
+ this.lensBuilder = lensBuilder;
+ this.synthesizedBridges = synthesizedBridges;
+ this.verticallyMergedClassesBuilder = verticallyMergedClassesBuilder;
+ }
+
+ synchronized void merge(VerticalClassMergerResult.Builder other) {
+ lensBuilder.merge(other.lensBuilder);
+ synthesizedBridges.addAll(other.synthesizedBridges);
+ verticallyMergedClassesBuilder.merge(other.verticallyMergedClassesBuilder);
+ }
+
+ VerticalClassMergerResult build() {
+ VerticallyMergedClasses verticallyMergedClasses = verticallyMergedClassesBuilder.build();
+ return new VerticalClassMergerResult(
+ lensBuilder, synthesizedBridges, verticallyMergedClasses);
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerTreeFixer.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerTreeFixer.java
index 832e38e..8358aac 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerTreeFixer.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerTreeFixer.java
@@ -14,6 +14,7 @@
import com.android.tools.r8.shaking.AnnotationFixer;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.OptionalBool;
+import com.android.tools.r8.utils.Timing;
import java.util.List;
class VerticalClassMergerTreeFixer extends TreeFixerBase {
@@ -23,18 +24,16 @@
private final List<SynthesizedBridgeCode> synthesizedBridges;
VerticalClassMergerTreeFixer(
- AppView<AppInfoWithLiveness> appView,
- VerticalClassMergerGraphLens.Builder lensBuilder,
- VerticallyMergedClasses mergedClasses,
- List<SynthesizedBridgeCode> synthesizedBridges) {
+ AppView<AppInfoWithLiveness> appView, VerticalClassMergerResult verticalClassMergerResult) {
super(appView);
this.lensBuilder =
- VerticalClassMergerGraphLens.Builder.createBuilderForFixup(lensBuilder, mergedClasses);
- this.mergedClasses = mergedClasses;
- this.synthesizedBridges = synthesizedBridges;
+ VerticalClassMergerGraphLens.Builder.createBuilderForFixup(verticalClassMergerResult);
+ this.mergedClasses = verticalClassMergerResult.getVerticallyMergedClasses();
+ this.synthesizedBridges = verticalClassMergerResult.getSynthesizedBridges();
}
- VerticalClassMergerGraphLens fixupTypeReferences() {
+ VerticalClassMergerGraphLens run(Timing timing) {
+ timing.begin("Fixup");
// Globally substitute merged class types in protos and holders.
for (DexProgramClass clazz : appView.appInfo().classes()) {
clazz.getMethodCollection().replaceMethods(this::fixupMethod);
@@ -46,10 +45,11 @@
for (SynthesizedBridgeCode synthesizedBridge : synthesizedBridges) {
synthesizedBridge.updateMethodSignatures(this::fixupMethodReference);
}
- VerticalClassMergerGraphLens lens = lensBuilder.build(appView, mergedClasses);
+ VerticalClassMergerGraphLens lens = lensBuilder.build(mergedClasses);
if (lens != null) {
new AnnotationFixer(lens, appView.graphLens()).run(appView.appInfo().classes());
}
+ timing.end();
return lens;
}
diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticallyMergedClasses.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticallyMergedClasses.java
index d6f3e64..8fb557a 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticallyMergedClasses.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticallyMergedClasses.java
@@ -5,14 +5,17 @@
package com.android.tools.r8.verticalclassmerging;
import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.classmerging.MergedClasses;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
import java.util.Collection;
-import java.util.Map;
import java.util.Set;
import java.util.function.BiConsumer;
@@ -28,6 +31,10 @@
this.mergedInterfaces = mergedInterfaces;
}
+ public static Builder builder() {
+ return new Builder();
+ }
+
public static VerticallyMergedClasses empty() {
EmptyBidirectionalOneToOneMap<DexType, DexType> emptyMap =
new EmptyBidirectionalOneToOneMap<>();
@@ -43,8 +50,8 @@
return mergedClasses;
}
- public Map<DexType, DexType> getForwardMap() {
- return mergedClasses.getForwardMap();
+ public Set<DexType> getSources() {
+ return mergedClasses.keySet();
}
public Collection<DexType> getSourcesFor(DexType type) {
@@ -90,4 +97,41 @@
}
return true;
}
+
+ public static class Builder {
+
+ private final MutableBidirectionalManyToOneRepresentativeMap<DexType, DexType> mergedClasses =
+ BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
+
+ private final BidirectionalManyToOneHashMap<DexType, DexType> mergedInterfaces =
+ BidirectionalManyToOneHashMap.newIdentityHashMap();
+
+ void add(DexProgramClass source, DexProgramClass target) {
+ mergedClasses.put(source.getType(), target.getType());
+ if (source.isInterface()) {
+ mergedInterfaces.put(source.getType(), target.getType());
+ }
+ }
+
+ Set<DexType> getSourcesFor(DexProgramClass target) {
+ return mergedClasses.getKeys(target.getType());
+ }
+
+ boolean isMergeSource(DexProgramClass clazz) {
+ return mergedClasses.containsKey(clazz.getType());
+ }
+
+ boolean isMergeTarget(DexProgramClass clazz) {
+ return mergedClasses.containsValue(clazz.getType());
+ }
+
+ void merge(VerticallyMergedClasses.Builder other) {
+ mergedClasses.putAll(other.mergedClasses);
+ mergedInterfaces.putAll(other.mergedInterfaces);
+ }
+
+ VerticallyMergedClasses build() {
+ return new VerticallyMergedClasses(mergedClasses, mergedInterfaces);
+ }
+ }
}
