FileDocCategorySizeDatePackage
SsaConverter.javaAPI DocAndroid 5.1 API13444Thu Mar 12 22:18:30 GMT 2015com.android.dx.ssa

SsaConverter

public class SsaConverter extends Object
Converts ROP methods to SSA Methods

Fields Summary
public static final boolean
DEBUG
Constructors Summary
Methods Summary
public static SsaMethodconvertToSsaMethod(com.android.dx.rop.code.RopMethod rmeth, int paramWidth, boolean isStatic)
Returns an SSA representation, edge-split and with phi functions placed.

param
rmeth input
param
paramWidth the total width, in register-units, of the method's parameters
param
isStatic {@code true} if this method has no {@code this} pointer argument
return
output in SSA form


                                                   
        
                
        SsaMethod result
            = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

        edgeSplit(result);

        LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);

        placePhiFunctions(result, localInfo, 0);
        new SsaRenamer(result).run();

        /*
         * The exit block, added here, is not considered for edge splitting
         * or phi placement since no actual control flows to it.
         */
        result.makeExitBlock();

        return result;
    
private static voidedgeSplit(SsaMethod result)
See Appel section 19.1: Converts CFG into "edge-split" form, such that each node either a unique successor or unique predecessor.

In addition, the SSA form we use enforces a further constraint, requiring each block with a final instruction that returns a value to have a primary successor that has no other predecessor. This ensures move statements can always be inserted correctly when phi statements are removed.

param
result method to process

        edgeSplitPredecessors(result);
        edgeSplitMoveExceptionsAndResults(result);
        edgeSplitSuccessors(result);
    
private static voidedgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth)
In ROP form, move-exception must occur as the first insn in a block immediately succeeding the insn that could thrown an exception. We may need room to insert move insns later, so make sure to split any block that starts with a move-exception such that there is a unique move-exception block for each predecessor.

param
ssaMeth method to process

        ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();

        /*
         * New blocks are added to the end of the block list during
         * this iteration.
         */
        for (int i = blocks.size() - 1; i >= 0; i-- ) {
            SsaBasicBlock block = blocks.get(i);

            /*
             * Any block that starts with a move-exception and has more than
             * one predecessor...
             */
            if (!block.isExitBlock()
                    && block.getPredecessors().cardinality() > 1
                    && block.getInsns().get(0).isMoveException()) {

                // block.getPredecessors() is changed in the loop below.
                BitSet preds = (BitSet)block.getPredecessors().clone();
                for (int j = preds.nextSetBit(0); j >= 0;
                     j = preds.nextSetBit(j + 1)) {
                    SsaBasicBlock predecessor = blocks.get(j);
                    SsaBasicBlock zNode
                        = predecessor.insertNewSuccessor(block);

                    /*
                     * Make sure to place the move-exception as the
                     * first insn.
                     */
                    zNode.getInsns().add(0, block.getInsns().get(0).clone());
                }

                // Remove the move-exception from the original block.
                block.getInsns().remove(0);
            }
        }
    
private static voidedgeSplitPredecessors(SsaMethod result)
Inserts Z nodes as new predecessors for every node that has multiple successors and multiple predecessors.

param
result {@code non-null;} method to process

        ArrayList<SsaBasicBlock> blocks = result.getBlocks();

        /*
         * New blocks are added to the end of the block list during
         * this iteration.
         */
        for (int i = blocks.size() - 1; i >= 0; i-- ) {
            SsaBasicBlock block = blocks.get(i);
            if (nodeNeedsUniquePredecessor(block)) {
                block.insertNewPredecessor();
            }
        }
    
private static voidedgeSplitSuccessors(SsaMethod result)
Inserts Z nodes for every node that needs a new successor.

param
result {@code non-null;} method to process

        ArrayList<SsaBasicBlock> blocks = result.getBlocks();

        /*
         * New blocks are added to the end of the block list during
         * this iteration.
         */
        for (int i = blocks.size() - 1; i >= 0; i-- ) {
            SsaBasicBlock block = blocks.get(i);

            // Successors list is modified in loop below.
            BitSet successors = (BitSet)block.getSuccessors().clone();
            for (int j = successors.nextSetBit(0);
                 j >= 0; j = successors.nextSetBit(j+1)) {

                SsaBasicBlock succ = blocks.get(j);

                if (needsNewSuccessor(block, succ)) {
                    block.insertNewSuccessor(succ);
                }
            }
        }
    
private static booleanneedsNewSuccessor(SsaBasicBlock block, SsaBasicBlock succ)
Returns {@code true} if block and successor need a Z-node between them. Presently, this is {@code true} if the final instruction has any sources or results and the current successor block has more than one predecessor.

param
block predecessor node
param
succ successor node
return
{@code true} if a Z node is needed

        ArrayList<SsaInsn> insns = block.getInsns();
        SsaInsn lastInsn = insns.get(insns.size() - 1);

        return ((lastInsn.getResult() != null)
                    || (lastInsn.getSources().size() > 0))
                && succ.getPredecessors().cardinality() > 1;
    
private static booleannodeNeedsUniquePredecessor(SsaBasicBlock block)

param
block {@code non-null;} block in question
return
{@code true} if this node needs to have a unique predecessor created for it

        /*
         * Any block with that has both multiple successors and multiple
         * predecessors needs a new predecessor node.
         */

        int countPredecessors = block.getPredecessors().cardinality();
        int countSuccessors = block.getSuccessors().cardinality();

        return  (countPredecessors > 1 && countSuccessors > 1);
    
private static voidplacePhiFunctions(SsaMethod ssaMeth, LocalVariableInfo localInfo, int threshold)
See Appel algorithm 19.6: Place Phi functions in appropriate locations.

param
ssaMeth {@code non-null;} method to process. Modifications are made in-place.
param
localInfo {@code non-null;} local variable info, used when placing phis
param
threshold registers below this number are ignored

        ArrayList<SsaBasicBlock> ssaBlocks;
        int regCount;
        int blockCount;

        ssaBlocks = ssaMeth.getBlocks();
        blockCount = ssaBlocks.size();
        regCount = ssaMeth.getRegCount() - threshold;

        DomFront df = new DomFront(ssaMeth);
        DomFront.DomInfo[] domInfos = df.run();

        // Bit set of registers vs block index "definition sites"
        BitSet[] defsites = new BitSet[regCount];

        // Bit set of registers vs block index "phi placement sites"
        BitSet[] phisites = new BitSet[regCount];

        for (int i = 0; i < regCount; i++) {
            defsites[i] = new BitSet(blockCount);
            phisites[i] = new BitSet(blockCount);
        }

        /*
         * For each register, build a set of all basic blocks where
         * containing an assignment to that register.
         */
        for (int bi = 0, s = ssaBlocks.size(); bi < s; bi++) {
            SsaBasicBlock b = ssaBlocks.get(bi);

            for (SsaInsn insn : b.getInsns()) {
                RegisterSpec rs = insn.getResult();

                if (rs != null && rs.getReg() - threshold >= 0) {
                    defsites[rs.getReg() - threshold].set(bi);
                }
            }
        }

        if (DEBUG) {
            System.out.println("defsites");

            for (int i = 0; i < regCount; i++) {
                StringBuilder sb = new StringBuilder();
                sb.append('v").append(i).append(": ");
                sb.append(defsites[i].toString());
                System.out.println(sb);
            }
        }

        BitSet worklist;

        /*
         * For each register, compute all locations for phi placement
         * based on dominance-frontier algorithm.
         */
        for (int reg = 0, s = regCount; reg < s; reg++) {
            int workBlockIndex;

            /* Worklist set starts out with each node where reg is assigned. */

            worklist = (BitSet) (defsites[reg].clone());

            while (0 <= (workBlockIndex = worklist.nextSetBit(0))) {
                worklist.clear(workBlockIndex);
                IntIterator dfIterator
                    = domInfos[workBlockIndex].dominanceFrontiers.iterator();

                while (dfIterator.hasNext()) {
                    int dfBlockIndex = dfIterator.next();

                    if (!phisites[reg].get(dfBlockIndex)) {
                        phisites[reg].set(dfBlockIndex);

                        int tReg = reg + threshold;
                        RegisterSpec rs
                            = localInfo.getStarts(dfBlockIndex).get(tReg);

                        if (rs == null) {
                            ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(tReg);
                        } else {
                            ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(rs);
                        }

                        if (!defsites[reg].get(dfBlockIndex)) {
                            worklist.set(dfBlockIndex);
                        }
                    }
                }
            }
        }

        if (DEBUG) {
            System.out.println("phisites");

            for (int i = 0; i < regCount; i++) {
                StringBuilder sb = new StringBuilder();
                sb.append('v").append(i).append(": ");
                sb.append(phisites[i].toString());
                System.out.println(sb);
            }
        }
    
public static SsaMethodtestEdgeSplit(com.android.dx.rop.code.RopMethod rmeth, int paramWidth, boolean isStatic)
Returns an SSA represention with only the edge-splitter run.

param
rmeth method to process
param
paramWidth width of all arguments in the method
param
isStatic {@code true} if this method has no {@code this} pointer argument
return
an SSA represention with only the edge-splitter run

        SsaMethod result;

        result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

        edgeSplit(result);
        return result;
    
public static SsaMethodtestPhiPlacement(com.android.dx.rop.code.RopMethod rmeth, int paramWidth, boolean isStatic)
Returns an SSA represention with only the steps through the phi placement run.

param
rmeth method to process
param
paramWidth width of all arguments in the method
param
isStatic {@code true} if this method has no {@code this} pointer argument
return
an SSA represention with only the edge-splitter run

        SsaMethod result;

        result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

        edgeSplit(result);

        LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);

        placePhiFunctions(result, localInfo, 0);
        return result;
    
public static voidupdateSsaMethod(SsaMethod ssaMeth, int threshold)
Updates an SSA representation, placing phi functions and renaming all registers above a certain threshold number.

param
ssaMeth input
param
threshold registers below this number are unchanged

        LocalVariableInfo localInfo = LocalVariableExtractor.extract(ssaMeth);
        placePhiFunctions(ssaMeth, localInfo, threshold);
        new SsaRenamer(ssaMeth, threshold).run();