| // Copyright (c) 2016, 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; |
| |
| import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull; |
| |
| import com.android.tools.r8.errors.Unreachable; |
| import com.android.tools.r8.graph.AppView; |
| import com.android.tools.r8.graph.DexProgramClass; |
| import com.android.tools.r8.graph.DexType; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.CatchHandlers; |
| import com.android.tools.r8.ir.code.CatchHandlers.CatchHandler; |
| import com.android.tools.r8.ir.code.CheckCast; |
| import com.android.tools.r8.ir.code.IRCode; |
| import com.android.tools.r8.ir.code.InitClass; |
| import com.android.tools.r8.ir.code.Instruction; |
| import com.android.tools.r8.ir.code.InstructionListIterator; |
| import com.android.tools.r8.ir.code.Phi; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.code.ValueIsDeadAnalysis; |
| import com.android.tools.r8.ir.conversion.passes.BranchSimplifier; |
| import com.android.tools.r8.ir.conversion.passes.MoveResultRewriter; |
| import com.android.tools.r8.shaking.AppInfoWithLiveness; |
| import com.android.tools.r8.utils.Box; |
| import com.android.tools.r8.utils.IterableUtils; |
| import com.android.tools.r8.utils.Timing; |
| import com.google.common.collect.ImmutableList; |
| import java.util.ArrayDeque; |
| import java.util.Collection; |
| import java.util.Deque; |
| import java.util.Iterator; |
| import java.util.Queue; |
| |
| public class DeadCodeRemover { |
| |
| private final AppView<?> appView; |
| |
| public DeadCodeRemover(AppView<?> appView) { |
| this.appView = appView; |
| } |
| |
| public void run(IRCode code, Timing timing) { |
| timing.begin("Remove dead code"); |
| |
| new MoveResultRewriter(appView).run(code, timing); |
| |
| BranchSimplifier branchSimplifier = new BranchSimplifier(appView); |
| |
| // We may encounter unneeded catch handlers after each iteration, e.g., if a dead instruction |
| // is the only throwing instruction in a block. Removing unneeded catch handlers can lead to |
| // more dead instructions. |
| Deque<BasicBlock> worklist = new ArrayDeque<>(); |
| do { |
| AffectedValues affectedValues = new AffectedValues(); |
| ValueIsDeadAnalysis valueIsDeadAnalysis = new ValueIsDeadAnalysis(appView, code); |
| worklist.addAll(code.topologicallySortedBlocks()); |
| while (!worklist.isEmpty()) { |
| BasicBlock block = worklist.removeLast(); |
| removeDeadInstructions(worklist, code, block, affectedValues, valueIsDeadAnalysis); |
| removeDeadAndTrivialPhis(worklist, block, valueIsDeadAnalysis); |
| } |
| affectedValues.narrowingWithAssumeRemoval(appView, code); |
| } while (branchSimplifier |
| .simplifyIf(code) |
| .asControlFlowSimplificationResult() |
| .anySimplifications() |
| || removeUnneededCatchHandlers(code)); |
| |
| code.removeRedundantBlocks(); |
| assert code.isConsistentSSA(appView); |
| assert verifyNoDeadCode(code); |
| |
| timing.end(); |
| } |
| |
| public boolean verifyNoDeadCode(IRCode code) { |
| assert new MoveResultRewriter(appView).run(code, Timing.empty()).hasChanged().isFalse(); |
| assert !removeUnneededCatchHandlers(code); |
| ValueIsDeadAnalysis valueIsDeadAnalysis = new ValueIsDeadAnalysis(appView, code); |
| for (BasicBlock block : code.blocks) { |
| assert !valueIsDeadAnalysis.hasDeadPhi(block); |
| for (Instruction instruction : block.getInstructions()) { |
| // No unused move-result instructions. |
| assert !instruction.isInvoke() |
| || !instruction.hasOutValue() |
| || instruction.outValue().hasAnyUsers(); |
| // No dead instructions. |
| assert !instruction.canBeDeadCode(appView, code).isDeadIfOutValueIsDead() |
| || (instruction.hasOutValue() && !valueIsDeadAnalysis.isDead(instruction.outValue())); |
| } |
| } |
| return true; |
| } |
| |
| // Add the block from where the value originates to the worklist. |
| private static void updateWorklist(Queue<BasicBlock> worklist, Value value) { |
| BasicBlock block = null; |
| if (value.isPhi()) { |
| block = value.asPhi().getBlock(); |
| } else if (value.definition.hasBlock()) { |
| block = value.definition.getBlock(); |
| } |
| if (block != null) { |
| worklist.add(block); |
| } |
| } |
| |
| // Add all blocks from where the in/debug-values to the instruction originates. |
| private static void updateWorklist(Queue<BasicBlock> worklist, Instruction instruction) { |
| for (Value inValue : instruction.inValues()) { |
| updateWorklist(worklist, inValue); |
| } |
| for (Value debugValue : instruction.getDebugValues()) { |
| updateWorklist(worklist, debugValue); |
| } |
| } |
| |
| private void removeDeadAndTrivialPhis( |
| Queue<BasicBlock> worklist, BasicBlock block, ValueIsDeadAnalysis valueIsDeadAnalysis) { |
| Iterator<Phi> phiIt = block.getPhis().iterator(); |
| while (phiIt.hasNext()) { |
| Phi phi = phiIt.next(); |
| if (valueIsDeadAnalysis.isDead(phi)) { |
| phiIt.remove(); |
| for (Value operand : phi.getOperands()) { |
| operand.removePhiUser(phi); |
| updateWorklist(worklist, operand); |
| } |
| } else if (phi.isTrivialPhi()) { |
| phiIt.remove(); |
| phi.removeTrivialPhi(); |
| } |
| } |
| } |
| |
| @SuppressWarnings("ReferenceEquality") |
| private void removeDeadInstructions( |
| Queue<BasicBlock> worklist, |
| IRCode code, |
| BasicBlock block, |
| AffectedValues affectedValues, |
| ValueIsDeadAnalysis valueIsDeadAnalysis) { |
| InstructionListIterator iterator = block.listIterator(code, block.getInstructions().size()); |
| while (iterator.hasPrevious()) { |
| Instruction current = iterator.previous(); |
| if (current.hasOutValue()) { |
| // Replace unnecessary cast values. |
| if (current.isCheckCast()) { |
| CheckCast checkCast = current.asCheckCast(); |
| if (!checkCast.isRefiningStaticType(appView.options()) |
| && checkCast.outValue().getLocalInfo() == checkCast.object().getLocalInfo()) { |
| updateWorklistWithNonDebugUses(worklist, checkCast); |
| checkCast.outValue().replaceUsers(checkCast.object(), affectedValues); |
| checkCast.object().uniquePhiUsers().forEach(Phi::removeTrivialPhi); |
| } |
| } |
| // Remove unused invoke results. |
| if (current.isInvoke() && !current.outValue().isUsed()) { |
| current.setOutValue(null); |
| } |
| if (current.isStaticGet() && !current.outValue().isUsed() && appView.hasLiveness()) { |
| Box<InitClass> initClass = new Box<>(); |
| if (iterator.removeOrReplaceCurrentInstructionByInitClassIfPossible( |
| appView.withLiveness(), |
| code, |
| current.asStaticGet().getField().getHolderType(), |
| initClass::set)) { |
| if (initClass.isSet()) { |
| // Apply dead code remover to the new init-class instruction. |
| current = iterator.previous(); |
| assert current == initClass.get(); |
| } else { |
| // Instruction removed. |
| continue; |
| } |
| } |
| } |
| } |
| DeadInstructionResult deadInstructionResult = current.canBeDeadCode(appView, code); |
| if (deadInstructionResult.isNotDead()) { |
| continue; |
| } |
| if (deadInstructionResult.isMaybeDead()) { |
| boolean satisfied = true; |
| for (Value valueRequiredToBeDead : deadInstructionResult.getValuesRequiredToBeDead()) { |
| if (!valueIsDeadAnalysis.isDead(valueRequiredToBeDead)) { |
| satisfied = false; |
| break; |
| } |
| } |
| if (!satisfied) { |
| continue; |
| } |
| } |
| Value outValue = current.outValue(); |
| if (outValue != null && !valueIsDeadAnalysis.isDead(outValue)) { |
| continue; |
| } |
| updateWorklist(worklist, current); |
| // All users will be removed for this instruction. Eagerly clear them so further inspection |
| // of this instruction during dead code elimination will terminate here. |
| if (outValue != null) { |
| outValue.clearUsers(); |
| } |
| iterator.removeOrReplaceByDebugLocalRead(); |
| } |
| } |
| |
| private static void updateWorklistWithNonDebugUses( |
| Queue<BasicBlock> worklist, CheckCast checkCast) { |
| for (Instruction user : checkCast.outValue().uniqueUsers()) { |
| worklist.add(user.getBlock()); |
| } |
| for (Phi user : checkCast.outValue().uniquePhiUsers()) { |
| worklist.add(user.getBlock()); |
| } |
| } |
| |
| private boolean removeUnneededCatchHandlers(IRCode code) { |
| boolean mayHaveIntroducedUnreachableBlocks = false; |
| for (BasicBlock block : code.blocks) { |
| if (block.hasCatchHandlers()) { |
| if (block.canThrow()) { |
| if (appView.enableWholeProgramOptimizations()) { |
| Collection<CatchHandler<BasicBlock>> deadCatchHandlers = getDeadCatchHandlers(block); |
| if (!deadCatchHandlers.isEmpty()) { |
| for (CatchHandler<BasicBlock> catchHandler : deadCatchHandlers) { |
| catchHandler.target.unlinkCatchHandlerForGuard(catchHandler.guard); |
| } |
| mayHaveIntroducedUnreachableBlocks = true; |
| } |
| } |
| } else { |
| CatchHandlers<BasicBlock> handlers = block.getCatchHandlers(); |
| for (BasicBlock target : handlers.getUniqueTargets()) { |
| target.unlinkCatchHandler(); |
| mayHaveIntroducedUnreachableBlocks = true; |
| } |
| } |
| } |
| } |
| if (mayHaveIntroducedUnreachableBlocks) { |
| AffectedValues affectedValues = code.removeUnreachableBlocks(); |
| affectedValues.narrowingWithAssumeRemoval(appView, code); |
| } |
| assert code.isConsistentGraph(appView); |
| return mayHaveIntroducedUnreachableBlocks; |
| } |
| |
| /** |
| * Returns the catch handlers of the given block that are dead, if any. |
| */ |
| private Collection<CatchHandler<BasicBlock>> getDeadCatchHandlers(BasicBlock block) { |
| AppInfoWithLiveness appInfoWithLiveness = appView.appInfo().withLiveness(); |
| ImmutableList.Builder<CatchHandler<BasicBlock>> builder = ImmutableList.builder(); |
| CatchHandlers<BasicBlock> catchHandlers = block.getCatchHandlers(); |
| for (int i = 0; i < catchHandlers.size(); ++i) { |
| DexType guard = catchHandlers.getGuards().get(i); |
| BasicBlock target = catchHandlers.getAllTargets().get(i); |
| |
| // We can exploit subtyping information to eliminate a catch handler if the guard is |
| // subsumed by a previous guard. |
| boolean isSubsumedByPreviousGuard = false; |
| for (int j = 0; j < i; ++j) { |
| DexType previousGuard = catchHandlers.getGuards().get(j); |
| if (appView.isSubtype(guard, previousGuard).isTrue()) { |
| isSubsumedByPreviousGuard = true; |
| break; |
| } |
| } |
| if (isSubsumedByPreviousGuard) { |
| builder.add(new CatchHandler<>(guard, target)); |
| continue; |
| } |
| |
| // We can exploit that a catch handler must be dead if its guard is never instantiated |
| // directly or indirectly. |
| if (appInfoWithLiveness != null) { |
| DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(guard)); |
| if (clazz != null && !appInfoWithLiveness.isInstantiatedDirectlyOrIndirectly(clazz)) { |
| builder.add(new CatchHandler<>(guard, target)); |
| continue; |
| } |
| } |
| } |
| return builder.build(); |
| } |
| |
| public abstract static class DeadInstructionResult { |
| |
| private static final DeadInstructionResult DEFINITELY_DEAD_INSTANCE = |
| new DeadInstructionResult() { |
| @Override |
| public boolean isDeadIfOutValueIsDead() { |
| return true; |
| } |
| }; |
| |
| private static final DeadInstructionResult DEFINITELY_NOT_DEAD_INSTANCE = |
| new DeadInstructionResult() { |
| @Override |
| public boolean isNotDead() { |
| return true; |
| } |
| }; |
| |
| public static DeadInstructionResult deadIfOutValueIsDead() { |
| return DEFINITELY_DEAD_INSTANCE; |
| } |
| |
| public static DeadInstructionResult notDead() { |
| return DEFINITELY_NOT_DEAD_INSTANCE; |
| } |
| |
| public static DeadInstructionResult deadIfInValueIsDead(Value inValueRequiredToBeDead) { |
| return new DeadInstructionResult() { |
| @Override |
| public boolean isMaybeDead() { |
| return true; |
| } |
| |
| @Override |
| public Iterable<Value> getValuesRequiredToBeDead() { |
| return IterableUtils.singleton(inValueRequiredToBeDead); |
| } |
| }; |
| } |
| |
| public boolean isDeadIfOutValueIsDead() { |
| return false; |
| } |
| |
| public boolean isNotDead() { |
| return false; |
| } |
| |
| public boolean isMaybeDead() { |
| return false; |
| } |
| |
| public Iterable<Value> getValuesRequiredToBeDead() { |
| throw new Unreachable(); |
| } |
| } |
| } |