| /* |
| * Copyright (C) 2007 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.dx.ssa; |
| |
| import com.android.dx.rop.code.RegisterSpec; |
| import com.android.dx.rop.code.RegisterSpecList; |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.HashSet; |
| |
| /** |
| * A variation on Appel Algorithm 19.12 "Dead code elimination in SSA form". |
| * |
| * TODO this algorithm is more efficient if run in reverse from exit |
| * block to entry block. |
| */ |
| public class DeadCodeRemover { |
| /** method we're processing */ |
| private final SsaMethod ssaMeth; |
| |
| /** ssaMeth.getRegCount() */ |
| private final int regCount; |
| |
| /** |
| * indexed by register: whether reg should be examined |
| * (does it correspond to a no-side-effect insn?) |
| */ |
| private final BitSet worklist; |
| |
| /** use list indexed by register; modified during operation */ |
| private final ArrayList<SsaInsn>[] useList; |
| |
| /** |
| * Process a method with the dead-code remver |
| * |
| * @param ssaMethod method to process |
| */ |
| public static void process(SsaMethod ssaMethod) { |
| DeadCodeRemover dc = new DeadCodeRemover(ssaMethod); |
| dc.run(); |
| } |
| |
| /** |
| * Constructs an instance. |
| * |
| * @param ssaMethod method to process |
| */ |
| private DeadCodeRemover(SsaMethod ssaMethod) { |
| this.ssaMeth = ssaMethod; |
| |
| regCount = ssaMethod.getRegCount(); |
| worklist = new BitSet(regCount); |
| useList = ssaMeth.getUseListCopy(); |
| } |
| |
| /** |
| * Runs the dead code remover. |
| */ |
| private void run() { |
| pruneDeadInstructions(); |
| |
| HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); |
| |
| ssaMeth.forEachInsn(new NoSideEffectVisitor(worklist)); |
| |
| int regV; |
| |
| while ( 0 <= (regV = worklist.nextSetBit(0)) ) { |
| worklist.clear(regV); |
| |
| if (useList[regV].size() == 0 |
| || isCircularNoSideEffect(regV, null)) { |
| |
| SsaInsn insnS = ssaMeth.getDefinitionForRegister(regV); |
| |
| // This insn has already been deleted. |
| if (deletedInsns.contains(insnS)) { |
| continue; |
| } |
| |
| RegisterSpecList sources = insnS.getSources(); |
| |
| int sz = sources.size(); |
| for (int i = 0; i < sz; i++) { |
| // Delete this insn from all usage lists. |
| RegisterSpec source = sources.get(i); |
| useList[source.getReg()].remove(insnS); |
| |
| if (!hasSideEffect( |
| ssaMeth.getDefinitionForRegister( |
| source.getReg()))) { |
| /* |
| * Only registers whose definition has no side effect |
| * should be added back to the worklist. |
| */ |
| worklist.set(source.getReg()); |
| } |
| } |
| |
| // Schedule this insn for later deletion. |
| deletedInsns.add(insnS); |
| } |
| } |
| |
| ssaMeth.deleteInsns(deletedInsns); |
| } |
| |
| /** |
| * Removes all instructions from every unreachable block. |
| */ |
| private void pruneDeadInstructions() { |
| HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); |
| |
| ssaMeth.computeReachability(); |
| |
| for (SsaBasicBlock block : ssaMeth.getBlocks()) { |
| if (block.isReachable()) continue; |
| |
| // Prune instructions from unreachable blocks |
| for (int i = 0; i < block.getInsns().size(); i++) { |
| SsaInsn insn = block.getInsns().get(i); |
| RegisterSpecList sources = insn.getSources(); |
| int sourcesSize = sources.size(); |
| |
| // Delete this instruction completely if it has sources |
| if (sourcesSize != 0) { |
| deletedInsns.add(insn); |
| } |
| |
| // Delete this instruction from all usage lists. |
| for (int j = 0; j < sourcesSize; j++) { |
| RegisterSpec source = sources.get(j); |
| useList[source.getReg()].remove(insn); |
| } |
| |
| // Remove this instruction result from the sources of any phis |
| RegisterSpec result = insn.getResult(); |
| if (result == null) continue; |
| for (SsaInsn use : useList[result.getReg()]) { |
| if (use instanceof PhiInsn) { |
| PhiInsn phiUse = (PhiInsn) use; |
| phiUse.removePhiRegister(result); |
| } |
| } |
| } |
| } |
| |
| ssaMeth.deleteInsns(deletedInsns); |
| } |
| |
| /** |
| * Returns true if the only uses of this register form a circle of |
| * operations with no side effects. |
| * |
| * @param regV register to examine |
| * @param set a set of registers that we've already determined |
| * are only used as sources in operations with no side effect or null |
| * if this is the first recursion |
| * @return true if usage is circular without side effect |
| */ |
| private boolean isCircularNoSideEffect(int regV, BitSet set) { |
| if ((set != null) && set.get(regV)) { |
| return true; |
| } |
| |
| for (SsaInsn use : useList[regV]) { |
| if (hasSideEffect(use)) { |
| return false; |
| } |
| } |
| |
| if (set == null) { |
| set = new BitSet(regCount); |
| } |
| |
| // This register is only used in operations that have no side effect. |
| set.set(regV); |
| |
| for (SsaInsn use : useList[regV]) { |
| RegisterSpec result = use.getResult(); |
| |
| if (result == null |
| || !isCircularNoSideEffect(result.getReg(), set)) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| /** |
| * Returns true if this insn has a side-effect. Returns true |
| * if the insn is null for reasons stated in the code block. |
| * |
| * @param insn {@code null-ok;} instruction in question |
| * @return true if it has a side-effect |
| */ |
| private static boolean hasSideEffect(SsaInsn insn) { |
| if (insn == null) { |
| /* While false would seem to make more sense here, true |
| * prevents us from adding this back to a worklist unnecessarally. |
| */ |
| return true; |
| } |
| |
| return insn.hasSideEffect(); |
| } |
| |
| /** |
| * A callback class used to build up the initial worklist of |
| * registers defined by an instruction with no side effect. |
| */ |
| static private class NoSideEffectVisitor implements SsaInsn.Visitor { |
| BitSet noSideEffectRegs; |
| |
| /** |
| * Passes in data structures that will be filled out after |
| * ssaMeth.forEachInsn() is called with this instance. |
| * |
| * @param noSideEffectRegs to-build bitset of regs that are |
| * results of regs with no side effects |
| */ |
| public NoSideEffectVisitor(BitSet noSideEffectRegs) { |
| this.noSideEffectRegs = noSideEffectRegs; |
| } |
| |
| /** {@inheritDoc} */ |
| public void visitMoveInsn (NormalSsaInsn insn) { |
| // If we're tracking local vars, some moves have side effects. |
| if (!hasSideEffect(insn)) { |
| noSideEffectRegs.set(insn.getResult().getReg()); |
| } |
| } |
| |
| /** {@inheritDoc} */ |
| public void visitPhiInsn (PhiInsn phi) { |
| // If we're tracking local vars, then some phis have side effects. |
| if (!hasSideEffect(phi)) { |
| noSideEffectRegs.set(phi.getResult().getReg()); |
| } |
| } |
| |
| /** {@inheritDoc} */ |
| public void visitNonMoveInsn (NormalSsaInsn insn) { |
| RegisterSpec result = insn.getResult(); |
| if (!hasSideEffect(insn) && result != null) { |
| noSideEffectRegs.set(result.getReg()); |
| } |
| } |
| } |
| } |