001: /*
002: * ProGuard -- shrinking, optimization, obfuscation, and preverification
003: * of Java bytecode.
004: *
005: * Copyright (c) 2002-2007 Eric Lafortune (eric@graphics.cornell.edu)
006: *
007: * This program is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU General Public License as published by the Free
009: * Software Foundation; either version 2 of the License, or (at your option)
010: * any later version.
011: *
012: * This program is distributed in the hope that it will be useful, but WITHOUT
013: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
014: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
015: * more details.
016: *
017: * You should have received a copy of the GNU General Public License along
018: * with this program; if not, write to the Free Software Foundation, Inc.,
019: * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
020: */
021: package proguard.optimize.peephole;
022:
023: import proguard.classfile.*;
024: import proguard.classfile.attribute.*;
025: import proguard.classfile.attribute.visitor.*;
026: import proguard.classfile.constant.*;
027: import proguard.classfile.constant.visitor.ConstantVisitor;
028: import proguard.classfile.instruction.*;
029: import proguard.classfile.instruction.visitor.InstructionVisitor;
030: import proguard.classfile.util.SimplifiedVisitor;
031:
032: /**
033: * This AttributeVisitor finds all instruction offsets, branch targets, and
034: * exception targets in the CodeAttribute objects that it visits.
035: *
036: * @author Eric Lafortune
037: */
038: public class BranchTargetFinder extends SimplifiedVisitor implements
039: AttributeVisitor, InstructionVisitor, ExceptionInfoVisitor,
040: ConstantVisitor {
041: //*
042: private static final boolean DEBUG = false;
043: /*/
044: private static boolean DEBUG = true;
045: //*/
046:
047: public static final int NONE = -2;
048: public static final int AT_METHOD_ENTRY = -1;
049:
050: private static final short INSTRUCTION = 1 << 0;
051: private static final short BRANCH_ORIGIN = 1 << 1;
052: private static final short BRANCH_TARGET = 1 << 2;
053: private static final short AFTER_BRANCH = 1 << 3;
054: private static final short EXCEPTION_START = 1 << 4;
055: private static final short EXCEPTION_END = 1 << 5;
056: private static final short EXCEPTION_HANDLER = 1 << 6;
057: private static final short SUBROUTINE_INVOCATION = 1 << 7;
058: private static final short SUBROUTINE_RETURNING = 1 << 8;
059:
060: private static final int MAXIMUM_CREATION_OFFSETS = 32;
061:
062: private short[] instructionMarks = new short[ClassConstants.TYPICAL_CODE_LENGTH + 1];
063: private int[] subroutineStarts = new int[ClassConstants.TYPICAL_CODE_LENGTH];
064: private int[] subroutineEnds = new int[ClassConstants.TYPICAL_CODE_LENGTH];
065: private int[] creationOffsets = new int[ClassConstants.TYPICAL_CODE_LENGTH];
066: private int[] initializationOffsets = new int[ClassConstants.TYPICAL_CODE_LENGTH];
067: private int super InitializationOffset;
068:
069: private int currentSubroutineStart;
070: private int currentSubroutineEnd;
071: private final int[] recentCreationOffsets = new int[MAXIMUM_CREATION_OFFSETS];
072: private int recentCreationOffsetIndex;
073: private boolean isInitializer;
074:
075: /**
076: * Returns whether there is an instruction at the given offset in the
077: * CodeAttribute that was visited most recently.
078: */
079: public boolean isInstruction(int offset) {
080: return (instructionMarks[offset] & INSTRUCTION) != 0;
081: }
082:
083: /**
084: * Returns whether the instruction at the given offset is the target of
085: * any kind in the CodeAttribute that was visited most recently.
086: */
087: public boolean isTarget(int offset) {
088: return offset == 0
089: || (instructionMarks[offset] & (BRANCH_TARGET
090: | EXCEPTION_START | EXCEPTION_END | EXCEPTION_HANDLER)) != 0;
091: }
092:
093: /**
094: * Returns whether the instruction at the given offset is the origin of a
095: * branch instruction in the CodeAttribute that was visited most recently.
096: */
097: public boolean isBranchOrigin(int offset) {
098: return (instructionMarks[offset] & BRANCH_ORIGIN) != 0;
099: }
100:
101: /**
102: * Returns whether the instruction at the given offset is the target of a
103: * branch instruction in the CodeAttribute that was visited most recently.
104: */
105: public boolean isBranchTarget(int offset) {
106: return (instructionMarks[offset] & BRANCH_TARGET) != 0;
107: }
108:
109: /**
110: * Returns whether the instruction at the given offset comes right after a
111: * definite branch instruction in the CodeAttribute that was visited most
112: * recently.
113: */
114: public boolean isAfterBranch(int offset) {
115: return (instructionMarks[offset] & AFTER_BRANCH) != 0;
116: }
117:
118: /**
119: * Returns whether the instruction at the given offset is the start of an
120: * exception try block in the CodeAttribute that was visited most recently.
121: */
122: public boolean isExceptionStart(int offset) {
123: return (instructionMarks[offset] & EXCEPTION_START) != 0;
124: }
125:
126: /**
127: * Returns whether the instruction at the given offset is the end of an
128: * exception try block in the CodeAttribute that was visited most recently.
129: */
130: public boolean isExceptionEnd(int offset) {
131: return (instructionMarks[offset] & EXCEPTION_END) != 0;
132: }
133:
134: /**
135: * Returns whether the instruction at the given offset is the start of an
136: * exception catch block in the CodeAttribute that was visited most recently.
137: */
138: public boolean isExceptionHandler(int offset) {
139: return (instructionMarks[offset] & EXCEPTION_HANDLER) != 0;
140: }
141:
142: /**
143: * Returns whether the instruction at the given offset is a subroutine
144: * invocation in the CodeAttribute that was visited most recently.
145: */
146: public boolean isSubroutineInvocation(int offset) {
147: return (instructionMarks[offset] & SUBROUTINE_INVOCATION) != 0;
148: }
149:
150: /**
151: * Returns whether the instruction at the given offset is the start of a
152: * subroutine in the CodeAttribute that was visited most recently.
153: */
154: public boolean isSubroutineStart(int offset) {
155: return subroutineStarts[offset] == offset;
156: }
157:
158: /**
159: * Returns whether the instruction at the given offset is part of a
160: * subroutine in the CodeAttribute that was visited most recently.
161: */
162: public boolean isSubroutine(int offset) {
163: return subroutineStarts[offset] != NONE;
164: }
165:
166: /**
167: * Returns whether the subroutine at the given offset is ever returning
168: * by means of a regular 'ret' instruction.
169: */
170: public boolean isSubroutineReturning(int offset) {
171: return (instructionMarks[offset] & SUBROUTINE_RETURNING) != 0;
172: }
173:
174: /**
175: * Returns the start offset of the subroutine at the given offset, in the
176: * CodeAttribute that was visited most recently.
177: */
178: public int subroutineStart(int offset) {
179: return subroutineStarts[offset];
180: }
181:
182: /**
183: * Returns the offset after the subroutine at the given offset, in the
184: * CodeAttribute that was visited most recently.
185: */
186: public int subroutineEnd(int offset) {
187: return subroutineEnds[offset];
188: }
189:
190: /**
191: * Returns whether the instruction at the given offset is a 'new'
192: * instruction, in the CodeAttribute that was visited most recently.
193: */
194: public boolean isNew(int offset) {
195: return initializationOffsets[offset] != NONE;
196: }
197:
198: /**
199: * Returns the instruction offset at which the object instance that is
200: * created at the given 'new' instruction offset is initialized, or
201: * <code>NONE</code> if it is not being created.
202: */
203: public int initializationOffset(int offset) {
204: return initializationOffsets[offset];
205: }
206:
207: /**
208: * Returns whether the method is an instance initializer, in the
209: * CodeAttribute that was visited most recently.
210: */
211: public boolean isInitializer() {
212: return super InitializationOffset != NONE;
213: }
214:
215: /**
216: * Returns the instruction offset at which this initializer is calling
217: * the "super" or "this" initializer method, or <code>NONE</code> if it is
218: * not an initializer.
219: */
220: public int super InitializationOffset() {
221: return super InitializationOffset;
222: }
223:
224: /**
225: * Returns whether the instruction at the given offset is the special
226: * invocation of an instance initializer, in the CodeAttribute that was
227: * visited most recently.
228: */
229: public boolean isInitializer(int offset) {
230: return creationOffsets[offset] != NONE;
231: }
232:
233: /**
234: * Returns the offset of the 'new' instruction that corresponds to the
235: * invocation of the instance initializer at the given offset, or
236: * <code>AT_METHOD_ENTRY</code> if the invocation is calling the "super" or
237: * "this" initializer method, , or <code>NONE</code> if it is not a 'new'
238: * instruction.
239: */
240: public int creationOffset(int offset) {
241: return creationOffsets[offset];
242: }
243:
244: // Implementations for AttributeVisitor.
245:
246: public void visitAnyAttribute(Clazz clazz, Attribute attribute) {
247: }
248:
249: public void visitCodeAttribute(Clazz clazz, Method method,
250: CodeAttribute codeAttribute) {
251: // DEBUG =
252: // clazz.getName().equals("abc/Def") &&
253: // method.getName(clazz).equals("abc");
254:
255: // Make sure there are sufficiently large arrays.
256: int codeLength = codeAttribute.u4codeLength;
257: if (subroutineStarts.length < codeLength) {
258: // Create new arrays.
259: instructionMarks = new short[codeLength + 1];
260: subroutineStarts = new int[codeLength];
261: subroutineEnds = new int[codeLength];
262: creationOffsets = new int[codeLength];
263: initializationOffsets = new int[codeLength];
264:
265: // Reset the arrays.
266: for (int index = 0; index < codeLength; index++) {
267: subroutineStarts[index] = NONE;
268: subroutineEnds[index] = NONE;
269: creationOffsets[index] = NONE;
270: initializationOffsets[index] = NONE;
271: }
272: } else {
273: // Reset the arrays.
274: for (int index = 0; index < codeLength; index++) {
275: instructionMarks[index] = 0;
276: subroutineStarts[index] = NONE;
277: subroutineEnds[index] = NONE;
278: creationOffsets[index] = NONE;
279: initializationOffsets[index] = NONE;
280: }
281:
282: instructionMarks[codeLength] = 0;
283: }
284:
285: super InitializationOffset = NONE;
286:
287: // We're not starting in a subroutine.
288: currentSubroutineStart = NONE;
289: currentSubroutineEnd = NONE;
290:
291: recentCreationOffsetIndex = 0;
292:
293: // Initialize the stack of 'new' instruction offsets if this method is
294: // an instance initializer.
295: if (method.getName(clazz).equals(
296: ClassConstants.INTERNAL_METHOD_NAME_INIT)) {
297: recentCreationOffsets[recentCreationOffsetIndex++] = AT_METHOD_ENTRY;
298: }
299:
300: // The end of the code is a branch target sentinel.
301: instructionMarks[codeLength] = BRANCH_TARGET;
302:
303: // Mark branch targets by going over all instructions.
304: codeAttribute.instructionsAccept(clazz, method, this );
305:
306: // Mark branch targets in the exception table.
307: codeAttribute.exceptionsAccept(clazz, method, this );
308:
309: // Fill out any gaps in the subroutine starts and the subroutine ends
310: // and subroutine returning flags, working backward.
311:
312: // We're not starting in a subroutine.
313: int subroutineStart = NONE;
314: int subroutineEnd = codeLength;
315: boolean subroutineReturning = false;
316:
317: for (int index = codeLength - 1; index >= 0; index--) {
318: if (isInstruction(index)) {
319: // Are we inside a previously marked subroutine?
320: if (subroutineStarts[index] != NONE) {
321: // Update the current subroutine start.
322: subroutineStart = subroutineStarts[index];
323: } else if (subroutineStart != NONE) {
324: // Mark the subroutine start.
325: subroutineStarts[index] = subroutineStart;
326: }
327:
328: // Did we reach the start of the subroutine.
329: if (isSubroutineStart(index)) {
330: // Stop marking it.
331: subroutineStart = NONE;
332: }
333:
334: // Are we inside a subroutine?
335: if (isSubroutine(index)) {
336: // Mark the subroutine end.
337: subroutineEnds[index] = subroutineEnd;
338:
339: // Update or mark the subroutine returning flag.
340: if (isSubroutineReturning(index)) {
341: subroutineReturning = true;
342: } else if (subroutineReturning) {
343: instructionMarks[index] |= SUBROUTINE_RETURNING;
344: }
345: } else {
346: // Update the subroutine end and returning flag.
347: subroutineEnd = index;
348: subroutineReturning = false;
349: }
350: }
351: }
352:
353: if (DEBUG) {
354: System.out.println();
355: System.out.println("Branch targets: " + clazz.getName()
356: + "." + method.getName(clazz)
357: + method.getDescriptor(clazz));
358:
359: for (int index = 0; index < codeLength; index++) {
360: if (isInstruction(index)) {
361: System.out
362: .println(""
363: + (isBranchOrigin(index) ? 'B'
364: : '-')
365: + (isBranchTarget(index) ? 'T'
366: : '-')
367: + (isExceptionStart(index) ? 'E'
368: : '-')
369: + (isExceptionEnd(index) ? 'E'
370: : '-')
371: + (isExceptionHandler(index) ? 'H'
372: : '-')
373: + (isSubroutineInvocation(index) ? 'J'
374: : '-')
375: + (isSubroutineStart(index) ? 'S'
376: : '-')
377: + (isSubroutineReturning(index) ? 'r'
378: : '-')
379: + (isSubroutine(index) ? " ["
380: + subroutineStart(index)
381: + " -> "
382: + subroutineEnd(index)
383: + "] " : " ")
384: + InstructionFactory.create(
385: codeAttribute.code, index)
386: .toString(index));
387: }
388: }
389: }
390: }
391:
392: // Implementations for InstructionVisitor.
393:
394: public void visitSimpleInstruction(Clazz clazz, Method method,
395: CodeAttribute codeAttribute, int offset,
396: SimpleInstruction simpleInstruction) {
397: // Mark the instruction.
398: instructionMarks[offset] |= INSTRUCTION;
399:
400: // Check if this is the first instruction of a subroutine.
401: checkSubroutine(offset);
402:
403: byte opcode = simpleInstruction.opcode;
404: if (opcode == InstructionConstants.OP_IRETURN
405: || opcode == InstructionConstants.OP_LRETURN
406: || opcode == InstructionConstants.OP_FRETURN
407: || opcode == InstructionConstants.OP_DRETURN
408: || opcode == InstructionConstants.OP_ARETURN
409: || opcode == InstructionConstants.OP_ATHROW) {
410: // Mark the branch origin.
411: markBranchOrigin(offset);
412:
413: // Mark the next instruction.
414: markAfterBranchOrigin(offset
415: + simpleInstruction.length(offset));
416: }
417: }
418:
419: public void visitConstantInstruction(Clazz clazz, Method method,
420: CodeAttribute codeAttribute, int offset,
421: ConstantInstruction constantInstruction) {
422: // Mark the instruction.
423: instructionMarks[offset] |= INSTRUCTION;
424:
425: // Check if this is the first instruction of a subroutine.
426: checkSubroutine(offset);
427:
428: // Check if the instruction is a 'new' instruction.
429: if (constantInstruction.opcode == InstructionConstants.OP_NEW) {
430: // Push the 'new' instruction offset on the stack.
431: recentCreationOffsets[recentCreationOffsetIndex++] = offset;
432: } else {
433: // Check if the instruction is an initializer invocation.
434: isInitializer = false;
435: clazz.constantPoolEntryAccept(
436: constantInstruction.constantIndex, this );
437: if (isInitializer) {
438: // Pop the 'new' instruction offset from the stack.
439: int recentCreationOffset = recentCreationOffsets[--recentCreationOffsetIndex];
440:
441: // Fill it out in the creation offsets.
442: creationOffsets[offset] = recentCreationOffset;
443:
444: // Fill out the initialization offsets.
445: if (recentCreationOffset == AT_METHOD_ENTRY) {
446: super InitializationOffset = offset;
447: } else {
448: initializationOffsets[recentCreationOffset] = offset;
449: }
450: }
451: }
452: }
453:
454: public void visitVariableInstruction(Clazz clazz, Method method,
455: CodeAttribute codeAttribute, int offset,
456: VariableInstruction variableInstruction) {
457: // Mark the instruction.
458: instructionMarks[offset] |= INSTRUCTION;
459:
460: // Check if this is the first instruction of a subroutine.
461: checkSubroutine(offset);
462:
463: if (variableInstruction.opcode == InstructionConstants.OP_RET) {
464: // Mark the branch origin.
465: markBranchOrigin(offset);
466:
467: // Mark the regular subroutine return.
468: instructionMarks[offset] |= SUBROUTINE_RETURNING;
469:
470: // Mark the next instruction.
471: markAfterBranchOrigin(offset
472: + variableInstruction.length(offset));
473: }
474: }
475:
476: public void visitBranchInstruction(Clazz clazz, Method method,
477: CodeAttribute codeAttribute, int offset,
478: BranchInstruction branchInstruction) {
479: // Mark the branch origin.
480: markBranchOrigin(offset);
481:
482: // Check if this is the first instruction of a subroutine.
483: checkSubroutine(offset);
484:
485: // Mark the branch target.
486: markBranchTarget(offset, branchInstruction.branchOffset);
487:
488: byte opcode = branchInstruction.opcode;
489: if (opcode == InstructionConstants.OP_JSR
490: || opcode == InstructionConstants.OP_JSR_W) {
491: // Mark the subroutine invocation.
492: instructionMarks[offset] |= SUBROUTINE_INVOCATION;
493:
494: // Mark the subroutine start.
495: int targetOffset = offset + branchInstruction.branchOffset;
496: subroutineStarts[targetOffset] = targetOffset;
497: } else if (opcode == InstructionConstants.OP_GOTO
498: || opcode == InstructionConstants.OP_GOTO_W) {
499: // Mark the next instruction.
500: markAfterBranchOrigin(offset
501: + branchInstruction.length(offset));
502: }
503: }
504:
505: public void visitAnySwitchInstruction(Clazz clazz, Method method,
506: CodeAttribute codeAttribute, int offset,
507: SwitchInstruction switchInstruction) {
508: // Mark the branch origin.
509: markBranchOrigin(offset);
510:
511: // Check if this is the first instruction of a subroutine.
512: checkSubroutine(offset);
513:
514: // Mark the branch targets of the default jump offset.
515: markBranchTarget(offset, switchInstruction.defaultOffset);
516:
517: // Mark the branch targets of the jump offsets.
518: markBranchTargets(offset, switchInstruction.jumpOffsets);
519:
520: // Mark the next instruction.
521: markAfterBranchOrigin(offset + switchInstruction.length(offset));
522: }
523:
524: // Implementations for ConstantVisitor.
525:
526: public void visitAnyConstant(Clazz clazz, Constant constant) {
527: }
528:
529: public void visitMethodrefConstant(Clazz clazz,
530: MethodrefConstant methodrefConstant) {
531: isInitializer = methodrefConstant.getName(clazz).equals(
532: ClassConstants.INTERNAL_METHOD_NAME_INIT);
533: }
534:
535: // Implementations for ExceptionInfoVisitor.
536:
537: public void visitExceptionInfo(Clazz clazz, Method method,
538: CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) {
539: // Mark the exception offsets.
540: instructionMarks[exceptionInfo.u2startPC] |= EXCEPTION_START;
541: instructionMarks[exceptionInfo.u2endPC] |= EXCEPTION_END;
542: instructionMarks[exceptionInfo.u2handlerPC] |= EXCEPTION_HANDLER;
543: }
544:
545: // Small utility methods.
546:
547: /**
548: * Marks the branch targets of the given jump offsets for the instruction
549: * at the given offset.
550: */
551: private void markBranchTargets(int offset, int[] jumpOffsets) {
552: for (int index = 0; index < jumpOffsets.length; index++) {
553: markBranchTarget(offset, jumpOffsets[index]);
554: }
555: }
556:
557: /**
558: * Marks the branch origin at the given offset.
559: */
560: private void markBranchOrigin(int offset) {
561: instructionMarks[offset] |= INSTRUCTION | BRANCH_ORIGIN;
562: }
563:
564: /**
565: * Marks the branch target at the given offset.
566: */
567: private void markBranchTarget(int offset, int jumpOffset) {
568: int targetOffset = offset + jumpOffset;
569:
570: instructionMarks[targetOffset] |= BRANCH_TARGET;
571:
572: // Are we inside a previously marked subroutine?
573: if (isSubroutine(offset)) {
574: // Mark the subroutine start of the target.
575: subroutineStarts[targetOffset] = currentSubroutineStart;
576:
577: // Update the current subroutine end.
578: if (currentSubroutineEnd < targetOffset) {
579: currentSubroutineEnd = targetOffset;
580: }
581: }
582: }
583:
584: /**
585: * Marks the instruction at the given offset, after a branch.
586: */
587: private void markAfterBranchOrigin(int nextOffset) {
588: instructionMarks[nextOffset] |= AFTER_BRANCH;
589:
590: // Are we at the end of the current subroutine?
591: if (currentSubroutineEnd <= nextOffset) {
592: // Reset the subroutine start.
593: currentSubroutineStart = NONE;
594: }
595: }
596:
597: /**
598: * Checks if the specified instruction is inside a subroutine.
599: */
600: private void checkSubroutine(int offset) {
601: // Are we inside a previously marked subroutine?
602: if (isSubroutine(offset)) {
603: // Update the current subroutine start.
604: currentSubroutineStart = subroutineStarts[offset];
605: } else {
606: // Mark the subroutine start (or NONE).
607: subroutineStarts[offset] = currentSubroutineStart;
608: }
609: }
610: }
|