Use the static opcode chains in dx.
This removes the need to iterate over all possible opcodes looking for
family/format matches whenever the need arises to rewrite an
instruction with a new opcode. This should speed dx up at least a
little, though I don't know if it will be measurable. It's certainly
cleaner and a bit simpler, though.
Change-Id: I779f19cb1249d30f6886faf76670ae37d5dfc402
diff --git a/dx/src/com/android/dx/dex/code/Dops.java b/dx/src/com/android/dx/dex/code/Dops.java
index 34d356d..417c1f1 100644
--- a/dx/src/com/android/dx/dex/code/Dops.java
+++ b/dx/src/com/android/dx/dex/code/Dops.java
@@ -1410,33 +1410,22 @@
}
/**
- * Gets the {@link Dop} with the given family/format combination, if
- * any.
+ * Gets the next {@link Dop} in the instruction fitting chain after the
+ * given instance, if any.
*
- * @param family {@code DalvOps.MIN_VALUE..DalvOps.MAX_VALUE;} the
- * opcode family
- * @param format {@code non-null;} the opcode's instruction format
- * @return {@code null-ok;} the corresponding opcode, or {@code null} if
- * there is none
+ * @param opcode {@code non-null;} the opcode
+ * @return {@code null-ok;} the next opcode in the same family, in the
+ * chain of opcodes to try, or {@code null} if the given opcode is
+ * the last in its chain
*/
- public static Dop getOrNull(int family, InsnFormat format) {
- if (format == null) {
- throw new NullPointerException("format == null");
+ public static Dop getNextOrNull(Dop opcode) {
+ int nextOpcode = opcode.getNextOpcode();
+
+ if (nextOpcode == DalvOps.NO_NEXT) {
+ return null;
}
- int len = DOPS.length;
-
- // TODO: Linear search is bad.
- for (int i = 0; i < len; i++) {
- Dop dop = DOPS[i];
- if ((dop != null) &&
- (dop.getFamily() == family) &&
- (dop.getFormat() == format)) {
- return dop;
- }
- }
-
- return null;
+ return get(nextOpcode);
}
/**
diff --git a/dx/src/com/android/dx/dex/code/OutputFinisher.java b/dx/src/com/android/dx/dex/code/OutputFinisher.java
index 4a51198..9d6fec7 100644
--- a/dx/src/com/android/dx/dex/code/OutputFinisher.java
+++ b/dx/src/com/android/dx/dex/code/OutputFinisher.java
@@ -63,8 +63,8 @@
* 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
+ * @param initialCapacity {@code >= 0;} initial capacity of the
+ * instructions list
*/
public OutputFinisher(int initialCapacity, int regCount) {
this.unreservedRegCount = regCount;
@@ -255,7 +255,8 @@
* @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
+ * @param newTarget {@code non-null;} the new target for the
+ * reversed branch
*/
public void reverseBranch(int which, CodeAddress newTarget) {
int size = insns.size();
@@ -345,9 +346,9 @@
throw new UnsupportedOperationException("already processed");
}
- InsnFormat[] formats = makeFormatsArray();
- reserveRegisters(formats);
- massageInstructions(formats);
+ Dop[] opcodes = makeOpcodesArray();
+ reserveRegisters(opcodes);
+ massageInstructions(opcodes);
assignAddressesAndFixBranches();
return DalvInsnList.makeImmutable(insns,
@@ -356,17 +357,17 @@
/**
* Helper for {@link #finishProcessingAndGetList}, which extracts
- * the format out of each instruction into a separate array, to be
+ * the opcode out of each instruction into a separate array, to be
* further manipulated as things progress.
*
- * @return {@code non-null;} the array of formats
+ * @return {@code non-null;} the array of opcodes
*/
- private InsnFormat[] makeFormatsArray() {
+ private Dop[] makeOpcodesArray() {
int size = insns.size();
- InsnFormat[] result = new InsnFormat[size];
+ Dop[] result = new Dop[size];
for (int i = 0; i < size; i++) {
- result[i] = insns.get(i).getOpcode().getFormat();
+ result[i] = insns.get(i).getOpcode();
}
return result;
@@ -375,13 +376,14 @@
/**
* 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
+ * them. It also updates the given {@code opcodes} array so
* as to avoid extra work when constructing the massaged
* instruction list.
*
- * @param formats {@code non-null;} array of per-instruction format selections
+ * @param opcodes {@code non-null;} array of per-instruction
+ * opcode selections
*/
- private void reserveRegisters(InsnFormat[] formats) {
+ private void reserveRegisters(Dop[] opcodes) {
int oldReservedCount = (reservedCount < 0) ? 0 : reservedCount;
/*
@@ -389,7 +391,7 @@
* reservation, repeatedly until no new reservations happen.
*/
for (;;) {
- int newReservedCount = calculateReservedCount(formats);
+ int newReservedCount = calculateReservedCount(opcodes);
if (oldReservedCount >= newReservedCount) {
break;
}
@@ -425,13 +427,14 @@
* 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
+ * {@code opcodes} list to help avoid extra work in future
* register reservation passes.
*
- * @param formats {@code non-null;} array of per-instruction format selections
+ * @param opcodes {@code non-null;} array of per-instruction
+ * opcode selections
* @return {@code >= 0;} the count of reserved registers
*/
- private int calculateReservedCount(InsnFormat[] formats) {
+ private int calculateReservedCount(Dop[] opcodes) {
int size = insns.size();
/*
@@ -444,14 +447,14 @@
for (int i = 0; i < size; i++) {
DalvInsn insn = insns.get(i);
- InsnFormat originalFormat = formats[i];
- InsnFormat newFormat = findFormatForInsn(insn, originalFormat);
+ Dop originalOpcode = opcodes[i];
+ Dop newOpcode = findOpcodeForInsn(insn, originalOpcode);
- if (originalFormat == newFormat) {
+ if (originalOpcode == newOpcode) {
continue;
}
- if (newFormat == null) {
+ if (newOpcode == null) {
/*
* The instruction will need to be expanded, so reserve
* registers for it.
@@ -462,50 +465,43 @@
}
}
- formats[i] = newFormat;
+ opcodes[i] = newOpcode;
}
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.
+ * Attempts to fit the given instruction into a specific opcode,
+ * returning the opcode whose 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
+ * opcode 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
+ * @param guess {@code null-ok;} the current guess as to the best
+ * opcode; {@code null} means that no simple opcode fits
+ * @return {@code null-ok;} a possibly-different opcode; either a
+ * {@code non-null} good fit or {@code null} to indicate that no
+ * simple opcode fits
*/
- private InsnFormat findFormatForInsn(DalvInsn insn, InsnFormat format) {
- if (format == null) {
- // The instruction is already known not to fit any simple format.
- return format;
- }
+ private Dop findOpcodeForInsn(DalvInsn insn, Dop guess) {
+ /*
+ * Note: The initial guess might be null, meaning that an
+ * earlier call to this method already determined that there
+ * was no possible simple opcode fit.
+ */
- 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))) {
+ while (guess != null) {
+ if (guess.getFormat().isCompatible(insn)) {
break;
}
+
+ guess = Dops.getNextOrNull(guess);
}
- return format;
+ return guess;
}
/**
@@ -527,27 +523,27 @@
* 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
+ * @param opcodes {@code non-null;} array of per-instruction
+ * opcode selections
*/
- private void massageInstructions(InsnFormat[] formats) {
+ private void massageInstructions(Dop[] opcodes) {
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.
+ * merely need to replace any instructions whose format
+ * (and hence whose opcode) 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];
+ Dop originalOpcode = insn.getOpcode();
+ Dop currentOpcode = opcodes[i];
- if (format != dop.getFormat()) {
- dop = Dops.getOrNull(dop.getFamily(), format);
- insns.set(i, insn.withOpcode(dop));
+ if (originalOpcode != currentOpcode) {
+ insns.set(i, insn.withOpcode(currentOpcode));
}
}
} else {
@@ -555,7 +551,7 @@
* The difficult uncommon case: Some instructions have to be
* expanded to deal with high registers.
*/
- insns = performExpansion(formats);
+ insns = performExpansion(opcodes);
}
}
@@ -566,22 +562,22 @@
* 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
+ * @param opcodes {@code non-null;} array of per-instruction
+ * opcode selections
* @return {@code non-null;} the replacement list
*/
- private ArrayList<DalvInsn> performExpansion(InsnFormat[] formats) {
+ private ArrayList<DalvInsn> performExpansion(Dop[] opcodes) {
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];
+ Dop originalOpcode = insn.getOpcode();
+ Dop currentOpcode = opcodes[i];
DalvInsn prefix;
DalvInsn suffix;
- if (currentFormat != null) {
+ if (currentOpcode != null) {
// No expansion is necessary.
prefix = null;
suffix = null;
@@ -592,20 +588,19 @@
/*
* Get the initial guess as to the hr version, but then
- * let findFormatForInsn() pick a better format, if any.
+ * let findOpcodeForInsn() pick a better format, if any.
*/
insn = insn.hrVersion();
- originalFormat = insn.getOpcode().getFormat();
- currentFormat = findFormatForInsn(insn, originalFormat);
+ originalOpcode = insn.getOpcode();
+ currentOpcode = findOpcodeForInsn(insn, originalOpcode);
}
if (prefix != null) {
result.add(prefix);
}
- if (currentFormat != originalFormat) {
- dop = Dops.getOrNull(dop.getFamily(), currentFormat);
- insn = insn.withOpcode(dop);
+ if (currentOpcode != originalOpcode) {
+ insn = insn.withOpcode(currentOpcode);
}
result.add(insn);
@@ -669,18 +664,17 @@
continue;
}
- Dop dop = insn.getOpcode();
- InsnFormat format = dop.getFormat();
+ Dop opcode = insn.getOpcode();
TargetInsn target = (TargetInsn) insn;
- if (format.branchFits(target)) {
+ if (opcode.getFormat().branchFits(target)) {
continue;
}
- if (dop.getFamily() == DalvOps.GOTO) {
+ if (opcode.getFamily() == DalvOps.GOTO) {
// It is a goto; widen it if possible.
- InsnFormat newFormat = findFormatForInsn(insn, format);
- if (newFormat == null) {
+ opcode = findOpcodeForInsn(insn, opcode);
+ if (opcode == null) {
/*
* The branch is already maximally large. This should
* only be possible if a method somehow manages to have
@@ -688,9 +682,7 @@
*/
throw new UnsupportedOperationException("method too long");
}
- dop = Dops.getOrNull(dop.getFamily(), newFormat);
- insn = insn.withOpcode(dop);
- insns.set(i, insn);
+ insns.set(i, insn.withOpcode(opcode));
} else {
/*
* It is a conditional: Reverse its sense, and arrange for
