0001: /* FlowBlock Copyright (C) 1998-2002 Jochen Hoenicke.
0002: *
0003: * This program is free software; you can redistribute it and/or modify
0004: * it under the terms of the GNU Lesser General Public License as published by
0005: * the Free Software Foundation; either version 2, or (at your option)
0006: * any later version.
0007: *
0008: * This program is distributed in the hope that it will be useful,
0009: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0010: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0011: * GNU General Public License for more details.
0012: *
0013: * You should have received a copy of the GNU Lesser General Public License
0014: * along with this program; see the file COPYING.LESSER. If not, write to
0015: * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
0016: *
0017: * $Id: FlowBlock.java.in,v 4.5.2.4 2002/05/28 17:34:09 hoenicke Exp $
0018: */
0019:
0020: package jode.flow;
0021:
0022: import jode.GlobalOptions;
0023: import jode.AssertError;
0024: import jode.decompiler.TabbedPrintWriter;
0025: import jode.decompiler.MethodAnalyzer;
0026: import jode.decompiler.LocalInfo;
0027: import jode.expr.Expression;
0028: import jode.expr.CombineableOperator;
0029: import jode.util.SimpleMap;
0030: import jode.util.SimpleSet;
0031:
0032: import java.util.Map;
0033: import java.util.Iterator;
0034: import java.util.Set;
0035: import java.util.ArrayList;
0036: import java.util.List;
0037:
0038: /**
0039: * A flow block is the structure of which the flow graph consists. A
0040: * flow block contains structured code together with some conditional
0041: * or unconditional jumps to the head of other flow blocks.
0042: *
0043: * We do a T1/T2 analysis to combine all flow blocks to a single. If
0044: * the graph isn't reducible that doesn't work, but java can only
0045: * produce reducible flow graphs.
0046: *
0047: * We don't use the notion of basic flow graphs. A flow block may be
0048: * anything from a single bytecode opcode, to the whole method.
0049: */
0050: public class FlowBlock {
0051:
0052: public static FlowBlock END_OF_METHOD;
0053: public static FlowBlock NEXT_BY_ADDR;
0054:
0055: static {
0056: END_OF_METHOD = new FlowBlock(null, Integer.MAX_VALUE);
0057: END_OF_METHOD.appendBlock(new EmptyBlock(), 0);
0058: END_OF_METHOD.label = "END_OF_METHOD";
0059:
0060: NEXT_BY_ADDR = new FlowBlock(null, -1);
0061: NEXT_BY_ADDR.appendBlock(new DescriptionBlock("FALL THROUGH"),
0062: 0);
0063: NEXT_BY_ADDR.label = "NEXT_BY_ADDR";
0064: }
0065:
0066: /**
0067: * The method analyzer. This is used to pretty printing the
0068: * Types and to get information about all locals in this code.
0069: */
0070: MethodAnalyzer method;
0071:
0072: /**
0073: * The in locals. This are the locals, which are used in this
0074: * flow block and whose values may be the result of a assignment
0075: * outside of this flow block. That means, that there is a
0076: * path from the start of the flow block to the instruction that
0077: * uses that variable, on which it is never assigned
0078: */
0079: private SlotSet in = new SlotSet();
0080: /**
0081: * The gen locals. This are the locals, to which are written
0082: * somewhere in this flow block. This is only used for try
0083: * catch blocks.
0084: */
0085: VariableSet gen = new VariableSet();
0086:
0087: /**
0088: * The starting address of this flow block. This is mainly used
0089: * to produce the source code in code order.
0090: */
0091: private int addr;
0092:
0093: /**
0094: * The length of the structured block, only needed at the beginning.
0095: */
0096: private int length;
0097:
0098: /**
0099: * The outermost structructed block in this flow block.
0100: */
0101: StructuredBlock block;
0102:
0103: /**
0104: * The last modified structured block. This is probably the
0105: * last instruction in the outermost block, that is in the
0106: * outermost chain of SequentialBlock.
0107: */
0108: StructuredBlock lastModified;
0109:
0110: /**
0111: * This contains a map of all successing flow blocks and there
0112: * jumps. The key of this map are the flow blocks, while
0113: * the elements is the first jump to that flow block. The other
0114: * jumps are accessible via the jump.next field.
0115: */
0116: private Map successors = new SimpleMap();
0117:
0118: /**
0119: * This is a vector of flow blocks, which reference this block.
0120: * Only if this vector contains exactly one element, it can be
0121: * moved into the preceding flow block.
0122: *
0123: * If this vectors contains the null element, this is the first
0124: * flow block in a method.
0125: */
0126: List predecessors = new ArrayList();
0127:
0128: /**
0129: * This is a pointer to the next flow block in byte code order.
0130: * It is null for the last flow block.
0131: */
0132: FlowBlock nextByAddr;
0133:
0134: /**
0135: * This is a pointer to the previous flow block in byte code order.
0136: * It is null for the first flow block.
0137: */
0138: FlowBlock prevByAddr;
0139:
0140: /**
0141: * The stack map. This tells how many objects are on stack at
0142: * begin of the flow block, and to what locals they are maped.
0143: * @see mapStackToLocal
0144: */
0145: VariableStack stackMap;
0146:
0147: static class SuccessorInfo {
0148: /**
0149: * The kill locals. This are the slots, which must be
0150: * overwritten in this block on every path to the successor.
0151: * That means, that all paths from the start of the current
0152: * flow block to the successor contain (unconditional)
0153: * assignments to this slot.
0154: */
0155: SlotSet kill;
0156:
0157: /**
0158: * The gen locals. This are the locals, which can be
0159: * overwritten in this block on a path to the successor. That
0160: * means, that there exists a path form the start of the
0161: * current flow block to the successor that contains a
0162: * assignments to this local, and that is not overwritten
0163: * afterwards.
0164: */
0165: VariableSet gen;
0166:
0167: /**
0168: * The linked list of jumps.
0169: */
0170: Jump jumps;
0171: }
0172:
0173: /**
0174: * The default constructor. Creates a new empty flowblock.
0175: */
0176: public FlowBlock(MethodAnalyzer method, int addr) {
0177: this .method = method;
0178: this .addr = addr;
0179: }
0180:
0181: public final int getNextAddr() {
0182: return addr + length;
0183: }
0184:
0185: public boolean hasNoJumps() {
0186: return successors.size() == 0 && predecessors.size() == 0;
0187: }
0188:
0189: /**
0190: * This method resolves some of the jumps to successor.
0191: * @param jumps The list of jumps with that successor.
0192: * @param succ The successing flow block.
0193: * @return The remaining jumps, that couldn't be resolved.
0194: */
0195: public Jump resolveSomeJumps(Jump jumps, FlowBlock succ) {
0196: /* We will put all jumps that we can not resolve into this
0197: * linked list.
0198: */
0199: Jump remainingJumps = null;
0200:
0201: if (lastModified.jump == null) {
0202: /* This can happen if lastModified is a breakable block, and
0203: * there is no break to it yet. We give lastModified this jump
0204: * as successor since many other routines rely on this.
0205: */
0206: Jump lastJump = new Jump(succ);
0207: lastModified.setJump(lastJump);
0208: remainingJumps = lastJump;
0209: }
0210:
0211: for (Jump jump = jumps; jump != null; jump = jump.next) {
0212: /* First swap all conditional blocks, that have two jumps,
0213: * so that the jump to succ will be on the outside.
0214: */
0215: if (jump.prev.outer instanceof ConditionalBlock
0216: && jump.prev.outer.jump != null) {
0217:
0218: StructuredBlock prev = jump.prev;
0219: ConditionalBlock cb = (ConditionalBlock) prev.outer;
0220: Expression instr = cb.getInstruction();
0221:
0222: cb.setInstruction(instr.negate());
0223: cb.swapJump(prev);
0224: }
0225: }
0226: next_jump: while (jumps != null) {
0227: Jump jump = jumps;
0228: jumps = jumps.next;
0229:
0230: /* if the jump is the jump of lastModified, skip it.
0231: */
0232: if (jump.prev == lastModified) {
0233: jump.next = remainingJumps;
0234: remainingJumps = jump;
0235: continue;
0236: }
0237:
0238: /* jump.prev.outer is not null, otherwise jump.prev would
0239: * be lastModified.
0240: */
0241:
0242: if (jump.prev.outer instanceof ConditionalBlock) {
0243: StructuredBlock prev = jump.prev;
0244: ConditionalBlock cb = (ConditionalBlock) prev.outer;
0245: Expression instr = cb.getInstruction();
0246:
0247: /* This is a jump inside an ConditionalBlock.
0248: *
0249: * cb is the conditional block,
0250: * prev the empty block containing the jump
0251: * instr is the condition */
0252:
0253: if (cb.jump != null) {
0254: /* This can only happen if cb also jumps to succ.
0255: * This is a weired "if (cond) empty"-block. We
0256: * transform it by hand.
0257: */
0258: prev.removeJump();
0259: IfThenElseBlock ifBlock = new IfThenElseBlock(cb
0260: .getInstruction().negate());
0261: ifBlock.moveDefinitions(cb, prev);
0262: ifBlock.replace(cb);
0263: ifBlock.moveJump(cb.jump);
0264: ifBlock.setThenBlock(prev);
0265: if (cb == lastModified)
0266: lastModified = ifBlock;
0267: continue;
0268: }
0269:
0270: /* Now cb.jump is null, so cb.outer is not null,
0271: * since otherwise it would have no successor. */
0272:
0273: if (cb.outer instanceof LoopBlock
0274: || (cb.outer instanceof SequentialBlock
0275: && cb.outer.getSubBlocks()[0] == cb && cb.outer.outer instanceof LoopBlock)) {
0276:
0277: /* If this is the first instruction of a
0278: * while/for(true) block, make this the loop condition
0279: * (negated of course).
0280: */
0281:
0282: LoopBlock loopBlock = (cb.outer instanceof LoopBlock) ? (LoopBlock) cb.outer
0283: : (LoopBlock) cb.outer.outer;
0284:
0285: if (loopBlock.getCondition() == LoopBlock.TRUE
0286: && loopBlock.getType() != LoopBlock.DOWHILE
0287: && (loopBlock.jumpMayBeChanged() || loopBlock
0288: .getNextFlowBlock() == succ)) {
0289:
0290: if (loopBlock.jump == null) {
0291: /* consider this jump again */
0292: loopBlock.moveJump(jump);
0293: jumps = jump;
0294: } else
0295: jump.prev.removeJump();
0296:
0297: loopBlock.setCondition(instr.negate());
0298: loopBlock.moveDefinitions(cb, null);
0299: cb.removeBlock();
0300: continue;
0301: }
0302:
0303: } else if (cb.outer instanceof SequentialBlock
0304: && cb.outer.getSubBlocks()[1] == cb) {
0305:
0306: /* And now for do/while loops, where the jump is
0307: * at the end of the loop.
0308: */
0309:
0310: /* First find the beginning of the loop */
0311: StructuredBlock sb = cb.outer.outer;
0312: while (sb instanceof SequentialBlock) {
0313: sb = sb.outer;
0314: }
0315: /* sb is now the first and cb is the last
0316: * instruction in the current block.
0317: */
0318: if (sb instanceof LoopBlock) {
0319: LoopBlock loopBlock = (LoopBlock) sb;
0320: if (loopBlock.getCondition() == LoopBlock.TRUE
0321: && loopBlock.getType() == LoopBlock.WHILE
0322: && (loopBlock.jumpMayBeChanged() || loopBlock
0323: .getNextFlowBlock() == succ)) {
0324:
0325: if (loopBlock.jump == null) {
0326: /* consider this jump again */
0327: loopBlock.moveJump(jump);
0328: jumps = jump;
0329: } else
0330: jump.prev.removeJump();
0331:
0332: loopBlock.setType(LoopBlock.DOWHILE);
0333: loopBlock.setCondition(instr.negate());
0334: loopBlock.moveDefinitions(cb, null);
0335: cb.removeBlock();
0336: continue;
0337: }
0338: }
0339: }
0340:
0341: /* This is still a jump inside an ConditionalBlock.
0342: *
0343: * cb is the conditional block,
0344: * prev the empty block containing the jump
0345: * instr is the condition */
0346:
0347: /* replace all conditional jumps to the successor, which
0348: * are followed by a block which has the end of the block
0349: * as normal successor, with "if (not condition) block":
0350: *
0351: * /IF cond GOTO succ if (!cond)
0352: * \block ===> block
0353: * -> normal Succesor succ -> normal Successor succ
0354: */
0355: if (cb.outer instanceof SequentialBlock
0356: && cb.outer.getSubBlocks()[0] == cb
0357: && (cb.outer.getNextFlowBlock() == succ || cb.outer
0358: .jumpMayBeChanged())) {
0359:
0360: SequentialBlock sequBlock = (SequentialBlock) cb.outer;
0361:
0362: IfThenElseBlock newIfBlock = new IfThenElseBlock(
0363: instr.negate());
0364: StructuredBlock thenBlock = sequBlock
0365: .getSubBlocks()[1];
0366:
0367: newIfBlock.moveDefinitions(sequBlock, thenBlock);
0368: newIfBlock.replace(sequBlock);
0369: newIfBlock.setThenBlock(thenBlock);
0370:
0371: if (thenBlock.contains(lastModified)) {
0372: if (lastModified.jump.destination == succ) {
0373: newIfBlock.moveJump(lastModified.jump);
0374: lastModified = newIfBlock;
0375: jump.prev.removeJump();
0376: continue;
0377: }
0378: lastModified = newIfBlock;
0379: }
0380:
0381: newIfBlock.moveJump(jump);
0382: /* consider this jump again */
0383: jumps = jump;
0384: continue;
0385: }
0386: } else {
0387:
0388: /* remove this jump if it jumps to the
0389: * getNextFlowBlock(). */
0390: if (jump.destination == jump.prev.outer
0391: .getNextFlowBlock(jump.prev)) {
0392: jump.prev.removeJump();
0393: continue;
0394: }
0395:
0396: /* Now find the real outer block, that is ascend the chain
0397: * of SequentialBlocks.
0398: *
0399: * Note that only the last instr in a SequentialBlock chain
0400: * can have a jump.
0401: *
0402: * We rely on the fact, that instanceof returns false
0403: * for a null pointer.
0404: */
0405: StructuredBlock sb = jump.prev.outer;
0406: while (sb instanceof SequentialBlock)
0407: sb = sb.outer;
0408:
0409: /* if this is an unconditional jump at the end of a
0410: * then block belonging to a if-then block without
0411: * else part, and the if block has a jump then replace
0412: * the if-then block with a if-then-else block with an
0413: * else block that contains only the jump and move the
0414: * unconditional jump to the if. (The jump in the else
0415: * block will later probably be replaced with a break,
0416: * continue or return statement.)
0417: */
0418: if (sb instanceof IfThenElseBlock) {
0419: IfThenElseBlock ifBlock = (IfThenElseBlock) sb;
0420: if (ifBlock.elseBlock == null
0421: && ifBlock.jump != null) {
0422: ifBlock.setElseBlock(new EmptyBlock());
0423: ifBlock.elseBlock.moveJump(ifBlock.jump);
0424: ifBlock.moveJump(jump);
0425: /* consider this jump again */
0426: jumps = jump;
0427: continue;
0428: }
0429: }
0430:
0431: /* if this is a jump at the end of a then block belonging
0432: * to a if-then block without else part, and the if-then
0433: * block is followed by a single block, then replace the
0434: * if-then block with a if-then-else block and move the
0435: * unconditional jump to the if.
0436: */
0437: if (sb instanceof IfThenElseBlock
0438: && sb.outer instanceof SequentialBlock
0439: && sb.outer.getSubBlocks()[0] == sb) {
0440:
0441: IfThenElseBlock ifBlock = (IfThenElseBlock) sb;
0442: SequentialBlock sequBlock = (SequentialBlock) sb.outer;
0443: StructuredBlock elseBlock = sequBlock.subBlocks[1];
0444:
0445: if (ifBlock.elseBlock == null
0446: && (elseBlock.getNextFlowBlock() == succ
0447: || elseBlock.jump != null || elseBlock
0448: .jumpMayBeChanged())) {
0449:
0450: ifBlock.replace(sequBlock);
0451: ifBlock.setElseBlock(elseBlock);
0452:
0453: if (elseBlock.contains(lastModified)) {
0454: if (lastModified.jump.destination == succ) {
0455: ifBlock.moveJump(lastModified.jump);
0456: lastModified = ifBlock;
0457: jump.prev.removeJump();
0458: continue;
0459: }
0460: lastModified = ifBlock;
0461: }
0462:
0463: /* consider this jump again */
0464: ifBlock.moveJump(jump);
0465: jumps = jump;
0466: continue;
0467: }
0468: }
0469: }
0470:
0471: /* if this is a jump in a breakable block, and that block
0472: * has not yet a next block, then create a new jump to that
0473: * successor.
0474: *
0475: * The break to the block will be generated later.
0476: */
0477:
0478: for (StructuredBlock surrounder = jump.prev.outer; surrounder != null; surrounder = surrounder.outer) {
0479: if (surrounder instanceof BreakableBlock) {
0480: if (surrounder.getNextFlowBlock() == succ)
0481: /* We can break to that block; this is done later. */
0482: break;
0483:
0484: if (surrounder.jumpMayBeChanged()) {
0485: surrounder.setJump(new Jump(succ));
0486: /* put surrounder in todo list */
0487: surrounder.jump.next = jumps;
0488: jumps = surrounder.jump;
0489: /* The break is inserted later */
0490: break;
0491: }
0492: if (succ == END_OF_METHOD) {
0493: /* If the jump can be replaced by a return
0494: * we won't do labeled breaks, so we must
0495: * stop here
0496: */
0497: break;
0498: }
0499: }
0500: }
0501: jump.next = remainingJumps;
0502: remainingJumps = jump;
0503: }
0504: return remainingJumps;
0505: }
0506:
0507: /**
0508: * Resolve remaining jumps to the successor by generating break
0509: * instructions. As last resort generate a do while(false) block.
0510: * @param jumps The jump list that need to be resolved.
0511: */
0512: void resolveRemaining(Jump jumps) {
0513: LoopBlock doWhileFalse = null;
0514: StructuredBlock outerMost = lastModified;
0515: boolean removeLast = false;
0516: next_jump: for (; jumps != null; jumps = jumps.next) {
0517: StructuredBlock prevBlock = jumps.prev;
0518:
0519: if (prevBlock == lastModified) {
0520: /* handled below */
0521: removeLast = true;
0522: continue;
0523: }
0524:
0525: int breaklevel = 0;
0526: BreakableBlock breakToBlock = null;
0527: for (StructuredBlock surrounder = prevBlock.outer; surrounder != null; surrounder = surrounder.outer) {
0528: if (surrounder instanceof BreakableBlock) {
0529: breaklevel++;
0530: if (surrounder.getNextFlowBlock() == jumps.destination) {
0531: breakToBlock = (BreakableBlock) surrounder;
0532: break;
0533: }
0534: }
0535: }
0536:
0537: prevBlock.removeJump();
0538:
0539: if (breakToBlock == null) {
0540: /* Nothing else helped, so put a do/while(0)
0541: * block around outerMost and break to that
0542: * block.
0543: */
0544: if (doWhileFalse == null) {
0545: doWhileFalse = new LoopBlock(LoopBlock.DOWHILE,
0546: LoopBlock.FALSE);
0547: }
0548: /* Adapt outermost, so that it contains the break. */
0549: while (!outerMost.contains(prevBlock))
0550: outerMost = outerMost.outer;
0551: prevBlock.appendBlock(new BreakBlock(doWhileFalse,
0552: breaklevel > 0));
0553: } else
0554: prevBlock.appendBlock(new BreakBlock(breakToBlock,
0555: breaklevel > 1));
0556: }
0557:
0558: if (removeLast)
0559: lastModified.removeJump();
0560:
0561: if (doWhileFalse != null) {
0562: doWhileFalse.replace(outerMost);
0563: doWhileFalse.setBody(outerMost);
0564: lastModified = doWhileFalse;
0565: }
0566: }
0567:
0568: /**
0569: * Move the successors of the given flow block to this flow block.
0570: * @param succ the other flow block
0571: */
0572: void mergeSuccessors(FlowBlock succ) {
0573: /* Merge the successors from the successing flow block
0574: */
0575: Iterator iter = succ.successors.entrySet().iterator();
0576: while (iter.hasNext()) {
0577: Map.Entry entry = (Map.Entry) iter.next();
0578: FlowBlock dest = (FlowBlock) entry.getKey();
0579: SuccessorInfo hisInfo = (SuccessorInfo) entry.getValue();
0580: SuccessorInfo myInfo = (SuccessorInfo) successors.get(dest);
0581:
0582: if (dest != END_OF_METHOD)
0583: dest.predecessors.remove(succ);
0584: if (myInfo == null) {
0585: if (dest != END_OF_METHOD)
0586: dest.predecessors.add(this );
0587: successors.put(dest, hisInfo);
0588: } else {
0589: myInfo.gen.addAll(hisInfo.gen);
0590: myInfo.kill.retainAll(hisInfo.kill);
0591: Jump myJumps = myInfo.jumps;
0592: while (myJumps.next != null)
0593: myJumps = myJumps.next;
0594: myJumps.next = hisInfo.jumps;
0595: }
0596: }
0597: }
0598:
0599: /**
0600: * Fixes the addr chained list, after merging this block with succ.
0601: */
0602: public void mergeAddr(FlowBlock succ) {
0603: if (succ.nextByAddr == this || succ.prevByAddr == null) {
0604: /* Merge succ with its nextByAddr.
0605: * Note: succ.nextByAddr != null, since this is on the
0606: * nextByAddr chain. */
0607: succ.nextByAddr.addr = succ.addr;
0608: succ.nextByAddr.length += succ.length;
0609:
0610: succ.nextByAddr.prevByAddr = succ.prevByAddr;
0611: if (succ.prevByAddr != null)
0612: succ.prevByAddr.nextByAddr = succ.nextByAddr;
0613: } else {
0614: /* Merge succ with its prevByAddr */
0615: succ.prevByAddr.length += succ.length;
0616:
0617: succ.prevByAddr.nextByAddr = succ.nextByAddr;
0618: if (succ.nextByAddr != null)
0619: succ.nextByAddr.prevByAddr = succ.prevByAddr;
0620: }
0621: }
0622:
0623: /**
0624: * Updates the in/out-Vectors of the structured block of the
0625: * successing flow block simultanous to a T2 transformation.
0626: * @param successor The flow block which is unified with this flow
0627: * block.
0628: * @param jumps The list of jumps to successor in this block.
0629: * @return The variables that must be defined in this block.
0630: */
0631: void updateInOut(FlowBlock successor, SuccessorInfo succInfo) {
0632: /* First get the gen/kill sets of all jumps to successor and
0633: * calculate the intersection.
0634: */
0635: SlotSet kills = succInfo.kill;
0636: VariableSet gens = succInfo.gen;
0637:
0638: /* Merge the locals used in successing block with those written
0639: * by this blocks.
0640: */
0641: successor.in.merge(gens);
0642:
0643: /* The ins of the successor that are not killed
0644: * (i.e. unconditionally overwritten) by this block are new
0645: * ins for this block.
0646: */
0647: SlotSet newIn = (SlotSet) successor.in.clone();
0648: newIn.removeAll(kills);
0649:
0650: /* The gen/kill sets must be updated for every jump
0651: * in the other block */
0652: Iterator i = successor.successors.values().iterator();
0653: while (i.hasNext()) {
0654: SuccessorInfo succSuccInfo = (SuccessorInfo) i.next();
0655: succSuccInfo.gen.mergeGenKill(gens, succSuccInfo.kill);
0656: if (successor != this )
0657: succSuccInfo.kill.mergeKill(kills);
0658: }
0659: this .in.addAll(newIn);
0660: this .gen.addAll(successor.gen);
0661:
0662: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
0663: GlobalOptions.err.println("UpdateInOut: gens : " + gens);
0664: GlobalOptions.err.println(" kills: " + kills);
0665: GlobalOptions.err.println(" s.in : "
0666: + successor.in);
0667: GlobalOptions.err.println(" in : " + in);
0668: }
0669: }
0670:
0671: /**
0672: * Updates the in/out-Vectors of the structured block of the
0673: * successing flow block for a try catch block. The main difference
0674: * to updateInOut in FlowBlock is, that this function works, as if
0675: * every instruction would have a jump. This is because every
0676: * instruction can throw an exception and thus enter the catch block.<br>
0677: *
0678: * For example this code prints <code>0</code>:
0679: * <pre>
0680: * int a=3;
0681: * try {
0682: * a = 5 / (a=0);
0683: * } catch (DivideByZeroException ex) {
0684: * System.out.println(a);
0685: * }
0686: * </pre>
0687: *
0688: * @param successor The flow block which is unified with this flow
0689: * block.
0690: * @return The variables that must be defined in this block.
0691: */
0692: public void updateInOutCatch(FlowBlock catchFlow) {
0693: VariableSet gens = ((TryBlock) block).gen;
0694:
0695: /* Merge the locals used in the catch block with those written
0696: * by the try block
0697: */
0698: catchFlow.in.merge(gens);
0699:
0700: /* The gen/kill sets must be updated for every jump
0701: * in the other block */
0702: Iterator i = catchFlow.successors.values().iterator();
0703: while (i.hasNext()) {
0704: SuccessorInfo succSuccInfo = (SuccessorInfo) i.next();
0705: succSuccInfo.gen.mergeGenKill(gens, succSuccInfo.kill);
0706: }
0707: in.addAll(catchFlow.in);
0708: gen.addAll(catchFlow.gen);
0709:
0710: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
0711: GlobalOptions.err.println("UpdateInOutCatch: gens : "
0712: + gens);
0713: GlobalOptions.err.println(" s.in : "
0714: + catchFlow.in);
0715: GlobalOptions.err.println(" in : " + in);
0716: }
0717: }
0718:
0719: /**
0720: * Checks if the FlowBlock and its StructuredBlocks are
0721: * consistent. There are to many conditions to list them
0722: * here, the best way is to read this function and all other
0723: * checkConsistent functions.
0724: */
0725: public void checkConsistent() {
0726: /* This checks are very time consuming, so don't do them
0727: * normally.
0728: */
0729: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_CHECK) == 0)
0730: return;
0731:
0732: try {
0733: if (block.outer != null || block.flowBlock != this ) {
0734: throw new AssertError("Inconsistency");
0735: }
0736: block.checkConsistent();
0737:
0738: for (Iterator i = predecessors.iterator(); i.hasNext();) {
0739: FlowBlock pred = (FlowBlock) i.next();
0740: if (pred == null)
0741: /* The special start marker */
0742: continue;
0743: if (!pred.successors.containsKey(this ))
0744: throw new AssertError("Inconsistency");
0745: }
0746:
0747: StructuredBlock last = lastModified;
0748: while (last.outer instanceof SequentialBlock
0749: || last.outer instanceof TryBlock
0750: || last.outer instanceof FinallyBlock)
0751: last = last.outer;
0752: if (last.outer != null)
0753: throw new AssertError("Inconsistency");
0754:
0755: Iterator iter = successors.entrySet().iterator();
0756: while (iter.hasNext()) {
0757: Map.Entry entry = (Map.Entry) iter.next();
0758: FlowBlock dest = (FlowBlock) entry.getKey();
0759: if (dest.predecessors.contains(this ) == (dest == END_OF_METHOD))
0760: throw new AssertError("Inconsistency");
0761:
0762: Jump jumps = ((SuccessorInfo) entry.getValue()).jumps;
0763: if (jumps == null)
0764: throw new AssertError("Inconsistency");
0765:
0766: for (; jumps != null; jumps = jumps.next) {
0767:
0768: if (jumps.destination != dest)
0769: throw new AssertError("Inconsistency");
0770:
0771: if (jumps.prev == null
0772: || jumps.prev.flowBlock != this
0773: || jumps.prev.jump != jumps)
0774: throw new AssertError("Inconsistency");
0775:
0776: prev_loop: for (StructuredBlock prev = jumps.prev; prev != block; prev = prev.outer) {
0777: if (prev.outer == null)
0778: throw new RuntimeException("Inconsistency");
0779: StructuredBlock[] blocks = prev.outer
0780: .getSubBlocks();
0781: int i;
0782: for (i = 0; i < blocks.length; i++)
0783: if (blocks[i] == prev)
0784: continue prev_loop;
0785:
0786: throw new AssertError("Inconsistency");
0787: }
0788: }
0789: }
0790: } catch (AssertError err) {
0791: GlobalOptions.err.println("Inconsistency in: " + this );
0792: throw err;
0793: }
0794: }
0795:
0796: public void appendBlock(StructuredBlock block, int length) {
0797: SlotSet succIn = new SlotSet();
0798: SlotSet succKill = new SlotSet();
0799: VariableSet succGen = new VariableSet();
0800: block.fillInGenSet(succIn, succKill);
0801: succGen.addAll(succKill);
0802:
0803: if (this .block == null) {
0804: this .block = block;
0805: lastModified = block;
0806: block.setFlowBlock(this );
0807: block.fillSuccessors();
0808: this .length = length;
0809:
0810: in = succIn;
0811: gen = succGen;
0812: for (Iterator i = successors.values().iterator(); i
0813: .hasNext();) {
0814: SuccessorInfo info = (SuccessorInfo) i.next();
0815: info.gen = new VariableSet();
0816: info.kill = new SlotSet();
0817: info.gen.addAll(succGen);
0818: info.kill.addAll(succKill);
0819: }
0820: } else if (!(block instanceof EmptyBlock)) {
0821: checkConsistent();
0822: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0) {
0823: GlobalOptions.err.println("appending Block: " + block);
0824: }
0825:
0826: SuccessorInfo succInfo = (SuccessorInfo) successors
0827: .get(NEXT_BY_ADDR);
0828: succIn.merge(succInfo.gen);
0829: succIn.removeAll(succInfo.kill);
0830:
0831: succGen.mergeGenKill(succInfo.gen, succKill);
0832: succKill.mergeKill(succInfo.kill);
0833: this .in.addAll(succIn);
0834: this .gen.addAll(succKill);
0835:
0836: removeSuccessor(lastModified.jump);
0837: lastModified.removeJump();
0838: lastModified = lastModified.appendBlock(block);
0839: block.fillSuccessors();
0840: succInfo = (SuccessorInfo) successors.get(NEXT_BY_ADDR);
0841: succInfo.gen = succGen;
0842: succInfo.kill = succKill;
0843: this .length += length;
0844: checkConsistent();
0845: doTransformations();
0846: }
0847: checkConsistent();
0848: }
0849:
0850: /**
0851: * Append the given flowblock to the nextByAddr/prevByAddr chain.
0852: * nextByAddr should be null, when calling this.
0853: * @param flow The flowBlock to append
0854: */
0855: public void setNextByAddr(FlowBlock flow) {
0856: /* nextByAddr can be set, when reordering block in transform exc */
0857: // if (nextByAddr != null)
0858: // throw new IllegalStateException("nextByAddr already set");
0859: if (flow == END_OF_METHOD || flow == NEXT_BY_ADDR)
0860: throw new IllegalArgumentException(
0861: "nextByAddr mustn't be special");
0862: SuccessorInfo info = (SuccessorInfo) successors
0863: .remove(NEXT_BY_ADDR);
0864: SuccessorInfo flowInfo = (SuccessorInfo) successors.get(flow);
0865: if (info != null) {
0866: NEXT_BY_ADDR.predecessors.remove(this );
0867: Jump jumps = info.jumps;
0868: jumps.destination = flow;
0869: while (jumps.next != null) {
0870: jumps = jumps.next;
0871: jumps.destination = flow;
0872: }
0873: successors.put(flow, info);
0874: if (flowInfo != null) {
0875: info.gen.addAll(flowInfo.gen);
0876: info.kill.retainAll(flowInfo.kill);
0877: jumps.next = flowInfo.jumps;
0878: } else
0879: flow.predecessors.add(this );
0880: }
0881: checkConsistent();
0882:
0883: nextByAddr = flow;
0884: flow.prevByAddr = this ;
0885: }
0886:
0887: /**
0888: * Do a T2 transformation with succ if possible. It is possible,
0889: * iff succ has exactly this block as predecessor.
0890: * @param succ the successor block, must be a valid successor of this
0891: * block, i.e. not null
0892: */
0893: public boolean doT2(FlowBlock succ) {
0894: /* check if this successor has only this block as predecessor.
0895: * if the predecessor is not unique, return false. */
0896: if (succ.predecessors.size() != 1
0897: || succ.predecessors.get(0) != this )
0898: return false;
0899:
0900: checkConsistent();
0901: succ.checkConsistent();
0902:
0903: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
0904: GlobalOptions.err.println("T2([" + addr + ","
0905: + getNextAddr() + "],[" + succ.addr + ","
0906: + succ.getNextAddr() + "])");
0907:
0908: SuccessorInfo succInfo = (SuccessorInfo) successors
0909: .remove(succ);
0910:
0911: /* Update the in/out-Vectors now */
0912: updateInOut(succ, succInfo);
0913: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
0914: GlobalOptions.err.println("before Resolve: " + this );
0915:
0916: /* Try to eliminate as many jumps as possible.
0917: */
0918: Jump jumps = resolveSomeJumps(succInfo.jumps, succ);
0919: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
0920: GlobalOptions.err.println("before Remaining: " + this );
0921: resolveRemaining(jumps);
0922: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
0923: GlobalOptions.err.println("after Resolve: " + this );
0924:
0925: /* Now unify the blocks.
0926: */
0927: lastModified = lastModified.appendBlock(succ.block);
0928: mergeSuccessors(succ);
0929:
0930: /* This will also set last modified to the new correct value. */
0931: doTransformations();
0932:
0933: /* Set addr and length to correct value and update nextByAddr */
0934: mergeAddr(succ);
0935:
0936: /* T2 transformation succeeded */
0937: checkConsistent();
0938: return true;
0939: }
0940:
0941: /**
0942: * Do a T2 transformation with the end_of_method block.
0943: */
0944: public void mergeEndBlock() {
0945: checkConsistent();
0946:
0947: SuccessorInfo endInfo = (SuccessorInfo) successors
0948: .remove(END_OF_METHOD);
0949: if (endInfo == null)
0950: return;
0951:
0952: Jump allJumps = endInfo.jumps;
0953: /* First remove all implicit jumps to the END_OF_METHOD block.
0954: */
0955: Jump jumps = null;
0956: for (; allJumps != null;) {
0957: Jump jump = allJumps;
0958: allJumps = allJumps.next;
0959:
0960: if (jump.prev instanceof ReturnBlock) {
0961: /* This jump is implicit */
0962: jump.prev.removeJump();
0963: continue;
0964: }
0965: jump.next = jumps;
0966: jumps = jump;
0967: }
0968:
0969: /* Try to eliminate as many jumps as possible.
0970: */
0971: jumps = resolveSomeJumps(jumps, END_OF_METHOD);
0972:
0973: next_jump: for (; jumps != null; jumps = jumps.next) {
0974:
0975: StructuredBlock prevBlock = jumps.prev;
0976:
0977: if (lastModified == prevBlock)
0978: /* handled later */
0979: continue;
0980:
0981: BreakableBlock breakToBlock = null;
0982: for (StructuredBlock surrounder = prevBlock.outer; surrounder != null; surrounder = surrounder.outer) {
0983: if (surrounder instanceof BreakableBlock) {
0984: if (surrounder.getNextFlowBlock() == END_OF_METHOD)
0985: breakToBlock = (BreakableBlock) surrounder;
0986:
0987: /* We don't want labeled breaks, because we can
0988: * simply return. */
0989: break;
0990: }
0991: }
0992: prevBlock.removeJump();
0993:
0994: if (breakToBlock == null)
0995: /* The successor is the dummy return instruction, so
0996: * replace the jump with a return.
0997: */
0998: prevBlock.appendBlock(new ReturnBlock());
0999: else
1000: prevBlock.appendBlock(new BreakBlock(breakToBlock,
1001: false));
1002: }
1003:
1004: /* Now remove the jump of the lastModified if it points to
1005: * END_OF_METHOD.
1006: */
1007: if (lastModified.jump.destination == END_OF_METHOD)
1008: lastModified.removeJump();
1009:
1010: doTransformations();
1011: /* transformation succeeded */
1012: checkConsistent();
1013: }
1014:
1015: public boolean doT1(int start, int end) {
1016: /* If there are no jumps to the beginning of this flow block
1017: * or if this block has other predecessors with a not yet
1018: * considered address, return false. The second condition
1019: * make sure that not for each continue a while is created.
1020: */
1021: if (!predecessors.contains(this ))
1022: return false;
1023: for (Iterator i = predecessors.iterator(); i.hasNext();) {
1024: FlowBlock predFlow = (FlowBlock) i.next();
1025: if (predFlow != null && predFlow != this
1026: && predFlow.addr >= start && predFlow.addr < end) {
1027: return false;
1028: }
1029: }
1030:
1031: checkConsistent();
1032:
1033: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1034: GlobalOptions.err.println("T1([" + addr + ","
1035: + getNextAddr() + "])");
1036: SuccessorInfo succInfo = (SuccessorInfo) successors
1037: .remove(this );
1038:
1039: /* Update the in/out-Vectors now */
1040: updateInOut(this , succInfo);
1041: Jump jumps = succInfo.jumps;
1042:
1043: StructuredBlock bodyBlock = block;
1044:
1045: /* If there is only one jump to the beginning and it is
1046: * the last jump (lastModified) and (there is a
1047: * do/while(0) block surrounding everything but the last
1048: * instruction, or the last instruction is a
1049: * increase/decrease statement), replace the do/while(0)
1050: * with a for(;;last_instr) resp. create a new one and
1051: * replace breaks to do/while with continue to for. */
1052:
1053: boolean createdForBlock = false;
1054:
1055: if (jumps.next == null
1056: && jumps.prev == lastModified
1057: && lastModified instanceof InstructionBlock
1058: && ((InstructionBlock) lastModified).getInstruction()
1059: .isVoid()) {
1060:
1061: if (lastModified.outer instanceof SequentialBlock
1062: && lastModified.outer.getSubBlocks()[0] instanceof LoopBlock) {
1063:
1064: LoopBlock lb = (LoopBlock) lastModified.outer
1065: .getSubBlocks()[0];
1066: if (lb.cond == lb.FALSE && lb.type == lb.DOWHILE) {
1067:
1068: /* The jump is directly following a
1069: * do-while(false) block
1070: *
1071: * Remove do/while, create a for(;;last_instr)
1072: * and replace break to that block with
1073: * continue to for.
1074: */
1075:
1076: lastModified.removeJump();
1077: LoopBlock forBlock = new LoopBlock(LoopBlock.FOR,
1078: LoopBlock.TRUE);
1079: forBlock.replace(bodyBlock);
1080: forBlock.setBody(bodyBlock);
1081: forBlock.incrInstr = ((InstructionBlock) lastModified)
1082: .getInstruction();
1083: forBlock.replaceBreakContinue(lb);
1084:
1085: lb.bodyBlock.replace(lastModified.outer);
1086: createdForBlock = true;
1087: }
1088:
1089: }
1090:
1091: if (!createdForBlock
1092: && (((InstructionBlock) lastModified)
1093: .getInstruction() instanceof CombineableOperator)) {
1094:
1095: /* The only jump is the jump of the last
1096: * instruction lastModified, there is a big
1097: * chance, that this is a for block, but we
1098: * can't be sure until we have seen the condition.
1099: * We will transform it to a for block, and take
1100: * that back, when we get a non matching condition.
1101: */
1102:
1103: lastModified.removeJump();
1104: LoopBlock forBlock = new LoopBlock(LoopBlock.POSSFOR,
1105: LoopBlock.TRUE);
1106: forBlock.replace(bodyBlock);
1107: forBlock.setBody(bodyBlock);
1108: forBlock.incrBlock = (InstructionBlock) lastModified;
1109:
1110: createdForBlock = true;
1111: }
1112: }
1113:
1114: if (!createdForBlock) {
1115: /* Creating a for block didn't succeed; create a
1116: * while block instead. */
1117:
1118: /* Try to eliminate as many jumps as possible.
1119: */
1120: jumps = resolveSomeJumps(jumps, this );
1121:
1122: LoopBlock whileBlock = new LoopBlock(LoopBlock.WHILE,
1123: LoopBlock.TRUE);
1124:
1125: /* The block may have been changed above. */
1126: bodyBlock = block;
1127: whileBlock.replace(bodyBlock);
1128: whileBlock.setBody(bodyBlock);
1129:
1130: /* if there are further jumps to this, replace every jump with a
1131: * continue to while block and return true.
1132: */
1133: for (; jumps != null; jumps = jumps.next) {
1134:
1135: if (jumps.prev == lastModified)
1136: /* handled later */
1137: continue;
1138:
1139: StructuredBlock prevBlock = jumps.prev;
1140:
1141: int breaklevel = 0, continuelevel = 0;
1142: BreakableBlock breakToBlock = null;
1143: for (StructuredBlock surrounder = prevBlock.outer; surrounder != whileBlock; surrounder = surrounder.outer) {
1144: if (surrounder instanceof BreakableBlock) {
1145: if (surrounder instanceof LoopBlock)
1146: continuelevel++;
1147: breaklevel++;
1148: if (surrounder.getNextFlowBlock() == this ) {
1149: breakToBlock = (BreakableBlock) surrounder;
1150: break;
1151: }
1152: }
1153: }
1154: prevBlock.removeJump();
1155: if (breakToBlock == null)
1156: prevBlock.appendBlock(new ContinueBlock(whileBlock,
1157: continuelevel > 0));
1158: else
1159: prevBlock.appendBlock(new BreakBlock(breakToBlock,
1160: breaklevel > 1));
1161: }
1162:
1163: /* Now remove the jump of lastModified if it points to this.
1164: */
1165: if (lastModified.jump.destination == this )
1166: lastModified.removeJump();
1167: }
1168:
1169: /* remove ourself from the predecessor list.
1170: */
1171: predecessors.remove(this );
1172: lastModified = block;
1173: doTransformations();
1174: // mergeCondition();
1175:
1176: /* T1 analysis succeeded */
1177: checkConsistent();
1178:
1179: return true;
1180: }
1181:
1182: public void doTransformations() {
1183: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1184: GlobalOptions.err.println("before Transformation: " + this );
1185:
1186: while (lastModified instanceof SequentialBlock) {
1187: if (lastModified.getSubBlocks()[0].doTransformations())
1188: continue;
1189: lastModified = lastModified.getSubBlocks()[1];
1190: }
1191: while (lastModified.doTransformations()) { /* empty */
1192: }
1193:
1194: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1195: GlobalOptions.err.println("after Transformation: " + this );
1196: }
1197:
1198: /**
1199: * Search for an apropriate successor.
1200: * @param prevSucc The successor, that was previously tried.
1201: * @param start The minimum address.
1202: * @param end The maximum address + 1.
1203: * @return the successor with smallest address greater than prevSucc
1204: * or null if there isn't any further successor at all.
1205: */
1206: FlowBlock getSuccessor(int start, int end) {
1207: /* search successor with smallest addr. */
1208: Iterator keys = successors.keySet().iterator();
1209: FlowBlock succ = null;
1210: while (keys.hasNext()) {
1211: FlowBlock fb = (FlowBlock) keys.next();
1212: if (fb.addr < start || fb.addr >= end || fb == this )
1213: continue;
1214: if (succ == null || fb.addr < succ.addr) {
1215: succ = fb;
1216: }
1217: }
1218: return succ;
1219: }
1220:
1221: /**
1222: * The main analyzation. This calls doT1 and doT2 on apropriate
1223: * regions until the whole function is transformed to a single
1224: * block.
1225: */
1226: public void analyze() {
1227: analyze(0, Integer.MAX_VALUE);
1228: mergeEndBlock();
1229: }
1230:
1231: /**
1232: * The main analyzation. This calls doT1 and doT2 on apropriate
1233: * regions. Only blocks whose address lies in the given address
1234: * range are considered.
1235: * @param start the start of the address range.
1236: * @param end the end of the address range.
1237: */
1238: public boolean analyze(int start, int end) {
1239: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1240: GlobalOptions.err.println("analyze(" + start + ", " + end
1241: + ")");
1242:
1243: checkConsistent();
1244: boolean changed = false;
1245:
1246: while (true) {
1247:
1248: if (lastModified instanceof SwitchBlock) {
1249: /* analyze the switch first.
1250: */
1251: analyzeSwitch(start, end);
1252: }
1253:
1254: if (doT1(start, end)) {
1255:
1256: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1257: GlobalOptions.err.println("after T1: " + this );
1258:
1259: /* T1 transformation succeeded. This may
1260: * make another T2 analysis in the previous
1261: * block possible.
1262: */
1263: if (addr != 0)
1264: return true;
1265: }
1266:
1267: FlowBlock succ = getSuccessor(start, end);
1268: while (true) {
1269: if (succ == null) {
1270: /* the Block has no successor where T2 is applicable.
1271: * Finish this analyzation.
1272: */
1273: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1274: GlobalOptions.err
1275: .println("No more successors applicable: "
1276: + start
1277: + " - "
1278: + end
1279: + "; "
1280: + addr + " - " + getNextAddr());
1281: return changed;
1282: } else {
1283: if ((nextByAddr == succ || succ.nextByAddr == this )
1284: /* Only do T2 transformation if the blocks are
1285: * adjacent.
1286: */
1287: && doT2(succ)) {
1288: /* T2 transformation succeeded. */
1289: changed = true;
1290:
1291: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1292: GlobalOptions.err.println("after T2: "
1293: + this );
1294: break;
1295: }
1296:
1297: /* Check if all predecessors of succ
1298: * lie in range [start,end). Otherwise
1299: * we have no chance to combine succ
1300: */
1301: for (Iterator i = succ.predecessors.iterator(); i
1302: .hasNext();) {
1303: int predAddr = ((FlowBlock) i.next()).addr;
1304: if (predAddr < start || predAddr >= end) {
1305: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1306: GlobalOptions.err
1307: .println("breaking analyze("
1308: + start + ", " + end
1309: + "); " + addr + " - "
1310: + getNextAddr());
1311: return changed;
1312: }
1313: }
1314: /* analyze succ, the new region is the
1315: * continuous region of
1316: * [start,end) \cap \compl [addr, getNextAddr())
1317: * where succ.addr lies in.
1318: */
1319: int newStart = (succ.addr > addr) ? getNextAddr()
1320: : start;
1321: int newEnd = (succ.addr > addr) ? end : addr;
1322: if (succ.analyze(newStart, newEnd))
1323: break;
1324: }
1325:
1326: /* Try the next successor.
1327: */
1328: succ = getSuccessor(succ.addr + 1, end);
1329: }
1330: }
1331: }
1332:
1333: /**
1334: * The switch analyzation. This calls doSwitchT2 and doT1 on apropriate
1335: * regions. Only blocks whose address lies in the given address
1336: * range are considered and it is taken care of, that the switch
1337: * is never leaved. <p>
1338: * The current flow block must contain the switch block as lastModified.
1339: * @param start the start of the address range.
1340: * @param end the end of the address range.
1341: */
1342: public boolean analyzeSwitch(int start, int end) {
1343: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1344: GlobalOptions.err.println("analyzeSwitch(" + start + ", "
1345: + end + ")");
1346:
1347: SwitchBlock switchBlock = (SwitchBlock) lastModified;
1348: boolean changed = false;
1349:
1350: int last = -1;
1351: FlowBlock lastFlow = null;
1352: for (int i = 0; i < switchBlock.caseBlocks.length; i++) {
1353: if (switchBlock.caseBlocks[i].subBlock instanceof EmptyBlock
1354: && switchBlock.caseBlocks[i].subBlock.jump != null) {
1355: FlowBlock nextFlow = switchBlock.caseBlocks[i].subBlock.jump.destination;
1356: if (nextFlow.addr >= end)
1357: break;
1358: else if (nextFlow.addr >= start) {
1359:
1360: /* First analyze the nextFlow block. It may
1361: * return early after a T1 trafo so call it
1362: * until nothing more is possible.
1363: */
1364: while (nextFlow.analyze(getNextAddr(), end))
1365: changed = true;
1366:
1367: if (nextFlow.addr != getNextAddr())
1368: break;
1369:
1370: /* Check if nextFlow has only the previous case
1371: * and this case as predecessor. Otherwise
1372: * break the analysis.
1373: */
1374: if (nextFlow.predecessors.size() > 2
1375: || (nextFlow.predecessors.size() > 1 && (lastFlow == null || !nextFlow.predecessors
1376: .contains(lastFlow)))
1377: || (((SuccessorInfo) successors
1378: .get(nextFlow)).jumps.next != null))
1379: break;
1380:
1381: checkConsistent();
1382:
1383: /* note that this info only contains
1384: * the single caseBlock jump */
1385: SuccessorInfo info = (SuccessorInfo) successors
1386: .remove(nextFlow);
1387:
1388: if (nextFlow.predecessors.size() == 2) {
1389: SuccessorInfo lastInfo = (SuccessorInfo) lastFlow.successors
1390: .remove(nextFlow);
1391:
1392: /* Do the in/out analysis with all jumps
1393: * Note that this won't update lastFlow.in, but
1394: * this will not be used anymore.
1395: */
1396: info.kill.retainAll(lastInfo.kill);
1397: info.gen.addAll(lastInfo.gen);
1398:
1399: Jump lastJumps = lastFlow.resolveSomeJumps(
1400: lastInfo.jumps, nextFlow);
1401: lastFlow.resolveRemaining(lastJumps);
1402: switchBlock.caseBlocks[last + 1].isFallThrough = true;
1403: }
1404: updateInOut(nextFlow, info);
1405:
1406: if (lastFlow != null) {
1407: lastFlow.block
1408: .replace(switchBlock.caseBlocks[last].subBlock);
1409: mergeSuccessors(lastFlow);
1410: }
1411:
1412: /* We merge the blocks into the caseBlock later, but
1413: * that doesn't affect consistency.
1414: */
1415:
1416: switchBlock.caseBlocks[i].subBlock.removeJump();
1417: mergeAddr(nextFlow);
1418:
1419: lastFlow = nextFlow;
1420: last = i;
1421:
1422: checkConsistent();
1423: changed = true;
1424: }
1425: }
1426: }
1427: if (lastFlow != null) {
1428: lastFlow.block
1429: .replace(switchBlock.caseBlocks[last].subBlock);
1430: mergeSuccessors(lastFlow);
1431: }
1432:
1433: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1434: GlobalOptions.err.println("after analyzeSwitch: " + this );
1435: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1436: GlobalOptions.err
1437: .println("analyzeSwitch done: " + start + " - "
1438: + end + "; " + addr + " - " + getNextAddr());
1439: checkConsistent();
1440: return changed;
1441: }
1442:
1443: /**
1444: * Mark the flow block as first flow block in a method.
1445: */
1446: public void makeStartBlock() {
1447: predecessors.add(null);
1448: }
1449:
1450: public void removeSuccessor(Jump jump) {
1451: SuccessorInfo destInfo = (SuccessorInfo) successors
1452: .get(jump.destination);
1453: Jump prev = null;
1454: Jump destJumps = destInfo.jumps;
1455: while (destJumps != jump && destJumps != null) {
1456: prev = destJumps;
1457: destJumps = destJumps.next;
1458: }
1459: if (destJumps == null)
1460: throw new IllegalArgumentException(addr
1461: + ": removing non existent jump: " + jump);
1462:
1463: if (prev != null)
1464: prev.next = destJumps.next;
1465: else {
1466: if (destJumps.next == null) {
1467: successors.remove(jump.destination);
1468: jump.destination.predecessors.remove(this );
1469: } else
1470: destInfo.jumps = destJumps.next;
1471: }
1472: }
1473:
1474: public Jump getJumps(FlowBlock dest) {
1475: return ((SuccessorInfo) successors.get(dest)).jumps;
1476: }
1477:
1478: public Jump removeJumps(FlowBlock dest) {
1479: if (dest != END_OF_METHOD)
1480: dest.predecessors.remove(this );
1481: return ((SuccessorInfo) successors.remove(dest)).jumps;
1482: }
1483:
1484: public Set getSuccessors() {
1485: return successors.keySet();
1486: }
1487:
1488: public void addSuccessor(Jump jump) {
1489: SuccessorInfo info = (SuccessorInfo) successors
1490: .get(jump.destination);
1491: if (info == null) {
1492: info = new SuccessorInfo();
1493: info.jumps = jump;
1494: if (jump.destination != END_OF_METHOD)
1495: jump.destination.predecessors.add(this );
1496: successors.put(jump.destination, info);
1497: } else {
1498: jump.next = info.jumps;
1499: info.jumps = jump;
1500: }
1501: }
1502:
1503: /**
1504: * This is called after the analysis is completely done. It
1505: * will remove all PUSH/stack_i expressions, (if the bytecode
1506: * is correct).
1507: * @return true, if the stack mapping succeeded.
1508: */
1509: public final boolean mapStackToLocal() {
1510: mapStackToLocal(VariableStack.EMPTY);
1511: return true;
1512: }
1513:
1514: /**
1515: * This is called after the analysis is completely done. It
1516: * will remove all PUSH/stack_i expressions, (if the bytecode
1517: * is correct).
1518: * @param initialStack the stackmap at begin of the flow block
1519: * @return false if the bytecode isn't correct and stack mapping
1520: * didn't worked.
1521: */
1522: public void mapStackToLocal(VariableStack initialStack) {
1523: if (initialStack == null)
1524: throw new jode.AssertError("initial stack is null");
1525: stackMap = initialStack;
1526: block.mapStackToLocal(initialStack);
1527: Iterator iter = successors.values().iterator();
1528: while (iter.hasNext()) {
1529: SuccessorInfo succInfo = (SuccessorInfo) iter.next();
1530: Jump jumps = succInfo.jumps;
1531: VariableStack stack;
1532: FlowBlock succ = jumps.destination;
1533: if (succ == END_OF_METHOD)
1534: continue;
1535: stack = succ.stackMap;
1536: for (/**/; jumps != null; jumps = jumps.next) {
1537: if (jumps.stackMap == null)
1538: GlobalOptions.err.println("Dead jump? "
1539: + jumps.prev + " in " + this );
1540:
1541: stack = VariableStack.merge(stack, jumps.stackMap);
1542: }
1543: if (succ.stackMap == null)
1544: succ.mapStackToLocal(stack);
1545: }
1546: }
1547:
1548: public void removePush() {
1549: if (stackMap == null)
1550: /* already done or mapping didn't succeed */
1551: return;
1552: stackMap = null;
1553: block.removePush();
1554: Iterator iter = successors.keySet().iterator();
1555: while (iter.hasNext()) {
1556: FlowBlock succ = (FlowBlock) iter.next();
1557: succ.removePush();
1558: }
1559: }
1560:
1561: public void removeOnetimeLocals() {
1562: block.removeOnetimeLocals();
1563: if (nextByAddr != null)
1564: nextByAddr.removeOnetimeLocals();
1565: }
1566:
1567: private void promoteInSets() {
1568: for (Iterator i = predecessors.iterator(); i.hasNext();) {
1569: FlowBlock pred = (FlowBlock) i.next();
1570: SuccessorInfo succInfo = (SuccessorInfo) pred.successors
1571: .get(this );
1572:
1573: /* First get the gen/kill sets of all jumps of predecessor
1574: * to this block and calculate the intersection.
1575: */
1576: VariableSet gens = succInfo.gen;
1577: SlotSet kills = succInfo.kill;
1578:
1579: /* Merge in locals of this block with those condionally
1580: * written by previous blocks */
1581: in.merge(gens);
1582:
1583: /* The ins of the successor that are not killed
1584: * (i.e. unconditionally overwritten) by this block are new
1585: * ins for this block.
1586: */
1587: SlotSet newIn = (SlotSet) in.clone();
1588: newIn.removeAll(kills);
1589:
1590: if (pred.in.addAll(newIn))
1591: pred.promoteInSets();
1592: }
1593:
1594: if (nextByAddr != null)
1595: nextByAddr.promoteInSets();
1596: }
1597:
1598: /**
1599: * Merge the parameter locals with the in set of this flow block.
1600: * This will also make a successive analysis to merge the gen/kill
1601: * set of the jumps with the next flow block. */
1602: public void mergeParams(LocalInfo[] param) {
1603: // Now we promote the final (maybe slow) in set analysis
1604: promoteInSets();
1605:
1606: VariableSet paramSet = new VariableSet(param);
1607: in.merge(paramSet);
1608: }
1609:
1610: /**
1611: * Make declarations. It will determine, where in each block the
1612: * variables and method scoped classes must be declared.
1613: */
1614: public void makeDeclaration(Set done) {
1615: block.propagateUsage();
1616: block.makeDeclaration(done);
1617: if (nextByAddr != null)
1618: nextByAddr.makeDeclaration(done);
1619: }
1620:
1621: /**
1622: * Simplify this and all following flowblocks.
1623: */
1624: public void simplify() {
1625: block.simplify();
1626: if (nextByAddr != null)
1627: nextByAddr.simplify();
1628: }
1629:
1630: /**
1631: * Print the source code for this structured block. This handles
1632: * everything that is unique for all structured blocks and calls
1633: * dumpInstruction afterwards.
1634: * @param writer The tabbed print writer, where we print to.
1635: */
1636: public void dumpSource(TabbedPrintWriter writer)
1637: throws java.io.IOException {
1638: if (predecessors.size() != 0) {
1639: writer.untab();
1640: writer.println(getLabel() + ":");
1641: writer.tab();
1642: }
1643:
1644: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
1645: writer.println("in: " + in);
1646: }
1647:
1648: block.dumpSource(writer);
1649:
1650: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
1651:
1652: Iterator iter = successors.entrySet().iterator();
1653: while (iter.hasNext()) {
1654: Map.Entry entry = (Map.Entry) iter.next();
1655: FlowBlock dest = (FlowBlock) entry.getKey();
1656: SuccessorInfo info = (SuccessorInfo) entry.getValue();
1657: writer.println("successor: " + dest.getLabel()
1658: + " gen : " + info.gen + " kill: "
1659: + info.kill);
1660: }
1661: }
1662:
1663: if (nextByAddr != null)
1664: nextByAddr.dumpSource(writer);
1665: }
1666:
1667: /**
1668: * The serial number for labels.
1669: */
1670: static int serialno = 0;
1671:
1672: /**
1673: * The label of this instruction, or null if it needs no label.
1674: */
1675: String label = null;
1676:
1677: /**
1678: * Returns the address, where the code in this flow block starts.
1679: */
1680: public int getAddr() {
1681: return addr;
1682: }
1683:
1684: /**
1685: * Returns the label of this block and creates a new label, if
1686: * there wasn't a label previously.
1687: */
1688: public String getLabel() {
1689: if (label == null)
1690: label = "flow_" + addr + "_" + (serialno++) + "_";
1691: return label;
1692: }
1693:
1694: /**
1695: * Returns the structured block, that this flow block contains.
1696: */
1697: public StructuredBlock getBlock() {
1698: return block;
1699: }
1700:
1701: public String toString() {
1702: try {
1703: java.io.StringWriter strw = new java.io.StringWriter();
1704: TabbedPrintWriter writer = new TabbedPrintWriter(strw);
1705: writer.println(super .toString() + ": " + addr + "-"
1706: + (addr + length));
1707: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
1708: writer.println("in: " + in);
1709: }
1710: writer.tab();
1711: block.dumpSource(writer);
1712: writer.untab();
1713: if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
1714:
1715: Iterator iter = successors.entrySet().iterator();
1716: while (iter.hasNext()) {
1717: Map.Entry entry = (Map.Entry) iter.next();
1718: FlowBlock dest = (FlowBlock) entry.getKey();
1719: SuccessorInfo info = (SuccessorInfo) entry
1720: .getValue();
1721: writer.println("successor: " + dest.getLabel()
1722: + " gen : " + info.gen + " kill: "
1723: + info.kill);
1724: }
1725: }
1726: return strw.toString();
1727: } catch (RuntimeException ex) {
1728: return super .toString() + ": (RUNTIME EXCEPTION)";
1729: } catch (java.io.IOException ex) {
1730: return super.toString();
1731: }
1732: }
1733: }
|