1 /* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2009 Eric Lafortune (eric (at) 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 */ 21 package proguard.optimize.evaluation; 22 23 import proguard.classfile.*; 24 import proguard.classfile.attribute.*; 25 import proguard.classfile.attribute.visitor.AttributeVisitor; 26 import proguard.classfile.constant.RefConstant; 27 import proguard.classfile.constant.visitor.ConstantVisitor; 28 import proguard.classfile.editor.CodeAttributeEditor; 29 import proguard.classfile.instruction.*; 30 import proguard.classfile.instruction.visitor.InstructionVisitor; 31 import proguard.classfile.util.*; 32 import proguard.classfile.visitor.*; 33 import proguard.evaluation.*; 34 import proguard.evaluation.value.*; 35 import proguard.optimize.info.*; 36 37 /** 38 * This AttributeVisitor simplifies the code attributes that it visits, based 39 * on partial evaluation. 40 * 41 * @author Eric Lafortune 42 */ 43 public class EvaluationShrinker 44 extends SimplifiedVisitor 45 implements AttributeVisitor 46 { 47 //* 48 private static final boolean DEBUG_RESULTS = false; 49 private static final boolean DEBUG = false; 50 /*/ 51 private static boolean DEBUG_RESULTS = true; 52 private static boolean DEBUG = true; 53 //*/ 54 55 private final InstructionVisitor extraDeletedInstructionVisitor; 56 private final InstructionVisitor extraAddedInstructionVisitor; 57 58 private final PartialEvaluator partialEvaluator; 59 private final PartialEvaluator simplePartialEvaluator = new PartialEvaluator(); 60 private final SideEffectInstructionChecker sideEffectInstructionChecker = new SideEffectInstructionChecker(true); 61 private final MyUnusedParameterSimplifier unusedParameterSimplifier = new MyUnusedParameterSimplifier(); 62 private final MyProducerMarker producerMarker = new MyProducerMarker(); 63 private final MyStackConsistencyFixer stackConsistencyFixer = new MyStackConsistencyFixer(); 64 private final CodeAttributeEditor codeAttributeEditor = new CodeAttributeEditor(false); 65 66 private boolean[][] variablesNecessaryAfter = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_VARIABLES_SIZE]; 67 private boolean[][] stacksNecessaryAfter = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_STACK_SIZE]; 68 private boolean[][] stacksSimplifiedBefore = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_STACK_SIZE]; 69 private boolean[] instructionsNecessary = new boolean[ClassConstants.TYPICAL_CODE_LENGTH]; 70 71 private int maxMarkedOffset; 72 73 74 /** 75 * Creates a new EvaluationShrinker. 76 */ 77 public EvaluationShrinker() 78 { 79 this(new PartialEvaluator(), null, null); 80 } 81 82 83 /** 84 * Creates a new EvaluationShrinker. 85 * @param partialEvaluator the partial evaluator that will 86 * execute the code and provide 87 * information about the results. 88 * @param extraDeletedInstructionVisitor an optional extra visitor for all 89 * deleted instructions. 90 * @param extraAddedInstructionVisitor an optional extra visitor for all 91 * added instructions. 92 */ 93 public EvaluationShrinker(PartialEvaluator partialEvaluator, 94 InstructionVisitor extraDeletedInstructionVisitor, 95 InstructionVisitor extraAddedInstructionVisitor) 96 { 97 this.partialEvaluator = partialEvaluator; 98 this.extraDeletedInstructionVisitor = extraDeletedInstructionVisitor; 99 this.extraAddedInstructionVisitor = extraAddedInstructionVisitor; 100 } 101 102 103 // Implementations for AttributeVisitor. 104 105 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 106 107 108 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 109 { 110 // DEBUG = DEBUG_RESULTS = 111 // clazz.getName().equals("abc/Def") && 112 // method.getName(clazz).equals("abc"); 113 114 // TODO: Remove this when the evaluation shrinker has stabilized. 115 // Catch any unexpected exceptions from the actual visiting method. 116 try 117 { 118 // Process the code. 119 visitCodeAttribute0(clazz, method, codeAttribute); 120 } 121 catch (RuntimeException ex) 122 { 123 System.err.println("Unexpected error while shrinking instructions after partial evaluation:"); 124 System.err.println(" Class = ["+clazz.getName()+"]"); 125 System.err.println(" Method = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]"); 126 System.err.println(" Exception = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")"); 127 System.err.println("Not optimizing this method"); 128 129 if (DEBUG) 130 { 131 method.accept(clazz, new ClassPrinter()); 132 133 throw ex; 134 } 135 } 136 } 137 138 139 public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute) 140 { 141 if (DEBUG_RESULTS) 142 { 143 System.out.println(); 144 System.out.println("Class "+ClassUtil.externalClassName(clazz.getName())); 145 System.out.println("Method "+ClassUtil.externalFullMethodDescription(clazz.getName(), 146 0, 147 method.getName(clazz), 148 method.getDescriptor(clazz))); 149 } 150 151 // Initialize the necessary array. 152 initializeNecessary(codeAttribute); 153 154 // Evaluate the method. 155 partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute); 156 157 int codeLength = codeAttribute.u4codeLength; 158 159 // Reset the code changes. 160 codeAttributeEditor.reset(codeLength); 161 162 // Mark any unused method parameters on the stack. 163 if (DEBUG) System.out.println("Invocation simplification:"); 164 165 for (int offset = 0; offset < codeLength; offset++) 166 { 167 if (partialEvaluator.isTraced(offset)) 168 { 169 Instruction instruction = InstructionFactory.create(codeAttribute.code, 170 offset); 171 172 instruction.accept(clazz, method, codeAttribute, offset, unusedParameterSimplifier); 173 } 174 } 175 176 // Mark all essential instructions that have been encountered as used. 177 if (DEBUG) System.out.println("Usage initialization: "); 178 179 maxMarkedOffset = -1; 180 181 // The invocation of the "super" or "this" <init> method inside a 182 // constructor is always necessary. 183 int superInitializationOffset = partialEvaluator.superInitializationOffset(); 184 if (superInitializationOffset != PartialEvaluator.NONE) 185 { 186 if (DEBUG) System.out.print("(super.<init>)"); 187 188 markInstruction(superInitializationOffset); 189 } 190 191 // Also mark infinite loops and instructions that cause side effects. 192 for (int offset = 0; offset < codeLength; offset++) 193 { 194 if (partialEvaluator.isTraced(offset)) 195 { 196 Instruction instruction = InstructionFactory.create(codeAttribute.code, 197 offset); 198 199 // Mark that the instruction is necessary if it is an infinite loop. 200 if (instruction.opcode == InstructionConstants.OP_GOTO && 201 ((BranchInstruction)instruction).branchOffset == 0) 202 { 203 if (DEBUG) System.out.print("(infinite loop)"); 204 markInstruction(offset); 205 } 206 207 // Mark that the instruction is necessary if it has side effects. 208 else if (sideEffectInstructionChecker.hasSideEffects(clazz, 209 method, 210 codeAttribute, 211 offset, 212 instruction)) 213 { 214 markInstruction(offset); 215 } 216 } 217 } 218 if (DEBUG) System.out.println(); 219 220 221 // Globally mark instructions and their produced variables and stack 222 // entries on which necessary instructions depend. 223 // Instead of doing this recursively, we loop across all instructions, 224 // starting at the highest previously unmarked instruction that has 225 // been been marked. 226 if (DEBUG) System.out.println("Usage marking:"); 227 228 while (maxMarkedOffset >= 0) 229 { 230 int offset = maxMarkedOffset; 231 232 maxMarkedOffset = offset - 1; 233 234 if (partialEvaluator.isTraced(offset)) 235 { 236 if (isInstructionNecessary(offset)) 237 { 238 Instruction instruction = InstructionFactory.create(codeAttribute.code, 239 offset); 240 241 instruction.accept(clazz, method, codeAttribute, offset, producerMarker); 242 } 243 244 // Check if this instruction is a branch origin from a branch 245 // that straddles some marked code. 246 markStraddlingBranches(offset, 247 partialEvaluator.branchTargets(offset), 248 true); 249 250 // Check if this instruction is a branch target from a branch 251 // that straddles some marked code. 252 markStraddlingBranches(offset, 253 partialEvaluator.branchOrigins(offset), 254 false); 255 } 256 257 if (DEBUG) 258 { 259 if (maxMarkedOffset > offset) 260 { 261 System.out.println(" -> "+maxMarkedOffset); 262 } 263 } 264 } 265 if (DEBUG) System.out.println(); 266 267 268 // Mark variable initializations, even if they aren't strictly necessary. 269 // The virtual machine's verification step is not smart enough to see 270 // this, and may complain otherwise. 271 if (DEBUG) System.out.println("Initialization marking: "); 272 273 for (int offset = 0; offset < codeLength; offset++) 274 { 275 // Is it a variable initialization that hasn't been marked yet? 276 if (partialEvaluator.isTraced(offset) && 277 !isInstructionNecessary(offset)) 278 { 279 // Is the corresponding variable necessary anywhere in the code, 280 // accoriding to a simple partial evaluation? 281 int variableIndex = partialEvaluator.initializedVariable(offset); 282 if (variableIndex >= 0 && 283 isVariableInitializationNecessary(clazz, 284 method, 285 codeAttribute, 286 offset, 287 variableIndex)) 288 { 289 markInstruction(offset); 290 } 291 } 292 } 293 if (DEBUG) System.out.println(); 294 295 296 // Locally fix instructions, in order to keep the stack consistent. 297 if (DEBUG) System.out.println("Stack consistency fixing:"); 298 299 maxMarkedOffset = codeLength - 1; 300 301 while (maxMarkedOffset >= 0) 302 { 303 int offset = maxMarkedOffset; 304 305 maxMarkedOffset = offset - 1; 306 307 if (partialEvaluator.isTraced(offset)) 308 { 309 Instruction instruction = InstructionFactory.create(codeAttribute.code, 310 offset); 311 312 instruction.accept(clazz, method, codeAttribute, offset, stackConsistencyFixer); 313 314 // Check if this instruction is a branch origin from a branch 315 // that straddles some marked code. 316 markStraddlingBranches(offset, 317 partialEvaluator.branchTargets(offset), 318 true); 319 320 // Check if this instruction is a branch target from a branch 321 // that straddles some marked code. 322 markStraddlingBranches(offset, 323 partialEvaluator.branchOrigins(offset), 324 false); 325 } 326 } 327 if (DEBUG) System.out.println(); 328 329 330 // Replace traced but unmarked backward branches by infinite loops. 331 // The virtual machine's verification step is not smart enough to see 332 // the code isn't reachable, and may complain otherwise. 333 // Any clearly unreachable code will still be removed elsewhere. 334 if (DEBUG) System.out.println("Infinite loop fixing:"); 335 336 for (int offset = 0; offset < codeLength; offset++) 337 { 338 // Is it a traced but unmarked backward branch, without an unmarked 339 // straddling forward branch? Note that this is still a heuristic. 340 if (partialEvaluator.isTraced(offset) && 341 !isInstructionNecessary(offset) && 342 isAllSmallerThanOrEqual(partialEvaluator.branchTargets(offset), 343 offset) && 344 !isAnyUnnecessaryInstructionBranchingOver(lastNecessaryInstructionOffset(offset), 345 offset)) 346 { 347 replaceByInfiniteLoop(clazz, offset); 348 } 349 } 350 if (DEBUG) System.out.println(); 351 352 353 // Insert infinite loops after jumps to subroutines that don't return. 354 // The virtual machine's verification step is not smart enough to see 355 // the code isn't reachable, and may complain otherwise. 356 if (DEBUG) System.out.println("Non-returning subroutine fixing:"); 357 358 for (int offset = 0; offset < codeLength; offset++) 359 { 360 // Is it a traced but unmarked backward branch, without an unmarked 361 // straddling forward branch? Note that this is still a heuristic. 362 if (isInstructionNecessary(offset) && 363 partialEvaluator.isSubroutineInvocation(offset)) 364 { 365 Instruction instruction = InstructionFactory.create(codeAttribute.code, 366 offset); 367 368 int nextOffset = offset + instruction.length(offset); 369 if (!isInstructionNecessary(nextOffset)) 370 { 371 replaceByInfiniteLoop(clazz, nextOffset); 372 } 373 } 374 } 375 if (DEBUG) System.out.println(); 376 377 378 // Delete all instructions that are not used. 379 int offset = 0; 380 do 381 { 382 Instruction instruction = InstructionFactory.create(codeAttribute.code, 383 offset); 384 if (!isInstructionNecessary(offset)) 385 { 386 codeAttributeEditor.deleteInstruction(offset); 387 388 codeAttributeEditor.insertBeforeInstruction(offset, (Instruction)null); 389 codeAttributeEditor.replaceInstruction(offset, (Instruction)null); 390 codeAttributeEditor.insertAfterInstruction(offset, (Instruction)null); 391 392 // Visit the instruction, if required. 393 if (extraDeletedInstructionVisitor != null) 394 { 395 instruction.accept(clazz, method, codeAttribute, offset, extraDeletedInstructionVisitor); 396 } 397 } 398 399 offset += instruction.length(offset); 400 } 401 while (offset < codeLength); 402 403 404 if (DEBUG_RESULTS) 405 { 406 System.out.println("Simplification results:"); 407 408 offset = 0; 409 do 410 { 411 Instruction instruction = InstructionFactory.create(codeAttribute.code, 412 offset); 413 System.out.println((isInstructionNecessary(offset) ? " + " : " - ")+instruction.toString(offset)); 414 415 if (partialEvaluator.isTraced(offset)) 416 { 417 int initializationOffset = partialEvaluator.initializationOffset(offset); 418 if (initializationOffset != PartialEvaluator.NONE) 419 { 420 System.out.println(" is to be initialized at ["+initializationOffset+"]"); 421 } 422 423 InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset); 424 if (branchTargets != null) 425 { 426 System.out.println(" has overall been branching to "+branchTargets); 427 } 428 429 boolean deleted = codeAttributeEditor.deleted[offset]; 430 if (isInstructionNecessary(offset) && deleted) 431 { 432 System.out.println(" is deleted"); 433 } 434 435 Instruction preInsertion = codeAttributeEditor.preInsertions[offset]; 436 if (preInsertion != null) 437 { 438 System.out.println(" is preceded by: "+preInsertion); 439 } 440 441 Instruction replacement = codeAttributeEditor.replacements[offset]; 442 if (replacement != null) 443 { 444 System.out.println(" is replaced by: "+replacement); 445 } 446 447 Instruction postInsertion = codeAttributeEditor.postInsertions[offset]; 448 if (postInsertion != null) 449 { 450 System.out.println(" is followed by: "+postInsertion); 451 } 452 } 453 454 offset += instruction.length(offset); 455 } 456 while (offset < codeLength); 457 } 458 459 // Apply all accumulated changes to the code. 460 codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute); 461 } 462 463 464 /** 465 * This MemberVisitor marks stack entries that aren't necessary because 466 * parameters aren't used in the methods that are visited. 467 */ 468 private class MyUnusedParameterSimplifier 469 extends SimplifiedVisitor 470 implements InstructionVisitor, ConstantVisitor, MemberVisitor 471 { 472 private int invocationOffset; 473 private ConstantInstruction invocationInstruction; 474 475 476 // Implementations for InstructionVisitor. 477 478 public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {} 479 480 481 public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) 482 { 483 switch (constantInstruction.opcode) 484 { 485 case InstructionConstants.OP_INVOKEVIRTUAL: 486 case InstructionConstants.OP_INVOKESPECIAL: 487 case InstructionConstants.OP_INVOKESTATIC: 488 case InstructionConstants.OP_INVOKEINTERFACE: 489 this.invocationOffset = offset; 490 this.invocationInstruction = constantInstruction; 491 clazz.constantPoolEntryAccept(constantInstruction.constantIndex, this); 492 break; 493 } 494 } 495 496 497 // Implementations for ConstantVisitor. 498 499 public void visitAnyRefConstant(Clazz clazz, RefConstant refConstant) 500 { 501 refConstant.referencedMemberAccept(this); 502 } 503 504 505 // Implementations for MemberVisitor. 506 507 public void visitAnyMember(Clazz clazz, Member member) {} 508 509 510 public void visitProgramMethod(ProgramClass programClass, ProgramMethod programMethod) 511 { 512 // Get the total size of the parameters. 513 int parameterSize = ParameterUsageMarker.getParameterSize(programMethod); 514 515 // Make the method invocation static, if possible. 516 if ((programMethod.getAccessFlags() & ClassConstants.INTERNAL_ACC_STATIC) == 0 && 517 !ParameterUsageMarker.isParameterUsed(programMethod, 0)) 518 { 519 replaceByStaticInvocation(programClass, 520 invocationOffset, 521 invocationInstruction); 522 } 523 524 // Remove unused parameters. 525 for (int index = 0; index < parameterSize; index++) 526 { 527 if (!ParameterUsageMarker.isParameterUsed(programMethod, index)) 528 { 529 TracedStack stack = 530 partialEvaluator.getStackBefore(invocationOffset); 531 532 int stackIndex = stack.size() - parameterSize + index; 533 534 if (DEBUG) 535 { 536 System.out.println(" ["+invocationOffset+"] Ignoring parameter #"+index+" of "+programClass.getName()+"."+programMethod.getName(programClass)+programMethod.getDescriptor(programClass)+"] (stack entry #"+stackIndex+" ["+stack.getBottom(stackIndex)+"])"); 537 System.out.println(" Full stack: "+stack); 538 } 539 540 markStackSimplificationBefore(invocationOffset, stackIndex); 541 } 542 } 543 } 544 } 545 546 547 /** 548 * This InstructionVisitor marks the producing instructions and produced 549 * variables and stack entries of the instructions that it visits. 550 * Simplified method arguments are ignored. 551 */ 552 private class MyProducerMarker 553 extends SimplifiedVisitor 554 implements InstructionVisitor 555 { 556 // Implementations for InstructionVisitor. 557 558 public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) 559 { 560 markStackProducers(clazz, offset, instruction); 561 } 562 563 564 public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction) 565 { 566 switch (simpleInstruction.opcode) 567 { 568 case InstructionConstants.OP_DUP: 569 conditionallyMarkStackEntryProducers(offset, 0, 0); 570 conditionallyMarkStackEntryProducers(offset, 1, 0); 571 break; 572 case InstructionConstants.OP_DUP_X1: 573 conditionallyMarkStackEntryProducers(offset, 0, 0); 574 conditionallyMarkStackEntryProducers(offset, 1, 1); 575 conditionallyMarkStackEntryProducers(offset, 2, 0); 576 break; 577 case InstructionConstants.OP_DUP_X2: 578 conditionallyMarkStackEntryProducers(offset, 0, 0); 579 conditionallyMarkStackEntryProducers(offset, 1, 1); 580 conditionallyMarkStackEntryProducers(offset, 2, 2); 581 conditionallyMarkStackEntryProducers(offset, 3, 0); 582 break; 583 case InstructionConstants.OP_DUP2: 584 conditionallyMarkStackEntryProducers(offset, 0, 0); 585 conditionallyMarkStackEntryProducers(offset, 1, 1); 586 conditionallyMarkStackEntryProducers(offset, 2, 0); 587 conditionallyMarkStackEntryProducers(offset, 3, 1); 588 break; 589 case InstructionConstants.OP_DUP2_X1: 590 conditionallyMarkStackEntryProducers(offset, 0, 0); 591 conditionallyMarkStackEntryProducers(offset, 1, 1); 592 conditionallyMarkStackEntryProducers(offset, 2, 2); 593 conditionallyMarkStackEntryProducers(offset, 3, 0); 594 conditionallyMarkStackEntryProducers(offset, 4, 1); 595 break; 596 case InstructionConstants.OP_DUP2_X2: 597 conditionallyMarkStackEntryProducers(offset, 0, 0); 598 conditionallyMarkStackEntryProducers(offset, 1, 1); 599 conditionallyMarkStackEntryProducers(offset, 2, 2); 600 conditionallyMarkStackEntryProducers(offset, 3, 3); 601 conditionallyMarkStackEntryProducers(offset, 4, 0); 602 conditionallyMarkStackEntryProducers(offset, 5, 1); 603 break; 604 case InstructionConstants.OP_SWAP: 605 conditionallyMarkStackEntryProducers(offset, 0, 1); 606 conditionallyMarkStackEntryProducers(offset, 1, 0); 607 break; 608 default: 609 markStackProducers(clazz, offset, simpleInstruction); 610 break; 611 } 612 } 613 614 615 public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) 616 { 617 // Is the variable being loaded (or incremented)? 618 if (variableInstruction.opcode < InstructionConstants.OP_ISTORE) 619 { 620 markVariableProducers(offset, variableInstruction.variableIndex); 621 } 622 else 623 { 624 markStackProducers(clazz, offset, variableInstruction); 625 } 626 } 627 628 629 public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) 630 { 631 // Mark the initializer invocation, if this is a 'new' instruction. 632 if (constantInstruction.opcode == InstructionConstants.OP_NEW) 633 { 634 markInitialization(offset); 635 } 636 637 markStackProducers(clazz, offset, constantInstruction); 638 } 639 640 641 public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction) 642 { 643 // Explicitly mark the produced stack entry of a 'jsr' instruction, 644 // because the consuming 'astore' instruction of the subroutine is 645 // cleared every time it is traced. 646 if (branchInstruction.opcode == InstructionConstants.OP_JSR || 647 branchInstruction.opcode == InstructionConstants.OP_JSR_W) 648 { 649 markStackEntryAfter(offset, 0); 650 } 651 else 652 { 653 markStackProducers(clazz, offset, branchInstruction); 654 } 655 } 656 } 657 658 659 /** 660 * This InstructionVisitor fixes instructions locally, popping any unused 661 * produced stack entries after marked instructions, and popping produced 662 * stack entries and pushing missing stack entries instead of unmarked 663 * instructions. 664 */ 665 private class MyStackConsistencyFixer 666 extends SimplifiedVisitor 667 implements InstructionVisitor 668 { 669 // Implementations for InstructionVisitor. 670 671 public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) 672 { 673 // Has the instruction been marked? 674 if (isInstructionNecessary(offset)) 675 { 676 // Check all stack entries that are popped. 677 // Typical case: a freshly marked variable initialization that 678 // requires some value on the stack. 679 int popCount = instruction.stackPopCount(clazz); 680 if (popCount > 0) 681 { 682 TracedStack tracedStack = 683 partialEvaluator.getStackBefore(offset); 684 685 int top = tracedStack.size() - 1; 686 687 int requiredPushCount = 0; 688 for (int stackIndex = 0; stackIndex < popCount; stackIndex++) 689 { 690 // Is the stack entry required by other consumers? 691 if (!isStackSimplifiedBefore(offset, top - stackIndex) && 692 !isAnyStackEntryNecessaryAfter(tracedStack.getTopProducerValue(stackIndex).instructionOffsetValue(), top - stackIndex)) 693 { 694 // Remember to push it. 695 requiredPushCount++; 696 } 697 } 698 699 // Push some necessary stack entries. 700 if (requiredPushCount > 0) 701 { 702 if (DEBUG) System.out.println(" Inserting before marked consumer "+instruction.toString(offset)); 703 704 if (requiredPushCount > (instruction.isCategory2() ? 2 : 1)) 705 { 706 throw new IllegalArgumentException("Unsupported stack size increment ["+requiredPushCount+"]"); 707 } 708 709 insertPushInstructions(offset, false, tracedStack.getTop(0).computationalType()); 710 } 711 } 712 713 // Check all stack entries that are pushed. 714 // Typical case: a return value that wasn't really required and 715 // that should be popped. 716 int pushCount = instruction.stackPushCount(clazz); 717 if (pushCount > 0) 718 { 719 TracedStack tracedStack = 720 partialEvaluator.getStackAfter(offset); 721 722 int top = tracedStack.size() - 1; 723 724 int requiredPopCount = 0; 725 for (int stackIndex = 0; stackIndex < pushCount; stackIndex++) 726 { 727 // Is the stack entry required by consumers? 728 if (!isStackEntryNecessaryAfter(offset, top - stackIndex)) 729 { 730 // Remember to pop it. 731 requiredPopCount++; 732 } 733 } 734 735 // Pop the unnecessary stack entries. 736 if (requiredPopCount > 0) 737 { 738 if (DEBUG) System.out.println(" Inserting after marked producer "+instruction.toString(offset)); 739 740 insertPopInstructions(offset, false, requiredPopCount); 741 } 742 } 743 } 744 else 745 { 746 // Check all stack entries that would be popped. 747 // Typical case: a stack value that is required elsewhere and 748 // that still has to be popped. 749 int popCount = instruction.stackPopCount(clazz); 750 if (popCount > 0) 751 { 752 TracedStack tracedStack = 753 partialEvaluator.getStackBefore(offset); 754 755 int top = tracedStack.size() - 1; 756 757 int expectedPopCount = 0; 758 for (int stackIndex = 0; stackIndex < popCount; stackIndex++) 759 { 760 // Is the stack entry required by other consumers? 761 if (isAnyStackEntryNecessaryAfter(tracedStack.getTopProducerValue(stackIndex).instructionOffsetValue(), top - stackIndex)) 762 { 763 // Remember to pop it. 764 expectedPopCount++; 765 } 766 } 767 768 // Pop the unnecessary stack entries. 769 if (expectedPopCount > 0) 770 { 771 if (DEBUG) System.out.println(" Replacing unmarked consumer "+instruction.toString(offset)); 772 773 insertPopInstructions(offset, true, expectedPopCount); 774 } 775 } 776 777 // Check all stack entries that would be pushed. 778 // Typical case: never. 779 int pushCount = instruction.stackPushCount(clazz); 780 if (pushCount > 0) 781 { 782 TracedStack tracedStack = 783 partialEvaluator.getStackAfter(offset); 784 785 int top = tracedStack.size() - 1; 786 787 int expectedPushCount = 0; 788 for (int stackIndex = 0; stackIndex < pushCount; stackIndex++) 789 { 790 // Is the stack entry required by consumers? 791 if (isStackEntryNecessaryAfter(offset, top - stackIndex)) 792 { 793 // Remember to push it. 794 expectedPushCount++; 795 } 796 } 797 798 // Push some necessary stack entries. 799 if (expectedPushCount > 0) 800 { 801 if (DEBUG) System.out.println(" Replacing unmarked producer "+instruction.toString(offset)); 802 803 insertPushInstructions(offset, true, tracedStack.getTop(0).computationalType()); 804 } 805 } 806 } 807 } 808 809 810 public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction) 811 { 812 if (isInstructionNecessary(offset) && 813 isDupOrSwap(simpleInstruction)) 814 { 815 fixDupInstruction(clazz, codeAttribute, offset, simpleInstruction); 816 } 817 else 818 { 819 visitAnyInstruction(clazz, method, codeAttribute, offset, simpleInstruction); 820 } 821 } 822 } 823 824 825 // Small utility methods. 826 827 /** 828 * Marks the variable and the corresponding producing instructions 829 * of the consumer at the given offset. 830 * @param consumerOffset the offset of the consumer. 831 * @param variableIndex the index of the variable to be marked. 832 */ 833 private void markVariableProducers(int consumerOffset, 834 int variableIndex) 835 { 836 TracedVariables tracedVariables = 837 partialEvaluator.getVariablesBefore(consumerOffset); 838 839 // Mark the producer of the loaded value. 840 markVariableProducers(tracedVariables.getProducerValue(variableIndex).instructionOffsetValue(), 841 variableIndex); 842 } 843 844 845 /** 846 * Marks the variable and its producing instructions at the given offsets. 847 * @param producerOffsets the offsets of the producers to be marked. 848 * @param variableIndex the index of the variable to be marked. 849 */ 850 private void markVariableProducers(InstructionOffsetValue producerOffsets, 851 int variableIndex) 852 { 853 if (producerOffsets != null) 854 { 855 int offsetCount = producerOffsets.instructionOffsetCount(); 856 for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++) 857 { 858 // Make sure the variable and the instruction are marked 859 // at the producing offset. 860 int offset = producerOffsets.instructionOffset(offsetIndex); 861 862 markVariableAfter(offset, variableIndex); 863 markInstruction(offset); 864 } 865 } 866 } 867 868 869 /** 870 * Marks the stack entries and their producing instructions of the 871 * consumer at the given offset. 872 * @param clazz the containing class. 873 * @param consumerOffset the offset of the consumer. 874 * @param consumer the consumer of the stack entries. 875 */ 876 private void markStackProducers(Clazz clazz, 877 int consumerOffset, 878 Instruction consumer) 879 { 880 // Mark the producers of the popped values. 881 int popCount = consumer.stackPopCount(clazz); 882 for (int stackIndex = 0; stackIndex < popCount; stackIndex++) 883 { 884 markStackEntryProducers(consumerOffset, stackIndex); 885 } 886 } 887 888 889 /** 890 * Marks the stack entry and the corresponding producing instructions 891 * of the consumer at the given offset, if the stack entry of the 892 * consumer is marked. 893 * @param consumerOffset the offset of the consumer. 894 * @param consumerStackIndex the index of the stack entry to be checked 895 * (counting from the top). 896 * @param producerStackIndex the index of the stack entry to be marked 897 * (counting from the top). 898 */ 899 private void conditionallyMarkStackEntryProducers(int consumerOffset, 900 int consumerStackIndex, 901 int producerStackIndex) 902 { 903 int top = partialEvaluator.getStackAfter(consumerOffset).size() - 1; 904 905 if (isStackEntryNecessaryAfter(consumerOffset, top - consumerStackIndex)) 906 { 907 markStackEntryProducers(consumerOffset, producerStackIndex); 908 } 909 } 910 911 912 /** 913 * Marks the stack entry and the corresponding producing instructions 914 * of the consumer at the given offset. 915 * @param consumerOffset the offset of the consumer. 916 * @param stackIndex the index of the stack entry to be marked 917 * (counting from the top). 918 */ 919 private void markStackEntryProducers(int consumerOffset, 920 int stackIndex) 921 { 922 TracedStack tracedStack = 923 partialEvaluator.getStackBefore(consumerOffset); 924 925 int stackBottomIndex = tracedStack.size() - 1 - stackIndex; 926 927 if (!isStackSimplifiedBefore(consumerOffset, stackBottomIndex)) 928 { 929 markStackEntryProducers(tracedStack.getTopProducerValue(stackIndex).instructionOffsetValue(), 930 stackBottomIndex); 931 } 932 } 933 934 935 /** 936 * Marks the stack entry and its producing instructions at the given 937 * offsets. 938 * @param producerOffsets the offsets of the producers to be marked. 939 * @param stackIndex the index of the stack entry to be marked 940 * (counting from the bottom). 941 */ 942 private void markStackEntryProducers(InstructionOffsetValue producerOffsets, 943 int stackIndex) 944 { 945 if (producerOffsets != null) 946 { 947 int offsetCount = producerOffsets.instructionOffsetCount(); 948 for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++) 949 { 950 // Make sure the stack entry and the instruction are marked 951 // at the producing offset. 952 int offset = producerOffsets.instructionOffset(offsetIndex); 953 954 markStackEntryAfter(offset, stackIndex); 955 markInstruction(offset); 956 } 957 } 958 } 959 960 961 /** 962 * Marks the stack entry and its initializing instruction 963 * ('invokespecial *.<init>') for the given 'new' instruction offset. 964 * @param newInstructionOffset the offset of the 'new' instruction. 965 */ 966 private void markInitialization(int newInstructionOffset) 967 { 968 int initializationOffset = 969 partialEvaluator.initializationOffset(newInstructionOffset); 970 971 TracedStack tracedStack = 972 partialEvaluator.getStackAfter(newInstructionOffset); 973 974 markStackEntryAfter(initializationOffset, tracedStack.size() - 1); 975 markInstruction(initializationOffset); 976 } 977 978 979 /** 980 * Marks the branch instructions of straddling branches, if they straddle 981 * some code that has been marked. 982 * @param instructionOffset the offset of the branch origin or branch target. 983 * @param branchOffsets the offsets of the straddling branch targets 984 * or branch origins. 985 * @param isPointingToTargets <code>true</code> if the above offsets are 986 * branch targets, <code>false</code> if they 987 * are branch origins. 988 */ 989 private void markStraddlingBranches(int instructionOffset, 990 InstructionOffsetValue branchOffsets, 991 boolean isPointingToTargets) 992 { 993 if (branchOffsets != null) 994 { 995 // Loop over all branch offsets. 996 int branchCount = branchOffsets.instructionOffsetCount(); 997 for (int branchIndex = 0; branchIndex < branchCount; branchIndex++) 998 { 999 // Is the branch straddling forward any necessary instructions? 1000 int branchOffset = branchOffsets.instructionOffset(branchIndex); 1001 1002 // Is the offset pointing to a branch origin or to a branch target? 1003 if (isPointingToTargets) 1004 { 1005 markStraddlingBranch(instructionOffset, 1006 branchOffset, 1007 instructionOffset, 1008 branchOffset); 1009 } 1010 else 1011 { 1012 markStraddlingBranch(instructionOffset, 1013 branchOffset, 1014 branchOffset, 1015 instructionOffset); 1016 } 1017 } 1018 } 1019 } 1020 1021 1022 private void markStraddlingBranch(int instructionOffsetStart, 1023 int instructionOffsetEnd, 1024 int branchOrigin, 1025 int branchTarget) 1026 { 1027 if (!isInstructionNecessary(branchOrigin) && 1028 isAnyInstructionNecessary(instructionOffsetStart, instructionOffsetEnd)) 1029 { 1030 if (DEBUG) System.out.print("["+branchOrigin+"->"+branchTarget+"]"); 1031 1032 // Mark the branch instruction. 1033 markInstruction(branchOrigin); 1034 } 1035 } 1036 1037 1038 /** 1039 * Marks the specified instruction if it is a required dup/swap instruction, 1040 * replacing it by an appropriate variant if necessary. 1041 * @param clazz the class that is being checked. 1042 * @param codeAttribute the code that is being checked. 1043 * @param dupOffset the offset of the dup/swap instruction. 1044 * @param instruction the dup/swap instruction. 1045 */ 1046 private void fixDupInstruction(Clazz clazz, 1047 CodeAttribute codeAttribute, 1048 int dupOffset, 1049 Instruction instruction) 1050 { 1051 int top = partialEvaluator.getStackAfter(dupOffset).size() - 1; 1052 1053 byte oldOpcode = instruction.opcode; 1054 byte newOpcode = 0; 1055 1056 // Simplify the popping instruction if possible. 1057 switch (oldOpcode) 1058 { 1059 case InstructionConstants.OP_DUP: 1060 { 1061 boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0); 1062 boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1); 1063 1064 // Should either the original element or the copy be present? 1065 if (stackEntryPresent0 || 1066 stackEntryPresent1) 1067 { 1068 // Should both the original element and the copy be present? 1069 if (stackEntryPresent0 && 1070 stackEntryPresent1) 1071 { 1072 newOpcode = InstructionConstants.OP_DUP; 1073 } 1074 } 1075 break; 1076 } 1077 case InstructionConstants.OP_DUP_X1: 1078 { 1079 boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0); 1080 boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1); 1081 boolean stackEntryPresent2 = isStackEntryNecessaryAfter(dupOffset, top - 2); 1082 1083 // Should either the original element or the copy be present? 1084 if (stackEntryPresent0 || 1085 stackEntryPresent2) 1086 { 1087 // Should the copy be present? 1088 if (stackEntryPresent2) 1089 { 1090 // Compute the number of elements to be skipped. 1091 int skipCount = stackEntryPresent1 ? 1 : 0; 1092 1093 // Should the original element be present? 1094 if (stackEntryPresent0) 1095 { 1096 // Copy the original element. 1097 newOpcode = (byte)(InstructionConstants.OP_DUP + skipCount); 1098 } 1099 else if (skipCount == 1) 1100 { 1101 // Move the original element. 1102 newOpcode = InstructionConstants.OP_SWAP; 1103 } 1104 } 1105 } 1106 break; 1107 } 1108 case InstructionConstants.OP_DUP_X2: 1109 { 1110 boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0); 1111 boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1); 1112 boolean stackEntryPresent2 = isStackEntryNecessaryAfter(dupOffset, top - 2); 1113 boolean stackEntryPresent3 = isStackEntryNecessaryAfter(dupOffset, top - 3); 1114 1115 // Should either the original element or the copy be present? 1116 if (stackEntryPresent0 || 1117 stackEntryPresent3) 1118 { 1119 // Should the copy be present? 1120 if (stackEntryPresent3) 1121 { 1122 int skipCount = (stackEntryPresent1 ? 1 : 0) + 1123 (stackEntryPresent2 ? 1 : 0); 1124 1125 // Should the original element be present? 1126 if (stackEntryPresent0) 1127 { 1128 // Copy the original element. 1129 newOpcode = (byte)(InstructionConstants.OP_DUP + skipCount); 1130 } 1131 else if (skipCount == 1) 1132 { 1133 // Move the original element. 1134 newOpcode = InstructionConstants.OP_SWAP; 1135 } 1136 else if (skipCount == 2) 1137 { 1138 // We can't easily move the original element. 1139 throw new UnsupportedOperationException("Can't handle dup_x2 instruction moving original element across two elements at ["+dupOffset +"]"); 1140 } 1141 } 1142 } 1143 break; 1144 } 1145 case InstructionConstants.OP_DUP2: 1146 { 1147 boolean stackEntriesPresent01 = isStackEntriesNecessaryAfter(dupOffset, top - 0, top - 1); 1148 boolean stackEntriesPresent23 = isStackEntriesNecessaryAfter(dupOffset, top - 2, top - 3); 1149 1150 // Should either the original element or the copy be present? 1151 if (stackEntriesPresent01 || 1152 stackEntriesPresent23) 1153 { 1154 // Should both the original element and the copy be present? 1155 if (stackEntriesPresent01 && 1156 stackEntriesPresent23) 1157 { 1158 newOpcode = InstructionConstants.OP_DUP2; 1159 } 1160 } 1161 break; 1162 } 1163 case InstructionConstants.OP_DUP2_X1: 1164 { 1165 boolean stackEntriesPresent01 = isStackEntriesNecessaryAfter(dupOffset, top - 0, top - 1); 1166 boolean stackEntryPresent2 = isStackEntryNecessaryAfter(dupOffset, top - 2); 1167 boolean stackEntriesPresent34 = isStackEntriesNecessaryAfter(dupOffset, top - 3, top - 4); 1168 1169 // Should either the original element or the copy be present? 1170 if (stackEntriesPresent01 || 1171 stackEntriesPresent34) 1172 { 1173 // Should the copy be present? 1174 if (stackEntriesPresent34) 1175 { 1176 int skipCount = stackEntryPresent2 ? 1 : 0; 1177 1178 // Should the original element be present? 1179 if (stackEntriesPresent01) 1180 { 1181 // Copy the original element. 1182 newOpcode = (byte)(InstructionConstants.OP_DUP2 + skipCount); 1183 } 1184 else if (skipCount > 0) 1185 { 1186 // We can't easily move the original element. 1187 throw new UnsupportedOperationException("Can't handle dup2_x1 instruction moving original element across "+skipCount+" elements at ["+dupOffset +"]"); 1188 } 1189 } 1190 } 1191 break; 1192 } 1193 case InstructionConstants.OP_DUP2_X2: 1194 { 1195 boolean stackEntriesPresent01 = isStackEntriesNecessaryAfter(dupOffset, top - 0, top - 1); 1196 boolean stackEntryPresent2 = isStackEntryNecessaryAfter(dupOffset, top - 2); 1197 boolean stackEntryPresent3 = isStackEntryNecessaryAfter(dupOffset, top - 3); 1198 boolean stackEntriesPresent45 = isStackEntriesNecessaryAfter(dupOffset, top - 4, top - 5); 1199 1200 // Should either the original element or the copy be present? 1201 if (stackEntriesPresent01 || 1202 stackEntriesPresent45) 1203 { 1204 // Should the copy be present? 1205 if (stackEntriesPresent45) 1206 { 1207 int skipCount = (stackEntryPresent2 ? 1 : 0) + 1208 (stackEntryPresent3 ? 1 : 0); 1209 1210 // Should the original element be present? 1211 if (stackEntriesPresent01) 1212 { 1213 // Copy the original element. 1214 newOpcode = (byte)(InstructionConstants.OP_DUP2 + skipCount); 1215 } 1216 else if (skipCount > 0) 1217 { 1218 // We can't easily move the original element. 1219 throw new UnsupportedOperationException("Can't handle dup2_x2 instruction moving original element across "+skipCount+" elements at ["+dupOffset +"]"); 1220 } 1221 } 1222 } 1223 break; 1224 } 1225 case InstructionConstants.OP_SWAP: 1226 { 1227 boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0); 1228 boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1); 1229 1230 // Will either element be present? 1231 if (stackEntryPresent0 || 1232 stackEntryPresent1) 1233 { 1234 // Will both elements be present? 1235 if (stackEntryPresent0 && 1236 stackEntryPresent1) 1237 { 1238 newOpcode = InstructionConstants.OP_SWAP; 1239 } 1240 } 1241 break; 1242 } 1243 } 1244 1245 if (newOpcode == 0) 1246 { 1247 // Delete the instruction. 1248 codeAttributeEditor.deleteInstruction(dupOffset); 1249 1250 if (extraDeletedInstructionVisitor != null) 1251 { 1252 extraDeletedInstructionVisitor.visitSimpleInstruction(null, null, null, dupOffset, null); 1253 } 1254 1255 if (DEBUG) System.out.println(" Marking but deleting instruction "+instruction.toString(dupOffset)); 1256 } 1257 else if (newOpcode == oldOpcode) 1258 { 1259 // Leave the instruction unchanged. 1260 codeAttributeEditor.undeleteInstruction(dupOffset); 1261 1262 if (DEBUG) System.out.println(" Marking unchanged instruction "+instruction.toString(dupOffset)); 1263 } 1264 else 1265 { 1266 // Replace the instruction. 1267 Instruction replacementInstruction = new SimpleInstruction(newOpcode); 1268 codeAttributeEditor.replaceInstruction(dupOffset, 1269 replacementInstruction); 1270 1271 if (DEBUG) System.out.println(" Replacing instruction "+instruction.toString(dupOffset)+" by "+replacementInstruction.toString()); 1272 } 1273 } 1274 1275 1276 /** 1277 * Pushes a specified type of stack entry before or at the given offset. 1278 * The instruction is marked as necessary. 1279 */ 1280 private void insertPushInstructions(int offset, 1281 boolean replace, 1282 int computationalType) 1283 { 1284 // Mark this instruction. 1285 markInstruction(offset); 1286 1287 // Create a simple push instrucion. 1288 Instruction replacementInstruction = 1289 new SimpleInstruction(pushOpcode(computationalType)); 1290 1291 if (DEBUG) System.out.println(": "+replacementInstruction.toString(offset)); 1292 1293 // Replace or insert the push instruction. 1294 if (replace) 1295 { 1296 // Replace the push instruction. 1297 codeAttributeEditor.replaceInstruction(offset, replacementInstruction); 1298 } 1299 else 1300 { 1301 // Insert the push instruction. 1302 codeAttributeEditor.insertBeforeInstruction(offset, replacementInstruction); 1303 1304 if (extraAddedInstructionVisitor != null) 1305 { 1306 replacementInstruction.accept(null, null, null, offset, extraAddedInstructionVisitor); 1307 } 1308 } 1309 } 1310 1311 1312 /** 1313 * Returns the opcode of a push instruction corresponding to the given 1314 * computational type. 1315 * @param computationalType the computational type to be pushed on the stack. 1316 */ 1317 private byte pushOpcode(int computationalType) 1318 { 1319 switch (computationalType) 1320 { 1321 case Value.TYPE_INTEGER: return InstructionConstants.OP_ICONST_0; 1322 case Value.TYPE_LONG: return InstructionConstants.OP_LCONST_0; 1323 case Value.TYPE_FLOAT: return InstructionConstants.OP_FCONST_0; 1324 case Value.TYPE_DOUBLE: return InstructionConstants.OP_DCONST_0; 1325 case Value.TYPE_REFERENCE: 1326 case Value.TYPE_INSTRUCTION_OFFSET: return InstructionConstants.OP_ACONST_NULL; 1327 } 1328 1329 throw new IllegalArgumentException("No push opcode for computational type ["+computationalType+"]"); 1330 } 1331 1332 1333 /** 1334 * Pops the given number of stack entries at or after the given offset. 1335 * The instructions are marked as necessary. 1336 */ 1337 private void insertPopInstructions(int offset, boolean replace, int popCount) 1338 { 1339 // Mark this instruction. 1340 markInstruction(offset); 1341 1342 switch (popCount) 1343 { 1344 case 1: 1345 { 1346 // Replace or insert a single pop instruction. 1347 Instruction popInstruction = 1348 new SimpleInstruction(InstructionConstants.OP_POP); 1349 1350 if (replace) 1351 { 1352 codeAttributeEditor.replaceInstruction(offset, popInstruction); 1353 } 1354 else 1355 { 1356 codeAttributeEditor.insertAfterInstruction(offset, popInstruction); 1357 1358 if (extraAddedInstructionVisitor != null) 1359 { 1360 popInstruction.accept(null, null, null, offset, extraAddedInstructionVisitor); 1361 } 1362 } 1363 break; 1364 } 1365 case 2: 1366 { 1367 // Replace or insert a single pop2 instruction. 1368 Instruction popInstruction = 1369 new SimpleInstruction(InstructionConstants.OP_POP2); 1370 1371 if (replace) 1372 { 1373 codeAttributeEditor.replaceInstruction(offset, popInstruction); 1374 } 1375 else 1376 { 1377 codeAttributeEditor.insertAfterInstruction(offset, popInstruction); 1378 1379 if (extraAddedInstructionVisitor != null) 1380 { 1381 popInstruction.accept(null, null, null, offset, extraAddedInstructionVisitor); 1382 } 1383 } 1384 break; 1385 } 1386 default: 1387 { 1388 // Replace or insert the specified number of pop instructions. 1389 Instruction[] popInstructions = 1390 new Instruction[popCount / 2 + popCount % 2]; 1391 1392 Instruction popInstruction = 1393 new SimpleInstruction(InstructionConstants.OP_POP2); 1394 1395 for (int index = 0; index < popCount / 2; index++) 1396 { 1397 popInstructions[index] = popInstruction; 1398 } 1399 1400 if (popCount % 2 == 1) 1401 { 1402 popInstruction = 1403 new SimpleInstruction(InstructionConstants.OP_POP); 1404 1405 popInstructions[popCount / 2] = popInstruction; 1406 } 1407 1408 if (replace) 1409 { 1410 codeAttributeEditor.replaceInstruction(offset, popInstructions); 1411 1412 for (int index = 1; index < popInstructions.length; index++) 1413 { 1414 if (extraAddedInstructionVisitor != null) 1415 { 1416 popInstructions[index].accept(null, null, null, offset, extraAddedInstructionVisitor); 1417 } 1418 } 1419 } 1420 else 1421 { 1422 codeAttributeEditor.insertAfterInstruction(offset, popInstructions); 1423 1424 for (int index = 0; index < popInstructions.length; index++) 1425 { 1426 if (extraAddedInstructionVisitor != null) 1427 { 1428 popInstructions[index].accept(null, null, null, offset, extraAddedInstructionVisitor); 1429 } 1430 } 1431 } 1432 break; 1433 } 1434 } 1435 } 1436 1437 1438 /** 1439 * Replaces the instruction at a given offset by a static invocation. 1440 */ 1441 private void replaceByStaticInvocation(Clazz clazz, 1442 int offset, 1443 ConstantInstruction constantInstruction) 1444 { 1445 // Remember the replacement instruction. 1446 Instruction replacementInstruction = 1447 new ConstantInstruction(InstructionConstants.OP_INVOKESTATIC, 1448 constantInstruction.constantIndex).shrink(); 1449 1450 if (DEBUG) System.out.println(" Replacing by static invocation "+constantInstruction.toString(offset)+" -> "+replacementInstruction.toString()); 1451 1452 codeAttributeEditor.replaceInstruction(offset, replacementInstruction); 1453 } 1454 1455 1456 /** 1457 * Replaces the given instruction by an infinite loop. 1458 */ 1459 private void replaceByInfiniteLoop(Clazz clazz, 1460 int offset) 1461 { 1462 if (DEBUG) System.out.println(" Inserting infinite loop at ["+offset+"]"); 1463 1464 // Mark the instruction. 1465 markInstruction(offset); 1466 1467 // Replace the instruction by an infinite loop. 1468 Instruction replacementInstruction = 1469 new BranchInstruction(InstructionConstants.OP_GOTO, 0); 1470 1471 codeAttributeEditor.replaceInstruction(offset, replacementInstruction); 1472 } 1473 1474 1475 // Small utility methods. 1476 1477 /** 1478 * Returns whether the given instruction is a dup or swap instruction 1479 * (dup, dup_x1, dup_x2, dup2, dup2_x1, dup2_x2, swap). 1480 */ 1481 private boolean isDupOrSwap(Instruction instruction) 1482 { 1483 return instruction.opcode >= InstructionConstants.OP_DUP && 1484 instruction.opcode <= InstructionConstants.OP_SWAP; 1485 } 1486 1487 1488 /** 1489 * Returns whether the given instruction is a pop instruction 1490 * (pop, pop2). 1491 */ 1492 private boolean isPop(Instruction instruction) 1493 { 1494 return instruction.opcode == InstructionConstants.OP_POP || 1495 instruction.opcode == InstructionConstants.OP_POP2; 1496 } 1497 1498 1499 /** 1500 * Returns whether any traced but unnecessary instruction between the two 1501 * given offsets is branching over the second given offset. 1502 */ 1503 private boolean isAnyUnnecessaryInstructionBranchingOver(int instructionOffset1, 1504 int instructionOffset2) 1505 { 1506 for (int offset = instructionOffset1; offset < instructionOffset2; offset++) 1507 { 1508 // Is it a traced but unmarked straddling branch? 1509 if (partialEvaluator.isTraced(offset) && 1510 !isInstructionNecessary(offset) && 1511 isAnyLargerThan(partialEvaluator.branchTargets(offset), 1512 instructionOffset2)) 1513 { 1514 return true; 1515 } 1516 } 1517 1518 return false; 1519 } 1520 1521 1522 /** 1523 * Returns whether all of the given instruction offsets (at least one) 1524 * are smaller than or equal to the given offset. 1525 */ 1526 private boolean isAllSmallerThanOrEqual(InstructionOffsetValue instructionOffsets, 1527 int instructionOffset) 1528 { 1529 if (instructionOffsets != null) 1530 { 1531 // Loop over all instruction offsets. 1532 int branchCount = instructionOffsets.instructionOffsetCount(); 1533 if (branchCount > 0) 1534 { 1535 for (int branchIndex = 0; branchIndex < branchCount; branchIndex++) 1536 { 1537 // Is the offset larger than the reference offset? 1538 if (instructionOffsets.instructionOffset(branchIndex) > instructionOffset) 1539 { 1540 return false; 1541 } 1542 } 1543 1544 return true; 1545 } 1546 } 1547 1548 return false; 1549 } 1550 1551 1552 /** 1553 * Returns whether any of the given instruction offsets (at least one) 1554 * is larger than the given offset. 1555 */ 1556 private boolean isAnyLargerThan(InstructionOffsetValue instructionOffsets, 1557 int instructionOffset) 1558 { 1559 if (instructionOffsets != null) 1560 { 1561 // Loop over all instruction offsets. 1562 int branchCount = instructionOffsets.instructionOffsetCount(); 1563 if (branchCount > 0) 1564 { 1565 for (int branchIndex = 0; branchIndex < branchCount; branchIndex++) 1566 { 1567 // Is the offset larger than the reference offset? 1568 if (instructionOffsets.instructionOffset(branchIndex) > instructionOffset) 1569 { 1570 return true; 1571 } 1572 } 1573 } 1574 } 1575 1576 return false; 1577 } 1578 1579 1580 /** 1581 * Initializes the necessary data structure. 1582 */ 1583 private void initializeNecessary(CodeAttribute codeAttribute) 1584 { 1585 int codeLength = codeAttribute.u4codeLength; 1586 int maxLocals = codeAttribute.u2maxLocals; 1587 int maxStack = codeAttribute.u2maxStack; 1588 1589 // Create new arrays for storing information at each instruction offset. 1590 if (variablesNecessaryAfter.length < codeLength || 1591 variablesNecessaryAfter[0].length < maxLocals) 1592 { 1593 variablesNecessaryAfter = new boolean[codeLength][maxLocals]; 1594 } 1595 else 1596 { 1597 for (int offset = 0; offset < codeLength; offset++) 1598 { 1599 for (int index = 0; index < maxLocals; index++) 1600 { 1601 variablesNecessaryAfter[offset][index] = false; 1602 } 1603 } 1604 } 1605 1606 if (stacksNecessaryAfter.length < codeLength || 1607 stacksNecessaryAfter[0].length < maxStack) 1608 { 1609 stacksNecessaryAfter = new boolean[codeLength][maxStack]; 1610 } 1611 else 1612 { 1613 for (int offset = 0; offset < codeLength; offset++) 1614 { 1615 for (int index = 0; index < maxStack; index++) 1616 { 1617 stacksNecessaryAfter[offset][index] = false; 1618 } 1619 } 1620 } 1621 1622 if (stacksSimplifiedBefore.length < codeLength || 1623 stacksSimplifiedBefore[0].length < maxStack) 1624 { 1625 stacksSimplifiedBefore = new boolean[codeLength][maxStack]; 1626 } 1627 else 1628 { 1629 for (int offset = 0; offset < codeLength; offset++) 1630 { 1631 for (int index = 0; index < maxStack; index++) 1632 { 1633 stacksSimplifiedBefore[offset][index] = false; 1634 } 1635 } 1636 } 1637 1638 if (instructionsNecessary.length < codeLength) 1639 { 1640 instructionsNecessary = new boolean[codeLength]; 1641 } 1642 else 1643 { 1644 for (int index = 0; index < codeLength; index++) 1645 { 1646 instructionsNecessary[index] = false; 1647 } 1648 } 1649 } 1650 1651 1652 /** 1653 * Returns whether the given stack entry is present after execution of the 1654 * instruction at the given offset. 1655 */ 1656 private boolean isStackEntriesNecessaryAfter(int instructionOffset, 1657 int stackIndex1, 1658 int stackIndex2) 1659 { 1660 boolean present1 = isStackEntryNecessaryAfter(instructionOffset, stackIndex1); 1661 boolean present2 = isStackEntryNecessaryAfter(instructionOffset, stackIndex2); 1662 1663 // if (present1 ^ present2) 1664 // { 1665 // throw new UnsupportedOperationException("Can't handle partial use of dup2 instructions"); 1666 // } 1667 1668 return present1 || present2; 1669 } 1670 1671 1672 /** 1673 * Returns whether the specified variable must be initialized at the 1674 * specified offset, according to the verifier of the JVM. 1675 */ 1676 private boolean isVariableInitializationNecessary(Clazz clazz, 1677 Method method, 1678 CodeAttribute codeAttribute, 1679 int initializationOffset, 1680 int variableIndex) 1681 { 1682 int codeLength = codeAttribute.u4codeLength; 1683 1684 // Is the variable necessary anywhere at all? 1685 if (isVariableNecessaryAfterAny(0, codeLength, variableIndex)) 1686 { 1687 if (DEBUG) System.out.println("Simple partial evaluation for initialization of variable v"+variableIndex+" at ["+initializationOffset+"]"); 1688 1689 // Lazily compute perform simple partial evaluation, the way the 1690 // JVM preverifier would do it. 1691 simplePartialEvaluator.visitCodeAttribute(clazz, method, codeAttribute); 1692 1693 if (DEBUG) System.out.println("End of simple partial evaluation for initialization of variable v"+variableIndex+" at ["+initializationOffset+"]"); 1694 1695 // Check if the variable is necessary elsewhere. 1696 for (int offset = 0; offset < codeLength; offset++) 1697 { 1698 if (isInstructionNecessary(offset)) 1699 { 1700 Value producer = partialEvaluator.getVariablesBefore(offset).getProducerValue(variableIndex); 1701 if (producer != null) 1702 { 1703 Value simpleProducer = simplePartialEvaluator.getVariablesBefore(offset).getProducerValue(variableIndex); 1704 if (simpleProducer != null) 1705 { 1706 InstructionOffsetValue producerOffsets = 1707 producer.instructionOffsetValue(); 1708 InstructionOffsetValue simpleProducerOffsets = 1709 simpleProducer.instructionOffsetValue(); 1710 1711 // Does the sophisticated partial evaluation have fewer 1712 // producers than the simple one? 1713 // And does the simple partial evaluation point to an 1714 // initialization of the variable? 1715 if (producerOffsets.instructionOffsetCount() < 1716 simpleProducerOffsets.instructionOffsetCount() && 1717 isVariableNecessaryAfterAny(producerOffsets, variableIndex) && 1718 simpleProducerOffsets.contains(initializationOffset)) 1719 { 1720 // Then the initialization is necessary. 1721 return true; 1722 } 1723 } 1724 } 1725 } 1726 } 1727 } 1728 1729 return false; 1730 } 1731 1732 1733 private void markVariableAfter(int instructionOffset, 1734 int variableIndex) 1735 { 1736 if (!isVariableNecessaryAfter(instructionOffset, variableIndex)) 1737 { 1738 if (DEBUG) System.out.print("["+instructionOffset+".v"+variableIndex+"],"); 1739 1740 variablesNecessaryAfter[instructionOffset][variableIndex] = true; 1741 1742 if (maxMarkedOffset < instructionOffset) 1743 { 1744 maxMarkedOffset = instructionOffset; 1745 } 1746 } 1747 } 1748 1749 1750 /** 1751 * Returns whether the specified variable is ever necessary after any 1752 * instruction in the specified block. 1753 */ 1754 private boolean isVariableNecessaryAfterAny(int startOffset, 1755 int endOffset, 1756 int variableIndex) 1757 { 1758 for (int offset = startOffset; offset < endOffset; offset++) 1759 { 1760 if (isVariableNecessaryAfter(offset, variableIndex)) 1761 { 1762 return true; 1763 } 1764 } 1765 1766 return false; 1767 } 1768 1769 1770 /** 1771 * Returns whether the specified variable is ever necessary after any 1772 * instruction in the specified set of instructions offsets. 1773 */ 1774 private boolean isVariableNecessaryAfterAny(InstructionOffsetValue instructionOffsetValue, 1775 int variableIndex) 1776 { 1777 int count = instructionOffsetValue.instructionOffsetCount(); 1778 1779 for (int index = 0; index < count; index++) 1780 { 1781 if (isVariableNecessaryAfter(instructionOffsetValue.instructionOffset(index), 1782 variableIndex)) 1783 { 1784 return true; 1785 } 1786 } 1787 1788 return false; 1789 } 1790 1791 1792 private boolean isVariableNecessaryAfter(int instructionOffset, 1793 int variableIndex) 1794 { 1795 return instructionOffset == PartialEvaluator.AT_METHOD_ENTRY || 1796 variablesNecessaryAfter[instructionOffset][variableIndex]; 1797 } 1798 1799 1800 private void markStackEntryAfter(int instructionOffset, 1801 int stackIndex) 1802 { 1803 if (!isStackEntryNecessaryAfter(instructionOffset, stackIndex)) 1804 { 1805 if (DEBUG) System.out.print("["+instructionOffset+".s"+stackIndex+"],"); 1806 1807 stacksNecessaryAfter[instructionOffset][stackIndex] = true; 1808 1809 if (maxMarkedOffset < instructionOffset) 1810 { 1811 maxMarkedOffset = instructionOffset; 1812 } 1813 } 1814 } 1815 1816 1817 private boolean isAnyStackEntryNecessaryAfter(InstructionOffsetValue instructionOffsets, 1818 int stackIndex) 1819 { 1820 int offsetCount = instructionOffsets.instructionOffsetCount(); 1821 1822 for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++) 1823 { 1824 if (isStackEntryNecessaryAfter(instructionOffsets.instructionOffset(offsetIndex), stackIndex)) 1825 { 1826 return true; 1827 } 1828 } 1829 1830 return false; 1831 } 1832 1833 1834 private boolean isStackEntryNecessaryAfter(int instructionOffset, 1835 int stackIndex) 1836 { 1837 return instructionOffset == PartialEvaluator.AT_CATCH_ENTRY || 1838 stacksNecessaryAfter[instructionOffset][stackIndex]; 1839 } 1840 1841 1842 private void markStackSimplificationBefore(int instructionOffset, 1843 int stackIndex) 1844 { 1845 stacksSimplifiedBefore[instructionOffset][stackIndex] = true; 1846 } 1847 1848 1849 private boolean isStackSimplifiedBefore(int instructionOffset, 1850 int stackIndex) 1851 { 1852 return stacksSimplifiedBefore[instructionOffset][stackIndex]; 1853 } 1854 1855 1856 private void markInstruction(int instructionOffset) 1857 { 1858 if (!isInstructionNecessary(instructionOffset)) 1859 { 1860 if (DEBUG) System.out.print(instructionOffset+","); 1861 1862 instructionsNecessary[instructionOffset] = true; 1863 1864 if (maxMarkedOffset < instructionOffset) 1865 { 1866 maxMarkedOffset = instructionOffset; 1867 } 1868 } 1869 } 1870 1871 1872 private boolean isAnyInstructionNecessary(int instructionOffset1, 1873 int instructionOffset2) 1874 { 1875 for (int instructionOffset = instructionOffset1; 1876 instructionOffset < instructionOffset2; 1877 instructionOffset++) 1878 { 1879 if (isInstructionNecessary(instructionOffset)) 1880 { 1881 return true; 1882 } 1883 } 1884 1885 return false; 1886 } 1887 1888 1889 /** 1890 * Returns the highest offset of an instruction that has been marked as 1891 * necessary, before the given offset. 1892 */ 1893 private int lastNecessaryInstructionOffset(int instructionOffset) 1894 { 1895 for (int offset = instructionOffset-1; offset >= 0; offset--) 1896 { 1897 if (isInstructionNecessary(instructionOffset)) 1898 { 1899 return offset; 1900 } 1901 } 1902 1903 return 0; 1904 } 1905 1906 1907 private boolean isInstructionNecessary(int instructionOffset) 1908 { 1909 return instructionOffset == PartialEvaluator.AT_METHOD_ENTRY || 1910 instructionsNecessary[instructionOffset]; 1911 } 1912 }
