| // 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 static com.android.tools.r8.ir.code.Opcodes.ADD; |
| import static com.android.tools.r8.ir.code.Opcodes.AND; |
| import static com.android.tools.r8.ir.code.Opcodes.ARGUMENT; |
| import static com.android.tools.r8.ir.code.Opcodes.ARRAY_LENGTH; |
| import static com.android.tools.r8.ir.code.Opcodes.ASSUME; |
| import static com.android.tools.r8.ir.code.Opcodes.CHECK_CAST; |
| import static com.android.tools.r8.ir.code.Opcodes.CMP; |
| import static com.android.tools.r8.ir.code.Opcodes.CONST_CLASS; |
| import static com.android.tools.r8.ir.code.Opcodes.CONST_NUMBER; |
| import static com.android.tools.r8.ir.code.Opcodes.CONST_STRING; |
| import static com.android.tools.r8.ir.code.Opcodes.DEX_ITEM_BASED_CONST_STRING; |
| import static com.android.tools.r8.ir.code.Opcodes.DIV; |
| import static com.android.tools.r8.ir.code.Opcodes.GOTO; |
| import static com.android.tools.r8.ir.code.Opcodes.IF; |
| import static com.android.tools.r8.ir.code.Opcodes.INSTANCE_GET; |
| import static com.android.tools.r8.ir.code.Opcodes.INSTANCE_OF; |
| import static com.android.tools.r8.ir.code.Opcodes.INSTANCE_PUT; |
| import static com.android.tools.r8.ir.code.Opcodes.INVOKE_DIRECT; |
| import static com.android.tools.r8.ir.code.Opcodes.INVOKE_INTERFACE; |
| import static com.android.tools.r8.ir.code.Opcodes.INVOKE_NEW_ARRAY; |
| import static com.android.tools.r8.ir.code.Opcodes.INVOKE_STATIC; |
| import static com.android.tools.r8.ir.code.Opcodes.INVOKE_VIRTUAL; |
| import static com.android.tools.r8.ir.code.Opcodes.MONITOR; |
| import static com.android.tools.r8.ir.code.Opcodes.MUL; |
| import static com.android.tools.r8.ir.code.Opcodes.NEW_ARRAY_EMPTY; |
| import static com.android.tools.r8.ir.code.Opcodes.NEW_INSTANCE; |
| import static com.android.tools.r8.ir.code.Opcodes.OR; |
| import static com.android.tools.r8.ir.code.Opcodes.REM; |
| import static com.android.tools.r8.ir.code.Opcodes.RETURN; |
| import static com.android.tools.r8.ir.code.Opcodes.SHL; |
| import static com.android.tools.r8.ir.code.Opcodes.SHR; |
| import static com.android.tools.r8.ir.code.Opcodes.STATIC_GET; |
| import static com.android.tools.r8.ir.code.Opcodes.SUB; |
| import static com.android.tools.r8.ir.code.Opcodes.THROW; |
| import static com.android.tools.r8.ir.code.Opcodes.USHR; |
| import static com.android.tools.r8.ir.code.Opcodes.XOR; |
| |
| 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.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.analysis.value.AbstractValue; |
| import com.android.tools.r8.ir.code.AliasedValueConfiguration; |
| import com.android.tools.r8.ir.code.AssumeAndCheckCastAliasedValueConfiguration; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.DominatorTree; |
| 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.InstancePut; |
| import com.android.tools.r8.ir.code.Instruction; |
| import com.android.tools.r8.ir.code.InstructionIterator; |
| import com.android.tools.r8.ir.code.Invoke; |
| import com.android.tools.r8.ir.code.InvokeDirect; |
| import com.android.tools.r8.ir.code.InvokeMethod; |
| import com.android.tools.r8.ir.code.InvokeNewArray; |
| import com.android.tools.r8.ir.code.InvokeVirtual; |
| import com.android.tools.r8.ir.code.NewInstance; |
| import com.android.tools.r8.ir.code.Return; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.optimize.DynamicTypeOptimization; |
| import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo; |
| import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerReceiverAnalysis; |
| 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.optimize.info.initializer.DefaultInstanceInitializerInfo; |
| import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo; |
| import com.android.tools.r8.ir.optimize.info.initializer.NonTrivialInstanceInitializerInfo; |
| 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.ListUtils; |
| import com.android.tools.r8.utils.MethodSignatureEquivalence; |
| import com.android.tools.r8.utils.Pair; |
| 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.Predicate; |
| |
| public class MethodOptimizationInfoCollector { |
| private final AppView<AppInfoWithLiveness> appView; |
| private final InternalOptions options; |
| private final DexItemFactory dexItemFactory; |
| |
| public MethodOptimizationInfoCollector(AppView<AppInfoWithLiveness> appView) { |
| this.appView = appView; |
| this.options = appView.options(); |
| this.dexItemFactory = appView.dexItemFactory(); |
| } |
| |
| public void collectMethodOptimizationInfo( |
| DexEncodedMethod method, |
| IRCode code, |
| OptimizationFeedback feedback, |
| DynamicTypeOptimization dynamicTypeOptimization) { |
| identifyClassInlinerEligibility(method, code, feedback); |
| identifyParameterUsages(method, code, feedback); |
| identifyReturnsArgument(method, code, feedback); |
| if (options.enableInlining) { |
| identifyInvokeSemanticsForInlining(method, code, appView, feedback); |
| } |
| computeDynamicReturnType(dynamicTypeOptimization, feedback, method, code); |
| computeInitializedClassesOnNormalExit(feedback, method, code); |
| computeInstanceInitializerInfo(method, code, feedback); |
| computeMayHaveSideEffects(feedback, method, code); |
| computeReturnValueOnlyDependsOnArguments(feedback, method, code); |
| computeNonNullParamOrThrow(feedback, method, code); |
| computeNonNullParamOnNormalExits(feedback, code); |
| } |
| |
| private 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; |
| } |
| |
| List<Pair<Invoke.Type, DexMethod>> callsReceiver = new ArrayList<>(); |
| boolean seenSuperInitCall = false; |
| boolean seenMonitor = false; |
| |
| AliasedValueConfiguration configuration = |
| AssumeAndCheckCastAliasedValueConfiguration.getInstance(); |
| Predicate<Value> isReceiverAlias = value -> value.getAliasedValue(configuration) == receiver; |
| for (Instruction insn : receiver.aliasedUsers(configuration)) { |
| switch (insn.opcode()) { |
| case ASSUME: |
| case CHECK_CAST: |
| case RETURN: |
| break; |
| |
| case MONITOR: |
| seenMonitor = true; |
| break; |
| |
| case INSTANCE_GET: |
| case INSTANCE_PUT: |
| { |
| if (insn.isInstancePut()) { |
| InstancePut instancePutInstruction = insn.asInstancePut(); |
| // Only allow field writes to the receiver. |
| if (!isReceiverAlias.test(instancePutInstruction.object())) { |
| return; |
| } |
| // Do not allow the receiver to escape via a field write. |
| if (isReceiverAlias.test(instancePutInstruction.value())) { |
| return; |
| } |
| } |
| DexField field = insn.asFieldInstruction().getField(); |
| if (appView.appInfo().resolveFieldOn(clazz, field) != null) { |
| // Require only accessing direct or indirect instance fields of the current class. |
| break; |
| } |
| return; |
| } |
| |
| case INVOKE_DIRECT: |
| { |
| InvokeDirect invoke = insn.asInvokeDirect(); |
| DexMethod invokedMethod = invoke.getInvokedMethod(); |
| if (dexItemFactory.isConstructor(invokedMethod) |
| && invokedMethod.holder == clazz.superType |
| && ListUtils.lastIndexMatching(invoke.arguments(), isReceiverAlias) == 0 |
| && !seenSuperInitCall |
| && instanceInitializer) { |
| seenSuperInitCall = true; |
| break; |
| } |
| // We don't support other direct calls yet. |
| return; |
| } |
| |
| case INVOKE_VIRTUAL: |
| { |
| InvokeVirtual invoke = insn.asInvokeVirtual(); |
| if (ListUtils.lastIndexMatching(invoke.arguments(), isReceiverAlias) != 0) { |
| return; // Not allowed. |
| } |
| DexMethod invokedMethod = invoke.getInvokedMethod(); |
| DexType returnType = invokedMethod.proto.returnType; |
| if (returnType.isClassType() |
| && appView.appInfo().isRelatedBySubtyping(returnType, method.method.holder)) { |
| return; // Not allowed, could introduce an alias of the receiver. |
| } |
| callsReceiver.add(new Pair<>(Invoke.Type.VIRTUAL, invokedMethod)); |
| } |
| break; |
| |
| default: |
| // Other receiver usages make the method not eligible. |
| return; |
| } |
| } |
| |
| if (instanceInitializer && !seenSuperInitCall) { |
| // Call to super constructor not found? |
| return; |
| } |
| |
| boolean synchronizedVirtualMethod = |
| method.accessFlags.isSynchronized() && method.isVirtualMethod(); |
| |
| feedback.setClassInlinerEligibility( |
| method, |
| new ClassInlinerEligibilityInfo( |
| callsReceiver, |
| new ClassInlinerReceiverAnalysis(appView, method, code).computeReturnsReceiver(), |
| seenMonitor || synchronizedVirtualMethod)); |
| } |
| |
| private 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() |
| ? DefaultMethodOptimizationInfo.UNKNOWN_PARAMETER_USAGE_INFO |
| : new ParameterUsagesInfo(usages)); |
| } |
| |
| private ParameterUsage collectParameterUsages(int i, Value value) { |
| ParameterUsageBuilder builder = new ParameterUsageBuilder(value, i); |
| for (Instruction user : value.aliasedUsers()) { |
| if (!builder.note(user)) { |
| return null; |
| } |
| } |
| return builder.build(); |
| } |
| |
| private 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) { |
| Value aliasedValue = returnValue.getAliasedValue(); |
| if (!aliasedValue.isPhi()) { |
| Instruction definition = aliasedValue.definition; |
| if (definition.isArgument()) { |
| // Find the argument number. |
| int index = aliasedValue.computeArgumentPosition(code); |
| assert index >= 0; |
| feedback.methodReturnsArgument(method, index); |
| } |
| DexType context = method.method.holder; |
| AbstractValue abstractReturnValue = definition.getAbstractValue(appView, context); |
| if (abstractReturnValue.isNonTrivial()) { |
| feedback.methodReturnsAbstractValue(method, appView, abstractReturnValue); |
| } |
| } |
| } |
| if (isNeverNull) { |
| feedback.methodNeverReturnsNull(method); |
| } |
| } |
| |
| private void computeInstanceInitializerInfo( |
| DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) { |
| assert !appView.appInfo().isPinned(method.method); |
| |
| if (!method.isInstanceInitializer()) { |
| return; |
| } |
| |
| if (method.accessFlags.isNative()) { |
| return; |
| } |
| |
| if (appView.appInfo().mayHaveSideEffects.containsKey(method.method)) { |
| return; |
| } |
| |
| DexClass clazz = appView.appInfo().definitionFor(method.method.holder); |
| if (clazz == null) { |
| assert false; |
| return; |
| } |
| |
| InstanceInitializerInfo instanceInitializerInfo = analyzeInstanceInitializer(code, clazz); |
| feedback.setInstanceInitializerInfo( |
| method, |
| instanceInitializerInfo != null |
| ? instanceInitializerInfo |
| : DefaultInstanceInitializerInfo.getInstance()); |
| } |
| |
| // This method defines trivial instance initializer as follows: |
| // |
| // ** The holder class must not define a finalize method. |
| // |
| // ** 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 InstanceInitializerInfo analyzeInstanceInitializer(IRCode code, DexClass clazz) { |
| if (clazz.definesFinalizer(options.itemFactory)) { |
| // Defining a finalize method can observe the side-effect of Object.<init> GC registration. |
| return null; |
| } |
| |
| NonTrivialInstanceInitializerInfo.Builder builder = NonTrivialInstanceInitializerInfo.builder(); |
| Value receiver = code.getThis(); |
| boolean hasCatchHandler = false; |
| for (BasicBlock block : code.blocks) { |
| if (block.hasCatchHandlers()) { |
| hasCatchHandler = true; |
| } |
| |
| for (Instruction instruction : block.getInstructions()) { |
| switch (instruction.opcode()) { |
| case ARGUMENT: |
| case ASSUME: |
| case CONST_NUMBER: |
| case GOTO: |
| case RETURN: |
| break; |
| |
| case IF: |
| builder.setInstanceFieldInitializationMayDependOnEnvironment(); |
| break; |
| |
| case ADD: |
| case AND: |
| case ARRAY_LENGTH: |
| case CHECK_CAST: |
| case CMP: |
| case CONST_CLASS: |
| case CONST_STRING: |
| case DEX_ITEM_BASED_CONST_STRING: |
| case DIV: |
| case INSTANCE_OF: |
| case MUL: |
| case NEW_ARRAY_EMPTY: |
| case OR: |
| case REM: |
| case SHL: |
| case SHR: |
| case SUB: |
| case THROW: |
| case USHR: |
| case XOR: |
| // These instructions types may raise an exception, which is a side effect. None of the |
| // instructions can trigger class initialization side effects, hence it is not necessary |
| // to mark all fields as potentially being read. Also, none of the instruction types |
| // can cause the receiver to escape. |
| if (instruction.instructionMayHaveSideEffects(appView, clazz.type)) { |
| builder.setMayHaveOtherSideEffectsThanInstanceFieldAssignments(); |
| } |
| break; |
| |
| case INSTANCE_GET: |
| case STATIC_GET: |
| { |
| FieldInstruction fieldGet = instruction.asFieldInstruction(); |
| DexEncodedField field = appView.appInfo().resolveField(fieldGet.getField()); |
| if (field == null) { |
| return null; |
| } |
| builder.markFieldAsRead(field); |
| if (fieldGet.instructionMayHaveSideEffects(appView, clazz.type)) { |
| builder.setMayHaveOtherSideEffectsThanInstanceFieldAssignments(); |
| if (fieldGet.isStaticGet()) { |
| // It could trigger a class initializer. |
| builder.markAllFieldsAsRead(); |
| } |
| } |
| } |
| break; |
| |
| case INSTANCE_PUT: |
| { |
| InstancePut instancePut = instruction.asInstancePut(); |
| DexEncodedField field = appView.appInfo().resolveField(instancePut.getField()); |
| if (field == null) { |
| return null; |
| } |
| if (instancePut.object().getAliasedValue() != receiver |
| || instancePut.instructionInstanceCanThrow(appView, clazz.type).isThrowing()) { |
| builder.setMayHaveOtherSideEffectsThanInstanceFieldAssignments(); |
| } |
| |
| Value value = instancePut.value().getAliasedValue(); |
| // TODO(b/142762134): Replace the use of onlyDependsOnArgument() by |
| // ValueMayDependOnEnvironmentAnalysis. |
| if (!value.onlyDependsOnArgument()) { |
| builder.setInstanceFieldInitializationMayDependOnEnvironment(); |
| } |
| if (value == receiver) { |
| builder.setReceiverMayEscapeOutsideConstructorChain(); |
| } |
| } |
| break; |
| |
| case INVOKE_DIRECT: |
| { |
| InvokeDirect invoke = instruction.asInvokeDirect(); |
| DexMethod invokedMethod = invoke.getInvokedMethod(); |
| DexEncodedMethod singleTarget = appView.definitionFor(invokedMethod); |
| if (singleTarget == null) { |
| return null; |
| } |
| if (singleTarget.isInstanceInitializer() && invoke.getReceiver() == receiver) { |
| if (builder.hasParent()) { |
| return null; |
| } |
| // java.lang.Enum.<init>() and java.lang.Object.<init>() are considered trivial. |
| if (invokedMethod == dexItemFactory.enumMethods.constructor |
| || invokedMethod == dexItemFactory.objectMethods.constructor) { |
| builder.setParent(invokedMethod); |
| break; |
| } |
| builder.merge(singleTarget.getOptimizationInfo().getInstanceInitializerInfo()); |
| for (int i = 1; i < invoke.arguments().size(); i++) { |
| Value argument = invoke.arguments().get(i).getAliasedValue(); |
| if (argument == receiver) { |
| // In the analysis of the parent constructor, we don't consider the non-receiver |
| // arguments as being aliases of the receiver. Therefore, we explicitly mark |
| // that the receiver escapes from this constructor. |
| builder.setReceiverMayEscapeOutsideConstructorChain(); |
| } |
| if (!argument.onlyDependsOnArgument()) { |
| // If the parent constructor assigns this argument into a field, then the value |
| // of the field may depend on the environment. |
| builder.setInstanceFieldInitializationMayDependOnEnvironment(); |
| } |
| } |
| builder.setParent(invokedMethod); |
| } else { |
| builder |
| .markAllFieldsAsRead() |
| .setMayHaveOtherSideEffectsThanInstanceFieldAssignments(); |
| for (Value inValue : invoke.inValues()) { |
| if (inValue.getAliasedValue() == receiver) { |
| builder.setReceiverMayEscapeOutsideConstructorChain(); |
| break; |
| } |
| } |
| } |
| } |
| break; |
| |
| case INVOKE_NEW_ARRAY: |
| { |
| InvokeNewArray invoke = instruction.asInvokeNewArray(); |
| if (invoke.instructionMayHaveSideEffects(appView, clazz.type)) { |
| builder.setMayHaveOtherSideEffectsThanInstanceFieldAssignments(); |
| } |
| for (Value argument : invoke.arguments()) { |
| if (argument.getAliasedValue() == receiver) { |
| builder.setReceiverMayEscapeOutsideConstructorChain(); |
| break; |
| } |
| } |
| } |
| break; |
| |
| case INVOKE_INTERFACE: |
| case INVOKE_STATIC: |
| case INVOKE_VIRTUAL: |
| { |
| InvokeMethod invoke = instruction.asInvokeMethod(); |
| builder |
| .markAllFieldsAsRead() |
| .setMayHaveOtherSideEffectsThanInstanceFieldAssignments(); |
| for (Value argument : invoke.arguments()) { |
| if (argument.getAliasedValue() == receiver) { |
| builder.setReceiverMayEscapeOutsideConstructorChain(); |
| break; |
| } |
| } |
| } |
| break; |
| |
| case NEW_INSTANCE: |
| { |
| NewInstance newInstance = instruction.asNewInstance(); |
| if (newInstance.instructionMayHaveSideEffects(appView, clazz.type)) { |
| // It could trigger a class initializer. |
| builder |
| .markAllFieldsAsRead() |
| .setMayHaveOtherSideEffectsThanInstanceFieldAssignments(); |
| } |
| } |
| break; |
| |
| default: |
| builder |
| .markAllFieldsAsRead() |
| .setInstanceFieldInitializationMayDependOnEnvironment() |
| .setMayHaveOtherSideEffectsThanInstanceFieldAssignments() |
| .setReceiverMayEscapeOutsideConstructorChain(); |
| break; |
| } |
| } |
| } |
| |
| // In presence of exceptional control flow, the assignments to the instance fields could depend |
| // on the environment, if there is an instruction that could throw. |
| // |
| // Example: |
| // void <init>() { |
| // try { |
| // throwIfTrue(Environment.STATIC_FIELD); |
| // } catch (Exception e) { |
| // this.f = 42; |
| // } |
| // } |
| if (hasCatchHandler && builder.mayHaveOtherSideEffectsThanInstanceFieldAssignments()) { |
| builder.setInstanceFieldInitializationMayDependOnEnvironment(); |
| } |
| |
| return builder.build(); |
| } |
| |
| private 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 (appView.options().kotlinOptimizationOptions().disableKotlinSpecificOptimizations) { |
| return false; |
| } |
| 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; |
| } |
| |
| private 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.methodReturnsObjectWithUpperBoundType(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().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); |
| } else { |
| assert !context.isD8R8SynthesizedLambdaClassType() |
| || options.debug |
| || appView.appInfo().hasPinnedInstanceInitializer(context) |
| : "Unexpected observable side effects from lambda `" + context.toSourceString() + "`"; |
| } |
| 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()) { |
| DexItemFactory dexItemFactory = appView.dexItemFactory(); |
| ResolutionResult resolutionResult = |
| appView |
| .appInfo() |
| .resolveMethodOnClass(clazz, appView.dexItemFactory().objectMethods.finalize); |
| |
| DexEncodedMethod target = resolutionResult.getSingleTarget(); |
| if (target != null |
| && target.method != dexItemFactory.enumMethods.finalize |
| && target.method != dexItemFactory.objectMethods.finalize) { |
| return true; |
| } |
| return false; |
| } else { |
| // Conservatively report that the library class could implement finalize(). |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| 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); |
| } |
| } |
| |
| // 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 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; |
| } |
| } |
