| // 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.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(); |
| if (ifInstruction.isZeroTest()) { |
| Value lhs = ifInstruction.lhs().getAliasedValue(); |
| if (lhs.isArgument() && !lhs.isThis()) { |
| int argumentIndex = lhs.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 = |
| computeConstraintFromIfZeroTest( |
| argumentIndex, argumentType, 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 = |
| computeConstraintFromIfZeroTest( |
| argumentIndex, argumentType, 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); |
| } |
| } |
| break; |
| |
| 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 computeConstraintFromIfZeroTest( |
| int argumentIndex, DexType argumentType, If.Type type) { |
| switch (type) { |
| case EQ: |
| if (argumentType.isReferenceType()) { |
| return factory.createNullConstraint(argumentIndex); |
| } |
| if (argumentType.isBooleanType()) { |
| return factory.createBooleanFalseConstraint(argumentIndex); |
| } |
| return NeverSimpleInliningConstraint.getInstance(); |
| |
| case NE: |
| if (argumentType.isReferenceType()) { |
| return factory.createNotNullConstraint(argumentIndex); |
| } |
| if (argumentType.isBooleanType()) { |
| return factory.createBooleanTrueConstraint(argumentIndex); |
| } |
| return NeverSimpleInliningConstraint.getInstance(); |
| |
| default: |
| return NeverSimpleInliningConstraint.getInstance(); |
| } |
| } |
| } |