FileDocCategorySizeDatePackage
FirstFitAllocator.javaAPI DocAndroid 1.5 API4921Wed May 06 22:41:02 BST 2009com.android.dx.ssa.back

FirstFitAllocator

public class FirstFitAllocator extends RegisterAllocator
Allocates registers via a naive n^2 register allocator. This allocator does not try to co-locate local variables or deal intelligently with different size register uses.

Fields Summary
private static final boolean
PRESLOT_PARAMS
If true, allocator places parameters at the top of the frame in calling-convention order.
private final BitSet
mapped
indexed by old reg; the set of old regs we've mapped
Constructors Summary
public FirstFitAllocator(com.android.dx.ssa.SsaMethod ssaMeth, InterferenceGraph interference)
{@inheritDoc}


      
     
                  
        super(ssaMeth, interference);

        mapped = new BitSet(ssaMeth.getRegCount());
Methods Summary
public com.android.dx.ssa.RegisterMapperallocateRegisters()
{@inheritDoc}

        int oldRegCount = ssaMeth.getRegCount();

        BasicRegisterMapper mapper
                = new BasicRegisterMapper(oldRegCount);

        int nextNewRegister = 0;

        if (PRESLOT_PARAMS) {
            /*
             * Reserve space for the params at the bottom of the register
             * space. Later, we'll flip the params to the end of the register
             * space.
             */

            nextNewRegister = ssaMeth.getParamWidth();
        }

        for (int i = 0; i < oldRegCount; i++) {
            if (mapped.get(i)) {
                // we already got this one
                continue;
            }

            int maxCategory = getCategoryForSsaReg(i);
            IntSet current = new BitIntSet(oldRegCount);

            interference.mergeInterferenceSet(i, current);

            boolean isPreslotted = false;
            int newReg = 0;

            if (PRESLOT_PARAMS && isDefinitionMoveParam(i)) {
                // Any move-param definition must be a NormalSsaInsn
                NormalSsaInsn defInsn = (NormalSsaInsn)
                       ssaMeth.getDefinitionForRegister(i);

                newReg = paramNumberFromMoveParam(defInsn);

                mapper.addMapping(i, newReg, maxCategory);
                isPreslotted = true;
            } else {
                mapper.addMapping(i, nextNewRegister, maxCategory);
                newReg = nextNewRegister;
            }

            for (int j = i + 1; j < oldRegCount; j++) {

                if (mapped.get(j) || isDefinitionMoveParam(j)) {
                    continue;
                }

                /*
                 * If reg j doesn't interfere with the current mapping.
                 * Also, if this is a pre-slotted method parameter, we
                 * can't use more than the original param width.
                 */
                if (!current.has(j)
                        && !(isPreslotted
                            && (maxCategory < getCategoryForSsaReg(j)))) {

                    interference.mergeInterferenceSet(j, current);

                    maxCategory = Math.max(maxCategory,
                            getCategoryForSsaReg(j));

                    mapper.addMapping(j, newReg, maxCategory);
                    mapped.set(j);
                }
            }

            mapped.set(i);
            if (!isPreslotted) {
                nextNewRegister += maxCategory;
            }
        }

        return mapper;
private intparamNumberFromMoveParam(com.android.dx.ssa.NormalSsaInsn ndefInsn)
Returns the parameter number that this move-param insn refers to

param
ndefInsn a move-param insn (otherwise, exceptions will be thrown)
return
parameter number (offset in the total parameter width)

        CstInsn origInsn = (CstInsn) ndefInsn.getOriginalRopInsn();

        return ((CstInteger) origInsn.getConstant()).getValue();
public booleanwantsParamsMovedHigh()
{@inheritDoc}

        return PRESLOT_PARAMS;