ssa/back/RegisterAllocator.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.back;

import com.android.dx.rop.code.RegOps;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.Rops;
import com.android.dx.rop.code.SourcePosition;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.ssa.NormalSsaInsn;
import com.android.dx.ssa.RegisterMapper;
import com.android.dx.ssa.SsaInsn;
import com.android.dx.ssa.SsaMethod;
import com.android.dx.ssa.SsaBasicBlock;
import com.android.dx.util.IntSet;
import com.android.dx.util.IntIterator;

import java.util.BitSet;
import java.util.ArrayList;

/**
 * Base class of all register allocators.
 */
public abstract class RegisterAllocator {
    /** method being processed */
    protected final SsaMethod ssaMeth;

    /** interference graph, indexed by register in both dimensions */
    protected final InterferenceGraph interference;

    /**
     * Creates an instance. Call {@code allocateRegisters} to run.
     * @param ssaMeth method to process.
     * @param interference Interference graph, indexed by register in both
     * dimensions.
     */
    public RegisterAllocator(SsaMethod ssaMeth,
            InterferenceGraph interference) {
        this.ssaMeth = ssaMeth;
        this.interference = interference;
    }

    /**
     * Indicates whether the method params were allocated at the bottom
     * of the namespace, and thus should be moved up to the top of the
     * namespace after phi removal.
     *
     * @return {@code true} if params should be moved from low to high
     */
    public abstract boolean wantsParamsMovedHigh();

    /**
     * Runs the algorithm.
     *
     * @return a register mapper to apply to the {@code SsaMethod}
     */
    public abstract RegisterMapper allocateRegisters();

    /**
     * Returns the category (width) of the definition site of the register.
     * Returns {@code 1} for undefined registers.
     *
     * @param reg register
     * @return {@code 1..2}
     */
    protected final int getCategoryForSsaReg(int reg) {
        SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);

        if (definition == null) {
            // an undefined reg
            return 1;
        } else {
            return definition.getResult().getCategory();
        }
    }

    /**
     * Returns the RegisterSpec of the definition of the register.
     *
     * @param reg {@code >= 0;} SSA register
     * @return definition spec of the register or null if it is never defined
     * (for the case of "version 0" SSA registers)
     */
    protected final RegisterSpec getDefinitionSpecForSsaReg(int reg) {
        SsaInsn definition = ssaMeth.getDefinitionForRegister(reg);

        return definition == null ? null : definition.getResult();
    }

    /**
     * Returns true if the definition site of this register is a
     * move-param (ie, this is a method parameter).
     *
     * @param reg register in question
     * @return {@code true} if this is a method parameter
     */
    protected boolean isDefinitionMoveParam(int reg) {
        SsaInsn defInsn = ssaMeth.getDefinitionForRegister(reg);

        if (defInsn instanceof NormalSsaInsn) {
            NormalSsaInsn ndefInsn = (NormalSsaInsn) defInsn;

            return ndefInsn.getOpcode().getOpcode() == RegOps.MOVE_PARAM;
        }

        return false;
    }

    /**
     * Inserts a move instruction for a specified SSA register before a
     * specified instruction, creating a new SSA register and adjusting the
     * interference graph in the process. The insn currently must be the
     * last insn in a block.
     *
     * @param insn {@code non-null;} insn to insert move before, must
     * be last insn in block
     * @param reg {@code non-null;} SSA register to duplicate
     * @return {@code non-null;} spec of new SSA register created by move
     */
    protected final RegisterSpec insertMoveBefore(SsaInsn insn,
            RegisterSpec reg) {
        SsaBasicBlock block = insn.getBlock();
        ArrayList<SsaInsn> insns = block.getInsns();
        int insnIndex = insns.indexOf(insn);

        if (insnIndex < 0) {
            throw new IllegalArgumentException (
                    "specified insn is not in this block");
        }

        if (insnIndex != insns.size() - 1) {
            /*
             * Presently, the interference updater only works when
             * adding before the last insn, and the last insn must have no
             * result
             */
            throw new IllegalArgumentException(
                    "Adding move here not supported:" + insn.toHuman());
        }

        /*
         * Get new register and make new move instruction.
         */

        // The new result must not have an associated local variable.
        RegisterSpec newRegSpec = RegisterSpec.make(ssaMeth.makeNewSsaReg(),
                reg.getTypeBearer());

        SsaInsn toAdd = SsaInsn.makeFromRop(
                new PlainInsn(Rops.opMove(newRegSpec.getType()),
                        SourcePosition.NO_INFO, newRegSpec,
                        RegisterSpecList.make(reg)), block);

        insns.add(insnIndex, toAdd);

        int newReg = newRegSpec.getReg();

        /*
         * Adjust interference graph based on what's live out of the current
         * block and what's used by the final instruction.
         */

        IntSet liveOut = block.getLiveOutRegs();
        IntIterator liveOutIter = liveOut.iterator();

        while (liveOutIter.hasNext()) {
            interference.add(newReg, liveOutIter.next());
        }

        // Everything that's a source in the last insn interferes.
        RegisterSpecList sources = insn.getSources();
        int szSources = sources.size();

        for (int i = 0; i < szSources; i++) {
            interference.add(newReg, sources.get(i).getReg());
        }

        ssaMeth.onInsnsChanged();

        return newRegSpec;
    }
}