| // Copyright (c) 2018, 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.classinliner; |
| |
| import com.android.tools.r8.errors.Unreachable; |
| import com.android.tools.r8.graph.AppInfo; |
| import com.android.tools.r8.graph.AppInfoWithSubtyping; |
| import com.android.tools.r8.graph.DexClass; |
| import com.android.tools.r8.graph.DexEncodedMethod; |
| import com.android.tools.r8.graph.DexEncodedMethod.ClassInlinerEligibility; |
| 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.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.ConstNumber; |
| import com.android.tools.r8.ir.code.IRCode; |
| import com.android.tools.r8.ir.code.InstanceGet; |
| import com.android.tools.r8.ir.code.Instruction; |
| import com.android.tools.r8.ir.code.InstructionListIterator; |
| import com.android.tools.r8.ir.code.InvokeDirect; |
| import com.android.tools.r8.ir.code.InvokeMethodWithReceiver; |
| import com.android.tools.r8.ir.code.NewInstance; |
| import com.android.tools.r8.ir.code.Phi; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.code.ValueType; |
| import com.android.tools.r8.ir.optimize.Inliner.InliningInfo; |
| import com.android.tools.r8.ir.optimize.Inliner.Reason; |
| import com.google.common.collect.Streams; |
| import java.util.ArrayList; |
| import java.util.IdentityHashMap; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Map.Entry; |
| import java.util.concurrent.ConcurrentHashMap; |
| import java.util.function.Predicate; |
| import java.util.stream.Collectors; |
| |
| public final class ClassInliner { |
| private final DexItemFactory factory; |
| private final int totalMethodInstructionLimit; |
| private final ConcurrentHashMap<DexType, Boolean> knownClasses = new ConcurrentHashMap<>(); |
| |
| public interface InlinerAction { |
| void inline(Map<InvokeMethodWithReceiver, InliningInfo> methods); |
| } |
| |
| public ClassInliner(DexItemFactory factory, int totalMethodInstructionLimit) { |
| this.factory = factory; |
| this.totalMethodInstructionLimit = totalMethodInstructionLimit; |
| } |
| |
| // Process method code and inline eligible class instantiations, in short: |
| // |
| // - collect all 'new-instance' instructions in the original code. Note that class |
| // inlining, if happens, mutates code and may add new 'new-instance' instructions. |
| // Processing them as well is possible, but does not seem to bring much value. |
| // |
| // - for each 'new-instance' we check if it is eligible for inlining, i.e: |
| // -> the class of the new instance is 'eligible' (see computeClassEligible(...)) |
| // -> the instance is initialized with 'eligible' constructor (see comments in |
| // CodeRewriter::identifyClassInlinerEligibility(...)) |
| // -> has only 'eligible' uses, i.e: |
| // * as a receiver of a field read/write for a field defined in same class |
| // as method. |
| // * as a receiver of virtual or interface call with single target being |
| // an eligible method according to identifyClassInlinerEligibility(...); |
| // NOTE: if method receiver is used as a return value, the method call |
| // should ignore return value |
| // |
| // - inline eligible 'new-instance' instructions, i.e: |
| // -> force inline methods called on the instance (including the initializer); |
| // (this may introduce additional instance field reads/writes on the receiver) |
| // -> replace instance field reads with appropriate values calculated based on |
| // fields writes |
| // -> remove the call to superclass initializer |
| // -> remove all field writes |
| // -> remove 'new-instance' instructions |
| // |
| // For example: |
| // |
| // Original code: |
| // class C { |
| // static class L { |
| // final int x; |
| // L(int x) { |
| // this.x = x; |
| // } |
| // int getX() { |
| // return x; |
| // } |
| // } |
| // static int method1() { |
| // return new L(1).x; |
| // } |
| // static int method2() { |
| // return new L(1).getX(); |
| // } |
| // } |
| // |
| // Code after class C is 'inlined': |
| // class C { |
| // static int method1() { |
| // return 1; |
| // } |
| // static int method2() { |
| // return 1; |
| // } |
| // } |
| // |
| public final void processMethodCode( |
| AppInfoWithSubtyping appInfo, |
| DexEncodedMethod method, |
| IRCode code, |
| Predicate<DexEncodedMethod> isProcessedConcurrently, |
| InlinerAction inliner) { |
| |
| // Collect all the new-instance instructions in the code before inlining. |
| List<NewInstance> newInstances = Streams.stream(code.instructionIterator()) |
| .filter(Instruction::isNewInstance) |
| .map(Instruction::asNewInstance) |
| .collect(Collectors.toList()); |
| |
| for (NewInstance newInstance : newInstances) { |
| Value eligibleInstance = newInstance.outValue(); |
| if (eligibleInstance == null) { |
| continue; |
| } |
| |
| DexType eligibleClass = newInstance.clazz; |
| if (!isClassEligible(appInfo, eligibleClass)) { |
| continue; |
| } |
| |
| Map<InvokeMethodWithReceiver, InliningInfo> methodCalls = checkInstanceUsersEligibility( |
| appInfo, method, isProcessedConcurrently, newInstance, eligibleInstance, eligibleClass); |
| if (methodCalls == null) { |
| continue; |
| } |
| |
| if (getTotalEstimatedMethodSize(methodCalls) >= totalMethodInstructionLimit) { |
| continue; |
| } |
| |
| // Inline the class instance. |
| forceInlineAllMethodInvocations(inliner, methodCalls); |
| removeSuperClassInitializerAndFieldReads(code, newInstance, eligibleInstance); |
| removeFieldWrites(eligibleInstance, eligibleClass); |
| removeInstruction(newInstance); |
| |
| // Restore normality. |
| code.removeAllTrivialPhis(); |
| assert code.isConsistentSSA(); |
| } |
| } |
| |
| private Map<InvokeMethodWithReceiver, InliningInfo> checkInstanceUsersEligibility( |
| AppInfoWithSubtyping appInfo, DexEncodedMethod method, |
| Predicate<DexEncodedMethod> isProcessedConcurrently, |
| NewInstance newInstanceInsn, Value receiver, DexType clazz) { |
| |
| // No Phi users. |
| if (receiver.numberOfPhiUsers() > 0) { |
| return null; // Not eligible. |
| } |
| |
| Map<InvokeMethodWithReceiver, InliningInfo> methodCalls = new IdentityHashMap<>(); |
| |
| for (Instruction user : receiver.uniqueUsers()) { |
| // Field read/write. |
| if (user.isInstanceGet() || |
| (user.isInstancePut() && user.asInstancePut().value() != receiver)) { |
| if (user.asFieldInstruction().getField().clazz == newInstanceInsn.clazz) { |
| // Eligible field read or write. Note: as long as we consider only classes eligible |
| // if they directly extend java.lang.Object we don't need to check if the field |
| // really exists in the class. |
| continue; |
| } |
| return null; // Not eligible. |
| } |
| |
| // Eligible constructor call. |
| if (user.isInvokeDirect()) { |
| InliningInfo inliningInfo = isEligibleConstructorCall(appInfo, method, |
| user.asInvokeDirect(), receiver, clazz, isProcessedConcurrently); |
| if (inliningInfo != null) { |
| methodCalls.put(user.asInvokeDirect(), inliningInfo); |
| continue; |
| } |
| return null; // Not eligible. |
| } |
| |
| // Eligible virtual method call. |
| if (user.isInvokeVirtual() || user.isInvokeInterface()) { |
| InliningInfo inliningInfo = isEligibleMethodCall( |
| appInfo, method, user.asInvokeMethodWithReceiver(), |
| receiver, clazz, isProcessedConcurrently); |
| if (inliningInfo != null) { |
| methodCalls.put(user.asInvokeMethodWithReceiver(), inliningInfo); |
| continue; |
| } |
| return null; // Not eligible. |
| } |
| |
| return null; // Not eligible. |
| } |
| return methodCalls; |
| } |
| |
| // Remove call to superclass initializer, replace field reads with appropriate |
| // values, insert phis when needed. |
| private void removeSuperClassInitializerAndFieldReads( |
| IRCode code, NewInstance newInstance, Value eligibleInstance) { |
| Map<DexField, FieldValueHelper> fieldHelpers = new IdentityHashMap<>(); |
| for (Instruction user : eligibleInstance.uniqueUsers()) { |
| // Remove the call to superclass constructor. |
| if (user.isInvokeDirect() && |
| user.asInvokeDirect().getInvokedMethod() == factory.objectMethods.constructor) { |
| removeInstruction(user); |
| continue; |
| } |
| |
| if (user.isInstanceGet()) { |
| // Replace a field read with appropriate value. |
| replaceFieldRead(code, newInstance, user.asInstanceGet(), fieldHelpers); |
| continue; |
| } |
| |
| if (user.isInstancePut()) { |
| // Skip in this iteration since these instructions are needed to |
| // properly calculate what value should field reads be replaced with. |
| continue; |
| } |
| |
| throw new Unreachable("Unexpected usage left after method inlining: " + user); |
| } |
| } |
| |
| private void removeFieldWrites(Value receiver, DexType clazz) { |
| for (Instruction user : receiver.uniqueUsers()) { |
| if (!user.isInstancePut()) { |
| throw new Unreachable("Unexpected usage left after field reads removed: " + user); |
| } |
| if (user.asInstancePut().getField().clazz != clazz) { |
| throw new Unreachable("Unexpected field write left after field reads removed: " + user); |
| } |
| removeInstruction(user); |
| } |
| } |
| |
| private int getTotalEstimatedMethodSize(Map<InvokeMethodWithReceiver, InliningInfo> methodCalls) { |
| int totalSize = 0; |
| for (InliningInfo info : methodCalls.values()) { |
| totalSize += info.target.getCode().estimatedSizeForInlining(); |
| } |
| return totalSize; |
| } |
| |
| private void replaceFieldRead(IRCode code, NewInstance newInstance, |
| InstanceGet fieldRead, Map<DexField, FieldValueHelper> fieldHelpers) { |
| |
| Value value = fieldRead.outValue(); |
| if (value != null) { |
| FieldValueHelper helper = fieldHelpers.computeIfAbsent( |
| fieldRead.getField(), field -> new FieldValueHelper(field, code, newInstance)); |
| Value newValue = helper.getValueForFieldRead(fieldRead.getBlock(), fieldRead); |
| value.replaceUsers(newValue); |
| for (FieldValueHelper fieldValueHelper : fieldHelpers.values()) { |
| fieldValueHelper.replaceValue(value, newValue); |
| } |
| assert value.numberOfAllUsers() == 0; |
| } |
| removeInstruction(fieldRead); |
| } |
| |
| // Describes and caches what values are supposed to be used instead of field reads. |
| private static final class FieldValueHelper { |
| final DexField field; |
| final IRCode code; |
| final NewInstance newInstance; |
| |
| private Value defaultValue = null; |
| private final Map<BasicBlock, Value> ins = new IdentityHashMap<>(); |
| private final Map<BasicBlock, Value> outs = new IdentityHashMap<>(); |
| |
| private FieldValueHelper(DexField field, IRCode code, NewInstance newInstance) { |
| this.field = field; |
| this.code = code; |
| this.newInstance = newInstance; |
| } |
| |
| void replaceValue(Value oldValue, Value newValue) { |
| for (Entry<BasicBlock, Value> entry : ins.entrySet()) { |
| if (entry.getValue() == oldValue) { |
| entry.setValue(newValue); |
| } |
| } |
| for (Entry<BasicBlock, Value> entry : outs.entrySet()) { |
| if (entry.getValue() == oldValue) { |
| entry.setValue(newValue); |
| } |
| } |
| } |
| |
| Value getValueForFieldRead(BasicBlock block, Instruction valueUser) { |
| assert valueUser != null; |
| Value value = getValueDefinedInTheBlock(block, valueUser); |
| return value != null ? value : getOrCreateInValue(block); |
| } |
| |
| private Value getOrCreateOutValue(BasicBlock block) { |
| Value value = outs.get(block); |
| if (value != null) { |
| return value; |
| } |
| |
| value = getValueDefinedInTheBlock(block, null); |
| if (value == null) { |
| // No value defined in the block. |
| value = getOrCreateInValue(block); |
| } |
| |
| assert value != null; |
| outs.put(block, value); |
| return value; |
| } |
| |
| private Value getOrCreateInValue(BasicBlock block) { |
| Value value = ins.get(block); |
| if (value != null) { |
| return value; |
| } |
| |
| List<BasicBlock> predecessors = block.getPredecessors(); |
| if (predecessors.size() == 1) { |
| value = getOrCreateOutValue(predecessors.get(0)); |
| ins.put(block, value); |
| } else { |
| // Create phi, add it to the block, cache in ins map for future use. |
| Phi phi = new Phi(code.valueNumberGenerator.next(), |
| block, ValueType.fromDexType(field.type), null); |
| ins.put(block, phi); |
| |
| List<Value> operands = new ArrayList<>(); |
| for (BasicBlock predecessor : block.getPredecessors()) { |
| operands.add(getOrCreateOutValue(predecessor)); |
| } |
| // Add phi, but don't remove trivial phis; since we cache the phi |
| // we just created for future use we should delay removing trivial |
| // phis until we are done with replacing fields reads. |
| phi.addOperands(operands, false); |
| value = phi; |
| } |
| |
| assert value != null; |
| return value; |
| } |
| |
| private Value getValueDefinedInTheBlock(BasicBlock block, Instruction stopAt) { |
| InstructionListIterator iterator = stopAt == null ? |
| block.listIterator(block.getInstructions().size()) : block.listIterator(stopAt); |
| |
| Instruction valueProducingInsn = null; |
| while (iterator.hasPrevious()) { |
| Instruction instruction = iterator.previous(); |
| assert instruction != null; |
| |
| if (instruction == newInstance || |
| (instruction.isInstancePut() && |
| instruction.asInstancePut().getField() == field && |
| instruction.asInstancePut().object() == newInstance.outValue())) { |
| valueProducingInsn = instruction; |
| break; |
| } |
| } |
| |
| if (valueProducingInsn == null) { |
| return null; |
| } |
| if (valueProducingInsn.isInstancePut()) { |
| return valueProducingInsn.asInstancePut().value(); |
| } |
| |
| assert newInstance == valueProducingInsn; |
| if (defaultValue == null) { |
| // If we met newInstance it means that default value is supposed to be used. |
| defaultValue = code.createValue(ValueType.fromDexType(field.type)); |
| ConstNumber defaultValueInsn = new ConstNumber(defaultValue, 0); |
| defaultValueInsn.setPosition(newInstance.getPosition()); |
| LinkedList<Instruction> instructions = block.getInstructions(); |
| instructions.add(instructions.indexOf(newInstance) + 1, defaultValueInsn); |
| defaultValueInsn.setBlock(block); |
| } |
| return defaultValue; |
| } |
| } |
| |
| private void forceInlineAllMethodInvocations( |
| InlinerAction inliner, Map<InvokeMethodWithReceiver, InliningInfo> methodCalls) { |
| if (!methodCalls.isEmpty()) { |
| inliner.inline(methodCalls); |
| } |
| } |
| |
| private void removeInstruction(Instruction instruction) { |
| instruction.inValues().forEach(v -> v.removeUser(instruction)); |
| instruction.getBlock().removeInstruction(instruction); |
| } |
| |
| private DexEncodedMethod findSingleTarget( |
| AppInfo appInfo, InvokeMethodWithReceiver invoke, DexType instanceType) { |
| |
| // We don't use computeSingleTarget(...) on invoke since it sometimes fails to |
| // find the single target, while this code may be more successful since we exactly |
| // know what is the actual type of the receiver. |
| |
| // Note that we also intentionally limit ourselves to methods directly defined in |
| // the instance's class. This may be improved later. |
| |
| DexClass clazz = appInfo.definitionFor(instanceType); |
| if (clazz != null) { |
| DexMethod callee = invoke.getInvokedMethod(); |
| for (DexEncodedMethod candidate : clazz.virtualMethods()) { |
| if (candidate.method.name == callee.name && candidate.method.proto == callee.proto) { |
| return candidate; |
| } |
| } |
| } |
| return null; |
| } |
| |
| private InliningInfo isEligibleConstructorCall( |
| AppInfoWithSubtyping appInfo, |
| DexEncodedMethod method, |
| InvokeDirect initInvoke, |
| Value receiver, |
| DexType inlinedClass, |
| Predicate<DexEncodedMethod> isProcessedConcurrently) { |
| |
| // Must be a constructor of the exact same class. |
| DexMethod init = initInvoke.getInvokedMethod(); |
| if (!factory.isConstructor(init)) { |
| return null; |
| } |
| // Must be a constructor called on the receiver. |
| if (initInvoke.inValues().lastIndexOf(receiver) != 0) { |
| return null; |
| } |
| |
| assert init.holder == inlinedClass |
| : "Inlined constructor? [invoke: " + initInvoke + |
| ", expected class: " + inlinedClass + "]"; |
| |
| DexEncodedMethod definition = appInfo.definitionFor(init); |
| if (definition == null || isProcessedConcurrently.test(definition)) { |
| return null; |
| } |
| |
| if (!definition.isInliningCandidate(method, Reason.SIMPLE, appInfo)) { |
| // We won't be able to inline it here. |
| |
| // Note that there may be some false negatives here since the method may |
| // reference private fields of its class which are supposed to be replaced |
| // with arguments after inlining. We should try and improve it later. |
| |
| // Using -allowaccessmodification mitigates this. |
| return null; |
| } |
| |
| return definition.getOptimizationInfo().getClassInlinerEligibility() != null |
| ? new InliningInfo(definition, inlinedClass) : null; |
| } |
| |
| private InliningInfo isEligibleMethodCall( |
| AppInfoWithSubtyping appInfo, |
| DexEncodedMethod method, |
| InvokeMethodWithReceiver invoke, |
| Value receiver, |
| DexType inlinedClass, |
| Predicate<DexEncodedMethod> isProcessedConcurrently) { |
| |
| if (invoke.inValues().lastIndexOf(receiver) > 0) { |
| return null; // Instance passed as an argument. |
| } |
| |
| DexEncodedMethod singleTarget = |
| findSingleTarget(appInfo, invoke, inlinedClass); |
| if (singleTarget == null || isProcessedConcurrently.test(singleTarget)) { |
| return null; |
| } |
| if (method == singleTarget) { |
| return null; // Don't inline itself. |
| } |
| |
| ClassInlinerEligibility eligibility = |
| singleTarget.getOptimizationInfo().getClassInlinerEligibility(); |
| if (eligibility == null) { |
| return null; |
| } |
| |
| // If the method returns receiver and the return value is actually |
| // used in the code the method is not eligible. |
| if (eligibility.returnsReceiver && |
| invoke.outValue() != null && invoke.outValue().numberOfAllUsers() > 0) { |
| return null; |
| } |
| |
| if (!singleTarget.isInliningCandidate(method, Reason.SIMPLE, appInfo)) { |
| // We won't be able to inline it here. |
| |
| // Note that there may be some false negatives here since the method may |
| // reference private fields of its class which are supposed to be replaced |
| // with arguments after inlining. We should try and improve it later. |
| |
| // Using -allowaccessmodification mitigates this. |
| return null; |
| } |
| |
| return new InliningInfo(singleTarget, inlinedClass); |
| } |
| |
| private boolean isClassEligible(AppInfo appInfo, DexType clazz) { |
| Boolean eligible = knownClasses.get(clazz); |
| if (eligible == null) { |
| Boolean computed = computeClassEligible(appInfo, clazz); |
| Boolean existing = knownClasses.putIfAbsent(clazz, computed); |
| assert existing == null || existing == computed; |
| eligible = existing == null ? computed : existing; |
| } |
| return eligible; |
| } |
| |
| // Class is eligible for this optimization. Eligibility implementation: |
| // - is not an abstract class or interface |
| // - directly extends java.lang.Object |
| // - does not declare finalizer |
| // - does not trigger any static initializers |
| private boolean computeClassEligible(AppInfo appInfo, DexType clazz) { |
| DexClass definition = appInfo.definitionFor(clazz); |
| if (definition == null || definition.isLibraryClass() || |
| definition.accessFlags.isAbstract() || definition.accessFlags.isInterface()) { |
| return false; |
| } |
| |
| // Must directly extend Object. |
| if (definition.superType != factory.objectType) { |
| return false; |
| } |
| |
| // Class must not define finalizer. |
| for (DexEncodedMethod method : definition.virtualMethods()) { |
| if (method.method.name == factory.finalizeMethodName && |
| method.method.proto == factory.objectMethods.finalize.proto) { |
| return false; |
| } |
| } |
| |
| // Check for static initializers in this class or any of interfaces it implements. |
| return !appInfo.canTriggerStaticInitializer(clazz); |
| } |
| } |