plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/FinallyProcessor.java

   1 // Copyright 2000-2021 JetBrains s.r.o. and contributors. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
   2 package org.jetbrains.java.decompiler.modules.decompiler;
   3
   4 import org.jetbrains.java.decompiler.code.CodeConstants;
   5 import org.jetbrains.java.decompiler.code.Instruction;
   6 import org.jetbrains.java.decompiler.code.InstructionSequence;
   7 import org.jetbrains.java.decompiler.code.SimpleInstructionSequence;
   8 import org.jetbrains.java.decompiler.code.cfg.BasicBlock;
   9 import org.jetbrains.java.decompiler.code.cfg.ControlFlowGraph;
  10 import org.jetbrains.java.decompiler.code.cfg.ExceptionRangeCFG;
  11 import org.jetbrains.java.decompiler.main.DecompilerContext;
  12 import org.jetbrains.java.decompiler.main.collectors.CounterContainer;
  13 import org.jetbrains.java.decompiler.main.extern.IFernflowerPreferences;
  14 import org.jetbrains.java.decompiler.modules.code.DeadCodeHelper;
  15 import org.jetbrains.java.decompiler.modules.decompiler.exps.AssignmentExprent;
  16 import org.jetbrains.java.decompiler.modules.decompiler.exps.ExitExprent;
  17 import org.jetbrains.java.decompiler.modules.decompiler.exps.Exprent;
  18 import org.jetbrains.java.decompiler.modules.decompiler.exps.VarExprent;
  19 import org.jetbrains.java.decompiler.modules.decompiler.sforms.DirectGraph;
  20 import org.jetbrains.java.decompiler.modules.decompiler.sforms.DirectNode;
  21 import org.jetbrains.java.decompiler.modules.decompiler.sforms.FlattenStatementsHelper;
  22 import org.jetbrains.java.decompiler.modules.decompiler.sforms.SSAConstructorSparseEx;
  23 import org.jetbrains.java.decompiler.modules.decompiler.stats.BasicBlockStatement;
  24 import org.jetbrains.java.decompiler.modules.decompiler.stats.CatchAllStatement;
  25 import org.jetbrains.java.decompiler.modules.decompiler.stats.RootStatement;
  26 import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement;
  27 import org.jetbrains.java.decompiler.modules.decompiler.vars.VarProcessor;
  28 import org.jetbrains.java.decompiler.modules.decompiler.vars.VarVersionPair;
  29 import org.jetbrains.java.decompiler.struct.StructClass;
  30 import org.jetbrains.java.decompiler.struct.StructMethod;
  31 import org.jetbrains.java.decompiler.struct.gen.MethodDescriptor;
  32 import org.jetbrains.java.decompiler.struct.gen.VarType;
  33 import org.jetbrains.java.decompiler.util.InterpreterUtil;
  34
  35 import java.util.*;
  36 import java.util.Map.Entry;
  37
  38 public class FinallyProcessor {
  39   private final Map<Integer, Integer> finallyBlockIDs = new HashMap<>();
  40   private final Map<Integer, Integer> catchallBlockIDs = new HashMap<>();
  41
  42   private final MethodDescriptor methodDescriptor;
  43   private final VarProcessor varProcessor;
  44
  45   public FinallyProcessor(MethodDescriptor md, VarProcessor varProc) {
  46     methodDescriptor = md;
  47     varProcessor = varProc;
  48   }
  49
  50   public boolean iterateGraph(StructClass cl, StructMethod mt, RootStatement root, ControlFlowGraph graph) {
  51     int bytecodeVersion = mt.getBytecodeVersion();
  52
  53     LinkedList<Statement> stack = new LinkedList<>();
  54     stack.add(root);
  55
  56     while (!stack.isEmpty()) {
  57       Statement stat = stack.removeLast();
  58
  59       Statement parent = stat.getParent();
  60       if (parent != null && parent.type == Statement.TYPE_CATCH_ALL &&
  61           stat == parent.getFirst() && !parent.isCopied()) {
  62
  63         CatchAllStatement fin = (CatchAllStatement)parent;
  64         BasicBlock head = fin.getBasichead().getBlock();
  65         BasicBlock handler = fin.getHandler().getBasichead().getBlock();
  66
  67         if (catchallBlockIDs.containsKey(handler.id)) {
  68           // do nothing
  69         }
  70         else if (finallyBlockIDs.containsKey(handler.id)) {
  71           fin.setFinally(true);
  72
  73           Integer var = finallyBlockIDs.get(handler.id);
  74           fin.setMonitor(var == null ? null : new VarExprent(var, VarType.VARTYPE_INT, varProcessor));
  75         }
  76         else {
  77           Record inf = getFinallyInformation(cl, mt, root, fin);
  78
  79           if (inf == null) { // inconsistent finally
  80             catchallBlockIDs.put(handler.id, null);
  81           }
  82           else {
  83             if (DecompilerContext.getOption(IFernflowerPreferences.FINALLY_DEINLINE) && verifyFinallyEx(graph, fin, inf)) {
  84               finallyBlockIDs.put(handler.id, null);
  85             }
  86             else {
  87               int varIndex = DecompilerContext.getCounterContainer().getCounterAndIncrement(CounterContainer.VAR_COUNTER);
  88               insertSemaphore(graph, getAllBasicBlocks(fin.getFirst()), head, handler, varIndex, inf, bytecodeVersion);
  89
  90               finallyBlockIDs.put(handler.id, varIndex);
  91             }
  92
  93             DeadCodeHelper.removeDeadBlocks(graph); // e.g. multiple return blocks after a nested finally
  94             DeadCodeHelper.removeEmptyBlocks(graph);
  95             DeadCodeHelper.mergeBasicBlocks(graph);
  96           }
  97
  98           return true;
  99         }
 100       }
 101
 102       stack.addAll(stat.getStats());
 103     }
 104
 105     return false;
 106   }
 107
 108   private static final class Record {
 109     private final int firstCode;
 110     private final Map<BasicBlock, Boolean> mapLast;
 111
 112     private Record(int firstCode, Map<BasicBlock, Boolean> mapLast) {
 113       this.firstCode = firstCode;
 114       this.mapLast = mapLast;
 115     }
 116   }
 117
 118   private Record getFinallyInformation(StructClass cl, StructMethod mt, RootStatement root, CatchAllStatement fstat) {
 119     Map<BasicBlock, Boolean> mapLast = new HashMap<>();
 120
 121     BasicBlockStatement firstBlockStatement = fstat.getHandler().getBasichead();
 122     BasicBlock firstBasicBlock = firstBlockStatement.getBlock();
 123     Instruction instrFirst = firstBasicBlock.getInstruction(0);
 124
 125     int firstcode = 0;
 126
 127     switch (instrFirst.opcode) {
 128       case CodeConstants.opc_pop:
 129         firstcode = 1;
 130         break;
 131       case CodeConstants.opc_astore:
 132         firstcode = 2;
 133     }
 134
 135     ExprProcessor proc = new ExprProcessor(methodDescriptor, varProcessor);
 136     proc.processStatement(root, cl);
 137
 138     SSAConstructorSparseEx ssa = new SSAConstructorSparseEx();
 139     ssa.splitVariables(root, mt);
 140
 141     List<Exprent> lstExprents = firstBlockStatement.getExprents();
 142
 143     VarVersionPair varpaar = new VarVersionPair((VarExprent)((AssignmentExprent)lstExprents.get(firstcode == 2 ? 1 : 0)).getLeft());
 144
 145     FlattenStatementsHelper flatthelper = new FlattenStatementsHelper();
 146     DirectGraph dgraph = flatthelper.buildDirectGraph(root);
 147
 148     LinkedList<DirectNode> stack = new LinkedList<>();
 149     stack.add(dgraph.first);
 150
 151     Set<DirectNode> setVisited = new HashSet<>();
 152
 153     while (!stack.isEmpty()) {
 154       DirectNode node = stack.removeFirst();
 155
 156       if (setVisited.contains(node)) {
 157         continue;
 158       }
 159       setVisited.add(node);
 160
 161       BasicBlockStatement blockStatement = null;
 162       if (node.block != null) {
 163         blockStatement = node.block;
 164       }
 165       else if (node.predecessors.size() == 1) {
 166         blockStatement = node.predecessors.get(0).block;
 167       }
 168
 169       boolean isTrueExit = true;
 170
 171       if (firstcode != 1) {
 172
 173         isTrueExit = false;
 174
 175         for (int i = 0; i < node.exprents.size(); i++) {
 176           Exprent exprent = node.exprents.get(i);
 177
 178           if (firstcode == 0) {
 179             List<Exprent> lst = exprent.getAllExprents();
 180             lst.add(exprent);
 181
 182             boolean found = false;
 183             for (Exprent expr : lst) {
 184               if (expr.type == Exprent.EXPRENT_VAR && new VarVersionPair((VarExprent)expr).equals(varpaar)) {
 185                 found = true;
 186                 break;
 187               }
 188             }
 189
 190             if (found) {
 191               found = false;
 192               if (exprent.type == Exprent.EXPRENT_EXIT) {
 193                 ExitExprent exexpr = (ExitExprent)exprent;
 194                 if (exexpr.getExitType() == ExitExprent.EXIT_THROW && exexpr.getValue().type == Exprent.EXPRENT_VAR) {
 195                   found = true;
 196                 }
 197               }
 198
 199               if (!found) {
 200                 return null;
 201               }
 202               else {
 203                 isTrueExit = true;
 204               }
 205             }
 206           }
 207           else if (firstcode == 2) {
 208             // search for a load instruction
 209             if (exprent.type == Exprent.EXPRENT_ASSIGNMENT) {
 210               AssignmentExprent assexpr = (AssignmentExprent)exprent;
 211               if (assexpr.getRight().type == Exprent.EXPRENT_VAR &&
 212                   new VarVersionPair((VarExprent)assexpr.getRight()).equals(varpaar)) {
 213
 214                 Exprent next = null;
 215                 if (i == node.exprents.size() - 1) {
 216                   if (node.successors.size() == 1) {
 217                     DirectNode nd = node.successors.get(0);
 218                     if (!nd.exprents.isEmpty()) {
 219                       next = nd.exprents.get(0);
 220                     }
 221                   }
 222                 }
 223                 else {
 224                   next = node.exprents.get(i + 1);
 225                 }
 226
 227                 boolean found = false;
 228                 if (next != null && next.type == Exprent.EXPRENT_EXIT) {
 229                   ExitExprent exexpr = (ExitExprent)next;
 230                   if (exexpr.getExitType() == ExitExprent.EXIT_THROW && exexpr.getValue().type == Exprent.EXPRENT_VAR
 231                       && assexpr.getLeft().equals(exexpr.getValue())) {
 232                     found = true;
 233                   }
 234                 }
 235
 236                 if (!found) {
 237                   return null;
 238                 }
 239                 else {
 240                   isTrueExit = true;
 241                 }
 242               }
 243             }
 244           }
 245         }
 246       }
 247
 248       // find finally exits
 249       if (blockStatement != null && blockStatement.getBlock() != null) {
 250         Statement handler = fstat.getHandler();
 251         for (StatEdge edge : blockStatement.getSuccessorEdges(Statement.STATEDGE_DIRECT_ALL)) {
 252           if (edge.getType() != StatEdge.TYPE_REGULAR && handler.containsStatement(blockStatement)
 253               && !handler.containsStatement(edge.getDestination())) {
 254             Boolean existingFlag = mapLast.get(blockStatement.getBlock());
 255             // note: the dummy node is also processed!
 256             if (existingFlag == null || !existingFlag) {
 257               mapLast.put(blockStatement.getBlock(), isTrueExit);
 258               break;
 259             }
 260           }
 261         }
 262       }
 263
 264       stack.addAll(node.successors);
 265     }
 266
 267     // empty finally block?
 268     if (fstat.getHandler().type == Statement.TYPE_BASIC_BLOCK) {
 269
 270       boolean isEmpty = false;
 271       boolean isFirstLast = mapLast.containsKey(firstBasicBlock);
 272       InstructionSequence seq = firstBasicBlock.getSeq();
 273
 274       switch (firstcode) {
 275         case 0:
 276           isEmpty = isFirstLast && seq.length() == 1;
 277           break;
 278         case 1:
 279           isEmpty = seq.length() == 1;
 280           break;
 281         case 2:
 282           isEmpty = isFirstLast ? seq.length() == 3 : seq.length() == 1;
 283       }
 284
 285       if (isEmpty) {
 286         firstcode = 3;
 287       }
 288     }
 289
 290     return new Record(firstcode, mapLast);
 291   }
 292
 293   private static void insertSemaphore(ControlFlowGraph graph,
 294                                       Set<BasicBlock> setTry,
 295                                       BasicBlock head,
 296                                       BasicBlock handler,
 297                                       int var,
 298                                       Record information,
 299                                       int bytecode_version) {
 300     Set<BasicBlock> setCopy = new HashSet<>(setTry);
 301
 302     int finallytype = information.firstCode;
 303     Map<BasicBlock, Boolean> mapLast = information.mapLast;
 304
 305     // first and last statements
 306     removeExceptionInstructionsEx(handler, 1, finallytype);
 307     for (Entry<BasicBlock, Boolean> entry : mapLast.entrySet()) {
 308       BasicBlock last = entry.getKey();
 309
 310       if (entry.getValue()) {
 311         removeExceptionInstructionsEx(last, 2, finallytype);
 312         graph.getFinallyExits().add(last);
 313       }
 314     }
 315
 316     // disable semaphore at statement exit points
 317     for (BasicBlock block : setTry) {
 318       List<BasicBlock> lstSucc = block.getSuccessors();
 319
 320       for (BasicBlock dest : lstSucc) {
 321         // break out
 322         if (dest != graph.getLast() && !setCopy.contains(dest)) {
 323           // disable semaphore
 324           SimpleInstructionSequence seq = new SimpleInstructionSequence();
 325           seq.addInstruction(Instruction.create(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{0}), -1);
 326           seq.addInstruction(Instruction.create(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{var}), -1);
 327
 328           // build a separate block
 329           BasicBlock newBlock = new BasicBlock(++graph.last_id, seq);
 330
 331           // insert between block and dest
 332           block.replaceSuccessor(dest, newBlock);
 333           newBlock.addSuccessor(dest);
 334           setCopy.add(newBlock);
 335           graph.getBlocks().addWithKey(newBlock, newBlock.id);
 336
 337           // exception ranges
 338           // FIXME: special case synchronized
 339
 340           // copy exception edges and extend protected ranges
 341           for (int j = 0; j < block.getSuccessorExceptions().size(); j++) {
 342             BasicBlock hd = block.getSuccessorExceptions().get(j);
 343             newBlock.addSuccessorException(hd);
 344
 345             ExceptionRangeCFG range = graph.getExceptionRange(hd, block);
 346             range.getProtectedRange().add(newBlock);
 347           }
 348         }
 349       }
 350     }
 351
 352     // enable semaphore at the statement entrance
 353     SimpleInstructionSequence seq = new SimpleInstructionSequence();
 354     seq.addInstruction(Instruction.create(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{1}), -1);
 355     seq.addInstruction(Instruction.create(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{var}), -1);
 356
 357     BasicBlock newHead = new BasicBlock(++graph.last_id, seq);
 358
 359     insertBlockBefore(graph, head, newHead);
 360
 361     // initialize semaphore with false
 362     seq = new SimpleInstructionSequence();
 363     seq.addInstruction(Instruction.create(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{0}), -1);
 364     seq.addInstruction(Instruction.create(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{var}), -1);
 365
 366     BasicBlock newHeadInit = new BasicBlock(++graph.last_id, seq);
 367
 368     insertBlockBefore(graph, newHead, newHeadInit);
 369
 370     setCopy.add(newHead);
 371     setCopy.add(newHeadInit);
 372
 373     for (BasicBlock hd : new HashSet<>(newHeadInit.getSuccessorExceptions())) {
 374       ExceptionRangeCFG range = graph.getExceptionRange(hd, newHeadInit);
 375
 376       if (setCopy.containsAll(range.getProtectedRange())) {
 377         newHeadInit.removeSuccessorException(hd);
 378         range.getProtectedRange().remove(newHeadInit);
 379       }
 380     }
 381   }
 382
 383   private static void insertBlockBefore(ControlFlowGraph graph, BasicBlock oldblock, BasicBlock newblock) {
 384     List<BasicBlock> lstTemp = new ArrayList<>();
 385     lstTemp.addAll(oldblock.getPredecessors());
 386     lstTemp.addAll(oldblock.getPredecessorExceptions());
 387
 388     // replace predecessors
 389     for (BasicBlock pred : lstTemp) {
 390       pred.replaceSuccessor(oldblock, newblock);
 391     }
 392
 393     // copy exception edges and extend protected ranges
 394     for (BasicBlock hd : oldblock.getSuccessorExceptions()) {
 395       newblock.addSuccessorException(hd);
 396
 397       ExceptionRangeCFG range = graph.getExceptionRange(hd, oldblock);
 398       range.getProtectedRange().add(newblock);
 399     }
 400
 401     // replace handler
 402     for (ExceptionRangeCFG range : graph.getExceptions()) {
 403       if (range.getHandler() == oldblock) {
 404         range.setHandler(newblock);
 405       }
 406     }
 407
 408     newblock.addSuccessor(oldblock);
 409     graph.getBlocks().addWithKey(newblock, newblock.id);
 410     if (graph.getFirst() == oldblock) {
 411       graph.setFirst(newblock);
 412     }
 413   }
 414
 415   private static Set<BasicBlock> getAllBasicBlocks(Statement stat) {
 416     List<Statement> lst = new LinkedList<>();
 417     lst.add(stat);
 418
 419     int index = 0;
 420     do {
 421       Statement st = lst.get(index);
 422
 423       if (st.type == Statement.TYPE_BASIC_BLOCK) {
 424         index++;
 425       }
 426       else {
 427         lst.addAll(st.getStats());
 428         lst.remove(index);
 429       }
 430     }
 431     while (index < lst.size());
 432
 433     Set<BasicBlock> res = new HashSet<>();
 434
 435     for (Statement st : lst) {
 436       res.add(((BasicBlockStatement)st).getBlock());
 437     }
 438
 439     return res;
 440   }
 441
 442   private boolean verifyFinallyEx(ControlFlowGraph graph, CatchAllStatement fstat, Record information) {
 443     Set<BasicBlock> tryBlocks = getAllBasicBlocks(fstat.getFirst());
 444     Set<BasicBlock> catchBlocks = getAllBasicBlocks(fstat.getHandler());
 445
 446     int finallytype = information.firstCode;
 447     Map<BasicBlock, Boolean> mapLast = information.mapLast;
 448
 449     BasicBlock first = fstat.getHandler().getBasichead().getBlock();
 450     boolean skippedFirst = false;
 451
 452     if (finallytype == 3) {
 453       // empty finally
 454       removeExceptionInstructionsEx(first, 3, finallytype);
 455
 456       if (mapLast.containsKey(first)) {
 457         graph.getFinallyExits().add(first);
 458       }
 459
 460       return true;
 461     }
 462     else {
 463       if (first.getSeq().length() == 1 && finallytype > 0) {
 464         BasicBlock firstsuc = first.getSuccessors().get(0);
 465         if (catchBlocks.contains(firstsuc)) {
 466           first = firstsuc;
 467           skippedFirst = true;
 468         }
 469       }
 470     }
 471
 472     // identify start blocks
 473     Set<BasicBlock> startBlocks = new HashSet<>();
 474     for (BasicBlock block : tryBlocks) {
 475       startBlocks.addAll(block.getSuccessors());
 476     }
 477     // throw in the try body will point directly to the dummy exit
 478     // so remove dummy exit
 479     startBlocks.remove(graph.getLast());
 480     startBlocks.removeAll(tryBlocks);
 481
 482     List<Area> lstAreas = new ArrayList<>();
 483
 484     for (BasicBlock start : startBlocks) {
 485
 486       Area arr = compareSubgraphsEx(graph, start, catchBlocks, first, finallytype, mapLast, skippedFirst);
 487       if (arr == null) {
 488         return false;
 489       }
 490
 491       lstAreas.add(arr);
 492     }
 493
 494     //          try {
 495     //                  DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true);
 496     //          } catch(Exception ex){ex.printStackTrace();}
 497
 498     // delete areas
 499     for (Area area : lstAreas) {
 500       deleteArea(graph, area);
 501     }
 502
 503     //          try {
 504     //                  DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true);
 505     //          } catch(Exception ex){ex.printStackTrace();}
 506
 507     // INFO: empty basic blocks may remain in the graph!
 508     for (Entry<BasicBlock, Boolean> entry : mapLast.entrySet()) {
 509       BasicBlock last = entry.getKey();
 510
 511       if (entry.getValue()) {
 512         removeExceptionInstructionsEx(last, 2, finallytype);
 513         graph.getFinallyExits().add(last);
 514       }
 515     }
 516
 517     removeExceptionInstructionsEx(fstat.getHandler().getBasichead().getBlock(), 1, finallytype);
 518
 519     return true;
 520   }
 521
 522   private static final class Area {
 523     private final BasicBlock start;
 524     private final Set<BasicBlock> sample;
 525     private final BasicBlock next;
 526
 527     private Area(BasicBlock start, Set<BasicBlock> sample, BasicBlock next) {
 528       this.start = start;
 529       this.sample = sample;
 530       this.next = next;
 531     }
 532   }
 533
 534   private Area compareSubgraphsEx(ControlFlowGraph graph,
 535                                   BasicBlock startSample,
 536                                   Set<BasicBlock> catchBlocks,
 537                                   BasicBlock startCatch,
 538                                   int finallytype,
 539                                   Map<BasicBlock, Boolean> mapLast,
 540                                   boolean skippedFirst) {
 541     class BlockStackEntry {
 542       public final BasicBlock blockCatch;
 543       public final BasicBlock blockSample;
 544
 545       // TODO: correct handling (merging) of multiple paths
 546       public final List<int[]> lstStoreVars;
 547
 548       BlockStackEntry(BasicBlock blockCatch, BasicBlock blockSample, List<int[]> lstStoreVars) {
 549         this.blockCatch = blockCatch;
 550         this.blockSample = blockSample;
 551         this.lstStoreVars = new ArrayList<>(lstStoreVars);
 552       }
 553     }
 554
 555     List<BlockStackEntry> stack = new LinkedList<>();
 556
 557     Set<BasicBlock> setSample = new HashSet<>();
 558
 559     Map<String, BasicBlock[]> mapNext = new HashMap<>();
 560
 561     stack.add(new BlockStackEntry(startCatch, startSample, new ArrayList<>()));
 562
 563     while (!stack.isEmpty()) {
 564
 565       BlockStackEntry entry = stack.remove(0);
 566       BasicBlock blockCatch = entry.blockCatch;
 567       BasicBlock blockSample = entry.blockSample;
 568
 569       boolean isFirstBlock = !skippedFirst && blockCatch == startCatch;
 570       boolean isLastBlock = mapLast.containsKey(blockCatch);
 571       boolean isTrueLastBlock = isLastBlock && mapLast.get(blockCatch);
 572
 573       if (!compareBasicBlocksEx(graph, blockCatch, blockSample, (isFirstBlock ? 1 : 0) | (isTrueLastBlock ? 2 : 0), finallytype,
 574                                 entry.lstStoreVars)) {
 575         return null;
 576       }
 577
 578       if (blockSample.getSuccessors().size() != blockCatch.getSuccessors().size()) {
 579         return null;
 580       }
 581
 582       setSample.add(blockSample);
 583
 584       // direct successors
 585       for (int i = 0; i < blockCatch.getSuccessors().size(); i++) {
 586         BasicBlock sucCatch = blockCatch.getSuccessors().get(i);
 587         BasicBlock sucSample = blockSample.getSuccessors().get(i);
 588
 589         if (catchBlocks.contains(sucCatch) && !setSample.contains(sucSample)) {
 590           stack.add(new BlockStackEntry(sucCatch, sucSample, entry.lstStoreVars));
 591         }
 592       }
 593
 594       // exception successors
 595       if (isLastBlock && blockSample.getSeq().isEmpty()) {
 596         // do nothing, blockSample will be removed anyway
 597       }
 598       else {
 599         if (blockCatch.getSuccessorExceptions().size() == blockSample.getSuccessorExceptions().size()) {
 600           for (int i = 0; i < blockCatch.getSuccessorExceptions().size(); i++) {
 601             BasicBlock sucCatch = blockCatch.getSuccessorExceptions().get(i);
 602             BasicBlock sucSample = blockSample.getSuccessorExceptions().get(i);
 603
 604             String excCatch = graph.getExceptionRange(sucCatch, blockCatch).getUniqueExceptionsString();
 605             String excSample = graph.getExceptionRange(sucSample, blockSample).getUniqueExceptionsString();
 606
 607             // FIXME: compare handlers if possible
 608             boolean equalexc = excCatch == null ? excSample == null : excCatch.equals(excSample);
 609
 610             if (equalexc) {
 611               if (catchBlocks.contains(sucCatch) && !setSample.contains(sucSample)) {
 612
 613                 List<int[]> lst = entry.lstStoreVars;
 614
 615                 if (sucCatch.getSeq().length() > 0 && sucSample.getSeq().length() > 0) {
 616                   Instruction instrCatch = sucCatch.getSeq().getInstr(0);
 617                   Instruction instrSample = sucSample.getSeq().getInstr(0);
 618
 619                   if (instrCatch.opcode == CodeConstants.opc_astore &&
 620                       instrSample.opcode == CodeConstants.opc_astore) {
 621                     lst = new ArrayList<>(lst);
 622                     lst.add(new int[]{instrCatch.operand(0), instrSample.operand(0)});
 623                   }
 624                 }
 625
 626                 stack.add(new BlockStackEntry(sucCatch, sucSample, lst));
 627               }
 628             }
 629             else {
 630               return null;
 631             }
 632           }
 633         }
 634         else {
 635           return null;
 636         }
 637       }
 638
 639       if (isLastBlock) {
 640         Set<BasicBlock> setSuccs = new HashSet<>(blockSample.getSuccessors());
 641         setSuccs.removeAll(setSample);
 642
 643         for (BlockStackEntry stackent : stack) {
 644           setSuccs.remove(stackent.blockSample);
 645         }
 646
 647         for (BasicBlock succ : setSuccs) {
 648           if (graph.getLast() != succ) { // FIXME: why?
 649             mapNext.put(blockSample.id + "#" + succ.id, new BasicBlock[]{blockSample, succ, isTrueLastBlock ? succ : null});
 650           }
 651         }
 652       }
 653     }
 654
 655     return new Area(startSample, setSample, getUniqueNext(graph, new HashSet<>(mapNext.values())));
 656   }
 657
 658   private static BasicBlock getUniqueNext(ControlFlowGraph graph, Set<BasicBlock[]> setNext) {
 659     // precondition: there is at most one true exit path in a finally statement
 660
 661     BasicBlock next = null;
 662     boolean multiple = false;
 663
 664     for (BasicBlock[] arr : setNext) {
 665
 666       if (arr[2] != null) {
 667         next = arr[1];
 668         multiple = false;
 669         break;
 670       }
 671       else {
 672         if (next == null) {
 673           next = arr[1];
 674         }
 675         else if (next != arr[1]) {
 676           multiple = true;
 677         }
 678
 679         if (arr[1].getPredecessors().size() == 1) {
 680           next = arr[1];
 681         }
 682       }
 683     }
 684
 685     if (multiple) { // TODO: generic solution
 686       for (BasicBlock[] arr : setNext) {
 687         BasicBlock block = arr[1];
 688
 689         if (block != next) {
 690           if (InterpreterUtil.equalSets(next.getSuccessors(), block.getSuccessors())) {
 691             InstructionSequence seqNext = next.getSeq();
 692             InstructionSequence seqBlock = block.getSeq();
 693
 694             if (seqNext.length() == seqBlock.length()) {
 695               for (int i = 0; i < seqNext.length(); i++) {
 696                 Instruction instrNext = seqNext.getInstr(i);
 697                 Instruction instrBlock = seqBlock.getInstr(i);
 698
 699                 if (!Instruction.equals(instrNext, instrBlock)) {
 700                   return null;
 701                 }
 702                 for (int j = 0; j < instrNext.operandsCount(); j++) {
 703                   if (instrNext.operand(j) != instrBlock.operand(j)) {
 704                     return null;
 705                   }
 706                 }
 707               }
 708             }
 709             else {
 710               return null;
 711             }
 712           }
 713           else {
 714             return null;
 715           }
 716         }
 717       }
 718
 719       //                        try {
 720       //                                DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true);
 721       //                        } catch(IOException ex) {
 722       //                                ex.printStackTrace();
 723       //                        }
 724
 725       for (BasicBlock[] arr : setNext) {
 726         if (arr[1] != next) {
 727           // FIXME: exception edge possible?
 728           arr[0].removeSuccessor(arr[1]);
 729           arr[0].addSuccessor(next);
 730         }
 731       }
 732
 733       DeadCodeHelper.removeDeadBlocks(graph);
 734     }
 735
 736     return next;
 737   }
 738
 739   private boolean compareBasicBlocksEx(ControlFlowGraph graph,
 740                                        BasicBlock pattern,
 741                                        BasicBlock sample,
 742                                        int type,
 743                                        int finallytype,
 744                                        List<int[]> lstStoreVars) {
 745     InstructionSequence seqPattern = pattern.getSeq();
 746     InstructionSequence seqSample = sample.getSeq();
 747
 748     if (type != 0) {
 749       seqPattern = seqPattern.clone();
 750
 751       if ((type & 1) > 0) { // first
 752         if (finallytype > 0) {
 753           seqPattern.removeInstruction(0);
 754         }
 755       }
 756
 757       if ((type & 2) > 0) { // last
 758         if (finallytype == 0 || finallytype == 2) {
 759           seqPattern.removeLast();
 760         }
 761
 762         if (finallytype == 2) {
 763           seqPattern.removeLast();
 764         }
 765       }
 766     }
 767
 768     if (seqPattern.length() > seqSample.length()) {
 769       return false;
 770     }
 771
 772     for (int i = 0; i < seqPattern.length(); i++) {
 773       Instruction instrPattern = seqPattern.getInstr(i);
 774       Instruction instrSample = seqSample.getInstr(i);
 775
 776       // compare instructions with respect to jumps
 777       if (!equalInstructions(instrPattern, instrSample, lstStoreVars)) {
 778         return false;
 779       }
 780     }
 781
 782     if (seqPattern.length() < seqSample.length()) { // split in two blocks
 783       SimpleInstructionSequence seq = new SimpleInstructionSequence();
 784       LinkedList<Integer> oldOffsets = new LinkedList<>();
 785       for (int i = seqSample.length() - 1; i >= seqPattern.length(); i--) {
 786         seq.addInstruction(0, seqSample.getInstr(i), -1);
 787         oldOffsets.addFirst(sample.getOriginalOffset(i));
 788         seqSample.removeInstruction(i);
 789       }
 790
 791       BasicBlock newBlock = new BasicBlock(++graph.last_id, seq);
 792       newBlock.getOriginalOffsets().addAll(oldOffsets);
 793
 794       List<BasicBlock> lstTemp = new ArrayList<>(sample.getSuccessors());
 795
 796       // move successors
 797       for (BasicBlock suc : lstTemp) {
 798         sample.removeSuccessor(suc);
 799         newBlock.addSuccessor(suc);
 800       }
 801
 802       sample.addSuccessor(newBlock);
 803
 804       graph.getBlocks().addWithKey(newBlock, newBlock.id);
 805
 806       Set<BasicBlock> setFinallyExits = graph.getFinallyExits();
 807       if (setFinallyExits.contains(sample)) {
 808         setFinallyExits.remove(sample);
 809         setFinallyExits.add(newBlock);
 810       }
 811
 812       // copy exception edges and extend protected ranges
 813       for (int j = 0; j < sample.getSuccessorExceptions().size(); j++) {
 814         BasicBlock hd = sample.getSuccessorExceptions().get(j);
 815         newBlock.addSuccessorException(hd);
 816
 817         ExceptionRangeCFG range = graph.getExceptionRange(hd, sample);
 818         range.getProtectedRange().add(newBlock);
 819       }
 820     }
 821
 822     return true;
 823   }
 824
 825   public boolean equalInstructions(Instruction first, Instruction second, List<int[]> lstStoreVars) {
 826     if (!Instruction.equals(first, second)) {
 827       return false;
 828     }
 829
 830     if (first.group != CodeConstants.GROUP_JUMP) { // FIXME: switch comparison
 831       for (int i = 0; i < first.operandsCount(); i++) {
 832         int firstOp = first.operand(i);
 833         int secondOp = second.operand(i);
 834         if (firstOp != secondOp) {
 835           // a-load/store instructions
 836           if (first.opcode == CodeConstants.opc_aload || first.opcode == CodeConstants.opc_astore) {
 837             for (int[] arr : lstStoreVars) {
 838               if (arr[0] == firstOp && arr[1] == secondOp) {
 839                 return true;
 840               }
 841             }
 842           }
 843
 844           return false;
 845         }
 846       }
 847     }
 848
 849     return true;
 850   }
 851
 852   private static void deleteArea(ControlFlowGraph graph, Area area) {
 853     BasicBlock start = area.start;
 854     BasicBlock next = area.next;
 855
 856     if (start == next) {
 857       return;
 858     }
 859
 860     if (next == null) {
 861       // dummy exit block
 862       next = graph.getLast();
 863     }
 864
 865     // collect common exception ranges of predecessors and successors
 866     Set<BasicBlock> setCommonExceptionHandlers = new HashSet<>(next.getSuccessorExceptions());
 867     for (BasicBlock pred : start.getPredecessors()) {
 868       setCommonExceptionHandlers.retainAll(pred.getSuccessorExceptions());
 869     }
 870
 871     boolean is_outside_range = false;
 872
 873     Set<BasicBlock> setPredecessors = new HashSet<>(start.getPredecessors());
 874
 875     // replace start with next
 876     for (BasicBlock pred : setPredecessors) {
 877       pred.replaceSuccessor(start, next);
 878     }
 879
 880     Set<BasicBlock> setBlocks = area.sample;
 881
 882     Set<ExceptionRangeCFG> setCommonRemovedExceptionRanges = null;
 883
 884     // remove all the blocks inbetween
 885     for (BasicBlock block : setBlocks) {
 886
 887       // artificial basic blocks (those resulted from splitting)
 888       // can belong to more than one area
 889       if (graph.getBlocks().containsKey(block.id)) {
 890
 891         if (!block.getSuccessorExceptions().containsAll(setCommonExceptionHandlers)) {
 892           is_outside_range = true;
 893         }
 894
 895         Set<ExceptionRangeCFG> setRemovedExceptionRanges = new HashSet<>();
 896         for (BasicBlock handler : block.getSuccessorExceptions()) {
 897           setRemovedExceptionRanges.add(graph.getExceptionRange(handler, block));
 898         }
 899
 900         if (setCommonRemovedExceptionRanges == null) {
 901           setCommonRemovedExceptionRanges = setRemovedExceptionRanges;
 902         }
 903         else {
 904           setCommonRemovedExceptionRanges.retainAll(setRemovedExceptionRanges);
 905         }
 906
 907         // shift extern edges on splitted blocks
 908         if (block.getSeq().isEmpty() && block.getSuccessors().size() == 1) {
 909           BasicBlock succs = block.getSuccessors().get(0);
 910           for (BasicBlock pred : new ArrayList<>(block.getPredecessors())) {
 911             if (!setBlocks.contains(pred)) {
 912               pred.replaceSuccessor(block, succs);
 913             }
 914           }
 915
 916           if (graph.getFirst() == block) {
 917             graph.setFirst(succs);
 918           }
 919         }
 920
 921         graph.removeBlock(block);
 922       }
 923     }
 924
 925     if (is_outside_range) {
 926       // new empty block
 927       BasicBlock emptyblock = new BasicBlock(++graph.last_id);
 928
 929       graph.getBlocks().addWithKey(emptyblock, emptyblock.id);
 930
 931       // add to ranges if necessary
 932       for (ExceptionRangeCFG range : setCommonRemovedExceptionRanges) {
 933         emptyblock.addSuccessorException(range.getHandler());
 934         range.getProtectedRange().add(emptyblock);
 935       }
 936
 937       // insert between predecessors and next
 938       emptyblock.addSuccessor(next);
 939       for (BasicBlock pred : setPredecessors) {
 940         pred.replaceSuccessor(next, emptyblock);
 941       }
 942     }
 943   }
 944
 945   private static void removeExceptionInstructionsEx(BasicBlock block, int blocktype, int finallytype) {
 946     InstructionSequence seq = block.getSeq();
 947
 948     if (finallytype == 3) { // empty finally handler
 949       for (int i = seq.length() - 1; i >= 0; i--) {
 950         seq.removeInstruction(i);
 951       }
 952     }
 953     else {
 954       if ((blocktype & 1) > 0) { // first
 955         if (finallytype == 2 || finallytype == 1) { // astore or pop
 956           seq.removeInstruction(0);
 957         }
 958       }
 959
 960       if ((blocktype & 2) > 0) { // last
 961         if (finallytype == 2 || finallytype == 0) {
 962           seq.removeLast();
 963         }
 964
 965         if (finallytype == 2) { // astore
 966           seq.removeLast();
 967         }
 968       }
 969     }
 970   }
 971 }