1/* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2013 Eric Lafortune (eric@graphics.cornell.edu) 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU General Public License as published by the Free 9 * Software Foundation; either version 2 of the License, or (at your option) 10 * any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 15 * more details. 16 * 17 * You should have received a copy of the GNU General Public License along 18 * with this program; if not, write to the Free Software Foundation, Inc., 19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21package proguard.optimize.peephole; 22 23import proguard.classfile.*; 24import proguard.classfile.attribute.*; 25import proguard.classfile.attribute.visitor.*; 26import proguard.classfile.constant.*; 27import proguard.classfile.constant.visitor.ConstantVisitor; 28import proguard.classfile.instruction.*; 29import proguard.classfile.instruction.visitor.InstructionVisitor; 30import proguard.classfile.util.SimplifiedVisitor; 31 32import java.util.Arrays; 33 34/** 35 * This AttributeVisitor finds all instruction offsets, branch targets, and 36 * exception targets in the CodeAttribute objects that it visits. 37 * 38 * @author Eric Lafortune 39 */ 40public class BranchTargetFinder 41extends SimplifiedVisitor 42implements AttributeVisitor, 43 InstructionVisitor, 44 ExceptionInfoVisitor, 45 ConstantVisitor 46{ 47 //* 48 private static final boolean DEBUG = false; 49 /*/ 50 private static boolean DEBUG = System.getProperty("btf") != null; 51 //*/ 52 53 public static final int NONE = -2; 54 public static final int AT_METHOD_ENTRY = -1; 55 56 public static final int UNKNOWN = -1; 57 public static final int NO_SUBROUTINE = -2; 58 59 private static final short INSTRUCTION = 1 << 0; 60 private static final short BRANCH_ORIGIN = 1 << 1; 61 private static final short BRANCH_TARGET = 1 << 2; 62 private static final short AFTER_BRANCH = 1 << 3; 63 private static final short EXCEPTION_START = 1 << 4; 64 private static final short EXCEPTION_END = 1 << 5; 65 private static final short EXCEPTION_HANDLER = 1 << 6; 66 private static final short SUBROUTINE_INVOCATION = 1 << 7; 67 private static final short SUBROUTINE_RETURNING = 1 << 8; 68 69 private static final int MAXIMUM_CREATION_OFFSETS = 32; 70 71 72 private short[] instructionMarks = new short[ClassConstants.TYPICAL_CODE_LENGTH + 1]; 73 private int[] subroutineStarts = new int[ClassConstants.TYPICAL_CODE_LENGTH]; 74 private int[] subroutineEnds = new int[ClassConstants.TYPICAL_CODE_LENGTH]; 75 private int[] creationOffsets = new int[ClassConstants.TYPICAL_CODE_LENGTH]; 76 private int[] initializationOffsets = new int[ClassConstants.TYPICAL_CODE_LENGTH]; 77 private int superInitializationOffset; 78 private boolean containsSubroutines; 79 80 private boolean repeat; 81 private int currentSubroutineStart; 82 private int[] recentCreationOffsets = new int[MAXIMUM_CREATION_OFFSETS]; 83 private int recentCreationOffsetIndex; 84 private boolean isInitializer; 85 86 87 /** 88 * Returns whether there is an instruction at the given offset in the 89 * CodeAttribute that was visited most recently. 90 */ 91 public boolean isInstruction(int offset) 92 { 93 return (instructionMarks[offset] & INSTRUCTION) != 0; 94 } 95 96 97 /** 98 * Returns whether the instruction at the given offset is the target of 99 * any kind in the CodeAttribute that was visited most recently. 100 */ 101 public boolean isTarget(int offset) 102 { 103 return offset == 0 || 104 (instructionMarks[offset] & (BRANCH_TARGET | 105 EXCEPTION_START | 106 EXCEPTION_END | 107 EXCEPTION_HANDLER)) != 0; 108 } 109 110 111 /** 112 * Returns whether the instruction at the given offset is the origin of a 113 * branch instruction in the CodeAttribute that was visited most recently. 114 */ 115 public boolean isBranchOrigin(int offset) 116 { 117 return (instructionMarks[offset] & BRANCH_ORIGIN) != 0; 118 } 119 120 121 /** 122 * Returns whether the instruction at the given offset is the target of a 123 * branch instruction in the CodeAttribute that was visited most recently. 124 */ 125 public boolean isBranchTarget(int offset) 126 { 127 return (instructionMarks[offset] & BRANCH_TARGET) != 0; 128 } 129 130 131 /** 132 * Returns whether the instruction at the given offset comes right after a 133 * definite branch instruction in the CodeAttribute that was visited most 134 * recently. 135 */ 136 public boolean isAfterBranch(int offset) 137 { 138 return (instructionMarks[offset] & AFTER_BRANCH) != 0; 139 } 140 141 142 /** 143 * Returns whether the instruction at the given offset is the start of an 144 * exception try block in the CodeAttribute that was visited most recently. 145 */ 146 public boolean isExceptionStart(int offset) 147 { 148 return (instructionMarks[offset] & EXCEPTION_START) != 0; 149 } 150 151 152 /** 153 * Returns whether the instruction at the given offset is the end of an 154 * exception try block in the CodeAttribute that was visited most recently. 155 */ 156 public boolean isExceptionEnd(int offset) 157 { 158 return (instructionMarks[offset] & EXCEPTION_END) != 0; 159 } 160 161 162 /** 163 * Returns whether the instruction at the given offset is the start of an 164 * exception catch block in the CodeAttribute that was visited most recently. 165 */ 166 public boolean isExceptionHandler(int offset) 167 { 168 return (instructionMarks[offset] & EXCEPTION_HANDLER) != 0; 169 } 170 171 172 /** 173 * Returns whether the instruction at the given offset is a subroutine 174 * invocation in the CodeAttribute that was visited most recently. 175 */ 176 public boolean isSubroutineInvocation(int offset) 177 { 178 return (instructionMarks[offset] & SUBROUTINE_INVOCATION) != 0; 179 } 180 181 182 /** 183 * Returns whether the instruction at the given offset is the start of a 184 * subroutine in the CodeAttribute that was visited most recently. 185 */ 186 public boolean isSubroutineStart(int offset) 187 { 188 return subroutineStarts[offset] == offset; 189 } 190 191 192 /** 193 * Returns whether the instruction at the given offset is part of a 194 * subroutine in the CodeAttribute that was visited most recently. 195 */ 196 public boolean isSubroutine(int offset) 197 { 198 return subroutineStarts[offset] >= 0; 199 } 200 201 202 /** 203 * Returns whether the subroutine at the given offset is ever returning 204 * by means of a regular 'ret' instruction. 205 */ 206 public boolean isSubroutineReturning(int offset) 207 { 208 return (instructionMarks[offset] & SUBROUTINE_RETURNING) != 0; 209 } 210 211 212 /** 213 * Returns the start offset of the subroutine at the given offset, in the 214 * CodeAttribute that was visited most recently. 215 */ 216 public int subroutineStart(int offset) 217 { 218 return subroutineStarts[offset]; 219 } 220 221 222 /** 223 * Returns the offset after the subroutine at the given offset, in the 224 * CodeAttribute that was visited most recently. 225 */ 226 public int subroutineEnd(int offset) 227 { 228 return subroutineEnds[offset]; 229 } 230 231 232 /** 233 * Returns whether the instruction at the given offset is a 'new' 234 * instruction, in the CodeAttribute that was visited most recently. 235 */ 236 public boolean isNew(int offset) 237 { 238 return initializationOffsets[offset] != NONE; 239 } 240 241 242 /** 243 * Returns the instruction offset at which the object instance that is 244 * created at the given 'new' instruction offset is initialized, or 245 * <code>NONE</code> if it is not being created. 246 */ 247 public int initializationOffset(int offset) 248 { 249 return initializationOffsets[offset]; 250 } 251 252 253 /** 254 * Returns whether the method is an instance initializer, in the 255 * CodeAttribute that was visited most recently. 256 */ 257 public boolean isInitializer() 258 { 259 return superInitializationOffset != NONE; 260 } 261 262 263 /** 264 * Returns the instruction offset at which this initializer is calling 265 * the "super" or "this" initializer method, or <code>NONE</code> if it is 266 * not an initializer. 267 */ 268 public int superInitializationOffset() 269 { 270 return superInitializationOffset; 271 } 272 273 274 /** 275 * Returns whether the instruction at the given offset is the special 276 * invocation of an instance initializer, in the CodeAttribute that was 277 * visited most recently. 278 */ 279 public boolean isInitializer(int offset) 280 { 281 return creationOffsets[offset] != NONE; 282 } 283 284 285 /** 286 * Returns the offset of the 'new' instruction that corresponds to the 287 * invocation of the instance initializer at the given offset, or 288 * <code>AT_METHOD_ENTRY</code> if the invocation is calling the "super" or 289 * "this" initializer method, , or <code>NONE</code> if it is not a 'new' 290 * instruction. 291 */ 292 public int creationOffset(int offset) 293 { 294 return creationOffsets[offset]; 295 } 296 297 298 /** 299 * Returns whether the method contains subroutines, in the CodeAttribute 300 * that was visited most recently. 301 */ 302 public boolean containsSubroutines() 303 { 304 return containsSubroutines; 305 } 306 307 308 // Implementations for AttributeVisitor. 309 310 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 311 312 313 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 314 { 315// DEBUG = 316// clazz.getName().equals("abc/Def") && 317// method.getName(clazz).equals("abc"); 318 319 // Make sure there are sufficiently large arrays. 320 int codeLength = codeAttribute.u4codeLength; 321 if (subroutineStarts.length < codeLength) 322 { 323 // Create new arrays. 324 instructionMarks = new short[codeLength + 1]; 325 subroutineStarts = new int[codeLength]; 326 subroutineEnds = new int[codeLength]; 327 creationOffsets = new int[codeLength]; 328 initializationOffsets = new int[codeLength]; 329 330 // Reset the arrays. 331 Arrays.fill(subroutineStarts, 0, codeLength, UNKNOWN); 332 Arrays.fill(subroutineEnds, 0, codeLength, UNKNOWN); 333 Arrays.fill(creationOffsets, 0, codeLength, NONE); 334 Arrays.fill(initializationOffsets, 0, codeLength, NONE); 335 } 336 else 337 { 338 // Reset the arrays. 339 Arrays.fill(instructionMarks, 0, codeLength, (short)0); 340 Arrays.fill(subroutineStarts, 0, codeLength, UNKNOWN); 341 Arrays.fill(subroutineEnds, 0, codeLength, UNKNOWN); 342 Arrays.fill(creationOffsets, 0, codeLength, NONE); 343 Arrays.fill(initializationOffsets, 0, codeLength, NONE); 344 345 instructionMarks[codeLength] = 0; 346 } 347 348 superInitializationOffset = NONE; 349 containsSubroutines = false; 350 351 // Iterate until all subroutines have been fully marked. 352 do 353 { 354 repeat = false; 355 currentSubroutineStart = NO_SUBROUTINE; 356 recentCreationOffsetIndex = 0; 357 358 // Initialize the stack of 'new' instruction offsets if this method 359 // is an instance initializer. 360 if (method.getName(clazz).equals(ClassConstants.INTERNAL_METHOD_NAME_INIT)) 361 { 362 recentCreationOffsets[recentCreationOffsetIndex++] = AT_METHOD_ENTRY; 363 } 364 365 // Mark branch targets by going over all instructions. 366 codeAttribute.instructionsAccept(clazz, method, this); 367 } 368 while (repeat); 369 370 // The end of the code is a branch target sentinel. 371 instructionMarks[codeLength] = BRANCH_TARGET; 372 373 // Mark branch targets in the exception table. 374 codeAttribute.exceptionsAccept(clazz, method, this); 375 376 if (containsSubroutines) 377 { 378 // Set the subroutine returning flag and the subroutine end at each 379 // subroutine start. 380 int previousSubroutineStart = NO_SUBROUTINE; 381 382 for (int offset = 0; offset < codeLength; offset++) 383 { 384 if (isInstruction(offset)) 385 { 386 int subroutineStart = subroutineStarts[offset]; 387 388 if (subroutineStart >= 0 && 389 isSubroutineReturning(offset)) 390 { 391 instructionMarks[subroutineStart] |= SUBROUTINE_RETURNING; 392 } 393 394 if (previousSubroutineStart >= 0) 395 { 396 subroutineEnds[previousSubroutineStart] = offset; 397 } 398 399 previousSubroutineStart = subroutineStart; 400 } 401 } 402 403 if (previousSubroutineStart >= 0) 404 { 405 subroutineEnds[previousSubroutineStart] = codeLength; 406 } 407 408 // Set the subroutine returning flag and the subroutine end at each 409 // subroutine instruction, based on the marks at the subroutine 410 // start. 411 for (int offset = 0; offset < codeLength; offset++) 412 { 413 if (isSubroutine(offset)) 414 { 415 int subroutineStart = subroutineStarts[offset]; 416 417 if (isSubroutineReturning(subroutineStart)) 418 { 419 instructionMarks[offset] |= SUBROUTINE_RETURNING; 420 } 421 422 subroutineEnds[offset] = subroutineEnds[subroutineStart]; 423 } 424 } 425 } 426 427 if (DEBUG) 428 { 429 System.out.println(); 430 System.out.println("Branch targets: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)); 431 432 for (int index = 0; index < codeLength; index++) 433 { 434 if (isInstruction(index)) 435 { 436 System.out.println("" + 437 (isBranchOrigin(index) ? 'B' : '-') + 438 (isAfterBranch(index) ? 'b' : '-') + 439 (isBranchTarget(index) ? 'T' : '-') + 440 (isExceptionStart(index) ? 'E' : '-') + 441 (isExceptionEnd(index) ? 'e' : '-') + 442 (isExceptionHandler(index) ? 'H' : '-') + 443 (isSubroutineInvocation(index) ? 'J' : '-') + 444 (isSubroutineStart(index) ? 'S' : '-') + 445 (isSubroutineReturning(index) ? 'r' : '-') + 446 (isSubroutine(index) ? " ["+subroutineStart(index)+" -> "+subroutineEnd(index)+"]" : "") + 447 (isNew(index) ? " ["+initializationOffset(index)+"] " : " ---- ") + 448 InstructionFactory.create(codeAttribute.code, index).toString(index)); 449 } 450 } 451 } 452 } 453 454 455 // Implementations for InstructionVisitor. 456 457 public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction) 458 { 459 // Mark the instruction. 460 instructionMarks[offset] |= INSTRUCTION; 461 462 // Check if this is an instruction of a subroutine. 463 checkSubroutine(offset); 464 465 byte opcode = simpleInstruction.opcode; 466 if (opcode == InstructionConstants.OP_IRETURN || 467 opcode == InstructionConstants.OP_LRETURN || 468 opcode == InstructionConstants.OP_FRETURN || 469 opcode == InstructionConstants.OP_DRETURN || 470 opcode == InstructionConstants.OP_ARETURN || 471 opcode == InstructionConstants.OP_ATHROW) 472 { 473 // Mark the branch origin. 474 markBranchOrigin(offset); 475 476 // Mark the next instruction. 477 markAfterBranchOrigin(offset + simpleInstruction.length(offset)); 478 } 479 } 480 481 482 public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) 483 { 484 // Mark the instruction. 485 instructionMarks[offset] |= INSTRUCTION; 486 487 // Check if this is an instruction of a subroutine. 488 checkSubroutine(offset); 489 490 // Check if the instruction is a 'new' instruction. 491 if (constantInstruction.opcode == InstructionConstants.OP_NEW) 492 { 493 // Push the 'new' instruction offset on the stack. 494 recentCreationOffsets[recentCreationOffsetIndex++] = offset; 495 } 496 else 497 { 498 // Check if the instruction is an initializer invocation. 499 isInitializer = false; 500 clazz.constantPoolEntryAccept(constantInstruction.constantIndex, this); 501 if (isInitializer) 502 { 503 // Pop the 'new' instruction offset from the stack. 504 int recentCreationOffset = recentCreationOffsets[--recentCreationOffsetIndex]; 505 506 // Fill it out in the creation offsets. 507 creationOffsets[offset] = recentCreationOffset; 508 509 // Fill out the initialization offsets. 510 if (recentCreationOffset == AT_METHOD_ENTRY) 511 { 512 superInitializationOffset = offset; 513 } 514 else 515 { 516 initializationOffsets[recentCreationOffset] = offset; 517 } 518 } 519 } 520 } 521 522 523 public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) 524 { 525 // Mark the instruction. 526 instructionMarks[offset] |= INSTRUCTION; 527 528 // Check if this is an instruction of a subroutine. 529 checkSubroutine(offset); 530 531 if (variableInstruction.opcode == InstructionConstants.OP_RET) 532 { 533 // Mark the method. 534 containsSubroutines = true; 535 536 // Mark the branch origin. 537 markBranchOrigin(offset); 538 539 // Mark the subroutine return at its return instruction. 540 instructionMarks[offset] |= SUBROUTINE_RETURNING; 541 542 // Mark the next instruction. 543 markAfterBranchOrigin(offset + variableInstruction.length(offset)); 544 } 545 } 546 547 548 public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction) 549 { 550 int branchOffset = branchInstruction.branchOffset; 551 int targetOffset = offset + branchOffset; 552 553 // Mark the branch origin. 554 markBranchOrigin(offset); 555 556 // Check if this is an instruction of a subroutine. 557 checkSubroutine(offset); 558 559 // Mark the branch target. 560 markBranchTarget(offset, branchOffset); 561 562 byte opcode = branchInstruction.opcode; 563 if (opcode == InstructionConstants.OP_JSR || 564 opcode == InstructionConstants.OP_JSR_W) 565 { 566 // Mark the method. 567 containsSubroutines = true; 568 569 // Mark the subroutine invocation. 570 instructionMarks[offset] |= SUBROUTINE_INVOCATION; 571 572 // Mark the new subroutine start. 573 markBranchSubroutineStart(offset, branchOffset, targetOffset); 574 } 575 else if (currentSubroutineStart != UNKNOWN) 576 { 577 // Mark the continued subroutine start. 578 markBranchSubroutineStart(offset, branchOffset, currentSubroutineStart); 579 } 580 581 if (opcode == InstructionConstants.OP_GOTO || 582 opcode == InstructionConstants.OP_GOTO_W) 583 { 584 // Mark the next instruction. 585 markAfterBranchOrigin(offset + branchInstruction.length(offset)); 586 } 587 } 588 589 590 public void visitAnySwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SwitchInstruction switchInstruction) 591 { 592 // Mark the branch origin. 593 markBranchOrigin(offset); 594 595 // Check if this is an instruction of a subroutine. 596 checkSubroutine(offset); 597 598 // Mark the branch targets of the default jump offset. 599 markBranch(offset, switchInstruction.defaultOffset); 600 601 // Mark the branch targets of the jump offsets. 602 markBranches(offset, switchInstruction.jumpOffsets); 603 604 // Mark the next instruction. 605 markAfterBranchOrigin(offset + switchInstruction.length(offset)); 606 } 607 608 609 // Implementations for ConstantVisitor. 610 611 public void visitAnyConstant(Clazz clazz, Constant constant) {} 612 613 614 public void visitMethodrefConstant(Clazz clazz, MethodrefConstant methodrefConstant) 615 { 616 isInitializer = methodrefConstant.getName(clazz).equals(ClassConstants.INTERNAL_METHOD_NAME_INIT); 617 } 618 619 620 // Implementations for ExceptionInfoVisitor. 621 622 public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) 623 { 624 // Mark the exception offsets. 625 instructionMarks[exceptionInfo.u2startPC] |= EXCEPTION_START; 626 instructionMarks[exceptionInfo.u2endPC] |= EXCEPTION_END; 627 instructionMarks[exceptionInfo.u2handlerPC] |= EXCEPTION_HANDLER; 628 } 629 630 631 // Small utility methods. 632 633 /** 634 * Marks the branch targets and their subroutine starts at the given 635 * offsets. 636 */ 637 private void markBranches(int offset, int[] jumpOffsets) 638 { 639 for (int index = 0; index < jumpOffsets.length; index++) 640 { 641 markBranch(offset, jumpOffsets[index]); 642 } 643 } 644 645 646 /** 647 * Marks the branch target and its subroutine start at the given offset. 648 */ 649 private void markBranch(int offset, int jumpOffset) 650 { 651 markBranchTarget(offset, jumpOffset); 652 653 if (currentSubroutineStart != UNKNOWN) 654 { 655 markBranchSubroutineStart(offset, jumpOffset, currentSubroutineStart); 656 } 657 } 658 659 /** 660 * Marks the branch origin at the given offset. 661 */ 662 private void markBranchOrigin(int offset) 663 { 664 instructionMarks[offset] |= INSTRUCTION | BRANCH_ORIGIN; 665 } 666 667 668 /** 669 * Marks the branch target at the given offset. 670 */ 671 private void markBranchTarget(int offset, int jumpOffset) 672 { 673 int targetOffset = offset + jumpOffset; 674 675 instructionMarks[targetOffset] |= BRANCH_TARGET; 676 } 677 678 679 /** 680 * Marks the subroutine start at the given offset, if applicable. 681 */ 682 private void markBranchSubroutineStart(int offset, 683 int jumpOffset, 684 int subroutineStart) 685 { 686 int targetOffset = offset + jumpOffset; 687 688 // Are we marking a subroutine and branching to an offset that hasn't 689 // been marked yet? 690 if (subroutineStarts[targetOffset] == UNKNOWN) 691 { 692 // Is it a backward branch? 693 if (jumpOffset < 0) 694 { 695 // Remember the smallest subroutine start. 696 if (subroutineStart > targetOffset) 697 { 698 subroutineStart = targetOffset; 699 } 700 701 // We'll have to go over all instructions again. 702 repeat = true; 703 } 704 705 // Mark the subroutine start of the target. 706 subroutineStarts[targetOffset] = subroutineStart; 707 } 708 } 709 710 711 /** 712 * Marks the instruction at the given offset, after a branch. 713 */ 714 private void markAfterBranchOrigin(int nextOffset) 715 { 716 instructionMarks[nextOffset] |= AFTER_BRANCH; 717 718 // Stop marking a subroutine. 719 currentSubroutineStart = UNKNOWN; 720 } 721 722 723 /** 724 * Checks if the specified instruction is inside a subroutine. 725 */ 726 private void checkSubroutine(int offset) 727 { 728 // Are we inside a previously marked subroutine? 729 if (subroutineStarts[offset] != UNKNOWN) 730 { 731 // Start marking a subroutine. 732 currentSubroutineStart = subroutineStarts[offset]; 733 } 734 735 // Are we marking a subroutine? 736 else if (currentSubroutineStart != UNKNOWN) 737 { 738 // Mark the subroutine start. 739 subroutineStarts[offset] = currentSubroutineStart; 740 741 if (currentSubroutineStart >= 0) 742 { 743 // Mark the subroutine end at the subroutine start. 744 subroutineEnds[currentSubroutineStart] = offset; 745 } 746 } 747 } 748} 749