/*
* 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.dexgen.dex.code;
import com.android.dexgen.rop.code.LocalItem;
import com.android.dexgen.rop.code.RegisterSpec;
import com.android.dexgen.rop.code.RegisterSpecList;
import com.android.dexgen.rop.code.RegisterSpecSet;
import com.android.dexgen.rop.code.SourcePosition;
import com.android.dexgen.rop.cst.Constant;
import com.android.dexgen.rop.cst.CstMemberRef;
import com.android.dexgen.rop.cst.CstType;
import com.android.dexgen.rop.cst.CstUtf8;
import com.android.dexgen.rop.type.Type;
import java.util.ArrayList;
import java.util.HashSet;
/**
* Processor for instruction lists, which takes a "first cut" of
* instruction selection as a basis and produces a "final cut" in the
* form of a {@link DalvInsnList} instance.
*/
public final class OutputFinisher {
/**
* {@code >= 0;} register count for the method, not including any extra
* "reserved" registers needed to translate "difficult" instructions
*/
private final int unreservedRegCount;
/** {@code non-null;} the list of instructions, per se */
private ArrayList<DalvInsn> insns;
/** whether any instruction has position info */
private boolean hasAnyPositionInfo;
/** whether any instruction has local variable info */
private boolean hasAnyLocalInfo;
/**
* {@code >= 0;} the count of reserved registers (low-numbered
* registers used when expanding instructions that can't be
* represented simply); becomes valid after a call to {@link
* #massageInstructions}
*/
private int reservedCount;
/**
* Constructs an instance. It initially contains no instructions.
*
* @param regCount {@code >= 0;} register count for the method
* @param initialCapacity {@code >= 0;} initial capacity of the instructions
* list
*/
public OutputFinisher(int initialCapacity, int regCount) {
this.unreservedRegCount = regCount;
this.insns = new ArrayList<DalvInsn>(initialCapacity);
this.reservedCount = -1;
this.hasAnyPositionInfo = false;
this.hasAnyLocalInfo = false;
}
/**
* Returns whether any of the instructions added to this instance
* come with position info.
*
* @return whether any of the instructions added to this instance
* come with position info
*/
public boolean hasAnyPositionInfo() {
return hasAnyPositionInfo;
}
/**
* Returns whether this instance has any local variable information.
*
* @return whether this instance has any local variable information
*/
public boolean hasAnyLocalInfo() {
return hasAnyLocalInfo;
}
/**
* Helper for {@link #add} which scrutinizes a single
* instruction for local variable information.
*
* @param insn {@code non-null;} instruction to scrutinize
* @return {@code true} iff the instruction refers to any
* named locals
*/
private static boolean hasLocalInfo(DalvInsn insn) {
if (insn instanceof LocalSnapshot) {
RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals();
int size = specs.size();
for (int i = 0; i < size; i++) {
if (hasLocalInfo(specs.get(i))) {
return true;
}
}
} else if (insn instanceof LocalStart) {
RegisterSpec spec = ((LocalStart) insn).getLocal();
if (hasLocalInfo(spec)) {
return true;
}
}
return false;
}
/**
* Helper for {@link #hasAnyLocalInfo} which scrutinizes a single
* register spec.
*
* @param spec {@code non-null;} spec to scrutinize
* @return {@code true} iff the spec refers to any
* named locals
*/
private static boolean hasLocalInfo(RegisterSpec spec) {
return (spec != null)
&& (spec.getLocalItem().getName() != null);
}
/**
* Returns the set of all constants referred to by instructions added
* to this instance.
*
* @return {@code non-null;} the set of constants
*/
public HashSet<Constant> getAllConstants() {
HashSet<Constant> result = new HashSet<Constant>(20);
for (DalvInsn insn : insns) {
addConstants(result, insn);
}
return result;
}
/**
* Helper for {@link #getAllConstants} which adds all the info for
* a single instruction.
*
* @param result {@code non-null;} result set to add to
* @param insn {@code non-null;} instruction to scrutinize
*/
private static void addConstants(HashSet<Constant> result,
DalvInsn insn) {
if (insn instanceof CstInsn) {
Constant cst = ((CstInsn) insn).getConstant();
result.add(cst);
} else if (insn instanceof LocalSnapshot) {
RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals();
int size = specs.size();
for (int i = 0; i < size; i++) {
addConstants(result, specs.get(i));
}
} else if (insn instanceof LocalStart) {
RegisterSpec spec = ((LocalStart) insn).getLocal();
addConstants(result, spec);
}
}
/**
* Helper for {@link #getAllConstants} which adds all the info for
* a single {@code RegisterSpec}.
*
* @param result {@code non-null;} result set to add to
* @param spec {@code null-ok;} register spec to add
*/
private static void addConstants(HashSet<Constant> result,
RegisterSpec spec) {
if (spec == null) {
return;
}
LocalItem local = spec.getLocalItem();
CstUtf8 name = local.getName();
CstUtf8 signature = local.getSignature();
Type type = spec.getType();
if (type != Type.KNOWN_NULL) {
result.add(CstType.intern(type));
}
if (name != null) {
result.add(name);
}
if (signature != null) {
result.add(signature);
}
}
/**
* Adds an instruction to the output.
*
* @param insn {@code non-null;} the instruction to add
*/
public void add(DalvInsn insn) {
insns.add(insn);
updateInfo(insn);
}
/**
* Inserts an instruction in the output at the given offset.
*
* @param at {@code >= 0;} what index to insert at
* @param insn {@code non-null;} the instruction to insert
*/
public void insert(int at, DalvInsn insn) {
insns.add(at, insn);
updateInfo(insn);
}
/**
* Helper for {@link #add} and {@link #insert},
* which updates the position and local info flags.
*
* @param insn {@code non-null;} an instruction that was just introduced
*/
private void updateInfo(DalvInsn insn) {
if (! hasAnyPositionInfo) {
SourcePosition pos = insn.getPosition();
if (pos.getLine() >= 0) {
hasAnyPositionInfo = true;
}
}
if (! hasAnyLocalInfo) {
if (hasLocalInfo(insn)) {
hasAnyLocalInfo = true;
}
}
}
/**
* Reverses a branch which is buried a given number of instructions
* backward in the output. It is illegal to call this unless the
* indicated instruction really is a reversible branch.
*
* @param which how many instructions back to find the branch;
* {@code 0} is the most recently added instruction,
* {@code 1} is the instruction before that, etc.
* @param newTarget {@code non-null;} the new target for the reversed branch
*/
public void reverseBranch(int which, CodeAddress newTarget) {
int size = insns.size();
int index = size - which - 1;
TargetInsn targetInsn;
try {
targetInsn = (TargetInsn) insns.get(index);
} catch (IndexOutOfBoundsException ex) {
// Translate the exception.
throw new IllegalArgumentException("too few instructions");
} catch (ClassCastException ex) {
// Translate the exception.
throw new IllegalArgumentException("non-reversible instruction");
}
/*
* No need to call this.set(), since the format and other info
* are the same.
*/
insns.set(index, targetInsn.withNewTargetAndReversed(newTarget));
}
/**
* Assigns indices in all instructions that need them, using the
* given callback to perform lookups. This should be called before
* calling {@link #finishProcessingAndGetList}.
*
* @param callback {@code non-null;} callback object
*/
public void assignIndices(DalvCode.AssignIndicesCallback callback) {
for (DalvInsn insn : insns) {
if (insn instanceof CstInsn) {
assignIndices((CstInsn) insn, callback);
}
}
}
/**
* Helper for {@link #assignIndices} which does assignment for one
* instruction.
*
* @param insn {@code non-null;} the instruction
* @param callback {@code non-null;} the callback
*/
private static void assignIndices(CstInsn insn,
DalvCode.AssignIndicesCallback callback) {
Constant cst = insn.getConstant();
int index = callback.getIndex(cst);
if (index >= 0) {
insn.setIndex(index);
}
if (cst instanceof CstMemberRef) {
CstMemberRef member = (CstMemberRef) cst;
CstType definer = member.getDefiningClass();
index = callback.getIndex(definer);
if (index >= 0) {
insn.setClassIndex(index);
}
}
}
/**
* Does final processing on this instance and gets the output as
* a {@link DalvInsnList}. Final processing consists of:
*
* <ul>
* <li>optionally renumbering registers (to make room as needed for
* expanded instructions)</li>
* <li>picking a final opcode for each instruction</li>
* <li>rewriting instructions, because of register number,
* constant pool index, or branch target size issues</li>
* <li>assigning final addresses</li>
* </ul>
*
* <p><b>Note:</b> This method may only be called once per instance
* of this class.</p>
*
* @return {@code non-null;} the output list
* @throws UnsupportedOperationException if this method has
* already been called
*/
public DalvInsnList finishProcessingAndGetList() {
if (reservedCount >= 0) {
throw new UnsupportedOperationException("already processed");
}
InsnFormat[] formats = makeFormatsArray();
reserveRegisters(formats);
massageInstructions(formats);
assignAddressesAndFixBranches();
return DalvInsnList.makeImmutable(insns,
reservedCount + unreservedRegCount);
}
/**
* Helper for {@link #finishProcessingAndGetList}, which extracts
* the format out of each instruction into a separate array, to be
* further manipulated as things progress.
*
* @return {@code non-null;} the array of formats
*/
private InsnFormat[] makeFormatsArray() {
int size = insns.size();
InsnFormat[] result = new InsnFormat[size];
for (int i = 0; i < size; i++) {
result[i] = insns.get(i).getOpcode().getFormat();
}
return result;
}
/**
* Helper for {@link #finishProcessingAndGetList}, which figures
* out how many reserved registers are required and then reserving
* them. It also updates the given {@code formats} array so
* as to avoid extra work when constructing the massaged
* instruction list.
*
* @param formats {@code non-null;} array of per-instruction format selections
*/
private void reserveRegisters(InsnFormat[] formats) {
int oldReservedCount = (reservedCount < 0) ? 0 : reservedCount;
/*
* Call calculateReservedCount() and then perform register
* reservation, repeatedly until no new reservations happen.
*/
for (;;) {
int newReservedCount = calculateReservedCount(formats);
if (oldReservedCount >= newReservedCount) {
break;
}
int reservedDifference = newReservedCount - oldReservedCount;
int size = insns.size();
for (int i = 0; i < size; i++) {
/*
* CodeAddress instance identity is used to link
* TargetInsns to their targets, so it is
* inappropriate to make replacements, and they don't
* have registers in any case. Hence, the instanceof
* test below.
*/
DalvInsn insn = insns.get(i);
if (!(insn instanceof CodeAddress)) {
/*
* No need to call this.set() since the format and
* other info are the same.
*/
insns.set(i, insn.withRegisterOffset(reservedDifference));
}
}
oldReservedCount = newReservedCount;
}
reservedCount = oldReservedCount;
}
/**
* Helper for {@link #reserveRegisters}, which does one
* pass over the instructions, calculating the number of
* registers that need to be reserved. It also updates the
* {@code formats} list to help avoid extra work in future
* register reservation passes.
*
* @param formats {@code non-null;} array of per-instruction format selections
* @return {@code >= 0;} the count of reserved registers
*/
private int calculateReservedCount(InsnFormat[] formats) {
int size = insns.size();
/*
* Potential new value of reservedCount, which gets updated in the
* following loop. It starts out with the existing reservedCount
* and gets increased if it turns out that additional registers
* need to be reserved.
*/
int newReservedCount = reservedCount;
for (int i = 0; i < size; i++) {
DalvInsn insn = insns.get(i);
InsnFormat originalFormat = formats[i];
InsnFormat newFormat = findFormatForInsn(insn, originalFormat);
if (originalFormat == newFormat) {
continue;
}
if (newFormat == null) {
/*
* The instruction will need to be expanded, so reserve
* registers for it.
*/
int reserve = insn.getMinimumRegisterRequirement();
if (reserve > newReservedCount) {
newReservedCount = reserve;
}
}
formats[i] = newFormat;
}
return newReservedCount;
}
/**
* Attempts to fit the given instruction into a format, returning
* either a format that the instruction fits into or {@code null}
* to indicate that the instruction will need to be expanded. This
* fitting process starts with the given format as a first "best
* guess" and then pessimizes from there if necessary.
*
* @param insn {@code non-null;} the instruction in question
* @param format {@code null-ok;} the current guess as to the best instruction
* format to use; {@code null} means that no simple format fits
* @return {@code null-ok;} a possibly-different format, which is either a
* good fit or {@code null} to indicate that no simple format
* fits
*/
private InsnFormat findFormatForInsn(DalvInsn insn, InsnFormat format) {
if (format == null) {
// The instruction is already known not to fit any simple format.
return format;
}
if (format.isCompatible(insn)) {
// The instruction already fits in the current best-known format.
return format;
}
Dop dop = insn.getOpcode();
int family = dop.getFamily();
for (;;) {
format = format.nextUp();
if ((format == null) ||
(format.isCompatible(insn) &&
(Dops.getOrNull(family, format) != null))) {
break;
}
}
return format;
}
/**
* Helper for {@link #finishProcessingAndGetList}, which goes
* through each instruction in the output, making sure its opcode
* can accomodate its arguments. In cases where the opcode is
* unable to do so, this replaces the instruction with a larger
* instruction with identical semantics that <i>will</i> work.
*
* <p>This method may also reserve a number of low-numbered
* registers, renumbering the instructions' original registers, in
* order to have register space available in which to move
* very-high registers when expanding instructions into
* multi-instruction sequences. This expansion is done when no
* simple instruction format can be found for a given instruction that
* is able to accomodate that instruction's registers.</p>
*
* <p>This method ignores issues of branch target size, since
* final addresses aren't known at the point that this method is
* called.</p>
*
* @param formats {@code non-null;} array of per-instruction format selections
*/
private void massageInstructions(InsnFormat[] formats) {
if (reservedCount == 0) {
/*
* The easy common case: No registers were reserved, so we
* merely need to replace any instructions whose format changed
* during the reservation pass, but all instructions will stay
* at their original indices, and the instruction list doesn't
* grow.
*/
int size = insns.size();
for (int i = 0; i < size; i++) {
DalvInsn insn = insns.get(i);
Dop dop = insn.getOpcode();
InsnFormat format = formats[i];
if (format != dop.getFormat()) {
dop = Dops.getOrNull(dop.getFamily(), format);
insns.set(i, insn.withOpcode(dop));
}
}
} else {
/*
* The difficult uncommon case: Some instructions have to be
* expanded to deal with high registers.
*/
insns = performExpansion(formats);
}
}
/**
* Helper for {@link #massageInstructions}, which constructs a
* replacement list, where each {link DalvInsn} instance that
* couldn't be represented simply (due to register representation
* problems) is expanded into a series of instances that together
* perform the proper function.
*
* @param formats {@code non-null;} array of per-instruction format selections
* @return {@code non-null;} the replacement list
*/
private ArrayList<DalvInsn> performExpansion(InsnFormat[] formats) {
int size = insns.size();
ArrayList<DalvInsn> result = new ArrayList<DalvInsn>(size * 2);
for (int i = 0; i < size; i++) {
DalvInsn insn = insns.get(i);
Dop dop = insn.getOpcode();
InsnFormat originalFormat = dop.getFormat();
InsnFormat currentFormat = formats[i];
DalvInsn prefix;
DalvInsn suffix;
if (currentFormat != null) {
// No expansion is necessary.
prefix = null;
suffix = null;
} else {
// Expansion is required.
prefix = insn.hrPrefix();
suffix = insn.hrSuffix();
/*
* Get the initial guess as to the hr version, but then
* let findFormatForInsn() pick a better format, if any.
*/
insn = insn.hrVersion();
originalFormat = insn.getOpcode().getFormat();
currentFormat = findFormatForInsn(insn, originalFormat);
}
if (prefix != null) {
result.add(prefix);
}
if (currentFormat != originalFormat) {
dop = Dops.getOrNull(dop.getFamily(), currentFormat);
insn = insn.withOpcode(dop);
}
result.add(insn);
if (suffix != null) {
result.add(suffix);
}
}
return result;
}
/**
* Helper for {@link #finishProcessingAndGetList}, which assigns
* addresses to each instruction, possibly rewriting branches to
* fix ones that wouldn't otherwise be able to reach their
* targets.
*/
private void assignAddressesAndFixBranches() {
for (;;) {
assignAddresses();
if (!fixBranches()) {
break;
}
}
}
/**
* Helper for {@link #assignAddressesAndFixBranches}, which
* assigns an address to each instruction, in order.
*/
private void assignAddresses() {
int address = 0;
int size = insns.size();
for (int i = 0; i < size; i++) {
DalvInsn insn = insns.get(i);
insn.setAddress(address);
address += insn.codeSize();
}
}
/**
* Helper for {@link #assignAddressesAndFixBranches}, which checks
* the branch target size requirement of each branch instruction
* to make sure it fits. For instructions that don't fit, this
* rewrites them to use a {@code goto} of some sort. In the
* case of a conditional branch that doesn't fit, the sense of the
* test is reversed in order to branch around a {@code goto}
* to the original target.
*
* @return whether any branches had to be fixed
*/
private boolean fixBranches() {
int size = insns.size();
boolean anyFixed = false;
for (int i = 0; i < size; i++) {
DalvInsn insn = insns.get(i);
if (!(insn instanceof TargetInsn)) {
// This loop only needs to inspect TargetInsns.
continue;
}
Dop dop = insn.getOpcode();
InsnFormat format = dop.getFormat();
TargetInsn target = (TargetInsn) insn;
if (format.branchFits(target)) {
continue;
}
if (dop.getFamily() == DalvOps.GOTO) {
// It is a goto; widen it if possible.
InsnFormat newFormat = findFormatForInsn(insn, format);
if (newFormat == null) {
/*
* The branch is already maximally large. This should
* only be possible if a method somehow manages to have
* more than 2^31 code units.
*/
throw new UnsupportedOperationException("method too long");
}
dop = Dops.getOrNull(dop.getFamily(), newFormat);
insn = insn.withOpcode(dop);
insns.set(i, insn);
} else {
/*
* It is a conditional: Reverse its sense, and arrange for
* it to branch around an absolute goto to the original
* branch target.
*
* Note: An invariant of the list being processed is
* that every TargetInsn is followed by a CodeAddress.
* Hence, it is always safe to get the next element
* after a TargetInsn and cast it to CodeAddress, as
* is happening a few lines down.
*
* Also note: Size gets incremented by one here, as we
* have -- in the net -- added one additional element
* to the list, so we increment i to match. The added
* and changed elements will be inspected by a repeat
* call to this method after this invocation returns.
*/
CodeAddress newTarget;
try {
newTarget = (CodeAddress) insns.get(i + 1);
} catch (IndexOutOfBoundsException ex) {
// The TargetInsn / CodeAddress invariant was violated.
throw new IllegalStateException(
"unpaired TargetInsn (dangling)");
} catch (ClassCastException ex) {
// The TargetInsn / CodeAddress invariant was violated.
throw new IllegalStateException("unpaired TargetInsn");
}
TargetInsn gotoInsn =
new TargetInsn(Dops.GOTO, target.getPosition(),
RegisterSpecList.EMPTY, target.getTarget());
insns.set(i, gotoInsn);
insns.add(i, target.withNewTargetAndReversed(newTarget));
size++;
i++;
}
anyFixed = true;
}
return anyFixed;
}
}
|
