Source Code Cross Referenced for FlowBlock.java in  » Development » jode » jode » flow » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Development » jode » jode.flow 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.