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

PhiTypeResolver

public class PhiTypeResolver extends Object
Resolves the result types of phi instructions. When phi instructions are inserted, their result types are set to BT_VOID (which is a nonsensical type for a register) but must be resolve to a real type before converting out of SSA form.

The resolve is done as an iterative merge of each phi's operand types. Phi operands may be themselves be the result of unresolved phis, and the algorithm tries to find the most-fit type (for example, if every operand is the same constant value or the same local variable info, we want that to be reflected).

This algorithm assumes a dead-code remover has already removed all circular-only phis that may have been inserted.

Fields Summary
SsaMethod
ssaMeth
private final BitSet
worklist
indexed by register; all registers still defined by unresolved phis
Constructors Summary
private PhiTypeResolver(SsaMethod ssaMeth)

        this.ssaMeth = ssaMeth;
        worklist = new BitSet(ssaMeth.getRegCount());
Methods Summary
private static booleanequalsHandlesNulls(com.android.dx.rop.code.LocalItem a, com.android.dx.rop.code.LocalItem b)
Returns true if a and b are equal, whether or not either of them are null.

param
a
param
b
return
true if equal

        return (a == b) || ((a != null) && a.equals(b));
public static voidprocess(SsaMethod ssaMeth)
Resolves all phi types in the method

param
ssaMeth method to process

        new PhiTypeResolver(ssaMeth).run();
booleanresolveResultType(PhiInsn insn)
Resolves the result of a phi insn based on its operands. The "void" type, which is a nonsensical type for a register, is used for registers defined by as-of-yet-unresolved phi operations.

return
true if the result type changed, false if no change

        insn.updateSourcesToDefinitions(ssaMeth);

        RegisterSpecList sources = insn.getSources();

        // Start by finding the first non-void operand
        RegisterSpec first = null;
        int firstIndex = -1;

        int szSources = sources.size();
        for (int i = 0 ; i <szSources ; i++) {
            RegisterSpec rs = sources.get(i);

            if (rs.getBasicType() != Type.BT_VOID) {
                first = rs;
                firstIndex = i;
            }
        }

        if (first == null) {
            // All operands are void -- we're not ready to resolve yet
            return false;
        }

        LocalItem firstLocal = first.getLocalItem();
        TypeBearer mergedType = first.getType();
        boolean sameLocals = true;
        for (int i = 0 ; i < szSources ; i++) {
            if (i == firstIndex) {
                continue;
            }

            RegisterSpec rs = sources.get(i);

            // Just skip void (unresolved phi results) for now
            if (rs.getBasicType() == Type.BT_VOID){
                continue;
            }

            sameLocals = sameLocals
                    && equalsHandlesNulls(firstLocal, rs.getLocalItem());

            mergedType = Merger.mergeType(mergedType, rs.getType());
        }

        TypeBearer newResultType;

        if (mergedType != null) {
            newResultType = mergedType;
        } else {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < szSources; i++) {
                sb.append(sources.get(i).toString());
                sb.append(' ");
            }

            throw new RuntimeException ("Couldn't map types in phi insn:" + sb);
        }

        LocalItem newLocal = sameLocals ? firstLocal : null;
        
        RegisterSpec result = insn.getResult();

        if ((result.getTypeBearer() == newResultType)
                && equalsHandlesNulls(newLocal, result.getLocalItem())) {
            return false;
        }

        insn.changeResultType(newResultType, newLocal);

        return true;
private voidrun()
Runs the phi-type resolver.


        int regCount = ssaMeth.getRegCount();

        for (int reg = 0; reg < regCount; reg++) {
            SsaInsn definsn = ssaMeth.getDefinitionForRegister(reg);

            if (definsn != null
                    && (definsn.getResult().getBasicType() == Type.BT_VOID)) {
                worklist.set(reg);
            }
        }

        int reg;
        while ( 0 <= (reg = worklist.nextSetBit(0))) {
            worklist.clear(reg);

            /*
             * definitions on the worklist have a type of BT_VOID, which
             * must have originated from a PhiInsn.
             */
            PhiInsn definsn = (PhiInsn)ssaMeth.getDefinitionForRegister(reg);

            if (resolveResultType(definsn)) {
                /*
                 * If the result type has changed, re-resolve all phis
                 * that use this.
                 */

                List<SsaInsn> useList = ssaMeth.getUseListForRegister(reg);

                int sz = useList.size();
                for (int i = 0; i < sz; i++ ) {
                    SsaInsn useInsn = useList.get(i);
                    RegisterSpec resultReg = useInsn.getResult();
                    if (resultReg != null && useInsn instanceof PhiInsn) {
                        worklist.set(resultReg.getReg());
                    }
                }
            }
        }