FileDocCategorySizeDatePackage
OutputFinisher.javaAPI DocAndroid 1.5 API25803Wed May 06 22:41:02 BST 2009com.android.dx.dex.code

OutputFinisher

public final class OutputFinisher extends Object
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.

Fields Summary
private final int
unreservedRegCount
>= 0; register count for the method, not including any extra "reserved" registers needed to translate "difficult" instructions
private ArrayList
insns
non-null; the list of instructions, per se
private boolean
hasAnyPositionInfo
whether any instruction has position info
private boolean
hasAnyLocalInfo
whether any instruction has local variable info
private int
reservedCount
>= 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}
Constructors Summary
public OutputFinisher(int initialCapacity, int regCount)
Constructs an instance. It initially contains no instructions.

param
regCount >= 0; register count for the method
param
initialCapacity >= 0; initial capacity of the instructions list

        this.unreservedRegCount = regCount;
        this.insns = new ArrayList<DalvInsn>(initialCapacity);
        this.reservedCount = -1;
        this.hasAnyPositionInfo = false;
        this.hasAnyLocalInfo = false;
    
Methods Summary
public voidadd(DalvInsn insn)
Adds an instruction to the output.

param
insn non-null; the instruction to add

        insns.add(insn);
        updateInfo(insn);
    
private static voidaddConstants(java.util.HashSet result, DalvInsn insn)
Helper for {@link #getAllConstants} which adds all the info for a single instruction.

param
result non-null; result set to add to
param
insn non-null; instruction to scrutinize

        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);
        }
    
private static voidaddConstants(java.util.HashSet result, com.android.dx.rop.code.RegisterSpec spec)
Helper for {@link #getAllConstants} which adds all the info for a single RegisterSpec.

param
result non-null; result set to add to
param
spec null-ok; register spec to add

        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);
        }
    
private voidassignAddresses()
Helper for {@link #assignAddressesAndFixBranches}, which assigns an address to each instruction, in order.

        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();
        }
    
private voidassignAddressesAndFixBranches()
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.

        for (;;) {
            assignAddresses();
            if (!fixBranches()) {
                break;
            }
        }
    
public voidassignIndices(DalvCode.AssignIndicesCallback callback)
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 non-null; callback object

        for (DalvInsn insn : insns) {
            if (insn instanceof CstInsn) {
                assignIndices((CstInsn) insn, callback);
            }
        }
    
private static voidassignIndices(CstInsn insn, DalvCode.AssignIndicesCallback callback)
Helper for {@link #assignIndices} which does assignment for one instruction.

param
insn non-null; the instruction
param
callback non-null; the 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);
            }
        }
    
private intcalculateReservedCount(InsnFormat[] formats)
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 formats list to help avoid extra work in future register reservation passes.

param
formats non-null; array of per-instruction format selections
return
>= 0; the count of reserved registers

        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;
    
private InsnFormatfindFormatForInsn(DalvInsn insn, InsnFormat format)
Attempts to fit the given instruction into a format, returning either a format that the instruction fits into or 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 non-null; the instruction in question
param
format null-ok; the current guess as to the best instruction format to use; null means that no simple format fits
return
null-ok; a possibly-different format, which is either a good fit or null to indicate that no simple format fits

        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;
    
public DalvInsnListfinishProcessingAndGetList()
Does final processing on this instance and gets the output as a {@link DalvInsnList}. Final processing consists of:
  • optionally renumbering registers (to make room as needed for expanded instructions)
  • picking a final opcode for each instruction
  • rewriting instructions, because of register number, constant pool index, or branch target size issues
  • assigning final addresses

Note: This method may only be called once per instance of this class.

return
non-null; the output list
throws
UnsupportedOperationException if this method has already been called

        if (reservedCount >= 0) {
            throw new UnsupportedOperationException("already processed");
        }

        InsnFormat[] formats = makeFormatsArray();
        reserveRegisters(formats);
        massageInstructions(formats);
        assignAddressesAndFixBranches();

        return DalvInsnList.makeImmutable(insns,
                reservedCount + unreservedRegCount);
    
private booleanfixBranches()
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 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 goto to the original target.

return
whether any branches had to be fixed

        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;
    
public java.util.HashSetgetAllConstants()
Returns the set of all constants referred to by instructions added to this instance.

return
non-null; the set of constants

        HashSet<Constant> result = new HashSet<Constant>(20);

        for (DalvInsn insn : insns) {
            addConstants(result, insn);
        }

        return result;
    
public booleanhasAnyLocalInfo()
Returns whether this instance has any local variable information.

return
whether this instance has any local variable information

        return hasAnyLocalInfo;
    
public booleanhasAnyPositionInfo()
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

        return hasAnyPositionInfo;
    
private static booleanhasLocalInfo(DalvInsn insn)
Helper for {@link #add} which scrutinizes a single instruction for local variable information.

param
insn non-null; instruction to scrutinize
return
true iff the instruction refers to any named locals

        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;
    
private static booleanhasLocalInfo(com.android.dx.rop.code.RegisterSpec spec)
Helper for {@link #hasAnyLocalInfo} which scrutinizes a single register spec.

param
spec non-null; spec to scrutinize
return
true iff the spec refers to any named locals

        return (spec != null)
            && (spec.getLocalItem().getName() != null);
    
public voidinsert(int at, DalvInsn insn)
Inserts an instruction in the output at the given offset.

param
at >= 0; what index to insert at
param
insn non-null; the instruction to insert

        insns.add(at, insn);
        updateInfo(insn);
    
private InsnFormat[]makeFormatsArray()
Helper for {@link #finishProcessingAndGetList}, which extracts the format out of each instruction into a separate array, to be further manipulated as things progress.

return
non-null; the array of formats

        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;
    
private voidmassageInstructions(InsnFormat[] formats)
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 will work.

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.

This method ignores issues of branch target size, since final addresses aren't known at the point that this method is called.

param
formats non-null; array of per-instruction format selections

        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);
        }
    
private java.util.ArrayListperformExpansion(InsnFormat[] 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 non-null; array of per-instruction format selections
return
non-null; the replacement list

        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;
    
private voidreserveRegisters(InsnFormat[] formats)
Helper for {@link #finishProcessingAndGetList}, which figures out how many reserved registers are required and then reserving them. It also updates the given formats array so as to avoid extra work when constructing the massaged instruction list.

param
formats non-null; array of per-instruction format selections

        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;
    
public voidreverseBranch(int which, CodeAddress newTarget)
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; 0 is the most recently added instruction, 1 is the instruction before that, etc.
param
newTarget non-null; the new target for the reversed branch

        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));
    
private voidupdateInfo(DalvInsn insn)
Helper for {@link #add} and {@link #insert}, which updates the position and local info flags.

param
insn non-null; an instruction that was just introduced

        if (! hasAnyPositionInfo) {
            SourcePosition pos = insn.getPosition();
            if (pos.getLine() >= 0) {
                hasAnyPositionInfo = true;
            }
        }

        if (! hasAnyLocalInfo) {
            if (hasLocalInfo(insn)) {
                hasAnyLocalInfo = true;
            }
        }