| // 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; |
| |
| import com.android.tools.r8.graph.DexString; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.Goto; |
| import com.android.tools.r8.ir.code.InstructionListIterator; |
| import com.android.tools.r8.ir.code.IntSwitch; |
| import com.android.tools.r8.ir.code.StringSwitch; |
| import com.android.tools.r8.ir.code.Switch; |
| import com.android.tools.r8.utils.BooleanUtils; |
| import it.unimi.dsi.fastutil.ints.IntArrayList; |
| import it.unimi.dsi.fastutil.ints.IntList; |
| import it.unimi.dsi.fastutil.ints.IntOpenHashSet; |
| import it.unimi.dsi.fastutil.ints.IntSet; |
| import java.util.Comparator; |
| import java.util.function.IntPredicate; |
| |
| /** Helper to remove dead switch cases from a switch instruction. */ |
| class SwitchCaseEliminator { |
| |
| private final BasicBlock block; |
| private final BasicBlock defaultTarget; |
| private final InstructionListIterator iterator; |
| private final Switch theSwitch; |
| |
| private int alwaysHitCase = -1; |
| private BasicBlock alwaysHitTarget; |
| private boolean liveFallthrough = true; |
| private boolean mayHaveIntroducedUnreachableBlocks = false; |
| private IntSet switchCasesToBeRemoved; |
| |
| SwitchCaseEliminator(Switch theSwitch, InstructionListIterator iterator) { |
| this.block = theSwitch.getBlock(); |
| this.defaultTarget = theSwitch.fallthroughBlock(); |
| this.iterator = iterator; |
| this.theSwitch = theSwitch; |
| } |
| |
| private boolean allSwitchCasesMarkedForRemoval() { |
| return switchCasesToBeRemoved != null |
| && switchCasesToBeRemoved.size() == theSwitch.numberOfKeys(); |
| } |
| |
| private boolean canBeOptimized() { |
| assert switchCasesToBeRemoved == null || !switchCasesToBeRemoved.isEmpty(); |
| return switchCasesToBeRemoved != null || hasAlwaysHitCase() || !isFallthroughLive(); |
| } |
| |
| boolean mayHaveIntroducedUnreachableBlocks() { |
| return mayHaveIntroducedUnreachableBlocks; |
| } |
| |
| public boolean isSwitchCaseLive(int index) { |
| if (hasAlwaysHitCase()) { |
| return index == alwaysHitCase; |
| } |
| if (switchCasesToBeRemoved != null) { |
| return !switchCasesToBeRemoved.contains(index); |
| } |
| assert !isFallthroughLive(); |
| return true; |
| } |
| |
| public boolean isFallthroughDead() { |
| return !isFallthroughLive(); |
| } |
| |
| public boolean isFallthroughLive() { |
| return liveFallthrough; |
| } |
| |
| public boolean hasAlwaysHitCase() { |
| return alwaysHitCase >= 0; |
| } |
| |
| void markSwitchCaseAsAlwaysHit(int i) { |
| assert alwaysHitCase < 0; |
| alwaysHitCase = i; |
| alwaysHitTarget = theSwitch.targetBlock(i); |
| liveFallthrough = false; |
| } |
| |
| void markSwitchCaseForRemoval(int i) { |
| if (switchCasesToBeRemoved == null) { |
| switchCasesToBeRemoved = new IntOpenHashSet(); |
| } |
| switchCasesToBeRemoved.add(i); |
| } |
| |
| void markSwitchFallthroughAsNeverHit() { |
| assert !hasAlwaysHitCase(); |
| liveFallthrough = false; |
| } |
| |
| boolean optimize() { |
| if (canBeOptimized()) { |
| int originalNumberOfSuccessors = block.getSuccessors().size(); |
| IntList removedSuccessorIndices = unlinkDeadSuccessors(); |
| if (hasAlwaysHitCase() || allSwitchCasesMarkedForRemoval()) { |
| // Replace switch with a simple goto. |
| replaceSwitchByGoto(); |
| } else { |
| // Replace switch by a new switch where the dead switch cases have been removed. |
| replaceSwitchByOptimizedSwitch(originalNumberOfSuccessors, removedSuccessorIndices); |
| } |
| return true; |
| } |
| return false; |
| } |
| |
| private IntList unlinkDeadSuccessors() { |
| IntPredicate successorHasBecomeDeadPredicate = computeSuccessorHasBecomeDeadPredicate(); |
| IntList successorIndicesToBeRemoved = new IntArrayList(); |
| for (int i = 0; i < block.getSuccessors().size(); i++) { |
| if (successorHasBecomeDeadPredicate.test(i)) { |
| BasicBlock successor = block.getSuccessors().get(i); |
| successor.removePredecessor(block, null); |
| successorIndicesToBeRemoved.add(i); |
| if (successor.getPredecessors().isEmpty()) { |
| mayHaveIntroducedUnreachableBlocks = true; |
| } |
| } |
| } |
| successorIndicesToBeRemoved.sort(Comparator.naturalOrder()); |
| block.removeSuccessorsByIndex(successorIndicesToBeRemoved); |
| return successorIndicesToBeRemoved; |
| } |
| |
| private IntPredicate computeSuccessorHasBecomeDeadPredicate() { |
| int[] numberOfControlFlowEdgesToBlockWithIndex = new int[block.getSuccessors().size()]; |
| for (int i = 0; i < theSwitch.numberOfKeys(); i++) { |
| if (isSwitchCaseLive(i)) { |
| int targetBlockIndex = theSwitch.getTargetBlockIndex(i); |
| numberOfControlFlowEdgesToBlockWithIndex[targetBlockIndex] += 1; |
| } |
| } |
| if (isFallthroughLive()) { |
| numberOfControlFlowEdgesToBlockWithIndex[theSwitch.getFallthroughBlockIndex()] += 1; |
| } |
| for (int i : block.getCatchHandlersWithSuccessorIndexes().getUniqueTargets()) { |
| numberOfControlFlowEdgesToBlockWithIndex[i] += 1; |
| } |
| return i -> numberOfControlFlowEdgesToBlockWithIndex[i] == 0; |
| } |
| |
| private void replaceSwitchByGoto() { |
| assert !hasAlwaysHitCase() || alwaysHitTarget != null; |
| BasicBlock target = hasAlwaysHitCase() ? alwaysHitTarget : defaultTarget; |
| iterator.replaceCurrentInstruction(new Goto(target)); |
| } |
| |
| private void replaceSwitchByOptimizedSwitch( |
| int originalNumberOfSuccessors, IntList removedSuccessorIndices) { |
| int[] targetBlockIndexOffset = new int[originalNumberOfSuccessors]; |
| for (int removedSuccessorIndex : removedSuccessorIndices) { |
| targetBlockIndexOffset[removedSuccessorIndex] = 1; |
| } |
| for (int i = 1; i < targetBlockIndexOffset.length; i++) { |
| targetBlockIndexOffset[i] += targetBlockIndexOffset[i - 1]; |
| } |
| |
| int newFallthrough = theSwitch.numberOfKeys(); |
| if (isFallthroughDead()) { |
| for (int i = theSwitch.numberOfKeys() - 1; i >= 0; i--) { |
| if (isSwitchCaseLive(i)) { |
| newFallthrough = i; |
| break; |
| } |
| } |
| } |
| |
| // Compute the number of removed switch cases. If the fallthrough is dead, we promote one of the |
| // live switch cases to being the fallthrough instead. |
| int numberOfRemovedSwitchCases = |
| switchCasesToBeRemoved != null ? switchCasesToBeRemoved.size() : 0; |
| numberOfRemovedSwitchCases += BooleanUtils.intValue(isFallthroughDead()); |
| |
| int newNumberOfKeys = theSwitch.numberOfKeys() - numberOfRemovedSwitchCases; |
| int[] newTargetBlockIndices = new int[newNumberOfKeys]; |
| for (int i = 0, j = 0; i < newFallthrough; i++) { |
| if (isSwitchCaseLive(i)) { |
| newTargetBlockIndices[j] = |
| theSwitch.getTargetBlockIndex(i) |
| - targetBlockIndexOffset[theSwitch.getTargetBlockIndex(i)]; |
| assert newTargetBlockIndices[j] < block.getSuccessors().size(); |
| j++; |
| } |
| } |
| |
| int fallthroughBlockIndex; |
| if (isFallthroughLive()) { |
| fallthroughBlockIndex = |
| theSwitch.getFallthroughBlockIndex() |
| - targetBlockIndexOffset[theSwitch.getFallthroughBlockIndex()]; |
| } else { |
| fallthroughBlockIndex = |
| theSwitch.getTargetBlockIndex(newFallthrough) |
| - targetBlockIndexOffset[theSwitch.getTargetBlockIndex(newFallthrough)]; |
| } |
| |
| Switch replacement; |
| if (theSwitch.isIntSwitch()) { |
| IntSwitch intSwitch = theSwitch.asIntSwitch(); |
| int[] newKeys = new int[newNumberOfKeys]; |
| for (int i = 0, j = 0; i < newFallthrough; i++) { |
| if (isSwitchCaseLive(i)) { |
| newKeys[j] = intSwitch.getKey(i); |
| j++; |
| } |
| } |
| replacement = |
| new IntSwitch(theSwitch.value(), newKeys, newTargetBlockIndices, fallthroughBlockIndex); |
| } else { |
| assert theSwitch.isStringSwitch(); |
| StringSwitch stringSwitch = theSwitch.asStringSwitch(); |
| DexString[] newKeys = new DexString[newNumberOfKeys]; |
| for (int i = 0, j = 0; i < newFallthrough; i++) { |
| if (isSwitchCaseLive(i)) { |
| newKeys[j] = stringSwitch.getKey(i); |
| j++; |
| } |
| } |
| replacement = |
| new StringSwitch( |
| theSwitch.value(), newKeys, newTargetBlockIndices, fallthroughBlockIndex); |
| } |
| iterator.replaceCurrentInstruction(replacement); |
| } |
| } |