| // Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| package com.android.tools.r8.ir.analysis.inlining; |
| |
| 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.RETURN; |
| import static com.android.tools.r8.ir.code.Opcodes.THROW; |
| |
| import com.android.tools.r8.graph.AppView; |
| import com.android.tools.r8.graph.DexType; |
| import com.android.tools.r8.graph.ProgramMethod; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.IRCode; |
| import com.android.tools.r8.ir.code.If; |
| import com.android.tools.r8.ir.code.Instruction; |
| import com.android.tools.r8.ir.code.InstructionIterator; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.shaking.AppInfoWithLiveness; |
| import com.android.tools.r8.utils.InternalOptions; |
| import com.google.common.collect.Sets; |
| import java.util.OptionalLong; |
| import java.util.Set; |
| |
| /** |
| * Analysis that given a method computes a constraint which is satisfied by a concrete call site |
| * only if the method becomes simple after inlining into the concrete call site. |
| * |
| * <p>Examples of simple inlining constraints are: |
| * |
| * <ul> |
| * <li>Always simple, |
| * <li>Never simple, |
| * <li>Simple if argument i is {true, false, null, not-null}, |
| * <li>Simple if argument i is true and argument j is false, or if argument i is false. |
| * </ul> |
| */ |
| public class SimpleInliningConstraintAnalysis { |
| |
| private final SimpleInliningConstraintFactory factory; |
| private final ProgramMethod method; |
| private final InternalOptions options; |
| private final int simpleInliningConstraintThreshold; |
| |
| private final Set<BasicBlock> seen = Sets.newIdentityHashSet(); |
| |
| public SimpleInliningConstraintAnalysis( |
| AppView<AppInfoWithLiveness> appView, ProgramMethod method) { |
| this.factory = appView.simpleInliningConstraintFactory(); |
| this.method = method; |
| this.options = appView.options(); |
| this.simpleInliningConstraintThreshold = appView.options().simpleInliningConstraintThreshold; |
| } |
| |
| public SimpleInliningConstraint analyzeCode(IRCode code) { |
| if (method.getReference().getArity() == 0) { |
| // The method does not have any parameters, so there is no need to analyze the method. |
| return NeverSimpleInliningConstraint.getInstance(); |
| } |
| |
| if (options.debug) { |
| // Inlining is not enabled in debug mode. |
| return NeverSimpleInliningConstraint.getInstance(); |
| } |
| |
| // Run a bounded depth-first traversal to collect the path constraints that lead to early |
| // returns. |
| InstructionIterator instructionIterator = |
| code.entryBlock().iterator(code.getNumberOfArguments()); |
| return analyzeInstructionsInBlock(code.entryBlock(), 0, instructionIterator); |
| } |
| |
| private SimpleInliningConstraint analyzeInstructionsInBlock(BasicBlock block, int depth) { |
| return analyzeInstructionsInBlock(block, depth, block.iterator()); |
| } |
| |
| private SimpleInliningConstraint analyzeInstructionsInBlock( |
| BasicBlock block, int instructionDepth, InstructionIterator instructionIterator) { |
| // If we reach a block that has already been seen, give up. |
| if (!seen.add(block)) { |
| return NeverSimpleInliningConstraint.getInstance(); |
| } |
| |
| // Move the instruction iterator forward to the block's jump instruction, while incrementing the |
| // instruction depth of the depth-first traversal. |
| Instruction instruction = instructionIterator.next(); |
| while (!instruction.isJumpInstruction()) { |
| assert !instruction.isArgument(); |
| assert !instruction.isDebugInstruction(); |
| if (!instruction.isAssume()) { |
| instructionDepth += 1; |
| } |
| instruction = instructionIterator.next(); |
| } |
| |
| // If we have exceeded the threshold, then all paths from this instruction will not lead to any |
| // early exits, so return 'never'. |
| if (instructionDepth > simpleInliningConstraintThreshold) { |
| return NeverSimpleInliningConstraint.getInstance(); |
| } |
| |
| // Analyze the jump instruction. |
| // TODO(b/132600418): Extend to switch and throw instructions. |
| switch (instruction.opcode()) { |
| case IF: |
| If ifInstruction = instruction.asIf(); |
| Value singleArgumentOperand = getSingleArgumentOperand(ifInstruction); |
| if (singleArgumentOperand == null || singleArgumentOperand.isThis()) { |
| break; |
| } |
| |
| Value otherOperand = |
| ifInstruction.isZeroTest() |
| ? null |
| : ifInstruction.getOperand( |
| 1 - ifInstruction.inValues().indexOf(singleArgumentOperand)); |
| |
| int argumentIndex = |
| singleArgumentOperand.getAliasedValue().getDefinition().asArgument().getIndex(); |
| DexType argumentType = method.getDefinition().getArgumentType(argumentIndex); |
| int currentDepth = instructionDepth; |
| |
| // Compute the constraint for which paths through the true target are guaranteed to exit |
| // early. |
| SimpleInliningConstraint trueTargetConstraint = |
| computeConstraintFromIfTest( |
| argumentIndex, argumentType, otherOperand, ifInstruction.getType()) |
| // Only recurse into the true target if the constraint from the if-instruction |
| // is not 'never'. |
| .lazyMeet( |
| () -> analyzeInstructionsInBlock(ifInstruction.getTrueTarget(), currentDepth)); |
| |
| // Compute the constraint for which paths through the false target are guaranteed to |
| // exit early. |
| SimpleInliningConstraint fallthroughTargetConstraint = |
| computeConstraintFromIfTest( |
| argumentIndex, argumentType, otherOperand, ifInstruction.getType().inverted()) |
| // Only recurse into the false target if the constraint from the if-instruction |
| // is not 'never'. |
| .lazyMeet( |
| () -> |
| analyzeInstructionsInBlock(ifInstruction.fallthroughBlock(), currentDepth)); |
| |
| // Paths going through this basic block are guaranteed to exit early if the true target |
| // is guaranteed to exit early or the false target is. |
| return trueTargetConstraint.join(fallthroughTargetConstraint); |
| |
| case GOTO: |
| return analyzeInstructionsInBlock(instruction.asGoto().getTarget(), instructionDepth); |
| |
| case RETURN: |
| return AlwaysSimpleInliningConstraint.getInstance(); |
| |
| case THROW: |
| return block.hasCatchHandlers() |
| ? NeverSimpleInliningConstraint.getInstance() |
| : AlwaysSimpleInliningConstraint.getInstance(); |
| |
| default: |
| break; |
| } |
| |
| // Give up. |
| return NeverSimpleInliningConstraint.getInstance(); |
| } |
| |
| private SimpleInliningConstraint computeConstraintFromIfTest( |
| int argumentIndex, DexType argumentType, Value otherOperand, If.Type type) { |
| boolean isZeroTest = otherOperand == null; |
| switch (type) { |
| case EQ: |
| if (isZeroTest) { |
| if (argumentType.isReferenceType()) { |
| return factory.createEqualToNullConstraint(argumentIndex); |
| } |
| if (argumentType.isBooleanType()) { |
| return factory.createEqualToFalseConstraint(argumentIndex); |
| } |
| } else if (argumentType.isPrimitiveType()) { |
| OptionalLong rawValue = getRawNumberValue(otherOperand); |
| if (rawValue.isPresent()) { |
| return factory.createEqualToNumberConstraint(argumentIndex, rawValue.getAsLong()); |
| } |
| } |
| return NeverSimpleInliningConstraint.getInstance(); |
| |
| case NE: |
| if (isZeroTest) { |
| if (argumentType.isReferenceType()) { |
| return factory.createNotEqualToNullConstraint(argumentIndex); |
| } |
| if (argumentType.isBooleanType()) { |
| return factory.createEqualToTrueConstraint(argumentIndex); |
| } |
| } else if (argumentType.isPrimitiveType()) { |
| OptionalLong rawValue = getRawNumberValue(otherOperand); |
| if (rawValue.isPresent()) { |
| return factory.createNotEqualToNumberConstraint(argumentIndex, rawValue.getAsLong()); |
| } |
| } |
| return NeverSimpleInliningConstraint.getInstance(); |
| |
| default: |
| return NeverSimpleInliningConstraint.getInstance(); |
| } |
| } |
| |
| private OptionalLong getRawNumberValue(Value value) { |
| Value root = value.getAliasedValue(); |
| if (root.isDefinedByInstructionSatisfying(Instruction::isConstNumber)) { |
| return OptionalLong.of(root.getDefinition().asConstNumber().getRawValue()); |
| } |
| return OptionalLong.empty(); |
| } |
| |
| private Value getSingleArgumentOperand(If ifInstruction) { |
| Value singleArgumentOperand = null; |
| |
| Value lhs = ifInstruction.lhs(); |
| if (lhs.getAliasedValue().isArgument()) { |
| singleArgumentOperand = lhs; |
| } |
| |
| if (!ifInstruction.isZeroTest()) { |
| Value rhs = ifInstruction.rhs(); |
| if (rhs.getAliasedValue().isArgument()) { |
| if (singleArgumentOperand != null) { |
| return null; |
| } |
| singleArgumentOperand = rhs; |
| } |
| } |
| |
| return singleArgumentOperand; |
| } |
| } |