| /* |
| * 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.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; |
| import com.android.dx.rop.type.TypeBearer; |
| import com.android.dx.rop.type.Type; |
| |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| |
| /** |
| * A small variant of Wegman and Zadeck's Sparse Conditional Constant |
| * Propagation algorithm. |
| */ |
| public class SCCP { |
| /** Lattice values */ |
| private static final int TOP = 0; |
| private static final int CONSTANT = 1; |
| private static final int VARYING = 2; |
| /** method we're processing */ |
| private SsaMethod ssaMeth; |
| /** ssaMeth.getRegCount() */ |
| private int regCount; |
| /** Lattice values for each SSA register */ |
| private int[] latticeValues; |
| /** For those registers that are constant, this is the constant value */ |
| 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 */ |
| private ArrayList<SsaInsn> ssaWorklist; |
| /** |
| * Worklist for SSA edges that represent varying values. It makes the |
| * algorithm much faster if you move all values to VARYING as fast as |
| * possible. |
| */ |
| private ArrayList<SsaInsn> varyingWorklist; |
| /** Worklist of potential branches to convert to gotos */ |
| private ArrayList<SsaInsn> branchWorklist; |
| |
| private SCCP(SsaMethod ssaMeth) { |
| this.ssaMeth = ssaMeth; |
| this.regCount = ssaMeth.getRegCount(); |
| 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; |
| } |
| } |
| |
| /** |
| * Performs sparse conditional constant propagation on a method. |
| * @param ssaMethod Method to process |
| */ |
| public static void process (SsaMethod ssaMethod) { |
| new SCCP(ssaMethod).run(); |
| } |
| |
| /** |
| * 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); |
| } |
| } |
| |
| /** |
| * Adds an SSA register's uses to the SSA worklist. |
| * @param reg SSA register |
| * @param latticeValue new lattice value for @param reg. |
| */ |
| private void addUsersToWorklist(int reg, int latticeValue) { |
| if (latticeValue == VARYING) { |
| for (SsaInsn insn : ssaMeth.getUseListForRegister(reg)) { |
| varyingWorklist.add(insn); |
| } |
| } else { |
| for (SsaInsn insn : ssaMeth.getUseListForRegister(reg)) { |
| ssaWorklist.add(insn); |
| } |
| } |
| } |
| |
| /** |
| * Sets a lattice value for a register to value. |
| * @param reg SSA register |
| * @param value Lattice value |
| * @param cst Constant value (may be null) |
| * @return true if the lattice value changed. |
| */ |
| private boolean setLatticeValueTo(int reg, int value, Constant cst) { |
| if (value != CONSTANT) { |
| if (latticeValues[reg] != value) { |
| latticeValues[reg] = value; |
| return true; |
| } |
| return false; |
| } else { |
| if (latticeValues[reg] != value |
| || !latticeConstants[reg].equals(cst)) { |
| latticeValues[reg] = value; |
| latticeConstants[reg] = cst; |
| return true; |
| } |
| return false; |
| } |
| } |
| |
| /** |
| * Simulates a PHI node and set the lattice for the result |
| * to the appropriate value. |
| * Meet values: |
| * TOP x anything = TOP |
| * VARYING x anything = VARYING |
| * CONSTANT x CONSTANT = CONSTANT if equal constants, VARYING otherwise |
| * @param insn PHI to simulate. |
| */ |
| private void simulatePhi(PhiInsn insn) { |
| int phiResultReg = insn.getResult().getReg(); |
| |
| if (latticeValues[phiResultReg] == VARYING) { |
| return; |
| } |
| |
| RegisterSpecList sources = insn.getSources(); |
| int phiResultValue = TOP; |
| Constant phiConstant = null; |
| int sourceSize = sources.size(); |
| |
| for (int i = 0; i < sourceSize; i++) { |
| int predBlockIndex = insn.predBlockIndexForSourcesIndex(i); |
| int sourceReg = sources.get(i).getReg(); |
| int sourceRegValue = latticeValues[sourceReg]; |
| |
| if (!executableBlocks.get(predBlockIndex)) { |
| continue; |
| } |
| |
| if (sourceRegValue == CONSTANT) { |
| if (phiConstant == null) { |
| phiConstant = latticeConstants[sourceReg]; |
| phiResultValue = CONSTANT; |
| } else if (!latticeConstants[sourceReg].equals(phiConstant)){ |
| phiResultValue = VARYING; |
| break; |
| } |
| } else { |
| phiResultValue = sourceRegValue; |
| break; |
| } |
| } |
| if (setLatticeValueTo(phiResultReg, phiResultValue, phiConstant)) { |
| addUsersToWorklist(phiResultReg, phiResultValue); |
| } |
| } |
| |
| /** |
| * Simulate a block and note the results in the lattice. |
| * @param block Block to visit |
| */ |
| private void simulateBlock(SsaBasicBlock block) { |
| for (SsaInsn insn : block.getInsns()) { |
| if (insn instanceof PhiInsn) { |
| simulatePhi((PhiInsn) insn); |
| } else { |
| simulateStmt(insn); |
| } |
| } |
| } |
| |
| /** |
| * 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"; |
| case CONSTANT: return "CONSTANT"; |
| case VARYING: return "VARYING"; |
| default: return "UNKNOWN"; |
| } |
| } |
| |
| /** |
| * Simulates branch insns, if possible. Adds reachable successor blocks |
| * to the CFG worklists. |
| * @param insn branch to simulate |
| */ |
| 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; |
| |
| RegisterSpec specA = sources.get(0); |
| int regA = specA.getReg(); |
| if (!ssaMeth.isRegALocal(specA) && |
| latticeValues[regA] == CONSTANT) { |
| cA = latticeConstants[regA]; |
| } |
| |
| if (sources.size() == 2) { |
| RegisterSpec specB = sources.get(1); |
| int regB = specB.getReg(); |
| if (!ssaMeth.isRegALocal(specB) && |
| 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)); |
| } |
| } |
| } |
| |
| /** |
| * Simulates math insns, if possible. |
| * |
| * @param insn non-null insn to simulate |
| * @param resultType basic type of the result |
| * @return constant result or null if not simulatable. |
| */ |
| private Constant simulateMath(SsaInsn insn, int resultType) { |
| Insn ropInsn = insn.getOriginalRopInsn(); |
| int opcode = insn.getOpcode().getOpcode(); |
| RegisterSpecList sources = insn.getSources(); |
| int regA = sources.get(0).getReg(); |
| Constant cA; |
| Constant cB; |
| |
| if (latticeValues[regA] != CONSTANT) { |
| cA = null; |
| } else { |
| cA = latticeConstants[regA]; |
| } |
| |
| if (sources.size() == 1) { |
| CstInsn cstInsn = (CstInsn) ropInsn; |
| cB = cstInsn.getConstant(); |
| } else { /* sources.size() == 2 */ |
| int regB = sources.get(1).getReg(); |
| if (latticeValues[regB] != CONSTANT) { |
| cB = null; |
| } else { |
| cB = latticeConstants[regB]; |
| } |
| } |
| |
| if (cA == null || cB == null) { |
| //TODO handle a constant of 0 with MUL or AND |
| return null; |
| } |
| |
| switch (resultType) { |
| case Type.BT_INT: |
| int vR; |
| boolean skip=false; |
| |
| int vA = ((CstInteger) cA).getValue(); |
| int vB = ((CstInteger) cB).getValue(); |
| |
| switch (opcode) { |
| case RegOps.ADD: |
| vR = vA + vB; |
| break; |
| case RegOps.SUB: |
| // 1 source for reverse sub, 2 sources for regular sub |
| if (sources.size() == 1) { |
| vR = vB - vA; |
| } else { |
| vR = vA - vB; |
| } |
| break; |
| case RegOps.MUL: |
| vR = vA * vB; |
| break; |
| case RegOps.DIV: |
| if (vB == 0) { |
| skip = true; |
| vR = 0; // just to hide a warning |
| } else { |
| vR = vA / vB; |
| } |
| break; |
| case RegOps.AND: |
| vR = vA & vB; |
| break; |
| case RegOps.OR: |
| vR = vA | vB; |
| break; |
| case RegOps.XOR: |
| vR = vA ^ vB; |
| break; |
| case RegOps.SHL: |
| vR = vA << vB; |
| break; |
| case RegOps.SHR: |
| vR = vA >> vB; |
| break; |
| case RegOps.USHR: |
| vR = vA >>> vB; |
| break; |
| case RegOps.REM: |
| if (vB == 0) { |
| skip = true; |
| vR = 0; // just to hide a warning |
| } else { |
| vR = vA % vB; |
| } |
| break; |
| default: |
| throw new RuntimeException("Unexpected op"); |
| } |
| |
| return skip ? null : CstInteger.make(vR); |
| |
| default: |
| // not yet supported |
| return null; |
| } |
| } |
| |
| /** |
| * Simulates a statement and set the result lattice value. |
| * @param insn instruction to simulate |
| */ |
| private void simulateStmt(SsaInsn insn) { |
| Insn ropInsn = insn.getOriginalRopInsn(); |
| if (ropInsn.getOpcode().getBranchingness() != Rop.BRANCH_NONE |
| || ropInsn.getOpcode().isCallLike()) { |
| simulateBranch(insn); |
| } |
| |
| int opcode = insn.getOpcode().getOpcode(); |
| RegisterSpec result = insn.getResult(); |
| |
| if (result == null) { |
| // Find move-result-pseudo result for int div and int rem |
| if (opcode == RegOps.DIV || opcode == RegOps.REM) { |
| SsaBasicBlock succ = insn.getBlock().getPrimarySuccessor(); |
| result = succ.getInsns().get(0).getResult(); |
| } else { |
| return; |
| } |
| } |
| |
| int resultReg = result.getReg(); |
| int resultValue = VARYING; |
| Constant resultConstant = null; |
| |
| switch (opcode) { |
| case RegOps.CONST: { |
| CstInsn cstInsn = (CstInsn)ropInsn; |
| resultValue = CONSTANT; |
| resultConstant = cstInsn.getConstant(); |
| break; |
| } |
| case RegOps.MOVE: { |
| if (insn.getSources().size() == 1) { |
| int sourceReg = insn.getSources().get(0).getReg(); |
| resultValue = latticeValues[sourceReg]; |
| resultConstant = latticeConstants[sourceReg]; |
| } |
| break; |
| } |
| case RegOps.ADD: |
| case RegOps.SUB: |
| case RegOps.MUL: |
| case RegOps.DIV: |
| case RegOps.AND: |
| case RegOps.OR: |
| case RegOps.XOR: |
| case RegOps.SHL: |
| case RegOps.SHR: |
| case RegOps.USHR: |
| case RegOps.REM: { |
| resultConstant = simulateMath(insn, result.getBasicType()); |
| if (resultConstant != null) { |
| resultValue = CONSTANT; |
| } |
| break; |
| } |
| case RegOps.MOVE_RESULT_PSEUDO: { |
| if (latticeValues[resultReg] == CONSTANT) { |
| resultValue = latticeValues[resultReg]; |
| resultConstant = latticeConstants[resultReg]; |
| } |
| break; |
| } |
| // TODO: Handle non-int arithmetic. |
| // TODO: Eliminate check casts that we can prove the type of. |
| default: {} |
| } |
| if (setLatticeValueTo(resultReg, resultValue, resultConstant)) { |
| addUsersToWorklist(resultReg, resultValue); |
| } |
| } |
| |
| private void run() { |
| SsaBasicBlock firstBlock = ssaMeth.getEntryBlock(); |
| addBlockToWorklist(firstBlock); |
| |
| /* Empty all the worklists by propagating our values */ |
| while (!cfgWorklist.isEmpty() |
| || !cfgPhiWorklist.isEmpty() |
| || !ssaWorklist.isEmpty() |
| || !varyingWorklist.isEmpty()) { |
| while (!cfgWorklist.isEmpty()) { |
| int listSize = cfgWorklist.size() - 1; |
| 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); |
| |
| if (!executableBlocks.get(insn.getBlock().getIndex())) { |
| continue; |
| } |
| |
| if (insn instanceof PhiInsn) { |
| simulatePhi((PhiInsn)insn); |
| } else { |
| simulateStmt(insn); |
| } |
| } |
| while (!ssaWorklist.isEmpty()) { |
| int listSize = ssaWorklist.size() - 1; |
| SsaInsn insn = ssaWorklist.remove(listSize); |
| |
| if (!executableBlocks.get(insn.getBlock().getIndex())) { |
| continue; |
| } |
| |
| if (insn instanceof PhiInsn) { |
| simulatePhi((PhiInsn)insn); |
| } else { |
| simulateStmt(insn); |
| } |
| } |
| } |
| |
| replaceConstants(); |
| replaceBranches(); |
| } |
| |
| /** |
| * Replaces TypeBearers in source register specs with constant type |
| * bearers if possible. These are then referenced in later optimization |
| * steps. |
| */ |
| private void replaceConstants() { |
| for (int reg = 0; reg < regCount; reg++) { |
| if (latticeValues[reg] != CONSTANT) { |
| continue; |
| } |
| if (!(latticeConstants[reg] instanceof TypedConstant)) { |
| // We can't do much with these |
| continue; |
| } |
| |
| SsaInsn defn = ssaMeth.getDefinitionForRegister(reg); |
| TypeBearer typeBearer = defn.getResult().getTypeBearer(); |
| |
| if (typeBearer.isConstant()) { |
| /* |
| * The definition was a constant already. |
| * The uses should be as well. |
| */ |
| 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. |
| */ |
| for (SsaInsn insn : ssaMeth.getUseListForRegister(reg)) { |
| if (insn.isPhiOrMove()) { |
| continue; |
| } |
| |
| NormalSsaInsn nInsn = (NormalSsaInsn) insn; |
| RegisterSpecList sources = insn.getSources(); |
| |
| int index = sources.indexOfRegister(reg); |
| |
| RegisterSpec spec = sources.get(index); |
| RegisterSpec newSpec |
| = spec.withType((TypedConstant)latticeConstants[reg]); |
| |
| nInsn.changeOneSource(index, newSpec); |
| } |
| } |
| } |
| |
| /** |
| * 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); |
| } |
| } |
| } |