0001: /*
0002: * Bytecode Analysis Framework
0003: * Copyright (C) 2003,2004 University of Maryland
0004: *
0005: * This library is free software; you can redistribute it and/or
0006: * modify it under the terms of the GNU Lesser General Public
0007: * License as published by the Free Software Foundation; either
0008: * version 2.1 of the License, or (at your option) any later version.
0009: *
0010: * This library is distributed in the hope that it will be useful,
0011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0013: * Lesser General Public License for more details.
0014: *
0015: * You should have received a copy of the GNU Lesser General Public
0016: * License along with this library; if not, write to the Free Software
0017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0018: */
0019:
0020: package edu.umd.cs.findbugs.ba;
0021:
0022: import java.util.BitSet;
0023: import java.util.IdentityHashMap;
0024: import java.util.Iterator;
0025: import java.util.LinkedList;
0026: import java.util.List;
0027:
0028: import org.apache.bcel.Constants;
0029: import org.apache.bcel.classfile.ClassParser;
0030: import org.apache.bcel.classfile.JavaClass;
0031: import org.apache.bcel.classfile.Method;
0032: import org.apache.bcel.generic.BranchInstruction;
0033: import org.apache.bcel.generic.ClassGen;
0034: import org.apache.bcel.generic.CodeExceptionGen;
0035: import org.apache.bcel.generic.ConstantPoolGen;
0036: import org.apache.bcel.generic.ExceptionThrower;
0037: import org.apache.bcel.generic.GETSTATIC;
0038: import org.apache.bcel.generic.INSTANCEOF;
0039: import org.apache.bcel.generic.Instruction;
0040: import org.apache.bcel.generic.InstructionHandle;
0041: import org.apache.bcel.generic.InstructionList;
0042: import org.apache.bcel.generic.InstructionTargeter;
0043: import org.apache.bcel.generic.JsrInstruction;
0044: import org.apache.bcel.generic.MONITOREXIT;
0045: import org.apache.bcel.generic.MethodGen;
0046: import org.apache.bcel.generic.NEW;
0047: import org.apache.bcel.generic.NOP;
0048: import org.apache.bcel.generic.PUTSTATIC;
0049: import org.apache.bcel.generic.ReturnInstruction;
0050:
0051: import edu.umd.cs.findbugs.SystemProperties;
0052: import edu.umd.cs.findbugs.annotations.NonNull;
0053: import edu.umd.cs.findbugs.annotations.Nullable;
0054:
0055: /**
0056: * A CFGBuilder that really tries to construct accurate control flow graphs.
0057: * The CFGs it creates have accurate exception edges, and have accurately
0058: * inlined JSR subroutines.
0059: *
0060: * @author David Hovemeyer
0061: * @see CFG
0062: */
0063: public class BetterCFGBuilder2 implements CFGBuilder, EdgeTypes, Debug {
0064:
0065: private static final boolean DEBUG = SystemProperties
0066: .getBoolean("cfgbuilder.debug");
0067:
0068: // TODO: don't forget to change BasicBlock so ATHROW is considered to have a null check
0069:
0070: /* ----------------------------------------------------------------------
0071: * Helper classes
0072: * ---------------------------------------------------------------------- */
0073:
0074: /**
0075: * A work list item for creating the CFG for a subroutine.
0076: */
0077: private static class WorkListItem {
0078: private final InstructionHandle start;
0079: private final BasicBlock basicBlock;
0080:
0081: /**
0082: * Constructor.
0083: *
0084: * @param start first instruction in the basic block
0085: * @param basicBlock the basic block to build
0086: */
0087: public WorkListItem(InstructionHandle start,
0088: BasicBlock basicBlock) {
0089: this .start = start;
0090: this .basicBlock = basicBlock;
0091: }
0092:
0093: /**
0094: * Get the start instruction.
0095: */
0096: public InstructionHandle getStartInstruction() {
0097: return start;
0098: }
0099:
0100: /**
0101: * Get the basic block.
0102: */
0103: public BasicBlock getBasicBlock() {
0104: return basicBlock;
0105: }
0106: }
0107:
0108: /**
0109: * A placeholder for a control edge that escapes its subroutine to return
0110: * control back to an outer (calling) subroutine. It will turn into a
0111: * real edge during inlining.
0112: */
0113: private static class EscapeTarget {
0114: private final InstructionHandle target;
0115: private final int edgeType;
0116:
0117: /**
0118: * Constructor.
0119: *
0120: * @param target the target instruction in a calling subroutine
0121: * @param edgeType the type of edge that should be created when the
0122: * subroutine is inlined into its calling context
0123: */
0124: public EscapeTarget(InstructionHandle target, int edgeType) {
0125: this .target = target;
0126: this .edgeType = edgeType;
0127: }
0128:
0129: /**
0130: * Get the target instruction.
0131: */
0132: public InstructionHandle getTarget() {
0133: return target;
0134: }
0135:
0136: /**
0137: * Get the edge type.
0138: */
0139: public int getEdgeType() {
0140: return edgeType;
0141: }
0142: }
0143:
0144: private static final LinkedList<EscapeTarget> emptyEscapeTargetList = new LinkedList<EscapeTarget>();
0145:
0146: /**
0147: * JSR subroutine. The top level subroutine is where execution starts.
0148: * Each subroutine has its own CFG. Eventually,
0149: * all JSR subroutines will be inlined into the top level subroutine,
0150: * resulting in an accurate CFG for the overall method.
0151: */
0152: private class Subroutine {
0153: private final InstructionHandle start;
0154: private final BitSet instructionSet;
0155: private final CFG cfg;
0156: private IdentityHashMap<InstructionHandle, BasicBlock> blockMap;
0157: private IdentityHashMap<BasicBlock, List<EscapeTarget>> escapeTargetListMap;
0158: private BitSet returnBlockSet;
0159: private BitSet exitBlockSet;
0160: private BitSet unhandledExceptionBlockSet;
0161: private LinkedList<WorkListItem> workList;
0162:
0163: /**
0164: * Constructor.
0165: *
0166: * @param start the start instruction for the subroutine
0167: */
0168: public Subroutine(InstructionHandle start) {
0169: this .start = start;
0170: this .instructionSet = new BitSet();
0171: this .cfg = new CFG();
0172: this .blockMap = new IdentityHashMap<InstructionHandle, BasicBlock>();
0173: this .escapeTargetListMap = new IdentityHashMap<BasicBlock, List<EscapeTarget>>();
0174: this .returnBlockSet = new BitSet();
0175: this .exitBlockSet = new BitSet();
0176: this .unhandledExceptionBlockSet = new BitSet();
0177: this .workList = new LinkedList<WorkListItem>();
0178: }
0179:
0180: /**
0181: * Get the start instruction.
0182: */
0183: public InstructionHandle getStartInstruction() {
0184: return start;
0185: }
0186:
0187: /**
0188: * Allocate a new basic block in the subroutine.
0189: */
0190: public BasicBlock allocateBasicBlock() {
0191: return cfg.allocate();
0192: }
0193:
0194: /**
0195: * Add a work list item for a basic block to be constructed.
0196: */
0197: public void addItem(WorkListItem item) {
0198: workList.add(item);
0199: }
0200:
0201: /**
0202: * Are there more work list items?
0203: */
0204: public boolean hasMoreWork() {
0205: return !workList.isEmpty();
0206: }
0207:
0208: /**
0209: * Get the next work list item.
0210: */
0211: public WorkListItem nextItem() {
0212: return workList.removeFirst();
0213: }
0214:
0215: /**
0216: * Get the entry block for the subroutine's CFG.
0217: */
0218: public BasicBlock getEntry() {
0219: return cfg.getEntry();
0220: }
0221:
0222: /**
0223: * Get the exit block for the subroutine's CFG.
0224: */
0225: public BasicBlock getExit() {
0226: return cfg.getExit();
0227: }
0228:
0229: /**
0230: * Get the start block for the subroutine's CFG.
0231: * (I.e., the block containing the start instruction.)
0232: */
0233: public BasicBlock getStartBlock() {
0234: return getBlock(start);
0235: }
0236:
0237: /**
0238: * Get the subroutine's CFG.
0239: */
0240: public CFG getCFG() {
0241: return cfg;
0242: }
0243:
0244: /**
0245: * Add an instruction to the subroutine.
0246: * We keep track of which instructions are part of which subroutines.
0247: * No instruction may be part of more than one subroutine.
0248: *
0249: * @param handle the instruction to be added to the subroutine
0250: */
0251: public void addInstruction(InstructionHandle handle)
0252: throws CFGBuilderException {
0253: int position = handle.getPosition();
0254: if (usedInstructionSet.get(position))
0255: throw new CFGBuilderException("Instruction " + handle
0256: + " visited in multiple subroutines");
0257: instructionSet.set(position);
0258: usedInstructionSet.set(position);
0259: }
0260:
0261: /**
0262: * Is the given instruction part of this subroutine?
0263: */
0264: public boolean containsInstruction(InstructionHandle handle) {
0265: return instructionSet.get(handle.getPosition());
0266: }
0267:
0268: /**
0269: * Get the basic block in the subroutine for the given instruction.
0270: * If the block doesn't exist yet, it is created, and a work list
0271: * item is added which will populate it. Note that if start is
0272: * an exception thrower, the block returned will be its ETB.
0273: *
0274: * @param start the start instruction for the block
0275: * @return the basic block for the instruction
0276: */
0277: public BasicBlock getBlock(InstructionHandle start) {
0278: BasicBlock block = blockMap.get(start);
0279: if (block == null) {
0280: block = allocateBasicBlock();
0281: blockMap.put(start, block);
0282:
0283: // Block is an exception handler?
0284: CodeExceptionGen exceptionGen = exceptionHandlerMap
0285: .getHandlerForStartInstruction(start);
0286: if (exceptionGen != null)
0287: block.setExceptionGen(exceptionGen);
0288:
0289: addItem(new WorkListItem(start, block));
0290: }
0291: return block;
0292: }
0293:
0294: /**
0295: * Indicate that the method returns at the end of the given block.
0296: *
0297: * @param block the returning block
0298: */
0299: public void setReturnBlock(BasicBlock block) {
0300: returnBlockSet.set(block.getLabel());
0301: }
0302:
0303: /**
0304: * Does the method return at the end of this block?
0305: */
0306: public boolean isReturnBlock(BasicBlock block) {
0307: return returnBlockSet.get(block.getLabel());
0308: }
0309:
0310: /**
0311: * Indicate that System.exit() is called at the end of the given block.
0312: *
0313: * @param block the exiting block
0314: */
0315: public void setExitBlock(BasicBlock block) {
0316: exitBlockSet.set(block.getLabel());
0317: }
0318:
0319: /**
0320: * Is System.exit() called at the end of this block?
0321: */
0322: public boolean isExitBlock(BasicBlock block) {
0323: return exitBlockSet.get(block.getLabel());
0324: }
0325:
0326: /**
0327: * Indicate that an unhandled exception may be thrown by
0328: * the given block.
0329: *
0330: * @param block the block throwing an unhandled exception
0331: */
0332: public void setUnhandledExceptionBlock(BasicBlock block) {
0333: unhandledExceptionBlockSet.set(block.getLabel());
0334: }
0335:
0336: /**
0337: * Does this block throw an unhandled exception?
0338: */
0339: public boolean isUnhandledExceptionBlock(BasicBlock block) {
0340: return unhandledExceptionBlockSet.get(block.getLabel());
0341: }
0342:
0343: /**
0344: * Add a control flow edge to the subroutine.
0345: * If the control target has not yet been added to the subroutine,
0346: * a new work list item is added. If the control target is in
0347: * another subroutine, an EscapeTarget is added.
0348: *
0349: * @param sourceBlock the source basic block
0350: * @param target the control target
0351: * @param edgeType the type of control edge
0352: */
0353: public void addEdgeAndExplore(BasicBlock sourceBlock,
0354: InstructionHandle target, int edgeType) {
0355: if (usedInstructionSet.get(target.getPosition())
0356: && !containsInstruction(target)) {
0357: // Control escapes this subroutine
0358: List<EscapeTarget> escapeTargetList = escapeTargetListMap
0359: .get(sourceBlock);
0360: if (escapeTargetList == null) {
0361: escapeTargetList = new LinkedList<EscapeTarget>();
0362: escapeTargetListMap.put(sourceBlock,
0363: escapeTargetList);
0364: }
0365: escapeTargetList
0366: .add(new EscapeTarget(target, edgeType));
0367: } else {
0368: // Edge within the current subroutine
0369: BasicBlock targetBlock = getBlock(target);
0370: addEdge(sourceBlock, targetBlock, edgeType);
0371: }
0372: }
0373:
0374: /**
0375: * Add an edge to the subroutine's CFG.
0376: *
0377: * @param sourceBlock the source basic block
0378: * @param destBlock the destination basic block
0379: * @param edgeType the type of edge
0380: */
0381: public void addEdge(BasicBlock sourceBlock,
0382: BasicBlock destBlock, int edgeType) {
0383: if (VERIFY_INTEGRITY) {
0384: if (destBlock.isExceptionHandler()
0385: && edgeType != HANDLED_EXCEPTION_EDGE)
0386: throw new IllegalStateException("In method "
0387: + SignatureConverter
0388: .convertMethodSignature(methodGen)
0389: + ": exception handler "
0390: + destBlock.getFirstInstruction()
0391: + " reachable by non exception edge type "
0392: + edgeType);
0393: }
0394: cfg.createEdge(sourceBlock, destBlock, edgeType);
0395: }
0396:
0397: /**
0398: * Get an Iterator over the EscapeTargets of given basic block.
0399: *
0400: * @param sourceBlock the basic block
0401: * @return an Iterator over the EscapeTargets
0402: */
0403: public Iterator<EscapeTarget> escapeTargetIterator(
0404: BasicBlock sourceBlock) {
0405: List<EscapeTarget> escapeTargetList = escapeTargetListMap
0406: .get(sourceBlock);
0407: if (escapeTargetList == null)
0408: escapeTargetList = emptyEscapeTargetList;
0409: return escapeTargetList.iterator();
0410: }
0411: }
0412:
0413: /**
0414: * Inlining context.
0415: * This essentially consists of a inlining site and
0416: * a subroutine to be inlined. A stack of calling contexts
0417: * is maintained in order to resolve EscapeTargets.
0418: */
0419: private static class Context {
0420: private final Context caller;
0421: private final Subroutine subroutine;
0422: private final CFG result;
0423: private final IdentityHashMap<BasicBlock, BasicBlock> blockMap;
0424: private final LinkedList<BasicBlock> workList;
0425:
0426: /**
0427: * Constructor.
0428: *
0429: * @param caller the calling context
0430: * @param subroutine the subroutine being inlined
0431: * @param result the result CFG
0432: */
0433: public Context(@Nullable
0434: Context caller, Subroutine subroutine, CFG result) {
0435: this .caller = caller;
0436: this .subroutine = subroutine;
0437: this .result = result;
0438: this .blockMap = new IdentityHashMap<BasicBlock, BasicBlock>();
0439: this .workList = new LinkedList<BasicBlock>();
0440: }
0441:
0442: /**
0443: * Get the calling context.
0444: */
0445: public Context getCaller() {
0446: return caller;
0447: }
0448:
0449: /**
0450: * Get the subroutine being inlined.
0451: */
0452: public Subroutine getSubroutine() {
0453: return subroutine;
0454: }
0455:
0456: /**
0457: * Get the result CFG.
0458: */
0459: public CFG getResult() {
0460: return result;
0461: }
0462:
0463: /**
0464: * Add a basic block to the inlining work list.
0465: */
0466: public void addItem(BasicBlock item) {
0467: workList.add(item);
0468: }
0469:
0470: /**
0471: * Are there more work list items?
0472: */
0473: public boolean hasMoreWork() {
0474: return !workList.isEmpty();
0475: }
0476:
0477: /**
0478: * Get the next work list item (basic block to be inlined).
0479: */
0480: public BasicBlock nextItem() {
0481: return workList.removeFirst();
0482: }
0483:
0484: /**
0485: * Map a basic block in a subroutine to the corresponding block
0486: * in the resulting CFG.
0487: *
0488: * @param subBlock the subroutine block
0489: * @param resultBlock the result CFG block
0490: */
0491: public void mapBlock(BasicBlock subBlock, BasicBlock resultBlock) {
0492: blockMap.put(subBlock, resultBlock);
0493: }
0494:
0495: /**
0496: * Get the block in the result CFG corresponding to the given
0497: * subroutine block.
0498: *
0499: * @param subBlock the subroutine block
0500: * @return the result CFG block
0501: */
0502: public BasicBlock getBlock(BasicBlock subBlock) {
0503: BasicBlock resultBlock = blockMap.get(subBlock);
0504: if (resultBlock == null) {
0505: resultBlock = result.allocate();
0506: blockMap.put(subBlock, resultBlock);
0507: workList.add(subBlock);
0508: }
0509: return resultBlock;
0510: }
0511:
0512: /**
0513: * Check to ensure that this context is not the result of recursion.
0514: */
0515: public void checkForRecursion() throws CFGBuilderException {
0516: Context callerContext = caller;
0517:
0518: while (callerContext != null) {
0519: if (callerContext.subroutine == this .subroutine)
0520: throw new CFGBuilderException(
0521: "JSR recursion detected!");
0522: callerContext = callerContext.caller;
0523: }
0524: }
0525: }
0526:
0527: /* ----------------------------------------------------------------------
0528: * Instance data
0529: * ---------------------------------------------------------------------- */
0530:
0531: private MethodGen methodGen;
0532: private ConstantPoolGen cpg;
0533: private ExceptionHandlerMap exceptionHandlerMap;
0534: private BitSet usedInstructionSet;
0535: private LinkedList<Subroutine> subroutineWorkList;
0536: private IdentityHashMap<InstructionHandle, Subroutine> jsrSubroutineMap;
0537: private Subroutine topLevelSubroutine;
0538: private CFG cfg;
0539:
0540: /* ----------------------------------------------------------------------
0541: * Public methods
0542: * ---------------------------------------------------------------------- */
0543:
0544: /**
0545: * Constructor.
0546: *
0547: * @param methodGen the method to build a CFG for
0548: */
0549: public BetterCFGBuilder2(@NonNull
0550: MethodGen methodGen) {
0551: this .methodGen = methodGen;
0552: this .cpg = methodGen.getConstantPool();
0553: this .exceptionHandlerMap = new ExceptionHandlerMap(methodGen);
0554: this .usedInstructionSet = new BitSet();
0555: this .jsrSubroutineMap = new IdentityHashMap<InstructionHandle, Subroutine>();
0556: this .subroutineWorkList = new LinkedList<Subroutine>();
0557: }
0558:
0559: public void build() throws CFGBuilderException {
0560: topLevelSubroutine = new Subroutine(methodGen
0561: .getInstructionList().getStart());
0562: subroutineWorkList.add(topLevelSubroutine);
0563:
0564: // Build top level subroutine and all JSR subroutines
0565: while (!subroutineWorkList.isEmpty()) {
0566: Subroutine subroutine = subroutineWorkList.removeFirst();
0567: if (DEBUG)
0568: System.out.println("Starting subroutine "
0569: + subroutine.getStartInstruction());
0570: build(subroutine);
0571: }
0572:
0573: // Inline everything into the top level subroutine
0574: cfg = inlineAll();
0575:
0576: // Add a NOP instruction to the entry block.
0577: // This allows analyses to construct a Location
0578: // representing the entry to the method.
0579: BasicBlock entryBlock = cfg.getEntry();
0580: InstructionList il = new InstructionList();
0581: entryBlock.addInstruction(il.append(new NOP()));
0582:
0583: if (VERIFY_INTEGRITY)
0584: cfg.checkIntegrity();
0585: }
0586:
0587: public CFG getCFG() {
0588: return cfg;
0589: }
0590:
0591: /* ----------------------------------------------------------------------
0592: * Implementation
0593: * ---------------------------------------------------------------------- */
0594:
0595: /**
0596: * Build a subroutine.
0597: * We iteratively add basic blocks to the subroutine
0598: * until there are no more blocks reachable from the calling context.
0599: * As JSR instructions are encountered, new Subroutines are added
0600: * to the subroutine work list.
0601: *
0602: * @param subroutine the subroutine
0603: */
0604: private void build(Subroutine subroutine)
0605: throws CFGBuilderException {
0606: // Prime the work list
0607: subroutine.addEdgeAndExplore(subroutine.getEntry(), subroutine
0608: .getStartInstruction(), START_EDGE);
0609:
0610: // Keep going until all basic blocks in the subroutine have been added
0611: while (subroutine.hasMoreWork()) {
0612: WorkListItem item = subroutine.nextItem();
0613:
0614: InstructionHandle handle = item.getStartInstruction();
0615: BasicBlock basicBlock = item.getBasicBlock();
0616:
0617: // Add exception handler block (ETB) for exception-throwing instructions
0618: if (isPEI(handle)) {
0619: if (DEBUG)
0620: System.out.println("ETB block "
0621: + basicBlock.getLabel() + " for " + handle);
0622: handleExceptions(subroutine, handle, basicBlock);
0623: BasicBlock body = subroutine.allocateBasicBlock();
0624: subroutine.addEdge(basicBlock, body, FALL_THROUGH_EDGE);
0625: basicBlock = body;
0626: }
0627:
0628: if (DEBUG)
0629: System.out.println("BODY block "
0630: + basicBlock.getLabel() + " for " + handle);
0631:
0632: if (!basicBlock.isEmpty())
0633: throw new IllegalStateException("Block isn't empty!");
0634:
0635: // Add instructions until we get to the end of the block
0636: boolean endOfBasicBlock = false;
0637: do {
0638: Instruction ins = handle.getInstruction();
0639:
0640: // Add the instruction to the block
0641: if (DEBUG)
0642: System.out.println("BB " + basicBlock.getLabel()
0643: + ": adding" + handle);
0644: basicBlock.addInstruction(handle);
0645: subroutine.addInstruction(handle);
0646:
0647: short opcode = ins.getOpcode();
0648:
0649: // TODO: should check instruction to ensure that in a JSR subroutine
0650: // no assignments are made to the local containing the return address.
0651: // if (ins instanceof ASTORE) ...
0652:
0653: if (opcode == Constants.JSR
0654: || opcode == Constants.JSR_W) {
0655: // Find JSR subroutine, add it to subroutine work list if
0656: // we haven't built a CFG for it yet
0657: JsrInstruction jsr = (JsrInstruction) ins;
0658: InstructionHandle jsrTarget = jsr.getTarget();
0659: Subroutine jsrSubroutine = jsrSubroutineMap
0660: .get(jsrTarget);
0661: if (jsrSubroutine == null) {
0662: jsrSubroutine = new Subroutine(jsrTarget);
0663: jsrSubroutineMap.put(jsrTarget, jsrSubroutine);
0664: subroutineWorkList.add(jsrSubroutine);
0665: }
0666:
0667: // This ends the basic block.
0668: // Add a JSR_EDGE to the successor.
0669: // It will be replaced later by the inlined JSR subroutine.
0670: subroutine.addEdgeAndExplore(basicBlock, handle
0671: .getNext(), JSR_EDGE);
0672: endOfBasicBlock = true;
0673: } else if (opcode == Constants.RET) {
0674: // End of JSR subroutine
0675: subroutine.addEdge(basicBlock,
0676: subroutine.getExit(), RET_EDGE);
0677: endOfBasicBlock = true;
0678: } else {
0679: TargetEnumeratingVisitor visitor = new TargetEnumeratingVisitor(
0680: handle, cpg);
0681: if (visitor.isEndOfBasicBlock()) {
0682: endOfBasicBlock = true;
0683:
0684: // Add control edges as appropriate
0685: if (visitor.instructionIsThrow()) {
0686: handleExceptions(subroutine, handle,
0687: basicBlock);
0688: } else if (visitor.instructionIsExit()) {
0689: subroutine.setExitBlock(basicBlock);
0690: } else if (visitor.instructionIsReturn()) {
0691: subroutine.setReturnBlock(basicBlock);
0692: } else {
0693: Iterator<Target> i = visitor
0694: .targetIterator();
0695: while (i.hasNext()) {
0696: Target target = i.next();
0697: subroutine.addEdgeAndExplore(
0698: basicBlock,
0699: target.getTargetInstruction(),
0700: target.getEdgeType());
0701: }
0702: }
0703: }
0704: }
0705:
0706: if (!endOfBasicBlock) {
0707: InstructionHandle next = handle.getNext();
0708: if (next == null)
0709: throw new CFGBuilderException(
0710: "Control falls off end of method: "
0711: + handle);
0712:
0713: // Is the next instruction a control merge or a PEI?
0714: if (isMerge(next) || isPEI(next)) {
0715: subroutine.addEdgeAndExplore(basicBlock, next,
0716: FALL_THROUGH_EDGE);
0717: endOfBasicBlock = true;
0718: } else {
0719: // Basic block continues
0720: handle = next;
0721: }
0722: }
0723:
0724: } while (!endOfBasicBlock);
0725: }
0726: }
0727:
0728: /**
0729: * Add exception edges for given instruction.
0730: *
0731: * @param subroutine the subroutine containing the instruction
0732: * @param pei the instruction which throws an exception
0733: * @param etb the exception thrower block (ETB) for the instruction
0734: */
0735: private void handleExceptions(Subroutine subroutine,
0736: InstructionHandle pei, BasicBlock etb) {
0737: etb.setExceptionThrower(pei);
0738:
0739: // Remember whether or not a universal exception handler
0740: // is reachable. If so, then we know that exceptions raised
0741: // at this instruction cannot propagate out of the method.
0742: boolean sawUniversalExceptionHandler = false;
0743:
0744: List<CodeExceptionGen> exceptionHandlerList = exceptionHandlerMap
0745: .getHandlerList(pei);
0746: if (exceptionHandlerList != null) {
0747: for (CodeExceptionGen exceptionHandler : exceptionHandlerList) {
0748: InstructionHandle handlerStart = exceptionHandler
0749: .getHandlerPC();
0750: subroutine.addEdgeAndExplore(etb, handlerStart,
0751: HANDLED_EXCEPTION_EDGE);
0752:
0753: if (Hierarchy
0754: .isUniversalExceptionHandler(exceptionHandler
0755: .getCatchType()))
0756: sawUniversalExceptionHandler = true;
0757: }
0758: }
0759:
0760: // If required, mark this block as throwing an unhandled exception.
0761: // For now, we assume that if there is no reachable handler that handles
0762: // ANY exception type, then the exception can be thrown out of the method.
0763: if (!sawUniversalExceptionHandler) {
0764: if (DEBUG)
0765: System.out
0766: .println("Adding unhandled exception edge from "
0767: + pei);
0768: subroutine.setUnhandledExceptionBlock(etb);
0769: }
0770: }
0771:
0772: /**
0773: * Return whether or not the given instruction can throw exceptions.
0774: *
0775: * @param handle the instruction
0776: * @return true if the instruction can throw an exception, false otherwise
0777: */
0778: private boolean isPEI(InstructionHandle handle) {
0779: Instruction ins = handle.getInstruction();
0780:
0781: if (!(ins instanceof ExceptionThrower))
0782: return false;
0783:
0784: if (ins instanceof NEW)
0785: return false;
0786: // if (ins instanceof ATHROW) return false;
0787: if (ins instanceof GETSTATIC)
0788: return false;
0789: if (ins instanceof PUTSTATIC)
0790: return false;
0791: if (ins instanceof ReturnInstruction)
0792: return false;
0793: if (ins instanceof INSTANCEOF)
0794: return false;
0795: // if (ins instanceof INVOKESTATIC) return false;
0796: // if (ins instanceof MONITORENTER) return false;
0797: if (ins instanceof MONITOREXIT)
0798: return false;
0799: return true;
0800:
0801: }
0802:
0803: /**
0804: * Determine whether or not the given instruction is a control flow merge.
0805: *
0806: * @param handle the instruction
0807: * @return true if the instruction is a control merge, false otherwise
0808: */
0809: private static boolean isMerge(InstructionHandle handle) {
0810: if (handle.hasTargeters()) {
0811: // Check all targeters of this handle to see if any
0812: // of them are branches. If so, the instruction is a merge.
0813: InstructionTargeter[] targeterList = handle.getTargeters();
0814: for (InstructionTargeter targeter : targeterList) {
0815: if (targeter instanceof BranchInstruction)
0816: return true;
0817: }
0818: }
0819: return false;
0820: }
0821:
0822: /**
0823: * Inline all JSR subroutines into the top-level subroutine.
0824: * This produces a complete CFG for the entire method, in which
0825: * all JSR subroutines are inlined.
0826: *
0827: * @return the CFG for the method
0828: */
0829: private CFG inlineAll() throws CFGBuilderException {
0830: CFG result = new CFG();
0831:
0832: Context rootContext = new Context(null, topLevelSubroutine,
0833: result);
0834: rootContext.mapBlock(topLevelSubroutine.getEntry(), result
0835: .getEntry());
0836: rootContext.mapBlock(topLevelSubroutine.getExit(), result
0837: .getExit());
0838:
0839: BasicBlock resultStartBlock = rootContext
0840: .getBlock(topLevelSubroutine.getStartBlock());
0841: result.createEdge(result.getEntry(), resultStartBlock,
0842: START_EDGE);
0843:
0844: inline(rootContext);
0845:
0846: return result;
0847: }
0848:
0849: /**
0850: * Inline a subroutine into a calling context.
0851: *
0852: * @param context the Context
0853: */
0854: public void inline(Context context) throws CFGBuilderException {
0855:
0856: CFG result = context.getResult();
0857:
0858: // Check to ensure we're not trying to inline something that is recursive
0859: context.checkForRecursion();
0860:
0861: Subroutine subroutine = context.getSubroutine();
0862: CFG subCFG = subroutine.getCFG();
0863:
0864: while (context.hasMoreWork()) {
0865: BasicBlock subBlock = context.nextItem();
0866: BasicBlock resultBlock = context.getBlock(subBlock);
0867:
0868: // Mark blocks which are in JSR subroutines
0869: resultBlock.setInJSRSubroutine(context.getCaller() != null);
0870:
0871: // Copy instructions into the result block
0872: BasicBlock.InstructionIterator insIter = subBlock
0873: .instructionIterator();
0874: while (insIter.hasNext()) {
0875: InstructionHandle handle = insIter.next();
0876: resultBlock.addInstruction(handle);
0877: }
0878:
0879: // Set exception thrower status
0880: if (subBlock.isExceptionThrower())
0881: resultBlock.setExceptionThrower(subBlock
0882: .getExceptionThrower());
0883:
0884: // Set exception handler status
0885: if (subBlock.isExceptionHandler())
0886: resultBlock.setExceptionGen(subBlock.getExceptionGen());
0887:
0888: // Add control edges (including inlining JSR subroutines)
0889: Iterator<Edge> edgeIter = subCFG
0890: .outgoingEdgeIterator(subBlock);
0891: while (edgeIter.hasNext()) {
0892: Edge edge = edgeIter.next();
0893: int edgeType = edge.getType();
0894:
0895: if (edgeType == JSR_EDGE) {
0896: // Inline a JSR subroutine...
0897:
0898: // Create a new Context
0899: InstructionHandle jsrHandle = subBlock
0900: .getLastInstruction();
0901: JsrInstruction jsr = (JsrInstruction) jsrHandle
0902: .getInstruction();
0903: Subroutine jsrSub = jsrSubroutineMap.get(jsr
0904: .getTarget());
0905: Context jsrContext = new Context(context, jsrSub,
0906: context.getResult());
0907:
0908: // The start block in the JSR subroutine maps to the first
0909: // inlined block in the result CFG.
0910: BasicBlock resultJSRStartBlock = jsrContext
0911: .getBlock(jsrSub.getStartBlock());
0912: result.createEdge(resultBlock, resultJSRStartBlock,
0913: GOTO_EDGE);
0914:
0915: // The exit block in the JSR subroutine maps to the result block
0916: // corresponding to the instruction following the JSR.
0917: // (I.e., that is where control returns after the execution of
0918: // the JSR subroutine.)
0919: BasicBlock subJSRSuccessorBlock = subroutine
0920: .getBlock(jsrHandle.getNext());
0921: BasicBlock resultJSRSuccessorBlock = context
0922: .getBlock(subJSRSuccessorBlock);
0923: jsrContext.mapBlock(jsrSub.getExit(),
0924: resultJSRSuccessorBlock);
0925:
0926: // Inline the JSR subroutine
0927: inline(jsrContext);
0928: } else {
0929: // Ordinary control edge
0930: BasicBlock resultTarget = context.getBlock(edge
0931: .getTarget());
0932: result.createEdge(resultBlock, resultTarget, edge
0933: .getType());
0934: }
0935: }
0936:
0937: // Add control edges for escape targets
0938: Iterator<EscapeTarget> escapeTargetIter = subroutine
0939: .escapeTargetIterator(subBlock);
0940: while (escapeTargetIter.hasNext()) {
0941: EscapeTarget escapeTarget = escapeTargetIter.next();
0942: InstructionHandle targetInstruction = escapeTarget
0943: .getTarget();
0944:
0945: // Look for the calling context which has the target instruction
0946: Context caller = context.getCaller();
0947: while (caller != null) {
0948: if (caller.getSubroutine().containsInstruction(
0949: targetInstruction))
0950: break;
0951: caller = caller.getCaller();
0952: }
0953:
0954: if (caller == null)
0955: throw new CFGBuilderException(
0956: "Unknown caller for escape target "
0957: + targetInstruction
0958: + " referenced by "
0959: + context.getSubroutine()
0960: .getStartInstruction());
0961:
0962: // Find result block in caller
0963: BasicBlock subCallerTargetBlock = caller
0964: .getSubroutine().getBlock(targetInstruction);
0965: BasicBlock resultCallerTargetBlock = caller
0966: .getBlock(subCallerTargetBlock);
0967:
0968: // Add an edge to caller context
0969: result.createEdge(resultBlock, resultCallerTargetBlock,
0970: escapeTarget.getEdgeType());
0971: }
0972:
0973: // If the block returns from the method, add a return edge
0974: if (subroutine.isReturnBlock(subBlock)) {
0975: result.createEdge(resultBlock, result.getExit(),
0976: RETURN_EDGE);
0977: }
0978:
0979: // If the block calls System.exit(), add an exit edge
0980: if (subroutine.isExitBlock(subBlock)) {
0981: result.createEdge(resultBlock, result.getExit(),
0982: EXIT_EDGE);
0983: }
0984:
0985: // If the block throws an unhandled exception, add an unhandled
0986: // exception edge
0987: if (subroutine.isUnhandledExceptionBlock(subBlock)) {
0988: result.createEdge(resultBlock, result.getExit(),
0989: UNHANDLED_EXCEPTION_EDGE);
0990: }
0991:
0992: }
0993:
0994: /*
0995: while (blocks are left) {
0996:
0997: get block from subroutine
0998: get corresponding block from result
0999: copy instructions into result block
1000:
1001: if (block terminated by JSR) {
1002: get JSR subroutine
1003: create new context
1004: create GOTO edge from current result block to start block of new inlined context
1005: map subroutine exit block to result JSR successor block
1006: inline (new context, result)
1007: } else {
1008: for each outgoing edge {
1009: map each target to result blocks (add block to to work list if needed)
1010: add edges to result
1011: }
1012:
1013: for each outgoing escape target {
1014: add edges into blocks in outer contexts (adding those blocks to outer work list if needed)
1015: }
1016:
1017: if (block returns) {
1018: add return edge from result block to result CFG exit block
1019: }
1020:
1021: if (block calls System.exit()) {
1022: add exit edge from result block to result CFG exit block
1023: }
1024:
1025: if (block throws unhandled exception) {
1026: add unhandled exception edge from result block to result CFG exit block
1027: }
1028: }
1029:
1030: }
1031: */
1032: }
1033:
1034: /**
1035: * Test driver.
1036: */
1037: public static void main(String[] argv) throws Exception {
1038: if (argv.length != 1) {
1039: System.err.println("Usage: "
1040: + BetterCFGBuilder2.class.getName()
1041: + " <class file>");
1042: System.exit(1);
1043: }
1044:
1045: String methodName = SystemProperties
1046: .getProperty("cfgbuilder.method");
1047:
1048: JavaClass jclass = new ClassParser(argv[0]).parse();
1049: ClassGen classGen = new ClassGen(jclass);
1050:
1051: Method[] methodList = jclass.getMethods();
1052: for (Method method : methodList) {
1053: if (method.isAbstract() || method.isNative())
1054: continue;
1055:
1056: if (methodName != null
1057: && !method.getName().equals(methodName))
1058: continue;
1059:
1060: MethodGen methodGen = new MethodGen(method, jclass
1061: .getClassName(), classGen.getConstantPool());
1062:
1063: CFGBuilder cfgBuilder = new BetterCFGBuilder2(methodGen);
1064: cfgBuilder.build();
1065:
1066: CFG cfg = cfgBuilder.getCFG();
1067:
1068: CFGPrinter cfgPrinter = new CFGPrinter(cfg);
1069: System.out
1070: .println("---------------------------------------------------------------------");
1071: System.out.println("Method: "
1072: + SignatureConverter
1073: .convertMethodSignature(methodGen));
1074: System.out
1075: .println("---------------------------------------------------------------------");
1076: cfgPrinter.print(System.out);
1077: }
1078: }
1079:
1080: }
1081:
1082: // vim:ts=4
|