PartialEvaluator.java revision b9cc48a43ed984587c939d02fba5316bf5c0df6e
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.evaluation; 22 23import proguard.classfile.*; 24import proguard.classfile.attribute.*; 25import proguard.classfile.attribute.visitor.*; 26import proguard.classfile.constant.ClassConstant; 27import proguard.classfile.instruction.*; 28import proguard.classfile.util.*; 29import proguard.classfile.visitor.*; 30import proguard.evaluation.*; 31import proguard.evaluation.value.*; 32import proguard.optimize.peephole.BranchTargetFinder; 33 34import java.util.Arrays; 35 36/** 37 * This AttributeVisitor performs partial evaluation on the code attributes 38 * that it visits. 39 * 40 * @author Eric Lafortune 41 */ 42public class PartialEvaluator 43extends SimplifiedVisitor 44implements AttributeVisitor, 45 ExceptionInfoVisitor 46{ 47 //* 48 private static final boolean DEBUG = false; 49 private static final boolean DEBUG_RESULTS = false; 50 /*/ 51 private static boolean DEBUG = true; 52 private static boolean DEBUG_RESULTS = true; 53 //*/ 54 55 private static final int MAXIMUM_EVALUATION_COUNT = 5; 56 57 public static final int NONE = -2; 58 public static final int AT_METHOD_ENTRY = -1; 59 public static final int AT_CATCH_ENTRY = -1; 60 61 private final ValueFactory valueFactory; 62 private final InvocationUnit invocationUnit; 63 private final boolean evaluateAllCode; 64 65 private InstructionOffsetValue[] branchOriginValues = new InstructionOffsetValue[ClassConstants.TYPICAL_CODE_LENGTH]; 66 private InstructionOffsetValue[] branchTargetValues = new InstructionOffsetValue[ClassConstants.TYPICAL_CODE_LENGTH]; 67 private TracedVariables[] variablesBefore = new TracedVariables[ClassConstants.TYPICAL_CODE_LENGTH]; 68 private TracedStack[] stacksBefore = new TracedStack[ClassConstants.TYPICAL_CODE_LENGTH]; 69 private TracedVariables[] variablesAfter = new TracedVariables[ClassConstants.TYPICAL_CODE_LENGTH]; 70 private TracedStack[] stacksAfter = new TracedStack[ClassConstants.TYPICAL_CODE_LENGTH]; 71 private boolean[] generalizedContexts = new boolean[ClassConstants.TYPICAL_CODE_LENGTH]; 72 private int[] evaluationCounts = new int[ClassConstants.TYPICAL_CODE_LENGTH]; 73 private boolean evaluateExceptions; 74 75 private final BasicBranchUnit branchUnit; 76 private final BranchTargetFinder branchTargetFinder; 77 78 private final java.util.Stack callingInstructionBlockStack; 79 private final java.util.Stack instructionBlockStack = new java.util.Stack(); 80 81 82 /** 83 * Creates a simple PartialEvaluator. 84 */ 85 public PartialEvaluator() 86 { 87 this(new ValueFactory(), 88 new BasicInvocationUnit(new ValueFactory()), 89 true); 90 } 91 92 93 /** 94 * Creates a new PartialEvaluator. 95 * @param valueFactory the value factory that will create all values 96 * during evaluation. 97 * @param invocationUnit the invocation unit that will handle all 98 * communication with other fields and methods. 99 * @param evaluateAllCode a flag that specifies whether all branch targets 100 * and exception handlers should be evaluated, 101 * even if they are unreachable. 102 */ 103 public PartialEvaluator(ValueFactory valueFactory, 104 InvocationUnit invocationUnit, 105 boolean evaluateAllCode) 106 { 107 this(valueFactory, 108 invocationUnit, 109 evaluateAllCode, 110 evaluateAllCode ? 111 new BasicBranchUnit() : 112 new TracedBranchUnit(), 113 new BranchTargetFinder(), 114 null); 115 } 116 117 118 /** 119 * Creates a new PartialEvaluator, based on an existing one. 120 * @param partialEvaluator the subroutine calling partial evaluator. 121 */ 122 private PartialEvaluator(PartialEvaluator partialEvaluator) 123 { 124 this(partialEvaluator.valueFactory, 125 partialEvaluator.invocationUnit, 126 partialEvaluator.evaluateAllCode, 127 partialEvaluator.branchUnit, 128 partialEvaluator.branchTargetFinder, 129 partialEvaluator.instructionBlockStack); 130 } 131 132 133 /** 134 * Creates a new PartialEvaluator. 135 * @param valueFactory the value factory that will create all 136 * values during evaluation. 137 * @param invocationUnit the invocation unit that will handle all 138 * communication with other fields and methods. 139 * @param evaluateAllCode a flag that specifies whether all branch 140 * targets and exception handlers should be 141 * evaluated, even if they are unreachable. 142 * @param branchUnit the branch unit that will handle all 143 * branches. 144 * @param branchTargetFinder the utility class that will find all 145 * branches. 146 */ 147 private PartialEvaluator(ValueFactory valueFactory, 148 InvocationUnit invocationUnit, 149 boolean evaluateAllCode, 150 BasicBranchUnit branchUnit, 151 BranchTargetFinder branchTargetFinder, 152 java.util.Stack callingInstructionBlockStack) 153 { 154 this.valueFactory = valueFactory; 155 this.invocationUnit = invocationUnit; 156 this.evaluateAllCode = evaluateAllCode; 157 this.branchUnit = branchUnit; 158 this.branchTargetFinder = branchTargetFinder; 159 this.callingInstructionBlockStack = callingInstructionBlockStack == null ? 160 this.instructionBlockStack : 161 callingInstructionBlockStack; 162 } 163 164 165 // Implementations for AttributeVisitor. 166 167 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 168 169 170 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 171 { 172// DEBUG = DEBUG_RESULTS = 173// clazz.getName().equals("abc/Def") && 174// method.getName(clazz).equals("abc"); 175 176 // TODO: Remove this when the partial evaluator has stabilized. 177 // Catch any unexpected exceptions from the actual visiting method. 178 try 179 { 180 // Process the code. 181 visitCodeAttribute0(clazz, method, codeAttribute); 182 } 183 catch (RuntimeException ex) 184 { 185 System.err.println("Unexpected error while performing partial evaluation:"); 186 System.err.println(" Class = ["+clazz.getName()+"]"); 187 System.err.println(" Method = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]"); 188 System.err.println(" Exception = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")"); 189 190 if (DEBUG) 191 { 192 method.accept(clazz, new ClassPrinter()); 193 194 System.out.println("Evaluation results:"); 195 196 int offset = 0; 197 do 198 { 199 if (isBranchOrExceptionTarget(offset)) 200 { 201 System.out.println("Branch target from ["+branchOriginValues[offset]+"]:"); 202 if (isTraced(offset)) 203 { 204 System.out.println(" Vars: "+variablesBefore[offset]); 205 System.out.println(" Stack: "+stacksBefore[offset]); 206 } 207 } 208 209 Instruction instruction = InstructionFactory.create(codeAttribute.code, 210 offset); 211 System.out.println(instruction.toString(offset)); 212 213 if (isTraced(offset)) 214 { 215 int initializationOffset = branchTargetFinder.initializationOffset(offset); 216 if (initializationOffset != NONE) 217 { 218 System.out.println(" is to be initialized at ["+initializationOffset+"]"); 219 } 220 221 InstructionOffsetValue branchTargets = branchTargets(offset); 222 if (branchTargets != null) 223 { 224 System.out.println(" has overall been branching to "+branchTargets); 225 } 226 227 System.out.println(" Vars: "+variablesAfter[offset]); 228 System.out.println(" Stack: "+stacksAfter[offset]); 229 } 230 231 offset += instruction.length(offset); 232 } 233 while (offset < codeAttribute.u4codeLength); 234 } 235 236 throw ex; 237 } 238 } 239 240 241 public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute) 242 { 243 // Evaluate the instructions, starting at the entry point. 244 if (DEBUG) 245 { 246 System.out.println(); 247 System.out.println("Partial evaluation: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)); 248 System.out.println(" Max locals = "+codeAttribute.u2maxLocals); 249 System.out.println(" Max stack = "+codeAttribute.u2maxStack); 250 } 251 252 // Reuse the existing variables and stack objects, ensuring the right size. 253 TracedVariables variables = new TracedVariables(codeAttribute.u2maxLocals); 254 TracedStack stack = new TracedStack(codeAttribute.u2maxStack); 255 256 // Initialize the reusable arrays and variables. 257 initializeArrays(codeAttribute); 258 initializeParameters(clazz, method, codeAttribute, variables); 259 260 // Find all instruction offsets,... 261 codeAttribute.accept(clazz, method, branchTargetFinder); 262 263 // Start executing the first instruction block. 264 evaluateInstructionBlockAndExceptionHandlers(clazz, 265 method, 266 codeAttribute, 267 variables, 268 stack, 269 0, 270 codeAttribute.u4codeLength); 271 272 if (DEBUG_RESULTS) 273 { 274 System.out.println("Evaluation results:"); 275 276 int offset = 0; 277 do 278 { 279 if (isBranchOrExceptionTarget(offset)) 280 { 281 System.out.println("Branch target from ["+branchOriginValues[offset]+"]:"); 282 if (isTraced(offset)) 283 { 284 System.out.println(" Vars: "+variablesBefore[offset]); 285 System.out.println(" Stack: "+stacksBefore[offset]); 286 } 287 } 288 289 Instruction instruction = InstructionFactory.create(codeAttribute.code, 290 offset); 291 System.out.println(instruction.toString(offset)); 292 293 if (isTraced(offset)) 294 { 295 int initializationOffset = branchTargetFinder.initializationOffset(offset); 296 if (initializationOffset != NONE) 297 { 298 System.out.println(" is to be initialized at ["+initializationOffset+"]"); 299 } 300 301 InstructionOffsetValue branchTargets = branchTargets(offset); 302 if (branchTargets != null) 303 { 304 System.out.println(" has overall been branching to "+branchTargets); 305 } 306 307 System.out.println(" Vars: "+variablesAfter[offset]); 308 System.out.println(" Stack: "+stacksAfter[offset]); 309 } 310 311 offset += instruction.length(offset); 312 } 313 while (offset < codeAttribute.u4codeLength); 314 } 315 } 316 317 318 /** 319 * Returns whether a block of instructions is ever used. 320 */ 321 public boolean isTraced(int startOffset, int endOffset) 322 { 323 for (int index = startOffset; index < endOffset; index++) 324 { 325 if (isTraced(index)) 326 { 327 return true; 328 } 329 } 330 331 return false; 332 } 333 334 335 /** 336 * Returns whether the instruction at the given offset has ever been 337 * executed during the partial evaluation. 338 */ 339 public boolean isTraced(int instructionOffset) 340 { 341 return evaluationCounts[instructionOffset] > 0; 342 } 343 344 345 /** 346 * Returns whether there is an instruction at the given offset. 347 */ 348 public boolean isInstruction(int instructionOffset) 349 { 350 return branchTargetFinder.isInstruction(instructionOffset); 351 } 352 353 354 /** 355 * Returns whether the instruction at the given offset is the target of a 356 * branch instruction or an exception. 357 */ 358 public boolean isBranchOrExceptionTarget(int instructionOffset) 359 { 360 return branchTargetFinder.isBranchTarget(instructionOffset) || 361 branchTargetFinder.isExceptionHandler(instructionOffset); 362 } 363 364 365 /** 366 * Returns whether the instruction at the given offset is the start of a 367 * subroutine. 368 */ 369 public boolean isSubroutineStart(int instructionOffset) 370 { 371 return branchTargetFinder.isSubroutineStart(instructionOffset); 372 } 373 374 375 /** 376 * Returns whether the instruction at the given offset is a subroutine 377 * invocation. 378 */ 379 public boolean isSubroutineInvocation(int instructionOffset) 380 { 381 return branchTargetFinder.isSubroutineInvocation(instructionOffset); 382 } 383 384 385 /** 386 * Returns whether the instruction at the given offset is part of a 387 * subroutine. 388 */ 389 public boolean isSubroutine(int instructionOffset) 390 { 391 return branchTargetFinder.isSubroutine(instructionOffset); 392 } 393 394 395 /** 396 * Returns whether the subroutine at the given offset is ever returning 397 * by means of a regular 'ret' instruction. 398 */ 399 public boolean isSubroutineReturning(int instructionOffset) 400 { 401 return branchTargetFinder.isSubroutineReturning(instructionOffset); 402 } 403 404 405 /** 406 * Returns the offset after the subroutine that starts at the given 407 * offset. 408 */ 409 public int subroutineEnd(int instructionOffset) 410 { 411 return branchTargetFinder.subroutineEnd(instructionOffset); 412 } 413 414 415 /** 416 * Returns the instruction offset at which the object instance that is 417 * created at the given 'new' instruction offset is initialized, or 418 * <code>NONE</code> if it is not being created. 419 */ 420 public int initializationOffset(int instructionOffset) 421 { 422 return branchTargetFinder.initializationOffset(instructionOffset); 423 } 424 425 426 /** 427 * Returns whether the method is an instance initializer. 428 */ 429 public boolean isInitializer() 430 { 431 return branchTargetFinder.isInitializer(); 432 } 433 434 435 /** 436 * Returns the instruction offset at which this initializer is calling 437 * the "super" or "this" initializer method, or <code>NONE</code> if it is 438 * not an initializer. 439 */ 440 public int superInitializationOffset() 441 { 442 return branchTargetFinder.superInitializationOffset(); 443 } 444 445 446 /** 447 * Returns the offset of the 'new' instruction that corresponds to the 448 * invocation of the instance initializer at the given offset, or 449 * <code>AT_METHOD_ENTRY</code> if the invocation is calling the "super" or 450 * "this" initializer method, , or <code>NONE</code> if it is not a 'new' 451 * instruction. 452 */ 453 public int creationOffset(int offset) 454 { 455 return branchTargetFinder.creationOffset(offset); 456 } 457 458 459 /** 460 * Returns the variables before execution of the instruction at the given 461 * offset. 462 */ 463 public TracedVariables getVariablesBefore(int instructionOffset) 464 { 465 return variablesBefore[instructionOffset]; 466 } 467 468 469 /** 470 * Returns the variables after execution of the instruction at the given 471 * offset. 472 */ 473 public TracedVariables getVariablesAfter(int instructionOffset) 474 { 475 return variablesAfter[instructionOffset]; 476 } 477 478 479 /** 480 * Returns the stack before execution of the instruction at the given 481 * offset. 482 */ 483 public TracedStack getStackBefore(int instructionOffset) 484 { 485 return stacksBefore[instructionOffset]; 486 } 487 488 489 /** 490 * Returns the stack after execution of the instruction at the given 491 * offset. 492 */ 493 public TracedStack getStackAfter(int instructionOffset) 494 { 495 return stacksAfter[instructionOffset]; 496 } 497 498 499 /** 500 * Returns the instruction offsets that branch to the given instruction 501 * offset. 502 */ 503 public InstructionOffsetValue branchOrigins(int instructionOffset) 504 { 505 return branchOriginValues[instructionOffset]; 506 } 507 508 509 /** 510 * Returns the instruction offsets to which the given instruction offset 511 * branches. 512 */ 513 public InstructionOffsetValue branchTargets(int instructionOffset) 514 { 515 return branchTargetValues[instructionOffset]; 516 } 517 518 519 // Utility methods to evaluate instruction blocks. 520 521 /** 522 * Pushes block of instructions to be executed in the calling partial 523 * evaluator. 524 */ 525 private void pushCallingInstructionBlock(TracedVariables variables, 526 TracedStack stack, 527 int startOffset) 528 { 529 callingInstructionBlockStack.push(new MyInstructionBlock(variables, 530 stack, 531 startOffset)); 532 } 533 534 535 /** 536 * Pushes block of instructions to be executed in this partial evaluator. 537 */ 538 private void pushInstructionBlock(TracedVariables variables, 539 TracedStack stack, 540 int startOffset) 541 { 542 instructionBlockStack.push(new MyInstructionBlock(variables, 543 stack, 544 startOffset)); 545 } 546 547 548 /** 549 * Evaluates the instruction block and the exception handlers covering the 550 * given instruction range in the given code. 551 */ 552 private void evaluateInstructionBlockAndExceptionHandlers(Clazz clazz, 553 Method method, 554 CodeAttribute codeAttribute, 555 TracedVariables variables, 556 TracedStack stack, 557 int startOffset, 558 int endOffset) 559 { 560 evaluateInstructionBlock(clazz, 561 method, 562 codeAttribute, 563 variables, 564 stack, 565 startOffset); 566 567 evaluateExceptionHandlers(clazz, 568 method, 569 codeAttribute, 570 startOffset, 571 endOffset); 572 } 573 574 575 /** 576 * Evaluates a block of instructions, starting at the given offset and ending 577 * at a branch instruction, a return instruction, or a throw instruction. 578 */ 579 private void evaluateInstructionBlock(Clazz clazz, 580 Method method, 581 CodeAttribute codeAttribute, 582 TracedVariables variables, 583 TracedStack stack, 584 int startOffset) 585 { 586 // Execute the initial instruction block. 587 evaluateSingleInstructionBlock(clazz, 588 method, 589 codeAttribute, 590 variables, 591 stack, 592 startOffset); 593 594 // Execute all resulting instruction blocks on the execution stack. 595 while (!instructionBlockStack.empty()) 596 { 597 if (DEBUG) System.out.println("Popping alternative branch out of "+instructionBlockStack.size()+" blocks"); 598 599 MyInstructionBlock instructionBlock = 600 (MyInstructionBlock)instructionBlockStack.pop(); 601 602 evaluateSingleInstructionBlock(clazz, 603 method, 604 codeAttribute, 605 instructionBlock.variables, 606 instructionBlock.stack, 607 instructionBlock.startOffset); 608 } 609 } 610 611 612 /** 613 * Evaluates a block of instructions, starting at the given offset and ending 614 * at a branch instruction, a return instruction, or a throw instruction. 615 * Instruction blocks that are to be evaluated as a result are pushed on 616 * the given stack. 617 */ 618 private void evaluateSingleInstructionBlock(Clazz clazz, 619 Method method, 620 CodeAttribute codeAttribute, 621 TracedVariables variables, 622 TracedStack stack, 623 int startOffset) 624 { 625 byte[] code = codeAttribute.code; 626 627 if (DEBUG) 628 { 629 System.out.println("Instruction block starting at ["+startOffset+"] in "+ 630 ClassUtil.externalFullMethodDescription(clazz.getName(), 631 0, 632 method.getName(clazz), 633 method.getDescriptor(clazz))); 634 System.out.println("Init vars: "+variables); 635 System.out.println("Init stack: "+stack); 636 } 637 638 Processor processor = new Processor(variables, 639 stack, 640 valueFactory, 641 branchUnit, 642 invocationUnit); 643 644 int instructionOffset = startOffset; 645 646 int maxOffset = startOffset; 647 648 // Evaluate the subsequent instructions. 649 while (true) 650 { 651 if (maxOffset < instructionOffset) 652 { 653 maxOffset = instructionOffset; 654 } 655 656 // Maintain a generalized local variable frame and stack at this 657 // instruction offset, before execution. 658 int evaluationCount = evaluationCounts[instructionOffset]; 659 if (evaluationCount == 0) 660 { 661 // First time we're passing by this instruction. 662 if (variablesBefore[instructionOffset] == null) 663 { 664 // There's not even a context at this index yet. 665 variablesBefore[instructionOffset] = new TracedVariables(variables); 666 stacksBefore[instructionOffset] = new TracedStack(stack); 667 } 668 else 669 { 670 // Reuse the context objects at this index. 671 variablesBefore[instructionOffset].initialize(variables); 672 stacksBefore[instructionOffset].copy(stack); 673 } 674 675 // We'll execute in the generalized context, because it is 676 // the same as the current context. 677 generalizedContexts[instructionOffset] = true; 678 } 679 else 680 { 681 // Merge in the current context. 682 boolean variablesChanged = variablesBefore[instructionOffset].generalize(variables, true); 683 boolean stackChanged = stacksBefore[instructionOffset].generalize(stack); 684 685 //System.out.println("GVars: "+variablesBefore[instructionOffset]); 686 //System.out.println("GStack: "+stacksBefore[instructionOffset]); 687 688 // Bail out if the current context is the same as last time. 689 if (!variablesChanged && 690 !stackChanged && 691 generalizedContexts[instructionOffset]) 692 { 693 if (DEBUG) System.out.println("Repeated variables, stack, and branch targets"); 694 695 break; 696 } 697 698 // See if this instruction has been evaluated an excessive number 699 // of times. 700 if (evaluationCount >= MAXIMUM_EVALUATION_COUNT) 701 { 702 if (DEBUG) System.out.println("Generalizing current context after "+evaluationCount+" evaluations"); 703 704 // Continue, but generalize the current context. 705 // Note that the most recent variable values have to remain 706 // last in the generalizations, for the sake of the ret 707 // instruction. 708 variables.generalize(variablesBefore[instructionOffset], false); 709 stack.generalize(stacksBefore[instructionOffset]); 710 711 // We'll execute in the generalized context. 712 generalizedContexts[instructionOffset] = true; 713 } 714 else 715 { 716 // We'll execute in the current context. 717 generalizedContexts[instructionOffset] = false; 718 } 719 } 720 721 // We'll evaluate this instruction. 722 evaluationCounts[instructionOffset]++; 723 724 // Remember this instruction's offset with any stored value. 725 Value storeValue = new InstructionOffsetValue(instructionOffset); 726 variables.setProducerValue(storeValue); 727 stack.setProducerValue(storeValue); 728 729 // Reset the trace value. 730 InstructionOffsetValue traceValue = InstructionOffsetValue.EMPTY_VALUE; 731 732 // Note that the instruction is only volatile. 733 Instruction instruction = InstructionFactory.create(code, instructionOffset); 734 735 // By default, the next instruction will be the one after this 736 // instruction. 737 int nextInstructionOffset = instructionOffset + 738 instruction.length(instructionOffset); 739 InstructionOffsetValue nextInstructionOffsetValue = new InstructionOffsetValue(nextInstructionOffset); 740 branchUnit.resetCalled(); 741 branchUnit.setTraceBranchTargets(nextInstructionOffsetValue); 742 743 if (DEBUG) 744 { 745 System.out.println(instruction.toString(instructionOffset)); 746 } 747 748 try 749 { 750 // Process the instruction. The processor may modify the 751 // variables and the stack, and it may call the branch unit 752 // and the invocation unit. 753 instruction.accept(clazz, 754 method, 755 codeAttribute, 756 instructionOffset, 757 processor); 758 } 759 catch (RuntimeException ex) 760 { 761 System.err.println("Unexpected error while evaluating instruction:"); 762 System.err.println(" Class = ["+clazz.getName()+"]"); 763 System.err.println(" Method = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]"); 764 System.err.println(" Instruction = "+instruction.toString(instructionOffset)); 765 System.err.println(" Exception = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")"); 766 767 throw ex; 768 } 769 770 // Collect the branch targets from the branch unit. 771 InstructionOffsetValue branchTargets = branchUnit.getTraceBranchTargets(); 772 int branchTargetCount = branchTargets.instructionOffsetCount(); 773 774 // Stop tracing. 775 branchUnit.setTraceBranchTargets(traceValue); 776 777 if (DEBUG) 778 { 779 if (branchUnit.wasCalled()) 780 { 781 System.out.println(" is branching to "+branchTargets); 782 } 783 if (branchTargetValues[instructionOffset] != null) 784 { 785 System.out.println(" has up till now been branching to "+branchTargetValues[instructionOffset]); 786 } 787 788 System.out.println(" Vars: "+variables); 789 System.out.println(" Stack: "+stack); 790 } 791 792 // Maintain a generalized local variable frame and stack at this 793 // instruction offset, after execution. 794 if (evaluationCount == 0) 795 { 796 // First time we're passing by this instruction. 797 if (variablesAfter[instructionOffset] == null) 798 { 799 // There's not even a context at this index yet. 800 variablesAfter[instructionOffset] = new TracedVariables(variables); 801 stacksAfter[instructionOffset] = new TracedStack(stack); 802 } 803 else 804 { 805 // Reuse the context objects at this index. 806 variablesAfter[instructionOffset].initialize(variables); 807 stacksAfter[instructionOffset].copy(stack); 808 } 809 } 810 else 811 { 812 // Merge in the current context. 813 variablesAfter[instructionOffset].generalize(variables, true); 814 stacksAfter[instructionOffset].generalize(stack); 815 } 816 817 // Did the branch unit get called? 818 if (branchUnit.wasCalled()) 819 { 820 // Accumulate the branch targets at this offset. 821 branchTargetValues[instructionOffset] = branchTargetValues[instructionOffset] == null ? 822 branchTargets : 823 branchTargetValues[instructionOffset].generalize(branchTargets).instructionOffsetValue(); 824 825 // Are there no branch targets at all? 826 if (branchTargetCount == 0) 827 { 828 // Exit from this code block. 829 break; 830 } 831 832 // Accumulate the branch origins at the branch target offsets. 833 InstructionOffsetValue instructionOffsetValue = new InstructionOffsetValue(instructionOffset); 834 for (int index = 0; index < branchTargetCount; index++) 835 { 836 int branchTarget = branchTargets.instructionOffset(index); 837 branchOriginValues[branchTarget] = branchOriginValues[branchTarget] == null ? 838 instructionOffsetValue: 839 branchOriginValues[branchTarget].generalize(instructionOffsetValue).instructionOffsetValue(); 840 } 841 842 // Are there multiple branch targets? 843 if (branchTargetCount > 1) 844 { 845 // Push them on the execution stack and exit from this block. 846 for (int index = 0; index < branchTargetCount; index++) 847 { 848 if (DEBUG) System.out.println("Pushing alternative branch #"+index+" out of "+branchTargetCount+", from ["+instructionOffset+"] to ["+branchTargets.instructionOffset(index)+"]"); 849 850 pushInstructionBlock(new TracedVariables(variables), 851 new TracedStack(stack), 852 branchTargets.instructionOffset(index)); 853 } 854 855 break; 856 } 857 858 if (DEBUG) System.out.println("Definite branch from ["+instructionOffset+"] to ["+branchTargets.instructionOffset(0)+"]"); 859 } 860 861 // Just continue with the next instruction. 862 instructionOffset = branchTargets.instructionOffset(0); 863 864 // Is this a subroutine invocation? 865 if (instruction.opcode == InstructionConstants.OP_JSR || 866 instruction.opcode == InstructionConstants.OP_JSR_W) 867 { 868 // Evaluate the subroutine in another partial evaluator. 869 evaluateSubroutine(clazz, 870 method, 871 codeAttribute, 872 variables, 873 stack, 874 instructionOffset, 875 instructionBlockStack); 876 877 break; 878 } 879 else if (instruction.opcode == InstructionConstants.OP_RET) 880 { 881 // Let the partial evaluator that has called the subroutine 882 // handle the evaluation after the return. 883 pushCallingInstructionBlock(new TracedVariables(variables), 884 new TracedStack(stack), 885 instructionOffset); 886 break; 887 } 888 } 889 890 if (DEBUG) System.out.println("Ending processing of instruction block starting at ["+startOffset+"]"); 891 } 892 893 894 /** 895 * Evaluates a subroutine and its exception handlers, starting at the given 896 * offset and ending at a subroutine return instruction. 897 */ 898 private void evaluateSubroutine(Clazz clazz, 899 Method method, 900 CodeAttribute codeAttribute, 901 TracedVariables variables, 902 TracedStack stack, 903 int subroutineStart, 904 java.util.Stack instructionBlockStack) 905 { 906 int subroutineEnd = branchTargetFinder.subroutineEnd(subroutineStart); 907 908 if (DEBUG) System.out.println("Evaluating subroutine from "+subroutineStart+" to "+subroutineEnd); 909 910 // Create a temporary partial evaluator, so there are no conflicts 911 // with variables that are alive across subroutine invocations, between 912 // different invocations. 913 PartialEvaluator subroutinePartialEvaluator = 914 new PartialEvaluator(this); 915 916 subroutinePartialEvaluator.initializeArrays(codeAttribute); 917 918 // Evaluate the subroutine. 919 subroutinePartialEvaluator.evaluateInstructionBlockAndExceptionHandlers(clazz, 920 method, 921 codeAttribute, 922 variables, 923 stack, 924 subroutineStart, 925 subroutineEnd); 926 927 // Merge back the temporary partial evaluator. This way, we'll get 928 // the lowest common denominator of stacks and variables. 929 generalize(subroutinePartialEvaluator, 0, codeAttribute.u4codeLength); 930 931 if (DEBUG) System.out.println("Ending subroutine from "+subroutineStart+" to "+subroutineEnd); 932 } 933 934 935 /** 936 * Generalizes the results of this partial evaluator with those of another 937 * given partial evaluator, over a given range of instructions. 938 */ 939 private void generalize(PartialEvaluator other, 940 int codeStart, 941 int codeEnd) 942 { 943 if (DEBUG) System.out.println("Generalizing with temporary partial evaluation"); 944 945 for (int offset = codeStart; offset < codeEnd; offset++) 946 { 947 if (other.branchOriginValues[offset] != null) 948 { 949 branchOriginValues[offset] = branchOriginValues[offset] == null ? 950 other.branchOriginValues[offset] : 951 branchOriginValues[offset].generalize(other.branchOriginValues[offset]).instructionOffsetValue(); 952 } 953 954 if (other.isTraced(offset)) 955 { 956 if (other.branchTargetValues[offset] != null) 957 { 958 branchTargetValues[offset] = branchTargetValues[offset] == null ? 959 other.branchTargetValues[offset] : 960 branchTargetValues[offset].generalize(other.branchTargetValues[offset]).instructionOffsetValue(); 961 } 962 963 if (evaluationCounts[offset] == 0) 964 { 965 variablesBefore[offset] = other.variablesBefore[offset]; 966 stacksBefore[offset] = other.stacksBefore[offset]; 967 variablesAfter[offset] = other.variablesAfter[offset]; 968 stacksAfter[offset] = other.stacksAfter[offset]; 969 generalizedContexts[offset] = other.generalizedContexts[offset]; 970 evaluationCounts[offset] = other.evaluationCounts[offset]; 971 } 972 else 973 { 974 variablesBefore[offset].generalize(other.variablesBefore[offset], false); 975 stacksBefore[offset] .generalize(other.stacksBefore[offset]); 976 variablesAfter[offset] .generalize(other.variablesAfter[offset], false); 977 stacksAfter[offset] .generalize(other.stacksAfter[offset]); 978 //generalizedContexts[offset] 979 evaluationCounts[offset] += other.evaluationCounts[offset]; 980 } 981 } 982 } 983 } 984 985 986 /** 987 * Evaluates the exception handlers covering and targeting the given 988 * instruction range in the given code. 989 */ 990 private void evaluateExceptionHandlers(Clazz clazz, 991 Method method, 992 CodeAttribute codeAttribute, 993 int startOffset, 994 int endOffset) 995 { 996 if (DEBUG) System.out.println("Evaluating exceptions covering ["+startOffset+" -> "+endOffset+"]:"); 997 998 ExceptionHandlerFilter exceptionEvaluator = 999 new ExceptionHandlerFilter(startOffset, 1000 endOffset, 1001 this); 1002 1003 // Evaluate the exception catch blocks, until their entry variables 1004 // have stabilized. 1005 do 1006 { 1007 // Reset the flag to stop evaluating. 1008 evaluateExceptions = false; 1009 1010 // Evaluate all relevant exception catch blocks once. 1011 codeAttribute.exceptionsAccept(clazz, 1012 method, 1013 startOffset, 1014 endOffset, 1015 exceptionEvaluator); 1016 } 1017 while (evaluateExceptions); 1018 } 1019 1020 1021 // Implementations for ExceptionInfoVisitor. 1022 1023 public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) 1024 { 1025 int startPC = exceptionInfo.u2startPC; 1026 int endPC = exceptionInfo.u2endPC; 1027 1028 // Do we have to evaluate this exception catch block? 1029 if (isTraced(startPC, endPC)) 1030 { 1031 int handlerPC = exceptionInfo.u2handlerPC; 1032 int catchType = exceptionInfo.u2catchType; 1033 1034 if (DEBUG) System.out.println("Evaluating exception ["+startPC +" -> "+endPC +": "+handlerPC+"]:"); 1035 1036 // Reuse the existing variables and stack objects, ensuring the 1037 // right size. 1038 TracedVariables variables = new TracedVariables(codeAttribute.u2maxLocals); 1039 TracedStack stack = new TracedStack(codeAttribute.u2maxStack); 1040 1041 // Initialize the trace values. 1042 Value storeValue = new InstructionOffsetValue(AT_CATCH_ENTRY); 1043 variables.setProducerValue(storeValue); 1044 stack.setProducerValue(storeValue); 1045 1046 // Initialize the variables by generalizing the variables of the 1047 // try block. Make sure to include the results of the last 1048 // instruction for preverification. 1049 generalizeVariables(startPC, 1050 endPC, 1051 evaluateAllCode, 1052 variables); 1053 1054 // Initialize the the stack. 1055 //stack.push(valueFactory.createReference((ClassConstant)((ProgramClass)clazz).getConstant(exceptionInfo.u2catchType), false)); 1056 String catchClassName = catchType != 0 ? 1057 clazz.getClassName(catchType) : 1058 ClassConstants.INTERNAL_NAME_JAVA_LANG_THROWABLE; 1059 1060 Clazz catchClass = catchType != 0 ? 1061 ((ClassConstant)((ProgramClass)clazz).getConstant(catchType)).referencedClass : 1062 null; 1063 1064 stack.push(valueFactory.createReferenceValue(catchClassName, 1065 catchClass, 1066 false)); 1067 1068 int evaluationCount = evaluationCounts[handlerPC]; 1069 1070 // Evaluate the instructions, starting at the entry point. 1071 evaluateInstructionBlock(clazz, 1072 method, 1073 codeAttribute, 1074 variables, 1075 stack, 1076 handlerPC); 1077 1078 // Remember to evaluate all exception handlers once more. 1079 if (!evaluateExceptions) 1080 { 1081 evaluateExceptions = evaluationCount < evaluationCounts[handlerPC]; 1082 } 1083 } 1084// else if (evaluateAllCode) 1085// { 1086// if (DEBUG) System.out.println("No information for partial evaluation of exception ["+startPC +" -> "+endPC +": "+exceptionInfo.u2handlerPC+"] yet"); 1087// 1088// // We don't have any information on the try block yet, but we do 1089// // have to evaluate the exception handler. 1090// // Remember to evaluate all exception handlers once more. 1091// evaluateExceptions = true; 1092// } 1093 else 1094 { 1095 if (DEBUG) System.out.println("No information for partial evaluation of exception ["+startPC +" -> "+endPC +": "+exceptionInfo.u2handlerPC+"]"); 1096 } 1097 } 1098 1099 1100 // Small utility methods. 1101 1102 /** 1103 * Initializes the data structures for the variables, stack, etc. 1104 */ 1105 private void initializeArrays(CodeAttribute codeAttribute) 1106 { 1107 int codeLength = codeAttribute.u4codeLength; 1108 1109 // Create new arrays for storing information at each instruction offset. 1110 if (variablesAfter.length < codeLength) 1111 { 1112 // Create new arrays. 1113 branchOriginValues = new InstructionOffsetValue[codeLength]; 1114 branchTargetValues = new InstructionOffsetValue[codeLength]; 1115 variablesBefore = new TracedVariables[codeLength]; 1116 stacksBefore = new TracedStack[codeLength]; 1117 variablesAfter = new TracedVariables[codeLength]; 1118 stacksAfter = new TracedStack[codeLength]; 1119 generalizedContexts = new boolean[codeLength]; 1120 evaluationCounts = new int[codeLength]; 1121 } 1122 else 1123 { 1124 // Reset the arrays. 1125 Arrays.fill(branchOriginValues, null); 1126 Arrays.fill(branchTargetValues, null); 1127 Arrays.fill(generalizedContexts, false); 1128 Arrays.fill(evaluationCounts, 0); 1129 1130 for (int index = 0; index < codeLength; index++) 1131 { 1132 if (variablesBefore[index] != null) 1133 { 1134 variablesBefore[index].reset(codeAttribute.u2maxLocals); 1135 } 1136 1137 if (stacksBefore[index] != null) 1138 { 1139 stacksBefore[index].reset(codeAttribute.u2maxStack); 1140 } 1141 1142 if (variablesAfter[index] != null) 1143 { 1144 variablesAfter[index].reset(codeAttribute.u2maxLocals); 1145 } 1146 1147 if (stacksAfter[index] != null) 1148 { 1149 stacksAfter[index].reset(codeAttribute.u2maxStack); 1150 } 1151 } 1152 } 1153 } 1154 1155 1156 /** 1157 * Initializes the data structures for the variables, stack, etc. 1158 */ 1159 private void initializeParameters(Clazz clazz, 1160 Method method, 1161 CodeAttribute codeAttribute, 1162 TracedVariables variables) 1163 { 1164 // Create the method parameters. 1165 TracedVariables parameters = new TracedVariables(codeAttribute.u2maxLocals); 1166 1167 // Remember this instruction's offset with any stored value. 1168 Value storeValue = new InstructionOffsetValue(AT_METHOD_ENTRY); 1169 parameters.setProducerValue(storeValue); 1170 1171 // Initialize the method parameters. 1172 invocationUnit.enterMethod(clazz, method, parameters); 1173 1174 if (DEBUG) 1175 { 1176 System.out.println(" Params: "+parameters); 1177 } 1178 1179 // Initialize the variables with the parameters. 1180 variables.initialize(parameters); 1181 1182 // Set the store value of each parameter variable. 1183 InstructionOffsetValue atMethodEntry = new InstructionOffsetValue(AT_METHOD_ENTRY); 1184 1185 for (int index = 0; index < parameters.size(); index++) 1186 { 1187 variables.setProducerValue(index, atMethodEntry); 1188 } 1189 } 1190 1191 1192 /** 1193 * Generalize the local variable frames of a block of instructions. 1194 */ 1195 private void generalizeVariables(int startOffset, 1196 int endOffset, 1197 boolean includeAfterLastInstruction, 1198 TracedVariables generalizedVariables) 1199 { 1200 boolean first = true; 1201 int lastIndex = -1; 1202 1203 // Generalize the variables before each of the instructions in the block. 1204 for (int index = startOffset; index < endOffset; index++) 1205 { 1206 if (isTraced(index)) 1207 { 1208 TracedVariables tracedVariables = variablesBefore[index]; 1209 1210 if (first) 1211 { 1212 // Initialize the variables with the first traced local 1213 // variable frame. 1214 generalizedVariables.initialize(tracedVariables); 1215 1216 first = false; 1217 } 1218 else 1219 { 1220 // Generalize the variables with the traced local variable 1221 // frame. We can't use the return value, because local 1222 // generalization can be different a couple of times, 1223 // with the global generalization being the same. 1224 generalizedVariables.generalize(tracedVariables, false); 1225 } 1226 1227 lastIndex = index; 1228 } 1229 } 1230 1231 // Generalize the variables after the last instruction in the block, 1232 // if required. 1233 if (includeAfterLastInstruction && 1234 lastIndex >= 0) 1235 { 1236 TracedVariables tracedVariables = variablesAfter[lastIndex]; 1237 1238 if (first) 1239 { 1240 // Initialize the variables with the local variable frame. 1241 generalizedVariables.initialize(tracedVariables); 1242 } 1243 else 1244 { 1245 // Generalize the variables with the local variable frame. 1246 generalizedVariables.generalize(tracedVariables, false); 1247 } 1248 } 1249 1250 // Just clear the variables if there aren't any traced instructions 1251 // in the block. 1252 if (first) 1253 { 1254 generalizedVariables.reset(generalizedVariables.size()); 1255 } 1256 } 1257 1258 1259 private static class MyInstructionBlock 1260 { 1261 private TracedVariables variables; 1262 private TracedStack stack; 1263 private int startOffset; 1264 1265 1266 private MyInstructionBlock(TracedVariables variables, 1267 TracedStack stack, 1268 int startOffset) 1269 { 1270 this.variables = variables; 1271 this.stack = stack; 1272 this.startOffset = startOffset; 1273 } 1274 } 1275} 1276