IDEA-285172 - [decompiler] - StrongConnectivityHelper refactoring
[idea/community.git] / 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 }