1 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 ; 32 import java.util.Iterator ; 33 import java.util.Set ; 34 import java.util.ArrayList ; 35 import java.util.List ; 36 37 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 68 MethodAnalyzer method; 69 70 77 private SlotSet in = new SlotSet(); 78 83 VariableSet gen = new VariableSet(); 84 85 89 private int addr; 90 91 94 private int length; 95 96 99 StructuredBlock block; 100 101 106 StructuredBlock lastModified; 107 108 114 private Map successors = new SimpleMap(); 115 116 124 List predecessors = new ArrayList (); 125 126 130 FlowBlock nextByAddr; 131 132 136 FlowBlock prevByAddr; 137 138 143 VariableStack stackMap; 144 145 static class SuccessorInfo { 146 153 SlotSet kill; 154 155 163 VariableSet gen; 164 165 168 Jump jumps; 169 } 170 171 172 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 194 public Jump resolveSomeJumps(Jump jumps, FlowBlock succ) { 195 198 Jump remainingJumps = null; 199 200 if (lastModified.jump == null) { 201 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 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 232 if (jump.prev == lastModified) { 233 jump.next = remainingJumps; 234 remainingJumps = jump; 235 continue; 236 } 237 238 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 252 253 if (cb.jump != null) { 254 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 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 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 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 310 311 312 StructuredBlock sb = cb.outer.outer; 313 while (sb instanceof SequentialBlock) { 314 sb = sb.outer; 315 } 316 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 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 347 348 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 383 jumps = jump; 384 continue; 385 } 386 } else { 387 388 390 if (jump.destination 391 == jump.prev.outer.getNextFlowBlock(jump.prev)) { 392 jump.prev.removeJump(); 393 continue; 394 } 395 396 397 406 StructuredBlock sb = jump.prev.outer; 407 while (sb instanceof SequentialBlock) 408 sb = sb.outer; 409 410 411 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 427 jumps = jump; 428 continue; 429 } 430 } 431 432 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 465 ifBlock.moveJump(jump); 466 jumps = jump; 467 continue; 468 } 469 } 470 } 471 472 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 484 break; 485 486 if (surrounder.jumpMayBeChanged()) { 487 surrounder.setJump(new Jump(succ)); 488 489 surrounder.jump.next = jumps; 490 jumps = surrounder.jump; 491 492 break; 493 } 494 if (succ == END_OF_METHOD) { 495 499 break; 500 } 501 } 502 } 503 jump.next = remainingJumps; 504 remainingJumps = jump; 505 } 506 return remainingJumps; 507 } 508 509 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 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 548 if (doWhileFalse == null) { 549 doWhileFalse = new LoopBlock(LoopBlock.DOWHILE, 550 LoopBlock.FALSE); 551 } 552 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 576 void mergeSuccessors(FlowBlock succ) { 577 579 Iterator 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 606 public void mergeAddr(FlowBlock succ) { 607 if (succ.nextByAddr == this || succ.prevByAddr == null) { 608 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 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 635 void updateInOut(FlowBlock successor, SuccessorInfo succInfo) { 636 639 SlotSet kills = succInfo.kill; 640 VariableSet gens = succInfo.gen; 641 642 645 successor.in.merge(gens); 646 647 651 SlotSet newIn = (SlotSet) successor.in.clone(); 652 newIn.removeAll(kills); 653 654 656 Iterator 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 695 public void updateInOutCatch (FlowBlock catchFlow) { 696 VariableSet gens = ((TryBlock)block).gen; 697 698 701 catchFlow.in.merge(gens); 702 703 705 Iterator 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 727 public void checkConsistent() { 728 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 i = predecessors.iterator(); i.hasNext(); ) { 741 FlowBlock pred = (FlowBlock)i.next(); 742 if (pred == null) 743 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 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 ("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 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 858 public void setNextByAddr(FlowBlock flow) 859 { 860 861 if (flow == END_OF_METHOD || flow == NEXT_BY_ADDR) 864 throw new IllegalArgumentException 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 896 public boolean doT2(FlowBlock succ) { 897 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 915 updateInOut(succ, succInfo); 916 if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0) 917 GlobalOptions.err.println("before Resolve: "+this); 918 919 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 930 lastModified = lastModified.appendBlock(succ.block); 931 mergeSuccessors(succ); 932 933 934 doTransformations(); 935 936 937 mergeAddr(succ); 938 939 940 checkConsistent(); 941 return true; 942 } 943 944 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 958 Jump jumps = null; 959 for (; allJumps != null; ) { 960 Jump jump = allJumps; 961 allJumps = allJumps.next; 962 963 if (jump.prev instanceof ReturnBlock) { 964 965 jump.prev.removeJump(); 966 continue; 967 } 968 jump.next = jumps; 969 jumps = jump; 970 } 971 972 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 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 994 break; 995 } 996 } 997 prevBlock.removeJump(); 998 999 if (breakToBlock == null) 1000 1003 prevBlock.appendBlock(new ReturnBlock()); 1004 else 1005 prevBlock.appendBlock 1006 (new BreakBlock(breakToBlock, false)); 1007 } 1008 1009 1012 if (lastModified.jump.destination == END_OF_METHOD) 1013 lastModified.removeJump(); 1014 1015 doTransformations(); 1016 1017 checkConsistent(); 1018 } 1019 1020 public boolean doT1(int start, int end) { 1021 1026 if (!predecessors.contains(this)) 1027 return false; 1028 for (Iterator 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 1043 updateInOut(this, succInfo); 1044 Jump jumps = succInfo.jumps; 1045 1046 StructuredBlock bodyBlock = block; 1047 1048 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 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 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 1120 1121 1123 jumps = resolveSomeJumps(jumps, this); 1124 1125 LoopBlock whileBlock = 1126 new LoopBlock(LoopBlock.WHILE, LoopBlock.TRUE); 1127 1128 1129 bodyBlock = block; 1130 whileBlock.replace(bodyBlock); 1131 whileBlock.setBody(bodyBlock); 1132 1133 1136 for (; jumps != null; jumps = jumps.next) { 1137 1138 if (jumps.prev == lastModified) 1139 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 1170 if (lastModified.jump.destination == this) 1171 lastModified.removeJump(); 1172 } 1173 1174 1176 predecessors.remove(this); 1177 lastModified = block; 1178 doTransformations(); 1179 1181 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 { } 1198 1199 if ((GlobalOptions.debuggingFlags & GlobalOptions.DEBUG_FLOW) != 0) 1200 GlobalOptions.err.println("after Transformation: "+this); 1201 } 1202 1203 1211 FlowBlock getSuccessor(int start, int end) { 1212 1213 Iterator 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 1231 public void analyze() { 1232 analyze(0, Integer.MAX_VALUE); 1233 mergeEndBlock(); 1234 } 1235 1236 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 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 1268 if (addr != 0) 1269 return true; 1270 } 1271 1272 FlowBlock succ = getSuccessor(start, end); 1273 while (true) { 1274 if (succ == null) { 1275 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 1290 && doT2(succ)) { 1291 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 1304 for (Iterator 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 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 1332 succ = getSuccessor(succ.addr+1, end); 1333 } 1334 } 1335 } 1336 1337 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 1368 while (nextFlow.analyze(getNextAddr(), end)) 1369 changed = true; 1370 1371 if (nextFlow.addr != getNextAddr()) 1372 break; 1373 1374 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 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 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 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 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 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 1514 public final boolean mapStackToLocal() { 1515 mapStackToLocal(VariableStack.EMPTY); 1516 return true; 1517 } 1518 1519 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 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 1556 return; 1557 stackMap = null; 1558 block.removePush(); 1559 Iterator 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 i = predecessors.iterator(); i.hasNext(); ) { 1574 FlowBlock pred = (FlowBlock) i.next(); 1575 SuccessorInfo succInfo = (SuccessorInfo) pred.successors.get(this); 1576 1577 1580 VariableSet gens = succInfo.gen; 1581 SlotSet kills = succInfo.kill; 1582 1583 1585 in.merge(gens); 1586 1587 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 1606 public void mergeParams(LocalInfo[] param) { 1607 promoteInSets(); 1609 1610 VariableSet paramSet = new VariableSet(param); 1611 in.merge(paramSet); 1612 } 1613 1614 1618 public void makeDeclaration(Set done) { 1619 block.propagateUsage(); 1620 block.makeDeclaration(done); 1621 if (nextByAddr != null) 1622 nextByAddr.makeDeclaration(done); 1623 } 1624 1625 1628 public void simplify() { 1629 block.simplify(); 1630 if (nextByAddr != null) 1631 nextByAddr.simplify(); 1632 } 1633 1634 1640 public void dumpSource(TabbedPrintWriter writer) 1641 throws java.io.IOException 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 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 1676 static int serialno = 0; 1677 1678 1681 String label = null; 1682 1683 1686 public int getAddr() { 1687 return addr; 1688 } 1689 1690 1694 public String getLabel() { 1695 if (label == null) 1696 label = "flow_"+addr+"_"+(serialno++)+"_"; 1697 return label; 1698 } 1699 1700 1703 public StructuredBlock getBlock() { 1704 return block; 1705 } 1706 1707 public String toString() { 1708 try { 1709 java.io.StringWriter strw = new java.io.StringWriter (); 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 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 ex) { 1734 return super.toString() + ": (RUNTIME EXCEPTION)"; 1735 } catch (java.io.IOException ex) { 1736 return super.toString(); 1737 } 1738 } 1739} 1740 | Popular Tags |