/*
* 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.*;
import com.android.dx.rop.type.TypeBearer;
import com.android.dx.rop.type.StdTypeList;
import com.android.dx.rop.type.Type;
import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.TypedConstant;
import com.android.dx.rop.cst.CstString;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
/**
* 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;
/**
* Process a method.
*
* @param ssaMethod non-null; method to process
*/
public static void process(SsaMethod ssaMethod) {
ConstCollector dc;
dc = new ConstCollector(ssaMethod);
dc.run();
}
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);
resultBlock.addInsnToHead(
new PlainInsn(
Rops.opMoveResultPseudo(result.getTypeBearer()),
SourcePosition.NO_INFO,
result, RegisterSpecList.EMPTY));
}
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 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) continue;
RegisterSpec result = insn.getResult();
TypeBearer typeBearer = insn.getResult().getTypeBearer();
if (!typeBearer.isConstant()) continue;
TypedConstant cst = (TypedConstant) typeBearer;
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
Iterator<TypedConstant> it = countUses.keySet().iterator();
ArrayList<TypedConstant> constantList = new ArrayList<TypedConstant>();
while (it.hasNext()) {
TypedConstant cst = it.next();
if (countUses.get(cst) > 1) {
constantList.add(cst);
}
}
// 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;
}
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</code> is associated with a local
* variable, then insert a mark-local for <code>newReg</code> just below
* it. We expect the definition of <code>origReg</code> to ultimately
* be removed by the dead code eliminator
*
* @param origReg non-null; original register
* @param newReg non-null; new register that will replace
* <code>origReg</code>
*/
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 non-null; mapping between constant and new reg
* @param origRegCount >=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);
}
}
}
}
|
