/*
* 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.RegOps;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Rop;
import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.Rops;
import com.android.dx.rop.code.SourcePosition;
import com.android.dx.rop.code.Insn;
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 SsaMethod ssaMeth;
/** ssaMeth.getRegCount() */
private int regCount;
/**
* indexed by register: whether reg should be examined
* (does it correspond to a no-side-effect insn?)
*/
private BitSet worklist;
/** use list indexed by register; modified during operation */
private ArrayList<SsaInsn>[] useList;
/**
* Process a method with the dead-code remver
* @param ssaMethod method to process
*/
public static void process(SsaMethod ssaMethod) {
DeadCodeRemover dc;
dc = new DeadCodeRemover(ssaMethod);
dc.run();
}
private DeadCodeRemover(SsaMethod ssaMethod) {
this.ssaMeth = ssaMethod;
regCount = ssaMethod.getRegCount();
worklist = new BitSet(regCount);
useList = ssaMeth.getUseListCopy();
}
/**
* Run the dead code remover
*/
private void run() {
HashSet<SsaInsn> deletedInsns = (HashSet<SsaInsn>) new HashSet();
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 who's 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);
}
/**
* 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 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 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
*/
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());
}
}
}
}
|
