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