KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > jode > flow > FlowBlock


1 /* FlowBlock Copyright (C) 1998-2002 Jochen Hoenicke.
2  *
3  * This program is free software; you can redistribute it and/or modify
4  * it under the terms of the GNU Lesser General Public License as published by
5  * the Free Software Foundation; either version 2, or (at your option)
6  * any later version.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  * GNU General Public License for more details.
12  *
13  * You should have received a copy of the GNU Lesser General Public License
14  * along with this program; see the file COPYING.LESSER. If not, write to
15  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
16  *
17  * $Id: FlowBlock.java.in,v 4.5.2.4 2002/05/28 17:34:09 hoenicke Exp $
18  */

19
20 package jode.flow;
21 import jode.GlobalOptions;
22 import jode.AssertError;
23 import jode.decompiler.TabbedPrintWriter;
24 import jode.decompiler.MethodAnalyzer;
25 import jode.decompiler.LocalInfo;
26 import jode.expr.Expression;
27 import jode.expr.CombineableOperator;
28 import jode.util.SimpleMap;
29 import jode.util.SimpleSet;
30
31 import java.util.Map JavaDoc;
32 import java.util.Iterator JavaDoc;
33 import java.util.Set JavaDoc;
34 import java.util.ArrayList JavaDoc;
35 import java.util.List JavaDoc;
36
37 /**
38  * A flow block is the structure of which the flow graph consists. A
39  * flow block contains structured code together with some conditional
40  * or unconditional jumps to the head of other flow blocks.
41  *
42  * We do a T1/T2 analysis to combine all flow blocks to a single. If
43  * the graph isn't reducible that doesn't work, but java can only
44  * produce reducible flow graphs.
45  *
46  * We don't use the notion of basic flow graphs. A flow block may be
47  * anything from a single bytecode opcode, to the whole method.
48  */

49 public class FlowBlock {
50
51     public static FlowBlock END_OF_METHOD;
52     public static FlowBlock NEXT_BY_ADDR;
53
54     static {
55     END_OF_METHOD = new FlowBlock(null, Integer.MAX_VALUE);
56     END_OF_METHOD.appendBlock(new EmptyBlock(), 0);
57         END_OF_METHOD.label = "END_OF_METHOD";
58
59     NEXT_BY_ADDR = new FlowBlock(null, -1);
60         NEXT_BY_ADDR.appendBlock(new DescriptionBlock("FALL THROUGH"), 0);
61     NEXT_BY_ADDR.label = "NEXT_BY_ADDR";
62     }
63
64     /**
65      * The method analyzer. This is used to pretty printing the
66      * Types and to get information about all locals in this code.
67      */

68     MethodAnalyzer method;
69
70     /**
71      * The in locals. This are the locals, which are used in this
72      * flow block and whose values may be the result of a assignment
73      * outside of this flow block. That means, that there is a
74      * path from the start of the flow block to the instruction that
75      * uses that variable, on which it is never assigned
76      */

77     private SlotSet in = new SlotSet();
78     /**
79      * The gen locals. This are the locals, to which are written
80      * somewhere in this flow block. This is only used for try
81      * catch blocks.
82      */

83     VariableSet gen = new VariableSet();
84
85     /**
86      * The starting address of this flow block. This is mainly used
87      * to produce the source code in code order.
88      */

89     private int addr;
90
91     /**
92      * The length of the structured block, only needed at the beginning.
93      */

94     private int length;
95
96     /**
97      * The outermost structructed block in this flow block.
98      */

99     StructuredBlock block;
100
101     /**
102      * The last modified structured block. This is probably the
103      * last instruction in the outermost block, that is in the
104      * outermost chain of SequentialBlock.
105      */

106     StructuredBlock lastModified;
107
108     /**
109      * This contains a map of all successing flow blocks and there
110      * jumps. The key of this map are the flow blocks, while
111      * the elements is the first jump to that flow block. The other
112      * jumps are accessible via the jump.next field.
113      */

114     private Map successors = new SimpleMap();
115
116     /**
117      * This is a vector of flow blocks, which reference this block.
118      * Only if this vector contains exactly one element, it can be
119      * moved into the preceding flow block.
120      *
121      * If this vectors contains the null element, this is the first
122      * flow block in a method.
123      */

124     List JavaDoc predecessors = new ArrayList JavaDoc();
125
126     /**
127      * This is a pointer to the next flow block in byte code order.
128      * It is null for the last flow block.
129      */

130     FlowBlock nextByAddr;
131
132     /**
133      * This is a pointer to the previous flow block in byte code order.
134      * It is null for the first flow block.
135      */

136     FlowBlock prevByAddr;
137
138     /**
139      * The stack map. This tells how many objects are on stack at
140      * begin of the flow block, and to what locals they are maped.
141      * @see mapStackToLocal
142      */

143     VariableStack stackMap;
144
145     static class SuccessorInfo {
146     /**
147      * The kill locals. This are the slots, which must be
148      * overwritten in this block on every path to the successor.
149      * That means, that all paths from the start of the current
150      * flow block to the successor contain (unconditional)
151      * assignments to this slot.
152      */

153     SlotSet kill;
154     
155     /**
156      * The gen locals. This are the locals, which can be
157      * overwritten in this block on a path to the successor. That
158      * means, that there exists a path form the start of the
159      * current flow block to the successor that contains a
160      * assignments to this local, and that is not overwritten
161      * afterwards.
162      */

163     VariableSet gen;
164     
165     /**
166      * The linked list of jumps.
167      */

168     Jump jumps;
169     }
170
171
172     /**
173      * The default constructor. Creates a new empty flowblock.
174      */

175     public FlowBlock(MethodAnalyzer method, int addr) {
176     this.method = method;
177         this.addr = addr;
178     }
179
180     public final int getNextAddr() {
181         return addr+length;
182     }
183
184     public boolean hasNoJumps() {
185     return successors.size() == 0 && predecessors.size() == 0;
186     }
187
188     /**
189      * This method resolves some of the jumps to successor.
190      * @param jumps The list of jumps with that successor.
191      * @param succ The successing flow block.
192      * @return The remaining jumps, that couldn't be resolved.
193      */

194     public Jump resolveSomeJumps(Jump jumps, FlowBlock succ) {
195     /* We will put all jumps that we can not resolve into this
196      * linked list.
197      */

198         Jump remainingJumps = null;
199
200         if (lastModified.jump == null) {
201         /* This can happen if lastModified is a breakable block, and
202          * there is no break to it yet. We give lastModified this jump
203          * as successor since many other routines rely on this.
204          */

205             Jump lastJump = new Jump(succ);
206             lastModified.setJump(lastJump);
207             remainingJumps = lastJump;
208         }
209
210         for (Jump jump = jumps; jump != null; jump = jump.next) {
211             /* First swap all conditional blocks, that have two jumps,
212              * so that the jump to succ will be on the outside.
213              */

214             if (jump.prev.outer instanceof ConditionalBlock
215                 && jump.prev.outer.jump != null) {
216
217                 StructuredBlock prev = jump.prev;
218                 ConditionalBlock cb = (ConditionalBlock) prev.outer;
219                 Expression instr = cb.getInstruction();
220                 
221                 cb.setInstruction(instr.negate());
222                 cb.swapJump(prev);
223             }
224         }
225     next_jump:
226         while (jumps != null) {
227             Jump jump = jumps;
228             jumps = jumps.next;
229
230             /* if the jump is the jump of lastModified, skip it.
231              */

232             if (jump.prev == lastModified) {
233                 jump.next = remainingJumps;
234                 remainingJumps = jump;
235                 continue;
236             }
237
238             /* jump.prev.outer is not null, otherwise jump.prev would
239              * be lastModified.
240              */

241
242             if (jump.prev.outer instanceof ConditionalBlock) {
243                 StructuredBlock prev = jump.prev;
244                 ConditionalBlock cb = (ConditionalBlock) prev.outer;
245                 Expression instr = cb.getInstruction();
246
247         /* This is a jump inside an ConditionalBlock.
248          *
249          * cb is the conditional block,
250          * prev the empty block containing the jump
251          * instr is the condition */

252
253                 if (cb.jump != null) {
254                     /* This can only happen if cb also jumps to succ.
255                      * This is a weired "if (cond) empty"-block. We
256                      * transform it by hand.
257                      */

258                     prev.removeJump();
259                     IfThenElseBlock ifBlock =
260                         new IfThenElseBlock(cb.getInstruction().negate());
261                     ifBlock.moveDefinitions(cb, prev);
262                     ifBlock.replace(cb);
263             ifBlock.moveJump(cb.jump);
264                     ifBlock.setThenBlock(prev);
265             if (cb == lastModified)
266             lastModified = ifBlock;
267                     continue;
268                 }
269
270                 /* Now cb.jump is null, so cb.outer is not null,
271                  * since otherwise it would have no successor. */

272
273                 if (cb.outer instanceof LoopBlock
274                     || (cb.outer instanceof SequentialBlock
275                         && cb.outer.getSubBlocks()[0] == cb
276                         && cb.outer.outer instanceof LoopBlock)) {
277             
278             /* If this is the first instruction of a
279              * while/for(true) block, make this the loop condition
280              * (negated of course).
281              */

282
283                     LoopBlock loopBlock = (cb.outer instanceof LoopBlock) ?
284                         (LoopBlock) cb.outer : (LoopBlock) cb.outer.outer;
285
286                     if (loopBlock.getCondition() == LoopBlock.TRUE &&
287                         loopBlock.getType() != LoopBlock.DOWHILE &&
288                         (loopBlock.jumpMayBeChanged()
289                          || loopBlock.getNextFlowBlock() == succ)) {
290                         
291                         if (loopBlock.jump == null) {
292                             /* consider this jump again */
293                             loopBlock.moveJump(jump);
294                             jumps = jump;
295                         } else
296                             jump.prev.removeJump();
297
298                         loopBlock.setCondition(instr.negate());
299                         loopBlock.moveDefinitions(cb, null);
300                         cb.removeBlock();
301                         continue;
302                     }
303
304                 } else if (cb.outer instanceof SequentialBlock
305                            && cb.outer.getSubBlocks()[1] == cb) {
306
307                     /* And now for do/while loops, where the jump is
308                      * at the end of the loop.
309                      */

310                     
311                     /* First find the beginning of the loop */
312                     StructuredBlock sb = cb.outer.outer;
313                     while (sb instanceof SequentialBlock) {
314                         sb = sb.outer;
315                     }
316                     /* sb is now the first and cb is the last
317                      * instruction in the current block.
318                      */

319                     if (sb instanceof LoopBlock) {
320                         LoopBlock loopBlock = (LoopBlock) sb;
321                         if (loopBlock.getCondition() == LoopBlock.TRUE &&
322                             loopBlock.getType() == LoopBlock.WHILE &&
323                             (loopBlock.jumpMayBeChanged()
324                              || loopBlock.getNextFlowBlock() == succ)) {
325                             
326                             if (loopBlock.jump == null) {
327                                 /* consider this jump again */
328                                 loopBlock.moveJump(jump);
329                                 jumps = jump;
330                             } else
331                                 jump.prev.removeJump();
332
333                             loopBlock.setType(LoopBlock.DOWHILE);
334                             loopBlock.setCondition(instr.negate());
335                             loopBlock.moveDefinitions(cb, null);
336                             cb.removeBlock();
337                             continue;
338                         }
339                     }
340                 }
341
342         /* This is still a jump inside an ConditionalBlock.
343          *
344          * cb is the conditional block,
345          * prev the empty block containing the jump
346          * instr is the condition */

347
348         /* replace all conditional jumps to the successor, which
349          * are followed by a block which has the end of the block
350          * as normal successor, with "if (not condition) block":
351          *
352          * /IF cond GOTO succ if (!cond)
353          * \block ===> block
354          * -> normal Succesor succ -> normal Successor succ
355          */

356                 if (cb.outer instanceof SequentialBlock &&
357                     cb.outer.getSubBlocks()[0] == cb &&
358                     (cb.outer.getNextFlowBlock() == succ ||
359                      cb.outer.jumpMayBeChanged())) {
360
361                     SequentialBlock sequBlock = (SequentialBlock) cb.outer;
362                     
363                     IfThenElseBlock newIfBlock
364                         = new IfThenElseBlock(instr.negate());
365                     StructuredBlock thenBlock = sequBlock.getSubBlocks()[1];
366
367                     newIfBlock.moveDefinitions(sequBlock, thenBlock);
368                     newIfBlock.replace(sequBlock);
369                     newIfBlock.setThenBlock(thenBlock);
370
371                     if (thenBlock.contains(lastModified)) {
372                         if (lastModified.jump.destination == succ) {
373                             newIfBlock.moveJump(lastModified.jump);
374                             lastModified = newIfBlock;
375                             jump.prev.removeJump();
376                             continue;
377                         }
378                         lastModified = newIfBlock;
379                     }
380
381                     newIfBlock.moveJump(jump);
382                     /* consider this jump again */
383                     jumps = jump;
384                     continue;
385                 }
386             } else {
387         
388         /* remove this jump if it jumps to the
389          * getNextFlowBlock(). */

390         if (jump.destination
391             == jump.prev.outer.getNextFlowBlock(jump.prev)) {
392             jump.prev.removeJump();
393             continue;
394         }
395
396
397                 /* Now find the real outer block, that is ascend the chain
398                  * of SequentialBlocks.
399                  *
400                  * Note that only the last instr in a SequentialBlock chain
401                  * can have a jump.
402                  *
403                  * We rely on the fact, that instanceof returns false
404                  * for a null pointer.
405                  */

406                 StructuredBlock sb = jump.prev.outer;
407                 while (sb instanceof SequentialBlock)
408                     sb = sb.outer;
409                 
410
411                 /* if this is an unconditional jump at the end of a
412          * then block belonging to a if-then block without
413          * else part, and the if block has a jump then replace
414          * the if-then block with a if-then-else block with an
415          * else block that contains only the jump and move the
416          * unconditional jump to the if. (The jump in the else
417          * block will later probably be replaced with a break,
418          * continue or return statement.)
419          */

420                 if (sb instanceof IfThenElseBlock) {
421                     IfThenElseBlock ifBlock = (IfThenElseBlock) sb;
422                     if (ifBlock.elseBlock == null && ifBlock.jump != null) {
423             ifBlock.setElseBlock(new EmptyBlock());
424             ifBlock.elseBlock.moveJump(ifBlock.jump);
425             ifBlock.moveJump(jump);
426             /* consider this jump again */
427             jumps = jump;
428             continue;
429             }
430         }
431
432                 /* if this is a jump at the end of a then block belonging
433                  * to a if-then block without else part, and the if-then
434                  * block is followed by a single block, then replace the
435                  * if-then block with a if-then-else block and move the
436                  * unconditional jump to the if.
437                  */

438                 if (sb instanceof IfThenElseBlock
439             && sb.outer instanceof SequentialBlock
440             && sb.outer.getSubBlocks()[0] == sb) {
441             
442                     IfThenElseBlock ifBlock = (IfThenElseBlock) sb;
443                     SequentialBlock sequBlock = (SequentialBlock) sb.outer;
444             StructuredBlock elseBlock = sequBlock.subBlocks[1];
445                     
446                     if (ifBlock.elseBlock == null
447                         && (elseBlock.getNextFlowBlock() == succ
448                 || elseBlock.jump != null
449                             || elseBlock.jumpMayBeChanged())) {
450                         
451                         ifBlock.replace(sequBlock);
452                         ifBlock.setElseBlock(elseBlock);
453
454                         if (elseBlock.contains(lastModified)) {
455                             if (lastModified.jump.destination == succ) {
456                                 ifBlock.moveJump(lastModified.jump);
457                                 lastModified = ifBlock;
458                                 jump.prev.removeJump();
459                                 continue;
460                             }
461                             lastModified = ifBlock;
462                         }
463                             
464                         /* consider this jump again */
465                         ifBlock.moveJump(jump);
466                         jumps = jump;
467                         continue;
468                     }
469         }
470             }
471
472             /* if this is a jump in a breakable block, and that block
473              * has not yet a next block, then create a new jump to that
474              * successor.
475              *
476              * The break to the block will be generated later.
477              */

478
479             for (StructuredBlock surrounder = jump.prev.outer;
480                  surrounder != null; surrounder = surrounder.outer) {
481                 if (surrounder instanceof BreakableBlock) {
482                     if (surrounder.getNextFlowBlock() == succ)
483             /* We can break to that block; this is done later. */
484             break;
485
486             if (surrounder.jumpMayBeChanged()) {
487                         surrounder.setJump(new Jump(succ));
488             /* put surrounder in todo list */
489                         surrounder.jump.next = jumps;
490                         jumps = surrounder.jump;
491             /* The break is inserted later */
492             break;
493                     }
494             if (succ == END_OF_METHOD) {
495             /* If the jump can be replaced by a return
496              * we won't do labeled breaks, so we must
497              * stop here
498              */

499             break;
500             }
501                 }
502             }
503             jump.next = remainingJumps;
504             remainingJumps = jump;
505         }
506         return remainingJumps;
507     }
508
509     /**
510      * Resolve remaining jumps to the successor by generating break
511      * instructions. As last resort generate a do while(false) block.
512      * @param jumps The jump list that need to be resolved.
513      */

514     void resolveRemaining(Jump jumps) {
515         LoopBlock doWhileFalse = null;
516         StructuredBlock outerMost = lastModified;
517         boolean removeLast = false;
518     next_jump:
519         for (; jumps != null; jumps = jumps.next) {
520             StructuredBlock prevBlock = jumps.prev;
521         
522             if (prevBlock == lastModified) {
523                 /* handled below */
524                 removeLast = true;
525                 continue;
526             }
527             
528             int breaklevel = 0;
529             BreakableBlock breakToBlock = null;
530             for (StructuredBlock surrounder = prevBlock.outer;
531                  surrounder != null; surrounder = surrounder.outer) {
532                 if (surrounder instanceof BreakableBlock) {
533                     breaklevel++;
534                     if (surrounder.getNextFlowBlock() == jumps.destination) {
535                         breakToBlock = (BreakableBlock) surrounder;
536                         break;
537                     }
538                 }
539             }
540             
541             prevBlock.removeJump();
542             
543             if (breakToBlock == null) {
544                 /* Nothing else helped, so put a do/while(0)
545                  * block around outerMost and break to that
546                  * block.
547                  */

548                 if (doWhileFalse == null) {
549                     doWhileFalse = new LoopBlock(LoopBlock.DOWHILE,
550                                                  LoopBlock.FALSE);
551                 }
552                 /* Adapt outermost, so that it contains the break. */
553                 while (!outerMost.contains(prevBlock))
554                     outerMost = outerMost.outer;
555                 prevBlock.appendBlock
556                     (new BreakBlock(doWhileFalse, breaklevel > 0));
557             } else
558                 prevBlock.appendBlock
559                     (new BreakBlock(breakToBlock, breaklevel > 1));
560         }
561         
562         if (removeLast)
563             lastModified.removeJump();
564
565         if (doWhileFalse != null) {
566             doWhileFalse.replace(outerMost);
567             doWhileFalse.setBody(outerMost);
568             lastModified = doWhileFalse;
569         }
570     }
571
572     /**
573      * Move the successors of the given flow block to this flow block.
574      * @param succ the other flow block
575      */

576     void mergeSuccessors(FlowBlock succ) {
577         /* Merge the successors from the successing flow block
578          */

579         Iterator JavaDoc iter = succ.successors.entrySet().iterator();
580         while (iter.hasNext()) {
581         Map.Entry entry = (Map.Entry) iter.next();
582             FlowBlock dest = (FlowBlock) entry.getKey();
583             SuccessorInfo hisInfo = (SuccessorInfo) entry.getValue();
584             SuccessorInfo myInfo = (SuccessorInfo) successors.get(dest);
585
586         if (dest != END_OF_METHOD)
587         dest.predecessors.remove(succ);
588             if (myInfo == null) {
589         if (dest != END_OF_METHOD)
590             dest.predecessors.add(this);
591                 successors.put(dest, hisInfo);
592             } else {
593         myInfo.gen.addAll(hisInfo.gen);
594         myInfo.kill.retainAll(hisInfo.kill);
595         Jump myJumps = myInfo.jumps;
596         while (myJumps.next != null)
597                     myJumps = myJumps.next;
598                 myJumps.next = hisInfo.jumps;
599             }
600         }
601     }
602
603     /**
604      * Fixes the addr chained list, after merging this block with succ.
605      */

606     public void mergeAddr(FlowBlock succ) {
607     if (succ.nextByAddr == this || succ.prevByAddr == null) {
608         /* Merge succ with its nextByAddr.
609          * Note: succ.nextByAddr != null, since this is on the
610          * nextByAddr chain. */

611         succ.nextByAddr.addr = succ.addr;
612         succ.nextByAddr.length += succ.length;
613
614         succ.nextByAddr.prevByAddr = succ.prevByAddr;
615         if (succ.prevByAddr != null)
616         succ.prevByAddr.nextByAddr = succ.nextByAddr;
617     } else {
618         /* Merge succ with its prevByAddr */
619         succ.prevByAddr.length += succ.length;
620
621         succ.prevByAddr.nextByAddr = succ.nextByAddr;
622         if (succ.nextByAddr != null)
623         succ.nextByAddr.prevByAddr = succ.prevByAddr;
624     }
625     }
626
627     /**
628      * Updates the in/out-Vectors of the structured block of the
629      * successing flow block simultanous to a T2 transformation.
630      * @param successor The flow block which is unified with this flow
631      * block.
632      * @param jumps The list of jumps to successor in this block.
633      * @return The variables that must be defined in this block.
634      */

635     void updateInOut(FlowBlock successor, SuccessorInfo succInfo) {
636         /* First get the gen/kill sets of all jumps to successor and
637          * calculate the intersection.
638      */

639         SlotSet kills = succInfo.kill;
640         VariableSet gens = succInfo.gen;
641
642         /* Merge the locals used in successing block with those written
643          * by this blocks.
644          */

645         successor.in.merge(gens);
646         
647         /* The ins of the successor that are not killed
648      * (i.e. unconditionally overwritten) by this block are new
649      * ins for this block.
650      */

651     SlotSet newIn = (SlotSet) successor.in.clone();
652     newIn.removeAll(kills);
653
654         /* The gen/kill sets must be updated for every jump
655          * in the other block */

656         Iterator JavaDoc i = successor.successors.values().iterator();
657         while (i.hasNext()) {
658         SuccessorInfo succSuccInfo = (SuccessorInfo) i.next();
659         succSuccInfo.gen.mergeGenKill(gens, succSuccInfo.kill);
660         if (successor != this)
661         succSuccInfo.kill.mergeKill(kills);
662         }
663         this.in.addAll(newIn);
664         this.gen.addAll(successor.gen);
665
666         if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
667             GlobalOptions.err.println("UpdateInOut: gens : "+gens);
668             GlobalOptions.err.println(" kills: "+kills);
669             GlobalOptions.err.println(" s.in : "+successor.in);
670             GlobalOptions.err.println(" in : "+in);
671         }
672     }
673
674     /**
675      * Updates the in/out-Vectors of the structured block of the
676      * successing flow block for a try catch block. The main difference
677      * to updateInOut in FlowBlock is, that this function works, as if
678      * every instruction would have a jump. This is because every
679      * instruction can throw an exception and thus enter the catch block.<br>
680      *
681      * For example this code prints <code>0</code>:
682      * <pre>
683      * int a=3;
684      * try {
685      * a = 5 / (a=0);
686      * } catch (DivideByZeroException ex) {
687      * System.out.println(a);
688      * }
689      * </pre>
690      *
691      * @param successor The flow block which is unified with this flow
692      * block.
693      * @return The variables that must be defined in this block.
694      */

695     public void updateInOutCatch (FlowBlock catchFlow) {
696         VariableSet gens = ((TryBlock)block).gen;
697
698         /* Merge the locals used in the catch block with those written
699          * by the try block
700          */

701         catchFlow.in.merge(gens);
702         
703         /* The gen/kill sets must be updated for every jump
704          * in the other block */

705         Iterator JavaDoc i = catchFlow.successors.values().iterator();
706         while (i.hasNext()) {
707         SuccessorInfo succSuccInfo = (SuccessorInfo) i.next();
708         succSuccInfo.gen.mergeGenKill(gens, succSuccInfo.kill);
709         }
710         in.addAll(catchFlow.in);
711         gen.addAll(catchFlow.gen);
712     
713         if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
714             GlobalOptions.err.println("UpdateInOutCatch: gens : "+gens);
715             GlobalOptions.err.println(" s.in : "+catchFlow.in);
716             GlobalOptions.err.println(" in : "+in);
717         }
718     }
719
720     
721     /**
722      * Checks if the FlowBlock and its StructuredBlocks are
723      * consistent. There are to many conditions to list them
724      * here, the best way is to read this function and all other
725      * checkConsistent functions.
726      */

727     public void checkConsistent() {
728         /* This checks are very time consuming, so don't do them
729          * normally.
730          */

731         if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_CHECK) == 0)
732             return;
733
734     try {
735         if (block.outer != null || block.flowBlock != this) {
736             throw new AssertError("Inconsistency");
737         }
738         block.checkConsistent();
739
740         for (Iterator JavaDoc i = predecessors.iterator(); i.hasNext(); ) {
741             FlowBlock pred = (FlowBlock)i.next();
742             if (pred == null)
743                 /* The special start marker */
744                 continue;
745             if (!pred.successors.containsKey(this))
746                 throw new AssertError("Inconsistency");
747         }
748
749         StructuredBlock last = lastModified;
750         while (last.outer instanceof SequentialBlock
751                || last.outer instanceof TryBlock
752                || last.outer instanceof FinallyBlock)
753             last = last.outer;
754         if (last.outer != null)
755             throw new AssertError("Inconsistency");
756
757         Iterator JavaDoc iter = successors.entrySet().iterator();
758         while (iter.hasNext()) {
759         Map.Entry entry = (Map.Entry) iter.next();
760             FlowBlock dest = (FlowBlock) entry.getKey();
761             if (dest.predecessors.contains(this) == (dest == END_OF_METHOD))
762                 throw new AssertError("Inconsistency");
763                 
764             Jump jumps = ((SuccessorInfo) entry.getValue()).jumps;
765             if (jumps == null)
766                 throw new AssertError("Inconsistency");
767                 
768             for (; jumps != null; jumps = jumps.next) {
769                     
770                 if (jumps.destination != dest)
771                     throw new AssertError("Inconsistency");
772                     
773                 if (jumps.prev == null
774             || jumps.prev.flowBlock != this
775             || jumps.prev.jump != jumps)
776                     throw new AssertError("Inconsistency");
777                     
778             prev_loop:
779                 for (StructuredBlock prev = jumps.prev; prev != block;
780                      prev = prev.outer) {
781                     if (prev.outer == null)
782                         throw new RuntimeException JavaDoc("Inconsistency");
783                     StructuredBlock[] blocks = prev.outer.getSubBlocks();
784                     int i;
785                     for (i=0; i<blocks.length; i++)
786                         if (blocks[i] == prev)
787                             continue prev_loop;
788                         
789                     throw new AssertError("Inconsistency");
790                 }
791             }
792         }
793     } catch (AssertError err) {
794         GlobalOptions.err.println("Inconsistency in: "+this);
795         throw err;
796     }
797     }
798
799     public void appendBlock(StructuredBlock block, int length) {
800     SlotSet succIn = new SlotSet();
801     SlotSet succKill = new SlotSet();
802     VariableSet succGen = new VariableSet();
803     block.fillInGenSet(succIn, succKill);
804     succGen.addAll(succKill);
805
806     if (this.block == null) {
807         this.block = block;
808         lastModified = block;
809         block.setFlowBlock(this);
810         block.fillSuccessors();
811         this.length = length;
812         
813         in = succIn;
814         gen = succGen;
815         for (Iterator JavaDoc i = successors.values().iterator(); i.hasNext();) {
816         SuccessorInfo info = (SuccessorInfo) i.next();
817         info.gen = new VariableSet();
818         info.kill = new SlotSet();
819         info.gen.addAll(succGen);
820         info.kill.addAll(succKill);
821         }
822     } else if (!(block instanceof EmptyBlock)) {
823         checkConsistent();
824         if ((GlobalOptions.debuggingFlags
825          & GlobalOptions.DEBUG_FLOW) != 0) {
826         GlobalOptions.err.println("appending Block: "+block);
827         }
828     
829         SuccessorInfo succInfo
830         = (SuccessorInfo) successors.get(NEXT_BY_ADDR);
831         succIn.merge(succInfo.gen);
832         succIn.removeAll(succInfo.kill);
833         
834         succGen.mergeGenKill(succInfo.gen, succKill);
835         succKill.mergeKill(succInfo.kill);
836         this.in.addAll(succIn);
837         this.gen.addAll(succKill);
838         
839         removeSuccessor(lastModified.jump);
840         lastModified.removeJump();
841         lastModified = lastModified.appendBlock(block);
842         block.fillSuccessors();
843         succInfo = (SuccessorInfo) successors.get(NEXT_BY_ADDR);
844         succInfo.gen = succGen;
845         succInfo.kill = succKill;
846         this.length += length;
847         checkConsistent();
848         doTransformations();
849     }
850     checkConsistent();
851     }
852
853     /**
854      * Append the given flowblock to the nextByAddr/prevByAddr chain.
855      * nextByAddr should be null, when calling this.
856      * @param flow The flowBlock to append
857      */

858     public void setNextByAddr(FlowBlock flow)
859     {
860     /* nextByAddr can be set, when reordering block in transform exc */
861 // if (nextByAddr != null)
862
// throw new IllegalStateException("nextByAddr already set");
863
if (flow == END_OF_METHOD || flow == NEXT_BY_ADDR)
864         throw new IllegalArgumentException JavaDoc
865         ("nextByAddr mustn't be special");
866     SuccessorInfo info = (SuccessorInfo) successors.remove(NEXT_BY_ADDR);
867     SuccessorInfo flowInfo = (SuccessorInfo) successors.get(flow);
868     if (info != null) {
869         NEXT_BY_ADDR.predecessors.remove(this);
870         Jump jumps = info.jumps;
871         jumps.destination = flow;
872         while (jumps.next != null) {
873         jumps = jumps.next;
874         jumps.destination = flow;
875         }
876         successors.put(flow, info);
877         if (flowInfo != null) {
878         info.gen.addAll(flowInfo.gen);
879         info.kill.retainAll(flowInfo.kill);
880         jumps.next = flowInfo.jumps;
881         } else
882         flow.predecessors.add(this);
883         }
884     checkConsistent();
885
886     nextByAddr = flow;
887     flow.prevByAddr = this;
888     }
889
890     /**
891      * Do a T2 transformation with succ if possible. It is possible,
892      * iff succ has exactly this block as predecessor.
893      * @param succ the successor block, must be a valid successor of this
894      * block, i.e. not null
895      */

896     public boolean doT2(FlowBlock succ) {
897         /* check if this successor has only this block as predecessor.
898          * if the predecessor is not unique, return false. */

899         if (succ.predecessors.size() != 1 ||
900             succ.predecessors.get(0) != this)
901             return false;
902
903         checkConsistent();
904         succ.checkConsistent();
905
906     if ((GlobalOptions.debuggingFlags
907          & GlobalOptions.DEBUG_ANALYZE) != 0)
908         GlobalOptions.err.println
909         ("T2(["+addr+","+getNextAddr()+"],["
910          +succ.addr+","+succ.getNextAddr()+"])");
911
912         SuccessorInfo succInfo = (SuccessorInfo) successors.remove(succ);
913
914         /* Update the in/out-Vectors now */
915         updateInOut(succ, succInfo);
916         if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
917             GlobalOptions.err.println("before Resolve: "+this);
918
919         /* Try to eliminate as many jumps as possible.
920          */

921         Jump jumps = resolveSomeJumps(succInfo.jumps, succ);
922         if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
923             GlobalOptions.err.println("before Remaining: "+this);
924         resolveRemaining(jumps);
925         if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
926             GlobalOptions.err.println("after Resolve: "+this);
927
928         /* Now unify the blocks.
929          */

930         lastModified = lastModified.appendBlock(succ.block);
931         mergeSuccessors(succ);
932
933         /* This will also set last modified to the new correct value. */
934         doTransformations();
935
936         /* Set addr and length to correct value and update nextByAddr */
937     mergeAddr(succ);
938
939         /* T2 transformation succeeded */
940         checkConsistent();
941         return true;
942     }
943
944     /**
945      * Do a T2 transformation with the end_of_method block.
946      */

947     public void mergeEndBlock() {
948         checkConsistent();
949
950         SuccessorInfo endInfo
951         = (SuccessorInfo) successors.remove(END_OF_METHOD);
952         if (endInfo == null)
953             return;
954
955     Jump allJumps = endInfo.jumps;
956         /* First remove all implicit jumps to the END_OF_METHOD block.
957          */

958         Jump jumps = null;
959         for (; allJumps != null; ) {
960             Jump jump = allJumps;
961             allJumps = allJumps.next;
962
963             if (jump.prev instanceof ReturnBlock) {
964                 /* This jump is implicit */
965                 jump.prev.removeJump();
966                 continue;
967             }
968             jump.next = jumps;
969             jumps = jump;
970         }
971             
972         /* Try to eliminate as many jumps as possible.
973          */

974         jumps = resolveSomeJumps(jumps, END_OF_METHOD);
975             
976     next_jump:
977         for (; jumps != null; jumps = jumps.next) {
978
979             StructuredBlock prevBlock = jumps.prev;
980         
981             if (lastModified == prevBlock)
982                 /* handled later */
983                 continue;
984
985             BreakableBlock breakToBlock = null;
986             for (StructuredBlock surrounder = prevBlock.outer;
987                  surrounder != null; surrounder = surrounder.outer) {
988                 if (surrounder instanceof BreakableBlock) {
989                     if (surrounder.getNextFlowBlock() == END_OF_METHOD)
990                         breakToBlock = (BreakableBlock) surrounder;
991
992                     /* We don't want labeled breaks, because we can
993                      * simply return. */

994                     break;
995                 }
996             }
997             prevBlock.removeJump();
998
999             if (breakToBlock == null)
1000                /* The successor is the dummy return instruction, so
1001                 * replace the jump with a return.
1002                 */

1003                prevBlock.appendBlock(new ReturnBlock());
1004            else
1005                prevBlock.appendBlock
1006                    (new BreakBlock(breakToBlock, false));
1007        }
1008
1009        /* Now remove the jump of the lastModified if it points to
1010         * END_OF_METHOD.
1011         */

1012        if (lastModified.jump.destination == END_OF_METHOD)
1013            lastModified.removeJump();
1014
1015        doTransformations();
1016        /* transformation succeeded */
1017        checkConsistent();
1018    }
1019
1020    public boolean doT1(int start, int end) {
1021        /* If there are no jumps to the beginning of this flow block
1022         * or if this block has other predecessors with a not yet
1023         * considered address, return false. The second condition
1024         * make sure that not for each continue a while is created.
1025         */

1026        if (!predecessors.contains(this))
1027            return false;
1028        for (Iterator JavaDoc i = predecessors.iterator(); i.hasNext(); ) {
1029            FlowBlock predFlow = (FlowBlock) i.next();
1030            if (predFlow != null && predFlow != this
1031                && predFlow.addr >= start && predFlow.addr < end) {
1032                return false;
1033            }
1034        }
1035
1036        checkConsistent();
1037
1038    if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1039        GlobalOptions.err.println("T1(["+addr+","+getNextAddr()+"])");
1040        SuccessorInfo succInfo = (SuccessorInfo) successors.remove(this);
1041
1042        /* Update the in/out-Vectors now */
1043        updateInOut(this, succInfo);
1044    Jump jumps = succInfo.jumps;
1045
1046        StructuredBlock bodyBlock = block;
1047
1048        /* If there is only one jump to the beginning and it is
1049         * the last jump (lastModified) and (there is a
1050         * do/while(0) block surrounding everything but the last
1051         * instruction, or the last instruction is a
1052         * increase/decrease statement), replace the do/while(0)
1053         * with a for(;;last_instr) resp. create a new one and
1054         * replace breaks to do/while with continue to for. */

1055
1056        boolean createdForBlock = false;
1057
1058        if (jumps.next == null
1059            && jumps.prev == lastModified
1060            && lastModified instanceof InstructionBlock
1061            && ((InstructionBlock)lastModified).getInstruction().isVoid()) {
1062            
1063            if (lastModified.outer instanceof SequentialBlock
1064                && lastModified.outer.getSubBlocks()[0]
1065                instanceof LoopBlock) {
1066                
1067                LoopBlock lb =
1068                    (LoopBlock) lastModified.outer.getSubBlocks()[0];
1069                if (lb.cond == lb.FALSE && lb.type == lb.DOWHILE) {
1070                    
1071                    /* The jump is directly following a
1072                     * do-while(false) block
1073                     *
1074                     * Remove do/while, create a for(;;last_instr)
1075                     * and replace break to that block with
1076                     * continue to for.
1077                     */

1078                    
1079                    lastModified.removeJump();
1080                    LoopBlock forBlock =
1081                        new LoopBlock(LoopBlock.FOR, LoopBlock.TRUE);
1082                    forBlock.replace(bodyBlock);
1083                    forBlock.setBody(bodyBlock);
1084                    forBlock.incrInstr
1085            = ((InstructionBlock) lastModified).getInstruction();
1086                    forBlock.replaceBreakContinue(lb);
1087
1088                    lb.bodyBlock.replace(lastModified.outer);
1089                    createdForBlock = true;
1090                }
1091                
1092            }
1093
1094            if (!createdForBlock
1095                && (((InstructionBlock) lastModified).getInstruction()
1096            instanceof CombineableOperator)) {
1097        
1098                /* The only jump is the jump of the last
1099                 * instruction lastModified, there is a big
1100                 * chance, that this is a for block, but we
1101                 * can't be sure until we have seen the condition.
1102                 * We will transform it to a for block, and take
1103                 * that back, when we get a non matching condition.
1104                 */

1105                
1106                lastModified.removeJump();
1107                LoopBlock forBlock =
1108                    new LoopBlock(LoopBlock.POSSFOR, LoopBlock.TRUE);
1109                forBlock.replace(bodyBlock);
1110                forBlock.setBody(bodyBlock);
1111                forBlock.incrBlock = (InstructionBlock) lastModified;
1112                
1113                createdForBlock = true;
1114            }
1115        }
1116
1117        if (!createdForBlock) {
1118            /* Creating a for block didn't succeed; create a
1119             * while block instead. */

1120            
1121            /* Try to eliminate as many jumps as possible.
1122             */

1123            jumps = resolveSomeJumps(jumps, this);
1124            
1125            LoopBlock whileBlock =
1126                new LoopBlock(LoopBlock.WHILE, LoopBlock.TRUE);
1127
1128            /* The block may have been changed above. */
1129            bodyBlock = block;
1130            whileBlock.replace(bodyBlock);
1131            whileBlock.setBody(bodyBlock);
1132            
1133            /* if there are further jumps to this, replace every jump with a
1134             * continue to while block and return true.
1135             */

1136            for (; jumps != null; jumps = jumps.next) {
1137                
1138                if (jumps.prev == lastModified)
1139                    /* handled later */
1140                    continue;
1141                
1142                StructuredBlock prevBlock = jumps.prev;
1143
1144                int breaklevel = 0, continuelevel = 0;
1145                BreakableBlock breakToBlock = null;
1146                for (StructuredBlock surrounder = prevBlock.outer;
1147                     surrounder != whileBlock;
1148                     surrounder = surrounder.outer) {
1149                    if (surrounder instanceof BreakableBlock) {
1150                        if (surrounder instanceof LoopBlock)
1151                            continuelevel++;
1152                        breaklevel++;
1153                        if (surrounder.getNextFlowBlock() == this) {
1154                            breakToBlock = (BreakableBlock) surrounder;
1155                            break;
1156                        }
1157                    }
1158                }
1159                prevBlock.removeJump();
1160                if (breakToBlock == null)
1161                    prevBlock.appendBlock
1162                        (new ContinueBlock(whileBlock, continuelevel > 0));
1163                else
1164                    prevBlock.appendBlock
1165                        (new BreakBlock(breakToBlock, breaklevel > 1));
1166            }
1167            
1168            /* Now remove the jump of lastModified if it points to this.
1169             */

1170            if (lastModified.jump.destination == this)
1171                lastModified.removeJump();
1172        }
1173
1174        /* remove ourself from the predecessor list.
1175         */

1176        predecessors.remove(this);
1177        lastModified = block;
1178        doTransformations();
1179// mergeCondition();
1180

1181        /* T1 analysis succeeded */
1182        checkConsistent();
1183
1184        return true;
1185    }
1186
1187    public void doTransformations() {
1188        if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1189            GlobalOptions.err.println("before Transformation: "+this);
1190
1191        while (lastModified instanceof SequentialBlock) {
1192            if (lastModified.getSubBlocks()[0].doTransformations())
1193        continue;
1194        lastModified = lastModified.getSubBlocks()[1];
1195        }
1196        while (lastModified.doTransformations())
1197        { /* empty */ }
1198
1199        if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1200            GlobalOptions.err.println("after Transformation: "+this);
1201    }
1202
1203    /**
1204     * Search for an apropriate successor.
1205     * @param prevSucc The successor, that was previously tried.
1206     * @param start The minimum address.
1207     * @param end The maximum address + 1.
1208     * @return the successor with smallest address greater than prevSucc
1209     * or null if there isn't any further successor at all.
1210     */

1211    FlowBlock getSuccessor(int start, int end) {
1212        /* search successor with smallest addr. */
1213        Iterator JavaDoc keys = successors.keySet().iterator();
1214        FlowBlock succ = null;
1215        while (keys.hasNext()) {
1216            FlowBlock fb = (FlowBlock) keys.next();
1217            if (fb.addr < start || fb.addr >= end || fb == this)
1218                continue;
1219            if (succ == null || fb.addr < succ.addr) {
1220                succ = fb;
1221            }
1222        }
1223        return succ;
1224    }
1225
1226    /**
1227     * The main analyzation. This calls doT1 and doT2 on apropriate
1228     * regions until the whole function is transformed to a single
1229     * block.
1230     */

1231    public void analyze() {
1232        analyze(0, Integer.MAX_VALUE);
1233        mergeEndBlock();
1234    }
1235
1236    /**
1237     * The main analyzation. This calls doT1 and doT2 on apropriate
1238     * regions. Only blocks whose address lies in the given address
1239     * range are considered.
1240     * @param start the start of the address range.
1241     * @param end the end of the address range.
1242     */

1243    public boolean analyze(int start, int end) {
1244        if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1245            GlobalOptions.err.println("analyze("+start+", "+end+")");
1246
1247    checkConsistent();
1248        boolean changed = false;
1249
1250        while (true) {
1251
1252            if (lastModified instanceof SwitchBlock) {
1253                /* analyze the switch first.
1254                 */

1255                analyzeSwitch(start, end);
1256            }
1257
1258
1259            if (doT1(start, end)) {
1260
1261                if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1262                    GlobalOptions.err.println("after T1: "+this);
1263
1264                /* T1 transformation succeeded. This may
1265                 * make another T2 analysis in the previous
1266                 * block possible.
1267                 */

1268                if (addr != 0)
1269                    return true;
1270            }
1271
1272            FlowBlock succ = getSuccessor(start, end);
1273            while (true) {
1274                if (succ == null) {
1275                    /* the Block has no successor where T2 is applicable.
1276                     * Finish this analyzation.
1277                     */

1278                    if ((GlobalOptions.debuggingFlags
1279             & GlobalOptions.DEBUG_ANALYZE) != 0)
1280                        GlobalOptions.err.println
1281                            ("No more successors applicable: "
1282                             + start + " - " + end + "; "
1283                             + addr + " - " + getNextAddr());
1284                    return changed;
1285                } else {
1286                    if ((nextByAddr == succ || succ.nextByAddr == this)
1287                        /* Only do T2 transformation if the blocks are
1288                         * adjacent.
1289             */

1290                        && doT2(succ)) {
1291            /* T2 transformation succeeded. */
1292            changed = true;
1293            
1294            if ((GlobalOptions.debuggingFlags
1295                 & GlobalOptions.DEBUG_FLOW) != 0)
1296                GlobalOptions.err.println("after T2: "+this);
1297            break;
1298            }
1299
1300                    /* Check if all predecessors of succ
1301                     * lie in range [start,end). Otherwise
1302                     * we have no chance to combine succ
1303                     */

1304            for (Iterator JavaDoc i = succ.predecessors.iterator();
1305             i.hasNext(); ) {
1306                        int predAddr = ((FlowBlock)i.next()).addr;
1307                        if (predAddr < start || predAddr >= end) {
1308                            if ((GlobalOptions.debuggingFlags
1309                 & GlobalOptions.DEBUG_ANALYZE) != 0)
1310                                GlobalOptions.err.println
1311                                    ("breaking analyze("
1312                                     + start + ", " + end + "); "
1313                                     + addr + " - " + getNextAddr());
1314                            return changed;
1315                        }
1316                    }
1317                    /* analyze succ, the new region is the
1318                     * continuous region of
1319                     * [start,end) \cap \compl [addr, getNextAddr())
1320                     * where succ.addr lies in.
1321                     */

1322                    int newStart = (succ.addr > addr)
1323                        ? getNextAddr() : start;
1324                    int newEnd = (succ.addr > addr)
1325                        ? end : addr;
1326                    if (succ.analyze(newStart, newEnd))
1327                        break;
1328                }
1329                    
1330                /* Try the next successor.
1331                 */

1332                succ = getSuccessor(succ.addr+1, end);
1333            }
1334        }
1335    }
1336    
1337    /**
1338     * The switch analyzation. This calls doSwitchT2 and doT1 on apropriate
1339     * regions. Only blocks whose address lies in the given address
1340     * range are considered and it is taken care of, that the switch
1341     * is never leaved. <p>
1342     * The current flow block must contain the switch block as lastModified.
1343     * @param start the start of the address range.
1344     * @param end the end of the address range.
1345     */

1346    public boolean analyzeSwitch(int start, int end) {
1347        if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_ANALYZE) != 0)
1348            GlobalOptions.err.println("analyzeSwitch("+start+", "+end+")");
1349
1350        SwitchBlock switchBlock = (SwitchBlock) lastModified;
1351        boolean changed = false;
1352
1353        int last = -1;
1354        FlowBlock lastFlow = null;
1355        for (int i=0; i < switchBlock.caseBlocks.length; i++) {
1356            if (switchBlock.caseBlocks[i].subBlock instanceof EmptyBlock
1357                && switchBlock.caseBlocks[i].subBlock.jump != null) {
1358                FlowBlock nextFlow = switchBlock.caseBlocks[i].
1359                    subBlock.jump.destination;
1360                if (nextFlow.addr >= end)
1361                    break;
1362                else if (nextFlow.addr >= start) {
1363                    
1364            /* First analyze the nextFlow block. It may
1365                     * return early after a T1 trafo so call it
1366                     * until nothing more is possible.
1367                     */

1368                    while (nextFlow.analyze(getNextAddr(), end))
1369                        changed = true;
1370                    
1371                    if (nextFlow.addr != getNextAddr())
1372                        break;
1373                    
1374                    /* Check if nextFlow has only the previous case
1375                     * and this case as predecessor. Otherwise
1376                     * break the analysis.
1377                     */

1378                    if (nextFlow.predecessors.size() > 2
1379                        || (nextFlow.predecessors.size() > 1
1380                            && (lastFlow == null
1381                                || !nextFlow.predecessors.contains(lastFlow)))
1382                        || (((SuccessorInfo)successors.get(nextFlow))
1383                .jumps.next != null))
1384                        break;
1385
1386                    checkConsistent();
1387
1388                    /* note that this info only contains
1389             * the single caseBlock jump */

1390                    SuccessorInfo info = (SuccessorInfo)
1391            successors.remove(nextFlow);
1392
1393                    if (nextFlow.predecessors.size() == 2) {
1394            SuccessorInfo lastInfo = (SuccessorInfo)
1395                lastFlow.successors.remove(nextFlow);
1396
1397                        /* Do the in/out analysis with all jumps
1398                         * Note that this won't update lastFlow.in, but
1399                         * this will not be used anymore.
1400                         */

1401            info.kill.retainAll(lastInfo.kill);
1402            info.gen.addAll(lastInfo.gen);
1403
1404                        Jump lastJumps = lastFlow.resolveSomeJumps
1405                (lastInfo.jumps, nextFlow);
1406                        lastFlow.resolveRemaining(lastJumps);
1407            switchBlock.caseBlocks[last+1].isFallThrough = true;
1408                    }
1409            updateInOut(nextFlow, info);
1410                    
1411                    if (lastFlow != null) {
1412                        lastFlow.block.replace
1413                            (switchBlock.caseBlocks[last].subBlock);
1414                        mergeSuccessors(lastFlow);
1415                    }
1416
1417                    /* We merge the blocks into the caseBlock later, but
1418                     * that doesn't affect consistency.
1419                     */

1420
1421                    switchBlock.caseBlocks[i].subBlock.removeJump();
1422            mergeAddr(nextFlow);
1423
1424                    lastFlow = nextFlow;
1425                    last = i;
1426
1427                    checkConsistent();
1428                    changed = true;
1429                }
1430            }
1431        }
1432        if (lastFlow != null) {
1433            lastFlow.block.replace
1434                (switchBlock.caseBlocks[last].subBlock);
1435            mergeSuccessors(lastFlow);
1436        }
1437    
1438    if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0)
1439        GlobalOptions.err.println("after analyzeSwitch: "+this);
1440    if ((GlobalOptions.debuggingFlags
1441         & GlobalOptions.DEBUG_ANALYZE) != 0)
1442        GlobalOptions.err.println
1443        ("analyzeSwitch done: " + start + " - " + end + "; "
1444         + addr + " - " + getNextAddr());
1445        checkConsistent();
1446        return changed;
1447    }
1448    
1449    /**
1450     * Mark the flow block as first flow block in a method.
1451     */

1452    public void makeStartBlock() {
1453        predecessors.add(null);
1454    }
1455
1456    public void removeSuccessor(Jump jump) {
1457        SuccessorInfo destInfo
1458        = (SuccessorInfo) successors.get(jump.destination);
1459        Jump prev = null;
1460    Jump destJumps = destInfo.jumps;
1461        while (destJumps != jump && destJumps != null) {
1462            prev = destJumps;
1463            destJumps = destJumps.next;
1464        }
1465        if (destJumps == null)
1466            throw new IllegalArgumentException JavaDoc
1467        (addr+": removing non existent jump: " + jump);
1468
1469        if (prev != null)
1470            prev.next = destJumps.next;
1471        else {
1472            if (destJumps.next == null) {
1473                successors.remove(jump.destination);
1474        jump.destination.predecessors.remove(this);
1475            } else
1476        destInfo.jumps = destJumps.next;
1477        }
1478    }
1479
1480    public Jump getJumps(FlowBlock dest) {
1481    return ((SuccessorInfo) successors.get(dest)).jumps;
1482    }
1483
1484    public Jump removeJumps(FlowBlock dest) {
1485    if (dest != END_OF_METHOD)
1486        dest.predecessors.remove(this);
1487    return ((SuccessorInfo) successors.remove(dest)).jumps;
1488    }
1489
1490    public Set getSuccessors() {
1491    return successors.keySet();
1492    }
1493
1494    public void addSuccessor(Jump jump) {
1495    SuccessorInfo info = (SuccessorInfo) successors.get(jump.destination);
1496    if (info == null) {
1497        info = new SuccessorInfo();
1498        info.jumps = jump;
1499        if (jump.destination != END_OF_METHOD)
1500        jump.destination.predecessors.add(this);
1501        successors.put(jump.destination, info);
1502    } else {
1503        jump.next = info.jumps;
1504        info.jumps = jump;
1505    }
1506    }
1507
1508    /**
1509     * This is called after the analysis is completely done. It
1510     * will remove all PUSH/stack_i expressions, (if the bytecode
1511     * is correct).
1512     * @return true, if the stack mapping succeeded.
1513     */

1514    public final boolean mapStackToLocal() {
1515    mapStackToLocal(VariableStack.EMPTY);
1516    return true;
1517    }
1518
1519    /**
1520     * This is called after the analysis is completely done. It
1521     * will remove all PUSH/stack_i expressions, (if the bytecode
1522     * is correct).
1523     * @param initialStack the stackmap at begin of the flow block
1524     * @return false if the bytecode isn't correct and stack mapping
1525     * didn't worked.
1526     */

1527    public void mapStackToLocal(VariableStack initialStack) {
1528    if (initialStack == null)
1529        throw new jode.AssertError("initial stack is null");
1530    stackMap = initialStack;
1531    block.mapStackToLocal(initialStack);
1532    Iterator JavaDoc iter = successors.values().iterator();
1533    while (iter.hasNext()) {
1534        SuccessorInfo succInfo = (SuccessorInfo) iter.next();
1535        Jump jumps = succInfo.jumps;
1536        VariableStack stack;
1537        FlowBlock succ = jumps.destination;
1538        if (succ == END_OF_METHOD)
1539        continue;
1540        stack = succ.stackMap;
1541        for (/**/; jumps != null; jumps = jumps.next) {
1542        if (jumps.stackMap == null)
1543            GlobalOptions.err.println("Dead jump? "+jumps.prev
1544                          +" in "+this);
1545        
1546        stack = VariableStack.merge(stack, jumps.stackMap);
1547        }
1548        if (succ.stackMap == null)
1549        succ.mapStackToLocal(stack);
1550    }
1551    }
1552
1553    public void removePush() {
1554    if (stackMap == null)
1555        /* already done or mapping didn't succeed */
1556        return;
1557    stackMap = null;
1558    block.removePush();
1559    Iterator JavaDoc iter = successors.keySet().iterator();
1560    while (iter.hasNext()) {
1561        FlowBlock succ = (FlowBlock)iter.next();
1562        succ.removePush();
1563    }
1564    }
1565
1566    public void removeOnetimeLocals() {
1567    block.removeOnetimeLocals();
1568    if (nextByAddr != null)
1569        nextByAddr.removeOnetimeLocals();
1570    }
1571
1572    private void promoteInSets() {
1573    for (Iterator JavaDoc i = predecessors.iterator(); i.hasNext(); ) {
1574        FlowBlock pred = (FlowBlock) i.next();
1575        SuccessorInfo succInfo = (SuccessorInfo) pred.successors.get(this);
1576
1577        /* First get the gen/kill sets of all jumps of predecessor
1578         * to this block and calculate the intersection.
1579         */

1580        VariableSet gens = succInfo.gen;
1581        SlotSet kills = succInfo.kill;
1582        
1583        /* Merge in locals of this block with those condionally
1584         * written by previous blocks */

1585        in.merge(gens);
1586        
1587        /* The ins of the successor that are not killed
1588         * (i.e. unconditionally overwritten) by this block are new
1589         * ins for this block.
1590         */

1591        SlotSet newIn = (SlotSet) in.clone();
1592        newIn.removeAll(kills);
1593
1594        if (pred.in.addAll(newIn))
1595        pred.promoteInSets();
1596    }
1597
1598    if (nextByAddr != null)
1599        nextByAddr.promoteInSets();
1600    }
1601
1602    /**
1603     * Merge the parameter locals with the in set of this flow block.
1604     * This will also make a successive analysis to merge the gen/kill
1605     * set of the jumps with the next flow block. */

1606    public void mergeParams(LocalInfo[] param) {
1607    // Now we promote the final (maybe slow) in set analysis
1608
promoteInSets();
1609
1610    VariableSet paramSet = new VariableSet(param);
1611    in.merge(paramSet);
1612    }
1613
1614    /**
1615     * Make declarations. It will determine, where in each block the
1616     * variables and method scoped classes must be declared.
1617     */

1618    public void makeDeclaration(Set done) {
1619    block.propagateUsage();
1620    block.makeDeclaration(done);
1621    if (nextByAddr != null)
1622        nextByAddr.makeDeclaration(done);
1623    }
1624
1625    /**
1626     * Simplify this and all following flowblocks.
1627     */

1628    public void simplify() {
1629    block.simplify();
1630    if (nextByAddr != null)
1631        nextByAddr.simplify();
1632    }
1633
1634    /**
1635     * Print the source code for this structured block. This handles
1636     * everything that is unique for all structured blocks and calls
1637     * dumpInstruction afterwards.
1638     * @param writer The tabbed print writer, where we print to.
1639     */

1640    public void dumpSource(TabbedPrintWriter writer)
1641        throws java.io.IOException JavaDoc
1642    {
1643        if (predecessors.size() != 0) {
1644            writer.untab();
1645            writer.println(getLabel()+":");
1646            writer.tab();
1647        }
1648
1649        if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_INOUT) != 0) {
1650            writer.println("in: "+in);
1651        }
1652
1653        block.dumpSource(writer);
1654
1655        if ((GlobalOptions.debuggingFlags
1656         & GlobalOptions.DEBUG_INOUT) != 0) {
1657        
1658        Iterator JavaDoc iter = successors.entrySet().iterator();
1659        while (iter.hasNext()) {
1660        Map.Entry entry = (Map.Entry) iter.next();
1661        FlowBlock dest = (FlowBlock) entry.getKey();
1662        SuccessorInfo info = (SuccessorInfo) entry.getValue();
1663        writer.println("successor: "+dest.getLabel()
1664                   +" gen : "+ info.gen
1665                   +" kill: "+ info.kill);
1666        }
1667    }
1668
1669    if (nextByAddr != null)
1670        nextByAddr.dumpSource(writer);
1671    }
1672
1673    /**
1674     * The serial number for labels.
1675     */

1676    static int serialno = 0;
1677
1678    /**
1679     * The label of this instruction, or null if it needs no label.
1680     */

1681    String JavaDoc label = null;
1682
1683    /**
1684     * Returns the address, where the code in this flow block starts.
1685     */

1686    public int getAddr() {
1687    return addr;
1688    }
1689
1690    /**
1691     * Returns the label of this block and creates a new label, if
1692     * there wasn't a label previously.
1693     */

1694    public String JavaDoc getLabel() {
1695        if (label == null)
1696            label = "flow_"+addr+"_"+(serialno++)+"_";
1697        return label;
1698    }
1699
1700    /**
1701     * Returns the structured block, that this flow block contains.
1702     */

1703    public StructuredBlock getBlock() {
1704        return block;
1705    }
1706
1707    public String JavaDoc toString() {
1708        try {
1709            java.io.StringWriter JavaDoc strw = new java.io.StringWriter JavaDoc();
1710            TabbedPrintWriter writer = new TabbedPrintWriter(strw);
1711            writer.println(super.toString() + ": "+addr+"-"+(addr+length));
1712        if ((GlobalOptions.debuggingFlags
1713         & GlobalOptions.DEBUG_INOUT) != 0) {
1714        writer.println("in: "+in);
1715        }
1716            writer.tab();
1717            block.dumpSource(writer);
1718            writer.untab();
1719        if ((GlobalOptions.debuggingFlags
1720         & GlobalOptions.DEBUG_INOUT) != 0) {
1721        
1722        Iterator JavaDoc iter = successors.entrySet().iterator();
1723        while (iter.hasNext()) {
1724            Map.Entry entry = (Map.Entry) iter.next();
1725            FlowBlock dest = (FlowBlock) entry.getKey();
1726            SuccessorInfo info = (SuccessorInfo) entry.getValue();
1727            writer.println("successor: "+dest.getLabel()
1728                   +" gen : "+ info.gen
1729                   +" kill: "+ info.kill);
1730        }
1731        }
1732            return strw.toString();
1733        } catch (RuntimeException JavaDoc ex) {
1734        return super.toString() + ": (RUNTIME EXCEPTION)";
1735        } catch (java.io.IOException JavaDoc ex) {
1736            return super.toString();
1737        }
1738    }
1739}
1740
Popular Tags