Top-down propagation of argument information to overrides
Bug: 190154391
Change-Id: I98b0c3d4edd0088765216b1cb432cab5e9c11a1d
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicType.java b/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicType.java
index ca4b23c..12d1c4c 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicType.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicType.java
@@ -60,7 +60,7 @@
}
public boolean isTrivial(TypeElement staticType) {
- return staticType == getDynamicUpperBoundType();
+ return staticType == getDynamicUpperBoundType() || isUnknown();
}
public boolean isUnknown() {
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java
index b664811..750169d 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java
@@ -15,6 +15,10 @@
return BottomValue.getInstance();
}
+ public static UnknownValue unknown() {
+ return UnknownValue.getInstance();
+ }
+
public abstract boolean isNonTrivial();
public boolean isSingleBoolean() {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/ConcreteCallSiteOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/ConcreteCallSiteOptimizationInfo.java
index 83fdf6a..ed27028 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/ConcreteCallSiteOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/ConcreteCallSiteOptimizationInfo.java
@@ -9,12 +9,17 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.analysis.type.DynamicType;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.ir.analysis.value.UnknownValue;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMonomorphicMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteParameterState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ParameterState;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
@@ -193,6 +198,68 @@
return isTop ? CallSiteOptimizationInfo.top() : newCallSiteInfo;
}
+ public static CallSiteOptimizationInfo fromMethodState(
+ AppView<AppInfoWithLiveness> appView,
+ ProgramMethod method,
+ ConcreteMonomorphicMethodState methodState) {
+ boolean allowConstantPropagation =
+ appView.options().callSiteOptimizationOptions().isConstantPropagationEnabled();
+ ConcreteCallSiteOptimizationInfo newCallSiteInfo =
+ new ConcreteCallSiteOptimizationInfo(methodState.size(), allowConstantPropagation);
+ boolean isTop = true;
+ for (int argumentIndex = 0; argumentIndex < methodState.size(); argumentIndex++) {
+ ParameterState parameterState = methodState.getParameterState(argumentIndex);
+ if (parameterState.isUnknown()) {
+ continue;
+ }
+
+ ConcreteParameterState concreteParameterState = parameterState.asConcrete();
+
+ // Constant propagation.
+ if (allowConstantPropagation) {
+ AbstractValue abstractValue = concreteParameterState.getAbstractValue();
+ if (abstractValue.isNonTrivial()) {
+ newCallSiteInfo.constants.put(argumentIndex, abstractValue);
+ isTop = false;
+ }
+ }
+
+ // Type propagation.
+ DexType staticType = method.getDefinition().getArgumentType(argumentIndex);
+ if (staticType.isReferenceType()) {
+ TypeElement staticTypeElement = staticType.toTypeElement(appView);
+ if (staticType.isArrayType()) {
+ Nullability nullability = concreteParameterState.asArrayParameter().getNullability();
+ if (nullability.isDefinitelyNull()) {
+ if (allowConstantPropagation) {
+ newCallSiteInfo.constants.put(
+ argumentIndex, appView.abstractValueFactory().createNullValue());
+ }
+ } else if (nullability.isDefinitelyNotNull()) {
+ newCallSiteInfo.dynamicUpperBoundTypes.put(
+ argumentIndex, staticTypeElement.asArrayType().asDefinitelyNotNull());
+ } else {
+ // Should never happen, since the parameter state is unknown in this case.
+ assert false;
+ }
+ } else if (staticType.isClassType()) {
+ DynamicType dynamicType =
+ method.getDefinition().isInstance() && argumentIndex == 0
+ ? concreteParameterState.asReceiverParameter().getDynamicType()
+ : concreteParameterState.asClassParameter().getDynamicType();
+ if (!dynamicType.isTrivial(staticTypeElement)) {
+ newCallSiteInfo.dynamicUpperBoundTypes.put(
+ argumentIndex, dynamicType.getDynamicUpperBoundType());
+ isTop = false;
+ } else {
+ newCallSiteInfo.dynamicUpperBoundTypes.put(argumentIndex, staticTypeElement);
+ }
+ }
+ }
+ }
+ return isTop ? CallSiteOptimizationInfo.top() : newCallSiteInfo;
+ }
+
@Override
public boolean isConcreteCallSiteOptimizationInfo() {
return true;
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/BottomMethodState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/BottomMethodState.java
new file mode 100644
index 0000000..fea97a2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/BottomMethodState.java
@@ -0,0 +1,36 @@
+// Copyright (c) 2021, 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.argumentpropagation.codescanner;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import java.util.function.Supplier;
+
+public class BottomMethodState extends MethodStateBase {
+
+ private static final BottomMethodState INSTANCE = new BottomMethodState();
+
+ private BottomMethodState() {}
+
+ public static BottomMethodState get() {
+ return INSTANCE;
+ }
+
+ @Override
+ public boolean isBottom() {
+ return true;
+ }
+
+ @Override
+ public MethodState mutableJoin(AppView<AppInfoWithLiveness> appView, MethodState methodState) {
+ return methodState;
+ }
+
+ @Override
+ public MethodState mutableJoin(
+ AppView<AppInfoWithLiveness> appView, Supplier<MethodState> methodStateSupplier) {
+ return methodStateSupplier.get();
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteArrayTypeParameterState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteArrayTypeParameterState.java
index e66cea9..7615aaf 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteArrayTypeParameterState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteArrayTypeParameterState.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.optimize.argumentpropagation.codescanner;
import com.android.tools.r8.ir.analysis.type.Nullability;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
public class ConcreteArrayTypeParameterState extends ConcreteParameterState {
@@ -31,10 +32,19 @@
}
@Override
+ public AbstractValue getAbstractValue() {
+ return AbstractValue.unknown();
+ }
+
+ @Override
public ConcreteParameterStateKind getKind() {
return ConcreteParameterStateKind.ARRAY;
}
+ public Nullability getNullability() {
+ return nullability;
+ }
+
@Override
public boolean isArrayParameter() {
return true;
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteClassTypeParameterState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteClassTypeParameterState.java
index 03fc610..9574d08 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteClassTypeParameterState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteClassTypeParameterState.java
@@ -51,6 +51,15 @@
}
@Override
+ public AbstractValue getAbstractValue() {
+ return abstractValue;
+ }
+
+ public DynamicType getDynamicType() {
+ return dynamicType;
+ }
+
+ @Override
public ConcreteParameterStateKind getKind() {
return ConcreteParameterStateKind.CLASS;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMethodState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMethodState.java
index 146d321..6aae75f 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMethodState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMethodState.java
@@ -11,6 +11,11 @@
public abstract class ConcreteMethodState extends MethodStateBase {
@Override
+ public boolean isConcrete() {
+ return true;
+ }
+
+ @Override
public ConcreteMethodState asConcrete() {
return this;
}
@@ -24,15 +29,22 @@
}
@Override
- public MethodState mutableJoin(
- AppView<AppInfoWithLiveness> appView, Supplier<MethodState> methodStateSupplier) {
- MethodState methodState = methodStateSupplier.get();
+ public MethodState mutableJoin(AppView<AppInfoWithLiveness> appView, MethodState methodState) {
+ if (methodState.isBottom()) {
+ return this;
+ }
if (methodState.isUnknown()) {
return methodState;
}
return mutableJoin(appView, methodState.asConcrete());
}
+ @Override
+ public MethodState mutableJoin(
+ AppView<AppInfoWithLiveness> appView, Supplier<MethodState> methodStateSupplier) {
+ return mutableJoin(appView, methodStateSupplier.get());
+ }
+
private MethodState mutableJoin(
AppView<AppInfoWithLiveness> appView, ConcreteMethodState methodState) {
if (isMonomorphic() && methodState.isMonomorphic()) {
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMonomorphicMethodState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMonomorphicMethodState.java
index 99609ac..c93f4cf 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMonomorphicMethodState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteMonomorphicMethodState.java
@@ -20,6 +20,10 @@
this.parameterStates = parameterStates;
}
+ public ParameterState getParameterState(int index) {
+ return parameterStates.get(index);
+ }
+
public ConcreteMonomorphicMethodStateOrUnknown mutableJoin(
AppView<AppInfoWithLiveness> appView, ConcreteMonomorphicMethodState methodState) {
if (size() != methodState.size()) {
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePolymorphicMethodState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePolymorphicMethodState.java
index bcb3d28..2e5a908 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePolymorphicMethodState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePolymorphicMethodState.java
@@ -9,6 +9,7 @@
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import java.util.HashMap;
import java.util.Map;
+import java.util.function.BiConsumer;
public class ConcretePolymorphicMethodState extends ConcreteMethodState {
@@ -22,6 +23,10 @@
receiverBoundsToState.put(receiverBounds, methodState);
}
+ public void forEach(BiConsumer<DynamicType, MethodState> consumer) {
+ receiverBoundsToState.forEach(consumer);
+ }
+
public boolean isEmpty() {
return receiverBoundsToState.isEmpty();
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePrimitiveTypeParameterState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePrimitiveTypeParameterState.java
index a10d24b..dc50932 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePrimitiveTypeParameterState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcretePrimitiveTypeParameterState.java
@@ -43,6 +43,11 @@
}
@Override
+ public AbstractValue getAbstractValue() {
+ return abstractValue;
+ }
+
+ @Override
public ConcreteParameterStateKind getKind() {
return ConcreteParameterStateKind.PRIMITIVE;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteReceiverParameterState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteReceiverParameterState.java
index 2af7b04..9a529b2 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteReceiverParameterState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ConcreteReceiverParameterState.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.optimize.argumentpropagation.codescanner;
import com.android.tools.r8.ir.analysis.type.DynamicType;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
public class ConcreteReceiverParameterState extends ConcreteParameterState {
@@ -31,6 +32,15 @@
}
@Override
+ public AbstractValue getAbstractValue() {
+ return AbstractValue.unknown();
+ }
+
+ public DynamicType getDynamicType() {
+ return dynamicType;
+ }
+
+ @Override
public ConcreteParameterStateKind getKind() {
return ConcreteParameterStateKind.RECEIVER;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodState.java
index ef56eed..5bc6049 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodState.java
@@ -10,10 +10,16 @@
public interface MethodState {
+ static BottomMethodState bottom() {
+ return BottomMethodState.get();
+ }
+
static UnknownMethodState unknown() {
return UnknownMethodState.get();
}
+ boolean isBottom();
+
boolean isConcrete();
ConcreteMethodState asConcrete();
@@ -24,6 +30,8 @@
boolean isUnknown();
+ MethodState mutableJoin(AppView<AppInfoWithLiveness> appView, MethodState methodState);
+
MethodState mutableJoin(
AppView<AppInfoWithLiveness> appView, Supplier<MethodState> methodStateSupplier);
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateBase.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateBase.java
index d102f6a..936210f 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateBase.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateBase.java
@@ -6,11 +6,20 @@
public abstract class MethodStateBase implements MethodState {
+ public static BottomMethodState bottom() {
+ return BottomMethodState.get();
+ }
+
public static UnknownMethodState unknown() {
return UnknownMethodState.get();
}
@Override
+ public boolean isBottom() {
+ return false;
+ }
+
+ @Override
public boolean isConcrete() {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateCollection.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateCollection.java
index f8eacd3..10e9573 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateCollection.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/MethodStateCollection.java
@@ -30,6 +30,22 @@
return new MethodStateCollection(new ConcurrentHashMap<>());
}
+ public void addMethodState(
+ AppView<AppInfoWithLiveness> appView, DexMethod method, MethodState methodState) {
+ if (methodState.isUnknown()) {
+ methodStates.put(method, methodState);
+ } else {
+ methodStates.compute(
+ method,
+ (ignore, existingMethodState) -> {
+ if (existingMethodState == null) {
+ return methodState;
+ }
+ return existingMethodState.mutableJoin(appView, methodState);
+ });
+ }
+ }
+
/**
* This intentionally takes a {@link Supplier<MethodState>} to avoid computing the method state
* for a given call site when nothing is known about the arguments of the method.
@@ -58,6 +74,11 @@
}
public MethodState get(ProgramMethod method) {
- return methodStates.get(method.getReference());
+ return methodStates.getOrDefault(method.getReference(), MethodState.bottom());
+ }
+
+ public MethodState remove(ProgramMethod method) {
+ MethodState removed = methodStates.remove(method.getReference());
+ return removed != null ? removed : MethodState.bottom();
}
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ParameterState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ParameterState.java
index 30953db..8f759cf 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ParameterState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/ParameterState.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.optimize.argumentpropagation.codescanner;
import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
public abstract class ParameterState {
@@ -13,6 +14,8 @@
return UnknownParameterState.get();
}
+ public abstract AbstractValue getAbstractValue();
+
public boolean isConcrete() {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownMethodState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownMethodState.java
index 815a97d..1cfe728 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownMethodState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownMethodState.java
@@ -26,6 +26,11 @@
}
@Override
+ public MethodState mutableJoin(AppView<AppInfoWithLiveness> appView, MethodState methodState) {
+ return this;
+ }
+
+ @Override
public MethodState mutableJoin(
AppView<AppInfoWithLiveness> appView, Supplier<MethodState> methodStateSupplier) {
return this;
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownParameterState.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownParameterState.java
index 5bd3156..8993b5c 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownParameterState.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/UnknownParameterState.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.optimize.argumentpropagation.codescanner;
import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
public class UnknownParameterState extends ParameterState {
@@ -18,6 +19,11 @@
}
@Override
+ public AbstractValue getAbstractValue() {
+ return AbstractValue.unknown();
+ }
+
+ @Override
public boolean isUnknown() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
index 844e000..a1ac738 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
@@ -103,7 +103,7 @@
interfaceDefinition.forEachProgramVirtualMethod(
method -> {
MethodState methodState = methodStates.get(method);
- if (methodState == null) {
+ if (methodState.isBottom()) {
return;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
index a455566..0e51d66 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
@@ -5,18 +5,124 @@
package com.android.tools.r8.optimize.argumentpropagation.propagation;
import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
-import com.android.tools.r8.errors.Unimplemented;
import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
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.ProgramMethod;
+import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
+import com.android.tools.r8.ir.analysis.type.DynamicType;
+import com.android.tools.r8.ir.optimize.info.ConcreteCallSiteOptimizationInfo;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcreteMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.ConcretePolymorphicMethodState;
+import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodState;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollection;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import java.util.HashMap;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Set;
import java.util.function.Consumer;
+import java.util.stream.Collectors;
public class VirtualDispatchMethodArgumentPropagator extends MethodArgumentPropagator {
+ class PropagationState {
+
+ // Argument information for virtual methods that must be propagated to all overrides (i.e., this
+ // information does not have a lower bound).
+ final MethodStateCollection active = MethodStateCollection.create();
+
+ // Argument information for virtual methods that must be propagated to all overrides that are
+ // above the given lower bound.
+ final Map<DexType, MethodStateCollection> activeUntilLowerBound = new IdentityHashMap<>();
+
+ // Argument information for virtual methods that is currently inactive, but should be propagated
+ // to all overrides below a given upper bound.
+ final Map<DynamicType, MethodStateCollection> inactiveUntilUpperBound = new HashMap<>();
+
+ PropagationState(DexProgramClass clazz) {
+ // Join the argument information from each of the super types.
+ immediateSubtypingInfo.forEachImmediateSuperClassMatching(
+ clazz,
+ (supertype, superclass) -> superclass != null && superclass.isProgramClass(),
+ (supertype, superclass) -> addParentState(clazz, superclass.asProgramClass()));
+ }
+
+ // TODO(b/190154391): This currently copies the state of the superclass into its immediate
+ // given subclass. Instead of copying the state, consider linking the states. This would reduce
+ // memory usage, but would require visiting all transitive (program) super classes for each
+ // subclass.
+ private void addParentState(DexProgramClass clazz, DexProgramClass superclass) {
+ PropagationState parentState = propagationStates.get(superclass.asProgramClass());
+ assert parentState != null;
+
+ // Add the argument information that must be propagated to all method overrides.
+ active.addMethodStates(appView, parentState.active);
+
+ // Add the argument information that is active until a given lower bound.
+ parentState.activeUntilLowerBound.forEach(
+ (lowerBound, activeMethodState) -> {
+ if (lowerBound != superclass.getType()) {
+ // TODO(b/190154391): Verify that the lower bound is a subtype of the current.
+ // Otherwise we carry this information to all subtypes although there is no need to.
+ activeUntilLowerBound
+ .computeIfAbsent(lowerBound, ignoreKey(MethodStateCollection::create))
+ .addMethodStates(appView, activeMethodState);
+ } else {
+ // No longer active.
+ }
+ });
+
+ // Add the argument information that is inactive until a given upper bound.
+ parentState.inactiveUntilUpperBound.forEach(
+ (bounds, inactiveMethodState) -> {
+ ClassTypeElement upperBound = bounds.getDynamicUpperBoundType().asClassType();
+ if (upperBound.getClassType() == clazz.getType()) {
+ // The upper bound is the current class, thus this inactive information now becomes
+ // active.
+ if (bounds.hasDynamicLowerBoundType()) {
+ activeUntilLowerBound
+ .computeIfAbsent(
+ bounds.getDynamicLowerBoundType().getClassType(),
+ ignoreKey(MethodStateCollection::create))
+ .addMethodStates(appView, inactiveMethodState);
+ } else {
+ active.addMethodStates(appView, inactiveMethodState);
+ }
+ } else {
+ // Still inactive.
+ // TODO(b/190154391): Only carry this information downwards if the upper bound is a
+ // subtype of this class. Otherwise we carry this information to all subtypes,
+ // although clearly the information will never become active.
+ inactiveUntilUpperBound
+ .computeIfAbsent(bounds, ignoreKey(MethodStateCollection::create))
+ .addMethodStates(appView, inactiveMethodState);
+ }
+ });
+ }
+
+ private MethodState computeMethodStateForPolymorhicMethod(ProgramMethod method) {
+ assert method.getDefinition().isNonPrivateVirtualMethod();
+ MethodState methodState = active.get(method);
+ for (MethodStateCollection methodStates : activeUntilLowerBound.values()) {
+ methodState = methodState.mutableJoin(appView, methodStates.get(method));
+ }
+ return methodState;
+ }
+ }
+
+ // For each class, stores the argument information for each virtual method on this class and all
+ // direct and indirect super classes.
+ //
+ // This data structure is populated during a top-down traversal over the class hierarchy, such
+ // that entries in the map can be removed when the top-down traversal has visited all subtypes of
+ // a given node.
+ final Map<DexProgramClass, PropagationState> propagationStates = new IdentityHashMap<>();
+
public VirtualDispatchMethodArgumentPropagator(
AppView<AppInfoWithLiveness> appView,
ImmediateProgramSubtypingInfo immediateSubtypingInfo,
@@ -25,6 +131,13 @@
}
@Override
+ public void run(Set<DexProgramClass> stronglyConnectedComponent) {
+ super.run(stronglyConnectedComponent);
+ assert verifyAllClassesFinished(stronglyConnectedComponent);
+ assert verifyStatePruned(stronglyConnectedComponent);
+ }
+
+ @Override
public void forEachSubClass(DexProgramClass clazz, Consumer<DexProgramClass> consumer) {
immediateSubtypingInfo.getSubclasses(clazz).forEach(consumer);
}
@@ -47,11 +160,137 @@
@Override
public void visit(DexProgramClass clazz) {
- throw new Unimplemented();
+ assert !propagationStates.containsKey(clazz);
+ PropagationState propagationState = computePropagationState(clazz);
+ setOptimizationInfo(clazz, propagationState);
+ }
+
+ private PropagationState computePropagationState(DexProgramClass clazz) {
+ PropagationState propagationState = new PropagationState(clazz);
+
+ // Join the argument information from the methods of the current class.
+ clazz.forEachProgramVirtualMethod(
+ method -> {
+ MethodState methodState = methodStates.get(method);
+ if (methodState.isBottom()) {
+ return;
+ }
+
+ // TODO(b/190154391): Add an unknown polymorphic method state, such that we can
+ // distinguish monomorphic unknown method states from polymorphic unknown method states.
+ // We only need to propagate polymorphic unknown method states here.
+ if (methodState.isUnknown()) {
+ propagationState.active.addMethodState(appView, method.getReference(), methodState);
+ return;
+ }
+
+ ConcreteMethodState concreteMethodState = methodState.asConcrete();
+ if (concreteMethodState.isMonomorphic()) {
+ // No need to propagate information for methods that do not override other methods and
+ // are not themselves overridden.
+ return;
+ }
+
+ ConcretePolymorphicMethodState polymorphicMethodState =
+ concreteMethodState.asPolymorphic();
+ polymorphicMethodState.forEach(
+ (bounds, methodStateForBounds) -> {
+ if (bounds.isUnknown()) {
+ propagationState.active.addMethodState(
+ appView, method.getReference(), methodStateForBounds);
+ } else {
+ // TODO(b/190154391): Verify that the bounds are not trivial according to the
+ // static receiver type.
+ ClassTypeElement upperBound = bounds.getDynamicUpperBoundType().asClassType();
+ if (upperBound.getClassType() == clazz.getType()) {
+ if (bounds.hasDynamicLowerBoundType()) {
+ // TODO(b/190154391): Verify that the lower bound is a subtype of the current
+ // class.
+ propagationState
+ .activeUntilLowerBound
+ .computeIfAbsent(
+ bounds.getDynamicLowerBoundType().getClassType(),
+ ignoreKey(MethodStateCollection::create))
+ .addMethodState(appView, method.getReference(), methodStateForBounds);
+ } else {
+ propagationState.active.addMethodState(
+ appView, method.getReference(), methodStateForBounds);
+ }
+ } else {
+ assert !appView.appInfo().isSubtype(clazz.getType(), upperBound.getClassType());
+ propagationState
+ .inactiveUntilUpperBound
+ .computeIfAbsent(bounds, ignoreKey(MethodStateCollection::create))
+ .addMethodState(appView, method.getReference(), methodStateForBounds);
+ }
+ }
+ });
+ });
+
+ propagationStates.put(clazz, propagationState);
+ return propagationState;
+ }
+
+ private void setOptimizationInfo(DexProgramClass clazz, PropagationState propagationState) {
+ clazz.forEachProgramMethod(method -> setOptimizationInfo(method, propagationState));
+ }
+
+ private void setOptimizationInfo(ProgramMethod method, PropagationState propagationState) {
+ MethodState methodState = methodStates.remove(method);
+
+ // If this is a polymorphic method, we need to compute the method state to account for dynamic
+ // dispatch.
+ if (methodState.isConcrete() && methodState.asConcrete().isPolymorphic()) {
+ methodState = propagationState.computeMethodStateForPolymorhicMethod(method);
+ }
+
+ if (methodState.isBottom()) {
+ // TODO(b/190154391): This should only happen if the method is never called. Consider removing
+ // the method in this case.
+ return;
+ }
+
+ if (methodState.isUnknown()) {
+ // Nothing is known about the arguments to this method.
+ return;
+ }
+
+ ConcreteMethodState concreteMethodState = methodState.asConcrete();
+ if (concreteMethodState.isPolymorphic()) {
+ assert false;
+ return;
+ }
+
+ // TODO(b/190154391): We need to resolve the flow constraints before this is guaranteed to be
+ // sound.
+ method
+ .getDefinition()
+ .joinCallSiteOptimizationInfo(
+ ConcreteCallSiteOptimizationInfo.fromMethodState(
+ appView, method, concreteMethodState.asMonomorphic()),
+ appView);
}
@Override
public void prune(DexProgramClass clazz) {
- throw new Unimplemented();
+ propagationStates.remove(clazz);
+ }
+
+ private boolean verifyAllClassesFinished(Set<DexProgramClass> stronglyConnectedComponent) {
+ for (DexProgramClass clazz : stronglyConnectedComponent) {
+ assert isClassFinished(clazz);
+ }
+ return true;
+ }
+
+ private boolean verifyStatePruned(Set<DexProgramClass> stronglyConnectedComponent) {
+ Set<DexType> types =
+ stronglyConnectedComponent.stream().map(DexClass::getType).collect(Collectors.toSet());
+ methodStates.forEach(
+ (method, methodState) -> {
+ assert !types.contains(method.getHolderType());
+ });
+ assert propagationStates.isEmpty();
+ return true;
}
}
