0001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
0002:
0003: This file is part of the db4o open source object database.
0004:
0005: db4o is free software; you can redistribute it and/or modify it under
0006: the terms of version 2 of the GNU General Public License as published
0007: by the Free Software Foundation and as clarified by db4objects' GPL
0008: interpretation policy, available at
0009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
0010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
0011: Suite 350, San Mateo, CA 94403, USA.
0012:
0013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
0014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
0015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0016: for more details.
0017:
0018: You should have received a copy of the GNU General Public License along
0019: with this program; if not, write to the Free Software Foundation, Inc.,
0020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
0021: package EDU.purdue.cs.bloat.cfg;
0022:
0023: import java.io.*;
0024: import java.util.*;
0025:
0026: import EDU.purdue.cs.bloat.codegen.*;
0027: import EDU.purdue.cs.bloat.editor.*;
0028: import EDU.purdue.cs.bloat.trans.*;
0029: import EDU.purdue.cs.bloat.tree.*;
0030: import EDU.purdue.cs.bloat.util.*;
0031:
0032: /**
0033: * FlowGraph constructs and represents a Control Flow Graph (CFG) used for
0034: * analyzing a method. It consists of the basic blocks of a method.
0035: * <p>
0036: *
0037: *
0038: * @see MethodEditor
0039: * @see Block
0040: */
0041: public class FlowGraph extends Graph {
0042: public static final int PEEL_NO_LOOPS = 0;
0043:
0044: public static final int PEEL_ALL_LOOPS = -1;
0045:
0046: public static int PEEL_LOOPS_LEVEL = 1;
0047:
0048: public static boolean DEBUG = false;
0049:
0050: public static boolean DB_GRAPHS = false;
0051:
0052: public static boolean PRINT_GRAPH = false;
0053:
0054: MethodEditor method; // The method that we create a CFG for.
0055:
0056: Map subroutines; // Mapping between a Subroutine and its
0057:
0058: // entry Block
0059: List catchBlocks; // The Blocks that begin exception handlers
0060:
0061: Map handlers; // Maps first block of exception handler to
0062:
0063: // its Handler object.
0064:
0065: Block srcBlock; // The first (source) basic Block in this method
0066:
0067: Block snkBlock; // The "last" Block (where throw and return go)
0068:
0069: Block iniBlock; // Block that handles initialization of parameters
0070:
0071: // A trace is a series of basic blocks that have the following properties:
0072: // 1) Blocks that end with a conditional jump are followed by the block
0073: // that is executed when the conditon is false.
0074: // 2) Where possible, blocks ending with a unconditional jump are
0075: // followed by the block that is the target of that unconditional jump.
0076: // Property 1) allows conditionals that resolve to false to "fall through"
0077: // and property 2) allows for the removal of labels. Typically,
0078: // bytecode will already be in trace form.
0079:
0080: List trace; // All of the basic Blocks except source and sink
0081:
0082: Graph loopTree; // A graph representing the loop nesting in
0083:
0084: // the method.
0085:
0086: // Modification counts for the dominator tree and the loop tree.
0087: // Recall that superclass Graph maintains the modifications counts
0088: // on nodes and edges.
0089: int domEdgeModCount;
0090:
0091: int loopEdgeModCount;
0092:
0093: // The maximum (greatest) loop depth/level
0094: int maxLoopDepth = 0;
0095:
0096: private void db(final String s) {
0097: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0098: System.out.println(s);
0099: }
0100: }
0101:
0102: /**
0103: * Constructor.
0104: *
0105: * @param method
0106: * The method to create the CFG for.
0107: */
0108: public FlowGraph(final MethodEditor method) {
0109: this .method = method;
0110:
0111: subroutines = new HashMap();
0112: catchBlocks = new ArrayList(method.tryCatches().size());
0113: handlers = new HashMap(method.tryCatches().size() * 2 + 1);
0114: trace = new LinkedList();
0115:
0116: srcBlock = newBlock();
0117: iniBlock = newBlock();
0118: snkBlock = newBlock();
0119:
0120: trace.add(iniBlock);
0121:
0122: // If this method is empty(!) just make some default cfg edges
0123: if (method.codeLength() == 0) {
0124: addEdge(srcBlock, iniBlock);
0125: addEdge(iniBlock, snkBlock);
0126: addEdge(srcBlock, snkBlock);
0127:
0128: buildSpecialTrees(null, null);
0129:
0130: return;
0131: }
0132:
0133: final Map labelPos = new HashMap();
0134: buildBlocks(labelPos);
0135: removeUnreachable();
0136:
0137: // Make sure any labels in the removed blocks are saved.
0138: saveLabels();
0139:
0140: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0141: System.out.println("---------- After building tree:");
0142: print(System.out);
0143: System.out
0144: .println("---------- end print after building tree");
0145: }
0146:
0147: }
0148:
0149: /**
0150: * Returns the maximum loop depth (also the maximum loop height) in the
0151: * control flow graph.
0152: */
0153: public int maxLoopDepth() {
0154: return (maxLoopDepth);
0155: }
0156:
0157: /**
0158: * Sets up the control flow graph. Computes the dominators and the dominance
0159: * frontier, cleans up the tree, works with the loops, inserts stores to aid
0160: * copy and constant propagation as well as code generation.
0161: */
0162: public void initialize() {
0163: if (method.codeLength() == 0) {
0164: computeDominators();
0165: buildLoopTree();
0166: return;
0167: }
0168:
0169: // Determine which vertices dominate which vertices, update the blocks
0170: // in the cfg appropriately
0171: computeDominators();
0172:
0173: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0174: db("------ After computing dominators (Begin)");
0175: this .print(System.out);
0176: db("------ After computing dominators (End)");
0177: }
0178:
0179: // Make sure that no block is both an entry block and a return target.
0180: splitPhiBlocks();
0181:
0182: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0183: db("------ After splitting phi blocks (Begin)");
0184: this .print(System.out);
0185: db("------ After splitting phi blocks (End)");
0186: }
0187:
0188: removeUnreachable();
0189:
0190: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0191: db("------ After removing unreachable 1 (Begin)");
0192: this .print(System.out);
0193: db("------ After removing unreachable 1 (End)");
0194: }
0195:
0196: splitIrreducibleLoops();
0197:
0198: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0199: db("------ After splitting irreduciable loops (Begin)");
0200: this .print(System.out);
0201: db("------ After splitting irreducible loops (End)");
0202: }
0203:
0204: removeUnreachable();
0205:
0206: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0207: db("------ After removing unreachable 2 (Begin)");
0208: this .print(System.out);
0209: db("------ After removing unreachable 2 (End)");
0210: }
0211:
0212: splitReducibleLoops();
0213:
0214: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0215: db("------ After splitting reducible loops (Begin)");
0216: this .print(System.out);
0217: db("------ After splitting reducible loops (End)");
0218: }
0219:
0220: removeUnreachable();
0221:
0222: if (FlowGraph.DEBUG || FlowGraph.DB_GRAPHS) {
0223: db("------ After removing unreachable 3 (Begin)");
0224: this .print(System.out);
0225: db("------ After removing unreachable 3 (End)");
0226: }
0227:
0228: buildLoopTree();
0229:
0230: peelLoops(FlowGraph.PEEL_LOOPS_LEVEL);
0231:
0232: removeCriticalEdges();
0233: removeUnreachable();
0234:
0235: // Insert stores after conditional branches to aid copy and constant
0236: // propagation.
0237: insertConditionalStores();
0238:
0239: // Insert stores at the beginnings of protected regions to aid
0240: // code generation for PhiCatchStmts.
0241: insertProtectedRegionStores();
0242:
0243: if (FlowGraph.DEBUG) {
0244: System.out.println("---------- After splitting loops:");
0245: print(System.out);
0246: System.out
0247: .println("---------- end print after splitting loops");
0248: }
0249: }
0250:
0251: /**
0252: * Returns the loop tree for the method modeled by this flow graph. The loop
0253: * tree represents the nesting of the loops in a method. The procedure is at
0254: * the root of the loop tree. Nested loops are represented by a parent and
0255: * child relationship.
0256: */
0257: public Graph loopTree() {
0258: if (loopEdgeModCount != edgeModCount) {
0259: buildLoopTree();
0260: }
0261:
0262: return loopTree;
0263: }
0264:
0265: /**
0266: * Builds the loop tree.
0267: *
0268: * @see #loopTree
0269: * @see LoopNode
0270: */
0271: private void buildLoopTree() {
0272: db(" Building loop tree");
0273:
0274: loopEdgeModCount = edgeModCount;
0275:
0276: removeUnreachable();
0277:
0278: setBlockTypes();
0279:
0280: final LoopNode root = new LoopNode(srcBlock);
0281:
0282: // loopTree has one root, the node containing the srcBlock.
0283: loopTree = new Graph() {
0284: public Collection roots() {
0285: final ArrayList r = new ArrayList(1);
0286: r.add(root);
0287: return r;
0288: }
0289: };
0290:
0291: loopTree.addNode(srcBlock, root);
0292:
0293: Iterator iter = nodes().iterator();
0294:
0295: // Iterate over the blocks in the control flow graph. Add blocks
0296: // to the loop tree node corresponding to their loop header. If
0297: // the block itself is a header block, make a new loop tree node
0298: // for it. An edge in the loop tree is added from the outer loop
0299: // tree node to the inner loop tree node.
0300: while (iter.hasNext()) {
0301: final Block block = (Block) iter.next();
0302: final Block header = block.header();
0303:
0304: if (header != null) {
0305: LoopNode headerLoop = (LoopNode) loopTree
0306: .getNode(header);
0307:
0308: if (headerLoop == null) {
0309: headerLoop = new LoopNode(header);
0310: loopTree.addNode(header, headerLoop);
0311: }
0312:
0313: headerLoop.elements.add(block);
0314:
0315: if (block.blockType() != Block.NON_HEADER) {
0316: LoopNode loop = (LoopNode) loopTree.getNode(block);
0317:
0318: if (loop == null) {
0319: loop = new LoopNode(block);
0320: loopTree.addNode(block, loop);
0321: }
0322:
0323: // Edges go from outer loops in.
0324: loopTree.addEdge(headerLoop, loop);
0325: }
0326: }
0327: }
0328:
0329: // Iterate over the loop tree from the bottom up and determine
0330: // each node's level. Level 0 occurs at the leaf nodes.
0331: iter = loopTree.postOrder().iterator();
0332:
0333: while (iter.hasNext()) {
0334: final LoopNode loop = (LoopNode) iter.next();
0335:
0336: // The level of the node is max(level(succs)) + 1.
0337: int level = 0;
0338:
0339: final Iterator succs = loopTree.succs(loop).iterator();
0340:
0341: while (succs.hasNext()) {
0342: final LoopNode inner = (LoopNode) succs.next();
0343:
0344: if (level < inner.level) {
0345: level = inner.level;
0346: }
0347: }
0348:
0349: loop.level = level + 1;
0350: }
0351:
0352: // Iterate over the loop tree from the top down and determine each
0353: // node's depth. Depth 0 occurs at the root node.
0354: iter = loopTree.preOrder().iterator();
0355:
0356: while (iter.hasNext()) {
0357: final LoopNode loop = (LoopNode) iter.next();
0358:
0359: // The depth of the node is depth(pred) + 1.
0360: final Iterator preds = loopTree.preds(loop).iterator();
0361:
0362: if (preds.hasNext()) {
0363: final LoopNode outer = (LoopNode) preds.next();
0364: loop.depth = outer.depth + 1;
0365:
0366: } else {
0367: loop.depth = 0;
0368: }
0369: }
0370: }
0371:
0372: /**
0373: * Creates the basic blocks for the method that is the cfg.
0374: *
0375: * @param labelPos
0376: * A mapping between the Labels in the code that start a basic
0377: * block and their offset in the code (an Integer).
0378: */
0379: private void buildBlocks(final Map labelPos) {
0380: db(" Building blocks");
0381:
0382: // Get the Labels and Instructions of this method
0383: ListIterator iter = method.code().listIterator();
0384:
0385: // Go through the code, find each Label that starts a block, create
0386: // a Block for that Label, and add it to the trace.
0387: while (iter.hasNext()) {
0388: final Object obj = iter.next();
0389:
0390: if (obj instanceof Label) {
0391: final Label label = (Label) obj;
0392:
0393: if (label.startsBlock()) {
0394: trace.add(newBlock(label));
0395: }
0396: }
0397: }
0398:
0399: Instruction lastInst = null;
0400:
0401: Block currBlock = iniBlock;
0402: Block firstBlock = null;
0403:
0404: int i = 0;
0405: iter = method.code().listIterator();
0406:
0407: while (iter.hasNext()) {
0408: final Object curr = iter.next();
0409:
0410: if (curr instanceof Label) {
0411: final Label label = (Label) curr;
0412:
0413: if (label.startsBlock()) {
0414: labelPos.put(label, new Integer(i));
0415:
0416: final Block nextBlock = (Block) getNode(label);
0417:
0418: // If the last instruction we saw was a jsr, establish a
0419: // path
0420: // between the current block and the block that contains the
0421: // subroutine (operand to the jsr).
0422: if ((lastInst != null) && lastInst.isJsr()) {
0423: final Block target = (Block) getNode(lastInst
0424: .operand());
0425: final Subroutine sub = (Subroutine) subroutines
0426: .get(target);
0427: sub.addPath(currBlock, nextBlock);
0428: }
0429:
0430: currBlock = nextBlock; // Go on to next block
0431:
0432: if (firstBlock == null) {
0433: firstBlock = currBlock;
0434: }
0435: }
0436:
0437: } else if (curr instanceof Instruction) {
0438: final Instruction currInst = (Instruction) curr;
0439:
0440: lastInst = currInst;
0441:
0442: // Call setsubEntry to maintain a mapping between the entry
0443: // block of a Subroutine and the Subroutine itself
0444: if (currInst.isJsr()) {
0445: final Label label = (Label) currInst.operand();
0446: final Block target = (Block) getNode(label);
0447:
0448: if (!subroutines.containsKey(target)) {
0449: final Subroutine sub = new Subroutine(this );
0450: setSubEntry(sub, target);
0451: }
0452: }
0453: } else {
0454: throw new IllegalArgumentException();
0455: }
0456:
0457: i++; // Go to next instruction
0458: }
0459:
0460: // Start the tedious process of building the expression trees for
0461: // the basic blocks
0462: buildTrees(firstBlock, labelPos);
0463: }
0464:
0465: /**
0466: * Build the trees for the blocks, construct subroutines and add edges in
0467: * the flow graph.
0468: *
0469: * There is a edge from the source block to the init block, to the entry of
0470: * each subroutine and to the catch block of each exception handler.
0471: *
0472: * After building trees for all nodes reachable from the source, blocks with
0473: * null trees are removed since they are unreachable.
0474: *
0475: * Edges are added to the sink block from each node ending in a return, a
0476: * throw, or a ret.
0477: *
0478: * In addition, an edge is added to the sink block from each node ending in
0479: * unconditional branch to an ancestor. These edges are used to allow the
0480: * post dominator tree to be contructed in the presence of loops.
0481: *
0482: * @param firstBlock
0483: * The first block of code in this method.
0484: * @param labelPos
0485: * A mapping between Labels and their instruction number (offset
0486: * into the code).
0487: */
0488: private void buildTrees(final Block firstBlock, final Map labelPos) {
0489: db(" Building trees for " + firstBlock);
0490:
0491: // Maps a "catch block" (beginning of exception handler that
0492: // stores the exception) to a "catch body" (the code immediately
0493: // follows the "catch block" -- the rest of the handler).
0494: final HashMap catchBodies = new HashMap(method.tryCatches()
0495: .size() * 2 + 1);
0496:
0497: final Iterator tryCatches = method.tryCatches().iterator();
0498:
0499: while (tryCatches.hasNext()) {
0500: final TryCatch tc = (TryCatch) tryCatches.next();
0501:
0502: // We create two blocks for each handler.
0503: // catchBlock is the handler target. It contains the code
0504: // which saves the exception on the operand stack.
0505: // catchBody is the block following the handler target.
0506: // It contains the code for the exception handler body.
0507: // We need to split these two blocks so that the handler target
0508: // cannot possibly be a loop header.
0509:
0510: // This block will be the target of the exception handler.
0511: final Block catchBlock = newBlock();
0512:
0513: // This block will hold the instructions in the catch body.
0514: final Block catchBody = (Block) getNode(tc.handler());
0515:
0516: catchBodies.put(catchBlock, catchBody);
0517:
0518: // Make sure we include the new block in any protected area
0519: // containing the catch body.
0520: Integer pos = (Integer) labelPos.get(tc.handler());
0521: labelPos.put(catchBlock.label(), pos);
0522:
0523: addEdge(catchBlock, catchBody);
0524: trace.add(trace.indexOf(catchBody), catchBlock);
0525:
0526: Type type = tc.type();
0527:
0528: if (type == null) {
0529: type = Type.NULL;
0530: }
0531:
0532: catchBlocks.add(catchBlock);
0533:
0534: // Save the exception to the stack.
0535: final StackExpr lhs = new StackExpr(0, Type.THROWABLE);
0536: final CatchExpr rhs = new CatchExpr(type, Type.THROWABLE);
0537: final StoreExpr store = new StoreExpr(lhs, rhs,
0538: Type.THROWABLE);
0539:
0540: // Build the tree for the exception handler target block.
0541: final Tree tree = new Tree(catchBlock, new OperandStack());
0542: catchBlock.setTree(tree);
0543: tree.addStmt(new ExprStmt(store));
0544: tree.addStmt(new GotoStmt(catchBody));
0545:
0546: // Create the Handler.
0547: final Integer start = (Integer) labelPos.get(tc.start());
0548: final Integer end = (Integer) labelPos.get(tc.end());
0549:
0550: final Handler handler = new Handler(catchBlock, type);
0551: handlers.put(catchBlock, handler);
0552:
0553: final Iterator blocks = nodes().iterator();
0554:
0555: // Examine all of the basic blocks in this CFG. If the block's
0556: // offset into the code is between the start and end points of
0557: // the TryCatch, then it is a protected block. So, the block
0558: // should be added to the Handler's list of protected blocks.
0559: while (blocks.hasNext()) {
0560: final Block block = (Block) blocks.next();
0561:
0562: pos = (Integer) labelPos.get(block.label());
0563:
0564: if (pos == null) {
0565: // This is one of the special blocks such as the source,
0566: // sink, and init block.
0567: continue;
0568: }
0569:
0570: if (start.intValue() <= pos.intValue()) {
0571: if ((end == null)
0572: || (pos.intValue() < end.intValue())) {
0573: handler.protectedBlocks().add(block);
0574: }
0575: }
0576: }
0577: }
0578:
0579: addEdge(srcBlock, iniBlock);
0580: addEdge(srcBlock, snkBlock);
0581: addEdge(iniBlock, firstBlock);
0582:
0583: buildSpecialTrees(catchBodies, labelPos);
0584:
0585: // Build the trees for the blocks reachable from the firstBlock.
0586: buildTreeForBlock(firstBlock, iniBlock.tree().stack(), null,
0587: labelPos, catchBodies);
0588: }
0589:
0590: /**
0591: * Insert stores after conditional branches to aid copy and constant
0592: * propagation.
0593: *
0594: * If a+b and c+d are non-leaf expressions, we convert:
0595: *
0596: * if (a+b == c+d) X else Y
0597: *
0598: * to:
0599: *
0600: * if ((e = a+b) == (f = c+d)) e = f X else Y
0601: *
0602: * We can't do this for reference types since we may loose type information.
0603: * Consider:
0604: *
0605: * class A {} class B extends A { void foo(); }
0606: *
0607: * L := someA(); M := someB();
0608: *
0609: * if (L == M) { M.foo(); }
0610: *
0611: * -->
0612: *
0613: * if (L == M) { M = L; // M now has type A, not B M.foo(); }
0614: *
0615: */
0616: private void insertConditionalStores() {
0617: db(" Inserting conditional stores");
0618:
0619: final Iterator blocks = new ImmutableIterator(nodes());
0620:
0621: while (blocks.hasNext()) {
0622: final Block block = (Block) blocks.next();
0623:
0624: final Stmt last = block.tree().lastStmt();
0625:
0626: if (last instanceof IfCmpStmt) {
0627: final IfCmpStmt stmt = (IfCmpStmt) last;
0628:
0629: // Where do we insert the conditional? (The target of the true
0630: // or false branch.)
0631: Block target = null;
0632:
0633: // Exclude targets which are mentioned more than once.
0634: // This prevents:
0635: //
0636: // if (i == j) goto L
0637: // else goto L
0638: // L:
0639: // i = j;
0640: //
0641: // Note: this shouldn't happen with IfStmts after critical.
0642: // edges are removed.
0643: //
0644: if (stmt.trueTarget() == stmt.falseTarget()) {
0645: continue;
0646: }
0647:
0648: // Ignore all comparison operations except EQ and NE
0649: if (stmt.comparison() == IfStmt.EQ) {
0650: target = stmt.trueTarget();
0651:
0652: } else if (stmt.comparison() == IfStmt.NE) {
0653: target = stmt.falseTarget();
0654: }
0655:
0656: if (target != null) {
0657: Expr left = stmt.left();
0658: Expr right = stmt.right();
0659:
0660: // If either the left expression or the right expresion is a
0661: // reference, then we can't do anything. See above.
0662: if (!left.type().isReference()
0663: && !right.type().isReference()) {
0664:
0665: // If either of the expression is a leaf expression
0666: // (meaning that it has no children expressions), make a
0667: // new local variable to store the result of the
0668: // expression. Replace the expression with a StoreExpr
0669: // that stores the result of the expression into the
0670: // local
0671: // variable.
0672:
0673: if (!(left instanceof LeafExpr)) {
0674: final LocalVariable v = method
0675: .newLocal(left.type());
0676: final LocalExpr tmp = new LocalExpr(v
0677: .index(), left.type());
0678: final Expr copy = (Expr) left.clone();
0679: copy.setDef(null);
0680: left.replaceWith(new StoreExpr(tmp, copy,
0681: left.type()));
0682: left = tmp;
0683: }
0684:
0685: if (!(right instanceof LeafExpr)) {
0686: final LocalVariable v = method
0687: .newLocal(right.type());
0688: final LocalExpr tmp = new LocalExpr(v
0689: .index(), right.type());
0690: final Expr copy = (Expr) right.clone();
0691: copy.setDef(null);
0692: right.replaceWith(new StoreExpr(tmp, copy,
0693: right.type()));
0694: right = tmp;
0695: }
0696:
0697: // If either the left expression or the right expression
0698: // is a LocalExpr (meaning that it used to be a non-leaf
0699: // expression and was replaced with a LocalExpr above),
0700: // then prepend an assignment to the LocalExpr to the
0701: // target block.
0702:
0703: if (left instanceof LocalExpr) {
0704: final LocalExpr tmp = (LocalExpr) left
0705: .clone();
0706: tmp.setDef(null);
0707: final Expr copy = (Expr) right.clone();
0708: copy.setDef(null);
0709: final Stmt insert = new ExprStmt(
0710: new StoreExpr(tmp, copy, left
0711: .type()));
0712:
0713: target.tree().prependStmt(insert);
0714:
0715: } else if (right instanceof LocalExpr) {
0716: final LocalExpr tmp = (LocalExpr) right
0717: .clone();
0718: tmp.setDef(null);
0719: final Expr copy = (Expr) left.clone();
0720: copy.setDef(null);
0721: final Stmt insert = new ExprStmt(
0722: new StoreExpr(tmp, copy, right
0723: .type()));
0724:
0725: target.tree().prependStmt(insert);
0726:
0727: } else {
0728: Assert
0729: .isTrue((left instanceof ConstantExpr)
0730: && (right instanceof ConstantExpr));
0731: }
0732: }
0733: }
0734:
0735: } else if (last instanceof IfZeroStmt) {
0736: final IfZeroStmt stmt = (IfZeroStmt) last;
0737: Block target = null;
0738:
0739: // Exclude targets which are mentioned more than once.
0740: // This prevents:
0741: //
0742: // if (i == j) goto L
0743: // else goto L
0744: // L:
0745: // i = j;
0746: //
0747: // Note: this shouldn't happen with IfStmts after critical.
0748: // edges are removed.
0749: //
0750: if (stmt.trueTarget() == stmt.falseTarget()) {
0751: continue;
0752: }
0753:
0754: // Ignore all comparisons except for EQ and NE
0755: if (stmt.comparison() == IfStmt.EQ) {
0756: target = stmt.trueTarget();
0757:
0758: } else if (stmt.comparison() == IfStmt.NE) {
0759: target = stmt.falseTarget();
0760: }
0761:
0762: if (target != null) {
0763: Expr left = stmt.expr();
0764:
0765: if (!left.type().isReference()) {
0766: // If left is not a leaf expression, make a new local
0767: // variable and replace left with an assignment from
0768: // left
0769: // to the local variable.
0770:
0771: if (!(left instanceof LeafExpr)) {
0772: final LocalVariable v = method
0773: .newLocal(left.type());
0774: final LocalExpr tmp = new LocalExpr(v
0775: .index(), left.type());
0776: final Expr copy = (Expr) left.clone();
0777: copy.setDef(null);
0778: left.replaceWith(new StoreExpr(tmp, copy,
0779: left.type()));
0780: left = tmp;
0781: }
0782:
0783: // Value of the right hand side. 0 if left is an
0784: // integer,
0785: // null otherwise (left is a reference type).
0786: Object value = null;
0787:
0788: final Type type = left.type();
0789:
0790: if (left.type().isIntegral()) {
0791: value = new Integer(0);
0792:
0793: } else {
0794: Assert.isTrue(left.type().isReference());
0795: }
0796:
0797: if (left instanceof LocalExpr) {
0798: // Prepend the target block with an assignment from
0799: // the
0800: // value of the right hand side to the left
0801: // expression.
0802:
0803: final LocalExpr copy = (LocalExpr) left
0804: .clone();
0805: copy.setDef(null);
0806: final Stmt insert = new ExprStmt(
0807: new StoreExpr(copy,
0808: new ConstantExpr(value,
0809: type), left.type()));
0810:
0811: target.tree().prependStmt(insert);
0812:
0813: } else {
0814: Assert.isTrue(left instanceof ConstantExpr);
0815: }
0816: }
0817: }
0818:
0819: } else if (last instanceof SwitchStmt) {
0820: final SwitchStmt stmt = (SwitchStmt) last;
0821:
0822: Expr index = stmt.index();
0823:
0824: if (!(index instanceof LeafExpr)) {
0825: // Replace index with a store into a new local variable
0826:
0827: final LocalVariable v = method.newLocal(index
0828: .type());
0829: final LocalExpr tmp = new LocalExpr(v.index(),
0830: index.type());
0831: final Expr copy = (Expr) index.clone();
0832: copy.setDef(null);
0833: index.replaceWith(new StoreExpr(tmp, copy, index
0834: .type()));
0835: index = tmp;
0836: }
0837:
0838: if (index instanceof LocalExpr) {
0839: final Block[] targets = stmt.targets();
0840: final int[] values = stmt.values();
0841:
0842: // Exclude targets which are mentioned more than once.
0843: // This prevents:
0844: //
0845: // switch (i) {
0846: // case 0:
0847: // case 1:
0848: // case 2:
0849: // i = 0;
0850: // i = 1;
0851: // i = 2;
0852: // use(i);
0853: // break;
0854: // case 3:
0855: // break;
0856: // }
0857: //
0858: final HashSet seen = new HashSet();
0859:
0860: // Targets that are branched to more than once
0861: final HashSet duplicate = new HashSet();
0862:
0863: for (int i = 0; i < targets.length; i++) {
0864: if (seen.contains(targets[i])) {
0865: duplicate.add(targets[i]);
0866: } else {
0867: seen.add(targets[i]);
0868: }
0869: }
0870:
0871: for (int i = 0; i < targets.length; i++) {
0872: final Block target = targets[i];
0873:
0874: // Skip targets that can be branched to in multiple
0875: // places
0876: if (duplicate.contains(target)) {
0877: continue;
0878: }
0879:
0880: // Why do we split the edge?
0881: splitEdge(block, targets[i]);
0882:
0883: // Make sure the edge was split.
0884: Assert.isTrue(targets[i] != target);
0885:
0886: // Insert a store to the index on the new empty block.
0887: final LocalExpr copy = (LocalExpr) index
0888: .clone();
0889: copy.setDef(null);
0890: final Stmt insert = new ExprStmt(new StoreExpr(
0891: copy, new ConstantExpr(new Integer(
0892: values[i]), index.type()),
0893: index.type()));
0894:
0895: targets[i].tree().prependStmt(insert);
0896: }
0897: }
0898: }
0899: }
0900: }
0901:
0902: /**
0903: * Insert stores at the beginnings of protected regions to aid code
0904: * generation for PhiCatchStmts.
0905: */
0906: private void insertProtectedRegionStores() {
0907: db(" Inserting protected region stores");
0908:
0909: final HashSet tryPreds = new HashSet();
0910:
0911: final Iterator blocks = catchBlocks.iterator();
0912:
0913: // Iterate over the blocks in this control flow graph. Build a
0914: // set of predacessors of all protected blocks that themselves are
0915: // not in the protected block. These blocks end with a jump into
0916: // a protected region.
0917: while (blocks.hasNext()) {
0918: final Block block = (Block) blocks.next();
0919:
0920: final Handler handler = (Handler) handlers.get(block);
0921:
0922: if (handler != null) {
0923: final HashSet p = new HashSet();
0924:
0925: final Iterator prots = handler.protectedBlocks()
0926: .iterator();
0927:
0928: while (prots.hasNext()) {
0929: final Block prot = (Block) prots.next();
0930: p.addAll(preds(prot));
0931: }
0932:
0933: p.removeAll(handler.protectedBlocks());
0934:
0935: tryPreds.addAll(p);
0936: }
0937: }
0938:
0939: // Starting with the source block,
0940: insertProtStores(srcBlock, tryPreds, new ResizeableArrayList());
0941: }
0942:
0943: /**
0944: * Insters copy statements into blocks whose successors lie in a protected
0945: * region.
0946: *
0947: * @param block
0948: * A block we are considering.
0949: * @param tryPreds
0950: * All blocks whose successor blocks lie in protected regions.
0951: * @param defs
0952: * Stores the expressions (LocalExprs) that define a given local
0953: * variable (index into array) in block. Basically, it contains
0954: * the LocalExpr that defines each local variable at a given
0955: * block.
0956: */
0957: private void insertProtStores(final Block block,
0958: final HashSet tryPreds, final ResizeableArrayList defs) {
0959: final Tree tree = block.tree();
0960:
0961: // Visit all LocalExprs in block. Recall that LocalExpr
0962: // represents a reference to a local variable. If the LocalExpr
0963: // defines the variable, then added it to the defs array. defs is
0964: // indexed by local variable.
0965: tree.visitChildren(new TreeVisitor() {
0966: public void visitLocalExpr(final LocalExpr expr) {
0967: if (expr.isDef()) {
0968: final int index = expr.index();
0969:
0970: if (expr.type().isWide()) {
0971: defs.ensureSize(index + 2);
0972: defs.set(index, expr);
0973: defs.set(index + 1, null);
0974:
0975: } else {
0976: defs.ensureSize(index + 1);
0977: defs.set(index, expr);
0978: }
0979: }
0980: }
0981: });
0982:
0983: // If block ends in a jump to a block in a protected region, add
0984: // statements that make a copy of each local variable. This is
0985: // done to avoid redefining local variables used by the jump
0986: // statement. I'm not too sure about all of this.
0987:
0988: if (tryPreds.contains(block)) {
0989: // Examine all of the definitions of all the local variables
0990: for (int i = 0; i < defs.size(); i++) {
0991: final LocalExpr expr = (LocalExpr) defs.get(i);
0992:
0993: if (expr != null) {
0994: // Insert stores before the last stmt to ensure we don't
0995: // redefine locals used by(?) the branch stmt.
0996: final Stmt last = tree.lastStmt();
0997:
0998: // Visit the Exprs in the last statement block. Remember
0999: // that this statement ends in a jump to a protected block.
1000: // Insert a store of the a copy of all Expr into a stack
1001: // variable right before the jump. I think this saves all
1002: // of the expressions in the jump statement to the stack.
1003: // Why? I don't know.
1004:
1005: last.visitChildren(new TreeVisitor() {
1006: public void visitExpr(final Expr expr) {
1007: StackExpr var = tree.newStack(expr.type());
1008: var.setValueNumber(expr.valueNumber());
1009:
1010: final Node p = expr.parent();
1011: expr.setParent(null);
1012: p.visit(new ReplaceVisitor(expr, var));
1013:
1014: var = (StackExpr) var.clone();
1015: var.setDef(null);
1016: final StoreExpr store = new StoreExpr(var,
1017: expr, expr.type());
1018: store.setValueNumber(expr.valueNumber());
1019:
1020: final Stmt storeStmt = new ExprStmt(store);
1021: storeStmt
1022: .setValueNumber(expr.valueNumber());
1023:
1024: tree.addStmtBeforeJump(storeStmt);
1025: }
1026:
1027: public void visitStackExpr(final StackExpr expr) {
1028: }
1029: });
1030:
1031: // Add assignment statements (StoreExpr) that store a copy
1032: // of expr (a defining instance of LocalExpr) into itself.
1033:
1034: final LocalExpr copy1 = (LocalExpr) expr.clone();
1035: final LocalExpr copy2 = (LocalExpr) expr.clone();
1036: copy1.setDef(null);
1037: copy2.setDef(null);
1038:
1039: final StoreExpr store = new StoreExpr(copy1, copy2,
1040: expr.type());
1041:
1042: tree.addStmtBeforeJump(new ExprStmt(store));
1043: }
1044: }
1045: }
1046:
1047: final Iterator children = domChildren(block).iterator();
1048:
1049: // Examine all of the blocks that block dominates. Note that
1050: // local variables will have the same definitions as in block
1051: // unless they are overriden in the child.
1052: while (children.hasNext()) {
1053: final Block child = (Block) children.next();
1054: insertProtStores(child, tryPreds, new ResizeableArrayList(
1055: defs));
1056: }
1057: }
1058:
1059: /**
1060: * Removing unreachable Blocks means that there are Labels that are no
1061: * longer label valid blocks (e.g. start basic blocks) in the CFG. However,
1062: * we still want the Labels to point to something meaningful. So, we hoist
1063: * them out of CFG and place them into the init block as LabelStmts.
1064: */
1065: private void saveLabels() {
1066: // Make sure any labels in the removed blocks are saved.
1067: boolean save = false;
1068:
1069: final Iterator iter = method.code().listIterator();
1070:
1071: while (iter.hasNext()) {
1072: final Object obj = iter.next();
1073:
1074: if (obj instanceof Label) {
1075: final Label label = (Label) obj;
1076:
1077: if (label.startsBlock()) {
1078: if (getNode(label) == null) {
1079: save = true;
1080: } else {
1081: save = false;
1082: }
1083: }
1084:
1085: if (save) {
1086: label.setStartsBlock(false);
1087: iniBlock.tree().addStmt(new LabelStmt(label));
1088: }
1089: }
1090: }
1091: }
1092:
1093: /**
1094: * Removes a subroutine from this method.
1095: *
1096: * @param sub
1097: * The subroutine to remove.
1098: */
1099: public void removeSub(final Subroutine sub) {
1100: subroutines.remove(sub.entry());
1101: }
1102:
1103: /**
1104: * Adds an edge between two nodes in this graph.
1105: *
1106: * @param src
1107: * Node at which the edge originates.
1108: * @param dst
1109: * Node at which the edge terminates.
1110: */
1111: public void addEdge(final GraphNode src, final GraphNode dst) {
1112: if (FlowGraph.DEBUG) {
1113: System.out.println(" ADDING EDGE " + src + " -> " + dst);
1114: }
1115:
1116: super .addEdge(src, dst);
1117: }
1118:
1119: /**
1120: * Removes an edge from the graph and performs the necessary cleanup.
1121: *
1122: * @param v
1123: * Node at which edge to be removed originates.
1124: * @param w
1125: * Node at which edge to be removed terminates.
1126: */
1127: public void removeEdge(final GraphNode v, final GraphNode w) {
1128: final Block src = (Block) v;
1129: final Block dst = (Block) w;
1130:
1131: if (FlowGraph.DEBUG) {
1132: System.out.println(" REMOVING EDGE " + src + " -> "
1133: + dst);
1134: }
1135:
1136: super .removeEdge(src, dst);
1137:
1138: cleanupEdge(src, dst);
1139: }
1140:
1141: /**
1142: * Visit the tree starting at the destination node.
1143: */
1144: private void cleanupEdge(final Block src, final Block dst) {
1145: dst.visit(new TreeVisitor() {
1146: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
1147: final Expr operand = stmt.operandAt(src);
1148:
1149: if (operand != null) {
1150: operand.cleanup();
1151:
1152: // Remove the operand associated with src
1153: // from a PhiJoinStmt
1154: stmt.setOperandAt(src, null);
1155: }
1156: }
1157:
1158: public void visitStmt(final Stmt stmt) {
1159: }
1160: });
1161: }
1162:
1163: /**
1164: * Returns a new <tt>Block</tt> with the next available <tt>Label</tt>.
1165: */
1166: public Block newBlock() {
1167: return newBlock(method.newLabel());
1168: }
1169:
1170: /**
1171: * Creates a new Block starting with the specified Label. The Block is added
1172: * to this FlowGraph using its label as its key.
1173: *
1174: * @param label
1175: * The new Block's Label
1176: */
1177: Block newBlock(final Label label) {
1178: final Block block = new Block(label, this );
1179: addNode(label, block);
1180:
1181: if (FlowGraph.DEBUG) {
1182: System.out.println(" new block " + block);
1183: }
1184:
1185: return block;
1186: }
1187:
1188: /**
1189: * Uses classes DominatorTree and DominaceFrontier to calculate which blocks
1190: * dominate which blocks.
1191: *
1192: * @see DominatorTree
1193: * @see DominanceFrontier
1194: */
1195: private void computeDominators() {
1196: db(" Computing Dominators");
1197:
1198: domEdgeModCount = edgeModCount;
1199:
1200: removeUnreachable();
1201:
1202: // Forward
1203: DominatorTree.buildTree(this , false);
1204: DominanceFrontier.buildFrontier(this , false);
1205:
1206: // Reverse
1207: DominatorTree.buildTree(this , true);
1208: DominanceFrontier.buildFrontier(this , true);
1209: }
1210:
1211: /**
1212: * Locate the reducible loops. We get better results if we call
1213: * splitIrreducibleLoops first to split reducible loop headers from
1214: * irreducible loops. This method is based on the analyze_loops algorithm
1215: * in:
1216: *
1217: * Paul Havlak, "Nesting of Reducible and Irreducible Loops", TOPLAS, 19(4):
1218: * 557-567, July 1997.
1219: */
1220: private void setBlockTypes() {
1221: db(" Setting block types");
1222:
1223: final List blocks = preOrder();
1224:
1225: // A block's predacessors that do not occur along back edges
1226: final Set[] nonBackPreds = new Set[blocks.size()];
1227:
1228: // A block's predacessors that DO occur along back edges
1229: final Set[] backPreds = new Set[blocks.size()];
1230:
1231: ListIterator iter = blocks.listIterator();
1232:
1233: while (iter.hasNext()) {
1234: final Block w = (Block) iter.next();
1235: final int wn = preOrderIndex(w);
1236:
1237: final Set nonBack = new HashSet();
1238: nonBackPreds[wn] = nonBack;
1239:
1240: final Set back = new HashSet();
1241: backPreds[wn] = back;
1242:
1243: w.setHeader(srcBlock);
1244: w.setBlockType(Block.NON_HEADER);
1245:
1246: final Iterator preds = preds(w).iterator();
1247:
1248: while (preds.hasNext()) {
1249: final Block v = (Block) preds.next();
1250:
1251: // If w is an ancestor of v, (v,w) is a back edge.
1252: if (isAncestorToDescendent(w, v)) {
1253: back.add(v);
1254: } else {
1255: nonBack.add(v);
1256: }
1257: }
1258: }
1259:
1260: srcBlock.setHeader(null);
1261:
1262: final UnionFind uf = new UnionFind(blocks.size());
1263:
1264: iter = blocks.listIterator(blocks.size());
1265:
1266: while (iter.hasPrevious()) {
1267: final Block w = (Block) iter.previous();
1268: final int wn = preOrderIndex(w);
1269:
1270: final Set nonBack = nonBackPreds[wn];
1271: final Set back = backPreds[wn];
1272:
1273: final Set body = new HashSet(); // The body of a loop
1274:
1275: final Iterator preds = back.iterator();
1276:
1277: // For each loop header, follow the back edges to construct the
1278: // body of the loop
1279: while (preds.hasNext()) {
1280: final Block v = (Block) preds.next();
1281:
1282: if (v != w) {
1283: final int vn = preOrderIndex(v);
1284: final Block f = (Block) blocks.get(uf.find(vn));
1285: body.add(f);
1286:
1287: } else {
1288: // Self loop
1289: w.setBlockType(Block.REDUCIBLE);
1290: }
1291: }
1292:
1293: if (body.size() == 0) {
1294: continue;
1295: }
1296:
1297: // Initially assume the block is reducible
1298: w.setBlockType(Block.REDUCIBLE);
1299:
1300: final LinkedList worklist = new LinkedList(body);
1301:
1302: while (!worklist.isEmpty()) {
1303: final Block x = (Block) worklist.removeFirst();
1304: final int xn = preOrderIndex(x);
1305:
1306: final Iterator e = nonBackPreds[xn].iterator();
1307:
1308: while (e.hasNext()) {
1309: final Block y = (Block) e.next(); // a block in the loop
1310: final int yn = preOrderIndex(y);
1311: final Block z = (Block) blocks.get(uf.find(yn)); // loop
1312: // header
1313: // of y
1314:
1315: if (!isAncestorToDescendent(w, z)) {
1316: // If a block in the loop is not a descendent of the
1317: // loop
1318: // header, then there must be another entry path into
1319: // the
1320: // loop. Thus, the loop (and its header) are
1321: // IRREDUCIBLE.
1322: w.setBlockType(Block.IRREDUCIBLE);
1323: nonBack.add(z);
1324:
1325: } else {
1326: if (!body.contains(z) && (z != w)) {
1327: // If we haven't seen z yet, add it to the worklist
1328: body.add(z);
1329: worklist.add(z);
1330: }
1331: }
1332: }
1333: }
1334:
1335: final Iterator e = body.iterator();
1336:
1337: // Merge all the blocks in the loop into the UnionFind set
1338: while (e.hasNext()) {
1339: final Block x = (Block) e.next();
1340: final int xn = preOrderIndex(x);
1341: x.setHeader(w);
1342: uf.union(xn, wn);
1343: }
1344: }
1345:
1346: // Say all loops containing jsrs or catch blocks are irreducible.
1347: // This prevents some problems with peeling.
1348: Iterator e = subroutines.values().iterator();
1349:
1350: while (e.hasNext()) {
1351: final Subroutine sub = (Subroutine) e.next();
1352:
1353: final Iterator paths = sub.paths().iterator();
1354:
1355: while (paths.hasNext()) {
1356: final Block[] path = (Block[]) paths.next();
1357:
1358: if (path[0].blockType() != Block.NON_HEADER) {
1359: path[0].setBlockType(Block.IRREDUCIBLE);
1360: }
1361:
1362: if (path[1].blockType() != Block.NON_HEADER) {
1363: path[1].setBlockType(Block.IRREDUCIBLE);
1364: }
1365:
1366: Block h;
1367:
1368: h = path[0].header();
1369:
1370: if (h != null) {
1371: h.setBlockType(Block.IRREDUCIBLE);
1372: }
1373:
1374: h = path[1].header();
1375:
1376: if (h != null) {
1377: h.setBlockType(Block.IRREDUCIBLE);
1378: }
1379: }
1380: }
1381:
1382: e = catchBlocks.iterator();
1383:
1384: while (e.hasNext()) {
1385: final Block catchBlock = (Block) e.next();
1386:
1387: if (catchBlock.blockType() != Block.NON_HEADER) {
1388: catchBlock.setBlockType(Block.IRREDUCIBLE);
1389: }
1390:
1391: final Block h = catchBlock.header();
1392:
1393: if (h != null) {
1394: h.setBlockType(Block.IRREDUCIBLE);
1395: }
1396: }
1397: }
1398:
1399: /**
1400: * Ensure that no reducible back edge shares a destination with a
1401: * irreducible back edge by splitting reducible loop headers from
1402: * irredicible loops. This is based on the fix_loops algorithm in:
1403: *
1404: * Paul Havlak, "Nesting of Reducible and Irreducible Loops", TOPLAS, 19(4):
1405: * 557-567, July 1997.
1406: */
1407: private void splitIrreducibleLoops() {
1408: db(" Splitting irreducible loops");
1409:
1410: final List removeEdges = new LinkedList();
1411:
1412: Iterator iter = nodes().iterator();
1413:
1414: // Iterate over all the blocks in this cfg. If a block could be
1415: // the header of a reducible loop (i.e. it is the target of a
1416: // "reducible backedge", a backedge for which its destination
1417: // dominates its source), the block is to be split. All
1418: // "irreducible backedges" are placed in a list and will be used
1419: // to insert an empty block so that the number of reducible loop
1420: // headers is maximize.
1421: while (iter.hasNext()) {
1422: final Block w = (Block) iter.next();
1423:
1424: boolean hasReducibleBackIn = false;
1425: final Set otherIn = new HashSet();
1426:
1427: final Iterator preds = preds(w).iterator();
1428:
1429: while (preds.hasNext()) {
1430: final Block v = (Block) preds.next();
1431:
1432: if (w.dominates(v)) {
1433: // (v,w) is a reducible back edge.
1434: hasReducibleBackIn = true;
1435:
1436: } else {
1437: otherIn.add(v);
1438: }
1439: }
1440:
1441: if (hasReducibleBackIn && (otherIn.size() > 1)) {
1442: final Iterator e = otherIn.iterator();
1443:
1444: while (e.hasNext()) {
1445: final Block v = (Block) e.next();
1446: removeEdges.add(new Block[] { v, w });
1447: }
1448: }
1449: }
1450:
1451: // Split the irreducible back edges.
1452: iter = removeEdges.iterator();
1453:
1454: while (iter.hasNext()) {
1455: final Block[] edge = (Block[]) iter.next();
1456: splitEdge(edge[0], edge[1]);
1457: }
1458: }
1459:
1460: /**
1461: * Ensure that no reducible back edge shares a destination with another
1462: * reducible back edge by splitting reducible loop headers. This makes loop
1463: * nesting easier to detect since each loop has a unique header.
1464: */
1465: private void splitReducibleLoops() {
1466: db(" Splitting reducible loops");
1467:
1468: final Map reducibleBackIn = new HashMap();
1469:
1470: final Stack stack = new Stack();
1471:
1472: final Iterator iter = nodes().iterator();
1473:
1474: while (iter.hasNext()) {
1475: final Block w = (Block) iter.next();
1476:
1477: final Set edges = new HashSet(); // reducible back edges
1478:
1479: final Iterator preds = preds(w).iterator();
1480:
1481: while (preds.hasNext()) {
1482: final Block v = (Block) preds.next();
1483:
1484: if (w.dominates(v)) {
1485: // (v,w) is a reducible back edge.
1486: edges.add(v);
1487: }
1488: }
1489:
1490: // There are strange cases in which a handler block may be the
1491: // target of a reducible backedge. Ignore it.
1492: if ((edges.size() > 1) && !handlers.containsKey(w)) {
1493: stack.push(w);
1494: reducibleBackIn.put(w, edges);
1495: }
1496: }
1497:
1498: while (!stack.isEmpty()) {
1499: final Block w = (Block) stack.pop();
1500: final Set edges = (Set) reducibleBackIn.get(w);
1501:
1502: // Find the back predecessor with the lowest pre-order index.
1503: Block min = null;
1504:
1505: Iterator preds = edges.iterator();
1506:
1507: while (preds.hasNext()) {
1508: final Block v = (Block) preds.next();
1509: final int vn = preOrderIndex(v);
1510:
1511: if ((min == null) || (vn < preOrderIndex(min))) {
1512: min = v;
1513: }
1514: }
1515:
1516: Assert.isTrue(min != null);
1517:
1518: Assert.isFalse(handlers.containsKey(w));
1519: Assert.isFalse(subroutines.containsKey(w));
1520:
1521: // Split the edge (min, w) from w.
1522:
1523: // Create a new block immediately before the header.
1524: final Block newBlock = newBlock();
1525:
1526: trace.add(trace.indexOf(w), newBlock);
1527:
1528: final Tree tree = new Tree(newBlock, min.tree().stack());
1529: newBlock.setTree(tree);
1530:
1531: tree.addInstruction(new Instruction(Opcode.opcx_goto, w
1532: .label()));
1533:
1534: // If the header is a protected block, the new block must be
1535: // also since code can be moved from the header up.
1536: final JumpStmt newJump = (JumpStmt) tree.lastStmt();
1537:
1538: final Iterator e = handlers.values().iterator();
1539:
1540: while (e.hasNext()) {
1541: final Handler handler = (Handler) e.next();
1542:
1543: if (handler.protectedBlocks().contains(w)) {
1544: Assert.isTrue(succs(w).contains(
1545: handler.catchBlock()));
1546: handler.protectedBlocks().add(newBlock);
1547: addEdge(newBlock, handler.catchBlock());
1548: newJump.catchTargets().add(handler.catchBlock());
1549: }
1550: }
1551:
1552: // Change all preds of the header, except min, to have an edge
1553: // to the new block instead.
1554: preds = new ImmutableIterator(preds(w));
1555:
1556: while (preds.hasNext()) {
1557: final Block v = (Block) preds.next();
1558:
1559: if (v != min) {
1560: addEdge(v, newBlock);
1561: removeEdge(v, w);
1562: v.visit(new ReplaceTarget(w, newBlock));
1563: }
1564: }
1565:
1566: // Add an edge from the new block to the header.
1567: addEdge(newBlock, w);
1568:
1569: // If the new block has more than one back edge, push it on the
1570: // stack to handle it next.
1571: edges.remove(min);
1572:
1573: if (edges.size() > 1) {
1574: stack.push(newBlock);
1575: reducibleBackIn.put(newBlock, edges);
1576: }
1577: }
1578: }
1579:
1580: /**
1581: * Loop peeling is a process by which the first iteration of a loop is
1582: * duplicated in the control flow graph. An code that has side effects (such
1583: * as throwing an exception) will be tested in the first iteration. This
1584: * allows us to make assumptions about the code in the second iteration.
1585: *
1586: * To detect loop nesting more easily we require that each loop header have
1587: * at most one incoming back edge.
1588: *
1589: * For each loop, peel up to the last exit if: 1. There is more than one
1590: * exit, or, 2. The last exit has a successor in the loop body (not the
1591: * header).
1592: */
1593: private void peelLoops(final int level) {
1594: if (FlowGraph.DEBUG) {
1595: System.out.println("Peeling loops");
1596: System.out.println(" loop tree = " + loopTree);
1597: }
1598:
1599: // Find the blocks that have expressions that can throw exceptions
1600: // and on which we can perform PRE.
1601: final Set hoistable = new HashSet();
1602:
1603: visit(new TreeVisitor() {
1604: public void visitNode(final Node node) {
1605: if (!hoistable.contains(node.block())) {
1606: node.visitChildren(this );
1607: }
1608: }
1609:
1610: public void visitCastExpr(final CastExpr expr) {
1611: if (expr.castType().isReference()) {
1612: if (expr.expr() instanceof LeafExpr) {
1613: hoistable.add(expr.block());
1614: }
1615: }
1616:
1617: visitNode(expr);
1618: }
1619:
1620: public void visitArithExpr(final ArithExpr expr) {
1621: if ((expr.operation() == ArithExpr.DIV)
1622: || (expr.operation() == ArithExpr.REM)) {
1623: if (expr.type().isIntegral()
1624: && (expr.left() instanceof LeafExpr)
1625: && (expr.right() instanceof LeafExpr)) {
1626: hoistable.add(expr.block());
1627: }
1628: }
1629:
1630: visitNode(expr);
1631: }
1632:
1633: public void visitArrayLengthExpr(final ArrayLengthExpr expr) {
1634: if (expr.array() instanceof LeafExpr) {
1635: hoistable.add(expr.block());
1636: }
1637:
1638: visitNode(expr);
1639: }
1640:
1641: public void visitArrayRefExpr(final ArrayRefExpr expr) {
1642: if ((expr.array() instanceof LeafExpr)
1643: && (expr.index() instanceof LeafExpr)) {
1644: hoistable.add(expr.block());
1645: }
1646:
1647: visitNode(expr);
1648: }
1649:
1650: public void visitFieldExpr(final FieldExpr expr) {
1651: if (expr.object() instanceof LeafExpr) {
1652: hoistable.add(expr.block());
1653: }
1654:
1655: visitNode(expr);
1656: }
1657: });
1658:
1659: // For each loop, from the innermost loop out, unroll the loop body
1660: // up to the last block which exits the loop.
1661:
1662: // The (pre-order indices of the headers) loops that should be
1663: // peeled
1664: final List peel = new ArrayList(loopTree.size());
1665:
1666: // The header blocks of loops to be peeled
1667: final List headers = new ArrayList(loopTree.size());
1668:
1669: // The outer loop of the loops to be peeled (i.e. parent in the
1670: // loop tree)
1671: final List outer = new ArrayList(loopTree.size());
1672:
1673: // All the loops in a tree in post-order
1674: final List loops = new ArrayList(loopTree.postOrder());
1675:
1676: for (int i = 0; i < loops.size(); i++) {
1677: final LoopNode loop = (LoopNode) loops.get(i);
1678:
1679: // Don't peel irreducible loops or the outermost loop.
1680: if ((loopTree.preds(loop).size() > 0)
1681: && (loop.header.blockType() != Block.IRREDUCIBLE)) {
1682:
1683: headers.add(loop.header);
1684: peel.add(new Integer(i));
1685:
1686: // Find the next outer loop.
1687: LoopNode outerLoop = null;
1688:
1689: final Iterator e = loopTree.preds(loop).iterator();
1690: Assert.isTrue(e.hasNext());
1691:
1692: outerLoop = (LoopNode) e.next();
1693: Assert.isTrue(!e.hasNext());
1694:
1695: final int outerIndex = loops.indexOf(outerLoop);
1696: Assert.isTrue(outerIndex != -1);
1697:
1698: outer.add(new Integer(outerIndex));
1699: }
1700: }
1701:
1702: // The level of each loop to be peeled
1703: final int[] levels = new int[loops.size()];
1704:
1705: // Replace the integer indicies in loops with the blocks in the
1706: // loop to be peeled and note the level of each loop
1707: for (int i = 0; i < loops.size(); i++) {
1708: final LoopNode loop = (LoopNode) loops.get(i);
1709: loops.set(i, new ArrayList(loop.elements));
1710: levels[i] = loop.level;
1711: maxLoopDepth = (loop.level > maxLoopDepth ? loop.level
1712: : maxLoopDepth);
1713: }
1714:
1715: LOOPS:
1716: // Examine each loop that is a candidate for peeling. Peel it if
1717: // we can. If we can't peel it, we might be able to invert it.
1718: for (int i = 0; i < peel.size(); i++) {
1719: // Index of loop header
1720: final Integer loopIndex = (Integer) peel.get(i);
1721: final Integer outerLoopIndex = (Integer) outer.get(i);
1722: final Block header = (Block) headers.get(i);
1723:
1724: final Collection loop = (Collection) loops.get(loopIndex
1725: .intValue());
1726: final Collection outerLoop = (Collection) loops
1727: .get(outerLoopIndex.intValue());
1728:
1729: // Remove any blocks from the loop that are not in this control
1730: // flow graph.
1731: loop.retainAll(nodes());
1732:
1733: if (FlowGraph.DEBUG) {
1734: System.out.println(" loop = " + loop);
1735: System.out.println(" outer = " + outerLoop);
1736: }
1737:
1738: boolean canPeel = false;
1739: boolean canInvert = false;
1740:
1741: // If we haven't exceeded the peeling level and the loop
1742: // contains a block containing an expression that can be
1743: // hoisted, then we should peel it.
1744: if (level != FlowGraph.PEEL_NO_LOOPS) {
1745: if ((level == FlowGraph.PEEL_ALL_LOOPS)
1746: || (level >= levels[loopIndex.intValue()])) {
1747: final Iterator e = loop.iterator();
1748:
1749: while (e.hasNext()) {
1750: final Block block = (Block) e.next();
1751:
1752: if (hoistable.contains(block)) {
1753: canPeel = true;
1754: break;
1755: }
1756: }
1757: }
1758: }
1759:
1760: // If we can't peel it, we may still be able to invert it...
1761: if (!canPeel) {
1762: boolean hasExitSucc = false;
1763: boolean hasLoopSucc = false;
1764:
1765: final Iterator succs = succs(header).iterator();
1766:
1767: while (succs.hasNext()) {
1768: final Block succ = (Block) succs.next();
1769:
1770: if (!loop.contains(succ)) {
1771: hasExitSucc = true;
1772: } else if (succ != header) {
1773: hasLoopSucc = true;
1774: }
1775: }
1776:
1777: // If the loop header has an edge to a block that is not in
1778: // the loop, then it can be inverted.
1779: canInvert = hasExitSucc && hasLoopSucc;
1780: }
1781:
1782: // The blocks in the loop that are to be copied
1783: final Set copySet = new HashSet();
1784:
1785: if (canPeel) {
1786: // Find the blocks which have exits outside the loop.
1787: final Set exits = new HashSet();
1788:
1789: // All blocks in the loop that may throw exceptions have an
1790: // edge to outside the loop.
1791: exits.addAll(hoistable);
1792: exits.retainAll(loop);
1793:
1794: Iterator e = loop.iterator();
1795:
1796: BLOCKS: while (e.hasNext()) {
1797: final Block block = (Block) e.next();
1798:
1799: final Iterator succs = succs(block).iterator();
1800:
1801: while (succs.hasNext()) {
1802: final Block succ = (Block) succs.next();
1803:
1804: if (!loop.contains(succ)) {
1805: // If the successor of one of the blocks in the loop
1806: // is
1807: // itself not in the loop, then it is an exit block.
1808: exits.add(block);
1809: continue BLOCKS;
1810: }
1811: }
1812: }
1813:
1814: final ArrayList stack = new ArrayList(exits);
1815:
1816: e = exits.iterator();
1817:
1818: // Add all "exit" blocks to the copy of the loop
1819: while (e.hasNext()) {
1820: final Block block = (Block) e.next();
1821: copySet.add(block);
1822: stack.add(block);
1823: }
1824:
1825: // Copy all reachable blocks into the copy of the loop. Start
1826: // with the exit blocks and work upwards.
1827: while (!stack.isEmpty()) {
1828: final Block block = (Block) stack.remove(stack
1829: .size() - 1);
1830:
1831: final Iterator preds = preds(block).iterator();
1832:
1833: while (preds.hasNext()) {
1834: final Block pred = (Block) preds.next();
1835:
1836: if (!copySet.contains(pred)) {
1837: copySet.add(pred);
1838: stack.add(pred);
1839: }
1840: }
1841: }
1842:
1843: } else if (canInvert) {
1844: // If all we're doing is inverting, just copy the loop header.
1845: copySet.add(header);
1846:
1847: } else {
1848: // If we can't invert or peel the loop, copy all the blocks
1849: // to the outer loop and go to the next loop.
1850: if (outerLoop != null) {
1851: outerLoop.addAll(loop);
1852: }
1853:
1854: // Consider the next loop to be peeled
1855: continue LOOPS;
1856: }
1857:
1858: // Maintain a mapping between a block in the loop and its copy
1859: final Map copies = new HashMap();
1860:
1861: Iterator e = copySet.iterator();
1862:
1863: // Go throught the blocks in the copy set and create a copy of
1864: // each of them using copyBlock(). Make sure there are no
1865: // duplicates.
1866: while (e.hasNext()) {
1867: final Block block = (Block) e.next();
1868:
1869: // Jeez, are we dealing with a finally block?
1870: if (FlowGraph.DEBUG) {
1871: final Stmt jump = block.tree().lastStmt();
1872:
1873: if (jump instanceof JsrStmt) {
1874: final JsrStmt jsr = (JsrStmt) jump;
1875: Assert.isTrue(copySet.contains(jsr.follow()));
1876: Assert.isTrue(copySet.contains(jsr.sub()
1877: .entry()));
1878: }
1879: }
1880:
1881: if (loop.contains(block)) {
1882: Block copy = (Block) copies.get(block);
1883:
1884: if (copy == null) {
1885: copy = copyBlock(block);
1886: copies.put(block, copy);
1887: }
1888:
1889: // Add the copy to the list of hositable blocks
1890: if (hoistable.contains(block)) {
1891: hoistable.add(copy);
1892: }
1893: }
1894: }
1895:
1896: if (FlowGraph.DEBUG) {
1897: System.out.println(" copy = " + copies);
1898: }
1899:
1900: int copyIndex = -1;
1901:
1902: e = preds(header).iterator();
1903:
1904: // Determine the index into the trace to add the copy of the
1905: // loop. Place the loop after the header's "latest" predacessor
1906: // in the trace.
1907: while (e.hasNext()) {
1908: final Block pred = (Block) e.next();
1909:
1910: if (!header.dominates(pred)) {
1911: final int index = trace.indexOf(pred);
1912:
1913: if (copyIndex <= index) {
1914: copyIndex = index + 1;
1915: }
1916: }
1917: }
1918:
1919: if (copyIndex < 0) {
1920: copyIndex = trace.indexOf(header);
1921: }
1922:
1923: // Insert the copies into the trace just above the loop.
1924: final List copyTrace = new ResizeableArrayList(copies
1925: .size());
1926:
1927: e = trace.iterator();
1928:
1929: while (e.hasNext()) {
1930: final Block block = (Block) e.next();
1931: final Block copy = (Block) copies.get(block);
1932:
1933: if (copy != null) {
1934: copyTrace.add(copy);
1935: }
1936: }
1937:
1938: // Add copy of loop to trace
1939: trace.addAll(copyIndex, copyTrace);
1940:
1941: // Edges to add to the control flow graph
1942: final List addEdges = new LinkedList();
1943:
1944: // Edges to remove from the control flow graph
1945: final List removeEdges = new LinkedList();
1946:
1947: // Fix up the edges for the block copies.
1948:
1949: // Add the edges within the peeled body and from the peeled body
1950: // to the original body.
1951: e = copies.entrySet().iterator();
1952:
1953: while (e.hasNext()) {
1954: final Map.Entry pair = (Map.Entry) e.next();
1955:
1956: final Block block = (Block) pair.getKey();
1957: final Block copy = (Block) pair.getValue();
1958:
1959: final Iterator h = handlers.values().iterator();
1960:
1961: // The copy of the a protected block is also protected
1962: while (h.hasNext()) {
1963: final Handler handler = (Handler) h.next();
1964:
1965: if (handler.protectedBlocks().contains(block)) {
1966: handler.protectedBlocks().add(copy);
1967: }
1968: }
1969:
1970: final Iterator succs = succs(block).iterator();
1971:
1972: // Make a list of edges to add to the control flow graph.
1973: // Create edges within the copied loop so that it looks like
1974: // the original loop.
1975: while (succs.hasNext()) {
1976: final Block succ = (Block) succs.next();
1977: final Block succCopy = (Block) copies.get(succ);
1978:
1979: if ((succ != header) && (succCopy != null)) {
1980: addEdges.add(new Block[] { copy, succCopy });
1981: copy.visit(new ReplaceTarget(succ, succCopy));
1982: } else {
1983: addEdges.add(new Block[] { copy, succ });
1984: }
1985: }
1986: }
1987:
1988: // Add the edges from outside the loop to the peeled body.
1989: // Remove the edges from outside the loop to the original body.
1990: e = copies.entrySet().iterator();
1991:
1992: while (e.hasNext()) {
1993: final Map.Entry pair = (Map.Entry) e.next();
1994:
1995: final Block block = (Block) pair.getKey();
1996: final Block copy = (Block) pair.getValue();
1997:
1998: final Iterator preds = preds(block).iterator();
1999:
2000: while (preds.hasNext()) {
2001: final Block pred = (Block) preds.next();
2002:
2003: if (!loop.contains(pred)) {
2004: addEdges.add(new Block[] { pred, copy });
2005: removeEdges.add(new Block[] { pred, block });
2006: pred.visit(new ReplaceTarget(block, copy));
2007: }
2008: }
2009: }
2010:
2011: e = addEdges.iterator();
2012:
2013: // Add edges to the control flow graph
2014: while (e.hasNext()) {
2015: final Block[] edge = (Block[]) e.next();
2016: addEdge(edge[0], edge[1]);
2017: }
2018:
2019: e = removeEdges.iterator();
2020:
2021: // Remove edges into the original (non-copied) loop
2022: while (e.hasNext()) {
2023: final Block[] edge = (Block[]) e.next();
2024: final Block v = edge[0];
2025: final Block w = edge[1];
2026:
2027: if (hasNode(v) && hasNode(w) && hasEdge(v, w)) {
2028: removeEdge(v, w);
2029: }
2030: }
2031:
2032: // Copy all the blocks to the outer loop.
2033: if (outerLoop != null) {
2034: outerLoop.addAll(copies.values());
2035: outerLoop.addAll(loop);
2036: }
2037: }
2038:
2039: if (FlowGraph.DEBUG) {
2040: System.out.println("Begin after peeling:");
2041: System.out.println(this );
2042: System.out.println("End after peeling");
2043: }
2044: }
2045:
2046: /**
2047: * Creates a copy of a block including its expression tree.
2048: */
2049: private Block copyBlock(final Block block) {
2050: final Block copy = newBlock();
2051:
2052: // Copy the stack from the end of the old block.
2053: // But don't change it when instructions are added.
2054:
2055: final Tree tree = new Tree(copy, block.tree().stack());
2056: copy.setTree(tree);
2057:
2058: // Fill the tree.
2059: final Iterator stmts = block.tree().stmts().iterator();
2060:
2061: while (stmts.hasNext()) {
2062: final Stmt stmt = (Stmt) stmts.next();
2063:
2064: if (stmt instanceof LabelStmt) {
2065: continue;
2066: }
2067:
2068: tree.addStmt((Stmt) stmt.clone());
2069: }
2070:
2071: return copy;
2072: }
2073:
2074: /**
2075: * Returns the <tt>Subroutine</tt> whose entry block is labeled by a given
2076: * <tt>Label</tt>.
2077: */
2078: public Subroutine labelSub(final Label label) {
2079: return (Subroutine) subroutines.get(getNode(label));
2080: }
2081:
2082: /**
2083: * Set the entry in the mapping between subroutine entry <tt>Block</tt>s
2084: * and the <tt>Subroutine</tt>s that they begin. It also sets the
2085: * <tt>Subroutine</tt>'s entry block.
2086: *
2087: * @param sub
2088: * The subroutine whose entry block is being set.
2089: * @param entry
2090: * The subroutine's entry Block.
2091: *
2092: * @see Subroutine#setEntry
2093: */
2094: void setSubEntry(final Subroutine sub, final Block entry) {
2095: if (sub.entry() != null) {
2096: subroutines.remove(sub.entry());
2097: }
2098:
2099: sub.setEntry(entry);
2100: subroutines.put(entry, sub);
2101: }
2102:
2103: /**
2104: * Returns all of the <tt>Subroutine</tt>s in the method modeled by this
2105: * <tt>FlowGraph</tt>.
2106: */
2107: public Collection subroutines() {
2108: return subroutines.values();
2109: }
2110:
2111: int file = 0;
2112:
2113: public void print(final PrintStream out) {
2114: print(new PrintWriter(out, true));
2115: }
2116:
2117: /**
2118: * Prints the graph.
2119: *
2120: * @param out
2121: * The writer to which to print.
2122: */
2123: public void print(final PrintWriter out) {
2124: final String dateString = java.text.DateFormat
2125: .getDateInstance().format(new Date());
2126: out.println("Print " + ++file + " at " + dateString + " "
2127: + method.type() + " " + method.name() + ":");
2128:
2129: visit(new PrintVisitor(out));
2130:
2131: if (FlowGraph.PRINT_GRAPH) {
2132: printGraph();
2133: }
2134: }
2135:
2136: int next = 1;
2137:
2138: public void printGraph() {
2139: try {
2140: final PrintStream out = new PrintStream(
2141: new FileOutputStream(method.name() + "." + next++
2142: + ".dot"));
2143: printGraph(out);
2144:
2145: } catch (final IOException e) {
2146: }
2147:
2148: }
2149:
2150: public void print() {
2151: try {
2152: final PrintStream out = new PrintStream(
2153: new FileOutputStream(method.name() + "." + next++
2154: + ".cfg"));
2155: print(out);
2156:
2157: } catch (final IOException e) {
2158: }
2159:
2160: }
2161:
2162: /**
2163: * Creates a graphical description of the CFG in the dot language. The name
2164: * of the generated file is the name of the method modeled by this CFG
2165: * followed by a number and the ".dot" postfix. For more information about
2166: * dot and tools that use it see:
2167: * <p align=center>
2168: * http://www.research.att.com/sw/tools/graphviz/
2169: */
2170: public void printGraph(final PrintStream out) {
2171: printGraph(new PrintWriter(out, true));
2172: }
2173:
2174: public void printGraph(final PrintWriter out) {
2175: printGraph(out, "cfg");
2176: }
2177:
2178: public void printGraph(final PrintWriter out, final String name) {
2179: out.println("digraph " + name + " {");
2180: out.println(" fontsize=8;");
2181: out.println(" ordering=out;");
2182: out.println(" center=1;");
2183:
2184: visit(new PrintVisitor(out) {
2185: public void println() {
2186: super .print("\\n");
2187: }
2188:
2189: public void println(final Object obj) {
2190: super .print(obj);
2191: super .print("\\n");
2192: }
2193:
2194: public void visitBlock(final Block block) {
2195: super
2196: .print(" "
2197: + block.label()
2198: + " [shape=box,fontname=\"Courier\",fontsize=6,label=\"");
2199: block.visitChildren(this );
2200: super .print("\"];\n");
2201:
2202: final Iterator succs = succs(block).iterator();
2203:
2204: while (succs.hasNext()) {
2205: final Block succ = (Block) succs.next();
2206:
2207: super .print(" " + block.label() + " -> "
2208: + succ.label());
2209:
2210: if (handlers.containsKey(succ)) {
2211: super .print(" [style=dotted];\n");
2212:
2213: } else {
2214: super .print(" [style=solid];\n");
2215: }
2216: }
2217: }
2218: });
2219:
2220: out.println(" page=\"8.5,11\";");
2221: out.println("}");
2222: out.close();
2223: }
2224:
2225: /**
2226: * Visit each node (block) in this CFG in pre-order.
2227: */
2228: public void visitChildren(final TreeVisitor visitor) {
2229: final List list = preOrder();
2230:
2231: if (!visitor.reverse()) {
2232: final ListIterator iter = list.listIterator();
2233:
2234: while (iter.hasNext()) {
2235: final Block block = (Block) iter.next();
2236: block.visit(visitor);
2237: }
2238:
2239: } else {
2240: final ListIterator iter = list.listIterator(list.size());
2241:
2242: while (iter.hasPrevious()) {
2243: final Block block = (Block) iter.previous();
2244: block.visit(visitor);
2245: }
2246: }
2247: }
2248:
2249: public void visit(final TreeVisitor visitor) {
2250: visitor.visitFlowGraph(this );
2251: }
2252:
2253: /**
2254: * Returns the method editor for the method modeled by this graph.
2255: */
2256: public MethodEditor method() {
2257: return method;
2258: }
2259:
2260: /**
2261: * Removes the critical edges (edges from a block with more than one
2262: * successor to a block with more than one predecessor) from the graph.
2263: * Critical edges can screw up code motion.
2264: * <p>
2265: * For code generation, the block must be inserted after the predecessor if
2266: * the successor is the default target. Throw successors and predecessors
2267: * are copied from the successor block.
2268: */
2269: private void removeCriticalEdges() {
2270: // The critical edges
2271: final List edges = new LinkedList();
2272:
2273: final Iterator blocks = nodes().iterator();
2274:
2275: // Examine each block in this CFG. Blocks in subroutines,
2276: // exception handlers, blocks with one or fewer predacessors, and
2277: // the sink block are ignored. For all other blocks, dst, their
2278: // predacessors are examined. If the predacessor, src, has more
2279: // than one sucessor, then the edge from src to dst is a critical
2280: // edge. A List of critical egdes is maintained.
2281: while (blocks.hasNext()) {
2282: final Block dst = (Block) blocks.next();
2283:
2284: // Skip edges to subroutine entries.
2285: if (subroutines.containsKey(dst)) {
2286: continue;
2287: }
2288:
2289: // Skip edges from protected blocks to handlers.
2290: if (handlers.containsKey(dst)) {
2291: continue;
2292: }
2293:
2294: if (preds(dst).size() <= 1) {
2295: continue;
2296: }
2297:
2298: if (dst == snkBlock) {
2299: continue;
2300: }
2301:
2302: final Iterator preds = preds(dst).iterator();
2303:
2304: while (preds.hasNext()) {
2305: final Block src = (Block) preds.next();
2306:
2307: if (succs(src).size() <= 1) {
2308: continue;
2309: }
2310:
2311: // The edge src->dst is a critical edge. Plop a new
2312: // block on the edge.
2313:
2314: edges.add(new Block[] { src, dst });
2315: }
2316: }
2317:
2318: final Iterator e = edges.iterator();
2319:
2320: // Remove the critical edges from this CFG. Call splitEdge to add
2321: // a block between the source and destination blocks of the
2322: // critical edges so that it is no longer critical.
2323: while (e.hasNext()) {
2324: final Block[] edge = (Block[]) e.next();
2325: final Block v = edge[0];
2326: final Block w = edge[1];
2327:
2328: if (hasEdge(v, w)) {
2329: if (FlowGraph.DEBUG) {
2330: System.out.println("removing critical edge from "
2331: + v + " to " + w);
2332: }
2333:
2334: splitEdge(v, w);
2335:
2336: Assert.isFalse(hasEdge(v, w));
2337: }
2338: }
2339: }
2340:
2341: /**
2342: * Splits an edge by inserting an new block between a source and a
2343: * destination block. The new block consists of a goto to the destination
2344: * block. However, later optimizations may move code from the destination
2345: * block into the new block. Thus, if the destination block is a proteced
2346: * block, the new block must also be a protected block.
2347: */
2348: private void splitEdge(final Block src, final Block dst) {
2349: // This shouldn't happen since
2350: // (1) edges from the source are either source->init, or
2351: // source->catch. Edges with catch blocks are already split.
2352: // (2) edges to the sink are always unconditional jumps.
2353: //
2354: Assert.isFalse((src == srcBlock) || (dst == snkBlock),
2355: "Can't split an edge from the source or to the sink");
2356:
2357: // Don't split exception edges
2358: if (handlers.containsKey(dst)) {
2359: if (FlowGraph.DEBUG) {
2360: System.out.println("not removing exception edge " + src
2361: + " -> " + dst);
2362: }
2363:
2364: return;
2365: }
2366:
2367: final Block newBlock = newBlock();
2368:
2369: // Insert in the trace before the dst.
2370: trace.add(trace.indexOf(dst), newBlock);
2371:
2372: final Tree tree = new Tree(newBlock, src.tree().stack());
2373: newBlock.setTree(tree);
2374:
2375: tree.addInstruction(new Instruction(Opcode.opcx_goto, dst
2376: .label()));
2377:
2378: if (FlowGraph.DEBUG) {
2379: System.out.println("add edge " + src + " -> " + newBlock);
2380: System.out.println("add edge " + newBlock + " -> " + dst);
2381: System.out.println("remove edge " + src + " -> " + dst);
2382: }
2383:
2384: src.visit(new ReplaceTarget(dst, newBlock));
2385:
2386: addEdge(src, newBlock);
2387: addEdge(newBlock, dst);
2388: removeEdge(src, dst);
2389:
2390: Assert.isTrue(hasEdge(src, newBlock));
2391: Assert.isTrue(hasEdge(newBlock, dst));
2392: Assert.isFalse(hasEdge(src, dst));
2393:
2394: // If the dst is a protected block, the new block must be
2395: // also since code can be moved from the dst up.
2396: final JumpStmt newJump = (JumpStmt) newBlock.tree().lastStmt();
2397:
2398: final Iterator e = handlers.values().iterator();
2399:
2400: while (e.hasNext()) {
2401: final Handler handler = (Handler) e.next();
2402:
2403: if (handler.protectedBlocks().contains(dst)) {
2404: Assert
2405: .isTrue(succs(dst).contains(
2406: handler.catchBlock()));
2407: handler.protectedBlocks().add(newBlock);
2408: addEdge(newBlock, handler.catchBlock());
2409: newJump.catchTargets().add(handler.catchBlock());
2410: }
2411: }
2412: }
2413:
2414: /**
2415: * Finds any blocks in the CFG that are both the entry block of a subroutine
2416: * and the return target of (another) subroutine.
2417: * <p>
2418: * The Subroutine's in the cfg are examined. If a block is encountered that
2419: * is both a subroutine entry block and the target of a subroutine return,
2420: * then we have to make two new blocks: a new target block and a new entry
2421: * block. The edges have to be adjusted accordingly.
2422: */
2423: private void splitPhiBlocks() {
2424: // Make sure a block is not more than one of: a catch block,
2425: // a sub entry block, a sub return target.
2426: // Otherwise, more than one SSA phi could be placed at the block.
2427: //
2428: // Since catch blocks and return targets are mutually exclusive
2429: // and since catch blocks and sub entries are mutually exclusive,
2430: // we need only check if the block is both an entry block and a
2431: // return target. Actually, I don't think this can possibly
2432: // happen, but do it just to be sure.
2433: //
2434: // Note that a phi can also be placed at the block if it has
2435: // more than one predecessor, but this condition and the others
2436: // are mutually exclusive since catch blocks and sub entries have
2437: // only the single source predecessor and return targets have
2438: // only the caller block as its predecessor.
2439: //
2440: final Iterator entries = subroutines.values().iterator();
2441:
2442: ENTRIES: while (entries.hasNext()) {
2443: final Subroutine entrySub = (Subroutine) entries.next();
2444:
2445: // An entry block of a subroutine
2446: final Block block = entrySub.entry();
2447:
2448: Subroutine returnSub = null;
2449:
2450: // A block that calls a subroutine that is followed by a block
2451: // (the return target of the subroutine) that also starts a
2452: // subroutine.
2453: Block returnSubCaller = null;
2454:
2455: final Iterator returns = subroutines.values().iterator();
2456:
2457: RETURNS: while (returns.hasNext()) {
2458: returnSub = (Subroutine) returns.next();
2459:
2460: if (returnSub == entrySub) {
2461: continue;
2462: }
2463:
2464: final Iterator paths = returnSub.paths().iterator();
2465:
2466: while (paths.hasNext()) {
2467: final Block[] path = (Block[]) paths.next();
2468:
2469: // If the block to which returnSub returns is also the entry
2470: // block of entrySub, then note the caller of returnSub as
2471: // the
2472: // returnSubCaller.
2473: if (block == path[1]) {
2474: returnSubCaller = path[0];
2475: break RETURNS;
2476: }
2477: }
2478: }
2479:
2480: if (returnSubCaller == null) {
2481: continue ENTRIES;
2482: }
2483:
2484: if (FlowGraph.DEBUG) {
2485: System.out.println("" + block
2486: + " is both an entry and a return target");
2487: }
2488:
2489: // Create new blocks to be the new sub entry block and the new
2490: // return target.
2491: //
2492: // Use the returning subroutine's exit block to get the state
2493: // of the operand stack.
2494: //
2495: final int traceIndex = trace.indexOf(block);
2496:
2497: Tree tree;
2498:
2499: final Block newEntry = newBlock();
2500:
2501: // Insert in the trace before the block.
2502: trace.add(traceIndex, newEntry);
2503:
2504: tree = new Tree(newEntry, returnSub.exit().tree().stack());
2505: newEntry.setTree(tree);
2506:
2507: tree.addInstruction(new Instruction(Opcode.opcx_goto, block
2508: .label()));
2509:
2510: addEdge(newEntry, block);
2511:
2512: final Iterator paths = entrySub.paths().iterator();
2513:
2514: while (paths.hasNext()) {
2515: final Block[] path = (Block[]) paths.next();
2516: removeEdge(path[0], block);
2517: addEdge(path[0], newEntry);
2518: path[0].visit(new ReplaceTarget(block, newEntry));
2519: }
2520:
2521: setSubEntry(entrySub, newEntry);
2522:
2523: final Block newTarget = newBlock();
2524:
2525: // Insert in the trace immediately after the jsr block.
2526: trace.add(traceIndex, newTarget);
2527:
2528: tree = new Tree(newTarget, returnSub.exit().tree().stack());
2529: newTarget.setTree(tree);
2530:
2531: tree.addInstruction(new Instruction(Opcode.opcx_goto, block
2532: .label()));
2533:
2534: returnSub.exit().visit(new ReplaceTarget(block, newTarget));
2535: ((JsrStmt) returnSubCaller.tree().lastStmt())
2536: .setFollow(newTarget);
2537:
2538: addEdge(newTarget, block);
2539: addEdge(returnSub.exit(), newTarget);
2540: removeEdge(returnSub.exit(), block);
2541:
2542: final JumpStmt entryJump = (JumpStmt) newEntry.tree()
2543: .lastStmt();
2544: final JumpStmt targetJump = (JumpStmt) newTarget.tree()
2545: .lastStmt();
2546:
2547: final Iterator e = handlers.values().iterator();
2548:
2549: // If block itself is a protected block (man, this block has
2550: // problems), add egdes from the newEntry and newTarget blocks
2551: // to the handlers for block.
2552: while (e.hasNext()) {
2553: final Handler handler = (Handler) e.next();
2554:
2555: if (handler.protectedBlocks().contains(block)) {
2556: Assert.isTrue(succs(block).contains(
2557: handler.catchBlock()));
2558:
2559: handler.protectedBlocks().add(newEntry);
2560: addEdge(newEntry, handler.catchBlock());
2561: entryJump.catchTargets().add(handler.catchBlock());
2562:
2563: handler.protectedBlocks().add(newTarget);
2564: addEdge(newTarget, handler.catchBlock());
2565: targetJump.catchTargets().add(handler.catchBlock());
2566: }
2567: }
2568: }
2569: }
2570:
2571: /**
2572: * Builds the expressions trees for the "special" blocks (source, sink, and
2573: * init blocks). Empty expressions trees are built for the source and sink
2574: * blocks. The init block's expression tree contains code that initializes
2575: * the method's parameters (represented as local variables).
2576: * <p>
2577: */
2578: private void buildSpecialTrees(final Map catchBodies,
2579: final Map labelPos) {
2580: Tree tree;
2581:
2582: tree = new Tree(srcBlock, new OperandStack());
2583: srcBlock.setTree(tree);
2584:
2585: tree = new Tree(snkBlock, new OperandStack());
2586: snkBlock.setTree(tree);
2587:
2588: tree = new Tree(iniBlock, new OperandStack());
2589: iniBlock.setTree(tree);
2590:
2591: if (method.codeLength() > 0) {
2592: tree.initLocals(methodParams(method));
2593: tree.addInstruction(new Instruction(Opcode.opcx_goto,
2594: method.firstBlock()));
2595:
2596: // (pr)
2597: if (catchBodies != null) {
2598: addHandlerEdges(iniBlock, catchBodies, labelPos, null,
2599: new HashSet());
2600: }
2601: }
2602: }
2603:
2604: /**
2605: * If a block may throws an exception (i.e. it is in a protected region),
2606: * there must be an edge in the control flow graph from that block to the
2607: * block that begins the exception handler. This method adds that edge.
2608: * <p>
2609: * We iterate over all of the Handler objects created for this FlowGraph. If
2610: * the block of interest lies in the protected region of the Handler, make
2611: * note of this fact and add an edge between the block and the first block
2612: * of the exception handler. Generate the expression tree for the exception
2613: * handler, if necessary.
2614: * <p>
2615: * Recursively call addHandlerEdges for the exception handler to accomodate
2616: * exception handlers within exception handlers.
2617: *
2618: * @param block
2619: * The "block of interest" (i.e. may throw an exception)
2620: * @param catchBodies
2621: * Maps "catch blocks" (first block of exception handler) to
2622: * "catch bodies" (block that begins the actual work of the
2623: * exception handler).
2624: * @param labelPos
2625: * Maps Labels to their offset in the code (needed for
2626: * buildTreeForBlock)
2627: * @param sub
2628: * The current Subroutine we're in (needed for
2629: * buildTreeForBlock).
2630: */
2631: private void addHandlerEdges(final Block block,
2632: final Map catchBodies, final Map labelPos,
2633: final Subroutine sub, final Set visited) {
2634: // (pr)
2635: if (visited.contains(block)) {
2636: return;
2637: }
2638: visited.add(block);
2639:
2640: final Tree tree = block.tree();
2641:
2642: Assert.isTrue(tree != null);
2643:
2644: final Iterator hiter = handlers.values().iterator();
2645:
2646: // Iterate over every Handler object created for this FlowGraph
2647: while (hiter.hasNext()) {
2648: final Handler handler = (Handler) hiter.next();
2649:
2650: boolean prot = false;
2651:
2652: // Determine whether or not the block of interest lies within
2653: // the Handler's protected region
2654: if (handler.protectedBlocks().contains(block)) {
2655: prot = true;
2656:
2657: } else {
2658: final Iterator succs = succs(block).iterator();
2659:
2660: while (succs.hasNext()) {
2661: final Block succ = (Block) succs.next();
2662:
2663: if (handler.protectedBlocks().contains(succ)) {
2664: prot = true;
2665: break;
2666: }
2667: }
2668: }
2669:
2670: // If the block of interest lies in a protected region, add an
2671: // edge in this CFG from the block to the Handler's "catch block"
2672: // (i.e. first block in Handler). Also examine the JumpStmt that
2673: // ends the block of interest and add the catch block to its list
2674: // of catch targets.
2675: //
2676: // Note that we do not want the init block to be protected.
2677: // This may happen if the first block in the CFG is protected.
2678: //
2679: // Next, obtain the "catch body" block (contains the real code)
2680: // of the method. If no expression tree has been constructed for
2681: // it, create a new OperandStack containing only the exception
2682: // object and build a new tree for it.
2683: //
2684: // Finally, recursively add the handler edges for the first block
2685: // of the exception handler.
2686: if (prot) { // && block != iniBlock) {
2687: final Block catchBlock = handler.catchBlock();
2688:
2689: final JumpStmt jump = (JumpStmt) tree.lastStmt();
2690:
2691: jump.catchTargets().add(catchBlock);
2692: addEdge(block, catchBlock);
2693:
2694: // Build the tree for the exception handler body.
2695: // We must have already added the edge from the catch block
2696: // to the catch body.
2697:
2698: final Block catchBody = (Block) catchBodies
2699: .get(catchBlock);
2700: Assert.isTrue(catchBody != null);
2701:
2702: if (catchBody.tree() == null) {
2703: final OperandStack s = new OperandStack();
2704: s.push(new StackExpr(0, Type.THROWABLE));
2705:
2706: buildTreeForBlock(catchBody, s, sub, labelPos,
2707: catchBodies);
2708: }
2709: // (pr)
2710: // if(!handler.catchBlock.equals(block)) {
2711: addHandlerEdges(catchBlock, catchBodies, labelPos, sub,
2712: visited);
2713: // }
2714: }
2715: }
2716: }
2717:
2718: /**
2719: * Dave sez: Builds the expression tree for a basic block and all blocks
2720: * reachable from that block. Basically, the block's code (Instructions and
2721: * Labels) are iterated over. The instructions are added to the tree with
2722: * calls to Tree#addInstruction. If an instruction invovles a change of
2723: * control flow (e.g. jsr, jump, switch), add an edge in the control flow
2724: * graph between the appropriate blocks. After all that is done, call
2725: * addHandlerEdges to add edges between blocks that may throw exceptions and
2726: * the blocks that handle those exceptions
2727: *
2728: * Nate sez: Visit a block other than source or catch. Since blocks are
2729: * visited depth-first, one predecessor was already visited, get the operand
2730: * stack state at the end of the predecessor block and use it as the initial
2731: * operand stack state for this block. We assume the class file passed
2732: * verification so which predecessor used shouldn't matter.
2733: *
2734: * @param block
2735: * The block for which to generate an expression tree.
2736: * @param stack
2737: * The operand stack before the block is executed.
2738: * @param sub
2739: * The current Subroutine.
2740: * @param labelPos
2741: * A mapping between Labels and their offset into the code
2742: * @param catchBodies
2743: * A mapping between "catch blocks" and "catch bodies"
2744: */
2745: private void buildTreeForBlock(final Block block,
2746: final OperandStack stack, final Subroutine sub,
2747: final Map labelPos, final Map catchBodies) {
2748: if (block.tree() != null) {
2749: return;
2750: }
2751:
2752: final Tree tree = new Tree(block, stack);
2753: block.setTree(tree);
2754:
2755: final Integer start = (Integer) labelPos.get(block.label());
2756: Integer targetStart;
2757:
2758: final ListIterator iter = method.code().listIterator(
2759: start.intValue() + 1);
2760:
2761: CODE:
2762: // Iterate over the code in the method...
2763: while (iter.hasNext()) {
2764: final Object ce = iter.next();
2765:
2766: if (ce instanceof Instruction) {
2767: final Instruction inst = (Instruction) ce;
2768:
2769: Block target; // The target of a jump
2770: Block next = null; // The Block following a jump
2771:
2772: // For jump instructions, look for the next Block
2773: if (inst.isJsr() || inst.isConditionalJump()) {
2774: int save = 0;
2775:
2776: while (iter.hasNext()) {
2777: final Object obj = iter.next();
2778: save++;
2779:
2780: if (obj instanceof Label) {
2781: if (((Label) obj).startsBlock()) {
2782: next = (Block) getNode(obj);
2783:
2784: while (save-- > 0) {
2785: iter.previous();
2786: }
2787:
2788: break;
2789: }
2790:
2791: } else {
2792: throw new RuntimeException(inst
2793: + " not followed by a label: "
2794: + obj + " (" + obj.getClass() + ")");
2795: }
2796: }
2797: }
2798:
2799: if (inst.opcodeClass() == Opcode.opcx_astore) {
2800: // We need the current subroutine in case this is a
2801: // returnAdress store.
2802: tree.addInstruction(inst, sub);
2803:
2804: } else if (inst.isRet()) {
2805: sub.setExit(block);
2806: tree.addInstruction(inst, sub);
2807:
2808: final Iterator paths = sub.paths().iterator();
2809:
2810: // Add edges from the exit Block of the Subroutine to the
2811: // Block that begins with the Subroutine's return address
2812: while (paths.hasNext()) {
2813: final Block[] path = (Block[]) paths.next();
2814: addEdge(block, path[1]);
2815: }
2816:
2817: break CODE;
2818:
2819: } else if (inst.isThrow() || inst.isReturn()) {
2820: tree.addInstruction(inst);
2821: addEdge(block, snkBlock);
2822: break CODE;
2823:
2824: } else if (inst.isJsr()) {
2825: Assert.isTrue(next != null, inst
2826: + " not followed by a block");
2827:
2828: tree.addInstruction(inst, next);
2829:
2830: final Label label = (Label) inst.operand();
2831:
2832: target = (Block) getNode(label);
2833: Assert.isTrue(target != null, inst
2834: + " target not found");
2835:
2836: final Subroutine nextSub = labelSub(label);
2837: setSubEntry(nextSub, target);
2838:
2839: buildTreeForBlock(target, tree.stack(), nextSub,
2840: labelPos, catchBodies);
2841: addEdge(block, target);
2842:
2843: if (nextSub.exit() != null) {
2844: buildTreeForBlock(next, nextSub.exit().tree()
2845: .stack(), sub, labelPos, catchBodies);
2846: addEdge(nextSub.exit(), next);
2847: }
2848:
2849: break CODE;
2850:
2851: } else if (inst.isGoto()) {
2852: tree.addInstruction(inst);
2853:
2854: final Label label = (Label) inst.operand();
2855:
2856: target = (Block) getNode(label);
2857: Assert.isTrue(target != null, inst
2858: + " target not found");
2859:
2860: addEdge(block, target);
2861:
2862: buildTreeForBlock(target, tree.stack(), sub,
2863: labelPos, catchBodies);
2864:
2865: break CODE;
2866:
2867: } else if (inst.isConditionalJump()) {
2868: Assert.isTrue(next != null, inst
2869: + " not followed by a block");
2870:
2871: tree.addInstruction(inst, next);
2872:
2873: final Label label = (Label) inst.operand();
2874:
2875: target = (Block) getNode(label);
2876: Assert.isTrue(target != null, inst
2877: + " target not found");
2878:
2879: addEdge(block, target);
2880: buildTreeForBlock(target, tree.stack(), sub,
2881: labelPos, catchBodies);
2882:
2883: addEdge(block, next);
2884: buildTreeForBlock(next, tree.stack(), sub,
2885: labelPos, catchBodies);
2886:
2887: break CODE;
2888:
2889: } else if (inst.isSwitch()) {
2890: tree.addInstruction(inst);
2891:
2892: final Switch sw = (Switch) inst.operand();
2893:
2894: target = (Block) getNode(sw.defaultTarget());
2895:
2896: addEdge(block, target);
2897:
2898: buildTreeForBlock(target, tree.stack(), sub,
2899: labelPos, catchBodies);
2900:
2901: for (int j = 0; j < sw.targets().length; j++) {
2902: target = (Block) getNode(sw.targets()[j]);
2903:
2904: addEdge(block, target);
2905:
2906: targetStart = (Integer) labelPos.get(target
2907: .label());
2908:
2909: buildTreeForBlock(target, tree.stack(), sub,
2910: labelPos, catchBodies);
2911: }
2912:
2913: break CODE;
2914:
2915: } else {
2916: tree.addInstruction(inst);
2917: }
2918:
2919: } else if (ce instanceof Label) {
2920: final Label label = (Label) ce;
2921:
2922: if (label.startsBlock()) {
2923: tree.addInstruction(new Instruction(
2924: Opcode.opcx_goto, label));
2925:
2926: final Block next = (Block) getNode(label);
2927:
2928: Assert.isTrue(next != null, "Block for " + label
2929: + " not found");
2930:
2931: addEdge(block, next);
2932: buildTreeForBlock(next, tree.stack(), sub,
2933: labelPos, catchBodies);
2934: break CODE;
2935: }
2936:
2937: tree.addLabel(label);
2938: }
2939: }
2940:
2941: addHandlerEdges(block, catchBodies, labelPos, sub,
2942: new HashSet());
2943: }
2944:
2945: /**
2946: * Returns an ArrayList of the parameters of a method, including the
2947: * receiver (non-static methods only).
2948: *
2949: * @param method
2950: * The method.
2951: */
2952: private ArrayList methodParams(final MethodEditor method) {
2953: final ArrayList locals = new ArrayList();
2954:
2955: int index = 0;
2956:
2957: if (!method.isStatic()) {
2958: // Add the this pointer to the locals.
2959: final Type type = method.declaringClass().type();
2960: final LocalVariable var = method.paramAt(index++);
2961: locals.add(new LocalExpr(var.index(), type));
2962: }
2963:
2964: final Type[] paramTypes = method.type().indexedParamTypes();
2965:
2966: for (int i = 0; i < paramTypes.length; i++) {
2967: if (paramTypes[i] != null) {
2968: final LocalVariable var = method.paramAt(index);
2969: locals.add(new LocalExpr(var.index(), paramTypes[i]));
2970: }
2971:
2972: index++;
2973: }
2974:
2975: return locals;
2976: }
2977:
2978: /**
2979: * Returns the basic blocks contained in this CFG in trace order. Trace
2980: * order implies that basic blocks that end with a conditional jump are
2981: * followed by their false branch and, where possible, that blocks that end
2982: * in an unconditional jump are followed by the block that is the target of
2983: * the unconditional branch.
2984: * <p>
2985: * The trace does not contain the source and the sink blocks.
2986: *
2987: * @return The basic Blocks in this CFG.
2988: */
2989: public List trace() {
2990: // The trace must include everything but the source and sink.
2991: Assert.isTrue(trace.size() == size() - 2, "trace contains "
2992: + trace.size() + " " + trace + " blocks, not "
2993: + (size() - 2) + " " + nodes());
2994: return trace;
2995: }
2996:
2997: /**
2998: * Commit changes back to the method editor.
2999: */
3000: public void commit() {
3001: method.clearCode();
3002:
3003: final CodeGenerator codegen = new CodeGenerator(method);
3004: visit(codegen);
3005:
3006: final Label endLabel = method.newLabel();
3007: method.addLabel(endLabel);
3008:
3009: // Add all the handlers back in the same order we got them.
3010: // This ensures that the correct catch clause will be called
3011: // when an exception is thrown.
3012: final Iterator iter = catchBlocks.iterator();
3013:
3014: while (iter.hasNext()) {
3015: final Block catchBlock = (Block) iter.next();
3016:
3017: final Handler handler = (Handler) handlers.get(catchBlock);
3018: Assert.isTrue(handler != null);
3019:
3020: Type type = handler.catchType();
3021:
3022: if (type.isNull()) {
3023: type = null;
3024: }
3025:
3026: Block begin = null;
3027:
3028: final Iterator blocks = trace().iterator();
3029:
3030: while (blocks.hasNext()) {
3031: final Block block = (Block) blocks.next();
3032:
3033: if (handler.protectedBlocks().contains(block)) {
3034: if (begin == null) {
3035: begin = block;
3036: }
3037: } else if (begin != null) {
3038: final TryCatch tc = new TryCatch(begin.label(),
3039: block.label(), catchBlock.label(), type);
3040:
3041: method.addTryCatch(tc);
3042:
3043: begin = null;
3044: }
3045: }
3046: }
3047: }
3048:
3049: /**
3050: * Returns the "Enter" block of this CFG. That is, the block through which
3051: * all paths enter.
3052: */
3053: public Block source() {
3054: return srcBlock;
3055: }
3056:
3057: /**
3058: * Returns the initialization block.
3059: *
3060: */
3061: public Block init() {
3062: return iniBlock;
3063: }
3064:
3065: /**
3066: * Returns the sink block. That is, the block through which all paths exit.
3067: */
3068: public Block sink() {
3069: return snkBlock;
3070: }
3071:
3072: /**
3073: * Returns the iterated dominance frontiers for several basic blocks.
3074: *
3075: * @see Block#domFrontier
3076: */
3077: public Collection iteratedDomFrontier(final Collection blocks) {
3078: return idf(blocks, false);
3079: }
3080:
3081: /**
3082: * Returns the iterated postdominance frontier for several basic blocks.
3083: *
3084: * @see Block#pdomFrontier
3085: */
3086: public Collection iteratedPdomFrontier(final Collection blocks) {
3087: return idf(blocks, true);
3088: }
3089:
3090: /**
3091: * Returns the iterated dominance frontier (DF+) for a given set of blocks.
3092: * <p>
3093: * The iterated dominance frontier for a set of nodes is defined to be the
3094: * union of the dominance frontiers of all the nodes in the set.
3095: * <p>
3096: * The iterated dominance frontier is particularly useful because the DF+ of
3097: * an assignment node for a variable (expression) specifies the nodes at
3098: * which phi-functions (PHI-functions) need to be inserted.
3099: *
3100: * @param blocks
3101: * The
3102: * @param reverse
3103: * Do we find the reverse (i.e. postdominance) dominance
3104: * frontier.
3105: *
3106: * @see SSAPRE#placePhis
3107: */
3108: private Collection idf(final Collection blocks, boolean reverse) {
3109: if (domEdgeModCount != edgeModCount) {
3110: computeDominators();
3111: }
3112:
3113: final HashSet idf = new HashSet();
3114:
3115: final HashSet inWorklist = new HashSet(blocks);
3116: final LinkedList worklist = new LinkedList(inWorklist);
3117:
3118: while (!worklist.isEmpty()) {
3119: final Block block = (Block) worklist.removeFirst();
3120:
3121: Collection df;
3122:
3123: if (!reverse) {
3124: df = block.domFrontier();
3125: } else {
3126: df = block.pdomFrontier();
3127: }
3128:
3129: final Iterator iter = df.iterator();
3130:
3131: while (iter.hasNext()) {
3132: final Block dfBlock = (Block) iter.next();
3133: idf.add(dfBlock);
3134:
3135: if (inWorklist.add(dfBlock)) {
3136: worklist.add(dfBlock);
3137: }
3138: }
3139: }
3140:
3141: return idf;
3142: }
3143:
3144: /**
3145: * @return A Collection containing the root(s) of this FlowGraph. In this
3146: * case there is only one root, so the Collection only contains the
3147: * source block.
3148: */
3149: public Collection roots() {
3150: return new AbstractCollection() {
3151: public int size() {
3152: return 1;
3153: }
3154:
3155: public boolean contains(final Object obj) {
3156: return obj == srcBlock;
3157: }
3158:
3159: public Iterator iterator() {
3160: return new Iterator() {
3161: Object next = srcBlock;
3162:
3163: public boolean hasNext() {
3164: return next != null;
3165: }
3166:
3167: public Object next() {
3168: final Object n = next;
3169: next = null;
3170: return n;
3171: }
3172:
3173: public void remove() {
3174: throw new UnsupportedOperationException();
3175: }
3176: };
3177: }
3178: };
3179: }
3180:
3181: /**
3182: * @return A Collection containing only the sink block.
3183: *
3184: * @see #roots
3185: */
3186: public Collection reverseRoots() {
3187: return new AbstractCollection() {
3188: public int size() {
3189: return 1;
3190: }
3191:
3192: public boolean contains(final Object obj) {
3193: return obj == snkBlock;
3194: }
3195:
3196: public Iterator iterator() {
3197: return new Iterator() {
3198: Object next = snkBlock;
3199:
3200: public boolean hasNext() {
3201: return next != null;
3202: }
3203:
3204: public Object next() {
3205: final Object n = next;
3206: next = null;
3207: return n;
3208: }
3209:
3210: public void remove() {
3211: throw new UnsupportedOperationException();
3212: }
3213: };
3214: }
3215: };
3216: }
3217:
3218: /**
3219: * Removes a node (a Block) from the graph.
3220: *
3221: * @param key
3222: * Block to remove
3223: */
3224: public void removeNode(final Object key) {
3225: final Block block = (Block) getNode(key);
3226: removeBlock(block);
3227: }
3228:
3229: /**
3230: * Returns A Map mapping the first block in an exception handler to its
3231: * <tt>Handler</tt> object.
3232: *
3233: * @see Handler
3234: */
3235: public Map handlersMap() {
3236: return handlers;
3237: }
3238:
3239: /**
3240: * Returns all of the <tt>Handler</tt> objects in this CFG.
3241: */
3242: public Collection handlers() {
3243: return handlers.values();
3244: }
3245:
3246: /**
3247: * Returns the<tt>Block</tt>s in this CFG that begin exception handlers.
3248: */
3249: public List catchBlocks() {
3250: return catchBlocks;
3251: }
3252:
3253: private void removeBlock(final Block block) {
3254: trace.remove(block);
3255: subroutines.remove(block);
3256: catchBlocks.remove(block);
3257: handlers.remove(block);
3258:
3259: // edgeModCount is incremented by super.removeNode().
3260: // Dominators will be recomputed automatically if needed, so just
3261: // clear the pointers to let the GC work.
3262:
3263: block.setDomParent(null);
3264: block.setPdomParent(null);
3265: block.domChildren().clear();
3266: block.pdomChildren().clear();
3267: block.domFrontier().clear();
3268: block.pdomFrontier().clear();
3269:
3270: Iterator iter = handlers.values().iterator();
3271:
3272: while (iter.hasNext()) {
3273: final Handler handler = (Handler) iter.next();
3274: handler.protectedBlocks().remove(block);
3275: }
3276:
3277: iter = subroutines.values().iterator();
3278:
3279: while (iter.hasNext()) {
3280: final Subroutine sub = (Subroutine) iter.next();
3281: sub.removePathsContaining(block);
3282:
3283: if (sub.exit() == block) {
3284: sub.setExit(null);
3285: }
3286: }
3287:
3288: if (block.tree() != null) {
3289: iter = block.tree().stmts().iterator();
3290:
3291: while (iter.hasNext()) {
3292: final Stmt s = (Stmt) iter.next();
3293:
3294: if (s instanceof LabelStmt) {
3295: final Label label = ((LabelStmt) s).label();
3296: label.setStartsBlock(false);
3297: iniBlock.tree().addStmt(new LabelStmt(label));
3298: }
3299:
3300: s.cleanup();
3301: }
3302: }
3303:
3304: super .removeNode(block.label());
3305: }
3306:
3307: /**
3308: * Returns the blocks that a given block dominates.
3309: */
3310: public Collection domChildren(final Block block) {
3311: if (domEdgeModCount != edgeModCount) {
3312: computeDominators();
3313: }
3314:
3315: return block.domChildren();
3316: }
3317:
3318: /**
3319: * Returns the <tt>Block</tt> that dominates a given block.
3320: */
3321: public Block domParent(final Block block) {
3322: if (domEdgeModCount != edgeModCount) {
3323: computeDominators();
3324: }
3325:
3326: return block.domParent();
3327: }
3328:
3329: /**
3330: * Returns the type of a given block. A block's type is one of
3331: * <tt>Block.NON_HEADER</tt>, <tt>Block.IRREDUCIBLE</tt>, or
3332: * <tt>Block.REDUCIBLE</tt>.
3333: */
3334: public int blockType(final Block block) {
3335: if (loopEdgeModCount != edgeModCount) {
3336: buildLoopTree();
3337: }
3338:
3339: return block.blockType();
3340: }
3341:
3342: /**
3343: * Returns the depth of the loop in which a block is contained. The block
3344: * must be contained in a loop. The procedure has depth 0. A loop (while,
3345: * for, etc.) at the procedure level has depth 1. Depth increases as loops
3346: * are nested.
3347: *
3348: * @param block
3349: * A block whose depth we are interested in.
3350: *
3351: * @see #loopLevel
3352: */
3353: public int loopDepth(final Block block) {
3354: if (loopEdgeModCount != edgeModCount) {
3355: buildLoopTree();
3356: }
3357:
3358: if ((block == srcBlock)
3359: || (block.blockType() != Block.NON_HEADER)) {
3360: final LoopNode loop = (LoopNode) loopTree.getNode(block);
3361: Assert.isTrue(loop != null, "no loop for " + block);
3362: return loop.depth;
3363: }
3364:
3365: if (block.header() != null) {
3366: final LoopNode loop = (LoopNode) loopTree.getNode(block
3367: .header());
3368: Assert
3369: .isTrue(loop != null, "no loop for "
3370: + block.header());
3371: return loop.depth;
3372: }
3373:
3374: throw new RuntimeException();
3375: }
3376:
3377: /**
3378: * Returns the level of the loop containing a given block. The innermost
3379: * loops have level 0. The level increases as you go outward to higher loop
3380: * nestings. For any given loop, the level is the maximum possible.
3381: * <p>
3382: *
3383: * <pre>
3384: * procedure()
3385: * {
3386: * // Depth 0, Level 2 (max possible)
3387: * while()
3388: * {
3389: * // Depth 1, Level 1
3390: * while()
3391: * {
3392: * // Depth 2, Level 0
3393: * }
3394: * }
3395: * while()
3396: * {
3397: * // Depth 1, Level 0
3398: * }
3399: * }
3400: * </pre>
3401: *
3402: * @param block
3403: * A block whose loop level we want to know. This block must be
3404: * contained in a loop.
3405: */
3406: public int loopLevel(final Block block) {
3407: if (loopEdgeModCount != edgeModCount) {
3408: buildLoopTree();
3409: }
3410:
3411: if ((block == srcBlock)
3412: || (block.blockType() != Block.NON_HEADER)) {
3413: final LoopNode loop = (LoopNode) loopTree.getNode(block);
3414: Assert.isTrue(loop != null, "no loop for " + block);
3415: return loop.level;
3416: }
3417:
3418: if (block.header() != null) {
3419: final LoopNode loop = (LoopNode) loopTree.getNode(block
3420: .header());
3421: Assert
3422: .isTrue(loop != null, "no loop for "
3423: + block.header());
3424: return loop.level;
3425: }
3426:
3427: throw new RuntimeException();
3428: }
3429:
3430: /**
3431: * Returns the loop header of the loop containing a given block. The loop
3432: * header is the block that dominates all of the blocks in the loop.
3433: */
3434: public Block loopHeader(final Block block) {
3435: if (loopEdgeModCount != edgeModCount) {
3436: buildLoopTree();
3437: }
3438:
3439: return block.header();
3440: }
3441:
3442: /**
3443: * Returns the blocks in the flow graph sorted in pre-order.
3444: */
3445: public List preOrder() {
3446: return super .preOrder();
3447: }
3448:
3449: /**
3450: * Returns the blocks in the flow graph sorted in post-order.
3451: */
3452: public List postOrder() {
3453: return super .postOrder();
3454: }
3455:
3456: /**
3457: * Returns the postdominator children of a given block.
3458: *
3459: * @see Block#pdomChildren
3460: */
3461: public Collection pdomChildren(final Block block) {
3462: if (domEdgeModCount != edgeModCount) {
3463: computeDominators();
3464: }
3465:
3466: return block.pdomChildren();
3467: }
3468:
3469: /**
3470: * Returns the postdominator parent of a given block.
3471: *
3472: * @see Block#pdomParent
3473: */
3474: public Block pdomParent(final Block block) {
3475: if (domEdgeModCount != edgeModCount) {
3476: computeDominators();
3477: }
3478:
3479: return block.pdomParent();
3480: }
3481:
3482: /**
3483: * Returns the dominance frontier of a given block.
3484: *
3485: * @see Block#domFrontier
3486: */
3487: public Collection domFrontier(final Block block) {
3488: if (domEdgeModCount != edgeModCount) {
3489: computeDominators();
3490: }
3491:
3492: return block.domFrontier();
3493: }
3494:
3495: /**
3496: * Returns the postdominance frontier of a given block.
3497: *
3498: * @see Block#pdomFrontier
3499: */
3500: public Collection pdomFrontier(final Block block) {
3501: if (domEdgeModCount != edgeModCount) {
3502: computeDominators();
3503: }
3504:
3505: return block.pdomFrontier();
3506: }
3507:
3508: /**
3509: * A LoopNode is a node in the loop tree. The loop tree is represents the
3510: * nesting of loops in the method being modeled in this CFG.
3511: */
3512: class LoopNode extends GraphNode {
3513: Block header;
3514:
3515: int depth;
3516:
3517: int level;
3518:
3519: Set elements;
3520:
3521: public LoopNode(final Block header) {
3522: this .header = header;
3523: this .depth = 1;
3524: this .level = 1;
3525: this .elements = new HashSet();
3526: this .elements.add(header);
3527: }
3528:
3529: public String toString() {
3530: return "level=" + level + " depth=" + depth + " header="
3531: + header + " " + elements;
3532: }
3533: }
3534:
3535: /**
3536: * Returns a brief textual description of this <tt>FlowGraph</tt>, namely
3537: * the name of the method it represents.
3538: */
3539: public String toString() {
3540: return ("CFG for " + method);
3541: }
3542: }
|