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.dex.DexException; 20 import com.android.dx.dex.DexOptions; 21 import com.android.dx.io.Opcodes; 22 import com.android.dx.rop.code.LocalItem; 23 import com.android.dx.rop.code.RegisterSpec; 24 import com.android.dx.rop.code.RegisterSpecList; 25 import com.android.dx.rop.code.RegisterSpecSet; 26 import com.android.dx.rop.code.SourcePosition; 27 import com.android.dx.rop.cst.Constant; 28 import com.android.dx.rop.cst.CstMemberRef; 29 import com.android.dx.rop.cst.CstString; 30 import com.android.dx.rop.cst.CstType; 31 import com.android.dx.rop.type.Type; 32 import com.android.dx.ssa.BasicRegisterMapper; 33 import java.util.ArrayList; 34 import java.util.BitSet; 35 import java.util.HashSet; 36 37 /** 38 * Processor for instruction lists, which takes a "first cut" of 39 * instruction selection as a basis and produces a "final cut" in the 40 * form of a {@link DalvInsnList} instance. 41 */ 42 public final class OutputFinisher { 43 /** {@code non-null;} options for dex output */ 44 private final DexOptions dexOptions; 45 46 /** 47 * {@code >= 0;} register count for the method, not including any extra 48 * "reserved" registers needed to translate "difficult" instructions 49 */ 50 private final int unreservedRegCount; 51 52 /** {@code non-null;} the list of instructions, per se */ 53 private ArrayList<DalvInsn> insns; 54 55 /** whether any instruction has position info */ 56 private boolean hasAnyPositionInfo; 57 58 /** whether any instruction has local variable info */ 59 private boolean hasAnyLocalInfo; 60 61 /** 62 * {@code >= 0;} the count of reserved registers (low-numbered 63 * registers used when expanding instructions that can't be 64 * represented simply); becomes valid after a call to {@link 65 * #massageInstructions} 66 */ 67 private int reservedCount; 68 69 /** 70 * {@code >= 0;} the count of reserved registers just before parameters in order to align them. 71 */ 72 private int reservedParameterCount; 73 74 /** 75 * Size, in register units, of all the parameters to this method 76 */ 77 private final int paramSize; 78 79 /** 80 * Constructs an instance. It initially contains no instructions. 81 * 82 * @param dexOptions {@code non-null;} options for dex output 83 * @param initialCapacity {@code >= 0;} initial capacity of the 84 * instructions list 85 * @param regCount {@code >= 0;} register count for the method 86 * @param paramSize size, in register units, of all the parameters for this method 87 */ 88 public OutputFinisher(DexOptions dexOptions, int initialCapacity, int regCount, int paramSize) { 89 this.dexOptions = dexOptions; 90 this.unreservedRegCount = regCount; 91 this.insns = new ArrayList<DalvInsn>(initialCapacity); 92 this.reservedCount = -1; 93 this.hasAnyPositionInfo = false; 94 this.hasAnyLocalInfo = false; 95 this.paramSize = paramSize; 96 } 97 98 /** 99 * Returns whether any of the instructions added to this instance 100 * come with position info. 101 * 102 * @return whether any of the instructions added to this instance 103 * come with position info 104 */ 105 public boolean hasAnyPositionInfo() { 106 return hasAnyPositionInfo; 107 } 108 109 /** 110 * Returns whether this instance has any local variable information. 111 * 112 * @return whether this instance has any local variable information 113 */ 114 public boolean hasAnyLocalInfo() { 115 return hasAnyLocalInfo; 116 } 117 118 /** 119 * Helper for {@link #add} which scrutinizes a single 120 * instruction for local variable information. 121 * 122 * @param insn {@code non-null;} instruction to scrutinize 123 * @return {@code true} iff the instruction refers to any 124 * named locals 125 */ 126 private static boolean hasLocalInfo(DalvInsn insn) { 127 if (insn instanceof LocalSnapshot) { 128 RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals(); 129 int size = specs.size(); 130 for (int i = 0; i < size; i++) { 131 if (hasLocalInfo(specs.get(i))) { 132 return true; 133 } 134 } 135 } else if (insn instanceof LocalStart) { 136 RegisterSpec spec = ((LocalStart) insn).getLocal(); 137 if (hasLocalInfo(spec)) { 138 return true; 139 } 140 } 141 142 return false; 143 } 144 145 /** 146 * Helper for {@link #hasAnyLocalInfo} which scrutinizes a single 147 * register spec. 148 * 149 * @param spec {@code non-null;} spec to scrutinize 150 * @return {@code true} iff the spec refers to any 151 * named locals 152 */ 153 private static boolean hasLocalInfo(RegisterSpec spec) { 154 return (spec != null) 155 && (spec.getLocalItem().getName() != null); 156 } 157 158 /** 159 * Returns the set of all constants referred to by instructions added 160 * to this instance. 161 * 162 * @return {@code non-null;} the set of constants 163 */ 164 public HashSet<Constant> getAllConstants() { 165 HashSet<Constant> result = new HashSet<Constant>(20); 166 167 for (DalvInsn insn : insns) { 168 addConstants(result, insn); 169 } 170 171 return result; 172 } 173 174 /** 175 * Helper for {@link #getAllConstants} which adds all the info for 176 * a single instruction. 177 * 178 * @param result {@code non-null;} result set to add to 179 * @param insn {@code non-null;} instruction to scrutinize 180 */ 181 private static void addConstants(HashSet<Constant> result, 182 DalvInsn insn) { 183 if (insn instanceof CstInsn) { 184 Constant cst = ((CstInsn) insn).getConstant(); 185 result.add(cst); 186 } else if (insn instanceof MultiCstInsn) { 187 MultiCstInsn m = (MultiCstInsn) insn; 188 for (int i = 0; i < m.getNumberOfConstants(); i++) { 189 result.add(m.getConstant(i)); 190 } 191 } else if (insn instanceof LocalSnapshot) { 192 RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals(); 193 int size = specs.size(); 194 for (int i = 0; i < size; i++) { 195 addConstants(result, specs.get(i)); 196 } 197 } else if (insn instanceof LocalStart) { 198 RegisterSpec spec = ((LocalStart) insn).getLocal(); 199 addConstants(result, spec); 200 } 201 } 202 203 /** 204 * Helper for {@link #getAllConstants} which adds all the info for 205 * a single {@code RegisterSpec}. 206 * 207 * @param result {@code non-null;} result set to add to 208 * @param spec {@code null-ok;} register spec to add 209 */ 210 private static void addConstants(HashSet<Constant> result, 211 RegisterSpec spec) { 212 if (spec == null) { 213 return; 214 } 215 216 LocalItem local = spec.getLocalItem(); 217 CstString name = local.getName(); 218 CstString signature = local.getSignature(); 219 Type type = spec.getType(); 220 221 if (type != Type.KNOWN_NULL) { 222 result.add(CstType.intern(type)); 223 } else { 224 /* If this a "known null", let's use "Object" because that's going to be the 225 * resulting type in {@link LocalList.MakeState#filterSpec} */ 226 result.add(CstType.intern(Type.OBJECT)); 227 } 228 229 if (name != null) { 230 result.add(name); 231 } 232 233 if (signature != null) { 234 result.add(signature); 235 } 236 } 237 238 /** 239 * Adds an instruction to the output. 240 * 241 * @param insn {@code non-null;} the instruction to add 242 */ 243 public void add(DalvInsn insn) { 244 insns.add(insn); 245 updateInfo(insn); 246 } 247 248 /** 249 * Inserts an instruction in the output at the given offset. 250 * 251 * @param at {@code at >= 0;} what index to insert at 252 * @param insn {@code non-null;} the instruction to insert 253 */ 254 public void insert(int at, DalvInsn insn) { 255 insns.add(at, insn); 256 updateInfo(insn); 257 } 258 259 /** 260 * Helper for {@link #add} and {@link #insert}, 261 * which updates the position and local info flags. 262 * 263 * @param insn {@code non-null;} an instruction that was just introduced 264 */ 265 private void updateInfo(DalvInsn insn) { 266 if (! hasAnyPositionInfo) { 267 SourcePosition pos = insn.getPosition(); 268 if (pos.getLine() >= 0) { 269 hasAnyPositionInfo = true; 270 } 271 } 272 273 if (! hasAnyLocalInfo) { 274 if (hasLocalInfo(insn)) { 275 hasAnyLocalInfo = true; 276 } 277 } 278 } 279 280 /** 281 * Reverses a branch which is buried a given number of instructions 282 * backward in the output. It is illegal to call this unless the 283 * indicated instruction really is a reversible branch. 284 * 285 * @param which how many instructions back to find the branch; 286 * {@code 0} is the most recently added instruction, 287 * {@code 1} is the instruction before that, etc. 288 * @param newTarget {@code non-null;} the new target for the 289 * reversed branch 290 */ 291 public void reverseBranch(int which, CodeAddress newTarget) { 292 int size = insns.size(); 293 int index = size - which - 1; 294 TargetInsn targetInsn; 295 296 try { 297 targetInsn = (TargetInsn) insns.get(index); 298 } catch (IndexOutOfBoundsException ex) { 299 // Translate the exception. 300 throw new IllegalArgumentException("too few instructions"); 301 } catch (ClassCastException ex) { 302 // Translate the exception. 303 throw new IllegalArgumentException("non-reversible instruction"); 304 } 305 306 /* 307 * No need to call this.set(), since the format and other info 308 * are the same. 309 */ 310 insns.set(index, targetInsn.withNewTargetAndReversed(newTarget)); 311 } 312 313 /** 314 * Assigns indices in all instructions that need them, using the 315 * given callback to perform lookups. This should be called before 316 * calling {@link #finishProcessingAndGetList}. 317 * 318 * @param callback {@code non-null;} callback object 319 */ 320 public void assignIndices(DalvCode.AssignIndicesCallback callback) { 321 for (DalvInsn insn : insns) { 322 if (insn instanceof CstInsn) { 323 assignIndices((CstInsn) insn, callback); 324 } else if (insn instanceof MultiCstInsn) { 325 assignIndices((MultiCstInsn) insn, callback); 326 } 327 } 328 } 329 330 /** 331 * Helper for {@link #assignIndices} which does assignment for one 332 * instruction. 333 * 334 * @param insn {@code non-null;} the instruction 335 * @param callback {@code non-null;} the callback 336 */ 337 private static void assignIndices(CstInsn insn, 338 DalvCode.AssignIndicesCallback callback) { 339 Constant cst = insn.getConstant(); 340 int index = callback.getIndex(cst); 341 342 if (index >= 0) { 343 insn.setIndex(index); 344 } 345 346 if (cst instanceof CstMemberRef) { 347 CstMemberRef member = (CstMemberRef) cst; 348 CstType definer = member.getDefiningClass(); 349 index = callback.getIndex(definer); 350 // TODO(oth): what scenarios is this guard valid under? Is it not just an error? 351 if (index >= 0) { 352 insn.setClassIndex(index); 353 } 354 } 355 } 356 357 /** 358 * Helper for {@link #assignIndices} which does assignment for one 359 * instruction. 360 * 361 * @param insn {@code non-null;} the instruction 362 * @param callback {@code non-null;} the callback 363 */ 364 private static void assignIndices(MultiCstInsn insn, DalvCode.AssignIndicesCallback callback) { 365 for (int i = 0; i < insn.getNumberOfConstants(); ++i) { 366 Constant cst = insn.getConstant(i); 367 int index = callback.getIndex(cst); 368 insn.setIndex(i, index); 369 370 if (cst instanceof CstMemberRef) { 371 CstMemberRef member = (CstMemberRef) cst; 372 CstType definer = member.getDefiningClass(); 373 index = callback.getIndex(definer); 374 insn.setClassIndex(index); 375 } 376 } 377 } 378 379 /** 380 * Does final processing on this instance and gets the output as 381 * a {@link DalvInsnList}. Final processing consists of: 382 * 383 * <ul> 384 * <li>optionally renumbering registers (to make room as needed for 385 * expanded instructions)</li> 386 * <li>picking a final opcode for each instruction</li> 387 * <li>rewriting instructions, because of register number, 388 * constant pool index, or branch target size issues</li> 389 * <li>assigning final addresses</li> 390 * </ul> 391 * 392 * <p><b>Note:</b> This method may only be called once per instance 393 * of this class.</p> 394 * 395 * @return {@code non-null;} the output list 396 * @throws UnsupportedOperationException if this method has 397 * already been called 398 */ 399 public DalvInsnList finishProcessingAndGetList() { 400 if (reservedCount >= 0) { 401 throw new UnsupportedOperationException("already processed"); 402 } 403 404 Dop[] opcodes = makeOpcodesArray(); 405 reserveRegisters(opcodes); 406 if (dexOptions.ALIGN_64BIT_REGS_IN_OUTPUT_FINISHER) { 407 align64bits(opcodes); 408 } 409 massageInstructions(opcodes); 410 assignAddressesAndFixBranches(); 411 412 return DalvInsnList.makeImmutable(insns, reservedCount + unreservedRegCount 413 + reservedParameterCount); 414 } 415 416 /** 417 * Helper for {@link #finishProcessingAndGetList}, which extracts 418 * the opcode out of each instruction into a separate array, to be 419 * further manipulated as things progress. 420 * 421 * @return {@code non-null;} the array of opcodes 422 */ 423 private Dop[] makeOpcodesArray() { 424 int size = insns.size(); 425 Dop[] result = new Dop[size]; 426 427 for (int i = 0; i < size; i++) { 428 DalvInsn insn = insns.get(i); 429 result[i] = insn.getOpcode(); 430 } 431 432 return result; 433 } 434 435 /** 436 * Helper for {@link #finishProcessingAndGetList}, which figures 437 * out how many reserved registers are required and then reserving 438 * them. It also updates the given {@code opcodes} array so 439 * as to avoid extra work when constructing the massaged 440 * instruction list. 441 * 442 * @param opcodes {@code non-null;} array of per-instruction 443 * opcode selections 444 * @return true if reservedCount is expanded, false otherwise 445 */ 446 private boolean reserveRegisters(Dop[] opcodes) { 447 boolean reservedCountExpanded = false; 448 int oldReservedCount = (reservedCount < 0) ? 0 : reservedCount; 449 450 /* 451 * Call calculateReservedCount() and then perform register 452 * reservation, repeatedly until no new reservations happen. 453 */ 454 for (;;) { 455 int newReservedCount = calculateReservedCount(opcodes); 456 if (oldReservedCount >= newReservedCount) { 457 break; 458 } 459 460 reservedCountExpanded = true; 461 462 int reservedDifference = newReservedCount - oldReservedCount; 463 int size = insns.size(); 464 465 for (int i = 0; i < size; i++) { 466 /* 467 * CodeAddress instance identity is used to link 468 * TargetInsns to their targets, so it is 469 * inappropriate to make replacements, and they don't 470 * have registers in any case. Hence, the instanceof 471 * test below. 472 */ 473 DalvInsn insn = insns.get(i); 474 if (!(insn instanceof CodeAddress)) { 475 /* 476 * No need to call this.set() since the format and 477 * other info are the same. 478 */ 479 insns.set(i, insn.withRegisterOffset(reservedDifference)); 480 } 481 } 482 483 oldReservedCount = newReservedCount; 484 } 485 486 reservedCount = oldReservedCount; 487 488 return reservedCountExpanded; 489 } 490 491 /** 492 * Helper for {@link #reserveRegisters}, which does one 493 * pass over the instructions, calculating the number of 494 * registers that need to be reserved. It also updates the 495 * {@code opcodes} list to help avoid extra work in future 496 * register reservation passes. 497 * 498 * @param opcodes {@code non-null;} array of per-instruction 499 * opcode selections 500 * @return {@code >= 0;} the count of reserved registers 501 */ 502 private int calculateReservedCount(Dop[] opcodes) { 503 int size = insns.size(); 504 505 /* 506 * Potential new value of reservedCount, which gets updated in the 507 * following loop. It starts out with the existing reservedCount 508 * and gets increased if it turns out that additional registers 509 * need to be reserved. 510 */ 511 int newReservedCount = reservedCount; 512 513 for (int i = 0; i < size; i++) { 514 DalvInsn insn = insns.get(i); 515 Dop originalOpcode = opcodes[i]; 516 Dop newOpcode = findOpcodeForInsn(insn, originalOpcode); 517 518 if (newOpcode == null) { 519 /* 520 * The instruction will need to be expanded, so find the 521 * expanded opcode and reserve registers for it. 522 */ 523 Dop expandedOp = findExpandedOpcodeForInsn(insn); 524 BitSet compatRegs = expandedOp.getFormat().compatibleRegs(insn); 525 int reserve = insn.getMinimumRegisterRequirement(compatRegs); 526 if (reserve > newReservedCount) { 527 newReservedCount = reserve; 528 } 529 } else if (originalOpcode == newOpcode) { 530 continue; 531 } 532 533 opcodes[i] = newOpcode; 534 } 535 536 return newReservedCount; 537 } 538 539 /** 540 * Attempts to fit the given instruction into a specific opcode, 541 * returning the opcode whose format that the instruction fits 542 * into or {@code null} to indicate that the instruction will need 543 * to be expanded. This fitting process starts with the given 544 * opcode as a first "best guess" and then pessimizes from there 545 * if necessary. 546 * 547 * @param insn {@code non-null;} the instruction in question 548 * @param guess {@code null-ok;} the current guess as to the best 549 * opcode; {@code null} means that no simple opcode fits 550 * @return {@code null-ok;} a possibly-different opcode; either a 551 * {@code non-null} good fit or {@code null} to indicate that no 552 * simple opcode fits 553 */ 554 private Dop findOpcodeForInsn(DalvInsn insn, Dop guess) { 555 /* 556 * Note: The initial guess might be null, meaning that an 557 * earlier call to this method already determined that there 558 * was no possible simple opcode fit. 559 */ 560 561 while (guess != null) { 562 if (guess.getFormat().isCompatible(insn)) { 563 /* 564 * Don't break out for const_string to generate jumbo version 565 * when option is enabled. 566 */ 567 if (!dexOptions.forceJumbo || 568 guess.getOpcode() != Opcodes.CONST_STRING) { 569 break; 570 } 571 } 572 573 guess = Dops.getNextOrNull(guess, dexOptions); 574 } 575 576 return guess; 577 } 578 579 /** 580 * Finds the proper opcode for the given instruction, ignoring 581 * register constraints. 582 * 583 * @param insn {@code non-null;} the instruction in question 584 * @return {@code non-null;} the opcode that fits 585 */ 586 private Dop findExpandedOpcodeForInsn(DalvInsn insn) { 587 Dop result = findOpcodeForInsn(insn.getLowRegVersion(), insn.getOpcode()); 588 if (result == null) { 589 throw new DexException("No expanded opcode for " + insn); 590 } 591 return result; 592 } 593 594 /** 595 * Helper for {@link #finishProcessingAndGetList}, which goes 596 * through each instruction in the output, making sure its opcode 597 * can accomodate its arguments. In cases where the opcode is 598 * unable to do so, this replaces the instruction with a larger 599 * instruction with identical semantics that <i>will</i> work. 600 * 601 * <p>This method may also reserve a number of low-numbered 602 * registers, renumbering the instructions' original registers, in 603 * order to have register space available in which to move 604 * very-high registers when expanding instructions into 605 * multi-instruction sequences. This expansion is done when no 606 * simple instruction format can be found for a given instruction that 607 * is able to accomodate that instruction's registers.</p> 608 * 609 * <p>This method ignores issues of branch target size, since 610 * final addresses aren't known at the point that this method is 611 * called.</p> 612 * 613 * @param opcodes {@code non-null;} array of per-instruction 614 * opcode selections 615 */ 616 private void massageInstructions(Dop[] opcodes) { 617 if (reservedCount == 0) { 618 /* 619 * The easy common case: No registers were reserved, so we 620 * merely need to replace any instructions whose format 621 * (and hence whose opcode) changed during the reservation 622 * pass, but all instructions will stay at their original 623 * indices, and the instruction list doesn't grow. 624 */ 625 int size = insns.size(); 626 627 for (int i = 0; i < size; i++) { 628 DalvInsn insn = insns.get(i); 629 Dop originalOpcode = insn.getOpcode(); 630 Dop currentOpcode = opcodes[i]; 631 632 if (originalOpcode != currentOpcode) { 633 insns.set(i, insn.withOpcode(currentOpcode)); 634 } 635 } 636 } else { 637 /* 638 * The difficult uncommon case: Some instructions have to be 639 * expanded to deal with high registers. 640 */ 641 insns = performExpansion(opcodes); 642 } 643 } 644 645 /** 646 * Helper for {@link #massageInstructions}, which constructs a 647 * replacement list, where each {link DalvInsn} instance that 648 * couldn't be represented simply (due to register representation 649 * problems) is expanded into a series of instances that together 650 * perform the proper function. 651 * 652 * @param opcodes {@code non-null;} array of per-instruction 653 * opcode selections 654 * @return {@code non-null;} the replacement list 655 */ 656 private ArrayList<DalvInsn> performExpansion(Dop[] opcodes) { 657 int size = insns.size(); 658 ArrayList<DalvInsn> result = new ArrayList<DalvInsn>(size * 2); 659 660 ArrayList<CodeAddress> closelyBoundAddresses = new ArrayList<CodeAddress>(); 661 662 for (int i = 0; i < size; i++) { 663 DalvInsn insn = insns.get(i); 664 Dop originalOpcode = insn.getOpcode(); 665 Dop currentOpcode = opcodes[i]; 666 DalvInsn prefix; 667 DalvInsn suffix; 668 669 if (currentOpcode != null) { 670 // No expansion is necessary. 671 prefix = null; 672 suffix = null; 673 } else { 674 // Expansion is required. 675 currentOpcode = findExpandedOpcodeForInsn(insn); 676 BitSet compatRegs = 677 currentOpcode.getFormat().compatibleRegs(insn); 678 prefix = insn.expandedPrefix(compatRegs); 679 suffix = insn.expandedSuffix(compatRegs); 680 681 // Expand necessary registers to fit the new format 682 insn = insn.expandedVersion(compatRegs); 683 } 684 685 if (insn instanceof CodeAddress) { 686 // If we have a closely bound address, don't add it yet, 687 // because we need to add it after the prefix for the 688 // instruction it is bound to. 689 if (((CodeAddress) insn).getBindsClosely()) { 690 closelyBoundAddresses.add((CodeAddress)insn); 691 continue; 692 } 693 } 694 695 if (prefix != null) { 696 result.add(prefix); 697 } 698 699 // Add any pending closely bound addresses 700 if (!(insn instanceof ZeroSizeInsn) && closelyBoundAddresses.size() > 0) { 701 for (CodeAddress codeAddress: closelyBoundAddresses) { 702 result.add(codeAddress); 703 } 704 closelyBoundAddresses.clear(); 705 } 706 707 if (currentOpcode != originalOpcode) { 708 insn = insn.withOpcode(currentOpcode); 709 } 710 result.add(insn); 711 712 if (suffix != null) { 713 result.add(suffix); 714 } 715 } 716 717 return result; 718 } 719 720 /** 721 * Helper for {@link #finishProcessingAndGetList}, which assigns 722 * addresses to each instruction, possibly rewriting branches to 723 * fix ones that wouldn't otherwise be able to reach their 724 * targets. 725 */ 726 private void assignAddressesAndFixBranches() { 727 for (;;) { 728 assignAddresses(); 729 if (!fixBranches()) { 730 break; 731 } 732 } 733 } 734 735 /** 736 * Helper for {@link #assignAddressesAndFixBranches}, which 737 * assigns an address to each instruction, in order. 738 */ 739 private void assignAddresses() { 740 int address = 0; 741 int size = insns.size(); 742 743 for (int i = 0; i < size; i++) { 744 DalvInsn insn = insns.get(i); 745 insn.setAddress(address); 746 address += insn.codeSize(); 747 } 748 } 749 750 /** 751 * Helper for {@link #assignAddressesAndFixBranches}, which checks 752 * the branch target size requirement of each branch instruction 753 * to make sure it fits. For instructions that don't fit, this 754 * rewrites them to use a {@code goto} of some sort. In the 755 * case of a conditional branch that doesn't fit, the sense of the 756 * test is reversed in order to branch around a {@code goto} 757 * to the original target. 758 * 759 * @return whether any branches had to be fixed 760 */ 761 private boolean fixBranches() { 762 int size = insns.size(); 763 boolean anyFixed = false; 764 765 for (int i = 0; i < size; i++) { 766 DalvInsn insn = insns.get(i); 767 if (!(insn instanceof TargetInsn)) { 768 // This loop only needs to inspect TargetInsns. 769 continue; 770 } 771 772 Dop opcode = insn.getOpcode(); 773 TargetInsn target = (TargetInsn) insn; 774 775 if (opcode.getFormat().branchFits(target)) { 776 continue; 777 } 778 779 if (opcode.getFamily() == Opcodes.GOTO) { 780 // It is a goto; widen it if possible. 781 opcode = findOpcodeForInsn(insn, opcode); 782 if (opcode == null) { 783 /* 784 * The branch is already maximally large. This should 785 * only be possible if a method somehow manages to have 786 * more than 2^31 code units. 787 */ 788 throw new UnsupportedOperationException("method too long"); 789 } 790 insns.set(i, insn.withOpcode(opcode)); 791 } else { 792 /* 793 * It is a conditional: Reverse its sense, and arrange for 794 * it to branch around an absolute goto to the original 795 * branch target. 796 * 797 * Note: An invariant of the list being processed is 798 * that every TargetInsn is followed by a CodeAddress. 799 * Hence, it is always safe to get the next element 800 * after a TargetInsn and cast it to CodeAddress, as 801 * is happening a few lines down. 802 * 803 * Also note: Size gets incremented by one here, as we 804 * have -- in the net -- added one additional element 805 * to the list, so we increment i to match. The added 806 * and changed elements will be inspected by a repeat 807 * call to this method after this invocation returns. 808 */ 809 CodeAddress newTarget; 810 try { 811 newTarget = (CodeAddress) insns.get(i + 1); 812 } catch (IndexOutOfBoundsException ex) { 813 // The TargetInsn / CodeAddress invariant was violated. 814 throw new IllegalStateException( 815 "unpaired TargetInsn (dangling)"); 816 } catch (ClassCastException ex) { 817 // The TargetInsn / CodeAddress invariant was violated. 818 throw new IllegalStateException("unpaired TargetInsn"); 819 } 820 TargetInsn gotoInsn = 821 new TargetInsn(Dops.GOTO, target.getPosition(), 822 RegisterSpecList.EMPTY, target.getTarget()); 823 insns.set(i, gotoInsn); 824 insns.add(i, target.withNewTargetAndReversed(newTarget)); 825 size++; 826 i++; 827 } 828 829 anyFixed = true; 830 } 831 832 return anyFixed; 833 } 834 835 private void align64bits(Dop[] opcodes) { 836 while (true) { 837 int notAligned64bitRegAccess = 0; 838 int aligned64bitRegAccess = 0; 839 int notAligned64bitParamAccess = 0; 840 int aligned64bitParamAccess = 0; 841 int lastParameter = unreservedRegCount + reservedCount + reservedParameterCount; 842 int firstParameter = lastParameter - paramSize; 843 844 // Collects the number of time that 64-bit registers are accessed aligned or not. 845 for (DalvInsn insn : insns) { 846 RegisterSpecList regs = insn.getRegisters(); 847 for (int usedRegIdx = 0; usedRegIdx < regs.size(); usedRegIdx++) { 848 RegisterSpec reg = regs.get(usedRegIdx); 849 if (reg.isCategory2()) { 850 boolean isParameter = reg.getReg() >= firstParameter; 851 if (reg.isEvenRegister()) { 852 if (isParameter) { 853 aligned64bitParamAccess++; 854 } else { 855 aligned64bitRegAccess++; 856 } 857 } else { 858 if (isParameter) { 859 notAligned64bitParamAccess++; 860 } else { 861 notAligned64bitRegAccess++; 862 } 863 } 864 } 865 } 866 } 867 868 if (notAligned64bitParamAccess > aligned64bitParamAccess 869 && notAligned64bitRegAccess > aligned64bitRegAccess) { 870 addReservedRegisters(1); 871 } else if (notAligned64bitParamAccess > aligned64bitParamAccess) { 872 addReservedParameters(1); 873 } else if (notAligned64bitRegAccess > aligned64bitRegAccess) { 874 addReservedRegisters(1); 875 876 // Need to shift parameters if they exist and if number of unaligned is greater than 877 // aligned. We test the opposite because we previously shift all registers by one, 878 // so the number of aligned become the number of unaligned. 879 if (paramSize != 0 && aligned64bitParamAccess > notAligned64bitParamAccess) { 880 addReservedParameters(1); 881 } 882 } else { 883 break; 884 } 885 886 if (!reserveRegisters(opcodes)) { 887 break; 888 } 889 } 890 } 891 892 private void addReservedParameters(int delta) { 893 shiftParameters(delta); 894 reservedParameterCount += delta; 895 } 896 897 private void addReservedRegisters(int delta) { 898 shiftAllRegisters(delta); 899 reservedCount += delta; 900 } 901 902 private void shiftAllRegisters(int delta) { 903 int insnSize = insns.size(); 904 905 for (int i = 0; i < insnSize; i++) { 906 DalvInsn insn = insns.get(i); 907 // Since there is no need to replace CodeAddress since it does not use registers, skips it to 908 // avoid to update all TargetInsn that contain a reference to CodeAddress 909 if (!(insn instanceof CodeAddress)) { 910 insns.set(i, insn.withRegisterOffset(delta)); 911 } 912 } 913 } 914 915 private void shiftParameters(int delta) { 916 int insnSize = insns.size(); 917 int lastParameter = unreservedRegCount + reservedCount + reservedParameterCount; 918 int firstParameter = lastParameter - paramSize; 919 920 BasicRegisterMapper mapper = new BasicRegisterMapper(lastParameter); 921 for (int i = 0; i < lastParameter; i++) { 922 if (i >= firstParameter) { 923 mapper.addMapping(i, i + delta, 1); 924 } else { 925 mapper.addMapping(i, i, 1); 926 } 927 } 928 929 for (int i = 0; i < insnSize; i++) { 930 DalvInsn insn = insns.get(i); 931 // Since there is no need to replace CodeAddress since it does not use registers, skips it to 932 // avoid to update all TargetInsn that contain a reference to CodeAddress 933 if (!(insn instanceof CodeAddress)) { 934 insns.set(i, insn.withMapper(mapper)); 935 } 936 } 937 } 938 } 939