dx/src/com/android/dx/dex/code/OutputFinisher.java - platform/dalvik - Git at Google

 /*
  * 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.dx.dex.code;

 import com.android.dx.rop.code.LocalItem;
 import com.android.dx.rop.code.RegisterSpec;
 import com.android.dx.rop.code.RegisterSpecList;
 import com.android.dx.rop.code.RegisterSpecSet;
 import com.android.dx.rop.code.SourcePosition;
 import com.android.dx.rop.cst.Constant;
 import com.android.dx.rop.cst.CstMemberRef;
 import com.android.dx.rop.cst.CstType;
 import com.android.dx.rop.cst.CstUtf8;
 import com.android.dx.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;
     }
 }
	/*
	* 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.dx.dex.code;

	import com.android.dx.rop.code.LocalItem;
	import com.android.dx.rop.code.RegisterSpec;
	import com.android.dx.rop.code.RegisterSpecList;
	import com.android.dx.rop.code.RegisterSpecSet;
	import com.android.dx.rop.code.SourcePosition;
	import com.android.dx.rop.cst.Constant;
	import com.android.dx.rop.cst.CstMemberRef;
	import com.android.dx.rop.cst.CstType;
	import com.android.dx.rop.cst.CstUtf8;
	import com.android.dx.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;
	}
	}