SCCP propagates more constants and prunes unexecuted paths from branches.
The SCCP pass now more aggressively propagates constant values through
the code. Combined with changes to the LiteralOpUpgrader, instructions
with known constant results will be replaced with a simple const
instruction.
In addition, the SCCP pass can now find branches with constant conditions
and remove the branch path that never ends up being executed. Because of
the way finally blocks end up being replicated, this tends to prune away
error handling when no exception occurs, and hard code error handling
when an exception happens.
Change-Id: I6f3330151ec387c8a1e7ce098ff6cdb8d0ce5606
diff --git a/dx/src/com/android/dx/rop/code/LocalVariableInfo.java b/dx/src/com/android/dx/rop/code/LocalVariableInfo.java
index 99a10ee..5d2b995 100644
--- a/dx/src/com/android/dx/rop/code/LocalVariableInfo.java
+++ b/dx/src/com/android/dx/rop/code/LocalVariableInfo.java
@@ -115,7 +115,11 @@
}
RegisterSpecSet newStart = start.mutableCopy();
- newStart.intersect(specs, true);
+ if (start.size() != 0) {
+ newStart.intersect(specs, true);
+ } else {
+ newStart = specs.mutableCopy();
+ }
if (start.equals(newStart)) {
return false;
diff --git a/dx/src/com/android/dx/ssa/ConstCollector.java b/dx/src/com/android/dx/ssa/ConstCollector.java
index bc8d137..cf6c019 100644
--- a/dx/src/com/android/dx/ssa/ConstCollector.java
+++ b/dx/src/com/android/dx/ssa/ConstCollector.java
@@ -172,7 +172,7 @@
for (int i = 0; i < regSz; i++) {
SsaInsn insn = ssaMeth.getDefinitionForRegister(i);
- if (insn == null) continue;
+ if (insn == null || insn.getOpcode() == null) continue;
RegisterSpec result = insn.getResult();
TypeBearer typeBearer = result.getTypeBearer();
diff --git a/dx/src/com/android/dx/ssa/DeadCodeRemover.java b/dx/src/com/android/dx/ssa/DeadCodeRemover.java
index 2a29050..07fb553 100644
--- a/dx/src/com/android/dx/ssa/DeadCodeRemover.java
+++ b/dx/src/com/android/dx/ssa/DeadCodeRemover.java
@@ -78,7 +78,9 @@
* Runs the dead code remover.
*/
private void run() {
- HashSet<SsaInsn> deletedInsns = (HashSet<SsaInsn>) new HashSet();
+ pruneDeadInstructions();
+
+ HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();
ssaMeth.forEachInsn(new NoSideEffectVisitor(worklist));
@@ -125,6 +127,49 @@
}
/**
+ * 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.
*
diff --git a/dx/src/com/android/dx/ssa/LiteralOpUpgrader.java b/dx/src/com/android/dx/ssa/LiteralOpUpgrader.java
index 01d818d..bac1d2c 100644
--- a/dx/src/com/android/dx/ssa/LiteralOpUpgrader.java
+++ b/dx/src/com/android/dx/ssa/LiteralOpUpgrader.java
@@ -16,6 +16,7 @@
package com.android.dx.ssa;
+import com.android.dx.rop.code.PlainCstInsn;
import com.android.dx.rop.code.TranslationAdvice;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Insn;
@@ -24,7 +25,9 @@
import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.Rops;
import com.android.dx.rop.code.RegOps;
+import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.CstLiteralBits;
+import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeBearer;
import java.util.List;
@@ -93,6 +96,18 @@
Rop opcode = originalRopInsn.getOpcode();
RegisterSpecList sources = insn.getSources();
+ // Replace insns with constant results with const insns
+ if (insn.getResult() != null &&
+ opcode.getOpcode() != RegOps.CONST) {
+ TypeBearer type = insn.getResult().getTypeBearer();
+ if (type.isConstant() &&
+ type.getBasicType() == Type.BT_INT) {
+ replacePlainInsn(insn, RegisterSpecList.EMPTY,
+ RegOps.CONST, (Constant) type);
+ return;
+ }
+ }
+
if (sources.size() != 2 ) {
// We're only dealing with two-source insns here.
return;
@@ -104,10 +119,10 @@
*/
if (isConstIntZeroOrKnownNull(sources.get(0))) {
replacePlainInsn(insn, sources.withoutFirst(),
- RegOps.flippedIfOpcode(opcode.getOpcode()));
+ RegOps.flippedIfOpcode(opcode.getOpcode()), null);
} else if (isConstIntZeroOrKnownNull(sources.get(1))) {
replacePlainInsn(insn, sources.withoutLast(),
- opcode.getOpcode());
+ opcode.getOpcode(), null);
}
} else if (advice.hasConstantOperation(
opcode, sources.get(0), sources.get(1))) {
@@ -131,25 +146,29 @@
/**
* Replaces an SsaInsn containing a PlainInsn with a new PlainInsn. The
- * new PlainInsn is contructed with a new RegOp and new sources.
+ * new PlainInsn is constructed with a new RegOp and new sources.
*
* TODO move this somewhere else.
*
* @param insn {@code non-null;} an SsaInsn containing a PlainInsn
* @param newSources {@code non-null;} new sources list for new insn
* @param newOpcode A RegOp from {@link RegOps}
+ * @param cst {@code null-ok;} constant for new instruction, if any
*/
private void replacePlainInsn(NormalSsaInsn insn,
- RegisterSpecList newSources, int newOpcode) {
+ RegisterSpecList newSources, int newOpcode, Constant cst) {
Insn originalRopInsn = insn.getOriginalRopInsn();
- Rop newRop = Rops.ropFor(newOpcode,
- insn.getResult(), newSources, null);
- Insn newRopInsn = new PlainInsn(newRop,
- originalRopInsn.getPosition(), insn.getResult(),
- newSources);
- NormalSsaInsn newInsn
- = new NormalSsaInsn(newRopInsn, insn.getBlock());
+ Rop newRop = Rops.ropFor(newOpcode, insn.getResult(), newSources, cst);
+ Insn newRopInsn;
+ if (cst == null) {
+ newRopInsn = new PlainInsn(newRop, originalRopInsn.getPosition(),
+ insn.getResult(), newSources);
+ } else {
+ newRopInsn = new PlainCstInsn(newRop, originalRopInsn.getPosition(),
+ insn.getResult(), newSources, cst);
+ }
+ NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock());
List<SsaInsn> insns = insn.getBlock().getInsns();
diff --git a/dx/src/com/android/dx/ssa/Optimizer.java b/dx/src/com/android/dx/ssa/Optimizer.java
index 06ed138..42ae166 100644
--- a/dx/src/com/android/dx/ssa/Optimizer.java
+++ b/dx/src/com/android/dx/ssa/Optimizer.java
@@ -158,6 +158,8 @@
if (steps.contains(OptionalStep.SCCP)) {
SCCP.process(ssaMeth);
+ DeadCodeRemover.process(ssaMeth);
+ needsDeadCodeRemover = false;
}
if (steps.contains(OptionalStep.LITERAL_UPGRADE)) {
diff --git a/dx/src/com/android/dx/ssa/PhiInsn.java b/dx/src/com/android/dx/ssa/PhiInsn.java
index 3ea876f..bc9c4b0 100644
--- a/dx/src/com/android/dx/ssa/PhiInsn.java
+++ b/dx/src/com/android/dx/ssa/PhiInsn.java
@@ -73,6 +73,7 @@
}
/** {@inheritDoc} */
+ @Override
public PhiInsn clone() {
throw new UnsupportedOperationException("can't clone phi");
}
@@ -134,6 +135,25 @@
}
/**
+ * Removes all operand uses of a register from this phi instruction.
+ *
+ * @param registerSpec register spec, including type and reg of operand
+ */
+ public void removePhiRegister(RegisterSpec registerSpec) {
+ ArrayList<Operand> operandsToRemove = new ArrayList<Operand>();
+ for (Operand o : operands) {
+ if (o.regSpec.getReg() == registerSpec.getReg()) {
+ operandsToRemove.add(o);
+ }
+ }
+
+ operands.removeAll(operandsToRemove);
+
+ // Un-cache sources, in case someone has already called getSources().
+ sources = null;
+ }
+
+ /**
* Gets the index of the pred block associated with the RegisterSpec
* at the particular getSources() index.
*
@@ -180,6 +200,7 @@
*
* @return {@code non-null;} sources list
*/
+ @Override
public RegisterSpecList getSources() {
if (sources != null) {
return sources;
diff --git a/dx/src/com/android/dx/ssa/SCCP.java b/dx/src/com/android/dx/ssa/SCCP.java
index f8bf74f..d158030 100644
--- a/dx/src/com/android/dx/ssa/SCCP.java
+++ b/dx/src/com/android/dx/ssa/SCCP.java
@@ -18,10 +18,12 @@
import com.android.dx.rop.code.CstInsn;
import com.android.dx.rop.code.Insn;
+import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.RegOps;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Rop;
import com.android.dx.rop.code.RegisterSpec;
+import com.android.dx.rop.code.Rops;
import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.CstInteger;
import com.android.dx.rop.cst.TypedConstant;
@@ -50,6 +52,8 @@
private Constant[] latticeConstants;
/** Worklist of basic blocks to be processed */
private ArrayList<SsaBasicBlock> cfgWorklist;
+ /** Worklist of executed basic blocks with phis to be processed */
+ private ArrayList<SsaBasicBlock> cfgPhiWorklist;
/** Bitset containing bits for each block that has been found executable */
private BitSet executableBlocks;
/** Worklist for SSA edges. This is a list of registers to process */
@@ -60,6 +64,8 @@
* possible.
*/
private ArrayList<SsaInsn> varyingWorklist;
+ /** Worklist of potential branches to convert to gotos */
+ private ArrayList<SsaInsn> branchWorklist;
private SCCP(SsaMethod ssaMeth) {
this.ssaMeth = ssaMeth;
@@ -67,9 +73,11 @@
this.latticeValues = new int[this.regCount];
this.latticeConstants = new Constant[this.regCount];
this.cfgWorklist = new ArrayList<SsaBasicBlock>();
+ this.cfgPhiWorklist = new ArrayList<SsaBasicBlock>();
this.executableBlocks = new BitSet(ssaMeth.getBlocks().size());
this.ssaWorklist = new ArrayList<SsaInsn>();
this.varyingWorklist = new ArrayList<SsaInsn>();
+ this.branchWorklist = new ArrayList<SsaInsn>();
for (int i = 0; i < this.regCount; i++) {
latticeValues[i] = TOP;
latticeConstants[i] = null;
@@ -85,13 +93,16 @@
}
/**
- * Add a new SSA basic block to the CFG worklist
+ * Adds a SSA basic block to the CFG worklist if it's unexecuted, or
+ * to the CFG phi worklist if it's already executed.
* @param ssaBlock Block to add
*/
private void addBlockToWorklist(SsaBasicBlock ssaBlock) {
if (!executableBlocks.get(ssaBlock.getIndex())) {
cfgWorklist.add(ssaBlock);
executableBlocks.set(ssaBlock.getIndex());
+ } else {
+ cfgPhiWorklist.add(ssaBlock);
}
}
@@ -139,7 +150,7 @@
/**
* Simulates a PHI node and set the lattice for the result
- * to the approriate value.
+ * to the appropriate value.
* Meet values:
* TOP x anything = anything
* VARYING x anything = VARYING
@@ -200,6 +211,21 @@
}
}
}
+
+ /**
+ * Simulate the phis in a block and note the results in the lattice.
+ * @param block Block to visit
+ */
+ private void simulatePhiBlock(SsaBasicBlock block) {
+ for (SsaInsn insn : block.getInsns()) {
+ if (insn instanceof PhiInsn) {
+ simulatePhi((PhiInsn) insn);
+ } else {
+ return;
+ }
+ }
+ }
+
private static String latticeValName(int latticeVal) {
switch (latticeVal) {
case TOP: return "TOP";
@@ -210,12 +236,122 @@
}
/**
- * Simplifies a jump statement.
- * @param insn jump to simplify
- * @return an instruction representing the simplified jump.
+ * Simulates branch insns, if possible. Adds reachable successor blocks
+ * to the CFG worklists.
+ * @param insn branch to simulate
*/
- private Insn simplifyJump (Insn insn) {
- return insn;
+ private void simulateBranch(SsaInsn insn) {
+ Rop opcode = insn.getOpcode();
+ RegisterSpecList sources = insn.getSources();
+
+ boolean constantBranch = false;
+ boolean constantSuccessor = false;
+
+ // Check if the insn is a branch with a constant condition
+ if (opcode.getBranchingness() == Rop.BRANCH_IF) {
+ Constant cA = null;
+ Constant cB = null;
+
+ int regA = sources.get(0).getReg();
+ if (latticeValues[regA] == CONSTANT) {
+ cA = latticeConstants[regA];
+ }
+
+ if (sources.size() == 2) {
+ int regB = sources.get(1).getReg();
+ if (latticeValues[regB] == CONSTANT) {
+ cB = latticeConstants[regB];
+ }
+ }
+
+ // Calculate the result of the condition
+ if (cA != null && sources.size() == 1) {
+ switch (((TypedConstant) cA).getBasicType()) {
+ case Type.BT_INT:
+ constantBranch = true;
+ int vA = ((CstInteger) cA).getValue();
+ switch (opcode.getOpcode()) {
+ case RegOps.IF_EQ:
+ constantSuccessor = (vA == 0);
+ break;
+ case RegOps.IF_NE:
+ constantSuccessor = (vA != 0);
+ break;
+ case RegOps.IF_LT:
+ constantSuccessor = (vA < 0);
+ break;
+ case RegOps.IF_GE:
+ constantSuccessor = (vA >= 0);
+ break;
+ case RegOps.IF_LE:
+ constantSuccessor = (vA <= 0);
+ break;
+ case RegOps.IF_GT:
+ constantSuccessor = (vA > 0);
+ break;
+ default:
+ throw new RuntimeException("Unexpected op");
+ }
+ break;
+ default:
+ // not yet supported
+ }
+ } else if (cA != null && cB != null) {
+ switch (((TypedConstant) cA).getBasicType()) {
+ case Type.BT_INT:
+ constantBranch = true;
+ int vA = ((CstInteger) cA).getValue();
+ int vB = ((CstInteger) cB).getValue();
+ switch (opcode.getOpcode()) {
+ case RegOps.IF_EQ:
+ constantSuccessor = (vA == vB);
+ break;
+ case RegOps.IF_NE:
+ constantSuccessor = (vA != vB);
+ break;
+ case RegOps.IF_LT:
+ constantSuccessor = (vA < vB);
+ break;
+ case RegOps.IF_GE:
+ constantSuccessor = (vA >= vB);
+ break;
+ case RegOps.IF_LE:
+ constantSuccessor = (vA <= vB);
+ break;
+ case RegOps.IF_GT:
+ constantSuccessor = (vA > vB);
+ break;
+ default:
+ throw new RuntimeException("Unexpected op");
+ }
+ break;
+ default:
+ // not yet supported
+ }
+ }
+ }
+
+ /*
+ * If condition is constant, add only the target block to the
+ * worklist. Otherwise, add all successors to the worklist.
+ */
+ SsaBasicBlock block = insn.getBlock();
+
+ if (constantBranch) {
+ int successorBlock;
+ if (constantSuccessor) {
+ successorBlock = block.getSuccessorList().get(1);
+ } else {
+ successorBlock = block.getSuccessorList().get(0);
+ }
+ addBlockToWorklist(ssaMeth.getBlocks().get(successorBlock));
+ branchWorklist.add(insn);
+ } else {
+ for (int i = 0; i < block.getSuccessorList().size(); i++) {
+ int successorBlock = block.getSuccessorList().get(i);
+ addBlockToWorklist(ssaMeth.getBlocks().get(successorBlock));
+ }
+ }
}
/**
@@ -327,14 +463,7 @@
Insn ropInsn = insn.getOriginalRopInsn();
if (ropInsn.getOpcode().getBranchingness() != Rop.BRANCH_NONE
|| ropInsn.getOpcode().isCallLike()) {
- ropInsn = simplifyJump (ropInsn);
- /* TODO: If jump becomes constant, only take true edge. */
- SsaBasicBlock block = insn.getBlock();
- int successorSize = block.getSuccessorList().size();
- for (int i = 0; i < successorSize; i++) {
- int successor = block.getSuccessorList().get(i);
- addBlockToWorklist(ssaMeth.getBlocks().get(successor));
- }
+ simulateBranch(insn);
}
if (insn.getResult() == null) {
@@ -397,6 +526,7 @@
/* Empty all the worklists by propagating our values */
while (!cfgWorklist.isEmpty()
+ || !cfgPhiWorklist.isEmpty()
|| !ssaWorklist.isEmpty()
|| !varyingWorklist.isEmpty()) {
while (!cfgWorklist.isEmpty()) {
@@ -404,6 +534,13 @@
SsaBasicBlock block = cfgWorklist.remove(listSize);
simulateBlock(block);
}
+
+ while (!cfgPhiWorklist.isEmpty()) {
+ int listSize = cfgPhiWorklist.size() - 1;
+ SsaBasicBlock block = cfgPhiWorklist.remove(listSize);
+ simulatePhiBlock(block);
+ }
+
while (!varyingWorklist.isEmpty()) {
int listSize = varyingWorklist.size() - 1;
SsaInsn insn = varyingWorklist.remove(listSize);
@@ -435,6 +572,7 @@
}
replaceConstants();
+ replaceBranches();
}
/**
@@ -463,6 +601,12 @@
continue;
}
+ // Update the destination RegisterSpec with the constant value
+ RegisterSpec dest = defn.getResult();
+ RegisterSpec newDest
+ = dest.withType((TypedConstant)latticeConstants[reg]);
+ defn.setResult(newDest);
+
/*
* Update the sources RegisterSpec's of all non-move uses.
* These will be used in later steps.
@@ -485,4 +629,34 @@
}
}
}
+
+ /**
+ * Replaces branches that have constant conditions with gotos
+ */
+ private void replaceBranches() {
+ for (SsaInsn insn : branchWorklist) {
+ // Find if a successor block is never executed
+ int oldSuccessor = -1;
+ SsaBasicBlock block = insn.getBlock();
+ int successorSize = block.getSuccessorList().size();
+ for (int i = 0; i < successorSize; i++) {
+ int successorBlock = block.getSuccessorList().get(i);
+ if (!executableBlocks.get(successorBlock)) {
+ oldSuccessor = successorBlock;
+ }
+ }
+
+ /*
+ * Prune branches that have already been handled and ones that no
+ * longer have constant conditions (no nonexecutable successors)
+ */
+ if (successorSize != 2 || oldSuccessor == -1) continue;
+
+ // Replace branch with goto
+ Insn originalRopInsn = insn.getOriginalRopInsn();
+ block.replaceLastInsn(new PlainInsn(Rops.GOTO,
+ originalRopInsn.getPosition(), null, RegisterSpecList.EMPTY));
+ block.removeSuccessor(oldSuccessor);
+ }
+ }
}
diff --git a/dx/src/com/android/dx/ssa/back/SsaToRop.java b/dx/src/com/android/dx/ssa/back/SsaToRop.java
index afbb285..0e30250 100644
--- a/dx/src/com/android/dx/ssa/back/SsaToRop.java
+++ b/dx/src/com/android/dx/ssa/back/SsaToRop.java
@@ -248,8 +248,8 @@
ssaMeth.computeReachability();
int ropBlockCount = ssaMeth.getCountReachableBlocks();
- // Don't count the exit block, if it exists.
- ropBlockCount -= (exitBlock == null) ? 0 : 1;
+ // Don't count the exit block, if it exists and is reachable.
+ ropBlockCount -= (exitBlock != null && exitBlock.isReachable()) ? 1 : 0;
BasicBlockList result = new BasicBlockList(ropBlockCount);
