BranchTargetFinder


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