1 files changed, 391 insertions, 0 deletions
diff --git a/dx/src/com/android/dx/ssa/SsaConverter.java b/dx/src/com/android/dx/ssa/SsaConverter.java
new file mode 100644
index 0000000..5cd8b6f
--- /dev/null
+++ b/dx/src/com/android/dx/ssa/SsaConverter.java
@@ -0,0 +1,391 @@
+/*
+ * 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);
+            }
+        }
+    }
+}