Refactor utils that collect method optimization info.
Bug: 141656615
Change-Id: If0ec84a917b22414918e0e24cdec923bab17da90
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 57425ab..dd3416f 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
@@ -5,7 +5,6 @@
import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.Flavor.ExcludeDexResources;
import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.Flavor.IncludeAllResources;
-import static com.android.tools.r8.ir.optimize.CodeRewriter.checksNullBeforeSideEffect;
import com.android.tools.r8.errors.CompilationError;
import com.android.tools.r8.errors.Unreachable;
@@ -26,17 +25,10 @@
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.graph.ResolutionResult;
-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;
import com.android.tools.r8.ir.analysis.fieldaccess.FieldBitAccessAnalysis;
import com.android.tools.r8.ir.analysis.fieldvalueanalysis.FieldValueAnalysis;
-import com.android.tools.r8.ir.analysis.sideeffect.ClassInitializerSideEffectAnalysis;
-import com.android.tools.r8.ir.analysis.sideeffect.ClassInitializerSideEffectAnalysis.ClassInitializerSideEffect;
-import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.code.AlwaysMaterializingDefinition;
import com.android.tools.r8.ir.code.AlwaysMaterializingUser;
@@ -74,6 +66,7 @@
import com.android.tools.r8.ir.optimize.ServiceLoaderRewriter;
import com.android.tools.r8.ir.optimize.UninstantiatedTypeOptimization;
import com.android.tools.r8.ir.optimize.classinliner.ClassInliner;
+import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfoCollector;
import com.android.tools.r8.ir.optimize.info.OptimizationFeedback;
import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackDelayed;
import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackIgnore;
@@ -107,7 +100,6 @@
import com.google.common.collect.Sets;
import com.google.common.collect.Streams;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
@@ -171,6 +163,8 @@
final DeadCodeRemover deadCodeRemover;
+ final MethodOptimizationInfoCollector methodOptimizationInfoCollector;
+
private final OptimizationFeedbackDelayed delayedOptimizationFeedback =
new OptimizationFeedbackDelayed();
private final OptimizationFeedback simpleOptimizationFeedback =
@@ -211,6 +205,7 @@
.map(prefix -> "L" + DescriptorUtils.getPackageBinaryNameFromJavaType(prefix))
.map(options.itemFactory::createString)
.collect(Collectors.toList());
+ this.methodOptimizationInfoCollector = new MethodOptimizationInfoCollector(appView);
if (options.isDesugaredLibraryCompilation()) {
// Specific L8 Settings.
// BackportedMethodRewriter is needed for retarget core library members and backports.
@@ -1403,7 +1398,7 @@
appView.callSiteOptimizationInfoPropagator().collectCallSiteOptimizationInfo(code);
}
// Computation of non-null parameters on normal exits rely on the existence of non-null IRs.
- nonNullTracker.computeNonNullParamOnNormalExits(feedback, code);
+ methodOptimizationInfoCollector.computeNonNullParamOnNormalExits(feedback, code);
}
if (aliasIntroducer != null || nonNullTracker != null || dynamicTypeOptimization != null) {
codeRewriter.removeAssumeInstructions(code);
@@ -1426,21 +1421,25 @@
// Compute optimization info summary for the current method unless it is pinned
// (in that case we should not be making any assumptions about the behavior of the method).
if (!appView.appInfo().withLiveness().isPinned(method.method)) {
- codeRewriter.identifyClassInlinerEligibility(method, code, feedback);
- codeRewriter.identifyParameterUsages(method, code, feedback);
- codeRewriter.identifyReturnsArgument(method, code, feedback);
- codeRewriter.identifyTrivialInitializer(method, code, feedback);
+ methodOptimizationInfoCollector.identifyClassInlinerEligibility(method, code, feedback);
+ methodOptimizationInfoCollector.identifyParameterUsages(method, code, feedback);
+ methodOptimizationInfoCollector.identifyReturnsArgument(method, code, feedback);
+ methodOptimizationInfoCollector.identifyTrivialInitializer(method, code, feedback);
if (options.enableInlining && inliner != null) {
- codeRewriter.identifyInvokeSemanticsForInlining(method, code, appView, feedback);
+ methodOptimizationInfoCollector
+ .identifyInvokeSemanticsForInlining(method, code, appView, feedback);
}
- computeDynamicReturnType(feedback, method, code);
+ methodOptimizationInfoCollector
+ .computeDynamicReturnType(dynamicTypeOptimization, feedback, method, code);
FieldValueAnalysis.run(appView, code, feedback, method);
- computeInitializedClassesOnNormalExit(feedback, method, code);
- computeMayHaveSideEffects(feedback, method, code);
- computeReturnValueOnlyDependsOnArguments(feedback, method, code);
- computeNonNullParamOrThrow(feedback, method, code);
+ methodOptimizationInfoCollector
+ .computeInitializedClassesOnNormalExit(feedback, method, code);
+ methodOptimizationInfoCollector.computeMayHaveSideEffects(feedback, method, code);
+ methodOptimizationInfoCollector
+ .computeReturnValueOnlyDependsOnArguments(feedback, method, code);
+ methodOptimizationInfoCollector.computeNonNullParamOrThrow(feedback, method, code);
}
}
@@ -1471,164 +1470,6 @@
finalizeIR(method, code, feedback);
}
- // Track usage of parameters and compute their nullability and possibility of NPE.
- private void computeNonNullParamOrThrow(
- OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
- if (method.getOptimizationInfo().getNonNullParamOrThrow() != null) {
- return;
- }
-
- List<Value> arguments = code.collectArguments();
- BitSet paramsCheckedForNull = new BitSet();
- for (int index = 0; index < arguments.size(); index++) {
- Value argument = arguments.get(index);
- // This handles cases where the parameter is checked via Kotlin Intrinsics:
- //
- // kotlin.jvm.internal.Intrinsics.checkParameterIsNotNull(param, message)
- //
- // or its inlined version:
- //
- // if (param != null) return;
- // invoke-static throwParameterIsNullException(msg)
- //
- // or some other variants, e.g., throw null or NPE after the direct null check.
- if (argument.isUsed() && checksNullBeforeSideEffect(code, argument, appView)) {
- paramsCheckedForNull.set(index);
- }
- }
- if (paramsCheckedForNull.length() > 0) {
- feedback.setNonNullParamOrThrow(method, paramsCheckedForNull);
- }
- }
-
- private void computeDynamicReturnType(
- OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
- if (dynamicTypeOptimization != null) {
- DexType staticReturnTypeRaw = method.method.proto.returnType;
- if (!staticReturnTypeRaw.isReferenceType()) {
- return;
- }
-
- TypeLatticeElement dynamicReturnType =
- dynamicTypeOptimization.computeDynamicReturnType(method, code);
- if (dynamicReturnType != null) {
- TypeLatticeElement staticReturnType =
- TypeLatticeElement.fromDexType(staticReturnTypeRaw, Nullability.maybeNull(), appView);
-
- // If the dynamic return type is not more precise than the static return type there is no
- // need to record it.
- if (dynamicReturnType.strictlyLessThan(staticReturnType, appView)) {
- feedback.methodReturnsObjectOfType(method, appView, dynamicReturnType);
- }
- }
-
- ClassTypeLatticeElement exactReturnType =
- dynamicTypeOptimization.computeDynamicLowerBoundType(method, code);
- if (exactReturnType != null) {
- feedback.methodReturnsObjectWithLowerBoundType(method, exactReturnType);
- }
- }
- }
-
- private void computeInitializedClassesOnNormalExit(
- OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
- if (options.enableInitializedClassesAnalysis && appView.appInfo().hasLiveness()) {
- AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
- Set<DexType> initializedClasses =
- InitializedClassesOnNormalExitAnalysis.computeInitializedClassesOnNormalExit(
- appViewWithLiveness, code);
- if (initializedClasses != null && !initializedClasses.isEmpty()) {
- feedback.methodInitializesClassesOnNormalExit(method, initializedClasses);
- }
- }
- }
-
- private void computeMayHaveSideEffects(
- OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
- // If the method is native, we don't know what could happen.
- assert !method.accessFlags.isNative();
-
- if (!options.enableSideEffectAnalysis) {
- return;
- }
-
- if (appView.appInfo().withLiveness().mayHaveSideEffects.containsKey(method.method)) {
- return;
- }
-
- DexType context = method.method.holder;
-
- if (method.isClassInitializer()) {
- // For class initializers, we also wish to compute if the class initializer has observable
- // side effects.
- ClassInitializerSideEffect classInitializerSideEffect =
- ClassInitializerSideEffectAnalysis.classInitializerCanBePostponed(appView, code);
- if (classInitializerSideEffect.isNone()) {
- feedback.methodMayNotHaveSideEffects(method);
- feedback.classInitializerMayBePostponed(method);
- } else if (classInitializerSideEffect.canBePostponed()) {
- feedback.classInitializerMayBePostponed(method);
- }
- return;
- }
-
- boolean mayHaveSideEffects;
- if (method.accessFlags.isSynchronized()) {
- // If the method is synchronized then it acquires a lock.
- mayHaveSideEffects = true;
- } else if (method.isInstanceInitializer() && hasNonTrivialFinalizeMethod(context)) {
- // If a class T overrides java.lang.Object.finalize(), then treat the constructor as having
- // side effects. This ensures that we won't remove instructions on the form `new-instance
- // {v0}, T`.
- mayHaveSideEffects = true;
- } else {
- // Otherwise, check if there is an instruction that has side effects.
- mayHaveSideEffects =
- Streams.stream(code.instructions())
- .anyMatch(instruction -> instruction.instructionMayHaveSideEffects(appView, context));
- }
-
- if (!mayHaveSideEffects) {
- 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) {
- DexClass clazz = appView.definitionFor(type);
- if (clazz != null) {
- if (clazz.isProgramClass() && !clazz.isInterface()) {
- ResolutionResult resolutionResult =
- appView
- .appInfo()
- .resolveMethodOnClass(clazz, appView.dexItemFactory().objectMethods.finalize);
- for (DexEncodedMethod target : resolutionResult.asListOfTargets()) {
- if (target.method != appView.dexItemFactory().objectMethods.finalize) {
- return true;
- }
- }
- return false;
- } else {
- // Conservatively report that the library class could implement finalize().
- return true;
- }
- }
- return false;
- }
-
private void finalizeIR(DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
code.traceBlocks();
if (options.isGeneratingClassFiles()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index b7d3dcd..932c817 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -4,7 +4,6 @@
package com.android.tools.r8.ir.optimize;
-import static com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query.DIRECTLY;
import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
import static com.android.tools.r8.optimize.MemberRebindingAnalysis.isTypeVisibleFromContext;
@@ -15,12 +14,7 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DebugLocalInfo;
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.DexEncodedMethod.ClassInlinerEligibility;
-import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer;
-import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer.TrivialClassInitializer;
-import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer.TrivialInstanceInitializer;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexItemFactory.ThrowableMethods;
@@ -28,7 +22,6 @@
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.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
import com.android.tools.r8.ir.analysis.equivalence.BasicBlockBehavioralSubsumption;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
@@ -54,7 +47,6 @@
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.If.Type;
import com.android.tools.r8.ir.code.InstanceOf;
-import com.android.tools.r8.ir.code.InstancePut;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InstructionListIterator;
@@ -74,7 +66,6 @@
import com.android.tools.r8.ir.code.NumericType;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Position;
-import com.android.tools.r8.ir.code.Return;
import com.android.tools.r8.ir.code.StaticGet;
import com.android.tools.r8.ir.code.StaticPut;
import com.android.tools.r8.ir.code.Switch;
@@ -85,17 +76,12 @@
import com.android.tools.r8.ir.conversion.IRConverter;
import com.android.tools.r8.ir.optimize.SwitchUtils.EnumSwitchInfo;
import com.android.tools.r8.ir.optimize.info.OptimizationFeedback;
-import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo;
-import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsage;
-import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsageBuilder;
import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
-import com.android.tools.r8.kotlin.Kotlin;
import com.android.tools.r8.shaking.AppInfoWithLiveness.EnumValueInfo;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.InternalOptions.AssertionProcessing;
import com.android.tools.r8.utils.InternalOutputMode;
import com.android.tools.r8.utils.LongInterval;
-import com.android.tools.r8.utils.MethodSignatureEquivalence;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.base.Supplier;
@@ -140,8 +126,6 @@
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
-import java.util.function.BiFunction;
-import java.util.function.Function;
import java.util.function.Predicate;
public class CodeRewriter {
@@ -1155,620 +1139,6 @@
assert code.isConsistentGraph();
}
- public void identifyReturnsArgument(
- DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
- List<BasicBlock> normalExits = code.computeNormalExitBlocks();
- if (normalExits.isEmpty()) {
- feedback.methodNeverReturnsNormally(method);
- return;
- }
- Return firstExit = normalExits.get(0).exit().asReturn();
- if (firstExit.isReturnVoid()) {
- return;
- }
- Value returnValue = firstExit.returnValue();
- boolean isNeverNull = returnValue.getTypeLattice().isReference() && returnValue.isNeverNull();
- for (int i = 1; i < normalExits.size(); i++) {
- Return exit = normalExits.get(i).exit().asReturn();
- Value value = exit.returnValue();
- if (value != returnValue) {
- returnValue = null;
- }
- isNeverNull &= value.getTypeLattice().isReference() && value.isNeverNull();
- }
- if (returnValue != null) {
- if (returnValue.isArgument()) {
- // Find the argument number.
- int index = code.collectArguments().indexOf(returnValue);
- assert index != -1;
- feedback.methodReturnsArgument(method, index);
- }
- if (returnValue.isConstant()) {
- if (returnValue.definition.isConstNumber()) {
- long value = returnValue.definition.asConstNumber().getRawValue();
- feedback.methodReturnsConstantNumber(method, value);
- } else if (returnValue.definition.isConstString()) {
- ConstString constStringInstruction = returnValue.definition.asConstString();
- if (!constStringInstruction.instructionInstanceCanThrow()) {
- feedback.methodReturnsConstantString(method, constStringInstruction.getValue());
- }
- }
- }
- }
- if (isNeverNull) {
- feedback.methodNeverReturnsNull(method);
- }
- }
-
- public void identifyInvokeSemanticsForInlining(
- DexEncodedMethod method, IRCode code, AppView<?> appView, OptimizationFeedback feedback) {
- if (method.isStatic()) {
- // Identifies if the method preserves class initialization after inlining.
- feedback.markTriggerClassInitBeforeAnySideEffect(
- method, triggersClassInitializationBeforeSideEffect(method.method.holder, code, appView));
- } else {
- // Identifies if the method preserves null check of the receiver after inlining.
- final Value receiver = code.getThis();
- feedback.markCheckNullReceiverBeforeAnySideEffect(
- method, receiver.isUsed() && checksNullBeforeSideEffect(code, receiver, appView));
- }
- }
-
- public void identifyClassInlinerEligibility(
- DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
- // Method eligibility is calculated in similar way for regular method
- // and for the constructor. To be eligible method should only be using its
- // receiver in the following ways:
- //
- // (1) as a receiver of reads/writes of instance fields of the holder class,
- // (2) as a return value,
- // (3) as a receiver of a call to the superclass initializer. Note that we don't
- // check what is passed to superclass initializer as arguments, only check
- // that it is not the instance being initialized,
- // (4) as argument to a monitor instruction.
- //
- // Note that (4) can safely be removed as the receiver is guaranteed not to escape when we class
- // inline it, and hence any monitor instructions are no-ops.
- boolean instanceInitializer = method.isInstanceInitializer();
- if (method.accessFlags.isNative()
- || (!method.isNonAbstractVirtualMethod() && !instanceInitializer)) {
- return;
- }
-
- feedback.setClassInlinerEligibility(method, null); // To allow returns below.
-
- Value receiver = code.getThis();
- if (receiver.numberOfPhiUsers() > 0) {
- return;
- }
-
- DexClass clazz = appView.definitionFor(method.method.holder);
- if (clazz == null) {
- return;
- }
-
- boolean receiverUsedAsReturnValue = false;
- boolean seenSuperInitCall = false;
- for (Instruction insn : receiver.uniqueUsers()) {
- if (insn.isMonitor()) {
- continue;
- }
-
- if (insn.isReturn()) {
- receiverUsedAsReturnValue = true;
- continue;
- }
-
- if (insn.isInstanceGet() || insn.isInstancePut()) {
- if (insn.isInstancePut()) {
- InstancePut instancePutInstruction = insn.asInstancePut();
- // Only allow field writes to the receiver.
- if (instancePutInstruction.object() != receiver) {
- return;
- }
- // Do not allow the receiver to escape via a field write.
- if (instancePutInstruction.value() == receiver) {
- return;
- }
- }
- DexField field = insn.asFieldInstruction().getField();
- if (field.holder == clazz.type && clazz.lookupInstanceField(field) != null) {
- // Require only accessing instance fields of the *current* class.
- continue;
- }
- return;
- }
-
- // If this is an instance initializer allow one call to superclass instance initializer.
- if (insn.isInvokeDirect()) {
- InvokeDirect invokedDirect = insn.asInvokeDirect();
- DexMethod invokedMethod = invokedDirect.getInvokedMethod();
- if (dexItemFactory.isConstructor(invokedMethod) &&
- invokedMethod.holder == clazz.superType &&
- invokedDirect.inValues().lastIndexOf(receiver) == 0 &&
- !seenSuperInitCall &&
- instanceInitializer) {
- seenSuperInitCall = true;
- continue;
- }
- // We don't support other direct calls yet.
- return;
- }
-
- // Other receiver usages make the method not eligible.
- return;
- }
-
- if (instanceInitializer && !seenSuperInitCall) {
- // Call to super constructor not found?
- return;
- }
-
- feedback.setClassInlinerEligibility(
- method, new ClassInlinerEligibility(receiverUsedAsReturnValue));
- }
-
- public void identifyTrivialInitializer(
- DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
- if (!method.isInstanceInitializer() && !method.isClassInitializer()) {
- return;
- }
-
- if (method.accessFlags.isNative()) {
- return;
- }
-
- DexClass clazz = appView.appInfo().definitionFor(method.method.holder);
- if (clazz == null) {
- return;
- }
-
- feedback.setTrivialInitializer(
- method,
- method.isInstanceInitializer()
- ? computeInstanceInitializerInfo(code, clazz, appView::definitionFor)
- : computeClassInitializerInfo(code, clazz));
- }
-
- public void identifyParameterUsages(
- DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
- List<ParameterUsage> usages = new ArrayList<>();
- List<Value> values = code.collectArguments();
- for (int i = 0; i < values.size(); i++) {
- Value value = values.get(i);
- if (value.numberOfPhiUsers() > 0) {
- continue;
- }
- ParameterUsage usage = collectParameterUsages(i, value);
- if (usage != null) {
- usages.add(usage);
- }
- }
- feedback.setParameterUsages(method, usages.isEmpty() ? null : new ParameterUsagesInfo(usages));
- }
-
- private ParameterUsage collectParameterUsages(int i, Value value) {
- ParameterUsageBuilder builder = new ParameterUsageBuilder(value, i);
- for (Instruction user : value.uniqueUsers()) {
- if (!builder.note(user)) {
- return null;
- }
- }
- return builder.build();
- }
-
- // This method defines trivial instance initializer as follows:
- //
- // ** The initializer may call the initializer of the base class, which
- // itself must be trivial.
- //
- // ** java.lang.Object.<init>() is considered trivial.
- //
- // ** all arguments passed to a super-class initializer must be non-throwing
- // constants or arguments.
- //
- // ** Assigns arguments or non-throwing constants to fields of this class.
- //
- // (Note that this initializer does not have to have zero arguments.)
- private TrivialInitializer computeInstanceInitializerInfo(
- IRCode code, DexClass clazz, Function<DexType, DexClass> typeToClass) {
- Value receiver = code.getThis();
-
- for (Instruction insn : code.instructions()) {
- if (insn.isReturn()) {
- continue;
- }
-
- if (insn.isArgument()) {
- continue;
- }
-
- if (insn.isConstInstruction()) {
- if (insn.instructionInstanceCanThrow()) {
- return null;
- } else {
- continue;
- }
- }
-
- if (insn.isInvokeDirect()) {
- InvokeDirect invokedDirect = insn.asInvokeDirect();
- DexMethod invokedMethod = invokedDirect.getInvokedMethod();
-
- if (invokedMethod.holder != clazz.superType) {
- return null;
- }
-
- // java.lang.Object.<init>() is considered trivial.
- if (invokedMethod == dexItemFactory.objectMethods.constructor) {
- continue;
- }
-
- DexClass holder = typeToClass.apply(invokedMethod.holder);
- if (holder == null) {
- return null;
- }
-
- DexEncodedMethod callTarget = holder.lookupDirectMethod(invokedMethod);
- if (callTarget == null ||
- !callTarget.isInstanceInitializer() ||
- callTarget.getOptimizationInfo().getTrivialInitializerInfo() == null ||
- invokedDirect.getReceiver() != receiver) {
- return null;
- }
-
- for (Value value : invokedDirect.inValues()) {
- if (value != receiver && !(value.isConstant() || value.isArgument())) {
- return null;
- }
- }
- continue;
- }
-
- if (insn.isInstancePut()) {
- InstancePut instancePut = insn.asInstancePut();
- DexEncodedField field = clazz.lookupInstanceField(instancePut.getField());
- if (field == null ||
- instancePut.object() != receiver ||
- (instancePut.value() != receiver && !instancePut.value().isArgument())) {
- return null;
- }
- continue;
- }
-
- if (insn.isGoto()) {
- // Trivial goto to the next block.
- if (insn.asGoto().isTrivialGotoToTheNextBlock(code)) {
- continue;
- }
- return null;
- }
-
- // Other instructions make the instance initializer not eligible.
- return null;
- }
-
- return TrivialInstanceInitializer.INSTANCE;
- }
-
- // This method defines trivial class initializer as follows:
- //
- // ** The initializer may only instantiate an instance of the same class,
- // initialize it with a call to a trivial constructor *without* arguments,
- // and assign this instance to a static final field of the same class.
- //
- private synchronized TrivialInitializer computeClassInitializerInfo(IRCode code, DexClass clazz) {
- Value createdSingletonInstance = null;
- DexField singletonField = null;
-
- for (Instruction insn : code.instructions()) {
- if (insn.isConstNumber()) {
- continue;
- }
-
- if (insn.isConstString()) {
- if (insn.instructionInstanceCanThrow()) {
- return null;
- }
- continue;
- }
-
- if (insn.isReturn()) {
- continue;
- }
-
- if (insn.isNewInstance()) {
- NewInstance newInstance = insn.asNewInstance();
- if (createdSingletonInstance != null ||
- newInstance.clazz != clazz.type ||
- insn.outValue() == null) {
- return null;
- }
- createdSingletonInstance = insn.outValue();
- continue;
- }
-
- if (insn.isInvokeDirect()) {
- InvokeDirect invokedDirect = insn.asInvokeDirect();
- if (createdSingletonInstance == null ||
- invokedDirect.getReceiver() != createdSingletonInstance) {
- return null;
- }
-
- DexEncodedMethod callTarget = clazz.lookupDirectMethod(invokedDirect.getInvokedMethod());
- if (callTarget == null ||
- !callTarget.isInstanceInitializer() ||
- !callTarget.method.proto.parameters.isEmpty() ||
- callTarget.getOptimizationInfo().getTrivialInitializerInfo() == null) {
- return null;
- }
- continue;
- }
-
- if (insn.isStaticPut()) {
- StaticPut staticPut = insn.asStaticPut();
- if (singletonField != null
- || createdSingletonInstance == null
- || staticPut.value() != createdSingletonInstance) {
- return null;
- }
-
- DexEncodedField field = clazz.lookupStaticField(staticPut.getField());
- if (field == null ||
- !field.accessFlags.isStatic() ||
- !field.accessFlags.isFinal()) {
- return null;
- }
- singletonField = field.field;
- continue;
- }
-
- // Other instructions make the class initializer not eligible.
- return null;
- }
-
- return singletonField == null ? null : new TrivialClassInitializer(singletonField);
- }
-
- /**
- * An enum used to classify instructions according to a particular effect that they produce.
- *
- * The "effect" of an instruction can be seen as a program state change (or semantic change) at
- * runtime execution. For example, an instruction could cause the initialization of a class,
- * change the value of a field, ... while other instructions do not.
- *
- * This classification also depends on the type of analysis that is using it. For instance, an
- * analysis can look for instructions that cause class initialization while another look for
- * instructions that check nullness of a particular object.
- *
- * On the other hand, some instructions may provide a non desired effect which is a signal for
- * the analysis to stop.
- */
- private enum InstructionEffect {
- DESIRED_EFFECT,
- CONDITIONAL_EFFECT,
- OTHER_EFFECT,
- NO_EFFECT
- }
-
- /**
- * Returns true if the given code unconditionally throws if value is null before any other side
- * effect instruction.
- *
- * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
- */
- public static boolean checksNullBeforeSideEffect(IRCode code, Value value, AppView<?> appView) {
- return alwaysTriggerExpectedEffectBeforeAnythingElse(
- code,
- (instr, it) -> {
- BasicBlock currentBlock = instr.getBlock();
- // If the code explicitly checks the nullability of the value, we should visit the next
- // block that corresponds to the null value where NPE semantic could be preserved.
- if (!currentBlock.hasCatchHandlers() && isNullCheck(instr, value)) {
- return InstructionEffect.CONDITIONAL_EFFECT;
- }
- if (isKotlinNullCheck(instr, value, appView)) {
- DexMethod invokedMethod = instr.asInvokeStatic().getInvokedMethod();
- // Kotlin specific way of throwing NPE: throwParameterIsNullException.
- // Similarly, combined with the above CONDITIONAL_EFFECT, the code checks on NPE on
- // the value.
- if (invokedMethod.name
- == appView.dexItemFactory().kotlin.intrinsics.throwParameterIsNullException.name) {
- // We found a NPE (or similar exception) throwing code.
- // Combined with the above CONDITIONAL_EFFECT, the code checks NPE on the value.
- for (BasicBlock predecessor : currentBlock.getPredecessors()) {
- if (isNullCheck(predecessor.exit(), value)) {
- return InstructionEffect.DESIRED_EFFECT;
- }
- }
- // Hitting here means that this call might be used for other parameters. If we don't
- // bail out, it will be regarded as side effects for the current value.
- return InstructionEffect.NO_EFFECT;
- } else {
- // Kotlin specific way of checking parameter nullness: checkParameterIsNotNull.
- assert invokedMethod.name
- == appView.dexItemFactory().kotlin.intrinsics.checkParameterIsNotNull.name;
- return InstructionEffect.DESIRED_EFFECT;
- }
- }
- if (isInstantiationOfNullPointerException(instr, it, appView.dexItemFactory())) {
- it.next(); // Skip call to NullPointerException.<init>.
- return InstructionEffect.NO_EFFECT;
- } else if (instr.throwsNpeIfValueIsNull(value, appView.dexItemFactory())) {
- // In order to preserve NPE semantic, the exception must not be caught by any handler.
- // Therefore, we must ignore this instruction if it is covered by a catch handler.
- // Note: this is a conservative approach where we consider that any catch handler could
- // catch the exception, even if it cannot catch a NullPointerException.
- if (!currentBlock.hasCatchHandlers()) {
- // We found a NPE check on the value.
- return InstructionEffect.DESIRED_EFFECT;
- }
- } else if (instr.instructionMayHaveSideEffects(appView, code.method.method.holder)) {
- // If the current instruction is const-string, this could load the parameter name.
- // Just make sure it is indeed not throwing.
- if (instr.isConstString() && !instr.instructionInstanceCanThrow()) {
- return InstructionEffect.NO_EFFECT;
- }
- // We found a side effect before a NPE check.
- return InstructionEffect.OTHER_EFFECT;
- }
- return InstructionEffect.NO_EFFECT;
- });
- }
-
- // Note that this method may have false positives, since the application could in principle
- // declare a method called checkParameterIsNotNull(parameter, message) or
- // throwParameterIsNullException(parameterName) in a package that starts with "kotlin".
- private static boolean isKotlinNullCheck(Instruction instr, Value value, AppView<?> appView) {
- if (!instr.isInvokeStatic()) {
- return false;
- }
- // We need to strip the holder, since Kotlin adds different versions of null-check machinery,
- // e.g., kotlin.collections.ArraysKt___ArraysKt... or kotlin.jvm.internal.ArrayIteratorKt...
- MethodSignatureEquivalence wrapper = MethodSignatureEquivalence.get();
- Wrapper<DexMethod> checkParameterIsNotNull =
- wrapper.wrap(appView.dexItemFactory().kotlin.intrinsics.checkParameterIsNotNull);
- Wrapper<DexMethod> throwParamIsNullException =
- wrapper.wrap(appView.dexItemFactory().kotlin.intrinsics.throwParameterIsNullException);
- DexMethod invokedMethod =
- appView.graphLense().getOriginalMethodSignature(instr.asInvokeStatic().getInvokedMethod());
- Wrapper<DexMethod> methodWrap = wrapper.wrap(invokedMethod);
- if (methodWrap.equals(throwParamIsNullException)
- || (methodWrap.equals(checkParameterIsNotNull) && instr.inValues().get(0).equals(value))) {
- if (invokedMethod.holder.getPackageDescriptor().startsWith(Kotlin.NAME)) {
- return true;
- }
- }
- return false;
- }
-
- private static boolean isNullCheck(Instruction instr, Value value) {
- return instr.isIf() && instr.asIf().isZeroTest()
- && instr.inValues().get(0).equals(value)
- && (instr.asIf().getType() == Type.EQ || instr.asIf().getType() == Type.NE);
- }
-
- /**
- * Returns true if the given instruction is {@code v <- new-instance NullPointerException}, and
- * the next instruction is {@code invoke-direct v, NullPointerException.<init>()}.
- */
- private static boolean isInstantiationOfNullPointerException(
- Instruction instruction, InstructionIterator it, DexItemFactory dexItemFactory) {
- if (!instruction.isNewInstance()
- || instruction.asNewInstance().clazz != dexItemFactory.npeType) {
- return false;
- }
- Instruction next = it.peekNext();
- if (next == null
- || !next.isInvokeDirect()
- || next.asInvokeDirect().getInvokedMethod() != dexItemFactory.npeMethods.init) {
- return false;
- }
- return true;
- }
-
- /**
- * Returns true if the given code unconditionally triggers class initialization before any other
- * side effecting instruction.
- *
- * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
- */
- private static boolean triggersClassInitializationBeforeSideEffect(
- DexType clazz, IRCode code, AppView<?> appView) {
- return alwaysTriggerExpectedEffectBeforeAnythingElse(
- code,
- (instruction, it) -> {
- DexType context = code.method.method.holder;
- if (instruction.definitelyTriggersClassInitialization(
- clazz, context, appView, DIRECTLY, AnalysisAssumption.INSTRUCTION_DOES_NOT_THROW)) {
- // In order to preserve class initialization semantic, the exception must not be caught
- // by any handler. Therefore, we must ignore this instruction if it is covered by a
- // catch handler.
- // Note: this is a conservative approach where we consider that any catch handler could
- // catch the exception, even if it cannot catch an ExceptionInInitializerError.
- if (!instruction.getBlock().hasCatchHandlers()) {
- // We found an instruction that preserves initialization of the class.
- return InstructionEffect.DESIRED_EFFECT;
- }
- } else if (instruction.instructionMayHaveSideEffects(appView, clazz)) {
- // We found a side effect before class initialization.
- return InstructionEffect.OTHER_EFFECT;
- }
- return InstructionEffect.NO_EFFECT;
- });
- }
-
- /**
- * Returns true if the given code unconditionally triggers an expected effect before anything
- * else, false otherwise.
- *
- * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
- */
- private static boolean alwaysTriggerExpectedEffectBeforeAnythingElse(
- IRCode code, BiFunction<Instruction, InstructionIterator, InstructionEffect> function) {
- final int color = code.reserveMarkingColor();
- try {
- ArrayDeque<BasicBlock> worklist = new ArrayDeque<>();
- final BasicBlock entry = code.entryBlock();
- worklist.add(entry);
- entry.mark(color);
-
- while (!worklist.isEmpty()) {
- BasicBlock currentBlock = worklist.poll();
- assert currentBlock.isMarked(color);
-
- InstructionEffect result = InstructionEffect.NO_EFFECT;
- InstructionIterator it = currentBlock.iterator();
- while (result == InstructionEffect.NO_EFFECT && it.hasNext()) {
- result = function.apply(it.next(), it);
- }
- if (result == InstructionEffect.OTHER_EFFECT) {
- // We found an instruction that is causing an unexpected side effect.
- return false;
- } else if (result == InstructionEffect.DESIRED_EFFECT) {
- // The current path is causing the expected effect. No need to go deeper in this path,
- // go to the next block in the work list.
- continue;
- } else if (result == InstructionEffect.CONDITIONAL_EFFECT) {
- assert !currentBlock.getNormalSuccessors().isEmpty();
- Instruction lastInstruction = currentBlock.getInstructions().getLast();
- assert lastInstruction.isIf();
- // The current path is checking if the value of interest is null. Go deeper into the path
- // that corresponds to the null value.
- BasicBlock targetIfReceiverIsNull = lastInstruction.asIf().targetFromCondition(0);
- if (!targetIfReceiverIsNull.isMarked(color)) {
- worklist.add(targetIfReceiverIsNull);
- targetIfReceiverIsNull.mark(color);
- }
- } else {
- assert result == InstructionEffect.NO_EFFECT;
- // The block did not cause any particular effect.
- if (currentBlock.getNormalSuccessors().isEmpty()) {
- // This is the end of the current non-exceptional path and we did not find any expected
- // effect. It means there is at least one path where the expected effect does not
- // happen.
- Instruction lastInstruction = currentBlock.getInstructions().getLast();
- assert lastInstruction.isReturn() || lastInstruction.isThrow();
- return false;
- } else {
- // Look into successors
- for (BasicBlock successor : currentBlock.getSuccessors()) {
- if (!successor.isMarked(color)) {
- worklist.add(successor);
- successor.mark(color);
- }
- }
- }
- }
- }
-
- // If we reach this point, we checked that the expected effect happens in every possible path.
- return true;
- } finally {
- code.returnMarkingColor(color);
- }
- }
-
private boolean checkArgumentType(InvokeMethod invoke, int argumentIndex) {
// TODO(sgjesse): Insert cast if required.
TypeLatticeElement returnType =
@@ -2203,11 +1573,6 @@
}
}
- private boolean canBeFolded(Instruction instruction) {
- return (instruction.isBinop() && instruction.asBinop().canBeFolded()) ||
- (instruction.isUnop() && instruction.asUnop().canBeFolded());
- }
-
// Split constants that flow into ranged invokes. This gives the register allocator more
// freedom in assigning register to ranged invokes which can greatly reduce the number
// of register needed (and thereby code size as well).
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java b/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
index 0adf3f7..cea57a8 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
@@ -22,7 +22,6 @@
import com.android.tools.r8.ir.code.FieldInstruction;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.If;
-import com.android.tools.r8.ir.code.If.Type;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InstructionListIterator;
@@ -31,14 +30,11 @@
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.optimize.info.FieldOptimizationInfo;
import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
-import com.android.tools.r8.ir.optimize.info.OptimizationFeedback;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.google.common.collect.Sets;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntList;
-import java.util.ArrayDeque;
import java.util.BitSet;
-import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.List;
@@ -413,107 +409,4 @@
&& type.asReferenceTypeLatticeElement().isNullable()
&& value.numberOfAllUsers() > 0;
}
-
- public void computeNonNullParamOnNormalExits(OptimizationFeedback feedback, IRCode code) {
- Set<BasicBlock> normalExits = Sets.newIdentityHashSet();
- normalExits.addAll(code.computeNormalExitBlocks());
- DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
- List<Value> arguments = code.collectArguments();
- BitSet facts = new BitSet();
- Set<BasicBlock> nullCheckedBlocks = Sets.newIdentityHashSet();
- for (int index = 0; index < arguments.size(); index++) {
- Value argument = arguments.get(index);
- // Consider reference-type parameter only.
- if (!argument.getTypeLattice().isReference()) {
- continue;
- }
- // The receiver is always non-null on normal exits.
- if (argument.isThis()) {
- facts.set(index);
- continue;
- }
- // Collect basic blocks that check nullability of the parameter.
- nullCheckedBlocks.clear();
- for (Instruction user : argument.uniqueUsers()) {
- if (user.isAssumeNonNull()) {
- nullCheckedBlocks.add(user.asAssumeNonNull().getBlock());
- }
- if (user.isIf()
- && user.asIf().isZeroTest()
- && (user.asIf().getType() == Type.EQ || user.asIf().getType() == Type.NE)) {
- nullCheckedBlocks.add(user.asIf().targetFromNonNullObject());
- }
- }
- if (!nullCheckedBlocks.isEmpty()) {
- boolean allExitsCovered = true;
- for (BasicBlock normalExit : normalExits) {
- if (!isNormalExitDominated(normalExit, code, dominatorTree, nullCheckedBlocks)) {
- allExitsCovered = false;
- break;
- }
- }
- if (allExitsCovered) {
- facts.set(index);
- }
- }
- }
- if (facts.length() > 0) {
- feedback.setNonNullParamOnNormalExits(code.method, facts);
- }
- }
-
- private boolean isNormalExitDominated(
- BasicBlock normalExit,
- IRCode code,
- DominatorTree dominatorTree,
- Set<BasicBlock> nullCheckedBlocks) {
- // Each normal exit should be...
- for (BasicBlock nullCheckedBlock : nullCheckedBlocks) {
- // A) ...directly dominated by any null-checked block.
- if (dominatorTree.dominatedBy(normalExit, nullCheckedBlock)) {
- return true;
- }
- }
- // B) ...or indirectly dominated by null-checked blocks.
- // Although the normal exit is not dominated by any of null-checked blocks (because of other
- // paths to the exit), it could be still the case that all possible paths to that exit should
- // pass some of null-checked blocks.
- Set<BasicBlock> visited = Sets.newIdentityHashSet();
- // Initial fan-out of predecessors.
- Deque<BasicBlock> uncoveredPaths = new ArrayDeque<>(normalExit.getPredecessors());
- while (!uncoveredPaths.isEmpty()) {
- BasicBlock uncoveredPath = uncoveredPaths.poll();
- // Stop traversing upwards if we hit the entry block: if the entry block has an non-null,
- // this case should be handled already by A) because the entry block surely dominates all
- // normal exits.
- if (uncoveredPath == code.entryBlock()) {
- return false;
- }
- // Make sure we're not visiting the same block over and over again.
- if (!visited.add(uncoveredPath)) {
- // But, if that block is the last one in the queue, the normal exit is not fully covered.
- if (uncoveredPaths.isEmpty()) {
- return false;
- } else {
- continue;
- }
- }
- boolean pathCovered = false;
- for (BasicBlock nullCheckedBlock : nullCheckedBlocks) {
- if (dominatorTree.dominatedBy(uncoveredPath, nullCheckedBlock)) {
- pathCovered = true;
- break;
- }
- }
- if (!pathCovered) {
- // Fan out predecessors one more level.
- // Note that remaining, unmatched null-checked blocks should cover newly added paths.
- uncoveredPaths.addAll(uncoveredPath.getPredecessors());
- }
- }
- // Reaching here means that every path to the given normal exit is covered by the set of
- // null-checked blocks.
- assert uncoveredPaths.isEmpty();
- return true;
- }
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfoCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfoCollector.java
new file mode 100644
index 0000000..78369e3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfoCollector.java
@@ -0,0 +1,948 @@
+// 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.optimize.info;
+
+import static com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query.DIRECTLY;
+import static com.android.tools.r8.ir.code.DominatorTree.Assumption.MAY_HAVE_UNREACHABLE_BLOCKS;
+
+import com.android.tools.r8.graph.AppView;
+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.DexEncodedMethod.ClassInlinerEligibility;
+import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer;
+import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer.TrivialClassInitializer;
+import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer.TrivialInstanceInitializer;
+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.DexType;
+import com.android.tools.r8.graph.ResolutionResult;
+import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
+import com.android.tools.r8.ir.analysis.DeterminismAnalysis;
+import com.android.tools.r8.ir.analysis.InitializedClassesOnNormalExitAnalysis;
+import com.android.tools.r8.ir.analysis.sideeffect.ClassInitializerSideEffectAnalysis;
+import com.android.tools.r8.ir.analysis.sideeffect.ClassInitializerSideEffectAnalysis.ClassInitializerSideEffect;
+import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.Nullability;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.ConstString;
+import com.android.tools.r8.ir.code.DominatorTree;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.If;
+import com.android.tools.r8.ir.code.InstancePut;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InvokeDirect;
+import com.android.tools.r8.ir.code.NewInstance;
+import com.android.tools.r8.ir.code.Return;
+import com.android.tools.r8.ir.code.StaticPut;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.DynamicTypeOptimization;
+import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsage;
+import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsageBuilder;
+import com.android.tools.r8.kotlin.Kotlin;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.collect.Sets;
+import com.google.common.collect.Streams;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Deque;
+import java.util.List;
+import java.util.Set;
+import java.util.function.BiFunction;
+import java.util.function.Function;
+
+public class MethodOptimizationInfoCollector {
+ private final AppView<?> appView;
+ private final InternalOptions options;
+ private final DexItemFactory dexItemFactory;
+
+ public MethodOptimizationInfoCollector(AppView<?> appView) {
+ this.appView = appView;
+ this.options = appView.options();
+ this.dexItemFactory = appView.dexItemFactory();
+ }
+
+ // TODO(b/141656615): Use this and then make all utils in this collector `private`.
+ public void collectMethodOptimizationInfo(
+ DexEncodedMethod method,
+ IRCode code,
+ OptimizationFeedback feedback,
+ DynamicTypeOptimization dynamicTypeOptimization) {
+ identifyClassInlinerEligibility(method, code, feedback);
+ identifyParameterUsages(method, code, feedback);
+ identifyReturnsArgument(method, code, feedback);
+ identifyTrivialInitializer(method, code, feedback);
+ if (options.enableInlining) {
+ identifyInvokeSemanticsForInlining(method, code, appView, feedback);
+ }
+ computeDynamicReturnType(dynamicTypeOptimization, feedback, method, code);
+ computeInitializedClassesOnNormalExit(feedback, method, code);
+ computeMayHaveSideEffects(feedback, method, code);
+ computeReturnValueOnlyDependsOnArguments(feedback, method, code);
+ computeNonNullParamOrThrow(feedback, method, code);
+ computeNonNullParamOnNormalExits(feedback, code);
+ }
+
+ public void identifyClassInlinerEligibility(
+ DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
+ // Method eligibility is calculated in similar way for regular method
+ // and for the constructor. To be eligible method should only be using its
+ // receiver in the following ways:
+ //
+ // (1) as a receiver of reads/writes of instance fields of the holder class,
+ // (2) as a return value,
+ // (3) as a receiver of a call to the superclass initializer. Note that we don't
+ // check what is passed to superclass initializer as arguments, only check
+ // that it is not the instance being initialized,
+ // (4) as argument to a monitor instruction.
+ //
+ // Note that (4) can safely be removed as the receiver is guaranteed not to escape when we class
+ // inline it, and hence any monitor instructions are no-ops.
+ boolean instanceInitializer = method.isInstanceInitializer();
+ if (method.accessFlags.isNative()
+ || (!method.isNonAbstractVirtualMethod() && !instanceInitializer)) {
+ return;
+ }
+
+ feedback.setClassInlinerEligibility(method, null); // To allow returns below.
+
+ Value receiver = code.getThis();
+ if (receiver.numberOfPhiUsers() > 0) {
+ return;
+ }
+
+ DexClass clazz = appView.definitionFor(method.method.holder);
+ if (clazz == null) {
+ return;
+ }
+
+ boolean receiverUsedAsReturnValue = false;
+ boolean seenSuperInitCall = false;
+ for (Instruction insn : receiver.uniqueUsers()) {
+ if (insn.isMonitor()) {
+ continue;
+ }
+
+ if (insn.isReturn()) {
+ receiverUsedAsReturnValue = true;
+ continue;
+ }
+
+ if (insn.isInstanceGet() || insn.isInstancePut()) {
+ if (insn.isInstancePut()) {
+ InstancePut instancePutInstruction = insn.asInstancePut();
+ // Only allow field writes to the receiver.
+ if (instancePutInstruction.object() != receiver) {
+ return;
+ }
+ // Do not allow the receiver to escape via a field write.
+ if (instancePutInstruction.value() == receiver) {
+ return;
+ }
+ }
+ DexField field = insn.asFieldInstruction().getField();
+ if (field.holder == clazz.type && clazz.lookupInstanceField(field) != null) {
+ // Require only accessing instance fields of the *current* class.
+ continue;
+ }
+ return;
+ }
+
+ // If this is an instance initializer allow one call to superclass instance initializer.
+ if (insn.isInvokeDirect()) {
+ InvokeDirect invokedDirect = insn.asInvokeDirect();
+ DexMethod invokedMethod = invokedDirect.getInvokedMethod();
+ if (dexItemFactory.isConstructor(invokedMethod)
+ && invokedMethod.holder == clazz.superType
+ && invokedDirect.inValues().lastIndexOf(receiver) == 0
+ && !seenSuperInitCall
+ && instanceInitializer) {
+ seenSuperInitCall = true;
+ continue;
+ }
+ // We don't support other direct calls yet.
+ return;
+ }
+
+ // Other receiver usages make the method not eligible.
+ return;
+ }
+ if (instanceInitializer && !seenSuperInitCall) {
+ // Call to super constructor not found?
+ return;
+ }
+
+ feedback.setClassInlinerEligibility(
+ method, new ClassInlinerEligibility(receiverUsedAsReturnValue));
+ }
+
+ public void identifyParameterUsages(
+ DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
+ List<ParameterUsage> usages = new ArrayList<>();
+ List<Value> values = code.collectArguments();
+ for (int i = 0; i < values.size(); i++) {
+ Value value = values.get(i);
+ if (value.numberOfPhiUsers() > 0) {
+ continue;
+ }
+ ParameterUsage usage = collectParameterUsages(i, value);
+ if (usage != null) {
+ usages.add(usage);
+ }
+ }
+ feedback.setParameterUsages(method, usages.isEmpty() ? null : new ParameterUsagesInfo(usages));
+ }
+
+ private ParameterUsage collectParameterUsages(int i, Value value) {
+ ParameterUsageBuilder builder = new ParameterUsageBuilder(value, i);
+ for (Instruction user : value.uniqueUsers()) {
+ if (!builder.note(user)) {
+ return null;
+ }
+ }
+ return builder.build();
+ }
+
+ public void identifyReturnsArgument(
+ DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
+ List<BasicBlock> normalExits = code.computeNormalExitBlocks();
+ if (normalExits.isEmpty()) {
+ feedback.methodNeverReturnsNormally(method);
+ return;
+ }
+ Return firstExit = normalExits.get(0).exit().asReturn();
+ if (firstExit.isReturnVoid()) {
+ return;
+ }
+ Value returnValue = firstExit.returnValue();
+ boolean isNeverNull = returnValue.getTypeLattice().isReference() && returnValue.isNeverNull();
+ for (int i = 1; i < normalExits.size(); i++) {
+ Return exit = normalExits.get(i).exit().asReturn();
+ Value value = exit.returnValue();
+ if (value != returnValue) {
+ returnValue = null;
+ }
+ isNeverNull &= value.getTypeLattice().isReference() && value.isNeverNull();
+ }
+ if (returnValue != null) {
+ if (returnValue.isArgument()) {
+ // Find the argument number.
+ int index = code.collectArguments().indexOf(returnValue);
+ assert index != -1;
+ feedback.methodReturnsArgument(method, index);
+ }
+ if (returnValue.isConstant()) {
+ if (returnValue.definition.isConstNumber()) {
+ long value = returnValue.definition.asConstNumber().getRawValue();
+ feedback.methodReturnsConstantNumber(method, value);
+ } else if (returnValue.definition.isConstString()) {
+ ConstString constStringInstruction = returnValue.definition.asConstString();
+ if (!constStringInstruction.instructionInstanceCanThrow()) {
+ feedback.methodReturnsConstantString(method, constStringInstruction.getValue());
+ }
+ }
+ }
+ }
+ if (isNeverNull) {
+ feedback.methodNeverReturnsNull(method);
+ }
+ }
+
+ public void identifyTrivialInitializer(
+ DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
+ if (!method.isInstanceInitializer() && !method.isClassInitializer()) {
+ return;
+ }
+
+ if (method.accessFlags.isNative()) {
+ return;
+ }
+
+ DexClass clazz = appView.appInfo().definitionFor(method.method.holder);
+ if (clazz == null) {
+ return;
+ }
+
+ feedback.setTrivialInitializer(
+ method,
+ method.isInstanceInitializer()
+ ? computeInstanceInitializerInfo(code, clazz, appView::definitionFor)
+ : computeClassInitializerInfo(code, clazz));
+ }
+
+ // This method defines trivial class initializer as follows:
+ //
+ // ** The initializer may only instantiate an instance of the same class,
+ // initialize it with a call to a trivial constructor *without* arguments,
+ // and assign this instance to a static final field of the same class.
+ //
+ private synchronized TrivialInitializer computeClassInitializerInfo(IRCode code, DexClass clazz) {
+ Value createdSingletonInstance = null;
+ DexField singletonField = null;
+ for (Instruction insn : code.instructions()) {
+ if (insn.isConstNumber()) {
+ continue;
+ }
+
+ if (insn.isConstString()) {
+ if (insn.instructionInstanceCanThrow()) {
+ return null;
+ }
+ continue;
+ }
+
+ if (insn.isReturn()) {
+ continue;
+ }
+
+ if (insn.isNewInstance()) {
+ NewInstance newInstance = insn.asNewInstance();
+ if (createdSingletonInstance != null
+ || newInstance.clazz != clazz.type
+ || insn.outValue() == null) {
+ return null;
+ }
+ createdSingletonInstance = insn.outValue();
+ continue;
+ }
+
+ if (insn.isInvokeDirect()) {
+ InvokeDirect invokedDirect = insn.asInvokeDirect();
+ if (createdSingletonInstance == null
+ || invokedDirect.getReceiver() != createdSingletonInstance) {
+ return null;
+ }
+ DexEncodedMethod callTarget = clazz.lookupDirectMethod(invokedDirect.getInvokedMethod());
+ if (callTarget == null
+ || !callTarget.isInstanceInitializer()
+ || !callTarget.method.proto.parameters.isEmpty()
+ || callTarget.getOptimizationInfo().getTrivialInitializerInfo() == null) {
+ return null;
+ }
+ continue;
+ }
+
+ if (insn.isStaticPut()) {
+ StaticPut staticPut = insn.asStaticPut();
+ if (singletonField != null
+ || createdSingletonInstance == null
+ || staticPut.value() != createdSingletonInstance) {
+ return null;
+ }
+ DexEncodedField field = clazz.lookupStaticField(staticPut.getField());
+ if (field == null
+ || !field.accessFlags.isStatic()
+ || !field.accessFlags.isFinal()) {
+ return null;
+ }
+ singletonField = field.field;
+ continue;
+ }
+
+ // Other instructions make the class initializer not eligible.
+ return null;
+ }
+ return singletonField == null ? null : new TrivialClassInitializer(singletonField);
+ }
+
+ // This method defines trivial instance initializer as follows:
+ //
+ // ** The initializer may call the initializer of the base class, which
+ // itself must be trivial.
+ //
+ // ** java.lang.Object.<init>() is considered trivial.
+ //
+ // ** all arguments passed to a super-class initializer must be non-throwing
+ // constants or arguments.
+ //
+ // ** Assigns arguments or non-throwing constants to fields of this class.
+ //
+ // (Note that this initializer does not have to have zero arguments.)
+ private TrivialInitializer computeInstanceInitializerInfo(
+ IRCode code, DexClass clazz, Function<DexType, DexClass> typeToClass) {
+ Value receiver = code.getThis();
+ for (Instruction insn : code.instructions()) {
+ if (insn.isReturn()) {
+ continue;
+ }
+
+ if (insn.isArgument()) {
+ continue;
+ }
+
+ if (insn.isConstInstruction()) {
+ if (insn.instructionInstanceCanThrow()) {
+ return null;
+ } else {
+ continue;
+ }
+ }
+
+ if (insn.isInvokeDirect()) {
+ InvokeDirect invokedDirect = insn.asInvokeDirect();
+ DexMethod invokedMethod = invokedDirect.getInvokedMethod();
+ if (invokedMethod.holder != clazz.superType) {
+ return null;
+ }
+ // java.lang.Object.<init>() is considered trivial.
+ if (invokedMethod == dexItemFactory.objectMethods.constructor) {
+ continue;
+ }
+ DexClass holder = typeToClass.apply(invokedMethod.holder);
+ if (holder == null) {
+ return null;
+ }
+ DexEncodedMethod callTarget = holder.lookupDirectMethod(invokedMethod);
+ if (callTarget == null
+ || !callTarget.isInstanceInitializer()
+ || callTarget.getOptimizationInfo().getTrivialInitializerInfo() == null
+ || invokedDirect.getReceiver() != receiver) {
+ return null;
+ }
+ for (Value value : invokedDirect.inValues()) {
+ if (value != receiver && !(value.isConstant() || value.isArgument())) {
+ return null;
+ }
+ }
+ continue;
+ }
+
+ if (insn.isInstancePut()) {
+ InstancePut instancePut = insn.asInstancePut();
+ DexEncodedField field = clazz.lookupInstanceField(instancePut.getField());
+ if (field == null
+ || instancePut.object() != receiver
+ || (instancePut.value() != receiver && !instancePut.value().isArgument())) {
+ return null;
+ }
+ continue;
+ }
+
+ if (insn.isGoto()) {
+ // Trivial goto to the next block.
+ if (insn.asGoto().isTrivialGotoToTheNextBlock(code)) {
+ continue;
+ }
+ return null;
+ }
+
+ // Other instructions make the instance initializer not eligible.
+ return null;
+ }
+ return TrivialInstanceInitializer.INSTANCE;
+ }
+
+ public void identifyInvokeSemanticsForInlining(
+ DexEncodedMethod method, IRCode code, AppView<?> appView, OptimizationFeedback feedback) {
+ if (method.isStatic()) {
+ // Identifies if the method preserves class initialization after inlining.
+ feedback.markTriggerClassInitBeforeAnySideEffect(
+ method, triggersClassInitializationBeforeSideEffect(method.method.holder, code, appView));
+ } else {
+ // Identifies if the method preserves null check of the receiver after inlining.
+ final Value receiver = code.getThis();
+ feedback.markCheckNullReceiverBeforeAnySideEffect(
+ method, receiver.isUsed() && checksNullBeforeSideEffect(code, receiver, appView));
+ }
+ }
+
+ /**
+ * Returns true if the given code unconditionally triggers class initialization before any other
+ * side effecting instruction.
+ *
+ * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
+ */
+ private static boolean triggersClassInitializationBeforeSideEffect(
+ DexType clazz, IRCode code, AppView<?> appView) {
+ return alwaysTriggerExpectedEffectBeforeAnythingElse(
+ code,
+ (instruction, it) -> {
+ DexType context = code.method.method.holder;
+ if (instruction.definitelyTriggersClassInitialization(
+ clazz, context, appView, DIRECTLY, AnalysisAssumption.INSTRUCTION_DOES_NOT_THROW)) {
+ // In order to preserve class initialization semantic, the exception must not be caught
+ // by any handler. Therefore, we must ignore this instruction if it is covered by a
+ // catch handler.
+ // Note: this is a conservative approach where we consider that any catch handler could
+ // catch the exception, even if it cannot catch an ExceptionInInitializerError.
+ if (!instruction.getBlock().hasCatchHandlers()) {
+ // We found an instruction that preserves initialization of the class.
+ return InstructionEffect.DESIRED_EFFECT;
+ }
+ } else if (instruction.instructionMayHaveSideEffects(appView, clazz)) {
+ // We found a side effect before class initialization.
+ return InstructionEffect.OTHER_EFFECT;
+ }
+ return InstructionEffect.NO_EFFECT;
+ });
+ }
+
+ /**
+ * Returns true if the given code unconditionally triggers an expected effect before anything
+ * else, false otherwise.
+ *
+ * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
+ */
+ private static boolean alwaysTriggerExpectedEffectBeforeAnythingElse(
+ IRCode code, BiFunction<Instruction, InstructionIterator, InstructionEffect> function) {
+ final int color = code.reserveMarkingColor();
+ try {
+ ArrayDeque<BasicBlock> worklist = new ArrayDeque<>();
+ final BasicBlock entry = code.entryBlock();
+ worklist.add(entry);
+ entry.mark(color);
+
+ while (!worklist.isEmpty()) {
+ BasicBlock currentBlock = worklist.poll();
+ assert currentBlock.isMarked(color);
+
+ InstructionEffect result = InstructionEffect.NO_EFFECT;
+ InstructionIterator it = currentBlock.iterator();
+ while (result == InstructionEffect.NO_EFFECT && it.hasNext()) {
+ result = function.apply(it.next(), it);
+ }
+ if (result == InstructionEffect.OTHER_EFFECT) {
+ // We found an instruction that is causing an unexpected side effect.
+ return false;
+ } else if (result == InstructionEffect.DESIRED_EFFECT) {
+ // The current path is causing the expected effect. No need to go deeper in this path,
+ // go to the next block in the work list.
+ continue;
+ } else if (result == InstructionEffect.CONDITIONAL_EFFECT) {
+ assert !currentBlock.getNormalSuccessors().isEmpty();
+ Instruction lastInstruction = currentBlock.getInstructions().getLast();
+ assert lastInstruction.isIf();
+ // The current path is checking if the value of interest is null. Go deeper into the path
+ // that corresponds to the null value.
+ BasicBlock targetIfReceiverIsNull = lastInstruction.asIf().targetFromCondition(0);
+ if (!targetIfReceiverIsNull.isMarked(color)) {
+ worklist.add(targetIfReceiverIsNull);
+ targetIfReceiverIsNull.mark(color);
+ }
+ } else {
+ assert result == InstructionEffect.NO_EFFECT;
+ // The block did not cause any particular effect.
+ if (currentBlock.getNormalSuccessors().isEmpty()) {
+ // This is the end of the current non-exceptional path and we did not find any expected
+ // effect. It means there is at least one path where the expected effect does not
+ // happen.
+ Instruction lastInstruction = currentBlock.getInstructions().getLast();
+ assert lastInstruction.isReturn() || lastInstruction.isThrow();
+ return false;
+ } else {
+ // Look into successors
+ for (BasicBlock successor : currentBlock.getSuccessors()) {
+ if (!successor.isMarked(color)) {
+ worklist.add(successor);
+ successor.mark(color);
+ }
+ }
+ }
+ }
+ }
+ // If we reach this point, we checked that the expected effect happens in every possible path.
+ return true;
+ } finally {
+ code.returnMarkingColor(color);
+ }
+ }
+
+ /**
+ * Returns true if the given code unconditionally throws if value is null before any other side
+ * effect instruction.
+ *
+ * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
+ */
+ private static boolean checksNullBeforeSideEffect(IRCode code, Value value, AppView<?> appView) {
+ return alwaysTriggerExpectedEffectBeforeAnythingElse(
+ code,
+ (instr, it) -> {
+ BasicBlock currentBlock = instr.getBlock();
+ // If the code explicitly checks the nullability of the value, we should visit the next
+ // block that corresponds to the null value where NPE semantic could be preserved.
+ if (!currentBlock.hasCatchHandlers() && isNullCheck(instr, value)) {
+ return InstructionEffect.CONDITIONAL_EFFECT;
+ }
+ if (isKotlinNullCheck(instr, value, appView)) {
+ DexMethod invokedMethod = instr.asInvokeStatic().getInvokedMethod();
+ // Kotlin specific way of throwing NPE: throwParameterIsNullException.
+ // Similarly, combined with the above CONDITIONAL_EFFECT, the code checks on NPE on
+ // the value.
+ if (invokedMethod.name
+ == appView.dexItemFactory().kotlin.intrinsics.throwParameterIsNullException.name) {
+ // We found a NPE (or similar exception) throwing code.
+ // Combined with the above CONDITIONAL_EFFECT, the code checks NPE on the value.
+ for (BasicBlock predecessor : currentBlock.getPredecessors()) {
+ if (isNullCheck(predecessor.exit(), value)) {
+ return InstructionEffect.DESIRED_EFFECT;
+ }
+ }
+ // Hitting here means that this call might be used for other parameters. If we don't
+ // bail out, it will be regarded as side effects for the current value.
+ return InstructionEffect.NO_EFFECT;
+ } else {
+ // Kotlin specific way of checking parameter nullness: checkParameterIsNotNull.
+ assert invokedMethod.name
+ == appView.dexItemFactory().kotlin.intrinsics.checkParameterIsNotNull.name;
+ return InstructionEffect.DESIRED_EFFECT;
+ }
+ }
+ if (isInstantiationOfNullPointerException(instr, it, appView.dexItemFactory())) {
+ it.next(); // Skip call to NullPointerException.<init>.
+ return InstructionEffect.NO_EFFECT;
+ } else if (instr.throwsNpeIfValueIsNull(value, appView.dexItemFactory())) {
+ // In order to preserve NPE semantic, the exception must not be caught by any handler.
+ // Therefore, we must ignore this instruction if it is covered by a catch handler.
+ // Note: this is a conservative approach where we consider that any catch handler could
+ // catch the exception, even if it cannot catch a NullPointerException.
+ if (!currentBlock.hasCatchHandlers()) {
+ // We found a NPE check on the value.
+ return InstructionEffect.DESIRED_EFFECT;
+ }
+ } else if (instr.instructionMayHaveSideEffects(appView, code.method.method.holder)) {
+ // If the current instruction is const-string, this could load the parameter name.
+ // Just make sure it is indeed not throwing.
+ if (instr.isConstString() && !instr.instructionInstanceCanThrow()) {
+ return InstructionEffect.NO_EFFECT;
+ }
+ // We found a side effect before a NPE check.
+ return InstructionEffect.OTHER_EFFECT;
+ }
+ return InstructionEffect.NO_EFFECT;
+ });
+ }
+
+ /**
+ * An enum used to classify instructions according to a particular effect that they produce.
+ *
+ * The "effect" of an instruction can be seen as a program state change (or semantic change) at
+ * runtime execution. For example, an instruction could cause the initialization of a class,
+ * change the value of a field, ... while other instructions do not.
+ *
+ * This classification also depends on the type of analysis that is using it. For instance, an
+ * analysis can look for instructions that cause class initialization while another look for
+ * instructions that check nullness of a particular object.
+ *
+ * On the other hand, some instructions may provide a non desired effect which is a signal for
+ * the analysis to stop.
+ */
+ private enum InstructionEffect {
+ DESIRED_EFFECT,
+ CONDITIONAL_EFFECT,
+ OTHER_EFFECT,
+ NO_EFFECT
+ }
+
+ // Note that this method may have false positives, since the application could in principle
+ // declare a method called checkParameterIsNotNull(parameter, message) or
+ // throwParameterIsNullException(parameterName) in a package that starts with "kotlin".
+ private static boolean isKotlinNullCheck(Instruction instr, Value value, AppView<?> appView) {
+ if (!instr.isInvokeStatic()) {
+ return false;
+ }
+ // We need to strip the holder, since Kotlin adds different versions of null-check machinery,
+ // e.g., kotlin.collections.ArraysKt___ArraysKt... or kotlin.jvm.internal.ArrayIteratorKt...
+ MethodSignatureEquivalence wrapper = MethodSignatureEquivalence.get();
+ Wrapper<DexMethod> checkParameterIsNotNull =
+ wrapper.wrap(appView.dexItemFactory().kotlin.intrinsics.checkParameterIsNotNull);
+ Wrapper<DexMethod> throwParamIsNullException =
+ wrapper.wrap(appView.dexItemFactory().kotlin.intrinsics.throwParameterIsNullException);
+ DexMethod invokedMethod =
+ appView.graphLense().getOriginalMethodSignature(instr.asInvokeStatic().getInvokedMethod());
+ Wrapper<DexMethod> methodWrap = wrapper.wrap(invokedMethod);
+ if (methodWrap.equals(throwParamIsNullException)
+ || (methodWrap.equals(checkParameterIsNotNull) && instr.inValues().get(0).equals(value))) {
+ if (invokedMethod.holder.getPackageDescriptor().startsWith(Kotlin.NAME)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private static boolean isNullCheck(Instruction instr, Value value) {
+ return instr.isIf() && instr.asIf().isZeroTest()
+ && instr.inValues().get(0).equals(value)
+ && (instr.asIf().getType() == If.Type.EQ || instr.asIf().getType() == If.Type.NE);
+ }
+
+ /**
+ * Returns true if the given instruction is {@code v <- new-instance NullPointerException}, and
+ * the next instruction is {@code invoke-direct v, NullPointerException.<init>()}.
+ */
+ private static boolean isInstantiationOfNullPointerException(
+ Instruction instruction, InstructionIterator it, DexItemFactory dexItemFactory) {
+ if (!instruction.isNewInstance()
+ || instruction.asNewInstance().clazz != dexItemFactory.npeType) {
+ return false;
+ }
+ Instruction next = it.peekNext();
+ if (next == null
+ || !next.isInvokeDirect()
+ || next.asInvokeDirect().getInvokedMethod() != dexItemFactory.npeMethods.init) {
+ return false;
+ }
+ return true;
+ }
+
+ public void computeDynamicReturnType(
+ DynamicTypeOptimization dynamicTypeOptimization,
+ OptimizationFeedback feedback,
+ DexEncodedMethod method,
+ IRCode code) {
+ if (dynamicTypeOptimization != null) {
+ DexType staticReturnTypeRaw = method.method.proto.returnType;
+ if (!staticReturnTypeRaw.isReferenceType()) {
+ return;
+ }
+ TypeLatticeElement dynamicReturnType =
+ dynamicTypeOptimization.computeDynamicReturnType(method, code);
+ if (dynamicReturnType != null) {
+ TypeLatticeElement staticReturnType =
+ TypeLatticeElement.fromDexType(staticReturnTypeRaw, Nullability.maybeNull(), appView);
+ // If the dynamic return type is not more precise than the static return type there is no
+ // need to record it.
+ if (dynamicReturnType.strictlyLessThan(staticReturnType, appView)) {
+ feedback.methodReturnsObjectOfType(method, appView, dynamicReturnType);
+ }
+ }
+ ClassTypeLatticeElement exactReturnType =
+ dynamicTypeOptimization.computeDynamicLowerBoundType(method, code);
+ if (exactReturnType != null) {
+ feedback.methodReturnsObjectWithLowerBoundType(method, exactReturnType);
+ }
+ }
+ }
+
+ public void computeInitializedClassesOnNormalExit(
+ OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
+ if (options.enableInitializedClassesAnalysis && appView.appInfo().hasLiveness()) {
+ AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+ Set<DexType> initializedClasses =
+ InitializedClassesOnNormalExitAnalysis.computeInitializedClassesOnNormalExit(
+ appViewWithLiveness, code);
+ if (initializedClasses != null && !initializedClasses.isEmpty()) {
+ feedback.methodInitializesClassesOnNormalExit(method, initializedClasses);
+ }
+ }
+ }
+
+ public void computeMayHaveSideEffects(
+ OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
+ // If the method is native, we don't know what could happen.
+ assert !method.accessFlags.isNative();
+ if (!options.enableSideEffectAnalysis) {
+ return;
+ }
+ if (appView.appInfo().withLiveness().mayHaveSideEffects.containsKey(method.method)) {
+ return;
+ }
+ DexType context = method.method.holder;
+ if (method.isClassInitializer()) {
+ // For class initializers, we also wish to compute if the class initializer has observable
+ // side effects.
+ ClassInitializerSideEffect classInitializerSideEffect =
+ ClassInitializerSideEffectAnalysis.classInitializerCanBePostponed(appView, code);
+ if (classInitializerSideEffect.isNone()) {
+ feedback.methodMayNotHaveSideEffects(method);
+ feedback.classInitializerMayBePostponed(method);
+ } else if (classInitializerSideEffect.canBePostponed()) {
+ feedback.classInitializerMayBePostponed(method);
+ }
+ return;
+ }
+ boolean mayHaveSideEffects;
+ if (method.accessFlags.isSynchronized()) {
+ // If the method is synchronized then it acquires a lock.
+ mayHaveSideEffects = true;
+ } else if (method.isInstanceInitializer() && hasNonTrivialFinalizeMethod(context)) {
+ // If a class T overrides java.lang.Object.finalize(), then treat the constructor as having
+ // side effects. This ensures that we won't remove instructions on the form `new-instance
+ // {v0}, T`.
+ mayHaveSideEffects = true;
+ } else {
+ // Otherwise, check if there is an instruction that has side effects.
+ mayHaveSideEffects =
+ Streams.stream(code.instructions())
+ .anyMatch(instruction -> instruction.instructionMayHaveSideEffects(appView, context));
+ }
+ if (!mayHaveSideEffects) {
+ feedback.methodMayNotHaveSideEffects(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) {
+ DexClass clazz = appView.definitionFor(type);
+ if (clazz != null) {
+ if (clazz.isProgramClass() && !clazz.isInterface()) {
+ ResolutionResult resolutionResult =
+ appView
+ .appInfo()
+ .resolveMethodOnClass(clazz, appView.dexItemFactory().objectMethods.finalize);
+ for (DexEncodedMethod target : resolutionResult.asListOfTargets()) {
+ if (target.method != appView.dexItemFactory().objectMethods.finalize) {
+ return true;
+ }
+ }
+ return false;
+ } else {
+ // Conservatively report that the library class could implement finalize().
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public void computeReturnValueOnlyDependsOnArguments(
+ OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
+ if (!options.enableDeterminismAnalysis) {
+ return;
+ }
+ boolean returnValueOnlyDependsOnArguments =
+ DeterminismAnalysis.returnValueOnlyDependsOnArguments(appView.withLiveness(), code);
+ if (returnValueOnlyDependsOnArguments) {
+ feedback.methodReturnValueOnlyDependsOnArguments(method);
+ }
+ }
+
+ // Track usage of parameters and compute their nullability and possibility of NPE.
+ public void computeNonNullParamOrThrow(
+ OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
+ if (method.getOptimizationInfo().getNonNullParamOrThrow() != null) {
+ return;
+ }
+ List<Value> arguments = code.collectArguments();
+ BitSet paramsCheckedForNull = new BitSet();
+ for (int index = 0; index < arguments.size(); index++) {
+ Value argument = arguments.get(index);
+ // This handles cases where the parameter is checked via Kotlin Intrinsics:
+ //
+ // kotlin.jvm.internal.Intrinsics.checkParameterIsNotNull(param, message)
+ //
+ // or its inlined version:
+ //
+ // if (param != null) return;
+ // invoke-static throwParameterIsNullException(msg)
+ //
+ // or some other variants, e.g., throw null or NPE after the direct null check.
+ if (argument.isUsed() && checksNullBeforeSideEffect(code, argument, appView)) {
+ paramsCheckedForNull.set(index);
+ }
+ }
+ if (paramsCheckedForNull.length() > 0) {
+ feedback.setNonNullParamOrThrow(method, paramsCheckedForNull);
+ }
+ }
+
+ public void computeNonNullParamOnNormalExits(OptimizationFeedback feedback, IRCode code) {
+ Set<BasicBlock> normalExits = Sets.newIdentityHashSet();
+ normalExits.addAll(code.computeNormalExitBlocks());
+ DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
+ List<Value> arguments = code.collectArguments();
+ BitSet facts = new BitSet();
+ Set<BasicBlock> nullCheckedBlocks = Sets.newIdentityHashSet();
+ for (int index = 0; index < arguments.size(); index++) {
+ Value argument = arguments.get(index);
+ // Consider reference-type parameter only.
+ if (!argument.getTypeLattice().isReference()) {
+ continue;
+ }
+ // The receiver is always non-null on normal exits.
+ if (argument.isThis()) {
+ facts.set(index);
+ continue;
+ }
+ // Collect basic blocks that check nullability of the parameter.
+ nullCheckedBlocks.clear();
+ for (Instruction user : argument.uniqueUsers()) {
+ if (user.isAssumeNonNull()) {
+ nullCheckedBlocks.add(user.asAssumeNonNull().getBlock());
+ }
+ if (user.isIf()
+ && user.asIf().isZeroTest()
+ && (user.asIf().getType() == If.Type.EQ || user.asIf().getType() == If.Type.NE)) {
+ nullCheckedBlocks.add(user.asIf().targetFromNonNullObject());
+ }
+ }
+ if (!nullCheckedBlocks.isEmpty()) {
+ boolean allExitsCovered = true;
+ for (BasicBlock normalExit : normalExits) {
+ if (!isNormalExitDominated(normalExit, code, dominatorTree, nullCheckedBlocks)) {
+ allExitsCovered = false;
+ break;
+ }
+ }
+ if (allExitsCovered) {
+ facts.set(index);
+ }
+ }
+ }
+ if (facts.length() > 0) {
+ feedback.setNonNullParamOnNormalExits(code.method, facts);
+ }
+ }
+
+ private boolean isNormalExitDominated(
+ BasicBlock normalExit,
+ IRCode code,
+ DominatorTree dominatorTree,
+ Set<BasicBlock> nullCheckedBlocks) {
+ // Each normal exit should be...
+ for (BasicBlock nullCheckedBlock : nullCheckedBlocks) {
+ // A) ...directly dominated by any null-checked block.
+ if (dominatorTree.dominatedBy(normalExit, nullCheckedBlock)) {
+ return true;
+ }
+ }
+ // B) ...or indirectly dominated by null-checked blocks.
+ // Although the normal exit is not dominated by any of null-checked blocks (because of other
+ // paths to the exit), it could be still the case that all possible paths to that exit should
+ // pass some of null-checked blocks.
+ Set<BasicBlock> visited = Sets.newIdentityHashSet();
+ // Initial fan-out of predecessors.
+ Deque<BasicBlock> uncoveredPaths = new ArrayDeque<>(normalExit.getPredecessors());
+ while (!uncoveredPaths.isEmpty()) {
+ BasicBlock uncoveredPath = uncoveredPaths.poll();
+ // Stop traversing upwards if we hit the entry block: if the entry block has an non-null,
+ // this case should be handled already by A) because the entry block surely dominates all
+ // normal exits.
+ if (uncoveredPath == code.entryBlock()) {
+ return false;
+ }
+ // Make sure we're not visiting the same block over and over again.
+ if (!visited.add(uncoveredPath)) {
+ // But, if that block is the last one in the queue, the normal exit is not fully covered.
+ if (uncoveredPaths.isEmpty()) {
+ return false;
+ } else {
+ continue;
+ }
+ }
+ boolean pathCovered = false;
+ for (BasicBlock nullCheckedBlock : nullCheckedBlocks) {
+ if (dominatorTree.dominatedBy(uncoveredPath, nullCheckedBlock)) {
+ pathCovered = true;
+ break;
+ }
+ }
+ if (!pathCovered) {
+ // Fan out predecessors one more level.
+ // Note that remaining, unmatched null-checked blocks should cover newly added paths.
+ uncoveredPaths.addAll(uncoveredPath.getPredecessors());
+ }
+ }
+ // Reaching here means that every path to the given normal exit is covered by the set of
+ // null-checked blocks.
+ assert uncoveredPaths.isEmpty();
+ return true;
+ }
+}
