path: root/dx/src/com/android/dx/ssa/ConstCollector.java

/*
 * Copyright (C) 2008 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.rop.code.LocalItem;
import com.android.dx.rop.code.PlainCstInsn;
import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.RegOps;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Rop;
import com.android.dx.rop.code.Rops;
import com.android.dx.rop.code.SourcePosition;
import com.android.dx.rop.code.ThrowingCstInsn;
import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.CstString;
import com.android.dx.rop.cst.TypedConstant;
import com.android.dx.rop.type.StdTypeList;
import com.android.dx.rop.type.TypeBearer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * Collects constants that are used more than once at the top of the
 * method block. This increases register usage by about 5% but decreases
 * insn size by about 3%.
 */
public class ConstCollector {
    /** Maximum constants to collect per method. Puts cap on reg use */
    private static final int MAX_COLLECTED_CONSTANTS = 5;

    /**
     * Also collect string consts, although they can throw exceptions.
     * This is off now because it just doesn't seem to gain a whole lot.
     * TODO if you turn this on, you must change SsaInsn.hasSideEffect()
     * to return false for const-string insns whose exceptions are not
     * caught in the current method.
     */
    private static boolean COLLECT_STRINGS = false;

    /**
     * If true, allow one local var to be involved with a collected const.
     * Turned off because it mostly just inserts more moves.
     */
    private static boolean COLLECT_ONE_LOCAL = false;

    /** method we're processing */
    private final SsaMethod ssaMeth;

    /**
     * Processes a method.
     *
     * @param ssaMethod {@code non-null;} method to process
     */
    public static void process(SsaMethod ssaMethod) {
        ConstCollector cc = new ConstCollector(ssaMethod);
        cc.run();
    }

    /**
     * Constructs an instance.
     *
     * @param ssaMethod {@code non-null;} method to process
     */
    private ConstCollector(SsaMethod ssaMethod) {
        this.ssaMeth = ssaMethod;
    }

    /**
     * Applies the optimization.
     */
    private void run() {
        int regSz = ssaMeth.getRegCount();

        ArrayList<TypedConstant> constantList
                = getConstsSortedByCountUse();

        int toCollect = Math.min(constantList.size(), MAX_COLLECTED_CONSTANTS);

        SsaBasicBlock start = ssaMeth.getEntryBlock();

        // Constant to new register containing the constant
        HashMap<TypedConstant, RegisterSpec> newRegs
                = new HashMap<TypedConstant, RegisterSpec> (toCollect);

        for (int i = 0; i < toCollect; i++) {
            TypedConstant cst = constantList.get(i);
            RegisterSpec result
                    = RegisterSpec.make(ssaMeth.makeNewSsaReg(), cst);

            Rop constRop = Rops.opConst(cst);

            if (constRop.getBranchingness() == Rop.BRANCH_NONE) {
                start.addInsnToHead(
                        new PlainCstInsn(Rops.opConst(cst),
                                SourcePosition.NO_INFO, result,
                                RegisterSpecList.EMPTY, cst));
            } else {
                // We need two new basic blocks along with the new insn
                SsaBasicBlock entryBlock = ssaMeth.getEntryBlock();
                SsaBasicBlock successorBlock
                        = entryBlock.getPrimarySuccessor();

                // Insert a block containing the const insn.
                SsaBasicBlock constBlock
                        = entryBlock.insertNewSuccessor(successorBlock);

                constBlock.replaceLastInsn(
                        new ThrowingCstInsn(constRop, SourcePosition.NO_INFO,
                                RegisterSpecList.EMPTY,
                                StdTypeList.EMPTY, cst));

                // Insert a block containing the move-result-pseudo insn.

                SsaBasicBlock resultBlock
                        = constBlock.insertNewSuccessor(successorBlock);
                PlainInsn insn
                    = new PlainInsn(
                            Rops.opMoveResultPseudo(result.getTypeBearer()),
                            SourcePosition.NO_INFO,
                            result, RegisterSpecList.EMPTY);

                resultBlock.addInsnToHead(insn);
            }

            newRegs.put(cst, result);
        }

        updateConstUses(newRegs, regSz);
    }

    /**
     * Gets all of the collectable constant values used in this method,
     * sorted by most used first. Skips non-collectable consts, such as
     * non-string object constants
     *
     * @return {@code non-null;} list of constants in most-to-least used order
     */
    private ArrayList<TypedConstant> getConstsSortedByCountUse() {
        int regSz = ssaMeth.getRegCount();

        final HashMap<TypedConstant, Integer> countUses
                = new HashMap<TypedConstant, Integer>();

        /*
         * Each collected constant can be used by just one local
         * (used only if COLLECT_ONE_LOCAL is true).
         */
        final HashSet<TypedConstant> usedByLocal
                = new HashSet<TypedConstant>();

        // Count how many times each const value is used.
        for (int i = 0; i < regSz; i++) {
            SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

            if (insn == null || insn.getOpcode() == null) continue;

            RegisterSpec result = insn.getResult();
            TypeBearer typeBearer = result.getTypeBearer();

            if (!typeBearer.isConstant()) continue;

            TypedConstant cst = (TypedConstant) typeBearer;

            // Find defining instruction for move-result-pseudo instructions
            if (insn.getOpcode().getOpcode() == RegOps.MOVE_RESULT_PSEUDO) {
                int pred = insn.getBlock().getPredecessors().nextSetBit(0);
                ArrayList<SsaInsn> predInsns;
                predInsns = ssaMeth.getBlocks().get(pred).getInsns();
                insn = predInsns.get(predInsns.size()-1);
            }

            if (insn.canThrow()) {
                /*
                 * Don't move anything other than strings -- the risk
                 * of changing where an exception is thrown is too high.
                 */
                if (!(cst instanceof CstString) || !COLLECT_STRINGS) {
                    continue;
                }
                /*
                 * We can't move any throwable const whose throw will be
                 * caught, so don't count them.
                 */
                if (insn.getBlock().getSuccessors().cardinality() > 1) {
                    continue;
                }
            }

            /*
             * TODO: Might be nice to try and figure out which local
             * wins most when collected.
             */
            if (ssaMeth.isRegALocal(result)) {
                if (!COLLECT_ONE_LOCAL) {
                    continue;
                } else {
                    if (usedByLocal.contains(cst)) {
                        // Count one local usage only.
                        continue;
                    } else {
                        usedByLocal.add(cst);
                    }
                }
            }

            Integer has = countUses.get(cst);
            if (has == null) {
                countUses.put(cst, 1);
            } else {
                countUses.put(cst, has + 1);
            }
        }

        // Collect constants that have been reused.
        ArrayList<TypedConstant> constantList = new ArrayList<TypedConstant>();
        for (Map.Entry<TypedConstant, Integer> entry : countUses.entrySet()) {
            if (entry.getValue() > 1) {
                constantList.add(entry.getKey());
            }
        }

        // Sort by use, with most used at the beginning of the list.
        Collections.sort(constantList, new Comparator<Constant>() {
            public int compare(Constant a, Constant b) {
                int ret;
                ret = countUses.get(b) - countUses.get(a);

                if (ret == 0) {
                    /*
                     * Provide sorting determinisim for constants with same
                     * usage count.
                     */
                    ret = a.compareTo(b);
                }

                return ret;
            }

            @Override
            public boolean equals (Object obj) {
                return obj == this;
            }
        });

        return constantList;
    }

    /**
     * Inserts mark-locals if necessary when changing a register. If
     * the definition of {@code origReg} is associated with a local
     * variable, then insert a mark-local for {@code newReg} just below
     * it. We expect the definition of  {@code origReg} to ultimately
     * be removed by the dead code eliminator
     *
     * @param origReg {@code non-null;} original register
     * @param newReg {@code non-null;} new register that will replace
     * {@code origReg}
     */
    private void fixLocalAssignment(RegisterSpec origReg,
            RegisterSpec newReg) {
        for (SsaInsn use : ssaMeth.getUseListForRegister(origReg.getReg())) {
            RegisterSpec localAssignment = use.getLocalAssignment();
            if (localAssignment == null) {
                continue;
            }

            if (use.getResult() == null) {
                /*
                 * This is a mark-local. it will be updated when all uses
                 * are updated.
                 */
                continue;
            }

            LocalItem local = localAssignment.getLocalItem();

            // Un-associate original use.
            use.setResultLocal(null);

            // Now add a mark-local to the new reg immediately after.
            newReg = newReg.withLocalItem(local);

            SsaInsn newInsn
                    = SsaInsn.makeFromRop(
                        new PlainInsn(Rops.opMarkLocal(newReg),
                        SourcePosition.NO_INFO, null,
                                RegisterSpecList.make(newReg)),
                    use.getBlock());

            ArrayList<SsaInsn> insns = use.getBlock().getInsns();

            insns.add(insns.indexOf(use) + 1, newInsn);
        }
    }

    /**
     * Updates all uses of various consts to use the values in the newly
     * assigned registers.
     *
     * @param newRegs {@code non-null;} mapping between constant and new reg
     * @param origRegCount {@code >=0;} original SSA reg count, not including
     * newly added constant regs
     */
    private void updateConstUses(HashMap<TypedConstant, RegisterSpec> newRegs,
            int origRegCount) {

        /*
         * set of constants associated with a local variable; used
         * only if COLLECT_ONE_LOCAL is true.
         */
        final HashSet<TypedConstant> usedByLocal
                = new HashSet<TypedConstant>();

        final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();

        for (int i = 0; i < origRegCount; i++) {
            SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

            if (insn == null) {
                continue;
            }

            final RegisterSpec origReg = insn.getResult();
            TypeBearer typeBearer = insn.getResult().getTypeBearer();

            if (!typeBearer.isConstant()) continue;

            TypedConstant cst = (TypedConstant) typeBearer;
            final RegisterSpec newReg = newRegs.get(cst);

            if (newReg == null) {
                continue;
            }

            if (ssaMeth.isRegALocal(origReg)) {
                if (!COLLECT_ONE_LOCAL) {
                    continue;
                } else {
                    /*
                     * TODO: If the same local gets the same cst
                     * multiple times, it would be nice to reuse the
                     * register.
                     */
                    if (usedByLocal.contains(cst)) {
                        continue;
                    } else {
                        usedByLocal.add(cst);
                        fixLocalAssignment(origReg, newRegs.get(cst));
                    }
                }
            }

            // maps an original const register to the new collected register
            RegisterMapper mapper = new RegisterMapper() {
                @Override
                public int getNewRegisterCount() {
                    return ssaMeth.getRegCount();
                }

                @Override
                public RegisterSpec map(RegisterSpec registerSpec) {
                    if (registerSpec.getReg() == origReg.getReg()) {
                        return newReg.withLocalItem(
                                registerSpec.getLocalItem());
                    }

                    return registerSpec;
                }
            };

            for (SsaInsn use : useList[origReg.getReg()]) {
                if (use.canThrow()
                        && use.getBlock().getSuccessors().cardinality() > 1) {
                    continue;
                }
                use.mapSourceRegisters(mapper);
            }
        }
    }
}