Canonicalize calls with no side effects and deterministic outputs.
Bug: 132123953
Change-Id: Iaaba650149eb95864c69d59342015aad729ce02d
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index add6578..a3a329e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -1008,6 +1008,7 @@
public static boolean UNKNOWN_INITIALIZER_ENABLING_JAVA_ASSERTIONS = false;
public static ParameterUsagesInfo UNKNOWN_PARAMETER_USAGE_INFO = null;
public static boolean UNKNOWN_MAY_HAVE_SIDE_EFFECTS = true;
+ public static boolean UNKNOWN_RETURN_VALUE_ONLY_DEPENDS_ON_ARGUMENTS = false;
public static BitSet NO_NULL_PARAMETER_OR_THROW_FACTS = null;
public static BitSet NO_NULL_PARAMETER_ON_NORMAL_EXITS_FACTS = null;
@@ -1143,6 +1144,11 @@
}
@Override
+ public boolean returnValueOnlyDependsOnArguments() {
+ return UNKNOWN_RETURN_VALUE_ONLY_DEPENDS_ON_ARGUMENTS;
+ }
+
+ @Override
public boolean returnValueHasBeenPropagated() {
return false;
}
@@ -1161,6 +1167,8 @@
private int returnedArgument = DefaultMethodOptimizationInfoImpl.UNKNOWN_RETURNED_ARGUMENT;
private boolean mayHaveSideEffects =
DefaultMethodOptimizationInfoImpl.UNKNOWN_MAY_HAVE_SIDE_EFFECTS;
+ private boolean returnValueOnlyDependsOnArguments =
+ DefaultMethodOptimizationInfoImpl.UNKNOWN_RETURN_VALUE_ONLY_DEPENDS_ON_ARGUMENTS;
private boolean neverReturnsNull = DefaultMethodOptimizationInfoImpl.UNKNOWN_NEVER_RETURNS_NULL;
private boolean neverReturnsNormally =
DefaultMethodOptimizationInfoImpl.UNKNOWN_NEVER_RETURNS_NORMALLY;
@@ -1369,6 +1377,11 @@
}
@Override
+ public boolean returnValueOnlyDependsOnArguments() {
+ return returnValueOnlyDependsOnArguments;
+ }
+
+ @Override
public void setParameterUsages(ParameterUsagesInfo parametersUsages) {
this.parametersUsages = parametersUsages;
}
@@ -1421,6 +1434,11 @@
}
@Override
+ public void markReturnValueOnlyDependsOnArguments() {
+ returnValueOnlyDependsOnArguments = true;
+ }
+
+ @Override
public void markNeverReturnsNull() {
neverReturnsNull = true;
}
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index cb9d725..d5ebf00 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -47,6 +47,7 @@
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Consumer;
import java.util.function.Function;
+import java.util.stream.Collectors;
public class DexItemFactory {
@@ -94,6 +95,8 @@
public DexItemFactory() {
this.kotlin = new Kotlin(this);
+ assert libraryMethodsWithoutSideEffects
+ .containsAll(libraryMethodsWithReturnValueDependingOnlyOnArguments);
}
public static boolean isInternalSentinel(DexItem item) {
@@ -349,6 +352,43 @@
public final ServiceLoaderMethods serviceLoaderMethods = new ServiceLoaderMethods();
+ public final BiMap<DexType, DexType> primitiveToBoxed = HashBiMap.create(
+ ImmutableMap.<DexType, DexType>builder()
+ .put(booleanType, boxedBooleanType)
+ .put(byteType, boxedByteType)
+ .put(charType, boxedCharType)
+ .put(shortType, boxedShortType)
+ .put(intType, boxedIntType)
+ .put(longType, boxedLongType)
+ .put(floatType, boxedFloatType)
+ .put(doubleType, boxedDoubleType)
+ .build());
+
+ public DexType getBoxedForPrimitiveType(DexType primitive) {
+ assert primitive.isPrimitiveType();
+ return primitiveToBoxed.get(primitive);
+ }
+
+ public DexType getPrimitiveFromBoxed(DexType boxedPrimitive) {
+ return primitiveToBoxed.inverse().get(boxedPrimitive);
+ }
+
+ // Boxed Boxed#valueOf(Primitive), e.g., Boolean Boolean#valueOf(B)
+ private Set<DexMethod> boxedValueOfMethods() {
+ return primitiveToBoxed.entrySet().stream()
+ .map(
+ entry -> {
+ DexType primitive = entry.getKey();
+ DexType boxed = entry.getValue();
+ return createMethod(
+ boxed.descriptor,
+ valueOfMethodName,
+ boxed.descriptor,
+ new DexString[] {primitive.descriptor});
+ })
+ .collect(Collectors.toSet());
+ }
+
public final DexMethod metafactoryMethod =
createMethod(
metafactoryType,
@@ -414,6 +454,18 @@
.addAll(classMethods.getNames)
.addAll(stringBufferMethods.constructorMethods)
.addAll(stringBuilderMethods.constructorMethods)
+ .addAll(boxedValueOfMethods())
+ .build();
+
+ // TODO(b/119596718): More idempotent methods? Any singleton accessors? E.g.,
+ // java.util.Calendar#getInstance(...) // 4 variants
+ // java.util.Locale#getDefault() // returns JVM default locale.
+ // android.os.Looper#myLooper() // returns the associated Looper instance.
+ // Note that this set is used for canonicalization of method invocations, together with a set of
+ // library methods that do not have side effects.
+ public Set<DexMethod> libraryMethodsWithReturnValueDependingOnlyOnArguments =
+ ImmutableSet.<DexMethod>builder()
+ .addAll(boxedValueOfMethods())
.build();
public Set<DexType> libraryTypesAssumedToBePresent =
@@ -436,27 +488,6 @@
return dexMethod == metafactoryMethod || dexMethod == metafactoryAltMethod;
}
- public final BiMap<DexType, DexType> primitiveToBoxed = HashBiMap.create(
- ImmutableMap.<DexType, DexType>builder()
- .put(booleanType, boxedBooleanType)
- .put(byteType, boxedByteType)
- .put(charType, boxedCharType)
- .put(shortType, boxedShortType)
- .put(intType, boxedIntType)
- .put(longType, boxedLongType)
- .put(floatType, boxedFloatType)
- .put(doubleType, boxedDoubleType)
- .build());
-
- public DexType getBoxedForPrimitiveType(DexType primitive) {
- assert primitive.isPrimitiveType();
- return primitiveToBoxed.get(primitive);
- }
-
- public DexType getPrimitiveFromBoxed(DexType boxedPrimitive) {
- return primitiveToBoxed.inverse().get(boxedPrimitive);
- }
-
public class LongMethods {
public final DexMethod compare;
diff --git a/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java b/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java
index 213bb11..108779c 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodOptimizationInfo.java
@@ -69,6 +69,8 @@
boolean mayHaveSideEffects();
+ boolean returnValueOnlyDependsOnArguments();
+
boolean returnValueHasBeenPropagated();
UpdatableMethodOptimizationInfo mutableCopy();
diff --git a/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java b/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java
index 5791733..da39812 100644
--- a/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/UpdatableMethodOptimizationInfo.java
@@ -28,6 +28,8 @@
void markMayNotHaveSideEffects();
+ void markReturnValueOnlyDependsOnArguments();
+
void markNeverReturnsNull();
void markNeverReturnsNormally();
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/DeterminismAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/DeterminismAnalysis.java
new file mode 100644
index 0000000..b8e6950
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/DeterminismAnalysis.java
@@ -0,0 +1,73 @@
+// Copyright (c) 2019, 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.ir.analysis;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+
+// Determine whether the given method generates the deterministic output for the given same input.
+// For now, this analysis is very conservative in the sense that it only allows methods that depend
+// on arguments. To that end, the followings are not allowed.
+// 1) any non-argument access, e.g., static-get, may result in different outputs.
+// 2) even for argument access, states of instance or array can be different in any way.
+// 3) if the current method invokes another method that is not deterministic, neither is it.
+public class DeterminismAnalysis {
+
+ public static boolean returnValueOnlyDependsOnArguments(
+ AppView<AppInfoWithLiveness> appView, IRCode code) {
+ for (Instruction instr : code.instructions()) {
+ if (instr.outValue() == null || !instr.outValue().isUsed()) {
+ continue;
+ }
+ if (instr.isStaticGet()) {
+ // Unless we model the heap and take into account the snapshot per call site.
+ return false;
+ }
+ if (instr.isInstanceGet()) {
+ // Unless we trace the state of the instance.
+ return false;
+ }
+ if (instr.isArrayGet() || instr.isArrayLength()) {
+ // Unless we trace the state of the array.
+ return false;
+ }
+ if (instr.isInvokeMethod()) {
+ DexEncodedMethod target =
+ instr.asInvokeMethod().lookupSingleTarget(appView, code.method.method.holder);
+ if (target != null && target.getOptimizationInfo().returnValueOnlyDependsOnArguments()) {
+ continue;
+ }
+ return false;
+ }
+ if (instr.isInvokeCustom() || instr.isInvokePolymorphic()) {
+ // Unless we can nail down the single target for these invocations.
+ return false;
+ }
+ if (instr.isCreatingInstanceOrArray()) {
+ // Unless we determine the new instance/array is local.
+ return false;
+ }
+ if (instr.isMoveException()) {
+ return false;
+ }
+ // isArrayPut and isFieldPut are missed as they don't have out value.
+ assert instr.isArgument()
+ || instr.isAssume()
+ || instr.isBinop()
+ || instr.isUnop()
+ || instr.isMonitor()
+ || instr.isMove()
+ || instr.isCheckCast()
+ || instr.isInstanceOf()
+ || instr.isConstInstruction()
+ || instr.isJumpInstruction()
+ || instr.isDebugInstruction()
+ : "Instruction that impacts determinism: " + instr;
+ }
+ return true;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index cc54a60..e6249ff 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -1014,4 +1014,27 @@
}
}
}
+
+ public Position findFirstNonNonePosition() {
+ Instruction rightAfterArguments =
+ entryBlock().listIterator().nextUntil(instr -> !instr.isArgument());
+ Position firstNonArgumentPosition = rightAfterArguments.getPosition();
+ Set<BasicBlock> visitedBlocks = new HashSet<>();
+ while (rightAfterArguments != null) {
+ // Make sure we are not looping.
+ if (visitedBlocks.contains(rightAfterArguments.getBlock())) {
+ break;
+ }
+ visitedBlocks.add(rightAfterArguments.getBlock());
+ // The very first non-argument instruction can be chained via goto.
+ if (rightAfterArguments.isGoto()) {
+ rightAfterArguments = rightAfterArguments.asGoto().getTarget().getInstructions().getFirst();
+ } else if (rightAfterArguments.getPosition().isSome()) {
+ return rightAfterArguments.getPosition();
+ } else {
+ break;
+ }
+ }
+ return firstNonArgumentPosition;
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index e1863b2..dbdc2dc 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -26,6 +26,7 @@
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.DexTypeList;
import com.android.tools.r8.graph.GraphLense;
+import com.android.tools.r8.ir.analysis.DeterminismAnalysis;
import com.android.tools.r8.ir.analysis.InitializedClassesOnNormalExitAnalysis;
import com.android.tools.r8.ir.analysis.TypeChecker;
import com.android.tools.r8.ir.analysis.constant.SparseConditionalConstantPropagation;
@@ -245,8 +246,7 @@
options.enableNestBasedAccessDesugaring ? new D8NestBasedAccessDesugaring(appView) : null;
}
this.deadCodeRemover = new DeadCodeRemover(appView, codeRewriter);
- this.idempotentFunctionCallCanonicalizer =
- new IdempotentFunctionCallCanonicalizer(appView.dexItemFactory());
+ this.idempotentFunctionCallCanonicalizer = new IdempotentFunctionCallCanonicalizer(appView);
}
public Set<DexCallSite> getDesugaredCallSites() {
@@ -612,6 +612,9 @@
}
if (Log.ENABLED) {
+ if (idempotentFunctionCallCanonicalizer != null) {
+ idempotentFunctionCallCanonicalizer.logResults();
+ }
if (libraryMethodOverrideAnalysis != null) {
libraryMethodOverrideAnalysis.logResults();
}
@@ -1157,6 +1160,7 @@
computeDynamicReturnType(feedback, method, code);
computeInitializedClassesOnNormalExit(feedback, method, code);
computeMayHaveSideEffects(feedback, method, code);
+ computeReturnValueOnlyDependsOnArguments(feedback, method, code);
computeNonNullParamOrThrow(feedback, method, code);
}
}
@@ -1295,11 +1299,25 @@
instruction ->
instruction.instructionMayHaveSideEffects(appView, method.method.holder));
if (!mayHaveSideEffects) {
+ // If the method is native, we don't know what could happen.
+ assert !method.accessFlags.isNative();
feedback.methodMayNotHaveSideEffects(method);
}
}
}
+ private void computeReturnValueOnlyDependsOnArguments(
+ OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
+ if (!options.enableDeterminismAnalysis) {
+ return;
+ }
+ boolean returnValueOnlyDependsOnArguments =
+ DeterminismAnalysis.returnValueOnlyDependsOnArguments(appView.withLiveness(), code);
+ if (returnValueOnlyDependsOnArguments) {
+ feedback.methodReturnValueOnlyDependsOnArguments(method);
+ }
+ }
+
// Returns true if `method` is an initializer and the enclosing class overrides the method
// `void java.lang.Object.finalize()`.
private boolean hasNonTrivialFinalizeMethod(DexType type) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
index bf7e94f..752f35e 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
@@ -32,6 +32,8 @@
void methodMayNotHaveSideEffects(DexEncodedMethod method);
+ void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method);
+
void methodNeverReturnsNull(DexEncodedMethod method);
void methodNeverReturnsNormally(DexEncodedMethod method);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
index 4ca780d..82f6391 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
@@ -85,6 +85,11 @@
}
@Override
+ public synchronized void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method) {
+ getOptimizationInfoForUpdating(method).markReturnValueOnlyDependsOnArguments();
+ }
+
+ @Override
public synchronized void markAsPropagated(DexEncodedMethod method) {
getOptimizationInfoForUpdating(method).markAsPropagated();
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
index 7eb3549..c0655df 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
@@ -48,6 +48,9 @@
public void methodMayNotHaveSideEffects(DexEncodedMethod method) {}
@Override
+ public void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method) {}
+
+ @Override
public void methodNeverReturnsNull(DexEncodedMethod method) {}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
index 44639e3..1fc7a91 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
@@ -54,6 +54,11 @@
}
@Override
+ public void methodReturnValueOnlyDependsOnArguments(DexEncodedMethod method) {
+ // Ignored.
+ }
+
+ @Override
public void methodNeverReturnsNull(DexEncodedMethod method) {
// Ignored.
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
index 085137f..3ff6074 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
@@ -18,15 +18,13 @@
import it.unimi.dsi.fastutil.objects.Object2ObjectLinkedOpenCustomHashMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectSortedMap.FastSortedEntrySet;
import java.util.ArrayList;
-import java.util.HashSet;
import java.util.List;
-import java.util.Set;
/**
* Canonicalize constants.
*/
public class ConstantCanonicalizer {
-
+ // Threshold to limit the number of constant canonicalization.
private static final int MAX_CANONICALIZED_CONSTANT = 15;
public static void canonicalize(AppView<?> appView, IRCode code) {
@@ -104,7 +102,7 @@
// Double-check the entry block does not have catch handlers.
// Otherwise, we need to split it before moving canonicalized const-string, which may throw.
assert !code.entryBlock().hasCatchHandlers();
- Position firstNonNonePosition = findFirstNonNonePosition(code);
+ final Position firstNonNonePosition = code.findFirstNonNonePosition();
FastSortedEntrySet<ConstInstruction, List<Value>> entries =
valuesDefinedByConstant.object2ObjectEntrySet();
// Sort the most frequently used constant first and exclude constant use only one time, such
@@ -156,30 +154,6 @@
it.add(canonicalizedConstant);
}
- private static Position findFirstNonNonePosition(IRCode code) {
- BasicBlock entryBlock = code.entryBlock();
- Instruction rightAfterArguments =
- entryBlock.listIterator().nextUntil(instr -> !instr.isArgument());
- Position firstNonArgumentPosition = rightAfterArguments.getPosition();
- Set<BasicBlock> visitedBlocks = new HashSet<>();
- while (rightAfterArguments != null) {
- // Make sure we are not looping.
- if (visitedBlocks.contains(rightAfterArguments.getBlock())) {
- break;
- }
- visitedBlocks.add(rightAfterArguments.getBlock());
- // The very first non-argument instruction can be chained via goto.
- if (rightAfterArguments.isGoto()) {
- rightAfterArguments = rightAfterArguments.asGoto().getTarget().getInstructions().getFirst();
- } else if (rightAfterArguments.getPosition().isSome()) {
- return rightAfterArguments.getPosition();
- } else {
- break;
- }
- }
- return firstNonArgumentPosition;
- }
-
private static boolean constantUsedByInvokeRange(ConstInstruction constant) {
for (Instruction user : constant.outValue().uniqueUsers()) {
if (user.isInvoke() && user.asInvoke().requiredArgumentRegisters() > 5) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java b/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java
index 2e31219..9b04a16 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizer.java
@@ -3,9 +3,12 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.optimize;
+import static com.android.tools.r8.optimize.MemberRebindingAnalysis.isMemberVisibleFromOriginalContext;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
@@ -13,17 +16,19 @@
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Invoke;
import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Value;
-import com.google.common.collect.ImmutableSet;
+import com.android.tools.r8.logging.Log;
+import com.android.tools.r8.utils.StringUtils;
import com.google.common.collect.Maps;
import it.unimi.dsi.fastutil.Hash.Strategy;
+import it.unimi.dsi.fastutil.objects.Object2IntArrayMap;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectLinkedOpenCustomHashMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectSortedMap.FastSortedEntrySet;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
-import java.util.Map.Entry;
-import java.util.Set;
/**
* Canonicalize idempotent function calls.
@@ -46,28 +51,36 @@
* // Update users of vx, vy, and vz.
*/
public class IdempotentFunctionCallCanonicalizer {
- private static final int MAX_CANONICALIZED_CALL = 7;
+ // Threshold to limit the number of invocation canonicalization.
+ private static final int MAX_CANONICALIZED_CALL = 15;
- private final Set<DexMethod> idempotentMethods;
+ private final AppView<?> appView;
+ private final DexItemFactory factory;
- public IdempotentFunctionCallCanonicalizer(DexItemFactory factory) {
- ImmutableSet.Builder<DexMethod> idempotentMethodsBuilder = ImmutableSet.builder();
- // Boxed Boxed#valueOf(Primitive), e.g., Boolean Boolean#valueOf(B)
- for (Entry<DexType, DexType> entry : factory.primitiveToBoxed.entrySet()) {
- DexType primitive = entry.getKey();
- DexType boxed = entry.getValue();
- idempotentMethodsBuilder.add(
- factory.createMethod(
- boxed.descriptor,
- factory.valueOfMethodName,
- boxed.descriptor,
- new DexString[] {primitive.descriptor}));
+ private int numberOfLibraryCallCanonicalization = 0;
+ private int numberOfProgramCallCanonicalization = 0;
+ private Object2IntMap<Long> histogramOfCanonicalizationCandidatesPerMethod = null;
+
+ public IdempotentFunctionCallCanonicalizer(AppView<?> appView) {
+ this.appView = appView;
+ this.factory = appView.dexItemFactory();
+ if (Log.ENABLED) {
+ histogramOfCanonicalizationCandidatesPerMethod = new Object2IntArrayMap<>();
}
- // TODO(b/119596718): More idempotent methods? Any singleton accessors? E.g.,
- // java.util.Calendar#getInstance(...) // 4 variants
- // java.util.Locale#getDefault() // returns JVM default locale.
- // android.os.Looper#myLooper() // returns the associated Looper instance.
- idempotentMethods = idempotentMethodsBuilder.build();
+ }
+
+ public void logResults() {
+ assert Log.ENABLED;
+ Log.info(getClass(),
+ "# invoke canonicalization (library): %s", numberOfLibraryCallCanonicalization);
+ Log.info(getClass(),
+ "# invoke canonicalization (program): %s", numberOfProgramCallCanonicalization);
+ assert histogramOfCanonicalizationCandidatesPerMethod != null;
+ Log.info(getClass(), "------ histogram of invoke canonicalization candidates ------");
+ histogramOfCanonicalizationCandidatesPerMethod.forEach((length, count) -> {
+ Log.info(getClass(),
+ "%s: %s (%s)", length, StringUtils.times("*", Math.min(count, 53)), count);
+ });
}
public void canonicalize(IRCode code) {
@@ -89,6 +102,7 @@
}
});
+ DexType context = code.method.method.holder;
// Collect invocations along with arguments.
for (BasicBlock block : code.blocks) {
InstructionListIterator it = block.listIterator();
@@ -98,10 +112,6 @@
continue;
}
InvokeMethod invoke = current.asInvokeMethod();
- // Interested in known-to-be idempotent method call.
- if (!idempotentMethods.contains(invoke.getInvokedMethod())) {
- continue;
- }
// If the out value of the current invocation is not used and removed, we don't care either.
if (invoke.outValue() == null) {
continue;
@@ -110,7 +120,36 @@
if (current.outValue().hasLocalInfo()) {
continue;
}
- assert !current.inValues().isEmpty();
+ DexMethod invokedMethod = invoke.getInvokedMethod();
+ // Interested in known-to-be idempotent methods.
+ if (!factory.libraryMethodsWithReturnValueDependingOnlyOnArguments.contains(invokedMethod)
+ || !factory.libraryMethodsWithoutSideEffects.contains(invokedMethod)) {
+ if (!appView.enableWholeProgramOptimizations()) {
+ // Give up in D8
+ continue;
+ }
+ assert appView.appInfo().hasLiveness();
+ // Check if the call has a single target; that target is side effect free; and
+ // that target's output depends only on arguments.
+ DexEncodedMethod target = invoke.lookupSingleTarget(appView.withLiveness(), context);
+ if (target == null
+ || target.getOptimizationInfo().mayHaveSideEffects()
+ || !target.getOptimizationInfo().returnValueOnlyDependsOnArguments()) {
+ continue;
+ }
+ // Verify that the target method is accessible in the current context.
+ if (!isMemberVisibleFromOriginalContext(
+ appView, context, target.method.holder, target.accessFlags)) {
+ continue;
+ }
+ // Check if the call could throw a NPE as a result of the receiver being null.
+ if (current.isInvokeMethodWithReceiver()) {
+ Value receiver = current.asInvokeMethodWithReceiver().getReceiver().getAliasedValue();
+ if (receiver.getTypeLattice().isNullable()) {
+ continue;
+ }
+ }
+ }
// TODO(b/119596718): Use dominant tree to extend it to non-canonicalized in values?
// For now, interested in inputs that are also canonicalized constants.
boolean invocationCanBeMovedToEntryBlock = true;
@@ -134,16 +173,32 @@
return;
}
+ // Double-check the entry block does not have catch handlers.
+ assert !code.entryBlock().hasCatchHandlers();
+
// InvokeMethod is not treated as dead code explicitly, i.e., cannot rely on dead code remover.
Map<InvokeMethod, Value> deadInvocations = Maps.newHashMap();
FastSortedEntrySet<InvokeMethod, List<Value>> entries = returnValues.object2ObjectEntrySet();
+ if (Log.ENABLED) {
+ Long numOfCandidates = entries.stream().filter(a -> a.getValue().size() > 1).count();
+ int count = histogramOfCanonicalizationCandidatesPerMethod.getOrDefault(numOfCandidates, 0);
+ histogramOfCanonicalizationCandidatesPerMethod.put(numOfCandidates, count + 1);
+ }
entries.stream()
.filter(a -> a.getValue().size() > 1)
.sorted((a, b) -> Integer.compare(b.getValue().size(), a.getValue().size()))
.limit(MAX_CANONICALIZED_CALL)
.forEach((entry) -> {
InvokeMethod invoke = entry.getKey();
+ if (Log.ENABLED) {
+ if (factory.libraryMethodsWithReturnValueDependingOnlyOnArguments
+ .contains(invoke.getInvokedMethod())) {
+ numberOfLibraryCallCanonicalization += entry.getValue().size() - 1;
+ } else {
+ numberOfProgramCallCanonicalization += entry.getValue().size() - 1;
+ }
+ }
Value canonicalizedValue = code.createValue(
invoke.outValue().getTypeLattice(), invoke.outValue().getLocalInfo());
Invoke canonicalizedInvoke =
@@ -153,7 +208,16 @@
null,
canonicalizedValue,
invoke.inValues());
- insertCanonicalizedInvoke(code, canonicalizedInvoke);
+ // Note that it is fine to use any position, since the invoke has no side effects, which
+ // is guaranteed not to throw. That is, we will never have a stack trace with this call.
+ // Nonetheless, here we pick the position of the very first invocation.
+ Position firstInvocationPosition = entry.getValue().get(0).definition.getPosition();
+ canonicalizedInvoke.setPosition(firstInvocationPosition);
+ if (invoke.inValues().size() > 0) {
+ insertCanonicalizedInvokeWithInValues(code, canonicalizedInvoke);
+ } else {
+ insertCanonicalizedInvokeWithoutInValues(code, canonicalizedInvoke);
+ }
for (Value oldOutValue : entry.getValue()) {
deadInvocations.put(oldOutValue.definition.asInvokeMethod(), canonicalizedValue);
}
@@ -182,7 +246,8 @@
assert code.isConsistentSSA();
}
- private static void insertCanonicalizedInvoke(IRCode code, Invoke canonicalizedInvoke) {
+ private static void insertCanonicalizedInvokeWithInValues(
+ IRCode code, Invoke canonicalizedInvoke) {
BasicBlock entryBlock = code.entryBlock();
// Insert the canonicalized invoke after in values.
int numberOfInValuePassed = 0;
@@ -193,7 +258,26 @@
numberOfInValuePassed++;
}
if (numberOfInValuePassed == canonicalizedInvoke.inValues().size()) {
- canonicalizedInvoke.setPosition(current.getPosition());
+ // If this invocation uses arguments and this iteration ends in the middle of Arguments,
+ // proceed further so that Arguments can be packed first (as per entry block's properties).
+ if (it.hasNext() && it.peekNext().isArgument()) {
+ it.nextUntil(instr -> !instr.isArgument());
+ }
+ break;
+ }
+ }
+ it.add(canonicalizedInvoke);
+ }
+
+ private static void insertCanonicalizedInvokeWithoutInValues(
+ IRCode code, Invoke canonicalizedInvoke) {
+ BasicBlock entryBlock = code.entryBlock();
+ // Insert the canonicalized invocation at the start of the block right after the argument
+ // instructions.
+ InstructionListIterator it = entryBlock.listIterator();
+ while (it.hasNext()) {
+ if (!it.next().isArgument()) {
+ it.previous();
break;
}
}
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 0964666..b456b95 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -163,6 +163,7 @@
public boolean enableClassStaticizer = true;
public boolean enableInitializedClassesAnalysis = true;
public boolean enableSideEffectAnalysis = true;
+ public boolean enableDeterminismAnalysis = true;
public boolean enableServiceLoaderRewriting = true;
// TODO(b/120138731): Enable this when it is worthwhile, e.g., combined with Class#forName.
public boolean enableNameReflectionOptimization = false;
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/DeterminismAnalysisTest.java b/src/test/java/com/android/tools/r8/ir/analysis/DeterminismAnalysisTest.java
new file mode 100644
index 0000000..1ea789d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/DeterminismAnalysisTest.java
@@ -0,0 +1,99 @@
+// Copyright (c) 2019, 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.ir.analysis;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.ir.code.IRCode;
+import java.util.function.Consumer;
+import org.junit.Test;
+
+public class DeterminismAnalysisTest extends AnalysisTestBase {
+
+ public DeterminismAnalysisTest() throws Exception {
+ super(TestClass.class.getTypeName(), TestClass.class);
+ }
+
+ @Test
+ public void testMax() throws Exception {
+ buildAndCheckIR("max", checkAnalysisResult(true));
+ }
+
+ @Test
+ public void testSget() throws Exception {
+ buildAndCheckIR("sget", checkAnalysisResult(false));
+ }
+
+ @Test
+ public void testIget() throws Exception {
+ buildAndCheckIR("iget", checkAnalysisResult(false));
+ }
+
+ @Test
+ public void testAget() throws Exception {
+ buildAndCheckIR("aget", checkAnalysisResult(false));
+ }
+
+ @Test
+ public void testAlength() throws Exception {
+ buildAndCheckIR("alength", checkAnalysisResult(false));
+ }
+
+ @Test
+ public void testCreateInstance() throws Exception {
+ buildAndCheckIR("createInstance", checkAnalysisResult(false));
+ }
+
+ @Test
+ public void testCreateArray() throws Exception {
+ buildAndCheckIR("createArray", checkAnalysisResult(false));
+ }
+
+ private Consumer<IRCode> checkAnalysisResult(boolean expectedResult) {
+ return code -> {
+ assertEquals(expectedResult,
+ DeterminismAnalysis.returnValueOnlyDependsOnArguments(appView.withLiveness(), code));
+ };
+ }
+
+ static class TestClass {
+
+ static int ID;
+ Object field;
+
+ static int max(int x, int y) {
+ return x > y ? x : y;
+ }
+
+ static int sget() {
+ return ID;
+ }
+
+ static Object iget(TestClass instance) {
+ return instance != null ? instance.field : null;
+ }
+
+ static TestClass aget(TestClass[] args, int i) {
+ return args != null ? args[i] : null;
+ }
+
+ static int alength(TestClass[] args) {
+ return args.length;
+ }
+
+ static TestClass createInstance(Object field) {
+ TestClass instance = new TestClass();
+ instance.field = field;
+ return instance;
+ }
+
+ static TestClass[] createArray(int size, Object[] fields) {
+ TestClass[] array = new TestClass[size];
+ for (int i = 0; i < size; i++) {
+ array[i].field = fields[i];
+ }
+ return array;
+ }
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java
index 1cc0288..52c0a70 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/IdempotentFunctionCallCanonicalizationTest.java
@@ -9,6 +9,7 @@
import static org.junit.Assume.assumeTrue;
import com.android.tools.r8.D8TestRunResult;
+import com.android.tools.r8.NeverInline;
import com.android.tools.r8.R8TestRunResult;
import com.android.tools.r8.TestBase;
import com.android.tools.r8.TestParameters;
@@ -29,7 +30,40 @@
import org.junit.runners.Parameterized;
class IdempotentFunctionMain {
+ static int SEED;
+
+ @NeverInline
+ static int random(int arg) {
+ return SEED * arg;
+ }
+
+ @NeverInline
+ static int max(int x, int y) {
+ return x > y ? x : y;
+ }
+
public static void main(String[] args) {
+ {
+ SEED = 0;
+ System.out.print(random(2));
+ SEED = 1;
+ // Should not be canonicalized.
+ System.out.print(random(2));
+
+ System.out.print(max(1, 2));
+
+ System.out.print(max(3, 2));
+ // Different order of arguments. Not canonicalized.
+ System.out.print(max(2, 3));
+ // Canonicalized.
+ System.out.print(max(3, 2));
+
+ // Canonicalized.
+ System.out.print(max(1, 2));
+
+ System.out.println();
+ }
+
// Primitive will be boxed automatically.
{
Map<String, Boolean> map = new HashMap<>();
@@ -82,6 +116,7 @@
public class IdempotentFunctionCallCanonicalizationTest extends TestBase {
private static final Class<?> MAIN = IdempotentFunctionMain.class;
private static final String JAVA_OUTPUT = StringUtils.lines(
+ "0223332",
"true",
"false",
"8",
@@ -94,6 +129,8 @@
private static final int EXPECTED_BOOLEAN_VALUE_OF = 2;
private static final int EXPECTED_INTEGER_VALUE_OF = 2;
private static final int EXPECTED_LONG_VALUE_OF = 7;
+ private static final int EXPECTED_MAX_CALLS = 3;
+ private static final int TOTAL_MAX_CALLS = 5;
@Parameterized.Parameters(name = "{0}")
public static TestParametersCollection data() {
@@ -122,7 +159,7 @@
&& method.name.toString().equals("valueOf");
}
- private long countValueOf(MethodSubject method, String descriptor) {
+ private static long countValueOf(MethodSubject method, String descriptor) {
return Streams.stream(method.iterateInstructions(instructionSubject -> {
if (instructionSubject.isInvoke()) {
return isValueOf(instructionSubject.getMethod(), descriptor);
@@ -131,8 +168,18 @@
})).count();
}
+ private static long countMaxCall(MethodSubject method) {
+ return Streams.stream(method.iterateInstructions(instructionSubject -> {
+ if (instructionSubject.isInvoke()) {
+ return instructionSubject.getMethod().name.toString().equals("max");
+ }
+ return false;
+ })).count();
+ }
+
private void test(
TestRunResult result,
+ int expectedMaxCount,
int expectedBooleanValueOfCount,
int expectedIntValueOfCount,
int expectedLongValueOfCount) throws Exception {
@@ -140,6 +187,7 @@
ClassSubject mainClass = codeInspector.clazz(MAIN);
MethodSubject mainMethod = mainClass.mainMethod();
assertThat(mainMethod, isPresent());
+ assertEquals(expectedMaxCount, countMaxCall(mainMethod));
assertEquals(expectedBooleanValueOfCount, countValueOf(mainMethod, BOOLEAN_DESCRIPTOR));
assertEquals(expectedIntValueOfCount, countValueOf(mainMethod, INTEGER_DESCRIPTOR));
assertEquals(expectedLongValueOfCount, countValueOf(mainMethod, LONG_DESCRIPTOR));
@@ -156,7 +204,12 @@
.setMinApi(parameters.getRuntime())
.run(parameters.getRuntime(), MAIN)
.assertSuccessWithOutput(JAVA_OUTPUT);
- test(result, EXPECTED_BOOLEAN_VALUE_OF, EXPECTED_INTEGER_VALUE_OF, EXPECTED_LONG_VALUE_OF);
+ test(
+ result,
+ TOTAL_MAX_CALLS,
+ EXPECTED_BOOLEAN_VALUE_OF,
+ EXPECTED_INTEGER_VALUE_OF,
+ EXPECTED_LONG_VALUE_OF);
result =
testForD8()
@@ -165,7 +218,12 @@
.setMinApi(parameters.getRuntime())
.run(parameters.getRuntime(), MAIN)
.assertSuccessWithOutput(JAVA_OUTPUT);
- test(result, EXPECTED_BOOLEAN_VALUE_OF, EXPECTED_INTEGER_VALUE_OF, EXPECTED_LONG_VALUE_OF);
+ test(
+ result,
+ TOTAL_MAX_CALLS,
+ EXPECTED_BOOLEAN_VALUE_OF,
+ EXPECTED_INTEGER_VALUE_OF,
+ EXPECTED_LONG_VALUE_OF);
}
@Test
@@ -175,12 +233,19 @@
.addProgramClasses(MAIN)
.enableInliningAnnotations()
.addKeepMainRule(MAIN)
+ .noMinification()
.setMinApi(parameters.getRuntime())
.run(parameters.getRuntime(), MAIN)
.assertSuccessWithOutput(JAVA_OUTPUT);
+ int expectedMaxCount = parameters.isCfRuntime() ? TOTAL_MAX_CALLS : EXPECTED_MAX_CALLS;
int expectedBooleanValueOfCount = parameters.isCfRuntime() ? 6 : EXPECTED_BOOLEAN_VALUE_OF;
int expectedIntValueOfCount = parameters.isCfRuntime() ? 5 : EXPECTED_INTEGER_VALUE_OF;
int expectedLongValueOfCount = parameters.isCfRuntime() ? 10 : EXPECTED_LONG_VALUE_OF;
- test(result, expectedBooleanValueOfCount, expectedIntValueOfCount, expectedLongValueOfCount);
+ test(
+ result,
+ expectedMaxCount,
+ expectedBooleanValueOfCount,
+ expectedIntValueOfCount,
+ expectedLongValueOfCount);
}
}
