| /* |
| * 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; |
| } |
| } |