| /* |
| * 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.RegisterSpec; |
| import com.android.dexgen.rop.code.RegisterSpecSet; |
| import com.android.dexgen.rop.cst.CstType; |
| import com.android.dexgen.rop.cst.CstUtf8; |
| import com.android.dexgen.rop.type.Type; |
| import com.android.dexgen.util.FixedSizeList; |
| |
| import java.io.PrintStream; |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| |
| /** |
| * List of local variables. Each local variable entry indicates a |
| * range of code which it is valid for, a register number, a name, |
| * and a type. |
| */ |
| public final class LocalList extends FixedSizeList { |
| /** {@code non-null;} empty instance */ |
| public static final LocalList EMPTY = new LocalList(0); |
| |
| /** whether to run the self-check code */ |
| private static final boolean DEBUG = false; |
| |
| /** |
| * Constructs an instance. All indices initially contain {@code null}. |
| * |
| * @param size {@code >= 0;} the size of the list |
| */ |
| public LocalList(int size) { |
| super(size); |
| } |
| |
| /** |
| * Gets the element at the given index. It is an error to call |
| * this with the index for an element which was never set; if you |
| * do that, this will throw {@code NullPointerException}. |
| * |
| * @param n {@code >= 0, < size();} which index |
| * @return {@code non-null;} element at that index |
| */ |
| public Entry get(int n) { |
| return (Entry) get0(n); |
| } |
| |
| /** |
| * Sets the entry at the given index. |
| * |
| * @param n {@code >= 0, < size();} which index |
| * @param entry {@code non-null;} the entry to set at {@code n} |
| */ |
| public void set(int n, Entry entry) { |
| set0(n, entry); |
| } |
| |
| /** |
| * Does a human-friendly dump of this instance. |
| * |
| * @param out {@code non-null;} where to dump |
| * @param prefix {@code non-null;} prefix to attach to each line of output |
| */ |
| public void debugPrint(PrintStream out, String prefix) { |
| int sz = size(); |
| |
| for (int i = 0; i < sz; i++) { |
| out.print(prefix); |
| out.println(get(i)); |
| } |
| } |
| |
| /** |
| * Disposition of a local entry. |
| */ |
| public static enum Disposition { |
| /** local started (introduced) */ |
| START, |
| |
| /** local ended without being replaced */ |
| END_SIMPLY, |
| |
| /** local ended because it was directly replaced */ |
| END_REPLACED, |
| |
| /** local ended because it was moved to a different register */ |
| END_MOVED, |
| |
| /** |
| * local ended because the previous local clobbered this one |
| * (because it is category-2) |
| */ |
| END_CLOBBERED_BY_PREV, |
| |
| /** |
| * local ended because the next local clobbered this one |
| * (because this one is a category-2) |
| */ |
| END_CLOBBERED_BY_NEXT; |
| } |
| |
| /** |
| * Entry in a local list. |
| */ |
| public static class Entry implements Comparable<Entry> { |
| /** {@code >= 0;} address */ |
| private final int address; |
| |
| /** {@code non-null;} disposition of the local */ |
| private final Disposition disposition; |
| |
| /** {@code non-null;} register spec representing the variable */ |
| private final RegisterSpec spec; |
| |
| /** {@code non-null;} variable type (derived from {@code spec}) */ |
| private final CstType type; |
| |
| /** |
| * Constructs an instance. |
| * |
| * @param address {@code >= 0;} address |
| * @param disposition {@code non-null;} disposition of the local |
| * @param spec {@code non-null;} register spec representing |
| * the variable |
| */ |
| public Entry(int address, Disposition disposition, RegisterSpec spec) { |
| if (address < 0) { |
| throw new IllegalArgumentException("address < 0"); |
| } |
| |
| if (disposition == null) { |
| throw new NullPointerException("disposition == null"); |
| } |
| |
| try { |
| if (spec.getLocalItem() == null) { |
| throw new NullPointerException( |
| "spec.getLocalItem() == null"); |
| } |
| } catch (NullPointerException ex) { |
| // Elucidate the exception. |
| throw new NullPointerException("spec == null"); |
| } |
| |
| this.address = address; |
| this.disposition = disposition; |
| this.spec = spec; |
| this.type = CstType.intern(spec.getType()); |
| } |
| |
| /** {@inheritDoc} */ |
| public String toString() { |
| return Integer.toHexString(address) + " " + disposition + " " + |
| spec; |
| } |
| |
| /** {@inheritDoc} */ |
| public boolean equals(Object other) { |
| if (!(other instanceof Entry)) { |
| return false; |
| } |
| |
| return (compareTo((Entry) other) == 0); |
| } |
| |
| /** |
| * Compares by (in priority order) address, end then start |
| * disposition (variants of end are all consistered |
| * equivalent), and spec. |
| * |
| * @param other {@code non-null;} entry to compare to |
| * @return {@code -1..1;} standard result of comparison |
| */ |
| public int compareTo(Entry other) { |
| if (address < other.address) { |
| return -1; |
| } else if (address > other.address) { |
| return 1; |
| } |
| |
| boolean thisIsStart = isStart(); |
| boolean otherIsStart = other.isStart(); |
| |
| if (thisIsStart != otherIsStart) { |
| return thisIsStart ? 1 : -1; |
| } |
| |
| return spec.compareTo(other.spec); |
| } |
| |
| /** |
| * Gets the address. |
| * |
| * @return {@code >= 0;} the address |
| */ |
| public int getAddress() { |
| return address; |
| } |
| |
| /** |
| * Gets the disposition. |
| * |
| * @return {@code non-null;} the disposition |
| */ |
| public Disposition getDisposition() { |
| return disposition; |
| } |
| |
| /** |
| * Gets whether this is a local start. This is just shorthand for |
| * {@code getDisposition() == Disposition.START}. |
| * |
| * @return {@code true} iff this is a start |
| */ |
| public boolean isStart() { |
| return disposition == Disposition.START; |
| } |
| |
| /** |
| * Gets the variable name. |
| * |
| * @return {@code null-ok;} the variable name |
| */ |
| public CstUtf8 getName() { |
| return spec.getLocalItem().getName(); |
| } |
| |
| /** |
| * Gets the variable signature. |
| * |
| * @return {@code null-ok;} the variable signature |
| */ |
| public CstUtf8 getSignature() { |
| return spec.getLocalItem().getSignature(); |
| } |
| |
| /** |
| * Gets the variable's type. |
| * |
| * @return {@code non-null;} the type |
| */ |
| public CstType getType() { |
| return type; |
| } |
| |
| /** |
| * Gets the number of the register holding the variable. |
| * |
| * @return {@code >= 0;} the number of the register holding |
| * the variable |
| */ |
| public int getRegister() { |
| return spec.getReg(); |
| } |
| |
| /** |
| * Gets the RegisterSpec of the register holding the variable. |
| * |
| * @return {@code non-null;} RegisterSpec of the holding register. |
| */ |
| public RegisterSpec getRegisterSpec() { |
| return spec; |
| } |
| |
| /** |
| * Returns whether or not this instance matches the given spec. |
| * |
| * @param otherSpec {@code non-null;} the spec in question |
| * @return {@code true} iff this instance matches |
| * {@code spec} |
| */ |
| public boolean matches(RegisterSpec otherSpec) { |
| return spec.equalsUsingSimpleType(otherSpec); |
| } |
| |
| /** |
| * Returns whether or not this instance matches the spec in |
| * the given instance. |
| * |
| * @param other {@code non-null;} another entry |
| * @return {@code true} iff this instance's spec matches |
| * {@code other} |
| */ |
| public boolean matches(Entry other) { |
| return matches(other.spec); |
| } |
| |
| /** |
| * Returns an instance just like this one but with the disposition |
| * set as given. |
| * |
| * @param disposition {@code non-null;} the new disposition |
| * @return {@code non-null;} an appropriately-constructed instance |
| */ |
| public Entry withDisposition(Disposition disposition) { |
| if (disposition == this.disposition) { |
| return this; |
| } |
| |
| return new Entry(address, disposition, spec); |
| } |
| } |
| |
| /** |
| * Constructs an instance for the given method, based on the given |
| * block order and intermediate local information. |
| * |
| * @param insns {@code non-null;} instructions to convert |
| * @return {@code non-null;} the constructed list |
| */ |
| public static LocalList make(DalvInsnList insns) { |
| int sz = insns.size(); |
| |
| /* |
| * Go through the insn list, looking for all the local |
| * variable pseudoinstructions, splitting out LocalSnapshots |
| * into separate per-variable starts, adding explicit ends |
| * wherever a variable is replaced or moved, and collecting |
| * these and all the other local variable "activity" |
| * together into an output list (without the other insns). |
| * |
| * Note: As of this writing, this method won't be handed any |
| * insn lists that contain local ends, but I (danfuzz) expect |
| * that to change at some point, when we start feeding that |
| * info explicitly into the rop layer rather than only trying |
| * to infer it. So, given that expectation, this code is |
| * written to deal with them. |
| */ |
| |
| MakeState state = new MakeState(sz); |
| |
| for (int i = 0; i < sz; i++) { |
| DalvInsn insn = insns.get(i); |
| |
| if (insn instanceof LocalSnapshot) { |
| RegisterSpecSet snapshot = |
| ((LocalSnapshot) insn).getLocals(); |
| state.snapshot(insn.getAddress(), snapshot); |
| } else if (insn instanceof LocalStart) { |
| RegisterSpec local = ((LocalStart) insn).getLocal(); |
| state.startLocal(insn.getAddress(), local); |
| } else if (insn instanceof LocalEnd) { |
| RegisterSpec local = ((LocalEnd) insn).getLocal(); |
| state.endLocal(insn.getAddress(), local); |
| } |
| } |
| |
| LocalList result = state.finish(); |
| |
| if (DEBUG) { |
| debugVerify(result); |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Debugging helper that verifies the constraint that a list doesn't |
| * contain any redundant local starts and that local ends that are |
| * due to replacements are properly annotated. |
| */ |
| private static void debugVerify(LocalList locals) { |
| try { |
| debugVerify0(locals); |
| } catch (RuntimeException ex) { |
| int sz = locals.size(); |
| for (int i = 0; i < sz; i++) { |
| System.err.println(locals.get(i)); |
| } |
| throw ex; |
| } |
| |
| } |
| |
| /** |
| * Helper for {@link #debugVerify} which does most of the work. |
| */ |
| private static void debugVerify0(LocalList locals) { |
| int sz = locals.size(); |
| Entry[] active = new Entry[65536]; |
| |
| for (int i = 0; i < sz; i++) { |
| Entry e = locals.get(i); |
| int reg = e.getRegister(); |
| |
| if (e.isStart()) { |
| Entry already = active[reg]; |
| |
| if ((already != null) && e.matches(already)) { |
| throw new RuntimeException("redundant start at " + |
| Integer.toHexString(e.getAddress()) + ": got " + |
| e + "; had " + already); |
| } |
| |
| active[reg] = e; |
| } else { |
| if (active[reg] == null) { |
| throw new RuntimeException("redundant end at " + |
| Integer.toHexString(e.getAddress())); |
| } |
| |
| int addr = e.getAddress(); |
| boolean foundStart = false; |
| |
| for (int j = i + 1; j < sz; j++) { |
| Entry test = locals.get(j); |
| if (test.getAddress() != addr) { |
| break; |
| } |
| if (test.getRegisterSpec().getReg() == reg) { |
| if (test.isStart()) { |
| if (e.getDisposition() |
| != Disposition.END_REPLACED) { |
| throw new RuntimeException( |
| "improperly marked end at " + |
| Integer.toHexString(addr)); |
| } |
| foundStart = true; |
| } else { |
| throw new RuntimeException( |
| "redundant end at " + |
| Integer.toHexString(addr)); |
| } |
| } |
| } |
| |
| if (!foundStart && |
| (e.getDisposition() == Disposition.END_REPLACED)) { |
| throw new RuntimeException( |
| "improper end replacement claim at " + |
| Integer.toHexString(addr)); |
| } |
| |
| active[reg] = null; |
| } |
| } |
| } |
| |
| /** |
| * Intermediate state when constructing a local list. |
| */ |
| public static class MakeState { |
| /** {@code non-null;} result being collected */ |
| private final ArrayList<Entry> result; |
| |
| /** |
| * {@code >= 0;} running count of nulled result entries, to help with |
| * sizing the final list |
| */ |
| private int nullResultCount; |
| |
| /** {@code null-ok;} current register mappings */ |
| private RegisterSpecSet regs; |
| |
| /** {@code null-ok;} result indices where local ends are stored */ |
| private int[] endIndices; |
| |
| /** {@code >= 0;} last address seen */ |
| private int lastAddress; |
| |
| /** |
| * Constructs an instance. |
| */ |
| public MakeState(int initialSize) { |
| result = new ArrayList<Entry>(initialSize); |
| nullResultCount = 0; |
| regs = null; |
| endIndices = null; |
| lastAddress = 0; |
| } |
| |
| /** |
| * Checks the address and other vitals as a prerequisite to |
| * further processing. |
| * |
| * @param address {@code >= 0;} address about to be processed |
| * @param reg {@code >= 0;} register number about to be processed |
| */ |
| private void aboutToProcess(int address, int reg) { |
| boolean first = (endIndices == null); |
| |
| if ((address == lastAddress) && !first) { |
| return; |
| } |
| |
| if (address < lastAddress) { |
| throw new RuntimeException("shouldn't happen"); |
| } |
| |
| if (first || (reg >= endIndices.length)) { |
| /* |
| * This is the first allocation of the state set and |
| * index array, or we need to grow. (The latter doesn't |
| * happen much; in fact, we have only ever observed |
| * it happening in test cases, never in "real" code.) |
| */ |
| int newSz = reg + 1; |
| RegisterSpecSet newRegs = new RegisterSpecSet(newSz); |
| int[] newEnds = new int[newSz]; |
| Arrays.fill(newEnds, -1); |
| |
| if (!first) { |
| newRegs.putAll(regs); |
| System.arraycopy(endIndices, 0, newEnds, 0, |
| endIndices.length); |
| } |
| |
| regs = newRegs; |
| endIndices = newEnds; |
| } |
| } |
| |
| /** |
| * Sets the local state at the given address to the given snapshot. |
| * The first call on this instance must be to this method, so that |
| * the register state can be properly sized. |
| * |
| * @param address {@code >= 0;} the address |
| * @param specs {@code non-null;} spec set representing the locals |
| */ |
| public void snapshot(int address, RegisterSpecSet specs) { |
| if (DEBUG) { |
| System.err.printf("%04x snapshot %s\n", address, specs); |
| } |
| |
| int sz = specs.getMaxSize(); |
| aboutToProcess(address, sz - 1); |
| |
| for (int i = 0; i < sz; i++) { |
| RegisterSpec oldSpec = regs.get(i); |
| RegisterSpec newSpec = filterSpec(specs.get(i)); |
| |
| if (oldSpec == null) { |
| if (newSpec != null) { |
| startLocal(address, newSpec); |
| } |
| } else if (newSpec == null) { |
| endLocal(address, oldSpec); |
| } else if (! newSpec.equalsUsingSimpleType(oldSpec)) { |
| endLocal(address, oldSpec); |
| startLocal(address, newSpec); |
| } |
| } |
| |
| if (DEBUG) { |
| System.err.printf("%04x snapshot done\n", address); |
| } |
| } |
| |
| /** |
| * Starts a local at the given address. |
| * |
| * @param address {@code >= 0;} the address |
| * @param startedLocal {@code non-null;} spec representing the |
| * started local |
| */ |
| public void startLocal(int address, RegisterSpec startedLocal) { |
| if (DEBUG) { |
| System.err.printf("%04x start %s\n", address, startedLocal); |
| } |
| |
| int regNum = startedLocal.getReg(); |
| |
| startedLocal = filterSpec(startedLocal); |
| aboutToProcess(address, regNum); |
| |
| RegisterSpec existingLocal = regs.get(regNum); |
| |
| if (startedLocal.equalsUsingSimpleType(existingLocal)) { |
| // Silently ignore a redundant start. |
| return; |
| } |
| |
| RegisterSpec movedLocal = regs.findMatchingLocal(startedLocal); |
| if (movedLocal != null) { |
| /* |
| * The same variable was moved from one register to another. |
| * So add an end for its old location. |
| */ |
| addOrUpdateEnd(address, Disposition.END_MOVED, movedLocal); |
| } |
| |
| int endAt = endIndices[regNum]; |
| |
| if (existingLocal != null) { |
| /* |
| * There is an existing (but non-matching) local. |
| * Add an explicit end for it. |
| */ |
| add(address, Disposition.END_REPLACED, existingLocal); |
| } else if (endAt >= 0) { |
| /* |
| * Look for an end local for the same register at the |
| * same address. If found, then update it or delete |
| * it, depending on whether or not it represents the |
| * same variable as the one being started. |
| */ |
| Entry endEntry = result.get(endAt); |
| if (endEntry.getAddress() == address) { |
| if (endEntry.matches(startedLocal)) { |
| /* |
| * There was already an end local for the same |
| * variable at the same address. This turns |
| * out to be superfluous, as we are starting |
| * up the exact same local. This situation can |
| * happen when a single local variable got |
| * somehow "split up" during intermediate |
| * processing. In any case, rather than represent |
| * the end-then-start, just remove the old end. |
| */ |
| result.set(endAt, null); |
| nullResultCount++; |
| regs.put(startedLocal); |
| endIndices[regNum] = -1; |
| return; |
| } else { |
| /* |
| * There was a different variable ended at the |
| * same address. Update it to indicate that |
| * it was ended due to a replacement (rather than |
| * ending for no particular reason). |
| */ |
| endEntry = endEntry.withDisposition( |
| Disposition.END_REPLACED); |
| result.set(endAt, endEntry); |
| } |
| } |
| } |
| |
| /* |
| * The code above didn't find and remove an unnecessary |
| * local end, so we now have to add one or more entries to |
| * the output to capture the transition. |
| */ |
| |
| /* |
| * If the local just below (in the register set at reg-1) |
| * is of category-2, then it is ended by this new start. |
| */ |
| if (regNum > 0) { |
| RegisterSpec justBelow = regs.get(regNum - 1); |
| if ((justBelow != null) && justBelow.isCategory2()) { |
| addOrUpdateEnd(address, |
| Disposition.END_CLOBBERED_BY_NEXT, |
| justBelow); |
| } |
| } |
| |
| /* |
| * Similarly, if this local is category-2, then the local |
| * just above (if any) is ended by the start now being |
| * emitted. |
| */ |
| if (startedLocal.isCategory2()) { |
| RegisterSpec justAbove = regs.get(regNum + 1); |
| if (justAbove != null) { |
| addOrUpdateEnd(address, |
| Disposition.END_CLOBBERED_BY_PREV, |
| justAbove); |
| } |
| } |
| |
| /* |
| * TODO: Add an end for the same local in a different reg, |
| * if any (that is, if the local migrates from vX to vY, |
| * we should note that as a local end in vX). |
| */ |
| |
| add(address, Disposition.START, startedLocal); |
| } |
| |
| /** |
| * Ends a local at the given address, using the disposition |
| * {@code END_SIMPLY}. |
| * |
| * @param address {@code >= 0;} the address |
| * @param endedLocal {@code non-null;} spec representing the |
| * local being ended |
| */ |
| public void endLocal(int address, RegisterSpec endedLocal) { |
| endLocal(address, endedLocal, Disposition.END_SIMPLY); |
| } |
| |
| /** |
| * Ends a local at the given address. |
| * |
| * @param address {@code >= 0;} the address |
| * @param endedLocal {@code non-null;} spec representing the |
| * local being ended |
| * @param disposition reason for the end |
| */ |
| public void endLocal(int address, RegisterSpec endedLocal, |
| Disposition disposition) { |
| if (DEBUG) { |
| System.err.printf("%04x end %s\n", address, endedLocal); |
| } |
| |
| int regNum = endedLocal.getReg(); |
| |
| endedLocal = filterSpec(endedLocal); |
| aboutToProcess(address, regNum); |
| |
| int endAt = endIndices[regNum]; |
| |
| if (endAt >= 0) { |
| /* |
| * The local in the given register is already ended. |
| * Silently return without adding anything to the result. |
| */ |
| return; |
| } |
| |
| // Check for start and end at the same address. |
| if (checkForEmptyRange(address, endedLocal)) { |
| return; |
| } |
| |
| add(address, disposition, endedLocal); |
| } |
| |
| /** |
| * Helper for {@link #endLocal}, which handles the cases where |
| * and end local is issued at the same address as a start local |
| * for the same register. If this case is found, then this |
| * method will remove the start (as the local was never actually |
| * active), update the {@link #endIndices} to be accurate, and |
| * if needed update the newly-active end to reflect an altered |
| * disposition. |
| * |
| * @param address {@code >= 0;} the address |
| * @param endedLocal {@code non-null;} spec representing the |
| * local being ended |
| * @return {@code true} iff this method found the case in question |
| * and adjusted things accordingly |
| */ |
| private boolean checkForEmptyRange(int address, |
| RegisterSpec endedLocal) { |
| int at = result.size() - 1; |
| Entry entry; |
| |
| // Look for a previous entry at the same address. |
| for (/*at*/; at >= 0; at--) { |
| entry = result.get(at); |
| |
| if (entry == null) { |
| continue; |
| } |
| |
| if (entry.getAddress() != address) { |
| // We didn't find any match at the same address. |
| return false; |
| } |
| |
| if (entry.matches(endedLocal)) { |
| break; |
| } |
| } |
| |
| /* |
| * In fact, we found that the endedLocal had started at the |
| * same address, so do all the requisite cleanup. |
| */ |
| |
| regs.remove(endedLocal); |
| result.set(at, null); |
| nullResultCount++; |
| |
| int regNum = endedLocal.getReg(); |
| boolean found = false; |
| entry = null; |
| |
| // Now look back further to update where the register ended. |
| for (at--; at >= 0; at--) { |
| entry = result.get(at); |
| |
| if (entry == null) { |
| continue; |
| } |
| |
| if (entry.getRegisterSpec().getReg() == regNum) { |
| found = true; |
| break; |
| } |
| } |
| |
| if (found) { |
| // We found an end for the same register. |
| endIndices[regNum] = at; |
| |
| if (entry.getAddress() == address) { |
| /* |
| * It's still the same address, so update the |
| * disposition. |
| */ |
| result.set(at, |
| entry.withDisposition(Disposition.END_SIMPLY)); |
| } |
| } |
| |
| return true; |
| } |
| |
| /** |
| * Converts a given spec into the form acceptable for use in a |
| * local list. This, in particular, transforms the "known |
| * null" type into simply {@code Object}. This method needs to |
| * be called for any spec that is on its way into a locals |
| * list. |
| * |
| * <p>This isn't necessarily the cleanest way to achieve the |
| * goal of not representing known nulls in a locals list, but |
| * it gets the job done.</p> |
| * |
| * @param orig {@code null-ok;} the original spec |
| * @return {@code null-ok;} an appropriately modified spec, or the |
| * original if nothing needs to be done |
| */ |
| private static RegisterSpec filterSpec(RegisterSpec orig) { |
| if ((orig != null) && (orig.getType() == Type.KNOWN_NULL)) { |
| return orig.withType(Type.OBJECT); |
| } |
| |
| return orig; |
| } |
| |
| /** |
| * Adds an entry to the result, updating the adjunct tables |
| * accordingly. |
| * |
| * @param address {@code >= 0;} the address |
| * @param disposition {@code non-null;} the disposition |
| * @param spec {@code non-null;} spec representing the local |
| */ |
| private void add(int address, Disposition disposition, |
| RegisterSpec spec) { |
| int regNum = spec.getReg(); |
| |
| result.add(new Entry(address, disposition, spec)); |
| |
| if (disposition == Disposition.START) { |
| regs.put(spec); |
| endIndices[regNum] = -1; |
| } else { |
| regs.remove(spec); |
| endIndices[regNum] = result.size() - 1; |
| } |
| } |
| |
| /** |
| * Adds or updates an end local (changing its disposition). If |
| * this would cause an empty range for a local, this instead |
| * removes the local entirely. |
| * |
| * @param address {@code >= 0;} the address |
| * @param disposition {@code non-null;} the disposition |
| * @param spec {@code non-null;} spec representing the local |
| */ |
| private void addOrUpdateEnd(int address, Disposition disposition, |
| RegisterSpec spec) { |
| if (disposition == Disposition.START) { |
| throw new RuntimeException("shouldn't happen"); |
| } |
| |
| int regNum = spec.getReg(); |
| int endAt = endIndices[regNum]; |
| |
| if (endAt >= 0) { |
| // There is a previous end. |
| Entry endEntry = result.get(endAt); |
| if ((endEntry.getAddress() == address) && |
| endEntry.getRegisterSpec().equals(spec)) { |
| /* |
| * The end is for the right address and variable, so |
| * update it. |
| */ |
| result.set(endAt, endEntry.withDisposition(disposition)); |
| regs.remove(spec); // TODO: Is this line superfluous? |
| return; |
| } |
| } |
| |
| endLocal(address, spec, disposition); |
| } |
| |
| /** |
| * Finishes processing altogether and gets the result. |
| * |
| * @return {@code non-null;} the result list |
| */ |
| public LocalList finish() { |
| aboutToProcess(Integer.MAX_VALUE, 0); |
| |
| int resultSz = result.size(); |
| int finalSz = resultSz - nullResultCount; |
| |
| if (finalSz == 0) { |
| return EMPTY; |
| } |
| |
| /* |
| * Collect an array of only the non-null entries, and then |
| * sort it to get a consistent order for everything: Local |
| * ends and starts for a given address could come in any |
| * order, but we want ends before starts as well as |
| * registers in order (within ends or starts). |
| */ |
| |
| Entry[] resultArr = new Entry[finalSz]; |
| |
| if (resultSz == finalSz) { |
| result.toArray(resultArr); |
| } else { |
| int at = 0; |
| for (Entry e : result) { |
| if (e != null) { |
| resultArr[at++] = e; |
| } |
| } |
| } |
| |
| Arrays.sort(resultArr); |
| |
| LocalList resultList = new LocalList(finalSz); |
| |
| for (int i = 0; i < finalSz; i++) { |
| resultList.set(i, resultArr[i]); |
| } |
| |
| resultList.setImmutable(); |
| return resultList; |
| } |
| } |
| } |
