1 /* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.dx.dex.code; 18 19 import com.android.dx.rop.code.RegisterSpec; 20 import com.android.dx.rop.code.RegisterSpecSet; 21 import com.android.dx.rop.cst.CstType; 22 import com.android.dx.rop.cst.CstString; 23 import com.android.dx.rop.type.Type; 24 import com.android.dx.util.FixedSizeList; 25 26 import java.io.PrintStream; 27 import java.util.ArrayList; 28 import java.util.Arrays; 29 30 /** 31 * List of local variables. Each local variable entry indicates a 32 * range of code which it is valid for, a register number, a name, 33 * and a type. 34 */ 35 public final class LocalList extends FixedSizeList { 36 /** {@code non-null;} empty instance */ 37 public static final LocalList EMPTY = new LocalList(0); 38 39 /** whether to run the self-check code */ 40 private static final boolean DEBUG = false; 41 42 /** 43 * Constructs an instance. All indices initially contain {@code null}. 44 * 45 * @param size {@code >= 0;} the size of the list 46 */ LocalList(int size)47 public LocalList(int size) { 48 super(size); 49 } 50 51 /** 52 * Gets the element at the given index. It is an error to call 53 * this with the index for an element which was never set; if you 54 * do that, this will throw {@code NullPointerException}. 55 * 56 * @param n {@code >= 0, < size();} which index 57 * @return {@code non-null;} element at that index 58 */ get(int n)59 public Entry get(int n) { 60 return (Entry) get0(n); 61 } 62 63 /** 64 * Sets the entry at the given index. 65 * 66 * @param n {@code >= 0, < size();} which index 67 * @param entry {@code non-null;} the entry to set at {@code n} 68 */ set(int n, Entry entry)69 public void set(int n, Entry entry) { 70 set0(n, entry); 71 } 72 73 /** 74 * Does a human-friendly dump of this instance. 75 * 76 * @param out {@code non-null;} where to dump 77 * @param prefix {@code non-null;} prefix to attach to each line of output 78 */ debugPrint(PrintStream out, String prefix)79 public void debugPrint(PrintStream out, String prefix) { 80 int sz = size(); 81 82 for (int i = 0; i < sz; i++) { 83 out.print(prefix); 84 out.println(get(i)); 85 } 86 } 87 88 /** 89 * Disposition of a local entry. 90 */ 91 public static enum Disposition { 92 /** local started (introduced) */ 93 START, 94 95 /** local ended without being replaced */ 96 END_SIMPLY, 97 98 /** local ended because it was directly replaced */ 99 END_REPLACED, 100 101 /** local ended because it was moved to a different register */ 102 END_MOVED, 103 104 /** 105 * local ended because the previous local clobbered this one 106 * (because it is category-2) 107 */ 108 END_CLOBBERED_BY_PREV, 109 110 /** 111 * local ended because the next local clobbered this one 112 * (because this one is a category-2) 113 */ 114 END_CLOBBERED_BY_NEXT; 115 } 116 117 /** 118 * Entry in a local list. 119 */ 120 public static class Entry implements Comparable<Entry> { 121 /** {@code >= 0;} address */ 122 private final int address; 123 124 /** {@code non-null;} disposition of the local */ 125 private final Disposition disposition; 126 127 /** {@code non-null;} register spec representing the variable */ 128 private final RegisterSpec spec; 129 130 /** {@code non-null;} variable type (derived from {@code spec}) */ 131 private final CstType type; 132 133 /** 134 * Constructs an instance. 135 * 136 * @param address {@code >= 0;} address 137 * @param disposition {@code non-null;} disposition of the local 138 * @param spec {@code non-null;} register spec representing 139 * the variable 140 */ Entry(int address, Disposition disposition, RegisterSpec spec)141 public Entry(int address, Disposition disposition, RegisterSpec spec) { 142 if (address < 0) { 143 throw new IllegalArgumentException("address < 0"); 144 } 145 146 if (disposition == null) { 147 throw new NullPointerException("disposition == null"); 148 } 149 150 try { 151 if (spec.getLocalItem() == null) { 152 throw new NullPointerException( 153 "spec.getLocalItem() == null"); 154 } 155 } catch (NullPointerException ex) { 156 // Elucidate the exception. 157 throw new NullPointerException("spec == null"); 158 } 159 160 this.address = address; 161 this.disposition = disposition; 162 this.spec = spec; 163 this.type = CstType.intern(spec.getType()); 164 } 165 166 /** {@inheritDoc} */ toString()167 public String toString() { 168 return Integer.toHexString(address) + " " + disposition + " " + 169 spec; 170 } 171 172 /** {@inheritDoc} */ equals(Object other)173 public boolean equals(Object other) { 174 if (!(other instanceof Entry)) { 175 return false; 176 } 177 178 return (compareTo((Entry) other) == 0); 179 } 180 181 /** 182 * Compares by (in priority order) address, end then start 183 * disposition (variants of end are all consistered 184 * equivalent), and spec. 185 * 186 * @param other {@code non-null;} entry to compare to 187 * @return {@code -1..1;} standard result of comparison 188 */ compareTo(Entry other)189 public int compareTo(Entry other) { 190 if (address < other.address) { 191 return -1; 192 } else if (address > other.address) { 193 return 1; 194 } 195 196 boolean thisIsStart = isStart(); 197 boolean otherIsStart = other.isStart(); 198 199 if (thisIsStart != otherIsStart) { 200 return thisIsStart ? 1 : -1; 201 } 202 203 return spec.compareTo(other.spec); 204 } 205 206 /** 207 * Gets the address. 208 * 209 * @return {@code >= 0;} the address 210 */ getAddress()211 public int getAddress() { 212 return address; 213 } 214 215 /** 216 * Gets the disposition. 217 * 218 * @return {@code non-null;} the disposition 219 */ getDisposition()220 public Disposition getDisposition() { 221 return disposition; 222 } 223 224 /** 225 * Gets whether this is a local start. This is just shorthand for 226 * {@code getDisposition() == Disposition.START}. 227 * 228 * @return {@code true} iff this is a start 229 */ isStart()230 public boolean isStart() { 231 return disposition == Disposition.START; 232 } 233 234 /** 235 * Gets the variable name. 236 * 237 * @return {@code null-ok;} the variable name 238 */ getName()239 public CstString getName() { 240 return spec.getLocalItem().getName(); 241 } 242 243 /** 244 * Gets the variable signature. 245 * 246 * @return {@code null-ok;} the variable signature 247 */ getSignature()248 public CstString getSignature() { 249 return spec.getLocalItem().getSignature(); 250 } 251 252 /** 253 * Gets the variable's type. 254 * 255 * @return {@code non-null;} the type 256 */ getType()257 public CstType getType() { 258 return type; 259 } 260 261 /** 262 * Gets the number of the register holding the variable. 263 * 264 * @return {@code >= 0;} the number of the register holding 265 * the variable 266 */ getRegister()267 public int getRegister() { 268 return spec.getReg(); 269 } 270 271 /** 272 * Gets the RegisterSpec of the register holding the variable. 273 * 274 * @return {@code non-null;} RegisterSpec of the holding register. 275 */ getRegisterSpec()276 public RegisterSpec getRegisterSpec() { 277 return spec; 278 } 279 280 /** 281 * Returns whether or not this instance matches the given spec. 282 * 283 * @param otherSpec {@code non-null;} the spec in question 284 * @return {@code true} iff this instance matches 285 * {@code spec} 286 */ matches(RegisterSpec otherSpec)287 public boolean matches(RegisterSpec otherSpec) { 288 return spec.equalsUsingSimpleType(otherSpec); 289 } 290 291 /** 292 * Returns whether or not this instance matches the spec in 293 * the given instance. 294 * 295 * @param other {@code non-null;} another entry 296 * @return {@code true} iff this instance's spec matches 297 * {@code other} 298 */ matches(Entry other)299 public boolean matches(Entry other) { 300 return matches(other.spec); 301 } 302 303 /** 304 * Returns an instance just like this one but with the disposition 305 * set as given. 306 * 307 * @param disposition {@code non-null;} the new disposition 308 * @return {@code non-null;} an appropriately-constructed instance 309 */ withDisposition(Disposition disposition)310 public Entry withDisposition(Disposition disposition) { 311 if (disposition == this.disposition) { 312 return this; 313 } 314 315 return new Entry(address, disposition, spec); 316 } 317 } 318 319 /** 320 * Constructs an instance for the given method, based on the given 321 * block order and intermediate local information. 322 * 323 * @param insns {@code non-null;} instructions to convert 324 * @return {@code non-null;} the constructed list 325 */ make(DalvInsnList insns)326 public static LocalList make(DalvInsnList insns) { 327 int sz = insns.size(); 328 329 /* 330 * Go through the insn list, looking for all the local 331 * variable pseudoinstructions, splitting out LocalSnapshots 332 * into separate per-variable starts, adding explicit ends 333 * wherever a variable is replaced or moved, and collecting 334 * these and all the other local variable "activity" 335 * together into an output list (without the other insns). 336 * 337 * Note: As of this writing, this method won't be handed any 338 * insn lists that contain local ends, but I (danfuzz) expect 339 * that to change at some point, when we start feeding that 340 * info explicitly into the rop layer rather than only trying 341 * to infer it. So, given that expectation, this code is 342 * written to deal with them. 343 */ 344 345 MakeState state = new MakeState(sz); 346 347 for (int i = 0; i < sz; i++) { 348 DalvInsn insn = insns.get(i); 349 350 if (insn instanceof LocalSnapshot) { 351 RegisterSpecSet snapshot = 352 ((LocalSnapshot) insn).getLocals(); 353 state.snapshot(insn.getAddress(), snapshot); 354 } else if (insn instanceof LocalStart) { 355 RegisterSpec local = ((LocalStart) insn).getLocal(); 356 state.startLocal(insn.getAddress(), local); 357 } else if (insn instanceof LocalEnd) { 358 RegisterSpec local = ((LocalEnd) insn).getLocal(); 359 state.endLocal(insn.getAddress(), local); 360 } 361 } 362 363 LocalList result = state.finish(); 364 365 if (DEBUG) { 366 debugVerify(result); 367 } 368 369 return result; 370 } 371 372 /** 373 * Debugging helper that verifies the constraint that a list doesn't 374 * contain any redundant local starts and that local ends that are 375 * due to replacements are properly annotated. 376 */ debugVerify(LocalList locals)377 private static void debugVerify(LocalList locals) { 378 try { 379 debugVerify0(locals); 380 } catch (RuntimeException ex) { 381 int sz = locals.size(); 382 for (int i = 0; i < sz; i++) { 383 System.err.println(locals.get(i)); 384 } 385 throw ex; 386 } 387 388 } 389 390 /** 391 * Helper for {@link #debugVerify} which does most of the work. 392 */ debugVerify0(LocalList locals)393 private static void debugVerify0(LocalList locals) { 394 int sz = locals.size(); 395 Entry[] active = new Entry[65536]; 396 397 for (int i = 0; i < sz; i++) { 398 Entry e = locals.get(i); 399 int reg = e.getRegister(); 400 401 if (e.isStart()) { 402 Entry already = active[reg]; 403 404 if ((already != null) && e.matches(already)) { 405 throw new RuntimeException("redundant start at " + 406 Integer.toHexString(e.getAddress()) + ": got " + 407 e + "; had " + already); 408 } 409 410 active[reg] = e; 411 } else { 412 if (active[reg] == null) { 413 throw new RuntimeException("redundant end at " + 414 Integer.toHexString(e.getAddress())); 415 } 416 417 int addr = e.getAddress(); 418 boolean foundStart = false; 419 420 for (int j = i + 1; j < sz; j++) { 421 Entry test = locals.get(j); 422 if (test.getAddress() != addr) { 423 break; 424 } 425 if (test.getRegisterSpec().getReg() == reg) { 426 if (test.isStart()) { 427 if (e.getDisposition() 428 != Disposition.END_REPLACED) { 429 throw new RuntimeException( 430 "improperly marked end at " + 431 Integer.toHexString(addr)); 432 } 433 foundStart = true; 434 } else { 435 throw new RuntimeException( 436 "redundant end at " + 437 Integer.toHexString(addr)); 438 } 439 } 440 } 441 442 if (!foundStart && 443 (e.getDisposition() == Disposition.END_REPLACED)) { 444 throw new RuntimeException( 445 "improper end replacement claim at " + 446 Integer.toHexString(addr)); 447 } 448 449 active[reg] = null; 450 } 451 } 452 } 453 454 /** 455 * Intermediate state when constructing a local list. 456 */ 457 public static class MakeState { 458 /** {@code non-null;} result being collected */ 459 private final ArrayList<Entry> result; 460 461 /** 462 * {@code >= 0;} running count of nulled result entries, to help with 463 * sizing the final list 464 */ 465 private int nullResultCount; 466 467 /** {@code null-ok;} current register mappings */ 468 private RegisterSpecSet regs; 469 470 /** {@code null-ok;} result indices where local ends are stored */ 471 private int[] endIndices; 472 473 /** {@code >= 0;} last address seen */ 474 private int lastAddress; 475 476 /** 477 * Constructs an instance. 478 */ MakeState(int initialSize)479 public MakeState(int initialSize) { 480 result = new ArrayList<Entry>(initialSize); 481 nullResultCount = 0; 482 regs = null; 483 endIndices = null; 484 lastAddress = 0; 485 } 486 487 /** 488 * Checks the address and other vitals as a prerequisite to 489 * further processing. 490 * 491 * @param address {@code >= 0;} address about to be processed 492 * @param reg {@code >= 0;} register number about to be processed 493 */ aboutToProcess(int address, int reg)494 private void aboutToProcess(int address, int reg) { 495 boolean first = (endIndices == null); 496 497 if ((address == lastAddress) && !first) { 498 return; 499 } 500 501 if (address < lastAddress) { 502 throw new RuntimeException("shouldn't happen"); 503 } 504 505 if (first || (reg >= endIndices.length)) { 506 /* 507 * This is the first allocation of the state set and 508 * index array, or we need to grow. (The latter doesn't 509 * happen much; in fact, we have only ever observed 510 * it happening in test cases, never in "real" code.) 511 */ 512 int newSz = reg + 1; 513 RegisterSpecSet newRegs = new RegisterSpecSet(newSz); 514 int[] newEnds = new int[newSz]; 515 Arrays.fill(newEnds, -1); 516 517 if (!first) { 518 newRegs.putAll(regs); 519 System.arraycopy(endIndices, 0, newEnds, 0, 520 endIndices.length); 521 } 522 523 regs = newRegs; 524 endIndices = newEnds; 525 } 526 } 527 528 /** 529 * Sets the local state at the given address to the given snapshot. 530 * The first call on this instance must be to this method, so that 531 * the register state can be properly sized. 532 * 533 * @param address {@code >= 0;} the address 534 * @param specs {@code non-null;} spec set representing the locals 535 */ snapshot(int address, RegisterSpecSet specs)536 public void snapshot(int address, RegisterSpecSet specs) { 537 if (DEBUG) { 538 System.err.printf("%04x snapshot %s\n", address, specs); 539 } 540 541 int sz = specs.getMaxSize(); 542 aboutToProcess(address, sz - 1); 543 544 for (int i = 0; i < sz; i++) { 545 RegisterSpec oldSpec = regs.get(i); 546 RegisterSpec newSpec = filterSpec(specs.get(i)); 547 548 if (oldSpec == null) { 549 if (newSpec != null) { 550 startLocal(address, newSpec); 551 } 552 } else if (newSpec == null) { 553 endLocal(address, oldSpec); 554 } else if (! newSpec.equalsUsingSimpleType(oldSpec)) { 555 endLocal(address, oldSpec); 556 startLocal(address, newSpec); 557 } 558 } 559 560 if (DEBUG) { 561 System.err.printf("%04x snapshot done\n", address); 562 } 563 } 564 565 /** 566 * Starts a local at the given address. 567 * 568 * @param address {@code >= 0;} the address 569 * @param startedLocal {@code non-null;} spec representing the 570 * started local 571 */ startLocal(int address, RegisterSpec startedLocal)572 public void startLocal(int address, RegisterSpec startedLocal) { 573 if (DEBUG) { 574 System.err.printf("%04x start %s\n", address, startedLocal); 575 } 576 577 int regNum = startedLocal.getReg(); 578 579 startedLocal = filterSpec(startedLocal); 580 aboutToProcess(address, regNum); 581 582 RegisterSpec existingLocal = regs.get(regNum); 583 584 if (startedLocal.equalsUsingSimpleType(existingLocal)) { 585 // Silently ignore a redundant start. 586 return; 587 } 588 589 RegisterSpec movedLocal = regs.findMatchingLocal(startedLocal); 590 if (movedLocal != null) { 591 /* 592 * The same variable was moved from one register to another. 593 * So add an end for its old location. 594 */ 595 addOrUpdateEnd(address, Disposition.END_MOVED, movedLocal); 596 } 597 598 int endAt = endIndices[regNum]; 599 600 if (existingLocal != null) { 601 /* 602 * There is an existing (but non-matching) local. 603 * Add an explicit end for it. 604 */ 605 add(address, Disposition.END_REPLACED, existingLocal); 606 } else if (endAt >= 0) { 607 /* 608 * Look for an end local for the same register at the 609 * same address. If found, then update it or delete 610 * it, depending on whether or not it represents the 611 * same variable as the one being started. 612 */ 613 Entry endEntry = result.get(endAt); 614 if (endEntry.getAddress() == address) { 615 if (endEntry.matches(startedLocal)) { 616 /* 617 * There was already an end local for the same 618 * variable at the same address. This turns 619 * out to be superfluous, as we are starting 620 * up the exact same local. This situation can 621 * happen when a single local variable got 622 * somehow "split up" during intermediate 623 * processing. In any case, rather than represent 624 * the end-then-start, just remove the old end. 625 */ 626 result.set(endAt, null); 627 nullResultCount++; 628 regs.put(startedLocal); 629 endIndices[regNum] = -1; 630 return; 631 } else { 632 /* 633 * There was a different variable ended at the 634 * same address. Update it to indicate that 635 * it was ended due to a replacement (rather than 636 * ending for no particular reason). 637 */ 638 endEntry = endEntry.withDisposition( 639 Disposition.END_REPLACED); 640 result.set(endAt, endEntry); 641 } 642 } 643 } 644 645 /* 646 * The code above didn't find and remove an unnecessary 647 * local end, so we now have to add one or more entries to 648 * the output to capture the transition. 649 */ 650 651 /* 652 * If the local just below (in the register set at reg-1) 653 * is of category-2, then it is ended by this new start. 654 */ 655 if (regNum > 0) { 656 RegisterSpec justBelow = regs.get(regNum - 1); 657 if ((justBelow != null) && justBelow.isCategory2()) { 658 addOrUpdateEnd(address, 659 Disposition.END_CLOBBERED_BY_NEXT, 660 justBelow); 661 } 662 } 663 664 /* 665 * Similarly, if this local is category-2, then the local 666 * just above (if any) is ended by the start now being 667 * emitted. 668 */ 669 if (startedLocal.isCategory2()) { 670 RegisterSpec justAbove = regs.get(regNum + 1); 671 if (justAbove != null) { 672 addOrUpdateEnd(address, 673 Disposition.END_CLOBBERED_BY_PREV, 674 justAbove); 675 } 676 } 677 678 /* 679 * TODO: Add an end for the same local in a different reg, 680 * if any (that is, if the local migrates from vX to vY, 681 * we should note that as a local end in vX). 682 */ 683 684 add(address, Disposition.START, startedLocal); 685 } 686 687 /** 688 * Ends a local at the given address, using the disposition 689 * {@code END_SIMPLY}. 690 * 691 * @param address {@code >= 0;} the address 692 * @param endedLocal {@code non-null;} spec representing the 693 * local being ended 694 */ endLocal(int address, RegisterSpec endedLocal)695 public void endLocal(int address, RegisterSpec endedLocal) { 696 endLocal(address, endedLocal, Disposition.END_SIMPLY); 697 } 698 699 /** 700 * Ends a local at the given address. 701 * 702 * @param address {@code >= 0;} the address 703 * @param endedLocal {@code non-null;} spec representing the 704 * local being ended 705 * @param disposition reason for the end 706 */ endLocal(int address, RegisterSpec endedLocal, Disposition disposition)707 public void endLocal(int address, RegisterSpec endedLocal, 708 Disposition disposition) { 709 if (DEBUG) { 710 System.err.printf("%04x end %s\n", address, endedLocal); 711 } 712 713 int regNum = endedLocal.getReg(); 714 715 endedLocal = filterSpec(endedLocal); 716 aboutToProcess(address, regNum); 717 718 int endAt = endIndices[regNum]; 719 720 if (endAt >= 0) { 721 /* 722 * The local in the given register is already ended. 723 * Silently return without adding anything to the result. 724 */ 725 return; 726 } 727 728 // Check for start and end at the same address. 729 if (checkForEmptyRange(address, endedLocal)) { 730 return; 731 } 732 733 add(address, disposition, endedLocal); 734 } 735 736 /** 737 * Helper for {@link #endLocal}, which handles the cases where 738 * and end local is issued at the same address as a start local 739 * for the same register. If this case is found, then this 740 * method will remove the start (as the local was never actually 741 * active), update the {@link #endIndices} to be accurate, and 742 * if needed update the newly-active end to reflect an altered 743 * disposition. 744 * 745 * @param address {@code >= 0;} the address 746 * @param endedLocal {@code non-null;} spec representing the 747 * local being ended 748 * @return {@code true} iff this method found the case in question 749 * and adjusted things accordingly 750 */ checkForEmptyRange(int address, RegisterSpec endedLocal)751 private boolean checkForEmptyRange(int address, 752 RegisterSpec endedLocal) { 753 int at = result.size() - 1; 754 Entry entry; 755 756 // Look for a previous entry at the same address. 757 for (/*at*/; at >= 0; at--) { 758 entry = result.get(at); 759 760 if (entry == null) { 761 continue; 762 } 763 764 if (entry.getAddress() != address) { 765 // We didn't find any match at the same address. 766 return false; 767 } 768 769 if (entry.matches(endedLocal)) { 770 break; 771 } 772 } 773 774 /* 775 * In fact, we found that the endedLocal had started at the 776 * same address, so do all the requisite cleanup. 777 */ 778 779 regs.remove(endedLocal); 780 result.set(at, null); 781 nullResultCount++; 782 783 int regNum = endedLocal.getReg(); 784 boolean found = false; 785 entry = null; 786 787 // Now look back further to update where the register ended. 788 for (at--; at >= 0; at--) { 789 entry = result.get(at); 790 791 if (entry == null) { 792 continue; 793 } 794 795 if (entry.getRegisterSpec().getReg() == regNum) { 796 found = true; 797 break; 798 } 799 } 800 801 if (found) { 802 // We found an end for the same register. 803 endIndices[regNum] = at; 804 805 if (entry.getAddress() == address) { 806 /* 807 * It's still the same address, so update the 808 * disposition. 809 */ 810 result.set(at, 811 entry.withDisposition(Disposition.END_SIMPLY)); 812 } 813 } 814 815 return true; 816 } 817 818 /** 819 * Converts a given spec into the form acceptable for use in a 820 * local list. This, in particular, transforms the "known 821 * null" type into simply {@code Object}. This method needs to 822 * be called for any spec that is on its way into a locals 823 * list. 824 * 825 * <p>This isn't necessarily the cleanest way to achieve the 826 * goal of not representing known nulls in a locals list, but 827 * it gets the job done.</p> 828 * 829 * @param orig {@code null-ok;} the original spec 830 * @return {@code null-ok;} an appropriately modified spec, or the 831 * original if nothing needs to be done 832 */ filterSpec(RegisterSpec orig)833 private static RegisterSpec filterSpec(RegisterSpec orig) { 834 if ((orig != null) && (orig.getType() == Type.KNOWN_NULL)) { 835 return orig.withType(Type.OBJECT); 836 } 837 838 return orig; 839 } 840 841 /** 842 * Adds an entry to the result, updating the adjunct tables 843 * accordingly. 844 * 845 * @param address {@code >= 0;} the address 846 * @param disposition {@code non-null;} the disposition 847 * @param spec {@code non-null;} spec representing the local 848 */ add(int address, Disposition disposition, RegisterSpec spec)849 private void add(int address, Disposition disposition, 850 RegisterSpec spec) { 851 int regNum = spec.getReg(); 852 853 result.add(new Entry(address, disposition, spec)); 854 855 if (disposition == Disposition.START) { 856 regs.put(spec); 857 endIndices[regNum] = -1; 858 } else { 859 regs.remove(spec); 860 endIndices[regNum] = result.size() - 1; 861 } 862 } 863 864 /** 865 * Adds or updates an end local (changing its disposition). If 866 * this would cause an empty range for a local, this instead 867 * removes the local entirely. 868 * 869 * @param address {@code >= 0;} the address 870 * @param disposition {@code non-null;} the disposition 871 * @param spec {@code non-null;} spec representing the local 872 */ addOrUpdateEnd(int address, Disposition disposition, RegisterSpec spec)873 private void addOrUpdateEnd(int address, Disposition disposition, 874 RegisterSpec spec) { 875 if (disposition == Disposition.START) { 876 throw new RuntimeException("shouldn't happen"); 877 } 878 879 int regNum = spec.getReg(); 880 int endAt = endIndices[regNum]; 881 882 if (endAt >= 0) { 883 // There is a previous end. 884 Entry endEntry = result.get(endAt); 885 if ((endEntry.getAddress() == address) && 886 endEntry.getRegisterSpec().equals(spec)) { 887 /* 888 * The end is for the right address and variable, so 889 * update it. 890 */ 891 result.set(endAt, endEntry.withDisposition(disposition)); 892 regs.remove(spec); // TODO: Is this line superfluous? 893 return; 894 } 895 } 896 897 endLocal(address, spec, disposition); 898 } 899 900 /** 901 * Finishes processing altogether and gets the result. 902 * 903 * @return {@code non-null;} the result list 904 */ finish()905 public LocalList finish() { 906 aboutToProcess(Integer.MAX_VALUE, 0); 907 908 int resultSz = result.size(); 909 int finalSz = resultSz - nullResultCount; 910 911 if (finalSz == 0) { 912 return EMPTY; 913 } 914 915 /* 916 * Collect an array of only the non-null entries, and then 917 * sort it to get a consistent order for everything: Local 918 * ends and starts for a given address could come in any 919 * order, but we want ends before starts as well as 920 * registers in order (within ends or starts). 921 */ 922 923 Entry[] resultArr = new Entry[finalSz]; 924 925 if (resultSz == finalSz) { 926 result.toArray(resultArr); 927 } else { 928 int at = 0; 929 for (Entry e : result) { 930 if (e != null) { 931 resultArr[at++] = e; 932 } 933 } 934 } 935 936 Arrays.sort(resultArr); 937 938 LocalList resultList = new LocalList(finalSz); 939 940 for (int i = 0; i < finalSz; i++) { 941 resultList.set(i, resultArr[i]); 942 } 943 944 resultList.setImmutable(); 945 return resultList; 946 } 947 } 948 } 949