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