dx/ssa/SsaConverter.java

/*
 * 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.RopMethod;
import com.android.dx.util.IntIterator;

import java.util.ArrayList;
import java.util.BitSet;

/**
 * Converts ROP methods to SSA Methods
 */
public class SsaConverter {
    public static final boolean DEBUG = false;

    /**
     * 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
     */
    public static SsaMethod convertToSsaMethod(RopMethod rmeth,
            int paramWidth, boolean isStatic) {
        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;
    }

    /**
     * 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
     */
    public static void updateSsaMethod(SsaMethod ssaMeth, int threshold) {
        LocalVariableInfo localInfo = LocalVariableExtractor.extract(ssaMeth);
        placePhiFunctions(ssaMeth, localInfo, threshold);
        new SsaRenamer(ssaMeth, threshold).run();
    }

    /**
     * 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
     */
    public static SsaMethod testEdgeSplit (RopMethod rmeth, int paramWidth,
            boolean isStatic) {
        SsaMethod result;

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

        edgeSplit(result);
        return result;
    }

    /**
     * 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
     */
    public static SsaMethod testPhiPlacement (RopMethod rmeth, int paramWidth,
            boolean isStatic) {
        SsaMethod result;

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

        edgeSplit(result);

        LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);

        placePhiFunctions(result, localInfo, 0);
        return result;
    }

    /**
     * See Appel section 19.1:
     *
     * Converts CFG into "edge-split" form, such that each node either a
     * unique successor or unique predecessor.<p>
     *
     * 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
     */
    private static void edgeSplit(SsaMethod result) {
        edgeSplitPredecessors(result);
        edgeSplitMoveExceptionsAndResults(result);
        edgeSplitSuccessors(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
     */
    private static void edgeSplitPredecessors(SsaMethod result) {
        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();
            }
        }
    }

    /**
     * @param block {@code non-null;} block in question
     * @return {@code true} if this node needs to have a unique
     * predecessor created for it
     */
    private static boolean nodeNeedsUniquePredecessor(SsaBasicBlock block) {
        /*
         * 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);
    }

    /**
     * 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
     */
    private static void edgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth) {
        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);
            }
        }
    }

    /**
     * Inserts Z nodes for every node that needs a new
     * successor.
     *
     * @param result {@code non-null;} method to process
     */
    private static void edgeSplitSuccessors(SsaMethod result) {
        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);
                }
            }
        }
    }

    /**
     * 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
     */
    private static boolean needsNewSuccessor(SsaBasicBlock block,
            SsaBasicBlock succ) {
        ArrayList<SsaInsn> insns = block.getInsns();
        SsaInsn lastInsn = insns.get(insns.size() - 1);

        return ((lastInsn.getResult() != null)
                    || (lastInsn.getSources().size() > 0))
                && succ.getPredecessors().cardinality() > 1;
    }

    /**
     * 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
     */
    private static void placePhiFunctions (SsaMethod ssaMeth,
            LocalVariableInfo localInfo, int threshold) {
        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);
            }
        }
    }
}