| // 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.optimize; |
| |
| import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull; |
| |
| import com.android.tools.r8.graph.AppView; |
| import com.android.tools.r8.graph.BottomUpClassHierarchyTraversal; |
| 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.DexType; |
| import com.android.tools.r8.graph.GraphLense.NestedGraphLense; |
| import com.android.tools.r8.graph.ProgramMethod; |
| import com.android.tools.r8.graph.SubtypingInfo; |
| import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo; |
| import com.android.tools.r8.ir.optimize.info.bridge.VirtualBridgeInfo; |
| import com.android.tools.r8.shaking.AppInfoWithLiveness; |
| import com.android.tools.r8.utils.MethodSignatureEquivalence; |
| import com.google.common.base.Equivalence; |
| import com.google.common.base.Equivalence.Wrapper; |
| import com.google.common.collect.BiMap; |
| import com.google.common.collect.HashBiMap; |
| import com.google.common.collect.ImmutableMap; |
| import java.util.HashSet; |
| import java.util.Set; |
| import java.util.TreeSet; |
| |
| /** |
| * An optimization pass that hoists bridges upwards with the purpose of sharing redundant bridge |
| * methods. |
| * |
| * <p>Example: <code> |
| * class A { |
| * void m() { ... } |
| * } |
| * class B1 extends A { |
| * void bridge() { m(); } |
| * } |
| * class B2 extends A { |
| * void bridge() { m(); } |
| * } |
| * </code> Is transformed into: <code> |
| * class A { |
| * void m() { ... } |
| * void bridge() { m(); } |
| * } |
| * class B1 extends A {} |
| * class B2 extends A {} |
| * </code> |
| */ |
| public class BridgeHoisting { |
| |
| private final AppView<AppInfoWithLiveness> appView; |
| |
| // A lens that keeps track of the changes for construction of the Proguard map. |
| private final BridgeHoistingLens.Builder lensBuilder = new BridgeHoistingLens.Builder(); |
| |
| public BridgeHoisting(AppView<AppInfoWithLiveness> appView) { |
| this.appView = appView; |
| } |
| |
| public void run() { |
| SubtypingInfo subtypingInfo = appView.appInfo().computeSubtypingInfo(); |
| BottomUpClassHierarchyTraversal.forProgramClasses(appView, subtypingInfo) |
| .excludeInterfaces() |
| .visit(appView.appInfo().classes(), clazz -> processClass(clazz, subtypingInfo)); |
| if (!lensBuilder.isEmpty()) { |
| BridgeHoistingLens lens = lensBuilder.build(appView); |
| boolean changed = appView.setGraphLense(lens); |
| assert changed; |
| appView.setAppInfo( |
| appView.appInfo().rewrittenWithLens(appView.appInfo().app().asDirect(), lens)); |
| } |
| } |
| |
| private void processClass(DexProgramClass clazz, SubtypingInfo subtypingInfo) { |
| Set<DexType> subtypes = subtypingInfo.allImmediateSubtypes(clazz.type); |
| Set<DexProgramClass> subclasses = new TreeSet<>((x, y) -> x.type.slowCompareTo(y.type)); |
| for (DexType subtype : subtypes) { |
| DexProgramClass subclass = asProgramClassOrNull(appView.definitionFor(subtype)); |
| if (subclass == null) { |
| return; |
| } |
| subclasses.add(subclass); |
| } |
| for (Wrapper<DexMethod> candidate : getCandidatesForHoisting(subclasses)) { |
| hoistBridgeIfPossible(candidate.get(), clazz, subclasses); |
| } |
| } |
| |
| private Set<Wrapper<DexMethod>> getCandidatesForHoisting(Set<DexProgramClass> subclasses) { |
| Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get(); |
| Set<Wrapper<DexMethod>> candidates = new HashSet<>(); |
| for (DexProgramClass subclass : subclasses) { |
| for (DexEncodedMethod method : subclass.virtualMethods()) { |
| BridgeInfo bridgeInfo = method.getOptimizationInfo().getBridgeInfo(); |
| // TODO(b/153147967): Even if the bridge is not targeting a method in the superclass, it may |
| // be possible to rewrite the bridge to target a method in the superclass, such that we can |
| // hoist it. Add a test. |
| if (bridgeInfo != null && bridgeIsTargetingMethodInSuperclass(subclass, bridgeInfo)) { |
| candidates.add(equivalence.wrap(method.method)); |
| } |
| } |
| } |
| return candidates; |
| } |
| |
| /** |
| * Returns true if the bridge method is referencing a method in the superclass of {@param holder}. |
| * If this is not the case, we cannot hoist the bridge method, as that would lead to a type error: |
| * <code> |
| * class A { |
| * void bridge() { |
| * v0 <- Argument |
| * invoke-virtual {v0}, void B.m() // <- not valid |
| * Return |
| * } |
| * } |
| * class B extends A { |
| * void m() { |
| * ... |
| * } |
| * } |
| * </code> |
| */ |
| private boolean bridgeIsTargetingMethodInSuperclass( |
| DexProgramClass holder, BridgeInfo bridgeInfo) { |
| if (bridgeInfo.isVirtualBridgeInfo()) { |
| VirtualBridgeInfo virtualBridgeInfo = bridgeInfo.asVirtualBridgeInfo(); |
| DexMethod invokedMethod = virtualBridgeInfo.getInvokedMethod(); |
| assert !appView.appInfo().isStrictSubtypeOf(invokedMethod.holder, holder.type); |
| if (invokedMethod.holder == holder.type) { |
| return false; |
| } |
| assert appView.appInfo().isStrictSubtypeOf(holder.type, invokedMethod.holder); |
| return true; |
| } |
| assert false; |
| return false; |
| } |
| |
| private void hoistBridgeIfPossible( |
| DexMethod method, DexProgramClass clazz, Set<DexProgramClass> subclasses) { |
| // If the method is defined on the parent class, we cannot hoist the bridge. |
| // TODO(b/153147967): If the declared method is abstract, we could replace it by the bridge. |
| // Add a test. |
| if (clazz.lookupMethod(method) != null) { |
| return; |
| } |
| |
| // Go through each of the subclasses and bail-out if each subclass does not declare the same |
| // bridge. |
| BridgeInfo firstBridgeInfo = null; |
| for (DexProgramClass subclass : subclasses) { |
| DexEncodedMethod definition = subclass.lookupVirtualMethod(method); |
| if (definition == null) { |
| DexEncodedMethod resolutionTarget = |
| appView.appInfo().resolveMethodOnClass(method, subclass).getSingleTarget(); |
| if (resolutionTarget == null || resolutionTarget.isAbstract()) { |
| // The fact that this class does not declare the bridge (or the bridge is abstract) should |
| // not prevent us from hoisting the bridge. |
| // |
| // Strictly speaking, there could be an invoke instruction that targets the bridge on this |
| // subclass and fails with an AbstractMethodError or a NoSuchMethodError in the input |
| // program. After hoisting the bridge to the superclass such an instruction would no |
| // longer fail with an error in the generated program. |
| // |
| // If this ever turns out be an issue, it would be possible to track if there is an invoke |
| // instruction targeting the bridge on this subclass that fails in the Enqueuer, but this |
| // should never be the case in practice. |
| continue; |
| } |
| return; |
| } |
| |
| BridgeInfo currentBridgeInfo = definition.getOptimizationInfo().getBridgeInfo(); |
| if (currentBridgeInfo == null) { |
| return; |
| } |
| |
| if (firstBridgeInfo == null) { |
| firstBridgeInfo = currentBridgeInfo; |
| } else if (!currentBridgeInfo.hasSameTarget(firstBridgeInfo)) { |
| return; |
| } |
| } |
| |
| // If we reached this point, it is because all of the subclasses define the same bridge. |
| assert firstBridgeInfo != null; |
| |
| // Choose one of the bridge definitions as the one that we will be moving to the superclass. |
| ProgramMethod representative = findRepresentative(subclasses, method); |
| assert representative != null; |
| |
| // Guard against accessibility issues. |
| if (mayBecomeInaccessibleAfterHoisting(clazz, representative)) { |
| return; |
| } |
| |
| // Move the bridge method to the super class, and record this in the graph lens. |
| DexMethod newMethod = |
| appView.dexItemFactory().createMethod(clazz.type, method.proto, method.name); |
| clazz.addVirtualMethod(representative.getDefinition().toTypeSubstitutedMethod(newMethod)); |
| lensBuilder.move(representative.getDefinition().method, newMethod); |
| |
| // Remove all of the bridges in the subclasses. |
| for (DexProgramClass subclass : subclasses) { |
| DexEncodedMethod removed = subclass.removeMethod(method); |
| assert removed == null || !appView.appInfo().isPinned(removed.method); |
| } |
| } |
| |
| private ProgramMethod findRepresentative(Iterable<DexProgramClass> subclasses, DexMethod method) { |
| for (DexProgramClass subclass : subclasses) { |
| DexEncodedMethod definition = subclass.lookupVirtualMethod(method); |
| if (definition != null) { |
| return new ProgramMethod(subclass, definition); |
| } |
| } |
| return null; |
| } |
| |
| private boolean mayBecomeInaccessibleAfterHoisting( |
| DexProgramClass clazz, ProgramMethod representative) { |
| if (clazz.type.isSamePackage(representative.getHolder().type)) { |
| return false; |
| } |
| return !representative.getDefinition().isPublic(); |
| } |
| |
| static class BridgeHoistingLens extends NestedGraphLense { |
| |
| public BridgeHoistingLens( |
| AppView<?> appView, BiMap<DexMethod, DexMethod> originalMethodSignatures) { |
| super( |
| ImmutableMap.of(), |
| ImmutableMap.of(), |
| ImmutableMap.of(), |
| null, |
| originalMethodSignatures, |
| appView.graphLense(), |
| appView.dexItemFactory()); |
| } |
| |
| @Override |
| public boolean isLegitimateToHaveEmptyMappings() { |
| return true; |
| } |
| |
| static class Builder { |
| |
| private final BiMap<DexMethod, DexMethod> originalMethodSignatures = HashBiMap.create(); |
| |
| public boolean isEmpty() { |
| return originalMethodSignatures.isEmpty(); |
| } |
| |
| public void move(DexMethod from, DexMethod to) { |
| originalMethodSignatures.forcePut(to, originalMethodSignatures.getOrDefault(from, from)); |
| } |
| |
| public BridgeHoistingLens build(AppView<?> appView) { |
| assert !isEmpty(); |
| return new BridgeHoistingLens(appView, originalMethodSignatures); |
| } |
| } |
| } |
| } |