FileDocCategorySizeDatePackage
SsaRenamer.javaAPI DocAndroid 1.5 API22238Wed May 06 22:41:02 BST 2009com.android.dx.ssa

SsaRenamer

public class SsaRenamer extends Object implements Runnable
Complete transformation to SSA form by renaming all registers accessed.

See Appel algorithm 19.7

Unlike the original algorithm presented in Appel, this renamer converts to a new flat (versionless) register space. The "version 0" registers, which represent the initial state of the Rop registers and should never actually be meaningfully accessed in a legal program, are represented as the first N registers in the SSA namespace. Subsequent assignments are assigned new unique names. Note that the incoming Rop representation has a concept of register widths, where 64-bit values are stored into two adjoining Rop registers. This adjoining register representation is ignored in SSA form conversion and while in SSA form, each register can be e either 32 or 64 bits wide depending on use. The adjoining-register represention is re-created later when converting back to Rop form.

But, please note, the SSA Renamer's ignoring of the adjoining-register ROP representation means that unaligned accesses to 64-bit registers are not supported. For example, you cannot do a 32-bit operation on a portion of a 64-bit register. This will never be observed to happen when coming from Java code, of course.

The implementation here, rather than keeping a single register version stack for the entire method as the dom tree is walked, instead keeps a mapping table for the current block being processed. Once the current block has been processed, this mapping table is then copied and used as the initial state for child blocks.

Fields Summary
private static final boolean
DEBUG
private final SsaMethod
ssaMeth
Method we're processing
private int
nextSsaReg
next available SSA register
private final int
ropRegCount
the number of original rop registers
private final RegisterSpec[]
startsForBlocks
Indexed by block index; register version state for each block start. This list is updated by each dom parent for its children. The only sub-arrays that exist at any one time are the start states for blocks yet to be processed by a BlockRenamer instance.
private final ArrayList
ssaRegToLocalItems
map of SSA register number to debug (local var names) or null of n/a
private com.android.dx.util.IntList
ssaRegToRopReg
Maps SSA registers back to the original rop number. Used for debug only.
Constructors Summary
SsaRenamer(SsaMethod ssaMeth)
Constructs an instance of the renamer

param
ssaMeth non-null; un-renamed SSA method that will be renamed.


                         
        
        ropRegCount = ssaMeth.getRegCount();

        this.ssaMeth = ssaMeth;
        /*
         * Reserve the first N registers in the SSA register space for
         * "version 0" registers
         */
        nextSsaReg = ropRegCount;
        startsForBlocks = new RegisterSpec[ssaMeth.getBlocks().size()][];

        ssaRegToLocalItems = new ArrayList<LocalItem>();

        if (DEBUG) {
            ssaRegToRopReg = new IntList(ropRegCount);
        }

        /*
         * Appel 19.7
         *
         * Initialization:
         *   for each variable a        // register i
         *      Count[a] <- 0           // nextSsaReg, flattened
         *      Stack[a] <- 0           // versionStack
         *      push 0 onto Stack[a]
         *
         */

        // top entry for the version stack is version 0
        RegisterSpec[] initialRegMapping = new RegisterSpec[ropRegCount];
        for (int i = 0; i < ropRegCount; i++) {
            // everyone starts with a version 0 register
            initialRegMapping[i] = RegisterSpec.make(i, Type.VOID);

            if (DEBUG) {
                ssaRegToRopReg.add(i);
            }
        }

        // Initial state for entry block
        startsForBlocks[ssaMeth.getEntryBlockIndex()] = initialRegMapping;
Methods Summary
private static RegisterSpec[]dupArray(RegisterSpec[] orig)
Duplicates a RegisterSpec array

param
orig non-null; array to duplicate
return
non-null; new instance

        RegisterSpec[] copy = new RegisterSpec[orig.length];

        System.arraycopy(orig, 0, copy, 0, orig.length);

        return copy;
private static booleanequalsHandlesNulls(java.lang.Object a, java.lang.Object b)
Returns true if a and b are equal or are both null

param
a null-ok
param
b null-ok
return
Returns true if a and b are equal or are both null

        return a == b ||  (a != null && a.equals(b));
private LocalItemgetLocalForNewReg(int ssaReg)
Gets a local variable item for a specified register.

param
ssaReg register in SSA name space
return
null-ok; Local variable name or null if none

        if (ssaReg < ssaRegToLocalItems.size()) {
            return ssaRegToLocalItems.get(ssaReg);
        } else {
            return null;
        }
private booleanisVersionZeroRegister(int ssaReg)
Returns true if this SSA register is a "version 0" register. All version 0 registers are assigned the first N register numbers, where N is the count of original rop registers.

param
ssaReg the SSA register in question
return
true if it is a version 0 register.

        return ssaReg < ropRegCount;
public voidrun()
Performs renaming transformation, modifying the method's instructions in-place.


        // Rename each block in dom-tree DFS order.
        ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() {
            public void visitBlock (SsaBasicBlock block, SsaBasicBlock unused) {
                new BlockRenamer(block).process();
            }
        });

        ssaMeth.setNewRegCount(nextSsaReg);
        ssaMeth.onInsnsChanged();

        if (DEBUG) {
            System.out.println("SSA\tRop");
            // We're going to compute the version of the rop register
            // by keeping a running total of how many times the rop register
            // has been mapped.
            int[] versions = new int[ropRegCount];

            int sz = ssaRegToRopReg.size();
            for(int i = 0; i < sz; i++) {
                int ropReg =  ssaRegToRopReg.get(i);
                System.out.println(i +"\t" + ropReg + "["
                        + versions[ropReg] + "]");
                versions[ropReg]++;
            }
        }
private voidsetNameForSsaReg(RegisterSpec ssaReg)
Records a debug (local variable) name for a specified register.

param
ssaReg non-null named register spec in SSA name space

        int reg = ssaReg.getReg();
        LocalItem local = ssaReg.getLocalItem();

        ssaRegToLocalItems.ensureCapacity(reg + 1);
        while (ssaRegToLocalItems.size() <= reg) {
            ssaRegToLocalItems.add(null);
        }

        ssaRegToLocalItems.set(reg, local);