dx/src/com/android/dx/ssa/PhiTypeResolver.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.cf.code.Merger;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.LocalItem;
import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeBearer;

import java.util.BitSet;
import java.util.List;

/**
 * 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.<p>
 *
 * 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).<p>
 *
 * This algorithm assumes a dead-code remover has already removed all
 * circular-only phis that may have been inserted.
 */
public class PhiTypeResolver {

    SsaMethod ssaMeth;
    /** indexed by register; all registers still defined by unresolved phis */
    private final BitSet worklist;

    /**
     * Resolves all phi types in the method
     * @param ssaMeth method to process
     */
    public static void process (SsaMethod ssaMeth) {
        new PhiTypeResolver(ssaMeth).run();
    }

    private PhiTypeResolver(SsaMethod ssaMeth) {
        this.ssaMeth = ssaMeth;
        worklist = new BitSet(ssaMeth.getRegCount());
    }

    /**
     * Runs the phi-type resolver.
     */
    private void run() {

        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());
                    }
                }
            }
        }
    }

    /**
     * Returns true if a and b are equal, whether
     * or not either of them are null.
     * @param a
     * @param b
     * @return true if equal
     */
    private static boolean equalsHandlesNulls(LocalItem a, LocalItem b) {
        return (a == b) || ((a != null) && a.equals(b));
    }

    /**
     * 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
     */
    boolean resolveResultType(PhiInsn insn) {
        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;
    }
}